<p>If anyone runs into this in the future:</p>
<p>What I did was, I used @lightxbulbs suggestion and made a sandwich although I used two planes instead of a prism because plane intersections are easier and simpler to calculate. I capped the intersection distance at 0 if it is negative and then calculated the intersection point (or the starting position if the intersection is behind the camera).</p>
<p>Then I do a few iterations of DDA (efficient grid traversal) looking for a texel with the correct depth that is also full.</p>
<p>If I find such a texel for the given pixel then I know my current ray MUST intersect one of the cubes. Then I raytrace normally from a small offset away from the intersection point.</p>
<p>I get this:</p>
<p><a href="https://i.sstatic.net/PDVDs.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/PDVDs.png" alt="enter image description here" /></a></p>

CC BY-SA 4.0
2022-05-14T19:14:54.577Z
2022-05-14T19:14:54.577Z
Makogan
<p>I am making a procedural sdf (just a bunch of cubes) based of an image. The idea is very simple. We have a stencil image:</p>
<p><a href="https://i.sstatic.net/KJL4u.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/KJL4u.png" alt="enter image description here" /></a></p>
<p>Each texel in the image corresponds to a 3D cube. So to ray trace what I am doing is, calculate the intersection with the plane where the image should live. Grab that point and cmpute the discrete coordinate of the texel corresponding to the collision point. e.g. if each texel corresponds to a cube of size <span class="math-container">$s$</span> and the plane corresponds to the union of the front faces of all squares we have:</p>
<p>Let <span class="math-container">$p$</span> be te point of intersection between the ray and the plane, the discrete cooridnate is <span class="math-container">$\lfloor p / s \rfloor$</span>.</p>
<p>This allows me to find the position of the cube sdf corresponding to the face being collided with. If I raytrace this sdf I get:</p>
<p><a href="https://i.sstatic.net/oiuJ6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/oiuJ6.png" alt="enter image description here" /></a></p>
<p>Which is an infinite tiling of cubes. Now I can use the above texel coordinate and the image to figure out if the point of collission <span class="math-container">$p$</span> corresponds to a full texel or not. If the texel is empty then i can modify the cube sdf to return infinity, making it be equivalent to an &quot;empty&quot; sdf.</p>
<p><a href="https://i.sstatic.net/pPxIM.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/pPxIM.png" alt="enter image description here" /></a></p>
<p>This did get rid of unwanted cubes, but now things look 2D. Since I am deciding which cubes to keep and which to throw based on the planar information, when we are looking from the side (or any angle induced by perspective) a ray that would have collided against a filled cube will collide first agianst an empty one and be discarded when it should actually collide.</p>
<p>I can correct this by not testing just the current cube sdf, but the 8 neighbours as well:</p>
<p><a href="https://i.sstatic.net/hodDv.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/hodDv.png" alt="enter image description here" /></a></p>
<p>This is much better and it looks solved, except...</p>
<p><a href="https://i.sstatic.net/Gj7Cr.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Gj7Cr.png" alt="enter image description here" /></a></p>
<p>A steeper angle will cause the issue from before. Now the ray is colliding against an empty texel much farther away from the filled ones and beign discarded when it should collide.</p>
<p>I was hoping someone could suggest a way to specify my sdf such that I get soemthing like the second to last picture from any angle:</p>
<pre><code>float CubeSdf( vec3 p )
{
    p -= vec3(voxel_size / 2.f);
    vec3 b = vec3(voxel_size / 2.f) - vec3(rounding) * 0.95;
    vec3 q = abs(p) - b;
    return (length(max(q,0.0)) + min(max(q.x,max(q.y,q.z)),0.0)) - rounding;
}

float CrossSdf( vec3 p, ivec2 map_index)
{
    vec3 position = vec3(-voxel_size * float(map_index.x), 0, -voxel_size * float(map_index.y));
    // vec3 position = vec3(0);

    float final = 1e30;
    int radius = 1;
    const ivec2 texture_size = textureSize(terrain_map, 0);
    for(int i=-radius; i&lt;=radius; i++)
    {
        for(int j=-radius; j&lt;=radius; j++)
        {
            ivec2 sample_coord = ivec2(map_index.x + i, texture_size.y - map_index.y - j);
            bool inside_bounds =
                sample_coord.x &gt;= 0 &amp;&amp; sample_coord.x &lt; texture_size.x &amp;&amp;
                sample_coord.y &gt;= 0 &amp;&amp; sample_coord.y &lt; texture_size.y ;
            float val = texelFetch(terrain_map, sample_coord, 0).r * int(inside_bounds);
            vec3 offset = vec3(float(i) * voxel_size, 0, float(j) * voxel_size);
            final = min(final, CubeSdf(p + position - offset) + float(1e30) * float(val &lt;= 0));
        }
    }

    return final;
}
</code></pre>

CC BY-SA 4.0
2022-05-13T13:43:21.610Z
Make the initial triangle a prism. Then the "texels" correspond to a whole extruded volume, and if you hit it from the side, everything is still fine.
lightxbulb
CC BY-SA 4.0
2022-05-13T19:02:49.757Z
That would work for this specific shape, but the point of using a texture is that there will be much more complciated shapes represented by the texel data. Creating a generalized prism for the outline of the shape seems like overkill.
Makogan
CC BY-SA 4.0
2022-05-13T20:15:31.390Z
I think the ray is simply missing the triangle in the second case, or am I misunderstanding the problem?
lightxbulb
CC BY-SA 4.0
2022-05-13T20:54:46.407Z
There is no triangle, that first image is an actual image, i.e. a set of pixels. It is a triangle in this case, but it could be a circle, a checkerboard pattern, a 1D height map...

I need this algorithm to work for any arbitrary set of texels in the mask (the black and white image).
Makogan
CC BY-SA 4.0
2022-05-13T21:37:40.400Z
So are you using the texture as some kind of acceleration structure? In that case I think that you would need to do several steps within the texture, at the very least until your ray exits on a depth coordinate larger than your cubes. So you should compute the initial intersection, and the exit intersection and the traverse the grid between those two.
lightxbulb
<raytracing><glsl><c++><mathematics>
Defining the proper sdf for this structure
Makogan
# Defining the proper sdf for this structure

(Asked by: username_0 on 2022-05-13)

I am making a procedural sdf (just a bunch of cubes) based of an image. The idea is very simple. We have a stencil image:

[![enter image description here](https://i.sstatic.net/KJL4u.png)](https://i.sstatic.net/KJL4u.png)

Each texel in the image corresponds to a 3D cube. So to ray trace what I am doing is, calculate the intersection with the plane where the image should live. Grab that point and cmpute the discrete coordinate of the texel corresponding to the collision point. e.g. if each texel corresponds to a cube of size $s$ and the plane corresponds to the union of the front faces of all squares we have:

Let $p$ be te point of intersection between the ray and the plane, the discrete cooridnate is $\lfloor p / s \rfloor$.

This allows me to find the position of the cube sdf corresponding to the face being collided with. If I raytrace this sdf I get:

[![enter image description here](https://i.sstatic.net/oiuJ6.png)](https://i.sstatic.net/oiuJ6.png)

Which is an infinite tiling of cubes. Now I can use the above texel coordinate and the image to figure out if the point of collission $p$ corresponds to a full texel or not. If the texel is empty then i can modify the cube sdf to return infinity, making it be equivalent to an "empty" sdf.

[![enter image description here](https://i.sstatic.net/pPxIM.png)](https://i.sstatic.net/pPxIM.png)

This did get rid of unwanted cubes, but now things look 2D. Since I am deciding which cubes to keep and which to throw based on the planar information, when we are looking from the side (or any angle induced by perspective) a ray that would have collided against a filled cube will collide first agianst an empty one and be discarded when it should actually collide.

I can correct this by not testing just the current cube sdf, but the 8 neighbours as well:

[![enter image description here](https://i.sstatic.net/hodDv.png)](https://i.sstatic.net/hodDv.png)

This is much better and it looks solved, except...

[![enter image description here](https://i.sstatic.net/Gj7Cr.png)](https://i.sstatic.net/Gj7Cr.png)

A steeper angle will cause the issue from before. Now the ray is colliding against an empty texel much farther away from the filled ones and beign discarded when it should collide.

I was hoping someone could suggest a way to specify my sdf such that I get soemthing like the second to last picture from any angle:

```
float CubeSdf( vec3 p )
{
    p -= vec3(voxel_size / 2.f);
    vec3 b = vec3(voxel_size / 2.f) - vec3(rounding) * 0.95;
    vec3 q = abs(p) - b;
    return (length(max(q,0.0)) + min(max(q.x,max(q.y,q.z)),0.0)) - rounding;
}

float CrossSdf( vec3 p, ivec2 map_index)
{
    vec3 position = vec3(-voxel_size * float(map_index.x), 0, -voxel_size * float(map_index.y));
    // vec3 position = vec3(0);

    float final = 1e30;
    int radius = 1;
    const ivec2 texture_size = textureSize(terrain_map, 0);
    for(int i=-radius; i<=radius; i++)
    {
        for(int j=-radius; j<=radius; j++)
        {
            ivec2 sample_coord = ivec2(map_index.x + i, texture_size.y - map_index.y - j);
            bool inside_bounds =
                sample_coord.x >= 0 && sample_coord.x < texture_size.x &&
                sample_coord.y >= 0 && sample_coord.y < texture_size.y ;
            float val = texelFetch(terrain_map, sample_coord, 0).r * int(inside_bounds);
            vec3 offset = vec3(float(i) * voxel_size, 0, float(j) * voxel_size);
            final = min(final, CubeSdf(p + position - offset) + float(1e30) * float(val <= 0));
        }
    }

    return final;
}

```

**Tags:** raytracing, glsl, c++, mathematics

> **Comments:**
> **username_1**: Make the initial triangle a prism. Then the "texels" correspond to a whole extruded volume, and if you hit it from the side, everything is still fine.  
> **username_0**: That would work for this specific shape, but the point of using a texture is that there will be much more complciated shapes represented by the texel data. Creating a generalized prism for the outline of the shape seems like overkill.  
> **username_1**: I think the ray is simply missing the triangle in the second case, or am I misunderstanding the problem?  
> **username_0**: There is no triangle, that first image is an actual image, i.e. a set of pixels. It is a triangle in this case, but it could be a circle, a checkerboard pattern, a 1D height map...  I need this algorithm to work for any arbitrary set of texels in the mask (the black and white image).  
> **username_1**: So are you using the texture as some kind of acceleration structure? In that case I think that you would need to do several steps within the texture, at the very least until your ray exits on a depth coordinate larger than your cubes. So you should compute the initial intersection, and the exit intersection and the traverse the grid between those two.  

---

## 1 answers

### Answer by username_0 on 2022-05-14. Score: 2 | Accepted answer

If anyone runs into this in the future:

What I did was, I used @lightxbulbs suggestion and made a sandwich although I used two planes instead of a prism because plane intersections are easier and simpler to calculate. I capped the intersection distance at 0 if it is negative and then calculated the intersection point (or the starting position if the intersection is behind the camera).

Then I do a few iterations of DDA (efficient grid traversal) looking for a texel with the correct depth that is also full.

If I find such a texel for the given pixel then I know my current ray MUST intersect one of the cubes. Then I raytrace normally from a small offset away from the intersection point.

I get this:

[![enter image description here](https://i.sstatic.net/PDVDs.png)](https://i.sstatic.net/PDVDs.png)


---

