• Advertisement
Sign in to follow this  

Integer only ray-grid traversal accuracy

This topic is 3576 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
This might be of interest....
Capsule vs Grid
Your line is a 0 radius capsule...
D = 0 , R = S

It does use float-to-int, but 2 per "row", rather than any per "cell"
Gives you first and last cells hit on a row... so then it's just a loop.

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
Sign in to follow this  

  • Advertisement