API tools faq
paste
Advertisement
Zgragselus

Untitled

Zgragselus
Jan 29th, 2023 (edited)
902
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.24 KB | None | 0 0
raw download clone embed print report
  1. BVHBuildNode* RecursiveBuild(BVHPrimitiveInfo* info, int begin, int end, int* totalNodes)
  2. {
  3.     BVHBuildNode* node = (BVHBuildNode*)_aligned_malloc(sizeof(BVHBuildNode), 16);
  4.     node->mChildren[0] = node->mChildren[1] = nullptr;
  5.     (*totalNodes)++;
  6.  
  7.     AABB bounds = AABB();
  8.     for (int i = begin; i < end; i++)
  9.     {
  10.         bounds.Union(info[i].mBounds);
  11.     }
  12.  
  13.     int primitives = end - begin;
  14.     if (primitives <= mMaxPrimsInNode)
  15.     {
  16.         // Create leaf
  17.         unsigned int idx = mIndexNext;
  18.         mIndexNext += primitives;
  19.         if (mIndexNext > mIndexCount)
  20.         {
  21.             mIndices = (unsigned int*)realloc(mIndices, sizeof(unsigned int) * mIndexCount * 2);
  22.             mIndexCount *= 2;
  23.         }
  24.  
  25.         for (int i = 0; i < primitives; i++)
  26.         {
  27.             mIndices[idx + i] = info[begin + i].mPrimitiveID;
  28.         }
  29.  
  30.         node->InitLeaf(idx, primitives, bounds, mTopLevel, mPrintDebugInfo);
  31.         return node;
  32.     }
  33.     else
  34.     {
  35.         // Compute bound of primitive centroids, choose split dimension
  36.         AABB centroidBounds = AABB();
  37.         for (int i = begin; i < end; ++i)
  38.         {
  39.             centroidBounds.Union(info[i].mCentroid);
  40.         }
  41.  
  42.         // Get splitting dimension
  43.         int dim = centroidBounds.GetLongestAxis();
  44.  
  45.         // If some conditions are met, build just a single leaf
  46.         if (centroidBounds.mMin[dim] == centroidBounds.mMax[dim] || end - begin <= mMaxPrimsInNode)
  47.         {
  48.             // Create leaf
  49.             unsigned int idx = mIndexNext;
  50.             mIndexNext += primitives;
  51.             if (mIndexNext > mIndexCount)
  52.             {
  53.                 mIndices = (unsigned int*)realloc(mIndices, sizeof(unsigned int) * mIndexCount * 2);
  54.                 mIndexCount *= 2;
  55.             }
  56.  
  57.             for (int i = 0; i < primitives; i++)
  58.             {
  59.                 mIndices[idx + i] = info[begin + i].mPrimitiveID;
  60.             }
  61.  
  62.             node->InitLeaf(idx, primitives, bounds, mTopLevel, mPrintDebugInfo);
  63.             return node;
  64.         }
  65.         // Otherwise partition based on split method
  66.         else
  67.         {
  68.             int mid = -1;
  69.             float pmid = -1.0f;
  70.             BVHPrimitiveInfo* midPtr = NULL;
  71.  
  72.             float minCost = std::numeric_limits<float>::infinity();
  73.             unsigned int minBucket = 0;
  74.             float leafCost = 0.0f;
  75.  
  76.             unsigned int minPosition = 0;
  77.             unsigned int minAxis = 0;
  78.  
  79.             switch (mSplitMode)
  80.             {
  81.             // Splitting in the middle of longest axis
  82.             case SplitMode::MIDDLE:
  83.                 pmid = (centroidBounds.mMin[dim] + centroidBounds.mMax[dim]) / 2.0f;
  84.                 midPtr = std::partition(&info[begin], &info[end], [dim, pmid](const BVHPrimitiveInfo& pi) { return pi.mCentroid[dim] < pmid; });
  85.                 mid = (int)(midPtr - &info[0]);
  86.                 if (mid != begin && mid != end)
  87.                 {
  88.                     break;
  89.                 }
  90.  
  91.             // Splitting based on median
  92.             case SplitMode::EQUAL_COUNTS:
  93.                 mid = (begin + end) / 2;
  94.                 std::nth_element(&info[begin], &info[mid], &info[end - 1] + 1, [dim](const BVHPrimitiveInfo& a, const BVHPrimitiveInfo& b) { return a.mCentroid[dim] < b.mCentroid[dim]; });
  95.                 break;
  96.  
  97.             // SAH splitting
  98.             case SplitMode::SAH:
  99.                 if (primitives <= 2)
  100.                 {
  101.                     mid = (begin + end) / 2;
  102.                     std::nth_element(&info[begin], &info[mid], &info[end - 1] + 1, [dim](const BVHPrimitiveInfo& a, const BVHPrimitiveInfo& b) { return a.mCentroid[dim] < b.mCentroid[dim]; });
  103.                 }
  104.                 else
  105.                 {
  106.                     // For each axis
  107.                     unsigned int bestAxis = 0;
  108.                     for (unsigned int axis = 0; axis < 3; axis++)
  109.                     {
  110.                         // Re-initialize buckets
  111.                         for (unsigned int i = 0; i < mBucketsCount; i++)
  112.                         {
  113.                             mBuckets[i].mBounds = AABB();
  114.                             mBuckets[i].mCount = 0;
  115.                             mSahCost[i] = 0.0f;
  116.                         }
  117.  
  118.                         // Prepare for SAH-partition buckets
  119.                         for (int i = begin; i < end; i++)
  120.                         {
  121.                             unsigned int b = (unsigned int)((float)mBucketsCount * ((info[i].mCentroid[axis] - centroidBounds.mMin[axis]) / (centroidBounds.mMax[axis] - centroidBounds.mMin[axis])));
  122.                             if (b >= mBucketsCount)
  123.                             {
  124.                                 b = mBucketsCount - 1;
  125.                             }
  126.  
  127.                             mBuckets[b].mCount++;
  128.                             mBuckets[b].mBounds.Union(info[i].mBounds);
  129.                         }
  130.  
  131.                         // Compute costs for splitting after each bucket
  132.                         for (unsigned int i = 0; i < mBucketsCount - 1; i++)
  133.                         {
  134.                             AABB b0 = AABB();
  135.                             AABB b1 = AABB();
  136.                             int count0 = 0;
  137.                             int count1 = 0;
  138.  
  139.                             for (unsigned int j = 0; j <= i; j++)
  140.                             {
  141.                                 b0.Union(mBuckets[j].mBounds);
  142.                                 count0 += mBuckets[j].mCount;
  143.                             }
  144.  
  145.                             for (unsigned int j = i + 1; j < mBucketsCount; j++)
  146.                             {
  147.                                 b1.Union(mBuckets[j].mBounds);
  148.                                 count1 += mBuckets[j].mCount;
  149.                             }
  150.  
  151.                             mSahCost[i] = 1.0f + (count0 * b0.GetSurfaceArea() + count1 * b1.GetSurfaceArea()) / bounds.GetSurfaceArea();
  152.                         }
  153.  
  154.                         // Select best cost bucket
  155.                         for (unsigned int i = 0; i < mBucketsCount - 1; i++)
  156.                         {
  157.                             if (mSahCost[i] < minCost)
  158.                             {
  159.                                 minCost = mSahCost[i];
  160.                                 minBucket = i;
  161.                                 bestAxis = axis;
  162.                             }
  163.                         }
  164.                     }
  165.  
  166.                     leafCost = (float)primitives;
  167.                     dim = bestAxis;
  168.                     if (leafCost < minCost || primitives > mMaxPrimsInNode)
  169.                     {
  170.                         midPtr = std::partition(&info[begin], &info[end], [&](const BVHPrimitiveInfo& pi)
  171.                         {
  172.                             unsigned int b = (unsigned int)((float)mBucketsCount * ((pi.mCentroid[dim] - centroidBounds.mMin[dim]) / (centroidBounds.mMax[dim] - centroidBounds.mMin[dim])));
  173.                             if (b >= mBucketsCount)
  174.                             {
  175.                                 b = mBucketsCount - 1;
  176.                             }
  177.  
  178.                             return b <= minBucket;
  179.                         });
  180.                         mid = (int)(midPtr - &info[0]);
  181.                     }
  182.                     else
  183.                     {
  184.                         // Create leaf
  185.                         unsigned int idx = mIndexNext;
  186.                         mIndexNext += primitives;
  187.                         if (mIndexNext > mIndexCount)
  188.                         {
  189.                             mIndices = (unsigned int*)realloc(mIndices, sizeof(unsigned int) * mIndexCount * 2);
  190.                             mIndexCount *= 2;
  191.                         }
  192.  
  193.                         for (int i = 0; i < primitives; i++)
  194.                         {
  195.                             mIndices[idx + i] = info[begin + i].mPrimitiveID;
  196.                         }
  197.  
  198.                         node->InitLeaf(idx, primitives, bounds, mTopLevel, mPrintDebugInfo);
  199.                         return node;
  200.                     }
  201.                 }
  202.                 break;
  203.  
  204.             // SAH with spatial splits
  205.             case SplitMode::SPLIT_SAH:
  206.                 if (primitives <= 2)
  207.                 {
  208.                     mid = (begin + end) / 2;
  209.                     std::nth_element(&info[begin], &info[mid], &info[end - 1] + 1, [dim](const BVHPrimitiveInfo& a, const BVHPrimitiveInfo& b) { return a.mCentroid[dim] < b.mCentroid[dim]; });
  210.                 }
  211.                 else
  212.                 {
  213.                     // For each axis
  214.                     unsigned int bestAxis = 0;
  215.                     for (unsigned int axis = 0; axis < 3; axis++)
  216.                     {
  217.                         // Re-initialize buckets
  218.                         for (unsigned int i = 0; i < mBucketsCount; i++)
  219.                         {
  220.                             mBuckets[i].mBounds = AABB();
  221.                             mBuckets[i].mCount = 0;
  222.                             mSahCost[i] = 0.0f;
  223.                         }
  224.  
  225.                         // Prepare for SAH-partition buckets
  226.                         for (int i = begin; i < end; i++)
  227.                         {
  228.                             unsigned int b = (unsigned int)((float)mBucketsCount * ((info[i].mCentroid[axis] - centroidBounds.mMin[axis]) / (centroidBounds.mMax[axis] - centroidBounds.mMin[axis])));
  229.                             if (b >= mBucketsCount)
  230.                             {
  231.                                 b = mBucketsCount - 1;
  232.                             }
  233.  
  234.                             mBuckets[b].mCount++;
  235.                             mBuckets[b].mBounds.Union(info[i].mBounds);
  236.                         }
  237.  
  238.                         // Compute costs for splitting after each bucket
  239.                         for (unsigned int i = 0; i < mBucketsCount - 1; i++)
  240.                         {
  241.                             AABB b0 = AABB();
  242.                             AABB b1 = AABB();
  243.                             int count0 = 0;
  244.                             int count1 = 0;
  245.  
  246.                             for (unsigned int j = 0; j <= i; j++)
  247.                             {
  248.                                 b0.Union(mBuckets[j].mBounds);
  249.                                 count0 += mBuckets[j].mCount;
  250.                             }
  251.  
  252.                             for (unsigned int j = i + 1; j < mBucketsCount; j++)
  253.                             {
  254.                                 b1.Union(mBuckets[j].mBounds);
  255.                                 count1 += mBuckets[j].mCount;
  256.                             }
  257.  
  258.                             mSahCost[i] = 1.0f + (count0 * b0.GetSurfaceArea() + count1 * b1.GetSurfaceArea()) / bounds.GetSurfaceArea();
  259.                         }
  260.  
  261.                         // Select best cost bucket
  262.                         for (unsigned int i = 0; i < mBucketsCount - 1; i++)
  263.                         {
  264.                             if (mSahCost[i] < minCost)
  265.                             {
  266.                                 minCost = mSahCost[i];
  267.                                 minBucket = i;
  268.                                 bestAxis = axis;
  269.                             }
  270.                         }
  271.                     }
  272.  
  273.                     leafCost = (float)primitives;
  274.                     dim = bestAxis;
  275.                     if (leafCost < minCost || primitives > mMaxPrimsInNode)
  276.                     {
  277.                         midPtr = std::partition(&info[begin], &info[end], [&](const BVHPrimitiveInfo& pi)
  278.                         {
  279.                             unsigned int b = (unsigned int)((float)mBucketsCount * ((pi.mCentroid[dim] - centroidBounds.mMin[dim]) / (centroidBounds.mMax[dim] - centroidBounds.mMin[dim])));
  280.                             if (b >= mBucketsCount)
  281.                             {
  282.                                 b = mBucketsCount - 1;
  283.                             }
  284.  
  285.                             return b <= minBucket;
  286.                         });
  287.                         mid = (int)(midPtr - &info[0]);
  288.                     }
  289.                     else
  290.                     {
  291.                         // Create leaf
  292.                         unsigned int idx = mIndexNext;
  293.                         mIndexNext += primitives;
  294.                         if (mIndexNext > mIndexCount)
  295.                         {
  296.                             mIndices = (unsigned int*)realloc(mIndices, sizeof(unsigned int) * mIndexCount * 2);
  297.                             mIndexCount *= 2;
  298.                         }
  299.  
  300.                         for (int i = 0; i < primitives; i++)
  301.                         {
  302.                             mIndices[idx + i] = info[begin + i].mPrimitiveID;
  303.                         }
  304.  
  305.                         node->InitLeaf(idx, primitives, bounds, mTopLevel, mPrintDebugInfo);
  306.                         return node;
  307.                     }
  308.                 }
  309.                 break;
  310.             }
  311.  
  312.             if (begin == mid || mid == end)
  313.             {
  314.                 mid = (begin + end) / 2;
  315.                 std::nth_element(&info[begin], &info[mid], &info[end - 1] + 1, [dim](const BVHPrimitiveInfo & a, const BVHPrimitiveInfo & b) { return a.mCentroid[dim] < b.mCentroid[dim]; });
  316.             }
  317.  
  318.             node->InitInterior(dim,
  319.                 RecursiveBuild(info, begin, mid, totalNodes),
  320.                 RecursiveBuild(info, mid, end, totalNodes));
  321.         }
  322.     }
  323.  
  324.     return node;
  325. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!