i
i
i
i
i
i
i
i
16.3. Space Partitioning 397
vertices, the surface will pass through that face and the face neighbor must be
processed. When this process has been completed for all the faces, the second
phase of the algorithm is applied to the cube. If the surface is closed, eventually
a cube will be re-visited and no more unmarked neighbors found, and the search
algorithm will terminate. Processing a cube involves marking it as processed
and processing its unmarked neighbors. Those that contain intersecting edges are
processed until the entire surface has been covered (see Figure 16.10).
Each cube is indexed by an identifying vertex which we define to be the lower-
left far corner (i.e., the vertex with the lowest (x, y, z)-coordinate values (see Fig-
ure 16.11)). For each vertex that is inside the surface, the corresponding bit will
be set to form the address in an 8-bit table (see Figure 16.11 and Section 16.3.3).
The identifying vertex is addressed by integers i, j, k, computed from the
(x, y, z)-coordinate location of the cube such that x =side∗i,etc.,whereside is
the size of the cube. The identifying vertex of each cube may appear in as many
as eight other cubes, and it would be inefficient to store these vertices more than
once. Thus, the vertices are stored uniquely in a chained hash table. Since most
0
Top
Front
Right
Right
0 0 00000001
1 01 00000010
2 010 00000100
3 011 00001000
4 100 00010000
5 101 00100000
6 110 01000000
7 111 10000000
Vertex If (+
Figure 16.11. Vertex num-
bering.
of the space does not contain any part of the surface, only those cubes that are
visited will be stored. The implicit function value is found for each vertex as it is
stored in the hash table.
Nothing is known about the topology of the surface so a search must be started
from every primitive to avoid any disconnected parts of the surface being missed.
A scalar can be used to scale the influence of a primitive. If the scalar can be less
than zero, then it is possible to search along an axis without finding an intersect-
ing edge. In this case, a more sophisticated search must be done to find a seed
cube (Galin & Akkouche, 1999).
Data Structures
The hash table entry holds five values:
• the i, j, k lattice indices of the identifying vertex (see Figure 16.11);
• f, the implicit function value of the identifying vertex;
• Boolean to indicate whether this cube has been visited.
The hash function computes an address in the hash table by selecting a few bits out
of each of i, j, k and combining them arithmetically. For example, the five least
significant bits produces a 15-bit address for a table, which must have a length
of 2
15
. Such a hash function can be neatly implemented in the C-preprocessor as
follows: