Varying wall heights in a 3D engine for the TI-83+

Monday, 25th October 2010

I've done a little more work on the 3D engine for TI-83+ calculators that I mentioned in the previous entry. The main difference is in limited support for varying the heights of floors and ceilings, illustrated in the following screenshots.

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

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

Walls now refer to one or two "sectors". A sector is a 2D region of the map of any size or shape; it can be concave or even have holes in it. Walls are also grouped into convex regions named subsectors for rendering purposes. Each wall has a sector in front of it and a sector behind it; these sectors have a specified floor and ceiling height. There are now two types of wall; a "middle" wall which connects the floor and ceiling of the sector in front of it and an "upper and lower" wall which connects the ceilings of the sectors on each side and the floors of the sectors on each side.

This makes occlusion a little trickier and determining where to draw lines around the edges of walls even more so!

Bounding rectangles around walls    Filled trapezia behind wall outlines

The previous version of the renderer worked by drawing walls back-to-front, clearing rectangles the height of the screen behind the wall segments as they were drawn. The first attempt to improve this exchanged rectangles the full height of the screen with trapezia. The screenshot to the left shows the bounding rectangle around each wall segment being filled and the one to the right shows each wall filled as a trapezium. (As before, clicking an image with a border will display an animated screenshot).

'Coloured' trapezia    Variable height walls

Rather than attempt to calculate where lines should be drawn around wall edges I thought I'd experiment with dithered wall fills instead. The left screenshot shows this addition (each wall has a different shade) and the right screenshot shows the addition of support for wall heights (still drawn in the simple back-to-front technique, resulting in significant amounts of overdraw).

Streaky LCD

Unfortunately, the LCD on the calculator copes rather poorly with dithered fills; the above photograph was taken at the highest contrast setting. Rotating the camera to look at walls with a different dither pattern brings the world back into view. This is rather unacceptable, and is something I ran into with my previous implementation. I think I'll stick to stroked wall outlines rather than filled walls.

Wireframe world imported from a C# level

I had been experimenting with a new level design in the C# prototype of the engine that added another room accessible via a tunnel from the starting room. I added some code to the C# program to output the level data in a form that could be assembled into the Z80 version. This is shown above, having reverted to a simple wireframe view in anticipation of the new wall drawing code.

Per-column completed wall counter

The new way to implement occlusion works very differently to the previous one. I had been sorting the geometry from back-to-front and rendering it in order, drawing walls in the foreground on top of walls in the background. This wasn't very efficient and wouldn't scale well. The new approach renders from the front to the back and works on information stored about each column of pixels on the screen. The screen is 96 pixels wide, so there are 96 columns to deal with. A counter is set to 96 at the start of rendering. When a column of a wall is rendered, a flag is set to indicate that that column has been completed and the counter is decremented. When the counter reaches zero, that means that every column on the screen has been completed and the renderer terminates. This is demonstrated in the above screenshot when compared to the previous one; walls that are some distance away from the camera (and behind other wall segments) are not always drawn as the renderer has decided that it has finished before reaching them.

An obvious issue with the above screenshot is that even though some of the geometry is culled, individual walls can still be seen through other ones.

Culled completed columns

Part of the solution is to use a custom line-drawing routine that checks each pixel against the completed columns table. If a column is marked as completed, the pixel is not drawn; if it isn't, the pixel is drawn. This is shown above.

I previously mentioned that there were two types of wall; "middle" walls (solid ones from the floor to the ceiling) and "upper and lower" ones (these have a hole in the middle). Only "middle" walls flag a column as being completed, as you need to be able to see through the hole in "upper and lower" ones. This causes the rendering bugs in the previous screenshot above and below the holes in the wall. The way to fix this is to add two new per-column clipping tables; one which defines the top edge of the screen and another which defines the bottom edge. These both start at the maximum values (0 for the top edge and 63 for the bottom) and are reduced whenever an "upper and lower" wall type is encountered.

Columns clipped against upper and lower bounds

The new code to do this is demonstrated in the above screenshot. There is still, however, a bug in this implementation. The per-column clipping tables are updated by the code that draws the line along the bottom or top edge of the hole in the wall. If this line is partially (or completely) off the screen, these tables are not updated and the rendering bugs appear again (as demonstrated at the end of the above screenshot). A final manual pass over parts of the line that are clipped off the screen corrects the issue:

Columns clipped against upper and lower bounds

As can be seen in the bottom left corner of the above screenshot I have added an FPS counter. This is accompanied by code that scales movement by elapsed time so you move at the same speed regardless of how long each frame takes to render. The engine is quite slow (and could no doubt be heavily optimised by someone who's good at assembly) and has quite a few bugs in it but it's certainly looking a little better than it did a week ago. As I only have a regular TI-83+ I'm aiming for something usable at 6MHz; the more modern calculators can run at 15MHz but this feature is not used in the demo.

For those interested in trying the demo on their calculators, click on the above image to download an archive containing a TI-83+ and TI-83 binary. As before, this is experimental and may well crash your calculator, so please back up any important files first!

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.

Page 5 of 46 1 2 3 4 5 6 7 8 946

Older postsNewer postsLatest posts RSSSearchBrowse by dateIndexTags