Implementing Groups
Groups are abstract shapes with no surface of their own, taking their form instead from the shapes they contain. This allows you to organize them in trees, with groups containing both other groups and concrete primitives. The real killer feature of groups, though, is that groups may be transformed just like any other shape, and those transforms then apply implicitly to any shapes contained by the group. You just put shapes in a group, transform the group, and voilà—it all applies as a single unit.
Let’s make this happen. You’ll tackle this in several steps:
- Create a new shape subclass called Group.
- Add a new attribute to Shape, called parent, which refers to the group that contains the shape (if any).
- Write a function for adding shapes to a group.
- Implement the ray-group intersection algorithm.
- Implement the necessary changes to compute the normal on a shape that is part of a group.
|
This section describes a bidirectional tree structure, where parent nodes reference child nodes and child nodes reference parent nodes. Not all programming languages make this easy to implement. If your language makes this challenging, consider reading through the entire chapter first, and then implement the feature in your own way. If you get stuck, you can always ask for tips on the forum.[20] |
Start by creating your new Group class for aggregating shapes.
Test #1: Creating a New Group
A group is a shape, which starts as an empty collection of shapes.
This test introduces a new function, group, which returns a new Group instance. The test then shows that the group has its own transformation (unsurprising, as it ought to be a Shape subclass), and the collection it represents should be empty.
| | Scenario: Creating a new group |
| | Given g ← group() |
| | Then g.transform = identity_matrix |
| | And g is empty |
Make that pass by adding a Group class, making it a container of shapes, and making it behave like a Shape itself. The next test will address the Shape side of things by adding a parent attribute.
Test #2: A Shape Has a Parent Attribute
A shape has an optional parent, which is unset by default.
This test requires a new attribute on Shape, called parent, which may be either unset (the default) or may be set to a Group instance. You’ll see your old test_shape function from Refactoring Shapes, used here as a generic shape to demonstrate the addition of the new attribute.
| | Scenario: A shape has a parent attribute |
| | Given s ← test_shape() |
| | Then s.parent is nothing |
Next up, you’ll write a function for adding shapes as children of a group, linking them together in a kind of tree.
Test #3: Adding a Child to a Group
Adding a child to a group makes the group the child’s parent and adds the child to the group’s collection.
This test adds a new function, add_child(group, shape) and shows how it is used to add a child shape to a group.
| | Scenario: Adding a child to a group |
| | Given g ← group() |
| | And s ← test_shape() |
| | When add_child(g, s) |
| | Then g is not empty |
| | And g includes s |
| | And s.parent = g |
Make that pass, and you can start moving on to the fun stuff! It’s time to intersect rays with these groups of shapes.
Tests #4 and 5: Intersecting a Ray with a Group
Two tests show that a ray intersects a group if and only if the ray intersects at least one child shape contained by the group.
The first test is the trivial case—casting a ray and checking to see if it intersects an empty group. The resulting collection of intersections should be empty.
| | Scenario: Intersecting a ray with an empty group |
| | Given g ← group() |
| | And r ← ray(point(0, 0, 0), vector(0, 0, 1)) |
| | When xs ← local_intersect(g, r) |
| | Then xs is empty |
The second test builds a group of three spheres and casts a ray at it. The spheres are arranged inside the group so that the ray will intersect two of the spheres but miss the third. The resulting collection of intersections should include those of the two spheres.
| | Scenario: Intersecting a ray with a nonempty group |
| | Given g ← group() |
| | And s1 ← sphere() |
| | And s2 ← sphere() |
| | And set_transform(s2, translation(0, 0, -3)) |
| | And s3 ← sphere() |
| | And set_transform(s3, translation(5, 0, 0)) |
| | And add_child(g, s1) |
| | And add_child(g, s2) |
| | And add_child(g, s3) |
| | When r ← ray(point(0, 0, -5), vector(0, 0, 1)) |
| | And xs ← local_intersect(g, r) |
| | Then xs.count = 4 |
| | And xs[0].object = s2 |
| | And xs[1].object = s2 |
| | And xs[2].object = s1 |
| | And xs[3].object = s1 |
To make both of these tests pass, implement the local_intersect function for your Group shape and have it iterate over all of the group’s children, calling intersect on each of them in turn. It should aggregate the resulting intersections into a single collection and sort them all by t.
Test #6: Group Transformations
Demonstrate that group and child transformations are both applied.
This test creates a group and adds a single sphere to it. The new group is given one transformation, and the sphere is given a different transformation. A ray is then cast in such a way that it should strike the sphere, as long as the sphere is being transformed by both its own transformation and that of its parent.
| | Scenario: Intersecting a transformed group |
| | Given g ← group() |
| | And set_transform(g, scaling(2, 2, 2)) |
| | And s ← sphere() |
| | And set_transform(s, translation(5, 0, 0)) |
| | And add_child(g, s) |
| | When r ← ray(point(10, 0, -10), vector(0, 0, 1)) |
| | And xs ← intersect(g, r) |
| | Then xs.count = 2 |
The lovely thing about this test is that it should already pass if your group’s local_intersect function calls intersect on its children. Make sure this is so.
When you’re ready, read on! The next piece of this puzzle requires finding the normal vector on a child object.