# Edge vs Edge Collision Detection

This topic is 5196 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi folks I have implemented collision detection for the case of vertex vs face (in the tri-tri scene) through the Badouel's algorithm for ray(vertex)-tracing. I do the tracing with final e initial position of the vertices and test against the faces. It gives me not very fast way to find collisions but a very accurate method. In the same way, i'm looking for a method to test edge vs edge. Any help will be appreciated, thx.

##### Share on other sites
Two edges travelling...

Let's have two segment [A0, B0], and [A1, B1]

the point of collision Pcoll will satisfy the equations

Pcoll = A0 + u * D0
Pcoll = A1 + v * D1 + Vrel * tcoll

where D0 = (B0 - A0), D1 = (B1 - A1)

Edge0 is assumed to be static, Vrel being the realtive velocity of edge1 from edge0 (Vrel = V1 - V0).

and

0 < u < 1
0 < v < 1
0 < t < 1

three unknown, only one equation :/

alternatively.

If edge1, that is travelling, is to collide with edge 0, then edge1, at the moment of collision will be in the plane [D0 x D1, A0].

To find the time edge1 hits that plane, it's a simple raytrace.

N = (D0 x D1)
t = ((A0 - A1) . N) / (Vrel . N)

if 0 < t < 1, then no collison.

To find the distance between the segments at the time of impact, it's quite simple, it the usual 3D line-line intersection / distance calculation. That will give you the u and v from above, that you can check for bounds.

##### Share on other sites
So, you are planning to use ray casting for detect collisions on a physics simulation?
I've heard about that topic early. The question is if that method is better than any distance algorithm?

Distace algorithms are like GJK, separating axis, voronoi and so.

And about ray casting, it seems that True Axis Engine applies it on its collision detection process. At this time, True Axis Engine shows better performance that others engines around the corner, like Newton or ODE.

But, anybody knows some paper that explain an optimized method for raycasting?
Ray should be the velocities? or the path of each vertex during a time step?

##### Share on other sites
Hi leoptimus

Sorry my delay.

I'm doing my first engine and i chose ray rasting for intersections just because it looks good hehe i don't know about performance between ray rasting and others...

Badouel's algorithm for ray-casting: http://graphics.cs.msu.su/courses/cg_el99/intersect.html
i'm using it, a very fast way...

##### Share on other sites
Quote:
 Edge0 is assumed to be static, Vrel being the realtive velocity of edge1 from edge0 (Vrel = V1 - V0).

But the velocity varies along the edge, should i use the midpoint's velocity to calculate the vel from an edge?

##### Share on other sites
varies along the edge?

Oh, you don't want to do that... Most collision detection works with uniform translations only. No rotations. Else it becomes much much much... more complicated.

##### Share on other sites
but... but... how the collision detection will work without rotation? just imagine a cube rotating, not translating, i'll never get a collision.

I can't figure out how to make the collision detections work without time-slicing in the case of edge-edge. Perphaps generating a volume with vertices of edge1(t0) edge1(t1) and testing it against edge0... i don't know how to proceed :/

or should i wait the delivery of Real-time Collision Detection from amazon? -.-

##### Share on other sites
that will give you lots of pointers, yeah.

There are loads more techniques, an obvious one would be to intersect polygons (or edge with triangles) between your rotating cube and whatever you want to collide with. Another is the method of separating axes.

There are more techniques descrbed in Christer's book.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 16
• 11
• 9
• 24
• 52