> > Possibly.  This implementation of solid meshes has some problems, as
> > you can see.
> 
> Just an idea, but could it help to test multiple times with different
> vectors to avoid these errors? Just use the result that the majority of
> vectors produce.

	Would be more expensive... but also more safe.
	Maybe the "inside" test could be simplified... For instance, instead
of counting the odd/even number of triangles that the test-ray hits, why
not to test the surface normal of the FIRST intersected triangle ? I'm
not sure, but I guess the dot product of the ray and this normal will be
positive if inside the mesh, negative if not (whatever is the mesh shape).
Anything wrong ?


*** Nicolas Calimet
*** http://pov4grasp.free.fr

Post a reply to this message

On Tue, 29 Aug 2000 13:33:57 +0200, Nicolas Calimet wrote:
>> > Possibly.  This implementation of solid meshes has some problems, as
>> > you can see.
>> 
>> Just an idea, but could it help to test multiple times with different
>> vectors to avoid these errors? Just use the result that the majority of
>> vectors produce.
>
>	Would be more expensive... but also more safe.
>	Maybe the "inside" test could be simplified... For instance, instead
>of counting the odd/even number of triangles that the test-ray hits, why
>not to test the surface normal of the FIRST intersected triangle ? I'm
>not sure, but I guess the dot product of the ray and this normal will be
>positive if inside the mesh, negative if not (whatever is the mesh shape).
>Anything wrong ?

Yes.  The normals are not constrained to be consistent within the mesh.
However, with a little work, they could be made consistent, at which point
such a scheme would work.  It's just a matter of writing the code...

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

Post a reply to this message

> The normals are not constrained to be consistent within the mesh.
> However, with a little work, they could be made consistent, at which point
> such a scheme would work.  It's just a matter of writing the code...

	Okay I thought it's the reason why this obvious test was not actually
used in MegaPOV. But how to make the triangle normals consistent ? I was
thinking about some simple (but slow) method like this:

1) Calculate the geometric center of all the mesh vertices
2) For each triangle
  a. calculate its geometric center from its vertices
     or even simply choose one of its vertex
  b. compare its normal vector to the (triangle center)-(vertices
     center) vector.
  c. revert the triangle vector if dot product is negative

	I'm not a genius in geometry/mathematics at all, but it sounds to
be a reasonnable approach to me... I'm waiting for comments from all you
clever boyz out there ;-)


*** Nicolas Calimet
*** http://pov4grasp.free.fr

Post a reply to this message

On Tue, 29 Aug 2000 16:43:43 +0200, Nicolas Calimet wrote:
>> The normals are not constrained to be consistent within the mesh.
>> However, with a little work, they could be made consistent, at which point
>> such a scheme would work.  It's just a matter of writing the code...
>
>	Okay I thought it's the reason why this obvious test was not actually
>used in MegaPOV. But how to make the triangle normals consistent ? I was
>thinking about some simple (but slow) method like this:

The easiest way is to pick a face to be the reference, then realign all 
adjacent faces so they have the same "sense."  Continue until you've visited
all adjacent faces.  If an unvisited face still exists, repeat with that face
as the reference.  When finished, reorient as necessary to correct for the
possibility that an entire surface is inverted.

This only works on meshes that are well-behaved, though.  If an edge is 
shared by more or fewer than exactly two faces, the mesh is not well-behaved
and the procedure will fail.  (But in those cases, "inside" isn't well-defined
anyway.)

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

Post a reply to this message

On Tue, 29 Aug 2000 16:43:43 +0200, Nicolas Calimet wrote:
>1) Calculate the geometric center of all the mesh vertices
>2) For each triangle
>  a. calculate its geometric center from its vertices
>     or even simply choose one of its vertex
>  b. compare its normal vector to the (triangle center)-(vertices
>     center) vector.
>  c. revert the triangle vector if dot product is negative
>

This algorithm is only guaranteed to work for convex meshes.  It 
fails for meshes with concavities or with multiple surfaces.

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

Post a reply to this message

Chris Huff <chr### [at] maccom> wrote:
: Just an idea, but could it help to test multiple times with different 
: vectors to avoid these errors? Just use the result that the majority of 
: vectors produce.

  There's one problem here.
  Suppose that you shoot two rays instead of one, to be sure. Then one
ray says that you are outside, the other one says that you are inside.
What do you do?

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

>   There's one problem here.
>   Suppose that you shoot two rays instead of one, to be sure. Then one
> ray says that you are outside, the other one says that you are inside.
> What do you do?

	Check at least three rays in the x/y/z directions ?


*** Nicolas Calimet
*** http://pov4grasp.free.fr

Post a reply to this message

In article <39abe095@news.povray.org>, Warp <war### [at] tagpovrayorg> 
wrote:

>   There's one problem here.
>   Suppose that you shoot two rays instead of one, to be sure. Then one
> ray says that you are outside, the other one says that you are inside.
> What do you do?

Easy: shoot a third one.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

I have done this kind of triangle mesh "fixing" myself (in my triangle
mesh smoother program).
  The idea is quite simple:

  1. Take the first triangle and mark it as 'handled'.

  2. Search all the triangles which are adjacent to this one and are
     not marked as 'handled'. An adjacent triangle is one that shares two
     vertices with this one.

  3. Check if the adjacent triangle is ordered correctly. That is, if the
     shared vertices are listed in inverse order in the adjacent triangle than
     in the current triangle, then it's ok. If they are listed in the same
     order, then you have to swap the other triangle.

  4. Now mark these adjacent triangles as 'handled' and for each one of them
     make recursively steps 2, 3 and 4 until no more triangles are found.

  5. After that, search for some unhandled triangle. If the mesh consisted of
     one contiguous surface, you'll not find any, but you have to do this
     because the mesh may consist of several separate parts. If you find
     an unhandled triangle, make all steps 1, 2, 3, 4 and 5 for it.


  This works pretty well, but it's very slow, specially with big meshes.
The slowest step is the second one (ie. the searching). There's probably some
way of speeding it up using some tree structure or hash table.

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

Chris Huff <chr### [at] maccom> wrote:
: Easy: shoot a third one.

  Could it be possible that two of them are wrong and one is right?-)

  All right, all right, I know that it's more probable that two are right
and one wrong and the other way around is a very rare case.

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