# 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. ```{index} single: modelling operation single: signed volume; as a test ``` ## 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](meshes) 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. ```{index} single: extrusion single: push/pull single: ear clipping ``` ## 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. ```perl # $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. ```text 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. ```{index} single: revolve single: surface of revolution ``` ## 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. ```perl 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: ```text 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. ```{index} single: subdivision single: subdivision surface single: Catmull-Clark subdivision ``` ## 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: ```perl 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: ```text 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. ```{index} single: boolean operations; on solids single: constructive solid geometry single: CSG single: point in mesh test single: Möller-Trumbore algorithm ``` ## 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. ```perl # 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; } ``` ```text [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](scene-graphs) arranges them: transform hierarchies, cameras, picking, and the spatial structures that keep scenes fast.