Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site uw-beaver
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxb!mhuxn!mhuxm!mhuxj!houxm!vax135!cornell!uw-beaver!info-mac
From: info-mac@uw-beaver
Newsgroups: fa.info-mac
Subject: Quickdraw polygons.
Message-ID: <829@uw-beaver>
Date: Sun, 10-Feb-85 23:40:47 EST
Article-I.D.: uw-beave.829
Posted: Sun Feb 10 23:40:47 1985
Date-Received: Tue, 12-Feb-85 05:36:41 EST
Sender: daemon@uw-beaver
Organization: U of Washington Computer Science
Lines: 122
From: Gustavo Fernandez
Last week, I had a talk with Bill atkinson. The subject of polygons came
up and I asked him what algorithm is used in Quickdraw for polygons. He said
that it was proprietary, telling me that there are two general schemes: a
fast one and a slow one and that he used the fast one. This got me into
wondering what sort of algorithm he DID use.
I first started with MacDraw. Using the Polygon tool, I drue a random poly
and filled it. I noticed two things: 1. The polygon filled from top to
bottom indicating that a run-length encoding scheme was being used. (most
algorithms of this type do.) 2. THe algorithm worked in at least two phases,
only the last of which drew anything. 3. As the polygon got larger, the
algorithm slowed down considerably, but mostly in the setup (non-drawing)
phase.
I then wrote a small LISA PASCAL program that would generate random polygons and fill them. while timing the performance of the fill. Results are shown below.
The program generated N+1 random points anywhere on the Mac screen and called
tickcount on either side of the fillpoly. Results are averaged over five trials
for each value of N.
N Ticks
# lines 60's second
_______ ___________
1 7
2 10
3 11
4 17
5 14
6 20
7 23
8 22
9 24
10 29
11 28
12 31
13 32
14 28
15 39
16 40
17 40
18 42
19 49
20 45
21 51
22 55
23 58
24 65
25 61
26 59
27 61
28 76
29 70
30 80
31 81
32 76
33 75
34 82
35 78
36 90
37 86
38 89
39 96
40 90
>40 BOMB!
This last statistic seemed interesting as there was obviously no limitation
in my own code that would make the routine bomb with either an ID=02 or ID=25
(Address error or memory full error.) These stats were taken on a 128K mac.
I then decided to go into Macsbug and look at what was going on. While I
got hopelessly lost trying to disassemble the fillpolygon routine. (A task
worth doing but requireing much more work) I was rather successful in using
the AT (TRAP) command to see what sorts of calls (to the memory manager)
FILLPOLY was doing.
It turns out that Fillpoly first allocates a handle and grows it several
times using sethandlesize. This handle contains the min and max X coordinates
of each Y coordinate of each line making up the polygon. For example, if
a line stretches from (0,0) to (2,8), the data structure would look like...
0 0 0 2 1 3 1 5 2 6 2 8
Each line appends its values to the run list. On my larger polygons, this
this became a rather substantial data structure. When All the lines are
processed, the entire list is sorted, first by Y, then by X.
For most other drawing packages, this would suffice and a simple horisontal
run drawing routine could be used to draw this structure directly to the
screen. However, since Quickdraw may have to clip the polygon to an arbitrary
region, it first converst the run list to a standard quickdraw region (thus
allocating a handle roughly the same size as the first.) This is a fairly
simple operation as regions are also a run-length encoded data structure
as explained in an INFO-MAC entry last month. Once the region is created,
the run-list is de-allocated and FINALLY, the newly created region can
be drawn using the standard fillregion routines already available.
Note that this is only a highly educated guess at what is going on inside
Quickdraw and I have obviously left out many details. However, a few conclusions
CAN be made.
1. Quickdraw is not optimal for any ONE application, mostly because of its
generality in clipping to regions.
2. Very large temporary data structures can often be produced. However, I
believe that I might have been close to the worst case behavior as I was
using random polygons who's edges were neither horizontal nor vertical
(i.e. not rectangular) and which took up the whole screen.
3. THere is still a question in my mind as to whether it would not be
more efficient to first sort the endpoints and THEN to generate the run-list
on the fly as needed, thus saving lots of memory and cutting down on sort time.
4. It seems as if Quickdraw is isolated from the system. Calls to Newhandle,
GetHandleSize, etc. while made through the normal trap mechanism, are made
through "Glue" routines which seem to do little more than check for a memory
full condition. (Is this necessary if all that ic can do is generate a system
error ID=25?)
I would like to hear from anyone else who has looked at the innards of either
QuickDraw or MacPaint, as there is certainly a lot to be learned there.
Gus Fernandez
-------