Post news RSS Floatlands devblog #27 - placement test function

Vili, our lead programmer will present to you a solution he worked on the previous week – placement test function. It checks if a certain object is colliding with the other objects in the world.

Posted by on

This blog post will be a bit more technical, so just a heads up before you start reading. Vili, our lead programmer will present to you a solution he worked on the previous week – placement test function. It checks if a certain object is colliding with the other objects in the world.

PLACEMENT TEST FUNCTION Vili Volčini


I’ve created a function that checks if 3D mesh object is colliding with the world – other 3D meshes and primitives. The hardest part here is to check if your 3D mesh is inside another 3D mesh and their walls/triangles are not colliding, because Unitys Physics.OverlapBox doesn’t return other 3D meshes. The reason is that 3D meshes are not usually topologically closed.

example specimen floatlands This is my test 3D mesh. It has 1700 vertices and 580 triangles.


The function is called ‘CanPlaceMesh’ and returns true or false and looks like this:

public static bool CanPlaceMesh(MeshCollider testCollider, LayerMask mask, Plane ignorePointsPlane)

I did an approximative calculation, because we don’t need 100% accuracy, but 90% or so suffices. The more important thing is that the function is fast. As you can see, my test mesh has 1700 vertices and that’s a lot of triangles. So I just took a small amount of triangle centers. The reason I choose triangle centers is because they are better distributed than just edges.

for(int i = 0;i < tris.Length; i+=8*3) { //Skip every 23 triangle
	Vector3 a = verts[tris[i + 0]];
    Vector3 b = verts[tris[i + 1]];
    Vector3 c = verts[tris[i + 2]];
    Vector3 triCenter = (a + b + c) / 3f; //calculate center
    Vector3 point = testCollider.transform.TransformPoint(triCenter); //transform into world position
    // if points on positive side of the plane
    if(ignorePointsPlane.GetSide(point)) {
        DebugDraw.DrawMarker(point, 0.1f, Color.green, 0f);
        _tempList.Add(point);
    }
    else
    {
        DebugDraw.DrawMarker(point, 0.1f, Color.red, 0f);
    }
}

So out of 1700 points I get to check only around 1700/(8*3) = 70 points. Still quite too much, but remember, if any point is found colliding with the world, the algorithm stops and returns false – meaning it can’t place. So we check averagely 70/2 = 35 points.

triangle points floatlandsTriangle center points


If you look closely, points are located in triangle centers. Let me first show you this .gif and then explain the red and green points (and blue splitting plane):

splitting plane animation floatlands
Splitting plane animation


Explanation is simple: we dip 3D mesh into the ground, so we really need to ignore the bottom points of 3D mesh or else it will collide with ground. This is exactly what this plane is meant for and why it’s called ignorePointsPlane. Now you may wonder what I do with these points? Before I start testing if points collide with the world, I need to do a query for nearby colliders:

var wB = testCollider.bounds; //get testCollider world bounds
Collider[] colliders = Physics.OverlapBox(wB.center, wB.extents + Vector3.up * 10f, Quaternion.identity, mask, QueryTriggerInteraction.Ignore); //query for all nearby colliders.

You may have noticed ‘Vector3.up * 10f’ – this extends query box up so it hits mesh colliders. If our mesh testCollider is inside another mesh collider, normal query box (testCollider.bounds) won’t detect it.

inside mesh floatlands


This is why I extend it upwards so that query box looks like this:

query box floatlands


And you see it hits a big island mesh. Now that I have collected all ‘nearby’ colliders, I can test if points are inside them or not. I made special functions for concave mesh colliders and convex+primitive colliders. Those functions work only on closed meshes so this is why we use only closed 3D colliders.

Collider[] colliders = Physics.OverlapBox(wB.center, wB.extents + Vector3.up * 10f, Quaternion.identity, mask, QueryTriggerInteraction.Ignore);
for (int i = 0; i < colliders.Length; i++) {
    Collider c = colliders[i];

    if (testCollider == c)
        continue;

    if (c is MeshCollider && !(c as MeshCollider).convex)  {
        for (int k = 0; k < _tempList.Count; k++) {
            if (c.IsPointInside(_tempList[k])) {
                DebugDraw.DrawBounds(wB, Color.red, 0f);
                return false;
            }
        }
    }
    else {
        for (int k = 0; k < _tempList.Count; k++)
            if (c.IsPointInsideConvex(_tempList[k])) {
                DebugDraw.DrawBounds(wB, Color.red, 0f);
                return false;
            }
    }
}

DebugDraw.DrawBounds(wB, Color.green, 0f);
return true;

THE END RESULT:

finished lowpoly floatlands

Finished product acts like this


more about Floatlands


Comments
Wylie_Coyote
Wylie_Coyote

This is a really great idea!!
Much Love.

Reply Good karma Bad karma+2 votes
6Pills Author
6Pills

Thanks! Procedural generator is already well optimized, but we had some cases where the positioning of objects was weird, so this solution helped a lot.

Reply Good karma+1 vote
Post a comment
Sign in or join with:

Only registered members can share their thoughts. So come on! Join the community today (totally free - or sign in with your social account on the right) and join in the conversation.