# 2D visibility algorithm? (update)

## Recommended Posts

I'm almost positive that such an algorithm exists, but I havnt been able to google it. Maybe I'm not using the proper name for it. What I want to do is, given a 2D field full of polygons and a point P, calculate everything that is visible from P. Ive been struggling writing my own algorithm from scratch, but it seems like everything is a special case and I just cant get it to work properly. Im sure this has been solved many times already. Does anyone happen to know where I should look? Here is an example of what I want: TOP: A bunch of polygons in 2D and a point MIDDLE: The blue area is what the point can 'see' BOTTOM: This is the polygon that I want to compute. [Edited by - AndreTheGiant on August 22, 2009 12:31:33 PM]

##### Share on other sites
Krokhin    218
Sure.Even no need to seek it somewhere...
Try polar coordinates-i.e.project all corners to circle.Line between two corners define sector on the circle.Using range to corners and interpolated range between them,remove all hidden sectors,then cute all hidden parts of sectors in all mutually intersected (by polar angle) pairs.I.e you must check intersection by polar angle and sort corners/sectors on the circle by depth.
2D-coordinate give you chance to work with simple intervals like in case of one coordinate axis.Finally you can convert polygone from polar coordinates back.

##### Share on other sites

I read it about 5 times and I'm still not sure I completely get it. Im familiar with polar coordinates but I still dont see how your algorithm operates. Is this a known algorithm that works? Does it have a name so I can look up more details somewhere? Or is it just something off the top of your head that you think might work? In which case I'd appreciate some elaboration :) Thanks!

Also I'm still very open to other suggestions :)

##### Share on other sites
Talroth    3247
Just how complex of levels are you looking to use this in?

My first approach to this would be to swing a line around your center point, and pick out all vertexes. Establish lines from the center to each vertex, then start culling space based on edges.

##### Share on other sites
I tried out googling "line of sight" and game, and it actually came up with a reference to gamedev. I only skimmed it, but it looks useful.

http://www.gamedev.net/reference/articles/article729.asp

##### Share on other sites
Quote:
 Original post by TalrothJust how complex of levels are you looking to use this in?

Yeah its pretty CPU intensive. Im just doing some pre-calculations though, before the game starts.

Quote:
 Original post by TalrothMy first approach to this would be to swing a line around your center point, and pick out all vertexes. Establish lines from the center to each vertex, then start culling space based on edges.

If you think about it, that doesnt quite work, because some vertices are 'tips' of objects, and the line of sight actually goes past them on one side. Ive spent a few hours thinking about this and everytime I think Ive completed the algorithm, I realize theres another special case I havnt factored in. Im definetly getting there though!

##### Share on other sites
Quote:
 Original post by HostileExpanseI tried out googling "line of sight" and game, and it actually came up with a reference to gamedev. I only skimmed it, but it looks useful.http://www.gamedev.net/reference/articles/article729.asp

I found this on google also, but it felt very out of date and I only skimmed it. That might just be my bias against ascii art instead of actual images, so maybe I should give it another look :)

##### Share on other sites
Krokhin    218
Quote:
 Original post by AndreTheGiantThanks for the reply.Is this a known algorithm that works? Does it have a name so I can look up more details somewhere?

I don't know,it's from mind.I'm sorry also for my English,you can look at that like an attempt to write an article for local community,but with depressed result.Don't be upset,after all it's not a negotiations about nuclear disarmament[smile].
It will work,of couse,because stupid method -2D raytrace- work anyway,but we must think about possible optimisation.And Im trying to explain how we can do this optimisation.
I mean just the most suitable representation of information.If you are using poligons (lines) in 2D -space,the simplest thing what you can do is raytrace from camera point in all directions,right? But you can split poligons to set of lines,project endpoints of this lines to circle and consider it like a set of intervals-actually already in 1-D space (i.e. in polar coordinates - any angle and constant radius) and then sort this intervals using camera-endpoint distance.After sorting it will be a set of intervals, representing the same result as after raytrace in 2D.

[Edited by - Krokhin on August 16, 2009 12:13:21 PM]

##### Share on other sites
Talroth    3247
Quote:
Original post by AndreTheGiant
Quote:
 Original post by TalrothJust how complex of levels are you looking to use this in?

Yeah its pretty CPU intensive. Im just doing some pre-calculations though, before the game starts.

Quote:
 Original post by TalrothMy first approach to this would be to swing a line around your center point, and pick out all vertexes. Establish lines from the center to each vertex, then start culling space based on edges.

If you think about it, that doesnt quite work, because some vertices are 'tips' of objects, and the line of sight actually goes past them on one side. Ive spent a few hours thinking about this and everytime I think Ive completed the algorithm, I realize theres another special case I havnt factored in. Im definetly getting there though!

Well, I was thinking of it as you extend a line from the center point though the vertex. I should have written that clearer. You then start culling points based on the areas between the lines radiating out form the center based on lines of the polygons.

##### Share on other sites
noisecrime    817
Isn't this just the same as shadow volumes, but without the volume ;)

That is treat the point as a light source, loop through all shapes and determine which vertices define the visible silhoutte of the object with respect to the point. In simpler terms, loop through each edge in the shape and find two edges where one faces the point and the other doesn't. Thus you now have a point where you go from a visible edge, one that would cast a shadow to non-visible edge that wouldn't. You'll need to generate some addition data for each shape, such as what edges are connected.

Once you have the vertices you can cast a ray from the point through them to infinity (or rather the boundary of the game world).Pretty sure from those rays and the edges that face the point from the shape you can generate a polygon that defines non-visible area. Then its straightforward point in polygon tests to determine visibility.

Thats a brief and simplified method from 3d volumes, but there may be a more optimised method for your 2d shapes.

This article might explain the method better - its got pictures ;) I'm sure there was another article or tutorial on gamedev that did exactly waht you need in 2D, but can't find it now.

Another method that comes to mind might be to look up portal generation as its somewhat similar.

[Edited by - noisecrime on August 16, 2009 1:01:04 PM]

##### Share on other sites
Sirisian    2263
In the past I've just used 2D shadow volumes since they tend to work well. It's not the exact problem that you want though. It can be used to calculate non-visible regions.

Discussion on Kirupa about the problem

At the bottom I started to write the algorithm you proposed. It's not too bad to write. You end up just firing rays from the center to each vertex. If you hit an object then don't handle the vertex. If you get to the vertex continue the ray until you hit either the boundary or another object. There's a few more steps, but you'll figure them out as you go. The math library I included in that post is very important.

The algorithm I was writing was an self optimizing version that occluded objects as it went. (It was designed to run on a massive map with no boundaries).

##### Share on other sites
Andrew Russell    1394
2D shadow volumes are easy and relatively cheap to generate. The polygon you are trying to generate is much more difficult.

However - I struggle to think of any situation where one couldn't simply use 2D shadow volumes, and invert some other part of their algorithm.

And while I'm here, I might plug my game with realtime 2D soft shadows (pics and video, no download yet).

##### Share on other sites
jyk    2094
You've already gotten some good suggestions, but I'll go ahead and throw this out anyway.

The problem might be easier to solve if you first polygonize or triangulate the open areas. I recently had to solve this same problem in a project I'm working on, in the context of a navigation mesh built from a constrained Delaunay triangulation (note that you could easily build a CDT from the geometry you posted). The algorithm to build an exact visibility region given a query point and a CDT is actually fairly straightforward to implement (as far as this type of algorithm goes, at least).

##### Share on other sites
phresnel    953
Quote:
 Original post by Andrew Russell2D shadow volumes are easy and relatively cheap to generate. The polygon you are trying to generate is much more difficult.However - I struggle to think of any situation where one couldn't simply use 2D shadow volumes, and invert some other part of their algorithm.And while I'm here, I might plug my game with realtime 2D soft shadows (pics and video, no download yet).

Oh that reminds me of an old 2d path tracer I've written. It features global illumination (yay 2d caustics), but it's totally unoptimized towards 2d (basically I've took an older ray tracer of mine, and canceled out one dimension). clicky, clicky.

##### Share on other sites
Andrew Russell    1394
Quote:
Original post by phresnel
Quote:
 Original post by Andrew Russell2D shadow volumes are easy and relatively cheap to generate. The polygon you are trying to generate is much more difficult.However - I struggle to think of any situation where one couldn't simply use 2D shadow volumes, and invert some other part of their algorithm.And while I'm here, I might plug my game with realtime 2D soft shadows (pics and video, no download yet).

Oh that reminds me of an old 2d path tracer I've written. It features global illumination (yay 2d caustics), but it's totally unoptimized towards 2d (basically I've took an older ray tracer of mine, and canceled out one dimension). clicky, clicky.

Wow that is cool! Now you've got me trying to come up with ways to get that effect on the GPU [smile] (which is where, btw, I am doing my shadow generation)

##### Share on other sites
Update:

After a LOT of research and experimentation and headaches, Ive written a demo that computes the visibility from any point in a field of arbitrary polygons.

Google was very little help. Everything I found dealt with extremly simplified cases, and not the general problem that I wanted to solve.

For example some solutions devided the entire level up into a grid, and just computed the visibility of each square in the grid, resulting in 'staircase' lines that are just an approximation of the visibility.

Other solutions assumed convex polygons only, and none of the solutions I found online explained the special cases and mathematical precision issues involved.

This was a pretty tedious and tricky project, but I'm happy with the results so far! Ive created a GIF of my test map and the visibility from various points:

##### Share on other sites
WazzatMan    102
That's pretty awesome, good work!

##### Share on other sites
Extrarius    1412
Quote:
 Original post by AndreTheGiant[...]Other solutions assumed convex polygons only[...]
If you found solutions for convex polygons, the easiest way to solve the problem probably would have been to just convert everything to convex polygons. It's pretty simple to convert any polygon as long as you don't allow self-intersection.

##### Share on other sites
Talroth    3247
So, how does your algorithm work?

##### Share on other sites
Quote:
Original post by Extrarius
Quote:
 Original post by AndreTheGiant[...]Other solutions assumed convex polygons only[...]
If you found solutions for convex polygons, the easiest way to solve the problem probably would have been to just convert everything to convex polygons. It's pretty simple to convert any polygon as long as you don't allow self-intersection.

Thats so true that you blew my mind when I read that! I went back to these 'other solutions' and realized that I misspoke. I never actually found any solutions that worked for convex polygons only. If I had, Im sure I would have thought of chopping my wierd polygons into convex ones and using that solution. I really cant remember what I meant by that. O_o

Quote:
 Original post by Talroth So, how does your algorithm work?

Overall, it works pretty much like you suggested. (I think - dont want to put words in your mouth). For each vertex, I test if it is visible, and if it is, I extend a ray from the eye, through the vertex, back until the next intersection, until the new vertex is no longer visible. Then move on to the next vertex in a counterclockwise (or clockwise) order, adding the successful points to the visible polygon. The tricky stuff comes in when deciding if these extended vertices are really visible or not, and cases where lines are parallel, or lines intersect polygons exactly on another vertex, and mathematical precision issues.

##### Share on other sites
jyk    2094
Quote:
 Overall, it works pretty much like you suggested. (I think - dont want to put words in your mouth). For each vertex, I test if it is visible, and if it is, I extend a ray from the eye, through the vertex, back until the next intersection, until the new vertex is no longer visible. Then move on to the next vertex in a counterclockwise (or clockwise) order, adding the successful points to the visible polygon. The tricky stuff comes in when deciding if these extended vertices are really visible or not, and cases where lines are parallel, or lines intersect polygons exactly on another vertex, and mathematical precision issues.
This is probably kind of irrelevant (since you already have a working implementation), but I'll mention again that if you represent the environment using a constrained Delaunay triangulation, the process of building the visibility region corresponding to a point becomes fairly straightforward. It also sounds like there might be fewer precision issues to contend with when using the CDT approach.

The CDT approach is also quite efficient, as it doesn't involve any visibility tests (per se).

Again, this is probably irrelevant at this point, but I just thought I'd mention the CDT method again as a possible alternative approach to the problem.