有没有绘制粗抗锯齿线条的“标准”算法？我发现了夏林·吴（Xiaolin Wu）用于绘制1像素宽线条的算法，但还没有找到任何用于粗线条的扩展。
3个回答
4
如果你的线始终是直的，并且不需要抗锯齿曲线，那么可以采用三遍方法。我不确定在您的环境中这种方式是否高效，但是您可以使用厚度为
thickness - 2 的锯齿版本线条，然后使用Xiaolin Wu的方法两次进行抗锯齿处理。@Francisco P. 的方法也有效，并且可能更可取。总之，锯齿必须沿着外边缘平滑处理。如果您正在处理厚度大于1的线，请仅绘制两个边缘进行抗锯齿处理，然后填充中间部分即可。- Xenethyl
3
一种低效、粗糙、快速的方法是将线条放大（比如说4倍），然后使用权重平均缩小它们。具体细节请参考：位图字体缩小算法，查看被采纳的答案。
- F. P.
3
哈哈，谢谢，但我想我应该在我的问题中用“高效、合理优雅”代替“标准”这个词。 - rcv
1嗯，也许我低估了我的努力，但这是一个相当标准的方法来完成你所要求的。 - F. P.
我认为这归结于CPU和内存之间的权衡。进行多次遍历可能比缩小更具计算成本，但缩小可能需要更高分辨率的内存。除此之外，还有CPU处理来缩小行。最终，在桌面机上两种方法都可能表现相同，但如果我们谈论手机，这可能会有所不同。无论如何，我认为您的建议更加主流。 - Xenethyl
1
基于我的光栅化库的一个好而快速的解决方案，它使用了吴氏算法来处理细线（
该算法使用吴氏线算法绘制粗线的轮廓，然后通过将其分成两个三角形并使用快速算法填充每个三角形的内部来填充内部。
xmin,ymin,xmax,ymax是用于裁剪的视口边界）。该算法使用吴氏线算法绘制粗线的轮廓，然后通过将其分成两个三角形并使用快速算法填充每个三角形的内部来填充内部。
/*
given line's thickness w and dx,dy of line, wx, wy are computed as:
n = hypot(dx, dy)
w2 = (w-1)/2
wx = dy*w2/n
wy = dx*w2/n
*/
function wu_thick_line(set_pixel, xs, ys, xe, ye, dx, dy, wx, wy, xmin, ymin, xmax, ymax)
{
var t, sx, sy,
wsx, wsy,
xa, xb, xc, xd,
ya, yb, yc, yd;
if (xs > xe)
{
t = xs;
xs = xe;
xe = t;
t = ys;
ys = ye;
ye = t;
}
sx = 1;
sy = ys > ye ? -1 : 1;
if (is_strictly_equal(dx, 0))
{
return fill_rect(set_pixel, stdMath.round(xs - wx), stdMath.round(ys), stdMath.round(xs + wx), stdMath.round(ye), xmin, ymin, xmax, ymax);
}
if (is_strictly_equal(dy, 0))
{
return fill_rect(set_pixel, stdMath.round(xs), stdMath.round(ys - wy), stdMath.round(xe), stdMath.round(ys + wy), xmin, ymin, xmax, ymax);
}
/*
wx .b
+-----.(s) .
wy |.a | . . f
. | . .
dy |. . .
| .g . . d
| . .(e)
+----- .----
dx c
a: ys + wsy - ys = -(x - xs)/m => x = xs - m*wsy: (xs-wsx, ys+wsy)
b: ys - wsy - ys = -(x - xs)/m => x = xs + m*wsy: (xs+wsx, ys-wsy)
c: ye + wsy - ye = -(x - xe)/m => x = xe - m*wsy: (xe-wsx, ye+wsy)
d: ye - wsy - ye = -(x - xe)/m => x = xe + m*wsy: (xe+wsx, ye-wsy)
*/
wsx = sx*wx;
wsy = sy*wy;
xa = xs - wsx;
ya = ys + wsy;
xb = xs + wsx;
yb = ys - wsy;
xc = xe - wsx;
yc = ye + wsy;
xd = xe + wsx;
yd = ye - wsy;
// outline
wu_line(set_pixel, xa, ya, xb, yb, null, null, xmin, ymin, xmax, ymax);
wu_line(set_pixel, xb, yb, xd, yd, null, null, xmin, ymin, xmax, ymax);
wu_line(set_pixel, xd, yd, xc, yc, null, null, xmin, ymin, xmax, ymax);
wu_line(set_pixel, xc, yc, xa, ya, null, null, xmin, ymin, xmax, ymax);
// fill
fill_triangle(set_pixel, xa, ya, xb, yb, xc, yc, xmin, ymin, xmax, ymax);
fill_triangle(set_pixel, xb, yb, xc, yc, xd, yd, xmin, ymin, xmax, ymax);
}
function wu_line(set_pixel, xs, ys, xe, ye, dx, dy, xmin, ymin, xmax, ymax)
{
var xm = stdMath.min(xs, xe), xM = stdMath.max(xs, xe),
ym = stdMath.min(ys, ye), yM = stdMath.max(ys, ye);
// if line is outside viewport return
if (xM < xmin || xm > xmax || yM < ymin || ym > ymax) return;
if (null == dx)
{
dx = stdMath.abs(xe - xs);
dy = stdMath.abs(ye - ys);
}
// clip it to viewport if needed
if (xm < xmin || xM > xmax || ym < ymin || yM > ymax)
{
var clipped = clip(xs, ys, xe, ye, xmin, ymin, xmax, ymax);
if (!clipped) return;
xs = clipped[0];
ys = clipped[1];
xe = clipped[2];
ye = clipped[3];
}
if (is_strictly_equal(dx, 0) || is_strictly_equal(dy, 0))
{
return fill_rect(set_pixel, stdMath.round(xs), stdMath.round(ys), stdMath.round(xe), stdMath.round(ye));
}
// Wu's line algorithm
// https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm
var x, y,
x1, x2,
y1, y2,
xend, yend,
gradient = 0,
intersect = 0,
fpart = 0,
rfpart = 0,
gap = 0,
e = 0.5,
steep = dy > dx;
if (steep)
{
x = xs;
xs = ys;
ys = x;
x = xe;
xe = ye;
ye = x;
x = dx;
dx = dy;
dy = x;
}
if (xs > xe)
{
x = xs;
xs = xe;
xe = x;
y = ys;
ys = ye;
ye = y;
}
gradient = (ys > ye ? -1 : 1)*dy/dx;
// handle first endpoint
xend = stdMath.round(xs);
yend = ys + gradient * (xend - xs);
gap = 1 - (xs + e - stdMath.floor(xs + e));
x1 = xend;
y1 = stdMath.floor(yend);
fpart = yend - y1;
rfpart = 1 - fpart;
if (steep)
{
set_pixel(y1, x1, rfpart*gap);
set_pixel(y1 + 1, x1, fpart*gap);
}
else
{
set_pixel(x1, y1, rfpart*gap);
set_pixel(x1, y1 + 1, fpart*gap);
}
intersect = yend + gradient;
// handle second endpoint
xend = stdMath.round(xe);
yend = ye + gradient * (xend - xe);
gap = xe + e - stdMath.floor(xe + e);
x2 = xend;
y2 = stdMath.floor(yend);
fpart = yend - y2;
rfpart = 1 - fpart;
if (steep)
{
set_pixel(y2, x2, rfpart*gap);
set_pixel(y2 + 1, x2, fpart*gap);
}
else
{
set_pixel(x2, y2, rfpart*gap);
set_pixel(x2, y2 + 1, fpart*gap);
}
// main loop
if (steep)
{
for (x=x1+1; x<x2; ++x)
{
y = stdMath.floor(intersect);
fpart = intersect - y;
rfpart = 1 - fpart;
if (0 < rfpart) set_pixel(y, x, rfpart);
if (0 < fpart) set_pixel(y + 1, x, fpart);
intersect += gradient;
}
}
else
{
for (x=x1+1; x<x2; ++x)
{
y = stdMath.floor(intersect);
fpart = intersect - y;
rfpart = 1 - fpart;
if (0 < rfpart) set_pixel(x, y, rfpart);
if (0 < fpart) set_pixel(x, y + 1, fpart);
intersect += gradient;
}
}
}
function clip(x1, y1, x2, y2, xmin, ymin, xmax, ymax)
{
// clip points to viewport
// https://en.wikipedia.org/wiki/Liang%E2%80%93Barsky_algorithm
var p1 = -(x2 - x1),
p2 = -p1,
p3 = -(y2 - y1),
p4 = -p3,
q1 = x1 - xmin,
q2 = xmax - x1,
q3 = y1 - ymin,
q4 = ymax - y1,
rn2 = 1, rn1 = 0,
r1, r2, r3, r4;
if ((p1 === 0 && q1 < 0) || (p2 === 0 && q2 < 0) || (p3 === 0 && q3 < 0) || (p4 === 0 && q4 < 0))
{
// parallel to edge and outside of viewport
return;
}
if (p1 !== 0)
{
r1 = q1/p1;
r2 = q2/p2;
if (p1 < 0)
{
if (r1 > rn1) rn1 = r1;
if (r2 < rn2) rn2 = r2;
}
else
{
if (r2 > rn1) rn1 = r2;
if (r1 < rn2) rn2 = r1;
}
}
if (p3 !== 0)
{
r3 = q3/p3;
r4 = q4/p4;
if (p3 < 0)
{
if (r3 > rn1) rn1 = r3;
if (r4 < rn2) rn2 = r4;
}
else
{
if (r4 > rn1) rn1 = r4;
if (r3 < rn2) rn2 = r3;
}
}
// completely outside viewport
if (rn1 > rn2) return;
return [
x1 + p2*rn1, y1 + p4*rn1,
x1 + p2*rn2, y1 + p4*rn2
];
}
function fill_rect(set_pixel, x1, y1, x2, y2, xmin, ymin, xmax, ymax)
{
// fill a rectangular area between (x1,y1), (x2,y2) integer coords
var x, y;
if (x1 > x2)
{
x = x1;
x1 = x2;
x2 = x;
}
if (y1 > y2)
{
y = y1;
y1 = y2;
y2 = y;
}
if (null != xmin)
{
if (x2 < xmin || x1 > xmax || y2 < ymin || y1 > ymax) return;
x1 = stdMath.max(x1, xmin);
y1 = stdMath.max(y1, ymin);
x2 = stdMath.min(x2, xmax);
y2 = stdMath.min(y2, ymax);
}
if (y1 === y2)
{
for (x=x1; x<=x2; ++x) set_pixel(x, y1, 1);
}
else if (x1 === x2)
{
for (y=y1; y<=y2; ++y) set_pixel(x1, y, 1);
}
else
{
for (y=y1; y<=y2; ++y)
{
for (x=x1; x<=x2; ++x) set_pixel(x, y, 1);
}
}
}
function fill_triangle(set_pixel, ax, ay, bx, by, cx, cy, xmin, ymin, xmax, ymax)
{
// fill the triangle defined by a, b, c points
var x, xx, t,
y, yb, yc,
xac, xab, xbc,
yac, yab, ybc,
zab, zbc,
clip = null != xmin, e = 0.5;
if (clip)
{
if (stdMath.max(ax,bx,cx) < xmin || stdMath.min(ax,bx,cx) > xmax || stdMath.max(ay,by,cy) < ymin || stdMath.min(ay,by,cy) > ymax) return;
}
if (by < ay) {t = ay; ay = by; by = t; t = ax; ax = bx; bx = t;}
if (cy < ay) {t = ay; ay = cy; cy = t; t = ax; ax = cx; cx = t;}
if (cy < by) {t = by; by = cy; cy = t; t = bx; bx = cx; cx = t;}
yac = cy - ay;
if (is_strictly_equal(yac, 0))
{
// line or single point
y = stdMath.round(ay);
x = stdMath.round(stdMath.min(ax, bx, cx));
xx = stdMath.round(stdMath.max(ax, bx, cx));
return fill_rect(set_pixel, x, y, xx, y, xmin, ymin, xmax, ymax);
}
yab = by - ay;
ybc = cy - by;
xac = cx - ax;
xab = bx - ax;
xbc = cx - bx;
zab = is_strictly_equal(yab, 0);
zbc = is_strictly_equal(ybc, 0);
y = stdMath.round(ay + e);
yb = by;
yc = stdMath.round(cy - e);
if (clip) {y = stdMath.max(ymin, y); yc = stdMath.min(ymax, yc);}
for (; y<=yc; ++y)
{
if (y < yb)
{
if (zab)
{
x = ax;
xx = bx;
}
else
{
x = xac*(y - ay)/yac + ax;
xx = xab*(y - ay)/yab + ax;
}
}
else
{
if (zbc)
{
x = bx;
xx = cx;
}
else
{
x = xac*(y - ay)/yac + ax;
xx = xbc*(y - by)/ybc + bx;
}
}
if (stdMath.abs(xx - x) < 1)
{
if (!clip || (x >= xmin && x <= xmax)) set_pixel(stdMath.round(x), y, 1);
continue;
}
if (xx < x)
{
t = x;
x = xx;
xx = t;
}
x = stdMath.round(x + e);
xx = stdMath.round(xx - e);
if (clip) {x = stdMath.max(xmin, x); xx = stdMath.min(xmax, xx);}
for (; x<=xx; ++x) set_pixel(x, y, 1);
}
}
结果（画布线 vs 光栅化器线）：
- Nikos M.
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接