This code uses a Point type that contains X/Y as integers similar to System.Drawing.Point. This class is used to calculate vertical scan lines for a polygon. It has been tested with 3 points but beyond that I am unsure if it will work. using System; /// <summary> /// Helper class used to calculate scan lines of a triangle /// </summary> public class TriangleScanLineCalculator { /// <summary> /// Provides a high low type for storing min & max values for scan lines. /// </summary> public struct HiLoTYPE { public int High; public int Low; } /// <summary> /// Holds scan line information. /// </summary> protected internal HiLoTYPE[] scanLines; /// <summary> /// Holds the calculated scan line count. /// </summary> protected internal int scanLineCount; /// <summary> /// Gets the right most side of the triangle. /// </summary> public int MaximumX { get; private set; } /// <summary> /// Gets the left most side of the triangle. /// </summary> public int MinimumX { get; private set; } /// <summary> /// Gets the number of scan lines. /// </summary> public int Count { get { return scanLineCount; } } /// <summary> /// Calculates the min & max y values for each scan line. /// </summary> /// <param name="points">The points that make up the triangle</param> public void Calculate(Point[] points) { var xMax = 0; var xMin = 0; float XDelta = 0; float YDelta = 0; // X/Y distance between 2 vertexes float YPos = 0; float YSlope = 0; var VertIndex1 = 0; var VertIndex2 = 0; var tempIndex = 0; // Step 1: Find the min and max 'X' dimensions of the polygon xMax = int.MinValue; xMin = int.MaxValue; for (var i = 0; i <= points.Length - 1; i++) { if (xMax < points[i].X) { xMax = points[i].X; } if (xMin > points[i].X) { xMin = points[i].X; } } this.MinimumX = xMin; this.MaximumX = xMax; this.scanLineCount = xMax - xMin; // Step 2: Resize scan line array to hold all the high and low x values if (this.scanLines == null || this.scanLines.Length < xMax - xMin) { // allocate Array.Resize(ref this.scanLines, (xMax - xMin) + 100); } // Step3: Set the height value of all scan lines to there min or max value(s) for (var i = 0; i <= this.scanLines.Length - 1; i++) { this.scanLines[i].High = int.MinValue; this.scanLines[i].Low = int.MaxValue; } // Step 4: Set up the Y highs and lows for each X scan line between the min X and Max X points for (var i = 0; i < points.Length; i++) { // Step4a: Determine witch sides of the polygon we will be setting up VertIndex1 = i; VertIndex2 = i + 1; if (VertIndex2 == points.Length) VertIndex2 = 0; // Step4b: check if the first vertex if farther right then the second vertex // and if so swap vertex indexes if (points[VertIndex1].X > points[VertIndex2].X) { tempIndex = VertIndex1; VertIndex1 = VertIndex2; VertIndex2 = tempIndex; } // Step4c: Find the X/Y dist between vert1 and vert2 XDelta = points[VertIndex2].X - points[VertIndex1].X; YDelta = points[VertIndex2].Y - points[VertIndex1].Y; // Step4d: Determine the Y slope to use. // YSlope determines how much to move down for every move we make to the right if (XDelta != 0) { YSlope = YDelta / XDelta; } else { YSlope = 0; } // Save the starting y position in YPos YPos = points[VertIndex1].Y; // Step4e: Process all of scan lines between vert1 and vert2 for (var idy = points[VertIndex1].X; idy < points[VertIndex2].X; idy++) { // If the scan lines higher value has already been set then set the lower value // we use the formula 'idy - XMin' to determine what index into the scan line // array to use. (ScanLineIndex = AnyPositionBetweenVert1AndVert2 - LeftMostPartOfPoly) // Store the scan line index in the TmpIndex variable so we don't // have the overhead of doing 5 subtractions tempIndex = idy - xMin; var item = this.scanLines[tempIndex]; // Check if Scan(TmpIndex).High has been set already if (item.High == int.MinValue) { // High has not been set yet item.High = (int)YPos; } else { // High has been set yet so we set the low point item.Low = (int)YPos; // Ensure that the High is actually a higher value then low if (item.High < item.Low) { var tempValue = item.High; item.High = item.Low; item.Low = tempValue; } } this.scanLines[tempIndex] = item; // update the Y position YPos += YSlope; } } } /// <summary> /// Retrieves a scan line. /// </summary> /// <param name="index">The index of the scan line.</param> /// <returns>Returns information about the scan line.</returns> public HiLoTYPE ScanLine(int index) { return this.scanLines[index]; } /// <summary> /// Gets all the scan lines. /// </summary> /// <returns>Returns all the scan line information.</returns> public HiLoTYPE[] GetScanLines() { // if there are no scan lines return null. if (this.scanLineCount == 0) { return null; } // resize the array Array.Resize(ref this.scanLines, this.scanLineCount); return this.scanLines; } /// <summary> /// Calculates the scan lines for a triangle. /// </summary> /// <param name="points">The triangle points.</param> /// <param name="minXValue">Will return the minimum x value that the triangle starts at.</param> /// <returns>Returns the min max y values of the scanline.</returns> public static HiLoTYPE[] Calculate(Point[] points, out int minXValue) { // create scan line calculator and get values from it var scanner = new TriangleScanLineCalculator(); scanner.Calculate(points); var items = scanner.GetScanLines(); minXValue = scanner.MinimumX; return items; } } |

Add comment