2
\$\begingroup\$

There are two objects - blue circle and black square. When you normally render them, you will see situation in "A". But how do I render only specific part of blue circle, which can be "seen" (is in sight) from red dot in middle of the circle ("B" situation)?

\$\endgroup\$
2
  • \$\begingroup\$ Are the shapes just images? Or polygon data? Rendered how? What are the details of your set up? \$\endgroup\$ – PatrickSharbaugh Feb 25 '16 at 18:08
  • \$\begingroup\$ Yes they are just images, bitmaps. \$\endgroup\$ – johnyX Feb 25 '16 at 18:29
1
\$\begingroup\$

An ugly but possibly easier solution could be to

  1. Check angle between red dot and all corners of the square. Store the two corners that have the largest and smallest angle to the red dot.
  2. Make a blue triangle between the two stored corners and the red dot.
  3. Make a blue arc covering the whole circle except the angles between the two stored corners.

If you have multiple obstacles within the vision circle, you'd have to first count how many obstacles there are, then alternate between arcs and polygons around the circle accordingly.

Edit: An even uglier paint-picture to illustrate: FoV

\$\endgroup\$
2
\$\begingroup\$

Since I'm curious about an optimal solution I'll post the naive solution that will check if the center of a pixel can be raycast from the red point to the pixel without hitting a black pixel.

For every blue pixel in the blue object perform a 2D-DDA traversal from the center of the pixel to the center of the red dot. For every cell traversed check the black bitmap for a black pixel. If you hit a black pixel set the pixel to white on the blue bitmap. (Or write to another bitmap with a blue pixel if you reach the red dot).

The incomplete algorithm would look like:

for (var y = 0; y < blueBitmapHeight; ++y)
{
    for (var x = 0; x < blueBitmapWidth; ++x)
    {
        if (sampleBlueBitmap(x, y) == blue pixel)
        {
            // 2D-DDA traversal from (x + 0.5, y + 0.5) to redPoint
            // if hit then write a white pixel at (x, y)
        }
    }
}

I should point out that this is a very expensive operation and wouldn't be ideal for real-time. Even if you implemented it in a fragment/pixel shader it would require possibly hundreds, maybe thousands, of samples per pixel.

An optimization would be to post-process the image into a quad-tree and do a 2D-DDA quadtree traversal. This would help a lot if the black bitmap contains very sparse objects.

The 2D-DDA algorithm is described in this post.

\$\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.