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