Comment généraliser l'algorithme de ligne de Bresenham aux points de terminaison à virgule flottante?

J'essaie de combiner deux choses. J'écris un jeu et je dois déterminer les carrés de la grille se trouvant sur une ligne avec les points d'extrémité à virgule flottante.

De plus, j'en ai besoin pour inclure tous les carrés de la grille qu'il touche (c'est-à-dire pas seulement la ligne de Bresenham mais la bleue):

Quelqu'un peut-il me donner une idée de la façon de procéder? La solution évidente consiste à utiliser un algorithme de ligne naïf, mais existe-t-il quelque chose de plus optimisé (plus rapide)?

Vous recherchez un algorithme de traversée de grille. Ce document donne une bonne mise en œuvre;

Voici l'implémentation de base en 2D trouvée sur le papier:

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

Il existe également une version de lancer de rayons 3D sur le papier.

Dans le cas où le lien pourrit , vous pouvez trouver de nombreux miroirs avec son nom: Un algorithme de traversée de voxels plus rapide pour le raytracing .

L'idée de Blue est bonne, mais la mise en œuvre est un peu maladroite. En fait, vous pouvez facilement le faire sans sqrt. Supposons pour le moment que vous excluez les cas dégénérés ( BeginX==EndX || BeginY==EndY) et que vous vous concentrez uniquement sur les directions de ligne dans le premier quadrant BeginX < EndX && BeginY < EndY. Vous devrez également implémenter une version pour au moins un autre quadrant, mais c'est très similaire à la version pour le premier quadrant - vous ne vérifiez que les autres bords. En pseudo code 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;
  }
}

Maintenant , pour les autres quarts de cercle, vous changez juste le ++cxou ++cyet la condition de la boucle. Si vous l'utilisez pour la collision, vous devrez probablement implémenter les 4 versions, sinon vous pouvez vous en tirer avec deux en échangeant de manière appropriée les points de début et de fin.

Votre hypothèse n'est pas nécessairement de trouver les cellules mais les lignes qu'elle traverse sur cette grille.

Par exemple en prenant votre image on peut mettre en évidence non pas les cellules, mais les lignes de la grille qu'elle traverse:

Cela montre alors que s'il traverse une ligne de grille, les cellules de chaque côté de cette ligne sont celles qui sont remplies.

Vous pouvez utiliser un algorithme d'intersection pour déterminer si votre ligne à virgule flottante les traversera en mettant à l'échelle vos points en pixels. Si vous avez un rapport 1,0: 1 de coordonnées flottantes: pixels, vous êtes trié et vous pouvez simplement le traduire directement. En utilisant l'algorithme d'intersection de segment de ligne, vous pouvez vérifier si votre ligne inférieure gauche (1,7) (2,7) croise votre ligne (1.3,6.2) (6.51,2.9). http://alienryderflex.com/intersect/

Une traduction de c en C # sera nécessaire, mais vous pouvez vous en inspirer. Je mettrai le code ci-dessous au cas où le lien se romprait.

//  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 A-B.
  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 A-B.
  ABpos=Dx+(Cx-Dx)*Dy/(Dy-Cy);

  //  (4) Apply the discovered position to line A-B in the original coordinate system.
  *X=Ax+ABpos*theCos;
  *Y=Ay+ABpos*theSin;

  //  Success.
  return YES; }

Si vous devez savoir uniquement quand (et où) les segments de ligne se croisent, vous pouvez modifier la fonction comme suit:

//  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 A-B.
  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 C-D doesn't cross line A-B.
  if (Cy<0. && Dy<0. || Cy>=0. && Dy>=0.) return NO;

  //  (3) Discover the position of the intersection point along line A-B.
  ABpos=Dx+(Cx-Dx)*Dy/(Dy-Cy);

  //  Fail if segment C-D crosses line A-B outside of segment A-B.
  if (ABpos<0. || ABpos>distAB) return NO;

  //  (4) Apply the discovered position to line A-B 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;

Démo JS:

//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(a.x*PX,a.y*PX);
  ctx.lineTo(b.x*PX,b.y*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>

J'ai rencontré le même problème aujourd'hui et j'ai fait une assez grande montagne de spaghettis à partir d'une colline de taupes, mais j'ai fini avec quelque chose qui fonctionne: https://github.com/SnpM/Pan-Line-Algorithm .

Du ReadMe:

Le concept de base de cet algorithme est similaire à celui de Bresenham en ce qu'il incrémente d'une unité sur un axe et teste l'augmentation sur l'autre axe. Les fractions rendent l'incrémentation beaucoup plus difficile, cependant, et beaucoup de pizzas ont dû être ajoutées. Par exemple, l'incrémentation de X = .21 à X = 1.21 avec une pente de 5 rend le problème complexe (modèles de coordonnées entre ces nombres désagréables sont difficiles à prévoir) mais incrémenter de 1 à 2 avec une pente de 5 rend le problème facile. Le modèle de coordonnées entre les nombres entiers est très facile à résoudre (juste une ligne perpendiculaire à l'axe d'incrémentation). Pour obtenir le problème facile, l'incrémentation est décalée en un nombre entier avec tous les calculs effectués séparément pour la pièce fractionnée. Donc, au lieu de commencer l'incrémentation sur .21,

Le ReadMe explique la solution bien mieux que le code. Je prévois de le réviser pour qu'il induise moins de maux de tête.

Je sais que j'ai un an de retard sur cette question, mais j'espère que cela parviendra à ceux qui recherchent une solution à ce problème.