ClassesClasses | | Operators

triangulate_object_model_3dT_triangulate_object_model_3dTriangulateObjectModel3dTriangulateObjectModel3d (Operator)

Name

triangulate_object_model_3dT_triangulate_object_model_3dTriangulateObjectModel3dTriangulateObjectModel3d — Create a surface triangulation for a 3D object model.

Signature

triangulate_object_model_3d( : : ObjectModel3D, Method, GenParamName, GenParamValue : TriangulatedObjectModel3D, Information)

Herror T_triangulate_object_model_3d(const Htuple ObjectModel3D, const Htuple Method, const Htuple GenParamName, const Htuple GenParamValue, Htuple* TriangulatedObjectModel3D, Htuple* Information)

void TriangulateObjectModel3d(const HTuple& ObjectModel3D, const HTuple& Method, const HTuple& GenParamName, const HTuple& GenParamValue, HTuple* TriangulatedObjectModel3D, HTuple* Information)

static HObjectModel3DArray HObjectModel3D::TriangulateObjectModel3d(const HObjectModel3DArray& ObjectModel3D, const HString& Method, const HTuple& GenParamName, const HTuple& GenParamValue, HTuple* Information)

HObjectModel3D HObjectModel3D::TriangulateObjectModel3d(const HString& Method, const HTuple& GenParamName, const HTuple& GenParamValue, Hlong* Information) const

HObjectModel3D HObjectModel3D::TriangulateObjectModel3d(const char* Method, const HTuple& GenParamName, const HTuple& GenParamValue, Hlong* Information) const

static void HOperatorSet.TriangulateObjectModel3d(HTuple objectModel3D, HTuple method, HTuple genParamName, HTuple genParamValue, out HTuple triangulatedObjectModel3D, out HTuple information)

static HObjectModel3D[] HObjectModel3D.TriangulateObjectModel3d(HObjectModel3D[] objectModel3D, string method, HTuple genParamName, HTuple genParamValue, out HTuple information)

HObjectModel3D HObjectModel3D.TriangulateObjectModel3d(string method, HTuple genParamName, HTuple genParamValue, out int information)

Description

The operator triangulate_object_model_3dtriangulate_object_model_3dTriangulateObjectModel3dTriangulateObjectModel3dTriangulateObjectModel3d generates a surface of triangular faces for the 3D object model ObjectModel3DObjectModel3DObjectModel3DObjectModel3DobjectModel3D and returns the resulting surface in TriangulatedObjectModel3DTriangulatedObjectModel3DTriangulatedObjectModel3DTriangulatedObjectModel3DtriangulatedObjectModel3D. Currently, the operator offers four methods for the triangulation that can be selected in MethodMethodMethodMethodmethod: 'polygon_triangulation'"polygon_triangulation""polygon_triangulation""polygon_triangulation""polygon_triangulation", 'xyz_mapping'"xyz_mapping""xyz_mapping""xyz_mapping""xyz_mapping", 'greedy'"greedy""greedy""greedy""greedy" and 'implicit'"implicit""implicit""implicit""implicit". 'polygon_triangulation'"polygon_triangulation""polygon_triangulation""polygon_triangulation""polygon_triangulation" is a simple method for the conversion of a polygonal to a triangular face representation in a 3D object model. 'xyz_mapping'"xyz_mapping""xyz_mapping""xyz_mapping""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'"greedy""greedy""greedy""greedy" and 'implicit'"implicit""implicit""implicit""implicit" algorithm is provided in the paragraph "Comparison of the triangulation methods" below.

Polygon triangulation

By selecting MethodMethodMethodMethodmethod='polygon_triangulation'"polygon_triangulation""polygon_triangulation""polygon_triangulation""polygon_triangulation", all polygons in ObjectModel3DObjectModel3DObjectModel3DObjectModel3DobjectModel3D 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 ObjectModel3DObjectModel3DObjectModel3DObjectModel3DobjectModel3D is returned in TriangulatedObjectModel3DTriangulatedObjectModel3DTriangulatedObjectModel3DTriangulatedObjectModel3DtriangulatedObjectModel3D.

2D mapping triangulation

By selecting MethodMethodMethodMethodmethod='xyz_mapping'"xyz_mapping""xyz_mapping""xyz_mapping""xyz_mapping", the points are triangulated in 2D according to a 2D mapping contained in ObjectModel3DObjectModel3DObjectModel3DObjectModel3DobjectModel3D. The used method is the same as in prepare_object_model_3dprepare_object_model_3dPrepareObjectModel3dPrepareObjectModel3dPrepareObjectModel3d for Purpose='segmentation'. If no 2D mapping is available, an exception is raised.

By setting GenParamNameGenParamNameGenParamNameGenParamNamegenParamName to the following value, the additional parameter specific for the 2D mapping triangulation can be set with GenParamValueGenParamValueGenParamValueGenParamValuegenParamValue:

'xyz_mapping_max_area_holes'"xyz_mapping_max_area_holes""xyz_mapping_max_area_holes""xyz_mapping_max_area_holes""xyz_mapping_max_area_holes"

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 GenParamNameGenParamNameGenParamNameGenParamNamegenParamName 'max_area_holes' of prepare_object_model_3dprepare_object_model_3dPrepareObjectModel3dPrepareObjectModel3dPrepareObjectModel3d.

Suggested values: 1, 10 (default), 100

Greedy triangulation

By selecting MethodMethodMethodMethodmethod='greedy'"greedy""greedy""greedy""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:

  1. the distance between both points is smaller or equal to r, i.e.,

  2. both normals have similar orientation, i.e., the angle or - if no strict consistency of the normals is enforced -

  3. the vector is close to orthogonal with respect to N, i.e., the angle

  4. 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'"greedy_radius_type""greedy_radius_type""greedy_radius_type""greedy_radius_type" and 'greedy_radius_value'"greedy_radius_value""greedy_radius_value""greedy_radius_value""greedy_radius_value"), (see 'greedy_neigh_orient_tol'"greedy_neigh_orient_tol""greedy_neigh_orient_tol""greedy_neigh_orient_tol""greedy_neigh_orient_tol"), (see 'greedy_neigh_latitude_tol'"greedy_neigh_latitude_tol""greedy_neigh_latitude_tol""greedy_neigh_latitude_tol""greedy_neigh_latitude_tol"), and d (see 'greedy_neigh_vertical_tol'"greedy_neigh_vertical_tol""greedy_neigh_vertical_tol""greedy_neigh_vertical_tol""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:

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_3dsample_object_model_3dSampleObjectModel3dSampleObjectModel3dSampleObjectModel3d with Method set to 'fast' and a small SampleDistance will remove most local inconsistencies from ObjectModel3DObjectModel3DObjectModel3DObjectModel3DobjectModel3D. 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:

  1. Triangulation of all points reachable by SNC

  2. Hole filling (see 'greedy_hole_filling'"greedy_hole_filling""greedy_hole_filling""greedy_hole_filling""greedy_hole_filling")

  3. Flip resolval (see 'greedy_fix_flips'"greedy_fix_flips""greedy_fix_flips""greedy_fix_flips""greedy_fix_flips")

  4. Mesh morphology (see 'greedy_mesh_erosion'"greedy_mesh_erosion""greedy_mesh_erosion""greedy_mesh_erosion""greedy_mesh_erosion", 'greedy_mesh_dilation'"greedy_mesh_dilation""greedy_mesh_dilation""greedy_mesh_dilation""greedy_mesh_dilation", and 'greedy_remove_small_surfaces'"greedy_remove_small_surfaces""greedy_remove_small_surfaces""greedy_remove_small_surfaces""greedy_remove_small_surfaces")

By setting GenParamNameGenParamNameGenParamNameGenParamNamegenParamName to one of the following values, additional parameters specific for the greedy triangulation can be set with GenParamValueGenParamValueGenParamValueGenParamValuegenParamValue:

'greedy_kNN'"greedy_kNN""greedy_kNN""greedy_kNN""greedy_kNN"

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

'greedy_radius_type'"greedy_radius_type""greedy_radius_type""greedy_radius_type""greedy_radius_type":

if set to 'fixed'"fixed""fixed""fixed""fixed",'greedy_radius_value'"greedy_radius_value""greedy_radius_value""greedy_radius_value""greedy_radius_value" specifies the SNC radius r in meter units.

If set to 'z_factor'"z_factor""z_factor""z_factor""z_factor", r is calculated for each point P by multiplying its z-coordinate by the value specified by 'greedy_radius_value'"greedy_radius_value""greedy_radius_value""greedy_radius_value""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'"auto""auto""auto""auto", the algorithm determines internally whether to use a 'fixed'"fixed""fixed""fixed""fixed" or a 'z_factor'"z_factor""z_factor""z_factor""z_factor" radius and estimates its value. The estimated value is then multiplied by the value specified in 'greedy_radius_value'"greedy_radius_value""greedy_radius_value""greedy_radius_value""greedy_radius_value". This way, the user specifies a scale factor for the estimated radius.

List of values: 'auto'"auto""auto""auto""auto" (default), 'fixed'"fixed""fixed""fixed""fixed", 'z_factor'"z_factor""z_factor""z_factor""z_factor"

'greedy_radius_value'"greedy_radius_value""greedy_radius_value""greedy_radius_value""greedy_radius_value":

see 'greedy_radius_type'"greedy_radius_type""greedy_radius_type""greedy_radius_type""greedy_radius_type".

Suggested values: 0.01, 0.05, 0.5, 0.66, 1.0, 1.5, 2.0, 3.0, 4.0

'greedy_neigh_orient_tol'"greedy_neigh_orient_tol""greedy_neigh_orient_tol""greedy_neigh_orient_tol""greedy_neigh_orient_tol":

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

'greedy_neigh_orient_consistent'"greedy_neigh_orient_consistent""greedy_neigh_orient_consistent""greedy_neigh_orient_consistent""greedy_neigh_orient_consistent":

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'"true""true""true""true", 'false'"false""false""false""false" (default)

'greedy_neigh_latitude_tol'"greedy_neigh_latitude_tol""greedy_neigh_latitude_tol""greedy_neigh_latitude_tol""greedy_neigh_latitude_tol":

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

'greedy_neigh_vertical_tol'"greedy_neigh_vertical_tol""greedy_neigh_vertical_tol""greedy_neigh_vertical_tol""greedy_neigh_vertical_tol":

sets the SNC parameter d as a factor of the radius r.

Suggested values: 0.01, 0.1 (default), 0.2, 0.3

'greedy_hole_filling'"greedy_hole_filling""greedy_hole_filling""greedy_hole_filling""greedy_hole_filling":

sets the length of surface boundaries (in number of point vertices) that should be considered for the hole filling. If 'false'"false""false""false""false" is specified, then the hole filling step is disabled.

Suggested values: 'false'"false""false""false""false", 20, 40 (default), 60

'greedy_fix_flips'"greedy_fix_flips""greedy_fix_flips""greedy_fix_flips""greedy_fix_flips":

enables/disables the flip resolving step of the algorithm.

List of values: 'true'"true""true""true""true" (default), 'false'"false""false""false""false"

'greedy_prefetch_neighbors'"greedy_prefetch_neighbors""greedy_prefetch_neighbors""greedy_prefetch_neighbors""greedy_prefetch_neighbors":

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'"greedy_kNN""greedy_kNN""greedy_kNN""greedy_kNN", and n is the number of points in ObjectModel3DObjectModel3DObjectModel3DObjectModel3DobjectModel3D). 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'"true""true""true""true" (default), 'false'"false""false""false""false"

'greedy_mesh_erosion'"greedy_mesh_erosion""greedy_mesh_erosion""greedy_mesh_erosion""greedy_mesh_erosion":

specifies the number of erosion cycles applied to the final mesh.

Suggested values: 0 (default), 1, 2, 3

'greedy_mesh_dilation'"greedy_mesh_dilation""greedy_mesh_dilation""greedy_mesh_dilation""greedy_mesh_dilation":

specifies the number of dilation cycles. The mesh dilation is applied after the mesh erosion. If 'greedy_mesh_dilation'"greedy_mesh_dilation""greedy_mesh_dilation""greedy_mesh_dilation""greedy_mesh_dilation" is set to a greater value than 'greedy_mesh_erosion'"greedy_mesh_erosion""greedy_mesh_erosion""greedy_mesh_erosion""greedy_mesh_erosion", it will be reduced internally to the value of 'greedy_mesh_erosion'"greedy_mesh_erosion""greedy_mesh_erosion""greedy_mesh_erosion""greedy_mesh_erosion".

Suggested values: 0 (default), 1, 2, 3

'greedy_remove_small_surfaces'"greedy_remove_small_surfaces""greedy_remove_small_surfaces""greedy_remove_small_surfaces""greedy_remove_small_surfaces":

controls the criteria for removing small surface pieces. If set to 'false'"false""false""false""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'"greedy_remove_small_surfaces""greedy_remove_small_surfaces""greedy_remove_small_surfaces""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'"greedy_remove_small_surfaces""greedy_remove_small_surfaces""greedy_remove_small_surfaces""greedy_remove_small_surfaces" will be removed.

Suggested values: 'false'"false""false""false""false" (default), 0.01, 0.05, 0.1, 10, 100, 1000, 10000

'greedy_timeout'"greedy_timeout""greedy_timeout""greedy_timeout""greedy_timeout":

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'"greedy_timeout""greedy_timeout""greedy_timeout""greedy_timeout" to 'false'"false""false""false""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'"timer_mode""timer_mode""timer_mode""timer_mode" set via set_systemset_systemSetSystemSetSystemSetSystem.

Suggested values: 'false'"false""false""false""false" (default), 0.1, 0.5, 1, 10, 100

'greedy_suppress_timeout_error'"greedy_suppress_timeout_error""greedy_suppress_timeout_error""greedy_suppress_timeout_error""greedy_suppress_timeout_error":

by default, if a timeout occurs the operator returns a timeout error code. By setting 'greedy_suppress_timeout_error'"greedy_suppress_timeout_error""greedy_suppress_timeout_error""greedy_suppress_timeout_error""greedy_suppress_timeout_error" to 'true'"true""true""true""true" instead, the operator returns no error and the intermediate results of the triangulation are returned in TriangulatedObjectModel3DTriangulatedObjectModel3DTriangulatedObjectModel3DTriangulatedObjectModel3DtriangulatedObjectModel3D. With the error suppressed, the occurrence of a timeout can be checked by querying the list of values returned in InformationInformationInformationInformationinformation (in 'verbose'"verbose""verbose""verbose""verbose" mode) by looking for the value corresponding to 'timeout_occured'"timeout_occured""timeout_occured""timeout_occured""timeout_occured".

List of values: 'false'"false""false""false""false" (default), 'true'"true""true""true""true"

'information'"information""information""information""information":

specifies, which intermediate results shall be reported in InformationInformationInformationInformationinformation. By default ('information'"information""information""information""information"='num_triangles'"num_triangles""num_triangles""num_triangles""num_triangles"), the number of generated triangles is reported. For 'information'"information""information""information""information"='verbose'"verbose""verbose""verbose""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'"auto""auto""auto""auto" for 'specified_radius_type'"specified_radius_type""specified_radius_type""specified_radius_type""specified_radius_type", this
                                                                field reports the radius type that was selected 
                                                                internally; if ObjectModel3DObjectModel3DObjectModel3DObjectModel3DobjectModel3D is a 3D primitive, the
                                                                user specified radius value is internally used as a
                                                                sampling step and 'used_radius_type'"used_radius_type""used_radius_type""used_radius_type""used_radius_type" reports 
                                                                'sampling'"sampling""sampling""sampling""sampling".
                
  used_radius_value        <used radius value>                  reports the radius value used internally;
                                                                if 'used_radius_type'"used_radius_type""used_radius_type""used_radius_type""used_radius_type"='fixed'"fixed""fixed""fixed""fixed", then the absolute 
                                                                neighborhood radius in meters is reported; 
                                                                if 'used_radius_type'"used_radius_type""used_radius_type""used_radius_type""used_radius_type"='z_factor'"z_factor""z_factor""z_factor""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'"used_radius_type""used_radius_type""used_radius_type""used_radius_type"='sampling'"sampling""sampling""sampling""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'"alpha""alpha""alpha""alpha" in
                                                                degrees that was used for the triangulation.
                 
  neigh_latitude_tol        <beta>                               reports the angular tolerance window 'beta'"beta""beta""beta""beta" in degrees
                                                                that was used to select surface neighbors.
                 
  neigh_vertical_tol       <d>                                  reports the neighborhood parameter 'd'"d""d""d""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'"false""false""false""false" when the hole filling was disabled, or
                                                                the specified maximal hole boundary length number of
                                                                points.
                 
  timeout                  false | <timeout>                    reports 'false'"false""false""false""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'"num_triangles""num_triangles""num_triangles""num_triangles" (default), 'verbose'"verbose""verbose""verbose""verbose"

Implicit triangulation

By selecting MethodMethodMethodMethodmethod='implicit'"implicit""implicit""implicit""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'"greedy""greedy""greedy""greedy" algorithm, the 'implicit'"implicit""implicit""implicit""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 ObjectModel3DObjectModel3DObjectModel3DObjectModel3DobjectModel3D are lying on the surface of an object and the normals of the points in ObjectModel3DObjectModel3DObjectModel3DObjectModel3DobjectModel3D 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 TriangulatedObjectModel3DTriangulatedObjectModel3DTriangulatedObjectModel3DTriangulatedObjectModel3DtriangulatedObjectModel3D. As a consequence, the resolution of the surface details reconstructed in TriangulatedObjectModel3DTriangulatedObjectModel3DTriangulatedObjectModel3DTriangulatedObjectModel3DtriangulatedObjectModel3D depends directly on the resolution of the octree (i.e., on its depth).

By setting GenParamNameGenParamNameGenParamNameGenParamNamegenParamName to one of the following values, additional parameters specific for the implicit triangulation can be set with GenParamValueGenParamValueGenParamValueGenParamValuegenParamValue:

'implicit_octree_depth'"implicit_octree_depth""implicit_octree_depth""implicit_octree_depth""implicit_octree_depth":

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'"implicit_octree_depth""implicit_octree_depth""implicit_octree_depth""implicit_octree_depth" 12

'implicit_solver_depth'"implicit_solver_depth""implicit_solver_depth""implicit_solver_depth""implicit_solver_depth":

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_solver_depth""implicit_solver_depth""implicit_solver_depth""implicit_solver_depth" 'implicit_octree_depth'"implicit_octree_depth""implicit_octree_depth""implicit_octree_depth""implicit_octree_depth"

'implicit_min_num_samples'"implicit_min_num_samples""implicit_min_num_samples""implicit_min_num_samples""implicit_min_num_samples":

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'"information""information""information""information":

specifies, which intermediate results shall be reported in InformationInformationInformationInformationinformation. By default ('information'"information""information""information""information"='num_triangles'"num_triangles""num_triangles""num_triangles""num_triangles"), the number of generated triangles is reported. For 'information'"information""information""information""information"='verbose'"verbose""verbose""verbose""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'"num_triangles""num_triangles""num_triangles""num_triangles" (default), 'verbose'"verbose""verbose""verbose""verbose"

Comparison of the triangulation methods

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 ObjectModel3DObjectModel3DObjectModel3DObjectModel3DobjectModel3D, 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_3dsample_object_model_3dSampleObjectModel3dSampleObjectModel3dSampleObjectModel3d.

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.

Execution Information

Parameters

ObjectModel3DObjectModel3DObjectModel3DObjectModel3DobjectModel3D (input_control)  object_model_3d(-array) HObjectModel3D, HTupleHTupleHtuple (handle) (IntPtr) (HHandle) (handle)

Handle of the 3D object model containing 3D point data.

MethodMethodMethodMethodmethod (input_control)  string HTupleHTupleHtuple (string) (string) (HString) (char*)

Triangulation method.

Default value: 'greedy' "greedy" "greedy" "greedy" "greedy"

List of values: 'greedy'"greedy""greedy""greedy""greedy", 'implicit'"implicit""implicit""implicit""implicit", 'polygon_triangulation'"polygon_triangulation""polygon_triangulation""polygon_triangulation""polygon_triangulation", 'xyz_mapping'"xyz_mapping""xyz_mapping""xyz_mapping""xyz_mapping"

GenParamNameGenParamNameGenParamNameGenParamNamegenParamName (input_control)  attribute.name-array HTupleHTupleHtuple (string) (string) (HString) (char*)

Names of the generic triangulation parameters.

Default value: []

List of values: 'greedy_fix_flips'"greedy_fix_flips""greedy_fix_flips""greedy_fix_flips""greedy_fix_flips", 'greedy_hole_filling'"greedy_hole_filling""greedy_hole_filling""greedy_hole_filling""greedy_hole_filling", 'greedy_kNN'"greedy_kNN""greedy_kNN""greedy_kNN""greedy_kNN", 'greedy_mesh_dilation'"greedy_mesh_dilation""greedy_mesh_dilation""greedy_mesh_dilation""greedy_mesh_dilation", 'greedy_mesh_erosion'"greedy_mesh_erosion""greedy_mesh_erosion""greedy_mesh_erosion""greedy_mesh_erosion", 'greedy_neigh_latitude_tol'"greedy_neigh_latitude_tol""greedy_neigh_latitude_tol""greedy_neigh_latitude_tol""greedy_neigh_latitude_tol", 'greedy_neigh_orient_consistent'"greedy_neigh_orient_consistent""greedy_neigh_orient_consistent""greedy_neigh_orient_consistent""greedy_neigh_orient_consistent", 'greedy_neigh_orient_tol'"greedy_neigh_orient_tol""greedy_neigh_orient_tol""greedy_neigh_orient_tol""greedy_neigh_orient_tol", 'greedy_neigh_vertical_tol'"greedy_neigh_vertical_tol""greedy_neigh_vertical_tol""greedy_neigh_vertical_tol""greedy_neigh_vertical_tol", 'greedy_prefetch_neighbors'"greedy_prefetch_neighbors""greedy_prefetch_neighbors""greedy_prefetch_neighbors""greedy_prefetch_neighbors", 'greedy_radius_type'"greedy_radius_type""greedy_radius_type""greedy_radius_type""greedy_radius_type", 'greedy_radius_value'"greedy_radius_value""greedy_radius_value""greedy_radius_value""greedy_radius_value", 'greedy_remove_small_surfaces'"greedy_remove_small_surfaces""greedy_remove_small_surfaces""greedy_remove_small_surfaces""greedy_remove_small_surfaces", 'greedy_suppress_timeout_error'"greedy_suppress_timeout_error""greedy_suppress_timeout_error""greedy_suppress_timeout_error""greedy_suppress_timeout_error", 'greedy_timeout'"greedy_timeout""greedy_timeout""greedy_timeout""greedy_timeout", 'implicit_min_num_samples'"implicit_min_num_samples""implicit_min_num_samples""implicit_min_num_samples""implicit_min_num_samples", 'implicit_octree_depth'"implicit_octree_depth""implicit_octree_depth""implicit_octree_depth""implicit_octree_depth", 'implicit_solver_depth'"implicit_solver_depth""implicit_solver_depth""implicit_solver_depth""implicit_solver_depth", 'information'"information""information""information""information", 'xyz_mapping_max_area_holes'"xyz_mapping_max_area_holes""xyz_mapping_max_area_holes""xyz_mapping_max_area_holes""xyz_mapping_max_area_holes"

GenParamValueGenParamValueGenParamValueGenParamValuegenParamValue (input_control)  attribute.value-array HTupleHTupleHtuple (real / integer / string) (double / int / long / string) (double / Hlong / HString) (double / Hlong / char*)

Values of the generic triangulation parameters.

Default value: []

Suggested values: 6, 8, 12, 'true'"true""true""true""true", 'false'"false""false""false""false", 'auto'"auto""auto""auto""auto", 'fixed'"fixed""fixed""fixed""fixed", 'z_factor'"z_factor""z_factor""z_factor""z_factor", 'verbose'"verbose""verbose""verbose""verbose", 'num_triangles'"num_triangles""num_triangles""num_triangles""num_triangles"

TriangulatedObjectModel3DTriangulatedObjectModel3DTriangulatedObjectModel3DTriangulatedObjectModel3DtriangulatedObjectModel3D (output_control)  object_model_3d(-array) HObjectModel3D, HTupleHTupleHtuple (handle) (IntPtr) (HHandle) (handle)

Handle of the 3D object model with the triangulated surface.

InformationInformationInformationInformationinformation (output_control)  number(-array) HTupleHTupleHtuple (integer / string) (int / long / string) (Hlong / HString) (Hlong / char*)

Additional information about the triangulation process.

Possible Predecessors

read_object_model_3dread_object_model_3dReadObjectModel3dReadObjectModel3dReadObjectModel3d, gen_plane_object_model_3dgen_plane_object_model_3dGenPlaneObjectModel3dGenPlaneObjectModel3dGenPlaneObjectModel3d, gen_sphere_object_model_3dgen_sphere_object_model_3dGenSphereObjectModel3dGenSphereObjectModel3dGenSphereObjectModel3d, gen_cylinder_object_model_3dgen_cylinder_object_model_3dGenCylinderObjectModel3dGenCylinderObjectModel3dGenCylinderObjectModel3d, gen_box_object_model_3dgen_box_object_model_3dGenBoxObjectModel3dGenBoxObjectModel3dGenBoxObjectModel3d, gen_sphere_object_model_3d_centergen_sphere_object_model_3d_centerGenSphereObjectModel3dCenterGenSphereObjectModel3dCenterGenSphereObjectModel3dCenter, sample_object_model_3dsample_object_model_3dSampleObjectModel3dSampleObjectModel3dSampleObjectModel3d

Possible Successors

write_object_model_3dwrite_object_model_3dWriteObjectModel3dWriteObjectModel3dWriteObjectModel3d, render_object_model_3drender_object_model_3dRenderObjectModel3dRenderObjectModel3dRenderObjectModel3d, project_object_model_3dproject_object_model_3dProjectObjectModel3dProjectObjectModel3dProjectObjectModel3d, simplify_object_model_3dsimplify_object_model_3dSimplifyObjectModel3dSimplifyObjectModel3dSimplifyObjectModel3d

References

M. Kazhdan, M. Bolitho, and H. Hoppe: “Poisson Surface Reconstruction.” Symposium on Geometry Processing (June 2006).

Module

3D Metrology


ClassesClasses | | Operators