> 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