Determine point inside/outside enclosed surface

Hi there,
I have a problem here we my application receives a triangulated, closed surface which encloses a volume. The resolution of this surface is high, i.e. there are > 100,000 triangles in it, and it can be concave. Here’s an example:

I now also have an unstructured grid which contains a similar amount of 3D cells. For each of these cells I would like to know if its centre is located inside or outside of the enclosed volume given by the triangulated surface.

Any ideas on how to do this really fast?

Hi @drpeterfranz

It may be simpler and faster to use vtkStaticCellLocator on the volume instead of using the surface.

Can you elaborate? Set vtkStaticCellLocator->SetDataSet() to the poly data containing the surface encompassing the volume? And then what?

Nope, you would need the volume you are refering to in your initial post:

a triangulated, closed surface which encloses a volume.

If you dont have it, then my advice may not be as useful as you would need to reconstruct it, and Delaunay3D do not work with concave surface, so not an option.

Ah, sorry. No, the triangulated surface encloses a real-world volume, i.e. it describes the boundaries of a real world object. What I meant with ‘encloses’ it is that the surface is closed, i.e. it doesn’t have any holes in it. Hope I use the correct language here.

Then you can still use a locator with your surface, assuming all your triangle are correctly oriented.

use vtkStaticCellLocator::IntersectWithLine and check if the sign of t to know if you are inside/outside.

That’s similar to something I have tried before. Will vtkStaticCellLocator test every cell for intersection, or will it use its ‘locator’ functionality first to only consider a tiny subset of the cells? Else it would take too long again.

The locator internally uses a binary tree so finding the cell is O(log(n)).
It is fairly fast and is made for this specific usage.

You can however further optimize if you know that you may hit multiple times the same cells by caching the last N cells or even try to find in the neighbours before using the locator if you know the there is some spatial proximity when you iterate over your volume cell centers.

Perfect, sounds what I have been looking for!

Works a treat, razor fast, less than 1 second execution time :grinning:

Can now use the shapes to assign materials to my model: