Please login to add comments to this page.

Posted by russchou at 2011-04-05 10:33:07

32 + 32 + 2 = 64!

Posted by alexq at 2011-04-05 10:34:15

The lower order 2 bits of the 32 bit position are used for split plane direction.

Posted by schlen at 2011-04-05 12:45:14

The packets of rays can also take advantage of vector instructions. The idea is that rays in a packet will follow roughly the same path through the scene.

Posted by jruder at 2011-04-05 11:42:16

The special case of axis-aligned triangles relies on the realization that scenes will often feature planes alongside those axis (ceiling, floor etc).

Posted by boval at 2011-04-05 18:02:08

I stumbled across ray casting trying to look up more information on the computational geometry stuff in the next slide, but I think it's appropriate here. If I'm interpreting this right, ray casting is basically the packet of rays, but taken to an extreme. The wikipedia article doesn't quite describe it this way, but Permadi (from one of the references) does.

I find this an interesting tidbit because wikipedia mentions ray casting was used in Wolfenstein 3D, which ran on commodity hardware in the mid-1990s. The computer I had then, which ran Wolfenstein 3D, had a processor on the order of tens of MHz and I don't think had specialized graphics hardware.

Posted by avogel at 2011-04-05 19:52:50

It might've been used not for graphics, but for gameplay, like determining where a gunshot goes or something by casting a ray and seeing if it hits a person.

Posted by alexq at 2011-04-05 21:54:27

It was mentioned that if you wanna try something fanciful with the kd-tree in pbrt, you need to mask out the 2 bits in the exponent of the floating point. Was it the lowest or highest significant bit?

Posted by bsee at 2011-04-06 13:17:06

@alexq I might be totally wrong because I've only read a little bit from wiki and Parmadi's writeup, but it still sounds like they used ray casting for much of the 3D engine. By making the walls and doors very regular, i.e., only intersecting at 90 degree angles, they were able to render them efficiently with ray casting and textures, while the enemy and player were transparent bitmaps. The Wolfenstein 3D code (zip file from ftp.idsoftware.com) is open source, though I don't have time to really dig into it now. This site also seems promising for a high-level overview.

Posted by avogel at 2011-04-06 19:24:33

Yeah, I was just hypothesizing what else they could've used raycasting for. It's awesome that they managed to get that kind of stuff working on such primitive computers.

Posted by alexq at 2011-04-07 13:24:29

Yeah they definitely used raycasting for the engine in Wolfenstein 3D. My understanding is that they fire a ray for each vertical column of pixels on the screen and intersect it with a 2D grid of the world map to determine how far away the player is from the geometry, allowing them to scale the walls/enemies appropriately. This only works though because everything is the same height i.e. there is a ground plane with no stairs or anything. This essentially makes the game 2.5D; you can't look up or down.

Posted by lukeja at 2011-04-11 19:32:47

Raycasting is the method used in early "3D" games before modern rasterizing was adopted (with the arrival of hardware acceleration and GPUs). As lukeja said, in this method you cast a ray for each vertical line of your screen into a 2D map. It is basically a way to extrude a simple height map into a 3D world, where the only possible heights are 0 and 1 (height of a wall). Each ray is traced through the grid with a DDA algorithm, and a vertical line is displayed on the screen with a color and a length depending on the type of wall (color, texture) and its distance to the player. Since every wall has the same height, you do not need any hidden surface removal, because walls which are closer to the camera will automatically hide the walls which are behind them. The issue comes up when you want to display sprites (enemies, objects, etc.) which can occlude the walls or be occluded. There you need to sort the elements and render them back to front.

This method is really interesting because it shows how far technology was at that time (Wolfenstein is a 1992 game). The DDA algorithm has been used a lot then (in both rasterization and ray tracing), the notion of uniform grid describing the scene was already used, texture mapping was working quite well and programmers even figured out how to make floors and windows (Doom, 1993), or buildings, non-planar objects, two angles of view (Duke Nukem 3D, 1996), still with ray casting. And everything was running on the CPU :)

Posted by aharaux at 2011-04-12 20:54:45

I thought ray casting is simply ray tracing with depth 1.

Posted by zeyangl at 2011-04-20 10:48:49