Ian Guthridge.com

Edge Mapping

Some Background:

For Audiball, I had to create a system that would let us make obstacles out of any texture even concave ones. The most straightforward system I could envision that would work with our existing collision model (at the time based on normals) was to generate an ordered array of edge pixels, and use those to compute the normal vector at the collision point.

Now there are 2 major values that have to be kept as small as possible whenever writing an algorithm like this: the “big O” runtime and memory usage of the algorithm. That being said, you must also keep the development schedule in mind, so the question is, just how efficient does the algorithm need to be? My code is definitely not the most optimal solution, but it is good enough. This is because we are able to do all the “heavy” computation when the level loads, and thanks to the wonders of static hash tables (or “dictionaries” in C#), I only have to compute the edge map once per texture (even if copies of it are loaded and unloaded dozens times). 

How to:

Computing an edge map is a relatively straight forward process: find the object pixels, determine which of those are edge pixels, and then sort them so that they represent something meaningful. 

First, we iterate through the array and create a 1 bit map of the texture: 1 if it is part of our object, and 0 if it is a transparent background pixel. As a side note, a boolean in C# is between 8 and 32 bits in size, depending on how it lines up in memory.  An on-off value taking up more than 1 bit just seems silly! Luckily Microsoft isn’t stupid, so they created a lovely structure called BitArray that compresses an array of booleans so that each is properly represented by 1 bit*. Thus, we can create an array of those and have a bit map. Now we need to get rid of all those excess “body pixels”. We’ll define a body pixel as a pixel that has a value of 1, as well as four neighboring pixels with a value of 1. So after we iterate through and remove all of those, we are left with an bitmap containing our edge. 

After we convert that to an array of x,y coordinates, we are almost done… we just have to sort it. I employed 2 methods of sorting, a radial sort and a nearest neighbor sort. I did this because while the radial sort works on all “simple” objects 100% of the time, “complex” objects (i.e. hollow objects and concave objects whose centroid lies outside its “body”) turn out nasty at best. A naive nearest neighbor sort averages about 90% accuracy between the two types of objects, because it can get confused when it hits acute angles. Furthermore, it is really helpful to have a standard origin when we rotate our obstacles (a topic I will discuss in a later post). Combining the two produces a very robust system with only one issue… Some obstacles are ordered going clockwise, while others are ordered going counter-clockwise. This isn’t an issue unless the obstacle is rotated, and even then a simple check of the handedness works rather well and is more efficient than reordering the array.

Here is link to the code: makeEdge(),VertexCompare.cs. BEFORE USING THIS CODE: This code is not optimized and is inefficient. I did not optimize it, because it was intended to only runs once per texture (during level loads), storing the result in a static hash table(C# calls this a dictionary).

And to sum it up, here is a picture to elaborate on the process:

Edge Map Demo pic

The vector render I use for debugging draws a line between each point in the array, so the first image looks a little odd, but the three images are, from left to right, the unsorted edge map, the map after a radial sort, and the map after the radial sort and the nearest neighbor search.

*A few minor caveats:

  1. The BitArray object itself will take up some space, so it is really only helpful if you need to store some significant number of booleans.
  2. BitArray is  a reference type and will therefore exist on the heap and produce garbage. A boolean is a value type and will reside on the stack.  Keep this in mind if you are on a platform that has issues with garbage collection (such as the Xbox 360) and are planning on running this algorithm a lot.
  3. Because of how data fits into memory, the actual number of bits this object [from my understanding] will take up will be (size of BitArray object + number of items) rounded up to the nearest  32 bits
  • Share/Bookmark

Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!