Implementing CSG
For simplicity’s sake, your implementation will treat all CSG operations as strictly binary, meaning that each one takes exactly two shapes as input. This may seem restrictive, but since a CSG object is itself a shape, you can build arbitrarily complex CSG operations by combining them in a hierarchy, like this:
You’ll render these shapes by intersecting them with a ray, as you’ve done with every other shape you’ve implemented. Intersecting a ray with a CSG shape begins just like intersecting one with a Group: you first intersect the ray with the shape’s children. Then, you iterate over the resulting intersection records, tracking which ones are inside which child and filtering out those that don’t conform to the current operation. The resulting list of intersections is then returned.
The devil, as ever, is in the details. We’ll walk through this process one bit at a time, following these steps:
- Create a CSG shape by providing an operation and two operand shapes, left and right.
- Implement the rules for union, intersection, and difference.
- Filter a list of intersections using the rules from step 2.
- Demonstrate what happens when a ray misses a CSG object.
- Demonstrate what happens when a ray hits a CSG object.
Begin by creating the CSG shape itself.
Test #1: Creating a CSG Shape
A CSG shape is composed of an operation and two operand shapes.
Instantiate a new CSG shape. For the sake of the test, use the union operation and give it a sphere and a cube for the two operands.
| | Scenario: CSG is created with an operation and two shapes |
| | Given s1 ← sphere() |
| | And s2 ← cube() |
| | When c ← csg("union", s1, s2) |
| | Then c.operation = "union" |
| | And c.left = s1 |
| | And c.right = s2 |
| | And s1.parent = c |
| | And s2.parent = c |
The operands are referred to as left and right, mirroring the structure of a binary tree where the two children of a parent are arranged with one on the left and one on the right. Note that your code should set the parent attribute of both child shapes to the CSG shape itself, just as if they were part of a group.
Test #2: Evaluating the Rule for a CSG Union Operation
A CSG union preserves all intersections on the exterior of both shapes.
Consider the following illustration, showing a ray intersecting two overlapping spheres. If the two spheres represent a union operation, the highlighted intersections are the ones to be preserved; the rest are ignored.
You’ll encode this rule in a new function, called intersection_allowed(op, lhit, inl, inr). The arguments are interpreted as follows:
- op is the CSG operation being evaluated.
- lhit is true if the left shape was hit, and false if the right shape was hit.
- inl is true if the hit occurs inside the left shape.
- inr is true if the hit occurs inside the right shape.
Referring to the previous figure, and assuming the ray moves from left to right, you would evaluate the four intersections with the following calls to intersection_allowed:
-
intersection_allowed("union", true, false, false)—the hit is on the outside of the left shape.
-
intersection_allowed("union", false, true, false)—the hit is on the outside of the right shape, while inside the left shape.
-
intersection_allowed("union", true, true, true)—the hit is on the inside of the left shape, while inside the right shape.
-
intersection_allowed("union", false, false, true)—the hit is on the inside of the right shape.
You can arrange the arguments in those calls to form a truth table, a method of showing boolean input values and the expected output of some operation on them. The following test describes the basic outline you’ll use to exercise all three operations, as well as a truth table to describe how the intersection_allowed function works with the union operation.
| | Scenario Outline: Evaluating the rule for a CSG operation |
| | When result ← intersection_allowed("<op>", <lhit>, <inl>, <inr>) |
| | Then result = <result> |
| | |
| | Examples: |
| | | op | lhit | inl | inr | result | |
| | | union | true | true | true | false | |
| | | union | true | true | false | true | |
| | | union | true | false | true | false | |
| | | union | true | false | false | true | |
| | | union | false | true | true | false | |
| | | union | false | true | false | false | |
| | | union | false | false | true | true | |
| | | union | false | false | false | true | |
The goal is to implement intersection_allowed in such a way as to make sure it returns the correct answer for all possible combinations of inputs, thus allowing only the correct intersections.
To make the test pass, consider what the union operation actually means. You only want the intersections that are not inside another object. If the hit is on the left object, it must not also be inside the right, and if it is on the right, it must not simultaneously be inside the left. In pseudocode, the logic looks something like this:
| | function intersection_allowed(op, lhit, inl, inr) |
| | if op is "union" |
| | return (lhit and not inr) or (not lhit and not inl) |
| | end if |
| | |
| | # default answer |
| | return false |
| | end function |
Implement that to make the test pass. Next you’ll tackle the rule for the intersect operation.
Test #3: Evaluating the Rule for a CSG Intersect Operation
A CSG intersect preserves all intersections where both shapes overlap.
Take a look at the next illustration, again showing a ray intersecting two overlapping spheres. This time, though, the highlights show which intersections are kept by a CSG intersect operation.
The intersections are chosen in such a way as to preserve the volume that the shapes have in common. Add the following truth table to the end of the one you started in the previous test, showing how the intersection_allowed function ought to behave in this case.
| | # append after the union examples... |
| | | intersection | true | true | true | true | |
| | | intersection | true | true | false | false | |
| | | intersection | true | false | true | true | |
| | | intersection | true | false | false | false | |
| | | intersection | false | true | true | true | |
| | | intersection | false | true | false | true | |
| | | intersection | false | false | true | false | |
| | | intersection | false | false | false | false | |
To make those examples pass, you want to allow only those intersections that strike one object while inside the other. If a ray hits the object on the left, the intersection must be inside the right, and vice versa. In pseudocode, that logic looks like this:
| | function intersection_allowed(op, lhit, inl, inr) |
| | if op is "union" |
| | return (lhit and not inr) or (not lhit and not inl) |
| » | else if op is "intersect" |
| » | return (lhit and inr) or (not lhit and inl) |
| | end if |
| | |
| | return false |
| | end function |
Get those new examples passing, and then move on to the third CSG operation: difference.
Test #4: Evaluating the Rule for a CSG Difference Operation
A CSG difference preserves all intersections not exclusively inside the object on the right.
Take a look at the following diagram of two overlapping spheres. The intersections are now highlighted to represent a CSG difference operation.
Add this last truth table to the end of the other two, to show how the difference operation should work.
| | # append after the intersection examples... |
| | | difference | true | true | true | false | |
| | | difference | true | true | false | true | |
| | | difference | true | false | true | false | |
| | | difference | true | false | false | true | |
| | | difference | false | true | true | true | |
| | | difference | false | true | false | true | |
| | | difference | false | false | true | false | |
| | | difference | false | false | false | false | |
The difference operation will keep every intersection on left that is not inside right, and every intersection on right that is inside left. Written as pseudocode, it looks like this:
| | function intersection_allowed(op, lhit, inl, inr) |
| | if op is "union" |
| | return (lhit and not inr) or (not lhit and not inl) |
| | else if op is "intersect" |
| | return (lhit and inr) or (not lhit and inl) |
| » | else if op is "difference" |
| » | return (lhit and not inr) or (not lhit and inl) |
| | end if |
| | |
| | return false |
| | end function |
Great! Once those tests are all passing, you’re ready to start filtering intersections based on those rules.
Test #5: Filtering a List of Intersections
Given a set of intersections, produce a subset of only those intersections that conform to the operation of the current CSG object.
Once you have the intersection_allowed function working, you get to use it in the next part of your implementation of CSG: intersection filtering. In the big scheme of things, when your renderer intersects a ray with a CSG object, the CSG object will produce a list of intersections between that ray and its children. This filter_intersections(csg, xs) function accepts that list (xs), evaluates each intersection with the intersection_allowed function, and returns a new intersection list consisting of those that pass.
The following test creates a csg object composed of two shapes. Then it creates a list of intersections (xs) and calls filter_intersections. Finally, it checks that the two result intersections are what is expected for the current operation.
| | Scenario Outline: Filtering a list of intersections |
| | Given s1 ← sphere() |
| | And s2 ← cube() |
| | And c ← csg("<operation>", s1, s2) |
| | And xs ← intersections(1:s1, 2:s2, 3:s1, 4:s2) |
| | When result ← filter_intersections(c, xs) |
| | Then result.count = 2 |
| | And result[0] = xs[<x0>] |
| | And result[1] = xs[<x1>] |
| | |
| | Examples: |
| | | operation | x0 | x1 | |
| | | union | 0 | 3 | |
| | | intersection | 1 | 2 | |
| | | difference | 0 | 1 | |
For this to work, your filter_intersections function needs to loop over each intersection in xs, keeping track of which child the intersection hits and which children it is currently inside, and then passing that information to intersection_allowed. If the intersection is allowed, it’s added to the list of passing intersections.
Here it is in pseudocode:
| | function filter_intersections(csg, xs) |
| | # begin outside of both children |
| | inl ← false |
| | inr ← false |
| | |
| | # prepare a list to receive the filtered intersections |
| | result ← empty intersection list |
| | |
| | for each intersection "i" in xs |
| | # if i.object is part of the "left" child, then lhit is true |
| | lhit ← csg.left includes i.object |
| | |
| | if intersection_allowed(csg.operation, lhit, inl, inr) then |
| | add i to result |
| | end if |
| | |
| | # depending on which object was hit, toggle either inl or inr |
| | if lhit then |
| | inl ← not inl |
| | else |
| | inr ← not inr |
| | end if |
| | end for |
| | |
| | return result |
| | end function |
Note the line with csg.left includes i.object, just at the start of the for loop. The implementation of this will be up to you, but A includes B should behave like this:
-
If A is a Group, the includes operator should return true if child includes B for any child of A.
-
If A is a CSG object, the includes operator should return true if either child of A includes B.
-
If A is any other shape, the includes operator should return true if A is equal to B.
In other words, it should recursively search a subtree, looking for the given object, to see whether or not the intersection occurred on the left side of the CSG tree. If it did, then lhit must be true.
Go ahead and make that test pass. Once you do, you can move on to the last two tests: making sure that the actual intersection routine functions correctly.
Tests #6 and 7: Intersecting a Ray with a CSG Object
A ray should intersect a CSG object if it intersects any of its children.
The following tests set up a CSG object and a ray and check to see whether or not the ray intersects. The first test makes sure that a ray misses when it should miss, and the second test makes sure that it hits when it should hit. The second test also applies a transformation to one of the primitives to ensure that the resulting intersections are being filtered correctly.
| | Scenario: A ray misses a CSG object |
| | Given c ← csg("union", sphere(), cube()) |
| | And r ← ray(point(0, 2, -5), vector(0, 0, 1)) |
| | When xs ← local_intersect(c, r) |
| | Then xs is empty |
| | |
| | Scenario: A ray hits a CSG object |
| | Given s1 ← sphere() |
| | And s2 ← sphere() |
| | And set_transform(s2, translation(0, 0, 0.5)) |
| | And c ← csg("union", s1, s2) |
| | And r ← ray(point(0, 0, -5), vector(0, 0, 1)) |
| | When xs ← local_intersect(c, r) |
| | Then xs.count = 2 |
| | And xs[0].t = 4 |
| | And xs[0].object = s1 |
| | And xs[1].t = 6.5 |
| | And xs[1].object = s2 |
Make this pass by intersecting the ray with the left and right children and combining the resulting intersections into a single (sorted!) list. The combined intersections should be passed to filter_intersections, and the filtered collection should then be returned.
In pseudocode, it looks like this:
| | function local_intersect(csg, ray) |
| | leftxs ← intersect(csg.left, ray) |
| | rightxs ← intersect(csg.right, ray) |
| | |
| | xs ← combine leftxs and rightxs |
| | xs ← sort xs by t |
| | |
| | return filter_intersections(csg, xs) |
| | end function |
And that completes your implementation of CSG shapes! You don’t even need to compute a normal vector; the intersection records always point to the primitive object that was hit, and not the parent CSG shape, which means the primitive shape itself will always perform the normal computation. Neat!
One last thing to talk about is how to apply color to CSG shapes.