Adaptive Multigrid Solvers (Version 16.05)

links compilation executables library usage changes

This code-base was born from the Poisson Surface Reconstruction code. It has evolved to support more general adaptive finite-elements systems:





  1. The implementation of the --samplesPerNode parameter has been modified so that a value of "1" more closely corresponds to a distribution with one sample per leaf node.
  2. The code has been modified to support compilation under MSVC 2010 and the associated solution and project files are now provided. (Due to a bug in the Visual Studios compiler, this required modifying the implementation of some of the bit-shifting operators.)
Version 4:
  1. The code supports screened reconstruction, with interpolation weight specified through the --pointWeight parameter.
  2. The code has been implemented to support parallel processing, with the number of threads used for parallelization specified by the --threads parameter.
  3. The input point set can now also be in PLY format, and the file-type is determined by the extension, so that the --binary flag is now obsolete.
  4. At depths coarser than the one specified by the value --minDepth the octree is no longer adaptive but rather complete, simplifying the prolongation operator.
Version 4.5:
  1. The algorithmic complexity of the solver was reduced from log-linear to linear.
Version 4.51:
  1. Smart pointers were added to ensure that memory accesses were in bounds.
Version 5:
  1. The --density flag was added to the reconstructor to output the estimated depth of the iso-vertices.
  2. The SurfaceTrimmer executable was added to support trimming off the subset of the reconstructed surface that are far away from the input samples, thereby allowing for the generation of non-water-tight surface.
Version 5.1:
  1. Minor bug-fix to address incorrect neighborhood estimation in the octree finalization.
Version 5.5a:
  1. Modified to support depths greater than 14. (Should work up to 18 or 19 now.)
  2. Improved speed and memory performance by removing the construction of integral and value tables.
  3. Fixed a bug in Version 5.5 that used memory and took more time without doing anything useful.
Version 5.6:
  1. Added the --normalWeight flag to support setting a point's interpolation weight in proportion to the magnitude of its normal.
Version 5.7:
  1. Modified the setting of the constraints, replacing the map/reduce implementation with OpenMP atomics to reduce memory usage.
  2. Fixed bugs that caused numerical overflow when processing large point clouds on multi-core machines.
  3. Improved efficiency of the iso-surface extraction phse.
Version 5.71:
  1. Added the function GetSolutionValue to support the evaluation of the implicit function at a specific point.
Version 6:
  1. Modified the solver to use Gauss-Seidel relaxation instead of conjugate-gradients at finer resolution.
  2. Re-ordered the implementation of the solver so that only a windowed subset of the matrix is in memory at any time, thereby reducing the memory usage during the solver phase.
  3. Separated the storage of the data associated with the octree nodes from the topology.
Version 6.1:
  1. Re-ordered the implementation of the iso-surface extraction so that only a windowed subset of the octree is in memory at any time, thereby reducing the memory usage during the extracted phase.
Version 6.11:
  1. Fixed a bug that created a crash in the evaluation phase when --pointWeight is set zero.
Version 6.12:
  1. Removed the OpenMP firstprivate directive as it seemed to cause trouble under Linux compilations.
Version 6.13:
  1. Added a MemoryPointStream class in PointStream.inl to support in-memory point clouds.
  2. Modified the signature of Octree::SetTree in MultiGridOctreeData.h to take in a pointer to an object of type PointStream rather than a file-name.
Version 6.13a:
  1. Modified the signature of Octree::SetIsoSurface to rerun a void. [cloudcompare]
  2. Added a definition of SetIsoVertexValue supporting double precision vertices. [cloudcompare]
  3. Removed Time.[h/cpp] from the repository. [cloudcompare/asmaloney]
  4. Fixed assignment bug in Octree::SetSliceIsoVertices. [asmaloney]
  5. Fixed initialization bug in SortedTreeNodes::SliceTableData and SortedTreeNodes::XSliceTableData. [asmaloney]
  6. Included stdlib.h in Geometry.h. [asmaloney]
  7. Fixed default value bug in declaration of Octree::SetTree. [asmaloney]
Version 7.0:
  1. Added functionality to support color extrapolation if present in the input.
  2. Modified a bug with the way in which sample contributions were scaled.
Version 8.0:
  1. Added support for different degree B-splines. (Note that as the B-spline degree is a template parameter, only degree 1 through 4 are supported. If higher order degrees are desired, additional template parameters can be easily added in the body of the Execute function inside of PoissonRecon.cpp. Similarly, to reduce compilation times, support for specific degrees can be removed.)
  2. Added the --primalGrid flag to support to extraction of a grid using primal sampling.
  3. Changed the implementation of the grid sampling so that computation is now linear, rather than log-linear, in the number of samples.
Version 9.0:
  1. Added support for free boundary conditions.
  2. Extended the solver to support more general linear systems. This makes it possible to use the same framework to implement the Smoothed Signed Distance Reconstruction of Calakli and Taubin (2011).
  3. Modified the implementation of density estimation and input representation. This tends to define a slightly larger system. On its own, this results in slightly increased running-time/footprint for full-res reconstructions, but provides a substantially faster implementation when the output complexity is smaller than the input.
Version 9.01:
  1. Reverted the density estimation to behave as in Version 8.0.
Version 9.011:
  1. Added a parameter for specifying the temporary directory.
Version 10.00:
  1. The code has been reworked to support arbitrary dimensions, finite elements of arbitrary degree, generally SPD systems in the evaluated/integrated values and derivatives of the functions, etc.
  2. For the reconstruction code, added the --width flag which allows the system to compute the depth of the octree given a target depth for the finest resolution nodes.
  3. For the reconstruction code, fixed a bug in the handling of the confidence encoded in the lengths of the normals. In addition, added the flags --confidence and --confidenceBias which allow the user more control of how confidence is used to affect the contribution of a sample.
Version 10.01:
  1. Modified the reconstruction code to facilitate interpolation of other input-sample quantities, in addition to color.
Version 10.02:
  1. Set the default value for --degree in PoissonRecon to 1 and change the definitiion of DATA_DEGREE to 0 for sharper color interpolation.
Version 10.03:
  1. Cleaned up memory leaks and fixed a bug causing ImageStitching and EDTInHeat to SEGFAULT on Linux.
Version 10.04:
  1. Replaced the ply I/O code with an object-oriented implementation.
  2. Updated the code to support compilation under gcc version 4.8.
Version 10.05:
  1. Added cleaner support for warning and error handling.
  2. Minor bug fixes.
  3. Added a --inCore flag that enables keeping the pointset in memory instead of streaming it in from disk.
Version 10.06:
  1. Improved performance.
  2. Modified PoissonRecon and SSDRecon to support processing of 2D point sets.
  3. Modified the 2D implementations of PoissonRecon, SSDRecon, and AdaptiveTreeVisualization to support ouput to .jpg and .png image files.
Version 10.07:
  1. Removed a bug that would cause memory access errors when some slices were empty.
Version 11.00:
  1. Added support for processing point-sets so large that 32-bit indices for octrees are not sufficient. (Enabled by defining the preprocessor variable BIG_DATA in the file PreProcessor.h.
  2. Added C++11 parallelism for compilers that do not support OpenMP.
  3. Added the code for ChunkPly which breaks up large meshes and/or point-sets into chunks.
Version 11.01:
  1. Fixed bug with _mktemp that caused the code to crash on Windows machine with more than 26 cores.
Version 11.02:
  1. Added error handling for numerical imprecision issues arrising when too many samples fall into a leaf node.
Version 12.00:
  1. Added functionality enabling AdaptiveTreeVisualization to output the values of a function at prescribed sample positions.
  2. Added the implementation of PointInterpolant that fits a function to a discrete set of sample values.
Version 13.00:
  1. Enabled passing in a constraint envelope to PoissonRecon, allowing one to define a region that is known to be outside the surface.
  2. Updated ChunkPLY to support processing of input points in either ASCII or binary format.
Version 13.50:
  1. Enabled support for automatically detecting attirbutes of input point cloud (in addition to positions and normals) when provided in .ply format.
Version 13.60:
  1. Modified the implementation of PointInterpolant to support separately prescribing value and gradient constraints.
Version 13.61:
  1. Bug fix addressing the problem that the memory for a DynamicFactory object is dynamically allocated and not only known at construction time.
Version 13.70:
  1. Using the updated PLY libraray with the less restrictive BSD license.
Version 13.71:
  1. Fixed a bug that resulted in incorrect point weighting when the samples were too sparse.
Version 13.72:
  1. Fixed a bug that could result in the reconstruction not solving up to the finest depth when the --width argument is used.
Version 13.73:
  1. Re-fixed a bug that could result in the reconstruction not solving up to the finest depth when the --width argument is used.
Version 13.74:
  1. Fixed a bug that could result in reconstruction failure when the reconstruction depth (e.g. computed using the --width argument) was lower than the full depth value.
Version 13.80:
  1. Updated the SurfaceTrimmer code to better handle small islands.
Version 13.99:
  1. Modified the --width parameter so that it serves as an upper bound on the width of a cell at the finest resolution.
  2. Modified the code so that the output mesh no longer has statistics about processing time/memory.
Version 14.00:
  1. Added support for distributed screened Poisson Surface Reconstruction.
Version 14.01:
  1. Added support for fixed width integer types.
Version 14.02:
  1. Fixed overflow bug when there are more than 2^32 nodes in the tree.
Version 15.00:
  1. Added support for header-only interface.
  2. Added example using the header-only interface for reconstructing surfaces from points randomly sampled from a sphere.
Version 15.01:
  1. Cleaned up interface into the reconstruction library.
Version 15.02:
  1. Changed Poisson and SSD to be classes for cleaner library interface in Reconstruction.example.cpp.
Version 15.03:
  1. Fixed --width bug in estimating scale factor.
Version 15.10:
  1. Added iso-curve extraction support (for 2D reconstruction)
Version 16.01:
  1. Added support for separte value interpolation in Poisson Surface Reconstruction
Version 16.02:
  1. Added support for additional .ply types
Version 16.03:
  1. Fixed --width compatibility bug with default depth.
Version 16.04:
  1. Fixed --exact bug.
Version 16.05:
  1. Fixed ChunkPly bug.