1
$\begingroup$

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

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

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

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

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

enter image description here

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;
}
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – lightxbulb
    May 13 at 13:43
  • $\begingroup$ 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. $\endgroup$
    – Makogan
    May 13 at 19:02
  • $\begingroup$ I think the ray is simply missing the triangle in the second case, or am I misunderstanding the problem? $\endgroup$
    – lightxbulb
    May 13 at 20:15
  • $\begingroup$ 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). $\endgroup$
    – Makogan
    May 13 at 20:54
  • $\begingroup$ 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. $\endgroup$
    – lightxbulb
    May 13 at 21:37

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.