Sign in to follow this  
ehmdjii

ray intersection in regular grid

Recommended Posts

hello, i have a regular grid where each cell may represent an unpassable obstacle. now i am looking for an algorithm that shoots a ray from a certain point into a certain direction and returns the first intersection point with such an unpassable cell. the grid datastructure is just a 2d-array where i can access each cell with x,y and ask if it is passable or not. thanks!

Share this post


Link to post
Share on other sites
First find what your height in your grid will be based on your x
s=source
x and y are the height and width of an arbitrary triangle based on your angle.

s=(x1,y1)
|\ .
| \ ray
y | \ .
|___\ .
x

angle from s

tan(s)=x / y


so
y=((x + x1) / tan(s)) + y1

or
x=tan(s) * (y + y1) + x1

Then run through your grid horizontally using this equation (plugging in value for x) and request solidity of grid(x,y)

Also, then to compensate for the case where a line hits two or
more squares within an x, do it vertically (using the second equation) and plugging into to solidity(x,y)

Share this post


Link to post
Share on other sites


I have done this by prebuilding an array of the vectors traversals for an adaquate number of angles intervals (the path cell dx/dy offsets are stored working outward from the 0,0 center point). Visibility is scanned for all the angles/vectors within the view boresite and when one cell blocks then everything further is assumed not seen. (I used a similar system for a boresite culling of a grid based chunk rendering system also)

My simplification assumes that the entire cell is blocked and that the center point is in the middle of the cell. The array would be built for the maximum allowable distance (in cells) that can be seen (ie- 32). If that distance is too far then it gets prohibitive because the data and processing is proportionally N^2 to the max distance.


Within the above limitations, the data is static so you might as well prebuild it.

My usage was for complete scaning of an area within a pie section, and if you are back tracing from the target to the viewpoint, then something like Bresenham would be more applicable.

Share this post


Link to post
Share on other sites
thanks a lot guys! your solutions are working, but i forgot to mention something really important.

i am not only looking for the nearest sild grid cell, but in more detail for the nearest intersection point on that cell.

so the given position is a floating point. for example (4.7|2.1) that would mean that the position is on the tile(4|2) and there on the subposition (0.7|0.1)

so if the direction would change a little, the resulting point would slide along the closest sides of the solid grid cells.

thanks!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this