# Problem with line intersection with grid.

• Feb 21st 2011, 08:34 PM
Higgs1
Problem with line intersection with grid.
Yes, poorly named thread I'm sorry. One problem I'm having is that I have absolutely no idea what this is called, or even what area of math this falls under. To the best of my knowledge it falls under Trig because it deals with angles.

Anyway, I'm a computer programmer working on something and I'm given a 3d grid. This space is infinite in two dimensions, but finite in the third. Then, I have a point in this space and a direction. One thing I kept in my mind while trying to solve this problem is that this line thing will only stop if the direction is not parallel to the dimension that is finite. Yes, wrong terminology. Chances are that the direction isn't parallel though.

What I'm looing for is the first cube (that is, closest to the point I'm given) that this resulting line (it might be called a ray) occupies that matches a certain criteria that I'm given. To do that I'll need to check each cube to see if it matches my criteria. The only problem is that I can't figure out how to get which cubes this line occupies.

My current method is to increment a certain distance (currently I'm using 1/10th of the size of a cube, it works well) away from the point and test if the occupied cube matches the criteria. If it doesn't increment again and repeat. The problem with this method is that if the line/ray just clips a corner of a cube, I may miss it. I know for certain there is a way to solve this without missing any cubes.

Also, if at all possible, could i have the name of my method and the correct method so that I know what to call them?
• Feb 21st 2011, 08:57 PM
thyrgle
If I am understanding what you are saying, I believe you are talking about "penetration depth". Which is by checking through increments or periodically, if something has collided with something else. Usually used in video games I believe for collision detection. And the amount of increments or the amount of times between checking influences the accuracy and results.
• Feb 22nd 2011, 10:38 AM
Higgs1
THank you. Is there any alternative that doesn't involve incrementing so that it doesn't miss?
• Feb 22nd 2011, 05:52 PM
thyrgle
@Higgs1:

Basically, check if the line is parallel, check for which plane it will intersect and then use math to solve where the ray intersects the plane ( Intersection of Lines and Planes). That's what I would do.
• Feb 22nd 2011, 07:15 PM
Higgs1
Thank you, i had not thought of that. And thanks for the code too, I'm using Java but they're the same thing.