I have a union of many small, mostly disjoint objects, and now I need to do
a difference with them.  From past experience, when I do an intersection
with such a conglomeration, it turns it into a single large object that is
only bounded at the largest extent, and slows down the render a lot.  I may
not have the above correct, but it certainly slows the render down a lot.

Since the section I have to cut out is small, and doesn't intersect most of
the objects, I'm wondering if there might be a better way.  I'm thinking
doing a check to see if each individual object intersects the cutout, and if
so, do a difference with it.  Otherwise, don't.  Take the union of all that. 
Most of the objects would not be affected.

The only problem is how to determine if the cutout and the union object
intersect.  Does anyone have any ideas how to do this?  Can we access the
bounding boxes POV generates?  That would probably be ideal, since it's
trivial to check if two boxes intersect, but is there another, faster way to
do this (I'm somewhat concerned about trading the parse time for render
time, though in this case, parse time will be cheap comparatively)

Also, has anyone considered automating such an algorithm?  It seems to me
that POV could, when seeing code like:

difference
{
  union
  {
    smallobject1
    smallobject2
    smallobject3
    smallobject4
    .
    .
    .
    smallobjectn
  }
  anotherobject
}

it could turn it into:

union
{
  difference { smallobject1 anotherobject }
  smallobject2
  smallobject3
  smallobject4
}

assuming that only smo1 intersected ano's bounding box.  I would think this
would speed things up.  Could work for intersections too.  Of course, some
heuristics would need to be generated to determine when to do the level
swapping, and I have no idea how to do that.

Geoff

Post a reply to this message

Geoff Wedig wrote:
> 
> I have a union of many small, mostly disjoint objects, and now I need to do
> a difference with them.  From past experience, when I do an intersection
> with such a conglomeration, it turns it into a single large object that is
> only bounded at the largest extent, and slows down the render a lot.  I may
> not have the above correct, but it certainly slows the render down a lot.
> 
> Since the section I have to cut out is small, and doesn't intersect most of
> the objects, I'm wondering if there might be a better way.  I'm thinking
> doing a check to see if each individual object intersects the cutout, and if
> so, do a difference with it.  Otherwise, don't.  Take the union of all that.
> Most of the objects would not be affected.

You could turn off auto-bounding and manually bound your objects.

> 
> The only problem is how to determine if the cutout and the union object
> intersect.  Does anyone have any ideas how to do this?  Can we access the
> bounding boxes POV generates?

In MegaPOV, you can use the max_extent() and min_extent() functions to
do just that.

>  That would probably be ideal, since it's
> trivial to check if two boxes intersect, but is there another, faster way to
> do this (I'm somewhat concerned about trading the parse time for render
> time, though in this case, parse time will be cheap comparatively)
> 
> Also, has anyone considered automating such an algorithm?  It seems to me
> that POV could, when seeing code like:
> 
> difference
> {
>   union
>   {
>     smallobject1
>     smallobject2
>     smallobject3
>     smallobject4
>     .
>     .
>     .
>     smallobjectn
>   }
>   anotherobject
> }
> 
> it could turn it into:
> 
> union
> {
>   difference { smallobject1 anotherobject }
>   smallobject2
>   smallobject3
>   smallobject4
> }
> 
> assuming that only smo1 intersected ano's bounding box.  I would think this
> would speed things up.  Could work for intersections too.  Of course, some
> heuristics would need to be generated to determine when to do the level
> swapping, and I have no idea how to do that.

It would indeed appear to be feasible, but a b*tch to program as YOU
know that you want to cut out ano from smo1, but POV has no way of
knowing that this is what YOU want.  Unless your objects are randomly
placed at runtime (or move around in an animation), I think it's
probably better if you optimise your CSG-tree by hand.

-- 
Francois Labreque | And a four year old carelessly banging on a toy
    flabreque     | piano is not only 'music', it's probably the last
        @         | moment of 'artistic purity' they'll ever enjoy
   videotron.ca   | before outside influences start corrupting their
                  | expression.    - Chris R.

Post a reply to this message

Francois Labreque <fla### [at] videotronca> wrote:
>> 
>> difference
>> {
>>   union
>>   {
>>     smallobject1
>>     smallobject2
>>     smallobject3
>>     smallobject4
>>     .
>>     .
>>     .
>>     smallobjectn
>>   }
>>   anotherobject
>> }
>> 
>> it could turn it into:
>> 
>> union
>> {
>>   difference { smallobject1 anotherobject }
>>   smallobject2
>>   smallobject3
>>   smallobject4
>> }
>> 
>> assuming that only smo1 intersected ano's bounding box.  I would think this
>> would speed things up.  Could work for intersections too.  Of course, some
>> heuristics would need to be generated to determine when to do the level
>> swapping, and I have no idea how to do that.

> It would indeed appear to be feasible, but a b*tch to program as YOU
> know that you want to cut out ano from smo1, but POV has no way of
> knowing that this is what YOU want.  Unless your objects are randomly
> placed at runtime (or move around in an animation), I think it's
> probably better if you optimise your CSG-tree by hand.

Well, you want to cut ano from all of the so's, but some of them don't need
any cutting.  

And yeah, my objects are pseudo random, so it's not so simple to optimize by
hand, but I think I can write the algorithm to do it.

Geoff

Post a reply to this message

Geoff Wedig wrote in message <3aae32a8@news.povray.org>...
> And yeah, my objects are pseudo random, so it's not so simple to optimize by
> hand, but I think I can write the algorithm to do it.


perhaps your objects are small enough with comparision with cutting object and
size of pixels - than you can remove instead differencing and it increase speed
of rendering a lot (no differences and less objects)

ABX

Post a reply to this message

Wlodzimierz ABX Skiba <abx### [at] abxartpl> wrote:

> Geoff Wedig wrote in message <3aae32a8@news.povray.org>...
>> And yeah, my objects are pseudo random, so it's not so simple to optimize by
>> hand, but I think I can write the algorithm to do it.


> perhaps your objects are small enough with comparision with cutting object and
> size of pixels - than you can remove instead differencing and it increase speed
> of rendering a lot (no differences and less objects)

Basically, that was part of the hope too.  My solution at this point has
been to modify the code so the bits contained within the difference area are
removed entirely.  I get a ragged edge that I have to hide, but that I can
deal with by, well, hiding it. ;)

Geoff

Post a reply to this message

>I have a union of many small, mostly disjoint objects, and now I need to do
>a difference with them.  From past experience, when I do an intersection
>with such a conglomeration, it turns it into a single large object that is
>only bounded at the largest extent, and slows down the render a lot.  I may
>not have the above correct, but it certainly slows the render down a lot.

Several things come to mind:

1) union the differences of every small object and the cutting object
2) do a hierarchical octree optimisation using manual bounding
3) see what the +SU and +MB options can do for you (they are on by
default but who knows?)


Peter Popov ICQ : 15002700
Personal e-mail : pet### [at] vipbg
TAG      e-mail : pet### [at] tagpovrayorg

Post a reply to this message