How does ray collision work?


Most of us know of the ray collision detection. In Blender Bullet physics we call rayCast to do this collision detection. However, I want to find out the math behind this. I need to only for ray/triangle and ray/sphere collision cases.
The inputs aviable are:

  • Ray([vector] starting point position, [vector] ending point position)
  • Triangle([vector] vertex 1 position, [vector] vertex 2 position, [vector] vertex 3 position)
  • Sphere([vector] sphere center position, [float] sphere radius)

Outputs needed:

  • Collision([boolean] collides or not)

I hope that you can help me solving this.


You just need the formulas for ray/line and sphere or triangle/plane intersection. If you google that, you also find explanations how those can be derived.

you can access most of these functions inside mathutils,

you can also use a bvhtree raycast to get a ray /face intersection

It is not a collision (in terms of physics) as a ray is not a physics object. A ray is just a line.

So basically you can look for:

  • line intersecting plane
  • line intersecting sphere/circle

These are formulas typically taught at school. So you should be able to find plenty of materials.

To transform a plane to a triangle, quad, polygon you “simply” check if the found intersection point is inside the polygons boundary. It already has to be on top of the plane. So it reduces to a simpler 2D-operation.

The major problem is that you usually do not have a single plane, but a lot of them. While the number is not the issue (it is always the same formula) the accumulated processing time is problematic. Theoretically you need to perform the cross check on all polygons. With some clever organization you can exclude whole chunks of planes with fast checking (e.g. bounding box checks).It can add processing time. This is fine as long as it reduces the overall processing time in a typical scenario.

So you do not just need the formulas, you need some architecture that allows to get a fast (and correct) result.

hint* if you localize a world position of a ray start/ end , you can check it against a bvh tree that is local,(so you dont need to rebalance the tree and update positions when moving*)

build bvh tree on init-> later localize the raycast
start = startWorldPosition-model.worldPosition
start = model.worldOrientation.inverted()*start

same for endpoint*

@BluePrintRandom - you seem to be a real (bvh) tree lover.

It is nice that you love them, but how do you think should an imaginary bvh tree help to find the intersection point of a plane with a line?

it returns exactly what face in the bvh tree was hit and where,

its not imaginary it’s in mathutils,

just pass local points using fromPoly :slight_smile:

I have already used it**

just build on frame zero, and raycast using the world cords localized to the model transform…

here is the raycast against the tree,

biggest saver = finding what face you hit a complex mesh with a ray, without using a triangle mesh physics type*

if you just need to test 1 plane

and the code -

Line can be a 4D conversion to 3D object. In that case it’s just a 4D point(vertex).
So I must search more carefully for the line/plane intersects. OK!
About the checking to reduce calculations - I’ll most likely use a method for both - the triangle which I am checking and the line - to use the circular bounds method. The line’s radius is half of it’s length, but triangles radius is half of it’s longest edges length. I check between their origins(triangles origin is in the centre of longest edge, propably this is how I get it: (vertex1.position + vertex2.position) / 2. And same applies for the line’s origin. Than I just find the distance between them and check for collision only if it is smaller than line radius + triangle radius.

What exactly are you trying to do? Do you want to understand how it works and implement it on your own? Do you want to understand how state of the art physics engines do it?

It is a lot easier to answer your questions if we know this. What you are doing right now seems extremely inefficient in my opinion, but maybe it is efficient for what you are trying to do. Or maybe it is simply good enough.

I am trying to implement it in my own system. I need efficient vertex/triangle collisions(assuming moving vertex).

As a workaround because it is not possible in the Blender Game Engine at the moment?

No. As an only option as I am using custom dictionary based mesh systems for custom physics model.

Is it for your custom softbody experiments? If you want code that will run efficiently you should probably use the mathutils.geometry functions. BPR’s suggestion of the BVH tree is actually not such a bad idea, since you can build it using the mesh data from the tires. I don’t know enough about it to tell you if it requires a different kind of tree though, there are others I seem to recall. I know the designers of the original Doom used BSP trees to help calculate render order of sprites. There are several formal structures like this that can be used in various ways.

But maybe you want to understand the methods yourself, I know you’re young and probably smarter than me so maybe you’ll be writing your own game engine someday soon. If so, python is probably not the best language to use. You might need to give more background about your request though otherwise people might say “just use the built in tools” or “just don’t bother, it’s not worth the effort”. Only you know if it’s worth the effort, but others will judge your question by their own opinions, knowledge and favorite tools.

Yeah… It’s actually not for tires only. I’m writing something universal, that can be used for everything. I basicly do everything manually. I think that I’ll find something good soon.

Go to the bullet 3 repo,

start building bullet for a few months, and come back and integrate bullet 3 when it lands into the bge,

Do you think that it has good softbodies?:smiley: I may try implementing it in BGE, though, but with my own softbodies(using Bullet functions for collisions, integration and springs, but my own setup method). It’d require to create some new features in Blender editor, tho(e.g. support springs).