Vertex Ordering
Author
Hello
A 3D program assumes a clock-wise vertex order for front face in a left-handed system. The problem is when exporting a non-convex polygon, how can the vertex order be determined?
Lets say a polygon of this shape:
2 _
\ \ \ \ \ 3
1 / /
/ /
/ /
//
0
The verts are obtained in this order: 0, 1, 2, 3
if 0, 1, 2 are taken to det cross product and hence the normal
then it will be wrong since the 0, 1, 2 does not reflect the correct order of this polygon, which should be 2, 3, 0, ie.
How do I solve this?
Quote:Original post by WISMAKAvoid using non-convex polygons. Seriously, this is precisely the kind of situation in which they just make things difficult... there are algorithms out there for breaking non-convex polygons down into convex ones.
How do I solve this?
Quote:Original post by WISMAK
How do I solve this?
Several possibilities. Let me quote the algorithm FAQ:
Quote:
Subject 2.07: How do I find the orientation of a simple polygon?
Compute the signed area (Subject 2.01). The orientation is
counter-clockwise if this area is positive.
A slightly faster method is based on the observation that it isn't
necessary to compute the area. Find the lowest vertex (or, if
there is more than one vertex with the same lowest coordinate,
the rightmost of those vertices) and then take the cross product
of the edges fore and aft of it. Both methods are O(n) for n vertices,
but it does seem a waste to add up the total area when a single cross
product (of just the right edges) suffices. Code for this is
available at ftp://cs.smith.edu/pub/code/polyorient.C (2K).
The reason that the lowest, rightmost (or any other such extreme) point
works is that the internal angle at this vertex is necessarily convex,
strictly less than pi (even if there are several equally-lowest points).
Quote:
Subject 2.01: How do I find the area of a polygon?
The signed area can be computed in linear time by a simple sum.
The key formula is this:
If the coordinates of vertex v_i are x_i and y_i,
twice the signed area of a polygon is given by
2 A( P ) = sum_{i=0}^{n-1} (x_i y_{i+1} - y_i x_{i+1}).
Here n is the number of vertices of the polygon, and index
arithmetic is mod n, so that x_n = x_0, etc. A rearrangement
of terms in this equation can save multiplications and operate on
coordinate differences, and so may be both faster and more
accurate:
2 A(P) = sum_{i=1}^{n} ( x_i (y_{i+1} - y_{i-1}) )
References: [O' Rourke (C)] Thm. 1.3.3, p. 21; [Gems II] pp. 5-6:
"The Area of a Simple Polygon", Jon Rokne.
To find the area of a planar polygon not in the x-y plane, use:
2 A(P) = abs(N . (sum_{i=0}^{n-1} (v_i x v_{i+1})))
where N is a unit vector normal to the plane. The `.' represents the
dot product operator, the `x' represents the cross product operator,
and abs() is the absolute value function.
[Gems II] pp. 170-171:
"Area of Planar Polygons and Volume of Polyhedra", Ronald N. Goldman.
The best would be to avoid concave polygons alltogether, as superpig mentioned. This is not always possible, but if used for rendering purposes only, then you should seriously consider triangulating everything.
Author
No nonononononono
Let me reword my problem.
I read polygon information from a 3d program which assumes a clockwise ordering for a front face in a left handed system.
I want to calc a normal for the exported polygon which goes out of the front face. If it's a convex polygon, then I will use any three successive vertices in their order to form the normal.
However, when there is a concave polygon, then how do I pass a three vertices that reflect the correct ordering?
Hope this clarify the problem.
Let me reword my problem.
I read polygon information from a 3d program which assumes a clockwise ordering for a front face in a left handed system.
I want to calc a normal for the exported polygon which goes out of the front face. If it's a convex polygon, then I will use any three successive vertices in their order to form the normal.
However, when there is a concave polygon, then how do I pass a three vertices that reflect the correct ordering?
Hope this clarify the problem.
I'd really recommend that you take that concave polygon with it's clockwise ordering, and break it down into convex polys. Then you can take one of those convex polys and extract the normal from that.
Author
This is the tricky part. How to break it up into triangles?
Anyway, I'll use the glu tesselator routines.
Anyway, I'll use the glu tesselator routines.
hm one way i could think of is
you have 3 vertices a b c
where b is the center of the 2 edges in a concave polygon
if you have a polygon with 12 vertices for example
go from 0->12 and calculate the planes
now take the 2 neighbouring vertices and see if both are either on or infront of the 2 planes of the 2 edges your 3 vertices represent
if one vertex is behind the possible triangle would be outside the polygon
if both are on the plane they where tested against the 3 vertices lie on one line/edge so you could merge them to reduces your triangle resolution
i suggest your paint it down somewhere
once you have make a triangle out of the 3 vertices you need to mark the center vertex of the 2 choosen edges to be skipped for further triangulation otherwise you get overlapping triangles
P.S.: this neat algorithm might not be the best solution and probably has some bugs in it since i wrote it out of the top of my head
you have 3 vertices a b c
where b is the center of the 2 edges in a concave polygon
if you have a polygon with 12 vertices for example
go from 0->12 and calculate the planes
now take the 2 neighbouring vertices and see if both are either on or infront of the 2 planes of the 2 edges your 3 vertices represent
if one vertex is behind the possible triangle would be outside the polygon
if both are on the plane they where tested against the 3 vertices lie on one line/edge so you could merge them to reduces your triangle resolution
i suggest your paint it down somewhere
once you have make a triangle out of the 3 vertices you need to mark the center vertex of the 2 choosen edges to be skipped for further triangulation otherwise you get overlapping triangles
P.S.: this neat algorithm might not be the best solution and probably has some bugs in it since i wrote it out of the top of my head
There are some established algorithms for it. Magic Software might have something.
This is more of a math problem than a graphics problem, though. Would you like me to move the thread to the math forum?
This is more of a math problem than a graphics problem, though. Would you like me to move the thread to the math forum?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement