Crash Bandicoot Dev on rendering techniques

As seen on Hacker News:
Maybe Andy forgot to mention it; it's been a while since I've read the whole series.
The code was C and lisp so it didn't really require any effort to port other than replacing the rendering pipeline. And we used the SGIs to pre-render every frame anyway, to precompute the polygon sort order. (The PS1 had no Z-buffer, so you were stuck sorting polygons at run-time if you didn't do something clever.)
So we already had the rendering pipeline ported. Obviously you couldn't save your game to the memory card, etc. -- some stuff didn't work. But the game was playable (albeit very frustrating with keyboard controls).
That blows my mind, I always assumed it did have a z buffer. So what did you guys do to remedy 'z fighting' triangles? My interest is; I wrote a 3d renderer in Java using fillPolygon() many years ago, and used polygon sorting in place of a z buffer. Z fighting was of course a problem.

Some day I will write this up for real, but without going into detail, here's a summary.
The camera in Crash was on a rail. It could rotate left, right, up, and down (in Crash 2 and beyond, at least), but could not translate except by moving forward/backward on the rail. This motivates a key insight: if you're only rotating the camera, the sort order of the polygons in the scene cannot change.
This allowed us to sample points on the rail and render the frame at each sample point ahead of time, as a batch job, on the SGI using a Z-buffer. (We may have done the Z-buffer with software; I don't remember.) Then we could recover the polygon order of each frame by looking at the Z-buffer. And, even better, at run-time we could simply not render at all those polygons that weren't ultimately visible in the pre-rendered scene. This solved both the sorting and clipping problem nicely, and made the look of the game closer to 3K polygons/frame vs. the 1K polygons we were actually rendering in real time. (Many polygons were occluded by other polygons.)
The trick, though, was what exactly to do with this sort/occlusion information. In a nutshell, what I did was write a custom delta-compression algorithm tailored to the purpose of maintaining the sorted polygon list from frame to frame, in R3000 assembly language. Miraculously, this ended up being quite feasible because the delta between frames was in practice very small -- a hundred bytes or so was typical. And if a transition was too heavyweight (i.e., the delta was too big) we'd either sample more finely in that area or tell the artists to take stuff out. :)
One thing nobody talks about but which is obvious in retrospect is that without a Z-buffer you're pretty screwed: sorting polygons is not O(N lg N) -- it's O(N^2). This is because polygons don't obey the transitivity property, because you can have cyclic overlap. (I.e., A > B and B > C does not imply A > C). This is why virtually every game from that era has flickery polygons -- they were using bucket sorting, which has the advantage of being linear time complexity, but the disadvantage of being wrong, and producing this flickery effect as polygons jump from bucket to bucket between frames.
I'll leave the matter of weaving the foreground characters -- Crash himself and the other creatures -- into the pre-sorted background for another day.

Comments

Post a Comment

Popular posts from this blog

GLES Quake - a port of Quake to the Android platform

I've just published the source code to a port of Quake to the Android platform . This is something I did a while ago as a internal test application. It's not very useful as a game, because there hasn't been any attempt to optimize the controls for the mobile phone. It's also awkward to install because the end user has to supply the Quake data files on their own. Still, I thought people might enjoy seeing a full-sized example of how to write a native code video game for the Android platform. So there it is, in all its retro glory. (Porting Quake II or Quake III is left as an exercise for the reader. :-) What's different about this particular port of Quake? Converted the original application into a DLL Android applications are written in Java, but they are allowed to call native languge DLLs, and the native language DLLs are allowed to call a limited selection of OS APIs, which include OpenGL ES and Linux File I/O. I was able to make the game work by using Java for: T
Read more

A Taipei-Torrent postmortem: Writing a BitTorrent client in Go

This is a BitTorrent client. There are many like it, but this one is mine. -- the BitTorrent Implementer's Creed For fun I've started writing a command-line BitTorrent client in Google's go programming language. The program, Taipei-Torrent , is about 70% done. It can successfully download a torrent, but there are still lots of edge cases to implement. Go routines and channels are a good base for writing multithreaded network code. My design uses goroutines as follows: a single main goroutine contains most of the BitTorrent client logic. each BitTorrent peer is serviced by two goroutines: one to read data from the peer, the other to write data to the peer. a goroutine is used to communicate with the tracker some "time.Tick" goroutines are used to wake the main goroutine up periodically to perform housekeeping duties. All the complicated data structures are owned by the main goroutine. The other goroutines just perform potentially blocking network I/O using channel
Read more

A Multi-threaded Go Raytracer

Image
Above is the output of the raytracer. Below is a diagnostic mode showing which goroutines raytraced which section of the screen. Each goroutine has its own color to outline the pixels it traces: I wrote a simple multi-threaded ray tracer in Google's new "go" language. It's an adaptation of Flying Frog Consultancy's Raytracer . It runs single-threaded about 1/2 the speed of a comparable C++ version. I guess the C++ version benefits from a more optimizing compiler and the ability to inline small functions. Compared to ordinary C/C++, the Go version was easier to multithread. On my dual-core Macbook Pro I get an 1.80x speedup when running with GOMAXPROCS > 1: $ GOMAXPROCS=1 time ./gotrace 1.52 real 1.50 user 0.01 sys $ GOMAXPROCS=2 time ./gotrace 0.82 real 1.50 user 0.01 sys $ GOMAXPROCS=3 time ./gotrace 0 .81 real 1.50 user 0.01 sys On an eight-core, 16 Hyperthread HP Z600 running Ubuntu 9
Read more