1. Field of the Invention
The present invention relates generally to point cloud data, and in particular, to a method, apparatus, and article of manufacture for culling point cloud data to represent a displayed point cloud.
2. Description of the Related Art
When attempting to render billions of points in real-time, the bottleneck is to figure out which points are relevant for the screen space representation. Loading all of the points and overwriting the render buffer for every improved/better point results in a far from real-time performance. With points, there is little information that can help determine if it's relevant for screen space or not. A point cloud is entirely see-through because it does not represent a volume. Accordingly, what is needed is a method for culling a point cloud to determine which points are relevant. To better understand these problems, a description of prior art point cloud systems may be useful.
Point clouds are often created by reality capture devices such as laser three-dimensional (3D) scanners that measure a large number of points (e.g., from thousands to many billions of points [3D coordinates]) on the surface of an object, and output a point cloud as a data file. The point cloud represents the visible surface of the object that has been scanned or digitized. With the increased usage of such reality capture devices, large point cloud data sets are more frequently created for consumption by design applications. The challenge that design software faces is visualizing and using this data efficiently in the applications. While the point cloud data set is often very large, the number of points an application is capable of handling for visualization and other needs is a small fraction—a few million points, for example. Prior art methods fail to provide the ability to process the massive volume of points, in real time (e.g., preserving a ten [10] frames per second or faster rate) to read a small fraction of points that have the property of accurately representing the original data set without loss of detail or information that causes misrepresentation of the original data.
Point cloud visualization and applications are increasingly important in design, especially due to the decrease in the price point of the technology. Point clouds can contain an enormous number of points. One of the major challenges is representing the set of points while providing the ability to extract a small subset that is highly representative of the spatial region of interest.
As described above, a point cloud is created using a laser beam/scanner that scans objects/surfaces to obtain millions of points. For example, an image scanner on top of a car that drives through a city may obtain millions upon millions of points. If such points are rendered in a certain environment, different viewpoints may be queried/requested and displayed to a user. However, with a point cloud, if a scene is rendered, the depth component may not map properly. As a result, a visualization of a point cloud may require one thousand (1000) times of overdraw before the correct visualization is achieved.
Prior art methodologies may attempt to select a subset of the points in a quick and efficient manner. One approach divides a volume of interest into equal size rectangular 3D cells. Each of the thousands of cells may contain millions of points. The issue arises as to how to determine how many and which points to select from/in a cell. Further, point cloud data resulting from a scanner may have various artifacts that are undesirable. Accordingly, there is a desire to eliminate the scanner artifact, to normalize the point selection, and to obtain a uniform distribution/real depiction of the distribution of the point cloud data regardless of the location of the scanner. Many prior art approaches have attempted to solve such problems. Such approaches range from nearest neighbor based approaches to frequency domain based approaches. Concepts of downsampling, borrowed from image processing techniques have also been incorporated in solutions to view large point data sets. Goals of some techniques include noise removal and optimal representation, at the expense of computation and with freedom to modify the original point set.