I posted an article in povray.binaries.images about random placement
of non-intersecting spheres.
  I got 5000 spheres of diameter 0.2 placed randomly in a planar area
between <-10, 0, -10> and <10, 0, 10> in 15 seconds with my 3.4GHz P4.
When I increased the diameter of the spheres to 0.23 (a much tougher
job because there's less space to place all the 5000 spheres) the time
was 1:50.
  There's no trick in calculating the random location of the spheres,
ie. no speedups using repeating patterns or anything, but every single
sphere is placed with a honest
MinCoords+(MaxCoords-MinCoords)*<rand(Seed), 0, rand(Seed)>

  Basically I use the naive method of putting the center coordinate of
each new sphere in an array and each time I try to create a new sphere,
I first go through the array and check if it would be too close to any
of the other spheres (IOW. if the distance between the centers would
be smaller than the diameter of the spheres).

  Of course a linear search of the array is very slow and results in
an O(n^2) algorithm which gets increasingly slow as the number of
spheres grows. I thought how hard would it be to develop an algorithm
which could make this check faster than in linear time.
  Of course this is already difficult for spheres located in a plane,
not to talk about spheres freely located in space.
  Then I thought that it would require some kind of binary space
partitioning or any similar speeding-up algorithm.
  But then it just hit me: POV-Ray *already* has speeding algorithms
for checking points against objects much faster than in linear time.
Thus the only trick is how to get to use these already-existing
algorithms.

  There's a simple (at least in theory) way for this: Make a union of
spheres of double diameter from all the existing coordinates and then
check if the new center coordinate you calculated for the new sphere
is inside() this union. That's it. POV-Ray uses internally quite advanced
algorithms for speeding up this inside() test and it does it much faster
than in linear time.

  Of course there's a problem here: You just can't create the union of
spheres each time you want to create a new sphere. That would actually
be slower than the naive approach.

  One possible solution would be to build up a nested union of spheres.
In other words, each time you create a new sphere you would create a
union of this sphere and the existing union of spheres.
  However, the problem with this solution is, I believe, that it's really
resource-heavy and consumes lots of memory because each such union would
exist all at the same time in memory. It might also be somewhat slow to
create such a nested union each time you create a new sphere. (To be
honest, however, I didn't even try it to see what happens.)

  So what I ended up doing was a compromise between the naive solution
and the inside()-of-union solution:
  For the first 200 spheres (the number was searched by trial-and-error)
I create them by the naive method. Then I create a union of these 200
spheres and put them in an array.
  For the next 200 spheres I first test them against the union(s) in
that array (using inside()) and only if that test is negative I then
check it with the naive way with the newly-created coordinates. Then
I create another union of these new 200 spheres and put them in that
array.
  And so on for the next 200 spheres etc.

  The code below is not very optimized as I wrote it more or less hastily,
but it still resulted in the times I mentioned at the beginning.


#declare SpheresAmount = 5000;
#declare MinCoords = <-10, 0, -10>;
#declare MaxCoords = <10, 0, 10>;
#declare SphereDiameter = .2;
#declare Seed = seed(0);

#declare ChunkSize = 200;

#declare ChunksAmount = ceil(SpheresAmount/ChunkSize);
#declare Chunks = array[ChunksAmount];
#declare ChunkIndex = 0;

#declare CheckArray = array[ChunkSize];

#while(ChunkIndex < ChunksAmount)
  #declare CAInd = 0;
  #while(CAInd < ChunkSize)
    #declare CoordOk = false;
    #while(!CoordOk)
      #declare Coord =
      MinCoords+(MaxCoords-MinCoords)*<rand(Seed), 0, rand(Seed)>;
      #declare CoordOk = true;
      #declare Ind = 0;
      #while(Ind < ChunkIndex)
        #if(inside(Chunks[Ind], Coord))
          #declare CoordOk = false;
          #declare Ind = ChunkIndex;
        #end
        #declare Ind = Ind+1;
      #end
      #if(CoordOk)
        #declare Ind = CAInd-1;
        #while(Ind >= 0)
          #if(vlength(CheckArray[Ind]-Coord) < SphereDiameter)
            #declare CoordOk = false;
            #declare Ind = -1;
          #end
          #declare Ind = Ind-1;
        #end // #while(Ind >= 0)
      #end // #if
    #end // #while(!CoordOk)
    #declare CheckArray[CAInd] = Coord;
    #declare CAInd = CAInd+1;

    sphere
    { Coord, SphereDiameter/2
      pigment { rgb <rand(Seed), rand(Seed), rand(Seed)> }
      finish { specular .7 }
    }
  #end

  #declare ChunkIndex = ChunkIndex+1;
  #if(ChunkIndex < ChunksAmount)
    #declare Chunks[ChunkIndex-1] =
      union
      { #declare Ind = 0;
        #while(Ind < ChunkSize)
          sphere { CheckArray[Ind], SphereDiameter }
          #declare Ind = Ind+1;
        #end
      };
  #end

  #debug concat("Chunks: ", str(ChunkIndex,0,0), "/", str(ChunksAmount,0,0),
                "\n")
#end

camera { location <-.5, 25, -5>*1.5 look_at 0 angle 35 }
light_source { <100, 200, -50>, 1 }
plane
{ y, -SphereDiameter/2
  pigment { rgb <.8,.9,1> }
}

Post a reply to this message