2

I need something like Bresenham algorithm but not quite and for 3d grid-space.

I got 3d grid of cells (edge size 1.0) need to start in point S and advance to point K 'touching' all the cells the line touches (even if only edge point is touched I need to touch all 8 cells).

Need to use it for traversal writing values to the cells or reading values from the cells and need it to be as fast as manageable (it would be in massive use of drawing millions of such 3d grid lines per frame).

Could somebody say how it could look like?

1201ProgramAlarm
  • 32,384
  • 7
  • 42
  • 56
user2214913
  • 1,441
  • 2
  • 19
  • 29
  • nothing comes to my mind, I could use dirty methot of iterating by small step but it would be slow and can skip some cells – user2214913 Jul 29 '14 at 13:35
  • possible duplicate of [Walk a line between two points in a 3D voxel space visiting all cells](http://stackoverflow.com/questions/16505905/walk-a-line-between-two-points-in-a-3d-voxel-space-visiting-all-cells) – Drew McGowen Jul 29 '14 at 13:36
  • youre right that would be on the topic.. tnx.. Though if someone would like to ad yet some soulution feel free to ad it here as those codes mentioned looks strangely complicated, nothing a bit simpler? – user2214913 Jul 29 '14 at 13:41
  • 1
    3D Bresenham isn't exactly a simple algorithm... – Drew McGowen Jul 29 '14 at 13:41
  • (wanted to upvote your link (as that was usefull too) but undone accidentaly and cannot so upvote here), regz – user2214913 Jul 29 '14 at 15:12

1 Answers1

2

Consider using of Woo and Amanatides grid traversal algorithm: article "Fast Voxel Traversal Algorithm..."

Practical implementation is in grid traversal section here

2d-case illustration:

enter image description here

MBo
  • 77,366
  • 5
  • 53
  • 86
  • Related answer, uses same paper: https://gamedev.stackexchange.com/a/81332/63053 – Andrew May 01 '20 at 06:46
  • what does the red and blue color mean? – Franva Apr 21 '23 at 13:02
  • 1
    @Franva Blue for cells having one touch point with line (or edge touching for vertical/horizontal lines), not intersection. Some applications require counting such cells, others - not – MBo Apr 21 '23 at 13:14