Recursive Dimensional Clustering problems

Has anybody successfully implemented the Recursive Dimensional Clustering algorithm? I've copied it nearly verbatim from Game Programming Gems 2, and it seems to have a major flaw. Let's say we have the following sorted entity boundary list (ID is a unique ID representing an entity):


Boundary:	     Type:		ID:
-30		     open		6
20		     open		7
30		     close		6
70		     open		8
80		     close		7
120		     open		9
130		     close		8
170		     open		10
180		     close		9
220		     open		11
230		     close		10
270		     open		12
280		     close		11
320		     open		13
330		     close		12
380		     close		13

That's a series of entities, slightely overlapping their next and previous, along the X axis. Now, if I understand it correctly, RDC identifies a new group of entities to recursively subdivide by traversing the boundary list and adding each OPEN boundary to the group, until it reaches a CLOSE boundary. At this point, the group is sent to a new instance of the algorithm, then cleared before constructing the next group. Each group conceptually represents a cluster of entities that directly or indirectly overlap. Given the above data, this system fails. Basically, instead of detecting all eight entities as one cluster, it's broken up by the first CLOSE entry, which results in a collision pair being undetected. This is quite hard to explain, but I hope those of you that have implemented the algorithm successfully can help explain if this is a bug in my implementation, a flaw in my understanding, or if its a flaw in the algorithm. Here is my implementation: rdc.h



//-----------------------------------------------------------------------
//Recursive Dimensional Clustering functions
//-----------------------------------------------------------------------

#ifndef INC_RDC
#define INC_RDC

#include "globals.h"
#include "entity.h"
#include "algorithm"

typedef deque<Entity*> Group;

struct Pair {
	Entity* A;
	Entity* B;
	Pair() {}	//no initialisation here, for speed
	Pair(Entity* A, Entity* B): A(A), B(B) {}
	const bool operator == (const Pair& p) const {
		return (p.A == A && p.B == B) || (p.B == A && p.A == B);
	}
	/*const bool operator < (const Pair& p) const {
		return p.A < A || p.B < B;
	}*/
};

typedef deque<Pair> Pairs;

enum OpenCloseObject { OPEN, CLOSE };

struct BoundaryObject {
	Entity* entity;
	OpenCloseObject oc;
	DistanceType boundary;
	BoundaryObject() {}	//no initialisation here either
	BoundaryObject(Entity* entity, OpenCloseObject oc, DistanceType boundary): 
		entity(entity),
		oc(oc),
		boundary(boundary) {}
};

typedef vector<BoundaryObject> OpenCloseBoundaryList;
enum Axis { INVALID_AXIS, X_AXIS, Y_AXIS, Z_AXIS };

inline bool myCompare(BoundaryObject& b1, BoundaryObject& b2) {
	return b1.boundary < b2.boundary;
}

/*class MyCompare {
	public:
		bool operator() (BoundaryObject& b1, Boundary& b2) {
			return myCompare(b1, b2);
		}
};*/

void FindOpenCloseBoundaries(Axis axis, Group& group, OpenCloseBoundaryList& boundaries);
void SortOpenCloseBoundaries(OpenCloseBoundaryList& b);
void BruteForceComparison(Pairs& pairs, Group& group);

//Print a boundary list
inline void printBoundaryList(OpenCloseBoundaryList& b, int depth) {
	
	for(int i=0; i<depth; ++i)
		cout << " ";
	
	cout << "------------------------" << endl;
	
	for(OpenCloseBoundaryList::const_iterator it = b.begin(); it != b.end(); ++it) {
	
		for(int i=0; i<depth; ++i)
			cout << " ";
	
		cout << "boundary: " << (*it).boundary;
	
		if( (*it).oc == OPEN )
			cout << " OPEN";
		else
			cout << " CLOSE";
		
		cout << " " << (*it).entity->name << endl;
		
	}
	
	for(int i=0; i<depth; ++i)
			cout << " ";
	
	cout << "------------------------" << endl;
	
}

//Print a group
inline void printGroup(Group& group) {
	
	cout << "------------------------" << endl;
	
	for(Group::const_iterator it = group.begin(); it != group.end(); ++it) {
	
		cout << (*it)->name << endl;
		
	}
	
	cout << "------------------------" << endl;
	
}

void RDC(Pairs& pairs, Group& group, Axis axis1, Axis axis2, Axis axis3, int* depth);

#endif

rdc.cpp



//-----------------------------------------------------------------------
//Recursive Dimensional Clustering functions
//-----------------------------------------------------------------------

#include "rdc.h"

#define RDC_GROUPSIZE_CUTOFF 5

//Recursive Dimensional Clustering algorithm
void RDC(Pairs& pairs, Group& group, Axis axis1, Axis axis2, Axis axis3, int* depth) {

	(*depth)+=3;

	if(group.size() <= 0)
		return;

	//end recursion and test for collisions with brute force method if the group size is low enough
	if(group.size() < RDC_GROUPSIZE_CUTOFF || axis1 == INVALID_AXIS) {
		BruteForceComparison(pairs, group);
	}
	else {

		OpenCloseBoundaryList boundaries;
		FindOpenCloseBoundaries(axis1, group, boundaries);	//put the boundaries of this group into a list
		SortOpenCloseBoundaries(boundaries);								//now sort that list
		printBoundaryList(boundaries, *depth);
		
		Group subGroup;
		unsigned int count = 0;
		Axis newAxis1 = axis2;
		Axis newAxis2 = axis3;
		Axis newAxis3 = INVALID_AXIS;
		bool groupSubdivided = false;
		
		//subdivide the group if possible and call recursively
		for(OpenCloseBoundaryList::const_iterator it = boundaries.begin(); it != boundaries.end(); ++it) {
		
			if( (*it).oc == OPEN ) {	//open
				++count;
				subGroup.push_back( (*it).entity );
			}
			else {	//close
				--count;
				
				//found the end of a cluster group - take subgroup and call recursively on remaining axis'
				if(count == 0) {
					
					if(it != boundaries.end() - 1)
						groupSubdivided = true;
					
					if(groupSubdivided) {
					
						//reconsider other axis
						switch(axis1) {
							case X_AXIS: 
								newAxis1 = Y_AXIS;
								newAxis2 = Z_AXIS;
								break;
							case Y_AXIS: 
								newAxis1 = X_AXIS;
								newAxis2 = Z_AXIS;
								break;	
							case Z_AXIS: 
								newAxis1 = X_AXIS;
								newAxis2 = Y_AXIS;
								break;
						}
						
					}
					
				}
				
				//recursive call
				RDC(pairs, subGroup, newAxis1, newAxis2, INVALID_AXIS, depth);
				subGroup.clear();
				
			}
		
		}
		assert(count == 0);
	
	}
	
	(*depth)-=3;

}

//Find open/close boundaries
void FindOpenCloseBoundaries(Axis axis, Group& group, OpenCloseBoundaryList& boundaries) {

	switch(axis) {

		case X_AXIS:
			for(Group::const_iterator it = group.begin(); it != group.end(); ++it) {
	
				boundaries.push_back(BoundaryObject( *it, OPEN, (*it)->collisionMask.box.x));
				boundaries.push_back(BoundaryObject( *it, CLOSE, (*it)->collisionMask.box.x + (*it)->collisionMask.box.w));
			
			}
			break;
			
		case Y_AXIS:
			for(Group::const_iterator it = group.begin(); it != group.end(); ++it) {
	
				boundaries.push_back(BoundaryObject( *it, OPEN, (*it)->collisionMask.box.y));
				boundaries.push_back(BoundaryObject( *it, CLOSE, (*it)->collisionMask.box.y + (*it)->collisionMask.box.h));
			
			}
			break;
			
		case Z_AXIS:
			for(Group::const_iterator it = group.begin(); it != group.end(); ++it) {
	
				boundaries.push_back(BoundaryObject( *it, OPEN, 0.0));
				boundaries.push_back(BoundaryObject( *it, CLOSE, 0.0));
			
			}
			break;
			
		case INVALID_AXIS:
		default:
			break;
			
	}

}

//Sort a boundary list
void SortOpenCloseBoundaries(OpenCloseBoundaryList& b) {
	std::sort(b.begin(), b.end(), myCompare);
}

//Brute force comparison
void BruteForceComparison(Pairs& pairs, Group& group) {
	for(Group::const_iterator it = group.begin(); it != group.end(); ++it)
		for(Group::const_iterator it2 = group.begin(); it2 != group.end(); ++it2)
			if(rectOverlap(&((*it)->collisionMask.box), &((*it2)->collisionMask.box)) && *it != *it2)
				pairs.push_back(Pair(*it, *it2));
}

Thank you.

I've implemented RDC within a 3D environment; it was by far the most complex implementation of my all the spatial locality mechanics covered. It uses some x vectors with reserved sizes, plenty of memory going to waist but the focus was performance. When applying brute force to the clusters found, RDC out preformed brute force sufficiently when objects were in small clusters and not densely packed. It proves to be an efficient algorithm for finding clusters of objects, for example arrangements you might find in say starcraft where units spend allot of their time bunched (the algorithm finds the cluster, it’s up to you how you deal with the cluster, if you were to brute force the cluster and it had a significant number of elements then yes it would be slow, the idea is that you could apply group logic to the cluster, or you might have a reason to want to know what object are bunched up).

Topic Locked