Project: Constructive Solid Geometry

Constructive Solid Geometry

The main/mandatory part of milestone 2 is the implementation of the Constructive Solid Geometry (CSG) operations (true) union, intersection and difference. Note that the framework already contains a “union”, but instead of actually combining objects it always treats them as disjoint. For example, if we wanted the union of two spheres that partially overlap, we might expect a ray that intersects them to have one entry and one exit hit (as it enters and then leaves the combined volume). The current “union” does not take this case into account, and will instead return four intersections: Two entries (into each of the individual spheres), and two exits (from the two spheres). What we want for this milestone, instead, is to return entry- and exit-hits only when the resulting (combined) volume is actually entered and exited.

First, note that the result of every intersect method is an ArrayList<RayHit>, which should be ordered in ascending distance from the origin (which is the t value in the RayHit object). Second, a true combined volume will alternate between entry- and exit-hits, i.e. if the volume is entered the only thing the ray can do next is exit, and vice versa. The first hit may be an exit-hit, if the ray originated inside the volume, and the last hit may be an entry-hit, if the volume extends infinitely, and the ray never exits it. In particular, the way we defined planes and triangles, they actually extend infinitely in the direction opposite their normal vector. The only file you need to change for this task is `CSG.pde’.

The main difference between the CSG operations is how they define when the combined volume is entered and exited.

(True) Union

As mentioned above, the existing union-code does not represent a “true” union, because entry- and exit-hits don’t necessarily alternate. It will work fine for volumes that don’t overlap (and exists to allow having multiple objects in a scene), but as soon as objects start to overlap it produces the wrong results. This is not an issue as long as only these “fake” unions are present in a scene, but it will break when combined with an intersection.

In order to produce a true Union, you can use the existing code as a starting point:

ArrayList<RayHit> hits = new ArrayList<RayHit>();
for (SceneObject sc : children)
{
   hits.addAll(sc.intersect(r));
}
hits.sort(new HitCompare());
return hits;

This will call intersect on all objects in the union, and then sort the hits in ascending distance from the origin. Instead of returning this hits ArrayList directly, though, you should only include the “true” entry- and exit-hits: The ray is inside the (combined) volume as soon as it enters the first sub-volume, and any subsequent entry-hits are not to be included in the result. However, you need to count them, because only once the ray has exited the same number of volumes, it will be exit the combined volume, and this last exit should also be included in the result. Note that a ray may enter and exit the combined volume multiple times (consider two spheres that are non-overlapping and behind each other). Also note that the ray may start inside the combined volume to begin with. You can determine how “deep” inside the ray starts by counting how often the first ray-hit of a child-object is an exit-hit.

Intersection

In contrast to the union, there is no “basic” version of the intersection. However, once you have the Union operation implemented, the Intersection operation follows analogously. The only difference is that a ray is considered to enter the intersection volume when it has entered all subvolumes, i.e. you count how many volumes the ray has entered (adding one when it enters a volume, subtracting one if it exits), and when this count is equal to the total number of child-volumes, the ray enters the intersection, i.e. that is the entry-hit you should include. Likewise, as soon as the ray exits any of the child-volumes again, it also exits the intersection.

Just as with the union, the ray may start inside some of the child-volumes, and this case needs to be taken into account!

Difference

The difference-operation, finally, differs slightly from the previous two in that it has exactly two children, i.e. there is no “counting” required. Instead, the semantics of “difference between a and b” are that the ray is inside the combined volume iff it is inside a but not inside b. There are three basic cases to consider:

  • If the ray enters a first, it will exit the combined volume either when it enters b, or when it exits a again, whichever comes first. Note that you can not simply reuse the RayHit that enters b, as you will need to change the entry-value and flip the normal vector!
  • If the ray enters b first, and enters a before it exits b, it will enter the combined volume when it exits b (if it is still inside a at the time). As before, you will need to change the entry-value and flip the normal vector!
  • If the ray enters b first, and then exits it before entering a we are back to the start.

However, note that each volume may be entered and exited multiple times in arbitrary combination, e.g. the ray may enter a, then b, then exit b, then enter b again, then exit a, then exit b, then enter a again, etc.

The best approach to each of these operations is to iterate over the ray hits returned by the children (or a and b) in increasing order of t, and keep track of whether the ray is inside or outside the combined volume. In the case of the difference operation, care must be taken to flip entry (and normal to point outwards!) as necessary.