Draws a polygon using the scan-line algorithm.

draw_polygon.gml

/// @desc Uses the scan line algorithm to render a polygon.
/// @param polygon {Integer} The id of the ds_list which stores pairwise positios of verticies.
/// @param outline {Boolean} Draw an outline instead of a filled shape.
/// @author Kat @katsaii
var count = ds_list_size(argument0) div 2;
if (count > 1) {
    if (argument1) {
        // outline
        draw_primitive_begin(pr_linestrip);
        draw_vertex( // last vertex
                argument0[| (count - 1) * 2 + 0],
                argument0[| (count - 1) * 2 + 1]);
        for(var i = 0; i < count; i++){
            draw_vertex( // current vertex
                    argument0[| i * 2 + 0],
                    argument0[| i * 2 + 1]);
        }
        draw_primitive_end();
    } else {
        // scanline
        var top = infinity;
        var bottom = -infinity;
        // compile edge table
        var x1 = argument0[| (count - 1) * 2 + 0]; // last vertex
        var y1 = argument0[| (count - 1) * 2 + 1];
        var edges = ds_grid_create(4, count); // every vert has a corresponding edge
        for (var i = 0; i < count; i++){
            var x2 = argument0[| i * 2 + 0];
            var y2 = argument0[| i * 2 + 1];
            // add vertex data to the edge table
            if (y2 < y1){
                edges[# 0, i] = x1;
                edges[# 1, i] = y1;
                edges[# 2, i] = x2;
                edges[# 3, i] = y2;
            } else {
                edges[# 0, i] = x2;
                edges[# 1, i] = y2;
                edges[# 2, i] = x1;
                edges[# 3, i] = y1;
            }
            // update last vertex
            x1 = x2;
            y1 = y2;
            // check whether the vertex is the new max/min
            top = min(top, y1);
            bottom = max(bottom, y1);
        }
        // sort the edge table by y-axis
        ds_grid_sort(edges,3,true);
        // draw scan lines
        var line_count = 0;
        top = floor(top);
        bottom = ceil(bottom);
        draw_primitive_begin(pr_linelist);
        for (var yy = top; yy <= bottom; yy++) {
            var intersections = ds_list_create();
            // step through y-axis
            for (var i = 0; i < count; i++) {
                var x1 = edges[# 0,i];
                var y1 = edges[# 1,i];
                var x2 = edges[# 2,i];
                var y2 = edges[# 3,i];
                // check for a collision (where y1 < yy)
                if (y2 > yy) {
                    // no more collisions
                    break;
                } else if (y1 > yy) {
                    // collision with the edge: find the point of intersection
                    var xx;
                    if (abs(x2 - x1) < 0.01) {
                        // vertical intersection where the gradient is undefined
                        xx = (x2 + x1) * 0.5;
                    } else {
                        // y = mx + c => y + c = mx => x = (y + c)/m
                        var mm = (y2 - y1) / (x2 - x1);
                        var dy = yy - y1;
                        var dx = dy / mm;
                        xx = x1 + dx;
                    }
                    // add x vertex to the vertex list
                    ds_list_add(intersections, xx);
                }
            }
            // sort verts
            ds_list_sort(intersections, true);
            for (var j = 0; j < ds_list_size(intersections); j++){
                var xx = intersections[| j];
                draw_vertex(xx, yy);
                if (line_count < 1000) {
                    // increment the draw count for the vertex system
                    line_count++;
                } else {
                    // create a new primitve when the vertex count has reached the threshold
                    draw_primitive_end();
                    draw_primitive_begin(pr_linelist);
                    line_count = 0;
                }
            }
            ds_list_destroy(intersections);
        }
        draw_primitive_end();
        ds_grid_destroy(edges);
    }
}