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 char* in_file = (argc > 2) ? argv[2] : "data/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>

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`. More...

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`. More...

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`. More...

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`. More...

template<class PolygonMesh , class NamedParameters >
void	CGAL::Subdivision_method_3::CatmullClark_subdivision (PolygonMesh &pmesh, const NamedParameters &np)
	applies Catmull-Clark subdivision several times on the control mesh `pmesh`. More...

template<class PolygonMesh >
void	CGAL::Subdivision_method_3::CatmullClark_subdivision (PolygonMesh &pmesh)

template<class PolygonMesh , class NamedParameters >
void	CGAL::Subdivision_method_3::Loop_subdivision (PolygonMesh &pmesh, const NamedParameters &np)
	applies Loop subdivision several times on the control mesh `pmesh`. More...

template<class PolygonMesh >
void	CGAL::Subdivision_method_3::Loop_subdivision (PolygonMesh &pmesh)

template<class PolygonMesh , class NamedParameters >
void	CGAL::Subdivision_method_3::DooSabin_subdivision (PolygonMesh &pmesh, const NamedParameters &np)
	applies DooSabin subdivision several times on the control mesh `pmesh`. More...

template<class PolygonMesh >
void	CGAL::Subdivision_method_3::DooSabin_subdivision (PolygonMesh &pmesh)

template<class PolygonMesh , class NamedParameters >
void	CGAL::Subdivision_method_3::Sqrt3_subdivision (PolygonMesh &pmesh, const NamedParameters &np)
	applies \( \sqrt{3}\)-subdivision several times on the control mesh `pmesh`. More...

template<class PolygonMesh >
void	CGAL::Subdivision_method_3::Sqrt3_subdivision (PolygonMesh &pmesh)

Function Documentation

◆ CatmullClark_subdivision()

template<class PolygonMesh , class NamedParameters >

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

#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

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.

the number of subdivision steps
Type: unsigned int
Default: 1

Precondition: pmesh must be a triangle mesh.

Examples:: Subdivision_method_3/CatmullClark_subdivision.cpp.

◆ DooSabin_subdivision()

template<class PolygonMesh , class NamedParameters >

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

#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

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.

the number of subdivision steps
Type: unsigned int
Default: 1

Examples:: Subdivision_method_3/DooSabin_subdivision.cpp.

◆ 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

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.

the number of subdivision steps
Type: unsigned int
Default: 1

Precondition: pmesh must be a triangle mesh.

◆ Loop_subdivision()

template<class PolygonMesh , class NamedParameters >

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

#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

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.

the number of subdivision steps
Type: unsigned int
Default: 1

Examples:: Subdivision_method_3/Loop_subdivision.cpp.

◆ 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

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.

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

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.

the number of subdivision steps
Type: unsigned int
Default: 1

Examples:: Subdivision_method_3/Customized_subdivision.cpp.

◆ 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

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.

the number of subdivision steps
Type: unsigned int
Default: 1

Precondition: pmesh must be a triangle mesh.

◆ Sqrt3_subdivision()

template<class PolygonMesh , class NamedParameters >

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

#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

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.

the number of subdivision steps
Type: unsigned int
Default: 1

Precondition: pmesh must be a triangle mesh.

Examples:: Subdivision_method_3/Sqrt3_subdivision.cpp.

Functions

Function Documentation

◆ CatmullClark_subdivision()

◆ DooSabin_subdivision()

◆ DQQ()

◆ Loop_subdivision()

◆ PQQ()

◆ PTQ()

◆ Sqrt3()

◆ Sqrt3_subdivision()