|
GEL
2
GEL is a library for Geometry and Linear Algebra
|
|
GEL
2
GEL is a library for Geometry and Linear Algebra
|
A ThreeDDDA is a class for traversing a grid of cells. More...
#include <ThreeDDDA.h>
Public Member Functions | |
| ThreeDDDA (const CGLA::Vec3f &p0, const CGLA::Vec3f &p1, int _PRECISION=0x100) | |
| int | get_no_steps () const |
| Return the total number of steps the ray will traverse. | |
| const CGLA::Vec3i & | get_current_cell () const |
| Yields the current cell containing the ray. | |
| const CGLA::Vec3i & | get_first_cell () const |
| Get the initial cell containing the ray. | |
| const CGLA::Vec3i & | get_last_cell () const |
| Get the last cell containing the ray. | |
| const CGLA::Vec3f | get_first_point () const |
| Get the initial point containing the ray. | |
| const CGLA::Vec3f | get_last_point () const |
| Get the last cell containing the ray. | |
| bool | at_end () const |
| Returns true if we have reached the last cell. | |
| void | operator++ () |
| Take a step along the ray. | |
| const CGLA::Vec3f | step () |
| Get the initial point containing the ray. | |
A ThreeDDDA is a class for traversing a grid of cells.
We wish to enumerate all cells pierced by the ray going from a point p0 to a point p1. It is dangerous to use floating point arithmetic since rounding errors may accumulate entailing that the 3ddda misses the cell containing the end point of the ray.
Daniel Cohen-Or devised a technique for exact ray traversal using only integer arithmetic. Using integer arithmetic, the computations are exact, but the ray must start and terminate exactly at grid points. I.e. the ray must start and terminate in cell corners.
To overcome this issue, I have implemented a scheme where the ray starts and terminates on a grid that is finer than the cell grid. This means that we have fast and exact computations, and the ray can travel between two almost arbitrary points.
A central problem with this scheme was that - in order to simplify things during the iterative traversal - the ray direction vector is always mirrored into the first octant (+x +y +z). If the fine grid used for the ray start and end points is a superset of the grid points of the cell grid, this mirroring is almost impossible to implement correctly. This is due to the fact that the first cell on the right side of the y axis is called 0,y whereas the first cell on the left is called -1,y. This lack of symmetry makes things very difficult, but by ensuring that the endpoints of a ray can never lie on an a corner, edge, or face of the cell grid, we can make the problems go away.
Hence, in this implementation, the fine grid is obtained by dividing the cell into NxNxN subcells, but the grid points of the fine grid lie at the CENTRES of these subcells.
| Geometry::ThreeDDDA::ThreeDDDA | ( | const CGLA::Vec3f & | p0, |
| const CGLA::Vec3f & | p1, | ||
| int | _PRECISION = 0x100 |
||
| ) |
Create a 3DDDA based on the two end-points of the ray. An optional last argument indicates the resolution of the grid.
1.7.5.1
