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

Attachments:
Download 'cereal.pov.txt' (3 KB)

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

Hi Kent,

"theJackal" <nomail@nomail> wrote in message
news:web.426fd1a3ff53c806186fb9fe0@news.povray.org...
> "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.
> > .. snip ..
> > The tricky bit is detecting and avoiding collisions.
>> .. snip ..
> > This gets exponentially more expensive on machine resource as you
increase
> > the number of objects.
> > .. snip ..
>
> 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.
>

Maybe I overstressed the innefficiency of the scene file I posted. Although
it does get a bit heavy on machine resource when the number of pieces you
want to position gets high, it does render in under 20 Seconds on my 600MHz
machine with the 70 pieces of cereal defined. Increasing that to 100 only
increases that to 40 seconds and 140 pieces gives a quite full looking bowl
of cereal and only takes about 1min 30 seconds. Basically, doubling the
number of flakes takes quadruple the amount of time (plus a bit to allow for
an ever increasing number of collisions).

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

I think there are a few flaws in the algorithm you propose.

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

I think this is the big flaw with your cunning plan :-)
This seems to be a 3D array with three dimensions of 10000, making a 1
Trillion elements.
I think you're right when you say below that it 'might' be heavy on memory.

>
> 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];

I'm not sure how you would 'preselect' the points? If each flake is randomly
oriented then these points would not be the same for each iteration.

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

I don't think that writing a C or C++ program was what the original
questioner was after.

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

Wouldn't that stop them getting anywhere near each other and for a bowl of
cereal you really want them all piling up in a slightly soggy heap.

>
>
> theJackal
>
> kentfredric(nospam) at (nospam)gmail dot com
>
> eg: A(nospam) at (nospam) B dot C = A@B.C
>
>

Best Wishes,
Chris B.

Post a reply to this message