• Please review our updated Terms and Rules here

Coordinate Rotation using Fixed Point

neilobremski

Experienced Member
Joined
Oct 9, 2016
Messages
55
Location
Seattle, USA
The goal here is to quickly rotate points by a certain number of degrees using precalculated SINE/COSINE values and without floating point, e.g. only integers. In order to do that I am using fixed point [SUP][1][/SUP] and a lookup table. So first I want to discuss fixed point a bit to get our feet wet.

Fixed point is a technique where one designates a number of high bits in an integer to the whole portion and leaves the remaining lower bits to represent a fractional part. This is usually expressed with a colon or a period such as 8.8 or 8:8 for a 16-bit integer divided in half for whole and fractional parts. The simplest way I have found for thinking about it is that the fractional piece is truly a fraction with a 2[SUP]bits[/SUP] denominator. In the 8:8 example, the denominator is 2[SUP]8[/SUP] or 256.

To put a whole number into an 8:8 fixed point integer is easy: just stick it in the MSB [SUP][2][/SUP]. If there is an arbitrary number of bits allocated to the fractional portion then you shift the whole number that many to the left.

Code:
MOV	AX, 08	; convert whole integer 8
MOV	CL, 04	; by shifting to the left 4
SHL	AX, CL	; to arrive at 12:4 fixed point

Arithmetic on fixed point numbers is straight-forward [SUP][3][/SUP] and I won't burden this blog with it except to talk about multiplication which is the operation used in rotation. After multiplying two fixed point numbers together, the result must be shifted to the right the same number of bits as is used for the fractional portion. That is, if you want the result to be in fixed point. If you want it to be a whole number, as I do, then you'll have to shift twice that amount!

Obviously if you can avoid that shifting then that's all to the better, because SAL and SAR take quite a few cycles per the amount in CL. But how do I achieve this? Going back to the first example of 8:8, the amount I'd have to shift would be 8 or 16 depending on if I wanted a new fixed point value or a whole number only. There's no reason to shift at all, because in the former case I can grab DL and AH directly and in the latter case I can just use DX!

It's the DL + AH solution I'll have to use, though, because for SINE and COSINE I need signed fixed point numbers. In order to make this simple, I'm defining it as 8:8 and it must be noted that the fractional portion is always unsigned! The sign bit in X86 is all the way on the left and never interferes with the fractional portion. This is a very important note because it means to achieve 8 bits of fraction, I actually need 9 bits to store the sign too! On top of this I'll need an extra bit to be able to handle a whole number 1. In the end this uses a 16-bit WORD but only utilizes 10 bits of it.

Why not use a single byte? For two reasons: firstly, that would only allow for a 1/64 range which is even more rudimentary than I can handle. And secondly, the MUL and IMUL instructions must use a full word if either operand is a word. Using a byte might save a memory read SUP][4][/SUP] but the result would be much lower accuracy plus a CBW instruction.

That decision made, below is an example of how to multiply a negative, fractional fixed point number with a whole number. Oh yes, notice that only the multiplier is a fixed point where as the multiplicand is a whole number. For this case, the result needs no shifting to already be a fixed point number. However, I want a whole number result and in a single 16-bit WORD. For this reason, I do need to shift but I do it by sticking together the DL and AH registers as described above:

Code:
MOV	AX, 2000; 8,192
MOV	BX, FF80; -0.5 in 8:8 signed fixed point
IMUL	BX	; 8,192 * -0.5
MOV	AL, AH	; SAR >> 8
MOV	AH, DL	; result in AX = F000h (-4,096)

With that all under my belt I now need to cache the results of SINE and COSINE in a lookup table and then simply look them up. By the way, the function of a sine wave is beyond the scope of this post but it is something I am fascinated by. Anyway, the algorithm of rotating a coordinate is: [SUP][5][/SUP]

Code:
RotatedX = (Y * sin(deg)) + (X * cos(deg))
RotatedY = (Y * cos(deg)) - (X * sin(deg))

This rotates around an origin of (0,0) so X and Y can (and will) be negative. [SUP][6][/SUP] In order to translate to the screen, you'd add a horizontal and vertical modifier such as X + 160 and Y + 100 (on a 320x200 resolution). Now there are 360 degrees and I could even support half degrees but as my rotations are going to be rounded out to about 10 degrees, I'm only going to create a lookup of 36 entries (0 - 35).

Given all that, I can finally write a rotation method! But alas I'll have to save that for another post because I've run out of time and room for today.

Footnotes:
[SUP][1][/SUP]. Although I did come across a technique called CORDIC (and an article at Dr Dobbs) that makes me wonder about calculating arbitrary sine values without fixed point or a lookup table, but that is a post for another day.

[SUP][2][/SUP]. Most Significant Byte, e.g. the upper byte. In little endian byte order (as we have on the x86) this is always going to have a higher memory address.

[SUP][3][/SUP]. Fixed Point Arithmetic and Tricks

[SUP][4][/SUP]. Effective Address calculation and RAM in general on the 8088 is quite slow.

[SUP][5][/SUP]. The C methods use radians for sin() and cos() but my calculator uses degrees and that's what I'll setup my program to use as well.

[SUP][6][/SUP]. In 3D one axis is immobile and rotated around like pole stuck in the ground. For example, looking top-down I would rotate around Y but Y would not be modified. Regardless, any rotation in 3D boils down to two axis changing via the same algorithm with two coordinates and sine/cosine results (disregarding matrices which I'll talk about later).
 
Back
Top