Cowdozer 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. ```/// /// Represents the start and end position of a particular row. /// public struct PixelRow { public int Row, StartColumn, EndColumn; } /// /// Returns an enumerator that iterates through each integral row /// and returns a PixelRow, containing the row index, /// starting column index, and ending column index. /// /// /// public static IEnumerable 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; } ```