| Operators |
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. 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
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. |
| 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.
Handle of the 3D object model containing 3D point data.
Triangulation method.
Default value: 'greedy'
List of values: 'greedy', 'implicit', 'polygon_triangulation', 'xyz_mapping'
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'
Values of the generic triangulation parameters.
Default value: []
Suggested values: 6, 8, 12, 'true', 'false', 'auto', 'fixed', 'z_factor', 'verbose', 'num_triangles'
Handle of the 3D object model with the triangulated surface.
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
| Operators |