Out of curiosity: does anyone know the time complexity of merge?  Is it O(n)
or O(n^2)?  Because I was just rendering a scene with 20,000 spheres, and it
takes 13 seconds to parse with no merge (there's a bunch of other stuff
going on), but when I tried putting them all in a merge object, well....  I
cut it off after 17 minutes.  I don't know how long it would take to finish,
but since it is an animation, and that is only one frame, and the animation
will be much more complex soon, this time is simply not acceptable.  If the
time is O(n^2), would it be any faster to merge them in batches, and then
merge the batches?  Or will I just have to deal with not being able to merge
them?
Thanks!

Barron Gillon

Post a reply to this message

It depends on the scene.

Merge takes care that surfaces inside the merged objects don't show up. In
effect, once it is inside an object, it will somehow discern if the next
surface it encounters should be calculated and used or not. For large
amounts of objects this can get pretty complicated, especially if they're
spaced widely apart. A friend of mine, DT, once built a castle, which you
can view on IRTC and his website (www.digitaltwilight.de), and used merge
first. The entire scene took forever to render. I replaced his merges with
unions (cause his objects aren't transparent), and then it rendered like
"PLOP-Finished".

I don't know HOW it actually checks for inside/outside surfaces though. It
seems that when the objects are stacked together nicely, it can sometimes do
better than when they are spread wide apart. Someone else might explain the
details. I just know that you should DEFINITELY use merge only when
necessary, never to an excess.

-- 
Tim Nikias v2.0
Homepage: http://www.digitaltwilight.de/no_lights
Email: tim.nikias (@) gmx.de


> Out of curiosity: does anyone know the time complexity of merge?  Is it
O(n)
> or O(n^2)?  Because I was just rendering a scene with 20,000 spheres, and
it
> takes 13 seconds to parse with no merge (there's a bunch of other stuff
> going on), but when I tried putting them all in a merge object, well....
I
> cut it off after 17 minutes.  I don't know how long it would take to
finish,
> but since it is an animation, and that is only one frame, and the
animation
> will be much more complex soon, this time is simply not acceptable.  If
the
> time is O(n^2), would it be any faster to merge them in batches, and then
> merge the batches?  Or will I just have to deal with not being able to
merge
> them?
> Thanks!
>
> Barron Gillon
>
>


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.521 / Virus Database: 319 - Release Date: 23.09.2003

Post a reply to this message

In article <3f793c99$1@news.povray.org> , "Barron Gillon" 
<gil### [at] purdueedu> wrote:

> Out of curiosity: does anyone know the time complexity of merge?  Is it O(n)
> or O(n^2)?

It seems you have the misconception that the merge algorithm would be slow
somehow, but this is ray-tracing, there is no tesselation and thus a merge
is now slower than any other object.  However, the automatic bounding built
into POV-Ray can compute only one unified bound for the merge, whiule with
many individual objects it can compute optimal bounding for every swingle
objects.  As finding the intersection is faster for well-bound objects, and
POV-ray does not bound the objects inside the merge, tracing takes longer as
more objects beed to be tested.  There is no way around, only adding a
manual bound if you can come up with a more efficient one.

BTW, if you just want to move non-intersecting objects as if they were one
objects, use "union" not "merge"!

    Thorsten


____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

In article <3f79eedf@news.povray.org>,
 "Thorsten Froehlich" <tho### [at] trfde> wrote:

> BTW, if you just want to move non-intersecting objects as if they were one
> objects, use "union" not "merge"!

Also, in most cases, merge is worthless for opaque objects. With 
transparent objects, avoiding refraction computations for interior 
surfaces can speed things up as well as removing undesired surfaces, but 
for other uses it will just slow things down.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message