Wiki - README‎ > ‎Programming‎ > ‎

Math Tricks

graph laplacians [link] [arXiv pdf]

Quaternions (link)

Isomap (link) (link)

Fast Approximate Distance Functions (link)
u32 approx_distance( s32 dx, s32 dy )
{
   u32 min, max, approx;

   if ( dx < 0 ) dx = -dx;
   if ( dy < 0 ) dy = -dy;

   if ( dx < dy )
   {
      min = dx;
      max = dy;
   } else {
      min = dy;
      max = dx;
   }

   approx = ( max * 1007 ) + ( min * 441 );
   if ( max < ( min << 4 ))
      approx -= ( max * 40 );

   // add 512 for proper rounding
   return (( approx + 512 ) >> 10 );
}

computationally-stable way to calculate angle between unit vectors (link)
Don't ever use cos^{-1}(u dot v)! If you ever see yourself taking the inverse cosine of a number close to 1 (or -1), you have usually done something bad: at worst, the argument will be slightly > 1 due to floating-point roundoff error, in which case you get a divide-by-zero error; but even if you avoid this by clamping to 1 before taking the inverse cosine, you are still usually throwing away half the bits (or more) that you could have had.

The following works well:
  2*atan2(|u-v|/2, |u+v|/2) = 2*atan2(|u-v|, |u+v|)

however, it ends up requiring more square roots than necessary, so use this instead.
   if (dot(u,v) < 0.)
    return PI - 2 * asin( ||v + u|| / 2 )
  else
    return 2 * asin( ||v - u|| / 2)
aoeu
Comments