Geometrical Robustness - Real-Time Collision Detection - page 472

next[numVertices] = first[bucket];
first[bucket] = numVertices++;

}

When working with floating-point values, for large coordinates the addition of
a small epsilon leaves the coordinate unchanged (see Chapter 11). In this case, the
code would not correctly test against neighboring cells. Therefore, for the code to be
robust it is important to make sure WELD_EPSILON is large enough for the coordinate
values used. (A pragmatic solution is to add asserts to the code to detect this problem
occuring. Should the assert trigger, the epsilon value is increased until the problem
goes away.) The welding code is implemented by the following routine.

Point *WeldVertex(Point *v)
{

// Make sure epsilon is not too small for the coordinates used!
assert(v- > x - WELD_EPSILON != v- > x&&v- > x + WELD_EPSILON != v- > x);
assert(v- > y - WELD_EPSILON != v- > y&&v- > y + WELD_EPSILON != v- > y);

// Compute cell coordinates of bounding box of vertex epsilon neighborhood
int top = int((v- > y - WELD_EPSILON) / CELL_SIZE);
int left = int((v- > x - WELD_EPSILON) / CELL_SIZE);
int right = int((v- > x + WELD_EPSILON) / CELL_SIZE);
int bottom = int((v- > y + WELD_EPSILON) / CELL_SIZE);

// To lessen effects of worst-case behavior, track previously tested buckets
unsigned int prevBucket[4]; //4in2D,8in3D

int numPrevBuckets = 0;

// Loop over all overlapped cells and test against their buckets
for (int i = left; i <= right; i++) {
for (int j = top; j <= bottom; j++) {
unsigned int bucket = GetGridCellBucket(i, j);
// If this bucket already tested, don't test it again
for(intk=0;k<numPrevBuckets; k++)
if (bucket == prevBucket[k]) goto skipcell;
// Add this bucket to visited list, then test against its contents
prevBucket[numPrevBuckets++] = bucket;
Point *weldVertex;
// Call function to step through linked list of bucket, testing
// if v is within the epsilon of one of the vertices in the bucket
if (LocateVertexInBucket(*v, bucket, &weldVertex)) return weldVertex;