It is currently Fri Oct 20, 2017 6:19 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 40 posts ]  Go to page Previous  1, 2, 3  Next
Author Message
PostPosted: Sun Oct 01, 2017 3:07 pm 
Offline

Joined: Sat Apr 25, 2015 1:47 pm
Posts: 328
Location: FL
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.


Top
 Profile  
 
PostPosted: Sun Oct 01, 2017 3:21 pm 
Online
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10064
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
PostPosted: Sun Oct 01, 2017 3:45 pm 
Offline
User avatar

Joined: Mon Sep 15, 2014 4:35 pm
Posts: 3074
Location: Nacogdoches, Texas
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?


Top
 Profile  
 
PostPosted: Sun Oct 01, 2017 4:00 pm 
Online

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19110
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Sun Oct 01, 2017 4:09 pm 
Online
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10064
Location: Rio de Janeiro - Brazil
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 392 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 392 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.


Top
 Profile  
 
PostPosted: Sun Oct 01, 2017 4:45 pm 
Offline
User avatar

Joined: Mon Sep 15, 2014 4:35 pm
Posts: 3074
Location: Nacogdoches, Texas
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...


Top
 Profile  
 
PostPosted: Sun Oct 01, 2017 5:17 pm 
Offline

Joined: Wed May 19, 2010 6:12 pm
Posts: 2290
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.


Last edited by psycopathicteen on Sun Oct 01, 2017 5:25 pm, edited 1 time in total.

Top
 Profile  
 
PostPosted: Sun Oct 01, 2017 5:25 pm 
Online
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10064
Location: Rio de Janeiro - Brazil
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;
      }


Top
 Profile  
 
PostPosted: Sun Oct 01, 2017 5:40 pm 
Online
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10064
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
PostPosted: Sun Oct 01, 2017 7:48 pm 
Offline

Joined: Sun Mar 27, 2016 7:56 pm
Posts: 137
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.


Top
 Profile  
 
PostPosted: Sun Oct 01, 2017 8:05 pm 
Online

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19110
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Mon Oct 02, 2017 3:48 pm 
Offline

Joined: Fri Jul 04, 2014 9:31 pm
Posts: 787
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.


Top
 Profile  
 
PostPosted: Mon Oct 02, 2017 9:52 pm 
Offline
User avatar

Joined: Mon Sep 15, 2014 4:35 pm
Posts: 3074
Location: Nacogdoches, Texas
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).


Top
 Profile  
 
PostPosted: Mon Oct 02, 2017 11:01 pm 
Offline

Joined: Fri Jul 04, 2014 9:31 pm
Posts: 787
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.


Top
 Profile  
 
PostPosted: Tue Oct 03, 2017 3:47 am 
Offline

Joined: Sat Jun 01, 2013 11:55 am
Posts: 23
Location: Maine, U.S.A.
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 40 posts ]  Go to page Previous  1, 2, 3  Next

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 8 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group