Determining how much of a tile is intersected by a ray to help calculate lighting and deal with shadow issues

Question

I'm currently using the following steps for my lighting system

• Calculate all the tiles along the perimeter based on the radius of the light
• Cast a ray from the center of the light to each perimeter tile
• The ray cast returns which cells it intersects
• Each cell is lit based on their distance from the source (light attenuation)
• If a cell is determined to be opaque then the subsequent cells are not lit (hard shadow)

The problem is that in some cases this makes the shadowing looks a bit odd and gives a Peter Pan type of effect where the shadow is not attached to the shadow caster (opaque cell).

For example:

The culprit is highlighted here:

If we take a look at the ray causing the issue we can see that it hardly intersects the cells behind the opaque object but they are still counted as being lit:

The method used for ray traversal is a typical Bresenham line drawing algorithm:

    while (true)
    {
        // Do not return cells outside the map bounds
        if (x0 < 0 || x0 >= width || y0 < 0 || y0 >= height)
            break;

        // Add the current cell to the list
        cells.Add(GetCell(x0, y0));

        if (MathExt.AlmostEquals(maxX, maxY, 0.01f))
        {
            // Cannot travel any further in this direction so this is the last cell
            if (x0 == x1 || y0 == y1)
                break;

            maxX += deltaX;
            maxY += deltaY;
            x0 += stepX;
            y0 += stepY;
        }
        else if (maxX < maxY)
        {
            // Cannot travel any further in this direction so this is the last cell
            if (x0 == x1)
                break;

            maxX += deltaX;
            x0 += stepX;
        }
        else
        {
            // Cannot travel any further in this direction so this is the last cell
            if (y0 == y1)
                break;

            maxY += deltaY;
            y0 += stepY;
        }
    }

My current line of thinking is to calculate how much of the cell is intersected by the ray and use that to influence the contribution of the lighting, alongside the attenuation.

Therefore, my question is how do I calculate how much of the cell is intersected by the ray?

Alternatively, can anyone suggest a more suitable solution for this issue?

Answer 1

First of all a ray isn't going to help you with this. You will need at least 2 rays.

"How much of a tile a ray intersects" is not really a meaningful question, since the ray will always split a tile it intersects into two parts and then how do you decide which part you want.

Instead you want to know how much of a tile is in between two rays, both of which extend from the sides of an obstacle. That will give you an idea of how well lit a tile should be. But if you are going to do that you might as well just do stencil shadows to begin with.

The basic answer is, you will have to build shadow geometry one way or another. Then you need to calculate how much light each tile gets. You can do it on the CPU like your proposed solution, or you can do it on the GPU which basically turns it into stencil shadows.

Answer 2

I disagree with @Nils Ole Timm, you can use a single ray. (While two rays is another, probably much nicer and robust, implementation.)

What you should use with a single line is to just use the length of the line inside the square.

To do that you could either calculate the exact (floating point) intersections with the square at all four edges and use that.

Or I guess you could use the variable that just counts up and resets regularily in Bresenham's algorithm. Your Bresenham doesn't really look the way I'm used to, I'm referring to D at https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

Answer 3

I mostly agree with the solution presented by @NiklasJ in that a single ray may be sufficient, but I don't think that only using the length of the line segment in the interior is the correct metric to determine the outcome.

Consider a case where the light ray runs just inside & parallel to the edge of the rectangle. This could produce a relatively long line segment, but you might prefer to reject the intersection due to its glancing nature. If so, I suggest comparing the areas of the sections on either side of the intersecting line.

Calculating the areas isn't too complex, but it is more complex than simply checking the length of the intersection. If performance is a concern, first use @NiklasJ's solution. If the intersection is very small you can reject the hit. If the intersection is very large (say comparable to the hypotenuse), you can accept the hit. If the result is in between & you want to filter out glancing edge cases, resort to comparing the areas on either side of the bisection.

With all this being said, I'll agree with @Nils Ole Timm in that you may get a truer result via shadow geometry; I'm currently using a 3D Bresenham algorithm to determine visibility & have not yet resolved all the undesirable edge cases.

Answer 4

People are overcomplicating, which is easy to do in computational geometry.

All you need to find is the two points of intersection with the circle, which I am sure you can figure out on your own.

From there, calculate the area of the triangle. 1/2 base * height.

That should be a close approximation for most purposes but you can also calculate the other bit.

This remaining area is called a chord. The area formula for a chord is A = 1/2 R2 theta - L/2 (R-h).

O is the center of the circle.

So you can calculate out the exact area. Or you could approximate this by coming up with a constant to multiply by the chord length since this is a pretty small area really.