How to Detect All Mesh Triangles Within a Given Area

Questions & Answers
1

Hello - I’m looking for a way to detect all mesh triangles of a single mesh within a given area.

I’ve actually gotten this working, but ever method I’ve used is simply not performant enough - it totally crushes my framerate.

My current method of detection is to iterate through all mesh vertices and check their proximity to a RaycastHit.point on the mesh’s surface.

When the icospherical mesh is sparse, as you can see in IcoPerformance_1.JPG, performance is good.

However, when the icospherical mesh becomes more dense, as you can see in IcoPerformance_2.JPG and IcoPerformance_3.JPG, performance simply tanks (as there are many more mesh vertices to iterate through).

Some other methods I’ve tried:

  • SphereCast and SphereCastAll only register the first impact with the mesh; not all impacted triangles.
  • I have tried casting a “cone” of RayCasts out to the surface of the mesh from the camera. This sortof works, but because of the nature of casting hundreds of individual rays, sometimes triangles get missed, especially small ones.
  • All of my triangles are linked to an abstract icospherical model in code. This model’s triangular faces all have adjacency data; I have tried doing an adjacency search, and this works correctly, but unfortunately it also tanks performance.

There has got to be some method of simply detecting all mesh triangles within an area that I’m missing. Thank you in advance!

IcoPerformance 1:

159850-icoperformance-1.jpg
159850-icoperformance-1.jpg1228×941 128 KB

IcoPerformance 2:

159851-icoperformance-2.jpg
159851-icoperformance-2.jpg1339×943 187 KB

IcoPerformance 3:

2

For anybody interested, I solved this problem by using a bounded volume search. My AbstractIcosphere, the data class that represents the icosphere before it reaches unity, is a QuadTree data structure. The shallowest level of the quad tree are the twenty icosahedral faces.

When “importing” the abstractIcosphere to unity, I set up the vertices using a “bounded volume” system. All vertices belong to one of the 20 parent icosahedral faces.

When making our vertex search, we first make a search for icosahedral regions that are within radius, and only search those regions for vertices.

This works very well up to a moderate density. For higher density regions, framerate drops to about 30fps. To solve this I will next create a second “bounded volume” tree…it will eventually become a bounded volume hierarchy.

3

Do you have source code to this?
I am trying to get triangles within a given area and find if the mesh is flat or not.