[Edited by - AndreTheGiant on August 22, 2009 12:31:33 PM]
2D visibility algorithm? (update)
Author
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]
[Edited by - AndreTheGiant on August 22, 2009 12:31:33 PM]
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.
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.
Author
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 :)
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 :)
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.
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.
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
http://www.gamedev.net/reference/articles/article729.asp
Author
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!
Author
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 :)
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]
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.
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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
