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).
2D visibility algorithm? (update)
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).
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).
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).
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).
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.
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)
Author
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:
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:
Quote:Original post by AndreTheGiantIf 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.
[...]Other solutions assumed convex polygons only[...]
Author
Quote:Original post by ExtrariusQuote:Original post by AndreTheGiantIf 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.
[...]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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
