Heya all.
I thought I'd devote a thread to this class, since its so generically useful to 3D gamecoding.
CBoundingBox class provides all the necessary code to perform all kinds of intersection tests of points, lines, planes and of course, bounding boxes, against one another.
One very good example of why you might wish to perform such tests is culling. We can define the Viewing Frustrum as a boundingbox, and check what's totally inside it, whats partially inside it, and whats not inside it at all, before we go rendering stuff to the screen.
Another obvious example is testing for collisions of point and planes, after all, we don't want objects falling through the floor, and we'd like them to stop when they hit walls :)

The class I will describe is taken from my bsp demo, which itself is incomplete.
I'd love to hear any feedback, particularly in terms of optimisations to the code presented - if we are going to use this class for things like culling and collision detection, we'd like it to be as fast as possible.

I'll begin by describing the functions within the class, then we'll define the class object and its data members, and finally, begin presenting the actual code.

Function #1 - FindBoundingBoxA
This function is used to calculate the tightest fitting boundingbox around an arbitrary number of vertices (points in 3D space).

Function #2 - FindBoundingBoxB
This variation of the above function calculates a boundingbox from two vertices (which could be considered corners of the BB).

Both of these functions can handle situations where an axis of the BB has zero depth in an axis (all lay on an axial plane).

Function #3 - SetBoundingBoxA
This function sets an object's BoundingBox once its been calculated, and additionally calculates and sets the six PLANES which are the faces of the boundingbox. Objects wishing to have support from CBoundingBox class can either inherit from it (if they are class-based themselves) or create an instance of CBoundingBox for themselves and store a pointer to it in their struct.

Function #4 - SetBoundingBoxB
This variation of the above function sets the boundingbox and planes for an object same as above, except it assumes the planes are precalculated and takes a pointer to them as a parameter.

Function #5 - TransformBoundingBox
This function manipulates all of a boundingbox's 8 points and 6 planes according to a given transformation matrix.

Function #6 - IsIntersecting
This function performs intersection tests between two boundingboxes. The four possible return values are:
NOT_INTERSECTING equ 0
PARTIALY_INTERSECTING equ 1
COMPLETELY_COVER equ 2
COMPLETELY_INSIDE equ 3

Function #7 - LazyIsIntersecting
Same as above, except less computationally intensive (less accurate but lots faster). It's useful to perform a rough test, and if it returns a positive result, we can optionally perform a more accurate test or tests.

Function #8 - IsPenetrated
This function tests for intersection of a boundingbox and a line (two points).
It simply returns TRUE or FALSE.

Except for a couple of helper functions which I consider to be external to the Class (no good reason to add class calling overhead to generic functions) that pretty much wraps up the functionality of CBoundingBox class.

An idea I had which is yet to be explored is the concept of creating HIERARCHIES of boundingboxes whereby we could reduce the number of tests necessary.
For instance, one BoundingBox might contain several others. If we performed a test on the larger, outer BB first and it failed, we could forego performing the same test on anything inside it. This could be useful in situations like culling of objects. If the larger BB does not intersect the viewing frustrum for example, theres no possibility of any of its child BB's from penetrating it.
Next time we'll start laying out the class definition for CBoundingBox and examine its data members more closely.

Have a nice day :)
Posted on 2004-01-13 03:57:35 by Homer
Well I was bored so I decided to make another post immediately.
I want to lay out the class definition for you.
For some of you, this may be your first ever look at an oop class in asm.
I want you to know that I've adopted the ATC oop support macros which were written by Ultrano, a regular user of this board.
There are several other oop implementations around, but I like his one.
Enough waffling, on with the show :)

We will define a top level class (one that doesnt inherit from another class).
Under ATC, we can define Class Methods (functions) two ways:
virtual MethodName will define a Method that can be overridden by a Method of the same name in a class that inherits from the current one.
void MethodName will define a Method that CANNOT be overridden. 'void' does NOT imply that there is no return value, it only refers to that feature of inheritance. This is NOT C++, it just looks a little similar sometimes :P

The class definition looks like this:

class CBoundingBox
;---Class Methods---
void FindBoundingBoxA
void FindBoundingBoxB
void SetBoundingBoxA
void SetBoundingBoxB
void TransformBoundingBox
void IsIntersecting
void LazyIsIntersecting
void IsPenetrated
;---Class Data---
long valid
array points,D3DXVECTOR3,8
array planes,D3DXPLANE,6
endclass

Now some notes.
We do not need to describe the number or type of params for Methods.
There are several keywords (theyre macros) we can use to add various data types to our Class. Here's a few of them:

char - defines a named BYTE
short - defines a named WORD
long - defines a named DWORD
float - defines a named 32bit FLOAT (real4)
real - defines a named 64bit FLOAT (real8)

The 'array' type was only added to ATC by me today and may be subject to change without notice. Previously I had been using a macro called 'AddClassData' which is part of ATC and is used internally to define the various datatypes, and can be used to add unhandled types.
For the curious among you who have the latest version of ATC and are wondering where the 'array' macro is, its right here :

array macro argName:REQ, argType:REQ, argNum:REQ
AddClassData <argName argType argNum dup (<?>)>
endm

===========
The Class Data
===========
valid is defined as a DWORD, but probably should be a BYTE since its merely a BOOLEAN flag that is used to determine whether a particular instance of the class object has been initialised or not.
points is an array of 8 vec3's that define the xyz values of the 8 corners of a box.
Note here that the box does not have to be regular, it can be trapezoidal (squashed), it just has to have eight corners.
planes is an array of 6 planes which define the planes formed by the six sides of the box.
Nothing has been given any initial values, but ATC will zero everything when an object instance is created.

Once we have defined the class above in our source, we can create any number of instances of the class ('objects') using the 'new' directive (another macro).
'new' returns a pointer to the object instance which should be stored somewhere, and has been setup like '\$invoke' to allow the following syntax:
mov pBB, new (CBoundingBox)
See, it DOES look like C++ :grin:

I modified my own version of 'new' to preserve ecx register, the reasons for this will become obvious when we start looking at the code, and I'll ask Ultrano to make this change standard in the next public release of ATC.

Thats it for my posting for today, I know I rambled a lot, I'm sure those unfamiliar with ATC oop programming will appreciate it all the same.

Have a nice day :)
Posted on 2004-01-13 05:17:14 by Homer
Afternoon, EvilHomer2k.

An idea I had which is yet to be explored is the concept of creating HIERARCHIES of boundingboxes whereby we could reduce the number of tests necessary.
For instance, one BoundingBox might contain several others. If we performed a test on the larger, outer BB first and it failed, we could forego performing the same test on anything inside it. This could be useful in situations like culling of objects. If the larger BB does not intersect the viewing frustrum for example, theres no possibility of any of its child BB's from penetrating it.

This is basically how you use an Octree. It's the modern replacement to BSP.
The nice extra feature is that you can actually have deformable objects using Octree culling. Recalculation during realtime is no problem (unlike the preprocessed data for BSP).
When I say "Deformable objects", I mean stuff like allowing the player to blow holes in *any* of the walls/etc. With BSP, you have to already select which walls are "blowable".

Are the bounding boxes actual boxes? If used as the view frustrum it wouldn't be correct. The view frustrum angles out from the viewer like a cone (or like a Trapezoid).

Cheers,
Scronty
Posted on 2004-01-13 06:20:40 by Scronty
Scronty,

I did mention that they are deformable in my second posting, quoting myself :
points is an array of 8 vec3's that define the xyz values of the 8 corners of a box.
Note here that the box does not have to be regular, it can be trapezoidal (squashed), it just has to have eight corners.

:)

Are there any decent map editors that produce pre-sorted octrees?
octree and hextree are as old as bsp, but I had no idea they were being applied in such ways, intruiging :)
Posted on 2004-01-13 06:55:28 by Homer
Scronty,
I've just done a little digging around the modern usage of OSP Trees, and I find they have two common forms:
1>Hierarchical Bounding Volumes
2>Canonical Space Subdivision

The descriptions of both types insist that the boundingboxes be pure cubes whose faces are axially aligned to the World Axes, can you think of any good reason for this? Is it to eliminate the need for storing plane information in the nodes, and to allow for using simplistic axial comparison in the math rather than performing plane tests? Or is this just leftover logic from the earliest form of osp (canonical space subdivision)?

To put it plainly, this cubic approach is fine as long as the cubes are large enough such that a rotating object never protrudes through its own cube, but then the cubes are relatively inaccurate for intersection testing, and the whole approach seems unsuitable to long, thin objects, it seems geared towards round or cubic objects.
This includes world surfaces.

Perhaps the tightest-fitting approach might have merit in an osp engine, if planes could be calculated on the fly, or at least not stored in the boundingbox nodes themselves but in a separate mapped database?

What are your thoughts?
Posted on 2004-01-13 22:15:00 by Homer