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