Convert Polygon region to list of Pixels

Topics: User Forum
Aug 16, 2009 at 6:19 PM

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 ad-hoc 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 behind--we 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 behind--we 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;
}