使用Scanline循环绘制填充多边形

Question

我试图在scanline循环中使用单个像素绘制一个填充的多边形(因此没有lineTo或fill画布方法)。

我能够在这个方法中实现一个三角形(下面的例子)，但是我不知道从哪里开始一个更复杂的多边形(比如星型★)。对于如何处理Javascript &画布的这个或现有的形状算法示例，有人能给出任何建议吗？

我曾经研究过Bresenham的算法，但是由于我对它的理解有限，所以对多边形的实现没有成功。如果有什么不清楚的地方请告诉我。

谢谢!

​

var canvas = document.querySelector('#canvas')
var ctx = canvas.getContext('2d');
var widthRange = document.querySelector('#widthRange')
var heightRange = document.querySelector('#heightRange')
ctx.fillStyle = 'blue';

var DrawPixel = function (x, y) {
  ctx.fillRect(x, y, 1, 1);
}

var x = 100;
var y = 100;
var width = widthRange.value;
var height = heightRange.value;

const draw = () =>
{
  ctx.clearRect(0,0,canvas.width,canvas.height); 
  wHRatio = width/height;
  for (var j=0; j<height; j++)
  {
    w = width-j*wHRatio;
    for (var i=0; i<w; i++)
    {
      DrawPixel(Math.floor(i+(j*(wHRatio/2))),height-j);
    }
  }
}

draw();

widthRange.addEventListener("input", function(e){
  width = e.currentTarget.value;
  draw();
})

heightRange.addEventListener("input", function(e){
  height = e.currentTarget.value;
  draw();
})

#canvas {
  outline: 1px solid grey;
}

.slidecontainer
{
  display: inline-block;
}

<div class="slidecontainer">
  <label for="widthRange">Width</label>
  <input type="range" min="1" max="300" value="100" class="slider" id="widthRange">
</div>
<div class="slidecontainer">
  <label for="heightRange">Height</label>
  <input type="range" min="1" max="150" value="100" class="slider" id="heightRange">
</div>
<canvas width=300 height=150 id="canvas"></canvas>

​

Answer 1

非自交多边形的扫描线。

使用scanline方法绘制具有3条或多条边的凹多边形或凸多边形。

slowest.

• Polygon是最简单的，而且points.

• Polygon是一组有开始和结束的直线，可以是unordered

• Polygon必须关闭

• ，任何多边形线都不能跨越任何其他多边形线。

步骤

Find bounding box of lines. top, left, right, bottom.
Set x, y to  top left of bounding box.
while y is less than bottom.
    Find all lines that will cross the line from left, y to right, y
    Sort lines in distance from x to point where above line crossed
    while there are sorted lines
        shift two lines from sorted lines and scan the pixels between
    add 1 to y      

A实施。

函数scanlinePoly(lines, col)绘制像素。lines是用createLines创建的，它是一个带有辅助函数的行数组，用于添加行、查找行、排序行和获取边界。

辅助函数

• createStar(x, y, r1, r2, points)将为星体、x、y星心、r1半径、r2第二半径创建一个lines数组，points数返回2D point
• L2(p1, p2)返回包含直线斜率的2D行。P2
• atLineLevelY(y)创建的点，如果行在y

处横过扫描线，则返回true

​

const scanlinePoly = (lines, col) => {
    const b = lines.getBounds();
    var x, y, xx;
    ctx.fillStyle = col;
    b.left = Math.floor(b.left);
    b.top = Math.floor(b.top);
    for (y = b.top; y <= b.bottom; y ++) {
        // update 
        // old line was const ly = lines.getLinesAtY(y).sortLeftToRightAtY(y);
        // changed to
        const ly = lines.getLinesAtY(y + 0.5).sortLeftToRightAtY(y + 0.5);
        x = b.left - 1; 
        while(x <= b.right) {
            const nx1 = ly.nextLineFromX(x);
            if (nx1 !== undefined) {
                const nx2 = ly.nextLineFromX(nx1);
                if (nx2 !== undefined) {
                    const xS = Math.floor(nx1); 
                    const xE = Math.floor(nx2); 
                    for (xx = xS; xx < xE; xx++) {
                        ctx.fillRect(xx, y, 1, 1);
                    }
                    x = nx2;
                } else { break }
            } else { break }
        }
    }
}

function createLines(linesArray = []) {
     return   Object.assign(linesArray, {
        addLine(l) { this.push(l) },
        getLinesAtY(y) { return createLines(this.filter(l => atLineLevelY(y, l))) },
        sortLeftToRightAtY(y) {
            for (const l of this) { l.dist = l.p1.x + l.slope * (y - l.p1.y) }
            this.sort((a,b) => a.dist - b.dist);
            return this;
        },
        nextLineFromX(x) { // only when sorted
            const line = this.find(l => l.dist > x);
            return line ? line.dist : undefined;
        },
        getBounds() {
            var top = Infinity, left = Infinity;
            var right = -Infinity,  bottom = -Infinity;
            for (const l of this) {
                top = Math.min(top, l.p1.y, l.p2.y);
                left = Math.min(left, l.p1.x, l.p2.x);
                right = Math.max(right, l.p1.x, l.p2.x);
                bottom = Math.max(bottom, l.p1.y, l.p2.y);
            }
            return {top, left, right, bottom};
        },
    });
}

const createStar = (x, y, r1, r2, points) => {
    var i = 0, pFirst, p1, p2;
    const lines = createLines()
    while (i < points * 2) {
        const r = i % 2 ? r1 : r2;
        const ang = (i / (points * 2)) * Math.PI * 2;
        p2 = P2(Math.cos(ang) * r + x, Math.sin(ang) * r + y);
        if (pFirst === undefined) { pFirst = p2 };
        if (p1 !== undefined) { lines.addLine(L2(p1, p2)) }
        p1 = p2;
        i++;
    }
    lines.addLine(L2(p2, pFirst));    
    return lines;
}
const ctx = canvas.getContext("2d");

const P2 = (x = 0,y = 0) => ({x, y});
const L2 = (p1 = P2(), p2 = P2()) => ({p1, p2, slope: (p2.x - p1.x) / (p2.y - p1.y)});
const atLineLevelY = (y, l) => l.p1.y < l.p2.y && (y >= l.p1.y && y <= l.p2.y) || (y >= l.p2.y && y <= l.p1.y);

canvas.addEventListener("click", () => {
    ctx.clearRect(0,0,200,200);
    const star = createStar(
        100, 90, 
        Math.random() * 80 + 10,
        Math.random() * 80 + 10,
        Math.random() * 20 + 2 | 0
    );
    scanlinePoly(star, "#F00")


})


const star = createStar(100, 90, 90, 40, 10);
scanlinePoly(star, "#F00")

canvas {border: 1px solid black;}

<canvas id="canvas" width="200" height="180"></canvas>Click for rand star

​

注记内循环

for (xx = xS; xx < xE; xx++) {
    ctx.fillRect(xx, y, 1, 1);
}

可以用ctx.fillRect(xS, y, xE - xS, 1)代替，大大提高性能。

更新

再看一遍我的答案，看看是否可以改进，我注意到了一个问题，它导致行被错误地呈现。

要修复函数外循环中的第一行，需要更改scanlinePoly。

const ly = lines.getLinesAtY(y).sortLeftToRightAtY(y);

至

const ly = lines.getLinesAtY(y + 0.5).sortLeftToRightAtY(y + 0.5);