Writing a 3D geometry engine from scratch (discussion)

[Mike]

Hi!

This is the discussion thread accompanying the documentation thread "Writing a 3D geometry engine from scratch".

Please post comments solely in this thread here! Thank you.

Greetings,

Michael

[MrSterlingBS]

Hi Mike,

my question, why do you use 256 values for SIN (COS)? Is this not too much? This results in an approximate angle of 1.4 degrees.
Wouldn't 128 values ​​be sufficient for the low resolution of 128x160 or even 168x192 in full screen? (2.8 degrees)

BR
Sven

[Mike]

[...] why do you use 256 values for SIN (COS)?

Foremost, as I already had explained in the documentation thread, I use 256 as value for the full angle with SIN and COS, as this corresponds well to the range of the 8-bit (index) registers: no extra reduction is necessary, the angle argument simply wraps at 255 <-> 0.

Is this not too much?

Quite the contrary, reducing the number of angles reduces the capabilities of the geometry engine without good reason. One wants to be able to do fine turning rotations! A more coarse choice of angles also would show immediately with the given type of animation, rotating with a constant angle velocity in all three axes: the animation repeats at the very latest every 256 steps, as then - with any given increment or decrement - all angles will have returned to their start values. With symmetrical objects (as is a cube), one gets repeating views even more often.

Also, from another point of view, the chosen angle range could not be in any way be called "too much". One could justifiably call the angle precision too fine, if it would result in excessive repetition of (rounded) output values. This is not the case with the given angle argument and result value precision, see this diagram:



Critical here are not the argument ranges where SIN(X) or COS(X) have a low or even zero slope, but rather where SIN(X) or COS(X) have their maximum slope. If we would get repeated values there, then either the argument precision would be too fine or, alternatively, the result precision would be too coarse.

The specification of the geometry engine fixes the result precision at 2:6 fixpoint. For the arguments with the biggest slopes, there is (still) no unwarranted repetition of result values, so in whole, the arrangement is well balanced.

When the precision of the arithmetics is increased beyond 2:6 fixpoint, this also calls for increased (or finer) precision of the angles - and this is indeed the case in my original demo from 2003.

[MrSterlingBS]

Cool, thank you for the detailed explanation. 320 Bytes are not much today on the vic and make things easier.

BR
Sven

[MrSterlingBS]

Hello,

Can you please explain your division routine in more detail.
Or do you simply use LSR HighByte / ROR LowByte, six times?

BR
Sven

Note that the relevant part of the geometry engine, lines 29..35, has all the values stored in integer variables! Nominally, the divisions in the expressions for U% and V% in line 33 have been eliminated by the reciprocals in the arrays P%(...) and Q%(...) - the division by 64 in FNCV(...) doesn't count and will be replaced by shift operations when we do the port to machine code. Also note only one temporary for the S% and C% values is used - their values are directly read off the table S%(...).

[Mike]

One can also shift the 16-bit word of the intermediary result twice to the left and extract the 2:6 fixpoint value from the high byte.

[MrSterlingBS]

Hello,

I've thought about it and haven't really come up with a solution.

Why do both bytes, high and low, have to be shifted? With the ASL command, there is no carry to the next byte through the carry. The seventh bit is shifted into the carry and the first bit is filled with a zero. Wouldn't it be enough to "just" shift the high byte? Where is my thinking wrong? And what is meant by extract the 2:6 fixpoint value? Let's assume the high byte is the following bit sequence 00.010101 = $15 (21) ^= 0.328125 (~= 1/3).
Would that already be the solution or does this bit sequence still need to be converted?

Br
Sven

[Mike]

I had hoped it would not have been necessary to clear things up in such detail, but anyhow:

Hello,

I've thought about it and haven't really come up with a solution.

Why do both bytes, high and low, have to be shifted? With the ASL command, there is no carry to the next byte through the carry. The seventh bit is shifted into the carry and the first bit is filled with a zero. Wouldn't it be enough to "just" shift the high byte? Where is my thinking wrong? And what is meant by extract the 2:6 fixpoint value? Let's assume the high byte is the following bit sequence 00.010101 = $15 (21) ^= 0.328125 (~= 1/3).
Would that already be the solution or does this bit sequence still need to be converted?

Br
Sven

When two 8 bit numbers representing a 2:6 fixpoint value are multiplied, the intermediate result is a 16 bit number in 4:12 fixpoint format, i.e. 4 bits before the radix point and 12 bits behind the radix point. The two products in the rotation formulas are added/subtracted in full to retain their precision, the sum/difference then also is in 4:12 fixpoint format. For further processing though, only the 2 bits before the radix point and 6 bits behind the radix point are wanted/needed, see the diagram below:

Code: Select all

4:12 - b15 b14 b13 b12 . b11 b10  b9  b8  b7  b6  b5  b4  b3  b2  b1  b0

                |   |     |   |   |   |   |   |
                V   V     V   V   V   V   V   V

2:6  -          b7  b6 .  b5  b4  b3  b2  b1  b0

In the documentation thread, I already have gone into lengths to explain why we can afford to 'throw' away the two top most bits of the intermediary result: careful analysis has shown that none of the values exceed the range -2 to just below 2, so no overflows are supposed to happen. The bit b5 in the 4:12 fixpoint value however is used to round the resulting 2:6 fixpoint value. Those bits b4 to b0 in the 4:12 fixpoint value are truncated.

Once again, the 16 bit value then is shifted as whole to literally extract the 2:6 value from the 4:12 value as shown in the diagram above. If we use 6 times LSR/ROR, the result ends up in the low byte, and the C flag then contains the rounding bit. If we instead use 2 times ASL/ROL, the result ends up in the high byte; to obtain the rounding bit, an additional shift left of the low byte does the job. Doing just 2 shifts left instead of 6 shifts right of course is faster.

...

For the OT part, see here.

[Orangeman96]

Thanks for the OUTSTANDING explanation, Michael! Makes perfect sense! -OGM

[MrSterlingBS]

A quick question about the new episode of the course.

In my opinion, the shadow buffer or double buffer technology is the best for the visual experience. Unfortunately, the VIC doesn't have the hardware to deliver corresponding full-screen results at high speed. How about the Elite draw/undraw technology? Could that be a better solution? Of course, there will be some flickering, but would it be a solution for speed and memory usage in fullscreen?

Clear and copy needs 24.000‘ ?
Drawing all 12 Lines 16.000‘ ?
40.000‘ cycles

Draw/Undraw 2x16.000‘
32.000‘


The result of the Elite technologoy can be found here.
https://elite.bbcelite.com/hacks/flicke ... elite.html

[topcat]

I would like to run this in Vice, I extracted the zip but it is not obvious to me how to run it in Vice.

[Mike]

[...] how to run [the examples] in Vice[?]

Generally, if you want to (be able to) access files hosted in a PC directory from VICE, make sure:

In "Preferences > Settings ... > Peripheral Devices > Drive"

• True Drive Emulation (TDE) is ticked off,
• Virtual Device Traps is ticked on.

In "Preferences > Settings ... > Peripheral Devices > Host file system device":

• Access P00 files with their built-in filename is ticked on,
• Create P00 files on save is ticked off, and
• Only show P00 files is also ticked off.

In "Preferences > Settings ... > Host > Autostart":

• Set "Autostart mode" to "Virtual filesystem".

Don't forget to save these settings, so VICE remembers them on next start up. You will only need to re-enable True Drive Emulation in the rare case of programs that re-program the disk drive.

That also prepared, for the examples in the workshop, enable the necessary RAM expansion (in most cases, +8K RAM) and drag-and-drop the file "BOOT" into the VICE main window. This action mounts the surrounding PC directory as disk and autostarts the file.

Alternatively, if you want to load a file without autostarting it, first mount the surrounding PC directory in the "Browse ..." requester of "Preferences > Settings ... > Peripheral Devices > Host file system device > Host directory". Make sure there is no *.d64 (or *.d81, etc.) disk image attached by dismounting them all in "File > Detach disk image > Detach all". You can verify, that the correct PC directory is mounted as usual with LOAD"$",8 and LIST.

[MrSterlingBS]

Hello,

I have successfully implemented the sign multiplication routine from Toby Lobster's GitHub.
https://github.com/TobyLobster/multiply ... /smult10.a

This should make the 3D routine run even faster. However, it requires 2kB of memory. Certainly not a problem these days.

The COS/SIN, Projneg, Projpos and X,Y,Z values of the cube must be EOR #$80 before loading.

49' cylcles for normal multiplication
32' cycles if the multiplier loaded from previous calculation

That is very fast.

BR
Sven

[darkatx]

For both the interested newcomer and as a refresher for the experienced coder, the seminar also gives an outlook about what is necessary to advance beyond the scope of the featured wireframe cube demo, especially hidden line removal, filled vectors, lighting models and perspective correct texture mapping.

Hold on, you plan to do all that?!

This is going to be a helluva thread!

[Mike]

Hold on, you plan to do all that?!

Yes.

...