src/OpenGl/OpenGl_SceneGeometry.cxx

   1 // Created on: 2013-08-27
   2 // Created by: Denis BOGOLEPOV
   3 // Copyright (c) 2013 OPEN CASCADE SAS
   4 //
   5 // The content of this file is subject to the Open CASCADE Technology Public
   6 // License Version 6.5 (the "License"). You may not use the content of this file
   7 // except in compliance with the License. Please obtain a copy of the License
   8 // at http://www.opencascade.org and read it completely before using this file.
   9 //
  10 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
  11 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
  12 //
  13 // The Original Code and all software distributed under the License is
  14 // distributed on an "AS IS" basis, without warranty of any kind, and the
  15 // Initial Developer hereby disclaims all such warranties, including without
  16 // limitation, any warranties of merchantability, fitness for a particular
  17 // purpose or non-infringement. Please see the License for the specific terms
  18 // and conditions governing the rights and limitations under the License.
  19
  20 #ifdef HAVE_CONFIG_H
  21   #include <config.h>
  22 #endif
  23
  24 #ifdef HAVE_OPENCL
  25
  26 #include <limits>
  27
  28 #include <OpenGl_SceneGeometry.hxx>
  29
  30 namespace
  31 {
  32
  33   //! Number of node bins per axis.
  34   static const int THE_NUMBER_OF_BINS = 32;
  35
  36   //! Max number of triangles per leaf node.
  37   static const int THE_MAX_LEAF_TRIANGLES = 4;
  38
  39   //! Useful constant for null integer 4D vector.
  40   static const OpenGl_RTVec4i THE_ZERO_VEC_4I;
  41
  42   //! Useful constant for null floating-point 4D vector.
  43   static const OpenGl_RTVec4f THE_ZERO_VEC_4F;
  44
  45 };
  46
  47 // =======================================================================
  48 // function : OpenGl_RaytraceMaterial
  49 // purpose  : Creates new default material
  50 // =======================================================================
  51 OpenGl_RaytraceMaterial::OpenGl_RaytraceMaterial()
  52 : Ambient      (THE_ZERO_VEC_4F),
  53   Diffuse      (THE_ZERO_VEC_4F),
  54   Specular     (THE_ZERO_VEC_4F),
  55   Emission     (THE_ZERO_VEC_4F),
  56   Reflection   (THE_ZERO_VEC_4F),
  57   Refraction   (THE_ZERO_VEC_4F),
  58   Transparency (THE_ZERO_VEC_4F)
  59 { }
  60
  61 // =======================================================================
  62 // function : OpenGl_RaytraceMaterial
  63 // purpose  : Creates new material with specified properties
  64 // =======================================================================
  65 OpenGl_RaytraceMaterial::OpenGl_RaytraceMaterial (const OpenGl_RTVec4f& theAmbient,
  66                                                   const OpenGl_RTVec4f& theDiffuse,
  67                                                   const OpenGl_RTVec4f& theSpecular)
  68 : Ambient      (theAmbient),
  69   Diffuse      (theDiffuse),
  70   Specular     (theSpecular),
  71   Emission     (THE_ZERO_VEC_4F),
  72   Reflection   (THE_ZERO_VEC_4F),
  73   Refraction   (THE_ZERO_VEC_4F),
  74   Transparency (THE_ZERO_VEC_4F)
  75 {
  76   //
  77 }
  78
  79 // =======================================================================
  80 // function : OpenGl_RaytraceMaterial
  81 // purpose  : Creates new material with specified properties
  82 // =======================================================================
  83 OpenGl_RaytraceMaterial::OpenGl_RaytraceMaterial (const OpenGl_RTVec4f& theAmbient,
  84                                                   const OpenGl_RTVec4f& theDiffuse,
  85                                                   const OpenGl_RTVec4f& theSpecular,
  86                                                   const OpenGl_RTVec4f& theEmission,
  87                                                   const OpenGl_RTVec4f& theTranspar)
  88 : Ambient      (theAmbient),
  89   Diffuse      (theDiffuse),
  90   Specular     (theSpecular),
  91   Emission     (theEmission),
  92   Reflection   (THE_ZERO_VEC_4F),
  93   Refraction   (THE_ZERO_VEC_4F),
  94   Transparency (theTranspar)
  95 {
  96   //
  97 }
  98
  99 // =======================================================================
 100 // function : OpenGl_RaytraceMaterial
 101 // purpose  : Creates new material with specified properties
 102 // =======================================================================
 103 OpenGl_RaytraceMaterial::OpenGl_RaytraceMaterial (const OpenGl_RTVec4f& theAmbient,
 104                                                   const OpenGl_RTVec4f& theDiffuse,
 105                                                   const OpenGl_RTVec4f& theSpecular,
 106                                                   const OpenGl_RTVec4f& theEmission,
 107                                                   const OpenGl_RTVec4f& theTranspar,
 108                                                   const OpenGl_RTVec4f& theReflection,
 109                                                   const OpenGl_RTVec4f& theRefraction)
 110 : Ambient      (theAmbient),
 111   Diffuse      (theDiffuse),
 112   Specular     (theSpecular),
 113   Emission     (theEmission),
 114   Reflection   (theReflection),
 115   Refraction   (theRefraction),
 116   Transparency (theTranspar)
 117 {
 118   //
 119 }
 120
 121 // =======================================================================
 122 // function : OpenGl_LightSource
 123 // purpose  : Creates new light source
 124 // =======================================================================
 125 OpenGl_RaytraceLight::OpenGl_RaytraceLight (const OpenGl_RTVec4f& theAmbient)
 126 : Ambient (theAmbient)
 127 {
 128   //
 129 }
 130
 131 // =======================================================================
 132 // function : OpenGl_LightSource
 133 // purpose  : Creates new light source
 134 // =======================================================================
 135 OpenGl_RaytraceLight::OpenGl_RaytraceLight (const OpenGl_RTVec4f& theDiffuse,
 136                                             const OpenGl_RTVec4f& thePosition)
 137 : Diffuse (theDiffuse),
 138   Position (thePosition)
 139 {
 140   //
 141 }
 142
 143 // =======================================================================
 144 // function : Center
 145 // purpose  : Returns centroid of specified triangle
 146 // =======================================================================
 147 OpenGl_RTVec4f OpenGl_RaytraceScene::Center (const int theTriangle) const
 148 {
 149   const OpenGl_RTVec4i& anIndex = Triangles [theTriangle];
 150
 151   return ( Vertices[anIndex.x()] +
 152            Vertices[anIndex.y()] +
 153            Vertices[anIndex.z()] ) * ( 1.f / 3.f );
 154 }
 155
 156 // =======================================================================
 157 // function : CenterAxis
 158 // purpose  : Returns centroid of specified triangle
 159 // =======================================================================
 160 float OpenGl_RaytraceScene::CenterAxis (const int theTriangle,
 161                                         const int theAxis) const
 162 {
 163   const OpenGl_RTVec4i& anIndex = Triangles [theTriangle];
 164
 165   return ( Vertices[anIndex.x()][theAxis] +
 166            Vertices[anIndex.y()][theAxis] +
 167            Vertices[anIndex.z()][theAxis] ) * ( 1.f / 3.f );
 168 }
 169
 170 // =======================================================================
 171 // function : Box
 172 // purpose  : Returns AABB of specified triangle
 173 // =======================================================================
 174 OpenGl_AABB OpenGl_RaytraceScene::Box (const int theTriangle) const
 175 {
 176   const OpenGl_RTVec4i& anIndex = Triangles[theTriangle];
 177
 178   const OpenGl_RTVec4f& pA = Vertices[anIndex.x()];
 179   const OpenGl_RTVec4f& pB = Vertices[anIndex.y()];
 180   const OpenGl_RTVec4f& pC = Vertices[anIndex.z()];
 181
 182   OpenGl_AABB aBox (pA);
 183
 184   aBox.Add (pB);
 185   aBox.Add (pC);
 186
 187   return aBox;
 188 }
 189
 190 // =======================================================================
 191 // function : Clear
 192 // purpose  : Clears all scene geometry data
 193 // =======================================================================
 194 void OpenGl_RaytraceScene::Clear()
 195 {
 196   AABB.Clear();
 197
 198   OpenGl_RTArray4f anEmptyNormals;
 199   Normals.swap (anEmptyNormals);
 200
 201   OpenGl_RTArray4f anEmptyVertices;
 202   Vertices.swap (anEmptyVertices);
 203
 204   OpenGl_RTArray4i anEmptyTriangles;
 205   Triangles.swap (anEmptyTriangles);
 206
 207   std::vector<OpenGl_RaytraceMaterial,
 208               NCollection_StdAllocator<OpenGl_RaytraceMaterial> > anEmptyMaterials;
 209
 210   Materials.swap (anEmptyMaterials);
 211 }
 212
 213 // =======================================================================
 214 // function : OpenGl_Node
 215 // purpose  : Creates new empty BVH node
 216 // =======================================================================
 217 OpenGl_BVHNode::OpenGl_BVHNode()
 218 : myMinPoint (THE_ZERO_VEC_4F),
 219   myMaxPoint (THE_ZERO_VEC_4F),
 220   myDataRcrd (THE_ZERO_VEC_4I)
 221 {
 222   //
 223 }
 224
 225 // =======================================================================
 226 // function : OpenGl_Node
 227 // purpose  : Creates new BVH node with specified data
 228 // =======================================================================
 229 OpenGl_BVHNode::OpenGl_BVHNode (const OpenGl_RTVec4f& theMinPoint,
 230                                 const OpenGl_RTVec4f& theMaxPoint,
 231                                 const OpenGl_RTVec4i& theDataRcrd)
 232 : myMinPoint (theMinPoint),
 233   myMaxPoint (theMaxPoint),
 234   myDataRcrd (theDataRcrd)
 235 {
 236   //
 237 }
 238
 239 // =======================================================================
 240 // function : OpenGl_Node
 241 // purpose  : Creates new leaf BVH node with specified data
 242 // =======================================================================
 243 OpenGl_BVHNode::OpenGl_BVHNode (const OpenGl_AABB& theAABB,
 244                                 const int          theBegTriangle,
 245                                 const int          theEndTriangle)
 246 : myMinPoint (theAABB.CornerMin()),
 247   myMaxPoint (theAABB.CornerMax()),
 248   myDataRcrd (1,
 249               theBegTriangle,
 250               theEndTriangle,
 251               0)
 252 {
 253   //
 254 }
 255
 256 // =======================================================================
 257 // function : OpenGl_Node
 258 // purpose  : Creates new leaf BVH node with specified data
 259 // =======================================================================
 260 OpenGl_BVHNode::OpenGl_BVHNode (const OpenGl_RTVec4f& theMinPoint,
 261                                 const OpenGl_RTVec4f& theMaxPoint,
 262                                 const int             theBegTriangle,
 263                                 const int             theEndTriangle)
 264 : myMinPoint (theMinPoint),
 265   myMaxPoint (theMaxPoint),
 266   myDataRcrd (1,
 267               theBegTriangle,
 268               theEndTriangle,
 269               0)
 270 {
 271   //
 272 }
 273
 274 // =======================================================================
 275 // function : CleanUp
 276 // purpose  : Removes all tree nodes
 277 // =======================================================================
 278 void OpenGl_BVH::CleanUp()
 279 {
 280   OpenGl_RTArray4f anEmptyMinPointBuffer;
 281   myMinPointBuffer.swap (anEmptyMinPointBuffer);
 282
 283   OpenGl_RTArray4f anEmptyMaxPointBuffer;
 284   myMaxPointBuffer.swap (anEmptyMaxPointBuffer);
 285
 286   OpenGl_RTArray4i anEmptyDataRcrdBuffer;
 287   myDataRcrdBuffer.swap (anEmptyDataRcrdBuffer);
 288 }
 289
 290 // =======================================================================
 291 // function : Node
 292 // purpose  : Returns node with specified index
 293 // =======================================================================
 294 OpenGl_BVHNode OpenGl_BVH::Node (const int theIndex) const
 295 {
 296   return OpenGl_BVHNode (myMinPointBuffer[theIndex],
 297                          myMaxPointBuffer[theIndex],
 298                          myDataRcrdBuffer[theIndex]);
 299 }
 300
 301 // =======================================================================
 302 // function : SetNode
 303 // purpose  : Replaces node with specified index
 304 // =======================================================================
 305 void OpenGl_BVH::SetNode (const int             theIndex,
 306                           const OpenGl_BVHNode& theNode)
 307 {
 308   if (theIndex < static_cast<int> (myMinPointBuffer.size()))
 309   {
 310     myMinPointBuffer[theIndex] = theNode.myMinPoint;
 311     myMaxPointBuffer[theIndex] = theNode.myMaxPoint;
 312     myDataRcrdBuffer[theIndex] = theNode.myDataRcrd;
 313   }
 314 }
 315
 316 // =======================================================================
 317 // function : PushNode
 318 // purpose  : Adds new node to the tree
 319 // =======================================================================
 320 int OpenGl_BVH::PushNode (const OpenGl_BVHNode& theNode)
 321 {
 322   myMinPointBuffer.push_back (theNode.myMinPoint);
 323   myMaxPointBuffer.push_back (theNode.myMaxPoint);
 324   myDataRcrdBuffer.push_back (theNode.myDataRcrd);
 325   return static_cast<int> (myDataRcrdBuffer.size() - 1);
 326 }
 327
 328 // =======================================================================
 329 // function : OpenGl_NodeBuildTask
 330 // purpose  : Creates new node building task
 331 // =======================================================================
 332 OpenGl_BVHNodeTask::OpenGl_BVHNodeTask()
 333 : NodeToBuild (0),
 334   BegTriangle (0),
 335   EndTriangle (0)
 336 {
 337   //
 338 }
 339
 340 // =======================================================================
 341 // function : OpenGl_NodeBuildTask
 342 // purpose  : Creates new node building task
 343 // =======================================================================
 344 OpenGl_BVHNodeTask::OpenGl_BVHNodeTask (const int theNodeToBuild,
 345                                         const int theBegTriangle,
 346                                         const int theEndTriangle)
 347 : NodeToBuild (theNodeToBuild),
 348   BegTriangle (theBegTriangle),
 349   EndTriangle (theEndTriangle)
 350 {
 351   //
 352 }
 353
 354 // =======================================================================
 355 // function : OpenGl_BinnedBVHBuilder
 356 // purpose  : Creates new binned BVH builder
 357 // =======================================================================
 358 OpenGl_BinnedBVHBuilder::OpenGl_BinnedBVHBuilder()
 359 : myMaxDepth (30)
 360 {
 361   //
 362 }
 363
 364 // =======================================================================
 365 // function : ~OpenGl_BinnedBVHBuilder
 366 // purpose  : Releases binned BVH builder
 367 // =======================================================================
 368 OpenGl_BinnedBVHBuilder::~OpenGl_BinnedBVHBuilder()
 369 {
 370   //
 371 }
 372
 373 #define BVH_DEBUG_OUTPUT_
 374
 375 #if defined( BVH_DEBUG_OUTPUT )
 376   #include <iostream>
 377 #endif
 378
 379 // =======================================================================
 380 // function : ReinterpretIntAsFloat
 381 // purpose  : Reinterprets bits of integer value as floating-point value
 382 // =======================================================================
 383 inline float ReinterpretIntAsFloat (int theValue)
 384 {
 385   return *reinterpret_cast< float* > (&theValue);
 386 }
 387
 388 // =======================================================================
 389 // function : Build
 390 // purpose  : Builds BVH tree using binned SAH algorithm
 391 // =======================================================================
 392 void OpenGl_BinnedBVHBuilder::Build (OpenGl_RaytraceScene& theGeometry,
 393                                      const float           theEpsilon)
 394 {
 395   CleanUp();
 396
 397 #ifdef BVH_DEBUG_OUTPUT
 398   std::cout << "Start building BVH..." << std::endl;
 399
 400   std::cout << "Triangles: " << theGeometry.Triangles.size() << std::endl;
 401 #endif
 402
 403   if (theGeometry.Triangles.size() == 0)
 404     return;
 405
 406   // Create root node with all scene triangles
 407   OpenGl_AABB anAABB = theGeometry.AABB;
 408   anAABB.CornerMin() = OpenGl_RTVec4f (anAABB.CornerMin().x() - theEpsilon,
 409                                        anAABB.CornerMin().y() - theEpsilon,
 410                                        anAABB.CornerMin().z() - theEpsilon,
 411                                        1.0f);
 412   anAABB.CornerMax() = OpenGl_RTVec4f (anAABB.CornerMax().x() + theEpsilon,
 413                                        anAABB.CornerMax().y() + theEpsilon,
 414                                        anAABB.CornerMax().z() + theEpsilon,
 415                                        1.0f);
 416   myTree.PushNode (OpenGl_BVHNode (anAABB, 0, static_cast<int> (theGeometry.Triangles.size() - 1)));
 417
 418 #ifdef BVH_DEBUG_OUTPUT
 419   std::cout << "Push root node: [" << 0 << ", " <<
 420                       theGeometry.Triangles.size() - 1 << "]" << std::endl;
 421 #endif
 422
 423   // Setup splitting task for the root node
 424   myNodeTasksQueue.push_back (OpenGl_BVHNodeTask (0, 0, static_cast<int> (theGeometry.Triangles.size() - 1)));
 425
 426   // Building nodes while tasks queue is not empty
 427   for (int aTaskId = 0; aTaskId < static_cast<int> (myNodeTasksQueue.size()); ++aTaskId)
 428   {
 429     BuildNode (theGeometry, aTaskId);
 430   }
 431
 432   // Write support data to optimize traverse
 433   for (int aNode = 0; aNode < static_cast<int> (myTree.DataRcrdBuffer().size()); ++aNode)
 434   {
 435     OpenGl_RTVec4i aData = myTree.DataRcrdBuffer()[aNode];
 436     myTree.MinPointBuffer()[aNode].w() = ReinterpretIntAsFloat (aData[0] ? aData[1] : -aData[1]);
 437     myTree.MaxPointBuffer()[aNode].w() = ReinterpretIntAsFloat (aData[0] ? aData[2] : -aData[2]);
 438   }
 439 }
 440
 441 // =======================================================================
 442 // function : CleanUp
 443 // purpose  : Clears previously built tree
 444 // =======================================================================
 445 void OpenGl_BinnedBVHBuilder::CleanUp()
 446 {
 447   myTree.CleanUp();
 448   myNodeTasksQueue.clear();
 449 }
 450
 451 // =======================================================================
 452 // function : SetMaxDepth
 453 // purpose  : Sets maximum tree depth
 454 // =======================================================================
 455 void OpenGl_BinnedBVHBuilder::SetMaxDepth (const int theMaxDepth)
 456 {
 457   if (theMaxDepth > 1 && theMaxDepth < 30)
 458   {
 459     myMaxDepth = theMaxDepth - 1;
 460   }
 461 }
 462
 463 //! Minimum node size to split.
 464 static const float THE_NODE_MIN_SIZE = 1e-4f;
 465
 466 // =======================================================================
 467 // function : BuildNode
 468 // purpose  : Builds node using task info
 469 // =======================================================================
 470 void OpenGl_BinnedBVHBuilder::BuildNode (OpenGl_RaytraceScene& theGeometry,
 471                                          const int             theTask)
 472 {
 473   OpenGl_BVHNodeTask aTask = myNodeTasksQueue[theTask];
 474   OpenGl_BVHNode     aNode = myTree.Node (aTask.NodeToBuild);
 475
 476 #ifdef BVH_DEBUG_OUTPUT
 477   std::cout << "Build node " << aTask.NodeToBuild << ": [" <<
 478                   aTask.BegTriangle << ", " << aTask.EndTriangle << "]" << std::endl;
 479 #endif
 480
 481   OpenGl_AABB anAABB (aNode.MinPoint(), aNode.MaxPoint());
 482   const OpenGl_RTVec4f aNodeSize = anAABB.Size();
 483   const float aNodeArea = anAABB.Area();
 484
 485   // Parameters for storing best split
 486   float aMinSplitCost = std::numeric_limits<float>::max();
 487
 488   int aMinSplitAxis     = -1;
 489   int aMinSplitIndex    =  0;
 490   int aMinSplitLftCount =  0;
 491   int aMinSplitRghCount =  0;
 492
 493   OpenGl_AABB aMinSplitLftAABB;
 494   OpenGl_AABB aMinSplitRghAABB;
 495
 496   // Find best split
 497   for (int anAxis = 0; anAxis < 3; ++anAxis)
 498   {
 499     if (aNodeSize[anAxis] <= THE_NODE_MIN_SIZE)
 500       continue;
 501
 502     OpenGl_BinVector aBins (THE_NUMBER_OF_BINS);
 503     GetSubVolumes (theGeometry, aNode, aBins, anAxis);
 504
 505     // Choose the best split (with minimum SAH cost)
 506     for (int aSplit = 1; aSplit < THE_NUMBER_OF_BINS; ++aSplit)
 507     {
 508       int aLftCount = 0;
 509       int aRghCount = 0;
 510       OpenGl_AABB aLftAABB;
 511       OpenGl_AABB aRghAABB;
 512       for (int anIndex = 0; anIndex < aSplit; ++anIndex)
 513       {
 514         aLftCount += aBins[anIndex].Count;
 515         aLftAABB.Combine (aBins[anIndex].Volume);
 516       }
 517
 518       for (int anIndex = aSplit; anIndex < THE_NUMBER_OF_BINS; ++anIndex)
 519       {
 520         aRghCount += aBins[anIndex].Count;
 521         aRghAABB.Combine (aBins[anIndex].Volume);
 522       }
 523
 524       // Simple SAH evaluation
 525       float aCost = ( aLftAABB.Area() / aNodeArea ) * aLftCount +
 526                     ( aRghAABB.Area() / aNodeArea ) * aRghCount;
 527
 528 #ifdef BVH_DEBUG_OUTPUT
 529       std::cout << "\t\tBin " << aSplit << ", Cost = " << aCost << std::endl;
 530 #endif
 531
 532       if (aCost <= aMinSplitCost)
 533       {
 534         aMinSplitCost     = aCost;
 535         aMinSplitAxis     = anAxis;
 536         aMinSplitIndex    = aSplit;
 537         aMinSplitLftAABB  = aLftAABB;
 538         aMinSplitRghAABB  = aRghAABB;
 539         aMinSplitLftCount = aLftCount;
 540         aMinSplitRghCount = aRghCount;
 541       }
 542     }
 543   }
 544
 545   if (aMinSplitAxis == -1)
 546   {
 547     // make outer (leaf) node
 548     myTree.DataRcrdBuffer()[aTask.NodeToBuild].x() = 1;
 549     return;
 550   }
 551
 552 #ifdef BVH_DEBUG_OUTPUT
 553   switch (aMinSplitAxis)
 554   {
 555   case 0:
 556     std::cout << "\tSplit axis: X = " << aMinSplitIndex << std::endl;
 557     break;
 558   case 1:
 559     std::cout << "\tSplit axis: Y = " << aMinSplitIndex << std::endl;
 560     break;
 561   case 2:
 562     std::cout << "\tSplit axis: Z = " << aMinSplitIndex << std::endl;
 563     break;
 564   }
 565 #endif
 566
 567   int aMiddle = SplitTriangles (theGeometry, aTask.BegTriangle, aTask.EndTriangle,
 568                                 aNode, aMinSplitIndex - 1, aMinSplitAxis);
 569
 570 #ifdef BVH_DEBUG_OUTPUT
 571   std::cout << "\tLeft child: [" << aTask.BegTriangle << ", "
 572                       << aMiddle - 1 << "]" << std::endl;
 573
 574   std::cout << "\tRight child: [" << aMiddle << ", "
 575                       << aTask.EndTriangle << "]" << std::endl;
 576 #endif
 577
 578 #define BVH_SIDE_LFT 1
 579 #define BVH_SIDE_RGH 2
 580
 581   // Setting up tasks for child nodes
 582   for (int aSide = BVH_SIDE_LFT; aSide <= BVH_SIDE_RGH; ++aSide)
 583   {
 584     OpenGl_RTVec4f aMinPoint = (aSide == BVH_SIDE_LFT)
 585                              ? aMinSplitLftAABB.CornerMin()
 586                              : aMinSplitRghAABB.CornerMin();
 587     OpenGl_RTVec4f aMaxPoint = (aSide == BVH_SIDE_LFT)
 588                              ? aMinSplitLftAABB.CornerMax()
 589                              : aMinSplitRghAABB.CornerMax();
 590
 591     int aBegTriangle = (aSide == BVH_SIDE_LFT)
 592                      ? aTask.BegTriangle
 593                      : aMiddle;
 594     int aEndTriangle = (aSide == BVH_SIDE_LFT)
 595                      ? aMiddle - 1
 596                      : aTask.EndTriangle;
 597
 598     OpenGl_BVHNode aChild (aMinPoint, aMaxPoint, aBegTriangle, aEndTriangle);
 599     aChild.SetLevel (aNode.Level() + 1);
 600
 601     // Check to see if child node must be split
 602     const int aNbTriangles = (aSide == BVH_SIDE_LFT)
 603                            ? aMinSplitLftCount
 604                            : aMinSplitRghCount;
 605
 606     const int isChildALeaf = (aNbTriangles <= THE_MAX_LEAF_TRIANGLES) || (aNode.Level() >= myMaxDepth);
 607     if (isChildALeaf)
 608       aChild.SetOuter();
 609     else
 610       aChild.SetInner();
 611
 612     const int aChildIndex = myTree.PushNode (aChild);
 613
 614     // Modify parent node
 615     myTree.DataRcrdBuffer()[aTask.NodeToBuild].x() = 0; // inner node flag
 616     if (aSide == BVH_SIDE_LFT)
 617       myTree.DataRcrdBuffer()[aTask.NodeToBuild].y() = aChildIndex; // left child
 618     else
 619       myTree.DataRcrdBuffer()[aTask.NodeToBuild].z() = aChildIndex; // right child
 620
 621     // Make new building task
 622     if (!isChildALeaf)
 623       myNodeTasksQueue.push_back (OpenGl_BVHNodeTask (aChildIndex, aBegTriangle, aEndTriangle));
 624   }
 625 }
 626
 627 // =======================================================================
 628 // function : SplitTriangles
 629 // purpose  : Splits node triangles into two intervals for child nodes
 630 // =======================================================================
 631 int OpenGl_BinnedBVHBuilder::SplitTriangles (OpenGl_RaytraceScene& theGeometry,
 632                                              const int             theBegTriangle,
 633                                              const int             theEndTriangle,
 634                                              OpenGl_BVHNode&       theNode,
 635                                              int                   theBin,
 636                                              const int             theAxis)
 637 {
 638   int aLftIndex (theBegTriangle);
 639   int aRghIndex (theEndTriangle);
 640
 641   const float aMin = theNode.MinPoint()[theAxis];
 642   const float aMax = theNode.MaxPoint()[theAxis];
 643
 644   const float aStep = (aMax - aMin) / THE_NUMBER_OF_BINS;
 645
 646   do
 647   {
 648     while ((int )floorf ((theGeometry.CenterAxis (aLftIndex, theAxis) - aMin) / aStep) <= theBin
 649               && aLftIndex < theEndTriangle)
 650     {
 651       ++aLftIndex;
 652     }
 653     while ((int )floorf ((theGeometry.CenterAxis (aRghIndex, theAxis) - aMin) / aStep) >  theBin
 654               && aRghIndex > theBegTriangle)
 655     {
 656       --aRghIndex;
 657     }
 658
 659     if (aLftIndex <= aRghIndex)
 660     {
 661       if (aLftIndex != aRghIndex)
 662       {
 663         OpenGl_RTVec4i aLftTrg = theGeometry.Triangles[aLftIndex];
 664         OpenGl_RTVec4i aRghTrg = theGeometry.Triangles[aRghIndex];
 665         theGeometry.Triangles[aLftIndex] = aRghTrg;
 666         theGeometry.Triangles[aRghIndex] = aLftTrg;
 667       }
 668
 669       aLftIndex++; aRghIndex--;
 670     }
 671   } while (aLftIndex <= aRghIndex);
 672
 673   return aLftIndex;
 674 }
 675
 676 // =======================================================================
 677 // function : GetSubVolumes
 678 // purpose  : Arranges node triangles into bins
 679 // =======================================================================
 680 void OpenGl_BinnedBVHBuilder::GetSubVolumes (OpenGl_RaytraceScene& theGeometry,
 681                                              const OpenGl_BVHNode& theNode,
 682                                              OpenGl_BinVector&     theBins,
 683                                              const int             theAxis)
 684 {
 685   const float aMin = theNode.MinPoint()[theAxis];
 686   const float aMax = theNode.MaxPoint()[theAxis];
 687
 688   const float aStep = (aMax - aMin) / THE_NUMBER_OF_BINS;
 689
 690   for (int aTri = theNode.BegTriangle(); aTri <= theNode.EndTriangle(); ++aTri)
 691   {
 692     float aCenter = theGeometry.CenterAxis (aTri, theAxis);
 693     int aBinIndex = (int )floorf ((aCenter - aMin) * ( 1.0f / aStep));
 694     if (aBinIndex < 0)
 695     {
 696       aBinIndex = 0;
 697     }
 698     else if (aBinIndex >= THE_NUMBER_OF_BINS)
 699     {
 700       aBinIndex = THE_NUMBER_OF_BINS - 1;
 701     }
 702
 703     theBins[aBinIndex].Count++;
 704     theBins[aBinIndex].Volume.Combine (theGeometry.Box (aTri));
 705   }
 706 }
 707
 708 namespace OpenGl_Raytrace
 709 {
 710   // =======================================================================
 711   // function : IsRaytracedElement
 712   // purpose  : Checks to see if the element contains ray-trace geometry
 713   // =======================================================================
 714   Standard_Boolean IsRaytracedElement (const OpenGl_ElementNode* theNode)
 715   {
 716     if (TelParray == theNode->type)
 717     {
 718       OpenGl_PrimitiveArray* anArray = dynamic_cast< OpenGl_PrimitiveArray* > (theNode->elem);
 719       return anArray->PArray()->type >= TelPolygonsArrayType;
 720     }
 721     return Standard_False;
 722   }
 723
 724   // =======================================================================
 725   // function : IsRaytracedGroup
 726   // purpose  : Checks to see if the group contains ray-trace geometry
 727   // =======================================================================
 728   Standard_Boolean IsRaytracedGroup (const OpenGl_Group *theGroup)
 729   {
 730     const OpenGl_ElementNode* aNode;
 731     for (aNode = theGroup->FirstNode(); aNode != NULL; aNode = aNode->next)
 732     {
 733       if (IsRaytracedElement (aNode))
 734       {
 735         return Standard_True;
 736       }
 737     }
 738     return Standard_False;
 739   }
 740
 741   // =======================================================================
 742   // function : IsRaytracedStructure
 743   // purpose  : Checks to see if the structure contains ray-trace geometry
 744   // =======================================================================
 745   Standard_Boolean IsRaytracedStructure (const OpenGl_Structure *theStructure)
 746   {
 747     for (OpenGl_ListOfGroup::Iterator anItg (theStructure->Groups());
 748          anItg.More(); anItg.Next())
 749     {
 750       if (anItg.Value()->IsRaytracable())
 751         return Standard_True;
 752     }
 753     for (OpenGl_ListOfStructure::Iterator anIts (theStructure->ConnectedStructures());
 754          anIts.More(); anIts.Next())
 755     {
 756       if (IsRaytracedStructure (anIts.Value()))
 757         return Standard_True;
 758     }
 759     return Standard_False;
 760   }
 761 }
 762
 763 #endif