1. Point inside of
solid test.
To check if a point p is interior in
respect to a solid can be achieved in several ways. The one proposed
here consists of counting the parity of the number of intersections
between the solid and a ray starting on the given point; if the
number of intersections is odd, the point is outside the solid,
otherwise it is inside the solid.
Ray must be
intersected with all object's faces, finding the intersection point
p' between the face's support plane and the ray, and calling
PointInsideFace3D.
This routine checks if point p' is
interior in respect to the face, that is, if it is inside the contour
polygon but it is not inside any hole in the face. So, it is
convenient to design another routine, PointInsidePolygon3D,
that checks if a point is inside a polygon or not. This test can be
achieved projecting the polygon and the point in 2D, following the
most influent direction of the normal of the support plane.
This test must be run against two different kinds of edges: old edges, which were existing previously belonging to one of the solids (step 1 of the algorithm); and new edges, which are created as a result of the intersection between a plane belonging to one of the two solids and an edge of the other (step 2 of the algorithm).
|
In regard to the old edges, they
will be convex if Vi-Vf orientation equals the vectorial product
|
|
|
|
Considering the new edges,
convexity / concavity of each edge depends on the boolean
operation being performed at the moment: |
3.Face sorting in
respect to a vertex.
Like in the edge
convexity test, we are going to make here the same distinction
between old vertices (coming from step 1) and new vertices (coming
from step 2).
Sorting of faces in respect to
an old vertex can be extracted from information stored in B-Rep's
structure; we just must consider that if that vertex comes from a
solid B (in a A-B substraction) the final order of the faces must be
reversed.
 |
In case of new vertices, as we
have assumed that they always come from the intersection between
a face of one solid and a half-edge of the other, there are only
two possible sortings ( C1 Ce Cd or Cd Ce C1 in the
figure). The choice can be decided depending on the starting
vertex Vi of the half-edge, considering if it is inside or
outside of the plane of face C1.( |
For instance, if Vi is inside 
and the current boolean operation is an intersection, orientation is
Cd-Ce-C1; if Vi is outside ,
orientation is the opposite, C1-Ce-Cd. The following figure
illustrates these:
4.Obtaining the next
vertex in an edge's direction (in domino's algorithm).
The third step in the boolean operations
algorithm requires finding the next vertex in a given edge and in a
given direction. When sevenral candidates exist, a simple geometric
test must be performed in order to choose the nearest one in the
edge's direction.
This geometric test can be
performed in two ways:
Method
A: Sort all vertices along the
edge (not only the candidates, but all vertices along the edge). As
each vertex has its pair, the corresponding pair to current vertex
Vact has to be the next searched vertex.
Sorting is performed depending on the parameter 
of parametric equation of the supporting straight line of the
edge, 
+ Vact.
Vector ,
edge's direction, can be found either by performing the
vectorial product of normal vector to the plane of the face being
reconstructed, ,
with the normal vector of Vact next face, seg,
or by substracting to Vact any of the other remaining vertices on the
edge.
Method B: The previous method requires the storage of concavity / convexity information about edges around candidate vertices, in order to calculate the direction and sense of the reconstructed halfedge.
In this case, vector
is calculated using vectorial product xseg,
and if edge -seg
around Vact was concave, it is necessary to reverse the sense of .
The wanted vertex has the value of parameter
minimum, non-negative in equation
+ Vact, that is, the nearest to Vact in direction .
5.Internal /
external cicle classification.
When dominoes algorithm is done it has generated a number of cycles on the face that we are reconstructing. We must differentiate between external cycles, which form an independent face, and internal cycles, which are going to be holes in some face.
 |
To simplify this classification, you
can assume that there will not be internal faces in respect to
other faces, that is, that the situation of cycles C1 C2 C3 in the
figure will never occur because there is only one level of
overlap. |
The general algorithm is an iterative process which, in each iteration, classifies cycles which are non-internal to any other as external (faces) or internal (holes), depending on parity of the number of completed iterations.:
parity=TRUE
C:=set of face's cycles
while C!=Ø do { /* while cycles left */
D:=Ø
for each cycle Cx in C do
if Cx is internal to some cycle Cy of C-{Cx}
then classify as hole of Cy
else add to D
endif
endfor
if parity then D cycles are external faces
else D cycles are holes
endif
parity:=not parity
C:=C-D
endwhile
This process can be done while new faces and holes are created and added to the final resulting object of the boolean operation. Note that the order of the edges of the holes is the reverse of external polygons.
