Shape Grammars with Convex Polyhedra on the GPU

One of the most important aspects in the creation of games and CGI movies is the creation of detailed 3d models. Throughout the years, procedural modeling techniques have been successfully used to aid artists in this laborious task. One of the most commonly used techniques is the shape grammar. A shape grammar is a formal language that describes how to build a model. In recent years, the evaluation of shape grammars has been moved to the GPU.

PGA is our parallel shape grammar evaluator built on CUDA/C++. Currently PGA works with symbolic shape representations rather then ie. polygonal meshes. Because of that, PGA doesn't support general convex polyhedra.

The goal of this project is to define what shape representation suits better the GPU evaluation of shape grammars with convex polyhedra. Additionally, it's also necessary to implement (as efficient as possible) the modeling operators for convex polyhedra ie. subdivision and extrusion.

Tasks

• Caught up with PGA code base.
• Review fundamental literature on shape grammars and shape grammar evaluation on the GPU.
• Study, implement and benchmark different possible shape representations for convex polyhedra.
• Study and implement efficient ways to parallelize modeling operators on general convex polyhedra.

Requirements:

• Good C++ knowledge (in special template metaprogramming)
• Some knowledge in GPU programming (shaders or CUDA)