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