Draw A Filled Polygon Using Scanline Loop
I'm trying to draw a filled polygon using individual pixels in a scanline loop (so no lineTo or fill Canvas methods). I was able to achieve a triangle in this method (example below
Solution 1:
Scanline for non self intersecting polygons.
Draw any concave or convex polygon with 3 or more sides using scanline method.
- Is the easiest, also slowest.
- Polygon is a set of lines with start and end points.
- Polygon lines can be unordered
- Polygon must be closed
- None of polygon lines can cross any of the other polygon lines.
Steps
Find bounding box of lines. top, left, right, bottom.
Set x, y totopleft of bounding box.
while y is less than bottom.
Find all lines that will cross the line fromleft, y toright, 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 1to y
An implementation.
Function scanlinePoly(lines, col)
draw the pixels. lines
is create with createLines
which is an array of lines with helper functions to add lines, find lines, sort lines, and get bounds.
Helper functions
createStar(x, y, r1, r2, points)
will create alines
array for a star,x
,y
center of star,r1
radius,r2
second radius,points
number of pointsP2(x, y)
returns 2D pointL2(p1, p2)
returns 2D line that includes the slope of the line.p1
,p2
are points as created byP2
atLineLevelY(y)
returns true if line crosses scan line aty
constscanlinePoly = (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 toconst 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 }
}
}
}
functioncreateLines(linesArray = []) {
returnObject.assign(linesArray, {
addLine(l) { this.push(l) },
getLinesAtY(y) { returncreateLines(this.filter(l =>atLineLevelY(y, l))) },
sortLeftToRightAtY(y) {
for (const l ofthis) { l.dist = l.p1.x + l.slope * (y - l.p1.y) }
this.sort((a,b) => a.dist - b.dist);
returnthis;
},
nextLineFromX(x) { // only when sortedconst 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 ofthis) {
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};
},
});
}
constcreateStar = (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");
constP2 = (x = 0,y = 0) => ({x, y});
constL2 = (p1 = P2(), p2 = P2()) => ({p1, p2, slope: (p2.x - p1.x) / (p2.y - p1.y)});
constatLineLevelY = (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;}
<canvasid="canvas"width="200"height="180"></canvas>Click for rand star
Note that inner loop
for (xx = xS; xx < xE; xx++) {
ctx.fillRect(xx, y, 1, 1);
}
Can be replaced with ctx.fillRect(xS, y, xE - xS, 1)
to greatly improve performance.
UPDATE
Looking at my answer again to see if it could be improved I noticed a problem that resulted in lines incorrectly rendered.
To fix the the first line inside the outer loop of function scanlinePoly
needs to be changed from.
const ly = lines.getLinesAtY(y).sortLeftToRightAtY(y);
To
const ly = lines.getLinesAtY(y + 0.5).sortLeftToRightAtY(y + 0.5);
Post a Comment for "Draw A Filled Polygon Using Scanline Loop"