Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


2D visibility algorithm? (update)


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
20 replies to this topic

#1 AndreTheGiant   Members   -  Reputation: 191

Posted 16 August 2009 - 03:40 AM

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]

Sponsor:

#2 Krokhin   Members   -  Reputation: 218

Posted 16 August 2009 - 04:14 AM

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.

#3 AndreTheGiant   Members   -  Reputation: 191

Posted 16 August 2009 - 05:00 AM

Thanks for the reply.

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 Luckless   Crossbones+   -  Reputation: 2174

Posted 16 August 2009 - 05:27 AM

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.

#5 HostileExpanse   Members   -  Reputation: 116

Posted 16 August 2009 - 05:40 AM

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

#6 AndreTheGiant   Members   -  Reputation: 191

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 AndreTheGiant   Members   -  Reputation: 191

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 Krokhin   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 Luckless   Crossbones+   -  Reputation: 2174

Posted 16 August 2009 - 06:21 AM

Quote:
Original post by AndreTheGiant
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!


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 noisecrime   Members   -  Reputation: 746

Posted 16 August 2009 - 07:01 AM

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]

#11 Sirisian   Crossbones+   -  Reputation: 1941

Posted 16 August 2009 - 08:00 AM

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

#12 Andrew Russell   Moderators   -  Reputation: 1382

Posted 17 August 2009 - 12:15 AM

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

#13 scgames   Members   -  Reputation: 2037

Posted 17 August 2009 - 12:55 AM

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

#14 phresnel   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 Andrew Russell   Moderators   -  Reputation: 1382

Posted 17 August 2009 - 02:04 AM

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


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 AndreTheGiant   Members   -  Reputation: 191

Posted 22 August 2009 - 06:27 AM

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:



#17 WazzatMan   Members   -  Reputation: 102

Posted 22 August 2009 - 07:45 AM

That's pretty awesome, good work!

#18 Extrarius   Members   -  Reputation: 1412

Posted 22 August 2009 - 08:41 AM

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.

#19 Luckless   Crossbones+   -  Reputation: 2174

Posted 22 August 2009 - 08:47 AM

So, how does your algorithm work?

#20 AndreTheGiant   Members   -  Reputation: 191

Posted 23 August 2009 - 06:26 PM

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.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS