• entries
59
86
• views
40764

# Placement test function

1340 views

[color=#333333][font=Gudea]

[/font][/color]

# [font=arial]PLACEMENT TEST FUNCTION[/font]

## [font=arial][color=#333333]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.[/color][/font]

[code=js:1]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); }}

## [font=arial][color=#333333]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.[/color][color=#444444]Triangle center points[/color][color=#333333]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):[/color][color=#444444]Splitting plane animation[/color][color=#333333]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:[/color][/font]

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

## [font=arial][color=#333333]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.This is why I extend it upwards so that query box looks like this:[/color][color=#333333]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.[/color][/font]

[code=js:1]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; 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;

# [font=arial]THE END RESULT

## Vili Vol?ini

[/font]

I like it and I think I follow your logic.  Immediately a few questions come to mind.  You say that every 23rd triangle centre is referenced.

Does that mean the geometries are created in a uniform fashion that guarantee a good sampling of the geometry by only testing every 23rd face, Or does this mean there could be certain geometries which would generate is such a fashion that it could by chance, break the function because every 23rd triangle exists on one edge?

Upon geometry creation do you analyse the geometry and identify certain faces to be used as your test subjects for the function?

Also, what is a scenario that you could imagine where the function would not work properly?

Regardless, I like it a lot.

I like it and I think I follow your logic.  Immediately a few questions come to mind.  You say that every 23rd triangle centre is referenced.

Does that mean the geometries are created in a uniform fashion that guarantee a good sampling of the geometry by only testing every 23rd face, Or does this mean there could be certain geometries which would generate is such a fashion that it could by chance, break the function because every 23rd triangle exists on one edge?

Upon geometry creation do you analyse the geometry and identify certain faces to be used as your test subjects for the function?

Also, what is a scenario that you could imagine where the function would not work properly?

Regardless, I like it a lot.

I chose 23rd triangle because the number is big enough (no need to test every triangle for approximation) and also because it's a prime number. I also like prime numbers.

Geometries are probably not created in 100% uniform fashion, I think those caves were sculpted and then re-topologied. More optimal surface and quite uniform, but still not enough. I have some problems, because every 23rd triangle I picked were not really uniformly distributed. Yes, of course there are certain geometries that could break this.. for example cylinder with 23 sides.  To add even more confusion, triangle index also matters (and order of triangle indexes). You just can't make assumptions about them.

I don't really analyse geometry and identify certain faces because I think it's too computational expensive. But I know one good way: area triangles - with areas you can sort of guarantee uniform distribution of points, but again new problems if you are not careful. Calculating triangle area must be done with numerically correct formulas or else obtuse (and other weird triangles) will return you very wrong numbers.

Also thanks, cool that you like it.

Not sure I really understood. First the problem: Why can't I sink objects into the ground or collide with each other? You should be able to rotate/scale/sink rocks and overlap them all day in your world. What about tree leaves, are tree tops restricted from touching? As you said, precision isn't 100% necessary, but your original problem is you don't want overlap. So I guess you have accepted some overlap in your algorithm?

The solution: I've never used Unity but I guess you had to use an external function to get references to other objects. I feel like there must be a way. How else can you do normal bullet collision / damage without some kind of callback that has a reference to an entity?

Conclusion: Doesn't seem very useful. You wrote a simple point/triangle collision test and skipped a massive amount of your data set. Any piece of code which your skip iteration is 27 is obviously going to be fast.

Not sure I really understood. First the problem: Why can't I sink objects into the ground or collide with each other? You should be able to rotate/scale/sink rocks and overlap them all day in your world. What about tree leaves, are tree tops restricted from touching? As you said, precision isn't 100% necessary, but your original problem is you don't want overlap. So I guess you have accepted some overlap in your algorithm?

The solution: I've never used Unity but I guess you had to use an external function to get references to other objects. I feel like there must be a way. How else can you do normal bullet collision / damage without some kind of callback that has a reference to an entity?

Conclusion: Doesn't seem very useful. You wrote a simple point/triangle collision test and skipped a massive amount of your data set. Any piece of code which your skip iteration is 27 is obviously going to be fast.

First, you can't just test mesh collision against each other. The function bool Physics.DoesCollides(MeshCollider m1, MeshCollider m2) does simply not exist in Unity3D. Second, if you have a small mesh inside another large mesh which triangles do NOT collide & function Physics.OverlapBox doesn't find it outer mesh with box bound of small mesh (unless you enlarge query box in any dimension), what is there left to do?

Physics.OverlapSphere/Box or Physics.CheckSphere/Box are not really accurate enough.  And yes, I accepted some overlap. I used Physics.OverlapBox to get references to other objects, it's Unity3D physics function. Still, when you get reference to other collider, you need to do additional tests. Normal bullet collision & damage (which is different problem) is done with Physics.Raytrace, again Unity3D function.

Also your conclusion is false. I test triangle center if it is inside any other 3D mesh. For this to work, other meshes that I do tests on need to be topologically closed. Those meshes I do tests on are references collected with Physics.OverlapBox. Topologically closed mesh is a mesh without any holes, so if you fill this mesh with water it won't leak anywhere. It can be either convex or concave, doesn't matter.

## Create an account

Register a new account