0

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 inside the mesh.

[OP]

Hello all and thanks for any help I might receive. I am using vectors to create 3 dimensional objects. What I needs help doing is finding the largest box that will fit within the object. Imagine we have a sphere. How can I find the largest box that will fit within the sphere? On the other hand what if we had a 3 dimensional arrow. How would I go about finding the largest box that would fit within it? I have arrays of all the vectors used to create the objects. I'm looking for a way to use these arrays to find the largest box that will fit within the constructed objects.

Spektre
  • 49,595
  • 11
  • 110
  • 380
Kahless
  • 1,213
  • 2
  • 13
  • 31
  • 1
    The sentence "It's ok if the box does not contain all the vectors but it's important that it does not exceed the vectors" effectively makes the zero size box the right answer. – Eugene Sh. Dec 03 '14 at 02:16
  • I'm having a tough time wording my question. Think of it like this. Imagine there is an array of vectors that creates a sphere. I would like to find the larges box that would fit within the sphere. My issue is the object the box needs to fit in will not always be a sphere. – Kahless Dec 03 '14 at 02:21
  • It's a totally different meaning. You might want edit your question. But it is still not clear. The definition of "within" is unclear for a set of discrete points, unless there are some additional constraints. – Eugene Sh. Dec 03 '14 at 02:26
  • Btw, are talking of 3D space? – Eugene Sh. Dec 03 '14 at 02:34
  • So I guess you should start from understanding what is ”inside" your object and what is "outside". Having a finite set of points is not enough for defining an object. You need also some definition of how they are connected, and what is happening in between. – Eugene Sh. Dec 03 '14 at 02:50
  • ok that makes sense. I also have an array of faces that connect the vectors. I just did not realize that would help me. Also the inside of the object is hallow. – Kahless Dec 03 '14 at 02:55
  • Also the geometry is constructed and I can position a box within it. I'm just looking for a way to automatically position a box within the object and make it as large as possible without leaving the object – Kahless Dec 03 '14 at 02:58
  • And again, by "largest" do you refer to a volume? Think of a sphere, than you can bound a cube in it or, say, a long but thin box. The volumes and the objects will be different, but still fit your definition. – Eugene Sh. Dec 03 '14 at 03:03

1 Answers1

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

    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 ...

Spektre
  • 49,595
  • 11
  • 110
  • 380