Wednesday, December 21, 2016

Essential Geometry 1: Primitives and Basic Shapes

I've been thinking about the architecture for dealing with procedural generation for material culture: buildings, bridges, roads, fountains, etc.  I mentioned a bit in previous posts about procedural generation of buildings, terrain, and even language.  The building blocks of these different types of procedural content vary greatly, but for material culture it is represented in a virtual world by geometry.  Culture and semantics may drive arrangement and meaning, but the representation ultimately takes the form of geometry.

Mostly it is simple angular or curved geometry, not organic shapes.  As such, such geometry is often easily described in terms of primitives.  The most basic primitives are simple, generic representations of shapes in zero to three dimensions.  In the example below, a four-sided rectangle is shown for the face (polygon), but that could as easily be a hexagon, an octagon, etc.  Likewise, the polyhedron could be a dodecahedron, a tetrahedron, or an arbitrary mesh.

Figure 1: Essential geometric primitives

Because rendering 3D graphics usually requires a similar representation to what I've just described (triangles are best), more complex representations are built upon these basic geometric primitives. When rendering, even a cylinder, sphere, cone, or torus is an approximation in the form of a polyhedron.  (Ray tracing is sometimes an exception.)  All of the shapes in the figure 2 below could be represented as either a face/polygon or as a polyhedron.

Figure 2: Useful basic shapes
For procedural modeling, being able to easily create the basic shapes above can be quite useful. However, we still only need to have classes that represent the four primitives in figure 1. Any shape from figure 2 can be generated as an instance of one of the classes from figure 1.  A shape factory can generate the required instances based upon supplied parameters.  As such, a class representing each basic shape is not required in all situations; I do not plan to create such classes, and plan to rely upon a shape factory utility class to generate instances of the figure 1 classes that represent figure 2 shapes.

There are well-known algorithms for most of them.  The GLUT library used with OpenGL contains implementations of algorithms for generating the sphere, cube, cone, torus, dodecahedron, octahedron, tetrahedron, icosahedron, and the ever-populate teapot shapes.  The FreeGLUT library is an open-source (MIT X licensed) alternative to GLUT so you could review that source code for examples, or search online.  Paul Bourke's web site has descriptions and details for some of them, such as the superellipsoid.  

Some of the 3D shapes can also be produced by performing an extrusion or revolution of a sphere or rectangle.  I'll address that more in a future post on geometric operations that should be supported in order to provide for procedural modeling capabilities.   This post has covered the primitives and the basic shapes at a high level.  More details will be discussed in future posts.


No comments:

Post a Comment