Doom-type rendering techniques: can we do better?

[ReadOnlyCat]

Samurai_Crow recently mentioned in another thread the clever routine used by ADoom to reduce the time spent on the chunky-to-planar conversion which I will quote here for reference: (edited to shorter length)

Originally Posted by Samurai_Crow

By rendering 3 bitplanes of shading and 5 bitplanes of texture mapping, the amount of computation lost to the chunky-to-planar conversion of the texture mapping is cut to 5/8 the normal amount of time. In addition to that, the other 3 bitplanes get a speed boost by letting the blitter do its polygon-filling while the CPU is doing other things.

[...] a standard 8-bitplane chunky-to-planar routine [...] takes more CPU time and gets no boost from the blitter. Splitting the duty between the CPU and blitter makes a big speed improvement [...]. It essentially is a compromise between dithered pattern fills by the blitter like Walls 1.7 linked in my previous post and Doom's 8-bit chunky routines.[/

The technique is definitely clever, it reduces the CPU cost of the C2P conversion by 3/8th (almost half) and uses the blitter for what it is most efficient rather than for C2P. But it also imposes some hefty constraints on the color variety and I was also wondering if it could still not be pushed a bit further.

Since I am currently working on an Amiga project with completely different rendering methods and it is very unlikely that I will have time to code anything Doom like within this year I thought it could be profitable to discuss possible ways to push this system further by throwing out technical ideas in the air so that the talented coders around there could either snipe them or refine them until some testable better method could be produced.

So here are my current questions and remarks about the DoomAttack technique:

First, the number of available colors for textures is reduced to 32 (5 bits), I assume that this might not be too much of an issue since they essentially define a palette which will then be 8 levels shaded, but still, does this not visibly reduce the perceived variety of colors in games more colorful than Doom?

Second, even then, the C2P routine still does too much work in some cases: areas close to the camera display zoomed-in textures where a single texel occupy several pixels on screen, from 4 (2x2) in the lower case to possibly much larger areas (10x10? 20x20? More?).
Having these zoomed in areas undergo C2P is clearly a waste of processing power given the number of identical pixels and I have been trying to think of a few ways to attempt to exploit the redundancy.

The first problem to address is to split the display in different areas of similar texel/pixel ratio.
How to split? Split only the closest wall/floor/ceiling "polygons"? Split only the "non center" areas?

Then comes the problem of exploiting the pixel redundancy to reduce the cost of C2P or replace it with better suited methods:

Can you guys think of any ways to adapt the C2P routine to be more efficient for large texeled areas?
Since most polygons will not be perpendicular to the line of sight, could it be possible to adapt C2P to work directly on the texels and to take the angle of the polygon into account?

Replacing C2P with something more appropriate:
Taking the case of the left/right walls in a straight corridor. Their zoomed in areas essentially constitute a perspective grid of flat shaded polygons: each texel is visible as a perspective distorted flat shaded square. Could it be possible to somehow draw the corresponding grid lines efficiently using the blitter and fill them all in one blitter pass?
If possible (which I am far from being sure), this would totally eliminate the need for C2P on these areas.

What do you guys/gals think? Can you think of practical ways to implement these ideas? If not, can you picture any other way to take advantage of the texel/pixel ratios?

I will keep thinking about this in the back of my mind and will post any new idea which bubbles out but I am deeply curious to see what experienced coders might brainstorm out of these.

Also do not hesitate to voice strong criticism if you can prove these infeasible, my inner kitten is ego-less and any technical counter argument is most welcome!

[commodorejohn]

DOOM was actually pretty colorful - it wasn't until Quake that shooters started trending towards all-brown. But 32 colors can go a long way if you put some care into it. You could, for example, pick a heavily "themed" palette consisting of multiple shades of a few main colors (four shades of eight, or eight shades of four, or something in between.) I've considered even going so far as to do a primarily monochrome theme with splashes of color - say sixteen shades of gray with one or two highlight colors (the old Vincent Price movie The Tingler did something similar, being almost entirely in black and white but doing one scene where everything was monochrome except for the most vivid red blood you can imagine.) Could make for a very interesting look.

[Samurai_Crow]

The blitter is not fast enough to fill all of the bitplanes. Otherwise we would be using stencilmaps instead of textures all over the place.

We need a faster blitter. AGA blitter doesn't use page mode or 32 bit bus width at all.

[ReadOnlyCat]

Originally Posted by Samurai_Crow

The blitter is not fast enough to fill all of the bitplanes. Otherwise we would be using stencilmaps instead of textures all over the place.

We need a faster blitter. AGA blitter doesn't use page mode or 32 bit bus width at all.

Oh, I guess I probably badly explained myself then.

My hunch is that the CPU cost of the C2P can be reduced by exploiting the fact that zoomed in textures texels occupy several pixels on screen.
Regular C2P assumes that all chunky pixels are different so all pixels will get bitplane converted. However for zoomed in textures that is not the case and if say for texture A all texels occupy 4 pixels each then the cost of the C2P work can be reduced since for 1 chunky texel converted 4 planar pixels can be output.
This would reduce at least the chunky input bandwidth since the work is done directly on texels.
(There are other obstacles to overcome before this can be determined like verify that it is possible to take polygons angle when doing the C2P but I mentioned them in the OP.)

Only the "perspective grid drawing" suggestion would make use of the blitter. But I have yet to determine if it is really feasible.

I hope that is a bit clearer now.

[Mrs Beanbag]

i have sometimes wondered if it's possible to render more directly to the screen, without doing C2P at all.

[commodorejohn]

A raycaster-style renderer (ala DOOM) could probably make hay out of the fact that multiple columns are packed into one word of bitmap data in a planar system, I think. I haven't sat down to work out the details, but if you worked out the calculations for 16 or 32 columns (or pixels' worth of column, if you're doing a half-res mode or whatever) at once, you could assemble a whole word or double-word worth of pixel data column by column, bitplane by bitplane, and only then need to touch chip memory. I'm not sure if storing the textures as planar bitmaps would help any...?

[Photon]

Walls17 is untextured, and I would need to see some tech demo with textures before I decide if the blitter will help and that 7 levels of shading looks acceptable. I don't rule out new ideas (see reply in ref thread), but from instinct the blitter is better used for partial C2P invocation up to its max capacity and filling polygons with it on fast AGA machine will not help at all and that 7 levels of shading will look bad.

Now, realists never get anything great done, you have to be an unrealist to make something unreal. But the idea of applying polygons really requires at least a small tech demo with profiling.

[Samurai_Crow]

It was DoomAttack that's well optimized. ADoom is slower on low speed systems.

[Michael]

AlienF1 says it uses planar rendering for 3D texturing, and it's fast on slow amigas.
So some tricks are possible,

[ReadOnlyCat]

Originally Posted by Photon

Walls17 is untextured, and I would need to see some tech demo with textures before I decide if the blitter will help and that 7 levels of shading looks acceptable.

According to Samurai_Crow, DoomAttack (Aminet) is the one which does the 5bp colors + 3bp shading. I have not yet tested it on an Amiga (real or emulated) but I have found this [ Show youtube player ] which is by far the best I could find (the others have low quality which make it hard to analyze the final result). The guy plays the game quite extensively so it shows a large variety of environments.

The 7 levels of shading are a bit noticeable especially on the floor and ceiling but they seem to work quite nicely on walls and characters. It is really hard to figure out that the game uses only 5 bitplanes for texture color, to the point that I actually wondered if this is really how DoomAttack proceeds. But then, Doom never really felt very colourful even on PC.

Originally Posted by Photon

I don't rule out new ideas (see reply in ref thread), but from instinct the blitter is better used for partial C2P invocation up to its max capacity and filling polygons with it on fast AGA machine will not help at all and that 7 levels of shading will look bad.

It's true that 7 is not much but it might be possible to use dithering to increase the apparent number of levels. I am not so sure that this is doable with the blitter though, I lack practical experience with this kitten.

Originally Posted by Photon

Now, realists never get anything great done, you have to be an unrealist to make something unreal. But the idea of applying polygons really requires at least a small tech demo with profiling.

True, everything is impossible until it finally ends up being done.

When you mean "applying polygons" are you referring to DoomAttack's shading or to my suggestion of using a polygon grid to draw large texels?

Originally Posted by Michael

AlienF1 says it uses planar rendering for 3D texturing, and it's fast on slow amigas.
So some tricks are possible,

Alas, the source is not available as far as I can tell.
Also, not all rendered elements have texture so it is hard to evaluate which impact direct planar rendering might have. Maybe someone can modify the track data so it looks like a Doom level?

[Samurai_Crow]

I haven't looked at the source of DoomAttack much so it might just be a smarter C2P. Still, 7 shades works without textures if it's dithered on Walls17 so I figured it would work that way.

DoomAttack beta source is on Aminet...

Edit: here's the link to the source. http://aminet.net/package/game/shoot/DoomAttack_src

[ReadOnlyCat]

Originally Posted by Samurai_Crow

I haven't looked at the source of DoomAttack much so it might just be a smarter C2P. Still, 7 shades works without textures if it's dithered on Walls17 so I figured it would work that way.

DoomAttack beta source is on Aminet...

Edit: here's the link to the source. http://aminet.net/package/game/shoot/DoomAttack_src

Yaaah! You're the cutest kitten!

I actually googled the Doom palette to figure out how many levels of shading they used and found the original Doom palette on the Doom wiki.

It looks like they used up to 32 levels of shading for at least three colors (red-ish, brown-ish, grey), 24 for one color (another brown, less red), 16 for four colors, and 8 for a few more.

This makes Photon's remark that 7 levels of shading would not give good result quite relevant since that would completely change the precision of shading for the most used colors of the game (red, brown, green, grey). Moreover this would also rebalance massively the weight of each tint inside the palette.
Given how faithful to the original DoomAttack looks I am a bit puzzled.

I guess the answer lies in the source code.

[Mrs Beanbag]

i think this confuses two things:
the number of different shades of a colour on one "wall tile",
and the number of different shading levels a whole tile can have.

Mind you that palette doesn't look particularly efficient, anyway.

I'd say the answer lies in the wall texture images.

edit: and following on from this:
http://eab.abime.net/showpost.php?p=...2&postcount=54
ok...

there are so many overlapping threads i sometimes get lost. anyway my idea is basically to render a 16-pixel tall strip of walls with perspective-correct along the X-axis but no scaling on the Y axis. Then use an efficient sine-wave scroller technique to do the scaling. For each scanline on the destination image, selectively shift up rows of the strip and blit the top line onto the screen.

[commodorejohn]

There is no real distinction there. DOOM textures are 8-bit, so they can use the full palette, and shading is accomplished with a lookup table that maps each possible combination of texel value and light level to the closest approximation in the palette, so any pixel can theoretically be displayed at any light level (even though it works out to a close-enough approximation in reality, which mostly causes things to get a little washed-out at especially low levels.)

[ReadOnlyCat]

Originally Posted by Mrs Beanbag

i think this confuses two things:
the number of different shades of a colour on one "wall tile",
and the number of different shading levels a whole tile can have.

Although this distinction makes sense on the original Doom palette, it does not in the case of DoomAttack since shading uses 3 bits in the CLUT table and the blitter which implies that all colours defined using the 5 other bits have 8 levels of brightness. I would assume it would be quite inefficient to handle some colours differently than others after dividing the palette this way.

Originally Posted by Mrs Beanbag

Mind you that palette doesn't look particularly efficient, anyway.

Given that DoomAttack seems to look quite good with only 8 levels of brightness for all 32 colours allowed in its textures I am very tempted to agree with you on this point. I will however reserve my judgment until I can see it running with my own eyes alongside a regular VGA version.

Originally Posted by Mrs Beanbag

anyway my idea is basically to render a 16-pixel tall strip of walls with perspective-correct along the X-axis but no scaling on the Y axis. Then use an efficient sine-wave scroller technique to do the scaling. For each scanline on the destination image, selectively shift up rows of the strip and blit the top line onto the screen.

I fail to see the link with sine scroller techniques but I will gladly claim ignorance in this domain and I should be heading to bed at this hour so do not mind me.

But still I do not know if this would work.
Doom's drawing speed comes from the fact that it factorizes z computations for vertical walls columns and horizontal "floor/ceiling" lines. It essentially does away with the expensive perspective correction computations by doing only one per wall-column or floor/ceiling-row.

Avoiding this factorization implies a huge additional cost.

The polygon grid technique I was suggesting for walls retains it because we still need only one Z division per vertical grid line but if one draws walls horizontally one must compute Z stepping information as they progress on X and retain it for future above/below strips of the same wall which might imply fetches from memory which are unnecessary when proceeding vertically (for walls).

Also, if you scale up, it means you lose precision in the Y axis but a perspective correct polygon with large texels still has one pixel drawing precision.

Originally Posted by commodorejohn

There is no real distinction there. DOOM textures are 8-bit, so they can use the full palette, and shading is accomplished with a lookup table that maps each possible combination of texel value and light level to the closest approximation in the palette, so any pixel can theoretically be displayed at any light level (even though it works out to a close-enough approximation in reality, which mostly causes things to get a little washed-out at especially low levels.)

Yes, but this remapping probably cannot work with DoomAttack's division of the palette. Using the blitter for shading seems to imply losing the flexibility of per CLUT entry remapping.

[commodorejohn]

Yeah, it is a technique that requires chunky pixels, so if you're trying to avoid C2P somehow then it's definitely not the technique for you. It's just how DOOM does it, is all.

[Mrs Beanbag]

Originally Posted by ReadOnlyCat

I fail to see the link with sine scroller techniques but I will gladly claim ignorance in this domain and I should be heading to bed at this hour so do not mind me.

No i don't think you quite get how it's supposed to work...

but first important point is that it's only suggested for walls, not for floors and ceilings, which would require a different approach.

The "Sine Wave Scroller" is basically a technique to distort a horizontal strip of an image along the y-axis by an arbitrary function of X on a per-pixel basis. It can be done efficiently by the blitter. I might have to illustrate this somehow but the idea is, if we were using small textures of maybe 16 pixels in height, we could use the blitter to stretch a strip along the Y-axis, by distorting the source strip progressively, and copying it line by line into the screen.

Of course you would only need to calculate Z and texture X co-ordinates once per vertical row of wall pixels.

[Dunny]

I wrote a wolf-style raycaster in BASIC. It was pretty easy - there's a surprisingly low instruction count needed for the actual casting (the number of repetitions can get quite high though, as you need to cast from your viewpoint out to the nearest wall, so closed-in areas are faster to render). It's just bressenham, no need for trig tables or owt except for at the very start of the frame, and even those can usually be optimised away.

Walls were very easy - just calculate the height of the wall and stretch the texture to match the height. The interpreter has a pretty powerful and fast bitmap stretching routine, so that part was just one command.

Floors and ceilings are harder. As you turn, horizontal lines quickly slope away and so a blitting routine won't help - you have to calculate the floor/ceiling texture for each individual pixel which will really slow you down. Fortunately if the floor and ceiling textures are the same size then you only have to calculate one and mirror it for the other (the coordinate, that is).

And if you really want to simulate Doom, then there's going to be even more slowdown as you cast out to multiple height floormaps, but that's another story.

D.

[Mrs Beanbag]

Originally Posted by Dunny

I wrote a wolf-style raycaster in BASIC. ...

Walls were very easy - just calculate the height of the wall and stretch the texture to match the height. The interpreter has a pretty powerful and fast bitmap stretching routine, so that part was just one command.

I have also done this, in AMOS, using the Zoom command. Although i wouldn't exactly call that fast.

[eXeler0]

Ok, this is off topic, but I just wondered if you guys have watched this "behind the scenes" of a c64 demo group (Ninja/ The Dream)
[ Show youtube player ]

Intertesting stuff. Particularly the part where they talk about the fact that some hacks didn't surface until like after 20 years as its actually about learning the flaws in the chips and use them to your advantage.
Furthermore they talk about how self modifying code is essential to cram the most out of the c64.
From that point of view, I get the feeling the c64 has been pushed far more beyond it's -assumed- limits than the A500..?