triangulate_object_model_3d — Create a surface triangulation for a 3D object model.
triangulate_object_model_3d( : : ObjectModel3D, Method, GenParamName, GenParamValue : TriangulatedObjectModel3D, Information)
The operator triangulate_object_model_3d generates a surface of
triangular faces for the 3D object model ObjectModel3D and
returns the resulting surface in TriangulatedObjectModel3D.
Currently, the operator offers four methods for the triangulation that
can be selected in Method: 'polygon_triangulation',
'xyz_mapping', 'greedy' and 'implicit'.
'polygon_triangulation'
is a simple method for the conversion of a polygonal to a triangular face
representation in a 3D object model.
'xyz_mapping' triangulates the points in 2D according to a 2D
mapping. The other two methods are rather
complex algorithms that are used to calculate triangular faces from pure
3D point data with unknown surface topology. A detailed comparison of
the 'greedy' and 'implicit' algorithm is provided in the
paragraph "Comparison of the triangulation methods" below.
By selecting Method='polygon_triangulation',
all polygons in ObjectModel3D are triangulated.
No generic parameters are supported for this method. If no polygons are
available, an exception is raised. A triangular mesh representing the
same surface as ObjectModel3D is returned in
TriangulatedObjectModel3D.
By selecting Method='xyz_mapping', the points are
triangulated in 2D according to a 2D mapping contained in
ObjectModel3D. The used method is the same as in
prepare_object_model_3d for Purpose='segmentation'.
If no 2D mapping is available, an exception is raised.
By setting GenParamName to the following value, the additional
parameter specific for the 2D mapping triangulation can be set with
GenParamValue:
specifies which area holes of the point coordinates are closed during
a simple Delaunay triangulation. Only holes which are completely
surrounded by the image region are closed. If
'xyz_mapping_max_area_holes' is set to 0, no holes are triangulated.
The parameter corresponds to the GenParamName
'max_area_holes' of prepare_object_model_3d.
Suggested values: 1, 10
(default), 100
By selecting Method='greedy', a so called greedy
triangulation algorithm is invoked. It requires 3D point data containing
normals. If ObjectModel3D does not contain the normals, they are
calculated internally, in an identical manner to calling
surface_normals_object_model_3d with its default parameters before
triangulation. The algorithm constructs a surface, which passes through the
points and whose surface normals must be conform to the corresponding point
normals up to a given tolerance. The surface is represented by triangular
faces, which are constructed from triplets of neighboring points.
In order to determine which triplets qualify for a surface triangle, the
algorithm applies for each point pair the following local neighborhood test,
denoted as surface neighborhood criteria (SNC):
If a point P is lying on a surface, with N being the orientation (normal) of the surface, then a point P' with normal N' is considered to lay on this surface if:
the distance between both points is smaller or equal to
r, i.e.,
both normals have similar orientation, i.e., the angle or - if no strict consistency of the normals is enforced -
the vector is close to orthogonal with respect to N, i.e., the angle
if P' does not meet 3. but it is not further away from
the plane defined by [P,N] than d,
then it is accepted as well.
The four parameters r (see 'greedy_radius_type'
and 'greedy_radius_value'),
(see 'greedy_neigh_orient_tol'),
(see 'greedy_neigh_latitude_tol'), and d
(see 'greedy_neigh_vertical_tol') control the criteria and have
the following meaning:
The parameter essentially controls the curvature of the generated surface: for small values of the generated surface will be locally flatter; larger values of permit the generation of more curved surface fragments.
The other three parameters define a portion of a sphere that defines
the valid SNC neighborhood. The sphere has a radius r,
it is centered in P, and its equatorial plane is incident with
the plane [P,N]. Only points that are within the sphere
(first SNC criteria) are considered. Furthermore, they need to have a
latitude within [-; ]
(third SNC criteria) with respect to the equator unless they are lying
within the thin layer defined on the both sides of the equatorial plane
by the distance parameter d (fourth SNC criteria).
In contrast, points lying in any of both pole segments of the
sphere (i.e., with higher latitude than and
a distance from the equatorial plane beyond d)
are not considered as neighbors.
The parameter r prevents the algorithm from constructing
too big triangles. This is particularly important for point sets that
represent several disconnected surface pieces or a surface with holes
that must not be closed. The latitude window defined by
enables neighbors which deviate from
[P,N] due to noise or curvature to be considered as well.
Similarly, the parameter d enables neighbors
right "above" or "below" the equatorial plane to be accepted, which
essentially accounts for data noise.
Here are some advices for selecting the appropriate values for these parameters:
If the resulting surface triangulation looks very disconnected or
exhibits many holes, this might be a hint that r
is too small and thus restricts the generation of triangles that
are large enough to close the holes. Try to increase
r.
If the normals data is noisy (i.e., neighboring normals are deviating to a large extend from each other), then increase . The source of noisy normals is typically caused either by the sensor, which delivers both the point and the normals data, or an imprecise normals estimation routine, which computes the normals from the point data.
If the point data represents a very curved surface, i.e., it exhibits a very fine structure like, e.g., little buckles, fine waves or folds, or sharp turns, then make sure the generation of curved data is facilitated by an increasing and/or .
In contrast, if the data is rather planar but has lots of outliers (i.e., points laying next to the surface, which have completely different orientations and thus most probably do not belong to it), then decrease to exclude them from the surface generation.
If the point data is very noisy and resembles more a crust than a
single-layer surface, then increase
and/or d to make sure that neighbors for
P can still be found even if they are further away from
the optimal plane [P,N].
In contrast, if the data is rather noise-free, but two surfaces are
running close to each other and are nearly parallel, e.g., surfaces
representing the front and the back side of a thin, plate-like
object, then decrease and
d to avoid interference between the surfaces.
The greedy triangulation algorithm starts by initializing a
surface with one triangle constructed from three SNC-eligible, neighboring
points. If all valid neighborhoods show local inconsistencies like collinear
or 'double' points, an error will be raised. A prior call of
sample_object_model_3d with Method set to 'fast' and a small
SampleDistance will remove most local inconsistencies from
ObjectModel3D. Having found one triangle, the algorithm
then greedily constructs new triangles as long as further
points can be reached by the SNC rules from any point on the surface
boundaries. If no points can be reached from the current surface, but
there are unprocessed points in the 3D object model, a new surface is
initialized. Because the SNC rules are essentially defined only in the
small local neighborhoods of the points, the resulting surface can have
global topological artifacts like holes and flips. The latter occur,
when - while it is growing - a surface meets itself but with inverted
face orientations (i.e., the surface was flipped somewhere while
it was growing). These artifacts are handled in special post-processing
steps: hole filling and flip resolval, respectively.
Finally, a mesh morphology can be performed to additionally remove artifacts that occurred on the final surface boundaries. The mesh morphology consists of several mesh erosion cycles and several subsequent mesh dilation cycles. With each erosion cycle, all triangles reachable from the surface boundaries are removed and the surface boundaries shrink. Then, with each dilation cycle all triangles reachable from the surface boundaries are appended again to the surface and the boundaries expand. Note that this is only possible for triangles, which were removed by an erosion cycle before that. Therefore, once the original boundaries of the surface (i.e., those which existed before the mesh erosion cycles) are reached, the dilation cannot advance any further and hence the dilation cycles cannot be more than the erosion cycles. Applying mesh erosion and dilation subsequently is analogous to performing opening to standard HALCON regions. At last, the mesh morphology can delete surface pieces which have too few triangles.
The individual algorithm steps are summarized here:
Triangulation of all points reachable by SNC
Hole filling (see 'greedy_hole_filling')
Flip resolval (see 'greedy_fix_flips')
Mesh morphology (see 'greedy_mesh_erosion', 'greedy_mesh_dilation', and 'greedy_remove_small_surfaces')
By setting GenParamName to one of the following values, additional
parameters specific for the greedy triangulation can be set with
GenParamValue:
specifies the size k of the neighborhood. While
looking for reachable SNC neighbors for a surface boundary point, the
algorithm considers only its closest k neighbors.
Suggested values: 20, 30, 40
(default), 50, 60
if set to 'fixed','greedy_radius_value' specifies the
SNC radius r in meter units.
If set to 'z_factor', r is calculated for
each point P by multiplying its z-coordinate by the value
specified by 'greedy_radius_value'. This representation of
r is appropriate for data where the density of the
points correlates with their distance from the sensor they were
recorded with. This is typically the case with depth sensors or TOF
cameras.
If set to 'auto', the algorithm determines internally whether to use a 'fixed' or a 'z_factor' radius and estimates its value. The estimated value is then multiplied by the value specified in 'greedy_radius_value'. This way, the user specifies a scale factor for the estimated radius.
List of values: 'auto' (default),
'fixed', 'z_factor'
see 'greedy_radius_type'.
Suggested values: 0.01, 0.05, 0.5,
0.66, 1.0, 1.5,
2.0, 3.0, 4.0
sets the SNC parameter in degree units. controls the surface curvature as described with the SNC rules above.
Suggested values: 10, 20, 30
(default), 40
enforces that the normals of two neighboring points have the same orientation (i.e., they do not show in opposite directions). If enabled, this parameter disables the second part of the SNC criteria for , i.e., if , the criteria fails even if .
List of values: 'true', 'false'
(default)
sets the SNC parameter in degree units. controls the surface neighborhood latitude window as described with the SNC rules above.
Suggested values: 10, 20, 30
(default), 40
sets the SNC parameter d as a factor of the radius
r.
Suggested values: 0.01, 0.1
(default), 0.2, 0.3
sets the length of surface boundaries (in number of point vertices) that should be considered for the hole filling. If 'false' is specified, then the hole filling step is disabled.
Suggested values: 'false',
20, 40 (default),
60
enables/disables the flip resolving step of the algorithm.
List of values: 'true' (default),
'false'
enables/disables prefetching of lists of the k nearest neighbors for all
points. This prefetching improves the algorithm speed, but has high
memory requirements (O(k*n), where k
is the number specified by 'greedy_kNN', and
n is the number of points in ObjectModel3D).
For very large data, it might be impossible to preallocate such a big
amount of memory, results in a memory error message. In such a case the
prefetching must be disabled.
List of values: 'true' (default),
'false'
specifies the number of erosion cycles applied to the final mesh.
Suggested values: 0 (default),
1, 2, 3
specifies the number of dilation cycles. The mesh dilation is applied after the mesh erosion. If 'greedy_mesh_dilation' is set to a greater value than 'greedy_mesh_erosion', it will be reduced internally to the value of 'greedy_mesh_erosion'.
Suggested values: 0 (default),
1, 2, 3
controls the criteria for removing small surface pieces.
If set to 'false', the small surface removal is disabled. If
set to a value between 0.0 and 1.0, all surfaces
having less triangles than
'greedy_remove_small_surfaces'xnum_triangles
will be removed, where num_triangles is the total number
of triangles generated by the algorithm.
If set to a value greater than 1, all surfaces having less
triangles than 'greedy_remove_small_surfaces' will be removed.
Suggested values: 'false' (default),
0.01, 0.05, 0.1,
10, 100, 1000,
10000
using a timeout, it is possible to interrupt the operator after a
defined period of time in seconds. This is especially useful in cases,
where a maximum cycle time has to be ensured. The temporal accuracy of
this interrupt is about 10 ms. Passing values less then zero is not
valid. Setting 'greedy_timeout' to 'false' deactivates
the timeout, which corresponds to the default. The temporal accuracy
depends on several factors including
the size of the model, the speed of your computer, and the
'timer_mode' set via set_system.
Suggested values: 'false' (default),
0.1, 0.5, 1,
10, 100
by default, if a timeout occurs the operator returns a timeout error
code. By setting 'greedy_suppress_timeout_error' to
'true' instead, the operator returns no error and the
intermediate results of the triangulation are returned in
TriangulatedObjectModel3D. With the error suppressed, the
occurrence of a timeout can be checked by querying the list of values
returned in Information (in 'verbose' mode) by
looking for the value corresponding to 'timeout_occured'.
List of values: 'false' (default),
'true'
specifies, which intermediate results shall be reported in
Information. By default
('information'='num_triangles'), the number of
generated triangles is reported. For
'information'='verbose', a list of name-value
information pairs is returned. Currently, the following information
is reported:
Name Value Description
----------------------- ----------------------------------- -------------------------------------------------------
num_triangles <number of triangles> reports the number of generated triangular faces.
specified_radius_type auto | fixed | z_factor | none reports the radius type as specified by the user.
specified_radius_value <specified radius value> reports the radius value specified by the user.
used_radius_type fixed | z_factor | sampling reports the radius type used internally; if the user
specified 'auto' for 'specified_radius_type', this
field reports the radius type that was selected
internally; if ObjectModel3D is a 3D primitive, the
user specified radius value is internally used as a
sampling step and 'used_radius_type' reports
'sampling'.
used_radius_value <used radius value> reports the radius value used internally;
if 'used_radius_type'='fixed', then the absolute
neighborhood radius in meters is reported;
if 'used_radius_type'='z_factor', the multiplication
factor is reported, which is used to compute the
neighborhood radius from the z-coordinate of the
neighborhood center point;
if 'used_radius_type'='sampling', the sub-sampling
factor is reported, which is used to generate the
triangulation of 3D primitives, in particular:
cylinder and sphere.
neigh_orient_tol <alpha> reports the surface curvature parameter 'alpha' in
degrees that was used for the triangulation.
neigh_latitude_tol <beta> reports the angular tolerance window 'beta' in degrees
that was used to select surface neighbors.
neigh_vertical_tol <d> reports the neighborhood parameter 'd' as a factor of
the used radius.
fix_flips true | false reports whether the flip fixing was enabled.
hole_filling false | <max hole boundary length> reports 'false' when the hole filling was disabled, or
the specified maximal hole boundary length number of
points.
timeout false | <timeout> reports 'false' when the timeout was disabled, or the
specified timeout in seconds.
timeout_occured yes | no reports whether a timeout occurred.
List of values: 'num_triangles' (default),
'verbose'
By selecting Method='implicit' an implicit triangulation
algorithm based on a Poisson solver (see the paper in References) is
invoked. It constructs a water-tight surface, i.e., it is completely closed.
The implicit triangulation requires 3D point data containing normals.
Additionally, it is required that the 3D normals are pointing strictly
inwards or strictly outwards regarding the volume enclosed by the surface
to be reconstructed. Unlike the 'greedy' algorithm, the
'implicit' algorithm does not construct the surface through the
input 3D points. Instead, it constructs a surface that approximates the
original 3D data and creates a new set of 3D points lying on this surface.
First, the algorithm organizes the point data in an adaptive octree structure: the volume of the bounding box containing the point data is split in the middle in each dimension resulting in eight sub-volumes, or octree voxels. Voxels still containing enough point data can be split in further eight sub-voxels. Voxels that contain no or just few points must not be split further. This splitting is repeated recursively in regions of dense 3D point data until the resulting voxels contain no or just few points. The recursion level of the voxel splits, reached with the smallest voxels, is denoted as depth of the octree.
In the next step, the algorithm estimates the values of the so-called
implicit indicator function of the surface, based on the assumption
that the points from ObjectModel3D are lying on the surface of an
object and the normals of the points in ObjectModel3D are pointing
inwards that object (see the paper in References). This assumption explains
the requirement of mutually consistent normal orientations. The implicit
function has a value of 1 in voxel corners that are strictly inside the
body and 0 for voxel corners strictly outside of it. Due to noisy data,
voxel corners that are close to the boundary of the object cannot be
'labeled' unambiguously. Therefore, they receive a value between 0 and 1.
The implicit surface defined by the indicator function is a
surface, such that each point lying on it has an indicator value of
0.5. The implicit algorithm uses a standard marching cubes
algorithm to compute the intersection points of the implicit surface with
the sides of the octree voxels. The intersection points result in the
new set of 3D points spanning the surface returned in
TriangulatedObjectModel3D. As a consequence, the resolution of
the surface details reconstructed in TriangulatedObjectModel3D
depends directly on the resolution of the octree (i.e., on its
depth).
By setting GenParamName to one of the following values, additional
parameters specific for the implicit triangulation can be set with
GenParamValue:
sets the depth of the octree. The octree depth controls the resolution of the surface generation - a higher depth leads to a higher surface resolution. The octree depth has an exponential effect on the runtime and an exponential effect on the memory requirements of the octree. Therefore, the depth is limited to 12.
Suggested values: 5, 6 (default),
8, 10, 11,
12
Restriction: 5
'implicit_octree_depth'
12
enables an alternative algorithm, which can prepare the implicit function up to a user specified octree depth, before the original algorithm takes over the rest of the computations. This algorithm requires less memory than the original one, but is a bit slower.
Suggested values: 2, 4,
6 (default), 8,
10, 11, 12
Restriction: 'implicit_solver_depth'
'implicit_octree_depth'
sets the minimal number of point samples required per octree voxel node. If the number of points in a voxel is less than this value, the voxel is not split any further. For noise free data, this value can be set low (e.g., between 1-5). For noisy data, this value should be set higher (e.g., 10-20), such that the noisy data is accumulated in single voxel nodes to smooth the noise.
Suggested values: 1 (default), 5,
10, 15, 20,
30
Information. By default
('information'='num_triangles'), the number of
generated triangles is reported. For
'information'='verbose', a list of name-value
information pairs is returned. Currently, the following information
is reported:
| Name | Value | Description |
|---|---|---|
| num_triangles | <number of triangles> | reports the number of generated triangular faces. |
| num_points | <number of points> | reports the number of generated points. |
List of values: 'num_triangles' (default),
'verbose'
In this paragraph, a simple comparison of both supported triangulation methods is provided:
| Property | Greedy triangulation | Implicit triangulation |
|---|---|---|
| required data: | 3D points with 3D normals | 3D points with 3D normals, the normals must point consistently inwards |
| resulting surface: | open, triangulation of the input points | closed (water-tight), approximation of the input points |
| resulting point data: | the input point data is preserved | new point data is generated |
| noise handling: | moderate point and normal noise handled properly | point and normal noise handled implicitly; moderate and high noise levels are accepted |
| triangulation resolution: | explicit, controlled by surface neighborhood parameters | implicit, controlled by octree depth and minimal number of point samples per node |
| time complexity: | O(N k log(N)) | O(N D^3) |
| memory complexity: | O(N k), with neigh. prefetching | O(D^3) |
| O(N), without neigh. prefetching | ||
| where: | ||
| N: number of points | ||
| k: size of the neighborhood | ||
| D: depth of the octree |
Depending on the number of points in ObjectModel3D, noise, and
specific structure of the data, both algorithms deliver different results
and perform with different time and memory complexity. The greedy algorithm
works fast, requires less memory, and returns a high level of details in
the reconstructed surface for rather small data sets (up to, e.g., 500.000
points). Since the algorithm must basically process every single point
in the data, its time performance cannot be decoupled from the point number
and it can be rather time consuming for more than 500.000 points.
If large point sets need to be triangulated with this method anyway, it
is recommended to first sub-sample them via sample_object_model_3d.
In contrast, as described above, the implicit algorithm organizes all points in an underlying octree. Therefore, the details returned by it, its speed, and its memory consumption are dominated by the depth of the octree. While higher levels of surface details can only be achieved at disproportionately higher time and memory costs, the octree offers the advantage that it handles large point sets more efficiently. With the octree, the performance of the implicit algorithm depends mostly on the depth of the octree and to a lesser degree on the number of points to be processed. One further disadvantage of the implicit algorithm is its requirement that the adjacent point normals are strictly consistent. This requirement can seldom be fulfilled by usual normal estimation routines.
ObjectModel3D (input_control) object_model_3d(-array) → (handle)
Handle of the 3D object model containing 3D point data.
Method (input_control) string → (string)
Triangulation method.
Default value: 'greedy'
List of values: 'greedy', 'implicit', 'polygon_triangulation', 'xyz_mapping'
GenParamName (input_control) attribute.name-array → (string)
Names of the generic triangulation parameters.
Default value: []
List of values: 'greedy_fix_flips', 'greedy_hole_filling', 'greedy_kNN', 'greedy_mesh_dilation', 'greedy_mesh_erosion', 'greedy_neigh_latitude_tol', 'greedy_neigh_orient_consistent', 'greedy_neigh_orient_tol', 'greedy_neigh_vertical_tol', 'greedy_prefetch_neighbors', 'greedy_radius_type', 'greedy_radius_value', 'greedy_remove_small_surfaces', 'greedy_suppress_timeout_error', 'greedy_timeout', 'implicit_min_num_samples', 'implicit_octree_depth', 'implicit_solver_depth', 'information', 'xyz_mapping_max_area_holes'
GenParamValue (input_control) attribute.value-array → (real / integer / string)
Values of the generic triangulation parameters.
Default value: []
Suggested values: 6, 8, 12, 'true', 'false', 'auto', 'fixed', 'z_factor', 'verbose', 'num_triangles'
TriangulatedObjectModel3D (output_control) object_model_3d(-array) → (handle)
Handle of the 3D object model with the triangulated surface.
Information (output_control) number(-array) → (integer / string)
Additional information about the triangulation process.
read_object_model_3d,
gen_plane_object_model_3d,
gen_sphere_object_model_3d,
gen_cylinder_object_model_3d,
gen_box_object_model_3d,
gen_sphere_object_model_3d_center,
sample_object_model_3d
write_object_model_3d,
render_object_model_3d,
project_object_model_3d,
simplify_object_model_3d
M. Kazhdan, M. Bolitho, and H. Hoppe: “Poisson Surface Reconstruction.” Symposium on Geometry Processing (June 2006).
3D Metrology