ray intersection in regular grid

Recommended Posts

ehmdjii    238
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 on other sites
Deleter    169
s=source
x and y are the height and width of an arbitrary triangle based on your angle.
  s=(x1,y1)  |\ .  | \ rayy |  \ .  |___\ .    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 on other sites
Sneftel    1788
Bresenham's line algorithm can be used for this.

Share on other sites
wodinoneeye    1689

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 on other sites
ehmdjii    238
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!