
Yesterday I wrote a method that allows you easily iterate through all Pixels (integer positions) within a
convex polygon's area. The reason I am doing this is because I want to be able to perform collisions between sprites and polygons, except my sprite objects have the ability to change size and shape every frame. I don't expect that using Farseer's
Texture to Vertices technology is something that I can use as often as I'll need to. Anyway, I just wanted to give you an example of how this could be applied.
I did some adhoc tests and it seems to be performing pretty reliably. All I did was iterate through the pixels and draw them to screen (which, BTW, is a horribly inefficient way to draw polygons). There are some issues if points overlap each other and other
degenrate cases like that. If anyone has any suggestions about my algorithm, or knows of a better way to do what I'm doing (I'd love to have a method public
static WhatYouWant DontReinventTheWheel() ), I'd like to hear it!
I guess I'll start by showing what usage looks like:
foreach (PixelRow pr in myGeom.WorldVertices.GetPixelRows()){
for (int i = pr.StartColumn; i <= pr.EndColumn; i++){
//Do whatever you want for pixel at new Vector2(pr.Row, i)
}
}
And now, the implementation. Basically there are two stages. First, I find the highest points of the polygon and remember the leftmost and rightmost ones. Stage 2 is where I go down a line at a time and return a PixelRow until I reach the end.
/// <summary>
/// Represents the start and end position of a particular row.
/// </summary>
public struct PixelRow
{
public int
Row,
StartColumn,
EndColumn;
}
/// <summary>
/// Returns an enumerator that iterates through each integral row
/// and returns a <code>PixelRow</code>, containing the row index,
/// starting column index, and ending column index.
/// </summary>
/// <param name="verts"></param>
/// <returns></returns>
public static IEnumerable<PixelRow> GetPixelRows(this Vertices verts)
{
//Assume verts is nonnull, CCW, convex, and has > 1 vertices
Debug.Assert(verts != null);
Debug.Assert(verts.IsConvex());
Debug.Assert(verts.Count > 1);
/* Start by finding the top left and top right vertices */
int highestLeftIndex = 0,
highestRightIndex = 0;
//The highest Y coordinate is the most negative Y coordinate
int highestY = (int) verts[0].Y;
int currY;
//Rotate CCW (over the top, to the left)
for (int i = 1; i < verts.Count; i++)
{
currY = (int) verts[i].Y;
if (currY > highestY) //Are we going down?
{
//We don't want to go down. We've gone as far left as possible.
break;
}
else if (currY < highestY) //Are we going up?
{
//Update to the new high point we found
highestLeftIndex = highestRightIndex = i;
highestY = currY;
}
else //We are traversing a horizontal span
{
//Leave highestRightIndex behindwe want it to stay
//on the right if there is a plateau.
highestLeftIndex = i;
}
}
int loopPoint = highestRightIndex;
//Rotate CW (over the top, to the right) starting at the highest right point
for (int i = verts.PreviousIndex(highestRightIndex); i != loopPoint; i = verts.PreviousIndex(i))
{
currY = (int) verts[i].Y;
if (currY > highestY) //Are we going down?
{
//We don't want to go down. We've gone as far right as
//possible and both indices are now correct.
break;
}
else if (currY < highestY) //Are we going up?
{
//Update to the new high point we found
highestLeftIndex = highestRightIndex = i;
highestY = currY;
}
else //We are traversing a horizontal span
{
//Leave highestLeftIndex behindwe want it to stay
//on the left if there is a plateau.
highestRightIndex = i;
}
}
/* Now that we have the indices of the highest vertices,
* start at them and travel down either side, returning
* a row of pixels at a time. */
int curRow = highestY;
Vector2 L1, L2, R1, R2;
float Lslope, Rslope;
PixelRow pr = new PixelRow();
//Proper initialization happens upon first iteration
L2 = verts[highestLeftIndex];
L2.Y; //To make curRow > L2.Y for the first iteration
R2 = verts[highestRightIndex];
R2.Y;
Lslope = Rslope = 0;
while (true)
{
if (curRow > L2.Y)
{
//Get the next edge segment
L1 = verts[highestLeftIndex];
highestLeftIndex = verts.NextIndex(highestLeftIndex);
L2 = verts[highestLeftIndex];
//Get the next edge segment if this one is horizontal
if ((int)L1.Y == (int)L2.Y)
continue;
//Break if we have reached the bottom
if ((int)L1.Y > (int)L2.Y)
break;
Lslope = (L2.X  L1.X) / (L2.Y  L1.Y);
}
if (curRow > R2.Y)
{
//Get the next edge segment
R1 = verts[highestRightIndex];
highestRightIndex = verts.PreviousIndex(highestRightIndex);
R2 = verts[highestRightIndex];
//Get the next edge segment if this one is horizontal
if ((int)R1.Y == (int)R2.Y)
continue;
//Break if we have reached the bottom
if ((int)R1.Y > (int)R2.Y)
break;
Rslope = (R2.X  R1.X) / (R2.Y  R1.Y);
}
//Return pixel row information
pr.Row = curRow;
pr.StartColumn = (int)(L2.X + Lslope * (curRow  L2.Y));
pr.EndColumn = (int)(R2.X + Rslope * (curRow  R2.Y));
yield return pr;
//Do the next row down
curRow++;
}
//All rows are done
yield break;
}

