Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!ucbvax!agate!usenet From: deadman@garnet.berkeley.edu (Ben Haller) Newsgroups: comp.sys.mac.programmer Subject: Re: Mathematical problems with QuickDraw Message-ID: <1990Oct22.040702.22421@agate.berkeley.edu> Date: 22 Oct 90 04:07:02 GMT References: <1990Oct20.193947.16700@agate.berkeley.edu>, <1990Oct20.233910.28991@nada.kth.se> Sender: usenet@agate.berkeley.edu (USENET Administrator) Organization: Stick Software Lines: 118 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)