Path: utzoo!attcan!uunet!samsung!zaphod.mps.ohio-state.edu!uwm.edu!bionet!agate!usenet
From: deadman@garnet.berkeley.edu (Ben Haller)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Mathematical problems with QuickDraw
Message-ID: <1990Oct20.193947.16700@agate.berkeley.edu>
Date: 20 Oct 90 19:39:47 GMT
Sender: usenet@agate.berkeley.edu (USENET Administrator)
Organization: Stick Software
Lines: 116

In article <90293.122149CXT105@psuvm.psu.edu>, CXT105@psuvm.psu.edu
(Christopher Tate) writes:

> In article <1990Oct20.044902.11853@agate.berkeley.edu>,
> deadman@garnet.berkeley.edu (Ben Haller) says:
>
> > using QuickDraw.  It's slow, and it produces mathematically incorrect
> > results.                                     ^^^^^^^^^^^^^^ ^^^^^^^^^
>
> Personally, I'm shocked.  The Quickdraw chapter of IM I goes to *SUCH*
> great lengths talking about the mathematical foundation of QuickDraw, and
> now I discover that it's a lot of hoo-haw....
> 
> What are the documented shortcomings of QuickDraw along these lines?  IM
> claims (of course) that if you're careful, you'll never suffer from "end-
> point paranoia" or any such malady, but just what is *really* going wrong
> in there?

Well.  Ragging on QuickDraw being one of my favorite pastimes...
You can see several of these inaccuracies in any drawing program that uses
QuickDraw.  First, there's the abominable oval algorithm, which produces gaps
in ovals that have one long axis and one short axis.  This makes is impossible
to use a "paint can" fill on an oval, as well as looking horrible and being
brain-dead.
  Next, there's the problem QuickDraw has with lines.  It chooses the pixels
for the lines it draws incorrectly.  For example, if you draw a line from
point (100,100) to point (200,201) (note the 201 there), it needs to draw
a diagonal line with one "jog" in it.  It would, if it were mathematically
correct, put the "jog" in the middle of the line.  It doesn't, it puts it
at one end, like:
 *
  *
   *
    *
     **
or a similar configuration.  Very bad.
  QuickDraw has a strange habit of drawing extra pixels in its circles.  It
often gives you circles like:
     ****
   **    **
   *      *
  *        *
  *        *
  *        *
  *        *
   *      *
   **    **
     ****
(The aspect ratio problem with text graphics makes this look weird.  That's
not the point)  The problem is, why the "corner points" (the L-shaped things
on each diagonal portion of the oval)?  An easy answer would be that it's
because the circle passes through all of the points, so they're all filled
in.  But surely, if that's the model, then other points should be filled in
too.  The circle isn't coincidentally passing right through the corners of
pixels elsewhere.  So we *should* get an oval like:
      **
    ******
   **    **
  **      **
  *        *
 **        **
 **        **
  *        *
  **      **
   **    **
    ******
      **
This obviously isn't desirable.  So instead of choosing all points that the
circle goes through sometimes, and choosing only some other times, why not
choose correctly all the time?  Bresenham's circle algorithm (and Pitteway's
ellipse algorithm) choose in this fashion; they make better-looking ovals,
*and* they're the fastest algorithms I know of.  Why doesn't QuickDraw use
them?
  (Sorry if that discussion wasn't clear; without going into an in-depth
discussion of decision algorithms and how to pick which pixels to plot for
a given shape, it might be a little hard to see what I'm complaining
about).
  Let's see, what else...oh yes.  It chooses the pixels for a FillPolygon
in such a way that you can have a "net" of polygons that, mathematically,
share v{rtices and therefore should form a solid "sheet", but when
QuickDraw draws them, pixels show through in gaps between the polygons.  I
discovered this writing a program that draws fractal mountain landscapes.
I would, after much calculation, have a rhombus that was subdivided into
many small triangles, but since the triangles shared all their vertices and
edges, it should have had no gaps in it.  But it did.  This may be unique
to the Polygon fill, or it may also happen with the Polygon frame.  It may
even be attributable to the stupid line algorithm QuickDraw uses, since the
Polygon fill *should* produce the same edges at the line algorithm would
produce, otherwise their mathematical model is not only *wrong*, it's
internally inconsistent...
  What else?  I've never really understood upon what basis QuickDraw decides
where to stretch a bitmap when you CopyBits from one size of rectangle to
another; it seems almost random.  I may not have looked closely enough,
though.
  IMHO, the whole thing with QuickDraw using "pixel grid intersections"
instead of pixel centers is ridiculous.  I don't see what it's supposed to
solve, and it certainly causes some conceptual problems (all your rectangles
must be one pixel larger than they seem like they should be, for example).
I have never suffered from "endpoint paranoia" - it sounds to me like
something a psychiatrist should treat, not something a graphics library
should try to treat.
  Of course, I'm not even going to discuss my usual pet peeve that the name
"QuickDraw" is fundamentally wrong, and the library should be called
"SlowDraw" instead...
  This flame has been made possible by a grant from Doo-Wop She-Bop Inc.
Making fun of big companies for you.  Doo-Wop She-Bop Inc. - we make flames
better.  And to anyone who would defend QuickDraw: just consider, the
correct algorithms have been known and published for years.  The Mac is a
graphics machine.  Why can't it do correct graphics?  It has nothing to do
with speed (the correct algorithms are, coincidentally or not, blindingly
fast), or memory (the correct algorithms require no memory worth mentioning
for simple things like lines and circles).  Apple just messed up for no
good reason.  That what *I* think.

-Ben Haller (deadman@garnet.berkeley.edu)
"Who the caps fits / Let him wear it..." - Shinehead