Hacker News new | comments | show | ask | jobs | submit login

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.




I think Andy Gavin already wrote up quite a lot about those details, here: http://all-things-andy-gavin.com/2011/02/02/making-crash-ban...


I had to make an account to say this, please do the write up! I've been fascinated by crash ever since playing it in the 90s and had that reawakened after reading Andy Gavins blogposts.

Hearing how you managed to squeeze all this stuff out of what sounds like it was an experimental platform for 3D is just amazing.


Seems like that scheme doesn't necessarily solve z-fighting, unless your method also split overlapping polygons something akin to Newells algorithm.

>>I'll leave the matter of weaving the foreground characters -- Crash himself and the other creatures -- into the pre-sorted background for another day.

Please do \drool


We didn't split polygons, and you are correct that this doesn't provide an absolutely perfect solution either. However, it does in practice eliminate the flickery polygons, because the polygon ordering is far more stable than it is with bucketing.

And you can actually see a difference between Crash 1 and Crash 2+ if you pay close enough attention. For Crash 2, Stephen White cloned the PS1's renderer in software for the SGI so that it was pixel-for-pixel accurate. He did this in like two days, thereby earning himself a place in my top-5-programmers-I've-ever-worked-with list.

If you look closely during Crash 1 while you're moving Crash, you can see sometimes see what Andy not-so-affectionately called "crispies". These are pixel-size flickery bits caused by the subtle difference between the SGI's renderer and the PS1's hardware renderer. Just the difference in the way the two implementations rounded fractional coordinates showed up in the game.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: