I have a large set of PolyData shapes and I want to randomly sample from a list of them and place them in a bounded region in space, and don’t want them to overlap. They are generally the same size and all have zero origin.
Does anyone have an example of having dome something like this? I use the python bindings generally.
I think the easy part would be to create a mesh label for each object to number the objects and use append filter to create one cloud, or just do that individually.
I think it would also be easy to randomly sample a coordinate location in a box and translate each object.
I am not sure though how you would choose a random orientation and them make sure no objects intersect.
maybe particle packing has something interesting to say, which would also be an interesting to pack the objects as close together in some random fashion without intersection.
If you have just a couple of hundred shapes then the simplest is probably to create one model node for each shape.
If you don’t need optimal filling of available space then you can determine common bounding sphere size, use a simple sphere packing scheme to designate sphere center positions, and randomize the orientation. You can position and orient models using a transform. If you need more sophisticated packing methods then I’m sure you can find many in scientific papers and maybe there are open-source implementations (e.g., used for 3D printing from powder).
- That’s an optimization problem;
- It’s NP complete, since orientation can vary.
Given that, you’re better off with some stochastic approach such as Annealing or Genetic Algorithm, which don’t guarantee the best solution, but good enough solutions. Also, you can resort to some heuristic, which also don’t assure the best fit but fair enough arrangements.
https://delta1epsilon.github.io/2016/3D-bin-packing-problem-in-R/ (if orientation is fixed (NP-hard))
https://stackoverflow.com/questions/51482610/3d-bpp-algorithm-in-python (if orientation can vary)
@lassoan what if it’s over 1000 shapes?
@Paulo_Carvalho I think I came up with a simple solution because I don’t really care if they are packed tightly.
create a bounding sphere from the bounding box diagonal. I am sure there is an mini-ball implementation out there,and could do it iteratively/recusively, (Maybe a decent feature to add to vtk If I randomly get a bunch of extra time.)
I could then randomly rotate the sphere shape and apply it to the object contained by it and place the sphere in a box. and because I selected the object randomly, even if the placement in the box is semi-structured it would semi-representative I think.
A more complicated idea would be to simulate each shape with gravity and pour them into the box.
Kurt, what you seek is in the realm of computational geometry and physics, for which there are specialized libraries like CGAL and physics engines like React. I think you’re more likely to find answers in game dev communities ou there.