Conversion of NGP-0 Coordinates to Device Specific Coordinates
How to turn Network Graphics Protocol coordinates into whole-number screen positions with a shift, a multiply and an add.
Hansen, J., "Conversion of NGP-0 Coordinates to Device Specific Coordinates", RFC 401, DOI 10.17487/RFC0401, October 1972, <https://www.rfc-editor.org/info/rfc401>.
@misc{rfc401,
series = {Request for Comments},
number = 401,
howpublished = {RFC 401},
publisher = {RFC Editor},
doi = {10.17487/RFC0401},
url = {https://www.rfc-editor.org/info/rfc401},
author = {J. Hansen},
title = {{Conversion of NGP-0 Coordinates to Device Specific Coordinates}},
pagetotal = 2,
year = 1972,
month = oct,
} RFC text
Network Working Group Jim Hansen
Request for Comment #401 Center for Advanced
NIC #11923 Computation
Category: D.6 University of Illinois
Updates: RFC #387 October 23, 1972
Obsoletes: None
Conversion of NGP-0 Coordinates to Device
-----------------------------------------
Specific Coordinates
--------------------
Conversion of NGP-0 coordinates to floating point PDP-10 coordinates
was discussed in RFC #387. In general, however, it is undesirable to
convert NGP coordinates to floating point coordinates because real
devices require integer addressing. To this end, a means is described
to convert NGP coordi- nates to integer coordinates in the range zero
to M, where M is the maximum address of the device screen on a machine
using 2's complement arithmetic. It would not, however, be difficult
to modify this algorithm to operate on machines using one's complement
or sign-magnitude arithmetic.
First consider the NGP coordinate format:
+--+-----------+
| | n |
+--+-----------+
s ^ FRACTION
i
g
n
Where the sign occupies the most significant bit of the coordinate
followed by bits of numerical information (initial implementation of
NGP requires N=15). Negative numbers are represented by 2's
complement. Conversion to device coordinates is accomplished by:
D = S * f + S
Where D =>integer device coordinate
S =>scaling factor (typically M/2)
f =>NGP fractional coordinate
Let us rewrite this as:
n n
D = S*(2 *f)/2 +S
Now factor S into two terms:
I
S= Q * 2
Where Q is an odd integer and I is an integer.
When: I n n
D = Q * 2 *(2 *f)/2 +S
I-n n
= Q * 2 *(2 *f) +S
n
The factor (2 *f) is represented in 2's complement form simply by
extending the sign bit of f into the upper portion of the computer
word, If Q = 1 (as it would be with many devices), it can be ignored.
If Q >< 1, we may console ourselves that an integer multiply is faster
on most machines than a floating point multiply. In fact, on a
PDP-10, this multiply can usually be performed with no access to
memory since Q is usually small.
I-n
We are now left with the 2 factor. This can be accomplished with an
arithmetic shift left by (I-n) or an arithmetic shift right by (n-I)
as is appropriate. The offset factor, S, may now be added using an
integer add.
The procedure for converting NGP coordinates to integer device
coordinates is then:
1. move coordinate to a register and extend sign
2. integer multiply by Q (if necessary)
3. arithmetic shift left by (I-n)
4. integer add S
This procedure would generally be much faster than:
1. move coordinate to register and extend sign
2. float fractional coordinate
3. floating point multiply
4. floating point add
5. conversion to fixed point
[ This RFC was put into machine readable form for entry ]
[ into the online RFC archives by BBN Corp. under the ]
[ direction of Alex McKenzie. 1/97 ]
AI ELI5
On this page
§1The Conversion Problem
RFC 387 discussed converting NGP-0 coordinates to floating point PDP-10 coordinates. This note observes that this is generally undesirable, because real devices require integer addressing.
It therefore describes a way to convert NGP coordinates to integer coordinates in the range zero to M, where M is the maximum address of the device screen, on a machine using 2's complement arithmetic. The author says the algorithm could be modified for one's complement or sign-magnitude machines.
Screens count in whole steps, not fractions. This note shows how to get whole steps from the fractions the drawing rules use.
§2The NGP Coordinate Format
An NGP coordinate puts a sign in the most significant bit, followed by n bits of fractional information. The initial implementation of NGP requires N=15. Negative numbers are represented in 2's complement.
Conversion to a device coordinate is D = S * f + S, where D is the integer device coordinate, S is a scaling factor (typically M/2) and f is the NGP fractional coordinate.
A position is a fraction between minus one and one. Multiply by half the screen size and add the middle, and you land on a screen spot.
§3The Integer Procedure
The note writes S = Q * 2^I, where Q is an odd integer and I is an integer. The expression becomes D = Q * 2^(I-n) * (2^n * f) + S.
The factor 2^n * f is obtained simply by extending the sign bit into the upper part of the word. If Q is 1, as with many devices, the multiply can be ignored. The 2^(I-n) factor is an arithmetic shift left by (I-n), or right by (n-I). The offset S is then added with an integer add.
- Move the coordinate to a register and extend the sign.
- Integer multiply by Q (if necessary).
- Arithmetic shift left by (I-n).
- Integer add S.
Instead of doing fraction math, you slide the digits over and add a number. Sliding digits is much quicker for a computer.
§4Why It Is Faster
The alternative is to move the coordinate to a register, float it, do a floating point multiply and add, and convert back to fixed point. The note says the integer procedure would generally be much faster.
On most machines an integer multiply is faster than a floating point multiply. On a PDP-10 the multiply can usually be done with no access to memory, since Q is usually small.
Four quick steps beat five slow ones, so the screen can be drawn sooner.