Quake 2 on Falcon030

[dml]

Ok so while I have stopped improving on the code for now, I couldn't leave it completely alone - another vid testing the well known q2dm1 deathmatch map.

https://www.youtube.com/watch?v=OzkzWGt ... 5nMm10m0UM

It's sometimes hard to see where you're going in wireframe, when you can see stuff through walls. I run into dead-ends a few times, not quite remembering where stuff is.

I have downloaded a few of the old favourite DM maps, some of which are much better optimized for gameplay than the originals, just to see how the Falcon copes with those. Many of them are small, compact maps with nice architecture. If I get time later I'll upload another vid using one of those to compare.

[Zamuel_a]

Would it be much work to implement a simple flat shaded polygon routine? Just as a test to see how it would be without the wireframe graphics.

[dml]

Would it be much work to implement a simple flat shaded polygon routine? Just as a test to see how it would be without the wireframe graphics.

That will be done - at least once all the problems with upper-mid level of the geometry pipeline are fast enough to move on to the next stage. It's getting quite close to that now.

Implementing the final filler even for flat polys is going to take time though, because the complexity is quite high. There is a lot of code involved on the DSP side and some CPU/DSP work sharing design needed.


I could perhaps do a 'dummy' filler before that - once I can extract more than just edges from the DSP for debug-drawing. i.e. when I can get face information back with edges linked from faces then the CPU has enough information to make a complete terminator for individual polygons. But it will be slow, and enough work that it may be a waste of time. It might be better to spend the time working towards a proper filler gradually over a few sessions. I'll see what makes more sense once the other stuff is ready.

[Omikronman]

I can imagine a tron like style. edges only without transparency.

[dml]

I can imagine a tron like style. edges only without transparency.

Yes it's probably worth keeping a wireframe mode, but done properly with complete edges and hidden surface removal. Not sure that it will be much faster than filling because it must be processed as edges not original lines but it will probably look interesting at least.

[dml]

I figured something out this evening which allows per-pixel perspective correct texture mapping... using no divides, and needing only a tiny amount of RAM.

This raises the probability of Quake-style texturing on a plain F030 from 'no chance' to 'technically feasible'. Doesn't mean it can be done fast enough to be used in the Q2 engine but it's much, much closer to the target.

pctm.png

Experiment conducted on PC version using floats. I have still to solve some problems with a fixedpoint implementation. Not insignificant problems, but hopefully not as hard as figuring out the technique in the first place.

It is not the same as the other strange method I came up with for the first version of BadMood, but there was always that to fall back on - an improved, modified interpretation of it anyway.

The challenge is to make it work with fixedpoint. If that can be done then it opens up some new opportunities the old F030.

[dml]

I have found a second way to do this, which is even cheaper in some cases but not nearly so accurate. In fact it is so cheap that it might also work on a plain 68000. It's based on a mathematical technique I used to compress audio samples in a game long ago.

The first method though will be better on DSP because the cost difference isn't much and with some changes it can be shown that accuracy is practically as good as the original divide method, when used per pixel. I also now think it will convert to fixedpoint. I think maybe it is now a matter of effort - at least as sure as I can be without having done it.

[dml]

Fiddling around with back-of-envelope DSP code has given me an estimate of cost for Quake-style texturemapping. Specifically - perspective correct at every pixel drawn (the best BadMood could achieve was per-line, or per-column of pixels, which is why that engine can't look up/down 'properly' or tilt the camera sideways, or render sloping floor surfaces - no chance of that happening there).

I now think it's practical to obtain the screenspace u,v texture coordinates from 3D surface coordinates in 16 instructions or less (needed at span edges), and a full texture mapping fragment is 29 instructions or less per pixel, before attempting paralleling optimizations, or other shortcuts such as calculating every Nth pixel (which remains valid - but uncertain yet if it is helpful given other constraints).

By comparison the optimized BadMood liquid shader required 22 instructions per pixel and that was fast enough for shading a big area at least in chunky column mode. The optimized direct texture & lighting version uses 8 per pixel, assuming a constant-z, and hides fully behind a move (a0),(a1)+ on the CPU side but there's no way to achieve that kind of speed and still be perspective-corrected for individual pixels, it's completely out of scope.


Anyway providing other problems don't stop the arithmetic from working when it is translated, I think there is nothing else preventing Quake texture mapping from working as fast as one of the shaders already used in BadMood. Given that there are enough other constraints limiting window size (particularly, span processing cost to build the image) I don't think fillrate is going to be the main issue when attempting this.


That leaves the hidden surface removal and span processing/retrieval problem. It's hard to estimate the cost for that because it's different enough from the other scenarios I tried before so it could still be a showstopper. But the hard problems are gradually dissolving so we'll see I have some confidence in it working because it's similar to the kind of processing BM ended up using on floors, but still the amount of processing needed here is quite a lot higher.

The biggest problem I think in the end will be the sum of all these costs just being a bit too much for 16/32MHz, forcing some other decisions to be made. The individual costs are all manageable but added together, might still be too slow to be usable for a game. But even then it's probably close enough to be usable for something. By 'other decisions' I mean things like flatshading only, using simplified maps, using a small window (160x120) etc. etc. output limiting, not optimization related.

So I'll plod on over the next week or two as time permits and see if these things can be made to work as planned.

[Zamuel_a]

If it would be possible to use portals and sectors, when it would be very fast with the hidden surface removals. I guess it's difficult to convert the levels to be handled this way, but a Quake style engine using portals must be able to do on the Falcon. You should try and convert Decent since it's only using portals

[dml]

If it would be possible to use portals and sectors, when it would be very fast with the hidden surface removals. I guess it's difficult to convert the levels to be handled this way, but a Quake style engine using portals must be able to do on the Falcon. You should try and convert Decent since it's only using portals

I think Descent would be a fair target to try. A lot does depend on the state of the source. Some clean ports do exist, mostly OpenGL (which means the parts needing converted will be completely missing or compromised - since you don't need accurate portal clipping to draw portal scenery correctly in OpenGL). With some effort though it should be convertible.

[dml]

Made a new video over lunch, showing a test I conducted on a PC last night, aimed at a Falcon.

https://www.youtube.com/watch?v=r3suTkr ... e=youtu.be

Some detail described under the video. Basically I have a texturing technique now that works (at least some of the time!) using integers only, using 24bit arithmetic, without divides or memory greedy lookups.

Clearly its far from perfect but the kind of breakage isn't the kind I was worrying about. I think the other problems will get sorted out as I find time to work them out.

The most important bit of 'proof' in the video is the fact that some surfaces do render correctly at all distances and angles. While not seen in the video, this includes surfaces at funny diagonal angles. It's just that the maps which have those looked so broken it wasn't worth recording from them (even walking around them was a challenge) - this map was at least partially coherent with a few good surfaces near each other.

I'm very busy at work so don't have all that much time to play with this, but it is progressing gradually in the right direction.

[dml]

I managed to fix most of the damage within the last half an hour.

https://www.youtube.com/watch?v=yocH61F ... M&index=10

So the technique works, and it will translate to the Falcon's DSP.

(heh heh!)

I don't have much time on this today so will have to continue another time...

[EDIT]

Took a few screengrabs with the camera at funny angles, since this will break BadMood's axis-limited texturing and any kind of affine texturing. Not the white dots appearing sometimes - this is a side effect of precision loss, where the renderer walks off the edge of the texture sometimes.

[dml]

For the benefit of those who don't code, and to save me the trouble of explaining why its worth attempting perspective-correction, instead of using the more common affine texture mapping method used on 16bit (and slower 32bit) machines... here's a decent video comparing the two

https://www.youtube.com/watch?v=RyYEGdGwnFs

Put simply: one wobbles and the other doesn't

Note that the closer surfaces distort more than distant ones, which offers a good way to speed up processing of distant surfaces. i.e. you can use a less accurate, faster method if required.

[CiH]

Holee Feckin' crap!

[ausl8]

You are inspirational dml!!

[Scarlettkitten]

I don't know how you do it, that's amazing

[dml]

Thanks everyone. Glad there's some interest value here worth following.

I'm going to leave the texturing experiments now and return to the hidden surface removal. I have started to break up the project and tidy it up a bit to make progress a lot easier. It was becoming a big mess and keeping the Falcon and PC tests in sync was as much effort as writing the code. Once that's done I'll work on a minimal implementation of the polygon spanbuffer in C and then 68k/DSP.

The initial aim will be hidden surface removal, followed by filled faces.

[Omikronman]

Falcon games using graphics engines like this were rare on the Falcon. "Running" ran good but looked terrible. "Of Lasers and Men" was my favourite game of this type, even if the gameplay was quite choppy. "Towers II" was also not bad, even if the game window was a bit small. I really liked the "Moon Speeder", but it was not the smoothest one too.

[Zamuel_a]

How do you do perspective correct mapping without any div or mul? I wrote some texture mappers in the past, but I always had to use mul and div, unless you subdivided it into 16 pixel steps and reduced the amount of mul and div.

[dml]

How do you do perspective correct mapping without any div or mul? I wrote some texture mappers in the past, but I always had to use mul and div, unless you subdivided it into 16 pixel steps and reduced the amount of mul and div.

Perspective correction is really introducing a curve into a linear sampling sequence. The shape of the curve is more important than the operations that produce it. This is why you must multiply by z to prepare the interpolants, and then divide again by interpolated z. The z term cancels itself out, but the curve distortion is introduced by the division.

There are lots of ways to reproduce this curve or an approximation of it without a divide. It can also be done without multiplies - but with a significant increase in code complexity and larger error. That method involves calculating derivatives from sample points and performing lots of sequential adds per pixel. There is too much error to complete a span using this method so it needs a strategy to compensate and 'fit' the curve error. It is also an order-limited incremental approximation so at the very tightest angles it will begin to wobble again.

Another way is to encode the curve into a table (really a tangent table) and apply it to the interpolants, assuming the interpolants have a known range of 0-1 always. This doesn't require much arithmetic but uses memory and significant setup. The difficult part is determining where the curve begins and ends for a given span of pixels in order to address the table.

My aim is mainly to avoid divides and keep the code simple - I'm happy to use multiplies because they cost only 2 cycles each on the DSP. Even better that the DSP can move, multiply and add simultaneously. So the method I use is a quadratic approximation. Y = A(x^2)+Bx+C. It is cheap at 4 DSP instructions (8 cycles at 32MHz) and if used with great care can reproduce this curve.

I have other methods though. This one seems to do the best job for what I want here.

One of the experiments I ran last year was a genetic search algorithm which works on expression trees. It can hunt for arithmetic functions which approximate real functions. In other words it finds ways to encode curves efficiently. This has produced a few interesting cases which I'll be using for this kind of thing soon.

[Zamuel_a]

Sounds real clever! From the video you had, it looks like a "true" perspective mapper. Is it still slower than an affine mapper? If it would make sense to use that instead of polygons at a distance or polygons that are not on a steep angle from the player.

[dml]

Sounds real clever! From the video you had, it looks like a "true" perspective mapper. Is it still slower than an affine mapper? If it would make sense to use that instead of polygons at a distance or polygons that are not on a steep angle from the player.

If you have a DSP 'co-processor' as on the Falcon, and the textures are already too big to serve directly from the DSP, then there's not much gain in having an affine mapper even at distance providing the main one doesn't slow down the CPU.

In other scenarios though, yes it would pay to use an affine mapper for distant surfaces, or to spread accuracy across 16 pixel linear spans or so like the original Quake.

[dml]

A little bit of progress...

Yesterday I had an outline version of the spanbuffer algorithm implemented in C on the PC (minus all texturemapping, face processing etc) and which correctly applies hidden surface removal and fills faces with flat colour. It uses a combination of methods from Q2/Q2/PolyEngine to achieve the best fit for Falcon and simplifies some things which are either not wanted or not relevant for this project. It is now in a form which can be translated to DSP with a bit of effort.

I also had to fix some bugs in z-clipping, reversed winding order and closing open clipped polygons in the DSP version but that's done now. There is one more problem with the DSP version which isn't yet fixed - I think it is just running out of ram for vertices and edges at one point in the map and breaks down. This will be fixed by batching the geometry in smaller chunks.

I'll be starting on the hidden-line version next on Falcon.

That's all for now.

[dml]

Last thing done was a fix for the DSP ram overflow problem, by batching geometry 256 faces at a time.

This cleared up the problem with corrupt edges at some points on the map, and allows views with more than 2000 vertices or 1000 faces which was the fixed limit previously. It will also provide an opportunity later to overlap DSP and CPU work between batches if arranged with care.

There is a growing list of things needing optimized - but I think the path is clear now to work on a sensible DSP memory map and then code for hidden surface removal.

[dml]

Have written all of the DSP code for the Q2 scan conversion algorithm, from geometry to drawable faces.

About half of the code appears to work - the bit that handles the global and active edge tables, and keeping edges sorted.

The other half is the bit responsible for emitting spans and I'm not sure how close it is to working because it is still disabled.

There's a lot of code and it is complicated and hard to debug so it will probably take a few passes to get it all correct before it can start filling faces.