Tricks of the Windows Game Programming Gurus:Algorithms, Data Structures, Memory Management, and Multithreading

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

#### Fixed-Point Math

A couple of years ago, most 3D engines used fixed-point mathematics for much of the transformation and mathematical operations in 3D. This was due to the fact that the floating-point support wasn’t as fast as the integer support, even on the Pentium. However, these days the Pentium II, III, and Katmai have much better floating-point capabilities, and fixed-point is no longer as important.

However, in many cases the conversion from floating-point to integers for rasterization still is slow, so sometimes it’s still a good idea to try fixed-point in inner loops that use addition and subtraction operations. These operations are still faster than floating-point operations on the lower-level Pentiums, and you can use tricks to quickly extract the integral part of a fixed-point number rather than making a conversion from `float` to `int`, as you would if you stuck to floating-point.

In any case, this is all very iffy, and using floating-point for everything is usually the best way to do things these days. But it doesn’t hurt to know a little about fixed-point math. My philosophy is to use floating-point for all data representations and transformations, and then to try both floating- and fixed-point algorithms for low-level polygon rasterization to see which is fastest. Of course, this is even more irrelevant if you’re using pure hardware acceleration. If so, just stick to floating-point all the way.

With all that in mind, let’s take a look at fixed-point representations.

Representing Fixed-Point Numbers

All fixed-point math really is based on scaled integers. For example, let’s say that you want to represent the number 10.5 with an integer. You can’t; there isn’t a decimal place. You could truncate the number to 10.0 or round it to 11.0, but 10.5 isn’t an integer. But what if you scale the number by 10? Then 10.5 becomes 105.0, which is an integer. This is the basis of fixed-point. You scale numbers by some factor and that make sure to take this scale into consideration when doing mathematics.

Because computers are binary, most game programmers like to use 32-bit integers, or `int`s, to represent fixed-point numbers in a 16.16 format. Take a look at Figure 11.12 to see this graphically.

Figure 11.12 A 16.16 fixed-point representation.

You put the whole part in the upper 16 bits and the decimal part in the lower 16 bits. Hence, you’re scaling all numbers by 216, or 65,536. Moreover, to extract the integer portion of a fixed-point number, you shift and mask the upper 16 bits, and to get to the decimal portion, you shift and mask the lower 16 bits.

Here’s some working types for fixed-point math:

     #define FP_SHIFT 16     // shifts to produce a fixed-point number

     #define FP_SCALE 65536  // scaling factor

     typedef int FIXPOINT;

Conversions to and from Fixed-Point

There are two types of numbers you need to convert to fixed-point: integers and floating-point numbers. You must consider each one differently. For integers, the binary representation is in straight 2’s complement, so you can use shifts to multiply the number and convert it to fixed-point. On the other hand, floats use a IEEE format, which has a mantissa and an exponent stored in those four bytes, so shifting will destroy the number. You must use standard floating-point multiplication to make the conversion.

Math 2’s complement is a method of representing binary integers so that both positive and negative numbers can be represented and mathematical operations are closed on the set—that is, they work! The 2’s complement of a binary number means computing by inverting the bits and adding 1. Mathematically, let’s say you want to find the 2’s complement of 6—that is, –6. It would be –6+1 or ∼0110 + 0001 = 1001 + 0001 = 1010, which is 10 in normal binary but –6 in 2’s complement.

Here’s a macro that converts an integer to fixed-point:

    #define INT_TO_FIXP(n) (FIXPOINT((n << FP_SHIFT)))

For example:

    FIXPOINT speed = INT_TO_FIXP(100);

And here’s a macro to convert floating-point numbers to fixed-point:

    #define FLOAT_TO_FIXP(n) (FIXPOINT((float)n * FP_SCALE))

For example:

    FIXPOINT speed = FLOAT_TO_FIXP(100.5);

Extracting a fixed-point number is simple too. Here’s a macro to get the integral portion in the upper 16 bits:

    #define FIXP_INT_PART(n) (n >> 16)

And to get the decimal portion in the lower 16 bits, you simply need to mask the integral part:

    #define FIXP_DEC_PART(n) (n & 0x0000ffff)

Of course, if you’re smart, you might forget the conversions and just use pointers that are `SHORT`s to access the upper and lower parts instantly, like this:

    FIXPOINT fp;

    short *integral_part = &(fp+2), *decimal_part = &fp;

The pointers `integral_part` and `decimal_part` always point to the 16 bits that you want.

Accuracy

A question should be popping up in your head right now: “What the heck does the decimal part mean?”. Well, usually you won’t need it; it’s just there to be used in the computations. Normally, you just want the whole part in a rasterization loop or something, but because you’re in base 2, the decimal part is just a base 2 decimal, as shown in Figure 11.12. For example, the numbers

    1001.0001 is 9 + 0*1/2 + 0*1/4 + 0*1/8 + 1*1/16 = 9.0625

This brings us to the concept of accuracy. With four digits of base 2, you’re only accurate to about 1.5 decimals base 10 digits, or +-.0625. With 16 digits, you’re accurate to 1/216 = 1/65536 = .000015258, or about one part in 10,000. That’s not bad and will suffice for most purposes. On the other hand, you only have 16 bits to hold the integer part, meaning that you can hold signed integers -32767 to +32768 (or non-signed up to 65535). This might be an issue in a large universe or numerical space, so watch out for overflow!

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.