nesdev.com
http://forums.nesdev.com/

Digital Foundry Retro Doom port comparison
http://forums.nesdev.com/viewtopic.php?f=5&t=16524
Page 2 of 3

Author:  Revenant [ Sun Oct 01, 2017 3:07 pm ]
Post subject:  Re: Digital Foundry Retro Doom port comparison

The traditional definition of raycasting (at least with regard to Wolf3D and similar games) means simply doing a single distance check for each column of pixels on the screen, which is what leads to Wolf3D (and later iterations like Rise of the Triad) having relatively simplistic level geometry, with floors and ceilings always being at a fixed height, walls being completely solid, etc.

Doom instead breaks the level down into a BSP tree which it traverses from the player's point of view every frame to determine what's visible and where. The process is a lot more complex than simply doing a fixed number of simple distance checks like Wolf3D does, but it allows for much more elaborate geometry.

Author:  tokumaru [ Sun Oct 01, 2017 3:21 pm ]
Post subject:  Re: Digital Foundry Retro Doom port comparison

Espozo wrote:
What exactly does "raycaster" even mean?

A raycaster casts rays from the player, extending them until they hit walls. Once a ray hits a wall, the length of the ray can be used to calculate the apparent height of the wall (short rays mean large walls, long rays mean small walls), and the point of the wall that was hit indicates what texture column to use for that wall slice. Here's an animation illustrating how ray lengths translate into wall heights: https://commons.wikimedia.org/wiki/File ... ection.gif

Quote:
I know it's not how the walls are actually rendered, as Doom renders walls the same way as Wolfenstein 3D, (in one pixel wide, vertical slivers) but how the engine figures out where the walls are and their distance from the camera?

Yeah, the actual wall rendering is just 1D texture scaling, you just have to figure out a way to do it as fast as possible. In Wolfenstein 3D they apparently generated unrolled code in RAM for all possible wall sizes.

Quote:
How does Wolfenstein 3D accomplish this?

Wolfenstein 3D is just a raycaster. Overdraw isn't a problem because rays stop once they hit a wall, which means that hidden surfaces can never be hit by rays. This is one big advantage that raycasting has, you don't have to worry about clipping, walls that are behind the player, and so on. You just have one ray for each screen column and that one ray will give you all the information you need to draw that screen column. Raycasting doesn't help with rendering objects/sprites though, which require more traditional math.

Author:  Espozo [ Sun Oct 01, 2017 3:45 pm ]
Post subject:  Re: Digital Foundry Retro Doom port comparison

Thanks, Tokumaru. The only questions I have left are, does the "ray" have to be calculated "pixel by pixel"? Is this first speed this up by doing the equation using "map blocks" a grid instead of each "wall pixel" (if that makes sense)? This way, the bulk of performance loss would be due to how far a ray has to travel across the "map block" it is in before it hits the wall, rather than how far the ray has to travel in total.

Really though, I feel like drawing each wall column would take much more CPU time than "casting" each "ray" at a reasonable vertical resolution, but it also appears much easier to hardcode drawing walls. Isn't raycasting sometimes used in modern 3D graphics for reflections on non-flat surfaces?

I've never understood how this works: (Stage #10 of Expert Mode on Super Monkey Ball) https://www.youtube.com/watch?v=q1cfJ9WOptg#t=1m50s However, with how glitchy the reflection can be (not easily apparent in the video) I imagine they are just rendering the scene from the perspective of the reflection and stretching it. If I'm not mistaken, using raycasting for reflections is even out of the scope of games on modern consoles?

Author:  tepples [ Sun Oct 01, 2017 4:00 pm ]
Post subject:  Re: Digital Foundry Retro Doom port comparison

In a previous post, I proposed run-length-encoded ray casting, which checks each map cell only once, not once for each ray that passes through it.

Author:  tokumaru [ Sun Oct 01, 2017 4:09 pm ]
Post subject:  Re: Digital Foundry Retro Doom port comparison

Espozo wrote:
Thanks, Tokumaru. The only questions I have left are, does the "ray" have to be calculated "pixel by pixel"?

If you do it pixel by pixel I think you'll lose precision, and it'll be really slow. Normally you only check the intersections of the map's grid, like this:
Attachment:
raycasthit.gif
raycasthit.gif [ 2.3 KiB | Viewed 604 times ]

The downside is that your maps have to be blocky (i.e. like Wolfenstein 3D instead of Doom) for this to work. This can be pretty fast if you pre-calculate the distances between intersections for all possible angles:
Attachment:
raycastdelta.gif
raycastdelta.gif [ 3.24 KiB | Viewed 604 times ]

Notice how the deltas repeat as the ray extends.

Quote:
I feel like drawing each wall column would take much more CPU time than "casting" each "ray"

I guess it depends on how powerful the hardware is. On the NES, adding a delta, updating the map pointer, reading from the map and checking the block type repeatedly can use a lot of CPU time.

Author:  Espozo [ Sun Oct 01, 2017 4:45 pm ]
Post subject:  Re: Digital Foundry Retro Doom port comparison

tokumaru wrote:
If you do it pixel by pixel I think you'll lose precision

Each pixel wouldn't be 100% precise, but it can be precise as each column which is all that matters (if that makes sense), and there wouldn't be a drop off in precision the longer the ray is, as the equation would keep getting recalculated. Now that I think about it, with any moderately sized texture, (and thus moderately large pixel grid for each map block) this will be really slow though...

Do you only pay attention to the Y Delta if you hit a wall from the Y axis, and only pay attention to the X Delta if you hit a wall from the X axis?

tepples wrote:
In a previous post, I proposed run-length-encoded ray casting, which checks each map cell only once, not once for each ray that passes through it.

That looks interesting...

Author:  psycopathicteen [ Sun Oct 01, 2017 5:17 pm ]
Post subject:  Re: Digital Foundry Retro Doom port comparison

Are the walls in Wolfenstein completely flat, or do they have volume?

EDIT: Okay, I looked it up, and the walls are blocks, but the doors that open are completely flat.

Author:  tokumaru [ Sun Oct 01, 2017 5:25 pm ]
Post subject:  Re: Digital Foundry Retro Doom port comparison

Espozo wrote:
Do you only pay attention to the Y Delta if you hit a wall from the Y axis, and only pay attention to the X Delta if you hit a wall from the X axis?

The technique used in the tutorial I took the image from, which I loosely follow, each ray has 2 lengths, one for horizontal walls and one for vertical walls. At each step you extend the shortest length (H or V) by its respective delta, and advance one square in that axis in the map and check if that results in a collision. In the end, once a wall is found, one of the lengths is indeed discarded.

Here's the code from that tutorial that extends the ray (it's incredibly simple!):

Code:
      //perform DDA
      while (hit == 0)
      {
        //jump to next map square, OR in x-direction, OR in y-direction
        if (sideDistX < sideDistY)
        {
          sideDistX += deltaDistX;
          mapX += stepX;
          side = 0;
        }
        else
        {
          sideDistY += deltaDistY;
          mapY += stepY;
          side = 1;
        }
        //Check if ray has hit a wall
        if (worldMap[mapX][mapY] > 0) hit = 1;
      }

Author:  tokumaru [ Sun Oct 01, 2017 5:40 pm ]
Post subject:  Re: Digital Foundry Retro Doom port comparison

psycopathicteen wrote:
Are the walls in Wolfenstein completely flat, or do they have volume?

EDIT: Okay, I looked it up, and the walls are blocks

Yeah, but you could just as well have flat walls while still using the same overall technique. Instead of assuming each map cell is a solid block, you could assign different types to its 4 sides.

Quote:
but the doors that open are completely flat.

Yeah, they probably are like that because that's pretty easy to implement... When you hit a door block, just extend the ray for the door's axis by half the delta, and you have the distance to the paper-thin door. If that distance is shorter than the distance in the other axis (i.e. the distance to the solid wall that's perpendicular to the door), then you draw the door. Well, you still have to check the exact column of the door that was hit if the door is animating, to finally decide whether to draw the door or let the ray keep going because that specific part is already open.

Author:  Nicole [ Sun Oct 01, 2017 7:48 pm ]
Post subject:  Re: Digital Foundry Retro Doom port comparison

Espozo wrote:
Isn't raycasting sometimes used in modern 3D graphics for reflections on non-flat surfaces?

I've never understood how this works: (Stage #10 of Expert Mode on Super Monkey Ball) https://www.youtube.com/watch?v=q1cfJ9WOptg#t=1m50s However, with how glitchy the reflection can be (not easily apparent in the video) I imagine they are just rendering the scene from the perspective of the reflection and stretching it. If I'm not mistaken, using raycasting for reflections is even out of the scope of games on modern consoles?

Be careful not to confuse "raycasting" and "raytracing".

"Raycasting" usually specifically means the rendering technique used by Wolfenstein 3D and similar games, whereas "raytracing" is the 3D rendering technique where rays can reflect off of objects and so on.

Author:  tepples [ Sun Oct 01, 2017 8:05 pm ]
Post subject:  Re: Digital Foundry Retro Doom port comparison

And then there are hybrids of "raycasting" and "raytracing", like in the Build engine of Duke Nukem 3D. Build uses portal casting, a generalization of raycasting to an arbitrary mesh of sectors rather than a square grid. A portal caster traverses the graph of sectors using something analogous to the RLE technique that I linked above, where each solid wall splits the viewing cone into fractions at the left and right, and each wall of a sector that isn't solid extends the viewing cone to a different sector. And when a wall extends back onto the same sector, you get reflection, used for bathroom mirrors and the like.

Author:  93143 [ Mon Oct 02, 2017 3:48 pm ]
Post subject:  Re: Digital Foundry Retro Doom port comparison

I had somehow gotten the impression that Doom drew the walls in horizontal strips. If it really draws them in vertical strips (which honestly makes a lot more sense), then either the SNES version uses a different technique or it's wasting a lot of RAM bandwidth. It's possible the mosaic trick could actually result in a material speedup, if I can get it to work.

Author:  Espozo [ Mon Oct 02, 2017 9:52 pm ]
Post subject:  Re: Digital Foundry Retro Doom port comparison

SNES Doom doesn't actually use the Doom engine, so it very well could draw walls from left to right rather from top to bottom, although I have no idea why it would. I don't know anything about the Super FX, but I've always felt the SNES Doom port runs shittier than it needs to for how scaled back it is (pixel doubling, no textured floors).

Author:  93143 [ Mon Oct 02, 2017 11:01 pm ]
Post subject:  Re: Digital Foundry Retro Doom port comparison

The Super FX has an opcode called PLOT, that plots a pixel into a virtual framebuffer based on the coordinates in a pair of (otherwise general-purpose) CPU registers, and increments the register containing the x-coordinate.

What it actually does is plot the pixel into the primary pixel cache, which represents a specific tile-aligned 8-pixel sliver in the actual framebuffer (which is in SNES bitplane format), plus a bit for each pixel to denote whether or not you've plotted to it. Once the primary cache is full, or a pixel is plotted outside the sliver it corresponds to, it dumps itself to a secondary pixel cache so it can quickly receive new data. The secondary cache then empties itself into RAM, which takes quite a bit longer - at 21 MHz it's 5 cycles per byte, so that's 40 cycles for an 8bpp sliver, or 80 if some of the pixels are transparent/un-plotted, because it has to read the old sliver from RAM first to properly blit the new data into it. If the secondary cache is still doing this when the primary cache fills or is invalidated, instruction execution has to wait until the secondary cache is emptied so the primary cache can get rid of its old data and receive the new data.

This means that at 21 MHz and 8bpp, plotting solid scanlines is bottlenecked at 5 cycles per pixel, and plotting solid two-pixel columns is bottlenecked at 40 cycles per pixel.

Author:  ap9 [ Tue Oct 03, 2017 3:47 am ]
Post subject:  Re: Digital Foundry Retro Doom port comparison

93143 wrote:
I had somehow gotten the impression that Doom drew the walls in horizontal strips. If it really draws them in vertical strips (which honestly makes a lot more sense), then either the SNES version uses a different technique or it's wasting a lot of RAM bandwidth. It's possible the mosaic trick could actually result in a material speedup, if I can get it to work.

I remember a while back stepping through the Mac version of Doom in a debugger to discover a horizontal technique to render more than one pixel at a time by storing two 16 bit portions in a 32 bit register, for the low-res. mode. This method, of course, is not conceivable on a 16 bit system.

DOOM uses a lot of 32 bit math (esp. fixed point math); a proper port of Doom to SNES would be pretty slow in software because of the 16 bit limit. The Nintendo 64, on the other hand, had some hardware comparable to that of a low-end Power Mac— a 32/64 bit RISC CPU, for one— making the N64 port mentioned in the first post fairly easy. (RAM and other technical limitations still killed the N64 in the marketplace.)

I know the math well enough regarding 3D rendering that a divide operation is needed for every depth, which makes columns the fastest way for rendering walls— only one divide per x coordinate.

Quote:
This means that at 21 MHz and 8bpp, plotting solid scanlines is bottlenecked at 5 cycles per pixel, and plotting solid two-pixel columns is bottlenecked at 40 cycles per pixel.

God, that's slow, lol.

The SuperFX 2 was overclocked to 30 MHz, and the game was still slow for my taste. The engine Williams Entertainment used was maintained mostly in C, so there was plenty of room for performance improvements.

Page 2 of 3 All times are UTC - 7 hours
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/