TriangleGrouperClosestCentroid.cpp 3.1 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394
  1. // SPDX-FileCopyrightText: 2021 Jorrit Rouwe
  2. // SPDX-License-Identifier: MIT
  3. #include <Jolt/Jolt.h>
  4. #include <Jolt/TriangleGrouper/TriangleGrouperClosestCentroid.h>
  5. #include <Jolt/Geometry/MortonCode.h>
  6. #include <Jolt/Core/QuickSort.h>
  7. JPH_NAMESPACE_BEGIN
  8. void TriangleGrouperClosestCentroid::Group(const VertexList &inVertices, const IndexedTriangleList &inTriangles, int inGroupSize, Array<uint> &outGroupedTriangleIndices)
  9. {
  10. const uint triangle_count = (uint)inTriangles.size();
  11. const uint num_batches = (triangle_count + inGroupSize - 1) / inGroupSize;
  12. Array<Vec3> centroids;
  13. centroids.resize(triangle_count);
  14. outGroupedTriangleIndices.resize(triangle_count);
  15. for (uint t = 0; t < triangle_count; ++t)
  16. {
  17. // Store centroid
  18. centroids[t] = inTriangles[t].GetCentroid(inVertices);
  19. // Initialize sort table
  20. outGroupedTriangleIndices[t] = t;
  21. }
  22. Array<uint>::iterator triangles_end = outGroupedTriangleIndices.end();
  23. // Sort per batch
  24. for (uint b = 0; b < num_batches - 1; ++b)
  25. {
  26. // Get iterators
  27. Array<uint>::iterator batch_begin = outGroupedTriangleIndices.begin() + b * inGroupSize;
  28. Array<uint>::iterator batch_end = batch_begin + inGroupSize;
  29. Array<uint>::iterator batch_begin_plus_1 = batch_begin + 1;
  30. Array<uint>::iterator batch_end_minus_1 = batch_end - 1;
  31. // Find triangle with centroid with lowest X coordinate
  32. Array<uint>::iterator lowest_iter = batch_begin;
  33. float lowest_val = centroids[*lowest_iter].GetX();
  34. for (Array<uint>::iterator other = batch_begin; other != triangles_end; ++other)
  35. {
  36. float val = centroids[*other].GetX();
  37. if (val < lowest_val)
  38. {
  39. lowest_iter = other;
  40. lowest_val = val;
  41. }
  42. }
  43. // Make this triangle the first in a new batch
  44. swap(*batch_begin, *lowest_iter);
  45. Vec3 first_centroid = centroids[*batch_begin];
  46. // Sort remaining triangles in batch on distance to first triangle
  47. QuickSort(batch_begin_plus_1, batch_end,
  48. [&first_centroid, &centroids](uint inLHS, uint inRHS)
  49. {
  50. return (centroids[inLHS] - first_centroid).LengthSq() < (centroids[inRHS] - first_centroid).LengthSq();
  51. });
  52. // Loop over remaining triangles
  53. float furthest_dist = (centroids[*batch_end_minus_1] - first_centroid).LengthSq();
  54. for (Array<uint>::iterator other = batch_end; other != triangles_end; ++other)
  55. {
  56. // Check if this triangle is closer than the furthest triangle in the batch
  57. float dist = (centroids[*other] - first_centroid).LengthSq();
  58. if (dist < furthest_dist)
  59. {
  60. // Replace furthest triangle
  61. uint other_val = *other;
  62. *other = *batch_end_minus_1;
  63. // Find first element that is bigger than this one and insert the current item before it
  64. Array<uint>::iterator upper = std::upper_bound(batch_begin_plus_1, batch_end, dist,
  65. [&first_centroid, &centroids](float inLHS, uint inRHS)
  66. {
  67. return inLHS < (centroids[inRHS] - first_centroid).LengthSq();
  68. });
  69. copy_backward(upper, batch_end_minus_1, batch_end);
  70. *upper = other_val;
  71. // Calculate new furthest distance
  72. furthest_dist = (centroids[*batch_end_minus_1] - first_centroid).LengthSq();
  73. }
  74. }
  75. }
  76. }
  77. JPH_NAMESPACE_END