# Collision between lines and triangles

Is there simple to understand and good collision detection code?

I think the only important thing is to get the collision between a triangle and a line (+ the intersection point)

I also think about noraml-finding for faces and vertices. It would be great if you can help me!

thanks

I am also working on collision detection algorithms and am trying to do simple but powerful implementations that work for any given situation for an arbitrary application.

There are different complexity depending on what level of realism you are looking for.
Here are 4 different kinds of CD that I am currently trying to develope.

1. Point collision
Each object only tests their domain (points) against other objects domain (points) at a given timepoint, to check if the domains overlap or engulfs eachother. If so, a possible collision is possible and further testing is applied. This method may create collision misses if the speeds are too high for the check-granularity (checks per timeunit)

2. Velocity collision
Each object moves through a finite timespace (one process frame) and therefore creates a long sausagelike shape in timespace called a timespace domain. This domain is linear and fairly easy to implement in a CD engine. Each object checks their linear timespace volumes against eachother as in 1. This method catches any collision misses of method 1. but only if the check-granularity isnt to low so that complex motion disappears.

3. Acceleration collision
Each object uses a timespace domain, like that in 2. but here we also use the accelerations influence over the finite timeframe to produce a non-linear motion, creating a bent shape volume to use in the check. Checks are then made similar to 2.
This method is the method of choice for most application using a medium to high check-granularity.

4. Hyper collision
In the similar pattern as 1. 2. and 3. we take yet another step to influence the acceleration in the finite timespace to produce a non-linear timespace domain that are able to do full circles in their motions (which are necessary to do rotational collision detection with low check-granularity). This method allows a sphere shape to travel in a circle, producing a torus volume to use in collision detection.
The volume is checked using similiar method of 2.

You could actually be quite content with method 1. providing your check-granularity (number of frames you run) are presumably high.
Method 2 is abit more complex, but is quite enough for simple 3d shooters like quake3 or other.
Method 3 and preferably 4 are good enough to simulate realtime physics using a fairly high check-granularity, and is a good choice for doing physics in a 3d simulator with low framerate.

There is actually no limit (except CPU) to what level of complexity you desire, only append yet one more factor of influence to the prior factor using the basic laws of physics.

As for links to code or such, I can give you none. But maybe others in these forums can.

The links above from WhatEver are excellent implementations of the 2nd method.
Remember that each point in the shape you are checking must be transformed by the logic calculation given by the method timespace equation before checking.

To minimize number of calculations, divide your checking into different layers, also implement event-horizons for each timespace, letting you omit the obvious ‘no-chance-in-hell-out-of-range’ situations. Group your event-horizons into clusters to determine interactive groups. In cases of colliding, you will have to divide the timespace paths into new forks, linked lists of timespace as a suggestion (forks of motion in the same processframe).

And for last, KEEP THAT CHRONOLOGICALLY.

[This message has been edited by Hull (edited 04-30-2001).]

Thanks! It will give me to think a while about the problem but I am sure somethere is the solution.

Yet another reason why I love Game Programming Gems … it has a great algorithm for collision detection, and it includes line/triangle test. Basically, it finds where (if anywhere) the line intersects with the plane of the triangle. Then it projects the triangle and the intersection point onto a 2D plane. This makes the math to find if the point is INSIDE the triangle extremely easy and fast. Now, pick a point inside the triangle (the center is the easiest…its the average of the 3 corners) Now, for each 2D line segment that makes up the triangle, test if the intersection point and the center point are on opposite sides of the line (easy to do using the equation of the line). If they are on the same side of all 3 line segments, you have a collision between the triangle and the ray. Otherwise you dont.

You can also extend this to a ray/convex polygon test. The book also shows how to do quick triangle/triangle intersections based on the above technique.