1
\$\begingroup\$

I am trying to make simple RTS game, and here is the problem I encountered. I need to get model height in any position. Model will not be rotated or scaled. For example, I have a terrain model like this:

Example terrain model

and I want to get terrain height in unit`s position to place it correctly.

enter image description here

Thanks in advance!

\$\endgroup\$
2
  • \$\begingroup\$ Just get the vertex closest to the queried point, and use its Y value. Considering that the vertices usually are in object space, you might have to transform it to world space. \$\endgroup\$
    – EvilTak
    Oct 11 '15 at 9:49
  • \$\begingroup\$ Could you tell us what you have tried and why it did not work? \$\endgroup\$
    – Vaillancourt
    Oct 11 '15 at 13:18
1
\$\begingroup\$

You would have to extract all triangles from your terrain model and do a collision check on them. Preferably line against the triangle plane. XNA has methods for this but let's start by extracting the mesh data.

A XNA model contains Meshes which contains MeshParts which contains the Vertex buffer and Index buffer. You have to construct the triangles from these if you want to check collisions on them. You should not do this per frame of course but at initialization and store a Triangle list for later usage.

Start by creating a simple class that holds your triangles and a list for storing them.

class CollisionTriangle{
     public Vector3 [] v;
     public CollisionTriangle()
     {
         v = new Vector3[3];
     }
}

List<CollisionTriangle> triangles = new List<CollisionTriangle>();

You then iterate through your model and and fill up the list.

foreach(ModelMesh mesh in MyModel.Meshes){

    Matrix transform = CreateTransform(mesh.ParentBone); 
    foreach (ModelMeshPart meshPart in mesh.MeshParts)
    {
           ExtractMeshPart(meshPart, transform);            
    } 
}

Meshes has it's on Transformation space, there isn't ONE model space all vertices are located in. You create the current mesh space by going through the bone structure and build a matrix. This is used later when transforming the vertex positions to world space.

Matrix CreateTransform(ModelBone bone)
{
    if (bone == null)
        return Matrix.Identity;

    return bone.Transform * CreateTransform(bone.Parent);
}

This is where the vertex data is extracted and stored in your list:

public void ExtractMeshPart(ModelMeshPart meshPart, Matrix transform)
{

            VertexDeclaration declaration = meshPart.VertexBuffer.VertexDeclaration;
            VertexElement[] vertexElements = declaration.GetVertexElements();
            VertexElement vertexPosition = new VertexElement();

            foreach (VertexElement element in vertexElements)
            {
                 if (vert.VertexElementUsage == VertexElementUsage.Position && vert.VertexElementFormat == VertexElementFormat.Vector3)
                       vertexPosition = vert; 
            }

The VertexDeclaration tells us how the Vertex buffer is structured. We are only interested in retrieving the position part but this could be used for normals, UV, etc. as well.

Vector3 [] allVertex = new Vector3[meshPart.NumVertices];
meshPart.VertexBuffer.GetData<Vector3>(
                meshPart.VertexOffset * declaration.VertexStride + vertexPosition.Offset,
                allVertex,
                0,
                meshPart.NumVertices,
                declaration.VertexStride);

This is pretty straight forward, we allocate a array to store all vertex positions, send the offset and vertex stride to GetData() and it fills our array. Yay! But we still don't have any triangles so we need to get the indices as well.

short [] indices = new short[meshPart.PrimitiveCount * 3];
meshPart.IndexBuffer.GetData<short>(meshPart.StartIndex * 2, indices,  0,  meshPart.PrimitiveCount * 3);

Here is almost the same thing, indices are stored as short in XNA models so we create an array with the correct size. Please note that I assume the mesh is triangulated!

Before filling up your triangles and storing them away we need to transform the vertices from model space to world space. We use the transform we created earlier.

for (int i = 0; i != allVertex.Length; ++i)
{
    Vector3.Transform(ref allVertex[i], ref transform, out allVertex[i]);
}

And now we are ready to create triangles and fill up our list.

for (int i = 0; i < indices.length; i+= 3)
{
     CollisionTriangle triangle = new CollisionTriangle();
     triangle.v[0] = allVertex[indices[i]];
     triangle.v[1] = allVertex[indices[i + 1]];
     triangle.v[2] = allVertex[indices[i + 2]];

     triangles.add(triangle);

}

Now we have a triangle list to check collisions on each frame! (or rather after X frames for optimizations) For each unit that's moving, go trough all triangles check if it's position is within the three vertices. If so create a plane from the triangle and do a ray vs plane collision check, the unit should be placed at the intersection point.

foreach(RTSUnit unit in Unitlist)
{
    foreach(CollisionTriangle tri in triangles)
    {
       if(InsideTriangle(unit.Position, tri))
       {
            Vector3 rayStartPos = unit.Position + Vector.Unity * 100;
            Ray ray = new Ray(rayStartPos , -Vector3.UnitY);
            Plane plane = new Plane(tri.v[0], tri.v[1], tri.v[2]);

            float? intersectDist = ray.Intersection(plane);

            if(intersectDist != null)
                unit.Position = ray.Position + ray.Direction * intersectDist;

       }
    }
}

We start the ray from a bit up in the air to make sure we hit the ground even if moving up a slope. If there's an intersection intersectDist will tell us how far away from the rayStartPos the point is. That's where the ground is!

The way we check if the point is inside or not is by measuring the angles to the vertices from the point. If the combined angles are roughly 360 degrees then it's inside, otherwise it's not.

bool InsideTriangle(Vector pos, CollisionTriangle tri)
{
            Vector3 vec1 = Vector3.Subtract(tri.v[0], pos);
            Vector3 vec2 = Vector3.Subtract(tri.v[1], pos);

            vec1.Normalize();
            vec2.Normalize();

            double dotV = Vector2.Dot(vec1, vec2);
            double angle = (float)Math.Acos(dotV);

            vec1 = Vector3.Subtract(tri.v[1], pos);
            vec2 = Vector3.Subtract(tri.v[2], pos);

            vec1.Normalize();
            vec2.Normalize();

            double dotV = Vector2.Dot(vec1, vec2);
            double angle = (float)Math.Acos(dotV);

            vec1 = Vector3.Subtract(tri.v[2], pos);
            vec2 = Vector3.Subtract(tri.v[0], pos);

            vec1.Normalize();
            vec2.Normalize();

            double dotV = Vector3.Dot(vec1, vec2);
            double angle = (float)Math.Acos(dotV);

            float tolerance = 0.001f;

            if(angle > (Math.PI * 2) - tolerance)
                return true;

            return false;
}

We need to add a tolerance to the check because of float precision, angle is never going to be exactly 360.

That should be it! But please note that depending on terrain mesh detail, size and number of units this could be really slow. So if you are going with this solution I recommend having a collision mesh. Meaning a simpler mesh than what's being rendered. It should be as low poly as possible. Also you might want to split up the terrain mesh in smaller pieces so each unit doesn't have to check a huge triangle list each time.

Disclaimer, I wrote this here, the code has never been compiled so I suspect a few typos but you should be able to figure it out I think.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.