Subject:
|
Detemining Bad Vertex Sequence
|
Newsgroups:
|
lugnet.cad.dev
|
Date:
|
Wed, 11 Sep 2002 15:20:10 GMT
|
Viewed:
|
314 times
|
| |
|
|
Hi,
I've created a program to automaticaly BFC certify ldraw parts. Before
release this program, I need to make more tests and improve its performace.
Two things that I must fix before trying to certify any part, is correct the
bad vertex sequence of quads and break concave polygons into triangles ( I'm
using a Ray Tracing aproach to determine if the polygons are pointing in or out
of the part, and the intersection of a ray and a concave quad is a little bit
complicated ).
One thing that I would like to ask is:
What is the fastest way to know if the vertexes of a quad are in a bad
sequence?
I've found a algorithm, but I think that you may have better ones.
The algorithm that I'm using is the following:
let's call the vertex of the quad as p1, p2, p3, p4;
lets construct some vectors, joining these points:
v12 = p2 - p1;
v23 = p3 - p2;
v34 = p4 - p3;
v41 = p1 - p4;
Now, we can calculate the cross product of these vectors, this will give us
normals to the plane that contains the vectors. if the vectors are in CCW, the
normal will point out of the plane, otherwise, it will point in:
n1 = v41 x v12;
n2 = v12 x v23;
n3 = v23 x v34;
n4 = v34 x v41;
The last calculation involves a scalar product using these normals, if one
scalar is positive, their normals are pointing to the same region ( in or out
), otherwise, if it's negative, their normals are pointing to different regions.
s1 = n1 . n2;
s2 = n2 . n3;
s3 = n3 . n4;
s4 = n4 . n1;
Finally, we can determine the geometry of the quad:
if ( all scalars are positive )
THEN the polygon is convex and doesn't have a bad vertex sequence.
if ( only one of the scalars is negative and others are positive )
THEN the polygon is concave and doesn't have a bad vertex sequence.
if ( two of the scalars are positive and the others are negative )
THEN the polygon has a bad vertex sequence.
The advantage of this algorithm, is that the vertexes of the quad don't need
to be in the same plane.
The problem is that it is very slow ( lots of cross products and scalar
products ! ).
play well,
zanette.
|
|
Message has 2 Replies:
 | | Re: Detemining Bad Vertex Sequence
|
| (...) I would like to identify if a much simpler program exists... given a red/green render like L3Lab mytest6 can produce and a way to tell which quad/tri goes with which render, let me point at a quad/tri and just reverse the order of the vertices (...) (22 years ago, 12-Sep-02, to lugnet.cad.dev)
|
12 Messages in This Thread:
  
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
