Friedemann Schmidt wrote:
> 
> Hi,
> 
> I think it's a big big problem with more spheres than 2. I wanted to
> fill a transparent cylinder with lot of spheres randomly in POV-Ray -
> but I gave up... ;-)
> 
> I think, one have to simulate each sphere falling from the sky on top
> of the other spheres, which have to do a lot with physics. So it
> probably can't be done with the script language of POV-Ray.
> 
> Bye,
> Friedemann
> 
> Friedemann Schmidt
> Fri### [at] Stonescom
> Raytracing-Gallery: http://www.rz.fhtw-berlin.de/~s0049669/

If you have two spheres, and add a third touching the other two, you

with balls, simply by translating and rotating. 
If you want to stack the balls, add a fourth to the first tree, just
touching. Again, this ball is merely translated and rotated. It
shouldn't be that hard to figure out. Obviously some bright minds (like
K. Tyler) have already figured it out, even with spheres of different
sizes.

Regards,

Remco de Korte
http://www.xs4all.nl/~remcodek/

Post a reply to this message

Friedemann Schmidt wrote:

> Hi,
>
> I think it's a big big problem with more spheres than 2. I wanted to
> fill a transparent cylinder with lot of spheres randomly in POV-Ray -
> but I gave up... ;-)
>
> I think, one have to simulate each sphere falling from the sky on top
> of the other spheres, which have to do a lot with physics. So it
> probably can't be done with the script language of POV-Ray.
>
> Bye,
> Friedemann
>
> Friedemann Schmidt
> Fri### [at] Stonescom
> Raytracing-Gallery: http://www.rz.fhtw-berlin.de/~s0049669/

  I once asked if anybody had developed a routine for object collision
avoidance which I believe is what you will need to fill a cylinder or
any other shape without them overlapping. Dan Connely replied that
he had seen one recently but I can't remember where the posted reply
is located at. Dan if your out there could you fill in the blanks.

K.Tyler

Post a reply to this message

Hi,

>  I once asked if anybody had developed a routine for object collision
>avoidance which I believe is what you will need to fill a cylinder or
>any other shape without them overlapping. Dan Connely replied that
>he had seen one recently but I can't remember where the posted reply
>is located at. Dan if your out there could you fill in the blanks.

I just wrote a little macro which fills a cylinder with spheres
randomly without overlapping. The problems are, that it takes a long
time to render for many spheres in a small cylinder and that the
spheres doesn't contact each other. So it can only be used to fill a
shape in space without gravitation ;-)

The parameter variables are:
  SeedNr: value for initializing the random stream
  CylRadius: Radius of the cylinder
  CylHeight: Height of the cylinder
  Count: The number of spheres to create
  MinSize: Minimum size of a sphere
  MaxSize: Maximum size of a sphere
  MaxLoops: After this number of loops the macro will be interrupted
if no new position for a sphere can be found.

The cylinder is based on the X-Z-floor.

Example:  FillCylinder(1, 1, 2, 500, 0.1, 0.1, 100) 
(It took 50 seconds on my computer by parsing...)

A macro for filling a sphere or a box could be written easily by the
same way.

By the way, the macro can also be used by

union {
  FillCylinder(1, 1, 2, 500, 0.1, 0.1, 100)
  rotate...
  translate ...
}

#macro FillCylinder(SeedNr, CylRadius, CylHeight, Count, MinSize,
MaxSize, MaxLoops)
  #local Seed = seed(SeedNr);
  #local Pos = array[Count]
  #local Size = array[Count]

  #local i = 0;
  #local Loops = 0;
  #while (i < Count & Loops < MaxLoops)
    #local Size[i] = rand(Seed)*(MaxSize-MinSize)+MinSize;
    
    #local Break = false;
    #while (Break = false)
      #local X = rand(Seed)*(CylRadius-Size[i])*2-(CylRadius-Size[i]);
      #local Z = rand(Seed)*(CylRadius-Size[i])*2-(CylRadius-Size[i]);
      #if (vlength(<X, 0, Z>) <= CylRadius-Size[i])
        #local Break = true;
      #end
    #end
    #local Y = rand(Seed)*(CylHeight-2*Size[i])+Size[i];
    #local Pos[i] = <X, Y, Z>;
    
    #local ShowIt = true;
    #local j = 0;
    #while (j < i & ShowIt = true)
      #if (vlength(Pos[j]-Pos[i])-Size[j]-Size[i] < 0)
        #local ShowIt = false;
      #end
      #local j = j + 1;
    #end
      
    #if (ShowIt = true)    
      #debug concat("Sphere ", str(i+1, 0, 0), "\n")
      sphere {
        Pos[i], Size[i]
        pigment { color rgb <1, 0, 0> }
      }
      #local i = i + 1;
      #local Loops = 0;
    #else
      #local Loops = Loops + 1;
    #end
  #end
  #if (Loops > 0)
    #debug concat(">>> Break after ", str(Loops, 0, 0), " loops!\n")
  #end
#end

Bye,
Friedemann




Friedemann Schmidt
Fri### [at] Stonescom
Raytracing-Gallery: http://www.rz.fhtw-berlin.de/~s0049669/

Post a reply to this message

Hi,

the problem is, that this won't fill a shape randomly. It looks very
regular, doesn't it?

Bye,
Friedemann


Friedemann Schmidt
Fri### [at] Stonescom
Raytracing-Gallery: http://www.rz.fhtw-berlin.de/~s0049669/

Post a reply to this message

Friedemann Schmidt wrote:
> 
> Hi,
> 
> the problem is, that this won't fill a shape randomly. It looks very
> regular, doesn't it?
> 
> Bye,
> Friedemann
> 
> Friedemann Schmidt
> Fri### [at] Stonescom
> Raytracing-Gallery: http://www.rz.fhtw-berlin.de/~s0049669/

Yep, like if you filled a tube with identical sized marbles they would
fall neatly in a pattern if it weren't for the tube. I never tried
stacking marbles on an open surface, I think it would be very hard, and
then I guess you could also forget about the randomness. I might be
mistaken but I think that randomness in a stack of marbles (of the same
size) is not very realistic.

Regards,

Remco de Korte
'the iceman cometh' as K. Tyler once said ;-) at
http:www.xs4all.nl/~remcodek/

Post a reply to this message

K. Tyler wrot
>   I once asked if anybody had developed a routine for object collision
> avoidance which I believe is what you will need to fill a cylinder or
> any other shape without them overlapping. Dan Connely replied that
> he had seen one recently but I can't remember where the posted reply
> is located at. Dan if your out there could you fill in the blanks.


Nathan O'Brien's "Nature" entry in the IRTC:

http://www.irtc.org/ftp/pub/stills/1998-06-30/13nature.zip

BTW, this problem is non-trivial, as it will likely not be
the case that an integral number of unit cells in the
hexagonal-close-packed latticed formed by the balls will
fully fill the container.  Thus the ball positions will not
be fully constrained, and some balls may end up wedged
into nonequilibrium positions... Modeling the formation of
these stacking faults would make an interesting project.

Consider, for example, placing the balls in a spherical "bowl".
The first marble "plane" won't be planar at all, but will conform
to the bottom of the bowl.  This will make the formation of
a well-behaved lattice impossible.

Dan

-- 
http://www.flash.net/~djconnel/

Post a reply to this message

You're talking about SUDS right?  What you do is this:

Create an array which holds position values and radii for the spheres (one
entry for each sphere).  Then as you create each new sphere test it against
all previously created spheres to make sure it doesn't touch.  If it doesn't
touch add it, if it does, discard it and try another one.

In Psuedo-Code:

for noofspheres = 0 to 1000

NextRandomSphere:

x1 = rand * 100
y1 = rand * 100
z1 = rand * 100
rad1 = rand * 3

passed = 0

    for csphere = 0 to upperbound of sphereset

        x2 = sphereset(csphere).x
        y2 = sphereset(csphere).y
        z2 = sphereset(csphere).z
        rad2 = sphereset(csphere).r

        d = sqrt((x2-x1)^2+(y2-y1)^2+(z2-z1)^2)

        if d > rad1+rad2 then
            passed = passed + 1
        endif

    next csphere

if passed = 0 then
    redimension sphereset (upperbound of sphereset + 1) preserve
    sphereset(upperbound of sphereset).x = x1
    sphereset(upperbound of sphereset).y = y1
    sphereset(upperbound of sphereset).z = z1
    sphereset(upperbound of sphereset).r = rad1
else
    go back to NextRandomSphere
endif

next noofspheres

This will create an array of 1000 positions and radii of spheres that are
not neccessarily tangential (or though I'm sure you could do that easily
enough, i.e. modify the creation of the xyz and radius to be tangential to a
randomly selected sphere from the array) but don't touch.

Should work, haven't tested it though.  I did this once with candles of
different heights and radii to create a 'floor' full of lit candles.  Looked
really cool, took AGES to render.  Have fun.

--
Lance Birch
http://come.to/the.zone
Remove the smiley to e-mail.

Post a reply to this message

>Create an array which holds position values and radii for the spheres (one
>entry for each sphere).  Then as you create each new sphere test it against
>all previously created spheres to make sure it doesn't touch.  If it doesn't
>touch add it, if it does, discard it and try another one.

My above posted macro should do exatly this job to fill a cylinder.

BTW, what does your code do if there's no place for a new sphere? It
hangs up, doesn't it? ;-)

Bye,
Friedemann



Friedemann Schmidt
Fri### [at] Stonescom
Raytracing-Gallery: http://www.rz.fhtw-berlin.de/~s0049669/

Post a reply to this message

No, it loops back and trys a new position and a new size.  As you can see,
it *eventually* will create 1000 spheres.  I think with a grouping area of
that size (100x100x100) and a max radius of 3 it should be able to create
1000 sphere (actually, not should, will).

--
Lance Birch
http://come.to/the.zone
Remove the smiley to e-mail.

Post a reply to this message

Chris Maryan wrote:
> 
> I've noticed a number of cool looking images rendered in POVRay that
> involve balls/marbles/whatever stacket to look like a random pile (most
> notably the image that's on the POVRay 3.02 splash screen). Each of
> these images looks like the objects do not intersect but just touch. How
> is this usually done? Should I do the math (seems complicated) or is the
> only way to just guess and test-render?   [... snip]

One place to look for something like this might be Benoit B.
Mandelbrot's
(yes - _the_ Mandelbrot) book "The Fractal Geometry of Nature", chapter
18,
where, among other things, he discusses "Apollonian packing". This is a
situation where you fill a space with the largest circle that can fit in
some space (say, a triangle) and continue filling the remaining smaller
spaces with the largest circles possible, which are, of course, smaller
and smaller with each iteration. Ideally, with an infinite number of
circles,
the space is completely filled (in the fractal sense) with circles

It doesn't have anything in the way of an actual algorithm, but it might
provide a few keywords to search for in other sources. 

That book is published by W. H. Freeman and Company, New York, NY, USA.
The ISBN is 0-7176-1186-9

It's a fascinating read, even if it doesn't directly help you out with
the 
spherical packing problem.

-jr-
 
**********************************************
* Delete "spamBgone." to get my real address *
**********************************************

Post a reply to this message