Jak uogólnić algorytm liniowy Bresenhama na zmiennoprzecinkowe punkty końcowe?

Próbuję połączyć dwie rzeczy. Piszę grę i muszę określić kwadraty siatki leżące na linii z zmiennoprzecinkowymi punktami końcowymi.

Ponadto muszę uwzględnić wszystkie kwadraty siatki, których dotyka (tj. Nie tylko linię Bresenhama, ale niebieską):

Czy ktoś może zaoferować mi jakiś wgląd w to, jak to zrobić? Oczywistym rozwiązaniem jest użycie naiwnego algorytmu linii, ale czy istnieje coś bardziej zoptymalizowanego (szybszego)?

Szukasz algorytmu przechodzenia przez siatkę. Ten dokument daje dobre wdrożenie;

Oto podstawowa implementacja w 2D znaleziona na papierze:

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

Na papierze dostępna jest również wersja do rzucania promieni 3D.

W przypadku zepsucia łącza można znaleźć wiele kopii lustrzanych o jego nazwie: Szybszy algorytm przechodzenia wokseli do raytracingu .

Pomysł Blue jest dobry, ale implementacja jest nieco niezdarna. W rzeczywistości możesz to łatwo zrobić bez sqrt. Załóżmy na chwilę, że wykluczysz przypadki zdegenerowane ( BeginX==EndX || BeginY==EndY) i skupimy się tylko na kierunkach linii w pierwszej ćwiartce, więc BeginX < EndX && BeginY < EndY. Będziesz musiał zaimplementować wersję dla co najmniej jeszcze jednej ćwiartki, ale jest to bardzo podobne do wersji dla pierwszej ćwiartki - sprawdzasz tylko inne krawędzie. W pseudokodzie 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;
  }
}

Teraz w przypadku innych ćwiartek wystarczy zmienić warunek pętli ++cxlub ++cy. Jeśli użyjesz tego do kolizji, prawdopodobnie będziesz musiał zaimplementować wszystkie 4 wersje, w przeciwnym razie możesz uniknąć dwóch, odpowiednio zamieniając punkty początkowy i końcowy.

Twoim założeniem niekoniecznie jest znalezienie komórek, ale linie, które przecinają na tej siatce.

Na przykład robiąc zdjęcie nie możemy wyróżnić komórek, ale linie przecinającej się siatki:

To pokazuje, że jeśli przecina linię siatki, komórki po obu stronach tej linii są wypełnione.

Możesz użyć algorytmu przecięcia, aby sprawdzić, czy linia zmiennoprzecinkowa przecina je, skalując punkty do pikseli. Jeśli masz współczynnik pływających współrzędnych: pikseli wynoszący 1,0: 1, to jesteś posortowany i możesz po prostu przetłumaczyć go bezpośrednio. Za pomocą algorytmu przecięcia segmentu linii możesz sprawdzić, czy twoja lewa dolna linia (1,7) (2,7) przecina się z twoją linią (1.3,6.2) (6.51,2.9). http://alienryderflex.com/intersect/

Konieczne będzie tłumaczenie z c na C #, ale pomysł można uzyskać z tego artykułu. Wstawię poniższy kod na wypadek, gdyby link się zepsuł.

//  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; }

Jeśli chcesz dowiedzieć się tylko, kiedy (i gdzie) przecinają się segmenty linii, możesz zmodyfikować funkcję w następujący sposób:

//  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;

JS Demo:

//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>

Zetknąłem się dzisiaj z tym samym problemem i zrobiłem całkiem dużą górę spaghetti z kretowiska, ale skończyło się na czymś, co działa: https://github.com/SnpM/Pan-Line-Algorytm .

Z ReadMe:

Podstawowa koncepcja tego algorytmu jest podobna do Bresenhama, ponieważ zwiększa się o 1 jednostkę na jednej osi i testuje wzrost na drugiej osi. Ułamki znacznie utrudniają inkrementację i trzeba było dodać dużo pizzy. Na przykład inkrementacja od X = 0,21 do X = 1,21 z nachyleniem 5 stanowi złożony problem (wzory współrzędnych między tymi paskudnymi liczbami są trudne do przewidzenia), ale zwiększanie wartości z 1 do 2 przy nachyleniu 5 stanowi łatwy problem. Wzorzec współrzędnych między liczbami całkowitymi jest bardzo łatwy do rozwiązania (tylko linia prostopadła do osi przyrostu). Aby uzyskać prosty problem, inkrementacja jest przesunięta na liczbę całkowitą, a wszystkie obliczenia są wykonywane osobno dla części ułamkowej. Zamiast więc zwiększać wartość .21,

ReadMe wyjaśnia rozwiązanie znacznie lepiej niż kod. Planuję wprowadzić zmiany, aby nie powodowały bólu głowy.

Wiem, że spóźniłem się o rok z tym pytaniem, ale mam nadzieję, że dotrze to do innych, którzy szukają rozwiązania tego problemu.