开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 图形图像 > 3D图形编程 > 查看源码
TriOctree.cc
资源名称：scanalyze-1.0.3_source_code.rar　[点击查看]
上传用户：kellyonhid
上传日期：2013-10-12
资源大小：932k
文件大小：10k
源码类别：

3D图形编程

开发平台：

Visual C++

TriOctree.cc：源码内容
  1. //############################################################
  2. // 
  3. // TriOctree.cc
  4. //
  5. // Kari Pulli
  6. // Mon Nov 23 16:36:51 CET 1998
  7. //
  8. // Data structure that creates an octree containing all the 
  9. // triangles in a mesh.
  10. // Can also used to quickly evaluate approximate distances
  11. // to the surface.
  12. //
  13. //############################################################
  15. #include "TriOctree.h"
  18. // face indices:
  19. // 0, 2, 4 = dimension (x, y, z); +0 negative, +1 positive
  20. // so 0 is left, 1 is right
  21. //    2 is down, 3 is up
  22. //    4 is in,   5 is out
  23. //static const int face_negX = 0;
  24. //static const int face_posX = 1;
  25. //static const int face_negY = 2;
  26. //static const int face_posY = 3;
  27. //static const int face_negZ = 4;
  28. //static const int face_posZ = 5;
  31. TriOctree*
  32. TriOctree::recursive_find(int face, stack<int>& path, 
  33.   bool bReachedTop)
  34. {
  35.   if (path.empty()) return this;
  37.   int iChild;
  38.   if (bReachedTop) {
  39.     // then we want to descend
  40.     iChild = path.top(); path.pop();
  41.     TriOctree* theChild = child[iChild];
  42.     if (!theChild) return this; // child does not exist
  43.     return theChild->recursive_find (face, path, true);
  44.   } else {
  45.     // we still need to traverse horizontally...
  46.     if (!parent) return NULL;
  47.     if (is_neighbor_cell (face, iChild)) {
  48.       // if we have a sibling, we can traverse 
  49.       // (and we've reached the top!)
  50.       TriOctree* sibling = parent->child[iChild];
  51.       if (!sibling) return NULL;
  52.       return sibling->recursive_find (face, path, true);
  53.     } else {
  54.       // otherwise we have to go farther up.
  55.       path.push (iChild);
  56.       return parent->recursive_find (face, path, false);
  57.     }
  58.   }
  59. }
  62. bool
  63. TriOctree::is_neighbor_cell(int face, int &iChild)
  64. {
  65.   // given a direction, return the child index of the neighbor
  66.   // that lies in that direction.  If that neighbor is a sibling
  67.   // (iChild is valid for the same parent as us), return true.
  68.   // Otherwise, return false.
  70.   int axis = face / 2;
  71.   int sign = face % 2;
  73.   // neighbor will be in same position as we are, except
  74.   // the bit representing the axis we're moving along will be 
  75.   // flipped
  76.   iChild = parIdx ^ (1 << axis);
  78.   // if we have the bit for that axis set and the direction of
  79.   // movement is negative, it's a sibling, but if the direction 
  80.   // of movement is positive, it's not a sibling.  
  81.   // Vice-versa if our child index does
  82.   // not have the bit for the movement axis set.
  83.   int haveSign = (0 < (parIdx & (1 << axis)));
  84.   return (sign != haveSign);
  85. }
  88. TriOctree*
  89. TriOctree::find_neighbor (int face)
  90. {
  91.   if (!parent)
  92.     return NULL;
  94.   int iChild;
  95.   bool sibling = is_neighbor_cell(face, iChild);
  96.   if (sibling) {
  97.     TriOctree* theSibling = parent->child[iChild];
  98.     if (!theSibling) return NULL;
  99.     return theSibling;
  100.   }
  102.   // not a sibling: push child and go up
  103.   stack<int> path;
  104.   path.push (iChild);
  105.   return parent->recursive_find (face, path, false);
  106. }
  109. bool
  110. tri_outside_of_cube(const Pnt3 &c, float s,
  111.     const Pnt3 &t1, const Pnt3 &t2, const Pnt3 &t3);
  114. static int leaftricount = 0;
  117. TriOctree::TriOctree(const Pnt3 &c, float r, const Pnt3 *p,
  118.      const vector<int> &tris, float minRadius,
  119.      int pidx, TriOctree *parent)
  120.   : mCtr(c), mRadius(r), parIdx(pidx)
  121. {
  123.   /*
  124.   SHOW(mCtr);
  125.   SHOW(mRadius);
  126.   SHOW(tris.size()/3);
  127.   SHOW(minRadius);
  128.   */
  130.   // check whether we need to subdivide more
  131.   if (mRadius < 2*minRadius || tris.size() <= 18) {
  132.     pts = p;
  133.     tind = tris;
  134.     leaftricount += tris.size();
  135.     SHOW(leaftricount);
  136.     child[0] = child[1] = child[2] = child[3] = NULL;
  137.     child[4] = child[5] = child[6] = child[7] = NULL;
  138.     return;
  139.   }
  141.   pts = NULL;
  143.   // if so, try for triangle and each child whether they intersect
  144.   float halfR = mRadius*.5;
  145.   Pnt3 childCtr;
  147.   vector<int> xp, xm; // x plus, x minus
  148.   vector<int> yp, ym; // y plus, y minus
  149.   vector<int> zp, zm; // z plus, z minus
  150.   vector<int> uk;     // unknown (triangles going across splits)
  151.   xp.reserve(tris.size());
  152.   xm.reserve(tris.size());
  153.   uk.reserve(tris.size());
  155.   // split about x axis
  156.   vector<int>::const_iterator it = tris.begin();
  157.   int v1,v2,v3, cnt;
  158.   while (it != tris.end()) {
  159.     v1 = *it++; v2 = *it++; v3 = *it++;
  160.     cnt = (p[v1][0] >= mCtr[0]) + (p[v2][0] >= mCtr[0]) +
  161.       (p[v3][0] >= mCtr[0]);
  162.     if (cnt == 3) {
  163.       xp.push_back(v1); xp.push_back(v2); xp.push_back(v3);
  164.     } else if (cnt == 0) {
  165.       xm.push_back(v1); xm.push_back(v2); xm.push_back(v3);
  166.     } else {
  167.       uk.push_back(v1); uk.push_back(v2); uk.push_back(v3);
  168.     }  
  169.   }
  171.   // split about y axis
  172.   vector<int> &xv = xm;
  173.   vector<int> &yv = ym;
  174.   for (int i=0; i<2; i++) {
  175.     if (i) xv = xp;
  176.     else   xv = xm;
  177.     yp.clear(); yp.reserve(xv.size());
  178.     ym.clear(); ym.reserve(xv.size());
  179.        
  180.     it = xv.begin();
  181.     while (it != xv.end()) {
  182.       v1 = *it++; v2 = *it++; v3 = *it++;
  183.       cnt = (p[v1][1] >= mCtr[1]) + (p[v2][1] >= mCtr[1]) +
  184. (p[v3][1] >= mCtr[1]);
  185.       if (cnt == 3) {
  186. yp.push_back(v1); yp.push_back(v2); yp.push_back(v3);
  187.       } else if (cnt == 0) {
  188. ym.push_back(v1); ym.push_back(v2); ym.push_back(v3);
  189.       } else {
  190. uk.push_back(v1); uk.push_back(v2); uk.push_back(v3);
  191.       }  
  192.     }
  193.     for (int j=0; j<2; j++) {
  194.       if (j) yv = yp;
  195.       else   yv = ym;
  196.       zp.clear(); zp.reserve(yv.size());
  197.       zm.clear(); zm.reserve(yv.size());
  199.       it = yv.begin();
  200.       while (it != yv.end()) {
  201. v1 = *it++; v2 = *it++; v3 = *it++;
  202. cnt = (p[v1][2] >= mCtr[2]) + (p[v2][2] >= mCtr[2]) +
  203.   (p[v3][2] >= mCtr[2]);
  204. if (cnt == 3) {
  205.   zp.push_back(v1); zp.push_back(v2); zp.push_back(v3);
  206. } else if (cnt == 0) {
  207.   zm.push_back(v1); zm.push_back(v2); zm.push_back(v3);
  208. } else {
  209.   uk.push_back(v1); uk.push_back(v2); uk.push_back(v3);
  210. }  
  211.       }
  212.       
  213.       // check the unknowns
  214.       childCtr.set(mCtr[0] + (i ? halfR : -halfR),
  215.    mCtr[1] + (j ? halfR : -halfR),
  216.    mCtr[2] - halfR);
  217.       it = uk.begin();
  218.       while (it != uk.end()) {
  219. v1 = *it++; v2 = *it++; v3 = *it++;
  220. if (!tri_outside_of_cube(childCtr, mRadius, p[v1],
  221.  p[v2], p[v3])) {
  222.   zm.push_back(v1); zm.push_back(v2); zm.push_back(v3);
  223. }
  224.       }
  226.       // create the children, if needed
  227.       int k = i+2*j;
  228.       if (zm.size()) {
  229. child[k] = new TriOctree(childCtr, halfR, p, zm, 
  230.  minRadius, k, this);
  231.       } else {
  232. child[k] = NULL;
  233.       }
  235.       // check the unknowns
  236.       childCtr.set(mCtr[0] + (i ? halfR : -halfR),
  237.    mCtr[1] + (j ? halfR : -halfR),
  238.    mCtr[2] + halfR);
  239.       it = uk.begin();
  240.       while (it != uk.end()) {
  241. v1 = *it++; v2 = *it++; v3 = *it++;
  242. if (!tri_outside_of_cube(childCtr, mRadius, p[v1],
  243.  p[v2], p[v3])) {
  244.   zp.push_back(v1); zp.push_back(v2); zp.push_back(v3);
  245. }
  246.       }
  248.       k += 4;
  249.       if (zp.size()) {
  250. child[k] = new TriOctree(childCtr, halfR, p, zp, 
  251.  minRadius, k, this);
  252.       } else {
  253. child[k] = NULL;
  254.       }
  255.     }
  256.   }
  257.   /*
  258.   vector<int> tmptris;
  259.   tmptris.reserve(tris.size());
  260.   for (int i=0; i<8; i++) {
  261.     childCtr.set(mCtr[0] + ((i&1) ? halfR : -halfR),
  262.  mCtr[1] + ((i&2) ? halfR : -halfR),
  263.  mCtr[2] + ((i&4) ? halfR : -halfR));
  264.     tmptris.clear();
  265.     for (int j=0; j<tris.size(); j+=3) {
  266.       if (!tri_outside_of_cube(childCtr, mRadius, p[tris[j]], 
  267.        p[tris[j+1]], p[tris[j+2]])) {
  268. tmptris.push_back(tris[j]);
  269. tmptris.push_back(tris[j+1]);
  270. tmptris.push_back(tris[j+2]);
  271.       }
  272.     }
  273.     if (tmptris.size()) {
  274.       child[i] = new TriOctree(childCtr, halfR, p, tmptris, 
  275.        minRadius, i, this);
  276.     } else {
  277.       child[i] = NULL;
  278.     }
  279.   }
  280. */
  281. }
  284. // the return value tells whether the closest distance (squared)
  285. // has been found for sure
  286. bool
  287. TriOctree::search(const Pnt3 &p, Pnt3 &cp, float &d2)
  288. {
  289.   // is this a leaf node?
  290.   if (pts) {
  291.     // look for a new closest distance
  292.     vector<int>::const_iterator   it  = tind.begin();
  293.     while (it != tind.end()) {
  294.       closer_on_tri(p, cp, pts[*(it++)], pts[*(it++)], 
  295.     pts[*(it++)], d2);
  296.     }
  297.     return ball_within_bounds(p, sqrtf(d2), mCtr, mRadius);
  298.   }
  299.   
  300.   // which child contains p?
  301.   int iChild = 4*(mCtr[2]<p[2]) + 2*(mCtr[1]<p[1]) + (mCtr[0]<p[0]);
  302.   
  303.   // check that child first
  304.   if (child[iChild] && child[iChild]->search(p, cp, d2)) return true;
  306.   // now see if the other children need to be checked
  307.   for (int i=0; i<8; i++) {
  308.     if (i==iChild) continue;
  309.     //if (child[i] && child[i]->bounds_overlap_ball(p,d)) {
  310.     if (child[i] && bounds_overlap_ball(p,sqrtf(d2),child[i]->mCtr, 
  311. child[i]->mRadius)) {
  312.       if (child[i]->search(p, cp, d2)) return true;
  313.     }
  314.   }
  315.   return ball_within_bounds(p, sqrtf(d2), mCtr, mRadius);
  316. }
  319. static void
  320. cube_bdry(const Pnt3 &ctr, float r, 
  321.   vector<Pnt3> &p, vector<int> &i)
  322. {
  323.   int s = p.size();
  324.   p.push_back(ctr + Pnt3(-r,-r,-r));
  325.   p.push_back(ctr + Pnt3( r,-r,-r));
  326.   p.push_back(ctr + Pnt3(-r, r,-r));
  327.   p.push_back(ctr + Pnt3( r, r,-r));
  328.   p.push_back(ctr + Pnt3(-r,-r, r));
  329.   p.push_back(ctr + Pnt3( r,-r, r));
  330.   p.push_back(ctr + Pnt3(-r, r, r));
  331.   p.push_back(ctr + Pnt3( r, r, r));
  333.   i.push_back(s+0);
  334.   i.push_back(s+3);
  335.   i.push_back(s+1);
  336.   i.push_back(s+2);
  337.   i.push_back(s+3);
  338.   i.push_back(s+0);
  340.   i.push_back(s+0);
  341.   i.push_back(s+5);
  342.   i.push_back(s+4);
  343.   i.push_back(s+0);
  344.   i.push_back(s+1);
  345.   i.push_back(s+5);
  347.   i.push_back(s+2);
  348.   i.push_back(s+4);
  349.   i.push_back(s+6);
  350.   i.push_back(s+2);
  351.   i.push_back(s+0);
  352.   i.push_back(s+4);
  354.   i.push_back(s+3);
  355.   i.push_back(s+7);
  356.   i.push_back(s+5);
  357.   i.push_back(s+3);
  358.   i.push_back(s+5);
  359.   i.push_back(s+1);
  361.   i.push_back(s+2);
  362.   i.push_back(s+6);
  363.   i.push_back(s+7);
  364.   i.push_back(s+2);
  365.   i.push_back(s+7);
  366.   i.push_back(s+3);
  368.   i.push_back(s+7);
  369.   i.push_back(s+6);
  370.   i.push_back(s+4);
  371.   i.push_back(s+7);
  372.   i.push_back(s+4);
  373.   i.push_back(s+5);
  374. }
  377. // creates a mesh that shows the structure of the octree
  378. void
  379. TriOctree::visualize(vector<Pnt3> &p, vector<int> &ind)
  380. {
  381.   cube_bdry(mCtr, mRadius, p, ind);
  382.   for (int i=0; i<8; i++) {
  383.     if (child[i]) 
  384.       child[i]->visualize(p,ind);
  385.   }
  386. }
  389. #ifdef TRIOCTREEMAIN
  391. void
  392. main(void)
  393. {
  394.   Pnt3 *p = NULL;
  395.   vector<int> tris;
  396.   TriOctree to(Pnt3(), 1, p, tris, .1);
  397. }
  399. #endif