Megalextoria
Retro computing and gaming, sci-fi books, tv and movies and other geeky stuff.

Home » Archive » fa.info-mac » Quickdraw polygons.
Show: Today's Messages :: Show Polls :: Message Navigator
E-mail to friend 
Switch to threaded view of this topic Create a new topic Submit Reply
Quickdraw polygons. [message #82327] Sat, 08 June 2013 03:54
info-mac is currently offline  info-mac
Messages: 1763
Registered: May 2013
Karma: 0
Senior Member
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
-------
  Switch to threaded view of this topic Create a new topic Submit Reply
Previous Topic: MacPublisher and MacVision (sigh...)
Next Topic: MockWrite Bug
Goto Forum:
  

-=] Back to Top [=-
[ Syndicate this forum (XML) ] [ RSS ] [ PDF ]

Current Time: Thu Mar 28 08:31:28 EDT 2024

Total time taken to generate the page: 0.08204 seconds