Sometimes the dataset is given in irregular grids, for instance, datasets from computer simulations, partial differential equation solvers, and so on. The algorithms described in the previous sections assume a regular rectilinear grid and they can not work on general grids. The usual approach is to transform the irregular grid into a regular grid by introducing new points using some sort of interpolation. The problem with this approach is that the resulting regular grid may turn out to be very big.
Some methods have been designed to visualize a special type of irregular grid (such as those generated for Computational Fluid Dynamics [47]), but the problem of visualizing general irregular grids is still in its infancy. Here we present a method to visualize sparse irregular grids. The method assumes the elements that define the grid have a hexahedral convex shape. The sampled points are defined to be the vertices of the shape elements.
The algorithm is based on the plane sweep method, which is very common in
computational geometry [48]. The idea is to be able
to do a ray casting along the rays that start from the image plane as
these rays traverse the object. The problem is similar to a point
location problem in three dimensions, but the current solutions to
these problems are too slow and hard to code to be used in
visualization. To avoid doing point location at the elements in the
grid, the algorithm maintains a sweep plane perpendicular to the image plane
and the set of active elements
.
The intersection of the sweep plane and the active elements is a set of convex polygons. The algorithm breaks these polygons into triangles (in the simplest possible way, it just calculates the centroid of each polygon and connects the centroid to all the vertices). For each vertex of these triangles, the algorithm calculates the color and opacity associated with that vertex by linear interpolation. After all the triangles are complete, the algorithm casts rays in the plane.
By proceeding as described, the algorithm is able to efficient compute all the pixels in the image plane without any further assumption on the kind of grid being used. It also avoids computational geometry methods that may be cumbersome to implement and hard to debug because of degeneracies.