A primitive 3D engine for the TI-83+

Sunday, 17th October 2010

As you may have guessed from the number of spinning cubes in my projects, I am quite fond of primitive 3D. As you may also have guessed from the number of TI-83+ calculator projects I have undertaken, I'm also quite fond of programming on low-end machines. I have never really successfully put 3D and the TI-83+ together, though.

TI-83+ Raycaster

One way to build a 3D world in software is raycasting (e.g. Wolfenstein 3D). This typically results in blocky worlds where all walls are at 90° angles to each other. There are several games using raycasting engines on the TI-83+ already; they are much faster and better-looking than my sorry attempt pictured above.

TI-83+ 3D 'Quake'

Another method is to use true 3D geometry (e.g. Quake). Many years ago I attempted to work on something that looked a little like Quake. I built this on the Matt3D engine, which supported basic 8-bit coordinates and lines, but not solid objects. The result was even less useful than the above raycaster!

Attempt at a 2.5D engine.

Another method somewhere between the two is a "2.5D" engine, where level geometry is defined between points in 2D space but projected in 3D (e.g. DOOM). This allows for walls that are not at 90° angles to each other, whilst simplifying the rendering procedure significantly. I spent some weeks working on such an engine a few years ago yet never managed to get any further than the above screenshot. As you can probably tell from the fact that you can see the walls through each other I never found a good way to handle occlusion, and the project ended up stagnating.

TI-83+ 3D engine screenshot    TI-83+ 3D engine screenshot

TI-83+ 3D engine screenshot    TI-83+ 3D engine screenshot

Looking for a quick weekend project I thought back to the work I'd done with the DOOM and Quake engines. These engines use a BSP tree structure to sort the level geometry for rendering. I reckoned that if simplified a little a similar tree structure could be used to render a 3D world on the TI-83+ calculator. The four screenshots above show that this technique is indeed quite successful. My implementation could certainly do with a lot of work but I think the theory is at least sound.

Target level for the BSP renderer.

I decided that one way to make this project a bit more fun was to set myself a challenge; to design a level that I would, ultimately, be able to walk around in. This level is shown above, and contains a number of walls that are not parallel to the X or Y axis and a pillar. I have split the world into eight convex "sectors" (labelled 0 to 7) with a dotted line between them to show where the BSP tree is partitioned. All of the partitions are either horizontal or vertical to speed up tree traversal; the TI-83+'s Z80 CPU does not support floating point arithmetic, let alone multiplication or division, so being able to decide which side of a partition you're on quickly is very useful.

C# prototype of the BSP renderer

Rather than dive straight into Z80 assembly programming I knocked together a quick prototype in C#. This allows for quick and easy debugging; the blocks of colour allow me to quickly identify walls and the application title bar contains the order in which the sectors have been rendered. These can then be checked against the version running on the TI-83+ in case there are problems.

Vertex transformation

With the C# version running satisfactorily I started converting it to Z80 assembly. The above screenshot shows the first step; transforming the level's vertices around the camera. Clicking on the screenshots will take you to an animated version; as some of them are quite large I have linked to them rather than embedding them directly.

BSP tree traversal

The next step was to traverse the BSP tree. The numbers across the top of the screen indicate the order in which to render the sectors, from back to front — however, due to a simple bug, they are actually listed from front to back. This was fortunately very easy to fix.

Walls

Walls are connected between the vertices, so I quickly threw something together to display all of the walls on the screen. The walls will have to be clipped against the camera's view (or discarded entirely if they are outside the view) so being able to see them is a great debugging aid!

Clipping against Y=0

We are only interested in drawing walls that are in front of the camera, so the first bit of clipping code deals with clipping the walls against Y=0.

The above screenshots show the final three stages of clipping to the camera's view, defined by Y>0, Y>+X and Y>-X. The first screenshot shows culling of any wall that does not satisfy this in any way; walls that are completely outside the view are discarded. The second screenshot shows walls being clipped against Y=+X, and the third finally adds clipping against Y=-X. The lack of hardware floating-point arithmetic makes the code fairly slow and ugly but it does seem to be working relatively well.

Backface culling

We are only really interested in dealing with walls that are facing the camera; we don't want to draw the back of walls. To work out which we want to keep and which we want to ignore, we project the wall to the screen and check whether its projected start vertex appears to the left or the right of its end vertex.

Perspective projection     Perspective projection with ceiling-to-wall lines

A simple perspective projection is performed to turn this clipped 2D world into what appears to be a 3D one. The X coordinate of each vertex is divided by its Y to get the X coordinate on-screen and the height of the wall is divided by the vertex Y to get the Y coordinate on-screen. The left screenshot shows the top and bottom of wall edges; the right screenshot adds lines between the floor and the ceiling to produce a more convincing "wireframe" view of the world.

Solid walls

The final step is to make the world appear solid, by hiding walls that are far away behind walls that are closer to us. Traversing the BSP tree gives us the order in which to draw the walls, so all that is required is to draw solid quadrilaterals for each wall rather than the lines around its outside. A fast clipped quadrilateral filler would take me some time to write so I cheated by drawing a solid white rectangle the width of the wall and the height of the entire screen before drawing the wall outlines. As the camera is half-way up each wall and all of the walls are the same height there are no cases where a foreground wall only partially covers a background one so this trick works for the time being.

I'm glad I achieved my goal of walking around the 3D world I'd sketched in pencil at the start of the weekend but I'm not sure where I'll be able to take the project now. Turning it into a useful 3D engine for a game would certainly require a lot of work. The level and its BSP tree were generated by hand, which would not lend itself well to anything but the simplest of levels. However, the lack of variation in wall heights produces fairly dull levels in any case; DOOM-style levels would be something to strive for, but I'm not sure how well the calculator would be able to cope with them. I'm also unsure how well the engine would scale; this very primitive version only achieves around 12 FPS on a 6MHz TI-83+. It's certainly given me something interesting to think about!

If you would like to try the program on your calculator, please download Nostromo.8xp. It requires an Ion-compatible shell to run. It is very primitive, likely to be quite buggy (you may encounter rendering bugs when very close to walls due to integer overflow in the clipping and projection code) and may well crash your calculator; please back up any important files before running it. Use the arrow keys to move around, Trace and Graph to strafe and Clear to quit.

TV Demonstrator for TI calculators

Monday, 11th October 2010

I've been tinkering with a number of small projects recently. I've resumed work on an LED clock for my bedroom (using a 32×8 LED display) and written an experimental BASIC interpreter in C# which I may try to turn into an assembler (implementing assembly statements as BASIC ones). In the mean time, I have finished one project — a device to display a calculator's screen on a television set.

TV Demonstrator showing the STAT PLOT settings on a monitor.

Texas Instruments also manufacture a product that allows you to view the screen contents of a calculator with supported hardware on a TV; here is a video demonstrating it. The additional hardware (either on special "ViewScreen" calculator models or built into the more advanced calculators such as the TI-84+) allows the device to mirror what is sent to the calculator's LCD in real-time.

I do not have one of these calculators, just a plain old TI-83+. However, this calculator (as well as the older TI-83 and TI-82) allows you to capture a screenshot over the link port. Pressing a button on my device captures a screenshot in this manner and displays it on the TV. This relies on the calculator being in a state where it can respond to these screenshot requests, so is not ideal, but considering that the TI Presenter costs $300 and relies on special hardware inside the calculator and mine should cost less than a tenth of that in parts and work with older calculators I think it's a decent compromise.

I had previously believed that NTSC composite video signals used a negative voltage for sync pulses. I have since found documents that indicate that the sync, black and white levels are the same as those for PAL. The timing is, naturally, different but as there's no need to change the hardware it makes supporting both NTSC and PAL relatively straightforwards. This contraption can be set to operate in either NTSC or PAL mode by sending the real variable M to it from the calculator, with a value of 60 for NTSC and 50 for PAL.

I acknowledge that this is not the most useful of projects (unless you're a maths teacher with an interest in electronics) but the code may be of interest for other projects. A handful of inexpensive parts can get you a picture on a TV from a 96×64 monochromatic frame buffer (the 1KB RAM on the ATmega168 doesn't allow for much more, alas).

More information and downloads can be found on the TV Demonstrator project page.

A parallel port and a demonstration of the Z80 computer

Sunday, 5th September 2010

The last piece of hardware to add to the computer was a parallel port. These have eight data lines and nine assorted control and status lines. My last two 8-bit I/O expanders provide sixteen of these seventeen lines, and the final one was provided by the DS1307 real-time clock chip which happily has a spare pin on it that can be used as an output.

Parallel port I/O expanders Parallel port connector

This parallel port can be used to print from the computer. Some software has printing capabilities built in (such as the text editor VEDIT Plus), but by pressing Ctrl+P in CP/M any text sent to the display will be simultaneously sent to the printer.

I also needed to mount the LCD inside the case. I bought a plastic strip to try to make a nice frame for it, but couldn't cut it accurately enough by hand so have had to make do with merely sticking the LCD behind a rectangular hole cut in the aluminium. It's not the neatest arrangement and doesn't protect the LCD from scratches but is better than nothing.

To demonstrate the computer's hardware and software, I recorded a video:

I'm not desperately happy with the way it came out; I really need to find a better microphone and the angle of the sun and variable weather when I made the video threw the white balance off. On the plus side, I did find out how to capture crisp black and white video with my TV capture card; I connected the composite video output from the computer to the luma pins on the S-video input on the capture card, then dropped the saturation to zero in VirtualDub. For some reason this produces great quality video, in comparison to the composite input which produces a fuzzy mess — there shouldn't really be any difference with a black and white signal (regular television sets don't have any problems).

A clock and a serial port for the Z80 computer

Tuesday, 17th August 2010

At the end of the previous entry I mentioned that I was going to start developing my own programs for the Z80 computer. The first is a graphical clock, taking advantage of my implementation of the BBC Micro's VDU commands and the ability to use those commands to draw graphics onto the screen as well as text:

Graphical analogue clock for CP/M 3

I have uploaded the code and binary to my site for anyone who is interested, though it will only work on a machine running CP/M 3 and that is equipped with a display that implements a handful of BBC Micro VDU commands.

The computer features a display for output and a keyboard for input which is sufficient if you're interacting with a human but it's often nice for computers to be able to speak to eachother, so I've added an RS-232 serial port.

RS-232 driver and port from the inside

RS-232 is a bit of an unfriendly beast. Whereas the computer's logic uses 0V to indicate a logic low (0, "false") and 5V to indicate a logic high (1, "true") RS-232 uses around +12V for a logic low and -12V for a logic high. This requires that the outgoing signals are inverted and boosted and the incoming signals are inverted and reduced to protect the inputs of the receiver circuit. Fortunately you can easily get hold of chips that perform this task for you when aided by a number of capacitors; in my case I'm using an ST232, which is shown in the bottom left of the above photo. A DE-9M connector is provided on the outside of the case, much like the one you'd find on your desktop if you were trapped in the 1990s.

One issue I have yet to solve is handshaking. The serial port sends or receives data on two wires (TXD and RXD respectively). The receiver has to handle each incoming byte from the transmitter. As the receiver may be busy performing other tasks at the time it may end up receiving data faster than it can process it and it will start losing bytes. There are a number of different ways to avoid this problem. The simplest electronically is to use XON/XOFF handshaking; in this configuration, the receiver can send the XOFF byte to the transmitter when it's busy and the transmitter will stop sending data temporarily. The receiver can then send XON back to the transmitter when it's ready to receive more data. This technique has one major drawback — it prevents you from sending binary data containing the XOFF or XON bytes.

An alternative solution is to add two wires to the serial connection — Request To Send (RTS) and Clear To Send (CTS). These can be used to signal when each device is available to accept data. This allows you to send XOFF and XON directly over the serial port (extremely useful for binary data) yet requires the addition of two more wires to the port.

Unfortunately whilst implementing both techniques is possible, CP/M only internally refers to XON/XOFF handshaking; there is no way to select RTS/CTS handshaking. I think what I will end up doing is have CP/M's XON/XOFF refer to handshaking in general and then add a hardware-specific utility that lets me choose which particular type of handshaking I wish to use. This utility could also help me select other serial port configuration settings that CP/M doesn't expose (such as parity, number of stop bits or number of data bits).

Z80 computer session in PuTTY

With the hardware installed, the AVR I/O controller updated to use it and the BIOS reprogrammed to expose it to CP/M it is possible to interact with other computers over the serial port. CP/M features five logical I/O devices: CONIN and CONOUT for general console input and output, AUXIN and AUXOUT for general "auxiliary" output and LST for printer output. The BIOS exposes two physical devices; CRT for the keyboard and video display controller and RS232 for the serial port. By using the DEVICE utility you can connect these logical and physical devices together. In the above screenshot I have connected the serial port to both CONIN and CONOUT. This allows me to connect my desktop PC to the Z80 computer using a null modem cable and use terminal emulation software (such as PuTTY) to talk to it.

Simulated BBC Micro VDU mirroring console output

The above screenshot shows VirtualDub capturing the output of the video display controller next to an instance of BBC BASIC for Windows which is running the following program:

aux%=OPENIN("COM2: baud=9600 parity=N data=8 stop=1")
REPEAT
  REPEAT:UNTIL EXT#aux%
  VDU BGET#aux%
UNTIL.

This passes any data received over the serial port to the simulated VDU in BBC BASIC for Windows. As both video devices accept the same commands the result is that both show approximately the same thing.

I have been slightly improving the video display controller as I've gone along. One feature I had to add for the clock was the ability to draw text characters at the graphics cursor position, as opposed to the fixed text grid (this is used to draw the numbers around the dial). At the same time I added the ability to redefine the appearance of characters. One obvious use of this feature is to change the font, but when combined with the ability to render text anywhere on the screen some simple sprite-based games could be written for the computer. Each letter is just a 8×8 pixel sprite, after all.

MODE 2

Another feature I added was a simple implementation of MODE 2 where characters are stretched to sixteen pixels wide. You can't get much text on the screen in this mode but it may be useful for games.

A useful Z80 computer in a project box

Saturday, 14th August 2010

Work continues on the Z80 computer. The two final modifications to the box itself are the holes for the status LEDs and the power switch.

Status LEDs Power switch

The green LED indicates power and the orange one disk activity. Unfortunately, the project box is fairly scratched on the outside (one scratch on the front is my own fault, but the sides and back were fairly scuffed and scratched when I bought it). If anyone has any tips for polishing scratches out of ABS I'd be glad to hear them; the usual household polishing abrasives (such as toothpaste) remove most of the light scuffs and result in a lovely mirror finish, but don't do anything to the deeper scratches. I'll probably invest in the finest grade wet-and-dry sandpaper I can find and have a go with that followed with a Brasso polish, and if that doesn't help (or makes it worse) just sand the whole thing down and paint it.

Pin header connector

The circuit board inside the case needs to be attached to the case-mounted components somehow. In simpler projects I've resorted to soldering these connectors directly to the board, but this can make maintenance a problem (to remove the circuit board one would have to cut and resolder the wires). For this project I've left pin header strips on the board. The external connectors have leads soldered to them terminated with pin headers cut to size using some wire cutters and a rotary tool to polish them off; these headers are pictured above.

Circuit board mounted inside the case

The main circuit board can then be easily installed or removed from the case as required. The small circuit board for the video display controller is connected to the main circuit board in the same way.

Z80 and SRAM pin numbers marked

A Z80 computer can't live up to its name without some sort of a Z80 inside it, so I thought that that was the most obvious part to add next. Computers also generally need access to memory so I decided to add the 128KB SRAM chip at the same time. The Z80 communicates with the memory over an eight-bit data bus, a sixteen-bit address bus (to indicate which address in memory it is reading from or writing to) and a number of control lines (to indicate whether the current operation is a memory read or a memory write, for example). This provides a fairly tedious amount of soldering work; each pin on the memory needs to be connected to the corresponding pin on the Z80. To aid in the construction I stuck masking tape to the bottom of the perfboard around the outline of where the two chips would go and wrote the pin numbers onto the tape, shown in the photograph above.

Z80 and SRAM address, data and control buses

I put the two chips close together so I could put all of the bus wires on the inside of the IC holders rather than going around the outside. This saves a bit of space and avoids having to route the wires around the chip holders which gets a little untidy. The above photograph shows all of the wires in place before the chip holders were soldered in. Adding those in should be a quick and easy job, at least...

SRAM IC socket soldered in the wrong way around

Well, you'd have thought so, but somehow I managed to solder in the 32-pin SRAM socket the wrong way around. Each socket has a notch to help you align the chip using its corresponding notch. As you can see in the above photo the notch points right when it should point left like all of the other sockets. It wouldn't affect the operation of the circuit (as long as the SRAM chip was inserted with the notch to the left) but it looks untidy and I may as well do the job properly.

SRAM IC socket soldered in the correct way around

On the positive side I suppose I got to practice my desoldering skills.

Z80 and AVR data bus connections

The computer design uses an AVR microcontroller to manage the I/O devices (such as the keyboard, video display controller and SD card) and to load the OS into the Z80's memory on reset. To achieve this the Z80 and the AVR need to be connected together. The above photograph shows some new wires between the AVR (bottom left) and Z80 (bottom middle) to connect the Z80's data bus to the AVR's PORTA and a number of other wires to connect the Z80's control lines to several other I/O pins on the AVR. A number of pull-up resistors have been added to control lines on the Z80 so that when nothing is driving the control bus they rise high (the de-asserted state). If left disconnected ("floating") the other components connected to the control bus may think these lines had gone low (asserted) and treat that as a read or write operation, corrupting data.

I/O expanders Soldering detail of the I/O expanders

The AVR also needs to be connected to the Z80's address bus. This would take another sixteen pins if driven directly by the AVR; sixteen pins that aren't available to me! I am therefore using two MCP23S08 eight-bit I/O expanders, pictured above, to drive the address bus from the AVR. These are controlled over the SPI bus, which only takes up three pins on the AVR (these pins are shared with other SPI peripherals, such as the SD card) plus a single chip select pin that is unique to the I/O expanders. Four pins is better than sixteen, at any rate.

All ICs to date installed Computer in its project box

I keep mentioning chips even though the sockets are quite clearly empty in the above photographs. As I was approaching a useful computer circuit at this point I plugged all of the chips into their sockets to test the connections. As there was no SD card, real-time clock or keyboard I had to modify the boot loader on the AVR quite considerably; I started with a test program that wrote random data to blocks of memory then read them back to verify that they had written correctly. Once I had verified that the AVR was able to access memory correctly I reprogrammed it to copy a small Z80 program to memory and then let the Z80 take over. This Z80 program repeatedly output the string 'Z80' to the console output port. With everything plugged in I switched on the computer and saw the screen fill with Z80Z80Z80… so I was pretty certain that I'd wired everything up correctly!

DS1307 and battery clip

At this point I could start reintroducing the various peripherals to the computer. A DS1307 is used as a real-time clock. This clock needs to keep running when the computer is switched off, so I've added a 3V battery connector to the computer to keep it ticking.

SD card slot

As the computer uses a 512MB SD card for storage, I have added a pin socket strip to the board to plug in the SD card slot I scavenged from a card reader. The card is connected to the SPI bus along with the I/O expanders used to drive the Z80 address bus. SD cards run at 3.3V rather than the 5V that nearly everything else on the board uses so I've used a series of voltage dividers to drop the voltage on each input pin from 5V to around 3V (the resistor values I have don't allow me to get to 3.3V; 3V is the closest I can manage without going over 3.3V). The video display controller board also runs on 3.3V so I do at least have a suitable voltage supply for the card!

Keyboard connector

The final part of the computer that was on the breadboard prototype but not yet in the final build was the keyboard connector. This is simply a four pin header on the board that is connected to the PS/2 port screwed to the case. However, when I tried to use the computer, the keyboard didn't appear to work. Pressing Num Lock, Caps Lock or Scroll Lock would toggle the associated LED and hitting Ctrl+Alt+Del would reboot the computer but no other key worked. This implied that the AVR was handling the keyboard correctly but the Z80 wasn't receiving any notification of key presses. A bit of digging identified the problem; I'd forgotten to connect the Z80's interrupt pin to the AVR! When a key is pressed the AVR triggers an interrupt to let the Z80 know that a key is available. By soldering a wire between the two chips it started working as intended.

Z80 computer in its enclosure

The computer is now up to the same standard as it was when assembled on the breadboard, but is much more practical to work on. I hope to add a serial and parallel port to the computer soon, and would like to mount an LCD into the lid of the project box, but for the time being I am happy that I have managed to get this far.

Z80 computer running VEDIT

One of the advantages of running CP/M on the computer rather than my own operating system is the availability of existing software. The above photograph shows the computer running VEDIT, which is an excellent visual text editor.

VEDIT for CP/M

Zork for CP/M

With the hardware in a decent configuration I can start writing my own software. I think the first CP/M program I'll write is a graphical analogue clock, as this is the sort of program that can be left running for long periods as a way to check the stability of the computer.

Page 7 of 48 13 4 5 6 7 8 9 10 1148

Older postsNewer postsLatest posts RSSSearchBrowse by dateIndexTags