**0**

# 2D visibility algorithm? (update)

###
#1
Members - Reputation: **322**

Posted 16 August 2009 - 03:40 AM

###
#2
Members - Reputation: **218**

Posted 16 August 2009 - 04:14 AM

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.

###
#3
Members - Reputation: **322**

Posted 16 August 2009 - 05:00 AM

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 :)

###
#4
Crossbones+ - Reputation: **2803**

Posted 16 August 2009 - 05:27 AM

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.

###
#5
Members - Reputation: **120**

Posted 16 August 2009 - 05:40 AM

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

###
#6
Members - Reputation: **322**

Posted 16 August 2009 - 05:45 AM

Quote:

Original post by Talroth

Just 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 Talroth

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.

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!

###
#7
Members - Reputation: **322**

Posted 16 August 2009 - 05:47 AM

Quote:

Original post by HostileExpanse

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

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 :)

###
#8
Members - Reputation: **218**

Posted 16 August 2009 - 06:13 AM

Quote:

Original post by AndreTheGiant

Thanks 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]

###
#9
Crossbones+ - Reputation: **2803**

Posted 16 August 2009 - 06:21 AM

Quote:

Original post by AndreTheGiantQuote:

Original post by Talroth

Just 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 Talroth

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.

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.

###
#10
Members - Reputation: **812**

Posted 16 August 2009 - 07:01 AM

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]

###
#11
Crossbones+ - Reputation: **2257**

Posted 16 August 2009 - 08:00 AM

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).

###
#12
Moderators - Reputation: **1386**

Posted 17 August 2009 - 12:15 AM

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).

###
#13
Members - Reputation: **2075**

Posted 17 August 2009 - 12:55 AM

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).

###
#14
Members - Reputation: **949**

Posted 17 August 2009 - 01:25 AM

Quote:

Original post by Andrew Russell

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).

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.

###
#15
Moderators - Reputation: **1386**

Posted 17 August 2009 - 02:04 AM

Quote:

Original post by phresnelQuote:

Original post by Andrew Russell

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).

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)

###
#16
Members - Reputation: **322**

Posted 22 August 2009 - 06:27 AM

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:

###
#18
Members - Reputation: **1416**

Posted 22 August 2009 - 08:41 AM

Quote: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.

Original post by AndreTheGiant

[...]Other solutions assumed convex polygons only[...]

###
#20
Members - Reputation: **322**

Posted 23 August 2009 - 06:26 PM

Quote:

Original post by ExtrariusQuote: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.

Original post by AndreTheGiant

[...]Other solutions assumed convex polygons only[...]

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.