Create Largest Volume Inscribed 3d Box That Will Fit Within Array Of Points

I have a 3D mesh consisting of set of 3D points (Vertexes) and set of faces (connections between points). Q1 How can I find the largest (Volume) inscribed box that will fit insid

Solution 1:

1. you need to have a test if generic point is inside of your mesh or not

   this can be done by hit test of coarse instead of lines you have to deal with your faces so handle them as

   • planes defined by 2 basis vectors and 2 parameters (2D plane subset)

   find the intersection convert to 2D parameters and check if they are in valid range of the face.

2. now find the bounding box of your mesh

   just find min and max values for each axis (from your Vertex points) this leads to max size of your polygon

3. your task is not solvable algebraically for generic meshes so

   You have to use brute force + heuristics ... for example method genere and test so generate all (valid) solutions and take the largest from them. You can find optimal solution only by trying all possibilities but that is impossible due to infinite number of possibilities so you can achieve approximation to solution only. I think use of Voxel map will greatly improve performance of this.

   Heuristics means that you try only some solutions (based on knowledge of the task/dataset or exploiting something) for example if you have symmetric mesh then you can start your boxes as centered and symmetric the same way as mesh (no need to try some craze unaligned boxes ...)

4. create Voxel map

   you have bounding box so make 3D array that will dissect your mesh volume to cubes set each voxel as 0 (outside) or 1 (inside) mesh

5. create function that will determine if generic box is inside mesh

   just run 3 nested fors per each voxel of box and if all the Voxels are set as 1 then box is inside.

6. create box generator and tester

   generate all valid boxes possibilities with some grid step (for example voxel size)- for axis aligned boxes it is 6 nested fors on each first compute volume then compare it to actual found solution:

   • if it is not bigger then skip it and continue with next box
   • if it is bigger then run function from bullet #5
   • if it is inside remember it as new actual solution

7. at the end you should have approximation to your solution

8. you can improve accuracy by increasing voxel count (use smaller voxels) after bullet #7

   for example use 2x more voxels per each axis. Now try just boxes +/- 1 voxel from found solution. You can recursively apply this to achieve wanted precision

[Notes]

If your box is arbitrary oriented then you need to add 3 more dimensions (angles) but that leads to insane complexity. You can try to rotate the mesh so the box will be axis aligned. So first find biggest line inscribed inside and rotate mesh so it is aligned as axis x then find another one in yz plane and rotate mesh by x axis so the line became axis y. This way the solution should be axis aligned (but that is not always the case !!!). The initial Voxel map fill style determine if your found solution hits the surface or not ...