How to Detect All Mesh Triangles Within an Area

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, where the triangles within the desired radius are highlighted and performance is acceptable:


IcoPerformance_2, where the desired triangles are highlighted, but performance begins to stutter:


IcoPerformance_3, where performance hits the floor:

 

You appear to be attempting a very game-engine-y operation using a high-level scripting API. That's unlikely to be successful in a brute-force way.

Instead it might be necessary to pre-process the data into something that can be more rapidly traversed, perhaps spatially dividing it into regions, or else simply thinking about your entire problem in a different way.

 

Considering that I'm right on the doorstep of having it working, (simply having some performance issues) I'm first looking for some ideas that might not involve throwing out my entire data structure! haha

 

A couple ideas that I've had which are sortof shortcuts around the problem without really addressing it -

1. Only probe for a new observational area after migrating over some threshold of radians since the last probe, accepting a stutter in performance every now and then.
2. Only probe for a new observational area after zooming past some threshold of altitude above the surface since the last probe.

 

Well I suppose by that measure I am almost a billionaire, except I'm having some financial issues.

Engineering is where it all hits the road. If it turns out the road is made of swiss cheese (or bad analogies), then the engineering doesn't work.

It sounds like you're thinking of some interesting ways to do less work on this... that's engineering!

 

What's the end goal of all this?

 

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.

This is the world model for a scaling, dynamic planetary interface. Think of an ultralight "google earth."

This wound up being sortof the solution..the data was already organized into a quadtree, I just had to use it (but you couldn't have know that).