If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondence between the coordinates in bc and the vertices of the face f is the following:
Given a set of barycentric coordinates, returns whether those barycentric coordinates correspond to a point within the face (boundary included), that is, if all the barycentric coordinates are positive.
returns the location of the given vertex vd as a location, that is an ordered pair specifying a face incident to vd and the barycentric coordinates of the vertex vd in that face.
returns the location of a given vertex as a location in fd, that is an ordered pair composed of fd and of the barycentric coordinates of the vertex in fd.
Given a point described by a halfedge hd and a scalar t as p = (1 - t) * source(hd, tm) + t * target(hd, tm), returns this location along the given edge as a location, that is an ordered pair specifying a face containing the location and the barycentric coordinates of that location in that face.
Given a point query and a face fd of a triangulated surface mesh, returns this location as a location, that is an ordered pair composed of fd and of the barycentric coordinates of query with respect to the vertices of fd.
Given a location and a second face adjacent to the first, returns the location of the point in the second face.
Nearest Face Location Queries
The following functions can be used to find the closest point on a triangle mesh, given either a point or a ray.
This closest point is computed using a CGAL::AABB_tree. Users intending to call location functions on more than a single point (or ray) should first compute an AABB tree to store it (otherwise, it will be recomputed every time). Note that since the AABB tree class is a 3D structure, it might be required to wrap your point property map to convert your point type to the 3D point type (i.e., your traits' Point_3) if you are working with a 2D triangle structure.
If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondence between the coordinates in bc and the vertices of the face f is the following:
w0 corresponds to source(halfedge(f, tm), tm)
w1 corresponds to target(halfedge(f, tm), tm)
w2 corresponds to target(next(halfedge(f, tm), tm), tm)
This function should first be called by users who intend to locate multiple points: in this case, it is better to first build an AABB tree, and use the function locate_with_AABB_tree() that takes as parameter an AABB tree, instead of calling locate() multiple times, which will build a new AABB tree on every call.
must be a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and the CGAL 3D point type (your traits' Point_3) as value type.
Extra: The geometric traits class must be compatible with the vertex point type.
Extra: If such traits class is provided, its type FT must be identical to the template parameter FT of this function.
Precondition
loc.first is a face descriptor corresponding to a face of tm.
Returns
a point whose type is the same as the value type of the vertex point property map provided by the user or via named parameters, or the internal point map of the mesh tm.
Given a location, returns a descriptor to the simplex of smallest dimension on which the point corresponding to the location lies.
In other words:
if the point lies on a vertex, this function returns a boost::graph_traits<TriangleMesh>::vertex_descriptorv;
if the point lies on a halfedge, this function returns a boost::graph_traits<TriangleMesh>::halfedge_descriptorhd (note that in that case, loc.first == face(hd, tm) holds).
otherwise, this function returns a boost::graph_traits<TriangleMesh>::face_descriptorfd (equal to loc.first).
loc.first is a face descriptor corresponding to a face of tm.
loc describes the barycentric coordinates of a point that lives within the face (boundary included), meaning the barycentric coordinates are all positive.
Given a set of barycentric coordinates, returns whether those barycentric coordinates correspond to a point within the face (boundary included), that is, if all the barycentric coordinates are positive.
If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondence between the coordinates in bc and the vertices of the face f is the following:
w0 corresponds to source(halfedge(f, tm), tm)
w1 corresponds to target(halfedge(f, tm), tm)
w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Given a location, returns whether the location is in the face (boundary included) or not.
If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondence between the coordinates in bc and the vertices of the face f is the following:
w0 corresponds to source(halfedge(f, tm), tm)
w1 corresponds to target(halfedge(f, tm), tm)
w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Given a location, returns whether the location is on the boundary of the face or not.
If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondence between the coordinates in bc and the vertices of the face f is the following:
w0 corresponds to source(halfedge(f, tm), tm)
w1 corresponds to target(halfedge(f, tm), tm)
w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Given a location, returns whether this location is on the halfedge hd or not.
If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondence between the coordinates in bc and the vertices of the face f is the following:
w0 corresponds to source(halfedge(f, tm), tm)
w1 corresponds to target(halfedge(f, tm), tm)
w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Given a location, returns whether the location is on the border of the mesh or not.
If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondence between the coordinates in bc and the vertices of the face f is the following:
w0 corresponds to source(halfedge(f, tm), tm)
w1 corresponds to target(halfedge(f, tm), tm)
w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Given a location, returns whether the location is on the vertex vd or not.
If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondence between the coordinates in bc and the vertices of the face f is the following:
w0 corresponds to source(halfedge(f, tm), tm)
w1 corresponds to target(halfedge(f, tm), tm)
w2 corresponds to target(next(halfedge(f, tm), tm), tm)
returns the nearest face location to the given point.
Note that this function will build an AABB tree on each call. If you need to call this function more than once, first use build_AABB_tree() to create a an AABB tree that you can store and use the function locate_with_AABB_tree().
Extra: The geometric traits class must be compatible with the vertex point type.
a tolerance value used to snap barycentric coordinates
Type: double
Default: 0
Extra: Depending on the geometric traits used, the computation of the barycentric coordinates might be an inexact construction, thus leading to sometimes surprising values (e.g. a triplet [0.5, 0.5, -1-e17] for a point at the middle of an edge). The coordinates will be snapped towards 0 and 1 if the difference is smaller than the tolerance value, while still ensuring that the total sum of the coordinates is 1.
returns the face location along ray nearest to its source point.
If the ray does not intersect the mesh, a default constructed location is returned.
Note that this function will build an AABB tree on each call. If you need to call this function more than once, use build_AABB_tree() to cache a copy of the AABB_tree, and use the overloads of this function that accept a reference to an AABB tree as input.
Extra: The geometric traits class must be compatible with the vertex point type.
a tolerance value used to snap barycentric coordinates
Type: double
Default: 0
Extra: Depending on the geometric traits used, the computation of the barycentric coordinates might be an inexact construction, thus leading to sometimes surprising values (e.g. a triplet [0.5, 0.5, -1-e17] for a point at the middle of an edge). The coordinates will be snapped towards 0 and 1 if the difference is smaller than the tolerance value, while still ensuring that the total sum of the coordinates is 1.
Precondition
ray is an object with the same ambient dimension as the point type (the value type of the vertex point map).
Given a location and a second face adjacent to the first, returns the location of the point in the second face.
If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondence between the coordinates in bc and the vertices of the face f is the following:
w0 corresponds to source(halfedge(f, tm), tm)
w1 corresponds to target(halfedge(f, tm), tm)
w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Given a point query and a face fd of a triangulated surface mesh, returns this location as a location, that is an ordered pair composed of fd and of the barycentric coordinates of query with respect to the vertices of fd.
If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondence between the coordinates in bc and the vertices of the face f is the following:
w0 corresponds to source(halfedge(f, tm), tm)
w1 corresponds to target(halfedge(f, tm), tm)
w2 corresponds to target(next(halfedge(f, tm), tm), tm)
a point, whose type is equal to the value type of the vertex point property map (either user-provided via named parameters or the internal point map of the mesh tm)
fd
a face of tm
tm
a triangulated surface 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 tm
Type: a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and Point_3 as value type
Extra: The geometric traits class must be compatible with the vertex point type.
Extra: If such traits class is provided, its type FT must be identical to the template parameter FT of this function.
a tolerance value used to snap barycentric coordinates
Type: double
Default: 0
Extra: Depending on the geometric traits used, the computation of the barycentric coordinates might be an inexact construction, thus leading to sometimes surprising values (e.g. a triplet [0.5, 0.5, -1-e17] for a point at the middle of an edge). The coordinates will be snapped towards 0 and 1 if the difference is smaller than the tolerance value, while still ensuring that the total sum of the coordinates is 1.
Precondition
fd is not the null face
Returns
a face location. The type FT is deduced from the geometric traits, either provided by the user via named parameters (with geom_traits) or using CGAL::Kernel_traits and the point type of the vertex point property map in use.
Given a point described by a halfedge hd and a scalar t as p = (1 - t) * source(hd, tm) + t * target(hd, tm), returns this location along the given edge as a location, that is an ordered pair specifying a face containing the location and the barycentric coordinates of that location in that face.
If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondence between the coordinates in bc and the vertices of the face f is the following:
w0 corresponds to source(halfedge(f, tm), tm)
w1 corresponds to target(halfedge(f, tm), tm)
w2 corresponds to target(next(halfedge(f, tm), tm), tm)
returns the location of a given vertex as a location in fd, that is an ordered pair composed of fd and of the barycentric coordinates of the vertex in fd.
If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondence between the coordinates in bc and the vertices of the face f is the following:
w0 corresponds to source(halfedge(f, tm), tm)
w1 corresponds to target(halfedge(f, tm), tm)
w2 corresponds to target(next(halfedge(f, tm), tm), tm)
returns the location of the given vertex vd as a location, that is an ordered pair specifying a face incident to vd and the barycentric coordinates of the vertex vd in that face.
If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondence between the coordinates in bc and the vertices of the face f is the following:
w0 corresponds to source(halfedge(f, tm), tm)
w1 corresponds to target(halfedge(f, tm), tm)
w2 corresponds to target(next(halfedge(f, tm), tm), tm)
returns the face location nearest to the given point, as a location.
Note that it is possible for the triangle mesh to have ambiant dimension 2 (e.g. the mesh is a 2D triangulation, or a CGAL::Surface_mesh<CGAL::Point_2<Kernel> >), as long as an appropriate vertex point property map is passed in the AABB tree, which will convert from 2D to 3D.
must be a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and the CGAL 3D point type (your traits' Point_3) as value type.
Extra: The geometric traits class must be compatible with the vertex point type.
Extra: Must be identical to the traits used in the template parameter of the AABB_traits.
a tolerance value used to snap barycentric coordinates
Type: double
Default: 0
Extra: Depending on the geometric traits used, the computation of the barycentric coordinates might be an inexact construction, thus leading to sometimes surprising values (e.g. a triplet [0.5, 0.5, -1-e17] for a point at the middle of an edge). The coordinates will be snapped towards 0 and 1 if the difference is smaller than the tolerance value, while still ensuring that the total sum of the coordinates is 1.
Returns
a face location. The type FT is deduced from the geometric traits, either provided by the user via named parameters (with geom_traits) or using CGAL::Kernel_traits and the point type of the vertex point property map in use.
must be a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and the CGAL 3D point type (your traits' Point_3) as value type.
Extra: The geometric traits class must be compatible with the vertex point type.
Extra: Must be identical to the traits used in the template parameter of the AABB_traits.
a tolerance value used to snap barycentric coordinates
Type: double
Default: 0
Extra: Depending on the geometric traits used, the computation of the barycentric coordinates might be an inexact construction, thus leading to sometimes surprising values (e.g. a triplet [0.5, 0.5, -1-e17] for a point at the middle of an edge). The coordinates will be snapped towards 0 and 1 if the difference is smaller than the tolerance value, while still ensuring that the total sum of the coordinates is 1.
Precondition
ray is an object with the same ambient dimension as the point type (the value type of the vertex point map).
returns a random point over the face fd, as a location.
The random point is on the face, meaning that all its barycentric coordinates are positive. It is constructed by uniformly picking a value u between 0 and 1, a value v between 1-u, and setting the barycentric coordinates to u, v, and 1-u-v for respectively the source and target of halfedge(fd, tm), and the third point.
returns a random point over the halfedge hd, as a location.
The random point is chosen on the halfedge, meaning that all its barycentric coordinates are positive. It is constructed by uniformly generating a value t between 0 and 1 and setting the barycentric coordinates to t, 1-t, and 0 for respetively the source and target of hd, and the third vertex.
The returned location is obtained by choosing a random face of the mesh and a random point on that face. The barycentric coordinates of the point in the face are thus all positive. Note that all faces have the same probability to be chosen.
1.9.6