Subdivision Methods

A subdivision method recursively refines a coarse mesh and generates an ever closer approximation to a smooth surface.

Subdivision_method_3 consists of four subdivision methods and their refinement hosts. Each refinement host is a template function of a polygon mesh class and a geometry policy class. It refines the connectivity of the control mesh and computes the geometry of the refined mesh. The geometry computation is dedicated to the custom geometry policy. A geometry policy consists of functions that compute the new point based on the subdivision stencil. A stencil defines the footprint (a submesh of the control mesh) of a new point.

The four supported refinement hosts are the primal quadrilateral quadrisection (PQQ), the primal triangle quadrisection (PTQ), the dual quadrilateral quadrisection (DQQ), and the \( \sqrt{3}\) triangulation. These refinements are respectively used in Catmull-Clark, Loop, Doo-Sabin and \( \sqrt{3}\) subdivisions.

Refinement Host

A refinement host is a template function of a polygon mesh class and a geometry mask class. It refines the input polygon mesh, and computes new points through the geometry masks. Subdivision_method_3 supports four refinement hosts: PQQ, PTQ, DQQ and Sqrt3.

Example

This example program subdivides a polygonal mesh with Catmull-Clark subdivision.

File Subdivision_method_3/CatmullClark_subdivision.cpp

#include <CGAL/Simple_cartesian.h>
 
#include <CGAL/Surface_mesh.h>
#include <CGAL/boost/graph/graph_traits_Surface_mesh.h>
 
#include <CGAL/subdivision_method_3.h>
#include <CGAL/Timer.h>
 
#include <boost/lexical_cast.hpp>
 
#include <iostream>
#include <fstream>
 
typedef CGAL::Simple_cartesian<double>         Kernel;
typedef CGAL::Surface_mesh<Kernel::Point_3>    PolygonMesh;
 
using namespace std;
using namespace CGAL;
namespace params = CGAL::parameters;
 
int main(int argc, char** argv) {
  if (argc > 4) {
    cerr << "Usage: CatmullClark_subdivision [d] [filename_in] [filename_out] \n";
    cerr << "         d -- the depth of the subdivision (default: 1) \n";
    cerr << "         filename_in -- the input mesh (.off) (default: data/quint_tris.off) \n";
    cerr << "         filename_out -- the output mesh (.off) (default: result.off)" << endl;
    return 1;
  }
 
  int d = (argc > 1) ? boost::lexical_cast<int>(argv[1]) : 1;
  const std::string in_file = (argc > 2) ? argv[2] : CGAL::data_file_path("meshes/quint_tris.off");
  const char* out_file = (argc > 3) ? argv[3] : "result.off";
 
  PolygonMesh pmesh;
  std::ifstream in(in_file);
  if(in.fail()) {
    std::cerr << "Could not open input file " << in_file << std::endl;
    return 1;
  }
  in >> pmesh;
 
  Timer t;
  t.start();
  Subdivision_method_3::CatmullClark_subdivision(pmesh, params::number_of_iterations(d));
  std::cerr << "Done (" << t.time() << " s)" << std::endl;
 
  std::ofstream out(out_file);
  out << pmesh;
 
  return 0;
}

See also

CGAL::CatmullClark_mask_3<PolygonMesh>

CGAL::DooSabin_mask_3<PolygonMesh

CGAL::Loop_mask_3<PolygonMesh

CGAL::Sqrt3_mask_3<PolygonMesh>

CGAL::Linear_mask_3<PolygonMesh>

Functions
template<class PolygonMesh , class Mask , class NamedParameters >
void	CGAL::Subdivision_method_3::PQQ (PolygonMesh &pmesh, Mask mask, const NamedParameters &np)
	applies the PQQ refinement several times on the control mesh pmesh.
template<class PolygonMesh , class Mask , class NamedParameters >
void	CGAL::Subdivision_method_3::PTQ (PolygonMesh &pmesh, Mask mask, const NamedParameters &np)
	applies the PTQ refinement several times on the control mesh pmesh.
template<class PolygonMesh , class Mask , class NamedParameters >
void	CGAL::Subdivision_method_3::DQQ (PolygonMesh &pmesh, Mask mask, const NamedParameters &np)
	applies the DQQ refinement several times on the control mesh pmesh.
template<class PolygonMesh , class Mask , class NamedParameters >
void	CGAL::Subdivision_method_3::Sqrt3 (PolygonMesh &pmesh, Mask mask, const NamedParameters &np)
	applies the \( \sqrt{3}\) refinement several times on the control mesh pmesh.
template<class PolygonMesh , class NamedParameters = parameters::Default_named_parameters>
void	CGAL::Subdivision_method_3::CatmullClark_subdivision (PolygonMesh &pmesh, const NamedParameters &np=parameters::default_values())
	applies Catmull-Clark subdivision several times on the control mesh pmesh.
template<class PolygonMesh , class NamedParameters = parameters::Default_named_parameters>
void	CGAL::Subdivision_method_3::Loop_subdivision (PolygonMesh &pmesh, const NamedParameters &np=parameters::default_values())
	applies Loop subdivision several times on the control mesh pmesh.
template<class PolygonMesh , class NamedParameters = parameters::Default_named_parameters>
void	CGAL::Subdivision_method_3::DooSabin_subdivision (PolygonMesh &pmesh, const NamedParameters &np=parameters::default_values())
	applies DooSabin subdivision several times on the control mesh pmesh.
template<class PolygonMesh , class NamedParameters = parameters::Default_named_parameters>
void	CGAL::Subdivision_method_3::Sqrt3_subdivision (PolygonMesh &pmesh, const NamedParameters &np=parameters::default_values())
	applies \( \sqrt{3}\)-subdivision several times on the control mesh pmesh.

Function Documentation

CatmullClark_subdivision()

template<class PolygonMesh , class NamedParameters = parameters::Default_named_parameters>

void CGAL::Subdivision_method_3::CatmullClark_subdivision	(	PolygonMesh &	pmesh,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Subdivision_method_3/subdivision_methods_3.h>

applies Catmull-Clark subdivision several times on the control mesh pmesh.

The geometry of the refined mesh is computed by the geometry policy mask CatmullClark_mask_3. This function overwrites the control mesh pmesh with the subdivided mesh.

Template Parameters

PolygonMesh	a model of MutableFaceGraph
NamedParameters	a sequence of Named Parameters

Parameters

pmesh	a polygon mesh
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

vertex_point_map a property map associating points to the vertices of pmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, pmesh) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available for the vertices of pmesh.
number_of_iterations the number of subdivision steps Type: unsigned int Default: 1
do_not_modify_geometry if set to true, the geometry of the mesh will not be modified Type: Boolean Default: false Extra: If pmesh is in fact a triangle mesh, this named parameter is also available in Loop subdivision and will create better shaped elements.

Examples

Subdivision_method_3/Linear_subdivision.cpp.

DooSabin_subdivision()

template<class PolygonMesh , class NamedParameters = parameters::Default_named_parameters>

void CGAL::Subdivision_method_3::DooSabin_subdivision	(	PolygonMesh &	pmesh,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Subdivision_method_3/subdivision_methods_3.h>

applies DooSabin subdivision several times on the control mesh pmesh.

The geometry of the refined mesh is computed by the geometry policy mask DooSabin_mask_3. This function overwrites the control mesh pmesh with the subdivided mesh.

Template Parameters

PolygonMesh	a model of MutableFaceGraph
NamedParameters	a sequence of Named Parameters

Parameters

pmesh	a polygon mesh
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

vertex_point_map a property map associating points to the vertices of pmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, pmesh) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available for the vertices of pmesh.
number_of_iterations the number of subdivision steps Type: unsigned int Default: 1

DQQ()

template<class PolygonMesh , class Mask , class NamedParameters >

void CGAL::Subdivision_method_3::DQQ	(	PolygonMesh &	pmesh,
		Mask	mask,
		const NamedParameters &	np
	)

#include <CGAL/Subdivision_method_3/subdivision_hosts_3.h>

applies the DQQ refinement several times on the control mesh pmesh.

The geometry of the refined mesh is computed by the geometry policy mask. This function overwrites the control mesh pmesh with the refined mesh.

Template Parameters

PolygonMesh	a model of MutableFaceGraph
Mask	a model of DQQMask_3
NamedParameters	a sequence of Named Parameters

Parameters

pmesh	a polygon mesh
mask	a geometry policy mask
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

vertex_point_map a property map associating points to the vertices of pmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, pmesh) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available for the vertices of pmesh.
number_of_iterations the number of subdivision steps Type: unsigned int Default: 1

Precondition

pmesh must be a triangle mesh.

Loop_subdivision()

template<class PolygonMesh , class NamedParameters = parameters::Default_named_parameters>

void CGAL::Subdivision_method_3::Loop_subdivision	(	PolygonMesh &	pmesh,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Subdivision_method_3/subdivision_methods_3.h>

applies Loop subdivision several times on the control mesh pmesh.

The geometry of the refined mesh is computed by the geometry policy mask Loop_mask_3. This function overwrites the control mesh pmesh with the subdivided mesh.

Template Parameters

PolygonMesh	a model of MutableFaceGraph
NamedParameters	a sequence of Named Parameters

Parameters

pmesh	a polygon mesh
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

vertex_point_map a property map associating points to the vertices of pmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, pmesh) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available for the vertices of pmesh.
number_of_iterations the number of subdivision steps Type: unsigned int Default: 1
do_not_modify_geometry if set to true, the geometry of the mesh will not be modified Type: Boolean Default: false Extra: This named parameter is also available in Catmull-Clark subdivision for non-triangle meshes.

Precondition

pmesh must be a triangle mesh.

PQQ()

template<class PolygonMesh , class Mask , class NamedParameters >

void CGAL::Subdivision_method_3::PQQ	(	PolygonMesh &	pmesh,
		Mask	mask,
		const NamedParameters &	np
	)

#include <CGAL/Subdivision_method_3/subdivision_hosts_3.h>

applies the PQQ refinement several times on the control mesh pmesh.

The geometry of the refined mesh is computed by the geometry policy mask. This function overwrites the control mesh pmesh with the refined mesh.

Template Parameters

PolygonMesh	a model of MutableFaceGraph
Mask	a model of PQQMask_3
NamedParameters	a sequence of Named Parameters

Parameters

pmesh	a polygon mesh
mask	a geometry policy mask
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

vertex_point_map a property map associating points to the vertices of pmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, pmesh) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available for the vertices of pmesh.
number_of_iterations the number of subdivision steps Type: unsigned int Default: 1

PTQ()

template<class PolygonMesh , class Mask , class NamedParameters >

void CGAL::Subdivision_method_3::PTQ	(	PolygonMesh &	pmesh,
		Mask	mask,
		const NamedParameters &	np
	)

#include <CGAL/Subdivision_method_3/subdivision_hosts_3.h>

applies the PTQ refinement several times on the control mesh pmesh.

The geometry of the refined mesh is computed by the geometry policy mask. This function overwrites the control mesh pmesh with the refined mesh.

Template Parameters

PolygonMesh	a model of MutableFaceGraph
Mask	a model of PTQMask_3
NamedParameters	a sequence of Named Parameters

Parameters

pmesh	a polygon mesh
mask	a geometry policy mask
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

vertex_point_map a property map associating points to the vertices of pmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, pmesh) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available for the vertices of pmesh.
number_of_iterations the number of subdivision steps Type: unsigned int Default: 1

Sqrt3()

template<class PolygonMesh , class Mask , class NamedParameters >

void CGAL::Subdivision_method_3::Sqrt3	(	PolygonMesh &	pmesh,
		Mask	mask,
		const NamedParameters &	np
	)

#include <CGAL/Subdivision_method_3/subdivision_hosts_3.h>

applies the \( \sqrt{3}\) refinement several times on the control mesh pmesh.

The geometry of the refined mesh is computed by the geometry policy mask. This function overwrites the control mesh pmesh with the refined mesh.

Attention

The border subdivision only happens every second subdivision step during a single call of this function.

Template Parameters

PolygonMesh	a model of MutableFaceGraph
Mask	a model of Sqrt3Mask_3
NamedParameters	a sequence of Named Parameters

Parameters

pmesh	a polygon mesh
mask	a geometry policy mask
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

vertex_point_map a property map associating points to the vertices of pmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, pmesh) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available for the vertices of pmesh.
number_of_iterations the number of subdivision steps Type: unsigned int Default: 1

Precondition

pmesh must be a triangle mesh.

Sqrt3_subdivision()

template<class PolygonMesh , class NamedParameters = parameters::Default_named_parameters>

void CGAL::Subdivision_method_3::Sqrt3_subdivision	(	PolygonMesh &	pmesh,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Subdivision_method_3/subdivision_methods_3.h>

applies \( \sqrt{3}\)-subdivision several times on the control mesh pmesh.

The geometry of the refined mesh is computed by the geometry policy mask Sqrt3_mask_3. This function overwrites the control mesh pmesh with the subdivided mesh.

Attention

The border subdivision only happens every second subdivision step during a single call of this function.

Template Parameters

PolygonMesh	a model of MutableFaceGraph
NamedParameters	a sequence of Named Parameters

Parameters

pmesh	a polygon mesh
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

vertex_point_map a property map associating points to the vertices of pmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, pmesh) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available for the vertices of pmesh.
number_of_iterations the number of subdivision steps Type: unsigned int Default: 1

Precondition

pmesh must be a triangle mesh.