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

Yes, it's an interesting little problem, Warp. I have C code (on my Amiga)
to place circles of semi-random radius in a plane. It generates a random
maximum radius for each circle, looks for an empty spot for the circle's
centre (by directly reading the screen buffer) and then determines the
actual radius for the circle to fit the space, which is obviously limited
by the nearest neighbour. The results are quite aesthetically pleasing,
IMNSHO.

>   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.

But how inefficient is it if you incrementally build your union, like this
snippet from one of my Penrose tiles scenes:

#debug "\nIgnore following warning, this union intentionally empty\n"
#declare Null = union{}
#debug "Ignore previous warning, this union intentionally empty\n"

#declare SetT = Null;
#declare SetP = array[2]{Null, Null};

#macro AddTri(A,B,C) #declare SetT = union{object{SetT} Tri(A,B,C)} #end
#macro AddTri0(A,B,C,P)
  #declare SetP[P] = union{object{SetP[P]}Tri0(A,B,C)}
#end

Post a reply to this message