If you don't know what boundary representation means, here's a quick, probably insufficient, summary. There are two major techniques for representing a cube. In one, you have six four-sided polygons, and leave it at that. This is the model used by OpenGL. In the other technique, you have six planes, which start out infinite but are clipped by four edges. This is the b-rep model, and the one I prefer. In fact, to get a little more specific, I'm using a wing-edged b-rep model, which means that each edge of the cube has a pointer to the two faces it borders.
The advantages of b-rep over poly mesh are that b-rep can deal better with surfaces that have holes in the middle, and it makes it a lot easier to do things like find the intersection, union, or difference between two arbitrary shapes. It also takes a lot less memory for curved surfaces such as NURBS or ellipsoids. To me, it just feels like a much more robust representation. It's also fun, because it can easily represent shapes that extend into infinity (just leave off the boundary part in "boundary representation").
Now into the details. My current goal is just to be able to find the intersection, union, and difference of arbitrary solids. For those who know, this is called CSG (constructive solid geometry). Once I have that, I'll go on to other fun stuff like extrusions, volume calculations, even rendering.
Here's my data model (subject to change as I actually try to implement it):
It's important to note that the way I'm using the word "hole" may be slightly different than you expect. According to my usage, a donut does not have a hole. On the other hand, if you took the jelly out of a jelly donut and then sealed the donut back up again, there would be a hole where the jelly used to be. To be precise, a hole is a portion of empty space that is not continuous with the empty space outside the Island.
an infinite plane
a half-plane (e.g. x < 0, y = 0, z = 0)
a sphere with several holes in it
Surfaces are defined by two things: a domain, and a set of "loops". The domain is what the surface would look like if it wasn't clipped at all. For example, the domain of a plane is an infinite plane, while the domain of a sphere is just a sphere without any holes.
Loops are used to define the edges of a surface. If a Surface has no Loops, the surface consists of its entire domain. On the other hand, if a Surface has even a single Loop, then it just consists of the part of the domain inside that Loop. If it has *two* Loops, it consists of only that part of the domain that is inside *both* loops.
Note that this is a very flexible mechanism. For example, it's possible to define an infinite surface with a hole in it, or a surface with two unconnected pieces. So be very careful about what assumptions you make when dealing with Surfaces.
If the endpoints of the first and last Edges are not connected to each other, then they must both be unterminated -- this indicates that the loop encloses an infinite subset of the domain.
Edges can have 0, 1, or 2 endpoints. If they have 0 endpoints, then they are equal to their domain. With 1 endpoint, they are infinite in only one direction of their domain. With 2 endpoints, they are a finite curve segment. Note: circle edges can only have 0 or 2 endpoints; just 1 isn't allowed.
Edges are parameterized by a variable called "t", so when you want to find out where an Edge starts and stops, you use its "t1" and "t2" properties.
Edges store a list of all the Surfaces they border. This allows traversal of connected Surfaces. Unfortunately, it has the consequence that it's possible for a Surface to forget to add itself to, or remove itself from, the list. It's also slightly complicated by the fact that Edges don't belong directly to Surfaces; instead they belong to Loops, which belong to Surfaces.
Last updated April 25, 1999
Back to Kimberley's Code.
Back to Kimberley's Home Page.