Just thinking outlound here, but would it not be more efficient
programmatically to create a fixed size 3D array, and place a copy of each
object in it.
that way, instead of having to compare with every other piece, you'd simply
need to scan the slice of the 3D array that your object is in for other
pieces pre-inserted in the array, and only see if it clashes with them,
thus reducing the alogrithims complexity from O(n!) to O(n).

Ill put it in psudo code (well, its closer to C++/Java but hey) here cos Im
still not that familiar with povrays internel coding.

flakearray [10000] of flakes

pointarry = array [10000][10000][10000] of ints

boolean addflake(x,y,z){
  for each of the 100 preslectected important points in flake at x,y,z
     flakeValue=pointarray[[point.x*100][point.y*100][point.z*100];
     if flakeValue!=0
        possibleCollision = flakeArray[flakeValue];
        if thisFlake.isInside(possibleCollision) return FAILURE
   if no collisionsFound
       i=endOfFlakeArrayFill + 1;
       flakeArray.addNewFlakeAtIndex(i)
       for each of the 100 preselected points
          pointarray[point.x*100][point.y*100][point.z*100] = i
     return SUCCESS
}

then all thats nessecary is to loop the "addflake" method untill the number
of successes matches the desired number of flakes.

as you see i have 2 arrays... one to keep the number of the occluding flake.

also. i think this algo might be a little heavy on the ram use, so it might
pay to write a C or C++ program instead which spits out povray code.

if thats not good enough to work, heres another strategy I use frequently,
cellular placement:

basically, do it iteratively and just place them all in a grid, but jitter
each one from its centre by a random factor, but only have it jitter so
that in the worst case they still dont occlude.



theJackal

kentfredric(nospam) at (nospam)gmail dot com

eg: A(nospam) at (nospam) B dot C = A@B.C




"Chris B" <c_b### [at] btconnectcom> wrote:
> This post includes a scene file in response to a question on povray.newusers
> about randomly distributing pieces of cereal around in a surface (milk in
> this case). It stacks up bits of cereal, checking that the pieces don't
> intersect.
>
> It uses the rand() function to move a torus away from the origin. It then
> uses it again to rotate it so that the pieces of cereal are distributed
> randomly in a disc.
>
> The tricky bit is detecting and avoiding collisions. This example uses a
> combination of a number of principles gleaned from these news groups in the
> past. It checks each new piece of cereal against all previously defined
> pieces of cereal by doing an intersection and measuring the size of the
> result. Unfortunately this isn't very accurate (at least in POVRay 3.5 that
> I'm using) and therefore the example also steps through the points between
> the minimum extent of the intersection object and the maximum extent of the
> intersection object, looking for points that are inside the intersection
> object. If it finds a collision it moves the new piece of cereal to
> somewhere else and checks that position for collisions until it finds
> somewhere where it doesn't intersect with anything else.
>
> This gets exponentially more expensive on machine resource as you increase
> the number of objects.
>
> Hope this is useful
> Chris B.

Post a reply to this message