Essential Geometry 2: Basic operations

Yesterday's post covered geometric primitives and basic shapes for use in a 3D procedural modeling framework.  Today's post covers some basic operations that can be performed using those primitives and shapes.

We'll start off with the basic transformation operations.  A geometric primitive can be translated (moved), rotated (orientation adjusted), or scaled (made larger or smaller).  These are fairly basic operations which are well understood, and are typically performed using linear algebra (matrix math). Since this is such a well-documented area, I won't address it in great depth, other than to say these are truly fundamental operations for 2D and 3D geometry on a computer.  Even if you're not planning on procedural modeling, any framework needs to support them.

Figure 1: Transformation operations

Next we'll discuss three operations for generating 3D content from 2D polygons.  Extrusion, revolution, and sweeping can all be powerful operations.  I mentioned extrusion briefly a few posts back.  It can be used to generate tubes, columns, boxes, ducts, buildings, etc. from a simply polygon like a rectangle, octagon, etc.  Implementing extrusion is fairly simply.  Make a copy of the polygon. Translate the copy along the extrusion vector (red arrow in figure 2).  Then for each edge of the original polygon, create a new rectangular face that connects that edge with the corresponding edge on the copy.

Figure 2: Extrusion

Revolution is similar but a bit more complex.  With revolution, a polygon is swept through space in a circular arc around an axis.  (In figure 3, the axis is shown as the red vertical line.)  The arc may be partial (e.g. 90 degrees) or may be a complete circle.  To implement, we perform the rotation as an iterative process.  Make a copy of the polygon and rotate it some fraction of the desired rotation.  As with extrusion, create faces between edges of the previous polygon and the next polygon.  Repeat the process until the desired rotation is accomplished.

Figure 3: Revolution

Sweep is similar to revolution, but rather than simple rotation about an axis it involves following a path.  The path could be defined by a line segment (like extrusion), an arc (like revolution), a polyline, or a spline.  I cannot fully describe implementation at this time as it is something I am actively working on a proper implementation for, as I intend to use sweep for road and railroad shapes.

Figure 4: Sweep

Constructive solid geometry (CSG) operations are used to manipulate 3D solids (polyhedrons) much like boolean or set operations.  A union combines two solids.  An intersection yields the portion of solids that overlap.  A difference removes that part of solid A which solid B overlaps.  The simplified 2D equivalent of these operations is shown in figure 5.

Figure 5: Constructive solid geometry (CSG) operations

You may be wondering why CSG is useful.  If you wanted to create a dimpled cube, you could take the difference between a cube and a sphere.  If you wanted a thick-walled hollow tube, you could take the difference between one cylinder and a cylinder of smaller diameter.  You could use CSG to put window and door shaped holes into walls, carve star-shaped patterns into a box representing a frieze, or carve or raise decorative elements for columns.

Figure 6: Some scenarios for CSG use

CSG operations can be implemented using BSP (binary space partitioning) trees.  In Game Programming Gems 5, Octavian Marius Chincisan has an article on doing so, "CSG Construction Using BSP Trees," with an accompanying C++ implementation.  The OpenJSCAD uses a JavaScript implementation (CSG.js) to perform CSG operations inside a web browser, rendering them via OpenGL.  I ported CSG.js to C# but have yet to fully integrate it into anything just yet.  The tests for it produce output files which I can view using Blender.

Figure 7: Rendering of a shape produced using CSG operations.

There are more useful operations to discuss - such as those used in CGA Shape, and some common operations for edges - but those will wait for a future day.  This post covers some of the basic essential operations and provides some details to aid in implementation.