On Sat, 29 Jun 2002 23:34:06 -0400, Jim Kress wrote:
>> 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.

There's an easier way.  Find the vertex V that is closest to an arbitrary
faraway point P ("faraway" is ill-defined here, but 100x the size of the 
bounding box away from any point of the bounding box is probably far enough.)  
Now, find a triangles that abuts the vertex V and is closer to P than the 
other triangles that abut V (put all the other vertices W0..Wn of all the 
other triangles in a pile, pick the closest one of those and call it W.  Now,
you've narrowed it down to two triangles.  Whichever of those has the closest
third vertex is your triangle.)  If the dot-product of that triangle's normal 
with the vector P-V is positive, it's oriented correctly and you can use it 
to fix the orientation of the rest of the triangles as Warp described.  
Otherwise, it's oriented incorrectly and you just need to flip it.

This definitely works in 2d with line segments instead of triangles; I haven't 
checked it in 3d.

-- 
#local R=<7084844682857967,0787982,826975826580>;#macro L(P)concat(#while(P)chr(
mod(P,100)),#local P=P/100;#end"")#end background{rgb 1}text{ttf L(R.x)L(R.y)0,0
translate<-.8,0,-1>}text{ttf L(R.x)L(R.z)0,0translate<-1.6,-.75,-1>}sphere{z/9e3
4/26/2001finish{reflection 1}}//ron.parker@povray.org My opinions, nobody else's

Post a reply to this message

On 10 Jul 2002 17:52:36 -0400, Ron Parker wrote:
> other triangles that abut V (put all the other vertices W0..Wn of all the 
> other triangles in a pile, pick the closest one of those and call it W.  Now,
> you've narrowed it down to two triangles.  Whichever of those has the closest
> third vertex is your triangle.)  If the dot-product of that triangle's normal 

Ron, you ignorant git, you got it all wrong.  The closest triangle is harder
to find than that; you have to scale all the vectors W0-Wn so they fall on a 
unit (hemi)sphere centered on V first, then do the above.


--
#macro R(L P)sphere{L __}cylinder{L P __}#end#macro P(_1)union{R(z+_ z)R(-z _-z)
R(_-z*3_+z)torus{1__ clipped_by{plane{_ 0}}}translate z+_1}#end#macro S(_)9-(_1-
_)*(_1-_)#end#macro Z(_1 _ __)union{P(_)P(-_)R(y-z-1_)translate.1*_1-y*8pigment{
rgb<S(7)S(5)S(3)>}}#if(_1)Z(_1-__,_,__)#end#end Z(10x*-2,.2)camera{rotate x*90}

Post a reply to this message

Thanks Ron.

Got another question for you.  In a triangle mesh, only the x,y,z
coordinates of the verticies are given for each triangle.  How does povray
establish the numbering of the associated verticies?  I need to find a good
way to asign numerical indicies to verticies so I can specify a triangle by
giving its vertex numbers (VRML requires this information).  Any suggestions
how I can do this?

Thanks.

JIm

Post a reply to this message

On Fri, 12 Jul 2002 13:36:46 -0400, Jim Kress wrote:
> Thanks Ron.
> 
> Got another question for you.  In a triangle mesh, only the x,y,z
> coordinates of the verticies are given for each triangle.  How does povray
> establish the numbering of the associated verticies?  I need to find a good
> way to asign numerical indicies to verticies so I can specify a triangle by
> giving its vertex numbers (VRML requires this information).  Any suggestions
> how I can do this?

Well, you could start with a mesh2, which is already in a format like that.
Alternatively, just throw all the vertices in a container that can only 
contain one copy of each data item you put in, and then iterate over its 
members and assign a number to each member.

-- 
#local R=<7084844682857967,0787982,826975826580>;#macro L(P)concat(#while(P)chr(
mod(P,100)),#local P=P/100;#end"")#end background{rgb 1}text{ttf L(R.x)L(R.y)0,0
translate<-.8,0,-1>}text{ttf L(R.x)L(R.z)0,0translate<-1.6,-.75,-1>}sphere{z/9e3
4/26/2001finish{reflection 1}}//ron.parker@povray.org My opinions, nobody else's

Post a reply to this message

Ron Parker <ron### [at] povrayorg> wrote:
> Well, you could start with a mesh2, which is already in a format like that.
> Alternatively, just throw all the vertices in a container that can only 
> contain one copy of each data item you put in, and then iterate over its 
> members and assign a number to each member.

  Btw, doesn't POV-Ray internally use a hash table for this purpose (ie.
a container which can contain only unique elements)? I seem to remember
something like that when I was looking at the code (for the tesselation patch).

  The other (and perhaps more natural) alternative is to use a binary tree
(which should be weighted if average speed of all cases should be the
maximum). However, a binary tree usually takes more memory than a hash table
solution and it's not usually faster (if the hash table is done with expertise,
it's often faster than a binary tree).
  Neither of these containers are trivial to implement (unless an unweighted
binary tree is enough for your purposes, in which case it's the simplest to
implement).

-- 
#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

Hi Jim -

Another way to accomplish the same task is to run recursively through all of
your adjacent triangles and ensure that the "vertex ordering" of their two
adjacent vertices is the same.  That is, if triangle A is adjacent to
triangle B, and they share vertices v1 and v2, then if v1 comes "before" v2
in the vertex ordering of A, it should be the same for B.  I'd recommend
starting with any triangle in your surface, tweaking the order of the
adjacent triangles so that it matches your start triangle - then continuing
recursively with each of the child triangles.

Note that triangle A being (v1, v2, v3) and triangle B being (v4, v1, v2) is
valid - but triangle B being (v2, v1, v4) wouldn't be, so you'd want to
switch it to (v4, v1, v2).

Once you've oriented all of your triangles the same way, pick any normal
from any triangle in the surface and fire a ray from that triangle out into
the model.  If it intersects with an even number of triangles, it is facing
"out" - if it intersects with an odd number of triangles, it is facing "in".
You only need to do this for one triangle.  I'm assuming your surface has an
"inside" and an "outside", though.

That should solve your problem - not too hard to implement, either.

JP

"Warp" <war### [at] tagpovrayorg> wrote in message
news:3d1cecc2@news.povray.org...
> 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

On Thu, 25 Jul 2002 12:11:36 -0700, John Pallett wrote:
> Another way to accomplish the same task is to run recursively through all of
> your adjacent triangles and ensure that the "vertex ordering" of their two
> adjacent vertices is the same.  

Are you sure you don't have this backwards?

  A--B
  |\ |
  | \|
  C--D

Notice that A-D-C and B-D-A are both clockwise, but the D-A edge is not
represented the same in both triangles.

-- 
#macro R(P)z+_(P)_(P)_(P+1)_(P+1)+z#end#macro Q(C,T)bicubic_patch{type 1u_steps
6v_steps 6R(1)R(3)R(5)R(7)pigment{rgb z}}#end#macro _(Y)#local X=asc(substr(C,Y
,1))-65;<T+mod(X,4)div(X,4)9>-2#end#macro O(T)Q("ABEFUQWS",T)Q("WSXTLOJN",T)#
end O(0)O(3)Q("JNKLCGCD",0)light_source{x 1}// ron### [at] povrayorg

Post a reply to this message

You're right.  Adjust to make sure that all of your orderings are OPPOSITE,
not the same.  Sorry, that was a napkin-scratched solution.

Thanks, Ron.  Jim, hope this helps.

JP

"Ron Parker" <ron### [at] povrayorg> wrote in message
news:slr### [at] fwicom...
> On Thu, 25 Jul 2002 12:11:36 -0700, John Pallett wrote:
> > Another way to accomplish the same task is to run recursively through
all of
> > your adjacent triangles and ensure that the "vertex ordering" of their
two
> > adjacent vertices is the same.
>
> Are you sure you don't have this backwards?
>
>   A--B
>   |\ |
>   | \|
>   C--D
>
> Notice that A-D-C and B-D-A are both clockwise, but the D-A edge is not
> represented the same in both triangles.
>
> --
> #macro R(P)z+_(P)_(P)_(P+1)_(P+1)+z#end#macro Q(C,T)bicubic_patch{type
1u_steps
> 6v_steps 6R(1)R(3)R(5)R(7)pigment{rgb z}}#end#macro _(Y)#local
X=asc(substr(C,Y
> ,1))-65;<T+mod(X,4)div(X,4)9>-2#end#macro
O(T)Q("ABEFUQWS",T)Q("WSXTLOJN",T)#
> end O(0)O(3)Q("JNKLCGCD",0)light_source{x 1}// ron### [at] povrayorg

Post a reply to this message

Exactly how does this solution differ from the one I suggested?

-- 
#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

<laughing VERY hard> My apologies, Warp - not enough coffee yesterday.  I
re-read your solution and it is exactly the same as the one I proposed.

Well, not exactly.  In your solution, the ray gets fired first - in mine it
gets fired at the end.

Boy, am I embarrased.  :)

JP


"Warp" <war### [at] tagpovrayorg> wrote in message
news:3d4097dc@news.povray.org...
>   Exactly how does this solution differ from the one I suggested?
>
> --
> #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