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

Go to the source code of this file.

Data Structures

struct  cmp_pair
 

Macros

#define AXIS(depth)   ((depth)%3) /* cuts: X, Y, Z, repeat */
 
#define CMP(_p1, _p2, _memb, _ind)
 
#define USE_HIST   0
 
#define PIECE_BLOCK   512
 
#define PIECE_BLOCK   512
 

Functions

HIDDEN int rt_ck_overlap (const vect_t min, const vect_t max, const struct soltab *stp, const struct rt_i *rtip)
 
HIDDEN int rt_ct_box (struct rt_i *rtip, union cutter *cutp, int axis, double where, int force)
 
HIDDEN void rt_ct_optim (struct rt_i *rtip, union cutter *cutp, size_t depth)
 
HIDDEN void rt_ct_free (struct rt_i *rtip, union cutter *cutp)
 
HIDDEN void rt_ct_release_storage (union cutter *cutp)
 
HIDDEN void rt_ct_measure (struct rt_i *rtip, union cutter *cutp, int depth)
 
HIDDEN union cutterrt_ct_get (struct rt_i *rtip)
 
HIDDEN void rt_plot_cut (FILE *fp, struct rt_i *rtip, union cutter *cutp, int lvl)
 
void rt_pr_cut_info (const struct rt_i *rtip, const char *str)
 
HIDDEN int rt_ct_old_assess (register union cutter *, register int, double *, double *)
 
union cutterrt_cut_one_axis (struct bu_ptbl *boxes, struct rt_i *rtip, int axis, int min, int max, struct nugridnode *nuginfop)
 
void rt_cut_optimize_parallel (int cpu, void *arg)
 
HIDDEN int rt_projXmin_comp (const void *p1, const void *p2, void *arg)
 
HIDDEN int rt_projXmax_comp (const void *p1, const void *p2, void *arg)
 
HIDDEN int rt_projYmin_comp (const void *p1, const void *p2, void *arg)
 
HIDDEN int rt_projYmax_comp (const void *p1, const void *p2, void *arg)
 
HIDDEN int rt_projZmin_comp (const void *p1, const void *p2, void *arg)
 
HIDDEN int rt_projZmax_comp (const void *p1, const void *p2, void *arg)
 
void rt_nugrid_cut (register struct nugridnode *nugnp, register struct boxnode *fromp, struct rt_i *rtip, int just_collect_info, int depth)
 
int rt_split_mostly_empty_cells (struct rt_i *rtip, union cutter *cutp)
 
void rt_cut_it (register struct rt_i *rtip, int ncpu)
 
void rt_cut_extend (register union cutter *cutp, struct soltab *stp, const struct rt_i *rtip)
 
HIDDEN int rt_ct_populate_box (union cutter *outp, const union cutter *inp, struct rt_i *rtip)
 
HIDDEN int rt_ct_box (struct rt_i *rtip, register union cutter *cutp, register int axis, double where, int force)
 
HIDDEN int rt_ck_overlap (register const fastf_t *min, register const fastf_t *max, register const struct soltab *stp, register const struct rt_i *rtip)
 
HIDDEN size_t rt_ct_piececount (const union cutter *cutp)
 
HIDDEN void rt_ct_optim (struct rt_i *rtip, register union cutter *cutp, size_t depth)
 
HIDDEN void rt_ct_release_storage (register union cutter *cutp)
 
HIDDEN void rt_ct_free (struct rt_i *rtip, register union cutter *cutp)
 
void rt_pr_cut (const union cutter *cutp, int lvl)
 
void rt_fr_cut (struct rt_i *rtip, register union cutter *cutp)
 
HIDDEN void rt_plot_cut (FILE *fp, struct rt_i *rtip, register union cutter *cutp, int lvl)
 
HIDDEN void rt_ct_measure (register struct rt_i *rtip, register union cutter *cutp, int depth)
 
void rt_cut_clean (struct rt_i *rtip)
 
void remove_from_bsp (struct soltab *stp, union cutter *cutp, struct bn_tol *tol)
 
void insert_in_bsp (struct soltab *stp, union cutter *cutp)
 
void fill_out_bsp (struct rt_i *rtip, union cutter *cutp, struct resource *resp, fastf_t bb[6])
 

Variables

HIDDEN struct cmp_pair pairs []
 

Detailed Description

Cut space into lots of small boxes (RPPs actually).

Call tree for default path through the code: rt_cut_it() rt_cut_extend() for all solids in model rt_ct_optim() rt_ct_old_assess() rt_ct_box() rt_ct_populate_box() rt_ck_overlap()

Definition in file cut.c.

Macro Definition Documentation

#define AXIS (   depth)    ((depth)%3) /* cuts: X, Y, Z, repeat */

Definition at line 65 of file cut.c.

Referenced by rt_ct_optim(), and rt_plot_cut().

#define CMP (   _p1,
  _p2,
  _memb,
  _ind 
)
Value:
(*(const struct soltab **)(_p1))->_memb[_ind] < \
(*(const struct soltab **)(_p2))->_memb[_ind] ? -1 : \
(*(const struct soltab **)(_p1))->_memb[_ind] > \
(*(const struct soltab **)(_p2))->_memb[_ind] ? 1 : 0

Definition at line 159 of file cut.c.

Referenced by rt_projXmax_comp(), rt_projXmin_comp(), rt_projYmax_comp(), rt_projYmin_comp(), rt_projZmax_comp(), and rt_projZmin_comp().

#define USE_HIST   0
#define PIECE_BLOCK   512

Definition at line 2195 of file cut.c.

Referenced by insert_in_bsp(), and rt_ct_populate_box().

#define PIECE_BLOCK   512

Definition at line 2195 of file cut.c.

Function Documentation

HIDDEN int rt_ck_overlap ( const vect_t  min,
const vect_t  max,
const struct soltab stp,
const struct rt_i rtip 
)
HIDDEN int rt_ct_box ( struct rt_i rtip,
union cutter cutp,
int  axis,
double  where,
int  force 
)
HIDDEN void rt_ct_optim ( struct rt_i rtip,
union cutter cutp,
size_t  depth 
)
HIDDEN void rt_ct_free ( struct rt_i rtip,
union cutter cutp 
)

Referenced by rt_ct_box(), and rt_fr_cut().

HIDDEN void rt_ct_release_storage ( union cutter cutp)

Referenced by rt_ct_box(), rt_ct_free(), and rt_fr_cut().

HIDDEN void rt_ct_measure ( struct rt_i rtip,
union cutter cutp,
int  depth 
)

Referenced by rt_ct_measure(), and rt_cut_it().

HIDDEN union cutter * rt_ct_get ( struct rt_i rtip)

Definition at line 1599 of file cut.c.

References bu_calloc(), bu_malloc_len_roundup(), bu_ptbl_init(), bu_ptbl_ins(), bu_semaphore_acquire(), bu_semaphore_release(), cutter::cut_forw, CUTTER_NULL, bu_ptbl::l, bu_list::magic, RT_CK_RTI, RT_SEM_MODEL, rt_i::rti_busy_cutter_nodes, and rt_i::rti_CutFree.

Referenced by rt_ct_box().

Here is the call graph for this function:

HIDDEN void rt_plot_cut ( FILE *  fp,
struct rt_i rtip,
union cutter cutp,
int  lvl 
)

Referenced by rt_cut_it(), and rt_plot_cut().

HIDDEN int rt_ct_old_assess ( register union cutter cutp,
register int  axis,
double *  where_p,
double *  offcenter_p 
)

NOTE: Changing from rt_ct_assess() to this seems to result in a massive change in cut tree size.

This version results in nbins=22, maxlen=3, avg=1.09, while new version results in nbins=42, maxlen=3, avg=1.667 (on moss.g).

Definition at line 1484 of file cut.c.

References cutter::bn, boxnode::bn_len, boxnode::bn_list, boxnode::bn_max, boxnode::bn_min, boxnode::bn_piecelen, boxnode::bn_piecelist, bu_log(), DEBUG_CUTDETAIL, bound_rpp::max, MAX_FASTF, bound_rpp::min, rt_piecelist::npieces, rt_piecelist::pieces, RT_CK_PIECELIST, RT_G_DEBUG, soltab::st_max, soltab::st_min, soltab::st_piece_rpps, and rt_piecelist::stp.

Referenced by rt_ct_optim().

Here is the call graph for this function:

union cutter* rt_cut_one_axis ( struct bu_ptbl boxes,
struct rt_i rtip,
int  axis,
int  min,
int  max,
struct nugridnode nuginfop 
)

As a temporary aid until NUgrid is working, use NUgrid histogram to perform a preliminary partitioning of space, along a single axis. The tree built here is expected to be further refined. The bu_ptbl "boxes" contains a list of the boxnodes, for convenience.

Each span runs from [min].nu_spos to [max].nu_epos.

Definition at line 77 of file cut.c.

References cutter::bn, boxnode::bn_len, boxnode::bn_list, boxnode::bn_max, boxnode::bn_maxlen, boxnode::bn_min, boxnode::bn_type, BU_ALLOC, bu_calloc(), BU_CK_PTBL, bu_ptbl_ins(), cutter::cn, cutnode::cn_axis, cutnode::cn_l, cutnode::cn_point, cutnode::cn_r, cutnode::cn_type, CUT_BOXNODE, CUT_CUTNODE, rt_i::mdl_max, rt_i::mdl_min, rt_i::nsolids, nugridnode::nu_axis, nu_axis::nu_epos, nu_axis::nu_spos, RT_CHECK_SOLTAB, rt_ck_overlap(), RT_CK_RTI, RT_VISIT_ALL_SOLTABS_END, and RT_VISIT_ALL_SOLTABS_START.

Referenced by rt_cut_it().

Here is the call graph for this function:

void rt_cut_optimize_parallel ( int  cpu,
void *  arg 
)

Process all the nodes in the global array rtip->rti_cuts_waiting, until none remain. This routine is run in parallel.

Definition at line 133 of file cut.c.

References bu_log(), BU_PTBL_GET, bu_semaphore_acquire(), bu_semaphore_release(), DEBUG_CUT, bu_ptbl::end, RT_CK_RTI, rt_ct_optim(), RT_G_DEBUG, RT_SEM_WORKER, rt_i::rti_cuts_waiting, and Z.

Referenced by rt_cut_it().

Here is the call graph for this function:

HIDDEN int rt_projXmin_comp ( const void *  p1,
const void *  p2,
void *  arg 
)

Definition at line 174 of file cut.c.

References CMP, and X.

HIDDEN int rt_projXmax_comp ( const void *  p1,
const void *  p2,
void *  arg 
)

Definition at line 181 of file cut.c.

References CMP, and X.

HIDDEN int rt_projYmin_comp ( const void *  p1,
const void *  p2,
void *  arg 
)

Definition at line 188 of file cut.c.

References CMP, and Y.

HIDDEN int rt_projYmax_comp ( const void *  p1,
const void *  p2,
void *  arg 
)

Definition at line 195 of file cut.c.

References CMP, and Y.

HIDDEN int rt_projZmin_comp ( const void *  p1,
const void *  p2,
void *  arg 
)

Definition at line 202 of file cut.c.

References CMP, and Z.

HIDDEN int rt_projZmax_comp ( const void *  p1,
const void *  p2,
void *  arg 
)

Definition at line 209 of file cut.c.

References CMP, and Z.

void rt_nugrid_cut ( register struct nugridnode nugnp,
register struct boxnode fromp,
struct rt_i rtip,
int  just_collect_info,
int  depth 
)
int rt_split_mostly_empty_cells ( struct rt_i rtip,
union cutter cutp 
)
void rt_cut_extend ( register union cutter cutp,
struct soltab stp,
const struct rt_i rtip 
)
HIDDEN int rt_ct_populate_box ( union cutter outp,
const union cutter inp,
struct rt_i rtip 
)

Given that 'outp' has been given a bounding box smaller than that of 'inp', copy over everything which still fits in the smaller box.

Returns - 0 if outp has the same number of items as inp 1 if outp has fewer items than inp

Definition at line 1130 of file cut.c.

References cutter::bn, boxnode::bn_len, boxnode::bn_list, boxnode::bn_max, boxnode::bn_maxlen, boxnode::bn_maxpiecelen, boxnode::bn_min, boxnode::bn_piecelen, boxnode::bn_piecelist, bu_calloc(), bu_free(), bu_realloc(), bn_tol::dist, rt_piecelist::magic, bound_rpp::max, bound_rpp::min, rt_piecelist::npieces, PIECE_BLOCK, rt_piecelist::pieces, rt_ck_overlap(), RT_CK_PIECELIST, RT_CK_SOLTAB, RT_PIECELIST_MAGIC, rt_i::rti_tol, soltab::st_piece_rpps, and rt_piecelist::stp.

Referenced by rt_ct_box().

Here is the call graph for this function:

HIDDEN int rt_ct_box ( struct rt_i rtip,
register union cutter cutp,
register int  axis,
double  where,
int  force 
)

Cut the given box node with a plane along the given axis, at the specified distance "where". Convert the caller's box node into a cut node, allocating two additional box nodes for the new leaves.

If, according to the classifier, both sides have the same number of solids, then nothing is changed, and an error is returned.

The storage strategy used is to make the maximum length of each of the two child boxnodes be the current length of the source node.

Returns - 0 failure 1 success

Definition at line 1242 of file cut.c.

References cutter::bn, boxnode::bn_len, boxnode::bn_max, boxnode::bn_min, boxnode::bn_type, bu_log(), cutter::cn, cutnode::cn_axis, cutnode::cn_l, cutnode::cn_point, cutnode::cn_r, CUT_BOXNODE, CUT_CUTNODE, cutter::cut_type, DEBUG_CUTDETAIL, RT_CK_RTI, rt_ct_free(), rt_ct_get(), rt_ct_populate_box(), rt_ct_release_storage(), and RT_G_DEBUG.

Here is the call graph for this function:

HIDDEN int rt_ck_overlap ( register const fastf_t min,
register const fastf_t max,
register const struct soltab stp,
register const struct rt_i rtip 
)

See if any part of the solid is contained within the bounding box (RPP).

If the solid RPP at least partly overlaps the bounding RPP, invoke the per-solid "classifier" method to perform a more rigorous check.

Returns - !0 if object overlaps box. 0 if no overlap.

Definition at line 1314 of file cut.c.

References BN_CLASSIFY_OUTSIDE, bu_log(), DEBUG_BOXING, rt_functab::ft_classify, OBJ, RT_CHECK_SOLTAB, RT_G_DEBUG, rt_i::rti_tol, soltab::st_aradius, soltab::st_id, soltab::st_max, soltab::st_min, and VPRINT.

Here is the call graph for this function:

HIDDEN size_t rt_ct_piececount ( const union cutter cutp)

Returns the total number of solids and solid "pieces" in a boxnode.

Definition at line 1357 of file cut.c.

References cutter::bn, boxnode::bn_len, boxnode::bn_piecelen, boxnode::bn_piecelist, BU_ASSERT, CUT_BOXNODE, cutter::cut_type, and rt_piecelist::npieces.

Referenced by rt_ct_measure(), and rt_ct_optim().

HIDDEN void rt_ct_optim ( struct rt_i rtip,
register union cutter cutp,
size_t  depth 
)

Definition at line 1384 of file cut.c.

References AXIS, cutter::bn, boxnode::bn_max, boxnode::bn_min, bu_log(), cutter::cn, cutnode::cn_l, cutnode::cn_r, CUT_BOXNODE, CUT_CUTNODE, cutter::cut_type, DEBUG_CUTDETAIL, rt_ct_box(), rt_ct_old_assess(), rt_ct_optim(), rt_ct_piececount(), RT_G_DEBUG, rt_i::rti_cutdepth, X, and Z.

Here is the call graph for this function:

HIDDEN void rt_ct_release_storage ( register union cutter cutp)

Definition at line 1635 of file cut.c.

References cutter::bn, boxnode::bn_len, boxnode::bn_list, boxnode::bn_maxlen, boxnode::bn_maxpiecelen, boxnode::bn_piecelen, boxnode::bn_piecelist, bu_free(), bu_log(), CUT_BOXNODE, CUT_CUTNODE, CUT_NUGRIDNODE, cutter::cut_type, nugridnode::nu_axis, nugridnode::nu_grid, cutter::nugn, and rt_piecelist::pieces.

Here is the call graph for this function:

HIDDEN void rt_ct_free ( struct rt_i rtip,
register union cutter cutp 
)

Definition at line 1688 of file cut.c.

References bu_semaphore_acquire(), bu_semaphore_release(), cutter::cut_forw, RT_CK_RTI, rt_ct_release_storage(), RT_SEM_MODEL, and rt_i::rti_CutFree.

Here is the call graph for this function:

void rt_fr_cut ( struct rt_i rtip,
register union cutter cutp 
)

Definition at line 1790 of file cut.c.

References bp, bu_log(), cutter::cn, cutnode::cn_l, cutnode::cn_r, CUT_BOXNODE, CUT_CUTNODE, CUT_NUGRIDNODE, cutter::cut_type, CUTTER_NULL, nugridnode::nu_cells_per_axis, nugridnode::nu_grid, cutter::nugn, RT_CK_RTI, rt_ct_free(), rt_ct_release_storage(), X, Y, and Z.

Referenced by rt_cut_it().

Here is the call graph for this function:

HIDDEN void rt_plot_cut ( FILE *  fp,
struct rt_i rtip,
register union cutter cutp,
int  lvl 
)

Definition at line 1839 of file cut.c.

References AXIS, cutter::bn, boxnode::bn_max, boxnode::bn_min, bp, cutter::cn, cutnode::cn_l, cutnode::cn_r, CUT_BOXNODE, CUT_CUTNODE, CUT_NUGRIDNODE, cutter::cut_type, nugridnode::nu_axis, nugridnode::nu_cells_per_axis, nu_axis::nu_epos, nugridnode::nu_grid, nu_axis::nu_spos, cutter::nugn, pd_3line(), pdv_3box(), pl_color(), RT_CK_RTI, rt_plot_cut(), X, Y, and Z.

Here is the call graph for this function:

HIDDEN void rt_ct_measure ( register struct rt_i rtip,
register union cutter cutp,
int  depth 
)

Variable Documentation

HIDDEN struct cmp_pair pairs[]
Initial value:
= {
}
HIDDEN int rt_projXmin_comp(const void *p1, const void *p2, void *arg)
Definition: cut.c:174
HIDDEN int rt_projYmax_comp(const void *p1, const void *p2, void *arg)
Definition: cut.c:195
HIDDEN int rt_projZmin_comp(const void *p1, const void *p2, void *arg)
Definition: cut.c:202
HIDDEN int rt_projYmin_comp(const void *p1, const void *p2, void *arg)
Definition: cut.c:188
HIDDEN int rt_projXmax_comp(const void *p1, const void *p2, void *arg)
Definition: cut.c:181
HIDDEN int rt_projZmax_comp(const void *p1, const void *p2, void *arg)
Definition: cut.c:209

Referenced by rt_nugrid_cut().