nathanielbabiak 2021-12-20 11:44 (Edited)
I had mentioned on my racing upload here that I wasn't proud of the 3D polygon code. It uses my sprite expansion library to display the polys, and the frame update code is just so ugly and slow! (It's really tough to clear polys at stale locations.) So, a few polys are shown in one of the preview screen shots, but I never actually uploaded the code itself.
Anyway, as I woke up this morning, I realized there's a much better way to structure the sprite expansion library. The array used within the raster subprogram can be replaced with a RAM buffer. It's not a huge change to the library, but it'll run a few pct faster for drawing instructions, and a bunch faster for the instruction that clears the screen.
The important benefit of the change isn't as easy to describe, but it allows for double triple buffering! (Edit 2021-12-21: I should mention page-flipping works too - that's why I was so excited - it's finally possible.)
With the super-chip-8 stuff finished, I had planned to return to the racing upload and polish it off... However, with actual double triple buffering, I finally have enough libraries developed for:
... wait for it ...
...
...
full 3D.
The 3D racing upload here requires any 3D object to be aligned at a right-angle to the camera, and requires the camera to be aligned parallel to the road directly beneath it. The 3D maze uploads here and here require any 3D object to be aligned at a right-angle to the floor, and require the camera to be aligned parallel to the floor.
These early uploads were 2.5D, not truly 3D. It's a bit faster for retro hardware, and discussed here if anybody wants to read about it.
The next upload I'm planning is truly 3D, meaning six-axis degree-of-freedom. There's enough speed in the system for eight 24 colors of polygons, a planar (flat) ground with checkerboard pattern fading out into the horizon, and even a skybox!
It'll be here around February. More to come!
McPepic 2021-12-20 19:08
Super exciting! I’m always blown away by the programs you make and am confident that this new one is no exception. Keep up the good work!
nathanielbabiak 2021-12-22 02:19 (Edited)
Thanks!
Also, as I work through the details of the double-buffer triple-buffer page-flip implementation, I realized two MAJOR things:
It'll work with the 3D maze uploads (the earlier one), even though it uses an entirely different display system. (It'll work with any of the raster scanline display systems I've developed.) It's pretty cheap too, it only costs 2% CPU to modify the raster interrupt (2 clock cycles), and it means I can finally eliminate screen tearing from the 3D maze!
I've discovered a new optimization for raster display systems. (I verified it hasn't appeared in any uploads by anybody else before, even!) It's only optimal in displays showing 121 or fewer raster scanlines per frame, although the specific raster scanlines can be updated at any time (meaning it's not applicable to the 3D maze uploads, which run full-screen, 128 raster scanlines every frame). With this optimization enabled, the raster interrupt CPU usage is significantly reduced! And it only adds a single clock cycle to the raster interrupt.
With these two things figured-out, my CPU budget calculations indicate it's possible to update 10 polygons at once, at 20 to 30 fps (it's great they'll be drawn to a buffer, so the user won't see partially updated screen data). I finally have a real poly-count!!! I don't have a proof-of-concept .nx file I can upload yet, just some math in Excel. It's going to take the better part of a month to work out the structure and syntax, but the math says it'll work.
More to come!
nathanielbabiak 2021-12-28 13:31 (Edited)
Proof of concept is done! It's here
nathanielbabiak 2022-02-15 07:40 (Edited)
Well this is embarrasing...
I had originally estiamted the polys at around 25,000 clock cycles (CC) per render. I estimated the sprite display driver at 5,000 cc/frame. My estimates were spot-on, and I got a bit under 35,000 cc (basically 30 FPS).
BUT... I forgot basic addition - I forgot the other CC for the other stuff I wanted to show!
It looks like the planar (flat) ground with checkboard pattern is around 12,000 CC/render, and the skybox is another 5 to 10,000 cc/render (depending on implementation).
The problem is, some of the numbers above are CC/render, but one is CC/frame (which needs considered every time it goes over 17,556 CC).
So on one hand, I've been told at points in my life I'm a pretty smart guy. On the other hand, I've also been told I'm "either the dumbest smart guy, or the smartest dumb guy"!!! And it appears so in this case, as I've forgotten to add all these numbers together.
In total, the "full" 3D I'd create would run at 37,000 CC/render, with an additional 15,000 CC/frame, or around 15-20 FPS. It's just too slow to be pretty. And I'm super embarrased I forgot simple addition!
LOL. :-)
nathanielbabiak 2022-02-15 07:42 (Edited)
My point is, I'm giving up on my latest upload, as I don't believe it can be optimized to be useful in an actual game. I'm going back to other, more feasible ideas.
More to come (but not on this subject!)
(...this upload helped me figure out a fast-clear-screen implementation for the sprite display driver, so it can be incorporated into the racing upload...)
McPepic 2022-02-15 15:47
I honestly don’t know how you are figuring out all these clock cycle amounts. I usually just try to get everything to work first and then go back and optimize if something needs to be improved. Admittedly, when you started this project, I started working on my own 3D renderer. I’m just trying to convert position and rotation from camera space to world space.
Keep up the good work you’ve been doing though!
nathanielbabiak 2022-02-16 01:30 (Edited)
Hi McPepic,
There's three sources to determine clock cycles:
I'm really not trying to optimize every line I write, but rather I try to determine the essence of the optimal algorithm for the precise outcome desired (before I begin to code), then write the inner-most loop, then just multiply out with big-O notation to get to the values.
The trick is getting the arithmetic right to separately accommodate CC/frame and CC/render. Although my biggest stumbling block at the moment appears to be simple addition! Just kidding. (I like to weirdly poke fun at myself, have this odd notion it'll make me more approachable.)
Thanks,
~Nate
nathanielbabiak 2022-02-16 01:38 (Edited)
Hey again, (to address converting spaces),
Did you see in the star3D upload dated Jan. 5 that the model-, world-, and camera- space conversions are commented? Just CTRL+F for "SPACE".
Or is the issue that use of matrix notation makes it complicated? Or use of subprograms? Or arrays? Etc. Just let me know where the code gets too complicated and I'll see if I can help.
I only ask because you'll really need to understand all of those (pretty thoroughly) to do "full" 3D, and I'm happy to give some hints along the way. :-)
To simplify though, you could start with non-rotating 3D, and then you'd pretty quickly see that a change-of-space is basically just subtraction... ;-)
McPepic 2022-02-16 02:38
I already have a moving camera. It probably would be easier though if I uploaded what I have so far. I'll just fix up a couple of things before posting.
McPepic 2022-02-17 17:58
So, I actually figured out the local to global space calculation. But I realized that there’s a problem that I didn’t notice before and thought that you might know something about it. Before drawing each line, I am swapping in the sprite data from the buffer. For some reason though, on the last line, the full sprite is appearing, rather than just the first row of pixels. I think this has something to do with the fact that the data is only swapped in before a line is drawn.
nathanielbabiak 2022-02-18 04:48 (Edited)
Sorry, took a while to decompress from work today. (And my cat just got home from the vet, he's fine, but they said he'd be dizzy for another day or so, it's been a busy night.)
I reviewed your code dated 2022-02-12, and understand the issue. The "page flip" code clears (what I'll call the scanline buffer) at address GETADR(WRITEBUFF,0)
, which is correct. However, the code omits clearing (what I'll call the sprite buffer) at address $FE00
or $FE28
as appropriate.
You need to clear both, otherwise the stale sprites will be shown during off-frames.
TLDR: Modify this subprogram by adding the second line:
SUB CLEARBUFF
FILL GETADR(WRITEBUFF,0),5120
IF WRITEBUFF THEN FILL $FE28, 40 ELSE FILL $FE00, 40
END SUB
McPepic 2022-02-18 14:50
Thank you so much. I spent so long trying to figure out how to fix this. It usually is the simplest solutions, isn’t it. I was honestly just going to have it clip out the last line of the screen.
At this point with the program, I’m going to be adding back-face culling. Thanks again.
McPepic 2022-02-18 18:38
I got back-face culling working and can draw multiple triangles. :)
nathanielbabiak 2022-02-19 00:02
Nice!
McPepic 2022-02-19 14:56
I have a full cube now with a moving & rotating camera!
McPepic 2022-02-20 21:56
Hi again. This is what I have so far for my renderer.
nathanielbabiak 2022-02-25 02:30 (Edited)
Very nice! (I've uncommented the for-loop of course.) I like the blue background grid too, it'll certainly help orient camera changes distinctly from object changes. I did something similar actually (a skybox and an infinite geometric plane). What's next though? A space ship game? Or something else entirely? :-)
McPepic 2022-02-25 03:01
I'm currently modifying the clipping algorithm to work per-tri. This should reduce the per-line workload and cause the program to run much faster. I'm not exactly sure what kind of game to make yet. I'm hoping to first optimize my drawing algorithm and make it so that new objects can be added and calculated appropriately by the program.
McPepic 2022-05-11 16:02
Hi! I’ve kind of left this project on the shelf, as there has been a problem with the camera that I can’t figure out how to solve. For some reason, when I try to rotate the camera along the x when it’s rotated on the y at all, it tilts the camera strangely and I can’t figure out why. I was wondering if you could take a look at it.
nathanielbabiak 2022-05-11 16:16
Yeah I'll take a look over the next few days. Sounds like an out-of-sequence issue or housekeeping issue, but I'll have time after work to look into it.
nathanielbabiak 2022-05-24 20:30 (Edited)
(Sorry it took me a while to get around to this.) I'm having a lot of trouble following the variable and subprogram naming convention, the array indices, and the program flow in general.
I can't use the gamepad inputs to rotate in two axes (to try to recreate the issue you've described).
What line number would you modify to request a rotation in two axes from your translation code? (66?) And, what specific instruction would you place on that line?
McPepic 2022-05-25 16:29
The left and right arrows on the second gamepad are for y rotation and the up and down arrows on that same gamepad are for x rotation. The problem is when I rotate the camera around one and then the other. This rotates it weird (space transformation problem?). The old version didn’t do this though, so I wonder if I left out a step when I reorganized.
On your next point, I have this project on mobile, which doesn’t display line numbers. However, there is a general rotation sub program which rotates around the x,y,and z axis. Alternatively, there are separate sub programs for each axis (RotX,RotY,RotZ). The rotation sub program takes in the x,y,and z rotation to apply. It also takes an array that stores the position of the transform to be rotated. This array is also the output. The single axis rotation sub programs take in a single rotation value, as well as the position array (x,y,z).
I might have missed entirely what you were asking. I tried really hard to abstract the 3D functionality to make it easy to work with.
nathanielbabiak 2022-05-26 19:43 (Edited)
Got'cha.
I couldn't reproduce any space transformation problems, hope you find this funny... Your code is correct as-is! The visual artifact you've described is the field-of-view causing a fish-bowl effect. Adjust the FOV and it'll go away. My 3D proof of concept upload does the same thing if you set the FOV too high, you can try it by holding [B]
and tapping [UP]
here, or you can check out this article, just scroll down until you see an animation of a blue background and white house.
For line numbers, not that it matters, but you can always insert a line you want help with and type x=1/0, and run it, and provide the error's line number.
McPepic 2022-05-26 19:58
Really? My code actually works? I really appreciate the help. Thanks for the tip about line numbers!
I actually had another question. I can add objects to the scene and their transform is applied to the vertices, but the points are transformed globally instead of locally. (Scaling on the y stretches the model vertically no matter the rotation, causing weird stretching on the model). I can send you the program doing this if it helps.
nathanielbabiak 2022-05-26 20:25 (Edited)
The order in which you perform transformations matters. What you've described in your post is: first rotate, second stretch-Y. As an alternative, try re-ordering the CALL
instructions of your main loop (the ones that call various transformation subprograms) to do this instead: first stretch-Y, second rotate.
It's helpful to think about it like this: the vertices are being translated within a 3D space (the axes/origin of that 3D space are not being translated).
nathanielbabiak 2022-05-26 21:02
Disregard what I said about line numbers - looks like line numbers aren't shown in the iPad version for runtime errors.
McPepic 2022-05-26 21:05
Wow. I can't believe I didn't think of that. Also, I checked the FOV and it was only set to 45 degrees. The problem is if I rotate around the y and then the x. This causes the screen to tilt. I think it's rotating around the global axis instead of the local player axis (relative to the rotation of the camera).
McPepic 2022-05-26 21:12
It's weird, because the movement is relative to how the camera should be rotated, but the actual rotation that you see appears to be based on the global axis.
nathanielbabiak 2022-05-26 21:19 (Edited)
Yeah your FOV is set in SUB INIT_CAM
. 45 is too high. Try 30. If you need more convincing that this is the issue, try 55. To be clear, the FOV you're using in-code is actually half of an optical camera's horizontal FOV, so I'm really talking about optical camera horizontal FOV ranging from 60 (30x2) to 110 (55x2). This is evident if you construct the triangle where you're using TAN
within SUB PROJECT
.
Ugh, that was technical.
Note that the level of 'zoom' is effected when you adjust FOV, so you'll need to use the gamepad in your upload to increase the distance between camera and cube to compare various FOV values in a reasonable way. Both links in my message above (both my upload and Wikipedia's animation) auto-adjust the translation of the camera to make the comparison reasonable.
McPepic 2022-05-26 21:55
I even tried 10 and I'm having the same problem.
McPepic 2022-05-26 22:05
Maybe it's a projection problem?
nathanielbabiak 2022-05-27 01:00
Let me check again...
nathanielbabiak 2022-05-27 04:19 (Edited)
You know what I hate about the internet? You misread ONE thing and you're just LOST forever. I figured we're talking past each other, so I reread what you wrote from the beginning. It was like the first thing you said! "Try to rotate the camera along the x when it’s rotated on the y". (Sorry for dismissing this as a FOV issue... I hadn't really moved the camera rotation more than 5 degrees or so.)
OK so I can finally re-produce your bug - and I know what the problem is!
This is a transformation housekeeping bug (not a sequencing bug). What's happening here is that your principle coordinate axis (X-Y-Z) are either not orthogonal or not unit length after a transformation somewhere. You're using floating point math in successive transformations, and the errors are accumulating. So what you're seeing is kind'a like a mis-aligned optical element within a camera.
The gradual sloping of the camera is odd, but what really makes me think this is a principle axis definition issue is how movement along the z axis changes with player-1 up/down buttons.
Here's a 2D simplified example of what this would look like where the axis isn't orthogonal: link
It's surprising that this type of bug isn't more prominently discussed in tutorials, because it crops up in maddening ways.
McPepic 2022-05-27 14:57
What’s really weird is that this doesn’t happen at all in the old version. I still have a backup of it and there isn’t a problem. So somehow, when I organized the functionality into sub programs, this problem started happening.
nathanielbabiak 2022-05-31 14:39 (Edited)
Just realized my response wasn't super helpful.
You need to figure out where the matrix is loosing it's orthogonality and/or unity. Write two debuggers, one for each of these potential issues (although it's likely orthogonality, not unity), and put the debuggers after every transformation of your matrices. Then just step-through the transformations one-at-a-time and check.
Given that the issue doesn't appear in the first few degrees of rotation, I'd guess you're looking at an 'accumulation error'. I can't find a hyperlink for what I mean when I say that, so this explanation may be rough:
Every time you rotate a matrix, rounding occurs. (Not integer rounding, it's rounding to the nearest rational number that can be encoded in floating point format). For example, run this code snippet, and you'll get X=13.5, Y=13.50002.
X = 0
X = X + 0.1 * 135
PRINT "X =", X
Y = 0
FOR J = 1 TO 135
Y = Y + 0.1
NEXT J
PRINT "Y =", Y
So what you need to do then, wherever you find the source of the issue, is forbid re-translation of matrices. To do that, you have to set your rotation matrices per angle values (every iteration of your main loop), and set your vertex matrices per rotation matrices (again, every iteration). (What you can't do is re-use matrices that were translated in a prior iteration of your main loop.)