Hello, I have an intresting problem:

Consider this: Take a box with a specified height, with and depth. I
would like to place a number of spheres with a specific radius in this
box.

The problem is how to place the spheres in the box to get the maximum
numbers of spheres that can fit in the box. I think that this is not a
trivial problem, but is there a complete analytic solution at all (using
with, height, depth and radius as parameters)?

I had the idea of creating a macro with "height, with, depth, radius" as
input and get the locations of the spheres as output...

Any ideas?

Post a reply to this message

In article <37C181CF.D0580FDC@hpts.com>, Paul Johnsson <pau### [at] hptscom> wrote:

>Hello, I have an intresting problem:
>
>Consider this: Take a box with a specified height, with and depth. I
>would like to place a number of spheres with a specific radius in this
>box.

I'm not sure, but I think I saw this discussed in "Fractal Programming in
C++". You might do a search on the net for "Sphere Packing" and see if
that's the same thing you're talking about.

Jerry

Post a reply to this message

I believe that Suds does this same thing, less the macro part.
http://www.lcars.eu.org/r.jennings/winbat/povsud.zip
I'm not sure about this particular zip and location, the program is
for POV v2; and it was linked to via a Imagine users webpage for
converting from POV into that format. There may or may not be better
suited includes, macros, etc. of which I am unaware.

Bob

Paul Johnsson <pau### [at] hptscom> wrote in message
news:37C181CF.D0580FDC@hpts.com...
> Hello, I have an intresting problem:
>
> Consider this: Take a box with a specified height, with and depth. I
> would like to place a number of spheres with a specific radius in
this
> box.
>
> The problem is how to place the spheres in the box to get the
maximum
> numbers of spheres that can fit in the box. I think that this is not
a
> trivial problem, but is there a complete analytic solution at all
(using
> with, height, depth and radius as parameters)?
>
> I had the idea of creating a macro with "height, with, depth,
radius" as
> input and get the locations of the spheres as output...
>
> Any ideas?
>

Post a reply to this message

Paul Johnsson wrote:
> 
> Hello, I have an intresting problem:
> 
> Consider this: Take a box with a specified height, with and depth. I
> would like to place a number of spheres with a specific radius in this
> box.
> 
> The problem is how to place the spheres in the box to get the maximum
> numbers of spheres that can fit in the box. I think that this is not a
> trivial problem, but is there a complete analytic solution at all (using
> with, height, depth and radius as parameters)?
> 
> I had the idea of creating a macro with "height, with, depth, radius" as
> input and get the locations of the spheres as output...
> 
> Any ideas?

There are some volume filling macros at twysts site:
http://macroscope.twysted.net/

-- 
Ken Tyler

See my 850+ Povray and 3D Rendering and Raytracing Links at:
http://home.pacbell.net/tylereng/index.html

Post a reply to this message

Paul Johnsson wrote in message <37C181CF.D0580FDC@hpts.com>...
>Hello, I have an intresting problem:
>
>Consider this: Take a box with a specified height, with and depth. I
>would like to place a number of spheres with a specific radius in this
>box.
>
>The problem is how to place the spheres in the box to get the maximum
>numbers of spheres that can fit in the box. I think that this is not a
>trivial problem, but is there a complete analytic solution at all (using
>with, height, depth and radius as parameters)?
>
>I had the idea of creating a macro with "height, with, depth, radius" as
>input and get the locations of the spheres as output...


This is also known as the "sphere-stacking" problem in mathmatics.  For a
box, there is a single optimum solution, known (I think) as the "cubic
close-packed" positioning.  A macro implementing this method would be
relatively easy to write.

Mark

Post a reply to this message

> >The problem is how to place the spheres in the box to get the maximum
> >numbers of spheres that can fit in the box. I think that this is not a
> >trivial problem, but is there a complete analytic solution at all (using
> >with, height, depth and radius as parameters)?
> >

A crystaline matrix that has the body-centered cubic lattice construction is the
most efficient way to pack spheres.  Mother nature has proven this in many
materials that we run into all the time.  There are arguments for the FCC ( face
centered cubic lattice ) but those arguments are typically based on materials
that are under stress and demonstrate any of a number of dislocations in order
to achieve plastic deformation.  If you have a cubic box with three axi a,b,c of
equal length and angles alpha, beta, and gamma ( between each pair of axi ) that
are also equal then the lattice structure of Si or NaCl (salt) would be best. 
If you get into a triclinic system where all axi and angles are different then
the problem gets ugly very fast and even mother nature has a fit.  The best
material that would get close would be Al2SiO5 but again, like salt, we are
dealing with spheres of different sizes.  Kepler suggested this problem about
400 years ago and suggested a solution that was correct, without the benefit of
x-ray crystalography or modern numerical methods.  His solution was based on the
simple observation that a man selling grape-fruit in the market will stack in a
close packed haxagonal plane and then add another layer on top of that one
slightly shifted to allow the next layer to sit in the crevass between three
other touching grape-fruit on the lower layer.  Why?  Because it works.  The
grape-fruit don't tumble over the edge and this seems to be a good arrangement. 
There is plenty of lost volume in this packing but such is life.  If the sphere
radius is much smaller than the box dimensions then we have a solution.  

Dennis Clarke

Post a reply to this message

Dennis Clarke wrote in message <37C407D0.549A7778@interlog.com>...
>Kepler suggested this problem about
>400 years ago and suggested a solution that was correct, without the
benefit of
>x-ray crystalography or modern numerical methods.  His solution was based
on the
>simple observation that a man selling grape-fruit in the market will stack
in a
>close packed haxagonal plane and then add another layer on top of that one
>slightly shifted to allow the next layer to sit in the crevass between
three
>other touching grape-fruit on the lower layer.  Why?  Because it works.
The
>grape-fruit don't tumble over the edge and this seems to be a good
arrangement.
>There is plenty of lost volume in this packing but such is life.  If the
sphere
>radius is much smaller than the box dimensions then we have a solution.


This has been recently proven to be the correct solution.

Mark

Post a reply to this message

Let's suppose that you are given three buckets fulls of little marbles.  The
first bucket contains red marbles with a radius of 1 unit.  The second bucket
contains blue marbles with a radius of pi/4 and the last bucket contains green
marbles with a radius of pi/6.  If you are given and empty box that is cubic and
has a volume of 10^6 cubic units then how may we pack the marbles in the
interior of this smooth and perfect box in a most efficient manner?  What is the
least effecient manner that is stable?  Can this be solved in an deterministic
manner or are numerical methods required?

Now there you have a problem that would be useful for a program like Pov-Ray. 
Why?  Because the visualization of crystalline lattice patterns is a useful tool
for most physics labs and having multiple spheres of different dimensions is far
more likely in real materials.  A more interesting application still would be
the modeling of a DNA or RNA fragment based on a given gene sequence.  Thus if I
give the program GATTACA then perhaps we can visualize the fragment structure? 
There is a little chemical joke in that movie title by the way.

Any way, there are a number of Java applets that already do this with Java3D but
I think that the cpu overhead is really massive.  You need a pile of Sun servers
to render in any kind of reasonable time frame.

Have a crack at the marble problem... what are your thoughts?

Dennis Clarke

ps: I don't have the solution offhand, but I'm sure that it can be solved ....

Post a reply to this message

Dennis Clarke wrote:

> Any way, there are a number of Java applets that already do this with Java3D but
> I think that the cpu overhead is really massive.  You need a pile of Sun servers
> to render in any kind of reasonable time frame.
>

Applets doing Java3D???
Where?

Also, if the cpu overhead is for rendering, Java3D should have taken care of that
by using the hardware acceleration of the computer it's running on. So what does
take the cycles?

--
"My new computer's got the clocks, it rocks
But it was obsolete before I opened the box" - W.A.Y.

Post a reply to this message

Dennis Clarke wrote:

> > >The problem is how to place the spheres in the box to get the maximum
> > >numbers of spheres that can fit in the box. I think that this is not a
> > >trivial problem, but is there a complete analytic solution at all (using
> > >with, height, depth and radius as parameters)?
> > >
>
> A crystaline matrix that has the body-centered cubic lattice construction is the
> most efficient way to pack spheres.  Mother nature has proven this in many
> materials that we run into all the time.  There are arguments for the FCC ( face
> centered cubic lattice ) but those arguments are typically based on materials
> that are under stress and demonstrate any of a number of dislocations in order
> to achieve plastic deformation.  If you have a cubic box with three axi a,b,c of
> equal length and angles alpha, beta, and gamma ( between each pair of axi ) that
> are also equal then the lattice structure of Si or NaCl (salt) would be best.
> If you get into a triclinic system where all axi and angles are different then
> the problem gets ugly very fast and even mother nature has a fit.  The best
> material that would get close would be Al2SiO5 but again, like salt, we are
> dealing with spheres of different sizes.  Kepler suggested this problem about
> 400 years ago and suggested a solution that was correct, without the benefit of
> x-ray crystalography or modern numerical methods.  His solution was based on the
> simple observation that a man selling grape-fruit in the market will stack in a
> close packed haxagonal plane and then add another layer on top of that one
> slightly shifted to allow the next layer to sit in the crevass between three
> other touching grape-fruit on the lower layer.  Why?  Because it works.  The
> grape-fruit don't tumble over the edge and this seems to be a good arrangement.
> There is plenty of lost volume in this packing but such is life.  If the sphere
> radius is much smaller than the box dimensions then we have a solution.
>
> Dennis Clarke

I'm no math expert (high school sophomore) but I think this is right. Also, the most
efficient packing would depend on the ratio of the box size to the sphere size. For
example, if you have a 2x2x2 box and spheres of diameter one, obviously you could
pack at most eight spheres using a cube-type pattern. However, if the apheres are
much smaller, I believe the best arrangement is the hexagonal planes. The best way
to pack them is the way you would build a tetrahedron out of spheres, hexagonal
planes with each sphere resting on the three below it. There is a third way,
hexagonal planes where each sphere rests on two below it, so as to create hexagonal
tilings along the x-z plane and the x-y plane. I think this also depends on the
box-sphere ratio, but I'm pretty sure the tetrahedral stacking is best for
infinitessimal spheres.

Post a reply to this message