Contact me | Login | Search | Sitemap | Site Notice

Developping a 3D-Demo for the Apple ][

What's New?

Inspired by games like Elite or Stellar 7 I was wondering how difficult it would be to write a 3D-rendering engine in 6502 assembler for the Apple ][. The first results look promising and so I decided to release a small 3D-Demo in celebration of the 40th birthday of the Apple ][. This article shall shed some light on the algorithm and the inner structure of the 3D-Viewer. But first take a look at the program in action:
 



To-Do-List

This project is far from finished now. There are some things which I want to add in the next future. Some of the things to do are listed here:

  • Add rotation around the z-axis
  • Add clipping
  • Think about a hidden line algorithm
  • Try to do the division as a table lookup method
  • Maybe try to find a game concept for the engine

Disk Image and Source Code

Download the disk image (DSK-format) and the source code of the 3D-Demo V.1.1 here:

Download source code listing for 3D-Demo
6502-assembler source code
for Merlin-8-Assembler
   
Download a Apple ][ disk image
Apple ][ disk image
DOS 3.3 compatible

View source code listing for 3D-Demo
View source code listing
for Merlin-8-Assembler
   
Github repository a Apple ][ disk image
View repository
Github

Joystick- and Keyboard-Control of the 3D-Object

The 3D-object in the viewer can be easily controlled by using the joystick or paddles and the keyboard. The following operations are possible - depending on the input device you have. Normally on emulators full control of the program is possible using joystick-emulation:

  • x-axis, y-axis: These two axes of the joystick control the rotation of the object around the x- and the y-axis so you can directly control rotation by moving the joystick up, down, left or right.
  • Button 0: This button resets the aspect of the object to initial variables which means it resets the current rotation angles to the initial values and stops the rotation. Zooming will not be reset by pressing this button.
  • Button 1: This button exits the program.

The keyboard offers the following possibilities:

  • Keys 1-5: Switch between 5 different 3D-objects. Point and line data will be loaded from the disk.
  • Keys +/-: If your joystick does not support a z-axis you can do the object zoom with the + and - key on the keyboard. Not as elegant as doing it with paddles but it works.
  • Key B: Toggles the "benchmark" function on/off. Benchmark in this context here means that every 180° during the rotation a system beep (ctrl-G / BELL) will be issued. This allows counting beeps and using a stopwatch for measuring the time for a certain amounts of rotations.
  • Key Q: This key also exits the program. This feature will allow to use button 1 for a different function in the future

The following short video shows how you can control the rotation. First the 3D-object rotates wildly. Then after pressing button 0 the rotation is stopped and the rotation angles are resetted. Then a new rotation is started:


Mathematical Background

Some remarks on the mathematical background: Drawing 3D objects on the computer screen while performing rotations and translations of the objects requires some calculus known as affine transformations in geometry. Affine transformations in 3D-space can be computed using vector-matrix-multiplications and divisions.

The following text is stolen from Wikipedia and has been edited to make the basic concepts of the algorithm understandable:

When the human eye views a scene, objects in the distance appear smaller than objects close by - this is known as perspective. While orthographic projection ignores this effect to allow accurate measurements, perspective projection shows distant objects as smaller to provide additional realism when performing a 2D-projection of the 3D-scene.

The perspective projection requires a more involved definition as compared to orthographic projections. A conceptual aid to understanding the mechanics of this projection is to imagine the 2D projection as though the object(s) are being viewed through a camera viewfinder when the scene is presented on the computer screen. The camera's position, orientation, and field of view control the behavior of the projection transformation. The following variables are defined to describe this transformation:

  • a(x,y,z) - the 3D position of a point A that is to be projected.
  • c(x,y,z) - the 3D position of a point C representing the camera -> this it what you see on the screen!
  • theta(x,y,z) - the orientation of the camera.
  • e(x,y,z) - the viewer's position relative to the the display which can be used e.g. to center or translate the image on the computer screen.

Which results in:

  • b(x,y) - the 2D projection of a on the computer screen!

In order to compute b we first compute the vector d as the position of point A with respect to a coordinate system defined by the camera, with origin in C and rotated by theta with respect to the initial coordinate system. This is achieved by subtracting c from a and then applying a rotation by theta to the result:

This transformation is often called a camera transform expressing the rotation in terms of rotations about the x, y, and z axes. The three 3x3-matrices represents the rotation around the x-, y- and z-axis accordingly. These rotation matrices can be combined to a single rotation matrix by performing a matrix-matrix-multiplication beforehand and implementing the final matrix in the computer code which saves some computation time.

In order to "zoom" the scene in and out, it is possible to change the camera position c. Let c be positioned at (0,0,10). The camera is "viewing" the coordinate origin from a certain distance. If the 3D object is located at the origin of the coordinate system moving the camera along the z-axis results in the visual effect of zooming the 3D object in and out - this is how the concept of zooming is implemented in my algorithm.

The transformed point d can be projected on the computer screen by evaluating the following formula - this is where the division pinches in:

To keep this section short: this basically outlines what you need to do in order to draw a 3D-object on the screen and give the scene some sort of perspective. By drawing and undrawing the object while changing the camera angle theta you can create the impression of a rotating object.

By giving the user control of the camera angles and the distance of the camera to the coordinate origin you can create the appearance of a virtual reality simulation. Let's see how this maths can be stuffed in a 6502-assembler code for the Apple ][.

The Algorithm in Detail

The main program is written in assembler and expects all necessary data already loaded at the specific memory locations which are:

  • $6000: main program code (up to $675B, 1884 bytes)
  • $7000: SIN/COS-table
  • $7200: array with point and line data
  • $7400: character shape table for writing text on the HIRES-screen
  • $7A00: 2 kB data space for the multiplication table

At first the point and line data was created using inline code in the main program making the extension for drawing new objects a little bit unhandy. Now the table with point and line data can be supplied by an additional binary file. I have written a small AppleSoft-tool that let's you create new 3D objects from simple DATA-statements easily. The tool creates a binary file that can be loaded into memory order to draw the new 3D object.

Overall Algorithm Structure

The algorithm consists of the following parts:

  • Entry: setting up both HIRES screens for double buffering and drawing the borders as well as the text messages.
  • Main loop:

    • Read paddles and buttons for controlling the action on the screen
    • Calculate rotational speeds around x- and y-axis as well as setting the camera position along the z-axis
    • Calculate new position of the points of the 3D object
    • Undraw old 3D-objedct position (fast clear screen)
    • Draw new 3D object position
    • Manage double buffering overhead

  • Exit: switch back to text mode

Let's have a closer look on some details of the algorithm!

Internal Number Format

Calculus on an 8 bit machine is somewhat a problem if it comes to floating point calculations in assembler and leads automatically to accuracy related issues. Using floating point math is almost impossible due to the lack of processing speed for those numbers so other solutions have to be found.

I tried to keep things as simple as possible: a point A of the 3D-object should be described by three single byte values. Since the origin of the world coordinate system is put in the screen center single points of the object can have positive as well as negative coordinates. This requires to interpret the single byte numbers in two's complements:

  • $00-$7F: positive values from 0..127 (decimal)
  • $FF-$80: negative values backwards from -1..-128 (decimal)

Since the screen size of the Apple ][ HIRES-screen is 280 x 192 pixel single byte values for the 3D-object seemed to be handy. 

A Glance on Multiplication

At several points in the algorithm multiplication of values is necessary. If two 8-bit-values are multiplied with each other the result will be 16-bit wide. in order not to leave the 8-bit track I decided to use only the high byte of the multiplication result sacrificing a whole lot of accuracy but it still works out to give a nice animation.

What about Divisions?

In order to calculate the projection on the screen the x- and y-coordinates of d have to be divided by the z-value. This requires a division subroutine. I did not want to lose more accuracy so I decided to realise a 16-to8-bit division routine (dividend at 16 bits, divisor at 8 bits). Hence I used the 16-bit results from the last multiplication as input for the 16-bit dividend instead of just using the high-byte. This approach yields a better numerical accuracy. 

Due to speed reasons the division has been downscaled to a 14 bit / 6 bit division. See the numerics section for more information!

Watch the z-Values!

Multiplicating two 8-bit values and using only the high-byte of a 16-bit as result is seldom a problem. However, the division by z can yield funny results! if z is close to zero the division results increase dramatically leading to overflows and/or distorted graphical representation on the computer screen.So be sure to move the camera far enough away from the coordinate origin. 

If z is too large the division routine will yield zero as a result which also can lead to strange result so a balanced adjustment of the possible z values are necessary.

Sine-/Cosine-LookUp-Table

In order to evaluate the rotational matrices the calculation of the sine- and cosine-function is necessary. There are several approaches in order to accomplish this task:

  • Internal ROM routines: The AppleSoft-ROM includes trigonometric functions which evaluate a Taylor series expansion. Nice but too slow for my purpose. This also includes own code which calculates a series expansion.
  • Parabola approximation: Another try in order to avoid a Taylor series would be the use of simple parabolas as approximation of the sine-function. Works pretty well, but is also too slow.
  • LookUp-table: The classical lookup-table results in the best performance for my purposes.

Designing the LUT

I was thinking about a clever approach for implementing a SINE/COSINE-LUT in assembler. From my point of view I wanted a merry-go-round counter that is a single byte which can be decremented or incremented endlessly going automatically from $FF to $00 when incremented or from $00 to $FF when decremented, hence I do not need to take special care on overflows or counter boundaries. Instead I can realise a rotation by just counting up- or downwards.

I wanted to use the same LUT for both sine and cosine. Besides a phase shift of 90° the functions are identical. Hence I decided to set up a LUT where the value of 2*pi (360°) was evenly distributed over 256 steps. In order to manage the cosine with the same LUT I extended the sine-LUT with 64 bytes in order to take care of the 90° phase shift of the cosine. That means the evaluation of the cosine at an angle of 0° starts at byte position 64 in the sine-LUT.

The complete table consists of 320 bytes. The values for the sine and cosine are also stored in two's complement ranging from -127 to 127 which resemble the function values of -1 and 1 respectively. 

Since the total of 360° are distributed on 256 steps one step equals exactly 1.40625°. This angle resolution is absolutely sufficient for a smooth animation.

The following AppleSoft-program was used to calculate the sine-LUT beginning at location $7000:

 10  REM  MAKE SINE TABLE
 20  FOR I = 0 TO 360
 30 SI =  SIN (1.40625 * I * 0.017453295)
 40 SO =  INT (127 * SI + 0.5)
 50  PRINT SO
 52  IF SO < 0 THEN SO = 256 + SO
 55  POKE 28672 + I,SO
 70  NEXT I
 
*7000.713F

7000- 00 03 06 09 0C 10 13 16
7008- 19 1C 1F 22 25 28 2B 2E
7010- 31 33 36 39 3C 3F 41 44
7018- 47 49 4C 4E 51 53 55 58
7020- 5A 5C 5E 60 62 64 66 68
7028- 6A 6B 6D 6F 70 71 73 74
7030- 75 76 78 79 7A 7A 7B 7C
7038- 7D 7D 7E 7E 7E 7F 7F 7F
7040- 7F 7F 7F 7F 7E 7E 7E 7D
7048- 7D 7C 7B 7A 7A 79 78 76
7050- 75 74 73 71 70 6F 6D 6B
7058- 6A 68 66 64 62 60 5E 5C
7060- 5A 58 55 53 51 4E 4C 49
7068- 47 44 41 3F 3C 39 36 33
7070- 31 2E 2B 28 25 22 1F 1C
7078- 19 16 13 10 0C 09 06 03
7080- 00 FD FA F7 F4 F0 ED EA
7088- E7 E4 E1 DE DB D8 D5 D2
7090- CF CD CA C7 C4 C1 BF BC
7098- B9 B7 B4 B2 AF AD AB A8
70A0- A6 A4 A2 A0 9E 9C 9A 98
70A8- 96 95 93 91 90 8F 8D 8C
70B0- 8B 8A 88 87 86 86 85 84
70B8- 83 83 82 82 82 81 81 81
70C0- 81 81 81 81 82 82 82 83
70C8- 83 84 85 86 86 87 88 8A
70D0- 8B 8C 8D 8F 90 91 93 95
70D8- 96 98 9A 9C 9E A0 A2 A4
70E0- A6 A8 AB AD AF B2 B4 B7
70E8- B9 BC BF C1 C4 C7 CA CD
70F0- CF D2 D5 D8 DB DE E1 E4
70F8- E7 EA ED F0 F4 F7 FA FD
7100- 00 03 06 09 0C 10 13 16
7108- 19 1C 1F 22 25 28 2B 2E
7110- 31 33 36 39 3C 3F 41 44
7118- 47 49 4C 4E 51 53 55 58
7120- 5A 5C 5E 60 62 64 66 68
7128- 6A 6B 6D 6F 70 71 73 74
7130- 75 76 78 79 7A 7A 7B 7C
7138- 7D 7D 7E 7E 7E 7F 7F 7F

Double Buffering

Due to the fact that the Apple ][ has two HIRES-screens it is possible to implement double buffering which means that you draw on one screen while the other screen is being displayed. This technique efficiently reduces almost all flickering yielding smoother animation results. 

How is it done? Take a closer look on the following code snippet! The routine which draws the 3D-object first sets the screen to draw to and then the screen which is displayed. Remember the following addresses:

  • $E6: this zero page location determines on which screen is drawn!

    • $E6 = #$20: draw on HIRES screen 1
    • $E6 = #$40: draw on HIRES screen 2

  • $C054: toggle this hardware switch to show HIRES screen 1
  • $C055: toggle this hardware switch to show HIRES screen 2

Check the following code snippet: In line #411 - after the new position of the 3D-object has been drawn the active screen number is read in the accumulator and the new screen to draw to is set accordingly as well is the screen which is displayed. So if screen 1 is next to be drawn to screen 2 will be displayed and vice-versa. Next - not shown in this code snippet - the old lines are undrawn and the new lines are drawn on the active screen while the other screen is displayed:

  306 *
  307 ********************************
  308 * DRAW LINES                   *
  309 ********************************
  310 *
.
.
.
  411 DRWEND   LDA   ASCR       ; DISPLAY DRAW-SCREEN
  412          CMP   #$02
  413          BEQ   DISP2      ; SHOW SCREEN 2
  414          LDA   #64
  415          STA   $E6        ; DRAW ON 2
  416          STA   $C054      ; SWITCH TO SCREEN1
  417          INC   ASCR       ; ASCR = 2
  418          BNE   DRWEND2
  419 DISP2    STA   $C055      ; SWITCH TO SCREEN2
  420          LDA   #32
  421          STA   $E6        ; DRAW ON 1
  422          DEC   ASCR       ; ASCR = 1
  423 DRWEND2  RTS

A little Caveat

Double buffering requires a bit more data storage and handling overhead. When a 3D-object has been drawn the current coordinates must be saved in order for the undraw action to take place. If you draw on two screens consecutively it is necessary to store the last two object positions to be able to delete the last but one object position while the current position is still displayed. Sounds complicated? Well, data handling is a bit tricky but will be explained later in this text.

The following videos show on the left the flickering if no double buffering is active and on the right the benefits of double buffering:

Defining your own 3D-Objects

The algorithm expects a data table at position $7200 with a maximum length of 257 ($101) Bytes. The first byte defines the number of points of the 3D-object. The next 256 contain the object data. The data for each point of the object consists of a block of 16 bytes. Each block is defined as follows:

  • Bytes $00-$02: x-, y- and z-position in the object space. The values are stored in two's complement format, one byte for each coordinate. Scaling of the object is designed that the maximum values of -127 or +127 ($81/$7F) will completely fit on the screen at maximum zoom in the 3D-Viewer.
  • Bytes $03-$05: current drawing position of the point on the screen. Bytes $03 and $04 hold the x-values lo- and hi-byte, $05 holds the y-value.
  • Bytes $06-$0B: free data space at the moment since the undraw function has been rewritten to an alternate faster algorithm so the old drawing positions need not to be saved anymore for undrawing the 3D-object on the screen. This data space will be used for additional line data in the future
  • Bytes $0C-$0F: point number data to which the current point is connected to via a line. This influences which lines are drawn of the 3D-object. From each point a maximum of 4 lines to other points is allowed. This restriction limits the possibilities of interconnecting lines between points but with 4 lines a lot of objects can be designed.

 

 

 

Since the maximum data table size is 256 bytes a total of 16 points with 4 lines each (64 lines) can be defined. The image on the left in this paragraph shows a more complex object consisting out of 12 points and 16 lines. The algorithm performance in drawing this object is alright for that complexity of the object. I will try to do even more complex objects in order to see when speed of the animation is decreasing dramatically.

A little AppleSoft-Tool

Since it is a bit difficult to enter the data manually in the monitor and BSAVE the data table before you run the 3D-Viewer I have written a small but helpful AppleSoft-tool that lets you define your 3D-object in simple DATA-statements. The program reads the DATA and POKEs the according values of the object in the memory and save a binary file to disk for your convenience. Here is a listing of the tool:

 10  REM  MAKE DATA TABLE FOR 3D-DEMO
 20  PRINT "PREPARING DATA TABLE IN MEMORY..."
 30  READ N
 50  BA = 29184: REM  BASE ADRESS OF POINT TABLE
 55  POKE BA,N:BA = BA + 1
 60  FOR I = 1 TO N: REM  PROCESS ALL POINTS
 70  FOR J = 1 TO 3: READ P: GOSUB 2000: POKE BA,P:BA = BA + 1: NEXT J
 80  FOR J = 1 TO 9: POKE BA,0:BA = BA + 1: NEXT J
 90  FOR J = 1 TO 4: READ P: POKE BA,P:BA = BA + 1: NEXT J
 100  NEXT I
 110  L = 16 * N + 1: REM  LENGTH OF TABLE
 120  PRINT : PRINT "POKED ";L;" BYTE FROM $7200..."
 130  PRINT  CHR$ (4);"BSAVE POINTTABLE,A$7200,L";L
 990  END 
 1000  REM  DATA DEFINITION
 1004  REM  TOTAL NUMBER OF POINTS
 1005  DATA  12
 1010  DATA  -0.8,-0.8,0.8,2,4,5,0
 1020  DATA  0.8,-0.8,0.8,3,6,0,0
 1030  DATA  0.8,-0.8,-0.8,4,7,0,0
 1040  DATA  -0.8,-0.8,-0.8,8,0,0,0
 1050  DATA  -0.8,0.8,0.8,6,8,0,0
 1060  DATA  0.8,0.8,0.8,7,0,0,0
 1070  DATA  0.8,0.8,-0.8,8,0,0,0
 1080  DATA  -0.8,0.8,-0.8,0,0,0,0
 1090  DATA  0,-0.5,0,10,11,12,0
 1100  DATA  0,0.5,0.71,11,12,0,0
 1110  DATA  -0.61,0.5,-0.355,12,0,0,0
 1120  DATA  0.61,0.5,-0.355,0,0,0,0
 2000  REM  CALC POKE-VALUE
 2010  IF P < 0 THEN P =  INT (256 + P * 120): RETURN 
 2020  P =  INT (P * 120): RETURN 
 3000  END 

3D-Object Data-Format in AppleSoft

The first DATA-statement in line #1005 gives the total number of points of the 3D-object. A maximum of 16 points will be used by the 3D-algorithm. Though you can enter more points but they will not get drawn in the 3D-Viewer.

Each of the following DATA-statements (lines #1010 to #1120) contain the data for each point. Each point needs 7 input values:

  • Values #01, #02 and #03: The x-, y- and z-position of the point in object space. The tool converts the the input data to two's complement. Input values that shall yield meaningful results should stay in the range of -1.0 to +1.0 (floating point values are allowed here!). The tool converts these values to two's complement signed 8 bit integer numbers and pokes the values in memory. There is a little safety margin included for the maximum possible values of +1.0 and -1.0 such that it does not result in drawing errors when running the viewer with maximum zoom!
  • Values #04 to #07: These values define the point numbers where a line should be drawn. The first point you define gets number #1, the second #2 and so on. In order to draw a line from point #1 to #2 value #04 should be set to 2 for example. You can define four lines for each point. If you do not need these lines you must set the value 0 for each line that should not be drawn obligatory! The 3D-Viewer will skip these lines then during the 3D-object presentation!

Hint: Each line between two points only need to be defined once and are hence only drawn once. If you already defined a line between point #1 and #2 you do not need to define the same line again from #2 to #1!

Caution: The small tool does not incorporate range checking of any of the given parameters at the moment - so you have to check this by yourself for now!