Path: chuka.playstation.co.uk!news
From: Craig Graham <cgraham@intelligent-group.com>
Newsgroups: scee.yaroze.programming.3d_graphics
Subject: Re: Rotation, ApplyMatrix Query (fairly long)
Date: Thu, 19 Mar 1998 14:54:43 +0000
Organization: Intelligent Research
Lines: 49
Message-ID: <351131B3.FC7030EB@intelligent-group.com>
References: <34F3EFA2.4CD2@127.0.0.1> <350F949B.93337AA2@immd9.informatik.uni-erlangen.de>
NNTP-Posting-Host: 194.131.235.3
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 4.03 [en] (Win95; I)



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.