CMSSW Reference Manual

void addBestPlane	(	IgBSPNode *&	rootNode,
		IgBSPTriangle::List &	triangleList
	)

Definition at line 166 of file IgBSPTree.cc.

References IgBSPNode::add(), IgBSPTriangle::areIntersecting(), IgBSPNode::back(), calculateBarycenter(), end, evaluatePlane(), IgBSPNode::front(), i, IgBSPTriangle::isInBack(), IgBSPTriangle::isInFront(), j, level, t, IgBSPTriangle::unrefAndDeleteTriangles(), and IgBSPTriangle::v().

Referenced by IgBSPTree::add().

00168 {    
00169     //    debug (triangleList);
00170     
00171     level++;    
00172 
00173     if (triangleList.size ())
00174     {
00175         
00176         //Calculate the best plane possible for this set of points
00177         //
00178         // The position of the plane is given by the average of all the
00179         // barycenters.  
00180         SbVec3f planePos = calculateBarycenter (triangleList);
00181         // Evaluate which of the three cardinal planes passing for
00182         // planePos is the best suited for doing the subdivision.
00183         SbPlane bestPlane (SbVec3f (1,0,0), 0);
00184         float bestPlaneScore = 0;
00185     
00186         for (int j = 0; j < 3; j++)
00187         {
00188             SbVec3f planeNormal (0, 0, 0);
00189             planeNormal[j] = 1;
00190             SbPlane plane = SbPlane (planeNormal, planePos);
00191         
00192             float planeScore = evaluatePlane (plane, triangleList);
00193         
00194             if (bestPlaneScore < planeScore)
00195             {
00196                 bestPlane = plane;
00197                 bestPlaneScore = planeScore;        
00198             }   
00199         }
00200     
00201         if (triangleList.size () > 10
00202             && level < 10
00203             && bestPlaneScore > 0.7)
00204         {
00205             // Add the plane, making sure that a BSP node exist.
00206             assert (rootNode == 0);
00207             rootNode = new IgBSPNode (bestPlane);
00208     
00209             // Generate a list of triangles that should go in front and that
00210             // of those which should go in the back.  We include also the
00211             // triangles originating from the split against the cutting plane
00212     
00213             IgBSPTriangle::List frontList;
00214             IgBSPTriangle::List backList;
00215             IgBSPTriangle::List::iterator end (triangleList.end ());
00216             
00217             for (IgBSPTriangle::List::iterator i = triangleList.begin ();
00218                  i != end;
00219                  i++)
00220             {
00221                 int coplanarMask = (*i)->evaluateCoplanarMask (bestPlane);
00222                 int intersectionMask = (*i)->evaluateInHalfPlaneMask (bestPlane);
00223         
00224                 (*i)->ref ();
00225                 if (IgBSPTriangle::areIntersecting (coplanarMask, intersectionMask))
00226                 {
00227                     // If we are intersecting, splits the triangles, adds the
00228                     // results 
00229                     IgBSPTriangle::List splittedList;
00230 
00231                     (*i)->split (bestPlane, 
00232                                  splittedList, 
00233                                  coplanarMask, 
00234                                  intersectionMask);
00235                                  
00236                     (*i)->unref ();
00237                     IgBSPTriangle::List::iterator end (splittedList.end ());
00238                     for (IgBSPTriangle::List::iterator j = splittedList.begin ();
00239                          j != end;
00240                          j++)
00241                     {
00242                         int cMask = (*j)->evaluateCoplanarMask (bestPlane);
00243                         int iMask = (*j)->evaluateInHalfPlaneMask (bestPlane);
00244                 
00245                         if (IgBSPTriangle::isInFront (cMask, iMask))
00246                         {
00247                             (*j)->ref ();
00248                             frontList.push_back ((*j));
00249                         }
00250                         else if (IgBSPTriangle::isInBack (cMask, iMask))
00251                         {
00252                             (*j)->ref ();
00253                             backList.push_back ((*j));
00254                         }
00255                     }
00256                     IgBSPTriangle::unrefAndDeleteTriangles (splittedList);      
00257                 }
00258                 else if (IgBSPTriangle::isInFront (coplanarMask, intersectionMask))
00259                     frontList.push_back ((*i));     
00260                 else if (IgBSPTriangle::isInBack (coplanarMask, intersectionMask))
00261                     backList.push_back ((*i));
00262                 else
00263                     rootNode->add ((*i), true, 0, 0);
00264                 // FIXME: handle the case in which they are coplanar...
00265             }
00266 
00267             // Keep on going in subdividing.
00268             if (frontList.begin () != frontList.end ())
00269                 addBestPlane (rootNode->front (), frontList);
00270             if (backList.begin () != backList.end ())
00271                 addBestPlane (rootNode->back (), backList);
00272             IgBSPTriangle::unrefAndDeleteTriangles (frontList);
00273             IgBSPTriangle::unrefAndDeleteTriangles (backList);
00274         }
00275         else
00276         {
00277             // If there are less then 50 triangles in the left or we have
00278             // already too much recursion, start to add triangles in the
00279             // usual way.  
00280             //
00281             // FIXME: start with the biggest one (shall we sort the list?).
00282             if (triangleList.begin () != triangleList.end ())
00283             {
00284                 if (rootNode == 0)
00285                 {
00286                     IgBSPTriangle *t = *triangleList.begin ();
00287                     rootNode = new IgBSPNode (SbPlane (t->v (0), t->v (1), t->v (2)));
00288                 }
00289                 rootNode->add (triangleList);
00290             }
00291         }
00292     }
00293     
00294     level--;    
00295     return;
00296 }

SbVec3f calculateBarycenter ( IgBSPTriangle::List & triangleList )

Definition at line 80 of file IgBSPTree.cc.

References end, i, and HLT_VtxMuL3::result.

Referenced by addBestPlane().

00081 {
00082     SbVec3f result (0, 0, 0);
00083     assert (triangleList.begin () != triangleList.end ());
00084     
00085     IgBSPTriangle::List::iterator end (triangleList.end ());
00086     
00087     for (IgBSPTriangle::List::iterator i = triangleList.begin ();
00088          i != end;
00089          i++)
00090     {      
00091         result += (*i)->barycenter ();  
00092     }
00093 
00094     result /= (float) triangleList.size ();
00095     return result;    
00096 }

void debug ( const IgBSPTriangle::List & triangleList )

Definition at line 158 of file IgBSPTree.cc.

References TestMuL1L2Filter_cff::cerr, lat::endl(), i, and level.

00159 {
00160     for (int i = 0; i < level; i++)
00161         std::cerr << " ";
00162     std::cerr << "Num of triangles: " << triangleList.size () << std::endl;
00163 }

float evaluatePlane	(	SbPlane &	plane,
		IgBSPTriangle::List &	triangleList
	)

Definition at line 99 of file IgBSPTree.cc.

References IgBSPTriangle::areCoplanar(), end, i, IgBSPTriangle::isInBack(), and IgBSPTriangle::isInFront().

Referenced by addBestPlane().

00100 {
00101     SbVec3f normal = plane.getNormal ();
00102     assert (normal [0] || normal [1] || normal [2]);
00103     
00104     float frontTriangles = 0;
00105     float backTriangles = 0;
00106     float coplanarTriangles = 0;
00107     float totalTriangles = 0;
00108     
00109     assert (triangleList.begin () != triangleList.end ());
00110 
00111     IgBSPTriangle::List::iterator end (triangleList.end ());
00112     
00113     for (IgBSPTriangle::List::iterator i = triangleList.begin ();
00114          i != end;
00115          i++)
00116     {
00117         totalTriangles++;
00118         
00119         int coplanarMask = (*i)->evaluateCoplanarMask (plane);
00120         int intersectionMask = (*i)->evaluateInHalfPlaneMask (plane);
00121 
00122         if (IgBSPTriangle::isInFront (coplanarMask, 
00123                                       intersectionMask))
00124             frontTriangles++;
00125         else if (IgBSPTriangle::isInBack (coplanarMask, 
00126                                           intersectionMask))
00127             backTriangles++;
00128         else if (IgBSPTriangle::areCoplanar (coplanarMask))
00129             coplanarTriangles++;        
00130     }    
00131 
00132     if (totalTriangles == 0)
00133         return 0;    
00134 
00135     float splittingFactor = (frontTriangles 
00136                              + backTriangles 
00137                              + coplanarTriangles) / totalTriangles;
00138 
00139     float balancingFactor;
00140     
00141     if (frontTriangles+backTriangles)
00142         balancingFactor = 1 - fabs ((frontTriangles - backTriangles) /
00143                                     (frontTriangles + backTriangles));
00144     else
00145         balancingFactor = 0;
00146     
00147 
00148     float coplanarFactor = coplanarTriangles / totalTriangles;
00149 
00150     float total = 0.4 * splittingFactor 
00151                   + 0.4 * balancingFactor 
00152                   + 0.2 * coplanarFactor;     
00153     
00154     return total;    
00155 }

static void nodeToList	(	void *	userData,
		SoCallbackAction *	action,
		const SoPrimitiveVertex *	v1,
		const SoPrimitiveVertex *	v2,
		const SoPrimitiveVertex *	v3
	)			`[static]`

Definition at line 23 of file IgBSPTree.cc.

References j, and list().

Referenced by IgBSPTree::add(), and IgBSPTree::intersect().

00028 {
00029     // Get the points and transform them to world coordinates.
00030     const SbVec3f vtx[] = { v1->getPoint(), 
00031                             v2->getPoint(), 
00032                             v3->getPoint() };
00033     const SbMatrix mm = action->getModelMatrix ();
00034     SbVec3f vx[3];
00035     for (int j = 0; j < 3; j++) { mm.multVecMatrix (vtx[j], vx[j]); }
00036 
00037     IgBSPTriangle *triangle = 0;
00038         
00039     if (action->getVertexOrdering () == SoShapeHints::CLOCKWISE)
00040     {
00041         triangle = new IgBSPTriangle (vx[1], vx[0], vx[2]);
00042     }
00043     else
00044     {
00045         triangle = new IgBSPTriangle (vx[0], vx[1], vx[2]);
00046     }
00047     
00048     IgBSPTriangle::List *list = 
00049         static_cast<IgBSPTriangle::List *> (userData);
00050     
00051     list->push_back (triangle);
00052 }

int level = 0

Definition at line 77 of file IgBSPTree.cc.

Referenced by addBestPlane(), CalibrationXML::addChild(), HLTBtagLifetimeAnalyzer::analyze(), CSCNumberingScheme::baseNumberToUnitNumber(), RPCNumberingScheme::baseNumberToUnitNumber(), DTNumberingScheme::baseNumberToUnitNumber(), HLTMuonGenericRate::begin(), HLTMuonDQMSource::beginJob(), AlignmentMonitorSurvey::book(), HLTBtagLifetimeAnalyzer::cachePathDescription(), debug(), DTNumberingScheme::decode(), ZdcNumberingScheme::detectorLevel(), FP420NumberingScheme::detectorLevel(), CastorNumberingScheme::detectorLevel(), BscNumberingScheme::detectorLevel(), CaloTrkProcessing::detLV(), MaterialBudgetHcalHistos::fillBeginJob(), GetSensitiveVolume(), BscNumberingScheme::getUnitID(), EcalPreshowerNumberingScheme::getUnitID(), FP420NumberingScheme::getUnitID(), EcalHodoscopeNumberingScheme::getUnitID(), CastorNumberingScheme::getUnitID(), ESTBNumberingScheme::getUnitID(), ZdcNumberingScheme::getUnitID(), HCalSD::HCalSD(), HLTBtagLifetimeAnalyzer::HLTBtagLifetimeAnalyzer(), CaloTrkProcessing::isItCalo(), SteppingAction::isThisVolume(), StackingAction::isThisVolume(), operator<<(), IgModuleCache::parse(), SummaryPlotXmlParser::parseXML(), and TrackingMaterialProducer::update().

IgBSPTree.cc File Reference

Functions

Variables

Function Documentation

Variable Documentation


Functions
void	addBestPlane (IgBSPNode *&rootNode, IgBSPTriangle::List &triangleList)
SbVec3f	calculateBarycenter (IgBSPTriangle::List &triangleList)
void	debug (const IgBSPTriangle::List &triangleList)
float	evaluatePlane (SbPlane &plane, IgBSPTriangle::List &triangleList)
static void	nodeToList (void userData, SoCallbackAction action, const SoPrimitiveVertex v1, const SoPrimitiveVertex v2, const SoPrimitiveVertex *v3)
Variables
int	level = 0