Sign in to follow this  

Vertex Ordering

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Quote:
Original post by WISMAK
How 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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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?

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this