Search In
• More options...
Find results that contain...
Find results in...

# How Doom engine decides, which pixels to display from afar?

## Recommended Posts

In Doom, as it should be, things from afar looks smaller than if they are next to the player. Though, because of the low resolution of the original game (320x200 maybe?), far things are not more than some pixels. This was especially strongly noticeable for me on Doom2 MAP13 start, where Pinkies were roaming at the top of a building in the middle of the map.

How the engine calculates, which pixels to display? This is something I simply couldn't understand while I tried to understand the working mechanics of raycasting.

Very simply, the engine "skips" entire rows of pixels in each sprite or texture column depending on the drawing scale, or, conversely, draws each pixel more than once if something is to be drawn closer to the player.

Imagine if you have e.g. a column with 100 pixels. If you have a pixel stepping of 1, you draw every single one of them (no scaling). If you skip every other pixel (stepping of 2), you will only draw 50 pixels, and scale the column down. The Doom engine also allows "fractional" steppings.

Only walls are drawn by raycasting, things and flats aren't. For things, a very simple algorithm is used: first, things are sorted by distance and drawn in order from farthest to closest (painter's algorithm). Things are projected onto screen coordinates and drawn column by column, skipping or duplicating certain columns depending on the scaling factor (determined by distance and screen size) as described above. Each column drawn is scaled vertically the same way and clipped to previously drawn segs, if the thing's centre is behind the seg (according to the BSP). Since only the centre of the thing is checked, if the thing intersects the seg, it may be clipped incorrectly.

Actually, the individual columns of (unmasked) textures are drawn by exactly the same algorithm used for sprites (slightly modified to optimize drawing of unmasked textures). The only major difference is that wall drawers also can account for different view angles, while sprites are always drawn as if they were walls viewed full-frontal.

Masked textures in particular use the same exact column drawing functions as sprites, in addition to having regular walls' angle handling.

Thanks Maes!

Maes said:

Actually, the individual columns of (unmasked) textures are drawn by exactly the same algorithm used for sprites (slightly modified to optimize drawing of unmasked textures). The only major difference is that wall drawers also can account for different view angles, while sprites are always drawn as if they were walls viewed full-frontal.

Erm, yes, and the way that the wall drawing routine accounts for different angles is by raycasting, which is not used by sprites. Sprites are not drawn as if the were walls, in a manner analogous to the "billboard" technique used by modern 3D engines, but are instead projected into 2D screen space by the R_ProjectSprite() function. This is much faster than the algorithm used for walls, since R_DrawVisSprite() can just step through columns the same way it steps through pixels within a column (since all the columns are at the same z-depth), instead of having to work out where each column is individually.

There is no raycasting involved in the Doom engine. Old myth that won't die.

The Doom engine uses a Binary Space Partitioning tree to provide a correct drawing order for all camera points. This is the exact same algorithm later applied in full 3D for the id Tech 2 engine, and STILL in use in modern game engines.

The only part of Doom's renderer that's even remotely similar to a raycasting engine is the code that it uses to clip things in screen space, so that for example the corner of a wall can clip away half of an Imp. A very similar approach is used in advanced raycasters. Otherwise, there is no resemblence.

The algorithm used to step through the blockmap when firing tracers on the other hand is more or less a raycast, with a lot of added nonsense. But that has nothing to do with rendering :P

I have a little difficulty recognizing the code in these descriptions.
When I wrote the 15bit, 16bit, 24bit, and 32bit rendering for DoomLegacy, I remember it being this way.

1. The sprite, wall, and flat renderers converts offsets to fixed point texture coord.

2. Steps through the screen pixels covered by the draw, calculating in fixed point math which texture pixel to draw. To do this a constant fractional texture step is used, which may be smaller than 1 (up close, possibly reusing some texture columns) or larger than 1 (far away, possibly skipping some texture columns).
The fixed point texture position is truncated to an integer texture index, which may skip or dup some texture columns in a very irregular unpredictable way.
In this stepping it assumes all textures are only perfectly vertical, so texture columns align with screen columns, so no tilting of textures can occur.
This may skip or dup some columns, but only as a side effect. There should be no dup code in this rendering.

3. Sprites are rendered with transparent detection.

4. Walls are rendered with an additional fractional step of the top and bottom edges on the screen for each column. Scaling of the column is re-calculated.

5. There are explicit dup video settings for displaying text, intro pics, and intermission pics, to scale these to multiples of the pic size. In such cases there are filler bars around the displayed pic. Other modes, like OpenGL, will instead stretch the pic to fill the screen or window.

6. In OpenGL most of the above does not apply.

Quasar said:

There is no raycasting involved in the Doom engine. Old myth that won't die.

Upon closer inspection of the code, you're absolutely right. OP, quit confusing me. >.<

Sorry, I thought that Doom uses raycasting.

Raycasting: There is the book description that I last remember which is to throw out rays from the view point (for each screen pixel) and see what object, wall, etc. they hit first, and draw that. If it has transparency then keep following the ray until it hits something solid.

Doom uses occlusion, which is to draw everything, but draw it in distance order so that the far things are drawn first and the closer things are drawn over them. This results in much overdraw, which is a waste because it is not seen by the viewer.

As a speedup it calculates some special cases of occlusion before drawing, such as lower and upper thresholds of windows (ceiling and floor height changes of adjacent sectors). It keeps track of this as clipping, which moves the upper and lower edges of walls so they may be drawn in BSP order.

The BSP order itself imposes a back to front draw order. The BSP also uses the block map and reject map to do more occlusion culling.

Sprites are drawn in distance order over each other. Details will differ with the engine and draw library. The sprite can be clipped by the wall and drawn later, or it could be drawn first and then drawn over. Transparent walls must be considered too.

Transparent walls are drawn in distance order after all BSP drawing. In this case the overdraw is intentional and necessary. It gets complicated with more sorting when sprites are also involved.
Transparent walls include midgrate textures (patch open areas), and Boom effect transparency (alpha channel).

Using OpenGL forces some variations in sprite and transparent wall drawing.

Doom draws front to back.

I assume the "Doom draws front to back" applies to the BSP sector drawing order. I have never known any statement to apply equally to all parts of Doom rendering. It seems to me that BSP enters stuff into seg lists in front to back order.
I am not sure what order it actually gets drawn, and with correct clipping it would not matter for most walls.

As BSP draws parts of a front sector first, then the occlusion detection and the resultant clipping of the farther walls becomes a necessary part of the render process.
I would still call this occlusion detection.

For sprites vrs walls and other sprites, that is pure overdraw as far as I know.

I may have been working on DoomLegacy rendering too much lately.
There are differences due to transparent walls and 3d floors.
It is critical in DoomLegacy to draw back to front because not everything is clipped properly (clipping gets complicated with 3d floors).

There was a very nice animated gif around somewhere, which showed EXACTLY how Doom's rendering works...

In any case, rendering order may appear arbitrary to a casual observer. I really NEED to find that GIF now :-/

That's also a cool example, though the one I had in mind (and found again) is probably more familiar (and embeddable):

TBQH, I don't remember exactly where I first found it, but there's no obvious way to track it down via googling.

@Maes: That gif is stopping at an incomplete state after drawing a few walls -- is it supposed to, or is it not loading properly? Either way, it's best to not embed it since it's so large.

At any rate, this is actually confusing me a bit, for one reason in particular: if Doom is drawing things back-to-front, then why do things that don't get drawn because they're completely occluded get added to the seg count?

Walls are drawn front to back. It's sprites and masked midtextures that are drawn back to front.

Welp. Should've said "lines," not "things" -- I sometimes forget that "thing" has a very specific meaning in Doom's context when chatting casually. :P

Xaser prolly should've said:

At any rate, this is actually confusing me a bit, for one reason in particular: if Doom is drawing lines front-to-back, then why do lines that are completely occluded by other geometry (and therefore don't get drawn) get added to the seg count?

[Also corrected the sentence structure for clarity and one other obvious mistake, so there. Maybe I shouldn't post before coffee.]

The image is broken - I'm having some major problems with my connection -especially FTP transfers seem to fail halfway :-/ It's supposed to be about 625KB.

In any case, Doom draws in whatever order the BSP tree was compiled -it's perfectly possible to feed it with a "borked" BSP that will produce a back-to-front rendering, but there's occlusion testing anyway, so overdraw is practically non-existent and there are hacks to account for "openings" (e.g. windows, doors, etc.).

The only side effect will be somewhat slower rendering, while a properly made BSP is supposed to minimize overdraw and the need for explicit occlusion tests.

With no BSP at all, the engine would try to render everything (at least everything in the player's FOV), and it would only be by pure chance if occlusion testing would "catch" an overdraw. Games like Doom which however lacked a BSP tree (e.g. Duke Nukem 3D) showed full well why this was not a good idea: the performance tradeoff to make was too big, and even if visually Duke Nukem didn't look all that more detailed or impressive compared to Doom, it ran like molasses.

Also, in Doom, the only thing that's clearly drawn back-to-front with no account for overdraw whatsoever are sprites. It might be possible to draw them front-to-back using some sort of "dirty regions buffer" but I doubt if the gains would ever offset the overhead of checking, even in NUTS-like maps. Maybe only with a limited buffer, only activated for e.g. sprites right up the player's face, which would quickly reject visibility of a distant sprite if it was entirely contained in a "dirty" zone -some way of quickly encoding rough contours would be needed, so that you don't need a pixel-precise buffer though.

I have spent hours watching something similar in DoomLegacy.
You stick the following in at points of interest in your draw routines, and you can watch it draw. You can place as many as you want.
This depends on the port you are examining actually using the same names.
Many did not implement I_Sleep properly, so consider using your OS native sleep function.

#define WATCH_DRAWING

Draw loop

#ifdef WATCH_DRAWING
I_FinishUpdate();
I_Sleep(100);
#endif

Draw_something

End Draw loop

In DoomLegacy all sprites are considered to be potentially translucent. Such are fireballs, burning barrels, torches, etc..
All 3D floors in DoomLegacy are also all potentially translucent (water, fog, glass, etc..).
All translucent must be drawn back to front because other walls and sprites are visible through them. DoomLegacy spends much effort re-sorting the drawing order to be back to front.

Other ports with translucent walls or sprites must also re-sort those to draw them back to front, such as Boom translucent wall textures.

Vanilla BSP draw with sprites also makes a notable error with sprites where the image exceeds the physical size. Nearby walls will clip a sprite, but not floors or ceilings.
So if you have a sprite with a tail the extends past the physical size, that monster in a hole can have its tail drawn over the surrounding floor.
The physical size checks keeps it from getting too close to a wall most of the time, but where the tail sticks out it escapes this limitation. The view window clipping due to sector height differences will clip most of the sprite tail, but will miss any part of the tail the sticks out to the side of the backface surfaces of the hole.

If you think overdraw is a problem with "regular" ports, wait until you play -patiently- through an entire cDoom map: imagine the sprite & masked texture drawing algorithm but hacked to also include flats. Yup, that can look as "pretty" as it sounds.

wesleyjohnson said:

Vanilla BSP draw with sprites also makes a notable error with sprites where the image exceeds the physical size. Nearby walls will clip a sprite, but not floors or ceilings.

This is not actually an error; it is necessary because the art is drawn with a 3D perspective, resulting in parts of the sprite that are "in front of" the center being drawn "below" the base of the Thing. This diagram will hopefully explain what I'm babbling about :

```  _____ _____ Top of sprite graphic
/     \
/   .___\____ Top of physical Thing
\       /
|\_____/|
|       |
|       |  <- Barrel (perspective exaggerated)
|\_____/|
|       |
|       |
|\_____/|
|   .___|____ Bottom of physical Thing
\       /
\_____/_____ Bottom of sprite graphic
```
Naturally, if the top and bottom of the sprite is clipped to the floor or ceiling height, it would look completely wrong.

wesleyjohnson said:

The view window clipping due to sector height differences will clip most of the sprite tail, but will miss any part of the tail the sticks out to the side of the backface surfaces of the hole.

The specific case of a Thing in a hole could perhaps be fixed by clipping sprites to visplanes with a higher floor or lower ceiling, though even that's not perfect. We just have to accept the fact that sprites are a 2D representation of a 3D object, and as such any scene where a sprite intersects world geometry cannot be rendered accurately, since the sprite simply doesn't contain the 3D information needed for correct clipping.

Foxpup said:

Naturally, if the top and bottom of the sprite is clipped to the floor or ceiling height, it would look completely wrong.

Hardware-accelerated ports demonstrate this, by the way.

I don't think that any of the advanced ports handle sprites in a 3d way. It would require a 3d model
and the nature of drawing the 3d model would involve clipping parts of the model individually.
Vanilla drawing takes the sprite as a flat sheet and draws it facing the player, with only scaling adjustment.

The vanilla drawing error I mentioned is not that floors and ceilings don't clip. I was referring to the fact that the BSP wall clipping
does not account for sprites that have graphics that exceed the physical size. OpenGL handles the same sprite naturally and other techniques that advanced ports may use, have intermediate success.

It is an error because the tip of tail should not be visible but is drawn anyway. As an example, put the FreeDoom imp in a hole.
I have spent considerable time trying to fix this draw problem in DoomLegacy and have not found an easy way to clip that tail.

wesleyjohnson said:

I don't think that any of the advanced ports handle sprites in a 3d way. It would require a 3d model
and the nature of drawing the 3d model would involve clipping parts of the model individually.

Not necessarily. Another option is to give each sprite a depth map, giving each pixel a z-offset for clipping. I'm not sure if anyone's done anything like that though.

wesleyjohnson said:

The vanilla drawing error I mentioned is not that floors and ceilings don't clip. I was referring to the fact that the BSP wall clipping
does not account for sprites that have graphics that exceed the physical size. OpenGL handles the same sprite naturally and other techniques that advanced ports may use, have intermediate success.

It is an error because the tip of tail should not be visible but is drawn anyway. As an example, put the FreeDoom imp in a hole.
I have spent considerable time trying to fix this draw problem in DoomLegacy and have not found an easy way to clip that tail.

There is literally no good way to clip a sprite that intersects a wall that works correctly in all cases. It's inherently impossible when representing a 3D object as a 2D graphic.