3D Collision Algorithms
» >
»
» View previous topic :: View next topic  
I've been working on this for a while now, and it's barely making any sense as is. I've gotten some direction from fellow Cemetech member(s), and made a little foot-way. The project is designed in C#, with the OpenGL lib. The models are loaded from OBJ files into ram, and drawn with limited texturing (one texture per model). The goal at this point, is to search through every 'face', or 3d triangle, and check the players movements to see if it will collide with the triangle, and where. At this point, I am only coloring the triangles that the algorithms ping as a collision.

Terms/formulas you may need to be familiar with:
Ray-Plane Intersection
Line-Plane Intersection
Barycentric Coordinates
Matrix Calculations
Dot/Cross Products

Quick Run down:
Ray-Plane Intersection determines if a player 'will eventually' collide with a plane if they keep moving in a specified direction vector. This is done by 'flattening' the starting vector, and the plane, and check the area of the 3 triangles created versus the main triangle.

Line-Plane Intersection determines if a player's movement crosses the threshold of a triangle. No matter how much I read through this, I still don't quite understand it. That's probably why it still doesn't work.

Barycentric Coordinates determine the exact coordinates on a plane given a vector. I still don't understand how to formulate this with the variables I have, so I don't use it. Not to say it isn't practical.

Here's the current code (will be updated as progress is made):
[EDIT]
made several formulas and i parse them all, and color the triangles accordingly.
Main Loop (under update):

Code:

            if (!player.pos.Equals(dest))
            {
                collisions = new Model();
                List<Vector> verts = new List<Vector>();
                List<Vector> norms = new List<Vector>();
                List<Color> colors = new List<Color>();

                Stopwatch stopwatch = new Stopwatch();
                stopwatch.Start();

                //ParallelLoopResult result = Parallel.For(0, World._rawdata._Tri.Count(), i =>
                for (int i = 0; i < World._rawdata._Tri.Count(); i++)
                {

                    //Gl.glTranslated(0, -player.pos.Y, 0);
                    //Gl.glTranslated(player.pos.X, player.pos.Y, player.pos.Z);

                    Vector[] face = { World._rawdata._Vert[World._rawdata._Tri[i].Vertex[0]], World._rawdata._Vert[World._rawdata._Tri[i].Vertex[1]], World._rawdata._Vert[World._rawdata._Tri[i].Vertex[2]] };
                    Vector[] norm = { World._rawdata._Norm[World._rawdata._Tri[i].Normal[0]], World._rawdata._Norm[World._rawdata._Tri[i].Normal[1]], World._rawdata._Norm[World._rawdata._Tri[i].Normal[2]] };

                    Gl.glLoadIdentity();
                    /*if (RayPlane(player.pos, dest, face, norm[0]) > 0)
                    {
                        verts.Add(face[0]); verts.Add(face[1]); verts.Add(face[2]);
                        norms.Add(norm[0]); norms.Add(norm[1]); norms.Add(norm[2]);
                        colors.Add(new Color(0, 1, 0, 0.5f)); colors.Add(new Color(0, 1, 0, 0.5f)); colors.Add(new Color(0, 1, 0, 0.5f));
                    }*/
                    if (XNARayPlane(player.pos, dest, face, norm[0]) > 0)
                    {
                        verts.Add(face[0]); verts.Add(face[1]); verts.Add(face[2]);
                        norms.Add(norm[0]); norms.Add(norm[1]); norms.Add(norm[2]);
                        colors.Add(new Color(0, 0, 1, 0.5f)); colors.Add(new Color(0, 0, 1, 0.5f)); colors.Add(new Color(0, 0, 1, 0.5f));
                    }
                    if (LinePlane(player.pos, dest, face, norm[0]))
                    {
                        verts.Add(face[0]); verts.Add(face[1]); verts.Add(face[2]);
                        norms.Add(norm[0]); norms.Add(norm[1]); norms.Add(norm[2]);
                        colors.Add(new Color(1, 0, 0, 0.5f)); colors.Add(new Color(1, 0, 0, 0.5f)); colors.Add(new Color(1, 0, 0, 0.5f));
                    }
                    Vector size = player.model.getSize();
                    if (XNABoundingBox(new Vector(size.X / 2 - dest.X, size.Y / 2 - dest.Y, size.Z / 2 - dest.Z), size, face, norm[0]) == 0)
                    {
                       
                        verts.Add(face[0]); verts.Add(face[1]); verts.Add(face[2]);
                        norms.Add(norm[0]); norms.Add(norm[1]); norms.Add(norm[2]);
                        colors.Add(new Color(0, 1, 0, 0.5f)); colors.Add(new Color(0, 1, 0, 0.5f)); colors.Add(new Color(0, 1, 0, 0.5f));
                    }
                }//);
                collisions._rawdata._Vert = verts.ToArray();
                collisions._rawdata._Norm = norms.ToArray();
                int a = 0;
                collisions._vertexArray = new float[(collisions._rawdata._Vert.Count()) * 3 * 3];
                foreach (Vector v in collisions._rawdata._Vert)
                {
                    collisions._vertexArray[a + 0] = v.X;
                    collisions._vertexArray[a + 1] = v.Y;
                    collisions._vertexArray[a + 2] = v.Z;
                    a += 3;
                }
                a = 0;
                collisions._vertexNormal = new float[(collisions._rawdata._Norm.Count()) * 3 * 3];
                foreach (Vector v in collisions._rawdata._Norm)
                {
                    collisions._vertexNormal[a + 0] = v.X;
                    collisions._vertexNormal[a + 1] = v.Y;
                    collisions._vertexNormal[a + 2] = v.Z;
                    a += 3;
                }
                a = 0;
                collisions._vertexColors = new float[(collisions._rawdata._Vert.Count()) * 4 * 3];
                foreach (Color c in colors)
                {
                    collisions._vertexColors[a + 0] = c.Red;
                    collisions._vertexColors[a + 1] = c.Green;
                    collisions._vertexColors[a + 2] = c.Blue;
                    collisions._vertexColors[a + 3] = c.Alpha;
                    a += 4;
                }
                //while (!result.IsCompleted)
                //;

                stopwatch.Stop();
                //System.Console.WriteLine("[" + DateTime.Now.ToString("HH:mm:ss+ff") + "] <System>: Collision detections took: " + stopwatch.ElapsedMilliseconds + " miliseconds.");
                /*System.Console.WriteLine("[" + DateTime.Now.ToString("HH:mm:ss+ff") + "] <System>: Will collide with "+raycount+" faces,"+
                    "\nimmediate collisions "+(allow_move? "detected" : "not detected")+","+
                    "\nfound in " + stopwatch.ElapsedMilliseconds + " miliseconds.");*/
                stopwatch.Reset();
                player.pos = dest;
            }


XNARayPlane:

Code:

        int XNARayPlane(Vector start, Vector end, Vector[] face, Vector norm)
        {
            Vector direction = end.Subtract(start);
            Ray ray = new Ray(new Vector3(start.X, start.Y, start.Z), new Vector3(direction.X, direction.Y, direction.Z));

            Plane plane = new Plane(new Vector3(face[0].X, face[0].Y, face[0].Z), new Vector3(face[1].X, face[1].Y, face[1].Z), new Vector3(face[2].X, face[2].Y, face[2].Z));
            plane.Normal = new Vector3(norm.X, norm.Y, norm.Z);
            float? distance = ray.Intersects(plane);
            if (distance == null)
                return -1;
            Vector3 contact = ray.Position + ray.Direction * distance.Value;
            Vector p = new Vector(contact.X, contact.Y, contact.Z);
            double dist = p.Distance(start);
            double a = direction.Length();
            double b = end.Distance(start);
            if (dist < direction.Length())
            {
                //dest = start;
                return 2;
            }
            return 0;
        }


XNABoundingBox:

Code:

        int XNABoundingBox(Vector start, Vector end, Vector[] face, Vector norm)
        {
            BoundingBox box = new BoundingBox(new Vector3(start.X, start.Y, start.Z), new Vector3(end.X, end.Y, end.Z));

            Plane plane = new Plane(new Vector3(face[0].X, face[0].Y, face[0].Z), new Vector3(face[1].X, face[1].Y, face[1].Z), new Vector3(face[2].X, face[2].Y, face[2].Z));
            plane.Normal = new Vector3(norm.X, norm.Y, norm.Z);

            var type = box.Intersects(plane);
            if (type == PlaneIntersectionType.Front)
                return 1;
            return 0;
        }


Line-Plane:

Code:

bool LinePlane(Vector start, Vector end, Vector[] face, Vector norm)
        {
            //Vector direction = end.Subtract(start);
            Vector direction = end;

            // Prepare our barycentric variables
            Vector u = face[1].Subtract(face[0]);
            //Vertex u = new Vertex(face[1].X - face[0].X, face[1].Y - face[0].Y, face[1].Z - face[0].Z);
            Vector v = face[2].Subtract(face[0]);
            //Vertex v = new Vertex(face[2].X - face[0].X, face[2].Y - face[0].Y, face[2].Z - face[0].Z);
            Vector w = end.Subtract(face[0]);
            Vector vCrossW = Vector.Cross(v, w);
            Vector vCrossU = Vector.Cross(v, u);

            // Test sign of r
            if (Vector.Dot(vCrossW, vCrossU) < 0)
                return false;

            Vector uCrossW = Vector.Cross(u, w);
            Vector uCrossV = Vector.Cross(u, v);

            // Test sign of t
            if (Vector.Dot(uCrossW, uCrossV) < 0)
                return false;

            // At this piont, we know that r and t and both > 0
            float denom = uCrossV.Length();
            float r = vCrossW.Length() / denom;
            float t = uCrossW.Length() / denom;

            if (!(r <= 1 && t <= 1 && r + t <= 1))
                return false;
            return true;
        }


What is expected:
Any blocks that match the XNARayPlane should be colored 50% blue. LinePlane's are drawn 50% Red, and XNABoundingBox are colored Green. Looking for color changes when I move to, or through a plane, and only that plane should light up.

What really happens:
Odd collisions detected in obscure locations. Few accurate flickers. The closest match seems to be the LinePlane formula, but it still appears to be off.



I've started to get the sneaky feeling that something with OpenGL is affecting the coordinates where it shouldn't be. No proof, nor links suggesting such an act could happen.

PROGRESS!
After many hours of re-reading through all of my code, I found my cross product formula had a single mixed up math value. Changed that, and my line-plane function is doing rather well. Downside is that it's not perfectly accurate (triggers sooner than a plane is intersected) and there seems to be a vast vertical mishap where the ceiling or floor can be a great distance away and still be triggered. I would greatly appreciate an extra mind looking into my math, and see if there's anything I can do to add some accuracy.

MOAR PROGRESS!
Got together with a friend who helped me sort through some codez and we got something a little more accurate, but with a few bugs to whittle through:


Code:
bool LinePlane2(Vector start, Vector end, Vector[] face, Vector norm)
        {
            //Vector tmp;

            //tmp = start.Subtract(end);
            Vector3 lineDirection = -end.Vec3 - -start.Vec3;//end.Subtract(start).Vec3;
            //lineDirection.Y = -end.Y - -start.Y;
            // Prepare our barycentric variables
            // UV are our pixel coordinates in a 0 to 1 range
              Vector3 u, v, triangleNormal;

            //tmp = face[1].Subtract(face[0]);
              u = face[1].Subtract(face[0]).Vec3;
           
            //tmp = face[2].Subtract(face[0]);
              v = face[2].Subtract(face[0]).Vec3;

            triangleNormal = Vector3.Cross(u, v );

            // Paranoid Check for collapsed triangle
            if ( triangleNormal == new Vector3(0.0f,0.0f,0.0f) )
            {
                // triangle is degenerate
                return false;
            }


            //tmp = face[0].Subtract(end);
            Vector3 triangleToLineDirection = face[0].Subtract(end).Vec3; 

            // Parameters for ray/plane intersection
            float a, b, r;

            a = Vector3.Dot(triangleNormal , triangleToLineDirection);

            b = Vector3.Dot(triangleNormal, lineDirection);

            if (a < 0.0001f) // parallel check
            {
                if (a == 0)
                {
                    // ray lies in triangle plane
                    return false;
                }
                else
                {
                    // ray is disjointed from triangle's plane
                    return false;
                }
            }

            r = a / b;
            if ( r < 0.0f )
            {
                // Line points away from triangle
                return false;
            }
 
            // This is the intersection point of the line direction to the triangles plane
            //tmp = start;
            //Vector3 intersectionPoint = start.Vec3;
            Vector3 intersectionPoint = Vector3.Add(start.Vec3, lineDirection * r);

            // This is crazy vector dot product math that essentially is a set of line to point
            // collision checks
            float    uu, uv, vv, wu, wv, D;
            uu = Vector3.Dot(u,u);
            uv = Vector3.Dot(u,v);
            vv = Vector3.Dot(v,v);

            // Now we are getting ray from the intersection point to the refrence
            // point on the triangle
            //tmp = face[0];
            Vector3 refrencePointOnTriangle = face[0].Vec3;
            Vector3 w = intersectionPoint - refrencePointOnTriangle;

            wu = Vector3.Dot(w,u);
            wv = Vector3.Dot(w,v);

            D = uv * uv - uu * vv;

            // Testing the "parametric" coordinates
            float s, t;
            s = (uv * wv - vv * wu) / D;
            if (s < 0.0 || s > 1.0)        // I is outside T
            {
                // Line Intersection is outside of the Triangle
                return false;
            }

            t = (uv * wu - uu * wv) / D;
            if (t < 0.0 || (s + t) > 1.0)
            {
                // I is outside T
                return false;
            }

            // The line does intersect
            return true;
        }


Bug A: Seems to catch on 0X, 0Y plane-touching triangles.
Bug B: Seems to catch on triangles intersecting with a ray behind the players direction.
Have you stepped through this in a debugger and compared some of the calculations being performed to reference values?
<- Please Support on Lego Ideas
It's difficult to tell exactly what's going on and why a collision happens in one location, and not another when the map is drawn away from the location it should be at. I should be spawning at 0, 0, 0 which should be the center of my bedroom map that i created, but instead, it's a bit off in the distance. Fiddling with the lookat coordinates, but I'm awfully terrible at this XD



Coordinates repaired, Collisions not being detected where walls are. It seems to detect that collisions 'will' occur, so my best guess is that my formula:

Code:
Vector c0 = new Vector(start.X + direction.X * t, start.Y + direction.Y * t, start.Z + direction.Z * t);

Does NOT give me the exact coordinates of the eventual collision.
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
3D Collision Algorithms
»
» View previous topic :: View next topic  
Page 1 of 1
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement