quadrilateral clipping and other problems

[clickrush]

Hi, this is my first post here...

LÖVE is my first real programming experience after messing around with some of the free editor/design programs (GE and GM) out there and i love it. I never thought that programming/codeing is such a fun thing to do and I almost can't stop anymore. My main problem is that I'am often losing alot of time searching for solutions, due to my lack of knowledge. You see if i would try to read through the whole documentation at once, then I wouldn't understand alot of the things, so my learning process is problem orientented. This is why I'd like to start a thread so I can ask a few questions, and hopefully get a few "Aha!" moments if you'd please to help me

context:

My current task is to make a 2d light-shadow system. I've made a function where i input the coordinates of the light-source and a rectangle (my collision object),which returns me a convex quadrilateral (=the shadow) since I'd like to implement this in a plattformer (in case you ask why the shadow is allways a quadrilateral).

the 1. problem:

This works quite well when I'am adding more and more collision rectangles as the shadows just add up nicely. But if I'am adding additional light-scource then I have a problem: It would create just more shadow instead of less.

So I guess I have to check for intersection points and create a new polygon . The correct polygon would be inside of all the shadow-quadrilaterals. I'am kinda lost on this. I'am also not sure if love2d supports such tasks, if there is something built in that helps me?

the 2. problem:

I've allready come up with a solution to check if a point is in the shadow-quadrilateral (it's very easy you just have to check for the two triangles inside it). Let's say I load an image into the game. Is there a way to change only the colors that are inside the shadow (individual pixels)? If yes then how big should the image be at max to not slow down the game too much?

Thx for everyone who reads this and tries to help me.

[Robin]

Holy cow, these are pretty complex problems for someone who has no "real" prior programming experience.

I don't think either of the problems has a simple solution in LÖVE, although the second one might be solved by Stencils, but those are only there from 0.8.0.

And welcome!

[miko]

Hi, this is my first post here...

LÖVE is my first real programming experience after messing around with some of the free editor/design programs (GE and GM) out there and i love it. I never thought that programming/codeing is such a fun thing to do and I almost can't stop anymore. My main problem is that I'am often losing alot of time searching for solutions, due to my lack of knowledge.

You are wrong here: you are not losing time, but investing in your knowledge! And yes, your tasks are not first-timer usual problems.

This works quite well when I'am adding more and more collision rectangles as the shadows just add up nicely. But if I'am adding additional light-scource then I have a problem: It would create just more shadow instead of less.

So I guess I have to check for intersection points and create a new polygon . The correct polygon would be inside of all the shadow-quadrilaterals. I'am kinda lost on this. I'am also not sure if love2d supports such tasks, if there is something built in that helps me?

I can only think about BlendMode - that could change the way shadows look like, but you will not know the exact coordinates.

the 2. problem:

I've allready come up with a solution to check if a point is in the shadow-quadrilateral (it's very easy you just have to check for the two triangles inside it). Let's say I load an image into the game. Is there a way to change only the colors that are inside the shadow (individual pixels)? If yes then how big should the image be at max to not slow down the game too much?

You can manipulate pixel color with ImageData:setPixel. This is slow, but you could use threads to free the main loop, and framebuffers to cache your image. Still, I would try with BlendMode first, as that should be faster.

[clickrush]

Thx very much for your reply!

I just checked out "blend mode" as you suggested and I think this is the tool i need to change the appereance of my images depending on my shadow object. So I guess you gave me a very usefull hint for my second problem. thx

In the other hand I have to know where exactly the shadows are for my first problem to do the task above. so blend mode will not help me here. I guess I'd have to figure out an algorithm for creating a new shadow when two or more light sources hit the same object. I guess I store the shadow data into the individual objects, then check if there are more than one shadows and go on from here. I searched quite along time for a fitting algorithm because I couldn't figure it out yet. Unfortunately there are no polygon clipping libraries for lua that return me a new polygon .

If anyone is in urge to help me or is interested in the code: here is the function to make the shadow. It's very messy I guess but remember I'am a beginner (any tips for cleaning this up or for making it faster are appreciated!)

x1,y1 is the coordinate of my light-source and x2,y2,width,height defines my rectangle (as you see its alligned)
it first determines on which side the light source is so it can choose the tangents on the rectangle which are the first two coordinates of the shadow. Then it enlarges the vectors from the light source to the tangents to the point where they hit the bottom/top/side of the window. Notice that it doesn't care if the shadow is too big on the sides. I made this so I allways get a quadrilateral and to keep the code simple.

Code: Select all

function makeshadow(x1,y1,x2,y2,width,height)

--which side? which tangents?
if (x1-x2<=0) and (y1-y2<=0) then
	position="ul"
elseif (x1-x2>=0) and (x1-(x2+width)<=0) and (y1-y2<=0) then
	position="uu"
elseif (x1-(x2+width)>=0) and (y1-y2<=0) then
	position="ur"
elseif (x1-x2<=0) and (y1-y2>=0) and (y1-(y2+height)<=0) then
	position="cl"
elseif (x1-(x2+width)>=0) and (y1-y2>=0) and (y1-(y2+height)<=0) then
	position="cr"
elseif (x1-x2<=0) and (y1-(y2+height)>=0) then
	position="dl"
elseif (x1-x2>=0) and (x1-(x2+width)<=0) and (y1-(y2+height)>=0) then
	position="dd"
elseif (x1-(x2+width)>=0) and (y1-(y2+height)>=0) then
	position="dr"
end

--create tangents
if position=="ul" then
	tangents = {
		tangentl = {x=x2,y=y2+height},
		tangentr = {x=x2+width,y=y2}
	}
	
elseif position=="uu" then 
	tangents = {
		tangentl = {x=x2,y=y2},
		tangentr = {x=x2+width,y=y2}
	}
	
elseif position=="ur" then 
	tangents = {
		tangentl = {x=x2,y=y2},
		tangentr = {x=x2+width,y=y2+height}
	}
	
elseif position=="cr" then 
	tangents = {
		tangentl = {x=x2+width,y=y2},
		tangentr = {x=x2+width,y=y2+height}
	}
	
elseif position=="dr" then 
	tangents = {
		tangentl = {x=x2+width,y=y2},
		tangentr = {x=x2,y=y2+height}
	}
	
elseif position=="dd" then 
	tangents = {
		tangentl = {x=x2+width,y=y2+height},
		tangentr = {x=x2,y=y2+height}
	}
	
elseif position=="dl" then 
	tangents = {
		tangentl = {x=x2+width,y=y2+height},
		tangentr = {x=x2,y=y2}
	}
	
elseif position=="cl" then 
	tangents = {
		tangentl = {x=x2,y=y2+height},
		tangentr = {x=x2,y=y2}
	}
	
end

	stopl={}
	stopr={}

if (position=="ul") or (position=="uu") or (position=="ur") then
	stopl.x = ((600-y1)*(tangents.tangentl.x-x1)/(tangents.tangentl.y-y1))+x1
	stopl.y = 600
	stopr.x = ((600-y1)*(tangents.tangentr.x-x1)/(tangents.tangentr.y-y1))+x1
	stopr.y = 600
end

if (position=="dl") or (position=="dd") or (position=="dr") then
	stopl.x = ((y1*-1)*(tangents.tangentl.x-x1)/(tangents.tangentl.y-y1))+x1
	stopl.y = 0
	stopr.x = ((y1*-1)*(tangents.tangentr.x-x1)/(tangents.tangentr.y-y1))+x1
	stopr.y = 0
end

if (position=="cr") then
	stopl.x = 0
	stopl.y = ((x1*-1)*(tangents.tangentl.y-y1)/(tangents.tangentl.x-x1))+y1
	stopr.x = 0
	stopr.y = ((x1*-1)*(tangents.tangentr.y-y1)/(tangents.tangentr.x-x1))+y1
end

if (position=="cl") then
	stopl.x = 800
	stopl.y = ((800-x1)*(tangents.tangentl.y-y1)/(tangents.tangentl.x-x1))+y1
	stopr.x = 800
	stopr.y = ((800-x1)*(tangents.tangentr.y-y1)/(tangents.tangentr.x-x1))+y1
end

return tangents.tangentl.x, tangents.tangentl.y, tangents.tangentr.x, tangents.tangentr.y, stopr.x, stopr.y, stopl.x, stopl.y
end

EDIT: Ok I think I've found something that might resolve the task: http://rosettacode.org/wiki/Sutherland- ... n_clipping
there is a lua implementation for the sutherland-hogman algorithm. As far as I understand it by now, I think that this is really usefull stuff here for alot of LÖVE users. It's a simple function which can be used for generating graphics/collision polygons in a 2d environment as well as for cutting out stuff that doesn't have to be drawn and thus speed your game up quite a bit if you have a lot of stuff drawn on top of eachother. I guess it will only work if you use something that determines your drawing order (eg. z-depth).

I've yet to find out how to implement it though but iam eager to do this
edit2: shoutout to the person who made those smileys. They are so handsome

edit3: ok i totally missed out one reply..

Holy cow, these are pretty complex problems for someone who has no "real" prior programming experience.

I don't think either of the problems has a simple solution in LÖVE, although the second one might be solved by Stencils, but those are only there from 0.8.0.

And welcome!

You have to imagine how I'am working on this: I have constantly around 10 tabs open (some LÖVE documentations and "programming in lua" is allways open) while I'am learning things step by step. Pretty messy and exhausting but the more I'am doing it the more i love this framework (Iam not even sure what that is!) and the lua language. While messing around with gamemaker and gameeditor for a couple weeks, I figured out some of the basics like the if/for/while statements and how to work with logical operators. Now iam diggin into the matter of functions, algorithms and data structures (I love those lua tables btw.)

I'am really wondering what that "Stencil" stuff is you talk about. Do you care to explain or give me a link?

[Robin]

I'am really wondering what that "Stencil" stuff is you talk about. Do you care to explain or give me a link?

It's all very new and I haven't worked with it myself, but, in a picture:

It allows you to do something like this, but for images:

[clickrush]

if it is as usefull as funny this reply is then I'am looking forward to it

[miko]

EDIT: Ok I think I've found something that might resolve the task: http://rosettacode.org/wiki/Sutherland- ... n_clipping

Interesting. I have included both this implementation and your makeshadow function, and created a sample. There is some bug here (have not checked it), but it generally works as you wanted.
Press arrows to move a light source, shift+arrows to move an object, "l" to switch current light source, "o" to switch current object, and "z" or "x" to add random light source or object respectively.

I'am really wondering what that "Stencil" stuff is you talk about. Do you care to explain or give me a link?

http://love2d.org/forums/viewtopic.php? ... it=stencil

[clickrush]

this is great! thx very much.

I think the bugs could come from the "fill" mode as it does some strange things sometimes. gonna dig through your implementation now and hopefully learn a thing or two!

cheers

edit: i have to reword it: "fill" does behave strangely when your polygon is not properly defined or its vertices have some strange disposal.

edit: ok i finnaly get the concept of your code, allthough i dont understand the details really (I have to read through the lua reference again concerning tables and all the operators in a generic for loop...). But if I understood it right then you ask in the updateshadow function if there is more than one shadow for an object, then you send the shadows to the clipping function, while using your toVertexlist function to reorder the polygon table since the clipping function uses a tablestructure with points as tables instead of just the raw coordinates in one single table. Until now I'am almost 100% sure the bug comes from the order of the vertices so either one of those sources are responsible:

1. the makeshadow function does not order the vertices correctly, or at least not in a way where it is convenient to convert them...
2. the vertex conversion (from tables into raw data) you do is not 'consistent' (duh) enough with the order of the vertices.
3. the clipping function givesnt have a consistent enough order for the vertices
4. other, since I don't understand the code fully yet

I think the first solution i should try it so simply make the 2d table in the clipping function one dimensional, so it doesnt have to be converted at all and then just skip your table conversions? Letz try!

edit: completely abandoned my approach above since the clipping function is just too heavy to figure out for me. Playing around with your script (live) I figured that the bug almost allways occurs. Right now I'am guessing the worst case: it actually never really works but you can't see it allways... I've changed the object draw mode to 'line' and the outer lines actually never do sth weird, which would be a clear indication, that the polygon's vertices aren't aligned correctly in the tables. I don't even know what the question is...

EDIT: I got it yehaw!!!!! in the clipping functin (which I again found in the internet on the rosetta code wiki) searcher for the intersection points of the two polygons. The problem is: my polygons often have 2 coordinates in common and the intersection function doesn't take account for that possibility.
heres the intersection function inside the clipping function:

Code: Select all

function intersection(cp1, cp2, s, e)
  local dcx, dcy = cp1.x-cp2.x, cp1.y-cp2.y
  local dpx, dpy = s.x-e.x, s.y-e.y
  local n1 = cp1.x*cp2.y - cp1.y*cp2.x
  local n2 = s.x*e.y - s.y*e.x
  local n3 = 1 / (dcx*dpy - dcy*dpx)
  local x = (n1*dpx - n2*dcx) * n3
  local y = (n1*dpy - n2*dcy) * n3
  return {x=x, y=y}
end

so I just cheated to see if that is really the problem:

Code: Select all

function updateShadows()
  local shadow
  for k,o in ipairs(OBJECTS) do
    local currShadow, lshadow
    o.lightShadows={}
    for n,l in ipairs(LIGHTS) do
      if not currShadow then
        lshadow={makeshadow(l.x, l.y, o.x+n*2, o.y+n*2, o.w, o.h)} -- HERE I CHEATED LOL
        currShadow=toVertexList(lshadow)
        table.insert(o.lightShadows, lshadow)
      else
        lshadow={makeshadow(l.x, l.y, o.x, o.y, o.w, o.h)}
        currShadow=clip(currShadow, toVertexList(lshadow))
        table.insert(o.lightShadows, lshadow)
      end
    end
    o.shadow=fromVertexList(currShadow)
  end
end

I just moved one of the initial polygons a little so it allways has an intersection point. Since this isnt noticable I'll keep it that way until I'am smart enough to change the clipping function