Doom-type rendering techniques: can we do better?

[ReadOnlyCat]

Originally Posted by Mrs Beanbag

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.

That's actually what I understood.
So for a strip which is distorted exactly diagonally you will have to proceed to 16 blitter copies of the original strip each copying only one column of the source, and if the bitplanes are not interleaved the number of blits is multiplied by 8.
In practice however perspective projection means that all lines of the strip must be distorted differently and on a y basis, so the distortion is a function of x and y and not just y.
Maybe I am misunderstanding but I get the feeling that this requires one blit per line and column except when walls are almost perpendicular to the line of sight.

[britelite]

Originally Posted by eXeler0

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..?

Well, a lot of self modifying code has been used on the Amiga too

And it's quite a bit easier to do dirty tricks on the C64, as the machines rarely have any expansions, with C64+diskdrive being the standard configuration and you can assume that stuff that works on your machine works on all others. On Amiga you have to account for a lot of different configurations, which pretty much rules out a lot of tricks if you actually want your stuff to work on any other machine than your own.
And then there's of course the problem with people being unable to properly configure their WinUAE-setup

[Dunny]

Originally Posted by ReadOnlyCat

That's actually what I understood.
So for a strip which is distorted exactly diagonally you will have to proceed to 16 blitter copies of the original strip each copying only one column of the source, and if the bitplanes are not interleaved the number of blits is multiplied by 8.
In practice however perspective projection means that all lines of the strip must be distorted differently and on a y basis, so the distortion is a function of x and y and not just y.
Maybe I am misunderstanding but I get the feeling that this requires one blit per line and column except when walls are almost perpendicular to the line of sight.

In a raycasting engine (like Wolfenstein, similar to Doom) all the walls are perpendicular to the floor and there are no slopes to walk up or down. We can use this to our advantage - every texture strip we draw will be vertical.

So for each horizontal pixel position, we cast a ray out from our position - when it hits a wall, we know:

How far the wall was from our position

Which texture we've hit, and where on the texture we hit it.

That's all we need to know - we then scale depending on the distance, this gives us our wall height at this point. We know which column of texture pixels to use from the texture.

All we have to do is stretch that column of pixels to the right size, and pop it on the screen at the current horizontal coordinate, centred in the y-axis.

Do that for all horizontal pixels (320 of them for a nice highres) and you're done - repeat for every frame.

I did a raycaster in BASIC:

http://www.zxspectrum4.net/forum/vie....php?f=8&t=150

(Textured version is about halfway down the page).

The source is really simple, it's just an horrendously slow and repetitive task. It gets slower as you add floor and ceiling texturing (slows down by a factor of about 8) and if you add variable height floors and textures with transparent sections you could add about another 4 - 8x on top of that.

As Mrs Beanbag says, if the blitter is able to do the actual final stretch of the texture strips, that will help enormously - the rest of the raycasting loop is just a few add instructions and a test.

D.

[Mrs Beanbag]

Originally Posted by ReadOnlyCat

That's actually what I understood.
So for a strip which is distorted exactly diagonally you will have to proceed to 16 blitter copies of the original strip each copying only one column of the source...

No, that's why i mention "sine-wave scroller technique". You don't need to copy each 1-pixel column individually, you need at most 4 blits for an arbitrary x-dependent distortion of up to 15 pixels. But these blits are only 16 pixels tall for a 16 pixel tall texture.

In practice however perspective projection means that all lines of the strip must be distorted differently and on a y basis, so the distortion is a function of x and y and not just y.

Yes, that is the point. You distort it one way at the top, and by the time you reach the bottom it's distorted the other way. But the entire strip will not be distorted on every line, only small parts of it will change, since there is only 16 pixels of vertical distortion of the strip over the entire height of the destination screen.

[hooverphonique]

Originally Posted by Mrs Beanbag

No, that's why i mention "sine-wave scroller technique". You don't need to copy each 1-pixel column individually, you need at most 4 blits for an arbitrary x-dependent distortion of up to 15 pixels.

so you're saying you can do a sine-scroller (with 15 pixel amplitude) in 4 blits? please explain... I mean, I understand the 1 blit per vertical strip approach, but the other one I don't see how would work..

[Megol]

Originally Posted by 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..?

Isn't the "problem" that the Amiga hardware is too well documented and structured? Or phrased different: that there aren't to many places where undocumented features can hide?

Edit: a bit OT, super speculative etc. how about adding some hardware to get chunky graphics?

The general idea being that one set up a 4 BPL mode at 640x256, set up the bitplane registers with a fixed pattern (4 pixels each of color 0, 1, 2, 3) and then enable hardware to redirect bitplane fetches to color registers.
There are many potential problems but I don't know enough to even see if it could ever work. Anybody else?

[chb]

Originally Posted by Megol

Isn't the "problem" that the Amiga hardware is too well documented and structured? Or phrased different: that there aren't to many places where undocumented features can hide?

I'd rather think it's rooted in the fact that demo groups went on to AGA/060 during the 90's and did mainly chunky effects, treating the chipset like a dumb (and slow) framebuffer. There just weren't so many people poking the hardware for undocumented features (and because of incompatibilities with future hardware it has been discouraged earlier, and rightly so).

Originally Posted by Megol

Edit: a bit OT, super speculative etc. how about adding some hardware to get chunky graphics?

The general idea being that one set up a 4 BPL mode at 640x256, set up the bitplane registers with a fixed pattern (4 pixels each of color 0, 1, 2, 3) and then enable hardware to redirect bitplane fetches to color registers.
There are many potential problems but I don't know enough to even see if it could ever work. Anybody else?

Actually, the Graffiti graphics adapter from Individual Computers (http://wiki.icomp.de/wiki/Graffiti) did something similar. It digitized the video signal on a per-scanline basis and fed the result to a VGA RAMDAC. You'd get sort of a scrambled chunky buffer, where all pixels on position 0,4,8,12... where next to each other in memory, then 1,5,9,13,.. 2,6,10,14,.. and finally 3,7,11,15...
It was activated by setting the genlock bit. Unfortunately, it wasn't very popular back then - it wasn't that cheap and the benefits where limited. Would have been more useful maybe if they included a 320x256 mode with 16 bit color depth, which would consume only 50% of AGA max bandwidth.

[Megol]

Originally Posted by chb

I'd rather think it's rooted in the fact that demo groups went on to AGA/060 during the 90's and did mainly chunky effects, treating the chipset like a dumb (and slow) framebuffer. There just weren't so many people poking the hardware for undocumented features (and because of incompatibilities with future hardware it has been discouraged earlier, and rightly so).

You may be right
But for example doing 8 bit sample playback on the C64 IIRC requires using a "glitch" in the SID logic, I don't remember such glitches being exposed in the Amiga.

Actually, the Graffiti graphics adapter from Individual Computers (http://wiki.icomp.de/wiki/Graffiti) did something similar. It digitized the video signal on a per-scanline basis and fed the result to a VGA RAMDAC. You'd get sort of a scrambled chunky buffer, where all pixels on position 0,4,8,12... where next to each other in memory, then 1,5,9,13,.. 2,6,10,14,.. and finally 3,7,11,15...
It was activated by setting the genlock bit. Unfortunately, it wasn't very popular back then - it wasn't that cheap and the benefits where limited. Would have been more useful maybe if they included a 320x256 mode with 16 bit color depth, which would consume only 50% of AGA max bandwidth.

The problem with the Grafitti is that requires a lot of extra hardware which increases the price. My idea is to add a circuit between the motherboard and the Denise chip and (if enabled) change bitplane writes into color register writes. If realistic the cost would be very low but require internal hardware modification.
The big problem seems to be that one have to load the bitplane 1 register to load the bitplane shifters but the copper could manage that I guess. At least if the bitplane registers aren't actually the shifters, have to check that out.

[Mrs Beanbag]

Originally Posted by hooverphonique

so you're saying you can do a sine-scroller (with 15 pixel amplitude) in 4 blits? please explain... I mean, I understand the 1 blit per vertical strip approach, but the other one I don't see how would work..

yes, i am saying exactly that, and i discussed it already in this thread from a while back (includes source code if you're interested)
http://eab.abime.net/showthread.php?t=62868&page=2

but on thinking about it, if the columns are only stretched and never shrunk, it should only require a distortion of at most 1 pixel in amplitude, so it really only needs one blit in this case.

[ReadOnlyCat]

Originally Posted by Mrs Beanbag

No, that's why i mention "sine-wave scroller technique". You don't need to copy each 1-pixel column individually, you need at most 4 blits for an arbitrary x-dependent distortion of up to 15 pixels. But these blits are only 16 pixels tall for a 16 pixel tall texture.

Oh, cute! Gotcha. (Just read the thread you linked.)

The number of blits required can indeed be lowered to 4 by performing a binary encoding of the height displacement of each column and "adding" the displacement-bits at each blitter pass. Essentially log2(16) passes instead of 16.

But, still, the technique is efficient for sine scrolling because it is operating on a tall 16 pixels wide strip where the height displacement is constant per column.
The issue I mentioned is that perspective correction on walls guarantees that the height displacement varies with Y, not just with X. Which means that this technique applies in the worst case only on one pixel high strip.
The binary encoding must be re-performed on each line and along with the corresponding blitter setup (even when reusing previous setups) is going to cost possibly more than the blits themselves. Not to mention that having to handle different displacements per Y means that one must not only mask the columns to shift up but also the existing data from the previous line. This is going to seriously complexify the computation of the masks.
Maybe it is possible to somehow precompute delta-Y mask tables depending on Z, Y and the wall's angle but it seems like this would require a huge lot of memory.

Also, even if the Z computation is factored along each column, if it cannot be stored in a register it would have to be retrieved from memory for each new Y, if it cannot fit in the 256 bytes cache that would be dramatic. We are allowed very few memory accesses per 16 pixels of display memory before simply filling the screen with zeroes with the CPU becomes faster.

I would not exclude it can somehow be worked out, but it seems like an extremely tall order given the problems to solve. This said, I encourage you to pursue it, as Photon said, one cannot do anything if they do not try.

Originally Posted by Mrs Beanbag

Yes, that is the point. You distort it one way at the top, and by the time you reach the bottom it's distorted the other way. But the entire strip will not be distorted on every line, only small parts of it will change, since there is only 16 pixels of vertical distortion of the strip over the entire height of the destination screen.

As I mentioned above, it's the "distorted the other way" [along the way] which seems cost prohibitive. The binary encoding per Y is prohibitive so you have to somehow re-encode only the bits which require it and this is a function of X, Y, Z and angle of the wall. And you have to make sure you can mix previously blitted lines and new ones (that seems very complex to me). If you can intuitively visualize it possible then by all means keep thinking about it.

Originally Posted by Mrs Beanbag

yes, i am saying exactly that, and i discussed it already in this thread from a while back (includes source code if you're interested)
http://eab.abime.net/showthread.php?t=62868&page=2[

but on thinking about it, if the columns are only stretched and never shrunk, it should only require a distortion of at most 1 pixel in amplitude, so it really only needs one blit in this case.

The distortion depends on the angle between the wall and the line of sight.
The more walls are parallel to the line of sight, the higher the distortion and it will vary obviously heavily with Y.

The right wall on the image below illustrates pretty nicely the range of possible distortions on a single 16 pixels wide strip depending on Z, X and Y.

[Mrs Beanbag]

Originally Posted by ReadOnlyCat

The binary encoding must be re-performed on each line

Yes, that is correct

Not to mention that having to handle different displacements per Y means that one must not only mask the columns to shift up but also the existing data from the previous line.

I don't understand what you mean here, the data from the previous line has been shifted off the top of the strip. You copy the top line of the strip to the screen for each Y-position.

Maybe it is possible to somehow precompute delta-Y mask tables depending on Z, Y and the wall's angle but it seems like this would require a huge lot of memory.

Z, Y and the wall's angle are all irrelevant... you only need the screen co-ordinates of the top and bottom (i.e. the height) of the wall for each screen X co-ordinate.

[/quote]The right wall on the image below illustrates pretty nicely the range of possible distortions on a single 16 pixels wide strip depending on Z, X and Y.[/QUOTE]
Yes i know, but i don't know what is the problem here... maybe there is something you miss.

On each line you distort the previously distorted strip, you don't redraw the entire thing for every line. So as long as you are only "stretching" the columns, each pixel column of the 16-pixel tall strip need move upwards only 0 or 1 pixels.

In fact we can do better than that, because the stretch is symmetrical (even if the texture is not), so we only need to do half the number of blits really.

And i have thought about how to calculate the masks more efficiently, basically you need to draw lines along the walls onto a buffer, with 1 pixel per x-coordinate. When a set pixel is encountered in the mask image, it shifts the corresponding column of the texture strip upwards.

[d4rk3lf]

Sorry for interrupting guys,
I am no where in position to discuss with you on this matter, because I don't have a clue about amiga programming (neither I know what is: Copper or the Blitter).
I was dragged out here by a thread that ReadOnlyCat posted on his first post.
I am doing a 3D graphics.

I have one question:
In 3D, we have an option (it's kind of a trick) to fake some real lighting, and render Ambient Occlusion procedural shader.
Here is the samples:






So, all the shader is doing is calculating distance from surfaces of the polygons. The close the surface is - the more black is... and that's it.
Or simply said: If it's corner - it's black. If it is just an open wall, it is white.

So.. what about doom clone without textures? Yet, incredibly looking using this technique? I don't know if it's possible easily to write something like this. Pure solid colors on the walls, but shaded using ambient occlusion (or any technique that will make corners be gradiently black... to white).
Enemies - vectors. Similar to Another World, or Elite... or even.. enemies could been bitmaps, after all.

Cheers to all!

[eXeler0]

@darkelf Ambient Occlusion needs quite a lot of detail to look interesting. Your average Amiga cant handle a lot of polygons so it would probably look more like oldskool gourard shading anyway.

Also, real time Ambient Occlusion is calculated in ScreenSpace and was not seen until DirectX 10 (I think) hardware came along with more generalized fancy pixel shaders and such... (I think Crysis was the first game to use SSAO and it basically ran like crap on anything below a GeForce 8800 with its 20 billion texel fill rate)

On the Amiga you could ***in theory*** do these calcs on the CPU but it would be much, much...MUCH too slow to be useful.
I dont have the technical know how to tell you what and how much the copper and the blitter could help out, but Im gonna venture a guess here and sit around, waiting to be proved wrong ;-)
:I say, it cant be done with anything more complex than a really super simple scene... (even if you fake it with coarse approximations and interpolation).

[commodorejohn]

Screen-space ambient occlusion is just an operation on the framebuffer using the depth buffer as a reference, so if you're doing Z-buffered 3D at all you're already doing most of the calculations you need for it. I don't see why it would be that much slower than non-SSAO rendering, aside from the general memory-bottleneck issue.

That said, yes, I'm not sure that you'd get much benefit out of it at Amiga resolutions - particular not for a raycaster-type renderer, where it'd be much simpler to just do some basic interpolation on the brightness values between the start and end columns of each sector edge.

[ReadOnlyCat]

Originally Posted by d4rk3lf

Sorry for interrupting guys,
I am no where in position to discuss with you on this matter, because I don't have a clue about amiga programming (neither I know what is: Copper or the Blitter).

No worries, good ideas do not necessarily require expertise. Sometimes, being an expert in a field can actually reduce one's field of view (huhu) so fresh suggestions are always welcome.

Originally Posted by d4rk3lf

So.. what about doom clone without textures? Yet, incredibly looking using this technique? I don't know if it's possible easily to write something like this. Pure solid colors on the walls, but shaded using ambient occlusion (or any technique that will make corners be gradiently black... to white).
Enemies - vectors. Similar to Another World, or Elite... or even.. enemies could been bitmaps, after all.
Cheers to all!

This is definitely a valuable approach to 3D rendering on the Amiga: drawing non textured polygons is simpler and possibly faster than Doom-style texture mapping. And indeed, games such as [ Show youtube player ] show that an A500 can very competently render Wolfenstein-like non-textured shaded walls at a high frame rate.

As CommodoreJohn said, the shading visible in the images you added is produced using a technique called ambient occlusion. It is actually not a function of distance to the viewer but of the proximity of each pixel to other volumes of the scene, it essentially computes the amount of light each pixel receives from the rest of the scene (without taking actual light sources into account).
That is completely impossible to do in real time on any stock Amiga.

This said, it could probably be faked with a kind of non linear Gouraud shading. But I am not sure the blitter is really good with shading. This is not something I have put much thought into since I am already quite overwhelmed by my current pursuits and I am utterly incompetent in this area.

Also, the emphasis of this thread is on finding better techniques to reproduce Doom's style rendering without having to recourse to the costly chunky to planar conversion. Doom essentially decomposes the scene into horizontal and vertical spans and then does linear texture mapping for each of these spans, which is a process which works really well for chunky graphics but is as pleasant as eating kangaroo droppings on planar graphics.

So, yes, I think it is possible to produce games as good and atmospheric as Doom using purely shaded polygons on the Amiga, but the topic is wide enough to require a thread of its own.

Originally Posted by eXeler0

@darkelf Ambient Occlusion needs quite a lot of detail to look interesting. Your average Amiga cant handle a lot of polygons so it would probably look more like oldskool gourard shading anyway.

Yup, but since Doom/Wolfenstein have very simple geometries and hidden surfaces are easy to compute this is probably an approach worth pursuing, even if the shading is heavily faked.

Originally Posted by eXeler0

Also, real time Ambient Occlusion is calculated in ScreenSpace and was not seen until DirectX 10 (I think) hardware came along with more generalized fancy pixel shaders and such... (I think Crysis was the first game to use SSAO and it basically ran like crap on anything below a GeForce 8800 with its 20 billion texel fill rate)

On the Amiga you could ***in theory*** do these calcs on the CPU but it would be much, much...MUCH too slow to be useful.

Any shading would have to be precomputed. Ambient occlusion is doable in real time only with a good 3D graphic card and a single frame would probably take a lot of minutes to compute on a 1200.

Originally Posted by commodorejohn

Screen-space ambient occlusion is just an operation on the framebuffer using the depth buffer as a reference, so if you're doing Z-buffered 3D at all you're already doing most of the calculations you need for it. I don't see why it would be that much slower than non-SSAO rendering, aside from the general memory-bottleneck issue.

I love that "just". It relies on quite a few pre-conditions, none of which satisfied on a stock 1200.

Yup, SSAO is conceptually simple but it requires several additional generations of hardware to be doable in real time. I am pretty sure you could not do it in software even with the fastest PentiumI even at 320x200. There are only so many cycles you can spend per pixel without hardware acceleration.

Originally Posted by commodorejohn

That said, yes, I'm not sure that you'd get much benefit out of it at Amiga resolutions - particular not for a raycaster-type renderer, where it'd be much simpler to just do some basic interpolation on the brightness values between the start and end columns of each sector edge.

Actually, with a low polygon count typical of what the Amiga can do, it would probably be visible and bring a nice soft touch to the image. And yup, it would have to be 100% fake.

This said, we are very much off topic, and I said above this (good) idea is deserving of its own thread.
("Doom-like 3D shooter _gameplay_ with Amiga-specific/oriented rendering" sounds like a good name.)

[ReadOnlyCat]

To mods: please do not merge my posts, they really have completely different topics. Thanks.

Originally Posted by Mrs Beanbag

Yes i know, but i don't know what is the problem here... maybe there is something you miss.

On each line you distort the previously distorted strip, you don't redraw the entire thing for every line. So as long as you are only "stretching" the columns, each pixel column of the 16-pixel tall strip need move upwards only 0 or 1 pixels.

Holy kangaroo!
I had to let this post of yours mature peacefully for quite some time before it finally made sense when re-reading it today.

I previously understood that you would do 4 blits for each line of the source texture strip, but your plan was to factorize several lines at the same time and re-blit from the destination rather than the original texture strip.

So essentially you would:

1. "sine scroll" an initial block of say 16 rows x 16 lines, with "scroll" parameters defined by Y, Z and theta (angle between view vector and wall).
   The whole block is distorted per the parameters computed for the highest Y (lowest projected line on screen).
2. Then starting from the second highest Y (or lower depending on the desired granularity), you re-distort again that same block, but using itself as a source.
   With new parameters recomputed for this distortion.
3. Redo step 2 with lower Y until a new block from source is needed at which point go to step 1 (with different parameters though).

Is that what you meant? I am not sure I am explaining it very well.

I think this does indeed make sense. What you would obtain is essentially a function which Y-scales a source texture as a function of (Z, wall-angle).

For a super simple case, with:
- wall texture start coincides with left screen border
- ignoring perspective projection on x for now

You essentially need to compute the smallest set of texture-to-screen and screen-to-screen blits which ends up moving each pixel of the source texture at the proper y positions (because you possibly have to scale up). This for a given Z (distance wall-screen) and theta (angle wall-to-view-direction).

Damn, this might work.
Now, this doesn't obviously deal with x-axis perspective projection but this could indeed could be a very efficient way to Y/Z scale a texture.
I am not too sure if this handles scaling up well though, but at least it deals well with scaling down. Also, this would require mip maps otherwise you would do too many blits for far walls.

Originally Posted by MrsBeanBag

In fact we can do better than that, because the stretch is symmetrical (even if the texture is not), so we only need to do half the number of blits really.

It is symmetrical only if the eye is at exactly half the wall's height.
But even then, I am not sure this halves the number of blits? This certainly makes the top-half/bottom-half Y-shifts symmetrical though and thus easy to compute.

Originally Posted by MrsBeanBag

And i have thought about how to calculate the masks more efficiently, basically you need to draw lines along the walls onto a buffer, with 1 pixel per x-coordinate. When a set pixel is encountered in the mask image, it shifts the corresponding column of the texture strip upwards.

That I completely do not understand.
Can you try explaining it in a different way?

[s2325]

Wolf 3D beta by STL from 17-Bit Software CD [ Show youtube player ]

[ReadOnlyCat]

Originally Posted by ReadOnlyCat

[snip]
You essentially need to compute the smallest set of texture-to-screen and screen-to-screen blits which ends up moving each pixel of the source texture at the proper y positions (because you possibly have to scale up). This for a given Z (distance wall-screen) and theta (angle wall-to-view-direction).

Damn, this might work.
Now, this doesn't obviously deal with x-axis perspective projection but this could indeed could be a very efficient way to Y/Z scale a texture.
I am not too sure if this handles scaling up well though, but at least it deals well with scaling down. Also, this would require mip maps otherwise you would do too many blits for far walls.

Huh... What the kitten did I even mean to say?
Coming back to the topic after more than a year I am now totally unable to understand what I wrote.

Originally Posted by s2325

Wolf 3D beta by STL from 17-Bit Software CD [ Show youtube player ]

This is AGA only right?
The hope here is to write something which runs acceptably on the stock A500.
Even something like Catacomb would be ok and is I think totally doable.

[saimon69]

Would be still processor-intensive do walls and doors with one color texture only? If well done it can give a particular comic book feeling to the scene

[ReadOnlyCat]

Originally Posted by saimon69

Would be still processor-intensive do walls and doors with one color texture only? If well done it can give a particular comic book feeling to the scene

A vast majority of the CPU cycles used by ray-casting engines on the OCS/ECS machines is spent by the texture mapping routines. To be precise, in Wolf 3D parlance, this is the DrawSpan() function/routine which draws vertical columns of texture.

If you remove textures, then there is no need to draw individual columns anymore and the rendering becomes a simpler matter of filling quadrilateral shapes on the screen, which the Blitter does very efficiently. Such a game would run at 50/60 FPS easily.

The proof-in-the-pudding being the "Walls" game (http://aminet.net/package/game/demo/walls17) which does exactly that and even adds some shading instead of purely being monochromatic: it runs at max FPS without trouble.