|
![](/i/fill.gif) |
Hi Kent,
"theJackal" <nomail@nomail> wrote in message
news:web.426fd1a3ff53c806186fb9fe0@news.povray.org...
> "Chris B" <c_b### [at] btconnect com> 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
|
![](/i/fill.gif) |