Simple 3D graphics on an AtMega microcontroller

Go To Last Post
18 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

So this is a small thing I've been working on over the past few days. The basic Idea at the start was: Could I program a graphics engine that could render a simple 3D scene using only the limited amount of memory, processing power and program space available on my trusty old Atmega1284p? Now, even though it is obviously impossible to render complex 3D models on an AVR, I still wanted to be able to render a scene with multiple objects in it.

However, the fact that I won't be able to use any real 3D models meant that I would need to restrict myself to a few, mathematically easy to define shapes as the "building blocks" and construct my scene out of these, as if I was building with Lego. The first thing that immediately came to my mind was a voxel engine. Basically, the entire scene would consist of a regular grid of cubes (voxels) that could each have a different color or even full texture, that I could then use to build a more complex scene. I already had experience with creating such an engine, so I went with this Idea. Theoretically, however, it should be possible to render objects other then cubes, such as spheres. However, the more different objects that can be rendered, the longer it will take to render the scene, so I decided to stick with only cubes for now.

Now, I obviously needed an algorithm to actually render the scene. Now, I know that Rasterisation would be way too resource intensive and too difficult to implement on a Microcontroller. So I decided to go with ray marching.

Basically, for each pixel that needs to be rendered, the renderer "shoots" a ray/vector out from the position of the camera at an angle that is calculated from the position of the pixel in the image, which then moves forward in steps until it hits a voxel, at which point the color of the pixel is set to the color of the voxel. Or you could calculate the exact coordinates at which the ray intersects whatever side of the voxel it hit and sample a texture at those coordinates, which is what I ended up doing.

Now, normally, Rasterisation is much faster then ray marching, however, ray marching becomes extremely efficient if your entire scene consists only of axis-aligned cubes of the same size. It also uses barely any RAM (less then 1KB), which leaves a lot of free memory for storing the scene and textures for the voxels, which makes it perfect for running on an AVR.

So I went to work. And after three days of testing and debugging and optimizing all the code, I created a program, less then 1000 lines in length, which uses a ray marcher to render a pre-defined scene and save the final result to an SD card in the form of a bitmap image. I spent a lot of time optimizing the code as much as possible, but I still expected the render to take at least an hour on such a slow processor, even at a resolution of 160 by 128 pixels. So you can imagine how surprised I was when it finished in 20 seconds!

Yeah, turns out you can render things quite quickly with this.

As for what the render actually looks like, well, here's on more thing: I suck at making textures, so I borrowed some from a video game I used to play a lot, and...

I basically made Minecraft for AVR microcontrollers.

But interestingly enough, you could almost make a game out of this. There are variables in place to move and rotate the camera. All you'd need to do to make this a playable game is to slap a color LCD onto an AVR, add buttons for controls, and....find a way to make this take at most half a second to render. Yeah, I'm still working on that last part. I'm sure a faster Microcontroller could probably do it, but I'm not aware of any faster AVRs that I could easily try this with.

For the time being, however, I quickly edited the code to render 40 separate frames, with the camera's Y-rotation being increased by 9 degrees before each new frame. This only took a little less then 10 minutes, and afterwards I edited all the frames together into a gif:

So that's pretty neat. However, you might think that the image is still pretty pixelated because of the low resolution. However, rendering a frame at a higher resolution doesn't really take longer then a few minutes either, so here's the scene in all its glory:

However, at this resolution you might begin to notice some minor glitches, especially at the corners of blocks. That mostly has to do with the fact that I optimized the algorithm for speed, and not for precision. I believe the glitches are mostly caused by the renderer's use of fixed-point arithmetic. However, these glitches become less and less noticeable at lower resolutions, which is also what the renderer is optimized for due to the low-resolutions of most SPI LCD screens (I do not currently own one of those, which is why I'm rendering to an SD card, but I might buy one soon).

 

If you want to try this for yourself or maybe render your own scenes, I put the source code up on pastebin. It's only two files:

https://pastebin.com/tjqP60Ge

and

https://pastebin.com/pSRPph2R

 

there's a few settings you can modify at the beginning of the main function. One of them is called stepResolution. This basically defines the minimum length of the steps a ray can take as 1 / stepResolution. So a higher value will remove more of the glitches in the render at the cost of performance. Though setting this to anything higher then 20 without switching to floating point arithmetic, which you can do by adding the line '#define FLOATING_POINT' at the beginning of the file, will cause the render to fail horribly. You can also change the size of the world, but increasing its size will also increase RAM usage, so keep that in mind. Oh. Speaking of RAM, you WILL need an AtMega1284p for this. The compiled program is 35KB and probably uses almost all of the AtMega1284p's 16KB of RAM. So something like an AtMega32 will simply not cut it.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Nice project!  If you want more RAM, up to 64K is

possible using the External Memory Interface of

such chips as the Mega 2560.

 

--Mike

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

How cool!

 

If you end up looking for a faster uC, then know that the Xmegas run at 32 MHz in spec, and have been (easily) over-clocked for programs that don't use the EEPROM or the analog functions.

(Over-clocking is simply a matter of changing the PLL multiplier!)

 

Good luck with the next upgrade to your project!

 

JC

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I love this project. It's always fun to reduce bloated code to it's simplest minimalist form.

 

Constant data structures like textures and maps shouldn't be stored in RAM. Move them to flash. Look into using PROGMEM. This will free up RAM. I suspect that will be the most limiting commodity in the end.

 

You'll never get reasonable performance using floating point on the AVR. So, you should plan to ditch that.

 

Another detail will be the CPU cycles and RAM required to add the LCD interface. But, no need to get into those details just yet. I like your approach so far.

 

It's not a lost cause. I suspect you can get something working reasonably if you simplify the world modeling enough. Wolfenstein 3D ran at decent frame rates on a 10 mHz 80286 back in the day.

 

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

RacerXR wrote:

Constant data structures like textures and maps shouldn't be stored in RAM. Move them to flash. Look into using PROGMEM. This will free up RAM. I suspect that will be the most limiting commodity in the end.

I did actually try moving the textures into flash at one point, but it slowed things down quite noticeably, and it's not like I had a shortage of free RAM with the renderer using less then 1KB. As for the world/map, it has to be in RAM, simply because it is accessed more often then the textures. The renderer only needs to sample a single RGB value from a texture per pixel (if at all), but the world data is read from several hundred times per pixel at least. Moving the world to flash would slow down the renderer a lot.

 

RacerXR wrote:

You'll never get reasonable performance using floating point on the AVR. So, you should plan to ditch that.

Ditching floating-point for fixed-point maths was one of the first things I did, which definitely made things a whole lot faster. I only added the option to switch back to floating-point maths to my code because I thought using them might yield better image quality, but I'm starting to doubt that at this point.

RacerXR wrote:

It's not a lost cause. I suspect you can get something working reasonably if you simplify the world modeling enough. Wolfenstein 3D ran at decent frame rates on a 10 mHz 80286 back in the day.

If I remember correctly, the 80286 did have a floating point unit or a coprocessor with one. So it's already at an advantage just because of that. And I haven't yet heard of an AVR with an integrated floating point unit. But that thought did give me another Idea: what if there's some sort of floating-point coprocessor I could throw at a microcontroller? So I'm looking into that right now. Might be worth a shot

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I was taking a quick look to see if the Xmegas had a hardware multiplier, but I don't see it listed on their cover page.

 

Clearly there are PIC micros with multiply and add instructions, IIRC, aimed at digital signal processing.

 

Clearly you could move up to an Arm processor, but what's the fun in that?

(Might as well just run the code on your PC!)

 

There was a stand alone FPU chip, years ago.

IIRC there was quite a bit of overhead in loading its registers with the data to process, and then reading the results back into the primary uC.

The chip I'm thinking of was a small chip aimed at being integrated into small uC systems, it was much smaller than the 8087 which was designed to be used with the 8086 and 8088.

 

I can't recall its number, but likely another Forum member will recall the chip, and perhaps even still have a few in their parts bin!

 

JC

 

Edit:

The uM-FPU is a chip that does 32 bit floating point math and a few other things.

It has an I2C or SPI interface to the main processor.

I can't think of the number for the earlier version of this sort of chip.

 

Here is a link to the uM-FPU V1.

It is an 8-Pin Dip, and is, I think, what I was thinking of.

 

 

Last Edited: Mon. Feb 25, 2019 - 04:10 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

first a 80286 needed a 80287 to have FP. (as I remember the 80486 DX was the first with buildin FP (there was a SX without)).

 

Which display do you use ? (some displays you can upload a bigger picture than you see so pan only is a pointer change.)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

TheGhastModding wrote:
... and it's not like I had a shortage of free RAM with the renderer using less then 1KB.
32KB of local RAM for the two XMEGA384.

XMEGA data space is 16MB; one post here about, IIRC, one additional clock cycle to access XMEGA EBI SRAM (XMEGA EBI SDRAM may have less latency due to bursts) (ATxmega128A1U)

TheGhastModding wrote:
I only added the option to switch back to floating-point maths to my code because I thought using them might yield better image quality, but I'm starting to doubt that at this point.
IIRC, it's fractals where "dust" appears due to fixed-point arithmetic.

Fixed-point is either precision or range (not both)

TheGhastModding wrote:
But that thought did give me another Idea: what if there's some sort of floating-point coprocessor I could throw at a microcontroller?
Alorium Technology has a single precision arithmetic FPU (no trig ops) for a near mega328P.

pico RISC-V doesn't consume much of some FPGA; there's likely a RISC-V ISA extension to add floating-point.

 


XMega cranks out NTSC color and digital stereo sound! | AVR Freaks

https://gcc.gnu.org/wiki/avr-gcc#Fixed-Point_Support

Floating Point Math - Xcelerator Block | Alorium Technology

SoCs - RISC V Cores and SoCs · riscv/riscv-wiki Wiki · GitHub

 

"Dare to be naïve." - Buckminster Fuller

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

That rendering is pretty cool, certainly a lot of computations involved.  A slight tweaking of the method can make all of the speed difference.

Several folks have created "minimalist graphics", using just the AVR to generate both video timing, graphics & sound.

This is performed on a mega88  & is rather amazing:

https://www.youtube.com/watch?v=sNCqrylNY-0

 

Some graphics tricks/tips might be gleaned here:

https://www.linusakesson.net/scene/craft/

 

More recently, someone posted using a tiny13 (?) for some neat graphics

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This is an impressive project, good luck! I'm considering doing fake 3D on something like the pic32 on which I've done some simple 2D graphics. But I need to learn more about transforms. Any reason why you went with the voxel approach rather than polygons? 

Last Edited: Wed. Nov 27, 2019 - 03:38 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

erisan007 wrote:

This is an impressive project, good luck! I'm considering doing fake 3D on something like the pic32 on which I've done some simple 2D graphics. But I need to learn more about transforms. Any reason why you went with the voxel approach rather than polygons? 

 

Because testing the intersection between a cube and a ray is mathematically and computationally easier then testing the intersection between a ray and a polygon inside a larger 3D model. Plus, since all the cubes are axis-aligned and the same size, spacial partition of the game world kinda happens on its own, and you can do a whole bunch of optimizations with that.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

TheGhastModding, Do you feel up to the challenge of porting that to the Uzebox?  I can send you some hardware if you think you can give it a shot :)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0


Someone could do a remake of Driller for the AVR. This was the first solid-3D game I played, back in the 80s, on my ZX Spectrum. If a Z80 can do it, surely an AVR can do better.

 

edit: well, let me add a pic of the game, these days it would be categorized as an FPS.

 

Last Edited: Thu. Nov 28, 2019 - 03:17 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0


 

While I liked a lot of "3D games" on Spectrum/Amstrad such as NightLore

 

 

and other isometric 3D games from "Ultimate Play the Game" there will always be a very special place in my heart for Sandy White''s "Ant Attack" which was truly era defining!

 

 

I remember when I first saw/played it I couldn't believe what I was seeing.

 

Last Edited: Thu. Nov 28, 2019 - 01:19 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

El Tangas wrote:

Someone could do a remake of Driller for the AVR. This was the first solid-3D game I played, back in the 80s, on my ZX Spectrum. If a Z80 can do it, surely an AVR can do better.

 

edit: well, let me add a pic of the game, these days it would be categorized as an FPS.

 

 

El Tangas, I have a video mode on the Uzebox that would be perfect for Driller/Total-Eclipse and other freescape games.  It is 256x224 pixels x 256 colours and is internally described as a list of polygon edges.  It only uses about 1KB of the 4K RAM available and gives heaps of "user time" for the game code to run.  This is a static screen shot of what it can do.

 

 

clawson wrote:

 

While I liked a lot of "3D games" on Spectrum/Amstrad such as NightLore

 

 

and other isometric 3D games from "Ultimate Play the Game" there will always be a very special place in my heart for Sandy White''s "Ant Attack" which was truly era defining!

 

 

I remember when I first saw/played it I couldn't believe what I was seeing.

 

 

 

I'd say Batman and Head-over-Heals are the pinnacle of that genre :)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I used to be a regular writer of reviews in Amstrad Computer User ( https://en.wikipedia.org/wiki/Amstrad_Computer_User ) and even went as far as writing a map editor for KnightLore (hacking the copy protection to "get in" was "fun"!!) and while I agree that Batman and Head-over-Heels were good they tended to be a bit "me too". But a game like Ant Attack was truly revolutionary when it first appeared. 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:

I used to be a regular writer of reviews in Amstrad Computer User ( https://en.wikipedia.org/wiki/Amstrad_Computer_User ) and even went as far as writing a map editor for KnightLore (hacking the copy protection to "get in" was "fun"!!) and while I agree that Batman and Head-over-Heels were good they tended to be a bit "me too". But a game like Ant Attack was truly revolutionary when it first appeared. 

 

Ah cool.  I still have about 60 copies of ACU upstairs.  My favorite straddy game was Spindizzy.  I believe all the info for the map on it is available online so I should be able to make a port of it to the UzeBox if I get my ASM on to write a suitable video mode.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Wonderful project! Thank you for sharing it. I recently started playing Minecraft, and that was only because my kid got so into the game that he started learning programming languagesWonderful project! Thank you for sharing it. I recently started playing Minecraft, and that was only because my kid got so into the game that he started learning programming languages. That's wonderful. A common children's game that most parents underappreciate teaches kids the basics of programming. I would never have thought that was possible. Nowadays, various servers carry with them bad content for a child. So I found the site servers-minecraft.net, where safe servers are collected for minors and the computer. No viruses and bugs. I advise you to try it.

Last Edited: Mon. May 16, 2022 - 06:29 PM