Access a circle of rays efficiently (find closest obstacle contours)

1
votes

Have a binary grid (like black and white pixels with black = empty and white = obstacle). Starting from a given point on black, I want to emit "rays" in all directions. Those rays should either abort when reaching a given length (for example 100) or when hitting a white pixel (in which case the position of this pixel, aka obstacle contour shall be marked). Those marked pixels result in a view of all obstacle contours that are "visible" from the given point (not obstructed by other obstacles).

What I have thought of so far, is to simply call a sufficient number of bresenham lines. In the case of a radius of 100, that means 100*2*pi = 628 lines to cover all pixels on the outer most circle. However that results in many many multiple checks of same pixels closer to the center. Now I could split up the check in multiple rings, each of a different density of bresenham lines, but that appears rather inefficient too.

Does someone happen to have a more efficient algorithm idea for this? Huge thanks in advance!

2
c++algorithmbresenham
Usually a good approach is to fire only the rays that can give you relevant results: for example in a maze scenario with straight walls you need only to know if two given corners are visible or not to determine if the entire wall is visible. Maybe this can help you: ncase.me/sight-and-light – Liuka
To increase relevance of question to this site (which doesnt seem obvious to me), maybe you could add some figure AND a code snippet showing your idea (even pseudo code will be better than no code at all). – kebs
@Liuka Interesting work, but unfortunately such optimizations are not applicable to my case because the obstacle pixels can effectively look as if they are random. @ kebs Good idea, I'll make something. – AlexGeorg
If you're looking for a more 'pixel perfect approach' there is something like this: github.com/mattdesl/lwjgl-basics/wiki/2D-Pixel-Perfect-Shadows, that however, if I remember correctly, requires to move to a GPU shader to obtain good performance and as a result you obtain just an image not 'logic data'. The approach is cool though and maybe for your needs is enough – Liuka
Basically you transform the space (the grid) around your camera into polar coordinates (I think, but look at the article) and then you simply swipe from bottom to top for each pixel column and see which is the foremost pixel. In this way you are checking each pixel only once. Even though you need to apply an extra transformation that surely won't result in a pixel perfect image (but maybe can be a cool way to achieve partial visibility), I think you're reducing the total number of checks – Liuka

2 Answers

0
votes

Unfortunately the hints towards graphics processing techniques while fascinating, are not well applicable in my case because I have no access to shaders or a camera, etc.

For now I have found a sufficiently efficient solution myself. The basic idea is to launch rays from the contours, not from the origin. Furthermore to use a helper grid named "reachable" where all pixels are marked that are successfully visible from the origin. This way only few pixels are read twice, most are read just once and some are written at most once. The code is rather messy yet, thus only pseudocode here:

Have desired origin O.x/O.y
Have obstacle bool grid Obstacle

Define bool grid Reachable[w][h]    
Clear Reachable with false

Reachable[O.x][O.y] = true

For each Point C on all obstacle Contours // if not available, compute contours by finding all pixels adjacent to non-obstacle    
    For all Pixels A on Bresenham line from C to O

        If Obstacle[A.x][A.y]    
            Continue with outer loop on contours // abort this line due to obstacle hit

        If Reachable[A.x][A.y]
            For all Pixels B on Bresenham line from C to A
                Reachable[B.x][B.y] = true // mark all pixels on this line as Reachable
            Mark C as a desired result pixel
            Continue with outer loop on contours
0
votes

Let the "square distance" between two points (x1,y1) and (x2,y2) be max(|x1-x2|,|y1-y2|), so that the points at increasing "square distance" around a center for increasingly large squares.

Now, for each square distance d from your center point, in increasing order, keep track of the angles the center point can see through all the obstacles with distance <= d.

You can use a list of angle intervals starting at [(0,360)] for d=0.

For each new distance, you can inspect the list, examine the new pixels within the given angles, and remove angle from the intervals when obstacles are hit. Each obstacle that causes you to modify an interval is visible from the center point, so you can mark it as such.

This method examines pixels only once, and only examines pixels you can see. The way I wrote it above requires trigonometry, however, which is slow. For a practical implementation, instead of actually using angles, use slopes, which require only simple math, and process each octant separately.