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