Reconstruction of Solid Models from Oriented Points Sets
links
executable
implementation
compiling
LINKS
SGP 2005 Paper
Windows Executable
Source Code
License
EXECUTABLE ARGUMENTS
- --in <input points>
- This string is the name of the file from which the point set will be read.
The file should be an ascii file with groups of 6 floats (x-, y-, and z-coordinates of the point's position,
followed by the x-, y-, and z-coordinates of the point's normal).
Alternatively, if the file extension ends in .ply, the executable will attempt to read in the
PLY format. In this case, the file
should consist of a collection of vertex elements, where the vertex element has properties
x, y, and z corresponding to the position of the sample, and properties
nx, ny, and nz corresponding to the normal direction.
- --out <output triangle mesh>
- This string is the name of the file to which the triangle mesh will be written.
The file is in ascii format representing the triangles of the mesh, with no connectivity information.
The file is an enumeration of groups of either 9 or 18 floats (x-, y-, and z-coordinates of the three triangle's
vertices for the former, x-, y-, and z-coordinates of the three triangle's vertices followed by the x-, y-, and
z-coordinates of the triangle's normals for the latter). (See the description of the --normal argument
for more information.)
Alternatively, if the file extension ends in .ply, the executable will write out the mesh in the
PLY format.
- --res <reconstruction resolution>
- This integer is the resolution of the voxel grid that will be used for the surface reconstruction. Because the
implementation depends on the use of the FFT, res should be a power of two. (The memory foot-print of the
algorithm is a bit larger than 8xresxresxres so on a computer with 1 gigabyte of RAM,
the value of res should be no larger than 256, otherwise the code will thrash.)
- [--order <fitting type>]
- This integer argument specifies the type of function that is used to interpolate/approximate the voxel values. The
meaning of the integer values are as follows:
- 1: Linear Interpolation
- 2: Quadratic Interpolation
- 3: Cubic Interpolation
- 4: Catmull-Rom Interpolation
- 5: Uniform Cubic B-Spline Approximation
If this argument is not specified, the fitting will default to quadratic.
- [--normal]
- If this argument is specified the executable will also compute the normals of the triangle mesh at the vertices
by computing the appropriate derivatives of the fitting function. The normals will then be written out to the output
file as well. (In the case that the file is written out in
PLY format, the vertex element will have properties
nx, ny, and nz corresponding to the normal at the vertex.)
- [--weight <width>]
- This floating point value specifies the width of the Gaussian that should be used for assigning weights in the
case that the samples are non-uniform. (A small value around 1 generally works well.) If this argument is not specified,
the executable assumes that the points are uniform and assigns equal weight to every point. (If the value is negative,
the weighting is somewhat more complicated and takes more time, using not the only the distribution of the points,
but also the distribution of the normal directions to assign the sample weights.)
- [--smooth <width>]
- This floating point value specifies the width of the Gaussian that should be used for smoothing the iso-function.
(Because we are computing the Fourier coefficients of the iso-function anyway, smoothing does not take any extra time.)
In the case that the value of width is negative, the iso-function is convolved with a filter whose Fourier
coefficients are the reciprocals of those for the filter obtained using a Gaussian width of |width|, thereby
inverting the smoothing operation and effectively applying a sharpening filter to the data.
- [--scale <scale factor>]
- This floating point value specifies the factor of the bounding cube that the input samples should span. (By
default, the value is equal to 1.)
- [--noNormalize]
- By default, the program assumes that the sizes of the normals are unimportant and all normals are rescaled to
have unit length prior to processing. If this flag is set, the code will assume that the lengths of a normal
is inversely correlated with the sampling density at the point, and will (assuming that the --weight argument
is not specified) use the lengths to weight the contribution of the point to the overall reconstruction.
- [--fftwWisdom <wisdom file>]
- The name of the file into/from which FFTW should write/read in the wisdom it accumulates as it sets up the FFTW plans.
(The first time the code is run with this argument, the execution time will be markedly slower as the FFTW will be trying
different possible optimizations for computing the FFT. However, on the second run at the same resolution, this will
result in a speed-up over not using any wisdom at all.)
IMPLEMENTATION DETAILS
The implementation of the surface reconstruction algorithm provided in the source code contains several features
not explicitly discussed in the Symposium on Geometry Processing 2005
paper:
- Iso-Surface Extraction: The source code provides method for extracting iso-surfaces by fitting different
types of splines to the voxel data. This is particularly important since the iso-function exhibits a sharp
discontinuity around the surface boundary and a linear interpolation does not always give a smooth reconstruction at
these discontinuities.
- Normal Weighting: While the paper only discusses a weight assignment method that uses the convolution
of the sample position "splatting" with a Gaussian filter, the source code also provides a weight assignment
method that uses the convolution of the sample normal "splatting" with a Gaussian filter. This allows the
weighting algorithm to assign weights that are determined by the regional normal orientation. This weighting method
requires more computation but has the property that when two different surface patches are close to each other, the
regional weighting will only consider the density of points with similarly aligned normals.
- Extending the Fourier Coefficients: As discussed in the appendix of the paper, the surface reconstruction
has the theoretical property that it commutes with rotation. In order for this to be true in practice, for a
reconstruction at a resolution of r, the Fourier
coefficients need to be defined within a ball of radius Sqrt(3)*r/2 rather than a cube of size
[-r/2,r/2]x[-r/2,r/2]x[-r/2,r/2]. A direct method for satisfying this condition would be
to compute a somewhat larger FFT, using a cube with size
[-Sqrt(3)*r/2,Sqrt(3)*r/2]x[-Sqrt(3)*r/2,Sqrt(3)*r/2]x[-Sqrt(3)*r/2,Sqrt(3)*r/2] and
then zeroing out those coefficients corresponding to frequencies larger than Sqrt(3)*r/2.
However, this type of approach increases both the computational complexity and the memory overhead.
Instead, we address this requirement by aliasing the "splatting" functions(i.e. assuming that the value of the Fourier
coefficient at frequency k+r is equal to the value of the Fourier coefficient at frequency k) and
then convolving with a smoothing comb filter. Since most of the Fourier coefficients of the comb filter
will be zero, we can do this without noticeably affecting either the computation time or the memory overhead.
SOURCE CODE COMPILATION
The source code is not self-cotaining. In order to get it to compile you will need to link to the
FFTW libraries.
HOME