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.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Skype 8.68.0.96 - Voice-over-internet ph...
Skype is a telecommunications app that provides HD video calls, instant messaging, calling to any phone number or landline, and Skype for Business for productive cooperation on the projects. This... Read more
Capto 1.2.23 - Capture, annotate, organi...
Capto (was Voila) is an easy-to-use app that takes capturing, recording, video and image editing to the next level. With an intelligent file manager and quick sharing options, Capto is perfect for... Read more
Alfred 4.3.1 - Quick launcher for apps a...
Alfred is an award-winning productivity application for OS X. Alfred saves you time when you search for files online or on your Mac. Be more productive with hotkeys, keywords, and file actions at... Read more
Spotify 1.1.51.380. - Stream music, crea...
Spotify is a streaming music service that gives you on-demand access to millions of songs. Whether you like driving rock, silky R&B, or grandiose classical music, Spotify's massive catalogue puts... Read more
WiFiSpoof 3.5.4 - Change your WiFi MAC a...
WiFiSpoof quickly and easily allows you to change your WiFi MAC address via hot-key or the system menu bar. Version 3.5.4: Dutch localization Download Now]]> Read more
Sparkle Pro 3.0.7 - Visual website creat...
Sparkle Pro will change your mind if you thought building websites wasn't for you. Sparkle is the intuitive site builder that lets you create sites for your online portfolio, team or band pages, or... Read more
MySQL 8.0.23 - Industry-leading open-sou...
MySQL, the industry-leading open-source SQL database, is an accessible, easy-to-use relational database management system (RDBMS). As an alternative to Oracle and SQL server, MySQL offers features... Read more
OmniGraffle 7.18.2 - Create diagrams, fl...
OmniGraffle helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use Graffle to... Read more
OmniGraffle Pro 7.18.2 - Create diagrams...
OmniGraffle Pro helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use... Read more
Malwarebytes 4.7.9.3978 - Adware removal...
Malwarebytes (was AdwareMedic) helps you get your Mac experience back. Malwarebytes scans for and removes code that degrades system performance or attacks your system. Making your Mac once again your... Read more

Latest Forum Discussions

See All

Cookie Run: Kingdom is a base-building R...
Today, developer Devsisters has launched the latest title in their Cookie Run series. It's called Cookie Run: Kingdom and is a base-building RPG where you'll do battle against other players once you've created your delicious realms. [Read more] | Read more »
Here's what SpongeBob SquarePants:...
SpongeBob SquarePants: Battle for Bikini Bottom - Rehydrated came out this week on iOS, and it seems like a pretty solid platformer with a Banjo-Kazooie-style collection-based progression system. You play as SpongeBob, obviously, as he tries to... | Read more »
Pokemon Go will celebrate the arrival of...
Niantic has recently announced that Mega Ampharos, the more fabulous looking version of the Light Pokemon, is now available in the game. To commemorate the occasion, an Incense Day event featuring a host of different Electric and Dragon-Type... | Read more »
Nuts is a squirrel adventure game coming...
Noodlecake’s Nuts is a lo-fi photography game about surveying and documenting the secret lives of squirrels. It’s coming to Apple Arcade this Friday, 22nd January, with a further release coming later on PC and Nintendo Switch. [Read more] | Read more »
Super JetPak DX’s physical preorders sti...
The physical cartridge edition of Pocket Pixel Design’s Super JetPak DX is still available to preorder and will be until 31st January, with the game launching later this year on the Nintendo Game Boy. [Read more] | Read more »
Honkai Impact 3rd has revealed more deta...
Honkai Impact 3rd has now announced more details about its upcoming crossover with Neon Genesis Evangelion. This is set to arrive next week on January 22nd and will introduce an exclusive story, battlesuit and weapon to the popular action-RPG. [... | Read more »
Space Frog Intern, James Bolton's a...
James Bolton's arcade shooter Space Frog Intern is now available for Android devices following its release on iOS last year. It sees players taking control of the titular amphibian and blasting their way through various space beasties. [Read more... | Read more »
The 5 Best Mobile Ports
Ports or coversions of games from one platform to another can be quite tricky. This is especially true when porting games to phones and tablets, as these titles have to be designed with workable touch controls and account for smaller screen sizes... | Read more »
Erica, the PS4-exclusive FMV thriller, c...
London-based studio Flavourworks is bringing its FMV game Erica to iOS on Friday as a free trial, with a full release presumably following later. This is the second platform the game has launched on after its original release on PlayStation 4 two... | Read more »
Cute simulation game Dinosaur Park: Prim...
Dinosaur Park: Primeval Zoo is a cute zoo simulation game from upjers, and it sounds perfect for anyone who’s a dinosaur fan. It’s coming to Android in February, and is available right now for pre-registration. [Read more] | Read more »

Price Scanner via MacPrices.net

Apple restocks $599 4-Core Mac minis, Certifi...
Apple has restocked Certified Refurbished Intel-based 4-Core Mac minis for only $599 or $200 off original MSRP. Each mini comes with a new outer case plus a standard Apple one-year warranty. Shipping... Read more
Apple Magic Keyboard for 11″ iPad Pro/10.9″ i...
Amazon has the Apple Magic Keyboard for 11″ iPad Pro (2nd gen)/10.9″ iPad Air (4th gen) on sale today for only $199 including free shipping. Their price is $100 off Apple’s MSRP for this Magic... Read more
Verizon offers $400 off on iPhone 11 Pro mode...
Verizon is offering $400 off on iPhone 11 Pro models through January 24, 2021 when purchased with a new line of Unlimited service. Price start at $999.99 before the discount. Price is prorated... Read more
Flash sale! Apple’s 21″ 2.3GHz Dual-Core iMac...
Adorama has the 21″ 2.3GHz Dual-Core iMac on sale for a very limited time — today and early tomorrow — for $988 shipped. That’s $111 off Apple’s MSRP, and it’s the cheapest price available for a new... Read more
Boost Mobile continues to offer no contract A...
Boost Mobile is offering 2020 Apple iPhone SE models for $150 off MSRP with service. Their discount reduces the cost of an iPhone SE/64GB to $249.99. 128GB models are offered at a $50 discount: $399.... Read more
B&H launches Apple iMac sale with 21″ and...
B&H Photo has Apple 21″ and 27″ iMacs on sale today for up to $150 off MSRP with prices starting at $1049. Shipping is free. These are the same iMacs sold by Apple in their retail and online... Read more
Select 11″ WiFi iPad Pros on sale today for $...
B&H Photo has select 2020 Apple 11″ WiFi iPad Pros on sale today for $50 off Apple’s MSRP, each including free expedited shipping to most addresses in the US: – 11″ 256GB WiFi iPad Pro: $849 $50... Read more
Clearance 8-core iMac Pro available again for...
Apple has Certified Refurbished, clearance, 27″ 3.2GHz 8-Core iMac Pros available $3819 including free shipping. Their price is $1180 off the original MSRP of new models. A standard Apple one-year... Read more
B&H launches 16″ MacBook Pro sale with mo...
B&H has Apple’s 16″ MacBook Pros on sale for $200-$250 off Apple’s MSRP with prices starting at $2199. Expedited shipping is free to many addresses in the US. Their prices are among the lowest... Read more
At only $809, these are the cheapest MacBooks...
Apple has restocked at full line of Certified Refurbished 2020 13″ Intel-based MacBook Airs available starting at only $809 and up to $280 off original MSRP. Each MacBook features a new outer case,... Read more

Jobs Board

Technical Support - VIVA USA Inc (United Stat...
…when necessary to other client personnel. Knowledge: Systems administration knowledge of Microsoft, Apple , and Linux OS to include but not limited to Windows 7, 8, Read more
Store Associate - Shortage Control - Burlingt...
**LOCATION** 19131 Bear Valley Road Apple Valley CA US 92308 **Overview** If you want an exciting job with one of the largest off-price retail stores in the nation, Read more
Lead Software Engineer - 72673BR - CVS Health...
…by Aetna app, a first-of-its-kind health experience designed in collaboration with Apple . It helps drive healthy behavior by combining your health history with Read more
IOS Developer - Deloitte (United States)
…applications, including knowledge of Swift, Xcode, UIKit, AppleWatch and other core Apple frameworks. + Knowledge of Apple 's HealthKit, ResearchKit, and CareKit Read more
OBGYN Nurse Practitioner - Provider Solutions...
…clinicians in serving a medically diverse, high-acuity, underserved patient population in Apple Valley, California. You will have the opportunity to grow your Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.