Path: chuka.playstation.co.uk!news
From: Christoph Luerig <cpluerig@immd9.informatik.uni-erlangen.de>
Newsgroups: scee.yaroze.programming.3d_graphics
Subject: Re: Rotation, ApplyMatrix Query (fairly long)
Date: Fri, 20 Mar 1998 13:01:29 +0100
Organization: PlayStation Net Yaroze (SCEE)
Lines: 71
Message-ID: <35125A99.CB324946@immd9.informatik.uni-erlangen.de>
References: <34F3EFA2.4CD2@127.0.0.1> <350F949B.93337AA2@immd9.informatik.uni-erlangen.de> <351131B3.FC7030EB@intelligent-group.com>
NNTP-Posting-Host: faui90.informatik.uni-erlangen.de
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 4.04C-SGI [en] (X11; I; IRIX 6.3 IP32)

Hello Craig!

Especially in this case I would not use a finite series approximation, but
a newton method based iteration scheme.
Assume we wnat to calculate d=sqrt(x**2+y**2+z**2), then the iteration
method looks like
dnew=0.5*(dold+(x**2+y**2+z**2)/dold))
In integer coordinates that results in one division, one addition and one
bit shift per iteration. As the distance is computed during an animation,
one can assume, that the distance of the last frame is not too much away
from the distance, that has to be computed in this frame. This means, that
the distance computed for the last frame would make up a good starting
point for the iteration for the actual frame.

You can derive this formula by applying the newton method to the equation
error(d)=d**2-x**2-y**2-z**2=0

Christoph Luerig


Craig Graham wrote:

> Christoph Luerig wrote:
>
> >  Hello Majik!
> >
> > I think the problem is the way you compute the distance between two
> > points. The distance formula you use is the (or Norm mathematical
> > speaking) is
> > the so called L1-norm (d=abs(x)+abs(y)).  But the norm, that reflects
> > the geometric distance is the euclidian norm, which is defined as
> > (d=fsqrt(x**2+y**2)). If you consider one of the values x or y to be
> > zero, both formulas result in the same value, but if one of the values
> > is not zero, and both values are greater than one, the L1-norm always
> > results in a larger value than the euclidian norm. Take for instance
> > x=1 and y=1, in the case the
> > L1-norm results in 2, but the euclidian norm, which represents teh
> > geometric distance (euclidian norm) is 1.414..  This means, that using
> > the L1 norm distances, are overweighted at directions that are not
> > pointed at a right angle.
> >
> >
> > Christoph Luerig
> >
>
> I've got 3 different way's of calculating distance that I generally use
> in my code:
> 1) Integer only calculated Square Root (accurate to nearest whole
> number)
> - fairly slow, but quicker than a floating point square root.
> 2) Integer only lookup table SquareRoot (again, accurate to nearest
> whole numer).
> - faster, but requires a lookup table of length
> sqrt(largest_number_I_want_to_use).
> 3) Manhattan Distance Approximation. A finite series approximation to
> sqrt(X**2+Y**2+Z**2), very fast. Two variations on accuracy (a dead fast
>
> 70% accurate using power of 2 shiftable coeficients, and a slightly
> slower 85% with
> ideal coeficients).
>
> Method 3 is best in a realtime app. I've not got the code with me, but
> if anyone
> is interested I can post the (very simple) function to do the
> calculation........
>
> Craig.