LiDAR (Light Detection and Ranging)

LiDAR is a new approach to high-resolution surface model generation. A LiDAR scanner traces a narrow laser beam across a regular grid of sample points and measures the arrival time of reflected light for each sample point. Based on this time and the constant speed of light, the scanner can report the 3D positions of surface points lying inside a pyramidal region of space. Larger regions can be surveyed by aligning and merging multiple individual LiDAR scans. LiDAR's main benefits are accuracy of each sample point, and speed, i.e., the number of sample points that can be measured in a given time period.

• Airborne LiDAR mounts a downwards-pointing LiDAR scanner on a low-flying aircraft and is used to gather high-resolution DEMs (digital elevation models) of the Earth's surface. Data gathered by airborne LiDAR is generally treated as a height field and resampled to a regular grid of elevation postings.
• Terrestrial or tripod LiDAR, on the other hand, mounts a horizontally pointing LiDAR scanner on a tripod to gather ultra high-resolution 3D data of natural and man-made structures. Tripod LiDAR is typically treated as a "point cloud" sampling of arbitrary surfaces, and not resampled to a grid. It can generate samplings with sample spacings of less than a centimeter, and accuracies of around 2mm per sample.

Tripod LiDAR can be used for very accurate deformation measurement. By scanning a region at two different times, one can measure the displacement of individual features by comparing the point clouds defining their surfaces. However, since the distribution of individual sample points on a surface depends on the exact location and orientation of the scanner, LiDAR scans cannot be compared point-by-point. Instead, one has to derive position information from larger sets of points. For example, a LiDAR scan of a house will contain large numbers of points representing each of the walls, the roof, etc. By selecting the subset of points representing one wall, and assuming that the wall is planar, one can derive the equation of the plane that best fits the selected subset of points. Similarly, one can derive best-fitting cylinders (representing pipes etc.) or other shapes. By deriving multiple equations, one can then calculate the locations of points by intersecting several derived equations, for example three planes. Since each plane equation averages the positions of large numbers of individual sample points, the (small) random inaccuracies introduced by the scanning process are reduced significantly. This allows the measurement of features with sub-millimeter accuracy.

The challenge in visualizing and analyzing tripod LiDAR data is that data sets can contain hundreds of millions to billions of unstructured (scattered) 3D points, each with their (x, y, z) position and an associated intensity or color value. Although the sample points sample surfaces in the surveyed area, the data does not contain any relationships between points -- the underlying surfaces have to be reconstructed from the point data alone. Our work focuses on developing software to visualize the "raw" LiDAR data as a cloud of 3D points with intensity or color values. We use an out-of-core multiresolution approach to visualize LiDAR data that is too big to fit into the computer's main memory, at interactive frame rates of around 60 frames per second. Our software also contains tools to analyze LiDAR data, for example, an interactive selection tool to mark subsets of points defining a single feature, and algorithms to derive equations defining the shape of such features.

Figure 1: LiDAR scan of a part of the UC Davis campus, containing the UC Davis water tower and (parts of) the Mondavi Center for the Performing Arts. This data set contains around 4.7 million points, and was provided by Gerald Bawden of the US Geological Survey. A movie showing a user viewing and analyzing this data set in a CAVE VR environment is available for download (MPEG-1 format, 27MB).

---

Project Goals

• Implement an out-of-core multiresolution point cloud renderer to visualize large (100 million to 10 billion points) LiDAR scans at interactive frame rates (around 60 frames per second) in immersive environments.
  • LiDAR data is represented in an octree of point sets. The octree is created by recursively splitting the data set's domain until each octree leaf node contains less than a given number of sample points. Intermediate octree nodes are created by subsampling the union of point sets contained in their children. The subsampling algorithm merges pairs of closest points, to achieve a uniform point density in each interior node of the octree.
  • The in-memory representation of the octree serves as a cache for the on-disk representation. Only the octree nodes relevant for rendering the current view are kept in memory. Cached nodes are exchanged according to their priority, based on the visible size of the node's domain and their distance from a focus region.
  • Cached nodes are subdivided, i.e., their children are loaded from disk, if their projected size exceeds a given threshold. By adapting this threshold, the overall rendering quality can be changed to achieve interactive frame rates independent of the performance of the underlying graphics hardware.
  • Currently rendered nodes -- a subset of the nodes currently kept in memory -- are cached on the graphics card using OpenGL vertex buffer objects. The fixed number of cached nodes is managed based on a most-recently used strategy.
• Implement an interactive selection mechanism to identify subsets of sample points defining the surfaces of individual features.
• Implement algorithms to derive mathematical equations for surfaces defined by subsets of sample points.

Project Status

We implemented an out-of-core multiresolution point cloud renderer as described above. The renderer is able to visualize the largest LiDAR scans we currently have, containing 1.4 billion sample points, at interactive frame rates using a fixed-size memory cache. Visualization quality degrades gracefully with computer and graphics performance. We implemented a brush-based selection mechanism that allows a user to select points by touching them with a three-dimensional "brush" connected to a 6-DOF input device in a VR environment. Our software currently supports the extraction of plane, sphere, or cylinder equations to fit geometric primitives to selected subsets of data. It also contains a simple color mapping algorithm that visualizes each point's distance from an extracted plane, for quick visual assessment of data elevations.

Screen Shots - Screen shots of LiDAR scans visualized using our software, and photographs showing the LiDAR viewer used in immersive visualization environments.