Quake 2 on Falcon030

[dml]

In a flu-induced daze last night at 3am I realized what was causing the infuriating hidden-surface glitches that I was unable to debug or nudge in any useful way with the tests I tried.

The screenspace edge clipper checks for vertical and horizontal lines - vertical ones have a gradient of 0 and horizontal ones get discarded since they don't form a left or right side of anything solid. But discarding edges is dangerous if they are not really horizontal, because then surfaces don't get closed properly.

Both the clipper and span generator were rounding off fractions before dealing with heights of edges. The problem was the clipper was rounding down and the span generator was rounding up. With a 1-bit disagreement in an 8 bit fraction, there was a 1 in 256 chance a non-horizontal edge would get chucked away, or that a horizontal edge would be used to close a polygon. That made it just rare enough to be infuriating, but common enough to be glitching all the time as you walk around.

It was also very hard to debug because both clipper and span generator looked like they were doing the right thing. They just didn't agree on occasion.

That (and being unwell to focus properly) was the main thing stopping me from working towards a proper colour version of the demo. However there's still a problem with BadMood at the moment and I need to debug that next before doing more on this so I'm not holding things up.

[dml]

I see now why the polygon scan convertor was spending more time sorting faces vs edges, than expected.

I forgot that when I rewrote the BSP stuff I had assigned a unique sort key to each face as it came out of the BSP. In fact the original version assigns a unique sort key per BSP hyperplane - which can host several faces each. So quite often adjacent faces sharing the same plane would have the same sort key.

This has been fixed in the C version, still need to do the DSP fix. It does mean the next version will be faster though, since on average it will be doing less work per line.

These pics show faces coloured by their sort keys.

Before:

sort1.png

After:

sort2.png

A golden rule in programming: "only ignore what you can confidently explain - or pay the price"

(Where: explain != rationalize)

[dml]

Not been able to do very much due to being unwell but did fix some precision problems and reorganized memory map to free up space for more spans, so it's possible to render a full 320x200 window in one pass (previously it ran out of spans at 1/4 of this, causing mid-bottom of screen to go flaky - and would have needed regular flush/restart to complete the scene)

Will work on optimizing the code for base1, which is the first Q2 map and one of the densest - it was built to look pretty without being big so it has a lot of polygons packed in a small area, and much denser than many of the DM maps.

Currently with the early version of the DSP code, it takes about 15 VBLs to complete a frame looking out of the base1 corridor window to the outside area, and 10 VBLs for the interior. That's about 3fps and 5fps. Window area is 320x200 in truecolour.

Image10.png

Image11.png

The code will need optimized now to raise the FPS to something more comfortable. Once base1 can run reasonably well the DM maps should run better, especially the smaller, compact ones made for smooth 1:1 tournaments.

The final version will probably aim at something 160x168 with chunky columns (similar to BadMood defaults), which will also help.

AF is really lagggy these days - had trouble posting this.

[dml]

Woah this site is really struggling now.


Last evening I returned to the code and rewrote 3 of the 5 stages involved in hidden surface scanning, including various tricks from the different engine variants and some of my own. This has resulted in a big improvement in those areas.

The insertion, removal and stepping of active edges now takes under 3% of total frame time on the worst frames. That mostly removes them from the overall performance problem.

This leaves the parts which record edges output from the clipper (which also contains a small pre-sort pass when several edges are scheduled for the same scanline) and the main part which generates the scanline from the active edges. The last part still hogs about 17% of total time and is where most of the DSP time is being sunk.

I will be aiming to get that under 10% if possible. This might be a challenge but will see how that goes.


To get optimal results it will require a bigger rewrite/repair after changing the layout of structures used for edges and surfaces, because this is producing some really bad DSP code which can be avoided and makes a big difference to speed. I'll do that separately because there is no incremental way to go about it - the first change will break everything and require all of the code to be reviewed. Will be worth it though.

Given that I'll be busy for another week and this site is quite broken, it will be another week at least before the next update.

[dml]

I got back from vacation with some fresh ideas for this thing. Not had time to start working on them yet but should do before long - I want to wrap up a BM release before investing any serious time in this one.

The plan is partly related to optimization and partly 'what to do with it' once it has reached a useful stage. Should be interesting

[dml]

Does anyone have a Falcon mainboard with the upper shielding removed, and a clear view of the crystal MHz values on the two crystals near the NVRAM? This circuit generates the clock from which the CPU speed is derived. It's not exactly 32MHz so I'd like to know what the other digits are. I need this to fine-tune my cycle counter and account for the other noise.

[EvilFranky]

Me, give me 5 mins...

[EvilFranky]

Is that it??

[dml]

Is that it??

Yes, that's it.

[EvilFranky]

No worries mate.

[dml]

I stopped this project partly to work on bugs in BadMood (which are now fixed) but also because I had bugs in the Quake engine which prevented me from moving it forward properly.

There were some problems with faces popping/disappearing at the left edge and sometimes faces visible through walls. Attempts at debugging these problems were not very successful - its quite a hard program to debug actively with breakpoints and looking at data for problems, especially when a glitch takes so long to locate and repeat. I wasn't happy about adding more complexity on top of bugs so I left it to rest for a while.


I picked it up again last weekend and did some experiments to find the various things that influenced these bugs, and went through the change history to find the points where they first appeared. I left it alone again for a week and thought about the results from the tests.

Yesterday I returned to it, knowing what was wrong and fixed it - well, fixed the most obscure one. The other one I think won't take so much time. I think the active surface list is just overrunning in certain views.


Once I'm happy there are no more bugs I'll continue with the optimizations which were started some time ago.

[dml]

I know what causes the second glitch now, although it doesn't really need fixed since the affected code is temporary.

The surface list was not exactly overrunning, but the check that stops it adding new faces after it fills up, was doing so too late.

The face edges always get emitted and the new face gets cancelled later on, so lots of bogus edges end up linked to the last face posted to the list of active surfaces. This caused some strange sorting issues where the distant scenery rarely appeared in front of nearby walls. It also caused some slowdown when that happens.

So all of the strange drawing bugs are fixed or accounted for. I should be able to continue with the other bits.

[Eero Tamminen]

Great to hear and thanks for the update!

[dml]

Great to hear and thanks for the update!

The fixes have been successful, no more glitching anywhere. Looks like it is perfect now (at least, until I break it again).

Speed is gradually picking up too. It still needs more restructuring in places to save significant cycles but its improving.

I had an idea to speed up scan conversion in chunky column mode - once I have run out of code optimizations - by rotating the viewport by 90' - from 320x200 into a 200x(320/2)=160 scanlines (columns).

This reduces the number of scan conversion steps by 20%, and because of the way levels are built (content laid out horizontally) each scan intersects less geometry / fewer edges and statistically should cost less, except maybe when standing in front of a staircase. But if you're filling the screen with a staircase, the draw distance is likely to be short at the same time so I don't think that is a real problem.

Using chunky columns without rotating the view will only save some pixel plotting and discard a relatively small %age of degenerate spans - much less to gain.

Chunky columns are probably not very nice for flatshaded mode but would be essential for texturing.

[dml]

A quick video update. Similar to last time, but faster and without the 'mess'.

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

The scene peaks at around 700 faces (mostly quads), sorted and clipped for zero overdraw. The filled version is now significantly faster than the old wireframe/hidden-line version.

The points in the map which appear choppy are signs of the original PVS not doing a stellar job - big chunks of geometry turning on early without being in view. Usually a few 100s of faces at a time. These get processed even if they aren't drawn. It's difficult to stop this without recomputing the maps using a more fine-grained PVS so the only option available is to optimize the paths involved as much as possible.

Still some DSP optimization work to complete, and will start looking at correct colouring next.

[viking272]

A quick video update. Similar to last time, but faster and without the 'mess'.

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

The scene peaks at around 700 faces (mostly quads), sorted and clipped for zero overdraw. The filled version is now significantly faster than the old wireframe/hidden-line version.

The points in the map which appear choppy are signs of the original PVS not doing a stellar job - big chunks of geometry turning on early without being in view. Usually a few 100s of faces at a time. These get processed even if they aren't drawn. It's difficult to stop this without recomputing the maps using a more fine-grained PVS so the only option available is to optimize the paths involved as much as possible.

Still some DSP optimization work to complete, and will start looking at correct colouring next.

Hi Doug,

Sounds great however the YouTube video is private in the permissions.

[dml]

Hi Doug,
Sounds great however the YouTube video is private in the permissions.

doh. fixed the link: https://www.youtube.com/watch?v=tgHg_P8_ZuE

thanks for pointing that out

[mikro]

Fantastic progress, Doug. This work alone is an amazing achievement.

[Cyprian]

awesome

[AdamK]

Doug, you're awesome.

Is it possible you could share pre-pre-pre-alpha binary, so those lucky bastards that have Falcons could see it on real hw?

Also, have you been thinkng about name of your project? I don't think 'Bad Ekuaq' will play

[alexh]

Also, have you been thinkng about name of your project? I don't think 'Bad Ekuaq' will play

"Aftershock"? They usually follow a Quake

[dml]

Is it possible you could share pre-pre-pre-alpha binary, so those lucky bastards that have Falcons could see it on real hw?

Yes I can release a binary which does what you see in the video.

However first I need to check it still works on real HW - have been doing a lot in Hatari recently. And it needs an FPU for the collision detection and other misc engine code. That's a requirement that might not change in future.

The data directory will also need pared down to just the map and essentials - it is normally very big. I think it will be possible to work with just a map file though.

Also, have you been thinkng about name of your project? I don't think 'Bad Ekuaq' will play

Not thought about it at all. But I see suggestions appearing already.

[dml]

And thanks everyone - I'll keep hacking away at it and posting updates as stuff happens.

[Anima]

Amazing. Who would've ever thought of this possible on a Falcon?

[viking272]

"Aftershock"? They usually follow a Quake

That's a great name!

Great progress Doug, very impressive video.