I want to implement terrain collision. I have a class called GeoTerrain. Its constructor takes a picture as parameter and then builds a terrain out of triangles with vertices high for each light pixel and low for each dark pixel. This puts me in a position where I have to implement a proper collision detection for the OBBs when they hit the terrain. But my temporary solution is far from robust.
Here is my current approach: Each surface triangle has its own little hitbox that consists of 6 vertices (the 3 vertices on the triangle surface and three additional vertices that basically are the 3 surface vertices but shifted down the surface normal (so that they are underneath the visible surface).
Why: Because I do not know how to otherwise calculate the minimum translation vector without having a hitbox volume.
Sorry for the long code - I tried to comment as much as necessary:
// This method resides in the Hitbox class.
// The hitbox instance then checks against the other object (parameter):
private IntersectionObject TestIntersectionTerrain(GeoTerrain terra)
{
Vector3 mtv = new Vector3(0, 0, 0);
Vector3 mtvTotal = new Vector3(0, 0, 0);
float shape1Min, shape1Max, shape2Min, shape2Max;
// Select all triangles within reach of the OBB hitbox:
List<GeoTriangle> triangles = terra.GetTrianglesForHitbox(this);
// Loop through all triangles and check collision
// (cannot be more than 8 triangles, right now)
foreach (GeoTriangle triangle in triangles)
{
bool bothOverlap = false;
mtv = Vector3.Zero;
bool error;
bool breakDone = false;
float mtvDistance = float.MaxValue;
float mtvDirection = 1;
// loop through all hitbox normals (three normals):
for (int i = 0; i < mNormals.Length; i++)
{
error = false;
// project the current vertices of objects' hitbox and triangle hitbox to find
// both shapes' minimum and maximum:
SATtest(CurrentHitBoxNormals[i], CurrentHitBoxVertices, out shape1Min, out shape1Max);
SATtest(CurrentHitBoxNormals[i], triangle.VerticesHitbox, out shape2Min, out shape2Max);
if (!Overlaps(shape1Min, shape1Max, shape2Min, shape2Max))
{
bothOverlap = false;
breakDone = true;
break;
}
else
{
// calculate MTV:
CalculateOverlap(
CurrentHitBoxNormals[i], // normals (here, the meshes' hitbox normals)
ref shape1Min,
ref shape1Max,
ref shape2Min,
ref shape2Max,
out error,
ref mtvDistance,
ref mtv,
ref mtvDirection,
mCenterTranslated, // object's hitbox volume center (world space)
triangle.CenterHitbox); // triangle's hitbox volume center (world space)
}
// do the same but now for the triangle's normal
// (right now this unnecessarily also gets looped 3 times):
SATtest(triangle.Normal, CurrentHitBoxVertices, out shape1Min, out shape1Max);
SATtest(triangle.Normal, triangle.VerticesHitbox, out shape2Min, out shape2Max);
if (!Overlaps(shape1Min, shape1Max, shape2Min, shape2Max))
{
bothOverlap = false;
breakDone = true;
}
else
{
CalculateOverlap(triangle.Normal, ref shape1Min, ref shape1Max, ref shape2Min, ref shape2Max,
out error, ref mtvDistance, ref mtv, ref mtvDirection, mCenterTranslated, triangle.CenterHitbox);
bothOverlap = true;
}
}
if (bothOverlap && !breakDone && mtv != Vector3.Zero)
{
// add the current mtv to the total MTV (of all triangles)
// but only add more to it, if the current MTV has a bigger shift in
// one direction than the previous MTVs:
mtvTotal.X = Math.Abs(mtv.X) > Math.Abs(mtvTotal.X) ? mtv.X : mtvTotal.X;
mtvTotal.Y = Math.Abs(mtv.Y) > Math.Abs(mtvTotal.Y) ? mtv.Y : mtvTotal.Y;
mtvTotal.Z = Math.Abs(mtv.Z) > Math.Abs(mtvTotal.Z) ? mtv.Z : mtvTotal.Z;
}
}
if (mtvTotal != Vector3.Zero)
{
IntersectionObject o = new IntersectionObject();
o.IntersectingGameObject = terra.Owner;
o.MinimumTranslationVector = mtvTotal;
o.MeshNumber = 0;
o.MeshName = terra.Owner.Name;
return o;
}
else
{
return null;
}
}
private void CalculateOverlap(Vector3 axis, ref float shape1Min, ref float shape1Max, ref float shape2Min, ref float shape2Max, out bool error, ref float mtvDistance, ref Vector3 mtv, ref float mtvDirection, Vector3 posA, Vector3 posB)
{
float d0 = (shape2Max - shape1Min);
float d1 = (shape1Max - shape2Min);
float intersectionDepthScaled = (shape1Min < shape2Min)? (shape1Max - shape2Min) : (shape1Min - shape2Max);
float axisLengthSquared = Vector3.Dot(axis, axis);
if (axisLengthSquared < 1.0e-8f)
{
error = true;
return;
}
float intersectionDepthSquared = (intersectionDepthScaled * intersectionDepthScaled) / axisLengthSquared;
error = false;
if (intersectionDepthSquared < mtvDistance || mtvDistance < 0)
{
mtvDistance = intersectionDepthSquared;
mtv = axis * (intersectionDepthScaled / axisLengthSquared);
float notSameDirection = Vector3.Dot(posA - posB, mtv);
mtvDirection = notSameDirection < 0 ? -1.0f : 1.0f;
mtv = mtv * mtvDirection;
}
}
The problem is: it works, but not on the edges. With my approach (invisible hitbox below triangle surface) the player sometimes hits an invisible wall because the MTV tells him to move up (ok) and sideways as well (not ok). Mathematically this is correct, because if the player sinks into the fake triangle volume, the mtv may of course decide to shift him back on more than one axis if need be.
Is there any way to get the MTV from just checking against a flat triangle? I found several links that tell me "if" there is an intersection. But I found no understandable solution for getting the MTV. I think I need to find out by how much the player has to be shifted back along the surface normal?
EDIT (2019-02-12 22:00)
I updated the code according to the first answer. But I still get strange behaviour when applying the calculated MTV. This is my current algorithm:
My updated collision detection algorithm approach is so far:
Is that about right?
The SAT (Separation Axis Theorem) algorithm will give you the minimum translation vector quite easily, for any kind of convex shapes, that can also include triangles, quads, flat polygons.
In a brute-force manner, The SAT works in two steps, a couple more to get the MTV.
Find the list of minimum separation axes to tests against.
Project the two convex shapes on the separation axis, to get the projection intervals.
for example, for each shape, dot product all their vertices with the axis direction.
The min and max values will give you the intervals for each shape.
if the two intervals do not intersect, the objects are spearate and do not intersect.
if all intervals intersect on every spearation axis, the objects intersect.
to find the MTV, find the minimum overlap among all the speration axis intervals.
the interval overlap, combined with the separation axis direction, will give you the MTV.
For convex polyhedras, the separation axes to test against are quite simple. They are :
the surface normals for each shape, call them A and B.
the cross product of every edges of A against every edges of B.
There are optimisations, for examples, there is no need to test axes with opposite direction, or similar direction.
as an example, a OBB will need to be tested for three face normals, and three edge directions.
NOTE: that the MTV may not always be the best solution to your problem, especially when we talk about terrains.