I am making a 3D engine, and I need collisions. Since I have rotating objects, I've thought of using Oriented Bounding Box, and I've also heard that Separating Axis Theorem helps simplify this. I am having trouble getting started, I would love it if anyone can help give me the core mechanics and a base system.

While I have not made a good collision system in 3d, I have done some research and made some progress on the topic, so I thought I would share my two cents until someone else who is more qualified is willing to comment what worked for them.

I would advise that before you do anything is consider if there is a work around to any physics you need beforehand, and if you absolutely need collisions. Collision detection and response are very complicated, which I can attest to because I have tried to do a form of physics collisions in 2d which have not worked out great, and 3d collision is much more complicated than 2d.

Here are some sources I have found helpful for what I have accomplished and have researched:

Rigid Body Dynamics - Chris Hecker's Website - this website covers collision response, but is very complicated and every implementation of it I have failed to get to work. It's divided into four separate articles.

YouTube: Deriving 3D Rigid Body Physics and implementing it in C/C++ (with intuitions) - This video covers the rotation issue with rigid bodies, which I would watch for more detail on how the rotation mechanics works if you wish to account for things like the Tennis Racket Theorem which demonstrates how actual rigid bodies rotate without forces acting on them. This is one thing I was actually able to implement so if you need pointers on this specific topic just ask.

Rigid Body Collisions - this is a 2d demo with explanation similar to Chris Hecker's website. This is one thing I attempted to implement but failed to do a great job at.

All of these show general formulas you will need and can help you consider if you need these physics collisions. In most of my 3d projects, when thinking about when I would do collisions it always ended up working out better to find some sort of easy collision or a way to botch the physics. I apologize that I don't have a working collision simulator for you, but in my own research this is what I have found that was most helpful.

As for what I have done with Rigid bodies I would recommend using Rotation Matrices to store orientation, as they are the easiest in my opinion to work with physics wise. Then you can use their inverse (which is easy to caluclate for orthoganal aka rotation matrices) to calculate weather a point is inside a Oriented bounding box.

This is about as much as I can say. If anyone else has more experience please correct me on anything, I only put this out because most people who are experienced with this stuff have moved on from scratch or are too busy education wise to comment.

Finally, if you don't mind me asking, what do you intend to do with your 3D engine? Understanding this can help you narrow down which aspects of physics collision detection and response you actually need.

I'm working on this for an engine, but will later use it for a game, and since i've introduced rotation, I thought of trying OBBs. I know about rotating axis vectors and using half lengths, but not about combining the two to make an OBB. I've been told that Separating Axis Theorem can help, but I don't know how to project a 3D point onto a 1D line. For the rotations, the type I'm using is quaternions. Flexible and memory efficient, I can simply use the objects' quaternions to get axis vectors, but I need more.

If I remember right, I believe that the formula for projecting a 3d point onto a line is as follows:
Given a line defined by vector v and point P, a point x can be projected onto this line by
where * is the dot product and |v| is the length of the vector. This is also denoted as
If you are having trouble reading this formula a clearer version can be found on This Wikipedia article.

I've never tried OBB's or used the separating axis theorem, but this is one formula I would use if I were you. I also have never tried using quaternions, so I can't help you much with those.

For OBB's to check a point's collision you would take your point x, do the inverse translation on it based on the bounding box's location, and then do the inverse rotation on the new point, then that final point is what you would check is in the bounding box or not.

This is about the extent of my knowledge on this topic.

Okay, let's break this down, I can extract points as (x, y, z), and I do have some vector math using Pythagorean theorem(works in all dimensions), let's say I have the x, y, and z components of a point and a line as a vector, using this, would would the formula be?

If you have the direction vector of a line and a vector that connects two 3D points, then you can get distance of the points along the line using dot product

(Edit: I started writing this when the above two posts didn't exist)

Okay, I managed to work it out:

set [d_p v] to ((((px) * (ax)) + ((py) * (ay))) + ((pz) * (az)))
set [a^2 v] to ((((ax) * (ax)) + ((ay) * (ay))) + ((az) * (az)))
set [s v] to ((d_p) / (a^2))
set [pro_x v] to ((ax) * (s))
set [pro_y v] to ((ay) * (s))
set [pro_z v] to ((az) * (s))

px, py, pz are point inputs, ax, ay, az are axis vectors, and pro_x, pro_y, pro_z are the outputs, this should help, thanks!

Matthobro120 wrote:

Okay, let's break this down, I can extract points as (x, y, z), and I do have some vector math using Pythagorean theorem(works in all dimensions), let's say I have the x, y, and z components of a point and a line as a vector, using this, would would the formula be?

Say the point P is defined with (Px,Py,Pz) and the vector (vx,vy,vz), and you are trying to project point (x,y,z)

Then the formula becomes

set [x_p v] to ((Px)+((vx)*((((((x)-(Px))*(vx))+(((y)-(Py))*(vy)))+(((z)-(Pz))*(vz)))/((((vx)*(vx))+((vy)*(vy)))+((vz)*(vz))))))
set [y_p v] to ((Py)+((vy)*((((((x)-(Px))*(vx))+(((y)-(Py))*(vy)))+(((z)-(Pz))*(vz)))/((((vx)*(vx))+((vy)*(vy)))+((vz)*(vz))))))
set [z_p v] to ((Pz)+((vz)*((((((x)-(Px))*(vx))+(((y)-(Py))*(vy)))+(((z)-(Pz))*(vz)))/((((vx)*(vx))+((vy)*(vy)))+((vz)*(vz))))))

or more clearly:

Matthobro120 wrote:

Okay, I managed to work it out:

set [d_p v] to ((((px) * (ax)) + ((py) * (ay))) + ((pz) * (az)))
set [a^2 v] to ((((ax) * (ax)) + ((ay) * (ay))) + ((az) * (az)))
set [s v] to ((d_p) / (a^2))
set [pro_x v] to ((ax) * (s))
set [pro_y v] to ((ay) * (s))
set [pro_z v] to ((az) * (s))

px, py, pz are point inputs, ax, ay, az are axis vectors, and pro_x, pro_y, pro_z are the outputs, this should help, thanks!

This is close, but only works if your line passes through the origin, so you need to change px,py,pz with (x-Px) (y-Py) (z-Pz), where the line passes throught point (Px,Py,Pz). which you then need to add P back on to the points like in my example

Yes, my formula does go only through the origin, but since it accounts for rotations and scaling, I can just translate the results, especially since 6 of the 15 axis vectors go through an object. I would like to know how to figure out cross products though.

The formula for cross products can also be found on Wikipedia. In scratch code it looks like

define Cross product (x1)(y1)(z1) , (x2)(y2)(z2)
set [x v] to (((y1)*(z2))-((z1)*(y2)))
set [y v] to (((z1)*(x2))-((x1)*(z2)))
set [z v] to (((x1)*(y2))-((y1)*(x2)))

Does that cross product formula work with the location of the vector's relative origin?

Vectors are equivalent no matter where they start, so long as they have the same direction and magnitude.
This formula is for two specific vectors and gives their cross product. You can use the difference of two points to represent a vector, but mathematically their values don't depend on where the tail of the vector is. Glad I've been able to offer some assistance, because I have never tried to use OBB's.

You're right, both objects just need to be projected onto the same axis, the location doesn't change the result.

One thing that might be easier than projecting it onto the line is finding the scalar projection, which gives you a single number to compare vs multiple. It is calculated with
and in code would look like

set [d_p v] to ((((px) * (ax)) + ((py) * (ay))) + ((pz) * (az)))
set [a^2 v] to ((((ax) * (ax)) + ((ay) * (ay))) + ((az) * (az)))
set [pro v] to ((d_p) / ([sqrt v] of (a^2))

Where like you defined, px,py,pz are points, ax,ay,az is the axis vector and pro is your output. To find overlap you would then find the maximum and minimum values of pro for each shape's points, then compare them to see if they overlap.
visually:
Where the scaler projection would return a single number representing how far each point is on the axis. If the maximum of shape a is larger than the minimum of shape b, and the maximum of shape b is greater than the minimum of shape a, then you have overlap, otherwise, no overlap. This will probably help more than the vector projection.

Okay, thanks! I'll keep this open for code or if something doesn't work out.