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.
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.
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:
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 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.
The orbit camera#
Two angles and a distance. This is the camera every modelling tool uses, and the one the modeller capstone needs.
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.
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 advice applies, since accumulating Euler angles across thousands of frames drifts and eventually gimbal-locks.
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.
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. The aspect multiplies x because the field of view argument is vertical.
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:
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.
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:
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:
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:
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 hands the work to the graphics card, through Peta::WebGPU.