2

我正在寻找一种快速算法来绘制轮廓线。对于这个应用程序，轮廓只需要 1 个像素宽。无论是默认情况下还是通过选项，都应该可以使两条线无缝连接在一起，如果它们共享一个公共点。

请原谅 ASCII 艺术，但这可能是展示它的最佳方式。

正常线：

 ##
   ##
     ##
       ##
         ##
           ##

“概述”行：

 **
*##**
 **##**
   **##**
     **##**
       **##**
         **##*
           **

我正在研究 dsPIC33FJ128GP802。它是一个小型微控制器/数字信号处理器，能够处理 40 MIPS（每秒百万条指令）。它只能进行整数数学运算（加法、减法和乘法：它可以进行除法，但需要大约 19 个周期。）它正在被使用同时处理一个 OSD 层，只有 3-4 MIPS 的处理时间可用于计算，因此速度至关重要。像素占据三种状态：黑色、白色和透明；视频场为 192x128 像素。这是针对 Super OSD，一个开源项目：http ://code.google.com/p/super-osd/

我想到的第一个解决方案是在第一遍绘制带有轮廓像素的 3x3 矩形，在第二遍绘制普通像素，但这可能会很慢，因为每个像素至少有 3 个像素被覆盖，并且浪费了绘制它们的时间. 所以我正在寻找一种更快的方法。每个像素大约需要 30 个周期。目标是 <50, 000 个周期来绘制一条 100 像素长度的线。

4

2 回答 2

1

我建议这个（C/伪代码混合）：

void draw_outline(int x1, int y1, int x2, int y2)
{
    int x, y;
    double slope;

    if (abs(x2-x1) >= abs(y2-y1)) {
        // line closer to horizontal than vertical
        if (x2 < x1) swap_points(1, 2);
        // now x1 <= x2
        slope = 1.0*(y2-y1)/(x2-x1);
        draw_pixel(x1-1, y1, '*');
        for (x = x1; x <= x2; x++) {
            y = y1 + round(slope*(x-x1));
            draw_pixel(x, y-1, '*');
            draw_pixel(x, y+1, '*');
            // here draw_line() does draw_pixel(x, y, '#');
        }
        draw_pixel(x2+1, y2, '*');
    }
    else {
        // same as above, but swap x and y
    }
}

编辑：如果你想让连续的线无缝连接，我认为你真的必须在第一遍画出所有的轮廓，然后画线。我编辑了上面的代码以仅绘制轮廓。该 draw_line()功能将完全相同，但只有一个 draw_pixel(x, y, '#');而不是四个draw_pixel(..., ..., '*');。然后你就：

void draw_polyline(point p[], int n)
{
    int i;

    for (i = 0; i < n-1; i++)
        draw_outline(p[i].x, p[i].y, p[i+1].x, p[i+1].y);
    for (i = 0; i < n-1; i++)
        draw_line(p[i].x, p[i].y, p[i+1].x, p[i+1].y);
}
于 2010-10-12T20:23:38.323 回答
0

我的方法是使用 Bresenham 绘制多条线。查看您的 ASCII 艺术作品，您会注意到轮廓线与 Bresenham 线相同，只是上下移动了 1 个像素——加上第一个点左侧和最后一个点右侧的单个像素.

对于通用版本，您需要确定您的线是平坦的还是陡峭的 - 即是否abs(y1 - y0) <= abs(x1 - x0). 对于陡峭的线条，轮廓向左和向右移动 1 个像素，闭合像素位于起点上方和终点下方。

通过为每个线条像素一次绘制线条和两个轮廓像素来优化这一点可能是值得的。但是，如果您需要无缝轮廓，最简单的解决方案是首先绘制所有轮廓，然后绘制线条本身——这不适用于“三像素 Bresenham”优化。

于 2015-03-01T13:31:53.543 回答