Sign in to follow this  
Shai

ordering a list of 3d vertices in (anti)clockwise order

Recommended Posts

Shai    540
Hi, I have a list of four 3d vertices and was wondering how I could order them in clockwise or anticlockwise order. I considered Graham's scan, but that doesn't work for 3 dimensions. Does anyone have any suggestions on how to do this? It doesn't matter if it isn't very efficient, it just has to produce the correct result. :) Many thanks in advance.

Share this post


Link to post
Share on other sites
Shai    540
If anyone knows a way to check whether a bunch of 3d vertices are ordered (anti)clockwise... I'll settle for that too :).

Share this post


Link to post
Share on other sites
Ashkan    451
Here are some thoughts to warm up the discussion.

First of all, we need a reference frame to compare the vertices against. Without a reference frame to judge your vertices against, there's no way to tell if a set of given vertices are clockwise or counterclockwise. My reasoning is that if you're standing on P1=(10, 10, 10) and I'm standing on P2=(-10, -10, -10) and both of us are judging based on our local frame of reference we will get different results for a triangle that's sitting between us, while we will reach the same verdict if both of us judge based on a common frame of reference like the center of the coordinate system.

So, what's your frame of reference? The camera? The center of the coordinate system?

Share this post


Link to post
Share on other sites
chronos    100
First you'll need to project the vertices onto a 2D plane of your choosing. Once you've done that, determining the order of the projected polygon's vertices is simply a matter of computing the polygon's signed area and taking the sign, as described here.

Share this post


Link to post
Share on other sites
Ashkan    451
Here's a rundown of a solution that I came up with after thinking for an hour or so. Others may come up with better ideas though or may just expand on this and fill the gaps.

What does this solution try to solve? What is the problem?
Given three vertices A, B and C, we want to come up with a mathematical solution that gives the ordering of the resulting triangle in terms of a clockwise (CW) or counterclockwise (CCW) motion.

This solution can be recursively applied to a set of vertices to find the ordering of each one of them. This, I think, is a good method of decomposing the solution to smaller, more manageable parts.

So, how is it done?
A point in 3D space can be thought of as a vector with its head on the center of the coordinate space and its tail located on the point. Not only the position of the vertices, but also the order in which they are given is vital to a correct solution. Given three vertices, A, B and C, given in that specific order, we form two vectors AB and BC. These two vectors are not randomly chosen. Again, their choice is based on the order in which the original vertices are given. We define vector AB = OB - OA, with O being the center of the coordinate system and OO = 0. (a recursive definition)

Next, we compute the cross product of AB and BC, which I just call N. This results in a vector that's perpendicular to both AB and BC. It's also the normal vector of the plane that contains AB and BC since two vectors specify one plane and one plane only. So


N = AB x BC = (OB - OA) x (OC - OB)


Each plane divides space into two subspaces. We denote the one on the side pointed to by the normal to be 'positive'.

Now, if your frame of reference with regard to which you want to judge the ordering (the viewer, the camera, whatever you define it to be) is located on the positive side (i.e. the side that the normal is pointing) the vertices are in CCW order. If, on the other hand, the viewer is on the negative side of the plane, the viewer sees the vertices in a CW ordering.

Hope that helps,
Ashkan

Share this post


Link to post
Share on other sites

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