Bagaimana cara menggeneralisasi algoritma garis Bresenham ke titik akhir floating-point?

12

Saya mencoba menggabungkan dua hal. Saya sedang menulis permainan dan saya perlu menentukan kotak kisi yang terletak pada garis dengan titik akhir floating-point.

Garis melalui kotak

Selain itu saya membutuhkannya untuk memasukkan semua kotak kotak yang disentuhnya (yaitu bukan hanya garis Bresenham tetapi yang biru):

Bresenham vs sapuan penuh

Adakah yang bisa memberi saya wawasan tentang cara melakukannya? Solusi yang jelas adalah dengan menggunakan algoritma garis naif, tetapi apakah ada sesuatu yang lebih dioptimalkan (lebih cepat)?

SmartK8
sumber
Jika tautannya offline, cukup google untuk "Algoritma traversal voxel yang lebih cepat untuk raytracing"
Gustavo Maciel

Jawaban:

9

Anda mencari algoritme lintasan traversal. Makalah ini memberikan implementasi yang baik;

Inilah implementasi dasar dalam 2D ​​yang ditemukan di kertas:

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

Ada juga versi ray-casting 3D di atas kertas.

Jika tautannya membusuk , Anda dapat menemukan banyak mirror dengan namanya: Algoritma traversal voxel yang lebih cepat untuk raytracing .

Gustavo Maciel
sumber
Yah, aneh. Saya kira, saya akan mengalihkan jawaban untuk Anda dan memilih ltjax. Karena saya menyelesaikannya berdasarkan tautan Anda ke makalah itu.
SmartK8
5

Ide Blue bagus, tetapi implementasinya agak canggung. Bahkan, Anda dapat dengan mudah melakukannya tanpa sqrt. Mari kita asumsikan untuk saat ini bahwa Anda mengecualikan kasus degenerasi ( BeginX==EndX || BeginY==EndY) dan fokus hanya pada arah garis di kuadran pertama, jadi BeginX < EndX && BeginY < EndY. Anda harus mengimplementasikan versi untuk setidaknya satu kuadran lain juga, tetapi itu sangat mirip dengan versi untuk kuadran pertama - Anda hanya memeriksa tepi lainnya. Dalam kode semu 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;
  }
}

Sekarang untuk kuadran lain, Anda cukup mengubah ++cxatau ++cydan kondisi loop. Jika Anda menggunakan ini untuk tabrakan, Anda mungkin harus menerapkan semua 4 versi, jika tidak, Anda bisa mendapatkan dua versi dengan menukar titik awal dan titik akhir dengan tepat.

ltjax
sumber
Algoritma yang disediakan Gustavo Maciel sedikit lebih efisien. Ini hanya menentukan Ts pertama dan kemudian hanya menambahkan 1 ke vertikal atau horizontal dan menggeser Ts dengan ukuran sel. Tetapi karena dia tidak mengubahnya menjadi jawaban, saya akan menerima jawaban ini sebagai jawaban terdekat.
SmartK8
3

Asumsi Anda tidak harus menemukan sel tetapi garis-garis yang dilintasi pada kotak ini.

Misalnya mengambil gambar Anda, kami tidak dapat menyorot sel, tetapi garis-garis kisi yang dilintasi:

RedLines

Ini kemudian menunjukkan bahwa jika melintasi garis kisi, sel-sel di kedua sisi garis ini adalah sel-sel yang terisi.

Anda dapat menggunakan algoritma persimpangan untuk menemukan apakah garis titik apung Anda akan melewatinya dengan menskalakan poin Anda ke piksel. Jika Anda memiliki rasio koordinat mengambang: piksel 1,0: 1 maka Anda disortir dan Anda bisa langsung menerjemahkannya. Dengan menggunakan algoritma persimpangan segmen garis, Anda dapat memeriksa apakah garis kiri bawah Anda (1,7) (2,7) berpotongan dengan garis Anda (1.3,6.2) (6.51,2.9). http://alienryderflex.com/intersect/

Beberapa terjemahan dari c ke C # akan dibutuhkan tetapi Anda bisa mendapatkan ide dari makalah itu. Saya akan meletakkan kode di bawah jika tautannya terputus.

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

Jika Anda hanya perlu mengetahui kapan (dan di mana) segmen garis berpotongan, Anda dapat memodifikasi fungsi sebagai berikut:

//  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; }
Piddock Tom 'Biru'
sumber
Hai, traversal grid tepat untuk tujuan mengoptimalkan ribuan persimpangan garis di seluruh grid. Ini tidak dapat dipecahkan oleh ribuan persimpangan garis. Saya memiliki peta dalam game dengan garis tanah yang tidak dapat dilewati pemain. Mungkin ada ribuan ini. Saya perlu menentukan yang mana untuk menghitung persimpangan mahal. Untuk menentukan ini, saya hanya ingin menghitung persimpangan dari mereka dalam garis pergerakan pemain (atau cahaya dari sumber cahaya). Dalam kasus Anda, saya perlu menentukan persimpangan dengan segmen garis ~ 256x256x2 setiap putaran. Itu tidak akan dioptimalkan sama sekali.
SmartK8
Namun tetap terima kasih atas jawaban Anda. Secara teknis itu berfungsi dan benar. Tapi tidak layak untuk saya.
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;

Demo JS:

Imgur

A-312
sumber
1
Ini gagal bagi saya karena kesalahan numerik floating point (loop akan melakukan iterasi tambahan untuk fraksi paling kecil atas integer berikutnya yang akan mendorong titik akhir garis di luar lokasi 'akhir'). Perbaikan sederhana adalah dengan menghitung dist sebagai ceil di tempat pertama jadi dx, dy dibagi dengan jumlah integer dari iterasi dari loop (ini berarti Anda dapat kehilangan ceil (dist) di for loop).
PeteB
0

Saya mengalami masalah yang sama hari ini dan membuat gunung spageti yang cukup besar keluar dari bukit mol tetapi berakhir dengan sesuatu yang berfungsi: https://github.com/SnpM/Pan-Line-Algorithm .

Dari ReadMe:

Konsep inti dari algoritma ini mirip dengan Bresenham dalam hal itu bertambah 1 unit pada satu sumbu dan menguji peningkatan pada sumbu lainnya. Pecahan membuat penambahan jauh lebih sulit, namun, dan banyak pizza harus ditambahkan. Sebagai contoh, penambahan dari X = .21 ke X = 1.21 dengan kemiringan 5 membuat masalah yang kompleks (pola koordinat antara angka-angka jahat itu). sulit diprediksi) tetapi peningkatan dari 1 ke 2 dengan kemiringan 5 membuat masalah mudah. Pola koordinat antara bilangan bulat sangat mudah dipecahkan (hanya garis yang tegak lurus terhadap sumbu yang bertambah). Untuk mendapatkan masalah yang mudah, incrementing diimbangi ke angka integer dengan semua perhitungan dilakukan secara terpisah untuk bagian pecahan. Jadi alih-alih memulai kenaikan pada .21,

ReadMe menjelaskan solusinya jauh lebih baik daripada kode. Saya berencana merevisinya menjadi lebih sedikit sakit kepala.

Saya tahu saya terlambat sekitar satu tahun untuk pertanyaan ini, tetapi saya berharap ini dapat diterima oleh orang lain yang mencari solusi untuk masalah ini.

JPtheK9
sumber