# Clip ray against grid

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

## Recommended Posts

Hello!

I have a 2D grid in the XZ plane with N x M cells. Now I have a 3D ray and want to know which 2D cells are visited by the ray.
If the ray was a line segment with both start and endpoint inside the grid, everything would be easy. I would just project the line segment into the grid (by just skipping the y coordinate) and check which cells are touched.

Unfortunately my ray can start outside the grid and since my ray is infinitely long I need to compute where the ray leaves the grid. I added a sketch for the 3 cases as attachment.

In case A the ray starts (green dot) inside the grid and the ray intersects the grid rectangle (red point). In case B the ray does not intersect the grid rectangle and leaves at the upper grid edge. In case C the ray starts outside the grid and leaves the grid at the upper edge (both entry and exit points are red dots).

Does anyone know a simple algorithm/website which computes the red dots (the entry and exit points of the ray with the grid rectangle)?

##### Share on other sites

http://lodev.org/cgt...raycasting.html

Although the problem isn't too bad. Consider everything being 2d. Your ray has some arbitrary start point(P1) and end point(P2). You are trying to find some arbitrary point(P3) that intersects directly with any number of horizontal or vertical grid lines.

To find the total number of horizontal grid lines crossed you would do something like:
 floor(abs((P2.y - P1.y) / gridCellHeight)) 

To find the total number of vertical grid lines crossed you would do something like:
 floor(abs((P2.x - P1.x) / gridCellWidth)) 

You can then loop through the following formulas as long as you know the vertical or horizontal line that is being crossed.

to find the point on the line(P3) crossing the vertical grid line. P3.x is known
 P3.y =( -(P1.y-P2.y)*(P2.x - P3.x)/(P1.x-P2.x)) + P2.y 

to find the point on the line(P3) crossing the horizontal grid line. P3.y is known
 P3.x = -(P1.x *(P2.y-P3.y) - (P1.y-P3.y) *P2.x)/(P1.y-P2.y) 

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633725
• Total Posts
3013558
×