Show
Ignore:
Timestamp:
03/21/12 18:36:20 (3 years ago)
Author:
robert
Message:

Ran script to remove trailing spaces and tabs

Files:
1 modified

Legend:

Unmodified
Added
Removed
  • OpenSceneGraph/trunk/src/osg/KdTree.cpp

    r12437 r13041  
    1 /* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield  
     1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield 
    22 * 
    3  * This library is open source and may be redistributed and/or modified under   
    4  * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or  
     3 * This library is open source and may be redistributed and/or modified under 
     4 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or 
    55 * (at your option) any later version.  The full license is in LICENSE file 
    66 * included with this distribution, and on the openscenegraph.org website. 
    7  *  
     7 * 
    88 * This library is distributed in the hope that it will be useful, 
    99 * but WITHOUT ANY WARRANTY; without even the implied warranty of 
    10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the  
     10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
    1111 * OpenSceneGraph Public License for more details. 
    1212*/ 
     
    7070        const osg::Vec3& v1 = (*(_buildKdTree->_kdTree.getVertices()))[p1]; 
    7171        const osg::Vec3& v2 = (*(_buildKdTree->_kdTree.getVertices()))[p2]; 
    72      
     72 
    7373        // discard degenerate points 
    7474        if (v0==v1 || v1==v2 || v1==v2) 
     
    7979 
    8080        unsigned int i = _buildKdTree->_kdTree.addTriangle(KdTree::Triangle(p0,p1,p2)); 
    81          
     81 
    8282        osg::BoundingBox bb; 
    8383        bb.expandBy(v0); 
     
    8787        _buildKdTree->_centers.push_back(bb.center()); 
    8888        _buildKdTree->_primitiveIndices.push_back(i); 
    89          
    90     } 
    91      
     89 
     90    } 
     91 
    9292    BuildKdTree* _buildKdTree; 
    9393 
     
    101101bool BuildKdTree::build(KdTree::BuildOptions& options, osg::Geometry* geometry) 
    102102{ 
    103      
    104 #ifdef VERBOSE_OUTPUT     
     103 
     104#ifdef VERBOSE_OUTPUT 
    105105    OSG_NOTICE<<"osg::KDTreeBuilder::createKDTree()"<<std::endl;146 
    106106#endif 
     
    108108    osg::Vec3Array* vertices = dynamic_cast<osg::Vec3Array*>(geometry->getVertexArray()); 
    109109    if (!vertices) return false; 
    110      
     110 
    111111    if (vertices->size() <= options._targetNumTrianglesPerLeaf) return false; 
    112112 
    113113    _bb = geometry->getBound(); 
    114114    _kdTree.setVertices(vertices); 
    115      
     115 
    116116    unsigned int estimatedSize = (unsigned int)(2.0*float(vertices->size())/float(options._targetNumTrianglesPerLeaf)); 
    117117 
    118 #ifdef VERBOSE_OUTPUT     
     118#ifdef VERBOSE_OUTPUT 
    119119    OSG_NOTICE<<"kdTree->_kdNodes.reserve()="<<estimatedSize<<std::endl<<std::endl; 
    120120#endif 
    121121 
    122122    _kdTree.getNodes().reserve(estimatedSize*5); 
    123      
     123 
    124124    computeDivisions(options); 
    125125 
     
    145145    osg::BoundingBox bb = _bb; 
    146146    nodeNum = divide(options, bb, nodeNum, 0); 
    147      
     147 
    148148    // now reorder the triangle list so that it's in order as per the primitiveIndex list. 
    149149    KdTree::TriangleList triangleList(_kdTree.getTriangles().size()); 
     
    152152        triangleList[i] = _kdTree.getTriangle(_primitiveIndices[i]); 
    153153    } 
    154      
     154 
    155155    _kdTree.getTriangles().swap(triangleList); 
    156      
    157      
    158 #ifdef VERBOSE_OUTPUT     
     156 
     157 
     158#ifdef VERBOSE_OUTPUT 
    159159    OSG_NOTICE<<"Root nodeNum="<<nodeNum<<std::endl; 
    160160#endif 
    161      
    162      
     161 
     162 
    163163//    OSG_NOTICE<<"_kdNodes.size()="<<k_kdNodes.size()<<"  estimated size = "<<estimatedSize<<std::endl; 
    164164//    OSG_NOTICE<<"_kdLeaves.size()="<<_kdLeaves.size()<<"  estimated size = "<<estimatedSize<<std::endl<<std::endl; 
     
    174174                         _bb.zMax()-_bb.zMin()); 
    175175 
    176 #ifdef VERBOSE_OUTPUT     
     176#ifdef VERBOSE_OUTPUT 
    177177    OSG_NOTICE<<"computeDivisions("<<options._maxNumLevels<<") "<<dimensions<< " { "<<std::endl; 
    178178#endif 
    179179 
    180180    _axisStack.reserve(options._maxNumLevels); 
    181   
     181 
    182182    for(unsigned int level=0; level<options._maxNumLevels; ++level) 
    183183    { 
     
    194194        dimensions[axis] /= 2.0f; 
    195195 
    196 #ifdef VERBOSE_OUTPUT     
     196#ifdef VERBOSE_OUTPUT 
    197197        OSG_NOTICE<<"  "<<level<<", "<<dimensions<<", "<<axis<<std::endl; 
    198198#endif 
    199199    } 
    200200 
    201 #ifdef VERBOSE_OUTPUT     
     201#ifdef VERBOSE_OUTPUT 
    202202    OSG_NOTICE<<"}"<<std::endl; 
    203203#endif 
     
    210210    bool needToDivide = level < _axisStack.size() && 
    211211                        (node.first<0 && static_cast<unsigned int>(node.second)>options._targetNumTrianglesPerLeaf); 
    212                          
     212 
    213213    if (!needToDivide) 
    214214    { 
     
    217217            int istart = -node.first-1; 
    218218            int iend = istart+node.second-1; 
    219      
     219 
    220220            // leaf is done, now compute bound on it. 
    221221            node.bb.init(); 
     
    229229                node.bb.expandBy(v1); 
    230230                node.bb.expandBy(v2); 
    231                  
     231 
    232232            } 
    233233 
     
    242242                node.bb._max.z() += epsilon; 
    243243            } 
    244              
    245 #ifdef VERBOSE_OUTPUT     
     244 
     245#ifdef VERBOSE_OUTPUT 
    246246            if (!node.bb.valid()) 
    247247            { 
     
    263263    int axis = _axisStack[level]; 
    264264 
    265 #ifdef VERBOSE_OUTPUT     
     265#ifdef VERBOSE_OUTPUT 
    266266    OSG_NOTICE<<"divide("<<nodeIndex<<", "<<level<< "), axis="<<axis<<std::endl; 
    267267#endif 
    268268 
    269269    if (node.first<0) 
    270     {     
     270    { 
    271271        // leaf node as first <= 0, so look at dividing it. 
    272          
     272 
    273273        int istart = -node.first-1; 
    274274        int iend = istart+node.second-1; 
    275275 
    276276        //OSG_NOTICE<<"  divide leaf"<<std::endl; 
    277          
     277 
    278278        float original_min = bb._min[axis]; 
    279279        float original_max = bb._max[axis]; 
     
    289289            int left = istart; 
    290290            int right = iend; 
    291              
     291 
    292292            while(left<right) 
    293293            { 
     
    295295 
    296296                while(left<right && (_centers[_primitiveIndices[right]][axis]>mid)) { --right; } 
    297                  
     297 
    298298                while(left<right && (_centers[_primitiveIndices[right]][axis]>mid)) { --right; } 
    299299 
     
    305305                } 
    306306            } 
    307              
     307 
    308308            if (left==right) 
    309309            { 
     
    311311                else --right; 
    312312            } 
    313              
     313 
    314314            KdTree::KdNode leftLeaf(-istart-1, (right-istart)+1); 
    315315            KdTree::KdNode rightLeaf(-left-1, (iend-left)+1); 
     
    358358        } 
    359359 
    360          
     360 
    361361        float restore = bb._max[axis]; 
    362362        bb._max[axis] = mid; 
     
    366366 
    367367        bb._max[axis] = restore; 
    368          
     368 
    369369        restore = bb._min[axis]; 
    370370        bb._min[axis] = mid; 
     
    372372        //OSG_NOTICE<<"  divide rightLeaf "<<kdTree.getNode(nodeNum).second<<std::endl; 
    373373        int rightChildIndex = originalRightChildIndex!=0 ? divide(options, bb, originalRightChildIndex, level+1) : 0; 
    374          
     374 
    375375        bb._min[axis] = restore; 
    376          
     376 
    377377 
    378378        if (!insitueDivision) 
     
    381381            // have invalidate the previous node ref. 
    382382            KdTree::KdNode& newNodeRef = _kdTree.getNode(nodeIndex); 
    383          
     383 
    384384            newNodeRef.first = leftChildIndex; 
    385             newNodeRef.second = rightChildIndex;  
     385            newNodeRef.second = rightChildIndex; 
    386386 
    387387            insitueDivision = true; 
     
    417417        OSG_NOTICE<<"NOT expecting to get here"<<std::endl; 
    418418    } 
    419      
     419 
    420420    return nodeIndex; 
    421      
     421 
    422422} 
    423423 
     
    444444        _inverse_length = _length!=0.0f ? 1.0f/_length : 0.0; 
    445445        _d *= _inverse_length; 
    446          
     446 
    447447        _d_invX = _d.x()!=0.0f ? _d/_d.x() : osg::Vec3(0.0f,0.0f,0.0f); 
    448448        _d_invY = _d.y()!=0.0f ? _d/_d.y() : osg::Vec3(0.0f,0.0f,0.0f); 
     
    464464    float     _length; 
    465465    float     _inverse_length; 
    466      
     466 
    467467    osg::Vec3 _d_invX; 
    468468    osg::Vec3 _d_invY; 
     
    481481    { 
    482482        // treat as a leaf 
    483          
     483 
    484484        //OSG_NOTICE<<"KdTree::intersect("<<&leaf<<")"<<std::endl; 
    485485        int istart = -node.first-1; 
    486486        int iend = istart + node.second; 
    487          
     487 
    488488        for(int i=istart; i<iend; ++i) 
    489489        { 
     
    499499            osg::Vec3 E2 = v2 - v0; 
    500500            osg::Vec3 E1 = v1 - v0; 
    501              
     501 
    502502            osg::Vec3 P =  _d ^ E2; 
    503              
     503 
    504504            float det = P * E1; 
    505              
     505 
    506506            float r,r0,r1,r2; 
    507              
     507 
    508508            const float esplison = 1e-10f; 
    509509            if (det>esplison) 
     
    511511                float u = (P*T); 
    512512                if (u<0.0 || u>det) continue; 
    513                  
     513 
    514514                osg::Vec3 Q = T ^ E1; 
    515515                float v = (Q*_d); 
    516516                if (v<0.0 || v>det) continue; 
    517                  
     517 
    518518                if ((u+v)> det) continue; 
    519519 
    520                 float inv_det = 1.0f/det;                 
    521                 float t = (Q*E2)*inv_det;             
    522                 if (t<0.0 || t>_length) continue; 
    523  
    524                 u *= inv_det; 
    525                 v *= inv_det; 
    526  
    527                 r0 = 1.0f-u-v; 
    528                 r1 = u; 
    529                 r2 = v;  
    530                 r = t * _inverse_length; 
    531             } 
    532             else if (det<-esplison) 
    533             { 
    534  
    535                 float u = (P*T); 
    536                 if (u>0.0 || u<det) continue; 
    537                  
    538                 osg::Vec3 Q = T ^ E1; 
    539                 float v = (Q*_d); 
    540                 if (v>0.0 || v<det) continue; 
    541                  
    542                 if ((u+v) < det) continue; 
    543  
    544                 float inv_det = 1.0f/det;                 
    545                 float t = (Q*E2)*inv_det;             
     520                float inv_det = 1.0f/det; 
     521                float t = (Q*E2)*inv_det; 
    546522                if (t<0.0 || t>_length) continue; 
    547523 
     
    554530                r = t * _inverse_length; 
    555531            } 
     532            else if (det<-esplison) 
     533            { 
     534 
     535                float u = (P*T); 
     536                if (u>0.0 || u<det) continue; 
     537 
     538                osg::Vec3 Q = T ^ E1; 
     539                float v = (Q*_d); 
     540                if (v>0.0 || v<det) continue; 
     541 
     542                if ((u+v) < det) continue; 
     543 
     544                float inv_det = 1.0f/det; 
     545                float t = (Q*E2)*inv_det; 
     546                if (t<0.0 || t>_length) continue; 
     547 
     548                u *= inv_det; 
     549                v *= inv_det; 
     550 
     551                r0 = 1.0f-u-v; 
     552                r1 = u; 
     553                r2 = v; 
     554                r = t * _inverse_length; 
     555            } 
    556556            else 
    557557            { 
     
    562562            osg::Vec3 normal = E1^E2; 
    563563            normal.normalize(); 
    564              
     564 
    565565#if 1 
    566566            _intersections.push_back(KdTree::LineSegmentIntersection()); 
     
    705705            e = s+_d_invZ*(bb.zMax()-s.z()); 
    706706        } 
    707     }  
     707    } 
    708708    else 
    709709    { 
     
    723723        } 
    724724    } 
    725      
     725 
    726726    // OSG_NOTICE<<"clampped segment "<<s<<" "<<e<<std::endl; 
    727      
     727 
    728728    // if (s==e) return false; 
    729729 
    730     return true;     
     730    return true; 
    731731} 
    732732 
     
    767767bool KdTree::intersect(const osg::Vec3d& start, const osg::Vec3d& end, LineSegmentIntersections& intersections) const 
    768768{ 
    769     if (_kdNodes.empty())  
     769    if (_kdNodes.empty()) 
    770770    { 
    771771        OSG_NOTICE<<"Warning: _kdTree is empty"<<std::endl; 
     
    780780                                intersections, 
    781781                                start, end); 
    782                      
     782 
    783783    intersector.intersect(getNode(0), start, end); 
    784      
     784 
    785785    return numIntersectionsBefore != intersections.size(); 
    786786} 
     
    791791KdTreeBuilder::KdTreeBuilder(): 
    792792    osg::NodeVisitor(osg::NodeVisitor::TRAVERSE_ALL_CHILDREN) 
    793 {             
     793{ 
    794794    _kdTreePrototype = new osg::KdTree; 
    795795} 
     
    805805{ 
    806806    for(unsigned int i=0; i<geode.getNumDrawables(); ++i) 
    807     {             
     807    { 
    808808 
    809809        osg::Geometry* geom = geode.getDrawable(i)->asGeometry(); 
     
    820820                geom->setShape(kdTree.get()); 
    821821            } 
    822         }    
    823     } 
    824 } 
     822        } 
     823    } 
     824}