# Vertex Ordering

This topic is 5148 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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?

##### Share on other sites
Try using the [ code ] tags. That ASCII art just plain sucks [smile]

##### Share on other sites
Quote:
 Original post by WISMAKHow do I solve this?
Avoid 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.

##### Share on other sites
Quote:
 Original post by WISMAKHow 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.

##### Share on other sites
Isn't GL_POLYGON only supposed to be used for rendering convex polygons anyway?

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
This is the tricky part. How to break it up into triangles?
Anyway, I'll use the glu tesselator routines.

##### Share on other sites
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

##### Share on other sites
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?

1. 1
Rutin
28
2. 2
3. 3
4. 4
5. 5

• 11
• 13
• 11
• 10
• 13
• ### Forum Statistics

• Total Topics
632952
• Total Posts
3009438
• ### Who's Online (See full list)

There are no registered users currently online

×