Re: GnomeCanvasLine

[Jon Trowbridge <trow emccta com>]

On Wed, May 03, 2000 at 09:24:34PM +0100, Gustavo Joćo Alves Marques Carneiro wrote:
<snip>
> ...which calls the item's point virtual
> function.  This function calculates the distance between the point and
> each of the item's edges, using formulas like 			
> 	dist = sqrt (dx * dx + dy * dy) - width / 2.0;
> 
>   This is very slow; my teacher says we should use something like
> 	dist = dx; if the line's inclination is < 1.0, or
> 	dist = dy; otherwise.

IMHO, your teacher is wrong.  I would guess that, unless you are on
some very brain-damaged hardware, the biggest bottleneck here is the
virtual function call overhead.  (Your sqrt() call doesn't generate a
function call: the compiler should inline it for you).

Of course, if you *really* want to avoid transcendental functions,
there is always the approximation:

if (-epsilon < dx < epsilon) /* epsilon = 1e-8 is always a good choice... */
  dist = dy;
else {
    /* based on taylor expansion of sqrt(1+t^2), which is
     1 + 1/2 t^2 - 1/8 t^4 + ... */
  if (dx > dy) {
    quot = dy/dx;
    mult = dx;
  else {
    quot = dx/dy;
    mult = dy;
  }
  quot *= quot;
  dist = 1 + 0.5 * quot;
  quot *= quot;             /* optional */
  dist -= 0.125 * quot;     /* optional */
  dist *= mult;
}
  dist -= width / 2.0;

(You can omit the steps marked "optional" and still get pretty good
accuracy.  Your error will be O(min(x/y,y/x)^3) rather than
O(min(x/y,y/x)^6).  And beware, I just typed this code it: I didn't
try to compile it or check it...)

but these sorts of machinations shouldn't be necessary on modern
hardware for anything but the most intense numerical computing
problems.

Of course, these things used to be *very* necessary.  I used to use
tricks like this all the time... back before CPUs had build in FPUs.
(I still remember the explosive performance boost I got after
installing an 8087 in my old PC.)  Your teacher is probably a relic of
this era.  Nowadays, code locality is key: actual computation tends to
be very inexpensive relative to memory access.

> This is also very slow. Amazingly, I don't notice it being slow.

If you can't notice it, great --- one less thing to optimize.
Sometimes it is very hard to predict what will be slow and what won't
be.

-JT

-- 
GNU/Linux: Free your mind and your OS will follow.