# About

**XRT is a raytracing based programmable rendering system for photo-realistic image synthesis built around a plug-in architecture design.**

# Blog

## Constructive Solid Geometry

Posted: 20 Feb 2010 12:35

**Tags: csg**

The most widely known algorithms for rendering constructive solid geometry (CSG) require finding all intersections of a line with a primitive and then computing the intersections by examining the intervals. This is clearly inefficient because you need to store and compute all the intersections for all the sub-objects of the CSG tree. Not only you don't really need to know all intersections to find the nearest one but the storage/deletion of many hits within a rendering loop is a real performance killer. Another issue is that you must rewrite all your primitive intersection routines to support CSG which increases the code bloat.

Therefore, CSG support within **XRT** is based on a different algorithm described in a short paper from Andrew Kensler: *Ray Tracing CSG Objects Using Single Hit Intersections*. This paper is no longer available on the web but you can find a local copy here.

As the author states in his introduction:

"The [algorithm] computes intersections with binary CSG objects using the [nearest] intersection. Though it may need to do several of these per sub-object, the usual number needed is quite low. The only limitation of this algorithm is that the sub-objects must be closed, non-self-intersecting and have consistently oriented normals."^{1}

## Algorithm outline

A ray is shot at each sub-object to find the nearest intersection, then the intersection with the sub-object is classified as one of entering, exiting or missing it. Based upon the combination of the two classifications, one of several actions is taken:

- returning a hit
- returning a miss
- changing the starting point of the ray for one of the objects and then shooting this ray, classifying the intersection. In this case, the state machine enters a new loop.

The paper finally describes the state machine and the 3 different state tables (one for each CSG operation **Union**, **Intersection** and **Difference**) needed to raytrace a CSG tree. This a very neat idea expressed clearly and concisely: the paper is 3 pages long, 2/3 of it made of diagrams, state tables and pseudo code ready to be translated into C++. A real programmer's heaven.

But it doesn't work.

The state table for **Union** is OK but the state tables for **Intersection** and **Difference** are not. Even with very simple cases, when you run the routine with pen and paper, it fails. The good news are that it can be fixed with a few minor changes:

- create two other actions
- change the result of one combination in the
**Difference**and**Intersection**tables - update the state machine

My changes are given below in bold.

### List of actions

ReturnMiss | Exit, reporting no intersection |

ReturnAIfCloser | Return the intersection with A if it is closer |

ReturnAIfFarther | Return the intersection with A if it is farther |

ReturnA | Always return the intersection with A |

ReturnBIfCloser | Return the intersection with B if it is closer |

ReturnBIfFarther | Return the intersection with B if it is farther |

ReturnB | Always return the intersection with B |

FlipB | If returning an intersection with B, flip its normal |

AdvanceAAndLoop | Continue with the next intersection with A |

AdvanceBAndLoop | Continue with the next intersection with B |

AdvanceAAndLoopIfCloser |
Continue with the next intersection with A if the current intersection with A is closer |

AdvanceBAndLoopIfCloser |
Continue with the next intersection with B if the current intersection with B is closer |

### Action tables

Union | Enter B | Exit B | Miss B |
---|---|---|---|

Enter A | ReturnAIfCloser, ReturnBIfCloser | ReturnBIfCloser, AdvanceAAndLoop | ReturnA |

Exit A | ReturnAIfCloser, AdvanceBAndLoop | ReturnAIfFarther, ReturnBIfFarther | ReturnA |

Miss A | ReturnB | ReturnB | ReturnMiss |

Difference | Enter B | Exit B | Miss B |
---|---|---|---|

Enter A | ReturnAIfCloser, AdvanceBAndLoop | AdvanceAAndLoopIfCloser, AdvanceBAndLoopIfCloser |
ReturnA |

Exit A | ReturnAIfCloser, ReturnBIfCloser, FlipB | ReturnBIfCloser, FlipB, AdvanceAAndLoop | ReturnA |

Miss A | ReturnMiss | ReturnMiss | ReturnMiss |

Intersection | Enter B | Exit B | Miss B |
---|---|---|---|

Enter A | AdvanceAAndLoopIfCloser, AdvanceBAndLoopIfCloser |
ReturnAIfCloser, AdvanceBAndLoop | ReturnMiss |

Exit A | ReturnBIfCloser, AdvanceAAndLoop | ReturnAIfCloser, ReturnBIfCloser | ReturnMiss |

Miss A | ReturnMiss | ReturnMiss | ReturnMiss |

### State machine pseudo-code

The algorithm is slightly modified to take into account the new actions. Please note that minA and minB must **not** be initialized to 0.

```
minA = minB = min // current nearest intersection
( tA, NA ) = IntersectWithA( O, D, minA )
( tB, NB ) = IntersectWithB( O, D, minB )
stateA = ClassifyEnterExitOrMiss( tA, NA )
stateB = ClassifyEnterExitOrMiss( tB, NB )
loop
action = table [stateA, stateB]
if ReturnMiss ∈ action then
return miss
else if ReturnA ∈ action
or ( ReturnAIfCloser ∈ action and tA <= tB )
or ( ReturnAIfFarther ∈ action and tA > tB ) then
return tA, NA
else if ReturnB ∈ action
or ( ReturnBIfCloser ∈ action and tB <= tA )
or ( ReturnBIfFarther ∈ action and tB > tA ) then
if FlipB ∈ action then
NB = −NB
end if
return tB, NB
else if AdvanceAAndLoop ∈ action
or ( AdvanceAAndLoopIfCloser ∈ action and tA <= tB ) then
minA = tA
( tA, NA ) = IntersectWithA( O, D, minA )
stateA = ClassifyEnterExitOrMiss( tA, NA )
else if AdvanceBAndLoop ∈ action
or ( AdvanceBAndLoopIfCloser ∈ action and tB <= tA ) then
minB = tB
( tB, NB ) = IntersectWithB( O, D, minB )
stateB = ClassifyEnterExitOrMiss( tB, NB )
end if
end loop
```

You will find some examples of this feature in the gallery