Just wondering if this is possible. Rather than create shadows for a light I want to create the actual light polygon. Say I have a set of lines and a circle (light) is it possible to use a BSP to find what the polygon of the light would be against these lines? I've also been doing some research on CDT (Constrained Delaunay triangulation) which I think would work also, but I'm not sure how to implement either solutions. I will not require processing the lines in realtime, only once, so the BSP tree / CDT will be conmputed once and reused for different lights. Something tells me that I can use a BSP because of its ability to show visible polygons from a point and its ability to split the world into convex polygons, but I can't see how I would traverse the BSP to do this. Here's an image to help understand what I'm talking about: I know that I could raycast through every vertex, find first intersection point, sort clockwise and draw to every point, but I was hoping to be a little smarter than that. Any help is greatly appreciated. Thankyou.

A BSP divides the world into convex cells, solid or empty, which can help, but I think you still need to do the raycast to construct a shadow-area from the solid cells of the BSP tree. You can speed up the process by inspecting every solid cell closer to the light center than its radius (fast for a BSP), and iteratively clip the light area to outside the shadow-area constructed from that cell (think shadow-volumes, if you know about those, but in 2D).

Hi,

I just had to solve this exact problem for a project I'm working on. I use a CDT for this purpose (which nicely simplifies some of the algorithms involved), although I imagine it could be solved using a BSP as well.

Generating the shape in your last image basically breaks down into two steps: building the visibility polygon corresponding to the query point (where a 'visibility polygon' is a possibly non-convex polygon representing the area that is visible from the query point), and then clipping the visibility polygon (in one way or another) to a circle.

The algorithm for building a visibility polygon given a CDT and a query point isn't quite trivial, but it's relatively straightforward. I do have working code for all of this, but unfortunately it's fairly tightly integrated into my current project, so I'm not sure how much use it would be to you.

I have to take off at the moment, but feel free to ask if you need any additional info on this.

Quote:A BSP divides the world into convex cells, solid or empty, which can help, but I think you still need to do the raycast to construct a shadow-area from the solid cells of the BSP tree. You can speed up the process by inspecting every solid cell closer to the light center than its radius (fast for a BSP), and iteratively clip the light area to outside the shadow-area constructed from that cell (think shadow-volumes, if you know about those, but in 2D).

Just to clarify a bit, the method I use doesn't require any raycasting (per se) or clipping to build the visibility polygon associated with the query point. I'm sure it *can* be done that way, but in the case of a CDT at least, it can be done more simply.

Here's a code sample that does exactly what you request, except it uses a .bmp image instead of polygons. Please note that the code is in freebasic dialect.

http://www.jernmager.dk/stuff/freebasic/shadow.zip

cheers,
Mike

Quote:Could you give a quick overview of the algorithm? Most ones I can find on the internet only deal with a single simple polygon.

The first step is to find the triangle containing the query point. Clearly the entire triangle is visible from the query point, so we start by adding three triangles to the visibility polygon (each triangle is formed from the query point and an edge of the triangle).

For each unconstrained edge of the triangle, we recurse across that edge. By extending the edges of the triangle that terminates at that edge, we form an unbounded triangle representing the current potentially visible region in that direction. The opposite vertex of the triangle into which we're recursing will fall either within this extended triangle, or to the left or right of it. Furthermore, the opposite edges of the triangle may each be either constrained or unconstrained.

This gives us a finite number of cases to consider. If you draw out some example diagrams, it becomes fairly clear what needs to happen in each case. (In some cases, a new triangle is generated, clipped to a constrained edge; in some cases, we recurse across an unconstrained edge; and so on.)

In some cases line-line intersections will need to be performed to compute the vertices of the triangles of the visibility polygon, but other than that there's no raycasting or clipping of any sort required.

I'll have to leave it at that for now, but I can provide more info if needed. (I'll try to post some screenshots later today showing the algorithm in action.)

Also, I seem to recall that there was a similarly-themed thread in the Lounge (of all places) within the last few weeks. You might check that thread out as well if you're interested in alternative approaches.

Wow didn't expect this many responses :)

Erik - I was trying to stay away from shadow volumes, although I think you're talking about using them in a completely different way. Would you be able to explain a little further what you mean? The reason I don't want to draw shadow volumes is some overlap will occur and cause rendering performance problems (*using Flash)

jyk - I too would love a more detailed explanation. I'm very new to CDT and BSP's so much so that I only started reading about them 2 days ago. I've managed to get a DT in and almost a CDT but that's not really the problem. I think I kind of understand what you're talking about in your last post, extruding edges of a triangle and finding intersections along the way?

h4tt3n - Thanks, I'll try and look at the code, but I'm really after an explanation of how it all should work so I can understand it myself.

-------

here's what I have previously created using shadow like volumes:

light test

how it works:

loop through all lines and check overlapping AABB's
if overlap, find intersections points on line where circle intersects
if intersects, project intersections out from light center at light radius
close this shadow polygon and render.
shadow polygon is drawn into light, using a shader the shadow color erases the light.
continue over all overlapping lines.

results in lots of shadow overlaps, thus bad performance. Also, erasing the shadow from the light can be costly because of the shader.

My thoughts turn to just computing the light (visible) polygon for these infinitely high lines. For any other object which needs to receive light and cast shadows the shadow volume technique will be used.

You could avoid some overlap by first checking if the line you're about to extrude is already in shadow, and start from the closest lines moving outwards. Perhaps creating light volumes instead of shadow volumes could also be better.

After reading jyk's post I think his solution is much better than a BSP if you want to construct the light-area. A BSP based approach really doesn't seem efficient in this case. I think when implemented what I had in mind would be the same principle, clipping against adjacent solid cells, but it feels like it will require more calculations than with his method.

Erik - yep, I did try that and it did reduce some of the overlaps, but the calculations to determine these overlaps were proving costly on CPU. However I didn't start from closest lines first which could change that. In any case using a large moving light (radius of 700+) causes large shadow volumes to be constructed, I guess I could clip these volumes to the viewing rectangle but I still think drawing the light polygon could be more efficient *rendering wise. What do you mean by light volumes?

thanks for the help so far :)