(Followups are set to povray.programming, but the problem might be of general
 interest so it's crossposted to povray.general.  That's how crossposting
 is supposed to work, y'all.)

When I do the following in POV 3.02 or 3.1b4, I get the "wrong" result:

difference {
  sphere {0,1}
  intersection {
    sphere {-.3*x,.5}
    sphere {.3*x,.5}
  }
  texture {pigment {rgbf .8}}
}

Instead of getting a sphere with a lens sort of thing removed from the
interior, I get a sphere with interior surfaces corresponding to the two 
smaller spheres, with the lens removed.

I have traced this to the file CSG.C, in the function 
Invert_CSG_Intersection, at line 703 or thereabouts in the 3.02 code.  
The line reads:

  Object->Methods = &CSG_Union_Methods;

This works fine when the object isn't transparent, but it leads to 
unexpected interior surfaces for transparent objects.  To make the problem
go away, one could replace CSG_Union_Methods with CSG_Merge_Methods, but 
since merges are more expensive than unions, it might be preferable to have
a keyword that causes the merge methods to be used instead of the union 
methods when the scene requires it.

The workaround, of course, is to rewrite your scene to do the substitution
for you:

intersection {
  sphere {0,1}
  merge {
    sphere {-.3*x,.5 inverse}
    sphere {.3*x,.5 inverse}
  }
  texture {pigment {rgbf .8}}
}

I will probably do this with the code I'm having the problem with, but it
would tend to make one's head hurt if required on a large scale, and it does
make the code harder to visualize.

Post a reply to this message

Ron Parker wrote:
 [clip]
> This works fine when the object isn't transparent, but it leads to
> unexpected interior surfaces for transparent objects.  To make the problem
> go away, one could replace CSG_Union_Methods with CSG_Merge_Methods, but
> since merges are more expensive than unions, it might be preferable to have
> a keyword that causes the merge methods to be used instead of the union
> methods when the scene requires it.


This bug was brought up in povray.newusers by Alain Culos and Saif Ansari
a few days ago (see the thread "CSG"). At that time I let the POV-team know
about the bug (and its fix).  I did not consider, however, that merge is
slower than union.  If the choice of union/merge for inverting a difference
is allowed, though, I think that the default should be a merge, and
experienced users could use the union when they know that it won't hurt
the scene.

-Nathan Kopp

Post a reply to this message

In povray.general Ron Parker <ron### [at] rongwmicrocom> wrote:
: since merges are more expensive than unions

  Can you present some facts to support his claim?
  I once made a test: the camera was in the negative z direction, looking at
the origin. There was 20 semitransparent spheres in the z axis, from to origin
to the positive z direction. The spheres partially overlapped.
  I don't remember render times, but if the spheres were into a union the
rendering time was more than 2 times the time if the spheres were merged.
  I deduced from this that merge is actually faster than union. And this
makes sense. Why? Well, I don't know how povray merges the objects, but
I can imagine a really simple algorithm for that:
  Suppose that we are calculating the ray that is cast from the middle of
the screen, ie. it hits all the spheres at the center.
  First, suppose that the spheres are into a union. What happens? The ray
hits the outer surface of the first sphere. The color and brightness etc
of this point is calculated. Now another ray is calculated. It hits the
outer surface of the second sphere. Again, the color and brightness is
calculated. A third ray is cast: It hits the inner surface of the first
sphere (the 1st and 2nd spheres overlap partially). Again coloration is
calculated. Then a fourth ray is cast, and it hits the outer surface of
the third sphere, and coloration is calculated. And so on, and so on...
  Now, imagine that the spheres are merged:
  We have now a counter which starts from 0.
  The first ray hits the outer surface of the first sphere. Since the counter
is 0. the coloration of this surface is calculated and we increase the counter.
  A second ray is cast. It hits the outer surface of the second sphere. Since
the counter is greater than 0, we just ignore this surface (ie. no coloration
is calculated). We increase the counter (which is now 2, since we are inside
2 objects).
  A third ray is cast. Now it hits the inner surface of the first sphere, so
we decrease the counter. Since it's not 0 after the decrementation, we ignore
this surface too.
  A fourth ray is cast. It hits the outer surface of the third sphere. Since
the counter is not 0, we ignore this surface and increment the counter.
  And so on and so on.
  At last, we hit the inner surface of the last sphere and decrement the
counter. Now the counter becomes 0, so we calculate the coloration of this
surface.
  What happened? With union, we calculated a total of 40 color values, but
with merge we calculated only 2 (and this is logical: with union we see all
the 40 surfaces but with merge we see only 2, since all the inner surfaces
are removed).
  I suppose that povray uses this kind of algorithm. So can you present some
facts why merge is slower than union?

-- 
                                                              - Warp. -

Post a reply to this message

On Tue, 21 Jul 1998 20:06:58 -0600, Nathan Kopp <nk8### [at] ltuedu> wrote:
>Ron Parker wrote:
> [clip]
>> This works fine when the object isn't transparent, but it leads to
>> unexpected interior surfaces for transparent objects.  To make the problem
>> go away, one could replace CSG_Union_Methods with CSG_Merge_Methods, but
>> since merges are more expensive than unions, it might be preferable to have
>> a keyword that causes the merge methods to be used instead of the union
>> methods when the scene requires it.
>
>
>This bug was brought up in povray.newusers by Alain Culos and Saif Ansari
>a few days ago (see the thread "CSG"). At that time I let the POV-team know
>about the bug (and its fix).  I did not consider, however, that merge is
>slower than union.  If the choice of union/merge for inverting a difference
>is allowed, though, I think that the default should be a merge, and
>experienced users could use the union when they know that it won't hurt
>the scene.

Thanks.  I hadn't read povray.newusers before; maybe I should start.  If you
would, please convey my workaround to those who might be interested in it and
haven't seen it here.

Post a reply to this message

On 22 Jul 1998 06:37:13 -0500, Nieminen Mika <war### [at] assaricctutfi> wrote:
>In povray.general Ron Parker <ron### [at] rongwmicrocom> wrote:
>: since merges are more expensive than unions
>
>  Can you present some facts to support his claim?

[snip good argument]

>  I suppose that povray uses this kind of algorithm. So can you present some
>facts why merge is slower than union?

What you've said seems to make sense.  In my defense, I have only the word of
the 3.1b documentation, page 122, which says:

| Note that merge is slower rendering than union so it should only be used 
| when it is really necessary.

Post a reply to this message

On 22 Jul 1998 06:37:13 -0500, Nieminen Mika <war### [at] assaricctutfi> wrote:
>  We have now a counter which starts from 0.
>  The first ray hits the outer surface of the first sphere. Since the counter
>is 0. the coloration of this surface is calculated and we increase the counter.
>  A second ray is cast. It hits the outer surface of the second sphere. Since
>the counter is greater than 0, we just ignore this surface (ie. no coloration
>is calculated). We increase the counter (which is now 2, since we are inside
>2 objects).
>  A third ray is cast. Now it hits the inner surface of the first sphere, so
>we decrease the counter. Since it's not 0 after the decrementation, we ignore
>this surface too.
>  A fourth ray is cast. It hits the outer surface of the third sphere. Since
>the counter is not 0, we ignore this surface and increment the counter.
>  And so on and so on.
>  At last, we hit the inner surface of the last sphere and decrement the
>counter. Now the counter becomes 0, so we calculate the coloration of this
>surface.

Actually, I just reread this and realized that it's not the algorithm 
POV-Ray uses.  POV-Ray determines all of the intersections with the given
object, then picks the closest one.  In the process of doing so, it checks
each intersection to determine whether it is inside any of the other things
in the CSG.  For a union, however, it just returns the complete list of
intersections.  This means that finding all of the intersections in a union
is order n on the number of unioned objects, while a merge is order n^2.

Your algorithm would run into trouble in practice.  At each real surface, 
potentially two new rays are formed, plus as many shadow rays as you have
light sources.  Each of those rays would need its own copy of the counter.  
In addition, each ray would need to have a counter for every CSG object it
passed through.  That could get ugly very quickly.

It could be modified to work, though.  POV already keeps a stack of which 
objects each ray is inside, for IOR calculations.  It could just pop the top 
intersection off the stack, then check to see whether the container stack 
contains any of the other objects in this CSG.  If it does, then this surface 
should be ignored and we should go on to the next surface, after modifying 
the container stack to reflect the invisible transition.  If it doesn't, 
this is a "real" surface, so we should push it back on the intersection stack 
and return.  This would make merge on transparent objects almost as fast as 
union on opaque ones (union on transparent objects would probably be slower
than merge, because of the coloring step at each surface).

Post a reply to this message