ray intersection in regular grid
Author
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!
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.
angle from s
so
or
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)
s=source
x and y are the height and width of an arbitrary triangle based on your angle.
s=(x1,y1) |\ . | \ rayy | \ . |___\ . xangle from s
tan(s)=x / yso
y=((x + x1) / tan(s)) + y1or
x=tan(s) * (y + y1) + x1Then 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)
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.
Author
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!
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!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
