subdivision
Subdivision surfaces enable modelling of smooth surfaces using only a coarse control mesh. For example, the blue Doo-Sabin surface above is defined entirely by the positions of the 14 control vertices (gray). In fact, it is actually the surface "discovered" by repeatedly refining (subdividing) the control mesh (left to right).
The primary purpose of this repository is to enable straightforward use of subdivision surfaces by providing the code required for fast and exact evaluation of surface points and derivatives. Currently, only the code for Doo-Sabin subdivision surfaces is available, but the code for Loop subdivision surfaces will be added in due course.
Author: Richard Stebbing
License: MIT (refer to LICENSE).
Background
Uniform quadratic B-splines define smooth curves which are parameterised by a finite number of control vertices. Biquadratic B-splines and quadratic triangle B-splines are generalisations which define surfaces, where the influence of each control vertex is specified by its index in a regular quadrilateral or triangle mesh. For general meshes containing irregularities (e.g. non-quadrilateral faces, vertices with valency not equal to four/six) biquadratic and triangle B-splines cannot be applied directly. Instead, subdivision is necessary to refine the control mesh to "uncover" regular patches. To this end, the Doo-Sabin algorithm generalises biquadratic B-splines to general meshes, and the Loop subdivision algorithm generalises quadratic triangle B-splines to irregular triangle meshes.
Unlike their regular counterparts, evaluating positions and derivatives on Loop and Doo-Sabin subdivisions surfaces is more involved. This repository provides the code necessary to (a) understand subdivision surface evaluation, (b) enable straightforward adoption and evaluation of subdivision surfaces, and (c) verify properties of the first and second derivatives for each surface type.
Dependencies
Core:
- Eigen 3
- rstebbing/common
- Cython
- Numpy
- Sympy
- Scipy
Visualisation:
- matplotlib
- VTK
Doo-Sabin Subdivision Surfaces
Usage
C++
The Surface
class in doosabin.h implements the methods for evaluating positions and derivatives of points on a Doo-Sabin subdivision surface.
To build the test under cpp/doosabin:
- Run CMake with an out of source build.
- Set
EIGEN_INCLUDE_DIR
to the full path up to and including eigen3/. - Set
COMMON_CPP_INCLUDE_DIR
to the full path to rstebbing/common/cpp. (Add-std=c++11
toCMAKE_CXX_FLAGS
if compiling with gcc.) - Configure.
- Build.
Python
To build the Cython extension module and install subdivision
as a package (either globally or under a virtualenv):
- Set
EIGEN_INCLUDE
andCOMMON_CPP_INCLUDE
in site.cfg. - Build the Python package:
python setup.py build
. (Useexport CFLAGS=-std=c++11
beforehand if compiling with gcc.) - Install:
python setup.py install
.
To visualise the Doo-Sabin surface defined by a subdivided cube, from the examples directory and with rstebbing/common installed:
python doosabin/visualise_subdivision.py cube
More generally, to evaluate points uniformly distributed across a surface defined by the mesh T
and matrix of control vertices X
:
>>> import doosabin
>>> surface = doosabin.surface(T)
>>> pd, Ud, Td = surface.uniform_parameterisation(sample_density)
>>> M = surface.M(pd, Ud, X)
where sample_density
is a positive integer controlling the number of evaluated points and M
is the matrix of evaluated points.
Verification
From this directory:
-
Evaluate points on an extraordinary patch containing a face with
6
sides and show2
applications of Doo-Sabin subdivision:python verification/doosabin/evaluation.py 6 2
-
Show the magnitudes of the first and second derivative weight vectors (evaluated numerically) as the position being evaluated tends to the origin:
python verification/doosabin/derivatives_numeric.py 6 16
-
Evaluate the same vectors symbolically:
python verification/doosabin/derivatives_symbolic.py 6 16
Loop Subdivision Surfaces
Verification
From this directory:
-
Evaluate points on an extraordinary patch containing a vertex with valency
5
and show2
applications of Loop subdivision:python verification/loop/evaluation.py 5 2
-
Show the magnitudes of the first and second derivative weight vectors (evaluated numerically) as the position being evaluated tends to the origin:
python verification/loop/derivatives_numeric.py 5 16