Surface
Reconstruction from Range Images
Nick Burns, Klaus Rott
Nick Burns, Klaus Rott
This project demonstrates the reconstruction of range image data utilizing a genetic algorithm. The range image data is provided to us as an ordered 3D point cloud, i.e. all points are aligned to a grid. The initial triangulation algorithm traverses this grid while reconstructing the surface. This initial triangulation result is then matched to a number of other ranges images. In order to find the best fit of both range image data point clouds, a genetic algorithm is used. This algorithm utilizes translation and rotation around all 3 axis to find the best matching set of points. After each iteration a new set of points is produced that can be used as input into a Delaunay Triangulation in order to produce a viewable result.
One major problem we had to solve in this project was the Delaunay Triangulation of a 3D point cloud. After researching the Delaunay Triangulation we found that although it is relatively easy to code an algorithm with little complexity (O(n2)) for 2D. However, in 3 space this becomes a little more complex. Our initial and current algorithm has a complexity of O(n4), which is less than ideal for large datasets as range image data with millions of points. Our attempts to extend a 2D O(n2) triangulation into 3D did not seem to work on a piece of paper so we did not even try and implement it. We did, however, take some ideas, such as the seed edge of the closest neighboring points, and utilized these in our improved triangulation. Unfortunately, we could not determine the error we apparently have in our thought process: either we are producing triangles that should not be created or we are creating only a single triangle.
The second big part of our project was the genetic algorithm. We were able to accomplish a relatively good approximation of two range image data sets. As of now, we are unable to visualize this properly due to our slow triangulation algorithm. The display of point clouds does not provide a very high level of detail. An example picture is included in the Screenshots.
Downside of our genetic algorithm is still the fitness and speed. At the high level of detail it takes a very long time to compute the different generations. We counteracted that by using a highly downsampled point set for our initial generations and worked our way up to higher levels of detail.
|
Screenshots: |
|
| This picture depicts an initial triangulation of one range image after the image has been down sampled by relatively small factor (4). It shows a high level of detail such as the waves in the area of the ripcage. However, it also has some errors to it, e.g. the triangles between the hind legs. |  |
| Both images are the result of an initial triangulation. However, both images have been downsampled by a higher factor (8) in order to speed things up even further. There is still a great level of detail visible but also more errors, e.g. the triangles on between the front legs or the holes in the surface |  |
 |
|
| These
two images are the result of a even higher down sampling, resulting
in images with around 950 triangles each. We used our Delaunay algorithm
to produce these images and were able to roduce a fairly high level
of detail. A major problem we ran into was the that the initial algorithm produced triangles between edges, such as the tail, the back and the rear of the head. We countered this problem by only allowing circumspheres with a center point within the bounding box of the model and set a median for the radius. |
 |
 |
|
| This two image depict a merge of two range images by the genetic algorithm. In the second image both images are a lot better aligned than on the first. However, these are only snapshots of generation results from the genetic algorithm and are not the potential end result. |  |
 |
|
| This picture depicts a very low resolution triangulation result of two merged range images. Both images essentially sit on top of each other however the points are not identical yet which explains the rubble area around the body area. |  |
| This series depicts another merge of two range images as performed by our genetic algorithm. The first picture is the start situation whereas the other two pictures depict the merger at different stages. |  |
 |
|
 |
|
| This is an example of a snapshot of a point cloud during the operation of the genetic algorithm. The viewing angle is from the front right; the tail is fairly visibly on the right top area as well as the legs and the body. The tiger has an additional leg coming out of the head on the left top corner which would eventually get merged where it belongs. |  |
One of the biggest obstacles as of now is the Delaunay Triangulation. Our implementation has a complexity of O(n4) which makes the triangulation of range image data with more than one hundred thousand of triangles a very long job. Our attempts at making the triangulation faster did not fully succeed; it seems that our theory would work however, the coding did not match our theory yet.
A second area where we would like to see improvement is the genetic algorithm itself to achieve a better matching guarantee. As of now, the nature of the algorithm, makes it difficult to allow for a better solution if a close approximation has already been found.
Leach, Geoff; RMIT, Australia: Delaunay Triangulation
Lambert, Tim; University of New South Wales, Australia: Delaunay Triangulation