Interpolation-Based Animation - Computer Animation: Algorithms and Techniques - page 144

B 's intersections
connected
inside A

Vertices of
triangle A
inside of B

By a point By an edge

B

B

No vertices

A

A

B

B

One vertex

A

A

not possible with
triangles

Two vertices

A

B

FIGURE 4.39
Configurations possible with overlapping triangles and possible triangulations.

one considers the triangulation required from the combined models ( Figure 4.39 ) . Processing can pro-
ceed by considering all of the original triangles from one of the models. For each triangle, use the inter-
section points along its edges and the vertices of the other object that are contained in it (along with any
corresponding edge definitions) and construct a new triangulation of the triangle. When this is finished,
repeat the process with the next triangle from the object.
The process of triangulation proceeds as follows. First, output any complete triangles from the other
object contained in this object. Second, triangulate the fragments that include an edge or edge segment
of the original triangle. Start at one of the vertices of the triangle and go to the first intersection encoun-
tered along the boundary of the triangle. The procedure progresses around the boundary of the triangle
and ends when it returns to this intersection point. The next intersection along the boundary is also
obtained. These two intersections are considered and the configuration identified by noting whether
zero, one, or two original vertices are contained in the boundary between the two intersection points.
The element inside the triangle that connects the two vertices/intersections is a vertex or an edge of the