This builds on my previous system, which you can see in my previous post. If you want to learn how to make simple 2D lighting, read that first. If you want to know how to make it 10x+ faster, read this!
So, this post deals with the issues faced with the inefficient method described originally – that was, checking every single ray against every single 2D surface. Imagine doing this manually: draw some rectangles on a page, and for each degree from 0 – 360, you want to draw a ray extending from the center, limiting the length of the ray to the first thing the ray meets. Now assuming you’re a smart individual, you would only consider the rectangles on your piece of paper that are roughly in the direction of the ray you’re drawing. That makes sense, when you think about it: why would you even bother to look at rectangles that are in totally the wrong direction of the ray? Well, that’s what our previous algorithm was doing! Fortunately, there’s a solution. It’s called ‘spatial hashing’. It’s great! Here’s a video of it in action:
[vid url=”http://outbox.bitnode.co.uk/2G%202013-06-09%2004-20-49-09.webmvp8.webm”]
We’re getting 60+FPS with 100 rectangles and multiple lights, now, which is a vast improvement. There’s some extra optimizations we can make, in addition to spatial hashing, but we’ll stick with this for now for the sake of simplicity.
Just for a rough idea of just how good this can be:
The old algorithm of checking EVERY surface with EVERY ray regardless of the direction took about ~117ms per light for 400 surfaces
With this spatial hashing algorithm, that time is reduced to ~4ms
A huge improvement, and we still have more improvements we can make! Read more to find out how, and to see 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 method to understand the basics!]
As explained in the introduction, we essentially want the computer to be smarter about how it checks for intersects with rays and surfaces. Put simply, we don’t want it checking through all the surfaces, only the ones which the ray might hit. So how do we do that? Spatial hashing! Spatial hashing is where we divide the screen into smaller segments, work out which segment(s) (known as ‘buckets’) of the screen each rectangle is in. We then assign each rectangle to the buckets it lies within. Now we do our ray cast as normal, only this time we first work out which bucket our ray is in. Our ray can only ever intersect with the rectangles in that bucket, so here’s the key: we only check for intersects with the rectangles in that particular bucket! That has a tremendous advantage, because before we were looping over 400 rectangle boundaries (100 rectangles) for each ray, whereas now we’re only looping over the rectangles within the bucket the ray is within, which may only be a few!
Now since we’re ray casting, it makes sense to split the screen radially, like this:
Traditional 2D spatial hashing divides the screen into boxes, but this way is simple. You can try dividing the screen into boxes instead, and working out what boxes the light has influence in, and only looping over the rectangles in those boxes, but I’ll leave that up to you.
So, on to the “how”. First, we’ll need a new class. We’ll start with a constructor and a few basic members:
class RadialSpatialHasher
{
Point origin; //origin of the buckets (should match position of light)
int n; //how many buckets we want
double stopang; //leave as 2*PI for now, we want a full circle
double bucketsize; //we can work this out in our constructor (stopang/n)
ListNow we need a way to work out which bucket a particular angle falls into
public int GetBucketID(double ang)
{
//we need to implement some sort of "fall through" so that if the angle is -ve, we
//don't return a negative index because they don't exist! So find the equivalent positive one
//if the angle is -ve by subtracting the absolute of the angle from 2*PI
if (ang >= 0)
return (int)Math.Floor(ang / bucketsize);
else
return (int)Math.Floor( ((Math.PI*2) - Math.Abs(ang)) / bucketsize);
}
The reason we must check for a -ve angle is that there are no negative elements in an array, and there are no negative buckets! So if the angle is negative, we simply work out which bucket the angle falls into by working out the equivalent positive angle (2*PI – Abs(angle)).
Next, we need to have some way of working out which buckets a rectangle is in. Imagine a rectangle so large that it spans across 2 or more buckets, so we need to work out which buckets it falls into.
public List GetBucketsInRange(double minang, double maxang)
{
int startbucket = GetBucketID(minang);
int endbucket = GetBucketID(maxang);
List buckets = new List();
for (int i = startbucket; i <= endbucket; i++)
{
buckets.Add(i);
}
return buckets;
}
This method just returns a list of bucket IDs starting at one angle and ending at another (larger) angle. Should be easy enough!
Now the slightly harder part: we need to have a way of inserting the rectangles into all the buckets they fall into. On first thought, this sounds easy, but it's a little tricky if the rectangle overlaps the 0-360 boundary. We first need to find out the maximum angle of our rectangle, and the minimum angle. That is, the vertex with the largest angle from horizontal and the vertex with the smallest. That is a little tricky, but I'll explain later (see the appendix). For now, lets handle the adding of the rectangle to the buckets assuming we already know the minimum/maximum angle of the rectangle:
public void AddToBuckets(object newObject, double minang, double maxang)
{
List bucketIDs;
if (minang < 0)
{
bucketIDs = new List();
//if the object has overlapped the boundary: use the absolute value of the minimum angle
//work out how many segments this correlates to and fill buckets from
//(n - (number of segments we just worked out) to (n) AND segments from 0 to max angle
double tempang = Math.Abs(minang);
int bucketCount = GetBucketID(tempang);
for (int i = ( (n-1) - bucketCount); i <= (n-1); i++)
bucketIDs.Add(i);
//now we handle everything from 0 to the max angle
int posBuckets = GetBucketID(maxang);
for (int i = 0; i <= posBuckets; i++)
bucketIDs.Add(i);
}
else
{
bucketIDs = GetBucketsInRange(minang, maxang);
}
foreach (int bucketID in bucketIDs)
{
if (buckets[bucketID] == null)
buckets[bucketID] = new ListAs you see above, if the minimum angle of the rectangle is positive, it's easy (just use the GetBucketsInRange method we made earlier). However, if the minimum angle is less than 0, I.E this rectangle overlaps the 0-360 boundary, we need to do some thinking. First of all, treat the minimum angle as if it were positive, I.E take the absolute value. Now work out which bucket that would fall into, assuming the angle is positive. Now we just subtract that many buckets from the maximum bucket (n-1) and fill in the budkets between that. Exmaple: -0.5 radians -> imagine 0.5 radians falls in bucket 1. So we put this rectangle in buckets from (n-1) - 1, to (n-1) (I.E the last two buckets) and then we fill in from bucket 0 to the max angle, as usual. A little confusing, but read it enough time and it should make sense.
Finally, we want a function to get all the rectangles in a given bucket.
public ListWe just do some safety checks to ensure this bucket ID is sensible, and return the bucket with this ID.
Now we just modify the code from the Light class in my previous blog post:
public static void RenderLights(List lights, List rectangles, int n)
{
foreach (Light light in lights)
{
//make a hash at the position of this light, with a max angle of 2*PI
RadialSpatialHasher hash = new RadialSpatialHasher(light.pos.X,
light.pos.Y, n, Math.PI * 2);
foreach( RenRectangle rectangle in rectangles)
{
//add this rectangle to the hash, by working out the min/max angle of this rectangle from the light source
hash.AddToBuckets(rectangle, rectangle.MinAngle(light.pos.X,
light.pos.Y),rectangle.MaxAngle(light.pos.X,
light.pos.Y));
}
GL.Begin(BeginMode.TriangleFan);
GL.Color4(light.color.R, light.color.G, light.color.B, light.originalpha);
GL.Vertex2(light.pos.X, light.pos.Y); //central point
int startang = 0;
int maxang = 360;
//count in degrees, do for all 360 degrees
for (int i = startang; i <= maxang; i = i + light.anglestep)
{
if ((i == startang + 90) || (i == startang + 270))
continue;
float angle = (float)Math.PI * i / 180; //convert to radians
float dx = (float)Math.Cos(angle); //unit vector in x direction
float dy = (float)Math.Sin(angle); //unit vector in y direction
float t = light.size; //scalar distance of ray
//Here's the key part: we only loop for all the rectangles in this bucket!
//We get the bucket this ray is in by doing hash.GetBucketID(angle) where angle
//is the angle of this particular ray
foreach (RenRectangle rectangle in hash.GetBucket(hash.GetBucketID(angle)))
{
Line[] bounds = rectangle.GetBounds();
foreach (Line bound in bounds)
{
Intercept intercept = light.GetIntercept(bound, i, t);
if (intercept.Hit)
t = intercept.Distance;
}
}
float alphascale = light.originalpha * (t / light.size);
GL.Color4(light.color.R, light.color.G, light.color.B,
light.originalpha - alphascale);
GL.Vertex2(light.pos.X + dx * t, light.pos.Y + dy * t);
}
GL.End();
}
}
The comments explain the modified parts: if there's something you don't understand, take a look at my previous blog post. Hopefully now you'll have a basic understanding of how to make a radial spatial hash. You can experiment with the n parameter, to make fewer or more buckets. I found that hundreds of buckets works "bucket loads" better, but you can experiemnt for yourself by using the StopWatch class and finding out how long it takes to run the function. Good luck!
Appendix:
One final bit of code to help you: finding the min/max angle of all points in a rectangle. You'll need this when adding the rectangle to the hash. You can add this to your Rectangle class from the previous tutorial.
public double MaxAngle(float originX, float originY)
{
double maxang = 0;
bool overlap = false;
if (pos.Y >= originY && pos.Y - height < originY)
overlap = true;
foreach (Line bound in GetBounds())
{
foreach (Point endpoint in bound.GetEndpoints())
{
double newang = Vector2.AngleFromZero(originX, originY,
endpoint.X, endpoint.Y, overlap);
if (newang > maxang)
maxang = newang;
}
}
return maxang;
}
public double MinAngle(float originX, float originY)
{
double minang = (float)(2*Math.PI);
bool overlap = false;
if (pos.Y >= originY && pos.Y - height < originY)
overlap = true;
foreach (Line bound in GetBounds())
{
foreach (Point endpoint in bound.GetEndpoints())
{
double newang = Vector2.AngleFromZero(originX, originY, endpoint.X, endpoint.Y, overlap);
if (newang < minang)
minang = newang;
}
}
return minang;
}
The following code can be added to your Vector class. It is used ot work out the angle from one point to the other, and also takes into account if the shape overlaps the 0-360 boundary. A little bit of trigonometry will go far, here.
public static double AngleFromZero(float originX, float originY, float endX, float endY, bool overlap)
{
float dx = endX - originX;
float dy = endY - originY;
if (dx > 0)
{
//we're in the right-hand plane
if (dy > 0)
{
//we're in the top-right-hand plane
return Math.Atan(Math.Abs(dy / dx));
}
else
{
//we're in the bottom-right-hand plane
if (!overlap)
return ((2*Math.PI) - Math.Atan(Math.Abs(dy / dx)));
else
return (- Math.Atan(Math.Abs(dy / dx)));
}
}
else
{
if (dy > 0)
{
//we're in the top-left-hand plane
return (Math.PI - Math.Atan(Math.Abs(dy / dx)));
}
else
{
//we're in the bottom-left-hand plane
return (Math.PI + Math.Atan(Math.Abs(dy / dx)));
}
}
}
Leave a Reply