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


12

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

Siatka koryta linii

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

Bresenham vs full sweep

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)?


W przypadku gdy link przejdzie w tryb offline, po prostu wyszukaj w Google „Szybszy algorytm przejścia wokseli dla raytracingu”
Gustavo Maciel

Odpowiedzi:


9

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 .


Cóż, niezręcznie. Chyba przerzucę odpowiedź na ciebie i głosuję na ltjax. Ponieważ rozwiązałem na podstawie twojego linku do tego artykułu.
SmartK8,

5

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.


Podany algorytm Gustavo Maciel jest nieco bardziej wydajny. Określa tylko pierwsze Ts, a następnie dodaje 1 do pionu lub poziomu i przesuwa Ts o wielkość komórki. Ale ponieważ nie przekonwertował go na odpowiedź, zaakceptuję tę odpowiedź jako najbliższą.
SmartK8

3

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:

Czerwone linie

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

Cześć, przejście przez siatkę jest właśnie w celu optymalizacji tysięcy przecięć linii na całej siatce. Nie można tego rozwiązać za pomocą tysięcy przecięć linii. Mam w grze mapę z liniami naziemnymi, których gracz nie może przekroczyć. Mogą być ich tysiące. Muszę ustalić, dla którego obliczyć drogie skrzyżowanie. Aby je ustalić, chcę tylko obliczyć przecięcia tych w linii ruchu gracza (lub światła ze źródła światła). W twoim przypadku musiałbym określić skrzyżowania z ~ 256x256x2 segmentami linii w każdej rundzie. To wcale nie byłoby zoptymalizowane.
SmartK8,

Ale nadal dziękuję za odpowiedź. Technicznie działa i jest poprawny. Ale dla mnie nie jest to wykonalne.
SmartK8,

3
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:

Imgur


1
Nie udało mi się to z powodu błędów liczb zmiennoprzecinkowych (pętla wykona dodatkową iterację dla najmniejszej części ułamka następnej liczby całkowitej, która wypchnie punkt końcowy linii poza położenie „końcowe”). Prostym rozwiązaniem jest obliczenie dist jako pułapu, więc dx, dy są podzielone przez liczbę całkowitą iteracji pętli (oznacza to, że możesz stracić pułap (dist) w pętli for).
PeteB,

0

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.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.