Surface reconstruction | Animation | Surface retouching | Image Inpainting | Metamorphosis | Surface blending | Sketching | Smoothing |
If initially a set of N scattered data points in 3D are given and our goal is to reconstruct a surface based on this data. Using CSRBF we create a spline implicit function f(x,y,z)=0 (surface) or f(x,y,z)<=0 (volume).
There are two approaches to the reconstruction problem using RBF splines:
In practice, the problem of reconstruction with RBFs consists of the following steps: sorting the data, constructing the system of linear algebraic equations (SLAE), solving the SLAE, and evaluating the functions. In fact, while the solution of the system is the limiting step, constructing the matrix and evaluating the functions to extract the isosurface may also be computationally expensive.
We use CSRBF splines instead of RBF for both approaches which leads to a sparce matrix of size N+4*N+4 in SLAE. We have created a special algorithm based on octal tree subdivision of the intial space, which sorts initial data points in such a way that the resulting matrix is band-diagonal, which enables us to store it very compactly and solve it by using fast and easy direct solver. Later the octal tree is also used in the process of the surface extraction to accelerate the computation of the implicit function f(x,y,z).
Model of the Sea shell. You can download source
normalized point data (26 KiB) of this model and the result of reconstruction
model in vtk file format (321 KiB).
|
Test configuration: AMD Athlon 1000 Mhz, 128 MB RAM,
Microsoft Windows 2000.
|
Model of the Human Head. You can download source
normalized point data (41 KiB) of this model and the result of reconstruction
model in vtk file format (293 KiB).
|
Test configuration: AMD Athlon 1000 Mhz, 128 MB RAM,
Microsoft Windows 2000.
|
|
|
Donwload some of our test files and save them to disk or prepear some of your own examples. Note that the data you upload should be already normalized, i.e. all point should lie in unit cube 0-1,0-1,0-1. File format is following:
Normalized points for use with sphere as a carrier function:
xmin xmax ymin ymax zmin zmax xi yi zi ...(first line defines the original model bounds, before the normalization.)
xmin xmax ymin ymax zmin zmax xi+ yi+ zi+ xi- yi- zi- ...(first line defines the original model bounds, before the normalization, all other lines defines points on + side and - side of normals).
You'll also need a VRML plug-in for your browser, we reccomend Cortona http://www.parallelgraphics.com/products/cortona/download/.
Now you can appload file and see it as a VRML object. We strongly recommend you to use Netscape Communicator 4.x browser. Be prepared to wait for some time, network may be quite busy.
Note:This program was compiled for Microsoft Windows and can be used on any PC with Microsoft Windows 9x, Me, NT, 2000 or XP installed. Before running this program you need to download and install VTK runtime library VTK Core (2.8 MiB), if you have not done it already.
Normalizer: performs automatic normalization of source point data, given *.pts file:
xi yi zi ...it creates a normalized point data file (*.npts) for use with our reconstruction software.
NormalizerNorm: performs automatic normalization of source point data taken on both sides of normals, given *.pts file:
xi- yi- zi- xi+ yi+ zi+ ...it creates a normalized point data file (*.npts) for use with our reconstruction software.
Reconstruction: performs automatic reconstruction of normalized source point data, given *.npts file and selected radius of support r. If the file contains normalized points taken on the both sides of normal the programm will use both-sides approach, if not it will use sphere as initial carrier function. The model will be rendered on screen and also saved on disk in vtk file format (reconstructed_shape.vtk).
Usage: reconstruction.exe file.npts 0.28
Download: exe, 156 KiB.
Download example data (all examples): exe, 4.7 MiB.