Sign in to follow this  
duhroach

Integer only ray-grid traversal accuracy

Recommended Posts

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

Share this post


Link to post
Share on other sites
Interesting.

Effectively, what you're suggesting is an extension of Woo's A Fast Voxel Traversal Algorithm for Ray Tracing but expanding it to 3 lines rather than 1.

I like what you're suggesting about only having FTOI conversions for the endpoints in a row, and then interpolating in the row. One caveat though is that in any lines that have many x/z domain shifts, the 'per row' savings of FTOI is lost, as you could be changing rows every other grid step. Then these savings would only be present in rays that happen to be 'more dominant in one axis than the other, which I'm not too sure is a valid case to make for efficiency?

~Main
==
Colt "MainRoach" McAnlis
mainroach.blogspot.com

[Edited by - duhroach on May 9, 2008 9:10:57 AM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this