deadman@garnet.berkeley.edu (Ben Haller) (10/21/90)
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
d88-jwa@dront.nada.kth.se (Jon W{tte) (10/21/90)
In article <1990Oct20.193947.16700@agate.berkeley.edu> deadman@garnet.berkeley.edu (Ben Haller) writes: >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 This ought to be fixed... > Next, there's the problem QuickDraw has with lines. It chooses the pixels >correct, put the "jog" in the middle of the line. It doesn't, it puts it >at one end, like: This argument is also valid. How about some "fixed" math in there ? (Pun intended) > QuickDraw has a strange habit of drawing extra pixels in its circles. It >often gives you circles like: Well, actually they aren't extra. You have to have those "L-shaped" corners to avoid making the circle a hyper-ellipsoid. (Or whatever that translates into in English...) >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? Because they're patented. Simple when you think of it, no ? :-) > 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 This has bugged me as well. Should be fixable, but the "really good" algorithms are, unfortunately, patented... > 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). Here I disagree, the current model suits me JUST FINE ! And, think of it: You want a rectangle 16 dots wide - just draw it from 20 to 36, sizteen dots wide and 36 - 20 == 16. If you used pixel centers, you would have to do it from 20 to 35, not very logical. >I have never suffered from "endpoint paranoia" - it sounds to me like Well, I have (but I've overcome it) I know of lots of experienced programmers who still do. >"SlowDraw" instead... Try doing clipping to an arbitrary shape yourself. See you in 2010 ;-) Now, if the patches for the faults that actually ARE faults don't eat all of the memory I have left when INITs and hungry compilers and debuggers and projects and TechNote stacks and comm programs have taken their toll, I'll consider going religious... h+ h+@nada.kth.se "Moof!(tm)"
deadman@garnet.berkeley.edu (Ben Haller) (10/22/90)
Hallo. In article <1990Oct20.233910.28991@nada.kth.se>, d88-jwa@dront.nada.kth.se (Jon W{tte) (Jon Witte? Watte? I don't know...) writes: > In article <1990Oct20.193947.16700@agate.berkeley.edu>, > deadman@garnet.berkeley.edu (Ben Haller) writes: > >> QuickDraw. First, there's the abominable oval algorithm, which produces >> gaps in ovals that have one long axis and one short axis... > > This ought to be fixed... I imagine they haven't fixed it because they are compatibility-minded, and worry that some program actually *depends* on it working this way. Who knows. >> Next, there's the problem QuickDraw has with lines. It chooses the pixels >> correct, put the "jog" in the middle of the line. It doesn't, it puts it >> at one end, like: > > This argument is also valid. How about some "fixed" math in there ? > (Pun intended) Just in case it wasn't said solely for the pun: fixed math isn't necessary. Integer arithmetic can produce the correct results. >> QuickDraw has a strange habit of drawing extra pixels in its circles. It >> often gives you circles like: > > Well, actually they aren't extra. You have to have those "L-shaped" > corners to avoid making the circle a hyper-ellipsoid. (Or whatever > that translates into in English...) This, I don't get. I don't know what you mean. But what is the error in my argument? Either you fill *all* the pixels that the "mathematically ideal" circle passes through at all, which would result in far too many pixels, or you choose the best possible "minimum" that will still make a solid boundary. Anything inbetween seems inconsistent to me. >> ...Bresenham's circle algorithm (and Pitteway's ellipse algorithm)... >> Why doesn't QuickDraw use them? > > Because they're patented. Simple when you think of it, no ? :-) Simple indeed. But are you sure? This seems very odd to me. First of all, the algorithm is published in most reference books, such as Foley & Van Dam. Second, articles in MacTutor, Dr. Dobbs, Computer Language, etc. use these algorithms all the time with no reference to their being patented. Third, how can a simple, easily derivable formula like Bresenham's algorithm be patented? Any person with a simple calculus background could derive it... Fourth, Bresenham's algorithm was published somewhere around 1950, I think. I thought patents had a time limit of around 25 years (17 for copyrights, I think), so in any case the patnet would be expired, wouldn't it? And who holds the patents? And do they care, or are they permissive about people using the algorithms? Clarification would be very welcome. This is a matter of great interest to me. >> IMHO, the whole thing with..."pixel grid intersections" instead of pixel >> centers is ridiculous. > > Here I disagree, the current model suits me JUST FINE ! And, think of > it: You want a rectangle 16 dots wide - just draw it from 20 to 36, > sizteen dots wide and 36 - 20 == 16. If you used pixel centers, you > would have to do it from 20 to 35, not very logical. Sorry, I'm very used to zero-based counts. If you have an array of ten items in C, you need to index from 0 to 9, not 1 to 10, and *certainly* not from 0 to 10! I think going from 20 to 35 is *very* logical. I have to stop and think about the fact that QuickDraw uses intersections every time I use it. It bugs me like crazy. >>"SlowDraw" instead... > > Try doing clipping to an arbitrary shape yourself. See you in 2010 ;-) Oh, I've hacked region routines before. It's really not that hard. For my program Mandel 2.7, QuickDraw was able to display the graphics the way I wanted it to at a rate of about 1 screenful every few *minutes* (I had to display 1 pixel at a time, as the fractal was calculated). I hacked my own routine to go direct to screen, and it redisplayed in a matter of less than a second. This wasn't the region hack - later, for another program (unfinished and unreleased) called SuperFractal, I converted the routine to clip to the windows visRgn so that DAs, MultiFinder, multiple windows, etc. would still work. It took me about half a day of coding, and was very nearly as fast as the original. I just spent today writing my own region-or and region-and routines with my own internal format, for various reasons. I believe they're bug-free, and it only took me today and a little of yesterday. Is this the kind of thing that was supposed to take me until 2010? I'm really not impressed by anything QuickDraw does. I feel that it could have been made faster, more easy to use, cleaner, more powerful, etc., if Apple just put better programmers on the job. Of course it's too late now, for compatibility reasons. The damage has been done. BTW, in my original posting I mentioned a line routine I wrote that was 9.something times faster than QD in the general case and 11.something times faster in the specific case of a black line (all figures from memory, no flames if I said something else the first time, the original figures are correct). Well, I dug up that program and ran it again to see what 32-Bit QuickDraw had done to things. I guess the last time I ran it was before Andy HertzFeld's QuickerGraf, or else Apple has actually been optimizing behind our backs :->. I am now only 1.1something times faster in the general case, and 1.6something or 1.7something times faster for black lines. Still room for improvement, Apple...and they're executing out of the ROMs, presumably. BTW, if it matters, the more recent test was done on a IIfx running 32-Bit QuickDraw 1.2, and the original test was run on a vanilla II running Color QuickDraw before QuickerGraf. It is quite possible that these figures are not really comparable, since the IIfx is a strange beast, and the caching, NuBus speed, etc. might make a big difference to execution times. The only safe conclusion that can be drawn is that Apple's code is not fully optimized, a shameful state of affairs for one of the most common calls in any graphics library, LineTo. I wonder if anyone really cares about this stuff as much as I do? -Ben Haller (deadman@garnet.berkeley.edu)
miyakekm@mentor.cc.purdue.edu (Keith Miyake) (10/22/90)
In article <1990Oct20.193947.16700@agate.berkeley.edu> deadman@garnet.berkeley.edu (Ben Haller) writes: >Well. Ragging on QuickDraw being one of my favorite pastimes... >[ gaps in ovals ] I agree that this is not the way it should be done. I don't know if I'd call it "mathematically incorrect." It was just a stupid algorithm for them to have chosen. I don't remember where I heard this, but Quickdraw's oval frames are supposed to be the set of points between the ideal oval enclosed by the given rectangle and the ideal oval given by the rectangle inset by the pen width and pen height. Sometimes, this means that there are gaps in the oval. Supposedly, this is a feature, not a bug. >[ doesn't draw lines quite right ] Agreed. > QuickDraw has a strange habit of drawing extra pixels in its circles. Same reason as above. >Why doesn't QuickDraw use them [Bresenham's etc.]? Quickdraw's oval algorithm is based on a different mathematical concept of ideal oval. > IMHO, the whole thing with QuickDraw using "pixel grid intersections" >instead of pixel centers is ridiculous. There are times where it makes more sense than the more common model, and there are times when it makes less sense. >Apple just messed up for no good reason. That what *I* think. Well, I think it's a *little* more complicated than that. But let's just assume you were joking. -Sho