BRL-CAD
#include "common.h"
#include <stdlib.h>
#include <math.h>
#include "bio.h"
#include "bu/parallel.h"
#include "vmath.h"
#include "nmg.h"
#include "raytrace.h"
#include "plot3.h"
Include dependency graph for nmg_tri.c:

Go to the source code of this file.

Data Structures

struct  pt2d
 
struct  trap
 
struct  loopuse_tree_node
 

Macros

#define TOL_2D   1.0e-10
 
#define P_GT_V(_p, _v)   (((_p)->coord[Y] - (_v)->coord[Y]) > TOL_2D || (NEAR_EQUAL((_p)->coord[Y], (_v)->coord[Y], TOL_2D) && (_p)->coord[X] < (_v)->coord[X]))
 
#define P_LT_V(_p, _v)   (((_p)->coord[Y] - (_v)->coord[Y]) < (-TOL_2D) || (NEAR_EQUAL((_p)->coord[Y], (_v)->coord[Y], TOL_2D) && (_p)->coord[X] > (_v)->coord[X]))
 
#define P_GE_V(_p, _v)   (((_p)->coord[Y] - (_v)->coord[Y]) > TOL_2D || (NEAR_EQUAL((_p)->coord[Y], (_v)->coord[Y], TOL_2D) && (_p)->coord[X] <= (_v)->coord[X]))
 
#define P_LE_V(_p, _v)   (((_p)->coord[Y] - (_v)->coord[Y]) < (-TOL_2D) || (NEAR_EQUAL((_p)->coord[Y], (_v)->coord[Y], TOL_2D) && (_p)->coord[X] >= (_v)->coord[X]))
 
#define NMG_PT2D_MAGIC   0x2d2d2d2d
 
#define NMG_TRAP_MAGIC   0x1ab1ab
 
#define NMG_CK_PT2D(_p)   NMG_CKMAG(_p, NMG_PT2D_MAGIC, "pt2d")
 
#define NMG_CK_TRAP(_p)
 
#define NMG_TBL2D_MAGIC   0x3e3e3e3e
 
#define NMG_CK_TBL2D(_p)   NMG_CKMAG(_p, NMG_TBL2D_MAGIC, "tbl2d")
 
#define PT2D_NEXT(tbl, pt)   pt2d_pn(tbl, pt, 1)
 
#define PT2D_PREV(tbl, pt)   pt2d_pn(tbl, pt, -1)
 

Functions

int PvsV (struct trap *p, struct trap *v)
 
struct bu_listnmg_flatten_face (struct faceuse *fu, fastf_t *TformMat, const struct bn_tol *tol)
 
HIDDEN void pick_edges (struct vertex *v, struct vertexuse **vu_first, int *min_dir, struct vertexuse **vu_last, int *max_dir, struct faceuse *fu, fastf_t *dir)
 
struct edgeuse * pick_eu (struct edgeuse *eu_p, struct faceuse *fu, fastf_t *dir, int find_max)
 
void nmg_find_first_last_use_of_v_in_fu (struct vertex *v, struct vertexuse **first_vu, struct vertexuse **last_vu, fastf_t *dir, struct faceuse *fu, const struct bn_tol *tol)
 
void nmg_plot_fu (const char *prefix, const struct faceuse *fu, const struct bn_tol *tol)
 
int nmg_isect_pt_facet (struct vertex *v, struct vertex *v0, struct vertex *v1, struct vertex *v2, const struct bn_tol *tol)
 
int nmg_isect_potcut_fu (struct edgeuse *eu1, struct edgeuse *eu2, struct faceuse *fu, const struct bn_tol *tol)
 
void nmg_triangulate_rm_holes (struct faceuse *fu, struct bu_list *tbl2d, const struct bn_tol *tol)
 
int nmg_triangulate_rm_degen_loopuse (struct faceuse *fu, const struct bn_tol *tol)
 
void nmg_dump_model (struct model *m)
 
HIDDEN void nmg_tri_kill_accordions (struct loopuse *lu, struct bu_list *tbl2d)
 
HIDDEN void validate_tbl2d (const char *str, struct bu_list *tbl2d, struct faceuse *fu)
 
HIDDEN void cut_unimonotone (struct bu_list *tbl2d, struct loopuse *lu, const struct bn_tol *tol)
 
void print_loopuse_tree (struct bu_list *head, struct loopuse_tree_node *parent, const struct bn_tol *tol)
 
int nmg_classify_pt_loop_new (const struct vertex *line1_pt1_v_ptr, const struct loopuse *lu, const struct bn_tol *tol)
 
int nmg_classify_lu_lu_new (const struct loopuse *lu1, const struct loopuse *lu2, const struct bn_tol *tol)
 
void insert_above (struct loopuse *lu, struct loopuse_tree_node *node, const struct bn_tol *tol)
 
void insert_node (struct loopuse *lu, struct bu_list *head, struct loopuse_tree_node *parent, const struct bn_tol *tol)
 
void nmg_build_loopuse_tree (struct faceuse *fu, struct loopuse_tree_node **root, const struct bn_tol *tol)
 
int nmg_triangulate_fu (struct faceuse *fu, const struct bn_tol *tol)
 
void nmg_triangulate_shell (struct shell *s, const struct bn_tol *tol)
 
void nmg_triangulate_model (struct model *m, const struct bn_tol *tol)
 

Detailed Description

Triangulate the faces of a polygonal NMG.

Definition in file nmg_tri.c.

Macro Definition Documentation

#define TOL_2D   1.0e-10

Definition at line 44 of file nmg_tri.c.

#define P_GT_V (   _p,
  _v 
)    (((_p)->coord[Y] - (_v)->coord[Y]) > TOL_2D || (NEAR_EQUAL((_p)->coord[Y], (_v)->coord[Y], TOL_2D) && (_p)->coord[X] < (_v)->coord[X]))

Definition at line 45 of file nmg_tri.c.

Referenced by cut_unimonotone().

#define P_LT_V (   _p,
  _v 
)    (((_p)->coord[Y] - (_v)->coord[Y]) < (-TOL_2D) || (NEAR_EQUAL((_p)->coord[Y], (_v)->coord[Y], TOL_2D) && (_p)->coord[X] > (_v)->coord[X]))

Definition at line 47 of file nmg_tri.c.

Referenced by cut_unimonotone().

#define P_GE_V (   _p,
  _v 
)    (((_p)->coord[Y] - (_v)->coord[Y]) > TOL_2D || (NEAR_EQUAL((_p)->coord[Y], (_v)->coord[Y], TOL_2D) && (_p)->coord[X] <= (_v)->coord[X]))

Definition at line 49 of file nmg_tri.c.

#define P_LE_V (   _p,
  _v 
)    (((_p)->coord[Y] - (_v)->coord[Y]) < (-TOL_2D) || (NEAR_EQUAL((_p)->coord[Y], (_v)->coord[Y], TOL_2D) && (_p)->coord[X] >= (_v)->coord[X]))

Definition at line 51 of file nmg_tri.c.

#define NMG_PT2D_MAGIC   0x2d2d2d2d

Definition at line 54 of file nmg_tri.c.

#define NMG_TRAP_MAGIC   0x1ab1ab

Definition at line 55 of file nmg_tri.c.

#define NMG_CK_PT2D (   _p)    NMG_CKMAG(_p, NMG_PT2D_MAGIC, "pt2d")

Definition at line 56 of file nmg_tri.c.

Referenced by nmg_triangulate_rm_holes().

#define NMG_CK_TRAP (   _p)
Value:
{NMG_CKMAG(_p, NMG_TRAP_MAGIC, "trap");\
if (! BU_LIST_PREV(bu_list, &(_p)->l)) {\
bu_log("%s %d bad prev pointer of trapezoid %p\n", \
__FILE__, __LINE__, (void *)&(_p)->l); \
bu_bomb("NMG_CK_TRAP: aborting");\
} else if (! BU_LIST_NEXT(bu_list, &(_p)->l)) {\
bu_log("%s %d bad next pointer of trapezoid %p\n", \
__FILE__, __LINE__, (void *)&(_p)->l); \
bu_bomb("NMG_CL_TRAP: aborting");\
}}
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
Definition: list.h:118
if(share_geom)
Definition: nmg_mod.c:3829
#define NMG_TRAP_MAGIC
Definition: nmg_tri.c:55
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
#define BU_LIST_NEXT(structure, hp)
Definition: list.h:316
#define BU_LIST_PREV(structure, hp)
Definition: list.h:310

Definition at line 57 of file nmg_tri.c.

Referenced by PvsV().

#define NMG_TBL2D_MAGIC   0x3e3e3e3e

Definition at line 68 of file nmg_tri.c.

Referenced by nmg_flatten_face().

#define NMG_CK_TBL2D (   _p)    NMG_CKMAG(_p, NMG_TBL2D_MAGIC, "tbl2d")

Definition at line 69 of file nmg_tri.c.

Referenced by cut_unimonotone(), and nmg_tri_kill_accordions().

#define PT2D_NEXT (   tbl,
  pt 
)    pt2d_pn(tbl, pt, 1)

Definition at line 72 of file nmg_tri.c.

Referenced by cut_unimonotone().

#define PT2D_PREV (   tbl,
  pt 
)    pt2d_pn(tbl, pt, -1)

Definition at line 73 of file nmg_tri.c.

Referenced by cut_unimonotone().

Function Documentation

int PvsV ( struct trap p,
struct trap v 
)

Definition at line 105 of file nmg_tri.c.

References pt2d::coord, NMG_CK_TRAP, trap::top, X, and Y.

struct bu_list* nmg_flatten_face ( struct faceuse *  fu,
fastf_t TformMat,
const struct bn_tol tol 
)

Create the 2D coordinate table for the vertexuses of a face.

 ---------  -----------------------------------
 |pt2d --+-----> |     struct pt2d.{magic, coord[3]} |
 ---------  -----------------------------------
            |     struct pt2d.{magic, coord[3]} |
            -----------------------------------
            |     struct pt2d.{magic, coord[3]} |
            -----------------------------------

When the caller is done, nmg_free_2d_map() should be called to dispose of the map

Definition at line 377 of file nmg_tri.c.

References bn_mat_fromto(), bn_mat_print(), BU_ALLOC, bu_bomb(), BU_LIST_FIRST, BU_LIST_FIRST_MAGIC, BU_LIST_FOR, BU_LIST_INIT, BU_LIST_MAGIC_SET, bu_log(), lu, rt_g::NMG_debug, NMG_EDGEUSE_MAGIC, NMG_TBL2D_MAGIC, NMG_VERTEXUSE_MAGIC, RTG, and V3ARGS.

Referenced by nmg_triangulate_fu().

Here is the call graph for this function:

HIDDEN void pick_edges ( struct vertex *  v,
struct vertexuse **  vu_first,
int *  min_dir,
struct vertexuse **  vu_last,
int *  max_dir,
struct faceuse *  fu,
fastf_t dir 
)

Support routine for nmg_find_first_last_use_of_v_in_fu

The object of the game here is to find uses of the given vertex whose departing edges have the min/max dot product with the direction vector.

Definition at line 527 of file nmg_tri.c.

References bu_bomb(), BU_LIST_FOR, BU_LIST_PNEXT_CIRC, BU_LIST_PPREV_CIRC, bu_log(), rt_g::NMG_debug, nmg_find_fu_of_vu(), NMG_LOOPUSE_MAGIC, RTG, SMALL_FASTF, and V3ARGS.

Referenced by nmg_find_first_last_use_of_v_in_fu().

Here is the call graph for this function:

struct edgeuse* pick_eu ( struct edgeuse *  eu_p,
struct faceuse *  fu,
fastf_t dir,
int  find_max 
)

Support routine for nmg_find_first_last_use_of_v_in_fu

Given and edgeuse and a faceuse, pick the use of the edge in the faceuse whose left vector has the largest/smallest dot product with the given direction vector. The parameter "find_max" determines whether we return the edgeuse with the largest (find_max != 0) or the smallest (find_max == 0) left-dot-product.

Definition at line 684 of file nmg_tri.c.

References bu_bomb(), BU_LIST_PNEXT_CIRC, bu_log(), eu_p, rt_g::NMG_debug, nmg_find_eu_leftvec(), nmg_find_fu_of_eu(), RTG, and V3ARGS.

Referenced by nmg_find_first_last_use_of_v_in_fu().

Here is the call graph for this function:

void nmg_find_first_last_use_of_v_in_fu ( struct vertex *  v,
struct vertexuse **  first_vu,
struct vertexuse **  last_vu,
fastf_t dir,
struct faceuse *  fu,
const struct bn_tol tol 
)

Given a pointer to a vertexuse in a face and a ray, find the "first" and "last" uses of the vertex along the ray in the face. Consider the diagram below where 4 OT_SAME loopuses meet at a single vertex. The ray enters from the upper left and proceeds to the lower right. The ray encounters vertexuse (represented by "o" below) number 1 first and vertexuse 3 last.

             edge A
             |
         \  ^||
          \ |||
           1||V2
    ------->o|o------->

edge D -----------—.----------—edge B <----—o|o<---— 4^||3 ||| \ ||| \ ||V | | - edge C

The primary purpose of this routine is to find the vertexuses that should be the parameters to nmg_cut_loop() and nmg_join_loop().

Definition at line 795 of file nmg_tri.c.

References bu_bomb(), BU_LIST_PNEXT_CIRC, BU_LIST_PPREV_CIRC, bu_log(), eu_p, rt_g::NMG_debug, pick_edges(), pick_eu(), RTG, and V3ARGS.

Here is the call graph for this function:

void nmg_plot_fu ( const char *  prefix,
const struct faceuse *  fu,
const struct bn_tol tol 
)

Definition at line 1390 of file nmg_tri.c.

References bn_dist_pt3_pt3(), BU_LIST_FIRST_MAGIC, BU_LIST_FOR, bu_vls_addr(), bu_vls_free(), BU_VLS_INIT_ZERO, bu_vls_sprintf(), lu, NMG_EDGEUSE_MAGIC, pdv_3line(), and pl_color().

Referenced by cut_unimonotone(), nmg_triangulate_fu(), and print_loopuse_tree().

Here is the call graph for this function:

int nmg_isect_pt_facet ( struct vertex *  v,
struct vertex *  v0,
struct vertex *  v1,
struct vertex *  v2,
const struct bn_tol tol 
)

Definition at line 1489 of file nmg_tri.c.

References bn_dist_pt3_pt3(), bn_lseg3_lseg3_parallel(), bn_tol::dist, NEAR_ZERO, SMALL_FASTF, OSL::Strings::u, VSETALL, and ZERO.

Here is the call graph for this function:

int nmg_isect_potcut_fu ( struct edgeuse *  eu1,
struct edgeuse *  eu2,
struct faceuse *  fu,
const struct bn_tol tol 
)

Given the faceuse 'fu' test if the potential cut, defined by an edgeuse from 'eu1->vu_p' to 'eu2->vu_p', intersects any edgeuse of the faceuse.

Return 1 if intersect found otherwise return 0.

Definition at line 1650 of file nmg_tri.c.

References BN_CK_TOL, bn_isect_lseg3_lseg3(), bu_bomb(), BU_LIST_FOR, BU_LIST_PNEXT_CIRC, hit(), lu, NEAR_ZERO, NMG_CK_LOOPUSE(), and SMALL_FASTF.

Referenced by nmg_triangulate_rm_holes().

Here is the call graph for this function:

void nmg_triangulate_rm_holes ( struct faceuse *  fu,
struct bu_list tbl2d,
const struct bn_tol tol 
)

Definition at line 1788 of file nmg_tri.c.

References BN_CK_TOL, bu_bomb(), BU_LIST_FIRST, BU_LIST_FOR, BU_LIST_PNEXT_CIRC, bu_log(), eu1, eu2, hit(), N, NMG_CK_LOOPUSE(), NMG_CK_PT2D, nmg_find_model(), nmg_isect_potcut_fu(), nmg_plot_lu_around_eu(), nmg_stash_model_to_file(), V3ARGS, and VSETALL.

Referenced by nmg_triangulate_fu().

Here is the call graph for this function:

int nmg_triangulate_rm_degen_loopuse ( struct faceuse *  fu,
const struct bn_tol tol 
)

Definition at line 1990 of file nmg_tri.c.

References BN_CK_TOL, bu_bomb(), bu_calloc(), bu_free(), BU_LIST_FIRST, BU_LIST_FIRST_MAGIC, BU_LIST_FOR, BU_LIST_IS_HEAD, BU_LIST_PNEXT, bu_log(), bu_realloc(), eu1, if(), lu, NMG_CK_LOOPUSE(), rt_g::NMG_debug, NMG_EDGEUSE_MAGIC, nmg_klu(), nmg_kvu(), NMG_VERTEXUSE_MAGIC, out, and RTG.

Referenced by nmg_triangulate_fu().

Here is the call graph for this function:

void nmg_dump_model ( struct model *  m)

Definition at line 2168 of file nmg_tri.c.

References bu_bomb(), BU_LIST_FOR, lu, NMG_CK_LOOPUSE(), NMG_CK_SHELL(), s, and V3ARGS.

Here is the call graph for this function:

HIDDEN void nmg_tri_kill_accordions ( struct loopuse *  lu,
struct bu_list tbl2d 
)

Definition at line 2230 of file nmg_tri.c.

References bu_bomb(), BU_LIST_FIRST, BU_LIST_FIRST_MAGIC, BU_LIST_FOR, BU_LIST_IS_EMPTY, BU_LIST_NOT_HEAD, BU_LIST_PNEXT, BU_LIST_PNEXT_CIRC, BU_LIST_PPREV_CIRC, bu_log(), NMG_CK_LOOPUSE(), NMG_CK_TBL2D, rt_g::NMG_debug, NMG_EDGEUSE_MAGIC, nmg_keu(), RTG, and pt2d::vu_p.

Referenced by cut_unimonotone().

Here is the call graph for this function:

HIDDEN void validate_tbl2d ( const char *  str,
struct bu_list tbl2d,
struct faceuse *  fu 
)

Definition at line 2306 of file nmg_tri.c.

References bu_bomb(), BU_LIST_FIRST_MAGIC, BU_LIST_FOR, bu_log(), NMG_CK_LOOPUSE(), NMG_EDGEUSE_MAGIC, V3ARGS, and pt2d::vu_p.

Referenced by cut_unimonotone(), and nmg_triangulate_fu().

Here is the call graph for this function:

HIDDEN void cut_unimonotone ( struct bu_list tbl2d,
struct loopuse *  lu,
const struct bn_tol tol 
)
void print_loopuse_tree ( struct bu_list head,
struct loopuse_tree_node parent,
const struct bn_tol tol 
)

Definition at line 2805 of file nmg_tri.c.

References bu_bomb(), BU_LIST_FIRST, BU_LIST_FOR, BU_LIST_HEAD_MAGIC, BU_LIST_IS_EMPTY, BU_LIST_NON_EMPTY, bu_log(), bu_vls_addr(), bu_vls_free(), BU_VLS_INIT_ZERO, bu_vls_sprintf(), loopuse_tree_node::children_hd, loopuse_tree_node::lu, bu_list::magic, NMG_CK_LOOPUSE(), and nmg_plot_fu().

Here is the call graph for this function:

int nmg_classify_pt_loop_new ( const struct vertex *  line1_pt1_v_ptr,
const struct loopuse *  lu,
const struct bn_tol tol 
)

Definition at line 2836 of file nmg_tri.c.

References bn_angle_measure(), bn_isect_line3_line3(), bn_pt3_pt3_equal(), bu_bomb(), BU_LIST_FIRST, BU_LIST_FIRST_MAGIC, BU_LIST_FOR, BU_LIST_IS_HEAD, BU_LIST_PNEXT, bu_log(), bn_tol::dist, eu1, eu2, M_PI, MAX_FASTF, NEAR_ZERO, NMG_CK_LOOPUSE(), NMG_EDGEUSE_MAGIC, SMALL_FASTF, V3ARGS, X, Y, and Z.

Referenced by nmg_classify_lu_lu_new().

Here is the call graph for this function:

int nmg_classify_lu_lu_new ( const struct loopuse *  lu1,
const struct loopuse *  lu2,
const struct bn_tol tol 
)

Definition at line 3080 of file nmg_tri.c.

References bu_bomb(), BU_LIST_FIRST_MAGIC, BU_LIST_FOR, bu_log(), NMG_CK_LOOPUSE(), nmg_classify_pt_loop_new(), and NMG_EDGEUSE_MAGIC.

Referenced by insert_node().

Here is the call graph for this function:

void insert_above ( struct loopuse *  lu,
struct loopuse_tree_node node,
const struct bn_tol tol 
)

Definition at line 3131 of file nmg_tri.c.

References BU_ALLOC, bu_bomb(), BU_LIST_APPEND, BU_LIST_DEQUEUE, BU_LIST_HEAD_MAGIC, BU_LIST_INIT, BU_LIST_PNEXT, bu_log(), loopuse_tree_node::children_hd, loopuse_tree_node::l, loopuse_tree_node::lu, lu, bu_list::magic, NMG_CK_LOOPUSE(), nmg_classify_lu_lu(), and loopuse_tree_node::parent.

Here is the call graph for this function:

void insert_node ( struct loopuse *  lu,
struct bu_list head,
struct loopuse_tree_node parent,
const struct bn_tol tol 
)

Definition at line 3189 of file nmg_tri.c.

References BU_ALLOC, BU_LIST_APPEND, BU_LIST_DEQUEUE, BU_LIST_FOR, BU_LIST_INIT, BU_LIST_NON_EMPTY, bu_log(), loopuse_tree_node::children_hd, loopuse_tree_node::l, loopuse_tree_node::lu, lu, bu_list::magic, NMG_CK_LOOPUSE(), nmg_classify_lu_lu(), nmg_classify_lu_lu_new(), and loopuse_tree_node::parent.

Referenced by nmg_build_loopuse_tree().

Here is the call graph for this function:

void nmg_build_loopuse_tree ( struct faceuse *  fu,
struct loopuse_tree_node **  root,
const struct bn_tol tol 
)

Definition at line 3286 of file nmg_tri.c.

References BU_ALLOC, BU_LIST_FOR, BU_LIST_INIT, bu_log(), insert_node(), lu, and NMG_CK_LOOPUSE().

Here is the call graph for this function:

void nmg_triangulate_shell ( struct shell *  s,
const struct bn_tol tol 
)

Definition at line 3763 of file nmg_tri.c.

References BN_CK_TOL, bu_bomb(), BU_LIST_FIRST, BU_LIST_NOT_HEAD, BU_LIST_PNEXT, bu_log(), NMG_CK_SHELL(), rt_g::NMG_debug, nmg_edge_g_fuse(), nmg_kfu(), nmg_triangulate_fu(), nmg_unbreak_region_edges(), nmg_vsshell(), RTG, and UNLIKELY.

Referenced by nmg_bot(), and nmg_triangulate_model().

Here is the call graph for this function:

void nmg_triangulate_model ( struct model *  m,
const struct bn_tol tol 
)

Definition at line 3818 of file nmg_tri.c.

References BN_CK_TOL, BU_LIST_FOR, bu_log(), rt_g::NMG_debug, nmg_triangulate_shell(), RTG, and s.

Referenced by ged_bev(), ged_facetize(), ged_nmg_collapse(), and nmg_2_vrml().

Here is the call graph for this function: