TweetFollow Us on Twitter

Fixed Point Math
Volume Number:10
Issue Number:3
Column Tag:Under The Hood

Fixed Point Math For Speed Freaks

Fast fixed math and derived graphics utility routines

By Alexei Lebedev

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

About the author

Several of the author’s free programs, Kubik, Fractal Artist, Tower of Hanoi, as well as some other programs and patches can be downloaded from CompuServe. Author’s e-mail address is 70534,404@compuserve.com. Kubik simulates Rubik’s cube, and Fractal Artist draws some fractals like Mandelbrot Set and Julia Sets. Both Kubik and Fractal Artist (which were built for speed) make use of fixed point arithmetic techniques described here.

In this article we will explore several aspects of Mac programming: fixed point arithmetic in assembly, 3-d transformations, perspective and parallel projections, backplane elimination, offscreen bitmaps, and animation. We’ll discuss details of a set of utility routines, the complete source of which is available in the source files on disk or the online services (see page 2 for details about the online services).

Fixed Point Format

Let’s first build a small library of functions to do fixed point arithmetic. There are several reasons to do this instead of using built-in functions like FixMul and FixDiv. The first and most important is speed - Toolbox functions are slow. Just for comparison, our function for multiplying two Fixed numbers is 3 instructions long and computations are done in registers, whereas FixMul in my LC’s ROM has 47 instructions, and accesses memory many times. [This reasoning changes when it comes to math and the PowerPC. See the Powering Up series to learn more about the new common wisdom. - Ed. stb] The second reason is that we get to choose the precision of the numbers, because we can distribute bit usage between fractional and integer parts of a Fixed number in any way we like. Thus, if we were calculating a Mandelbrot set, we would probably choose 4 bits for the integer part, and 28 for the fraction. For graphics, on the other hand, it makes more sense to split the bits evenly between integer and fractional parts. This lets us use numbers as large as 32767+65535/65536, and fractions as small as 1/65536.

A Fixed number is simply a real number (float) multiplied by a scale in order to get rid of the fractional part. We will use 32-bit fixed point numbers, with the integer part in the higher word, and the fractional part in the lower word. So in our case (f) is scaled by 216 = 65536.

Fixed Point Arithmetic

Fixed numbers can be added (and subtracted) just like long integers. Why? Let n and m be the two numbers we want to add. Then their Fixed equivalents are nf and mf, where is f is, of course, 65536. Adding nf and mf we get (n+m)f, which is n+m expressed in Fixed notation. Let’s apply the same logic to other operations. With multiplication it’s a bit different (no pun intended), because nf*mf = (n*m)f2 has the wrong units. The correct result is (n*m)f. To get it, we simply divide the expression above by f. Note that this is not necessary when a Fixed number is being multiplied by an integer, because nf*m = (n*m)f. This important fact has been omitted in Inside Mac Volume I. As a result, some programmers write lines like fixnum = FixMul(fixnum, FixRatio(5, 1)), when all that is needed is fixnum *= 5 or something similar.

We will now implement multiplication in assembly. We will be using the 68020’s signed multiply instruction muls.l, which has syntax muls.l dx, dy:dz. This multiplies a long word in dx by a long word in dz, splitting the 64-bit result between dy and dz. Note that the registers can overlap, which means that to square a number, you would write muls.l dx,dy:dx.


/* 1 */
asm {
 muls.l d0, d1:d2
 move.w d1, d2 ; join high and low words of the result
 swap   d2; reorder words for correct result
}

The last two instructions divide d1:d2 by 65536, effectively shifting them down 16 bits. Figure 1 illustrates how this is done.

Fig. 1 Multiplying Fixed numbers

Division is slightly less trivial, but still very straight-forward. It uses the signed divide instruction divs.l.


/* 2 */
asm { 
 move.l num1, d2 ; num1 = numerator
 move.l num2, d1 ; num2 = denominator
 beq.s  @bad
 move.w d2, d0   ; split d2 between d2 and d0
 swap   d0
 clr.w  d0
 swap   d2
 ext.l  d2
 divs.l d1, d2:d0
 bra.s  @end
bad:    ; denom = 0
 moveq  #-2, d0
 ror.l  #1, d0
 tst.l  d2
 bgt    @end; is num1 > 0, return 0x7FFFFFFF
 not.l  d0; return 0x80000000
end:  
}

The code first loads the numbers and checks if denominator is 0. If this is the case, it tries to return a number closest to infinity of the same sign as the numerator.

Rotating -2 (0xFFFFFFFE) one bit to the right gives 0x7FFFFFFF. If numerator > 0, there is nothing to do, because 0x7FFFFFFF is the largest positive Fixed number. If numerator is negative, we return NOT(0xFFFFFFFE), or 0x80000000. Even though this IS the smallest Fixed number, it is not very usable, because -0x80000000 = 0x7FFFFFFF + 1 = 0x80000000! That’s why FixDiv() returns 0x80000001. Naturally, our code can be modified to return 0x80000001. All we have to is change not.l to neg.l. Actually, it not important at all which value is returned. Division by zero should not occur under any circumstances. The compiler, for example, doesn’t include any run time checking for this kind of thing in the code. The macro Divide() (in the file FixedPointMath.h) doesn’t either, because it takes up space. Function DivideCh() in FixedPointMath.c is safer to use, but it takes up more space, and handicaps you with function call overhead.

Let’s look at the mechanism of division. Multiply() and Divide() are two basic operations, using which you can implement many other functions, so it’s important to understand how they work.


/* 3 */
 move.w d2, d0
 swap   d0
 clr.w  d0
 swap   d2
 ext.l  d2

The idea here is to split d2 between d2 and d0, and divide this 64-bit quantity by d1 (it is basically the reverse of Multiply()). The first three instructions put d2.w into the d0.hw. The last two instructions put d2.hw into d2.w. After all of this is done, we can use divs.l d1,d2:d0 to divide the numbers.

Now that we know how division and multiplication work, we can build many more useful functions. For example, a square root function.


/* 4 */
Fixed FixSqrt(register Fixed num)  // uses Newton’s method to find  num
{
 register Fixed s;
 register short i;
 
 s = (num + 65536) >> 1;  //divide by 2
 for (i = 0; i < 6; i++)  //converge six times
 s = (s + Divide(num, s)) >> 1;
 return s;
}

It is the implementation of a well-known formula for finding square roots. It is based on Newton's method. S, (= num), can be calculated to any precision, but since (s+num/s)/2 converges very quickly, I decided that six iterations would be enough (For showing me the algorithm for this function, I would like to thank Alexander Migdal). Adescription of Newton’s method can be found in any high-school level book on mathematics.

As another example, we will consider a function for rounding Fixed to integers. After that we will move on to graphics-related topics. You will find more useful macros in FixedPointMath.h. Since they are all derived from Multiply(), Divide(), or FixRnd(), we will not discuss them here.


/* 5 */
asm {
 swap   d0
 bpl.s  @end
 addq   #1, d0
 bvc.s  @end
 subq   #1, d0
end:
}

This code rounds integers upwards. Note that when n > 0 and n - trunc(n) >= .5, bit 15 is set. After swap, this bit raises the N flag. In this case, we round up by adding 1 to the truncated result. If an overflow occurs, we subtract one

(d0.w (=0x8000) - 1 = 0x7FFF)

Note that this also works when n < 0, because for negative numbers bit 15 means that n - trunc(n) <= -.5. This code can be easily extended to round negative numbers correctly (away from 0), but since it is implemented as a macro, it would be nicer to keep it small (it returns the same result as Toolbox’s FixRound()).

3D Transformations

Possibly to your regret, I will not derive formulas for rotating points here. Instead, I will refer you to a book by Leendert Ammeraal, Programming Principles in Computer Graphics, second edition (published by John Wiley & Sons; its price is high, but think of it as the K&R of graphics programming). It is an excellent book, take my word for it. Using elegant C++ code, it implements vector classes, explains matrices, polygon triangulation, Bresenham’s algorithms, and includes a 3d graphics program utilizing z-buffer and other nice things. Here is a function for rotating a point about z-axis:


/* 6 */
void RollPoint(Vector3D *p, short angle)
{
 Fixed sin, cos, xPrime, yPrime;
 
 GetTrigValues(angle, &sin, &cos);
 xPrime = Multiply(p->x, cos) - Multiply(p->y, sin);
 yPrime = Multiply(p->x, sin) + Multiply(p->y, cos);
 p->x = xPrime;
 p->y = yPrime;
}

To demonstrate its correctness, let y be 0. Then after rotation p will have coordinates (x*cos(angle), x*sin(angle)). If on the other hand, we let x be 0, p will be (-y*sin(angle), y*cos(angle)). It’s always nice to have a piece of paper and pencil, because visualizing things is not always easy. Also, in case you didn’t know, a positive angle rotates a point counter-clockwise.

In RollPoint(), GetTrigValues() is used to calculate sine and cosine of an angle. Yes, it appeared previously in MacTutor (“Real-Time 3D Animation”, April/May 1992, Volume 8, No. 1, pp. 12-13). I borrowed it when I was building my 3D library, because I found it useful. You will find its implementation of GetTrigValues() in SineTable.h. The sine table used for look-up is initialized by InitSineTable(). InitSineTable() only builds the table once, storing it in a resource ‘sint’ with id 128.

You will find three other routines in file Transformations.c. They are ScalePoint(), PitchPoint(), and YawPoint(). ScalePoint() multiplies each coordinate of a point by the number you specify. The other two rotate points around x- and y- axes respectively (Yaw is for y, and Pitch is like a pitch modulation wheel in synthesizers: it spins up and down). Note that usually matrices are used for rotating and translating points. The advantage of using matrices is that they “remember” transformations applied to them, so if you teach a matrix three hundred transformations, you could quickly apply it to any other point, and this would be equivalent to doing all these transformations by hand.

Projection

We will now take a quick look at projection. Examine Fig. 2 to get an idea of what’s going on.

Figure 2.

SpaceSize specifies width and height of a rectangle in XY plane which is mapped to the screen. This rectangle (call it spaceR) has 3D coordinates of ((-spaceSize.x, spaceSize.y, 0), (spaceSize.x, spaceSize.y, 0), (spaceSize.x, -spaceSize.y, 0), (-spaceSize.x, -spaceSize.y, 0)). screenCenter is the origin of the 2D coordinate system. It maps to a 3D point (0,0,0), and vice versa. A screen rectangle (viewR) can be specified with ViewPort(). spaceR will be mapped to viewR and vice versa. screenCenter is set to the center of viewR.

Fig. 2 shows the viewing pyramid from the side. The camera is located on the Z axis, and is facing the XY plane. The distance from camera to the screen (eyez) can be changed using a routine SetViewAngle(theta). We calulate distance to the projection screen so that every point (lying in the xy plane) inside the spaceR rectangle is visible. The smaller the angle, the greater its cotangent, the greater eyez, and less noticeable the perspective. Specifying a viewing angle of 0 will result in a divide by zero. Instead, D3toD2par() should be used for parallel projection. A large value of theta will result in distortions and very strong perspective.


/* 7 */
eyez = spaceSize * cot(theta)
we have

P’ =   P * eyez   screenCenter  =  P * cot(theta) * screenCenter
     (eyez - P.z)  spaceSize                eyez - P.z

void D3toD2(Vector3D *p3D, Point *p2D)
{
 Fixed d = eyez - p3D->z;
   p2D->v = center.y 
 - FixRnd(Divide(Multiply(p3D->y, ratio.y),d));  
   p2D->h = center.x 
 + FixRnd(Divide(Multiply(p3D->x, ratio.x),d));
}

This function implements perspective projection (in Mac’s coordinate system the origin is in the upper-left corner, and y increases downward). Let’s see how parallel projection can be implemented. Since the camera is assumed to be infinitely far away, we take the limit of P’ as eyez approaches . We have


/* 8 */
P’  =    P *  screenCenter
           spaceSize

Another way to see this is note that P’.z no longer contributes (since there is no perspective), so eyez’s cancel.

Fig. 2 shows P’’, P’s image on the screen when using parallel projection. The following piece of code shows its implementation.


/* 9 */
void D3toD2par(Vector3D *p3D, Point *p2D)
{
   p2D->v = center.y - FixRnd(p3D->y * center.y/spaceSize.y);   
   p2D->h = center.x + FixRnd(p3D->x * center.x/spaceSize.x);
}

Back plane elimination

Suppose we have a triangle ABC. The orientation of points ABC is said to be positive if we turn counter-clockwise when visiting points ABC in the specified order. It is zero if A, B, and C lie on the same line, and is negative, if we turn clockwise. As long as we’re talking about convex, closed objects where all of the polygons use the same point ordering, the concept of orientation turns out to be very useful when determining whether a triangle (or some other polygon, provided all of its lie in the same plane) is visible. We say that points with positive (counter-clockwise) orientation lie on a visible plane, otherwise they line on the backplane, and the triangle is not drawn. The following function computes orientation of three points.


/* 10 */
static short visi(Point p1, Point p2, Point p3)
{
 return (long)((p2.v - p1.v) * (p3.h - p1.h)) - 
 (long)((p2.h - p1.h) * (p3.v - p1.v));
}

The result of this function is > 0 if the orientation is positive, < 0 if it negative, and 0 if all three points lie on the same line.

Figure 3

From this figure you see that A x B is a vector which points out of the page if (P1 P2 P3) have positive orientation, and into the page otherwise. The function visi() returns the opposite of (ad - bc) to account for mac’s coordinate system, where y increases downward. In that sense, mac has left-handed coordinate system.

Offscreen Bitmaps

We now come to the easiest part of the discussion.


/* 11 */
Boolean NewBitMap(BitMap *theBitMap, Rect *theRect)
{
 theBitMap->rowBytes = (((theRect->right 
 - theRect->left)+15)/16)*2;
 theBitMap->baseAddr = NewPtr((long)(theRect->bottom 
 - theRect->top) 
 * theBitMap->rowBytes);
 theBitMap->bounds = *theRect;
 return (!MemErr);
}

This function is straight-forward. rowBytes is calculated so it is even (as required by QuickDraw). Then NewBitMap allocates a block to hold the bit image. It returns true if everything is OK, otherwise it returns false.

Here is a piece of code from the OffscreenPort function, which allocates an offscreen port, and associates it with a bitmap, pointer to which is passed as a parameter:


/* 12 */
 OpenPort(newPort);
 newPort->portBits = *theBitMap;
 newPort->portRect = theBitMap->bounds;
 RectRgn(newPort->visRgn, &newPort->portRect);
 ClipRect(&newPort->portRect);
 EraseRect(&newPort->portRect);

We use RectRgn() to set new port’s visRgn to its portRect in case it happens to be larger than the screen. As to animation, it is all done by the CopyBits() call in the main() function.

 
AAPL
$104.85
Apple Inc.
+1.86
MSFT
$44.99
Microsoft Corpora
+0.61
GOOG
$545.04
Google Inc.
+12.33

MacTech Search:
Community Search:

Software Updates via MacUpdate

Art Text 2.4.8 - Create high quality hea...
Art Text is an OS X application for creating high quality textual graphics, headings, logos, icons, Web site elements, and buttons. Thanks to multi-layer support, creating complex graphics is no... Read more
Live Interior 3D Pro 2.9.6 - Powerful an...
Live Interior 3D Pro is a powerful yet very intuitive interior designing application. View Video Tutorials It has every feature of Live Interior 3D Standard, plus some exclusive ones: Create multi... Read more
The Hit List 1.1.7 - Advanced reminder a...
The Hit List manages the daily chaos of your modern life. It's easy to learn - it's as easy as making lists. And it's powerful enough to let you plan, then forget, then act when the time is right.... Read more
jAlbum Pro 12.2.4 - Organize your digita...
jAlbum Pro has all the features you love in jAlbum, but comes with a commercial license. With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code!... Read more
jAlbum 12.2.4 - Create custom photo gall...
With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code! Beginner-friendly, with pro results Simply drag and drop photos into groups, choose a design... Read more
ExpanDrive 4.1.7 - Access remote files o...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
OmniOutliner Pro 4.1.3 - Pro version of...
OmniOutliner Pro is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It'... Read more
Evernote 5.6.2 - Create searchable notes...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
OmniOutliner 4.1.3 - Organize your ideas...
OmniOutliner is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more
BBEdit 11.0 - Powerful text and HTML edi...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more

Latest Forum Discussions

See All

Puzzle to the Center of the Earth Review
Puzzle to the Center of the Earth Review By Campbell Bird on October 23rd, 2014 Our Rating: :: SPELUNKING PUZZLESUniversal App - Designed for iPhone and iPad Do some puzzles to make some platforms in this smart and fun free-to-play... | Read more »
Sleep Attack TD Review
Sleep Attack TD Review By Jennifer Allen on October 23rd, 2014 Our Rating: :: A TRUE TWISTUniversal App - Designed for iPhone and iPad Sleep Attack TD is a tower defense game with a difference – you can rotate the layout – and it’s... | Read more »
Earn Your Master Camper Badge in Camp Po...
Earn Your Master Camper Badge in Camp Pokemon Posted by Jessica Fisher on October 23rd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Garruk Gets His Revenge in a New Magic 2...
Garruk Gets His Revenge in a New Magic 2015 Expansion, Coming This November Posted by Jessica Fisher on October 23rd, 2014 [ permalink ] | Read more »
Sentinels of the Multiverse Review
Sentinels of the Multiverse Review By Rob Thomas on October 23rd, 2014 Our Rating: :: SENTINELS ASSEMBLEiPad Only App - Designed for the iPad Greater Than Games’ tabletop classic, Sentinels of the Multiverse swoops in to save the... | Read more »
Build Your Own Fantasy Football Dynasty...
Build Your Own Fantasy Football Dynasty with Draft Day Posted by Jessica Fisher on October 23rd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Cars: Fast as Lightning – Tips, Tricks,...
Hey there, Stickers: Want to know all about how impressed we were with Radiator Springs? Check out our Cars: Fast as Lightning review! Cars: Fast as Lightning is a cute and fun app that combines racing and town-building with the charisma and... | Read more »
Jam Messenger Review
Jam Messenger Review By Jennifer Allen on October 23rd, 2014 Our Rating: :: SIMPLE MESSAGINGiPhone App - Designed for the iPhone, compatible with the iPad Want a very quick way to send push-based messages? Jam Messenger is basic... | Read more »
Felllice (Games)
Felllice 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: EXCLUSIVE PRICE DROP! 50% OFF FOR A LIMITED TIME! EAT EAT EAT AND GROW ! | Read more »
The Arrow Game: by Grazie Media (Games)
The Arrow Game: by Grazie Media 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: Guide a flying arrow through skyscrapers and city streets to hit a distant target. Experience an endless... | Read more »

Price Scanner via MacPrices.net

Save up to $125 on Retina MacBook Pros
B&H Photo has the new 2014 13″ and 15″ Retina MacBook Pros on sale for up to $125 off MSRP. Shipping is free, and B&H charges NY sales tax only. They’ll also include free copies of Parallels... Read more
Apple refurbished Time Capsules available sta...
The Apple Store has certified refurbished Time Capsules available for up to $60 off MSRP. Apple’s one-year warranty is included with each Time Capsule, and shipping is free: - 2TB Time Capsule: $255... Read more
Textilus New Word, Notes and PDF Processor fo...
Textilus is new word-crunching, notes, and PDF processor designed exclusively for the iPad. I haven’t had time to thoroughly check it out yet, but it looks great and early reviews are positive.... Read more
WD My Passport Pro Bus-Powered Thunderbolt RA...
WD’s My Passport Pro RAID solution is powered by an integrated Thunderbolt cable for true portability and speeds as high as 233 MB/s. HighlightsOverviewSpecifications Transfer, Back Up And Edit In... Read more
Save with Best Buy’s College Student Deals
Take an additional $50 off all MacBooks and iMacs at Best Buy Online with their College Students Deals Savings, valid through November 1st. Anyone with a valid .EDU email address can take advantage... Read more
iPad Air 2 & iPad mini 3 Best Tablets Yet...
The new iPads turned out to be pretty much everything I’d been hoping for and more than I’d expected.”More” particularly in terms of a drinking-from-a-firehose choice of models and configurations,... Read more
Drafts 4 Reinvents iOS Productivity App
N Richland Hills, Texas based Agile Tortoise has announced the release of Drafts 4 for iPhone and iPad. Drafts is a quick capture note taking app with flexible output actions. Drafts 4 scales from... Read more
AT&T accepting preorders for new iPads fo...
AT&T Wireless is accepting preorders for the new iPad Air 2 and iPad mini 3, cellular models, for $100 off MSRP with a 2-year service agreement: - 16GB iPad Air 2 WiFi + Cellular: $529.99 - 64GB... Read more
Apple offering refurbished Mac Pros for up to...
The Apple Store is offering Apple Certified Refurbished 2013 Mac Pros for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The... Read more
Select MacBook Airs $100 off MSRP, free shipp...
B&H Photo has 2014 a couple of MacBook Airs on sale for $100 off MSRP. Shipping is free, and B&H charges NY sales tax only. They also include free copies of Parallels Desktop and LoJack for... Read more

Jobs Board

Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work 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
Position Opening at *Apple* - Apple (United...
…customers purchase our products, you're the one who helps them get more out of their new Apple technology. Your day in the Apple Store is filled with a range of Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.