On Mon, 14 Aug 2000 22:49:46 +0200, Peter J. Holzer wrote:
>>Tesselating a sphere is pretty easy, and wouldn't require MegaPOV.
>
>Yes. But even for such a simple CSG as in the example I gave (difference
>of two spheres) it isn't that simple any more. There are already three
>cases:
>1) The spheres don't intersect at all (easy - just tesselate the first one)
>2) The second is completely inside the first (also easy - tesselate both
>   but invert the normals of the second).
>3) Their surfaces intersect (a bit more complicated - you have to
>    compute the circle where they intersect, then tesselate two partial
>    spheres).

Or, you tesselate both spheres, ensure no triangles intersect, and perform 
the CSG operation on the resulting meshes.  If you can depend on the 
surfaces to be well-behaved, there are even shortcuts that can be taken to 
avoid testing insideness for every single vertex.

CSG is not the difficult thing to tesselate.  Things like julia objects
and infinite polys and other implicit objects are.

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message

Ron Parker <ron### [at] povrayorg> wrote:
: Or, you tesselate both spheres, ensure no triangles intersect, and perform 
: the CSG operation on the resulting meshes.

  But that would require more memory than necessary.

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

On 21 Aug 2000 06:01:18 -0400, Warp wrote:
>Ron Parker <ron### [at] povrayorg> wrote:
>: Or, you tesselate both spheres, ensure no triangles intersect, and perform 
>: the CSG operation on the resulting meshes.
>
>  But that would require more memory than necessary.

Depends on your definition of "necessary."  As I see it, the other path leads
to certain ruin.  Is it better to use lots of memory and succeed or to use
little memory and fail?

Besides, when did we start worrying about memory consumption?

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message

Ron Parker <ron### [at] povrayorg> wrote:
: Depends on your definition of "necessary."

  Well, suppose that we have two meshes consisting of 1 million triangles
each and we make an intersection of them. In the intersection only 10
triangles are visible.
  We can:
  a) Calculate a mesh which is the resulting intersection. This mesh would
take something like 15-20 triangles.
  b) Leave the meshes be and use just regular CSG intersection.

  In the case a) we need memory for 15-20 triangles. In case b) we need
memory for 2 million triangles (1999990 of them not affecting the scene
in any way (except slowing the render)).

: Besides, when did we start worrying about memory consumption?

  It is an important issue. I think that's the reason why copying a mesh
has been optimized to take as less memory as possible :)

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

On 22 Aug 2000 05:28:40 -0400, Warp wrote:
>Ron Parker <ron### [at] povrayorg> wrote:
>: Depends on your definition of "necessary."
>
>  Well, suppose that we have two meshes consisting of 1 million triangles
>each and we make an intersection of them. In the intersection only 10
>triangles are visible.
>  We can:
>  a) Calculate a mesh which is the resulting intersection. This mesh would
>take something like 15-20 triangles.
>  b) Leave the meshes be and use just regular CSG intersection.
>
>  In the case a) we need memory for 15-20 triangles. In case b) we need
>memory for 2 million triangles (1999990 of them not affecting the scene
>in any way (except slowing the render)).

Perhaps you misunderstood.  I was not talking about using regular CSG 
intersection (that would be of no use in exporting something other software
could use, after all.)  I was talking about computing the intersection of
two arbitrary but well-behaved meshes.  That is a solvable problem, and
there may even be a paper out there from someone who's solved it and/or 
optimized it.  I have solved it myself, though I've never implemented or
published the solution.  (The margins of this post, etc...)  Once you know
how to compute the intersection of two meshes, you have CSG licked.

The memory usage in this case would be that of 2 million triangles, but the
exported data would contain only the 15-20 (or 10, whatever) in the result.

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message