Collision checking on slopes

Question

I'm working on a new game, and am trying to detect whether or not the player (on a slope) is colliding with a given mesh based off of their coordinates relative to the coordinates of the slope. I'm using this function, which doesn't seem to be working (the slope seems too small or something)

//Slopes



        float slopeY = max.Y-min.Y;

    float slopeZ = max.Z-min.Z;

    float slopeX = max.X-min.X;

    float angle = (float)Math.Atan(slopeZ/slopeY);

    //Console.WriteLine(OpenTK.Math.Functions.RadiansToDegrees((float)Math.Atan(slopeZ/slopeY)).ToString()+" degrees incline");



    slopeY = slopeY/slopeZ;

    float slopeZX = slopeY/slopeX;

    //End slopes

    float surfaceposX = max.X-coord.X;

    float surfaceposY = max.Y-coord.Y;

    float surfaceposZ = min.Z-coord.Z;



    min-=sval;

    max+=sval;

    //Surface coords



    //End surface coords



    //Y SHOULD = mx+b, where M = slope and X = surfacepos, and B = surfaceposZ



    if(coord.X<max.X& coord.X>min.X&coord.Y>min.Y&coord.Y<max.Y&coord.Z>min.Z&coord.Z<max.Z) {







        if(slopeY !=0) {

        Console.WriteLine("Slope = "+slopeY.ToString()+"SlopeZX="+slopeZX.ToString()+" surfaceposZ="+surfaceposZ.ToString());

            Console.WriteLine(surfaceposY-(surfaceposY*slopeY));



            //System.Threading.Thread.Sleep(40000);



        if(surfaceposY-(surfaceposZ*slopeY)<3 || surfaceposY-(surfaceposX*slopeZX)<3) {

        return true;

        } else {

        return false;

        }

        } else {

        return true;

        }



    } else {





    return false;

    }

Any suggestions?

Sample output:

59.86697
6.225558 2761.331
68.3019 degrees incline
59.86698,46.12445
59.86698
6.225558 2761.332
0 degrees incline

EDIT: Partially fixed the problem. Slope detection works, but now I can walk through walls???

//Slopes



        float slopeY = max.Y-min.Y;

    float slopeZ = max.Z-min.Z;

    float slopeX = max.X-min.X;

    float angle = (float)Math.Atan(slopeZ/slopeY);

    //Console.WriteLine(OpenTK.Math.Functions.RadiansToDegrees((float)Math.Atan(slopeZ/slopeY)).ToString()+" degrees incline");



    slopeY = slopeY/slopeZ;

    float slopey = slopeY+1/slopeZ;

    float slopeZX = slopeY/slopeX;

    //End slopes

    float surfaceposX = min.X-coord.X;

    float surfaceposY = max.Y-coord.Y;

    float surfaceposZ = min.Z-coord.Z;



    min-=sval;

    max+=sval;

    //Surface coords



    //End surface coords



    //Y SHOULD = mx+b, where M = slope and X = surfacepos, and B = surfaceposZ



    if(coord.X<max.X& coord.X>min.X&coord.Y>min.Y&coord.Y<max.Y&coord.Z>min.Z&coord.Z<max.Z) {







        if(slopeY !=0) {

        Console.WriteLine("Slope = "+slopeY.ToString()+"SlopeZX="+slopeZX.ToString()+" surfaceposZ="+surfaceposZ.ToString());

            Console.WriteLine(surfaceposY-(surfaceposY*slopeY));



            //System.Threading.Thread.Sleep(40000);

         surfaceposZ = Math.Abs(surfaceposZ);



        if(surfaceposY>(surfaceposZ*slopeY) & surfaceposY-2<(surfaceposZ*slopeY) || surfaceposY>(surfaceposX*slopeZX) & surfaceposY-2<(surfaceposX*slopeZX)) {

        return true;

        } else {

        return false;

        }

        } else {

        return true;

        }



    } else {





    return false;

    }

Answer 1

Have you considered implementing a BSP tree? Even if you work out the bugs with the code you're using now, it'll be dog slow with a mesh of any decent size/complexity. A BSP or quadtree will go a long way towards simplifying your code and improving performance, and they're very easy to implement.

Edit

Here's a link to a nice BSP tutorial and overview.

If you're only concerned with terrain (no vertical walls, doors, etc), a quadtree might be more appropriate:

Here's a nice quadtree tutorial at gamedev.net.

Both of these algorithms are intended to divide your geometry into a tree to make searching easier. In your case, you're searching for polygons for collision purposes. To build a BSP tree (very briefly):

Define a structure for the nodes in the tree:

public class BspNode
{
    public List<Vector3> Vertices { get; set; }

    // plane equation coefficients
    float A, B, C, D;

    BspNode front;
    BspNode back;

    public BspNode(Vector3 v1, Vector3 v2, Vector3 v3)
    {
        Vertices = new List<Vector3>();
        Vertices.AddRange(new[] { v1, v2, v3 });
        GeneratePlaneEquationCoefficients();
    }

    void GeneratePlaneEquationCoefficients()
    {

        // derive the plane equation coefficients A,B,C,D from the input vertex list.
    }

    bool IsInFront(Vector3 point)
    {
        bool pointIsInFront=true;
        // substitute point.x/y/z into the plane equation and compare the result to D
        // to determine if the point is in front of or behind the partition plane.
        if (pointIsInFront && front!=null)
        {
            // POINT is in front of this node's plane, so check it against the front list.
            pointIsInFront = front.IsInFront(point);
        }
        else if (!pointIsInFront && back != null)
        {
            // POINT is behind this plane, so check it against the back list.
            pointIsInFront = back.IsInFront(point);
        }
        /// either POINT is in front and there are no front children,
        /// or POINT is in back and there are no back children. 
        /// Either way, recursion terminates here.
        return pointIsInFront;            
    }

    /// <summary>
    /// determines if the line segment defined by v1 and v2 intersects any geometry in the tree.
    /// </summary>
    /// <param name="v1">vertex that defines the start of the ray</param>
    /// <param name="v2">vertex that defines the end of the ray</param>
    /// <returns>true if the ray collides with the mesh</returns>
    bool SplitsRay(Vector3 v1, Vector3 v2)
    {

        var v1IsInFront = IsInFront(v1);
        var v2IsInFront = IsInFront(v2);
        var result = v1IsInFront!=v2IsInFront;

        if (!result)
        {
            /// both vertices are on the same side of the plane,
            /// so this node doesn't split anything. Check it's children.
            if (v1IsInFront && front != null)
                result =  front.SplitsRay(v1, v2);
            else if (!v1IsInFront && back != null)
                result = back.SplitsRay(v1, v2);
        }
        else
        {
            /// this plane splits the ray, but the intersection point may not be within the face boundaries.
            /// 1. calculate the intersection of the plane and the ray : intersection
            /// 2. create two new line segments: v1->intersection and intersection->v2
            /// 3. Recursively check those two segments against the rest of the tree.
            var intersection = new Vector3();

            /// insert code to magically calculate the intersection here.

            var frontSegmentSplits = false;
            var backSegmentSplits = false;


            if (front!=null)
            {
                if (v1IsInFront) frontSegmentSplits=front.SplitsRay(v1,intersection);
                else if (v2IsInFront) frontSegmentSplits=front.SplitsRay(v2,intersection);
            }
            if (back!=null)
            {
                if (!v1IsInFront) backSegmentSplits=back.SplitsRay(v1,intersection);
                else if (!v2IsInFront) backSegmentSplits=back.SplitsRay(v2,intersection);
            }

            result = frontSegmentSplits || backSegmentSplits;
        }

        return result;
    }
} 

1. Pick a "partition" plane (face) from your mesh that roughly divides the rest of the mesh in two. This is a lot easier to do with complex geometry as fully convex items (spheres and the like) tend to wind up looking like lists instead of trees.

2. Create a new BspNode instance from the vertices that define the partition plane.

3. Sort the remaining faces into two lists - one that is in front of the partition plane, and one containing those faces that are behind.
4. Recurse to step 2 until no more nodes are in the list.

When checking for collisions, you have two options.

1. Single-point: check the coordinates that the character or object is moving to against the tree by calling your root node's .IsInFront(moveDestination) If the method returns false, the target point is "inside" the mesh, and you've collided. If the method returns true, the target point is "outside" the mesh, and no collision has occurred.

2. Ray intersection. This one gets a little tricky. Call the root node's .SplitsRay() method with the object's current position and it's target position. If the methods returns true, moving between the two positions will transition through the mesh. This is a superior (though more complex) check because it will catch edge cases, such as when the desired movement would take an object completely through an object in one step.

I just threw that sample code together quickly; it's incomplete and probably won't even compile, but it should get you going in the right direction.

Another nice thing about the BSP: Using the .SplitsRay() method, you can determine if one point on a map is visible from another point. Some games use this to determine if NPCs/AIs can see each other or real players. You could use a slight modification of that to determine if they can hear each other walking, etc.

This may seem a lot more complicated than your original approach, but it's ultimately far more powerful and flexible. It's worth your time to investigate.