Pseudo angles

thinks · December 22, 2009, 6:31am

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, 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

Dark_Photon · December 22, 2009, 9:42am

Two chained googles reveals:

http://www.ogre3d.org/forums/viewtopic.php?f=2&t=53495

davidotcom:

Hey guys,

I figured it out. Just in case anyone needs it, here’s the algorithm to find pseudo-angles:

/*! Returns the pseudoangle between the line p1 to (infinity, p1.y) and the 
line from p1 to p2. The pseudoangle has the property that the ordering of 
points by true angle anround p1 and ordering of points by pseudoangle are the 
same The result is in the range [0, 4) (or error -1). */

float MathUtil::Pseudoangle(Ogre::Vector2 p1, Ogre::Vector2 p2) {
   Ogre::Vector2 delta = p2 - p1;
   float result;
   
   if ((delta.x == 0) && (delta.y == 0)) {
      return -1;
   } else {
      result = delta.y / (Ogre::Math::Abs(delta.x) + Ogre::Math::Abs(delta.y));
      
      if (delta.x < 0.0) {
         result = 2.0f - result;
      } else {
         result = 4.0f + result;
      }
      
   }
   
   return result;
}

Make sure the vector that’s being passed in is projected on to a plane.

Though despite the header, this appears to return [1,5].