Graphics Reference
In-Depth Information
A
B
Figure 12.4 Only the grid cells intersected by the tolerance neighborhood of a vertex (here
shown in gray) must be tested against during vertex welding. For vertex A this results in just
one cell tested. For vertex B , two cells must be examined.
neighborhood. Because only the grid cells overlapped by the tolerance region sur-
rounding V have to be examined, on average only the content of a single cell must be
tested! Figure 12.4 illustrates how the approach works for two sample vertices.
Second, under the hash mapping two or more cell neighborhoods of vertices may
map to the same hash bucket. This does not have any adverse effect on the method,
in that a distance test is performed for all vertices within a tested cell. At worst, this
results in a few extra vertices being tested during the welding test against the content
of that hash bucket. The following is a sample 2D implementation of the hashed grid
solution. First are some necessary constant values.
#define MAX_VERTICES 100000
// max number of vertices that can be welded at once
#define NUM_BUCKETS 128
// number of hash buckets to map grid cells into
#define CELL_SIZE 10.0f
// grid cell size; must be at least 2*WELD_EPSILON
#define WELD_EPSILON 0.5f
// radius around vertex defining welding neighborhood
// Maps unbounded grid cell coordinates (x, y) into an index
// into a fixed-size array of hash buckets
unsigned int GetGridCellBucket(int x, int y)
{
const unsigned int magic1 = 0x8da6b343; // Large multiplicative constants;
const unsigned int magic2 = 0xd8163841; // here arbitrarily chosen primes
unsigned int index = magic1*x+magic2 * y;
 
Search WWH ::




Custom Search