Boundary Representation

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):

Shape
A Shape is any arbitrary portion of 3d space. It is not necessarily connected; that is, it may have Islands. Also, each island may have holes, like swiss cheese. A Shape is defined as zero or more Islands (although there's really no point to having a Shape with zero Islands -- it just doesn't exist).
Island
Each Island consists of one Blob that defines the Island's exterior surface, plus any number of other Blobs that define interior holes.

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.

Blob
A Blob is a chunk of space. Every part of a Blob is connected to every other part; there are no islands. There are also no internal holes; Blobs are solid. The interior of a Blob is defined by a set of Faces.
Face
A Face is a Surface with a flag indicating whether the interior of the Blob is on the "inside" of the Surface, or the "outside". The meaning of "inside" and "outside" depends on the type of Surface. For a spherical Surface, it's obvious, while for a planar surface, one side is arbitrarily marked as the "inside".
Surface
A Surface is a two-dimensional shape in 3d space. The following are all valid Surfaces:
an infinite plane
a half-plane (e.g. x < 0, y = 0, z = 0)
a sphere
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.

Loop
A Loop is basically a list of Edges. The order of Edges in a Loop matters because the Edges are stored so that they connect end-to-end. Therefore you know that edges[0] connects with edges[1], but you do not know which endpoint of edges[0] connects with which endpoint of edges[1]. So, for each Edge we also store a flag indicating whether the Edge is "forward" or "backward". If edges[0] is marked as "forward", then its *second* endpoint will connect with edges[1]. If edges[1] is *also* marked as "forward", then edges[0].vertex2 == edges[1].vertex1. However, if edges[1] is "backward", then edges[0].vertex2 == edges[1].vertex2. The reason we have to do this is that Edges can be shared by more than one Loop (if you don't believe me, try drawing the Loops for a cube: for each edge, draw an arrow along it so that each face has a circle of arrows -- if any corner has two arrows pointing at each other, you're screwed).

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.

Edge
Edges can be used in isolation in order to represent curves in space. When used in connection with Surfaces (via Loops), they record where the surface stops.

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.


Related Projects


Last updated April 25, 1999
Back to Kimberley's Code.
Back to Kimberley's Home Page.