Hmmm... replying to my own message.  Just looking and I saw how in
various ways, merge and intersections require that more than just
the closest intersection be returned (probably difference, too).  Hmmm...
I'd rather not always get rid of this optimization, but it looks like
that might be necessary.

-Nathan

Post a reply to this message

>should be counted or not.  Nathan Kopp has added this sort of thing to his
>UV-mapping patch, available at http://nathan.kopp.com . It's a bit more
complex
>than just a "closed" keyword, though, IIRC.

Very nice :)

>A side note, and hopefully Nathan will see this too and make sure he's
dealing
>with it correctly: CSG requires more than just an insideness test.  It also
>requires that the All_Intersections method really return all intersections,
>because if the closest one fails it wants to find the next-closest.
Internally
>bounded meshes DO NOT do this by default, because of the optimization I
noted
>above.
OK. I didn't know this.
Now I say: "let's forget we have an internal structure: I consider my
triangle mesh just as a set of triangles, regardless their orientation". So:
- All_intersections is the union of all the triangle intersections, but
- when a point is shared by an even number of triangles, it is not an
intersection.

This leads to a pair of special cases:
- an edge intersection
- a vertex intersection
- an edge-vertex intersection

For the first case a could write a
Theorem: in a mesh representing a closed surface, each edge is shared by an
even number of triangles.
Proof: on a closed surface, you can walk forever, there aren't boundaries.
So, each time you meet an edge, you can be sure there is a triangle (and
only one) that leads you "on the other side". []
So, when a ray hits an edge, it hits n/2 times the surface.
I don't know what does "hitting an edge" really mean for the ray-tracer (I
still didn't have the time to read them carefully). I think it means
"getting closer than 10E-6 to a triangle". I think each time I get "close to
an edge", there could be a warning flag in a special version of the
ray-triangle intersection routine. How many triangles warned me? An even
number of them, I hope! so if (n/2) mod 2 gives 1, there is really an
intersection. Otherwise it's a point where the surface walks on itself, and
must not be taken into account.

Now, the vertex intersections. They are a mess: they could be the center of
a triangles star, but even the center (perfectly overlapping) of two stars
(not coplanar each other)... It's hard to say if it's a single or double or
triple surface point...
But how many points like that you will meet in a triangle mesh? I think a
few. And how many rays will hit it in a scene? I don't think more than one
(unless you don't write a disease-study mesh in an appropriate scene. And if
you move a bit your camera...). There could be an error, furthermore blurred
by antialias... So I think you could assert that
                   each "star point" is a single point.
It's untrue, I know, but I think it could work.

Edge-vertex intersections can be see as a vertex intersection (splitting the
triangle that gives the edge into twor triangles, in the intersection
point). So they fall in the previous case.

I Know it's less general than an usual surface intersection test, but I
think it would do his job.
And it could be easily extended do polygons mesh (somebody will write a
polygon mesh, one day...) and, with some work more, even to bicubic_patch
meshes (they don't have only one intersection for each ray)
:Daniele

Post a reply to this message

On Thu, 04 Mar 1999 23:29:46 -0500, Nathan Kopp <Nat### [at] Koppcom> wrote:
>I like this.

For more details, look for a posting I made to cgrr sometime in the past couple
of months that talks about this in excruciating detail.

>> A side note, and hopefully Nathan will see this too and make sure he's dealing
>> with it correctly: CSG requires more than just an insideness test.  It also
>> requires that the All_Intersections method really return all intersections,
>> because if the closest one fails it wants to find the next-closest.  Internally
>> bounded meshes DO NOT do this by default, because of the optimization I noted
>> above.
>
>What part of CSG requires that All_Intersections push everything onto the depth
>stack (it's been a while)?  (I knew that mesh optimized that, since I had to
>skip that part in order to count every intersection.)

That would be this part, in csg.c:

static int All_CSG_Intersect_Intersections (OBJECT *Object, RAY *Ray, 
	ISTACK *Depth_Stack)
{

[...]

      if (All_Intersections (Current_Sib, Ray, Local_Stack))
      {
        while ((Sibling_Intersection = pop_entry(Local_Stack)) != NULL)

I wouldn't have known about it myself if I hadn't seen it pointed out in the
isosurface documentation.  Normally, I wouldn't read the docs, but I was in
the process of formatting them for the Superpatch docs at the time...

>What about using the already existing surface
>normals (stored in the mesh structure)?  Of course, that would require any
>user-specified normals to always point 'out'.  Just a thought.

Of course.  I think reorientation should take place after normal calculation,
however the normal calculation takes place.  If two adjacent triangles have
opposing normals, flip one.  Do this until the whole mesh is consistent (there
are obviously more efficient ways to do this.  I explained one in the cgrr post
I mentioned above.)  The result is that all normals are either pointing inward
or outward, except that you have to treat unconnected (but closed) meshes
specially to ensure consistency between components.  The final step is to ensure
that a point that is known to be outside tests as outside; if not, flip the 
inverse flag.

Post a reply to this message

On Thu, 04 Mar 1999 23:39:08 -0500, Nathan Kopp <Nat### [at] Koppcom> wrote:
>Hmmm... replying to my own message.  Just looking and I saw how in
>various ways, merge and intersections require that more than just
>the closest intersection be returned (probably difference, too).  Hmmm...
>I'd rather not always get rid of this optimization, but it looks like
>that might be necessary.

Make it another flag.  That's what isosurfaces do.  Document it thusly:
"If it looks wrong, try setting the 'all_intersections' flag."

Post a reply to this message

The point I was trying to make is this: All edges are shared between exactly 
two triangles.  The problem is, we don't know whether an edge intersection 
should be counted as one intersection, two, or none.  Consider the following 
ugly 2-d art:

                  /
_ _ _ _ _ _ _ _ _/_ _ _ 
    /\           \               
   /A \         B \

The dotted horizontal line is your ray.  At A, it hits an edge that should 
not be counted.  At B, it hits an edge that should be counted.  Each is
shared between exactly two faces.

The workaround in a situation like this is to cast another ray, parallel
to the first one but offset by a sufficiently small amount, through the
triangles in question.  Count the intersections of that ray and use that
number to represent the intersections at the edge.  The same thing works 
for intersections at vertices, except that you have to make sure that you
don't hit any edges with the parallel ray.

Post a reply to this message

On 5 Mar 1999 08:39:48 -0500, Ron Parker <par### [at] my-dejanewscom> wrote:
>On Thu, 04 Mar 1999 23:29:46 -0500, Nathan Kopp <Nat### [at] Koppcom> wrote:
>>I like this.
>
>For more details, look for a posting I made to cgrr sometime in the past couple
>of months that talks about this in excruciating detail.

Urg.  Dejanews doesn't have that post.  I must have hallucinated it.  If
you really want the gory details, ask. :)

Post a reply to this message

>                  /
>_ _ _ _ _ _ _ _ _/_ _ _
>    /\           \
>   /A \         B \
>
>The dotted horizontal line is your ray.  At A, it hits an edge that should
>not be counted.  At B, it hits an edge that should be counted.  Each is
>shared between exactly two faces.


What happens if we count even A as one intersection? Could there be errors?
Would they be very noticeable?
:Daniele

Post a reply to this message

On Fri, 5 Mar 1999 17:43:33 +0100, Daniele Varrazzo 
	<pir### [at] officineitnospam> wrote:
>>                  /
>>_ _ _ _ _ _ _ _ _/_ _ _
>>    /\           \
>>   /A \         B \
>>
>>The dotted horizontal line is your ray.  At A, it hits an edge that should
>>not be counted.  At B, it hits an edge that should be counted.  Each is
>>shared between exactly two faces.
>
>
>What happens if we count even A as one intersection? Could there be errors?
>Would they be very noticeable?

Yes, there will be errors.  A is either zero intersections or two intersections.
If you count it as one intersection, it will invert the insideness for every
point to the left of A.  In practice, this shows up as a row of random-looking
pixels in your scene.  The text and prism objects in the official POV-Ray used 
to have this problem, too; I think the prism objects still do.

Post a reply to this message

On a side note to this thread I have always assumed from what is specified
in the docs that mesh objects are not allowed in csg operations.

From the Pov v3.1d documentation:

------------------------

Finite Patch Primitives

There are six totally thin, finite objects which have no well-defined inside.
They are bicubic patch, disc, smooth triangle, triangle, polygon and mesh.
They may be combined in CSG union but cannot be use in other types of CSG
(or inside a clipped_by statement). 

---------------------------------

  It specificaly states that these objects CANNOT be used in any csg operation
except for a union. If you take a moment to render the code below this note
you will find that this is not altogether true. I put together 4 triangles
that make up a square flat face for simplicity sake. The csg operations
that I have illustrated below work perfectly and the only thing the parser
does in protest is issue a quiet warning that patch objects are not allowed
in csg operations.  

Comments anyone ?


/******************************/

camera{location<0,0,-5>look_at 0}
light_source{<0,0,-30>rgb 1}

// first operation

 intersection{
   mesh {
    triangle{<-1,-1,0>,<0,0,0>,< 1,-1,0>}
    triangle{<-1,-1,0>,<0,0,0>,<-1, 1,0>}
    triangle{<-1, 1,0>,<0,0,0>,< 1, 1,0>}
    triangle{< 1, 1,0>,<0,0,0>,< 1,-1,0>}
    pigment{rgb 1}
   } // end mesh object

    sphere{0,.5 
      pigment{blue 1}
     inverse
    } // end sphere object

   translate<-1.5,0,0>

  } // end intersection


// second operation

 difference{
   mesh {
    triangle{<-1,-1,0>,<0,0,0>,< 1,-1,0>}
    triangle{<-1,-1,0>,<0,0,0>,<-1, 1,0>}
    triangle{<-1, 1,0>,<0,0,0>,< 1, 1,0>}
    triangle{< 1, 1,0>,<0,0,0>,< 1,-1,0>}
    pigment{rgb 1}
   } // end mesh object

    sphere{0,.5 
      pigment{blue 1}
     inverse
    } // end sphere object

   translate<1.5,0,0>

  } // end intersection


/*********************************/


-- 
Ken Tyler

mailto://tylereng@pacbell.net

Post a reply to this message

My understanding was that they are part-time workers in CSG. Either they
do or they don't function correctly in difference, intersection or
merge. What I don't understand is *when* that is the case. Believe it's
something to do with the intersection angle (of course) since the
primitives have to be found in the right way all along the CSG. I've
used these before too in CSG, regardless of the statements in the DOC,
as well as many other things I do right or wrong.


Ken wrote:
> 
> On a side note to this thread I have always assumed from what is specified
> in the docs that mesh objects are not allowed in csg operations.
> 
> From the Pov v3.1d documentation:
> 
> ------------------------
> 
> Finite Patch Primitives
> 
> There are six totally thin, finite objects which have no well-defined inside.
> They are bicubic patch, disc, smooth triangle, triangle, polygon and mesh.
> They may be combined in CSG union but cannot be use in other types of CSG
> (or inside a clipped_by statement).
> 
> ---------------------------------
> 
>   It specificaly states that these objects CANNOT be used in any csg operation
> except for a union. If you take a moment to render the code below this note
> you will find that this is not altogether true. I put together 4 triangles
> that make up a square flat face for simplicity sake. The csg operations
> that I have illustrated below work perfectly and the only thing the parser
> does in protest is issue a quiet warning that patch objects are not allowed
> in csg operations.
> 
> Comments anyone ?
> 
> /******************************/
> 
> camera{location<0,0,-5>look_at 0}
> light_source{<0,0,-30>rgb 1}
> 
> // first operation
> 
>  intersection{
>    mesh {
>     triangle{<-1,-1,0>,<0,0,0>,< 1,-1,0>}
>     triangle{<-1,-1,0>,<0,0,0>,<-1, 1,0>}
>     triangle{<-1, 1,0>,<0,0,0>,< 1, 1,0>}
>     triangle{< 1, 1,0>,<0,0,0>,< 1,-1,0>}
>     pigment{rgb 1}
>    } // end mesh object
> 
>     sphere{0,.5
>       pigment{blue 1}
>      inverse
>     } // end sphere object
> 
>    translate<-1.5,0,0>
> 
>   } // end intersection
> 
> // second operation
> 
>  difference{
>    mesh {
>     triangle{<-1,-1,0>,<0,0,0>,< 1,-1,0>}
>     triangle{<-1,-1,0>,<0,0,0>,<-1, 1,0>}
>     triangle{<-1, 1,0>,<0,0,0>,< 1, 1,0>}
>     triangle{< 1, 1,0>,<0,0,0>,< 1,-1,0>}
>     pigment{rgb 1}
>    } // end mesh object
> 
>     sphere{0,.5
>       pigment{blue 1}
>      inverse
>     } // end sphere object
> 
>    translate<1.5,0,0>
> 
>   } // end intersection
> 
> /*********************************/
> 
> --
> Ken Tyler
> 
> mailto://tylereng@pacbell.net

-- 
 omniVERSE: beyond the universe
  http://members.aol.com/inversez/POVring.htm
 mailto:inv### [at] aolcom?PoV

Post a reply to this message