Graphics Reference
In-Depth Information
Object *pObj;
// Pointer to the actual object contained in the AABB
};
struct Elem {
Elem *pLeft[3];
// Pointers to the previous linked list element (one for each axis)
Elem *pRight[3];
// Pointers to the next linked list element (one for each axis)
float value[3];
// All min or all max coordinate values (one for each axis)
int
minmax:1;
// All min values or all max values?
};
Given a pointer to an
Elem
struct, the corresponding AABB is located in this way:
AABB *GetAABB(Elem *pElem)
{
return (AABB *)(pElem-
>
minmax ? (pElem - 1) : pElem);
}
Compared to the previous representation, this saves four pointers (16 bytes at
4 bytes per pointer) per AABB. By embedding the structure inside the objects them-
selves, the pointer to the object would no longer be needed and an additional 4 bytes
would be saved. With a little trickery, the
minmax
bit fields could be moved from the
Elem
structs into the
AABB
struct to save some additional memory. They could, in fact,
be embedded within one of the other structure fields and thus take up no extra space.
This is still quite an expensive structure at about 76 to 84 bytes per object, depending
on implementation. Further savings can be had by turning the 32-bit pointers into
16-bit indices, assuming that at no time will there be more than 65,536 objects (which
is a safe assumption for many applications).
In the following code it is assumed the three lists have been initialized to have
both start and end sentinels. Sentinels can be set up as follows.
enum {
MIN_ELEM = 0,
// Indicates AABB minx, miny, or minz element
MAX_ELEM = 1
// Indicates AABB maxx, maxy, or maxz element
};
// Initialize the lists, with start and end sentinels
AABB *pSentinel = new AABB;
for(inti=0;i<3;i++) {
pSentinel->min.pLeft[i] = NULL;
// not strictly needed
pSentinel->min.pRight[i] = &pSentinel->max;
