Graphics Reference
In-Depth Information
are no degenerate situations causing excessive vertex drift, averaging can be more
consistent with an intuitive expectation of where the representative point should be.
Sequential processing implies an order dependency. Sequential methods must
also address the issue of two or more previous vertices found within the welding
distance of the current vertex. Should welding be performed with the closest one, or
perhaps with all of them? Additionally, for all three approaches there are degenerate
situations in which, although highly unlikely, two vertices arbitrarily close to each
other may weld to two different positions.
The last issue, along with what to do when there are several previous vertices
within the welding distance, can be avoided by using a simultaneous welding model.
The simultaneous model identifies all sets of vertices such that each vertex of the set
is within the tolerance distance of one or more other vertices of the set. For each
set, all vertices within the set are averaged. This is also illustrated in Figure 12.3.
This approach is more expensive to implement than sequential welding. It too suffers
from degenerate cases (as illustrated), and thus the value of simultaneous welding is
unclear.
A problem that remains is how to locate vertices within the welding distance of
each other. A brute-force approach to vertex welding is simply to test each vertex
A
against every other vertex
B
. Although this method is quite simple to implement, its
O
(
n
2
) complexity makes it too slow for large data sets. Fortunately, just about any
space-partitioning data structure could be used to speed up the welding operation
by, in effect, dividing the vertices into small distinct clusters so that only the vertices
of one or a few clusters would have to be tested. In fact, vertex welding can be
seen as a collision detection problem by thinking of the vertices and their welding
neighborhood as small spheres or boxes to be tested for overlap. Thus, any fast
collision method could be used for vertex welding.
A practical approach to the problem is to use the hashed uniform grid of Section
7.1.3. It is efficient, with an expected
O
(
n
) complexity, which is optimal. Technically,
its worst-case complexity is
O
(
n
2
) — when all points fall within the same grid cell,
but no welding takes place — but this worst-case scenario does not occur in practice.
It is also an
on-line
algorithm, and thus vertices can be welded as they are added,
instead of requiring all vertices to be present from the start.
The welding method employed in the following is a sequential processing of the
vertices, welding the current vertex against previous vertices. The idea is to add ver-
tices one at a time into the hashed grid. A test is then performed against grid cells
that fall within the welding neighborhood of the current vertex
V
. If one of the cells
contains some vertex
W
that
V
is within the welding distance of,
W
is returned as the
welded vertex. If not,
V
is added to the grid cell it maps to, and
V
itself is returned as
the welded vertex.
There are two key things to note. First, in order to limit the number of cells that
must be tested
CELL_SIZE
should at least be larger than
2 * WELD_EPSILON
. Then
the square welding neighborhood around
V
can at most overlap four neighboring
grid cells (in 2D, eight cells for the cubic welding neighborhood in 3D). In prac-
tice,
CELL_SIZE
is usually selected to be a factor or two larger than the welding
