BRL-CAD
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}
 
#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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 

Detailed Description

Macro Definition Documentation

◆ BG_TRIMESH_EDGES_INIT_NULL

#define BG_TRIMESH_EDGES_INIT_NULL   {0, NULL}

Definition at line 63 of file trimesh.h.

◆ BG_TRIMESH_FACES_INIT_NULL

#define BG_TRIMESH_FACES_INIT_NULL   {0, NULL}

Definition at line 64 of file trimesh.h.

◆ BG_TRIMESH_SOLID_ERRORS_INIT_NULL

Definition at line 65 of file trimesh.h.

◆ BG_TRIMESH_DECIMATION_METHOD_DEFAULT

#define BG_TRIMESH_DECIMATION_METHOD_DEFAULT   0

Definition at line 151 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}

Definition at line 152 of file trimesh.h.

◆ BG_TRIMESH_OPTIMIZATION_SETTINGS_INIT

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

Definition at line 213 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 102 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 103 of file trimesh.h.

Function Documentation

◆ bg_free_trimesh_edges()

void bg_free_trimesh_edges ( struct bg_trimesh_edges edges)

◆ bg_free_trimesh_faces()

void bg_free_trimesh_faces ( struct bg_trimesh_faces faces)

◆ bg_free_trimesh_solid_errors()

void bg_free_trimesh_solid_errors ( struct bg_trimesh_solid_errors errors)

◆ bg_trimesh_manifold_closed()

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

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 
)

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 
)

Check if a mesh is topologically solid. True if the mesh is closed, manifold, and oriented.

◆ bg_trimesh_face_exit()

int bg_trimesh_face_exit ( int  face_idx,
void *  data 
)

◆ bg_trimesh_face_continue()

int bg_trimesh_face_continue ( int  face_idx,
void *  data 
)

◆ bg_trimesh_face_gather()

int bg_trimesh_face_gather ( int  face_idx,
void *  data 
)

◆ bg_trimesh_edge_exit()

int bg_trimesh_edge_exit ( struct bg_trimesh_halfedge edge,
void *  data 
)

◆ bg_trimesh_edge_continue()

int bg_trimesh_edge_continue ( struct bg_trimesh_halfedge edge,
void *  data 
)

◆ bg_trimesh_edge_gather()

int bg_trimesh_edge_gather ( struct bg_trimesh_halfedge edge,
void *  data 
)

◆ bg_trimesh_degenerate_faces()

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

◆ 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 
)

◆ 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 
)

◆ 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 
)

◆ bg_trimesh_solid2()

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

◆ 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 
)

◆ bg_trimesh_generate_edge_list()

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

◆ 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 
)

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_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 
)

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 
)

◆ bg_trimesh_normals()

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.

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 
)

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 
)

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 
)

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 
)

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 
)

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 
)

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