Josiah Manson

Pipelined Wavelet Reconstruction - Source, Executable
July 24, 2008

This program performs wavelet surface reconstruction using either the Daubechies 4 or Haar wavelets. The reconstruction is performed in a streaming fashion so that large datasets can be processed. The reconstructed surface can be written to disk or displayed in a window with the input points or with a plane that shows values of the approximated indicator function.

Most of the programs options are controlled through the command line, many of which can significantly affect the memory usage and computation time of the reconstruction. What each option controls is explained below.

Example usage

To give a quick idea of how to perform surface reconstruction with our tools, I will give an example of how Armadillo Man can be converted from a Wavefront obj file to our pts fromat, and then reconstructed.

No streaming, but with visualization

> ObjToPts armadilloman.obj
> WaveletPipeRecon pts armadilloman.pts depth 7\
    wavelet daub4 stream f load_plane t load_points t

With streaming

> ObjToPts armadilloman.obj
> SortPoints armadilloman.pts
> WaveletPipeRecon pts armadilloman.pts depth 7\
    wavelet daub4 stream t to_screen f

Command line options

WaveletPipeRecon.exe

To get a list of possible parameters, run the program with no parameters.

> WaveletPipeRecon.exe
Parameters can be passed to the command line by first
giving the name of the parameter to modify followed
by its value.

pts         [.pts]
depth       [N]
wavelet     (haar|daub4)
to_screen   (t|f)
to_file     (t|f)
prune       (t|f)
blur        (t|f)
pts_node    (t|f)
above_below (t|f)
eval_pass   (t|f)
stream      (t|f)
surf_at_pts (t|f)
fill_in_mem (t|f)
stay_open   (t|f)
load_plane  (t|f)
load_points (t|f)
cfg         [config_file]

In all cases, the parameter you want to set is followed by the value the parameter should be set to.

pts

The point file to be processed should be given. If streaming is enabled, the point file must be sorted. Sorting can be performed by the SortPoints program. If streaming is not enabled, the input file does not need to be sorted. There are several tools to convert from different formats to our pts format, but if no tool exists to convert the input you are using, the pts files are simple to generate.

The pts format has a simple header followed by a list of all the points. Using C-like notation, the format is as follows:

struct xyz
{
    float x, y, z;
};

struct bbox
{
    xyz min_corner, max_corner;
};

struct header
{
    bbox bounds;
    int number_of_points;
};

struct point
{
    xyz normal, position;
};

struct pts_file
{
    header head;
    point points[];
};

depth

Depth specifies the maximum number of discrete function values on an edge of the bounding box that can be generated. The number of cells on a side is 2^depth.

wavelet

Either daub4 or haar can be specified for the Daubechies 4 or Haar wavelets respectively.

to_screen

If to_screen is true, then an OpenGL context will be created and all of the output triangles will be stored in memory so that the reconstructed surface can be visualized.

to_file

If to_file is true, then the output will be written to disk instead of being kept in memory. The output is written to a custom bobj format that is a simple conversion of the Wavefront object format to a binary form. If the bobj files become too large (around 400 megs), they will be split into multiple output files.

The bobj format consists of two types of fields: vertex positions, and triangles that index the vertices. The C-like specifications of the field types follow.

struct vertex
{
    char type = 0;
    float x, y, z;
};

struct triangle
{
    char type = 1;
    int v0, v1, v2;
};

A vertex's index is implied by its order in the file, and indexing starts from 1. There is no header, and the only guarantee on the ordering of triangle and vertex fileds is that trinagles will only index vertices that are specified earlier in the file.

prune

Pruning adds one pipeline stage for Daubechies 4, and two stages for Haar wavelets. Pruning also adds 8 bytes per node. Pruning enables adaptive resolution of the octree along a surface and prevents undersampling with sparse data.

blur

Blurring (a.k.a. smoothing) adds one stage to the pipeline and 32 bytes to each node. This option applies an adaptive 3x3x3 Gaussian blur to the approximated indicator function.

pts_node

When set to true, the resolution of the number of points in a cell is stored at one lower depth than when set to false. Thus, setting pts_node to true sacrifices some quality in approximating the surface area at each point, but saves 24 bytes per node.

above_below

Setting above_below to true uses one more byte per node to store information used to restrict the dual marching cubes traversal, and can save some time.

eval_pass

During Haar reconstruction, setting eval_pass to true will store the function values in the tree rather than evaluating the function on the fly. This adds one pipeline stage and 32 bytes per node, and should only be used to visualize the function values with a plane cross section.

stream

When set to true, streaming is enabled, and when set to false, the reconstruction is done entirely in memory. Not streaming saves time, and streaming saves memory.

surf_at_pts

For non-closed surfaces, it can be useful to reconstruct the surface only where scan data exists. Enable this option to cut away all surface that is not near input points.

fill_in_mem

To guarantee that there will be no artifacts from streaming in the streaming surface reconstruction, this option must be enabled. The option ensures that the tree is filled to a uniform depth up to the depth kept in memory. Often, this option is not required, and can be disabled to save some memory.

stay_open

load_plane

When enabled, the indicator function values can be visualized by a plane that slices through the volume.

load_points

When enabled, the input points can be visualized alongside the surface.

cfg

A configuration file can be specified to load parameters from. The configuration file uses the exact same format as the command line, except that lines can be commented by using the # character.

3D view interface

Rotation

Drag with the left mouse button.

Scaling

Drag with the right mouse button.

Translation

Drag with the middle mouse button.

Toggling point display

Press p to toggle and make sure that loading of points is enabled.

Toggling surface display

Press s to toggle display of the surface.

Toggling line display

Press l to toggle display of lines around triangles.

Toggling plane display

Press o to toggle and make sure that loading of the plane, and the evaluation pass or blur are enabled, and also that streaming is disabled.

Pressing [, ], -, and + move the slice along the plane normal, and x, y, z select the slice orientation.

Saving views

There are ten savable views that can be selected by pressing 0-9. After selecting a view, write to the view by pressing w, or read from it by pressing r.

SortPoints - Source, Executable
July 24, 2008

This program performs and out-of-core merge sort of a pts file along the z axis. If the longest axis is not the z axis, the model will be rotated so that the longest axis is the z axis. Nothing fancy is done, just 90 degree rotations. To use the program, supply an input file as an argument, and optionally give an output file name as a second argument. If no output file name is specified, the input file will be overwritten.

Example usage

> SortPoints armadilloman.pts

ObjToPts - Source, Executable
July 24, 2008

This program converts from a Wavefront obj file to an unsorted set of points that lie on the surface of the object. The output file will have the same name as the input file, except that the extension will be changed to pts.

Example usage

> ObjToPts armadilloman.obj

PlyExtract - Source, Executable
July 24, 2008

This program converts all of the ply files in a directory to a single unsorted set of points that lie on the surface of the object. The output file will have the same name as the input directory name, except that a pts extension will be added.

Example usage

> PlyExtract david

Uniform2D - Source, Executable
July 24, 2008

This program performs 2D contour reconstruction in a graphical interface. The shape that will be reconstructed is given by defining a uniform cubic b-spline from which input points are sampled for contour reconstruction. The control lines are shown in blue, the b-spline is shown in light green, and the reconstructed contour is shown in red. As well, the indicator function is drawn, with white being the largest value and black being the lowest value. Most commands can be done through menus, but also have keyboard shortcuts.

Drawing shapes

Shapes are defined by the lines and vertices of the control mesh. Vertices are added by left clicking. Each vertex can be one of three colors to indicate its state. Most vertices are purple, but there is one pink vertex, and one red vertex. The red vertex is the currently selected vertex, and the pink vertex is the previously selected vertex. Right clicking on a vertex selects it, and right dragging a vertex moves it. The keyboard commands to edit the mesh follow:

• c connects the selected vertices
• d deletes the line between the selected vertices
• s makes the current vertex sticky, or sharp
• x cuts the selected line into two lines
• r removes the selected vertex
• l toggles the display of the control mesh and its b-spline

Changing the view

Dragging with the middle mouse button translates the view, and pressing 0-9 zooms in or out.

Reconstruction

To perform Haar reconstruction, press h, and to perform Daubechies 4 reconstruction, press j.

Haar2D Adaptive - Source, Executable
July 24, 2008

This program performs adaptive 2D contour reconstruction in a graphical interface. Adaptive means that the tree will be pruned so that with non-uniform sampling, no part of the model will be undersampled. The interface to this program is identical to that of Uniform2D, except that adaptive pruning can be toggled by pressing y.

Sample Data
July 25, 2008

Here is some sample data to try out the program.