How does one test to see if a triangle's vertices are arranged in a
clockwise or counter clockwise direction?


Jim

Post a reply to this message

Jim Kress <kre### [at] kressworkscom> wrote:
> How does one test to see if a triangle's vertices are arranged in a
> clockwise or counter clockwise direction?

  Looking from which side?

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

>   Looking from which side?

I am presented with a list of vertices (and their Cartesian coordinates) and
a set of triples that specify the vertex numbers for each triangle.  That is
all the information I have

How would I find out which side I am looking and then the direction?

Jim

Post a reply to this message

Jim Kress <kre### [at] kressworkscom> wrote:
> I am presented with a list of vertices (and their Cartesian coordinates) and
> a set of triples that specify the vertex numbers for each triangle.  That is
> all the information I have

> How would I find out which side I am looking and then the direction?

  You are looking at the side which is visible? A triengle mesh has two
sides. Which side would you want to know? What direction are you talking
about?

  I have to make guesses here since you are not giving me enough information.
  Is your situation so that you *know* that the triangle vertices are listed
with a certain winding (eg. clockwise) and you want to know if you are
looking at the triangle from the "outside" or the "inside"?
  Or is it so that the triangle vertices are given in a random order and
you need to know for each triangle, which side is facing the same direction
as the adjacent triangles?
  Or something else?

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

I have a closed, 3D surface that is represented by a set of triangles.  I
have a list of the vertices of every triangle (i.e. the Cartesian
coordinates of each vertex) and I have a list of integers (grouped in
threes) where each group of integers gives me the number of each vertex in a
triangle.

For example:

vertex 1 is 1.0,2.0,3.0
vertex 2 is 2.0,3.0,4.0
vertex 3 is 4.0,5.0,6.0
vertex 4 is 5.0,6.0,7.0

Triangle 1 is made up of vertices 1,2,3
Triangle 2 is made up of vertices 1,2,4

The data I am given is:

1.0,2.0,3.0
2.0,3.0,4.0
4.0,5.0,6.0
5.0,6.0,7.0
1,2,3
1,2,4

This is all the data I am given.  I am not given any data about which side
of the triangle I am looking at.  I am not given any data about the winding
of the vertices.

What I want to do is make sure all triangle normals are pointing out of the
surface and all triangles are wound counter-clockwise.

Is that a better statement of my problem?  Any help you can provide would be
appreciated.

Jim

Post a reply to this message

Jim Kress wrote:
> 
> >   Looking from which side?
> 
> I am presented with a list of vertices (and their Cartesian coordinates) and
> a set of triples that specify the vertex numbers for each triangle.  That is
> all the information I have
> 
> How would I find out which side I am looking and then the direction?
> 
> Jim

First, you need your location (let's it be O).
Then compute the normal at one vertex (using vector product of
the edge of the triangle),
and lastly use the sign of the scalar product of the normal with
the vector O-vertex.
Clockwise will have one sign, and anti the other one.

Another use/convention of clockwise/anticlockwise orientation is
to indicate hole in mesh, but then they provide the normal of the
triangle too (because hole do not depent on view point). This
is obviously not the case here.

At best, all you could have in your case is a fast scanline engine,
removing the triangle which are facing the wrong direction
(assuming the mesh is closed and without holes). Or a dual texturing of
the triangles.
-- 
Non Sine Numine
http://grimbert.cjb.net/
Etiquette is for those with no breeding;
fashion for those with no taste.

Post a reply to this message

Jim Kress wrote:
> 
> I have a closed, 3D surface that is represented by a set of triangles.  
[SNIP]

> This is all the data I am given.  I am not given any data about which side
> of the triangle I am looking at.  I am not given any data about the winding
> of the vertices.
> 
> What I want to do is make sure all triangle normals are pointing out of the
> surface and all triangles are wound counter-clockwise.

See my other answer for the details.
Just choose any arbitrary location (possibly not right on the mesh, but even inside
is fine).
If the sign does not please you, just invert two vertices of the triangle.

Please note that you are not provided with the normal, so your first part looks
caduc (unless you exactly know how the normal is going to be computed).
The calculation of a normal always gives the same line, but the orientation
of the vector depends on the implementation. Your second part seems to imply
that you have such (implicit) knowledge about the internal computation.

> Is that a better statement of my problem?  Any help you can provide would be
> appreciated.

Just for curiosity, why do you need to do that ?


-- 
Non Sine Numine
http://grimbert.cjb.net/
Etiquette is for those with no breeding;
fashion for those with no taste.

Post a reply to this message

Jim Kress <kre### [at] kressworkscom> wrote:
> What I want to do is make sure all triangle normals are pointing out of the
> surface and all triangles are wound counter-clockwise.

  Why didn't you say so from the very beginning?

  The problem is not trivial nor necessarily fast to compute, specially
if you can't trust that the triangles are given all with the same winding.

  The problem makes sense only on closed triangle meshes (if the mesh is
open, it can't have a well-defined interior). Also each triangle should be
adjacent (ie. share two vertices) to exactly three other triangles, no more,
no less. If these conditions are not met, the problem is not unambiguous
and thus doesn't necessarily have one unique correct answer (and specially
if a triangle is not adjacent to exactly three other triangles, but less
or, heaven forbid, more, all kinds of funny problems will arise when trying
to decide which side is which). Another sanity prerequisite: no coincident
surfaces, thanks.

  If the conditions are met, then the problem is solvable and has a
unique solution (as your intuition probably tells you).

  First you have to take a triangle and solve which side is facing
outside the closed mesh and which side is facing inwards.
  There are probably several algorithms for resolving this, but the one
that comes to mind is: Shoot a ray from the surface of the triangle to one
side of it (it doesn't really matter which direction), and if hits an even
amount of other triangles (also 0 is even), that side is is outside, else
it's inside.
  This has to be implemented with extreme care. There's a patological case
which has to be handled carefully or else the result will be erroneous:
If the ray hits a triangle exactly in its edge or even in its vertex.
The problem with this is whether you have to count the other triangle sharing
that edge or not: In some cases you should not count it while in other
cases you must count it! (The two different cases happen when the ray
goes "through" the surface formed by the two triangles, or when it just
"touches" the edge formed by the two triangles, but without going through
it. If the ray goes through a vertex point, the situation is even more
complicated.)
  I would say that the easiest way is that if a ray-hits-edge or
ray-hits-vertex case is detected, then just forget that ray and shoot
another ray to another direction. (In theory this could lead to an
infinite loop in an extremely pathological case, but I think that the
odds for this happening are laughably small.)

  Once you have made sure for this triangle which side is the outside,
you can change the order of its vertices if necessary.
  Now the next task is to fix the order of the vertices of all the other
triangles as well.
  There are basically two approaches for this: You could repeat the
raytracing process described above for each triangle, or you could fix
the other triangles with the help of this one, which you already know for
sure.
  The latter method works like this: Since you know the right ordering of
this triangle, you can know the right order for the three triangles adjacent
to it (the two shared vertices in the adjacent triangle should be listed in
reverse order than in this triangle; if they aren't, just swap them and
there you are: it's fixed). Now you can do this process recursively to
each of the two other triangles adjacent to the three triangles you just
fixed (you have to ne able to mark triangles as "fixed" so that you know
where to continue and where to stop).
  Which one of these two methods is better depends. It's quite clear that
the raytracing method is much slower than the adjacent-triangle-checking
method. On the other hand, the latter needs more memory (in pathological
cases *huge* amounts of memory) because you need to do it recursively.
(It might be possible to develop a non-recursive, ie. iterative version
of this algorithm which doesn't take as much memory, but I'm too tired
to think about that now.)

  All in all, it's not trivial and requires some complicated algorithms.
You'd be better good at coding. :)

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

Thanks.  I'll try your suggestions and perhaps ask more questions later.

Jim

Post a reply to this message

Thanks for your help.  I'll try what you (and Warp) suggested.

Jim

Post a reply to this message

> that comes to mind is: Shoot a ray from the surface of the triangle to one
> side of it (it doesn't really matter which direction), and if hits an even
> amount of other triangles (also 0 is even), that side is is outside, else
> it's inside.

Got any suggestions how I would do this?  I've looked through the Internet
and have not been able to find an algorithum (or code) that would show me
how this is done.

Thanks.

Jim

Post a reply to this message

Warp wrote:

> Jim Kress <kre### [at] kressworkscom> wrote:
>> What I want to do is make sure all triangle normals are pointing out of
>> the surface and all triangles are wound counter-clockwise.
[...] 
>   The latter method works like this: Since you know the right ordering of
> this triangle, you can know the right order for the three triangles
> adjacent to it (the two shared vertices in the adjacent triangle should be
> listed in reverse order than in this triangle; if they aren't, just swap
> them and there you are: it's fixed). Now you can do this process
> recursively to each of the two other triangles adjacent to the three
> triangles you just fixed (you have to ne able to mark triangles as "fixed"
> so that you know where to continue and where to stop).
>   Which one of these two methods is better depends. It's quite clear that
> the raytracing method is much slower than the adjacent-triangle-checking
> method. On the other hand, the latter needs more memory (in pathological
> cases *huge* amounts of memory) because you need to do it recursively.

Sorry, but I can't completely agree with you. This approach isn't that bad. 
What you want to do is to visit all triangles. What you describe is more or 
less a depth-first search in the dual graph of the mesh. Since the mesh is 
a simple closed surface, the graph (and its dual) has only a linear number 
of edges. Space and time consumption of the graph traversal is linear in 
the number of vertices, i.e. the best we can get.

Best regards
Thomas

Post a reply to this message

Thomas Willhalm <tho### [at] uni-konstanzde> wrote:
> Sorry, but I can't completely agree with you. This approach isn't that bad. 

  I didn't say it's bad. I said that it takes memory (while the raytracing
method doesn't). Yes, it takes a linear amount of memory with respect to
the number of triangles, but as the number of triangles can sometimes be
counted in millions, it is a considerable amount of memory.
  Of course if you implement it properly, it doesn't really matter with
current computers (if the search takes some megabytes of memory, who cares?).

> What you want to do is to visit all triangles. What you describe is more or 
> less a depth-first search in the dual graph of the mesh.

  Yes, a depth-first search is the best way to go. However, it needs to
be made with care so that it doesn't take too much memory (ie. to avoid
pushing a triangle onto the stack more than once).
  In fact, the best approach is not to make a true depth-first search, but
a slightly modified one:

  - We have to be able to mark triangles as "not handled" and "handled"
  0. Initialize all triangles as "not handled".
  1. Push a triangle onto the stack and mark it as "handled".
  2. Pop a triangle from the top of the stack (and remove it from there).
  3. For each three triangles adjacent to this one: if the triangle is
     marked "not handled", then fix it, mark it as "handled" and push it
     onto the stack.
  4. If the stack is not empty, return to step 2.

  This does not perform a true depth-first search, but it doesn't matter
because it makes the job with the minimum amount of stack usage (ie. a
triangle is never pushed onto the stack more than once).
  Of course it requires that the mesh is connected.

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

By the way, for the algorithm to work fast, you need to know for a triangle
which three triangles are adjacent to it. This is a separate problem in
itself.
  For this we need to introduce the notion of "edge". That is, an "edge"
knows the two triangles sharing that edge, and each triangle should know
the three edges it uses.
  Initializing the edge information fast is a problem in itself.

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

> that comes to mind is: Shoot a ray from the surface of the triangle to one
> side of it (it doesn't really matter which direction), and if hits an even
> amount of other triangles (also 0 is even), that side is is outside, else
> it's inside.

Got any suggestions how I would do this?  I've looked through the Internet
and have not been able to find an algorithum (or code) that would show me
how this is done.

Thanks.

Jim

Post a reply to this message

Jim Kress <nos### [at] kressworkscom> wrote:
> Got any suggestions how I would do this?  I've looked through the Internet
> and have not been able to find an algorithum (or code) that would show me
> how this is done.

  I have never read or thought about the details of raytracing a triangle,
but the basic algorithm is:
  1. Calculate the intersection point of the ray and the plane (eg. the
     value t for P*t+D, where P is the starting point of the ray and D is
     the direction of the ray).
  2. See if the intersection point is inside the boundaries defined by the
     triangle (the first fast test is if t<0, then the ray did not hit the
     triangle).
  3. You'll have to perform the test with *each* triangle in the mesh
     (except the current one), unless you implement some space subdivision
     algorithm, eg. an octree (but that would make the algorithm a lot more
     complicated, though faster).

  I can't say right now how step 2 is implemented.

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

"Warp" <war### [at] tagpovrayorg>  wrote:
>   I have never read or thought about the details of raytracing a triangle,
> but the basic algorithm is:
> [...]
>   2. See if the intersection point is inside the boundaries defined by the
>      triangle (the first fast test is if t<0, then the ray did not hit the
>      triangle).
> [...]
>   I can't say right now how step 2 is implemented.

May I help?

You have the plane defined by three points A,B,C.
You also have the intersection of the ray and the plane at point P.

Now you simply try to represent P by a linear combination of (C-A) and (B-A):

P=u*(C-A)+v*(B-A)

If, and only if,
    a)  A,B,C are forming a plane, and
    b)  P lies in the plane
this equation has exactly one solution for u and v.

now simply compare, if u and v are between 0 and 1 (including). if so, P is
inside the triangle and the ray hits the triangle.

IIRC, there was a shortcut, to combine your step 1 and 2, to speed up some
calculations, but concerning the current time, I'm simply to lazy and tired to
look it up now ...

Post a reply to this message

Jan Walzer <jan### [at] lzernet> wrote:
> If, and only if,
>     a)  A,B,C are forming a plane, and
>     b)  P lies in the plane

  Isn't a) implicitly true? Three points always define a plane.
  As for b), due to the limited accuracy of floating point numbers, it's
almost always false. However, I suppose that it suffices that P is close
enough to the plane.

  And I can believe that there could be a shortcut to see if a line
intersects a triangle. It's just too complicated for me to think being
this tired (and lazy) :)

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

"Warp" wrote:
> > If, and only if,
> >     a)  A,B,C are forming a plane, and
> >     b)  P lies in the plane

 Isn't a) implicitly true? Three points always define a plane.
 [X]  Yes

> As for b), due to the limited accuracy of floating point numbers, it's
> almost always false. However, I suppose that it suffices that P is close
> enough to the plane.
 [X]  Yes

>   And I can believe that there could be a shortcut to see if a line
> intersects a triangle. It's just too complicated for me to think being
> this tired (and lazy) :)
 [X] You understand


;)

Post a reply to this message

On 30 Jun 2002 18:52:37 -0400, Warp <war### [at] tagpovrayorg> wrote:

>  Isn't a) implicitly true? Three points always define a plane.

Yes, but they do not always define a unique plane. If they are
collinear, they define a plane stack.


Peter Popov ICQ : 15002700
Personal e-mail : pet### [at] vipbg
TAG      e-mail : pet### [at] tagpovrayorg

Post a reply to this message

Warp wrote:
>   This does not perform a true depth-first search, but it doesn't matter
> because it makes the job with the minimum amount of stack usage (ie. a
> triangle is never pushed onto the stack more than once).
>   Of course it requires that the mesh is connected.

I'm sorry, because I didn't write precisely which variant of 
"depth-first-search" I meant. What you described is exactly what 
I had in mind.

> By the way, for the algorithm to work fast, you need to know for a 
triangle
> which three triangles are adjacent to it. This is a separate problem in
> itself.
>  For this we need to introduce the notion of "edge". That is, an "edge"
> knows the two triangles sharing that edge, and each triangle should know
> the three edges it uses.
>  Initializing the edge information fast is a problem in itself.

I agree with you, that this is the bigger problem in terms of running time.
The vertices already have a unique number. (Probably, it's a good idea
to make sure that the numbers are unique first.)
What I suggest is to represent every edge by the sorted numbers of its
vertices and a pointer to its triangle. Sorting these pairs 
lexicographically should reveal triangles that share an edge. It's then 
possible to store pointers to the three neighbors for each triangle. 
However, this dominates the overall algorithm, because sorting needs 
O(n log n) time.

Best regards
Thomas

Post a reply to this message

"Thomas Willhalm" <tho### [at] uni-konstanzde> wrote in message
news:3d20184c@news.povray.org...
> Warp wrote:
> >   This does not perform a true depth-first search, but it doesn't matter
> > because it makes the job with the minimum amount of stack usage (ie. a
> > triangle is never pushed onto the stack more than once).
> >   Of course it requires that the mesh is connected.
>
> I'm sorry, because I didn't write precisely which variant of
> "depth-first-search" I meant. What you described is exactly what
> I had in mind.
>
> > By the way, for the algorithm to work fast, you need to know for a
> triangle
> > which three triangles are adjacent to it. This is a separate problem in
> > itself.
> >  For this we need to introduce the notion of "edge". That is, an "edge"
> > knows the two triangles sharing that edge, and each triangle should know
> > the three edges it uses.
> >  Initializing the edge information fast is a problem in itself.
>
I actually use a more comprehensive (double) linking system:

1. Each vertex knows its location and the ID of edges that connect to it (5
or 6).
2. Each edge knows the ID of its 2 vertices and 2 faces.
3. Each face knows the ID of its 3 vertices and 3 edges (actually I store
twice that to allow for tessellation)

This can be set up as a database application (SQL and all).  Under this
system, if you have a face and want its neighbors, go to each edge and get
the face ID that does not equal the ID of the current face.  Initial startup
can be a pain if the initial object is too large... so start with a small
one and recursively tessellate (cut each triangle into quarters using the
midpoints of the edges) until satisfied with the detail level.

But there is simpler way to tell if a triangle points in or out if

1. The surface is convex at all vertices.
2. You know where the center is (average of all vertices, O)

Say your triangle is at P1, P2, P3.  First you get a surface normal at P1:
N = vcross(P2-P1, P3-P1).

Now you compare it with the radius: DR = vdot(N,P1-O).  This is the cosine
of the angle between the vectors.  If DR>0 then the triangle points out,
otherwise it points in.  For more complex shapes you may want a "local"
center using only vertices within a certain radius of P1.

This will at least make all of the triangles point in a consistent
direction.

Post a reply to this message

> 1. The surface is convex at all vertices.

What exactly do you mean by this?  For example, if you have a kidney shaped
surface, which is a closed surface but curves in and out, does that meet
your assumption?

Jim

Post a reply to this message

Warp wrote:
> 
> Jim Kress <nos### [at] kressworkscom> wrote:
> > Got any suggestions how I would do this?  I've looked through the Internet
> > and have not been able to find an algorithum (or code) that would show me
> > how this is done.
> 
>   I have never read or thought about the details of raytracing a triangle,
> but the basic algorithm is:
>   1. Calculate the intersection point of the ray and the plane (eg. the
>      value t for P*t+D, where P is the starting point of the ray and D is
>      the direction of the ray).

I suppose you meant P + t*D  ?


>   2. See if the intersection point is inside the boundaries defined by the
>      triangle (the first fast test is if t<0, then the ray did not hit the
>      triangle).

There are some discussions about this topic in this thread:
http://groups.google.com/groups?th=53321682e5f42db6

This search may also be useful:
http://www.google.com/search?q=ray+triangle+intersection


>   3. You'll have to perform the test with *each* triangle in the mesh
>      (except the current one), unless you implement some space subdivision
>      algorithm, eg. an octree (but that would make the algorithm a lot more
>      complicated, though faster).
> 
>   I can't say right now how step 2 is implemented.
>...



Tor Olav

Post a reply to this message

Tor Olav Kristensen <tor### [at] hotmailcom> wrote:
>>   1. Calculate the intersection point of the ray and the plane (eg. the
>>      value t for P*t+D, where P is the starting point of the ray and D is
>>      the direction of the ray).

> I suppose you meant P + t*D  ?

  Yes.
  I'm not perfect no matter how much I wanted to be. :P

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

David Wallace <dar### [at] earthlinknet> wrote:
> 1. The surface is convex at all vertices.

  Unfortunately triangles meshes seldom are (purely convex surfaces are
usually rather boring and useless).

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

Warp wrote:
>...
>   And I can believe that there could be a shortcut to see if a line
> intersects a triangle. It's just too complicated for me to think being
> this tired (and lazy) :)

I think that my RayIntersectsTriangle() macro in the code below
provides such a shortcut (*), but I'm not sure yet if it is optimal.

(*) Not really for lines, but for rays (which has a defined direction)


Tor Olav


// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
// Copyright 2002 by Tor Olav Kristensen
// Email: tor### [at] hotmailcom
// http://www.crosswinds.net/~tok/povray
// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7

#version 3.5;
#include "colors.inc"

// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
// Intersection macros

#macro RayIntersectsTriangle(pRay, vRay, pA, pB, pC)

  #local vRA = pA - pRay;
  #local vRB = pB - pRay;
  #local vRC = pC - pRay;
  #local vABN = vcross(vRA, vRB);
  #local vBCN = vcross(vRB, vRC);
  #local vCAN = vcross(vRC, vRA);
  #local STP = vdot(vABN, vRC);
  #if (STP = 0)
    #debug "Macro RayIntersectsTriangle: "
    #debug "Degenerate triangle or "
    #debug "origin of ray lies in same plane as triangle\n"
    #local Intersect = false;
  #else
    #local AB = vdot(vRay, vABN);
    #local BC = vdot(vRay, vBCN);
    #local CA = vdot(vRay, vCAN);
    #if (AB = 0 | BC = 0 | CA = 0)
      #local Intersect = true; // Intersection at one or two edges
    #else
      #if (STP > 0)
        #local Intersect = (AB > 0 & BC > 0 & CA > 0);
      #else
        #local Intersect = (AB < 0 & BC < 0 & CA < 0);
      #end // if
    #end // if
  #end // if

  Intersect
      
#end // macro RayIntersectsTriangle


#macro LinePlaneIntersection(pLine, vLine, pPlane, vPlane)

  (pLine + vLine*vdot(pPlane - pLine, vPlane)/vdot(vLine, vPlane))

#end // macro LinePlaneIntersection

// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
// Set up and show triangle

#declare p0 = <1, 3, -2>;
#declare p1 = <2, -3, 3>;
#declare p2 = <-2, 1, -3>;

triangle {
  p0, p1, p2
  pigment { color rgbf <1, 1, 0, 0.2> }
}

union {
  sphere { p0, 0.03 }
  sphere { p1, 0.03 }
  sphere { p2, 0.03 }
  pigment { color Magenta*2 }
}

union {
  cylinder { p0, p1, 0.02 }
  cylinder { p1, p2, 0.02 }
  cylinder { p2, p0, 0.02 }
  pigment { color Cyan*2 }
}

// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
// Shoot some random rays and highlight those that hits the triangle

#declare R = 4;
#declare S = seed(5);

#declare Cnt = 0;
#while (Cnt < 150)
  #declare pR = (<1, 1, 1> - 2*<rand(S), rand(S), rand(S)>)*R;
  #declare vR = (<1, 1, 1> - 2*<rand(S), rand(S), rand(S)>);
  #if (vlength(vR) > 0)
    sphere {
      pR, 0.04
      pigment { color Green*2 }
    }
    cylinder {
      pR, pR + 100*vnormalize(vR), 0.02
      pigment { color White }
    }
    #if (RayIntersectsTriangle(pR, vR, p0, p1, p2))
      #local vPlaneNormal = vcross(p1 - p0, p2 - p0);
      #local pIntersect = 
        LinePlaneIntersection(pR, vR, p0, vPlaneNormal);
      cylinder {
        pR, pIntersect, 0.021
        pigment { color White*4 }
      }
      sphere {
        pIntersect, 0.06
        pigment { color Red*2 }
      }
    #end // if
  #end // if  
  #declare Cnt = Cnt + 1;
#end // while

// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7

background { color Blue/2 }

light_source {
  <1, 1, -3>*100 color White
  shadowless
}

camera {
  location -10*z
  look_at <0, 0, 0>
}

// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7

Post a reply to this message

Ooops.
I think that my "Intersection at one or two edges"
comment in the code I just posted is wrong.

See my new RayIntersectsTriangle() macro below.

If one does not want the edges and vertices to count as
part of the triangle, then just replace the >= and <=
operators below with > and < operators.


Tor Olav


Tor Olav Kristensen wrote:
>...
> I think that my RayIntersectsTriangle() macro in the code below
> provides such a shortcut (*), but I'm not sure yet if it is optimal.
>...
> // ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
> // Copyright 2002 by Tor Olav Kristensen
> // Email: tor### [at] hotmailcom
> // http://www.crosswinds.net/~tok/povray
> // ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
> 
> #version 3.5;
> #include "colors.inc"
> 
> // ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
> // Intersection macros
> 
> #macro RayIntersectsTriangle(pRay, vRay, pA, pB, pC)
> 
>   #local vRA = pA - pRay;
>   #local vRB = pB - pRay;
>   #local vRC = pC - pRay;
>   #local vABN = vcross(vRA, vRB);
>   #local vBCN = vcross(vRB, vRC);
>   #local vCAN = vcross(vRC, vRA);
>   #local STP = vdot(vABN, vRC);
>   #if (STP = 0)
>     #debug "Macro RayIntersectsTriangle: "
>     #debug "Degenerate triangle or "
>     #debug "origin of ray lies in same plane as triangle\n"
>     #local Intersect = false;
>   #else
>     #local AB = vdot(vRay, vABN);
>     #local BC = vdot(vRay, vBCN);
>     #local CA = vdot(vRay, vCAN);
>     #if (AB = 0 | BC = 0 | CA = 0)
>       #local Intersect = true; // Intersection at one or two edges
>     #else
>       #if (STP > 0)
>         #local Intersect = (AB > 0 & BC > 0 & CA > 0);
>       #else
>         #local Intersect = (AB < 0 & BC < 0 & CA < 0);
>       #end // if
>     #end // if
>   #end // if
> 
>   Intersect
> 
> #end // macro RayIntersectsTriangle

#macro RayIntersectsTriangle(pRay, vRay, pA, pB, pC)

  #local vRA = pA - pRay;
  #local vRB = pB - pRay;
  #local vRC = pC - pRay;
  #local vABN = vcross(vRA, vRB);
  #local vBCN = vcross(vRB, vRC);
  #local vCAN = vcross(vRC, vRA);
  #local STP = vdot(vABN, vRC);
  #if (STP = 0)
    #debug "Macro RayIntersectsTriangle: "
    #debug "Degenerate triangle or "
    #debug "origin of ray lies in same plane as triangle\n"
    #local Intersect = false;
  #else
    #local AB = vdot(vRay, vABN);
    #local BC = vdot(vRay, vBCN);
    #local CA = vdot(vRay, vCAN);
    #if (STP > 0)
      #local Intersect = (AB >= 0 & BC >= 0 & CA >= 0);
    #else
      #local Intersect = (AB <= 0 & BC <= 0 & CA <= 0);
    #end // if
  #end // if

  Intersect
      
#end // macro RayIntersectsTriangle

Post a reply to this message

Tor Olav Kristensen <tor### [at] hotmailcom> wrote:
> If one does not want the edges and vertices to count as
> part of the triangle, then just replace the >= and <=
> operators below with > and < operators.

  My suggestion was that if such case is detected, then the whole ray is
discarded and another ray is shot to another direction. The reason being
that it's easier to do that than to figure out whether the intersection
should be counted or not (there are cases where it has to be counted and
cases where it must not be counted). Making the wrong decision can result
in the wrong result (since the result of the test is a yes/no answer,
giving the wrong answer is catastrophical).

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

In article <3D2389CA.9E4E78B2@hotmail.com>,
 Tor Olav Kristensen <tor### [at] hotmailcom> wrote:

> I think that my RayIntersectsTriangle() macro in the code below
> provides such a shortcut (*), but I'm not sure yet if it is optimal.
> 
> (*) Not really for lines, but for rays (which has a defined direction)

I haven't really been following this conversation, so I might be missing 
something, but wouldn't this be a better way?

#macro RayIntersectsTriangle(pRay, vRay, pA, pB, pC)
    #local iNorm = < 0, 0, 0>;
    #local tmpTri = triangle {pA, pB, pC}
    #local Scrap = trace(tmpTri, pRay, vRay, iNorm);
    (iNorm.x != 0 | iNorm.y != 0 | iNorm.z != 0)
#end

-- 
Christopher James Huff <chr### [at] maccom>
POV-Ray TAG e-mail: chr### [at] tagpovrayorg
TAG web site: http://tag.povray.org/

Post a reply to this message

Christopher James Huff <chr### [at] maccom> wrote:
> I haven't really been following this conversation, so I might be missing 
> something, but wouldn't this be a better way?

> #macro RayIntersectsTriangle(pRay, vRay, pA, pB, pC)
>     #local iNorm = < 0, 0, 0>;
>     #local tmpTri = triangle {pA, pB, pC}
>     #local Scrap = trace(tmpTri, pRay, vRay, iNorm);
>     (iNorm.x != 0 | iNorm.y != 0 | iNorm.z != 0)
> #end

  The whole idea was to code that trace() function in C++.
  Even though POV-Ray has a trace() function, C++ doesn't. :P

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

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

> Christopher James Huff <chr### [at] maccom> wrote:
> > I haven't really been following this conversation, so I might be missing 
> > something, but wouldn't this be a better way?
> 
> > #macro RayIntersectsTriangle(pRay, vRay, pA, pB, pC)
> >     #local iNorm = < 0, 0, 0>;
> >     #local tmpTri = triangle {pA, pB, pC}
> >     #local Scrap = trace(tmpTri, pRay, vRay, iNorm);
> >     (iNorm.x != 0 | iNorm.y != 0 | iNorm.z != 0)
> > #end
> 
>   The whole idea was to code that trace() function in C++.

Ah...maybe these links would be of help:

http://www.2tothex.com/raytracing/
http://www.faqs.org/faqs/graphics/algorithms-faq/
http://www.cfxweb.net/files/Sources/Effects/Raytrace/
http://www.3dspot.com/raytracing.html

-- 
Christopher James Huff <chr### [at] maccom>
POV-Ray TAG e-mail: chr### [at] tagpovrayorg
TAG web site: http://tag.povray.org/

Post a reply to this message

Warp wrote:
> 
> Tor Olav Kristensen <tor### [at] hotmailcom> wrote:
> > If one does not want the edges and vertices to count as
> > part of the triangle, then just replace the >= and <=
> > operators below with > and < operators.
> 
>   My suggestion was that if such case is detected, then the whole ray is
> discarded and another ray is shot to another direction. The reason being
> that it's easier to do that than to figure out whether the intersection
> should be counted or not (there are cases where it has to be counted and
> cases where it must not be counted). Making the wrong decision can result
> in the wrong result (since the result of the test is a yes/no answer,
> giving the wrong answer is catastrophical).

Ok, I think I understand now.

Then I propose something similar to the approach
in the macro below. It detects several cases.

But it could even be refined further:

E.g. it could detect whether the ray hits an edge
or a vertice, even if the ray origin lies in the
same plane as the triangle.

And it could be improved so that it takes care of
round off problems (in programming languages other
than POV-Ray SDL).

Note that this macro has not been tested very
thoroughly, but for me it seems to work ok.


Tor Olav


#macro RayIntersectsTriangle(pRay, vRay, pA, pB, pC)

  #local DegenTri = -2;
  #local InPlane  = -1;
  #local Outside  =  0;
  #local Edge     =  1;
  #local Vertice  =  2;
  #local Inside   =  3;
  #local vRA = pA - pRay;
  #local vRB = pB - pRay;
  #local vRC = pC - pRay;
  #local vABN = vcross(vRA, vRB);
  #local STP = vdot(vABN, vRC);
  #if (STP = 0)
    #if (vlength(vcross(pB - pA, pC - pA)) = 0)
      #local State = DegenTri;
    #else
      #local State = InPlane;
    #end // if
  #else
    #local vBCN = vcross(vRB, vRC);
    #local vCAN = vcross(vRC, vRA);
    #local AB = vdot(vRay, vABN);
    #local BC = vdot(vRay, vBCN);
    #local CA = vdot(vRay, vCAN);
    #if (STP > 0)
      #if (AB < 0 | BC < 0 | CA < 0)
        #local State = Outside;
      #else
        #if (AB > 0 & BC > 0 & CA > 0)
          #local State = Inside;
        #else
          #if ((CA = 0 & AB = 0) | (AB = 0 & BC = 0) | (BC = 0 & CA = 0))
            #local State = Vertice;
          #else
            #local State = Edge;
          #end // if
        #end // if
      #end // if
    #else
      #if (AB > 0 | BC > 0 | CA > 0)
        #local State = Outside;
      #else
        #if (AB < 0 & BC < 0 & CA < 0)
          #local State = Inside;
        #else
          #if ((CA = 0 & AB = 0) | (AB = 0 & BC = 0) | (BC = 0 & CA = 0))
            #local State = Vertice;
          #else
            #local State = Edge;
          #end // if
        #end // if
      #end // if
    #end // if
  #end // if
  #debug "Macro RayIntersectsTriangle: "
  #switch (State)
    #case (DegenTri)
      #debug "Degenerate triangle"
    #break
    #case (InPlane)
      #debug "Ray origin lies in triangle plane"
    #break
    #case (Outside)
      #debug "Ray does not hit triangle"
    #break
    #case (Edge)
      #debug "Ray hits an edge of triangle"
    #break
    #case (Vertice)
      #debug "Ray hits a vertice of triangle"
    #break
    #case (Inside)
      #debug "Ray hits inside triangle"
    #break
  #end // switch
  #debug "\n"

  State

#end // macro RayIntersectsTriangle

Post a reply to this message

Christopher James Huff wrote:
> 
> In article <3D2389CA.9E4E78B2@hotmail.com>,
>  Tor Olav Kristensen <tor### [at] hotmailcom> wrote:
> 
> > I think that my RayIntersectsTriangle() macro in the code below
> > provides such a shortcut (*), but I'm not sure yet if it is optimal.
> >
> > (*) Not really for lines, but for rays (which has a defined direction)
> 
> I haven't really been following this conversation, so I might be missing
> something, but wouldn't this be a better way?

Warp explained why I did not make it that way.

I just chose a programming language that many
in these groups know.  ;)

The algorithms I suggested should be quite
easy to see, even if they are provided as POV
scripts.

As a bonus POV-Ray makes it easy to illustrate
the workings of such graphic algorithms.
(Because most people that read these groups
have a common "platform": POV-Ray.)


Tor Olav

Post a reply to this message

"Jim Kress" <nos### [at] kressworkscom> wrote in message
news:3d20b74c$1@news.povray.org...
> > 1. The surface is convex at all vertices.
>
> What exactly do you mean by this?  For example, if you have a kidney
shaped
> surface, which is a closed surface but curves in and out, does that meet
> your assumption?
>
> Jim
>
That's why I suggested a "local" center to base the assumption on (the
centroid of the subset of points within a certain radius of the target
triangle).  Problematic surfaces look more like 3D crescents, the result of
CSG difference of nearly identical spheres, usually separated by a small
translation of the center.  The "interior" surface, created by the cutaway
sphere, would be the real issue.  Kidneys have but a small region that might
be similarly affected.

A better approach is to weight the contribution of the points by their
distance from the centroid of the triangle.  Say you have a list of the
object's vertices V[i] and a triangle <P1, P2, P3> or <I1, I2, I3> if you
are using indexed triangles via mesh2.  First you calculate the triangle
centroid:

#local oTri = (P1+P2+P3)/3; // (V[I1], V[I2], V[I3])/3 if indexed

Then you start adding the weights:

#local wgtTotal = 0;
#local pntTotal = <0,0,0>;
#local i = 0;
#while (i<numPoints)
    #local pntDist = vlength(V[i]-oTri);
    #if (pntDist<wgtThresh)
        #local wgtPoint = pow(pntDist, -wgtPower);
        #local wgtTotal = wgtTotal + wgtPoint;
        #local pntTotal = pntTotal + V[i]*wgtPoint;
    #end
    #local i = i + 1;
#end

#local oLocal = pntTotal/wgtTotal;

Now you can use this local center to check your triangle:

#local triNorm = vcross(P3-P1, P2-P1); // Again, replace Pn with V[In] if
using indexes
#local triDir = vdot(triNorm. P1-oLocal);
#if (triDir>0) true #else false #end

This is a rather computationally expensive process that scales poorly with
object size/vertex density.

Post a reply to this message

On Sat, 29 Jun 2002 23:34:06 -0400, Jim Kress wrote:
>> that comes to mind is: Shoot a ray from the surface of the triangle to one
>> side of it (it doesn't really matter which direction), and if hits an even
>> amount of other triangles (also 0 is even), that side is is outside, else
>> it's inside.
> 
> Got any suggestions how I would do this?  I've looked through the Internet
> and have not been able to find an algorithum (or code) that would show me
> how this is done.

There's an easier way.  Find the vertex V that is closest to an arbitrary
faraway point P ("faraway" is ill-defined here, but 100x the size of the 
bounding box away from any point of the bounding box is probably far enough.)  
Now, find a triangles that abuts the vertex V and is closer to P than the 
other triangles that abut V (put all the other vertices W0..Wn of all the 
other triangles in a pile, pick the closest one of those and call it W.  Now,
you've narrowed it down to two triangles.  Whichever of those has the closest
third vertex is your triangle.)  If the dot-product of that triangle's normal 
with the vector P-V is positive, it's oriented correctly and you can use it 
to fix the orientation of the rest of the triangles as Warp described.  
Otherwise, it's oriented incorrectly and you just need to flip it.

This definitely works in 2d with line segments instead of triangles; I haven't 
checked it in 3d.

-- 
#local R=<7084844682857967,0787982,826975826580>;#macro L(P)concat(#while(P)chr(
mod(P,100)),#local P=P/100;#end"")#end background{rgb 1}text{ttf L(R.x)L(R.y)0,0
translate<-.8,0,-1>}text{ttf L(R.x)L(R.z)0,0translate<-1.6,-.75,-1>}sphere{z/9e3
4/26/2001finish{reflection 1}}//ron.parker@povray.org My opinions, nobody else's

Post a reply to this message

On 10 Jul 2002 17:52:36 -0400, Ron Parker wrote:
> other triangles that abut V (put all the other vertices W0..Wn of all the 
> other triangles in a pile, pick the closest one of those and call it W.  Now,
> you've narrowed it down to two triangles.  Whichever of those has the closest
> third vertex is your triangle.)  If the dot-product of that triangle's normal 

Ron, you ignorant git, you got it all wrong.  The closest triangle is harder
to find than that; you have to scale all the vectors W0-Wn so they fall on a 
unit (hemi)sphere centered on V first, then do the above.


--
#macro R(L P)sphere{L __}cylinder{L P __}#end#macro P(_1)union{R(z+_ z)R(-z _-z)
R(_-z*3_+z)torus{1__ clipped_by{plane{_ 0}}}translate z+_1}#end#macro S(_)9-(_1-
_)*(_1-_)#end#macro Z(_1 _ __)union{P(_)P(-_)R(y-z-1_)translate.1*_1-y*8pigment{
rgb<S(7)S(5)S(3)>}}#if(_1)Z(_1-__,_,__)#end#end Z(10x*-2,.2)camera{rotate x*90}

Post a reply to this message

Thanks Ron.

Got another question for you.  In a triangle mesh, only the x,y,z
coordinates of the verticies are given for each triangle.  How does povray
establish the numbering of the associated verticies?  I need to find a good
way to asign numerical indicies to verticies so I can specify a triangle by
giving its vertex numbers (VRML requires this information).  Any suggestions
how I can do this?

Thanks.

JIm

Post a reply to this message

On Fri, 12 Jul 2002 13:36:46 -0400, Jim Kress wrote:
> Thanks Ron.
> 
> Got another question for you.  In a triangle mesh, only the x,y,z
> coordinates of the verticies are given for each triangle.  How does povray
> establish the numbering of the associated verticies?  I need to find a good
> way to asign numerical indicies to verticies so I can specify a triangle by
> giving its vertex numbers (VRML requires this information).  Any suggestions
> how I can do this?

Well, you could start with a mesh2, which is already in a format like that.
Alternatively, just throw all the vertices in a container that can only 
contain one copy of each data item you put in, and then iterate over its 
members and assign a number to each member.

-- 
#local R=<7084844682857967,0787982,826975826580>;#macro L(P)concat(#while(P)chr(
mod(P,100)),#local P=P/100;#end"")#end background{rgb 1}text{ttf L(R.x)L(R.y)0,0
translate<-.8,0,-1>}text{ttf L(R.x)L(R.z)0,0translate<-1.6,-.75,-1>}sphere{z/9e3
4/26/2001finish{reflection 1}}//ron.parker@povray.org My opinions, nobody else's

Post a reply to this message

Ron Parker <ron### [at] povrayorg> wrote:
> Well, you could start with a mesh2, which is already in a format like that.
> Alternatively, just throw all the vertices in a container that can only 
> contain one copy of each data item you put in, and then iterate over its 
> members and assign a number to each member.

  Btw, doesn't POV-Ray internally use a hash table for this purpose (ie.
a container which can contain only unique elements)? I seem to remember
something like that when I was looking at the code (for the tesselation patch).

  The other (and perhaps more natural) alternative is to use a binary tree
(which should be weighted if average speed of all cases should be the
maximum). However, a binary tree usually takes more memory than a hash table
solution and it's not usually faster (if the hash table is done with expertise,
it's often faster than a binary tree).
  Neither of these containers are trivial to implement (unless an unweighted
binary tree is enough for your purposes, in which case it's the simplest to
implement).

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

Hi Jim -

Another way to accomplish the same task is to run recursively through all of
your adjacent triangles and ensure that the "vertex ordering" of their two
adjacent vertices is the same.  That is, if triangle A is adjacent to
triangle B, and they share vertices v1 and v2, then if v1 comes "before" v2
in the vertex ordering of A, it should be the same for B.  I'd recommend
starting with any triangle in your surface, tweaking the order of the
adjacent triangles so that it matches your start triangle - then continuing
recursively with each of the child triangles.

Note that triangle A being (v1, v2, v3) and triangle B being (v4, v1, v2) is
valid - but triangle B being (v2, v1, v4) wouldn't be, so you'd want to
switch it to (v4, v1, v2).

Once you've oriented all of your triangles the same way, pick any normal
from any triangle in the surface and fire a ray from that triangle out into
the model.  If it intersects with an even number of triangles, it is facing
"out" - if it intersects with an odd number of triangles, it is facing "in".
You only need to do this for one triangle.  I'm assuming your surface has an
"inside" and an "outside", though.

That should solve your problem - not too hard to implement, either.

JP

"Warp" <war### [at] tagpovrayorg> wrote in message
news:3d1cecc2@news.povray.org...
> Jim Kress <kre### [at] kressworkscom> wrote:
> > What I want to do is make sure all triangle normals are pointing out of
the
> > surface and all triangles are wound counter-clockwise.
>
>   Why didn't you say so from the very beginning?
>
>   The problem is not trivial nor necessarily fast to compute, specially
> if you can't trust that the triangles are given all with the same winding.
>
>   The problem makes sense only on closed triangle meshes (if the mesh is
> open, it can't have a well-defined interior). Also each triangle should be
> adjacent (ie. share two vertices) to exactly three other triangles, no
more,
> no less. If these conditions are not met, the problem is not unambiguous
> and thus doesn't necessarily have one unique correct answer (and specially
> if a triangle is not adjacent to exactly three other triangles, but less
> or, heaven forbid, more, all kinds of funny problems will arise when
trying
> to decide which side is which). Another sanity prerequisite: no coincident
> surfaces, thanks.
>
>   If the conditions are met, then the problem is solvable and has a
> unique solution (as your intuition probably tells you).
>
>   First you have to take a triangle and solve which side is facing
> outside the closed mesh and which side is facing inwards.
>   There are probably several algorithms for resolving this, but the one
> that comes to mind is: Shoot a ray from the surface of the triangle to one
> side of it (it doesn't really matter which direction), and if hits an even
> amount of other triangles (also 0 is even), that side is is outside, else
> it's inside.
>   This has to be implemented with extreme care. There's a patological case
> which has to be handled carefully or else the result will be erroneous:
> If the ray hits a triangle exactly in its edge or even in its vertex.
> The problem with this is whether you have to count the other triangle
sharing
> that edge or not: In some cases you should not count it while in other
> cases you must count it! (The two different cases happen when the ray
> goes "through" the surface formed by the two triangles, or when it just
> "touches" the edge formed by the two triangles, but without going through
> it. If the ray goes through a vertex point, the situation is even more
> complicated.)
>   I would say that the easiest way is that if a ray-hits-edge or
> ray-hits-vertex case is detected, then just forget that ray and shoot
> another ray to another direction. (In theory this could lead to an
> infinite loop in an extremely pathological case, but I think that the
> odds for this happening are laughably small.)
>
>   Once you have made sure for this triangle which side is the outside,
> you can change the order of its vertices if necessary.
>   Now the next task is to fix the order of the vertices of all the other
> triangles as well.
>   There are basically two approaches for this: You could repeat the
> raytracing process described above for each triangle, or you could fix
> the other triangles with the help of this one, which you already know for
> sure.
>   The latter method works like this: Since you know the right ordering of
> this triangle, you can know the right order for the three triangles
adjacent
> to it (the two shared vertices in the adjacent triangle should be listed
in
> reverse order than in this triangle; if they aren't, just swap them and
> there you are: it's fixed). Now you can do this process recursively to
> each of the two other triangles adjacent to the three triangles you just
> fixed (you have to ne able to mark triangles as "fixed" so that you know
> where to continue and where to stop).
>   Which one of these two methods is better depends. It's quite clear that
> the raytracing method is much slower than the adjacent-triangle-checking
> method. On the other hand, the latter needs more memory (in pathological
> cases *huge* amounts of memory) because you need to do it recursively.
> (It might be possible to develop a non-recursive, ie. iterative version
> of this algorithm which doesn't take as much memory, but I'm too tired
> to think about that now.)
>
>   All in all, it's not trivial and requires some complicated algorithms.
> You'd be better good at coding. :)
>
> --
> #macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb
M()}}
> N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
> N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  -
Warp -

Post a reply to this message

On Thu, 25 Jul 2002 12:11:36 -0700, John Pallett wrote:
> Another way to accomplish the same task is to run recursively through all of
> your adjacent triangles and ensure that the "vertex ordering" of their two
> adjacent vertices is the same.  

Are you sure you don't have this backwards?

  A--B
  |\ |
  | \|
  C--D

Notice that A-D-C and B-D-A are both clockwise, but the D-A edge is not
represented the same in both triangles.

-- 
#macro R(P)z+_(P)_(P)_(P+1)_(P+1)+z#end#macro Q(C,T)bicubic_patch{type 1u_steps
6v_steps 6R(1)R(3)R(5)R(7)pigment{rgb z}}#end#macro _(Y)#local X=asc(substr(C,Y
,1))-65;<T+mod(X,4)div(X,4)9>-2#end#macro O(T)Q("ABEFUQWS",T)Q("WSXTLOJN",T)#
end O(0)O(3)Q("JNKLCGCD",0)light_source{x 1}// ron### [at] povrayorg

Post a reply to this message

You're right.  Adjust to make sure that all of your orderings are OPPOSITE,
not the same.  Sorry, that was a napkin-scratched solution.

Thanks, Ron.  Jim, hope this helps.

JP

"Ron Parker" <ron### [at] povrayorg> wrote in message
news:slr### [at] fwicom...
> On Thu, 25 Jul 2002 12:11:36 -0700, John Pallett wrote:
> > Another way to accomplish the same task is to run recursively through
all of
> > your adjacent triangles and ensure that the "vertex ordering" of their
two
> > adjacent vertices is the same.
>
> Are you sure you don't have this backwards?
>
>   A--B
>   |\ |
>   | \|
>   C--D
>
> Notice that A-D-C and B-D-A are both clockwise, but the D-A edge is not
> represented the same in both triangles.
>
> --
> #macro R(P)z+_(P)_(P)_(P+1)_(P+1)+z#end#macro Q(C,T)bicubic_patch{type
1u_steps
> 6v_steps 6R(1)R(3)R(5)R(7)pigment{rgb z}}#end#macro _(Y)#local
X=asc(substr(C,Y
> ,1))-65;<T+mod(X,4)div(X,4)9>-2#end#macro
O(T)Q("ABEFUQWS",T)Q("WSXTLOJN",T)#
> end O(0)O(3)Q("JNKLCGCD",0)light_source{x 1}// ron### [at] povrayorg

Post a reply to this message

Exactly how does this solution differ from the one I suggested?

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

<laughing VERY hard> My apologies, Warp - not enough coffee yesterday.  I
re-read your solution and it is exactly the same as the one I proposed.

Well, not exactly.  In your solution, the ray gets fired first - in mine it
gets fired at the end.

Boy, am I embarrased.  :)

JP


"Warp" <war### [at] tagpovrayorg> wrote in message
news:3d4097dc@news.povray.org...
>   Exactly how does this solution differ from the one I suggested?
>
> --
> #macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb
x]
> [1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
> -1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// -
Warp -

Post a reply to this message