Theory
Constructive Solid Geometry:
CSG
, short for "Constructive Solid Geometry",
adopts the "building block" approach to solid modeling in its pure
form. The required solid object is built from basic solid shapes by
applying boolean operations of Union, Intersection or Difference on
them.
Representation of CSG Models:
The most natural way to represent a CSG model and one that we used in
our implementation is the so-called CSG tree that can be defined as follows:
{CSG tree} ::== {primitive} |
{CSG Tree} {set operation} {CSG tree} |
{CSG Tree} {rigid motion}
In the above, {primitive} is an instance of a solid primitive,
represented through a primitive type identifier and a sequence of
dimension parameters. {rigid motion} is either translation, scaling or
a rotation, and {set operation} is either Union, Intersection or Difference.
Hence primitives are represented as the laeves of the CSG tree, while
interior nodes are marked with either a Boolean set operation or with
a rigid motion.
The CSG tree can be viewed as an implicit description of the geometry
of the solid modeled that must be "evaluated" in some fashion or order
to create a graphical output or perform calculations. When applied to
CSG trees, the natural way to subdivide a problem is to process the
two subtrees of each interior node denoting a Boolean set operation of
the tree separately. The recursion ends at levaes of the tree, where
the problem is solved for one primitive. Solutions of subproblems are
combined while taking the set operation at the node into respect.
Design
The overall software architecture forms the structure depicted in the
figure below.
+------------>| Solid |<------------+
| ------- |
| /\ |
| || |
V \/ V
----- ------ ---------
|Edges| | Face | |Vertices|
----- ------ ---------
/\ /\ /\
| || |
| \/ |
| ------ |
| | Loops| |
| ------ |
| /\ |
| || |
| \/ |
| -------- |
+-------------->|HalfEdge|<----------+
--------
The innermost layer consists of the half-edge data
structure and a set of procedures for its low level manipulations.
The next layer consists of Euler operators which form the basic
modeling procedures that are used to implement all higher level
operations.
Euler Operators
The operators are usually denoted by rather cryptic mnemonic
names. The key to the names which we have used is:
M - Make V - Vertex H - Hole
K - Kill E - Edge R - Ring
S - Split F - Face
J - Join S - Solid
For instance, the name MEV translates to Make, Edge, Vertex.
The operator MVFS creates from scratch an instance of the data
structure that has just once face and one lone vertex. Hence, the new
face has one empty loop with no edges at all.
The operator SMEF sub-divides a loop by joining two vertices
with a new edge. It's net effect is to add one new edge and face into
the data structure. The operator SMEV subdivides the cycle of
edges of a vertex into two cycles by splitting a vertex into two
vertices joined with a new edge.
Other such euler operators are MEKR, MFKRH, KFMRH and others
as explained in Professor Mantyla's book.
Data Structures
Solid
forms the root node of an instance of the halfedge data structure. The
solid node gives access to faces, edges and vertices of the model
through pointers to three doubly linked lists. All solids are linked
into a doubly linked list.
Face
represents one planar face of the polyhedron represented by the
halfedge data structure. Faces with multiple boundaries are included
in the data structure. Hence, each face is associated with a list of
loops, each representing one polygonal boundary curve of the face. As
all faces represent planar polygons, one of the loops can be
designated as the outer boundary while others represent the holes of a
face. Faces have a vector of four floating point numbers that
represent its plance equation. There is a doubly linked list of all
faces of a solid. Each face has a pointer to its parent solid.
Loop
describes one connected boundary as discussed above. It has a pointer
to its parent face, a pointer to one of the halfedges that form the
boundary and pointers to the next and previous loop of the face.
HalfEdge
describes one line segment of a loop. It consists of a pointer to its
parent loop and a pointer to the starting vertex of the line segment
in the direction of the loop. There exists a doubly linked list of
halfedges of a loop. Hence the final vertex of the line segment is
available as a starting vertex of the next halfedge. It also incluedes
a pointer to its parent edge.
Vertex
contains a vector of four floating point numbers that represent a
point in the homogeneous coodinate representation. There exists a
doubly linked list of vertices of a solid. Vertex includes an
additional pointer to one of the half edges emanating from it.
Edge
associates two halfedges with each other, intuitively, it combines the
two halves of a full edge together. There exists a doubly linked list
of edges.
Methods
The most important, and theoretically the most difficult part of this
project was implementing the code that performs the Boolean set operations.
We are going to be using polygon meshes that approximate the objects being
modeled. These meshes have some basic properties that ensure that the object
makes "sense". In other words, these restrictions ensure that the solids we
create are closed. This is accomplished by requiring the following properties
of the meshes we create:
1. Every edge belongs to exactly two faces.
2. Every vertex is surrounded by a single cycle of edges and faces.
3. Faces may not intersect each other except at a common edge or
vertices.
These properties define a class of meshes called 2-manifolds.
Unfortunately, 2-manifolds are not closed under boolean set operations.
This occurs whenever two objects touch at an edge. The problem is solved by
treating the edge as being slightly inside or outside the face it touches,
thus the result of our Boolean operation is assured to be a 2-manifold.
We can define the Boolean set operations on 2-manifolds by using a
boundary classification for an object: This classifications is defined as:
AinB : The portion of A inside of Solid B
AoutB: The portion of A outside of Solid B
AonB : The portion of A that lies con-planer with a portion of
Solid B
BinA : The portion of B inside of Solid A
BoutA : The portion of B outside of Solid A
BonA : The portion of B that lies co-planer with a portion of
Solid A
The "on" classifications have two sub-classes:
AonB+ : Two co-planer surfaces facing the same direction.
AonB- : Two co-planer surfaces facing in opposite directions.
Note that in the 2-manifold representations, surface orientation
is considered positive for "out" of the object and negative for "inside"
the object.
The boolean operations can be accomplished by taking the appropriate portions
of one solid and "gluing" or "joining" them with the appropriate portions of
the other solid. It can be easily verified that the Boolean-Operations
can be obtained as follows:
A Union B = AoutB (*) BoutA (*) AonB+
A Diff B = AoutB (*) (BinA)-1 (*) AonB-
A Intersect B = AinB (*) BinA (*) AonB+
where (*) is the "gluing operation and the ()-1 is the solid with its face
orientations reversed.
Evaluation of Boolean Operators
The algorithm can be stated as:
1. Determine the intersection of all edges of one object with the edges of
the other objects and split the edges at the point of intersection
2. Determine all intersections of the edges of one solid with faces of
the other solid and split the edge, and place a vertex in the face
intersected.
3. Determine all coincident vertices of the two solids. (These include
the vertices created in steps 1 & 2)
4. Create intersection polygons around the coincident vertices.
5. Choose the appropriate sides of intersection polygons from each
object and "glue" them together.