我如何将Bresenham的线algorithm推广到浮点端点?

我试图把两件事结合起来 我正在写一个游戏,我需要确定与浮点端点一致的网格。

线槽网格

此外,我需要它包括所有接触到的网格(即不只是Bresenham的线,而是蓝色的)。

Bresenham vs全面扫射

有人可以告诉我如何做到这一点? 显而易见的解决scheme是使用天真线路algorithm,但有什么更优化(更快)?

您正在寻找一个网格遍历algorithm。 本文给出了一个很好的实现;

这里是在纸上发现的2D的基本实现:

loop { if(tMaxX < tMaxY) { tMaxX= tMaxX + tDeltaX; X= X + stepX; } else { tMaxY= tMaxY + tDeltaY; Y= Y + stepY; } NextVoxel(X,Y); } 

纸上还有一个3D光线投射版本。

如果链接失败 ,你可以find许多镜像的名字: 一个更快的体素遍历algorithm的光线追踪

蓝色的想法是好的,但实施有点笨拙。 事实上,你可以很容易地做到这一点没有sqrt。 让我们暂时假设您排除了退化情况( BeginX==EndX || BeginY==EndY ),并且只关注第一象限中的行方向,所以BeginX < EndX && BeginY < EndY 。 您还必须为至less一个其他象限实施一个版本,但这与第一个象限的版本非常相似 – 只能检查其他边缘。 在C'ish伪代码中:

 int cx = floor(BeginX); // Begin/current cell coords int cy = floor(BeginY); int ex = floor(EndX); // End cell coords int ey = floor(EndY); // Delta or direction double dx = EndX-BeginX; double dy = EndY-BeginY; while (cx < ex && cy < ey) { // find intersection "time" in x dir float t0 = (ceil(BeginX)-BeginX)/dx; float t1 = (ceil(BeginY)-BeginY)/dy; visit_cell(cx, cy); if (t0 < t1) // cross x boundary first=? { ++cx; BeginX += t0*dx; BeginY += t0*dy; } else { ++cy; BeginX += t1*dx; BeginY += t1*dy; } } 

现在对于其他象限,只需更改++cx++cy和循环条件即可。 如果使用这种方式进行碰撞,则可能必须实现所有4个版本,否则可以通过适当地交换开始点和结束点来避免碰撞。

你的假设不一定是find单元格,而是它在这个网格上交叉的线条。

例如,考虑你的形象,我们可以突出显示不是单元格,而是突出显示它的网格线:

红线

这就表明,如果它穿过一条网格线,那么这条线的任何一边的单元格都是被填充的单元格。

您可以使用交点algorithm来查找您的浮点线是否会通过将点缩放到像素来跨越这些线。 如果浮点坐标:像素的比例为1.0:1,那么您已经sorting,您可以直接翻译它。 使用线段交点algorithm,可以检查左下角线(1,7)(2,7)是否与线(1.3,6.2)(6.51,2.9)相交。 http://alienryderflex.com/intersect/

一些从C到C#的翻译将是必要的,但你可以从那篇文章中得到这个想法。 我将把下面的代码放在链接中断的地方。

 // public domain function by Darel Rex Finley, 2006 // Determines the intersection point of the line defined by points A and B with the // line defined by points C and D. // // Returns YES if the intersection point was found, and stores that point in X,Y. // Returns NO if there is no determinable intersection point, in which case X,Y will // be unmodified. bool lineIntersection( double Ax, double Ay, double Bx, double By, double Cx, double Cy, double Dx, double Dy, double *X, double *Y) { double distAB, theCos, theSin, newX, ABpos ; // Fail if either line is undefined. if (Ax==Bx && Ay==By || Cx==Dx && Cy==Dy) return NO; // (1) Translate the system so that point A is on the origin. Bx-=Ax; By-=Ay; Cx-=Ax; Cy-=Ay; Dx-=Ax; Dy-=Ay; // Discover the length of segment AB. distAB=sqrt(Bx*Bx+By*By); // (2) Rotate the system so that point B is on the positive X axis. theCos=Bx/distAB; theSin=By/distAB; newX=Cx*theCos+Cy*theSin; Cy =Cy*theCos-Cx*theSin; Cx=newX; newX=Dx*theCos+Dy*theSin; Dy =Dy*theCos-Dx*theSin; Dx=newX; // Fail if the lines are parallel. if (Cy==Dy) return NO; // (3) Discover the position of the intersection point along line AB. ABpos=Dx+(Cx-Dx)*Dy/(Dy-Cy); // (4) Apply the discovered position to line AB in the original coordinate system. *X=Ax+ABpos*theCos; *Y=Ay+ABpos*theSin; // Success. return YES; } 

如果只需要找出线段相交的地方(和地点),则可以按如下方式修改该function:

 // public domain function by Darel Rex Finley, 2006 // Determines the intersection point of the line segment defined by points A and B // with the line segment defined by points C and D. // // Returns YES if the intersection point was found, and stores that point in X,Y. // Returns NO if there is no determinable intersection point, in which case X,Y will // be unmodified. bool lineSegmentIntersection( double Ax, double Ay, double Bx, double By, double Cx, double Cy, double Dx, double Dy, double *X, double *Y) { double distAB, theCos, theSin, newX, ABpos ; // Fail if either line segment is zero-length. if (Ax==Bx && Ay==By || Cx==Dx && Cy==Dy) return NO; // Fail if the segments share an end-point. if (Ax==Cx && Ay==Cy || Bx==Cx && By==Cy || Ax==Dx && Ay==Dy || Bx==Dx && By==Dy) { return NO; } // (1) Translate the system so that point A is on the origin. Bx-=Ax; By-=Ay; Cx-=Ax; Cy-=Ay; Dx-=Ax; Dy-=Ay; // Discover the length of segment AB. distAB=sqrt(Bx*Bx+By*By); // (2) Rotate the system so that point B is on the positive X axis. theCos=Bx/distAB; theSin=By/distAB; newX=Cx*theCos+Cy*theSin; Cy =Cy*theCos-Cx*theSin; Cx=newX; newX=Dx*theCos+Dy*theSin; Dy =Dy*theCos-Dx*theSin; Dx=newX; // Fail if segment CD doesn't cross line AB. if (Cy<0. && Dy<0. || Cy>=0. && Dy>=0.) return NO; // (3) Discover the position of the intersection point along line AB. ABpos=Dx+(Cx-Dx)*Dy/(Dy-Cy); // Fail if segment CD crosses line AB outside of segment AB. if (ABpos<0. || ABpos>distAB) return NO; // (4) Apply the discovered position to line AB in the original coordinate system. *X=Ax+ABpos*theCos; *Y=Ay+ABpos*theSin; // Success. return YES; } 
 float difX = end.x - start.x; float difY = end.y - start.y; float dist = abs(difX) + abs(difY); float dx = difX / dist; float dy = difY / dist; for (int i = 0, int x, int y; i <= ceil(dist); i++) { x = floor(start.x + dx * i); y = floor(start.y + dy * i); draw(x,y); } return true; 

JS演示:

Imgur

 //C# stackoverflow function verifyLoS(start, end) { var difX = end.x - start.x; var difY = end.y - start.y; var dist = Math.abs(difX) + Math.abs(difY); var dx = difX / dist; var dy = difY / dist; for (var i = 0, x, y; i <= Math.ceil(dist); i++) { x = Math.floor(start.x + dx * i); y = Math.floor(start.y + dy * i); draw(x,y); } return true; } var HEIGHT = 14, WIDTH = 14, PX = 32; var canvas, ctx; function main () { canvas = document.getElementById("canvas"); ctx = canvas.getContext("2d"); canvas.height = HEIGHT * PX; canvas.width = WIDTH * PX; loop(); } function loop() { for (var x=0;x<HEIGHT; x++) { for (var y=0; y<WIDTH; y++) { ctx.fillStyle = ((x+y)%2===0)?"#AFA":"#AEA"; ctx.fillRect(x*PX,y*PX,PX,PX); } } var a = {x:1.5, y:9.5}, b = {x:12.5, y:1.5}; verifyLoS(a, b); ctx.beginPath(); ctx.moveTo(ax*PX,ay*PX); ctx.lineTo(bx*PX,by*PX); ctx.stroke(); //window.requestAnimationFrame(loop); } function draw(x, y) { ctx.fillStyle = "rgba(255,0,0,0.2)"; ctx.fillRect(x*PX,y*PX,PX,PX); } main(); 
 <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title>JS Bin</title> </head> <body> <canvas id="canvas"></canvas> </body> </html> 

我今天遇到了同样的问题,从一个痣山上做了一个相当大的意大利面山,但最终得到了一些工作: https : //github.com/SnpM/Pan-Line-Algorithm 。

从自述:

该algorithm的核心概念与Bresenham的相似之处在于,它在一个轴上增加1个单位,并testing另一个轴上的增加。 然而,分数增加困难得多,而且必须添加大量比萨。例如,从X = 0.21递增到X = 1.21,斜率为5,这使得一个复杂的问题(这些讨厌的数字之间的坐标模式很难预测),但是从1增加到2,斜率为5,这是一个容易的问题。 整数之间的坐标模式很容易解决(只是垂直于递增轴的线)。 为了解决这个简单的问题,增量被偏移到一个整数,所有的计算都是单独完成的。 因此,不是在.21上开始递增,而是从1开始递增。

自述文件比代码更好地解释了解决scheme。 我打算修改它,以减less头痛的诱因。

我知道这个问题迟了大约一年,但是我希望这会得到其他人正在寻找解决这个问题的方法。