Jump to content
  • Advertisement
Sign in to follow this  
schupf

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.

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

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 this post


Link to post
Share on other sites
Advertisement
Try this link..

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)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!