标签: bresenham

我需要一个快速算法来计算两点之间的直线坐标.我试图找到很好的JavaScript Bresenham实现,但有太多和相当混乱的出版物.在维基百科 - 这里最快和最简单的形式(两个方向没有划分和误差计算)以伪代码的形式呈现,如下所示:

 function line(x0, y0, x1, y1)
   dx := abs(x1-x0)
   dy := abs(y1-y0) 
   if x0 < x1 then sx := 1 else sx := -1
   if y0 < y1 then sy := 1 else sy := -1
   err := dx-dy

   loop
     setPixel(x0,y0)
     if x0 = x1 and y0 = y1 exit loop
     e2 := 2*err
     if e2 > -dy then 
       err := err - dy
       x0 := x0 + sx 
     if e2 <  dx then 
       err := …

根据我对A*启发式的理解以及Bresenham算法如何工作,这可能是不可能的,因为只有当前状态和目标状态被传递给启发式函数.但也许某人有一个聪明的解决方案来解决这个问题.

我正在使用A*来计划网格上的路径,并且我想要一种启发式方法,当当前状态和目标之间存在自由空间或绕过障碍物时,可以使最佳路径遵循Bresenham线.

这里有一些图像来说明问题.

曼哈顿距离:

如果世界上的运动像一个网格上的棋子一样,这将是完美的,但我最终会将A*路径转换为连续平面上的运动,所以这确实很有效.

欧几里德距离:

更好,但仍然不完美.注意最后的直线.对角线可以很容易地保持对角线,这就是我想要的.

我想要的是:

Bresenham线被吸引到下一个回合或目标.

我在这里找到了一个很好的资源,http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html触及了我正在寻找的东西,但似乎只能用于从开始到目标绘制Bresenham线.我想要的是Bresenham线也被绕到障碍物的下一个转弯.

有什么想法可以很好地解决这个问题吗？

我编写了Bresenham的圆绘制算法的实现.这种算法利用了圆的高度对称性(它只计算第一个八分圆的点,并利用对称性绘制其他点).因此我期待它非常快.图形编程黑皮书,第35章标题为" Bresenham快速,快速好 ",虽然它是关于线条绘制算法,但我可以合理地期望圆形绘制算法也很快(因为原理是相同).

这是我的java,swing实现

public static void drawBresenhamsCircle(int r, double width, double height, Graphics g) {
    int x,y,d;
    y = r;
    x = 0;

    drawPoint(x, y, width, height,g);
    d = (3-2*(int)r);
    while (x <= y) {
        if (d <= 0) {
            d = d + (4*x + 6);
        } else {
            d = d + 4*(x-y) + 10;
            y--;
        }
        x++;

        drawPoint(x, y, width, height,g);

        drawPoint(-x, y, width, height,g);
        drawPoint(x, -y, width, height,g);

        drawPoint(-x, -y, width, height,g);
        drawPoint(y, …

基于维基百科关于Bresenham线路算法的文章,我已经实现了那里描述的简化版本,我的Java实现看起来像这样:

int dx = Math.abs(x2 - x1);
int dy = Math.abs(y2 - y1);

int sx = (x1 < x2) ? 1 : -1;
int sy = (y1 < y2) ? 1 : -1;

int err = dx - dy;

while (true) {
    framebuffer.setPixel(x1, y1, Vec3.one);

    if (x1 == x2 && y1 == y2) {
        break;
    }

    int e2 = 2 * err;

    if (e2 > -dy) {
        err = err - dy;
        x1 = x1 + sx;
    } …

我正在寻找一种算法(用Java编码会很好,但是任何足够清晰的转换为Java都很好)来绘制一条4连接线.似乎Bresenham的算法是使用最广泛的算法,但我发现的所有可理解的实现都是8连接的.OpenCV的cvline函数显然有一个4连接版本,但对我来说,源代码是一个平庸而且几乎是C文盲的程序员,难以理解.其他各种搜索都没有发现.

感谢任何人都能提供的帮助.

我需要一种比Bresenham线绘制算法慢一点的算法,但必须更精确.使用'exact'我的意思是:应该打印每个触摸的像素.不多也不少!这意味着使用更粗的线或类似物不是一种选择,因为将涉及太多的像素.此外,我并不需要一个图形框架或类似就像是问 之前,我需要的算法!应用程序实际上不是"图形",它位于像素为"图块" 的地理区域.

对我来说主要的问题是我需要子像素精度,这意味着一条线可以从0.75/0.33开始,而不仅仅是0/0,就像整数值的情况一样.我尝试在过去几个小时内创建一个可行的解决方案,但无法使其正常工作 - 边缘情况太多了.

首先,我认为抗锯齿的版本就像从算法吴应,但它打印像素过多(尤其是起点和终点),并在某些情况下,还惦记着,例如在非常短的线条一些像素.

然后我试着让Bresenham在我用'else if'取代第二个'if'的地方工作,这里指出了它,但它更接近但仍然不存在.然后我尝试将Bresenham从整数移动到浮点精度,这导致无限循环(因为x,y值跳过完成条件if (y1 == y2 && x1 == x2)).

我可以使用天真的线条绘图解决方案,但delta我应该使用哪个？例如,如果我使用0.1,我仍然会错过一些像素并使用较小的值,它可能会花费太长时间(仍然会错过像素).

C/Java/...中的工作解决方案将不胜感激.至少它应该适用于八分之一,但一个完整的解决方案会更好.

更新:我提出了以下想法:使用朴素行光栅化,您可以为每个点计算4个像素候选.然后检查这4个像素,如果该线真正穿过它们.但我不确定线/盒交叉点是否足够快.

我的计算机图形作业是仅使用绘制点的能力来实现OpenGL算法.

所以显然我需要开始drawLine()工作才能画出其他东西. drawLine()必须仅使用整数来完成.没有浮点.

这就是我的教导.基本上,线可以分为4个不同的类别,正陡,正浅,负陡和负浅.这是我应该画的图片:

这是我的程序绘制的图片:

颜色是为我们完成的.我们给出了顶点,我们需要使用Bresenham的Line算法根据起点和终点绘制线条.

这是我到目前为止:

int dx = end.x - start.x;
int dy = end.y - start.y;

//initialize varibales
int d;
int dL;
int dU;

if (dy > 0){
        if (dy > dx){
                //+steep
                d = dy - 2*dx;
                dL = -2*dx;
                dU = 2*dy - 2*dx;

                for (int x = start.x, y = start.y; y <= end.y; y++){
                        Vertex v(x,y);
                        drawPoint(v);

                        if (d >= 1){
                                d += dL;
                        }else{
                                x++;
                                d += dU;
                        } …

我需要检查一行中的所有像素,所以我使用Bresenham的算法来访问其中的每个像素.特别是我需要检查所有像素是否都位于位图的有效像素上.这是代码:

private void Bresenham(Point p1, Point p2, ref List<Point> track) {
  int dx = p2.X - p1.X;
  int dy = p2.Y - p1.Y;

  int swaps = 0;
  if (dy > dx) {
    Swap(ref dx, ref dy);
    swaps = 1;
  }

  int a = Math.Abs(dy);
  int b = -Math.Abs(dx);

  double d = 2*a + b;
  int x = p1.X;
  int y = p1.Y;
  color_track = Color.Blue;
  Check_Pixel(ref area, new Point(x,y));
  track.Clear();
  track.Add(new Point(x, y));

  int s = 1;
  int q = …

我有一个视线问题我需要通过访问两个(非网格对齐)点之间的3D体素空间中的所有可能单元来解决.

我考虑过使用3D Bresenham算法,但它会跳过一些细胞.

一个天真的实现可能是以比体素网格更高的分辨率检查沿线的点,但我希望有一个更智能的解决方案.

有人有任何线索吗？

目前我正在使用 Bresenham 的圆形绘制算法，该算法可以很好地绘制圆形，但是我想要一种相对快速且有效的方法来绘制具有指定厚度的圆形（因为 Bresenham 的方法仅绘制单个像素厚度）。我意识到我可以简单地绘制多个具有不同半径的圆，但我相信这会非常低效（效率很重要，因为这将在 Arduino 上运行，其中每一微秒都很宝贵）。我目前正在使用以下代码：

void circle(byte xc, byte yc, int radius, Colour colour) {
  int x = -radius, y = 0, err = 2 - 2 * radius;
  while(x < 0) {
    setPixel(xc - x, yc + y, colour);
    setPixel(xc - y, yc - x, colour);
    setPixel(xc + x, yc - y, colour);
    setPixel(xc + y, yc + x, colour);
    radius = err;
    if(radius <= y) {
      err += ++y * 2 + 1;
    }
    if(radius > …