Polar Function

    We consider again here the  polar functions converting cartesian to planar and spherical polar coordinates. These functions are of vital importance to the games programmer, their computational speed can be crucial.

    Polar2(x,y) = ( tan-1(y/x), (x2 + y2)½) º  (f,r)

    Polar3(x,y,z) = ( cos-1(z(x2 + y2 + z2),  tan-1(y/x), (x2 + y2 + z2)½ )   º  (q,f,r)

    Since Polar3(x,y,z) may be constructed as ( Polar2( Polar2(x,y)2 , z)1, Polar2(x,y)1, Polar2( Polar2(x,y)2 , z)2 ) it is Polar2 that is fundamental.

    (d/dx)Polar2(x,y) = (-y(x2+y2)-1 , x(x2+y2)) = (-r-1 sinf,  cosf)
    (d/dy)Polar2(x,y) = ( x(x2+y2)-1 , y(x2+y2)) = ( r-1 cosf,  sinf)
    (d/dx)2Polar2(x,y) = ( 2xy(x2+y2)-2 , y2(x2+y2)) = ( r-2 sin(2f) , r-1( sinf)2 )
    (d/dy)2Polar2(x,y) = ( -2xy(x2+y2)-2 , x2(x2+y2)) = ( -r-2 sin(2f) , r-1( cosf)2 )
    (d/dx)(d/dy)Polar2(x,y) = ( (y2-x2)(x2+y2)-2 , - xy(x2+y2)-3/2) = -( r-2 cos(2f) , ½r-1 sin(2f) )

    Also note that (d/dx)r2 = 2x ; (d/dy)r2 = 2y ; (d/dx)2 r2 = (d/dy)2 r2 = 2 ; (d/dx)(d/dy) r2 = 0 .
    One can frequently save compuations and simplfy algebra by working with (f,r2) coordinates rather than (f,r).

Euclidean Length
    The  Euclidean length or  magnitude of an N-dimensional vector x is |x| = (åi=1N xi2)½ . This corresponds to our inituitive concept of "length".  It is sometimes known as the  L2 norm.
    The  infinity norm of an N-dimensional vector x is |x|¥ = Max { |xi| 1 £ i £ N}.  It is sometimes known as the  L¥ norm.
    The  Chicago or  Manhattan distance of an N-dimensional vector x is |x|+ = åi=1N |xi|.  It is sometimes known as the  L1 norm.

Approximations to Eulidean Length

    For xÎÂ2 we can approximate |x| by a.xord where xord=(Max( |_x1|, |_x2|), Min( |_x1|, |_x2|) and a is a carefully chosen vector. a=(1,0) gives the infinity norm. a=(1,1) gives the Chicago distance.
a1a2NotesRange of a.x when |x|=1
10| |¥.B5041.0000
11| |+1.00001.6A08
2 cos (p/8)(1+ cos (p/8))-1    a1(Ö2-1)    Optimal    .F5E01.0A20

    For xÎÂ3 we define Mid(x,y,z) = x+y+z - Max(x,y,z) - Min(x,y,z). and approximate |x| by
a.xord where xord=(Max( |_x1|, |_x2|, |_x3|),Mid( |_x1|, |_x2|, |_x3|) ,Min( |_x1|, |_x2|, |_x3|) ).
a1a2a3 NotesRange of a.x when |x|=1
100| |¥.93CC1.0000
111| |+1.00001.BB68
2(1+Ö(9-2(Ö2+Ö6))-1    a1(Ö2-1)    a1(Ö3-Ö2)    Optimal    .F0981.0F68

   a=(15/16,3/8,3/8) is perhaps the best, requiring only a reduced sort and fast multiplies for a euclidean approximator within ± 7.72%.   

    For xÎÂN with N>2, setting sN = åk=1N (2k+1-2(k(k-1))½) we have optimal accuracy attained by a1=2(1+sN½)-1 and ai = a1(i½ - (i-1)½) though at a cost of N general multiplies.
    We often want an estimator that never overestimates (eg. for (rapid range checking) in which case we normalise a by setting a1 = 2sN(1+sN½-1 instead.

Calculating the Polar Angle

    We have written f =  tan-1(y/x) above but this is not strictly true since f for (-x,-y) differs by p from f for (x,y). What we require is the function C irritatingly impliments as _incode[atan2(y,x)] but which we will denote as f(x,y) and can impliment as follows:
    f(x,y) º tan-1(y/x) if x³y> 0 ; ½p-f(x,y)  if y>x>0 ; p-f(-x,y) if x<0 ; 2p-f(x,-y) if y<0 ; p/2 if x=0 y>0 ; -p/2 if x=0, y<0 ; or 0 if x=y=0.
    This approach only requires  tan-1() for values in the range [0,1]   (ie. angles in [0,¼p]) and returns f in [0,2p) rather than (-p,p] . We can attain the latter range by subtracting 2p if f>p.
    Consider F(x,y) º y/x  if x³y> 0 ; ¼-F(x,y)  if y>x>0 ; ½-F(-x,y)  if x<0 ; 1-F(x,-y) if y<0 ; ¼ if x=0 y>0 ; -¼ if x=0, y<0 ; or 0 if x=y=0.
    This provides a value F[x,y] in [0,1] having the same general shape as f(x,y) which we can multipluy by 2p to obtain a crude approximation to f(x,y) perfectly adequate for, say, sorting points by subtended angle as when constructing a convex hull.

Grad of distance functions
    Ñ(Ö(åi=1N xi2)) = x~.
    Ñ(|x|¥) = ei where i : |xi| ³ |xj| 1£j£N.
    Ñ(|x|+) = x-1.

Next : Matrices and Orientations

Glossary   Contents   Author
Copyright (c) Ian C G Bell 1998
Web Source: www.iancgbell.clara.net/maths or www.bigfoot.com/~iancgbell/maths
18 Nov 2006.