I’ve decided to tackle the challenge of 2D shadows and lighting first in my to-be 2D game. It’s something I’ve wanted to try for a long time, and never really had the guts to try. It seems like a daunting task, but after a few days of work, I’ve produced a basic lighting system which can be extended to any polygon. It doesn’t use the best algorithm in the world, however it’s a start, and it’s something I can build on and improve later. Performance-wise, it’s not terrible. It can handle 400 2D lines (100 rectangles) at 20FPS and one light source. Here’s a video of it in action:
[vid url=”http://outbox.bitnode.co.uk/2G%202013-06-07%2018-32-47-35.webmvp8.webm”]
The above video demonstrates a slightly more advanced multi-light system. Click “read more” to read the details of how it works, how to make it, and the source code.
[WARNING: This method is terribly inefficient. Please read some of the more recent articles for better methods. Feel free to read this to understand the basics, though.]
So, diving in to the technical details:
The general approach here is to define a point from which rays (of light) will extend, up to a defined maximum length. We extend a ray at every angle (0-360) from this point of light. We do a check with every ‘line’ of every polygon in the area and see if this ray intersects this line. If it does intersect this line, limit the length of the ray to the value of the distance from the point of light to the point of intersection.
As shown in the picture, only for all the angles in between my drawn ‘rays’ (and for the full 360 degrees)
Now, obviously if we tell OpenGL to draw only at these rays we’re going to end up with something that looks like a sea urchin rather than a source of light. So, we solve this by using the GL_TRIANGLE_FAN mode. Assuming the first vertex you specify is the location of the light source, you then specify all of the intersection points we figured out above as the following vertices. That way, we fill in the space between the rays with our light, while excluding the area behind the objects!
The red line represents the shape that OpenGL will draw as we specify all the vertices. Obviously with more rays, we’ll get a better result that doesn’t overlap the objects we’re trying to draw shadows around, but you get the idea from the picture (hopefully).
So now we know what to do, how do we do it? I’ll post the source code as we go along. First, we need to define some basic classes which will help us keep track of everything. It is reasonable to make a Rectangle class, because we’re using rectangles frequently. We’ll give it a position, a width and a height, for now. We’ll also want a way to draw the rectangles easily, so we’ll add a public function for that too.
class RenRectangle
{
Point pos;
public float width;
public float height;
Color4 color = Color4.Blue;
public float Width
{
get
{
return width;
}
}
public float Height
{
get
{
return height;
}
}
public Point Pos
{
get
{
return pos;
}
}
public RenRectangle(Point pos, float width, float height)
{
this.pos = pos;
this.width = width;
this.height = height;
}
public void Render()
{
//set OpenGL to draw a series of lines, specified by a chain of points
GL.Begin(BeginMode.Quads);
GL.Color4(color.R, color.G, color.B, 1f);
//specify the points of the rectangle
GL.Vertex2(pos.X, pos.Y);
GL.Vertex2(pos.X + width, pos.Y);
GL.Vertex2(pos.X + width, pos.Y - height);
GL.Vertex2(pos.X, pos.Y - height);
GL.End();
}
public Line[] GetBounds()
{
Line[] bounds = new Line[4];
bounds[0] = new Line(pos.X, pos.Y, pos.X + width, pos.Y); //top
bounds[1] = new Line(pos.X, pos.Y, pos.X, pos.Y - height); //left
bounds[2] = new Line(pos.X + width, pos.Y, pos.X + width, pos.Y - height); //right
bounds[3] = new Line(pos.X + width, pos.Y - height, pos.X, pos.Y - height); //bottom
return bounds;
}
}
The RenRectangle class (odd name so as not to conflict with Windows Drawing Rectangle class) has a position, specified with a Point object. This is a basic class, again, which simply holds an X and a Y value.
class Point
{
public float X, Y;
public Point()
{
X = Y = 0;
}
public Point(float x, float y)
{
this.X = x;
this.Y = y;
}
}
One final thing you may have noticed in the RenRectangle class, the GetBounds function. Rectangles are made up of 4 lines, by definition, so we have a function which generates and returns a list of those lines. You’ll see where these lines come in later, but lets introduce the Lines class (again, very basic)
class Line
{
public float X, Y, endX, endY;
public Line(float x, float y, float endx, float endy)
{
this.X = x;
this.Y = y;
this.endX = endx;
this.endY = endy;
}
}
Great, so we are almost ready to get going with the fun stuff. I will introduce the final fundamental class at this point, the Vector class. This is a little more involved, but not difficult to understand. Anyone who has studied vectors before should get the idea
class Vector2
{
float x, y;
public float X
{
get
{
return x;
}
}
public float Y
{
get
{
return y;
}
}
public Vector2(float x, float y)
{
this.x = x;
this.y = y;
}
public float Modulus()
{
return (float)Math.Sqrt(Math.Pow(x, 2) + Math.Pow(y, 2));
}
public Vector2 Unit()
{
float mod = this.Modulus();
return new Vector2(x/mod, y/mod);
}
public static Vector2 operator +(Vector2 A, Vector2 B)
{
return new Vector2(A.X + B.X, A.Y + B.Y);
}
public static Vector2 operator -(Vector2 A, Vector2 B)
{
return new Vector2(A.X - B.X, A.Y - B.Y);
}
public static Vector2 operator /(Vector2 A, float div)
{
return new Vector2(A.X / div, A.Y / div);
}
public static Vector2 operator *(Vector2 A, float mult)
{
return new Vector2(A.X * mult, A.Y * mult);
}
}
The Vector2 class has some operator overrides, which simply let us do things like multiplication of a float by a vector, for example. Very handy!
If you haven’t studied vectors, you should look into those before continuing. At this point we’ll lose you if you don’t understand the basics of vectors!
Right, the fun stuff. We need some vector maths.
As we said above, we need to be able to find the intersection point of 2 lines. A vector can be defined like this:
B is the starting point of the vector, D is the unit vector in the direction of the vector, and t is the scalar multiplication factor (remember: t: how far in the direction of the unit vector do we go?)
So, we want to find out where the vector of the ray meets the vector of the line of a rectangle, and we want to do that for ALL lines of ALL rectangles for ALL rays of light (0-360).
So, lets define one vector for the ray of light:
A is the starting position (the origin of our ray of light) and E is our unit direction vector for the ray
Now lets define our vector for the line of a side of a rectangle:
S is the starting point of our line, D is the unit direction vector of the line.
These two lines intersect when:
Which, splitting into i and j components gives:
We want to know the value of tR, so lets rearrange and solve for tR:
After some manipulation:
where
Still with me? Great! Now we just put all that we’ve said above in code.
First, we make a struct to pass information around this class in a flexible manner:
struct Intercept
{
public float Distance;
public bool Hit;
public Intercept(float distance, bool hit)
{
this.Hit = hit;
this.Distance = distance;
}
}
It simply stores information about the distance and if the lines do indeed intersect. So, on to the fun part: the light class.
What we’ll do is make a class which has a number of properties relevant to the light source defined through a constructor:
class Light
{
bool IsInRange(float a, float b, float testpoint)
{
if (a > b)
{
if (testpoint >= b && testpoint <= a)
{
return true;
}
}
else
{
if (testpoint >= a && testpoint <= b)
{
return true;
}
}
return false;
}
bool HitTestBound(Point min, Point max, Point point)
{
return IsInRange(min.X, max.X, point.X) && IsInRange(min.Y, max.Y, point.Y);
}
protected Point pos;
protected Color4 color;
protected float size;
protected float originalpha = 0.2f;
protected float direction = 0;
protected float width = 361;
protected int anglestep = 1;
protected bool dynamicflag = false;
public Light(Point pos, Color4 lightColor, float size)
{
this.pos = pos;
this.color = lightColor;
this.size = size;
}
public void SetPos(Point newPos)
{
pos = newPos;
}
Here we simply define a constructor, some properties of the light, and a few useful functions we'll use later. Should be fairly straightforward.
Next, we need to define the Render function, which will render light given a list of RenRectangle objects. It will then iterate from startang to maxang (0 to 360 degrees, in this case) after specifying the first Vertex for our light at the position of the light
public void Render(List rectangles)
{
//set to triangle fan, first point acts as the central point
//from which the "fan" extends. Following points describe
//the arc of the fan
GL.Begin(BeginMode.TriangleFan);
GL.Color4(color.R, color.G, color.B, originalpha);
GL.Vertex2(pos.X, pos.Y); //central point
int startang = (int)(direction - (width / 2));
int maxang = (int)(direction + (width / 2));
//count in degrees, do for all 360 degrees
for (int i = startang; i <= maxang; i = i + anglestep)
Great, so what we do next will be done for each of the rays of light. First, it's a good idea to convert to radians, so we can use the Math library for Cos and Sin. We'll use that to work out the direction vector of the ray of light, which is a unit vector in the x or y direction
//convert to radians
float angle = (float)Math.PI * i / 180;
//unit vector in x direction
float dx = (float)Math.Cos(angle);
//unit vector in y direction
float dy = (float)Math.Sin(angle);
//scalar distance of ray
float t = size;
At this point is it important to note the variable t. Recall from above, t is the distance (magnitude) of the vector from the origin of the light to the intersect of the ray of light with the 'boundary' line of a rectangle (see fig. 2 above) which, if it doesn't intersect anything, is simply the max size of the light. So we set t = size, to start with, but t may change if we later find out the ray intersects with a boundary of a rectangle. So, how do we find that out? Well, we already did the maths above, we simply check all the boundaries (lines) of all our rectangles to see if they intersect with this particular ray!
foreach (RenRectangle rectangle in rectangles)
{
Line[] bounds = rectangle.GetBounds();
foreach (Line bound in bounds)
{
Intercept intercept = GetIntercept(bound, i, t);
if (intercept.Hit)
t = intercept.Distance;
}
}
We'll define GetIntercept later, but for now just try to understand what is happening here. We're setting t to the lowest possible value of the distance between the intercept point (of ANY line of any rectangle) and the origin of the light. So that means that if this ray of light intersects a boundary, we get the effect shown in figure 2 above, where the actual drawn 'light' is 'blocked' at this distance, and does not get drawn over the rectangle or beyond it. That gives the illusion of shadows! Now we need to let OpenGL know we want to draw a Vertex here, so we do the following to finish up:
float alphascale = originalpha * (t / size);
GL.Color4(color.R, color.G, color.B, originalpha - alphascale);
GL.Vertex2(pos.X + dx * t, pos.Y + dy * t);
}
GL.End();
}
The alphascale simply gives that 'fade out' effect, so that as the ray extends, the light looks more diffused.
Now we need to define that GetIntercept function I mentioned and used earlier, this is where that vector maths comes in:
protected Intercept GetIntercept(Line bound, float degang, float t)
{
float angle = (float)Math.PI * degang / 180;
//first calculate unit vectors of bound
Vector2 S = new Vector2(bound.X, bound.Y); //start of bound
Vector2 ES = new Vector2(bound.endX, bound.endY); //end of bound
Vector2 SP = ES - S;
//unit vector of bound
Vector2 D = SP / (float)(Math.Sqrt(Math.Pow(ES.X - S.X, 2)
+ Math.Pow(ES.Y - S.Y, 2)));
//now calculate unit vectors of ray
//origin of ray
Vector2 A = new Vector2(pos.X, pos.Y);
//x component of unit vector of ray
float Ex = (float)Math.Cos(angle);
//y component of unit vector of ray
float Ey = (float)Math.Sin(angle);
//now calculate t of bound line
float tb = ((S.X * Ey) - (A.X * Ey) + (A.Y * Ex)
- (S.Y * Ex)) / ((D.Y * Ex) - (D.X * Ey));
//now we can find t of ray
float tr = ((S.X) + (tb * D.X) - (A.X)) / Ex;
//now we find the intersect by substituting back
Vector2 intersect = S + (D * tb);
After building the vectors we defined in the maths bit beforehand, we use our formula, then define the 'intersect' vector, which is finally the point of interception! Now we must ensure the point of intersection lies on the line (because it's possible that it doesn't, because the vectors go on for infinity) so we simply use our HitTestBound function to check that the intercept lies within the (very thin) box that is the line of the rectangle. If it lies in this box, it lies on the line of the rectangle, and thus it intercepts at this point.
Point intersectpoint = new Point(intersect.X, intersect.Y);
Point startBox = new Point(bound.X, bound.Y);
Point endBox = new Point(bound.endX, bound.endY);
if (HitTestBound(startBox, endBox, intersectpoint) && tr <= t && tr >= 0.0f)
return new Intercept(tr, true);
else
return new Intercept(tr, false);
}
We return an Intercept structure (for future flexibility) with the new value of tR, which was what we set out to find.
So now we have that, it's time to put it to good use.
In our main program, we can generate some random rectangles and a light:
int n = 100;
rectangles = new List();
light = new Light(new Point(50, 50), Color4.White, 200f);
Random rand = new Random();
for (int i = 0; i < n; i++)
{
float newx = (float)rand.NextDouble() * rand.Next(0, ClientRectangle.Width);
float newy = (float)rand.NextDouble() * rand.Next(0, ClientRectangle.Height);
float newwidth = (float)rand.NextDouble() * rand.Next(50, 100);
float newheight = (float)rand.NextDouble() * rand.Next(50, 100);
rectangles.Add(new RenRectangle(new Point(newx, newy), newwidth, newheight));
}
Now we can add the following to our OnRenderFrame function override:
foreach (RenRectangle rectangle in rectangles)
{
rectangle.Render();
}
light.Render(rectangles);
And there you have it, you should be able to piece the rest of it together if you've a bit of experience with OpenGL and OpenTK. It simply involves taking care of viewports and setting up the screens, but that's out of the realm of this tutorial, and can be found with a quick google search! Extend functionality by making a list of lights, and rendering each light in a foreach loop, as we did with the rectangles.
This system is rather inefficient, but it gives a starting point for ray casting and 2D shadows. In following tutorials I will explain the dynamic lighting you see in the video. In tutorials after that, I will explain how to optimise the system further (after I've gained enough understanding myself!)
Leave a Reply