CGAL 5.3 - 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.

Example

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

#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 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)

## ◆ 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::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::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::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::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::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::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::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::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.