Hi, everybody.
A triangle hasn't a well defined solid inside and an outside, that's
obvious. And so even a triangle mesh.
But if I know that my mesh represents a closed surface (or a set of closed
surfaces), there is an easy way to know if a point is inside or outside.
It is the Jordan's closed curve theorem, the same used with polygons:

   "if a line traced from the point to be tested to an external point touchs
the curve an odd nuber of times, then the point is inside the curve.
Otherwise it's outside"

Well, this works even in the space, where a "curve" is a "surface".
Furthermore, each triangle can have at least only one intersection with a
line, so the theorem could be read as:

   "if a line traced from the point to be tested to an external point touchs
an odd number of triangles, then the point is inside the mesh"

Well, of course this doesn't work with not perfectly closed meshes: the
results would be unpredictable.
So, what about a modifier: the keyword "closed". If I define a

triangle_mesh {
   closed
   triangle { ... }
   [...]
}

I am telling the tracer "trust me: this is a closed mesh". In this case, one
could use a closed triangle mesh in CSG...
I could have a closed triangle mesh representing an Easter Island Head, and
then subtract half of it from an iron box, and obtain the crusher of the
Easter Island Heads Factory (chains and steam here and there...)

I don't know the internal hierarchy of a mesh, but if the triangles were
sorted in some way, there could be many speedups.
With a normal camera, even the vista buffer could be used: if I trace the
line from the camera to a point to be tested, I must test only the triangles
whose vista box are hit.
I could put a special buffer (analogous to the light buffer) in the middle
of the mesh: this would minimize overlapping areas. And if the center of the
triangle buffer were inside the mesh? No problem: an odd number of
intersection would mean "the point is outside", an even one "the point is
inside"...
Bye!
:Daniele

Post a reply to this message

On Thu, 4 Mar 1999 16:59:57 +0100, Daniele Varrazzo <pir### [at] officineit> wrote:
>Hi, everybody.
>A triangle hasn't a well defined solid inside and an outside, that's
>obvious. And so even a triangle mesh.
>But if I know that my mesh represents a closed surface (or a set of closed
>surfaces), there is an easy way to know if a point is inside or outside.
>It is the Jordan's closed curve theorem, the same used with polygons:

There are some gotchas with that algorithm.  If you intersect an edge or a 
vertex, you have to do some extra work to determine whether the intersection 
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.  

There's another way, though: 

First, when someone says a triangle mesh is closed, it's relatively easy to 
verify that that's likely the case: simply verify that each edge has exactly 
two adjacent faces.  This won't catch certain degenerate self-intersecting 
surfaces, but it'll be a good start.  From there, it's a (relatively) simple 
matter to reorient all of the triangles so that the insideness test doesn't 
require intersection counting, but only requires finding the closest triangle 
along a random ray and checking the orientation of that triangle relative to 
the ray.  Meshes already have an internal structure that optimizes this search.

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.

Post a reply to this message

Ron Parker wrote:
> 
> First, when someone says a triangle mesh is closed, it's relatively easy to
> verify that that's likely the case: simply verify that each edge has exactly
> two adjacent faces.  This won't catch certain degenerate self-intersecting
> surfaces, but it'll be a good start.  From there, it's a (relatively) simple
> matter to reorient all of the triangles so that the insideness test doesn't
> require intersection counting, but only requires finding the closest triangle
> along a random ray and checking the orientation of that triangle relative to
> the ray.  Meshes already have an internal structure that optimizes this search.

I like this.

> 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.)

My implementation of this is very simple and really hasn't been tested much.
I don't handle any of the gotchas (like intersecting an edge, but I like
using orientation better anyway (it should be faster and is a more standard
way of solving the problem).  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.

-Nathan

Post a reply to this message

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