More of a maths problem than code: Poly intersection

[JkWhoSaysNi]

I've made a quite nice shadow calculator that works out what areas should be light and what should be dark. (See attached screenshot)

As it is, my lighting system works really well (and in a lot of levels really looks beautiful) but it just breaks when 2 light sources overlap.

Heres how it works:

-Calculates areas hit by first light source
-Inverts it creating the co-ords for places that are in shadow,
-Does the same for the next light and the calculated poly is added to the existing poly this makes it so that any previously shadow areas inside the 2nd poly are now light...

Which brings us to the problem. Where 2 light areas overlap I get shadow.

I think there are 2 ways of solving this:

1) For any point, if i could work out whether it was inside an existing light source I could work back along the line towards the source until i found shadow and place the point there. Though this could result in small holes the size of the step. I don't know how for any point

2) Calculate the area which the polys overlap (the intersection) and re-add the co-ordinates to the poly. This would work but I have no idea how to work out the intersection of any 2 (never a predictable shape) polys

Is this possible? am I missing an obvious 3rd option?

Thanks.

[Chompy]

Really, really nice! (The screenshot)

[godofwarares]

I think what you're looking for is:

Use the formula:
y = mx+b
To find the slope, and then where the lines intersect.

Example:
y = 2x-3         Y-Intercept is -3, Slope is 2
y = x-1          Y-Intercept is -1, Slope is 1

Finding the point of interception, Use this:
rise / run

2 / 1             Up 2, Over 1
1 / 1             Up 1, Over 1

Intersection is at (2, 1), so (2, 1) is the solution.


Check if solution is correct

y = 2x-3
1 = 2(2)-3
1 = 4 - 3
1 = 1 (True)

y = x - 1
1 = 2 - 1
1 = 1 (True)

I suppose you can implement that into your script, although I am not sure how you would interpret it.

[Tolnaftate2004]

I'm assuming the shade on the thing holding the chest is not supposed to be there... If so, for each point, check to see if the ray extending from Point A crosses the line extending from the point that is specified 2 after the original point (Point C), with Point B between the two of them.

Any two lines cross at x=-(b1-b2)/(m1-m2). So, save an array as {-(b1-b2)/(m1-m2),m1*(-(b1-b2)/(m1-m2))+b1}, where y=m1x+b1 is the equation on the line going through Point A, and the same with 2s for Point C, to get the point at which the two rays cross. This will be Point M. Now, all you have to do, is in your polygon's array of points is replace ..., Point B, Point C, ... with ..., Point M, Point C, Point B, Point M, ... and the are will not be overlap anymore.

So basically, you're just keeping the shape by defining the "bend" and switching the points that cause the overlap.

[JkWhoSaysNi]

Originally Posted by Tolnaftate2004

I'm assuming the shade on the thing holding the chest is not supposed to be there... If so, for each point, check to see if the ray extending from Point A crosses the line extending from the point that is specified 2 after the original point (Point C), with Point B between the two of them.

Any two lines cross at x=-(b1-b2)/(m1-m2). So, save an array as {-(b1-b2)/(m1-m2),m1*(-(b1-b2)/(m1-m2))+b1}, where y=m1x+b1 is the equation on the line going through Point A, and the same with 2s for Point C, to get the point at which the two rays cross. This will be Point M. Now, all you have to do, is in your polygon's array of points is replace ..., Point B, Point C, ... with ..., Point M, Point C, Point B, Point M, ... and the are will not be overlap anymore.

So basically, you're just keeping the shape by defining the "bend" and switching the points that cause the overlap.

Thanks, i'll see if i can implement that

As for the places it doesn't quite look correct, it's due to the resolution of the check. It checks along 360 angles from the light source, obviously the further away the bigger the gap will be, I could increase the number of checks but at the moment 360 is enough, it's not perfect, but it looks good

[smirt362]

Thats...pretty damn cool!

[DustyPorViva]

Hmmm, there should be a better way to detect the tiles for the lights instead of checking 360 angles. I'm not sure how, though I have a rough idea of what you might be able to do, I just have a hard time explaining it. Maybe store the level's tile data(what's a wall and what's not), and have the check that you're doing in each angle adhere to the nearest edge of the tile. Do a search for kaimetsu and vector collision, he has a script that does this really well.

[JkWhoSaysNi]

actually it does round to the nearest tile already, the problem is, it cuts the corners because of where the next vertex is. I've attached a better example, without adding more sides to the poly (which i wouldnt know how to calculate anyway) or doing more angles, i'm not sure it's possible to stop it cutting corners.

when the script is finished it'll only ever do the light check once per level, the poly co-ordinates will then be stored. so it's not like it has to do this every time someone enters.

[DustyPorViva]

The thing that might help you in kaimetsu's script is he detects where the tiles transition from non-blocking to blocking, in each direction.

[Kristi]

Originally Posted by DustyPorViva

The thing that might help you in kaimetsu's script is he detects where the tiles transition from non-blocking to blocking, in each direction.

light projects in infinite directions.

Jk, if you wanted to test it so it didnt cut corners and appeared visually perfect, youd have to test 4096 lines of light from the center, since thats the only way to potentially test every pixel in the 64x64 level.

This would have been an easy task if it was just the tiles, however, i like to concider both the player and the npcs. the player is a square (techinally), so that doesnt add a challenge, but npcs can have a nonretcangular base. Also the play can be between two tiles, so simplifying the math is out.

As for detecting an overlap, calculate where the light is supposed to be for each, and give the npcs a name, like ("lightsource"@this.id) = this; then have all the npcs check if its the lightsource with the lowest id, and have the lowest id'd lightsource check all the npcs to find out if its alightsource, and grab the poly from each lightsource, and have the lowest id'd lightsource calculate the new poly based on all the poly's and draw it.

[DustyPorViva]

I know it does? What's the point of that statement? He already stated he doesn't want to raise the check he has of 360, so I was proposing an alternative.

[Kristi]

Originally Posted by DustyPorViva

I know it does? What's the point of that statement? He already stated he doesn't want to raise the check he has of 360, so I was proposing an alternative.

If im remembering correctly kais can only check the grid, not arbitrarily sized npcs, so that was the point.

[DustyPorViva]

I didn't say do the exact same thing Kai did. I was saying to check out his script and get some ideas from it. Kai managed to map the level, determining what blocks and what doesn't, and draw the boundaries. The boundary drawing is what I figured he would be interested in, if he wanted to draw the light around the corners correctly.

[theHAWKER]

dude, you should make it move-albe with your mouse! it would be soooo cool!!!!

[JkWhoSaysNi]

unfortunately it takes a couple of seconds to work out, making it moveable or attaching it to the player isn't really an option.