Removing Topological Handles by Pre-Processing Range Images

Craig Povey and Eric Firestone
CSC 570R
Winter 2006

[ Introduction ] [ Design ] [ Algorithm ] [ Screenshots ] [ Downloads ]

Introduction

Although range scanning technology has contributed greatly to 3D model creation, it has also introduced some concerns that did not previously exist. For instance, geometric and topological defects in the final model result from a number of factors inherent to the scanning process, such as: sampling density, sampling noise, misalignment of range images, poor calibration of scanner and camera, or grid discretization.

Surface handles and genus

One particular topological defect common to most 3D models reconstructed from range scans is that of extraneous topological “handles” or “tunnels”; this is the class of defect that our application addresses. In order to define what a topological handle is, we must first define the mathematical term genus. For our purposes, the genus of a closed surface is analogous to the number of “watertight holes” in the surface; for instance, a sphere has genus 0, while a torus has genus 1. We then define a handle (also known as a tunnel) as a toroidal region of the surface with a genus of 1. A handle can be imagined as a portion of the surface that would be topologically analogous to the handle on a coffee cup model (or the center of a donut model, etc.). Therefore, we will often use the genus of a surface synonymously with the “handle count” of that surface.

Why are topological handles a problem?

In most cases, the handles found on the final reconstructed models are extremely small; in fact, the vast majority will be completely imperceptible to any user viewing the model from a reasonable distance. Since these topological defects seem not to degrade the appearance of the final model, it may seem pointless to attempt to remove them. However, although topological handles may not directly degrade the quality of a 3D model, they do in fact degrade it indirectly by complicating subsequent geometry processing procedures, such as model simplification, smoothing, and parameterization. In addition, topological artifacts hinder any type of mesh processing that must parameterize the surface (such as texture mapping and remeshing). Finally, some applications (such as the fitting of organ templates to medical MRI data) actually require topologically correct models.

To illustrate the effects of topological handles on the quality of a reconstructed 3D model, consider the example of mesh simplification systems. Most traditional mesh simplification algorithms preserve the topology of the original mesh (including any extraneous handles); as a result, many triangles on the simplified mesh are wasted on preserving minuscule handles on the surface that should not have existed in the first place (see images below). By removing these unwanted handles, the surface may be more accurately and efficiently simplified, deformed, animated, and rendered.

For this project, we have created a tool to modify the range data early in the pipeline in such a way that the final surface (extracted from the pre-processed data) will have a reduced number of extraneous handles.

Design

We designed our tool as a pre-processor to be used in conjunction with a system for reconstrucing a volume from a set of range images (such as VRIP). Specifically, our tool takes raw range images and processes them to remove data points that could lead to topological handles and other similar defects. After our error-detection algorithm (described in detail below) runs on a given set of range images, it can be used to write out a "clean" version of each range image (that is, a copy of the original range image with the tagged data points removed). These clean range images can then be passed through VRIP (or any other similar system that is compatible with the input format) in order to create a final volumetric 3D model that will have fewer topological defects then the corresponding model using the original data would. This system is described by the flowchart shown below:

Algorithm

Our main goal in this algorithm was to remove data in range images that will eventually lead to topological handles in the volumetric model. However, since this problem has never really been addressed in this way before, our first step in formulating a solution was to simply make an educated guess regarding the nature of the handle-sausing data; that is, we needed to come up with some metric to determine whether some particular range image data point would/could lead to topological defects. Our hypothesis was that the problem had something to do with the aligning and merging of multiple range images; specifically, we decided to pursue the hypothesis that the "bad data" occurs within the "overlap" region between two different range images. If a point in this overlapping region is "too far" away from the opposite range surface, this point may very likely lead to topological errors.

The main idea of our algorthm therefore, is: for the overlap of each range image pair R₁ and R₂, measure the distance of each point P₁ in R₁ to the range surface represented by R₂. If this distance is above some defined distance threshold, then we want to remove this data points. The main, high-level steps of our algorithm are as follows:

1. Find range image overlaps
2. For each point P in overlap, find closest point on opposite range surface
3. If the distance of this closest point is outside a given threshold, remove P from the range image

A more detailed description of each step in our algorithm is given below:

Step 1: Find range image overlaps

• Create "bucket" grid
1. Compute bounding box of R₁ + R₂
2. Segment bounding box into volumetric “buckets” (analogous to voxels)
• We are now concerned only with buckets containing pt(s) from both R₁ and R₂ (we call these "overlap buckets")

Step 2: Find the distance to the opposite surface

• For each “overlap bucket,” find distance from each point P₁ in R₁ to each face F₂ in R₂
1. First check if closest point P’ on F₂’s plane is actually within the polygon – if so, find point-to-plane dist and we’re done!
2. If P’ is not within the polygon, find dist from P₁ to each of of the polygon’s edges, and save the shortest

Step 3: Remove the "bad" data points

• After Step 2, we have the shortest distance of each point in R₁ to every other overlapping range surface.
• Now, for each overlapping point P, check this shortest distance D_calc against a given threshold D_thresh
• If this shortest distance is greater than the threshold (D_calc > D_thresh), we remove P from its range image
• The process of removing a data point in the range image is strongly dependent on the format of the input data. In our case, we read in (and write out) PLY files (see documentation here or here - see section 3.1) and therefore the process of removing a data point is dependent on the format of the PLY files we read in.

  Format of PLY range images

  A range image stored in a ply file consists of two "element" types: vertex and range_grid. The vertex elements have three "properties" - x, y, z - corresponding to the vertex positions. The vertex elements are stored sequentially in an order such that the range_grid can index into them.

  The range_grid is a matrix that indicates what point(s) if any were seen along each line of sight of the regular sampling grid. Range_grid elements have one property - a list of vertices per line of sight in the range image. Normally, this list is either of length 0, meaning no range point was observed or length 1 indicating a single point was observed. If the length is 1, then the list contains the index of the vertex observed. The range_grid elements are stored in row major order.

  The header of a PLY range image should look something like the following:

  ply
format binary_big_endian 1.0
obj_info num_cols 512
obj_info num_rows 400
element vertex 22310
property float x
property float y
property float z
element range_grid 204800
property list uchar int vertex_indices
end_header

  Based on this format, there are two steps to removing a point from the range image.

1. First remove the "bad" vertex from the vertex list
2. Next, go through the range_grid matrix and update the matrix entry containing the removed vertex (as well as all subsequent entries)
Once we have removed all the "bad" data from a range image, we may then write all the data back out to a new PLY file. We name this output file with the same name as the original PLY, but give it a ".cln.ply" extension to easily differentiate between the original and processed data.

Screenshots

The following screenshots are taken after running our tool with just two range images of the "Happy Buddha" model, taken from Stanford's 3D Scanning Data Repository

Two differently-colored range images.	Same model, after running our algorithm. Points to be removed are shown in RED.

Original range image data after processing	"Cleaned" range image data after being processed a second time

	Original Range Data	"Cleaned" Range Data
Genus (# of handles)	104	38

Comparing the volumetric models created from the original range data and our cleaned data (respectively). Notice that our volume had a noticeably lower genus (# of handles) than the original volume

The final volumetric model reconstructed from our clean range data, using VRIP. This is the model with genus 38.

Downloads

Executable: Engine.exe

Example PLY Configuration file: happyStandRight.conf

Example PLY range images: happyStandRight_0.ply   |   happyStandRight_24.ply

Execution Instructions:

In order to download our tool and the sample data set used for the screenshots on this website, please follow the instructions below:

• Download the executable, the configuration file, and both PLY files to a directory of your choice. Then, open up a DOS command prompt window and cd to this directory.
• Next, simply enter the command: "Engine happyStandRight.conf", kick back, and prepare to be amazed!
• NOTE: This may take some time (5 ~ 10 minutes, depending on the video card and processing power) to finish...please be patient!