Warp <war### [at] tagpovrayorg> wrote:
> I posted an article in povray.binaries.images about random placement
> of non-intersecting spheres.
> ... and so on..

Actually, your method is quite different from mine.

Again, the spheres are placed in the exact same way, random generation.
The methoid of checking intersections is also based on the naive approach,
but uses a different methodology.  Rather than checking each and every
sphere, only spheres that are within a certain distance are checked.
This is done by partitioning the space into square regions sized such that
only one sphere center may be present without intersection (D/sqrt(2)) and
build an array (what I like to call mailboxes).  Then as each position is
generated, first the mailbox that contains that position is checked, if it
is full, discard and generate a new point. If it is empty, check the
surrounding mailboxes that could contain a sphere that could intersect
(i.e, any mailbox within D of the position).  If any mailboxes are full,
check the distance between the two positions, if they intersect, discard
and move on. If no intersection is found, then the position is good and the
sphere is placed, the position value of this sphere is placed in the
corresponding mailbox and the mailbox is marked full.

Using this method avoids having to check each sphere.  Rather, each sphere
records its presence and position in the mailbox and each subsequent one
only needs to poll the necessary mailboxes for intersectiong spheres.
As more spheres get placed the method slows down as it gets harder to find a
random position that is good.  Eventually, when no positions exist, an
endless loop can be reached, however I haven't included any termination
criteria for this.
Partitions of any size can be used as long as they can only contain one
sphere (ie D/sqrt(2) or smaller) but I found that partition sizes that
equal to D/sqrt(2) work the fastest.  Larger partition sizes can be used,
but requires modification to the code to allow for multiple spheres within
the mailboxes, but I found it slows as the partition size gets bigger as
well.

Hope this is informative, if not boring.

code:
//start
camera{
  up y
  right x*image_width/image_height
  angle 60
  location <-8,30,1>
  look_at  0
}
light_source{<0,200,100> rgb 1 fade_power 2 fade_distance 200}

box{<-10,-1,-10> <10,0,10>
 texture{pigment{rgb 1} finish{ambient 0 diffuse 0.75}}
}



#local minPos=-10; #local maxPos= 10; //bounds
#local Rng=(maxPos-minPos);
#local D=0.23; //sphere radius
#local D2=D/sqrt(2); //partition size
#local nS=5000; //number of spheres
#local mn=ceil(Rng/D2); //number of partions needed
#local MBox=array[mn][mn]; //initialize mailboxes
#local R=seed(0);
#local xztomn=function(POS){ceil((POS-minPos)/D2)-1} //convert position to
mailbox number
#local D3=function(J,POSX)
{sqrt(pow(D,2)-pow(POSX-(J+select(J-xztomn(POSX),1,0))*D2-minPos,2))}
#local OBJ=sphere{0 D/2 texture{pigment{rgb <1,0,0>} finish{ambient 0
diffuse 0.75}}}

#local i=0; #while (i<nS)
  #local OK=false;
  #while (!OK)
    #local Pos1=<rand(R)*Rng+minPos,0,rand(R)*Rng+minPos>; //generate
position
    #ifndef(MBox[xztomn(Pos1.x)][xztomn(Pos1.z)]) #local OK=true; #end
//check mailbox. if defined then it is full, discard and generate new
position.
  #end
  #local j=max(xztomn(Pos1.x-D),0); #while (j<=min(xztomn(Pos1.x+D),mn-1) &
OK)//check surrounding mailboxes (only those within D of the position)
    #local DD3=D3(j,Pos1.x);
    #local k=max(xztomn(Pos1.z-DD3),0); #while
(k<=min(xztomn(Pos1.z+DD3),mn-1) & OK)
      #ifdef(MBox[j][k]) //if mailbox is defined, then it is full and
intersection needs to be checked
        #if (vlength(Pos1-MBox[j][k])<D) #local OK=false; #end //if
intersection found, break loop and discard
      #end
    #local k=k+1;#end
  #local j=j+1;#end
  #if (OK) //all mailboxes checked and no intersetion found
    #local MBox[xztomn(Pos1.x)][xztomn(Pos1.z)]=Pos1;//write position to
corresponding mailbox, this mailbox is now full
    object{OBJ translate Pos1} //place sphere
    #local i=i+1;
  #end
#end

//end

-tgq

Post a reply to this message