# Scene graphs: hierarchy, cameras, picking A scene is more than a pile of meshes. Objects are attached to other objects, a camera has to be steered, the user clicks on something and expects the right thing selected, and none of it may cost a pass over every triangle. This chapter covers those four. ```{index} single: scene graph single: transform hierarchy single: local transform single: world transform ``` ## The hierarchy Each node holds a **local** transform, relative to its parent, and a list of children. Its **world** transform is the parent's world times its own local, which means one top-down walk computes the whole scene. ```perl sub walk { # $parent_world is the identity at the root. Multiplication order # is parent * local: the local transform applies FIRST, then the # parent's, which is the right-to-left rule from foundations. my ($node, $parent_world, $out) = @_; my $world = m_mul($parent_world, $node->{local}); $out->{ $node->{name} } = $world; walk($_, $world, $out) for @{ $node->{children} }; return $out; } ``` A turntable yawed 90 degrees, an arm translated 4 along its own x, and a hand raised 2 above the arm: ```text turntable origin at [ 0.00, 0.00, 0.00] arm origin at [ 0.00, 0.00, -4.00] hand origin at [ 0.00, 2.00, -4.00] ``` The arm was placed 4 along **its own** x, and the turntable's yaw put it on world -z. The hand rose 2 in y, which the yaw leaves alone. That is the entire value of a hierarchy: the arm's author never thinks about the turntable's angle. **Symptom: rotating a parent makes a child orbit when it should spin in place, or vice versa.** Cause: the multiplication order at this line. It is the [foundations](foundations) order rule appearing where it costs the most. Recomputing the whole tree every frame is normal and cheap. Caching world transforms is an optimisation that needs invalidation on every parent change, and getting that wrong is a much worse bug than the recompute is a cost. ```{index} single: orbit camera single: fly camera ``` ## The orbit camera Two angles and a distance. This is the camera every modelling tool uses, and the one the [modeller capstone](capstone-modeller) needs. ```perl sub orbit_eye { # $yaw and $pitch in radians, $dist from the target. Clamp pitch # short of +/- 90 degrees: at exactly vertical the view direction # is parallel to `up` and look_at degenerates. my ($target, $yaw, $pitch, $dist) = @_; return [ $target->[0] + $dist * cos($pitch) * sin($yaw), $target->[1] + $dist * sin($pitch), $target->[2] + $dist * cos($pitch) * cos($yaw) ]; } ``` The camera has an invariant worth testing against, because it holds at every angle: the target must land on the view-space -z axis at exactly the orbit distance. ```text yaw 0: eye [ 0.00, 3.42, 9.40] target in view space [ 0.00, 0.00, -10.00] yaw 45: eye [ 6.64, 3.42, 6.64] target in view space [ 0.00, -0.00, -10.00] yaw 90: eye [ 9.40, 3.42, 0.00] target in view space [ 0.00, 0.00, -10.00] ``` The eye swings around, the target stays put. Any camera bug shows up here immediately as a target that drifts off the axis or changes depth. A **fly camera** is the other common kind: position plus a forward direction, moved with the keyboard and turned with the mouse. It stores orientation rather than deriving it, which is where the [quaternion](foundations) advice applies, since accumulating Euler angles across thousands of frames drifts and eventually gimbal-locks. ```{index} single: picking single: ray; through a pixel single: ray-sphere intersection ``` ## Picking The user clicks a pixel and means an object. Turning the first into the second is a **ray** through that pixel, then an intersection test. The ray could be built by inverting the view-projection matrix, but for a camera it is cheaper to construct it directly from the camera axes: the pixel's normalised device coordinates scale the right and up vectors, and forward supplies the rest. ```perl sub pick_ray { my ($eye, $target, $up, $fovy, $aspect, $sx, $sy, $W, $H) = @_; my $f = v_norm(v_sub($target, $eye)); my $s = v_norm(v_cross($f, $up)); my $u = v_cross($s, $f); my $ndc_x = 2 * ($sx + 0.5) / $W - 1; my $ndc_y = 1 - 2 * ($sy + 0.5) / $H; # screen y is down my $th = tan_half($fovy); my @d = map { $f->[$_] + $s->[$_] * $ndc_x * $th * $aspect + $u->[$_] * $ndc_y * $th } 0..2; return ($eye, v_norm(\@d)); } ``` The `+ 0.5` samples the pixel centre and the `1 -` flips screen y, both for the same reasons as in the [rasteriser](software-rasteriser). The aspect multiplies x because the field of view argument is vertical. ```text centre pixel ray dir [ 0.00, -0.00, -1.00] right-of-centre dir [ 0.50, -0.00, -0.87] unit sphere at origin: hit at t=9.000 (eye is 10 away, r=1) same sphere from the off-centre ray: miss ``` The centre pixel gives exactly `-z`, and a unit sphere at the origin is hit at `t = 9` from an eye 10 away. Both are checkable by hand, which is what makes them useful tests. Test against **bounding volumes first**, and only then against triangles. A sphere test is a handful of operations: ```perl sub ray_sphere { # Returns the near intersection distance, or undef. $d MUST be # normalised or $t is in units of $d's length rather than distance. my ($o, $d, $c, $r) = @_; my $oc = v_sub($o, $c); my $b = 2 * v_dot($oc, $d); my $cc = v_dot($oc, $oc) - $r * $r; my $disc = $b*$b - 4*$cc; return undef if $disc < 0; my $t = (-$b - sqrt($disc)) / 2; return $t > 0 ? $t : undef; } ``` The `$t > 0` check rejects hits behind the eye. Without it, clicking empty space selects whatever is behind the camera. ```{index} single: bounding volume hierarchy single: BVH single: slab method single: frustum culling ``` ## The bounding volume hierarchy Testing every object per ray is fine for ten objects and hopeless for ten thousand. A **BVH** is a binary tree of nested boxes: if the ray misses a node's box, nothing inside it needs testing. Building it is a recursive median split along the widest axis: ```perl sub build_bvh { my ($items) = @_; my ($lo, $hi) = bounds($items); return { lo => $lo, hi => $hi, items => $items } if @$items <= 4; my $ax = 0; my $best = $hi->[0] - $lo->[0]; for my $a (1, 2) { my $e = $hi->[$a] - $lo->[$a]; if ($e > $best) { $best = $e; $ax = $a } } my @sorted = sort { $a->{c}[$ax] <=> $b->{c}[$ax] } @$items; my $mid = int(@sorted / 2); return { lo => $lo, hi => $hi, left => build_bvh([ @sorted[0 .. $mid-1] ]), right => build_bvh([ @sorted[$mid .. $#sorted] ]) }; } ``` Splitting the **widest** axis is what keeps the boxes compact; always splitting x produces long thin nodes that overlap and defeat the pruning. The leaf size of 4 is a tuning constant: smaller leaves prune better and cost more nodes to traverse. The ray/box test is the slab method, intersecting the ray with each pair of parallel planes and keeping the overlap: ```perl my $inv = 1 / $d->[$ax]; my ($t1, $t2) = (($lo->[$ax]-$o->[$ax])*$inv, ($hi->[$ax]-$o->[$ax])*$inv); ($t1, $t2) = ($t2, $t1) if $t1 > $t2; $tmin = $t1 if $t1 > $tmin; $tmax = $t2 if $t2 < $tmax; return 0 if $tmin > $tmax; ``` A zero component in the direction needs handling before the division, or the reciprocal is an infinity and the comparisons stop meaning what they should. Over 512 objects on a grid, with one ray: ```text 512 objects, 255 BVH nodes BVH: hit object 0 at t=9.00, 39 nodes visited linear: hit object 0 at t=9.00, 512 objects tested same answer: yes ``` Thirty-nine node visits against 512 object tests, for the same answer. The 255 nodes are 128 leaves of four objects each plus 127 internal nodes, which is where the memory goes. The same structure serves collision detection and ray tracing. In a renderer its sibling is **frustum culling**: test each node's box against the six planes of the view volume and skip whole subtrees that fall outside, which is the same pruning with a different predicate. ## Next This closes the geometry half of the guide. Everything so far has been plain Perl, computing pixels or coordinates in software. The [next arc](gpu-device-and-window) hands the work to the graphics card, through `Peta::WebGPU`.