<p>Congratulations for having progressed so far.</p>
<h2>Context, first analysis</h2>
<p>Your explanation:</p>
<blockquote>
<p>I am using a z-buffer, with one stored length to a wall for the x coordinate of each ray.</p>
</blockquote>
<p>Means the z-buffer is currently one-dimension.</p>
<p>One dimension is enough in the first case (your first two images) but not in the second case. To see why, imagine that the red tomato sprite was closer to the player, such that the left half of it would be partially obscured by the first wall (bottom left). Since the top of that wall is projected to a diagonal line, it means that the property &quot;is pixel P of the sprite obscured?&quot; does not only depend on X but also on Y.</p>
<p>So, in the exact setup you have, a 1D Z-buffer is definitely not capable of performing the clipping you want.</p>
<h2>Options</h2>
<p>From that on, here are a few options:</p>
<ul>
<li>switch to a 2D z-buffer (slower)</li>
<li>switch to painter's algorithm (slower)</li>
<li>switch to a 2D-based occlusion algorithm</li>
<li>study how Doom did it</li>
</ul>
<p>Your geometry seems similar to Doom. It is probably a very good investment for you to study how the Doom rendering engine works. It clips sprites (called &quot;things&quot;) using a 1D criterion, then refines. One area has only one floor height and one ceiling height. This is very important and it looks like your geometry is similar.</p>
<h2>Solution</h2>
<p>The solution, to summarize, is to keep not only a 1D z-buffer, but actually a structure keeping for each sector (in doom parlance) the lines that make the limit and their parameters (like the a and b in y=ax+b).
Then, when you want to draw the sprite, clip X with 1D criterion but <strong>depending on the sector the sprite is in</strong>, and then limit the Y range of pixels drawn based on the y=ax+b of the sector just in front of it.</p>
<p>I don't know what data structure you currently have in your program. If this seems totally unreachable, then you need to rethink the data structure you keep while drawing.</p>
<p>If you haven't yet, you should read (sorry if you did already) <a href="https://doomwiki.org/wiki/Doom_rendering_engine#Rendering" rel="nofollow noreferrer">https://doomwiki.org/wiki/Doom_rendering_engine#Rendering</a> and the pages behind the links there, perhaps run their code in slow motion or see a video where someone shows/explains how it works.  This one lacks explanations but might help your intuition: <a href="https://www.youtube.com/watch?v=gfM6NpxmVGg" rel="nofollow noreferrer">https://www.youtube.com/watch?v=gfM6NpxmVGg</a> .</p>
<p>Hope this helps.  Keep up the good work!</p>

CC BY-SA 4.0
2021-07-05T18:19:30.697Z
See also https://twobithistory.org/2019/11/06/doom-bsp.html#bsp-trees-in-doom "the Doom renderer uses a kind of implicit z-buffer that provides much of the benefit of a z-buffer with a much smaller memory footprint. There is one array that keeps track of occlusion in the horizontal dimension, and another two arrays that keep track of occlusion in the vertical dimension from the top and bottom of the screen." (...) "It then draws the enemies in back-to-front order, clipping them against the segments of the screen that occlude them."
Stéphane Gourichon
CC BY-SA 4.0
2021-05-28T20:24:54.800Z
2021-05-28T20:24:54.800Z
Stéphane Gourichon
<p>I am writing a raycasting engine. At this point, I have added sprites, and I am using a z-buffer, with one stored length to a wall for the x coordinate of each ray. Below is an image of a sprite which is fully visible.</p>
<p><a href="https://i.sstatic.net/6H5kA.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/6H5kA.jpg" alt="Image 1" /></a></p>
<p>Z-buffering works fine when my vertical height is zero, as seen below.</p>
<p><a href="https://i.sstatic.net/ZASqq.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ZASqq.jpg" alt="Image 2" /></a></p>
<p>However, when I change my vertical height and stand on top of a wall, as seen below, my sprite becomes only half-visible. I understand why this is true; the Z-buffer is only accounting for the first level of vertical height, and so it seems like the sprite should be partially obscured, even when it is not.  However, there also cases when most of a sprite is obscured except for the top. In that case, I could not simply have a z-buffer for each level of vertical height. Does anyone know of an algorithm that can determine the visible area of a billboard sprite in a raycasting environment?</p>
<p><a href="https://i.sstatic.net/sYGg5.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/sYGg5.jpg" alt="Image 3" /></a></p>

<depth-map><z-buffer><occlusion><scanline>
A solution to sprite visibility in a raycasting engine with variable wall heights?
Caspian Ahlberg
# A solution to sprite visibility in a raycasting engine with variable wall heights?

(Asked by: username_0 on 2021-05-28)

I am writing a raycasting engine. At this point, I have added sprites, and I am using a z-buffer, with one stored length to a wall for the x coordinate of each ray. Below is an image of a sprite which is fully visible.

[![Image 1](https://i.sstatic.net/6H5kA.jpg)](https://i.sstatic.net/6H5kA.jpg)

Z-buffering works fine when my vertical height is zero, as seen below.

[![Image 2](https://i.sstatic.net/ZASqq.jpg)](https://i.sstatic.net/ZASqq.jpg)

However, when I change my vertical height and stand on top of a wall, as seen below, my sprite becomes only half-visible. I understand why this is true; the Z-buffer is only accounting for the first level of vertical height, and so it seems like the sprite should be partially obscured, even when it is not. However, there also cases when most of a sprite is obscured except for the top. In that case, I could not simply have a z-buffer for each level of vertical height. Does anyone know of an algorithm that can determine the visible area of a billboard sprite in a raycasting environment?

[![Image 3](https://i.sstatic.net/sYGg5.jpg)](https://i.sstatic.net/sYGg5.jpg)

**Tags:** depth-map, z-buffer, occlusion, scanline


---

## 1 answers

### Answer by username_1 on 2021-05-28. Score: 2 | Accepted answer

Congratulations for having progressed so far.

## Context, first analysis

Your explanation:

> I am using a z-buffer, with one stored length to a wall for the x coordinate of each ray.

Means the z-buffer is currently one-dimension.

One dimension is enough in the first case (your first two images) but not in the second case. To see why, imagine that the red tomato sprite was closer to the player, such that the left half of it would be partially obscured by the first wall (bottom left). Since the top of that wall is projected to a diagonal line, it means that the property "is pixel P of the sprite obscured?" does not only depend on X but also on Y.

So, in the exact setup you have, a 1D Z-buffer is definitely not capable of performing the clipping you want.

## Options

From that on, here are a few options:

* switch to a 2D z-buffer (slower)
* switch to painter's algorithm (slower)
* switch to a 2D-based occlusion algorithm
* study how Doom did it

Your geometry seems similar to Doom. It is probably a very good investment for you to study how the Doom rendering engine works. It clips sprites (called "things") using a 1D criterion, then refines. One area has only one floor height and one ceiling height. This is very important and it looks like your geometry is similar.

## Solution

The solution, to summarize, is to keep not only a 1D z-buffer, but actually a structure keeping for each sector (in doom parlance) the lines that make the limit and their parameters (like the a and b in y=ax+b).
Then, when you want to draw the sprite, clip X with 1D criterion but **depending on the sector the sprite is in**, and then limit the Y range of pixels drawn based on the y=ax+b of the sector just in front of it.

I don't know what data structure you currently have in your program. If this seems totally unreachable, then you need to rethink the data structure you keep while drawing.

If you haven't yet, you should read (sorry if you did already) <https://doomwiki.org/wiki/Doom_rendering_engine#Rendering> and the pages behind the links there, perhaps run their code in slow motion or see a video where someone shows/explains how it works. This one lacks explanations but might help your intuition: <https://www.youtube.com/watch?v=gfM6NpxmVGg> .

Hope this helps. Keep up the good work!

> **Comments:**
> **username_1**: See also https://twobithistory.org/2019/11/06/doom-bsp.html#bsp-trees-in-doom "the Doom renderer uses a kind of implicit z-buffer that provides much of the benefit of a z-buffer with a much smaller memory footprint. There is one array that keeps track of occlusion in the horizontal dimension, and another two arrays that keep track of occlusion in the vertical dimension from the top and bottom of the screen." (...) "It then draws the enemies in back-to-front order, clipping them against the segments of the screen that occlude them."  

---

