Computer Aided Engineering Design

SOLID MODELING 261

With these tables, we can know what vertices, edges and faces are adjacent to a face, edge or a
vertex, which are 9 adjacency relations. Note that once a polyhedron is given with fixed number of
edges, faces and vertices, the sizes of the three tables containing topological information get fixed.
All now remains is to store the geometric data which corresponds to the coordinates of the data
points, slopes and/or knot vectors of the boundary curves and faces (surface patches) forming a solid.
In case a solid, e.g. in Figure 8.16, has voids that penetrate the solid partially or completely, there
are two ways in which one could apply the Baumgart’s data structure. For a face with inner loops as
in Figure 8.18(a), we can retain the clockwise order for the outer loops while the inner loops would
be ordered counterclockwise. The alternative is to add an auxiliary edge between an inner loop and
the outer loop as shown in Figure 8.18(b) with dashed lines. The auxiliary edge will have the same
face to its left and right, one way to identify them in the data structure, and the number of loops will
get reduced to 1 for a face with inner loops. The topological tables can be constructed in a manner
similar to those explained for the tetrahedron above.

Vertex table Face table

Vertex Edge Face Edge

1 (1) A (1)

2 (2) B (2)

3 (3) C (4)

4 (6) D (5)

Figure 8.18 Two schemes to treat the inner loops for the Baumgart’s data structure

(a) (b)

Baumgart’s winged-edge data structure is efficient in performing certain operations, a reason why
it is more popular compared to other schemes. For instance, it helps in identifying all loops on each
face quickly and also allows traverse along each edge on a face. Thus, many algorithms in computational
geometry (Chapter 9) benefit from this data structure. Baumgart’s scheme also helps in quickly
determining the orientation (inward pointing normal) of each face. This is important when a computer
is rendering the image of an object on the screen. Once the object is transformed to a particular
orientation, its visible and invisible faces can be determined quickly. Also, for a given face, finding
its neighboring faces is easier.

8.8.2 Euler-Poincaré Formula

The formula relates the number of vertices, edges and faces of a polyhedral solid and has been
generalized to include the potholes and through voids penetrating the solid. For V as number of