Dev Log 2: AABB tree implementation (part1)

I decided to begin with the broadphase and the first question I had was "Would be better to implement the whole physics engine with ECS?" Well there is no much information about the performance gains of this method so I will go with the classical OOP approach.

As the name sugest we need an AABB. First we are gonna define what an AABB is.

Axis Aligned Bounding Box, AABB for short, is a box that delimit an object extents with the particularity of being always aligned to the world axes.

Defining the AABB

You can represent an AABB in 2 ways.

By it extents:

vec3 min_extents; vec3 max_extents;

Or by half extents:

vec3 position; vec3 half_extents;

Here you can go with whatever you want, might depend on how you use it that one may perform better than the other. I choose the first way.

Transforming the AABB

This is a fairly difficult topic, well at least if you want to do less operations. First I will show the intuitive way and then the way bullet3d does it (to be honest I believe bullet3d use another method more efficient with quaternions but I found this in their source code too and I understand this one).

Intuitive way:

Well everybody think to just descompose the aabb into its 8 vertices transform them and then calculate an aabb from them. In other words, rotate the aabb and calculate a new aabb to that obb. For simplicity I show 2D case.

PseudoCode:

vec3 vertices[8]; vec3 halfExtentNew; for vert in vertices: vert = tranform * vert; if vert.x > halfExtentNew.x: halfExtentNew.x = vert.x; if vert.y > halfExtentNew.y: halfExtentNew.y = vert.y; if vert.z > halfExtentNew.z: halfExtentNew.z = vert.z;

Bullet3d way:

This one took me a while to understand it since there is no explanation everywhere just the code.

To get it clear we have to remember:

• The dot product between a unit vector and another vector gives the length of the projection of the vector on to the unit vector.

• The transform matrix columns are the vectors of the new coordinates system.

SInce we want the maximum projection we need the axis vectors to be absolute values so we copy our transform matrix with absolute values.

Then the new halfExtents are the dot products of halfExtents by each absolute axis.

float Xprime = dot(halfExtents, transform[0]) asume column major float Yprime = dot(halfExtents, transform[1]) float Zprime = dot(halfExtents, transform[2]) vec3 halfExtentsNew = (Xprime, Yprime, Zprime)

and the new center is the 3rd column of the transform matrix

vec3 center = transform[3].xyz;

The white axes are the world axes The yellow axes are the new axes The yellow X axis and the orange Y axis are the absolute axes The cian vectors in the aabb center represents the Yprime and the Xprime I didnt put the aabb on the new center but you get the idea.

Most of the time the center is in between the max and min extents but that depends on how you implement it.

Volume of the AABB:

Needed for balancing the binary tree in part 2.

This is easy as side by side by side.

vec3 size = max_extent - min_extent float volume = size.x * size.y * size.z

Union of 2 AABB:

This function is used to create branches AABBs. Explained in part2.

We need the biggest value of each AABB so we do:

for i in range(3): max_new[i] = (right.max[i] > left.max[i]) ? right.max[i] : left.max[i] min_new[i] = (right.min[i] < left.min[i]) ? right.min[i] : left.min[i]

Check if an AABB contain another AABB:

This function is used to get the nodes to reinsert in the tree. Expained in part2.

As we see in the picture above for an AABB1 to contain a AABB2, the first most have bigger max extents and smaller min extents. So to check that we do the next as show in the snippet code:

bool contains = false for i in range(3): contains = max_extent1[i] > max_extent2[i] && min_extent1[i] < min_extent2[i] && contains;

Notes:

This part of the project taught me very good thing that I strugled with when I was younger like navigating huge source code written by others and understanding the how the code works by just looking at it since there is no wiki about how the code works.

That's it for this post, folks. Bye!