V.2.42 has been released into the wild on February the 20th, 2018. See the demonstration video on Youtube below or download a DSK-image and try it in your emulator or on real wood!
Disk image of V.1.61 is out now as well as the source code of V.1.61 on GitHub or as assembler listing.
New article available giving a detailed description of the numerical algorithm and its optimisations so far.
There is a new demonstration video available which shows the speed improvement from V.1.61 in comparison to V.1.10.
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.
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.
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.
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.
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.
b(x,y) - the 2D projection of a on the computer screen!
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.
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 ][.
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.
Entry: setting up both HIRES screens for double buffering and drawing the borders as well as the text messages.
Let's have a closer look on some details of the algorithm!
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.
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.
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.
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!
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.
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.
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.
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.
$E6: this zero page location determines on which screen is drawn!
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.
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 $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.
20  PRINT "PREPARING DATA TABLE IN MEMORY..."
120  PRINT : PRINT "POKED ";L;" BYTE FROM $7200..."
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.
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!