Saturday, August 13, 2011

Algorithm for line-cuboid intersection?

I need to know a formula or algorithm for determining the intersection of a cuboid (defined by its two corners) and a line (defined by a point lying on the line and a vector describing the direction of the line- although a second point lying on the line would obviously be easy to construct) in 3D space. I don't need it to generate point data, just a yes or no answer as to whether the line and the cuboid have any points in common. The reason is that I'm writing a program that will need to use this kind of math. Don't worry, it's not homework. I know that I can do this in principle, but because the program will need to do it a huge number of times, I'd like to use the fastest available formula that can reasonably be written in Java, and I doubt that any solution I come up with would be optimal. A degree of error due to floating point inaccuracy is acceptable, so long as it's small enough. Anyone know of a good (preferably optimal) formula for this?

No comments:

Post a Comment