ordering a list of 3d vertices in (anti)clockwise order
Author
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.
Author
If anyone knows a way to check whether a bunch of 3d vertices are ordered (anti)clockwise... I'll settle for that too :).
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?
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?
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.
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
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
