Hello,
In my work with DEM (Discrete Element Modeling) I am often approximating a shape, for example a rock, with N spheres. The normal work flow is to load in a STL file that contains the shape that I would like to approximate. I then pack the interior of the stl outline with the N spheres. I try to match the general shape but there really is no rhyme or reason in placing a sphere in a certain location with some radius.
I would like to write/use an algorithm that can find the "best" way to pack a given stl file. I have been looking into the sphere packing problem from mathematics and physics but they do no allow overlapping.
I have been working on a program in matlab that would do this for me. Its process is as follows.
1) Import a STL file and find its bounding box.
2) Create a bounding grid with dimensions (7,7,7) (for example...)
3) Out of these points, find only the ones that are inside the Polygon
4) Pick a random point from step 3 and minimize a function F solving for the radius of the sphere (more on F in a bit)
5) Repeat steps 3 and step 4, 50 times (for example...)
6) Pick the best minimum value from the step 5s 50 values that minimized F
7) Using the x,y,z values that yielded the minimum value from step 6, reduce the grid such that the grid is now centered around the x,y,z values that minimized F the most.
8) Repeat steps 3 through 7 until a convergence on x,y,z,r is found.
The function F was a little tricky to formulate and I don't know if it yields exactly what I want, but the general Idea is as follows.
I would like to compare the volumes of the sphere with relationship to the volume of the polygon as follows.
F = (V_s not V_p) - (V_s and V_p) + (V_p not V_s) or
F = Vol of s that is not in the polygon minus the Vol of s that is in the polygon plus the volume of the poly that is not in the spheres
My question is a combination of if anyone has ran into a similar problem and in what ways could I improve my algorithm.
Thank you for any and all suggestions!
Please let me know in what ways I can improve my question.
it seems clear that (V_s and V_p) + (V_p not V_s) = V_p
one way to set up your problem would be to max (V_s and V_p) and min (V_s not V_p)
have you examined simple 2D examples just to get the flavor of the problem?
are you planning to use uniform spheres (circles?)
are they allowed to overlap (it seems so)
sorry I don't have an immediate answer but in my case experimenting with similar packing problems I like to experiment with physical analogs
The following paper may help you.
Cheng-Qing Li，Wen-Jie Xu，Qing-Shan Meng.Multi-sphere approximation of real particles for DEM simulation based on a modified greedy heuristic algorithm. Powder Technology,Volume 286, December 2015, Pages 478–487
Hello,
Thanks for the response.
I have done some work with 2d problems using matlab's fmincon and the pattern search functions. With promising results, but once I went into 3d I started to get abnormal shapes.
My Idea behind this program is to input an STL file, the number of spheres to use, and the minimum radius any one sphere can be. The program would then give me a set of {x,y,z,r} for each sphere that would tell be where in the 3d plane to put the sphere and what its radius should be.
Overlap is fine as long as one sphere is not inside another sphere.
Well I have not implemented (3d) but did little on planar (circle packing)
For equations :
http://mathworld.wolfram.com/SpherePacking.html
http://mathworld.wolfram.com/KissingNumber.html
@Wen-jie-Xu
Thank you for the paper. I started to read it but I have not finished and I may have questions for you later.
@Aparna Murthy
Thanks for your reply. To my understanding, the SpherePacking and Kissing Number do not apply for my problem because I want the spheres to overlap.
Matt Schramm Has you finished the work? I'm very sorry for the delay reply you.
Best regards.
- Badges
- Science topic