"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