How to Detect All Mesh Triangles Within a Given Area

Question

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: alt text

IcoPerformance 2: alt text

IcoPerformance 3:

Answer 1

Best Answer

Answer by KeeganTawa · May 20, 2020 at 03:42 PM

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.

Add comment · Show 2 · Share

rguerrasa · Nov 30, 2020 at 12:53 AM 0

Share

Very interesting. I did a very similar thing with a plane in 2D. I wonder if there is a way to do this in the GPU instead, using shaders.

Navy_Seals · Oct 14, 2021 at 07:58 AM 0

Share

@KeeganTawa Thanks for the blog as well. I am trying to implement and test this from the blog

Can you share the example class for the class Triangle ? I get errors while implementing your code.

 [Serializable]
 public class Triangle
 {
     public Vector3 adjacency1;
     public Vector3 adjacency2;
     public Vector3 adjacency3;
 }

I get error here below as adjacency1, adjacency2, adjacency3.

  foreach (Triangle t in ring1)
             {
                 // Add adjacencies (duplicates will be skipped).
                 if (t.adjacency1.visible)
                 {
                     // Add adjacency 1 to all adjacencies.
                     allAdjacencies.Add(t.adjacency1);
 
                     // If adjacency 1 is not present in ring 2, save it to be added to the next ring 2.
                     if (!ring2.Contains(t.adjacency1))
                     {
                         // Save adjacency 1 to be added to Ring 2.
                         buffer.Add(t.adjacency1);
                     }
                 }
                 if (t.adjacency2.visible)
                 {
                     // Add adjacency 2 to all adjacencies.
                     allAdjacencies.Add(t.adjacency2);
 
                     // If adjacency 2 is not present in ring 2, save it to be added to the next ring 2.
                     if (!ring2.Contains(t.adjacency2))
                     {
                         // Save adjacency 2 to be added to Ring 2.
                         buffer.Add(t.adjacency2);
                     }
                 }
                 if (t.adjacency3.visible)
                 {
                     // Add adjacency 3 to all adjacencies.
                     allAdjacencies.Add(t.adjacency3);
 
                     // If adjacency 3 is not present in ring 2, save it to be added to the next ring 2.
                     if (!ring2.Contains(t.adjacency3))
                     {
                         // Save adjacency 3 to be added to Ring 2.
                         buffer.Add(t.adjacency3);
                     }
                 }
             }

Many thanks in advance

Answer 2

Answer by Navy_Seals · Sep 29, 2021 at 10:25 AM

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.

Add comment · Show 3 · Share

KeeganTawa · Sep 29, 2021 at 05:23 PM 1

Share

Hey @Navy_Seals , I eventually wound up solving this in a much faster and more efficient way. I call it the "coupled ring search" and you can read about it here on my blog.

The big thing is that all of my triangles are "smart" triangles and have knowledge of their surroundings. Without this backing data structure, you won't be able to pull off the ring search.

Navy_Seals KeeganTawa · Oct 04, 2021 at 05:05 AM 0

Share

Dear @KeeganTawa, That's a fantastic blog! I really loved the simplicity of your explanation there. Please advice me how to make adjustment in the code to form a square or rectangle boundary by keeping the "observationCenter" in the middle. Many thanks and you saved the day!

Navy_Seals KeeganTawa · Oct 04, 2021 at 05:47 AM 0

Share

Also, Please share the code for the method "HighlightObservationGroup();". You have missed this in your blog. This will help a lot for me. I just bookmarked your blog. Wonderful work!

How to Detect All Mesh Triangles Within a Given Area

2 Replies

Your answer

Follow this Question

Related Questions