eic-opticks/sysrap/snd.cc

0001
0002 #include <iostream>
0003 #include <algorithm>
0004 #include <csignal>
0005
0006 #include "glm/glm.hpp"
0007 #include "glm/gtx/string_cast.hpp"
0008 #include <glm/gtx/transform.hpp>
0009 #include <glm/gtc/type_ptr.hpp>
0010
0011 #include "spa.h"
0012 #include "sbb.h"
0013 #include "sxf.h"
0014 #include "scanvas.h"
0015
0016 #include "OpticksCSG.h"
0017 #include "scsg.hh"
0018 #include "snd.hh"
0019 #include "sndtree.h"  // using flexible sn.h
0020
0021 #include "st.h"       // only st::complete_binary_tree_nodes
0022 #include "stra.h"     // transform utilities based on glm
0023
0024
0025
0026 scsg* snd::POOL = nullptr  ;
0027 void snd::SetPOOL( scsg* pool ){ POOL = pool ; }  // static
0028 int snd::Level(){ return POOL ? POOL->level : -1 ; } // static
0029
0030 NPFold* snd::Serialize(){ return POOL ? POOL->serialize() : nullptr ; }  // static
0031 void    snd::Import(const NPFold* fold){ assert(POOL) ; POOL->import(fold) ; } // static
0032 std::string snd::Desc(){  return POOL ? POOL->desc() : "? NO POOL ?" ; } // static
0033
0034
0035
0036 std::string snd::Brief(int idx) // static
0037 {
0038     const snd* nd = Get(idx);
0039     return nd ? nd->brief() : "-" ;
0040 }
0041 std::string snd::Brief(const std::vector<int>& nodes) // static
0042 {
0043     int num_nodes = nodes.size();
0044     std::stringstream ss ;
0045     ss << "snd::Brief num_nodes " << num_nodes << std::endl ;
0046     for(int i=0 ; i < num_nodes ; i++)
0047     {
0048         int idx = nodes[i];
0049         const snd* nd = Get(idx);
0050         assert( nd );
0051         ss << std::setw(2) << i << " : " << nd->brief() << std::endl ;
0052     }
0053     std::string str = ss.str();
0054     return str ;
0055 }
0056
0057 std::string snd::Brief_(const std::vector<snd>& nodes) // static
0058 {
0059     int num_nodes = nodes.size();
0060     std::stringstream ss ;
0061     ss << "snd::Brief_ num_nodes " << num_nodes << std::endl ;
0062     for(int i=0 ; i < num_nodes ; i++)
0063     {
0064         const snd& nd = nodes[i] ;
0065         ss << std::setw(2) << i << " : " << nd.brief() << std::endl ;
0066     }
0067     std::string str = ss.str();
0068     return str ;
0069 }
0070
0071 const snd* snd::Get(int idx){ return POOL ? POOL->getND(idx) : nullptr ; } // static
0072       snd* snd::Get_(int idx){ return POOL ? POOL->getND_(idx) : nullptr ; } // static
0073
0074
0075 int snd::GetMaxDepth( int idx)
0076 {
0077     const snd* nd = Get(idx) ;
0078     return nd ? nd->max_depth() : -1 ;
0079 }
0080 int snd::GetNumNode( int idx)
0081 {
0082     const snd* nd = Get(idx) ;
0083     return nd ? nd->num_node() : -1 ;
0084 }
0085
0086 /**
0087 snd::GetTypes
0088 --------------
0089
0090 **/
0091
0092 void snd::GetTypes(std::vector<int>& types, const std::vector<int>& nd_idxs ) // static
0093 {
0094     int num_idx = nd_idxs.size();
0095     for(int i=0 ; i < num_idx ; i++)
0096     {
0097         int idx = nd_idxs[i];
0098         const snd* nd = Get(idx) ;
0099         types.push_back(nd->typecode) ;
0100     }
0101     assert( nd_idxs.size() == types.size() );
0102 }
0103
0104
0105 /**
0106 snd::GetNodeXForm : xform "pointer" for a node
0107 ----------------------------------------------
0108
0109 Access the idx *snd*  and return the xform *idx*
0110
0111 This is used from U4Solid::init_BooleanSolid
0112 to check that xforms are associated to the left, right
0113 nodes.
0114
0115 */
0116
0117 int snd::GetNodeXForm(int idx)   // static
0118 {
0119     const snd* n = Get(idx);
0120     return n ? n->xform : -1 ;
0121 }
0122
0123
0124 /**
0125 snd::SetNodeXForm
0126 ------------------
0127
0128 Canonical usage is from U4Solid::init_DisplacedSolid collecting boolean rhs transforms
0129
0130 **/
0131
0132 void snd::SetNodeXForm(int idx, const glm::tmat4x4<double>& t )
0133 {
0134     snd* nd = Get_(idx);
0135     nd->combineXF(t);
0136 }
0137 void snd::SetNodeXForm(int idx, const glm::tmat4x4<double>& t, const glm::tmat4x4<double>& v )
0138 {
0139     snd* nd = Get_(idx);
0140     nd->combineXF(t, v);
0141 }
0142
0143
0144
0145
0146 /**
0147 snd::setXF
0148 ---------------
0149
0150 Calling setXF again will just adds another transform
0151 and updates the snd::xform integer reference, effectively leaking the old transform.
0152
0153 HMM if there is a transform already present (eg ellipsoid scale transform)
0154 the setXF actually needs to combine the transforms as was done in nnode::set_transform
0155 so that with snd::combineXF
0156
0157
0158 **/
0159
0160 void snd::setXF(const glm::tmat4x4<double>& t )
0161 {
0162     glm::tmat4x4<double> v = glm::inverse(t) ;
0163     setXF(t, v);
0164 }
0165 void snd::combineXF(const glm::tmat4x4<double>& t )
0166 {
0167     glm::tmat4x4<double> v = glm::inverse(t) ;
0168     combineXF(t, v);
0169 }
0170
0171
0172 void snd::setXF(const glm::tmat4x4<double>& t, const glm::tmat4x4<double>& v )
0173 {
0174     if( xform > -1 )
0175     {
0176         if(Level()>-1) std::cout
0177             << "snd::setXF STOMPING"
0178             << " xform " << xform
0179             << std::endl
0180             << stra<double>::Desc(t,v, "t", "v")
0181             << std::endl
0182             ;
0183     }
0184
0185
0186     sxf xf ;
0187     xf.t = t ;
0188     xf.v = v ;
0189
0190     CheckPOOL("snd::setXForm") ;
0191     xform = POOL->addXF(xf) ;
0192 }
0193
0194 /**
0195 snd::combineXF
0196 ----------------
0197
0198 Transform product ordering is an ad-hoc guess::
0199
0200     tt = current->t * t
0201     vv = v * current->v
0202
0203 **/
0204
0205 void snd::combineXF( const glm::tmat4x4<double>& t, const glm::tmat4x4<double>& v )
0206 {
0207     sxf* current = getXF_();
0208     if(current == nullptr)
0209     {
0210         setXF(t,v);
0211     }
0212     else
0213     {
0214         glm::tmat4x4<double> tt = current->t * t ;
0215         glm::tmat4x4<double> vv = v * current->v ;
0216
0217         current->t = tt ;
0218         current->v = vv ;
0219     }
0220 }
0221
0222
0223 const sxf* snd::GetXF(int idx)  // static
0224 {
0225     const snd* n = Get(idx);
0226     return n ? n->getXF() : nullptr ;
0227 }
0228 sxf* snd::GetXF_(int idx)  // static
0229 {
0230     snd* n = Get_(idx);
0231     return n ? n->getXF_() : nullptr ;
0232 }
0233
0234 const sxf* snd::getXF() const
0235 {
0236     CheckPOOL("snd::getXF") ;
0237     return POOL->getXF(xform) ;
0238 }
0239 sxf* snd::getXF_()
0240 {
0241     CheckPOOL("snd::getXF_") ;
0242     return POOL->getXF_(xform) ;
0243 }
0244
0245 /**
0246 snd::NodeTransformProduct
0247 ---------------------------
0248
0249 cf nmat4triple::product
0250
0251 1. finds CSG node ancestors of snd idx
0252
0253
0254 **/
0255
0256 void snd::NodeTransformProduct(int idx, glm::tmat4x4<double>& t, glm::tmat4x4<double>& v, bool reverse, std::ostream* out)  // static
0257 {
0258     std::vector<int> nds ;
0259     Ancestors(idx, nds);
0260     nds.push_back(idx);
0261     int num_nds = nds.size();
0262
0263     if(out)
0264     {
0265         *out
0266              << std::endl
0267              << "snd::NodeTransformProduct"
0268              << " idx " << idx
0269              << " reverse " << reverse
0270              << " num_nds " << num_nds
0271              << std::endl
0272              ;
0273     }
0274
0275     glm::tmat4x4<double> tp(1.);
0276     glm::tmat4x4<double> vp(1.);
0277
0278     for(int i=0 ; i < num_nds ; i++ )
0279     {
0280         int j  = num_nds - 1 - i ;
0281         int ii = nds[reverse ? j : i] ;
0282         int jj = nds[reverse ? i : j] ;
0283
0284         const sxf* ixf = GetXF(ii) ;
0285         const sxf* jxf = GetXF(jj) ;
0286
0287         if(out)
0288         {
0289             *out
0290                 << " i " << i
0291                 << " j " << j
0292                 << " ii " << ii
0293                 << " jj " << jj
0294                 << " ixf " << ( ixf ? "Y" : "N" )
0295                 << " jxf " << ( jxf ? "Y" : "N" )
0296                 << std::endl
0297                 ;
0298
0299            if(ixf) *out << stra<double>::Desc( ixf->t, ixf->v, "(ixf.t)", "(ixf.v)" ) << std::endl ;
0300            if(jxf) *out << stra<double>::Desc( jxf->t, jxf->v, "(jxf.t)", "(jxf.v)" ) << std::endl ;
0301         }
0302
0303
0304         if(ixf) tp *= ixf->t ;
0305         if(jxf) vp *= jxf->v ;  // // inverse-transform product in opposite order
0306     }
0307     memcpy( glm::value_ptr(t), glm::value_ptr(tp), sizeof(glm::tmat4x4<double>) );
0308     memcpy( glm::value_ptr(v), glm::value_ptr(vp), sizeof(glm::tmat4x4<double>) );
0309
0310     if(out) *out << stra<double>::Desc( tp, vp , "tp", "vp" ) << std::endl ;
0311 }
0312
0313 std::string snd::DescNodeTransformProduct(int root, glm::tmat4x4<double>& t, glm::tmat4x4<double>& v,  bool reverse) // static
0314 {
0315     std::stringstream ss ;
0316     ss << "snd::DescNodeTransformProduct" << std::endl ;
0317     NodeTransformProduct( root, t, v, reverse, &ss );
0318     std::string str = ss.str();
0319     return str ;
0320 }
0321
0322
0323 void snd::node_transform_product(glm::tmat4x4<double>& t, glm::tmat4x4<double>& v,  bool reverse, std::ostream* out ) const
0324 {
0325     NodeTransformProduct(index, t, v, reverse, out);
0326 }
0327
0328
0329
0330
0331
0332
0333 void snd::SetLabel(int idx, const char* label_ ) // static
0334 {
0335     snd* nd = Get_(idx);
0336     nd->setLabel(label_);
0337 }
0338
0339
0340
0341
0342 /**
0343 snd::SetLVID : label node tree
0344 ----------------------------------
0345
0346 This gets invoked from the snd roots only,
0347 as its called for each root from U4Tree::initSolid
0348
0349 **/
0350 void snd::SetLVID(int idx, int lvid)  // static
0351 {
0352     snd* nd = Get_(idx);
0353     nd->setLVID(lvid);
0354     if(nd->is_root()) nd->sibdex = 0 ;
0355
0356     int chk = nd->checktree();
0357     if( chk != 0 )
0358     {
0359         if(Level() > 0 ) std::cerr
0360            << "snd::SetLVID"
0361            << " idx " << idx
0362            << " lvid " << lvid
0363            << " checktree " << chk
0364            << std::endl
0365            << " POOL.desc "
0366            << POOL->desc()
0367            ;
0368     }
0369     assert( chk == 0 );
0370 }
0371
0372
0373 /**
0374 snd::GetLVID (GetLVIDNodes more appropos)
0375 -------------------------------------------------
0376
0377 Q: Is the last snd returned always root ?
0378 A: As trees are created postorder and nodes get added to the POOL
0379    in creation order I think that indeed the last must always be the root node.
0380
0381    * NOT SO SURE ABOUT THAT
0382
0383 **/
0384
0385 void snd::GetLVID( std::vector<snd>& nds, int lvid )  // static
0386 {
0387     POOL->getLVID(nds, lvid);
0388
0389     int num_nd = nds.size();
0390     assert( num_nd > 0 );
0391     const snd& last = nds[num_nd-1] ;
0392     bool last_expect =  last.is_root()  ;
0393     if(!last_expect) std::cerr << "snd::GetLVID last_expect " << std::endl ;
0394     assert( last_expect );
0395 }
0396
0397 /**
0398 snd::GetLVRoot
0399 ---------------
0400
0401 First snd with the lvid and snd::is_root():true in (scsg)POOL
0402
0403 **/
0404 const snd* snd::GetLVRoot( int lvid ) // static
0405 {
0406     const snd* root = POOL->getLVRoot(lvid);
0407     return root ;
0408 }
0409
0410 int snd::GetLVNumNode( int lvid ) // static
0411 {
0412     const snd* root = GetLVRoot(lvid);
0413     return root ? root->getLVNumNode() : -1 ;
0414 }
0415 int snd::GetLVBinNode( int lvid ) // static    NumBinNode
0416 {
0417     const snd* root = GetLVRoot(lvid);
0418     return root ? root->getLVBinNode() : -1 ;
0419 }
0420 int snd::GetLVSubNode( int lvid ) // static    NumSubNode
0421 {
0422     const snd* root = GetLVRoot(lvid);
0423     return root ? root->getLVSubNode() : -1 ;
0424 }
0425
0426
0427
0428
0429 /**
0430 snd::getLVNumNode
0431 -------------------
0432
0433 Returns total number of nodes that can contain
0434 a complete binary tree + listnode constituents
0435 serialization of this node.
0436
0437 **/
0438
0439 int snd::getLVNumNode() const
0440 {
0441     int bn = getLVBinNode() ;
0442     int sn = getLVSubNode() ;
0443     return bn + sn ;
0444 }
0445
0446 /**
0447 snd::getLVBinNode
0448 ------------------
0449
0450 Returns the number of nodes in a complete binary tree
0451 of height corresponding to the max_binary_depth
0452 of this node.
0453 **/
0454
0455 int snd::getLVBinNode() const
0456 {
0457     int h = max_binary_depth();
0458     return st::complete_binary_tree_nodes( h );
0459 }
0460
0461 /**
0462 snd::getLVSubNode
0463 -------------------
0464
0465 Sum of children of compound nodes found beneath this node.
0466 HMM: this assumes compound nodes only contain leaf nodes
0467
0468 Notice that the compound nodes themselves are regarded as part of
0469 the binary tree.
0470
0471 **/
0472 int snd::getLVSubNode() const
0473 {
0474     int constituents = 0 ;
0475     std::vector<int> subs ;
0476     typenodes_(subs, CSG_CONTIGUOUS, CSG_DISCONTIGUOUS, CSG_OVERLAP );
0477     int nsub = subs.size();
0478     for(int i=0 ; i < nsub ; i++)
0479     {
0480         int idx = subs[i] ;
0481         const snd* nd = Get(idx);
0482         assert( nd->typecode == CSG_CONTIGUOUS || nd->typecode == CSG_DISCONTIGUOUS );
0483         constituents += nd->num_child ;
0484     }
0485     return constituents ;
0486 }
0487
0488
0489
0490 /**
0491 snd::GetLVNodesComplete
0492 -------------------------
0493
0494 As the traversal is constrained to the binary tree portion of the n-ary snd tree
0495 can populate a vector of *snd* pointers in complete binary tree level order indexing
0496 with nullptr left for the zeros.  This is similar to the old NCSG::export_tree_r.
0497
0498 **/
0499
0500 void snd::GetLVNodesComplete(std::vector<const snd*>& nds, int lvid) // static
0501 {
0502     const snd* root = GetLVRoot(lvid);  // first snd in (scsg)POOL
0503     root->getLVNodesComplete(nds);
0504
0505     int level = Level();
0506
0507     if(level > 0 && nds.size() > 8 )
0508     {
0509         std::cout
0510             << "snd::GetLVNodesComplete"
0511             << " lvid " << lvid
0512             << " level " << level
0513             << std::endl
0514             << root->rbrief()
0515             << std::endl
0516             << root->render(3)
0517             ;
0518     }
0519 }
0520
0521
0522 /**
0523 snd::getLVNodesComplete
0524 -------------------------
0525
0526 **/
0527
0528 void snd::getLVNodesComplete(std::vector<const snd*>& nds) const
0529 {
0530     int bn = getLVBinNode();
0531     int sn = getLVSubNode();
0532     int numParts = bn + sn ;
0533     nds.resize(numParts);
0534
0535     assert( sn == 0 ); // CHECKING : AS IMPL LOOKS LIKE ONLY HANDLES BINARY NODES
0536
0537     GetLVNodesComplete_r( nds, this, 0 );
0538 }
0539
0540
0541 void snd::GetLVNodesComplete_r(std::vector<const snd*>& nds, const snd* nd, int idx)  // static
0542 {
0543     assert( idx < int(nds.size()) );
0544     nds[idx] = nd ;
0545
0546     if( nd->num_child > 0 && nd->is_listnode() == false ) // non-list operator node
0547     {
0548         assert( nd->num_child == 2 ) ;
0549         int ch = nd->first_child ;
0550         for(int i=0 ; i < nd->num_child ; i++)
0551         {
0552             const snd* child = snd::Get(ch) ;
0553             assert( child->index == ch );
0554
0555             int cidx = 2*idx + 1 + i ; // 0-based complete binary tree level order indexing
0556
0557             GetLVNodesComplete_r(nds, child, cidx );
0558
0559             ch = child->next_sibling ;
0560         }
0561     }
0562 }
0563
0564
0565
0566
0567 std::string snd::Desc(      int idx){ return POOL ? POOL->descND(idx) : "-" ; } // static
0568 std::string snd::DescParam( int idx){ return POOL ? POOL->descPA(idx) : "-" ; } // static
0569 std::string snd::DescXForm( int idx){ return POOL ? POOL->descXF(idx) : "-" ; } // static
0570 std::string snd::DescAABB(  int idx){ return POOL ? POOL->descBB(idx) : "-" ; } // static
0571
0572
0573 int snd::Add(const snd& nd) // static
0574 {
0575     assert( POOL && "snd::Add MUST SET snd::SetPOOL to scsg instance first" );
0576     return POOL->addND(nd);
0577 }
0578
0579
0580 bool snd::is_listnode() const
0581 {
0582     return CSG::IsList(typecode);
0583 }
0584
0585 std::string snd::tag() const
0586 {
0587     return typecode < 0 ? "negative-typecode-ERR" : CSG::Tag(typecode) ;
0588 }
0589
0590 int snd::idx() const {  return index ; }
0591
0592
0593 std::string snd::brief() const
0594 {
0595     char l0 = label[0] == '\0' ? '-' : label[0] ;
0596     int w = 5 ;
0597     std::stringstream ss ;
0598     ss
0599        << l0
0600        << " ix:" << std::setw(w) << index
0601        << " dp:" << std::setw(w) << depth
0602        << " sx:" << std::setw(w) << sibdex
0603        << " pt:" << std::setw(w) << parent
0604        << "    "
0605        << " nc:" << std::setw(w) << num_child
0606        << " fc:" << std::setw(w) << first_child
0607        << " ns:" << std::setw(w) << next_sibling
0608        << " lv:" << std::setw(w) << lvid
0609        << "    "
0610        << " tc:" << std::setw(w) << typecode
0611        << " pa:" << std::setw(w) << param
0612        << " bb:" << std::setw(w) << aabb
0613        << " xf:" << std::setw(w) << xform
0614        << "    "
0615        << tag()
0616        ;
0617     std::string str = ss.str();
0618     return str ;
0619 }
0620
0621 std::string snd::rbrief() const
0622 {
0623     std::stringstream ss ;
0624     ss << "snd::rbrief" << std::endl ;
0625
0626     rbrief_r(ss, 0) ;
0627     std::string str = ss.str();
0628     return str ;
0629 }
0630
0631
0632 void snd::rbrief_r(std::ostream& os, int d) const
0633 {
0634     os << brief() << std::endl ;
0635     int ch = first_child ;
0636     while( ch > -1 )
0637     {
0638         snd& child = POOL->node[ch] ;
0639         child.rbrief_r(os, d+1) ;
0640         ch = child.next_sibling ;
0641     }
0642 }
0643
0644
0645
0646
0647
0648
0649 const char* snd::ERROR_NO_POOL_NOTES = R"(
0650 snd::ERROR_NO_POOL_NOTES
0651 ======================================
0652
0653 The POOL static scsg instance is nullptr
0654
0655 * MUST call snd::SetPOOL to an scsg instance before using snd
0656
0657 * stree instanciation will do this, so the preferred approach
0658   is to instanciate stree in the main prior to using any snd methods.
0659
0660 ::
0661
0662     #include "stree.h"
0663     #include "snd.hh"
0664
0665     int main(int argc, char** argv)
0666     {
0667         stree st ;
0668         int a = snd::Sphere(100.) ;
0669         return 0 ;
0670     }
0671
0672
0673 )" ;
0674
0675 void snd::CheckPOOL(const char* msg) // static
0676 {
0677     if(POOL) return ;
0678     std::cout << "snd::CheckPOOL " << msg << " FATAL " << std::endl ;
0679     std::cout <<  ERROR_NO_POOL_NOTES  ;
0680     assert( POOL );
0681 }
0682
0683
0684 void snd::setParam( double x, double y, double z, double w, double z1, double z2 )
0685 {
0686     CheckPOOL("snd::setParam") ;
0687     spa o = { x, y, z, w, z1, z2 } ;
0688     param = POOL->addPA(o) ;
0689 }
0690 void snd::setAABB( double x0, double y0, double z0, double x1, double y1, double z1 )
0691 {
0692     CheckPOOL("snd::setAABB") ;
0693     sbb o = {x0, y0, z0, x1, y1, z1} ;
0694
0695     aabb = POOL->addBB(o) ;
0696 }
0697
0698 const double* snd::getParam() const
0699 {
0700     if(param == -1 ) return nullptr ;
0701     assert( param > -1 );
0702     const spa& pa = POOL->param[param] ;
0703     return pa.data() ;
0704 }
0705 const double* snd::getAABB() const
0706 {
0707     if(aabb == -1 ) return nullptr ;
0708     assert( aabb > -1 );
0709     const sbb& bb = POOL->aabb[aabb] ;
0710     return bb.cdata() ;
0711 }
0712
0713 bool snd::hasUnsetAABB() const   // nullptr or all zero
0714 {
0715     const double* aabb = getAABB();
0716     if(aabb == nullptr) return true ;
0717     return sbb::IsZero(aabb);
0718 }
0719 bool snd::hasAABB() const   // not-nullptr and not all zero
0720 {
0721     const double* aabb = getAABB();
0722     return aabb != nullptr && !sbb::IsZero(aabb) ;
0723 }
0724
0725
0726
0727
0728
0729 void snd::setLabel( const char* label_ )
0730 {
0731     // strncpy( &label[0], label_, sizeof(label) );
0732     //
0733     // above gives warning: specified bound 16 equals destination size [-Wstringop-truncation]
0734     // but truncation of the null terminator is intended
0735     // so switch to memcpy to avoid the warning
0736
0737     memset( &label[0], 0, sizeof(label) );
0738     memcpy( &label[0], label_, std::min(strlen(label_), sizeof(label))  );
0739
0740 }
0741
0742 void snd::setLVID(int lvid_)
0743 {
0744     setLVID_r(lvid_, 0);
0745 }
0746 void snd::setLVID_r(int lvid_, int d )
0747 {
0748     lvid = lvid_ ;
0749     depth = d ;
0750
0751     int ch = first_child ;
0752     while( ch > -1 )
0753     {
0754         snd& child = POOL->node[ch] ;
0755         child.setLVID_r(lvid, depth+1 );
0756         ch = child.next_sibling ;
0757     }
0758 }
0759
0760 int snd::checktree() const
0761 {
0762     int chk_D = checktree_r('D', 0);
0763     int chk_P = checktree_r('P', 0);
0764     int chk = chk_D + chk_P ;
0765
0766     if( chk > 0 )
0767     {
0768         if(Level()>0) std::cerr
0769             << "snd::checktree"
0770             << " chk_D " << chk_D
0771             << " chk_P " << chk_P
0772             << brief()
0773             << std::endl
0774             ;
0775     }
0776
0777     return chk ;
0778 }
0779 int snd::checktree_r(char code,  int d ) const
0780 {
0781     int chk = 0 ;
0782     int ch = first_child ;
0783
0784     if( code == 'D' ) // check expected depth
0785     {
0786         if(d != depth) chk += 1 ;
0787     }
0788     else if( code == 'P' ) // check for non-roots without parent set
0789     {
0790         if( depth > 0 && parent < 0 ) chk += 1 ;
0791     }
0792
0793
0794     while( ch > -1 )
0795     {
0796         snd& child = POOL->node[ch] ;
0797
0798         chk += child.checktree_r(code,  d + 1 );
0799
0800         ch = child.next_sibling ;
0801     }
0802     return chk ;
0803 }
0804
0805
0806 /**
0807 snd::Visit
0808 -----------
0809
0810 Example static function that can be passed to the traverse using::
0811
0812     snd::PreorderTraverse(root, std::bind( &snd::Visit, std::placeholders::_1 ) );
0813
0814 Note that the fn above is a static member function.
0815
0816 Although it is possible to bind to a non-static member function using "this"
0817 object pointer as first argument that would not be useful with a recursive traversal
0818 as the point of the traversal is to visit multiple nodes of the tree.  Using a static
0819 with int argument which picks the node sidesteps this.
0820
0821 **/
0822 void snd::Visit(int idx)  // static
0823 {
0824     snd* nd = Get_(idx);
0825
0826     std::cout
0827         << "snd::Visit"
0828         << " idx " << std::setw(3) << idx
0829         << " : " << nd->brief()
0830         << std::endl
0831         ;
0832 }
0833
0834
0835 void snd::PreorderTraverse(int idx, std::function<void(int)> fn) // static
0836 {
0837     snd* nd = Get_(idx);
0838     nd->preorder_traverse( fn );
0839 }
0840
0841 void snd::preorder_traverse( std::function<void(int)> fn )
0842 {
0843     preorder_traverse_r(fn, 0);
0844 }
0845 void snd::preorder_traverse_r( std::function<void(int)> fn, int d)
0846 {
0847     fn(index);
0848
0849     int ch = first_child ;
0850     while( ch > -1 )
0851     {
0852         snd* child = Get_(ch) ;
0853         child->preorder_traverse_r(fn,  d + 1 );
0854         ch = child->next_sibling ;
0855     }
0856 }
0857
0858
0859 void snd::PostorderTraverse(int idx, std::function<void(int)> fn ) // static
0860 {
0861     snd* nd = Get_(idx);
0862     nd->postorder_traverse( fn );
0863 }
0864 void snd::postorder_traverse( std::function<void(int)> fn )
0865 {
0866     postorder_traverse_r(fn, 0);
0867 }
0868 void snd::postorder_traverse_r( std::function<void(int)> fn, int d)
0869 {
0870     int ch = first_child ;
0871     while( ch > -1 )
0872     {
0873         snd* child = Get_(ch) ;
0874         child->postorder_traverse_r(fn,  d + 1 );
0875         ch = child->next_sibling ;
0876     }
0877
0878     fn(index);
0879
0880 }
0881
0882
0883
0884
0885
0886
0887
0888
0889 /**
0890 snd::max_depth
0891 ---------------
0892
0893 Q: How to handle compound nodes CSG_CONTIGUOUS/CSG_DISCONTIGUOUS with regard to depth ?
0894 A: Kinda depends on the purpose of the depth ? Need separate methods max_treedepth ?
0895 A: As compound nodes should only hold leaves the default way to get
0896    depth should usually be correct. But there are special cases where it
0897    might not be. For example where the root node is compound the max depth
0898    should be 0. Suggests should stop traversal when hit compound ?
0899
0900 **/
0901
0902 int snd::max_depth() const
0903 {
0904     return max_depth_r(0);
0905 }
0906 int snd::max_depth_r(int d) const
0907 {
0908     int mx = d ;
0909     int ch = first_child ;
0910     while( ch > -1 )
0911     {
0912         snd& child = POOL->node[ch] ;
0913         mx = std::max( mx,  child.max_depth_r(d + 1) ) ;
0914         ch = child.next_sibling ;
0915     }
0916     return mx ;
0917 }
0918
0919 /**
0920 snd::max_binary_depth
0921 -----------------------
0922
0923 Maximum depth of the binary compliant portion of the n-ary tree,
0924 ie with listnodes not recursed and where nodes have either 0 or 2 children.
0925 The listnodes are regarded as leaf node primitives.
0926
0927 * Despite the *snd* tree being an n-ary tree (able to hold polycone and multiunion compounds)
0928   it must be traversed as a binary tree by regarding the compound nodes as effectively
0929   leaf node "primitives" in order to generate the indices into the complete binary
0930   tree serialization in level order
0931
0932 * hence the recursion is halted at list nodes
0933
0934 **/
0935 int snd::max_binary_depth() const
0936 {
0937     return max_binary_depth_r(0) ;
0938 }
0939 int snd::max_binary_depth_r(int d) const
0940 {
0941     int mx = d ;
0942
0943     if( is_listnode() == false )
0944     {
0945         if( num_child > 0 ) assert( num_child == 2 ) ;
0946         int ch = first_child ;
0947         for(int i=0 ; i < num_child ; i++)
0948         {
0949             snd& child = POOL->node[ch] ;
0950             assert( child.index == ch );
0951             mx = std::max( mx,  child.max_binary_depth_r(d + 1) ) ;
0952             ch = child.next_sibling ;
0953         }
0954     }
0955     return mx ;
0956 }
0957
0958
0959 int snd::num_node() const
0960 {
0961     return num_node_r(0);
0962 }
0963 int snd::num_node_r(int d) const
0964 {
0965     int nn = 1 ;   // always at least 1 node,  HMM: no exclusion of CSG_ZERO ?
0966     int ch = first_child ;
0967     while( ch > -1 )
0968     {
0969         snd& child = POOL->node[ch] ;
0970         nn += child.num_node_r(d + 1);
0971         ch = child.next_sibling ;
0972     }
0973     return nn ;
0974 }
0975
0976
0977 bool snd::is_root() const  // NB depth gets set by calling setLVID
0978 {
0979     return depth == 0 && parent == -1 ;
0980 }
0981
0982 bool snd::is_leaf() const
0983 {
0984     return num_child == 0 ;
0985 }
0986
0987 bool snd::is_binary_leaf() const
0988 {
0989     return num_child == 0 || CSG::IsList(typecode ) ;
0990 }
0991
0992 bool snd::is_sibdex(int q_sibdex) const
0993 {
0994     return sibdex == q_sibdex ;
0995 }
0996
0997
0998
0999
1000
1001
1002 /**
1003 inorder
1004 ------------
1005
1006 Try to adapt X4SolidTree::inorder_r to n-ary tree
1007
1008 For inorder traversal of an n-ary tree need to define how to split the children.
1009
1010 binary:  i = 0, 1,     num_child = 2  split = 1 = num_child - 1
1011 3-ary :  i = 0, 1, 2   num_child = 3  split = 2 = num_child - 1
1012
1013 :google:`inorder traveral of n-ary tree`
1014
1015 https://www.geeksforgeeks.org/inorder-traversal-of-an-n-ary-tree/
1016
1017 The inorder traversal of an N-ary tree is defined as visiting all the children
1018 except the last then the root and finally the last child recursively.
1019
1020 https://ondrej-kvasnovsky-2.gitbook.io/algorithms/data-structures/n-ary-tree
1021
1022 A binary tree can be traversed in preorder, inorder, postorder or level-order.
1023 Among these traversal methods, preorder, postorder and level-order traversal
1024 are suitable to be extended to an N-ary tree.
1025
1026 https://stackoverflow.com/questions/23778489/in-order-tree-traversal-for-non-binary-trees
1027
1028 **/
1029
1030
1031 void snd::Inorder(std::vector<int>& order, int idx ) // static
1032 {
1033     const snd* nd = Get(idx);
1034     nd->inorder(order);
1035 }
1036
1037 void snd::inorder(std::vector<int>& order ) const
1038 {
1039     inorder_r(order, 0);
1040 }
1041
1042 void snd::inorder_r(std::vector<int>& order, int d ) const
1043 {
1044     if( num_child <= 0 )
1045     {
1046         order.push_back(index) ;
1047     }
1048     else
1049     {
1050         int split = num_child - 1 ;
1051         int ch = first_child ;
1052
1053         for(int i=0 ; i < split ; i++)
1054         {
1055             snd& child = POOL->node[ch] ;
1056             assert( child.index == ch );
1057             child.inorder_r( order, d+1 );
1058             ch = child.next_sibling ;
1059         }
1060
1061         order.push_back(index) ;
1062
1063         for(int i=split ; i < num_child ; i++)
1064         {
1065             snd& child = POOL->node[ch] ;
1066             assert( child.index == ch );
1067             child.inorder_r( order, d+1 );
1068             ch = child.next_sibling ;
1069         }
1070     }
1071 }
1072
1073 /**
1074 snd::Ancestors
1075 ---------------
1076
1077 Collect by following parent links then reverse
1078 the vector to put into root first order.
1079
1080 **/
1081
1082 void snd::Ancestors(int idx, std::vector<int>& nodes)  // static
1083 {
1084     const snd* nd = Get(idx) ;
1085     while( nd->parent > -1 )
1086     {
1087         nodes.push_back(nd->parent);
1088         nd = Get(nd->parent) ;
1089     }
1090     std::reverse( nodes.begin(), nodes.end() );
1091 }
1092
1093 void snd::ancestors(std::vector<int>& nodes) const
1094 {
1095     Ancestors(index, nodes);
1096 }
1097
1098
1099
1100
1101
1102
1103
1104 void snd::leafnodes( std::vector<int>& nodes ) const
1105 {
1106     leafnodes_r(nodes, 0 );
1107 }
1108
1109 void snd::leafnodes_r( std::vector<int>& nodes, int d  ) const
1110 {
1111     if(is_leaf()) nodes.push_back(index);
1112
1113     int ch = first_child ;
1114     for(int i=0 ; i < num_child ; i++)
1115     {
1116         snd& child = POOL->node[ch] ;
1117         assert( child.index == ch );
1118         child.leafnodes_r(nodes, d+1 );
1119         ch = child.next_sibling ;
1120     }
1121 }
1122
1123 int snd::Find(int idx, char l0) // static
1124 {
1125     const snd* nd = Get(idx) ;
1126     return nd ? nd->find(l0) : -1 ;
1127 }
1128
1129 int snd::find(char l0) const
1130 {
1131     std::vector<int> nodes ;
1132     find_r(nodes, l0, 0) ;
1133     return nodes.size() == 1 ? nodes[0] : -1 ;
1134 }
1135
1136 void snd::find_r(std::vector<int>& nodes, char l0, int d) const
1137 {
1138     if(label[0] == l0) nodes.push_back(index);
1139
1140     int ch = first_child ;
1141     for(int i=0 ; i < num_child ; i++)
1142     {
1143         const snd* child = Get(ch) ;
1144         assert( child->index == ch );
1145         child->find_r(nodes, l0, d+1 );
1146         ch = child->next_sibling ;
1147     }
1148 }
1149
1150
1151
1152 /**
1153 snd::typenodes_
1154 -----------------
1155
1156 Collect snd indices with typecode provided in the args.
1157
1158 **/
1159
1160 template<typename ... Args>
1161 void snd::typenodes_(std::vector<int>& nodes, Args ... tcs ) const
1162 {
1163     std::vector<OpticksCSG_t> types = {tcs ...};
1164     typenodes_r_(nodes, types, 0 );
1165 }
1166
1167 // NB MUST USE SYSRAP_API TO PLANT THE SYMBOLS IN THE LIB (OR MAKE THEM VISIBLE FROM ELSEWHERE)
1168 template SYSRAP_API void snd::typenodes_(std::vector<int>& nodes, OpticksCSG_t ) const ;
1169 template SYSRAP_API void snd::typenodes_(std::vector<int>& nodes, OpticksCSG_t, OpticksCSG_t ) const ;
1170 template SYSRAP_API void snd::typenodes_(std::vector<int>& nodes, OpticksCSG_t, OpticksCSG_t, OpticksCSG_t ) const ;
1171
1172 /**
1173 snd::typenodes_r_
1174 -------------------
1175
1176 Recursive traverse CSG tree collecting snd::index when the snd::typecode is in the types vector.
1177
1178 **/
1179
1180 void snd::typenodes_r_(std::vector<int>& nodes, const std::vector<OpticksCSG_t>& types, int d) const
1181 {
1182     if(has_type(types)) nodes.push_back(index);
1183
1184     int ch = first_child ;
1185     for(int i=0 ; i < num_child ; i++)
1186     {
1187         snd& child = POOL->node[ch] ;
1188         assert( child.index == ch );
1189         child.typenodes_r_(nodes, types, d+1 );
1190         ch = child.next_sibling ;
1191     }
1192 }
1193
1194 bool snd::has_type(const std::vector<OpticksCSG_t>& types) const
1195 {
1196     return std::find( types.begin(), types.end(), typecode ) != types.end() ;
1197 }
1198
1199
1200 template<typename ... Args>
1201 std::string snd::DescType(Args ... tcs)  // static
1202 {
1203     std::vector<OpticksCSG_t> types = {tcs ...};
1204     int num_tc = types.size();
1205
1206     std::stringstream ss ;
1207     for(int i=0 ; i < num_tc ; i++)
1208     {
1209         int tc = types[i];
1210         ss << CSG::Tag(tc)  ;
1211         if(i < num_tc - 1) ss << "," ;
1212     }
1213     std::string str = ss.str();
1214     return str ;
1215 }
1216
1217 template SYSRAP_API std::string snd::DescType(OpticksCSG_t );
1218 template SYSRAP_API std::string snd::DescType(OpticksCSG_t, OpticksCSG_t );
1219 template SYSRAP_API std::string snd::DescType(OpticksCSG_t, OpticksCSG_t, OpticksCSG_t );
1220
1221
1222
1223
1224 void snd::typenodes(std::vector<int>& nodes, int tc ) const
1225 {
1226     typenodes_r(nodes, tc, 0 );
1227 }
1228 void snd::typenodes_r(std::vector<int>& nodes, int tc, int d) const
1229 {
1230     if(typecode == tc ) nodes.push_back(index);
1231
1232     int ch = first_child ;
1233     for(int i=0 ; i < num_child ; i++)
1234     {
1235         snd& child = POOL->node[ch] ;
1236         assert( child.index == ch );
1237         child.typenodes_r(nodes, tc, d+1 );
1238         ch = child.next_sibling ;
1239     }
1240 }
1241
1242
1243
1244 int snd::get_ordinal( const std::vector<int>& order ) const
1245 {
1246     int ordinal = std::distance( order.begin(), std::find(order.begin(), order.end(), index )) ;
1247     return ordinal < int(order.size()) ? ordinal : -1 ;
1248 }
1249
1250
1251 std::string snd::dump() const
1252 {
1253     std::stringstream ss ;
1254     dump_r( ss, 0 );
1255     std::string str = ss.str();
1256     return str ;
1257 }
1258
1259 void snd::dump_r( std::ostream& os, int d ) const
1260 {
1261     os << "snd::dump_r"
1262        << " d " << d
1263        << brief()
1264        << std::endl
1265        ;
1266
1267     int ch = first_child ;
1268     while( ch > -1 )
1269     {
1270         snd& child = POOL->node[ch] ;
1271         child.dump_r( os, d+1 );
1272         ch = child.next_sibling ;
1273     }
1274 }
1275
1276
1277
1278 std::string snd::dump2() const
1279 {
1280     std::stringstream ss ;
1281     dump2_r( ss, 0 );
1282     std::string str = ss.str();
1283     return str ;
1284 }
1285
1286 void snd::dump2_r( std::ostream& os, int d ) const
1287 {
1288     os << "snd::dump2_r"
1289        << " d " << d
1290        << brief()
1291        << std::endl
1292        ;
1293
1294     int ch = first_child ;
1295     for(int i=0 ; i < num_child ; i++)
1296     {
1297         snd& child = POOL->node[ch] ;
1298         child.dump2_r( os, d+1 );
1299         ch = child.next_sibling ;
1300     }
1301 }
1302
1303
1304
1305 std::string snd::Render(int idx, int mode)  // static
1306 {
1307     const snd* n = Get(idx);
1308     return n ? n->render(mode) : "snd::Render bad idx ";
1309 }
1310
1311 std::string snd::render(int mode_) const
1312 {
1313     int width = num_node();
1314     int height = max_depth();
1315     int defmode = width > 16 ? 0 : 1 ;
1316     int mode = mode_ > -1 ? mode_ : defmode ;
1317
1318     std::vector<int> order ;
1319     inorder(order);
1320     assert( int(order.size()) == width );
1321
1322     scanvas canvas( width+1, height+2, 4, 2 );
1323     render_r(&canvas, order, mode, 0);
1324
1325     std::stringstream ss ;
1326     ss
1327        << std::endl
1328        << "snd::render"
1329        << " width " << width
1330        << " height " << height
1331        << " mode " << mode
1332        << std::endl
1333        << std::endl
1334        << canvas.c
1335        << std::endl
1336        ;
1337
1338     std::string str = ss.str();
1339     return str ;
1340 }
1341
1342 void snd::render_r(scanvas* canvas, const std::vector<int>& order, int mode, int d) const
1343 {
1344     render_v(canvas, order, mode, d);   // visit in preorder
1345
1346     int ch = first_child ;
1347     while( ch > -1 )
1348     {
1349         snd& child = POOL->node[ch] ;
1350         child.render_r( canvas, order, mode, d+1 );
1351         ch = child.next_sibling ;
1352     }
1353 }
1354
1355
1356 /**
1357 snd::render_v
1358 -----------------
1359 +-------+--------------------------------+
1360 | mode  |  notes                         |
1361 +=======+================================+
1362 |  0    |  first character of snd label  |
1363 +-------+--------------------------------+
1364 |  1    |  snd::index                    |
1365 +-------+--------------------------------+
1366 |  2    |  snd::typecode                 |
1367 +-------+--------------------------------+
1368 |  3    |  snd::typecode CSG::Tag        |
1369 +-------+--------------------------------+
1370
1371 **/
1372
1373
1374 void snd::render_v( scanvas* canvas, const std::vector<int>& order, int mode, int d ) const
1375 {
1376     int ordinal = get_ordinal( order );
1377     assert( ordinal > -1 );
1378
1379     //std::cout << "snd::render_v " << brief() << " ordinal " << ordinal << std::endl ;
1380
1381     int ix = ordinal ;
1382     int iy = d ;        // using depth instead of d would require snd::SetLVID to have been called
1383
1384     char l0 = label[0] ;
1385     if(l0 == '\0' ) l0 = 'o' ;
1386
1387     if( mode == 0 )
1388     {
1389         canvas->drawch( ix, iy, 0,0,  l0 );
1390     }
1391     else if( mode == 1 )
1392     {
1393         canvas->draw( ix, iy, 0,0,  index );
1394     }
1395     else if( mode == 2 )
1396     {
1397         canvas->draw( ix, iy, 0,0,  typecode );
1398     }
1399     else if( mode == 3 )
1400     {
1401         std::string tc = tag();
1402         canvas->draw( ix, iy, 0,0,  tc.c_str() );
1403     }
1404 }
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414 double snd::zmin() const
1415 {
1416     assert( CSG::CanZNudge(typecode) );
1417     assert( param > -1 );
1418     const spa& pa = POOL->param[param] ;
1419     return pa.zmin();
1420 }
1421
1422 double snd::zmax() const
1423 {
1424     assert( CSG::CanZNudge(typecode) );
1425     assert( param > -1 );
1426     const spa& pa = POOL->param[param] ;
1427     return pa.zmax();
1428 }
1429
1430 void snd::check_z() const
1431 {
1432     assert( CSG::CanZNudge(typecode) );
1433     assert( param > -1 );
1434     assert( aabb > -1 );
1435
1436     const spa& pa = POOL->param[param] ;
1437     const sbb& bb = POOL->aabb[aabb] ;
1438
1439     bool pa_expect = pa.zmin() == bb.zmin() && pa.zmax() == bb.zmax()  ;
1440     if(!pa_expect) std::raise(SIGINT);
1441     assert( pa_expect );
1442 }
1443
1444
1445 /**
1446 snd::decrease_zmin
1447 -------------------
1448
1449    bb.z1 +--------+ pa.z2
1450          |        |
1451          |        |
1452          |________|
1453    bb.z0 +~~~~~~~~+ pa.z1
1454
1455 **/
1456
1457 void snd::decrease_zmin( double dz )
1458 {
1459     check_z();
1460
1461     spa& pa = POOL->param[param] ;
1462     sbb& bb = POOL->aabb[aabb] ;
1463
1464     pa.decrease_zmin(dz);
1465     bb.decrease_zmin(dz);
1466 }
1467
1468 /**
1469 snd::increase_zmax
1470 -------------------
1471
1472 ::
1473
1474    bb.z1 +~~~~~~~~+ pa.z2
1475          +--------+
1476          |        |
1477          |        |
1478          |        |
1479    bb.z0 +--------+ pa.z1
1480
1481 **/
1482
1483 void snd::increase_zmax( double dz )
1484 {
1485     check_z();
1486
1487     spa& pa = POOL->param[param] ;
1488     sbb& bb = POOL->aabb[aabb] ;
1489
1490     pa.increase_zmax(dz) ;
1491     bb.increase_zmax(dz) ;
1492 }
1493
1494 /**
1495 snd::ZDesc
1496 -----------
1497
1498    +----+
1499    |    |
1500    +----+
1501    |    |
1502    +----+
1503    |    |
1504    +----+
1505
1506 **/
1507
1508 std::string snd::ZDesc(const std::vector<int>& prims) // static
1509 {
1510     std::stringstream ss ;
1511     ss << "snd::ZDesc" ;
1512     ss << " prims(" ;
1513     for(unsigned i=0 ; i < prims.size() ; i++) ss << prims[i] << " " ;
1514     ss << ") " ;
1515     ss << std::endl ;
1516
1517     for(unsigned i=0 ; i < prims.size() ; i++)
1518     {
1519         int _a = prims[i];
1520         snd& a = POOL->node[_a] ;
1521         ss << std::setw(3) << _a
1522            << ":"
1523            << " " << std::setw(10) << a.zmin()
1524            << " " << std::setw(10) << a.zmax()
1525            << std::endl
1526            ;
1527     }
1528     std::string str = ss.str();
1529     return str ;
1530 }
1531
1532 /**
1533 snd::ZNudgeExpandEnds
1534 -----------------------
1535
1536 CAUTION: changes geometry, only appropriate
1537 for subtracted consituents eg inners
1538
1539 **/
1540
1541 void snd::ZNudgeExpandEnds(const std::vector<int>& prims) // static
1542 {
1543     int level = Level();
1544     if(level > 0) std::cout
1545        << std::endl
1546        << "snd::ZNudgeExpandEnds "
1547        << std::endl
1548        << ZDesc(prims)
1549        << std::endl
1550        ;
1551
1552     /*
1553     for(unsigned i=1 ; i < prims.size() ; i++)
1554     {
1555         int _a = prims[i-1];
1556         int _b = prims[i];
1557
1558         snd& a = POOL->node[_a] ;
1559         snd& b = POOL->node[_b] ;
1560
1561         a.check_z();
1562         b.check_z();
1563     }
1564     */
1565 }
1566
1567 void snd::ZNudgeOverlapJoints(const std::vector<int>& prims) // static
1568 {
1569     int level = Level();
1570     if(level > 0) std::cout
1571        << std::endl
1572        << "snd::ZNudgeOverlapJoints PLACEHOLDER  "
1573        << std::endl
1574        << ZDesc(prims)
1575        << std::endl
1576        ;
1577 }
1578
1579
1580
1581
1582 std::string snd::desc() const
1583 {
1584     std::stringstream ss ;
1585     ss
1586        << "[snd::desc" << std::endl
1587        << brief() << std::endl
1588        << DescParam(param) << std::endl
1589        << DescAABB(aabb) << std::endl
1590        << DescXForm(xform) << std::endl
1591        ;
1592
1593     const snd& nd = *this ;
1594     int ch = nd.first_child ;
1595     int count = 0 ;
1596
1597     while( ch > -1 )
1598     {
1599         ss << Desc(ch) << std::endl ;
1600         const snd& child = POOL->node[ch] ;
1601
1602         bool consistent_parent_index = child.parent == nd.index ;
1603
1604         if(!consistent_parent_index) ss
1605             << "snd::desc "
1606             << " FAIL consistent_parent_index "
1607             << " ch " << ch
1608             << " count " << count
1609             << " child.parent " << child.parent
1610             << " nd.index " << nd.index
1611             << " nd.lvid "  << nd.lvid
1612             << " child.index " << child.index
1613             << " child.lvid "  << child.lvid
1614             << std::endl
1615             ;
1616
1617         //assert(consistent_parent_index);
1618         count += 1 ;
1619         ch = child.next_sibling ;
1620     }
1621
1622     bool expect_child = count == nd.num_child ;
1623
1624     if(!expect_child)
1625     {
1626         ss << std::endl << " FAIL count " << count << " num_child " << num_child << std::endl;
1627     }
1628     assert(expect_child);
1629     ss << "]snd::desc" << std::endl ;
1630     std::string str = ss.str();
1631     return str ;
1632 }
1633
1634 std::ostream& operator<<(std::ostream& os, const snd& v)
1635 {
1636     os << v.desc() ;
1637     return os;
1638 }
1639
1640
1641
1642
1643
1644
1645
1646 snd snd::Init(int tc)  // static
1647 {
1648     snd nd = {} ;
1649     nd.init();
1650     nd.typecode = tc ;
1651     nd.num_child = 0 ;
1652     nd.complement = 0 ;  // not used in snd, but set it false anyhow
1653     return nd ;
1654 }
1655
1656
1657 /**
1658 snd::init
1659 -----------
1660
1661 **/
1662
1663 void snd::init()
1664 {
1665     typecode = -1  ;
1666     complement = -1 ;
1667     lvid = -1 ;
1668     xform = -1 ;
1669     param = -1 ;
1670     aabb = -1 ;
1671     parent = -1 ;
1672     sibdex = -1 ;
1673     num_child = -1 ;
1674     first_child = -1 ;
1675     next_sibling = -1 ;
1676     index = -1 ;
1677     depth = -1 ;
1678 }
1679
1680 /**
1681 snd::Boolean
1682 --------------
1683
1684 NB forming a boolean sets up the
1685 sibling and parent node linkages
1686
1687 HMM: for positivization need to first
1688 create the full flexible sn tree
1689 and only mint
1690
1691
1692
1693 **/
1694
1695 int snd::Boolean( int op, int l, int r ) // static
1696 {
1697     assert( l > -1 && r > -1 );
1698
1699     snd nd = Init( op );
1700     assert( nd.xform == -1 );
1701
1702     nd.num_child = 2 ;
1703     nd.first_child = l ;
1704
1705     snd* ln = Get_(l) ;
1706     snd* rn = Get_(r) ;
1707
1708     ln->next_sibling = r ;
1709     ln->sibdex = 0 ;
1710
1711     rn->next_sibling = -1 ;
1712     rn->sibdex = 1 ;
1713
1714     int idx_0 = POOL->node.size() ;
1715
1716     ln->parent = idx_0 ;
1717     rn->parent = idx_0 ;
1718
1719     int idx = Add(nd) ;
1720
1721     assert( idx_0 == idx );
1722
1723     /*
1724     ln->parent = idx ;  // <-- INSIDIOUS BUG : DONT USE PTRS/REFS AFTER snd::Add
1725     rn->parent = idx ;  // <-- INSIDIOUS BUG : DONT USE PTRS/REFS AFTER snd::Add
1726
1727     NB : IT WOULD BE AN INSIDIOUS BUG TO USE *ln/rn* POINTERS/REFERENCES
1728     HERE AS REALLOC WILL SOMETIMES HAPPEN WHEN DO snd::Add WHICH
1729     WOULD INVALIDATE THE POINTERS/REFERENCES OBTAINED PRIOR TO snd::Add
1730
1731     THE BUG MANIFESTS AS PARENT FIELDS NOT BEING SET AS THE ln/rn WOULD
1732     NO LONGER BE POINTING INTO THE NODE VECTOR DUE TO THE REALLOCATION.
1733     */
1734
1735     return idx ;
1736 }
1737
1738 int snd::Compound(int type, const std::vector<int>& prims )
1739 {
1740     assert( type == CSG_CONTIGUOUS || type == CSG_DISCONTIGUOUS );
1741
1742     int num_prim = prims.size();
1743     assert( num_prim > 0 );
1744
1745     snd nd = Init( type );
1746     nd.sibdex = 0 ; // root sibdex to 0
1747     nd.num_child = num_prim ;
1748     nd.first_child = prims[0] ;
1749     int idx = Add(nd) ;
1750
1751     for(int i=0 ; i < num_prim ; i++)
1752     {
1753         int i_sib = prims[i];
1754         int p_sib = i > 0 ? prims[i-1] : -1 ;
1755
1756         snd& i_child = POOL->node[i_sib] ;
1757         i_child.sibdex = i ;
1758         i_child.parent = idx ;
1759         i_child.next_sibling = -1 ;
1760
1761         // other than for last i = num_prim-1
1762         // the next_sibling gets reset by prior "reach back" below
1763
1764         if(i > 0)
1765         {
1766             assert( p_sib > -1 );
1767             snd& p_child = POOL->node[p_sib] ;
1768             p_child.next_sibling = i_sib ;
1769         }
1770     }
1771     return idx ;
1772 }
1773
1774
1775 int snd::UnionTree(const std::vector<int>& prims )
1776 {
1777     int idx = sndtree::CommonTree_PlaceLeaves( prims, CSG_UNION );
1778     snd* n = Get_(idx);
1779     bool n_expect =  n->sibdex == 0  ;
1780     if(!n_expect) std::raise(SIGINT) ;
1781     assert( n_expect ) ;  // root sibdex to 0
1782     return idx ;
1783 }
1784
1785 int snd::Contiguous( const std::vector<int>& prims )
1786 {
1787     int idx = snd::Compound( CSG_CONTIGUOUS, prims );
1788     return idx ;
1789 }
1790
1791
1792 /**
1793 snd::Collection
1794 -----------------
1795
1796 Used for example from U4Polycone::init
1797
1798 +-------------+-------------------+-------------------+
1799 |  VERSION    |  Impl             |  Notes            |
1800 +=============+===================+===================+
1801 |     0       |  snd::UnionTree   | backward looking  |
1802 +-------------+-------------------+-------------------+
1803 |     1       |  snd::Contiguous  | forward looking   |
1804 +-------------+-------------------+-------------------+
1805
1806 **/
1807
1808 int snd::Collection( const std::vector<int>& prims ) // static
1809 {
1810     int idx = -1 ;
1811     switch(VERSION)
1812     {
1813         case 0: idx = UnionTree(prims)  ; break ;
1814         case 1: idx = Contiguous(prims) ; break ;
1815     }
1816     return idx ;
1817 }
1818
1819
1820 int snd::Cylinder(double radius, double z1, double z2) // static
1821 {
1822     assert( z2 > z1 );
1823     snd nd = Init(CSG_CYLINDER);
1824     nd.setParam( 0.f, 0.f, 0.f, radius, z1, z2)  ;
1825     nd.setAABB( -radius, -radius, z1, +radius, +radius, z2 );
1826     return Add(nd) ;
1827 }
1828
1829 int snd::Cone(double r1, double z1, double r2, double z2)  // static
1830 {
1831     assert( z2 > z1 );
1832     double rmax = fmax(r1, r2) ;
1833     snd nd = Init(CSG_CONE) ;
1834     nd.setParam( r1, z1, r2, z2, 0., 0. ) ;
1835     nd.setAABB( -rmax, -rmax, z1, rmax, rmax, z2 );
1836     return Add(nd) ;
1837 }
1838
1839 int snd::Sphere(double radius)  // static
1840 {
1841     assert( radius > zero );
1842     snd nd = Init(CSG_SPHERE) ;
1843     nd.setParam( zero, zero, zero, radius, zero, zero );
1844     nd.setAABB(  -radius, -radius, -radius,  radius, radius, radius  );
1845     return Add(nd) ;
1846 }
1847
1848 int snd::ZSphere(double radius, double z1, double z2)  // static
1849 {
1850     assert( radius > zero );
1851     assert( z2 > z1 );
1852     snd nd = Init(CSG_ZSPHERE) ;
1853     nd.setParam( zero, zero, zero, radius, z1, z2 );
1854     nd.setAABB(  -radius, -radius, z1,  radius, radius, z2  );
1855     return Add(nd) ;
1856 }
1857
1858 int snd::Box3(double fullside)  // static
1859 {
1860     return Box3(fullside, fullside, fullside);
1861 }
1862 int snd::Box3(double fx, double fy, double fz )  // static
1863 {
1864     assert( fx > 0. );
1865     assert( fy > 0. );
1866     assert( fz > 0. );
1867
1868     snd nd = Init(CSG_BOX3) ;
1869     nd.setParam( fx, fy, fz, 0.f, 0.f, 0.f );
1870     nd.setAABB( -fx*0.5 , -fy*0.5, -fz*0.5, fx*0.5 , fy*0.5, fz*0.5 );
1871     return Add(nd) ;
1872 }
1873
1874 int snd::Zero(double  x,  double y,  double z,  double w,  double z1, double z2) // static
1875 {
1876     snd nd = Init(CSG_ZERO);
1877     nd.setParam( x, y, z, w, z1, z2 );
1878     return Add(nd) ;
1879 }
1880
1881 int snd::Zero() // static
1882 {
1883     snd nd = Init(CSG_ZERO);
1884     return Add(nd) ;
1885 }
1886
1887