Howdy, Stranger!
It looks like you're new here. If you want to get involved, click one of these buttons!
Categories
In this Discussion
Code Critique: RoundRects - Apple QuickDraw Source Code
Bill Atkinson was a member of the original Macintosh development team. He created Quickdraw first for the Lisa, as LisaGraf. Andy Hertzfeld, another key member of the team, considers QuickDraw “the single most significant component of the original Macintosh technology” in its ability to “push pixels around in the frame buffer at blinding speeds to create the celebrated user interface.”
The Anecdote
Bill Atkinson worked mostly at home, but whenever he made significant progress he rushed in to Apple to show it off to anyone who would appreciate it. This time, he visited the Macintosh offices at Texaco Towers to show off his brand new oval routines in Quickdraw, which were implemented using a really clever algorithm.
Bill had added new code to QuickDraw (which was still called LisaGraf at this point) to draw circles and ovals very quickly. That was a bit hard to do on the Macintosh, since the math for circles usually involved taking square roots, and the 68000 processor in the Lisa and Macintosh didn't support floating point operations. But Bill had come up with a clever way to do the circle calculation that only used addition and subtraction, not even multiplication or division, which the 68000 could do, but was kind of slow at.
Bill's technique used the fact the sum of a sequence of odd numbers is always the next perfect square (For example, 1 + 3 = 4, 1 + 3 + 5 = 9, 1 + 3 + 5 + 7 = 16, etc). So he could figure out when to bump the dependent coordinate value by iterating in a loop until a threshold was exceeded. This allowed QuickDraw to draw ovals very quickly.
Bill fired up his demo and it quickly filled the Lisa screen with randomly-sized ovals, faster than you thought was possible. But something was bothering Steve Jobs. "Well, circles and ovals are good, but how about drawing rectangles with rounded corners? Can we do that now, too?"
"No, there's no way to do that. In fact it would be really hard to do, and I don't think we really need it". I think Bill was a little miffed that Steve wasn't raving over the fast ovals and still wanted more.
Steve suddenly got more intense. "Rectangles with rounded corners are everywhere! Just look around this room!". And sure enough, there were lots of them, like the whiteboard and some of the desks and tables. Then he pointed out the window. "And look outside, there's even more, practically everywhere you look!". He even persuaded Bill to take a quick walk around the block with him, pointing out every rectangle with rounded corners that he could find.
When Steve and Bill passed a no-parking sign with rounded corners, it did the trick. "OK, I give up", Bill pleaded. "I'll see if it's as hard as I thought." He went back home to work on it.
Bill returned to Texaco Towers the following afternoon, with a big smile on his face. His demo was now drawing rectangles with beautifully rounded corners blisteringly fast, almost at the speed of plain rectangles. When he added the code to LisaGraf, he named the new primitive "RoundRects". Over the next few months, roundrects worked their way into various parts of the user interface, and soon became indispensable.
The Code
Author: Bill Atkinson
Year: 1981
QuickDraw is the Macintosh library for creating bit-mapped graphics, which was used by MacPaint and other applications. It consists of a total of 17,101 lines in 36 files, all written in assembler language for the 68000.
This is the RRects code which contains the functions for the new primitive "RoundRects". We now take these for granted in the Mac and iOS interfaces, but they started out here. I thought it would be interesting to try to deconstruct this code which is extremely tightly written to see if we can see the beginnings of a user interface primitive that has become so iconic (look at your display!). The full code for QuickDraw is here.
.INCLUDE GRAFTYPES.TEXT
;-----------------------------------------------------------
;
;
; **** **** ***** *** ***** ***
; * * * * * * * * * *
; * * * * * * * *
; **** **** *** * * ***
; * * * * * * * *
; * * * * * * * * * *
; * * * * ***** *** * ***
;
;
; procedures for operating on RoundRects.
;
;
.PROC StdRRect,4
.REF CheckPic,DPutPicByte,PutPicVerb,PutPicLong,PutPicRect
.REF PutOval,PushVerb,DrawArc
;---------------------------------------------------------------
;
; PROCEDURE StdRRect(verb: GrafVerb; r: Rect; ovWd,ovHt: INTEGER);
;
; A6 OFFSETS OF PARAMS AFTER LINK:
;
PARAMSIZE .EQU 10
VERB .EQU PARAMSIZE+8-2 ;GRAFVERB
RECT .EQU VERB-4 ;LONG, ADDR OF RECT
OVWD .EQU RECT-2 ;WORD
OVHT .EQU OVWD-2 ;WORD
LINK A6,#0 ;NO LOCALS
MOVEM.L D7/A3-A4,-(SP) ;SAVE REGS
MOVE.B VERB(A6),D7 ;GET VERB
JSR CHECKPIC ;SET UP A4,A3 AND CHECK PICSAVE
BLE.S NOTPIC ;BRANCH IF NOT PICSAVE
MOVE.B D7,-(SP) ;PUSH VERB
JSR PutPicVerb ;PUT ADDIONAL PARAMS TO THEPIC
;
; CHECK FOR NEW OVAL SIZE
;
MOVE.L PICSAVE(A3),A0 ;GET PICSAVE HANDLE
MOVE.L (A0),A0 ;DE-REFERENCE PICSAVE
MOVE.L OVHT(A6),D0 ;GET OVWD AND OVHT
CMP.L PICOVSIZE(A0),D0 ;SAME AS CURRENT OVAL SIZE ?
BEQ.S OVALOK ;YES, CONTINUE
MOVE.L D0,PICOVSIZE(A0) ;NO, UPDATE STATE VARIABLE
MOVE.L D0,-(SP) ;PUSH OVSIZE FOR PutPicLong CALL
MOVEQ #$0B,D0
JSR DPutPicByte ;PUT OVSIZE OPCODE
JSR PutPicLong ;PUT NEW OVAL SIZE DATA
OVALOK MOVEQ #$40,D0 ;PUT RRECT NOUN IN HI NIBBLE
ADD D7,D0 ;PUT VERB IN LO NIBBLE
MOVE.B D0,-(SP) ;PUSH OPCODE
MOVE.L RECT(A6),-(SP) ;PUSH ADDR OF RECT
JSR PutPicRect ;PUT OPCODE AND RECTANGLE
NOTPIC MOVE.L RECT(A6),-(SP) ;PUSH ADDR OF RECT
CLR.B -(SP) ;PUSH HOLLOW = FALSE
TST.B D7 ;IS VERB FRAME ?
BNE.S DOIT ;NO, CONTINUE
TST.L RGNSAVE(A3) ;YES, IS RGNSAVE TRUE ?
BEQ.S NOTRGN ;NO, CONTINUE
MOVE.L RECT(A6),-(SP) ;YES, PUSH ADDR OF RECT
MOVE.L OVHT(A6),-(SP) ;PUSH OVWD, OVHT
MOVE.L RGNBUF(A4),-(SP) ;PUSH RGNBUF
PEA RGNINDEX(A4) ;PUSH VAR RGNINDEX
PEA RGNMAX(A4) ;PUSH VAR RGNMAX
JSR PutOval ;ADD AN OVAL TO THERGN
NOTRGN MOVE.B #1,(SP) ;REPLACE, PUSH HOLLOW = TRUE
DOIT MOVE.L OVHT(A6),-(SP) ;PUSH OVWD,OVHT
JSR PushVerb ;PUSH MODE AND PATTERN
CLR -(SP) ;PUSH STARTANGLE = 0
MOVE #360,-(SP) ;PUSH ARCANGLE = 360
; DrawArc(r,hollow,ovWd,ovHt,mode,pat,startAng,arcAng);
JSR DrawArc
MOVEM.L (SP)+,D7/A3-A4 ;RESTORE REGS
UNLINK PARAMSIZE,'STDRRECT'
.PROC FrameRoundRect,3
.DEF CallRRect,PaintRoundRect,EraseRoundRect
.DEF InvertRoundRect,FillRoundRect
.REF StdRRect
;--------------------------------------------------------
;
; PROCEDURE FrameRoundRect(* r: Rect; ovWd,ovHt: INTEGER *);
;
MOVEQ #FRAME,D0 ;VERB = FRAME
BRA.S CallRRect ;SHARE COMMON CODE
;--------------------------------------------------------
;
; PROCEDURE PaintRoundRect(* r: Rect; ovWd,ovHt: INTEGER *);
;
PaintRoundRect
MOVEQ #PAINT,D0 ;VERB = PAINT
BRA.S CallRRect ;SHARE COMMON CODE
;--------------------------------------------------------
;
; PROCEDURE EraseRoundRect(* r: Rect; ovWd,ovHt: INTEGER *);
;
EraseRoundRect
MOVEQ #ERASE,D0 ;VERB = ERASE
BRA.S CallRRect ;SHARE COMMON CODE
;--------------------------------------------------------
;
; PROCEDURE InvertRoundRect(* r: Rect; ovWd,ovHt: INTEGER *);
;
InvertRoundRect
MOVEQ #INVERT,D0 ;VERB = INVERT
BRA.S CallRRect ;SHARE COMMON CODE
;--------------------------------------------------------
;
; PROCEDURE FillRoundRect(r: Rect; ovWd,ovHt: INTEGER; pat: Pattern);
;
FillRoundRect
MOVE.L (SP)+,A0 ;POP RETURN ADDR
MOVE.L (SP)+,A1 ;POP ADDR OF PATTERN
MOVE.L A0,-(SP) ;PUT RETURN ADDR BACK
MOVE.L GRAFGLOBALS(A5),A0 ;POINT TO LISAGRAF GLOBALS
MOVE.L THEPORT(A0),A0 ;GET CURRENT GRAFPORT
LEA FILLPAT(A0),A0 ;POINT TO FILLPAT
MOVE.L (A1)+,(A0)+ ;COPY PAT INTO FILLPAT
MOVE.L (A1)+,(A0)+ ;ALL EIGHT BYTES
MOVEQ #FILL,D0 ;VERB = FILL
BRA.S CallRRect ;SHARE COMMON CODE
;---------------------------------------------------------------
;
; PROCEDURE CallRRect(r: Rect; ovWd,ovHt: INTEGER);
;
; code shared by FrameRoundRect, PaintRoundRect, EraseRoundRect,
; InvertRoundRect, and FillRoundRect.
; enter with verb in D0.
;
CallRRect
MOVE.L (SP)+,A0 ;POP RETURN ADDR
MOVE.L (SP)+,D1 ;POP ovWd and ovHt
MOVE.L (SP)+,A1 ;POP ADDR OF RECT
MOVE.B D0,-(SP) ;PUSH VERB
MOVE.L A1,-(SP) ;PUSH ADDR OF RECT
MOVE.L D1,-(SP) ;PUSH ovWd and ovHt
MOVE.L A0,-(SP) ;RESTORE RETURN ADDR
MOVE.L GRAFGLOBALS(A5),A0 ;POINT TO LISAGRAF GLOBALS
MOVE.L THEPORT(A0),A0 ;GET CURRENT GRAFPORT
MOVE.L GRAFPROCS(A0),D0 ;IS GRAFPROCS NIL ?
LEA STDRRECT,A0
BEQ.S USESTD ;YES, USE STD PROC
MOVE.L D0,A0
MOVE.L RRECTPROC(A0),A0 ;NO, GET PROC PTR
USESTD JMP (A0) ;GO TO IT
.END
Comments
(From the Inside Macintosh: Imaging With QuickDraw, Chapter 3 - QuickDraw Drawing / QuickDraw Drawing Reference)
Drawing Rounded Rectangles
As with rectangles, QuickDraw provides routines with which you can frame, paint, fill, erase, and invert rounded rectangles. Rounded rectangles are rectangles with rounded corners defined by the width and height of the ovals forming their corners.
You can use the FrameRoundRect procedure to draw an outline of a rounded rectangle with the size, pattern, and pattern mode of the graphics pen. You can use the PaintRoundRect procedure to draw a rounded rectangle's interior with the pattern of the graphics pen, using the pattern mode of the graphics pen.
Using the FillRoundRect procedure, you can draw a rounded rectangle's interior with any pattern you specify. The procedure transfers the pattern with the patCopy pattern mode, which directly copies your requested pattern into the shape.
You can use the EraseRoundRect procedure to erase a rounded rectangle; this procedure fills the rectangle's interior with the background pattern for the current graphics port.
You can use the InvertRoundRect procedure to invert a rounded rectangle; this procedure reverses the colors of all pixels within the rounded rectangle. Although this procedure operates on color pixels in color graphics ports, the results are predictable only with 1-bit and direct color pixels.
When using these procedures, you specify a rectangle, which is defined by a data structure of type Rect. You must also specify the width and height of the ovals that describe the curvature of the rounded corners
(From the Inside Macintosh: Imaging With QuickDraw, Chapter 3 - QuickDraw Drawing / QuickDraw Drawing Reference)
FrameRoundRect
To draw an outline inside a rounded rectangle, use the FrameRoundRect procedure.
The rectangle that defines the rounded rectangle's boundaries.
The width of the oval defining the rounded corner.
The height of the oval defining the rounded corner.
DESCRIPTION
Using the pattern, pattern mode, and size of the graphics pen for the current graphics port, the FrameRoundRect procedure draws an outline just inside the rounded rectangle bounded by the rectangle that you specify in the r parameter. The outline is as wide as the pen width and as tall as the pen height. The pen location does not change.
Use the ovalWidth and ovalHeight parameters to specify the diameters of curvature for the corners of the rounded rectangle.
If a region is open and being formed, the outside outline of the new rounded rectangle is mathematically added to the region's boundary.
SPECIAL CONSIDERATIONS
The FrameRoundRect procedure may move or purge memory blocks in the application heap. Your application should not call this procedure at interrupt time.
(From the Inside Macintosh: Imaging With QuickDraw, Chapter 3 - QuickDraw Drawing / QuickDraw Drawing Reference)
PaintRoundRect
To paint a rounded rectangle with the graphics pen's pattern and pattern mode, use the PaintRoundRect procedure.
The rectangle that defines the rounded rectangle's boundaries.
The width of the oval defining the rounded corner.
The height of the oval defining the rounded corner.
DESCRIPTION
Using the pattern and pattern mode of the graphics pen for the current graphics port, the PaintRoundRect procedure draws the interior of the rounded rectangle bounded by the rectangle that you specify in the r parameter. Use the ovalWidth and ovalHeight parameters to specify the diameters of curvature for the corners of the rounded rectangle.
The pen location does not change.
SPECIAL CONSIDERATIONS
The PaintRoundRect procedure may move or purge memory blocks in the application heap. Your application should not call this procedure at interrupt time.
SEE ALSO
You can use the FillRoundRect procedure, described next, to draw the interior of a rounded rectangle with a pen pattern different from that for the current graphics port.
From Programming Primer for the Macintosh®, Volume 1 By John M. May, Judy Whittle
< DIGRESSION >
Apparently since iOS 7, Apple has moved away from RoundRects to the squircle which is the mathematical intermediate of a square and a circle.
Architect Peter Panholzer coined the term “squircle” in the summer of 1966 while working for Gerald Robinson. Robinson had seen a Scientific American article on the superellipse shape popularized by Piet Hein and suggested Panholzer use the shape in a project.
Piet Hein used the term superellipse for a compromise between an ellipse and a rectangle, and the term “supercircle” for the special case of axes of equal length. While Piet Hein popularized the superellipse shape, the discovery of the shape goes back to Gabriel Lamé in 1818.
According to Gabriel Lamé, the Superellipse follows the modified formular for the ellipse, (x/a)n + (y/b)n = 1, where the power of 2 is increased to a higher number. Piet Hein used an arbitrary relatively low exponent n of 2.6 for his urban design pattern. Peter asked himself, why should one be eyeballing the resulting shape for aesthetic or practical effect. Simplifying the problem he settled on the special case of a circle instead of an ellipse (which Piet Hein also did and dubbed a Supercircle). The circle is defined by the formula x2 + y2 =1, a special case of the more general formula |x|n + |y|n = 1, where n may rise from 2 to any higher number.
As n converges to infinity ∞, the circle converges to a square. In order to find the aesthetic middle between a circle and a square, Panholzer posed the question: at which ideal n in the formula |x|n + |y|n =1 does the resulting Squircle reache a stage such that one cannot decide, if the resulting “ideal” Squircle is visually closer to a circle or a square.
So a “squircle” is a sort of compromise between a square and circle, but one that differs from a square with rounded corners. It’s a shape you’ll see, for example, in some of Apple’s more recent designs.
</ DIGRESSION >
In the Processing community forums there have been a long-running set of conversations about how to implement rounded rects and/or squircles, and the differences between the two.
Processing `rect(x, y, w, h,
In Processing,
rect()supports three signatures:The first is a normal rectangle, the second is a rounded rect with a corner raidius
r-- and the third defines a different radius (or 0) for each of the four corners.Internally, the rounded rect implementation is using quadratic Bezier curves:
Most users don't seem to care specifically how the curved portion is created -- as an ellipse, a bezier curve, or a circular section -- because performance is not an issue, and the various results all seem rounded. That is, until they attempt to animate a square turning into a circle and back using the rounded rect implementation, and they discover that four bezier sections don't make a circle, they make an awkward looking... bezircle.
This leads in two directions -- either towards a rounding process that culminates in a circular shape, or towards a morph process that bows out the sides towards a circular shape while keeping the corner point locations fixed.
The conversation keeps coming back -- for example, I recently saw another version of it asking about the limitations rounded rects in JavaScript + WebGL (vs Java + OpenGL). Solutions are invented, but problems don't necessarily stay solved -- they keep needing to be re-solved.