CGAL 5.5.2 - 3D Surface 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.

RefSchemes.svg

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/Timer.h>
#include <boost/lexical_cast.hpp>
#include <iostream>
#include <fstream>
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>

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

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
PolygonMesha model of MutableFaceGraph
NamedParametersa sequence of Named Parameters
Parameters
pmesha polygon mesh
npan 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 = 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
PolygonMesha model of MutableFaceGraph
NamedParametersa sequence of Named Parameters
Parameters
pmesha polygon mesh
npan 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
PolygonMesha model of MutableFaceGraph
Maska model of DQQMask_3
NamedParametersa sequence of Named Parameters
Parameters
pmesha polygon mesh
maska geometry policy mask
npan 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 = 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
PolygonMesha model of MutableFaceGraph
NamedParametersa sequence of Named Parameters
Parameters
pmesha polygon mesh
npan 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
PolygonMesha model of MutableFaceGraph
Maska model of PQQMask_3
NamedParametersa sequence of Named Parameters
Parameters
pmesha polygon mesh
maska geometry policy mask
npan 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
PolygonMesha model of MutableFaceGraph
Maska model of PTQMask_3
NamedParametersa sequence of Named Parameters
Parameters
pmesha polygon mesh
maska geometry policy mask
npan 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
PolygonMesha model of MutableFaceGraph
Maska model of Sqrt3Mask_3
NamedParametersa sequence of Named Parameters
Parameters
pmesha polygon mesh
maska geometry policy mask
npan 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 = 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
PolygonMesha model of MutableFaceGraph
NamedParametersa sequence of Named Parameters
Parameters
pmesha polygon mesh
npan 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.