Original Post
I've been working with optimizing a ray traversal over a 2D terrain grid to remove unneeded float-to-int and vector-to-int conversions during the ray walk. I've been attempting to implement iterative, integer only based methods, like Bresenham, but am finding that the resolution of the actual integer-only methods (bresenham, cohen) still is not as accurate as the floating point walk methods that require a float-to-int conversion to access the grid mesh. Proper grid cell intersection is absolutely critical for the integer methods. At the most inner loop, when a ray intersects a cell, it must then do two triangle checks to test for collision. Since this is the case, if the cell walk is off by even a single cell, the entire raycast will fail due to the ray not colliding with any of the polygons. So, here's what I've found: Bresenham's algorithm just falls flat on it's face when compared to the float iteration. To even get close to accuracy, 2 additional ray-cell intersection tests must occur for every dominant axis change, and even then, the accuracy is poor (~66% accurate). This effectively turns the algorithm into a 2x2 line drawing algorithm, which also increases the number of tiles checked for intersection. Cohen's algorithm (Graphics Gems 3) is much more accurate when you add the additional domain-shift intersections (ie shifting from X dominant iteration to Z Dominant iteration). But even then, we're still looking at around 95% - 100% accuracy, which unfortunately, is still not 100% all the time. Is there some other algorithm I'm missing here? It would seem with all these years of ray tracing that we would have a suitable solution to an integer only grid traversal that reaches accuracy of a float one.. Or at least one that minimizes float to int conversions in some clever manner.. ~Main == Colt "MainRoach" McAnlis mainroach.blogspot.com