So, is Doom a raycaster?

[Optimus]

I think not. But I wanted to ask the community, cause you've played with the sources.

What I mean by raycasting is, any kind of shooting rays/finding intersections with walls, just for determining which walls or columns to draw. I know many people confuse raycasting with column rendering of wolfenstein and this is not what I ask.

I just came to this again because I found a lot of different opinions. And some of them at first don't seem to be uneducated like "Lol, Dewm is raycasting because it's 2.5d or column rendering". Some of this are like "Yeah, of course it uses BSP, but that doesn't exclude raycasting. It still raycasts on the BSP tree"

Facts: Wikipedia on Doom engine and Fabien Sanglard's code review explain things well and does not even mention raycasting. Wikipedia article on raycasting mentions wolfenstein 3d but never Doom.

Ok, I opened the code and slowly slowly tried to follow and understand what I can: There is some BSP traversing, through SSECTORS (convex parts of Sectors?), then in the SSEGMENTS (I guess clipped line segments). And then it runs a function Addline to add what I guess those datas in a list. It simply determines the visible line segments that needs to be drawn and then proceeds from left edge to right edge to render individual columns (I guess, before calling for rendering individual columns, it interpolates the starting and ending texcoords and column heights per column, across the wall). There seems to be no intersection determination, just visibility determination (and no ray/raycast or other things inside the code). So I guess I have my answer, but maybe I am wrong and I missed it?

My other question is, maybe some of the alpha versions of Doom relied on raycasting before moving on to BSP with no raycasting? Or maybe some of the other Doom ports on Jaguar or other platforms used raycasting on the BSP trees? (The Jaguar source is full of assembly for these parts, but the function names and what they do seem to be the same). I see both seemingly educated programmers arguing in some places, some saying NO definitely not raycasting, others being also certain, like YES it does do raycasting but on BSP trees.

p.s. Random interesting fact. Carmack himself in some video where he was playing wolfenstein, said that the SNES CPU was too slow for raycasting, so that version is actually using BSP trees. I didn't know BSPs could prove to be faster (is it?) in older hardware. I never coded a BSP engine but have coded raycasting wolfenstein style engine many times.

[Gez]

Short answer: no.

Long answer: nope.

[Maes]

True ray casting means that you project a ray from each and every object (or pixel of the object) you want to render, and see if it intersects your view plane first. If yes, then that point is visible. If not, then it's
hidden.

Of course, if you truly do it on a pixel-by-pixel basis it will be shit-slow, so you can take some shortcuts like e.g. checking only some pixels of a wall and taking advantage of map geometry (e.g. in Wolf3D there's no up/down view nor height variation, so checking just the points across a wall's center line might be sufficient.

With BSP, you try being a bit smarter about it, and its purpose is exactly avoiding "brute force" checking, which is basically what raycasting does.

[fraggle]

No.

[Blzut3]

What Gez said.

Optimus said:

My other question is, maybe some of the alpha versions of Doom relied on raycasting before moving on to BSP with no raycasting? Or maybe some of the other Doom ports on Jaguar or other platforms used raycasting on the BSP trees? (The Jaguar source is full of assembly for these parts, but the function names and what they do seem to be the same). I see both seemingly educated programmers arguing in some places, some saying NO definitely not raycasting, others being also certain, like YES it does do raycasting but on BSP trees.

It's possible some of the early alphas did if you consider the Shadowcaster engine an alpha of Doom. Otherwise I'd be surprised if any version of Doom used ray casting. (And honestly I would not be surprised if I found out Shadowcaster uses BSPs, but I haven't looked at the game much.)

As for console versions, as you noted the SNES branch of the Wolf3D engine uses BSP rendering since it's faster.

Optimus said:

I didn't know BSPs could prove to be faster (is it?) in older hardware. I never coded a BSP engine but have coded raycasting wolfenstein style engine many times.

Ray casting is a very simple rendering method, but that doesn't make it fast. As Maes says, the BSP rendering method, which is basically polygon projection, avoids doing a lot of brute force work. Especially if you have large wall segments (like Wolf3D tends to have and even more so for the SNES branch since the texture count is reduced). As you noted, for BSP you only need to do two distance calculations and the columns between the left and right side can be interpolated.

Maes said:

(e.g. in Wolf3D there's no up/down view nor height variation, so checking just the points across a wall's center line might be sufficient.

I don't believe adding height variation to the Wolf3D engine would change anything in this regard.

[Quasar]

Blzut3 said:

What Gez said.

It's possible some of the early alphas did if you consider the Shadowcaster engine an alpha of Doom. Otherwise I'd be surprised if any version of Doom used ray casting. (And honestly I would not be surprised if I found out Shadowcaster uses BSPs, but I haven't looked at the game much.)

Nope, the original Doom engine used an ad hoc sector-based rendering algorithm, which Romero broke with some concentric circles that eventually became part of E1M2. Carmack was dissatisfied with the limitations of this algorithm and went to research BSP trees. The rest is, as they say, history. I'm not sure which out of the alphas is still using the sector-based algorithm, if any are other than the 0.2 alpha... Does the 0.4 alpha have BSP lumps in its IWAD? I know for certain the 0.5 alpha is using BSPs. The pre-beta is very nearly the final engine except for:

• Visplanes don't exist yet. Instead a large zoo of similar data structures are used in an apparently needlessly complicated scheme.
  
• Drawsegs are unfinished and look like Romero literally made Carmack stop coding for a second so he could build the release.
  

I think the tech break was fairly clean between the ShadowCaster experimental engine and the first Doom algorithm, considering the former is still cell-based and the latter uses linedefs and sectors. Some of the dressings are likely related though, like the colormapping.

[Optimus]

Ok, confirmed now!

Good explanation on the BSP thing. Makes me wanna start making first tests on PC and then try to port to CPC. Non orthogonal walls, even with simple rooms would be impressive, wondering why most 8bit engines go the wolfenstein way.

[Maes]

Optimus said:

wondering why most 8bit engines go the wolfenstein way.

I can think of two reasons:

1. Coding simplicity
   
2. The (reasonable) expectation that a simpler engine will also be faster
   

Of course, b) might not be true once the levels start getting bigger and bigger and occlusion testing starts dominating rendering time. AFAIK, the only Doom port for an 8-bit system that uses actual BSP for rendering (and part of the actual SC) is the Vic-20 port:

TBQH however, at such a low resolution, the benefits of a non-orthogonal architecture are barely visible. Compare it with M.O.O.D.:

It doesn't help that in most 8-bit systems the display is not chunky, and you cannot really render pixel-by-pixel without a significant time penalty (the CPU doesn't have cycles to spare, either), so you'll have to use a very low horizontal (at least) resolution, as the Z80 CPU can only move 8 and 16 bits at a time efficiently, without resorting to expensive bit shifting and masking.

So on a CPC you'll have to write either 2 pixels at a time (in mode 0) or even more in Mode 1 and 2. I am not sure if on the CPC it's more efficient to do character or tile/bitblt-based rendering, like on the Spectrum and C64, but those modes of course impose even lower resolutions, as the minimum drawable unit is even bigger than a horizontal group of pixels.

[Optimus]

So on a CPC you'll have to write either 2 pixels at a time (in mode 0) or even more in Mode 1 and 2. I am not sure if on the CPC it's more efficient to do character or tile/bitblt-based rendering, like on the Spectrum and C64, but those modes of course impose even lower resolutions, as the minimum drawable unit is even bigger than a horizontal group of pixels.

The CPC does not have hw char modes unfortunately. One byte, which is 2 Mode 0 pixels are the easiest way to go indeed. My engine is making less than 2 VBL (more than 25fps) to render the walls. It also works with sets of unrolled codes for every different column height. And it looks like this. That's with precalced distances animation though. I never optimized the raycasting calculations which take much much more and are buggy.

[Maes]

Interesting, your engine has the same "alternating lines" look of this Wolf3D engine on an "Atari 8-bit" computer:

Not certain about which model they are referring to, but probably one of the XL/XE ones. Those had a 256 color display, and probably were able to use not only chunky modes but also Atari 2600-like scanline modes.

In any case, it seems that the CPU lower bound can be pushed quite low with these kinds of engines (the "Atari 8-bit" uses a plain 6502!), with the most critical/crippling issue being the kind of access mode the video hardware allows.

• Chunky: ideal. Simply write a pixel where you want it.
  
• Char/tile-based: fast if you settle for blocky graphics and inflexible detail, but horrible if you try pixel-by-pixel rendering. It may be possible to use it for "accelerating" drawing of some things like patterns, but it won't look like true scaling.
  
• Bit-planar w/o hardware chars/tiles: worst case scenario. At most you can accelerate horizontal or whole-block blits with memory copies, but you get all the limitations PLUS wasting CPU power. I really wonder what kind of performance they got out of EGA-mode Wolfenstein...
  
• Scanline-based: might be actually better than tile or bit-planar if you are smart enough to code an engine that renders with a purely horizontal pipeline.
  

Spectrum CPC uses a combination of char/tile based graphics, using fixed pattern fills, pre-scaled sprites and textures, and even pre-rotated textures (for things like angles), thus really using negligible CPU time. It's literally just fetching blocks from memory and throwing them to the screen.

The downside is that textures look practically the same at all scales, there's real scaling or rotating except for the floors, which seem to have some perspective.

[Optimus]

Well yes, at the time I was kinda inspired by the Atari engine. Although it was a necessity to go for byte and scanlines to draw faster and less. I've chosen a typical 64 bytes * 64 scanlines (128 lines screen area) and then I realized even this seems to be the same size on the Atari engine. So you could say I was totally inspired :)

I am wondering what video mode the atari engine uses. I don't know much about atari XL/XE.

[sheridan]

Maes said:

True ray casting means that you project a ray from each and every object (or pixel of the object) you want to render, and see if it intersects your view plane first. If yes, then that point is visible. If not, then it's hidden.

You kind of have things backwards with this, raytracing works on a per-pixel basis, not a per object basis, and the rays are cast from the observer, not from whatever objects you intend to render.

[Maes]

You are right about the direction of the rays (though it really boils down to a chicken & egg-like problem, aka semantics), but in an engine like Wolf3D's, where there are no other shapes to consider but rectangular walls of constant height, the checks pretty much get simplified to objects or portions of objects.

Once you determine that the middle row of pixels of a wall is visible, there's no point in examining the rest of the pixels: there's nothing that could possibly prevent the top and the bottom part of the wall from being rendered, even if it's partially hidden behind another wall.

Due to the engine's fixed perspective and lack of height variations, I'd be surprised if they need to check anything but a few rows at the center of the screen, TBQH, as all walls will have to converge there.

[Optimus]

Yeah, while it confused me at first, I understood this as an inverted way to explain raycasting just to extend into BSP logic. But anyway, raycasting in wolfenstein just casts one ray per column iirc.

[sheridan]

It is semantic but for sake of the explanation it's important that things are not thought of or explained on a per-object basis because that's just not how the algorithm works.

Strictly speaking raycasting and raytracing are synonymous terms in computer graphics but thanks to Wolfenstein they've taken on somewhat separate meanings. Raytracing tends to imply that you're casting one ray for every pixel, whereas raycasting implies that you're maintaining a fixed perspective along one of the axes (usually the z axis) so you only have to cast one ray per column (or row).

Even if you write a fairly complicated raycaster that involves varying height levels like Doom, it will likely not be necessary to cast more than one ray per column since you can simply keep advancing the ray either until the column is completely painted or occluded and then stop. Again, it's not necessary to cast more than one ray because you're dealing with a fixed perspective.

EDIT: If you guys are curious what I'm talking about you're free to check out a fairly advanced raycaster I wrote a few years ago here: http://github.com/SheridanR/BSDL

The code is ugly as fuck because at the time it was all very experimental and I didn't understand many good coding practices, and the column drawing code is slow as balls because I didn't realize a much faster solution was sitting right under my nose until I had already abandoned the project, but there it is nonetheless.

[Optimus]

Raycasting and Raytracing seems to be intermixed in gamedev. I was surprised to read how the scientific literature has defined the terms at first, because we mistakenly thought raycasting is something like wolfenstein, 2d rays cast per column, and true raytracing is the real thing, 3d rays through each pixel. Or it is just semantics, how we learned to call things.

The most common definition is, raycasting means you cast rays just to determine which surfaces you hit. Raytracing means to continue tracing these rays after they hit the surface, for reflections. And also shadows. Generally to cast more rays per pixel. So, technically with that definition, if you make a raytracer and don't have reflection or shadows yet, it's still raycasting. It doesn't matter if it's per pixel or per column. So, I used to joke, does it mean if you add mirrors in the original wolfenstein, it's now 2d raytracing?

But I heard more. Raycasting is also used in other things like volume raycasting, and of course in some game engines you have a function that is called Raycast and tests a single ray to the objects in the world, to determine collisions of a bullet with objects, for gameplay rather than rendering. Because that's what it is, test if ray intersects with geometry. I have heard this definition too: Raytracing is not this diferentiation, is just another rendering technique using raycasting. One to find the objects, one for every reflection and one from every light to find shadows. It uses raycasting many times and that sounds correct based on the raycasting definition.

Yeah, we are even more confused in the demoscene with terms like raymarching, distance tracing and sphere tracing. I sort of have some definitions but they are always interchanged.

[Maes]

So, Wolf3D would be a "simplified" or "limited" raycaster, because the algo doesn't go like:

For each pixel of the screen, cast a ray and see where it bumps first.

but rather

For some pixels of the screen, cast a ray and see where it bumps first.
If it bumps into something, that entire column is visible, and don't bother with the rest of its pixels.

Of course, no talk about reflections here. If you let those simplifying assumptions slip, e.g. as in Duke3D, then you have a much slower engine on your hands, as the algo practically degenerates into a brute-force affair.

[Optimus]

I would still call it a raycaster (2d).

[Maes]

Either that, or imagining that all walls were 1 pixel tall, eliminating the effect of vertical resolution from the complexity.

[sheridan]

Duke3D isn't a raycaster either. It uses a portal system to determine which sectors are visible from the current sector and then simply draws everything front to back. Vertices are occluded easily once their distance and column is determined simply by finding if a closer wall was drawn there first.

The only actual Doom-esque engine to use raycasting that I've found is the engine Bungie wrote for Marathon way back in the day. That is a true raycaster, but supports non-orthogonal walls, height differences, texture mapping on all surfaces, and room over room.

[Maes]

sheridan said:

Duke3D isn't a raycaster either. It uses a portal system to determine which sectors are visible from the current sector and then simply draws everything front to back. Vertices are occluded easily once their distance and column is determined simply by finding if a closer wall was drawn there first.

...and what is that, if not raycasting by another name? This "drawing front to back" after "determining which sectors are visible", and determining occlusions by "dirty" regions of the screen, looks an awful lot like raycasting, even if it might be a bit more
sophisticated underneath.

In any case, there seems to be somewhat of a debate on the Duke3D engine. E.g. this guy, also a qualified writer of a 3D engines, states:

Another misconception about Build is that it is not a raycaster: 
The vertices are projected first in player space and then a column/distance from POV are generated.

...which is exactly how raycasting works in my book, no matter if what you render are complex polyobjects and linedefs on a fine mesh, or "dumb" Wolf3D walls on a fixed grid.

[Optimus]

Another misconception about Build is that it is not a raycaster:
The vertices are projected first in player space and then a column/distance from POV are generated.

I am lost a bit here. Isn't this similar to what doom does at the end? Ok, it determines which walls to render, their vertices have to be projected at the end, to interpolate and render columns.

I hope he didn't misphrase it at the end, he either said "it's a misconception that Build is not a raycaster", or wanted to say "there is a misconception and so I have to stress that it's not a raycaster." He doesn't explain why he thinks(?) it's a raycaster.

Whatever, no rays are cast, is it?

[Maes]

Doom is a whole lot smarter than just "projecting vertices in user space": the position and direction the player looks determines which branch of the main BSP tree the binary traversal will set off, and after some black juju majik, Doom knows EXACTLY which walls to render and HOW to render them, angles, non-visible portions, openings and all, without doing ANY kind of geometric intersection checks.

It doesn't need to actually first draw a linedef and make a check to see if it intersects the player's eye with a geometric formula. This kind of check, in Doom, is only performed for hitscan attacks/LOS checks.

Now imagine doing a LOS check for each pixel on the screen (or almost)...that's what a fully 3D raycasting engine would have to do, with no shortcuts. Duke3D is only a step up from this, and Wolf3D keeps it manageable by having a really crude and simple geometry.

If it's not BSP, it's raycasting. Are there any other alternatives in computer land?

[Superluigieth1]

Maes said:

Are there any other alternatives in computer land?

Unreal Engine's.

[sheridan]

Maes said:

...and what is that, if not raycasting by another name?

Umm, no, it's not raycasting under another name, and you should neither call nor think of it as raycasting unless you want to look like a flaming idiot.

By your logic, nearly every 3D engine imaginable would be a raycaster, because nearly every 3D engine uses some kind of visibility check to determine if a set of objects should be drawn or not. But that is simply not the case.

Maes said:

...which is exactly how raycasting works in my book, no matter if what you render are complex polyobjects and linedefs on a fine mesh, or "dumb" Wolf3D walls on a fixed grid.

The key difference is that Wolf3D casts literal rays which gather two pieces of information:

1. The distance to the next wall from the camera at the given angle
2. The wall's texture

Neither Build nor Doom ever do this. Ergo, they are not raycasters.

Maes said:

If it's not BSP, it's raycasting. Are there any other alternatives in computer land?

Yes, it's called basic 3D transformation and rotation, and before you keep going I honestly suggest you do a little more reading on 3D graphics before you continue confusing and misinforming everyone in this thread.

There's a great deal of irony in the fact that the "black magic" you mentioned in your last post is exactly what I'm talking about. It might blow your mind to know that you can get a 3D picture on a 2D screen without using either BSPs (which have nothing to do with the drawing part - they simply determine which lines should be drawn) or raycasting at all.

[Blzut3]

To me, it's not a ray caster if its rendering process can't be parallelized by simply dividing the screen and have close to zero overhead over the single threaded version (memory aside). But I could be oversimplifying things.

[Optimus]

I gotta see how Duke uses portals. I think when a portal is in your view, then you know this portal is connected with the next sector, so you check in the narrower view through this portal for walls or more portals in this other sector, and repeat. I think you kinda have to intersect the view (or the view frustum in 3d) with the lines in next sector, so if intersections of rays at the edges of the view are checked, the you could say the algorithm uses raycasting for it's purprose. I wouldn't call the engine itself raycaster though. Gotta check oneday how the portal system works though, in Fabien's site it really looks much more simple than Doom's engine.

I also found today in this interview, Catacombs 3D, while it looked exactly like wolfenstein, it wasn't using raycasting.

The internal rendering was very different from Catacombs 3D. Catacombs used basically a line- rasterization approach, whii Wolfenstein used a much more robust ray-casting approach. But the end result was that they rendered the same pictures.

Different approaches for the same kinda of visuals, cool.

[Maes]

Uh oh. Seems like I struck a sensitive nerve here. And nothing tells you you're on the right path than when the ad-hominems start flying ;-)

Seriously, this is like the big endian/little endian debate (the one in Gulliver's travels, not the one in CS). But for one last time (sigh).

Broadly, 3D engines can be divided in those that use a precalculated structure to determine visibility (BSP or octrees, for instance), and those that use geometric projection checks, no matter under which guise.

3D polygon engines may use some clever geometric clipping or let the hardware handle it. Software raycasting engines use geometric projection checks at the pixel level, though they don't need to extend to EVERY pixel on the screen for the reasons we already mentioned. But not every engine with a geometric projection check system is a raycaster

So, the main classes are precalculated and geometry-checks based, to dumb things down even more. Almost every 3D engine you can think of will belong to one of those two broad categories. Tertium non datur.

[sheridan]

Seriously guys, this is not a complicated issue. There's no beating around the bush here and no opinion to be had. Just a lot of misinformation flying around. Even if you were to go on Carmack and Silverman's words alone, you'd find Doom and Build are not raycasters. So it's completely pointless to continue trying to understand things in that way instead of realizing that you're wrong and learning how things actually work.

Optimus said:

I think you kinda have to intersect the view (or the view frustum in 3d) with the lines in next sector, so if intersections of rays at the edges of the view are checked, the you could say the algorithm uses raycasting for it's purprose.

Close, but no cigar. Seeing if a portal has been occluded by a wall (or anything else) in screen space is not raycasting.

Maes said:

Uh oh. Seems like I struck a sensitive nerve here. And nothing tells you you're on the right path than when the ad-hominems start flying ;-)

What I said was not fallacious. I told you you should not use the word "raycasting" as you have been unless you want to look idiotic (which is true) and that you seem to know very little about how 3D graphics works (which is also sadly true). Neither of these statements had any bearing on the rest of what I said, which explained very simply how Doom and Build aren't raycasters.

Take a look, you may be surprised to find all ad hominems are not inappropriate. It's sort of like that misconception that you "can't prove a negative." Modus tollens anyone?

http://en.wikipedia.org/wiki/Ad_hominem
http://en.wikipedia.org/wiki/Ad_hominem#Types_of_ad_hominem_reasoning

Maes said:

So, the main classes are precalculated and geometry-checks based, to dumb things down even more. Almost every 3D engine you can think of will belong to one of those two broad categories. Tertium non datur.

I'd agree with you completely if not for the fact that the issue at hand is not about whether you can divide computer graphics into two distinct categories or not. The issue is that you've been confusing the explanation, first by explaining raycasting badly, and then by attempting to use it as a general term for all kinds of occlusion and surface culling (except for BSPs, hurr durr). Call me pedantic if you want to but explanations like these just don't help anyone to understand anything.

That being said, if you feel like stepping away from your past statements now just so you can make a point about the difference between dynamic and static vision tests, that's fine, but don't gaslight me about the kind of detailed bullshit you've been saying about how 3D graphics works in general. You're very mistaken there and it's annoying to listen to you propagate your confusion to everyone else.

EDIT: This is a little late in coming, but I also think it's worth mentioning that it's a little silly to think of BSPs as the holy grail of computer graphics while portals are merely a "step-up" from raycasting. Both methods have clear cut uses, and Build can easily stand up to Doom in terms of both performance and feature set. Indeed, just the fact that BSPs preclude Doom's walls from moving is a pretty severe limitation in and of itself that Build clearly has no problem with.

[Maes]

Yup, seems like I struck a nerve there. I'm sorry that you feel this way.

Spoiler

*Adds "raycasting" to a long list of things causing immense butthurt for little or no reason to specific people. Examples: voxel graphics, Macintosh computers, adware bundles....*

Congratulations for the "sometimes ad-hominems are appropriate" comeback though. It's like saying "sometimes insulting is justified". And for someone who's just a few days on this forum, you sure were quick to make that judgement call. And with what aplomb! What resolution! What class! Like a boss! We certainly need more like you here.

Well, since you seem to be an OK (?) fellow who's obviously been there and knows his shit, answer me this question which has been bugging me for a long time: what do you reply to a woman asking you if a certain item of clothing makes her look fat?