Modelling operations: extrude, revolve, subdivide, combine#

Four operations build most geometry that is not scanned or sculpted. Each takes a mesh or a profile and produces a mesh, and each has an analytic answer you can check it against, which is what this chapter does throughout.

Checking a modelling operation#

Before the operations themselves: a modelling operation that produces a closed solid can be verified. The signed_volume from the meshes chapter returns the enclosed volume, and most primitive shapes have a known one. A wrong answer means wrong winding, a hole, or wrong geometry, and the three are distinguishable.

Treat it as the unit test for every operation below. It catches the faults that are invisible in a render until you rotate the camera.

Extrude#

Take a closed polygon, sweep it along a direction, cap both ends. This is the push/pull of a direct-modelling tool and the single most useful operation in the set.

# $poly is a closed polygon in the xy plane, counter-clockwise seen
# from +z. Extrudes along +z by $h. Returns ($verts, $indices).
sub extrude {
    my ($poly, $h) = @_;
    my $n = @$poly;
    # The outer parens are load-bearing: `my @v = (A), (B)` parses as
    # `(my @v = A), B` and silently stores only the first list.
    my @v = ( (map { [ $_->[0], $_->[1], 0  ] } @$poly),
              (map { [ $_->[0], $_->[1], $h ] } @$poly) );
    my @i;
    # top cap: fan over the upper ring, already CCW seen from +z
    push @i, ($n, $n + $_, $n + $_ + 1) for 1 .. $n - 2;
    # bottom cap: same fan reversed, so it faces -z
    push @i, (0, $_ + 1, $_) for 1 .. $n - 2;
    # sides: one quad per edge, wound outward
    for my $e (0 .. $n - 1) {
        my $f = ($e + 1) % $n;
        push @i, ($e, $f, $n + $f), ($e, $n + $f, $n + $e);
    }
    return (\@v, \@i);
}

An n-gon extrudes to 2n vertices and 4n - 4 triangles: n - 2 per cap and two per side quad.

unit square extruded by 2: 8 vertices, 12 triangles
signed volume = 2.0000  (analytic: area 1 * height 2 = 2)
unit hexagon extruded by 1: 20 triangles, volume 2.5981 (analytic 2.5981)

Extruding a unit square produces exactly the cube from the meshes chapter: 8 vertices, 12 triangles. The hexagon lands on 3*sqrt(3)/2 to four decimal places.

Fan-capping is only valid for a convex polygon. A concave outline needs ear clipping, and a polygon with holes needs a real triangulator; both produce caps that self-overlap if fanned.

Symptom: an extruded shape looks right from outside but its volume test returns a small or negative number. Cause: cap winding, usually the bottom cap not reversed.

Revolve#

Sweep a profile around an axis. The profile is a list of [radius, y] points; each is rotated into seg positions around the Y axis and consecutive rings are joined.

for my $k (0 .. $p - 2) {
    my ($q0, $q1) = ($s * $p + $k,     $t * $p + $k);
    my ($q2, $q3) = ($t * $p + $k + 1, $s * $p + $k + 1);
    # wound so the normal points away from the axis
    push @i, ($q0, $q3, $q2), ($q0, $q2, $q1);
}

Unlike extrude, revolve only approximates its analytic shape, and the segment count is the knob. A cylinder of radius 1 and height 2:

cylinder r=1 h=2, analytic volume 6.2832
    8 segments:   32 triangles, volume 5.6569
   16 segments:   64 triangles, volume 6.1229
   32 segments:  128 triangles, volume 6.2429
   64 segments:  256 triangles, volume 6.2731
  256 segments: 1024 triangles, volume 6.2826

The volume approaches pi * r^2 * h from below, because an inscribed prism is contained by the cylinder it approximates. Every doubling of segments cuts the error by roughly four, so accuracy is cheap in geometry: halving the error takes only about 41 percent more segments. 32 segments is within 0.7 percent and is the usual default in modelling tools for a reason.

A profile that reaches the axis (radius = 0) needs no cap at that end, and joining a full ring to a single axis point there produces degenerate zero-area triangles unless it is special-cased.

Subdivision#

Split each triangle into four by its edge midpoints. On its own this adds geometry without adding shape; the operation becomes useful when the new vertices are moved, which is what a subdivision surface does. Projecting them onto a sphere is the clearest case:

my $ab = $midpoint->($a, $b);
my $bc = $midpoint->($b, $c);
my $ca = $midpoint->($c, $a);
push @ni, ($a,$ab,$ca), ($ab,$b,$bc), ($ca,$bc,$c), ($ab,$bc,$ca);

The midpoint helper must cache by edge, or the two triangles sharing an edge each create their own copy of the midpoint and the mesh comes apart into unwelded fragments.

Starting from an octahedron and normalising every new vertex:

unit sphere, analytic volume 4.18879
  level 0:    8 triangles,    6 vertices, volume 1.33333
  level 1:   32 triangles,   18 vertices, volume 2.94281
  level 2:  128 triangles,   66 vertices, volume 3.81773
  level 3:  512 triangles,  258 vertices, volume 4.09160
  level 4: 2048 triangles, 1026 vertices, volume 4.16420

Triangles multiply by four per level. Vertices do not: each level yields 4V - 6, which the table confirms at every step (18, 66, 258, 1026), because the midpoints on shared edges are created once and used twice. The volume converges from below again, and level 4 is within 0.6 percent at 2048 triangles.

This is the simplest subdivision scheme. Catmull-Clark, the one modelling tools use, works on quads, weights each new vertex by its neighbours instead of projecting onto a known surface, and converges to a smooth limit surface with no target shape needed. The mechanism here is the same: insert vertices, then move them.

Boolean operations#

Union, difference and intersection of two solids. This is the operation users reach for most and the one that is hardest to implement, so the honest position matters: this chapter does not implement it. A correct constructive solid geometry (CSG) implementation is a project, not a page.

The reason is that it is not really a geometry problem, it is a robustness problem. The algorithm is:

  1. Split every triangle of A against the planes of B, and the reverse.

  2. Classify each resulting fragment as inside, outside, or on the boundary of the other solid.

  3. Keep the fragments the operation calls for, and flip the winding of B’s kept fragments for a difference.

Step 1 in floating point is where implementations fail. A vertex landing exactly on a plane, two coplanar faces, a nearly-degenerate sliver triangle: each needs an explicit decision, and getting one wrong yields a mesh with a hole rather than an error.

The classification in step 2 rests on one primitive that is worth having on its own, since picking and collision need it too: is a point inside a closed mesh? Cast a ray and count crossings. Odd means inside.

# FRAGMENT: the ray/triangle body is elided. Requires a CLOSED, manifold
# mesh. The ray direction is nudged off axis because a ray hitting an
# edge or vertex exactly is counted twice or not at all, and nudging is
# cheaper than special-casing every degenerate hit.
sub point_inside {
    my ($v, $i, $p) = @_;
    my $hits = 0;
    my $dir = v_norm([1, 0.0001, 0.0002]);
    for (my $k = 0; $k < @$i; $k += 3) {
        # ... Möller-Trumbore ray/triangle test, yielding $t ...
        $hits++ if $t > 1e-9;          # count forward hits only
    }
    return $hits % 2;
}

  [0,0,0         ] inside
  [0.9,0.9,0.9   ] inside
  [1.1,0,0       ] outside
  [2,2,2         ] outside
  [-0.5,0.5,0    ] inside

The Möller-Trumbore test in the loop returns the barycentric coordinates as a side effect of solving for the intersection, which is why the same routine serves picking in the scene-graph chapter.

For real boolean work, model as a tree of operations rather than committing to a result mesh: keep the primitives and the operations that combine them, and evaluate to triangles only for display or export. That is what CAD tools store, and it keeps the operations reversible.

Next#

Objects can now be built. The next chapter arranges them: transform hierarchies, cameras, picking, and the spatial structures that keep scenes fast.