thinks

12-22-2009, 06:31 AM

Consider the problem of having a set of vertices in a plane and trying to sort them according to some criteria. Let this criteria be that the vertices are sorted in CCW order with respect to some view point. I will give the basic idea, because it helps explain:

(1) Compute the average (center) of the vertices by finding the component-wise average. This is done in 2D plane-coordinates.

(2) Now, compute the angle between the center and each vertex. This can be done using atan2(dy, dx), where dx, dy are the signed distance from the vertex to the center.

(3) Sort vertices by angle. Done.

Now, my question is rather simple. In order to avoid the "atan2" function in the above approach, it is possible to use something called "pseudo angles", as described in GPU gems (http://http.developer.nvidia.com/GPUGems/gpugems_ch39.html), Section 39.4.2. However, I cannot seem to find the definition of these pseudo angles anywhere.

If anyone has experience using these I would much appreciate a brief explanation.

Thanks

(1) Compute the average (center) of the vertices by finding the component-wise average. This is done in 2D plane-coordinates.

(2) Now, compute the angle between the center and each vertex. This can be done using atan2(dy, dx), where dx, dy are the signed distance from the vertex to the center.

(3) Sort vertices by angle. Done.

Now, my question is rather simple. In order to avoid the "atan2" function in the above approach, it is possible to use something called "pseudo angles", as described in GPU gems (http://http.developer.nvidia.com/GPUGems/gpugems_ch39.html), Section 39.4.2. However, I cannot seem to find the definition of these pseudo angles anywhere.

If anyone has experience using these I would much appreciate a brief explanation.

Thanks