Lost in the math

[Labdabeta]

I have this problem:

struct Position
{
float x;
float y;
float z;
};
bool CheckCollision(Position *vertices, int numvertices, Position start, Position end)
{
//return true if there was NOT a collision with the polygon defined by the vertices and the vector defined by the two positions.
}

I dont even know where to begin, I thought of stepping through the vector from start to end in small increments, but that would be slow and might pass right through the polygon sans interference. Any hints?

[Taywin]

Hmm... Can't recall the algorithm I used to check for collision in one class I took called "Computational Geometry" when I had to implement an object going through an obstructed environment from a starting position to an end position... I don't have the code in hand right now too... Have to dig into my laptop... Anyway, are you allowed to use boost library?

Edited: By the way, what are the "start" and "end" positions for? If they are the position of traveling path of the polygon itself, the collision cannot be checked because there is no environment data to be compared with the traveling path...

[mike_2000_17]

Wow! You are stepping into a problem that is bigger than you can comprehend (no offense). This problem is the general problem of collision detection. To do this correctly and efficiently is a huge deal.

Generally, to solve this problem, you need to solve a number of very difficult problems.

First, you need a means to efficiently determine if two geometries are intersecting (i.e. colliding). There are a number of ways to do this ranging from closed-form minimum-distance formulas between primitive geometric volumes (boxes, cylinders, spheres, etc.), to optimization-based mathematical programming to determine the minimum distance or interception between meshes (set of polygons attached together making up the boundary of a 3D object, i.e. boundary representations (often called "B-Rep" for short)). The latter usually involves efficient mathematical programming algorithms from simple linear programs (e.g. Dual Simplex Method) to quadratic programs (e.g. Ellipsoid Method) to non-linear methods (e.g. general non-linear optimization methods, like LBFGS). In all cases, the methods generally operate only on convex geometries.

Second, if you deal with non-convex geometries, you need to decompose the volumes into a composite of convex geometries (i.e. Convex Decomposition). And that isn't a particularly easy task by itself. Beyond the complexity of just testing sub-meshes for being convex or not, and actually finding a split that works, there are measures involved to figure out the best split for the mesh such that collision detection on those sub-meshes is most efficient.

Third, in order to perform collision detection efficiently, you have to have methods that "cut through the crap", or, more formally, a dynamic programming method (or "divide-and-conquer", or "pruning strategies"). In the collision detection context, this usually involves Space Partitioning which is a way to compartmentalize or sort your 3D objects (or sub-meshes) according to their spatial distribution. For example, say you shoot a bullet through a scene with several characters and object in it, if you split your entire scene into a grid and categorize each object with what grid slot they are in, then you can simple test collision along all the grid slots that will be traversed by the bullet instead of testing collision with all the objects in the scene. Usually, people implement this using techniques such as Binary Space Partitioning (BSP), Kd-trees, quadtrees, octrees, Discrete Oriented Polytopes (DOP-trees), Axis-Aligned Bounding-Boxes (AABB-trees), Dynamic Vantage-Point trees (DVP-trees), etc.

Finally, to try to predict the collision point along the trajectory of a moving object (like a bullet) and possibly other moving objects (like characters, etc.), you are in even more trouble. The general "bullet-through-a-scene" type of problem is called Ray-Tracing (a term that is also used for high quality light-models, e.g., for photo-quality 3D rendering). With proper minimum-distance algorithms, it's possible to use binary search methods (or better) to find the point of collision along the trajectory (if it is a straight-line, or at least, if it is a reasonable assumption). More generally, these types of problems are solved with so-called "anytime" and "dynamic" algorithms which employ a strategy of successive approximate solutions with increasing precision and reuses previous estimates of the projected point of collision to make an educated guess to start the next iteration, and so on.

In summary, this is a huge deal and a very challenging problem. In most computer games, collision detection is simply done with simply geometric bounding volumes (boxes, spheres, cylinders, etc.) and space partitioning. But the general collision detection problem with all the possible source of complications (rapid motions, mesh-based representations, exact proximity queries, mesh deformations, large scenes, with few simplifying assumptions, etc.) is very hard and there are and have been a lot of university-level research on finding methods to do this efficiently.

Personally, I would suggest that you use software packages that have those methods implemented already (from complex to simpler methods), this site is a pretty good starting point. Many Physics Engines also include simple collision detection methods, like ODE. Several geometry packages also have collision detection included (often slower but exact methods).

[mike_2000_17]

>>I thought of stepping through the vector from start to end in small increments, but that would be slow and might pass right through the polygon sans interference. Any hints?

I'll just to add a concrete hint for that particular problem. Try a method like this (a secant-like method):

1) Find the vertex of your mesh that is the closest to the starting point of your line segment.
2) Compute the vector that goes from the start-point to the closest-point from the mesh.
3) Project that vector on the line-segment and that will give you a new point on the line.
4) Repeat the steps (back to 1)) with the new point instead of the start-point.

It will not be as simple as the above, but it's a good start. I believe that if you do the same procedure by starting at the end-point of the line-segment, you should be able to finish both algorithms and get points on the line-segment that should tell you if there is a collision or not. Also, using the normal vectors associated with the vertices of your mesh is an important information to determine if a collision actually occurs.

But more formally, this problem is easily solved with a Simplex Method.

[Labdabeta]

Don't you just hate it when you bite off more than you can chew? I am in Grade 12 taking a first year university programming course, I guess I will have to wait until later to learn some of the techniques on how to do this :(. For now I will work on a slow but functional version that I already have (it saves a set of CollisionCheck unions that can be spheres, or planes, then checks each one) Thanks for your help!

[mike_2000_17]

>>it saves a set of CollisionCheck unions that can be spheres, or planes, then checks each one

Definitely, this is the way to go. Doing collision checks between simple 3D shapes is a method that is accessible to a novice programmer and it is often sufficient for many purposes.

[doug65536]

Mike is talking about industrial strength optimal ways to handle it.

A while ago I developed a very simple way of doing it that is not even close to optimal but isn't too bad:

For triangle A B C calculate the vector

N = crossproduct(normalize(B - A), normalize(C - A))

This will give you the surface normal of the plane, N. Make a plane equation P for the plane:

P = -dotproduct(N, A)

Now we can calculate the distance 'start' is from the plane:

startDist = dotproduct(N, start) + Pd

And we can calculate the distance 'end' is from the plane:

endDist = dot(N, end) + Pd

If startDist is not the same sign as endDist then maybe it goes through the plane. If they are the same sign, the line segment between start and end couldn't possibly go through the plane.

Assuming they are different signs, we need to calculate the actual intersection point. We can do that by taking

intersectFrac = startDist / (endDist - startDist)

to calculate how far along the segment between start end end the intersection of the plane lies.

We can normalize the vector

start + (end - start)

and scalar multiply it by intersectFrac to find the exact point where that line intersects the plane.

We can use the surface normal, and each of the three line segments to generate "extruded edges" for the triangles, making planes that face "into" the triangle formed by the edges AB, BC, CA, using cross product. You can then make sure that the intersection point is in front of all three of those planes. If so, then you have successfully confirmed that the line segment from start to end does penetrate the triangle formed by those vertices.

As I said, nowhere near optimal, but hopefully understandable enough for a light-duty implementation.

HTH

[Labdabeta]

Thank you!