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

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

On Sun, 07 Mar 1999 20:05:31 -0800, Ken <tyl### [at] pacbellnet> 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.

There are indeed two reasons a mesh can't currently be used in an
intersection.  One is that they have no inside: the "am I inside"
function for meshes always says "no."  The other is that they don't
always return all intersections when asked.  What we're discussing
is making those two statements no longer true.  What you've found
must be a fluke.  It's been done before, in POV 2.2 with heightfields
which at that time didn't have an inside either.  But I wouldn't 
count on it working from all angles.

Post a reply to this message

Ron Parker <par### [at] my-dejanewscom> wrote:
: It's been done before, in POV 2.2 with heightfields
: which at that time didn't have an inside either.  But I wouldn't 
: count on it working from all angles.

  What do you mean? I just tested this and it seemed to work just fine:
http://www.cs.tut.fi/~warp/hftest.jpg

  The code:

camera { location -z*26 look_at 0 angle 35 }
light_source { <100,200,-200>,1 }
light_source { <-200,-200,-50>,<.2,.4,.6> }

#declare Test=
difference
{ height_field { tga "hf.tga" translate -.5 scale <4,1,4> }
  sphere { 0,1.5 }
  pigment { rgb <1,0,0> }
  finish { specular .5 }
}

object { Test rotate x*-90 translate -x*5+y*2.5 }
object { Test rotate x*-54 translate -x*0+y*2.5 }
object { Test rotate x*-18 translate x*5+y*2.5 }
object { Test rotate x*18 translate -x*5-y*2.5 }
object { Test rotate x*54 translate -x*0-y*2.5 }
object { Test rotate x*90 translate x*5-y*2.5 }


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

Post a reply to this message

On 8 Mar 1999 12:22:02 -0500, Nieminen Mika <war### [at] cctutfi> wrote:
>Ron Parker <par### [at] my-dejanewscom> wrote:
>: It's been done before, in POV 2.2 with heightfields
>: which at that time didn't have an inside either.  But I wouldn't 
>: count on it working from all angles.
>
>  What do you mean? I just tested this and it seemed to work just fine:
>http://www.cs.tut.fi/~warp/hftest.jpg

Sorry, I wasn't clear enough.  Height fields now have a well-defined
inside, but in POV 2.2 (or maybe it was 2.0... that's the problem with us
old farts, we're so forgetful...) they did not.  That didn't keep people from
using them as clipping objects, though.  There was even a demo scene in the
official distribution showing one such use.  It just didn't always
work from every angle.  The same now appears to be true of mesh objects.

Post a reply to this message

Ron Parker wrote in message <36e3d8c8.0@news.povray.org>...
>On Sun, 07 Mar 1999 20:05:31 -0800, Ken <tyl### [at] pacbellnet> 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.
>
>There are indeed two reasons a mesh can't currently be used in an
>intersection.  One is that they have no inside: the "am I inside"
>function for meshes always says "no."  The other is that they don't
>always return all intersections when asked.  What we're discussing
>is making those two statements no longer true.  What you've found
>must be a fluke.  It's been done before, in POV 2.2 with heightfields
>which at that time didn't have an inside either.  But I wouldn't
>count on it working from all angles.

I've found that doing what Ken has done usually works. You can usually use
differences to chop bits off meshes. If you try to reverse the difference,
take the mesh from the sphere, it doesn't quite work though. The mesh
appears as an infinitely thin surface (which makes sense I guess) and
appears to behave as such in CSGs.

On the topic in general, I would think the method of using the normals to
determine the "inside" was more useful as this way open meshes could also be
used. I still have a little trouble picturing how this would work exactly
though!

Regards
Gordon

Post a reply to this message

On Thu, 11 Mar 1999 22:03:44 +0800, Gordon <gbe### [at] birdcameroncomau> wrote:
>I've found that doing what Ken has done usually works. You can usually use
>differences to chop bits off meshes. If you try to reverse the difference,
>take the mesh from the sphere, it doesn't quite work though. The mesh
>appears as an infinitely thin surface (which makes sense I guess) and
>appears to behave as such in CSGs.

Are you sure?  It seems it should work the other way, since meshes
are defined to have no inside.  Difference is just intersection with
an inverse, so I'll use intersection to explain:

What intersection does is find all ray-object intersections with each 
component object, then filter the results so only the intersections
that are inside all other component objects are returned.  Since
nothing is inside a mesh, all intersections with non-mesh objects
should be ignored.  Intersections with the mesh object would survive.
The result seems like it would be quite unlike an intersection.

difference{sphere{...}mesh{...}} would return all intersections
with the sphere, plus whatever mesh surfaces fall inside the sphere.
For opaque objects, the result should be a sphere.

difference{mesh{...}sphere{...}} would return whatever intersections
with the mesh fall outside the sphere, but no intersections with the
sphere.  The result would be a hole in your mesh, not a spherical
cutout.

>On the topic in general, I would think the method of using the normals to
>determine the "inside" was more useful as this way open meshes could also be
>used. I still have a little trouble picturing how this would work exactly
>though!

Quite simply, it wouldn't really.  The "inside" of such a mesh would not
be well-defined, as whether a given point were inside or outside would
depend on which triangle it hit when testing.  Some points would always
be inside, of course, and some outside, but for anything but a simple flat
mesh you'd have lots of points that were undefined.

Post a reply to this message

Gordon wrote:
> 
> On the topic in general, I would think the method of using the normals to
> determine the "inside" was more useful as this way open meshes could also be
> used. I still have a little trouble picturing how this would work exactly
> though!
> 
> Regards
> Gordon

This sounds a bit like treating the triangles of a mesh as if they were
prisms which extend off to infinity in one direction (defined by the
normal) and just not drawing the sides.  I've had a weird experience
along these lines with disks in an old version of the superpatch (the
compile I made for Linux was buggy so I didn't think much of it at the
time).  Anyway, depending on where I put the camera relative to the
disk, I would get the standard warning about cameras inside non-hollow
objects causing problems with atmospheres.  Is it possible that pov does
try to treat some of these non-3d objects as if they were some strange
variant of a prism?

Would it be possible to use this to make an inside for a mesh (even an
open one?)  That way you could test if you are inside the prism of more
that one triangle and that should be enough to be inside your mesh, at
least for a simple mesh.  Would have to sit down and scratch my head for
a bit to see how to treat complicated shapes.  I just think that the
normals method is a nice way to go.

-- 
Carl Bartels, Department of Chemistry, Mcgill University, to reply to
me,
just kill a and 5 from the email name, Montreal, QC, cAnAdA

Post a reply to this message

On Thu, 11 Mar 1999 18:08:17 -0500, Carl Bartels 
	<cab### [at] bravo436chemmcgillca> wrote:
>Would it be possible to use this to make an inside for a mesh (even an
>open one?)  That way you could test if you are inside the prism of more
>that one triangle and that should be enough to be inside your mesh, at
>least for a simple mesh.  Would have to sit down and scratch my head for
>a bit to see how to treat complicated shapes.  I just think that the
>normals method is a nice way to go.

Consider a mesh of a bowl.  Any point in the part where the Chocolate 
Frosted Sugar Bombs go would be considered "inside" by this method, as 
would a good number of points in the environment, including some below 
the surface of the table (due to the rim of the bowl).

Even convex polyhedra would have problems.  Consider a football (without
seams.)  It's convex, but the intersections of the prisms associated with 
triangles near opposite ends are outside the surface of the football.

Post a reply to this message

Ron Parker heeft geschreven in bericht <36e9176a.0@news.povray.org>...
>Consider a mesh of a bowl.  Any point in the part where the Chocolate
>Frosted Sugar Bombs go would be considered "inside" by this method, as
>would a good number of points in the environment, including some below
>the surface of the table (due to the rim of the bowl).
>
>Even convex polyhedra would have problems.  Consider a football (without
>seams.)  It's convex, but the intersections of the prisms associated with
>triangles near opposite ends are outside the surface of the football.


I'm not hamperd by any knowledge of programming and raytracing theory, so if
what I try to say is bare nonsense have a good laugh, but please tell me
why.

I can imagine using planes instead of prisms to represent the triangles (in
a closed mesh). First use Ron's method to check if the mesh is closed. Then
for every triangle calculate the normal. Follow each normal in both
directions and count the intersections, to determine the inside (odd
number). Then replace the triangle by a plane with the "outside normal".
Then for every plane check wether all points of the mesh are on the inside
of the plane. Give these triangles the status intersection. All others get
the status union.
Now get the first triangle/plane with the status union, check what status
the neighbour triangles have. Is it union, put all these planes in a union
statement. Check the neighbours of the neighbours and so on until all
neighbour  triangles have the status intersection. Now go to the next "union
triangle" that is not in the first union already. Start a new union.
Repeat all this till there are no union triangles left. Now put all the
union blocks together with all triangles with status intersection in an
intersection block. The result should be a solid shape.
Does this make sense?
Something like this:

intersection{
      union{
         plane{-z, 0.5}
         plane{<-1,0,-1>,0}
         plane{< 1,0,-1>,0}
      }
      plane{-z, 1.5}
      plane{<-1,0,-1>,(4*sqrt(2)/2)}
      plane{< 1,0,-1>,(4*sqrt(2)/2)}
      plane{-x,3.5}
      plane{ x,3.5}
      plane{<-1,0, 1>,(4*sqrt(2)/2)}
      plane{< 1,0, 1>,(4*sqrt(2)/2)}
      plane{ z, 1.5}
      union{
         plane{ z, 0.5}
         plane{<-1,0, 1>,0}
         plane{< 1,0, 1>,0}
      }
   plane{y,1}
   plane{-y,1}
   pigment {rgb 0.8}
}

ingo
--
Met dank aan de muze met het glazen oog.

Post a reply to this message

On Fri, 12 Mar 1999 21:54:32 +0100, ingo <ing### [at] ingodemonnl> wrote:
>I can imagine using planes instead of prisms to represent the triangles (in
>a closed mesh). First use Ron's method to check if the mesh is closed. Then
>for every triangle calculate the normal. 

>Follow each normal in both
>directions and count the intersections, to determine the inside (odd
>number). 

This has all the same drawbacks as the original proposal, of course.  
There are better ways to find the outside normal.  In fact, the one I'm
thinking of is the same kind of algorithm you've proposed: 

1. start with a random triangle and pick a direction to be called "outside."  
2. Propagate this decision to its neighbors, and their neighbors, and so on 
   until there are no more neighbors.  Now you have a connected, closed piece 
   of the mesh with consistent normals.  
3. Pick a point outside the bounding box of the mesh.
4. If the point is "inside" the piece using the test below, flip all the 
   normals.  
5. If there are any triangles left that are not in the "mesh so far," pick one 
   and build a closed, connected surface for it using steps 1-4.  
6. If one of the points on the new piece is inside the "mesh so far", flip its 
   normals again before adding it to the "mesh so far."  
7. If any piece of the "mesh so far" is inside the new piece, flip that piece's 
   normals before adding the new piece.  Do this for every piece that's inside
   the new piece.
8. Repeat from step 5 until you run out of unused triangles.

>Then replace the triangle by a plane with the "outside normal".

If you know the outside normal for every triangle, your work is done.  For
any given point, just fire a ray at a random triangle in the mesh.  At the
first intersection (possibly not the triangle you fired at) check the normal.
If it points away from you, you're inside.  If it points toward you, you're
not.  If it's perpendicular, ignore it and try firing at a different triangle.

[plausible solution snipped for space]
>Does this make sense?

It makes sense.  I think it would even work.  But I think it'd be even slower
than intersection-counting.  It would almost certainly be slower than the 
method I've proposed.

Post a reply to this message

Ron Parker wrote in message <36e7f128.0@news.povray.org>...
>On Thu, 11 Mar 1999 22:03:44 +0800, Gordon <gbe### [at] birdcameroncomau>
wrote:
>>I've found that doing what Ken has done usually works. You can usually use
>>differences to chop bits off meshes. If you try to reverse the difference,
>>take the mesh from the sphere, it doesn't quite work though. The mesh
>>appears as an infinitely thin surface (which makes sense I guess) and
>>appears to behave as such in CSGs.
>
>Are you sure?  It seems it should work the other way, since meshes
>are defined to have no inside.  Difference is just intersection with
>an inverse, so I'll use intersection to explain:
>
>What intersection does is find all ray-object intersections with each
>component object, then filter the results so only the intersections
>that are inside all other component objects are returned.  Since
>nothing is inside a mesh, all intersections with non-mesh objects
>should be ignored.  Intersections with the mesh object would survive.
>The result seems like it would be quite unlike an intersection.
>
>difference{sphere{...}mesh{...}} would return all intersections
>with the sphere, plus whatever mesh surfaces fall inside the sphere.
>For opaque objects, the result should be a sphere.
>
>difference{mesh{...}sphere{...}} would return whatever intersections
>with the mesh fall outside the sphere, but no intersections with the
>sphere.  The result would be a hole in your mesh, not a spherical
>cutout.

A hole in the mesh is what I mean't. I was considering the mesh to be a
surface not a solid. So the difference{mesh{}sphere{}} does let me "trim" a
mesh which is often useful. I agree completely that POVRay doesn't currently
deal with meshes as solid objects in any sensible way.

>
>>On the topic in general, I would think the method of using the normals to
>>determine the "inside" was more useful as this way open meshes could also
be
>>used. I still have a little trouble picturing how this would work exactly
>>though!
>
>Quite simply, it wouldn't really.  The "inside" of such a mesh would not
>be well-defined, as whether a given point were inside or outside would
>depend on which triangle it hit when testing.  Some points would always
>be inside, of course, and some outside, but for anything but a simple flat
>mesh you'd have lots of points that were undefined.
>

From the programmers point of view, I agree. What I mean't was that from a
modellers point of view, this may be more useful. Though if it can't be
implemented, I guess the point is moot.

Regards
Gordon

Post a reply to this message