Website may be up and down over next few months. I'm currently doing a complete overhaul of everything. Going back to simple individual .htm pages, new overall site theme, sanitizing and cleaning up html of all pages and blog posts, attempting to implement a new tooling and publishing system etc etc.

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



biuquote
  • Comment
  • Preview
Loading






Created by: X

Just another personal website in this crazy online world

Name of author Dean Lunz (aka Created by: X)
Computer programming nerd, and tech geek.
About Me -- Resume