intriangulation(ver​tices,faces,testp,h​eavytest)

Are 3D-testpoints located inside or outside an arbitrary watertight mesh with vertices and faces?
2K Downloads
Updated 26 Jul 2016

View License

How often does this happen: You have a nice mesh in 3d, which is described by an np by 3 array of vertices and an nt by 3 array of indices into this array, which describe the faces. lets further say, the mesh is closed, i.e. it divides the total 3d space into a bounded and an unbounded domain in a way that it is impossible to connect any point inside with any point outside the domain without crossing the triangulation.
Now you have another fine set of points in 3d and you need to know which of these points are inside the triangulated volume and which aren't.
Intriangulation is the solution.

With the command

in = intriangulation(vertices,faces,testpoints)

you get an array of the same length as the testpoints with an entry 1 for testpoints inside the triangulated volume and an entry 0 for those points that aren't. (OK, you get -1 for points where the algorithm failed.)

See

help intriangulation

for an example and details.

In contrast to the FEX-submission inpolyhedron, you do not need to compute and/or preprocess any face normals in intriangulation.

The mesh may not have internal faces!

ACKNOWLEDGMENT:

I have to announce that the core algorithm is 99% identical to the algorithm from Adam Aitkenhead in his submission "Mesh voxelisation". I use it here with his permission. Please go and rate "mesh voxelisation" also if you like intriangulation.

Also thanks to Sven's comments on algorithm and special cases.

Cite As

Johannes Korsawe (2024). intriangulation(vertices,faces,testp,heavytest) (https://www.mathworks.com/matlabcentral/fileexchange/43381-intriangulation-vertices-faces-testp-heavytest), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2010b
Compatible with any release
Platform Compatibility
Windows macOS Linux
Categories
Find more on Computational Geometry in Help Center and MATLAB Answers
Acknowledgements

Inspired by: Mesh voxelisation

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.5.0.0

Added function drehmatrix, which is needed for optional parameter heavytest.
Also added comments for alternative interpretation of heavytest inside code.

1.4.0.0

result=1 for testpoints==vertices

1.3.0.0

Numerous improvements in speed using Matlab Profiler.

1.2.0.0

Algorithm update: No more fails if testpoint is projected on edge of mesh.

1.1.0.0

Following the idea of Sven's hint. Testing successive directions only if former tests left undeterminable results.

1.0.0.0