How to find the "interior boundary" / "interior convex hull" for a list of 3D points?

Solution 1:

I would do it like this:

1. tetrahedronize your pointcloud

   so create a mesh consisting of tetrahedrons where no tetrahedron intersect any other or contain any point in it. I do it like this:

   1. structures

   you need list of points,triangles and tetrahedrons. Each triangle need one counter which will tell you if it is used once or twice.

   2. create first tetrahedron

   by 4 nested loops through all points and check if formed tetrahedron does not contain any point inside. If not stop as you found your first tetrahedron. This is O(n^5) but as there are a lot of valid tetrahedrons it will never reach such high runtime... Now just add this tetrahedron to triangle and tetrahedron lists.

   3. find next tetrahedron

   now loop through all triangles that has been used once. for each form tetrahedron by using those 3 points used by it and find 4th point the same way as in #2. Valid tetrahedron must not contain any points in it and also must not intersect any existing tetrahedron in the list.

   To ensure whole volume will be filled without holes you need to prioritize the process by preferring tetrahedrons with more triangles already in list. So first search 4 triangles if no found than 3 etc ...

   For each found valid tetrahedron add it to the lists and look again until no valid tetrahedron can be formed ... The whole process is around O(n^2) so be careful with too many points in pointcloud. Also having normals for triangles stored can speed the tests a lot ...

2. outer boundary

   outer boundary consist of triangles in list which have been used just once

3. interior boundary

   interior gap tetrahedrons should be larger than all the others. So check their size against average size and if bigger they are most likely a gap. So group them together to lists. Each gap have only large tetrahedrons and all of them must share at least one face (triangle). Now just count the triangle usage for each group alone and all the triangles used just once will form your gap/hole/interior boundary/mesh.

If your point density is uniform you can adapt this:

• Finding holes in 2d point sets?

And create a voxel map of point density... voxels with no density are either gap or outer space. This can be used for faster and better selection of interior tetrahedrons.

Solution 2:

If I understand well your question, you want the largest volume inside another volume, without points in common between the two volumes.

The outer volume is built from a subset of the set of points. The obvious solution is to build the inner volume with the rest of points.

A volume from a set of points can be made in several ways. If the volume is not convex, then you need some more info (e.g. minimum angle between faces) because you get starred polytopo or cuasi-convex, or some other shape.

For convex volume I recomend the 3D Delaunay construction, with tetrahedra. The boundary is defined by the faces of "tets" that are not shared with other "tets".

Remove from the full set of points those belonging to the boundary: Each tet in boundary has a fourth point that does not lie on the boundary.

The inner volume is another Delaunay construction. Perhaps you only need the fourth points from the previous boundary-tets.