TweetFollow Us on Twitter

Bezier Curve
Volume Number:5
Issue Number:1
Column Tag:C Workshop

Related Info: Quickdraw

Bezier Curve Ahead!

By David W. Smith, Los Gatos, CA

Note: Source code files accompanying article are located on MacTech CD-ROM or source code disks.

David W. Smith (no known relation to the Editor) is a Sr. Software Engineer at ACM Research, Inc., in Los Gatos.

There comes a time in the development of some applications when arcs and wedges just don’t cut the mustard. You want to draw a pretty curve from point A to point B, and QuickDraw isn’t giving you any help. It seems like a good time to reach for a computer graphics text, blow the dust off of your college math, and try to decipher their explanation of splines. Stop. All is not lost. The Bezier curve may be just what you need.

Bezier Curves

Bezier curves (pronounced “bez-yeah”, after their inventor, a French mathematician) are well suited to graphics applications on the Macintosh for a number of reasons. First, they’re simple to describe. A curve is a function of four points. Second, the curve is efficient to calculate. From a precomputed table, the segments of the curve can be produced using only fixed-point multiplication. No trig, no messy quadratics, and no inSANEity. Third, and, to some, the most important, the Bezier curve is directly supported by the PostScript curve and curveto operators, and is one of the components of PostScript’s outlined fonts. The Bezier curve is also one of the principle drawing elements of Adobe Illustrator™. (Recently, they’ve shown up in a number of other places.)

Bezier curves have some interesting properties. Unlike some other classes of curves, they can fold over on themselves. They can also be joined together to form smooth (continuous) shapes. Figure 1 shows a few Bezier curves, including two that are joined to form a smooth shape.

The Gruesome Details

The description of Bezier curves below is going to get a bit technical. If you’re not comfortable with the math, you can trust that the algorithm works, and skip ahead to the implementation. However, if you’re curious about how the curves work and how to optimize their implementation, or just don’t trust using code that you don’t understand, read on.

The Bezier curve is a parametric function of four points; two endpoints and two “control” points. The curve connects the endpoints, but doesn’t necessarily touch the control points. The general form Bezier equation, which describes each point on the curve as a function of time, is:

where P1 and P4 are the endpoints, P2 and P3 are the control points, and the wn’s are weighting functions, which blend the four points to produce the curve. (The weights are applied to the h and v components of each point independently.) The single parameter t represents time, and varies from 0 to 1. The full form of the Bezier curve is:

We know that the curve touches each endpoint, so it isn’t too surprising that at t=0 the first weighting function is 1 and all others are 0 (i.e., the initial point on the curve is the first endpoint). Likewise, at t=1, the fourth weighting function is 1 and the rest are 0. However, it’s what happens between 0 and 1 that’s really interesting. A quick side-trip into calculus to take some first derivatives tells us that the second weighting function is maximized (has its greatest impact on the curve) at t=1/3, and the third weight is maximized at t=2/3. But the clever part--the bit that the graphics books don’t bother to mention--run the curve backwards by solving the equation for 1-t, and you find that w1(t)=w4(1-t) and w2(t)=w3(1-t). As we’ll see below, this symmetry halves the effort needed to compute values for the weights.

Figure 1. Some Beizer Curves and Shapes

Implementing Bezier Curves

One strategy for implementing Bezier curves is to divide the curve into a fixed number of segments and then to pre-compute the values of the weighting functions for each of the segments. The greater the number of segments, the smoother the curve. (I’ve found that 16 works well for display purposes, but 32 is better for hardcopy.) Computing any given curve becomes a simple matter of using the four points and the precomputed weights to produce the end-points of the curve segments. Fixed-point math yields reasonable accuracy, and is a hands down winner over SANE on the older (pre-Mac II) Macs, so we’ll use it.

We can optimize the process a bit. The curve touches each endpoint, so we can assume weights of 0 or 1 and needn’t compute weights for these points. Another optimization saves both time and space. By taking advantage of the symmetric nature of the Bezier equation, we can compute arrays of values for the first two of the weighting functions, and obtain values for the other two weights by indexing backwards into the arrays.

Drawing the curve, given the endpoints of the segments, is the duty of QuickDraw (or of PostScript, if you’re really hacking).

The listing below shows a reasonably efficient implementation of Bezier curves in Lightspeed C™. A few reminders about fixed-point math: an integer times a fixed-point number yields a fixed-point number, and a fixed by fixed multiplication uses a trap. The storage requirement for the algorithm, assuming 16 segments, (32 fixed-point values), is around 32*4*4, or 512 bytes. The algorithm computes all of the segments before drawing them so that the drawing can be done at full speed. (Having all of the segments around at one time can be useful for other reasons.)

More Fun With Curves

Given an implementation for Bezier curves, there are some neat things that fall out for almost free. Drawing a set of joined curves within an OpenPoly/ClosePoly or an OpenRgn/CloseRgn envelope yields an object that can be filled with a pattern. (Shades of popular illustration packages?) For that matter, lines, arcs, wedges, and Bezier curves can be joined to produce complicated shapes, such as outlined fonts. Given the direct mapping to PostScript’s curve and curveto operators, Bezier curves are a natural for taking better advantage of the LaserWriter.

As mentioned above, Bezier curves can be joined smoothly to produce more complicated shapes (see figure 1). The catch is that the point at which two curves are joined, and the adjacent control points, must be colinear (i.e., the three points must lay on a line). If you take a close look at Adobe Illustrator’s drawing tool, you’ll see what this means.

One nonobvious use of Bezier curves is in animation. The endpoints of the segments can be used as anchor-points for redrawing an object, giving it the effect of moving smoothly along the curve. One backgammon program that I’ve seen moves the tiles along invisible Bezier curves, and the effect is very impressive. For animation, you would probably want to vary the number of segments. Fortunately, the algorithm below is easily rewritten to produce the nth segment of an m segment curve given the the end and control points.

Further Optimizations

If you’re really tight on space or pressed for speed, there are a few things that you can do to tighten up the algorithm. A bit of code space (and a negligible amount of time) can be preserved by eliminating the setup code in favor of statically initializing the weight arrays with precomputed constant values. Drawing can be optimized by using GetTrapAddress to find the address in ROM of lineto, and then by calling it directly from inline assembly language, bypassing the trap mechanism. I’ve found that neither optimization is necessary for reasonable performance.

/*
**  Bezier  --  Support for Bezier curves
** Herein reside support routines for drawing Bezier curves.
**  Copyright (C) 1987, 1988 David W. Smith
**  Submitted to MacTutor for their source-disk.
*/

#include <MacTypes.h>
/*
   The greater the number of curve segments, the smoother the curve, 
and the longer it takes to generate and draw.  The number below was pulled 
out of a hat, and seems to work o.k.
 */
#define SEGMENTS 16

static Fixedweight1[SEGMENTS + 1];
static Fixedweight2[SEGMENTS + 1];

#define w1(s)  weight1[s]
#define w2(s)  weight2[s]
#define w3(s)  weight2[SEGMENTS - s]
#define w4(s)  weight1[SEGMENTS - s]

/*
 *  SetupBezier  --  one-time setup code.
 * Compute the weights for the Bezier function.
 *  For the those concerned with space, the tables can be precomputed. 
Setup is done here for purposes of illustration.
 */
void
SetupBezier()
{
 Fixed  t, zero, one;
 int    s;

 zero  = FixRatio(0, 1);
 one   = FixRatio(1, 1);
 weight1[0] = one;
 weight2[0] = zero;
 for ( s = 1 ; s < SEGMENTS ; ++s ) {
 t = FixRatio(s, SEGMENTS);
 weight1[s] = FixMul(one - t, FixMul(one - t, one - t));
 weight2[s] = 3 * FixMul(t, FixMul(t - one, t - one));
 }
 weight1[SEGMENTS] = zero;
 weight2[SEGMENTS] = zero;
}

/*
 *  computeSegments  --  compute segments for the Bezier curve
 * Compute the segments along the curve.
 *  The curve touches the endpoints, so don’t bother to compute them.
 */
static void
computeSegments(p1, p2, p3, p4, segment)
 Point  p1, p2, p3, p4;
 Point  segment[];
{
 int    s;
 
 segment[0] = p1;
 for ( s = 1 ; s < SEGMENTS ; ++s ) {
 segment[s].v = FixRound(w1(s) * p1.v + w2(s) * p2.v +
 w3(s) * p3.v + w4(s) * p4.v);
 segment[s].h = FixRound(w1(s) * p1.h + w2(s) * p2.h +
 w3(s) * p3.h + w4(s) * p4.h);
 }
 segment[SEGMENTS] = p4;
}

/*
 *  BezierCurve  --  Draw a Bezier Curve
 * Draw a curve with the given endpoints (p1, p4), and the given 
 * control points (p2, p3).
 *  Note that we make no assumptions about pen or pen mode.
 */
void
BezierCurve(p1, p2, p3, p4)
 Point  p1, p2, p3, p4;
{
 int    s;
 Point  segment[SEGMENTS + 1];

 computeSegments(p1, p2, p3, p4, segment);
 MoveTo(segment[0].h, segment[0].v);

 for ( s = 1 ; s <= SEGMENTS ; ++s ) {
 if ( segment[s].h != segment[s - 1].h ||
  segment[s].v != segment[s - 1].v ) {
 LineTo(segment[s].h, segment[s].v);
 }
 }
}

/*
**  CurveLayer.c  
** These routines provide a layer of support between my bare-  
 bones application skeleton and the Bezier curve code.   
  There’s little here of interest outside of the mouse 
  tracking and the curve drawing.
**  David W. Smith
*/

#include “QuickDraw.h”
#include “MacTypes.h”
#include “FontMgr.h”
#include “WindowMgr.h”
#include “MenuMgr.h”
#include “TextEdit.h”
#include “DialogMgr.h”
#include “EventMgr.h”
#include “DeskMgr.h”
#include “FileMgr.h”
#include “ToolboxUtil.h”
#include “ControlMgr.h”

/*
 *  Tracker objects.  Similar to MacAPP trackers, but much,
 much simpler.
 */
struct Tracker
{
 void (*track)();
 int    thePoint;
};

static struct Tracker aTracker;
static struct Tracker bTracker;

/*
 *  The Bezier curve control points.
 */
Point   control[4] = {{144,72}, {72,144}, {216,144}, {144,216}};


/*
 *  Draw
 *  Called from the skeleton to update the window.  Draw the   
 initial curve.
 */
Draw()
{
 PenMode(patXor);
 DrawTheCurve(control, true);
}

/*
 *  DrawTheCurve
 * Draw the given Bezier curve in the current pen mode.Draw 
   the control points if requested.
 */
DrawTheCurve(c, drawPoints)
 Point  c[];
{
 if ( drawPoints )
 DrawThePoints(c);
 BezierCurve(c[0], c[1], c[2], c[3]);
}

/*
 *  DrawThePoints
 *  Draw all of the control points.
 */
DrawThePoints(c)
 Point  c[];
{
 int    n;
 
 for ( n = 0 ; n < 4 ; ++n ) {
 DrawPoint(c, n);
 }
}

/*
 *  DrawPoint
 *  Draw a single control point
 */
DrawPoint(c, n)
 Point  c[];
 int    n;
{
 PenSize(3, 3);
 MoveTo(c[n].h - 1, c[n].v - 1);
 LineTo(c[n].h - 1, c[n].v - 1);
 PenSize(1, 1);
}

/*
 * GetTracker
 * Produce a tracker object
 * Called by the skeleton to handle mouse-down events.
 * If the mouse touches a control point, return a tracker for
 that point. Otherwise, return a tracker that drags a gray 
 rectangle.
 */
struct Tracker *
GetTracker(point)
 Point  point;
{
 void   TrackPoint(), TrackSelect();
 int    i;

 aTracker.track = TrackPoint;

 for ( i = 0 ; i < 4 ; ++i ) {
 if ( TouchPoint(control[i], point) ) {
 aTracker.thePoint = i;
 return (&aTracker);
 }
 }
 bTracker.track = TrackSelect;
 return (&bTracker);
}

/*
 *  TouchPoint
 *  Do the points touch?
 */
#define abs(a) (a < 0 ? -(a) : (a))

TouchPoint(target, point)
 Point  target;
 Point  point;
{
 SubPt(point, &target);
 if ( abs(target.h) < 3 && abs(target.v) < 3 )
 return (1);
 return (0);
}

/*
 *  TrackPoint
 *  Called while dragging a control point.
 */
void
TrackPoint(tracker, point, phase)
 struct Tracker  *tracker;
 Point  point;
 int    phase;
{
 Point  savePoint;

 switch ( phase ) {
 case 1:
 /* initial click - XOR out the control point */
 DrawPoint(control, tracker->thePoint);
 break;
 case 2:
 /* drag - undraw the original curve and draw the new one */
 DrawTheCurve(control, false);
 control[tracker->thePoint] = point;
 DrawTheCurve(control, false);
 break;
 case 3:
 /* release - redraw the control point */
 DrawPoint(control, tracker->thePoint);
 break;
 }
}

/*
 *  TrackSelect
 *  Track a gray selection rectangle
 */
static Pointfirst;
static Rect r;

void
TrackSelect(tracker, point, phase)
 struct Tracker  *tracker;
 Point  point;
 int    phase;
{
 switch ( phase ) {
 case 1:
 PenPat(gray);
 first = point;
 SetupRect(&r, first, point);
 FrameRect(&r);
 break;
 case 2:
 FrameRect(&r);
 SetupRect(&r, first, point);
 FrameRect(&r);
 break;
 case 3:
 FrameRect(&r);
 PenPat(black);
 break;
 }
}

/*
 *  SetupRect
 *  Setup the rectangle for tracking.
 */
#define min(x, y) (((x) < (y)) ? (x) : (y))
#define max(x, y) (((x) > (y)) ? (x) : (y))

SetupRect(rect, point1, point2)
 Rect   *rect;
 Point  point1;
 Point  point2;
{
 SetRect(rect,
 min(point1.h, point2.h),
 min(point1.v, point2.v),
 max(point1.h, point2.h),
 max(point1.v, point2.v));
}

/*
**  Skeleton.c  --  A bare-bones skeleton.
** This has been hacked up to demonstrate Bezier curves.  
    Other than the tracking technique, there’s little here of 
    interest.
**  David W. Smith
*/

#include “QuickDraw.h”
#include “MacTypes.h”
#include “FontMgr.h”
#include “WindowMgr.h”
#include “MenuMgr.h”
#include “TextEdit.h”
#include “DialogMgr.h”
#include “EventMgr.h”
#include “DeskMgr.h”
#include “FileMgr.h”
#include “ToolboxUtil.h”
#include “ControlMgr.h”

WindowRecordwRecord;
WindowPtr myWindow;

/*
 *  main
 *  Initialize the world, then handle events until told to quit.
 */
main() 
{
 InitGraf(&thePort);
 InitFonts();
 FlushEvents(everyEvent, 0);
 InitWindows();
 InitMenus();
 InitDialogs(0L);
 InitCursor();
 MaxApplZone();

 SetupMenus();
 SetupWindow();
 SetupBezier();

 while ( DoEvent(everyEvent) )
 ;
}

/*
 *  SetupMenus
 *  For the purpose of this demo, we get somewhat non-standard and use 
no menus.  Closing the window quits.
 */
SetupMenus()
{
 DrawMenuBar();
}

/*
 *  SetupWindow
 *  Setup the window for the Bezier demo.
 */
SetupWindow()
{
 Rect   bounds;

 bounds = WMgrPort->portBits.bounds;
 bounds.top += 36;
 InsetRect(&bounds, 5, 5);

 myWindow = NewWindow(&wRecord, &bounds, “\pBezier Sampler - Click and 
Drag”, 1, noGrowDocProc, 0L, 1, 0L);
 
 SetPort(myWindow);
}

/*
 *  DoEvent
 *  Generic event handling.
 */
DoEvent(eventMask)
 int    eventMask;
{
 EventRecordmyEvent;
 WindowPtrwhichWindow;
 Rect   r;
 
 SystemTask();
 if ( GetNextEvent(eventMask, &myEvent) )
 {
 switch ( myEvent.what )
 {
 case mouseDown:
 switch ( FindWindow( myEvent.where, &whichWindow ) )
 {
 case inDesk: 
 break;
 case inGoAway:
 if ( TrackGoAway(myWindow, myEvent.where) )
 {
 HideWindow(myWindow);
 return (0);
 }
 break;
 case inMenuBar:
 return (DoCommand(MenuSelect(myEvent.where)));
 case inSysWindow:
 SystemClick(&myEvent, whichWindow);
 break;
 case inDrag:
 break;
 case inGrow:
 break;
 case inContent:
 DoContent(&myEvent);
 break;
 default:
 break;;
 }
 break;
 case keyDown:
 case autoKey: 
 break;
 case activateEvt:
 break;
 case updateEvt:
 DoUpdate();
 break;
 default:
 break;
 }
 }
 return(1);
}

/*
 *  DoCommand
 *  Command handling would normally go here.
 */
DoCommand(mResult)
 long   mResult;
{
 int    theItem, temp;
 Str255 name;
 WindowPeek wPtr;
 
 theItem = LoWord(mResult);

 switch ( HiWord(mResult) )
 {
 }

 HiliteMenu(0);
 return(1);
}

/*
 *  DoUpdate
 *  Generic update handler.
 */
DoUpdate()
{
 BeginUpdate(myWindow);
 Draw();
 EndUpdate(myWindow);
}

/*
 *  DoContent
 *  Handle mouse-downs in the content area by asking the application 
to produce a tracker object.  We then call the tracker repeatedly to 
track the mouse. This technique came originally (as nearly as I can tell) 
from Xerox, and is used in a modified form in MacApp.
 */
struct Tracker
{
 int    (*Track)();
};

int
DoContent(pEvent)
 EventRecord*pEvent;
{
 struct Tracker  *GetTracker();
 struct Tracker  *t;
 Point  point, newPoint;
 
 point = pEvent->where;
 GlobalToLocal(&point);
 t = GetTracker(point);
 if ( t ) {
 (*t->Track)(t, point, 1);
 while ( StillDown() ) {
 GetMouse(&newPoint);
 if ( newPoint.h != point.h || newPoint.v != point.v ) {
 point = newPoint;
 (*t->Track)(t, point, 2);
 }
 }
 (*t->Track)(t, point, 3);
 }
}

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Check out the new Pirate Attack update i...
Love pirates and board games? Well, you'll love the new Pirate Attack themed update that just launched in Game of Dice. It adds a bunch of new content themed around pirates, like an all new event map based on a pirate ship which revamps the toll... | Read more »
Splash Cars guide - How to paint the tow...
Splash Cars is an arcade driving game that feels like a hybrid between Dawn of the Plow and Splatoon. In it, you'll need to drive a car around to repaint areas of a town that have lost all of their color. Check out these tips to help you perform... | Read more »
The best video player on mobile
We all know the stock video player on iOS is not particularly convenient, primarily because it asks us to hook a device up to iTunes to sync video in a world that has things like Netflix. [Read more] | Read more »
Four apps to help improve your Super Bow...
Super Bowl Sunday is upon us, and whether you’re a Panthers or a Broncos fan you’re no doubt gearing up for it. [Read more] | Read more »
LooperSonic (Music)
LooperSonic 1.0 Device: iOS Universal Category: Music Price: $4.99, Version: 1.0 (iTunes) Description: LooperSonic is a multi-track audio looper and recorder that will take your loops to the next level. Use it like a loop pedal to... | Read more »
Space Grunts guide - How to survive
Space Grunts is a fast-paced roguelike from popular iOS developer, Orange Pixel. While it taps into many of the typical roguelike sensibilities, you might still find yourself caught out by a few things. We delved further to find you some helpful... | Read more »
Dreii guide - How to play well with othe...
Dreii is a rather stylish and wonderful puzzle game that’s reminiscent of cooperative games like Journey. If that sounds immensely appealing, then you should immediately get cracking and give it a whirl. We can offer you some tips and tricks on... | Read more »
Kill the Plumber World guide - How to ou...
You already know how to hop around like Mario, but do you know how to defeat him? Those are your marching orders in Kill the Plumber, and it's not always as easy as it looks. Here are some tips to get you started. This is not a seasoned platform... | Read more »
Planar Conquest (Games)
Planar Conquest 1.0 Device: iOS Universal Category: Games Price: $12.99, Version: 1.0 (iTunes) Description: IMPORTANT: Planar Conquest is compatible only with iPad 3 & newer devices, iPhone 5 & newer. It’s NOT compatible with... | Read more »
We talk to Cheetah Mobile about its plan...
Piano Tiles 2 is a fast-paced rhythm action high score chaser out now on iOS and Android. You have to tap a series of black tiles that appear on the screen in time to the music, being careful not to accidentally hit anywhere else. Do that and it's... | Read more »

Price Scanner via MacPrices.net

BookBook For iPad Pro Coming Soon
The iPad Pro is a device unlike any other, and with Apple Pencil, it’s the ideal portable sketchpad: all that’s missing is the modern easel and portfolio to go. TwelveSouth’s BookBook for iPad Pro... Read more
12-inch 1.2GHz Silver Retina MacBook on sale...
B&H Photo has the 12″ 1.2GHz Silver Retina MacBook on sale for $1399 including free shipping plus NY sales tax only. Their price is $200 off MSRP, and it’s the lowest price for this model from... Read more
iPads on sale at Target: $100 off iPad Air 2,...
Target has WiFi iPad Air 2s and iPad mini 4s on sale for up to $100 off MSRP on their online store for a limited time. Choose free shipping or free local store pickup (if available). Sale prices for... Read more
Target offers Apple Watch for $100 off MSRP
Target has Apple Watches on sale for $100 for a limited time. Choose free shipping or free local store pickup (if available). Sale prices for online orders only, in-store prices may vary: - Apple... Read more
Apple refurbished 2014 13-inch Retina MacBook...
Apple has Certified Refurbished 2014 13″ Retina MacBook Pros available for up to $400 off original MSRP, starting at $979. An Apple one-year warranty is included with each model, and shipping is free... Read more
Macs available for up to $300 off MSRP, $20 o...
Purchase a new Mac or iPad using Apple’s Education Store and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free, and... Read more
Watch Super Bowl 50 Live On Your iPad For Fre...
Watch Super Bowl 50 LIVE on the CBS Sports app for iPad and Apple TV. Get the app and then tune in Sunday, February 7, 2016 at 6:30 PM ET to catch every moment of the big game. The CBS Sports app is... Read more
Two-thirds Of All Smart Watches Shipped In 20...
Apple dominated the smart watch market in 2015, accounting for over 12 million units and two-thirds of all shipments according to Canalys market research analysts’ estimates. Samsung returned to... Read more
12-inch 1.2GHz Retina MacBooks on sale for up...
B&H Photo has 12″ 1.2GHz Retina MacBooks on sale for $180 off MSRP. Shipping is free, and B&H charges NY tax only: - 12″ 1.2GHz Gray Retina MacBook: $1499 $100 off MSRP - 12″ 1.2GHz Silver... Read more
12-inch 1.1GHz Gray Retina MacBook on sale fo...
B&H Photo has the 12″ 1.1GHz Gray Retina MacBook on sale for $1199 including free shipping plus NY sales tax only. Their price is $100 off MSRP, and it’s the lowest price available for this model... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Subject Matter Expert - Experis (Uni...
This position is for an Apple Subject Matter Expert to assist in developing the architecture, support and services for integration of Apple devices into the domain. Read more
*Apple* Macintosh OSX - Net2Source Inc. (Uni...
…: * Work Authorization : * Contact Number(Best time to reach you) : Skills : Apple Macintosh OSX Location : New York, New York. Duartion : 6+ Months The associate would Read more
Computer Operations Technician ll - *Apple*...
# Web Announcement** Apple Technical Liaison**The George Mason University, Information Technology Services (ITS), Technology Support Services, Desktop Support Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.