BRL-CAD
Loading...
Searching...
No Matches
Triangle Mesh Algorithms
Collaboration diagram for Triangle Mesh Algorithms:

Data Structures

struct  bg_trimesh_halfedge
 Algorithms related to 3D meshes built from triangles. More...
 
struct  bg_trimesh_edges
 
struct  bg_trimesh_faces
 
struct  bg_trimesh_solid_errors
 
struct  bg_trimesh_decimation_settings
 
struct  bg_trimesh_optimization_settings
 

Macros

#define BG_TRIMESH_EDGES_INIT_NULL   {0, NULL}
 
#define BG_TRIMESH_FACES_INIT_NULL   {0, NULL}
 
#define BG_TRIMESH_SOLID_ERRORS_INIT_NULL   {BG_TRIMESH_FACES_INIT_NULL, BG_TRIMESH_EDGES_INIT_NULL, BG_TRIMESH_EDGES_INIT_NULL, BG_TRIMESH_EDGES_INIT_NULL}
 
#define BG_TRIMESH_DECIMATION_METHOD_DEFAULT   0
 
#define BG_TRIMESH_DECIMATION_SETTINGS_INIT   {BG_TRIMESH_DECIMATION_METHOD_DEFAULT, 0.0, 0.0, 0, BU_VLS_INIT_ZERO}
 
#define BG_TRIMESH_OPTIMIZATION_SETTINGS_INIT   {0, 0.0, 0.0, 0}
 

Typedefs

typedef int(* bg_face_error_func_t) (int face_idx, void *data)
 
typedef int(* bg_edge_error_funct_t) (struct bg_trimesh_halfedge *edge, void *data)
 

Functions

void bg_free_trimesh_edges (struct bg_trimesh_edges *edges)
 
void bg_free_trimesh_faces (struct bg_trimesh_faces *faces)
 
void bg_free_trimesh_solid_errors (struct bg_trimesh_solid_errors *errors)
 
int bg_trimesh_manifold_closed (int vcnt, int fcnt, fastf_t *v, int *f)
 
int bg_trimesh_oriented (int vcnt, int fcnt, fastf_t *v, int *f)
 
int bg_trimesh_solid (int vcnt, int fcnt, fastf_t *v, int *f, int **bedges)
 
int bg_trimesh_face_exit (int face_idx, void *data)
 
int bg_trimesh_face_continue (int face_idx, void *data)
 
int bg_trimesh_face_gather (int face_idx, void *data)
 
int bg_trimesh_edge_exit (struct bg_trimesh_halfedge *edge, void *data)
 
int bg_trimesh_edge_continue (struct bg_trimesh_halfedge *edge, void *data)
 
int bg_trimesh_edge_gather (struct bg_trimesh_halfedge *edge, void *data)
 
int bg_trimesh_degenerate_faces (int num_faces, int *fpoints, bg_face_error_func_t degenerate_func, void *data)
 
int bg_trimesh_unmatched_edges (int num_edges, struct bg_trimesh_halfedge *edge_list, bg_edge_error_funct_t error_edge_func, void *data)
 
int bg_trimesh_misoriented_edges (int num_edges, struct bg_trimesh_halfedge *edge_list, bg_edge_error_funct_t error_edge_func, void *data)
 
int bg_trimesh_excess_edges (int num_edges, struct bg_trimesh_halfedge *edge_list, bg_edge_error_funct_t error_edge_func, void *data)
 
int bg_trimesh_solid2 (int vcnt, int fcnt, fastf_t *v, int *f, struct bg_trimesh_solid_errors *errors)
 
int bg_trimesh_hanging_nodes (int num_vertices, int num_faces, fastf_t *vertices, int *faces, struct bg_trimesh_solid_errors *errors)
 
struct bg_trimesh_halfedgebg_trimesh_generate_edge_list (int fcnt, int *f)
 
int bg_trimesh_aabb (point_t *min, point_t *max, const int *faces, size_t num_faces, const point_t *p, size_t num_pnts)
 Calculate an axis aligned bounding box (RPP) for a triangle mesh.
 
fastf_t bg_trimesh_area (const int *faces, size_t num_faces, const point_t *p, size_t num_pnts)
 Calculate the surface area of a triangle mesh.
 
int bg_trimesh_decimate (int **ofaces, int *n_ofaces, int *ifaces, int n_ifaces, point_t *p, int n_p, struct bg_trimesh_decimation_settings *s)
 Decimate a mesh and return the decimated faces.
 
int bg_trimesh_isect (int **faces_inside_1, int *num_faces_inside_1, int **faces_inside_2, int *num_faces_inside_2, int **faces_isect_1, int *num_faces_isect_1, int **faces_isect_2, int *num_faces_isect_2, int *faces_1, int num_faces_1, point_t *vertices_1, int num_vertices_1, int *faces_2, int num_faces_2, point_t *vertices_2, int num_vertices_2)
 
int bg_trimesh_normals (vect_t **onorms, int *ifaces, int n_ifaces, point_t *p, int n_p)
 Compute vertex normals for a mesh based on the connected faces.
 
int bg_trimesh_optimize (int **ofaces, int *n_ofaces, point_t **opnts, vect_t **onorms, int *n_opnts, const int *ifaces, int n_ifaces, const point_t *ipnts, const vect_t *inorms, struct bg_trimesh_optimization_settings *s)
 Return trimesh information for a 3D mesh that contains just the date needed to represent in the mesh. Used to finalize intermediate processing meshes to generate a compact mesh for export or storage.
 
int bg_trimesh_2d_gc (int **ofaces, int *n_ofaces, point2d_t **opnts, int *n_opnts, const int *ifaces, int n_ifaces, const point2d_t *ipnts)
 Return trimesh information for a planar (2D) mesh that contains just the set of points active in the mesh.
 
int bg_trimesh_3d_gc (int **ofaces, point_t **opnts, int *n_opnts, const int *faces, int num_faces, const point_t *in_pts)
 Return trimesh information for a 3D mesh that contains just the set of points active in the mesh.
 
int bg_trimesh_sync (int *of, int *f, int fcnt)
 Return a face set where all topologically connected faces are oriented consistently relative to their neighbors.
 
int bg_trimesh_split (int ***ofs, int **ofc, int *f, int fcnt)
 Return a set of face sets where all topologically connected faces are grouped into common sets.
 
int bg_trimesh_2d_plot3 (const char *fname, const int *faces, size_t num_faces, const point2d_t *pnts, size_t num_pnts)
 Return a set of face sets where all topologically connected faces are grouped into common sets.
 
int bg_trimesh_diff (const int *f1, size_t num_f1, const point_t *p1, size_t num_p1, const int *f2, size_t num_f2, const point_t *p2, size_t num_p2, fastf_t dist_tol)
 Compare two trimeshes to determine if they (within tolerance) define the same mesh.
 
unsigned long long bg_trimesh_hash (const int *f, size_t num_f, const point_t *p, size_t num_p, fastf_t dist_tol)
 Generate a hash from the mesh data, using the tolerance parameter to clamp the numerical values. Both vertex positions and face topology are considered, in a style similar to bg_trimesh_diff.
 

Detailed Description

Macro Definition Documentation

◆ BG_TRIMESH_EDGES_INIT_NULL

#define BG_TRIMESH_EDGES_INIT_NULL   {0, NULL}

Definition at line 64 of file trimesh.h.

◆ BG_TRIMESH_FACES_INIT_NULL

#define BG_TRIMESH_FACES_INIT_NULL   {0, NULL}

Definition at line 65 of file trimesh.h.

◆ BG_TRIMESH_SOLID_ERRORS_INIT_NULL

Definition at line 66 of file trimesh.h.

◆ BG_TRIMESH_DECIMATION_METHOD_DEFAULT

#define BG_TRIMESH_DECIMATION_METHOD_DEFAULT   0

Definition at line 167 of file trimesh.h.

◆ BG_TRIMESH_DECIMATION_SETTINGS_INIT

#define BG_TRIMESH_DECIMATION_SETTINGS_INIT   {BG_TRIMESH_DECIMATION_METHOD_DEFAULT, 0.0, 0.0, 0, BU_VLS_INIT_ZERO}

Definition at line 168 of file trimesh.h.

◆ BG_TRIMESH_OPTIMIZATION_SETTINGS_INIT

#define BG_TRIMESH_OPTIMIZATION_SETTINGS_INIT   {0, 0.0, 0.0, 0}

Definition at line 229 of file trimesh.h.

Typedef Documentation

◆ bg_face_error_func_t

typedef int(* bg_face_error_func_t) (int face_idx, void *data)

Definition at line 104 of file trimesh.h.

◆ bg_edge_error_funct_t

typedef int(* bg_edge_error_funct_t) (struct bg_trimesh_halfedge *edge, void *data)

Definition at line 105 of file trimesh.h.

Function Documentation

◆ bg_free_trimesh_edges()

void bg_free_trimesh_edges ( struct bg_trimesh_edges edges)
extern

◆ bg_free_trimesh_faces()

void bg_free_trimesh_faces ( struct bg_trimesh_faces faces)
extern

◆ bg_free_trimesh_solid_errors()

void bg_free_trimesh_solid_errors ( struct bg_trimesh_solid_errors errors)
extern

◆ bg_trimesh_manifold_closed()

int bg_trimesh_manifold_closed ( int  vcnt,
int  fcnt,
fastf_t v,
int *  f 
)
extern

Check if a mesh is topologically closed and manifold. True if for every edge, there is exactly one other edge with the same two end vertices.

◆ bg_trimesh_oriented()

int bg_trimesh_oriented ( int  vcnt,
int  fcnt,
fastf_t v,
int *  f 
)
extern

Check if a mesh is consistently oriented. True if for every edge that has exactly one matching edge, the two edges have opposite orientations. Note that an open mesh can be oriented, but a non-manifold mesh cannot.

◆ bg_trimesh_solid()

int bg_trimesh_solid ( int  vcnt,
int  fcnt,
fastf_t v,
int *  f,
int **  bedges 
)
extern

Check if a mesh is topologically solid. Returns 1 if the mesh is NOT SOLID and 0 if the mesh is SOLID. A SOLID (0) outcome indicates the mesh satisfies all three criteria: Closed, Manifold, Oriented

◆ bg_trimesh_face_exit()

int bg_trimesh_face_exit ( int  face_idx,
void data 
)
extern

◆ bg_trimesh_face_continue()

int bg_trimesh_face_continue ( int  face_idx,
void data 
)
extern

◆ bg_trimesh_face_gather()

int bg_trimesh_face_gather ( int  face_idx,
void data 
)
extern

◆ bg_trimesh_edge_exit()

int bg_trimesh_edge_exit ( struct bg_trimesh_halfedge edge,
void data 
)
extern

◆ bg_trimesh_edge_continue()

int bg_trimesh_edge_continue ( struct bg_trimesh_halfedge edge,
void data 
)
extern

◆ bg_trimesh_edge_gather()

int bg_trimesh_edge_gather ( struct bg_trimesh_halfedge edge,
void data 
)
extern

◆ bg_trimesh_degenerate_faces()

int bg_trimesh_degenerate_faces ( int  num_faces,
int *  fpoints,
bg_face_error_func_t  degenerate_func,
void data 
)
extern

◆ bg_trimesh_unmatched_edges()

int bg_trimesh_unmatched_edges ( int  num_edges,
struct bg_trimesh_halfedge edge_list,
bg_edge_error_funct_t  error_edge_func,
void data 
)
extern

◆ bg_trimesh_misoriented_edges()

int bg_trimesh_misoriented_edges ( int  num_edges,
struct bg_trimesh_halfedge edge_list,
bg_edge_error_funct_t  error_edge_func,
void data 
)
extern

◆ bg_trimesh_excess_edges()

int bg_trimesh_excess_edges ( int  num_edges,
struct bg_trimesh_halfedge edge_list,
bg_edge_error_funct_t  error_edge_func,
void data 
)
extern

◆ bg_trimesh_solid2()

int bg_trimesh_solid2 ( int  vcnt,
int  fcnt,
fastf_t v,
int *  f,
struct bg_trimesh_solid_errors errors 
)
extern

◆ bg_trimesh_hanging_nodes()

int bg_trimesh_hanging_nodes ( int  num_vertices,
int  num_faces,
fastf_t vertices,
int *  faces,
struct bg_trimesh_solid_errors errors 
)
extern

◆ bg_trimesh_generate_edge_list()

struct bg_trimesh_halfedge * bg_trimesh_generate_edge_list ( int  fcnt,
int *  f 
)
extern

◆ bg_trimesh_aabb()

int bg_trimesh_aabb ( point_t min,
point_t max,
const int *  faces,
size_t  num_faces,
const point_t p,
size_t  num_pnts 
)
extern

Calculate an axis aligned bounding box (RPP) for a triangle mesh.

NOTE: This routine bounds only those points that are active in the triangle mesh, not all points present in the supplied points array.

Parameters
[out]minXYZ coordinate defining the minimum bbox point
[out]maxXYZ coordinate defining the maximum bbox point
[in]facesarray of trimesh faces
[in]num_facessize of faces array
[in]parray that holds the points defining the trimesh
[in]num_pntssize of pnts array

◆ bg_trimesh_area()

fastf_t bg_trimesh_area ( const int *  faces,
size_t  num_faces,
const point_t p,
size_t  num_pnts 
)
extern

Calculate the surface area of a triangle mesh.

Parameters
[in]facesarray of trimesh faces
[in]num_facessize of faces array
[in]parray that holds the points defining the trimesh
[in]num_pntssize of pnts array
Returns
-1 if error, else area of mesh in millimeters

◆ bg_trimesh_decimate()

int bg_trimesh_decimate ( int **  ofaces,
int *  n_ofaces,
int *  ifaces,
int  n_ifaces,
point_t p,
int  n_p,
struct bg_trimesh_decimation_settings s 
)
extern

Decimate a mesh and return the decimated faces.

Parameters
[out]ofacesfaces array for the new output mesh
[out]n_ofaceslength of ofaces array
[in]ifacesarray of input trimesh
[in]n_ifacessize of input faces array
[in]parray that holds the points defining the trimesh
[in]n_psize of points array
[in]sdecimation settings

NOTE: This routine will not produce a points array that includes only the points used in the decimated mesh - to generate that output, use the bg_trimesh_3d_gc routine with the ofaces set produced by this function.

Returns
-1 if error, 0 if successful

◆ bg_trimesh_isect()

int bg_trimesh_isect ( int **  faces_inside_1,
int *  num_faces_inside_1,
int **  faces_inside_2,
int *  num_faces_inside_2,
int **  faces_isect_1,
int *  num_faces_isect_1,
int **  faces_isect_2,
int *  num_faces_isect_2,
int *  faces_1,
int  num_faces_1,
point_t vertices_1,
int  num_vertices_1,
int *  faces_2,
int  num_faces_2,
point_t vertices_2,
int  num_vertices_2 
)
extern

◆ bg_trimesh_normals()

int bg_trimesh_normals ( vect_t **  onorms,
int *  ifaces,
int  n_ifaces,
point_t p,
int  n_p 
)
extern

Compute vertex normals for a mesh based on the connected faces.

Parameters
[out]onormsarray of normals - will have the same length as the input points array
[in]ifacesarray of input trimesh
[in]n_ifacessize of input faces array
[in]parray that holds the points defining the trimesh
[in]n_psize of points array

NOTE: Any vertex point not used by the triangles in the trimesh will have a zero normal in the onorms array. This routine does not repack the data to eliminate unused vertices - for that use bg_trimesh_optimize

Returns
-1 if error, 0 if successful

◆ bg_trimesh_optimize()

int bg_trimesh_optimize ( int **  ofaces,
int *  n_ofaces,
point_t **  opnts,
vect_t **  onorms,
int *  n_opnts,
const int *  ifaces,
int  n_ifaces,
const point_t ipnts,
const vect_t inorms,
struct bg_trimesh_optimization_settings s 
)
extern

Return trimesh information for a 3D mesh that contains just the date needed to represent in the mesh. Used to finalize intermediate processing meshes to generate a compact mesh for export or storage.

Parameters
[out]ofacesfaces array for the new output mesh with new indices based on opnts array.
[out]n_ofaceslength of ofaces array
[out]opntscompact points array for the new output mesh.
[out]onorms(optional) compact normals array for the output mesh's points.
[out]n_opntslength of opnts array.
[in]ifacesarray of input trimesh
[in]n_ifacessize of input faces array
[in]ipntsarray that holds the points defining the original trimesh
[in]inorms(optional) array that holds the normals for the mesh vertices
[in]s(optional) settings to enable various additional processing steps
Returns
-1 if error, number of faces in new trimesh if successful

◆ bg_trimesh_2d_gc()

int bg_trimesh_2d_gc ( int **  ofaces,
int *  n_ofaces,
point2d_t **  opnts,
int *  n_opnts,
const int *  ifaces,
int  n_ifaces,
const point2d_t ipnts 
)
extern

Return trimesh information for a planar (2D) mesh that contains just the set of points active in the mesh.

Parameters
[out]ofacesfaces array for the new output mesh
[out]n_ofaceslength of ofaces array
[out]opntspoints array for the new output mesh
[out]n_opntslength of opnts array
[in]ifacesarray of input trimesh
[in]n_ifacessize of input faces array
[in]ipntsarray that holds the points defining the original trimesh
Returns
-1 if error, number of faces in new trimesh if successful (should match the original face count)

◆ bg_trimesh_3d_gc()

int bg_trimesh_3d_gc ( int **  ofaces,
point_t **  opnts,
int *  n_opnts,
const int *  faces,
int  num_faces,
const point_t in_pts 
)
extern

Return trimesh information for a 3D mesh that contains just the set of points active in the mesh.

Parameters
[out]ofacesfaces array for the new output mesh.
[out]opntspoints array for the new output mesh.
[out]n_opntslength of opnts array.
[in]facesarray of input trimesh
[in]num_facessize of input faces array
[in]in_ptsholds the points defining the original trimesh
Returns
-1 if error, number of faces in new trimesh if successful (should match the original face count)

◆ bg_trimesh_sync()

int bg_trimesh_sync ( int *  of,
int *  f,
int  fcnt 
)
extern

Return a face set where all topologically connected faces are oriented consistently relative to their neighbors.

Parameters
[out]offaces array for the new output mesh (of==f is valid).
[in]finput set of faces.
[in]fcntinput face count
Returns
-1 if error, otherwise return the number of times a face flipping operation was performed

◆ bg_trimesh_split()

int bg_trimesh_split ( int ***  ofs,
int **  ofc,
int *  f,
int  fcnt 
)
extern

Return a set of face sets where all topologically connected faces are grouped into common sets.

Parameters
[out]ofsarray of faces arrays containing the new output face sets.
[out]ofcarray of face counts for the new output face sets.
[in]finput set of faces.
[in]fcntinput face count
Returns
-1 if error, otherwise return the number of face sets created

◆ bg_trimesh_2d_plot3()

int bg_trimesh_2d_plot3 ( const char fname,
const int *  faces,
size_t  num_faces,
const point2d_t pnts,
size_t  num_pnts 
)
extern

Return a set of face sets where all topologically connected faces are grouped into common sets.

Parameters
[in]fnameplot file name
[in]facesface index array
[in]num_facesnumber of faces
[in]pntspoints array
[in]num_pntsnumber of points
Returns
BRLCAD_ERROR if error, otherwise return BRLCAD_OK

◆ bg_trimesh_diff()

int bg_trimesh_diff ( const int *  f1,
size_t  num_f1,
const point_t p1,
size_t  num_p1,
const int *  f2,
size_t  num_f2,
const point_t p2,
size_t  num_p2,
fastf_t  dist_tol 
)
extern

Compare two trimeshes to determine if they (within tolerance) define the same mesh.

This is a fairly focused function whose purpose is to spot meshes that have potentially gone through numerical or topological reordering but still define the same volume (for example, meshes that have been rotated or translated and then returned to an origin with PCA.) By design it does not analyze the differences to report on why two meshes differ - it simply returns a yes/no decision. Different vertex or face counts are grounds for immediate declaration the meshes differ - no effort is made to look for duplicate vertices or degenerate faces. Any such clean-ups must be performed before calling this function.

The specification of a distance tolerance is used for vertex comparisons. Below the specified threshold, vertices that would otherwise be considered rejection criteria for being different will be considered the same. HOWEVER, that tolerance does NOT merge vertices - rather, when vertices are organized and sorted for comparison the candidate pairing vertices in the arrays are compared using the tolerance.

Both vertex positions and face topology must be compatible - faces may use a different starting vertex (i.e. 0->1->2 and 1->2->0 are considered to be the same) but the ordering must be consistent (i.e. 0->2->1 would not be considered the same.)

Parameters
[in]f1face index array referencing points in p1
[in]num_f1number of faces in f1
[in]p1first points array
[in]num_p1number of points in p1
[in]f2face index array referencing points in p2
[in]num_f2number of faces in f2
[in]p2second points array
[in]num_p2number of points in p2
[in]dist_toldistance in mm below which points are considered the same
Returns
0 if same, otherwise return 1.

◆ bg_trimesh_hash()

unsigned long long bg_trimesh_hash ( const int *  f,
size_t  num_f,
const point_t p,
size_t  num_p,
fastf_t  dist_tol 
)
extern

Generate a hash from the mesh data, using the tolerance parameter to clamp the numerical values. Both vertex positions and face topology are considered, in a style similar to bg_trimesh_diff.

The clamping needed to generate a hash value will increase the chances of two similar meshes having the same hash, but the nature of numerical clamping results in some very close but not exact values clamping in opposite directions. Without global awareness of all vertex points at play in a database it is not possible to establish a binning that will work for all meshes in the same way (and there are no guarantees it is possible even with that knowledge, strictly speaking.) For a proper distance-based comparison of two meshes, bg_trimesh_diff should be used rather than comparing hash values. However, if mesh hash values DO match then the associated meshes should be quite close to being the same geometry per the specified tolerance - and in practice there are situations where we can get enough matching hashes to be useful - trial runs of PCA oriented BoT object grouping on a large database were able to identify matching hashes for about 80% of the cases were bg_trimesh_diff was able to geometrically identify fuzzy matches.

Applications for this hash include looking up data associated with meshes via hash keys - if a large majority of duplicate meshes can be spotted in a .g database and indexed this way, it makes it possible to reduce the amount of duplicate data being stored. It is also possible to associated meshes with their hashes and then use a bg_trimesh_diff result to further map those hashes to unique data copies.

Todo:
Parameters
[in]fface index array referencing points in p
[in]num_fnumber of faces in f
[in]ppoints array
[in]num_pnumber of points in p
[in]dist_toltolerance used when clamping points
Returns
the bu_data_hash value of the mesh.