Graphics Reference
In-Depth Information
Elem *pRight;
// Pointer to the next linked list element
float value;
// The actual min or max coordinate value
int
minmax:1;
// A min value or a max value?
};
Here, the lists themselves would be represented by the three list headers:
Elem *gListHead[3];
By merging minimum and maximum values into one element each, space is con-
served (as only a single back pointer to the AABB object is needed). In addition, the
combined structure needs just one flag value, as its contained coordinate values are
either min or max values. This results in the following structures.
struct AABB {
Elem *pMin;
// Pointer to element containing the three minimum interval values
Elem *pMax;
// Pointer to element containing the three minimum interval values
Object *pObj;
// Pointer to the actual object contained in the AABB
};
struct Elem {
AABB *pAABB;
// Back pointer to AABB object (to find matching max/min element)
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?
};
Because the
Elem
structs do not move (only their contained pointers are being
relinked), this representation can be refined further by placing the structs contiguously
in memory. Given a pointer to either
Elem
struct, the corresponding min or max
element can always be found either before or after (respectively) the current one.
As the AABB struct was only needed to link the
Elem
structs, the pair of
Elem
structs
can effectively serve as the new AABB structure. Whereas previously
AABB
structs and
Elem
structs were allocated separately, now the
AABB
struct contains all required data
and only a single structure need be allocated.
struct AABB {
Elem min;
// Element containing the three minimum interval values
Elem max;
// Element containing the three maximum interval values
