! finds the best split */
| 63 | |
| 64 | /*! finds the best split */ |
| 65 | const Split find(const range<size_t>& set, size_t logBlockSize) |
| 66 | { |
| 67 | Vec3fa axis0(0,0,1); |
| 68 | uint64_t bestGeomPrimID = -1; |
| 69 | |
| 70 | /* curve with minimum ID determines first axis */ |
| 71 | for (size_t i=set.begin(); i<set.end(); i++) |
| 72 | { |
| 73 | const uint64_t geomprimID = prims[i].ID64(); |
| 74 | if (geomprimID >= bestGeomPrimID) continue; |
| 75 | const Vec3fa axis = direction(prims[i]); |
| 76 | if (sqr_length(axis) > 1E-18f) { |
| 77 | axis0 = normalize(axis); |
| 78 | bestGeomPrimID = geomprimID; |
| 79 | } |
| 80 | } |
| 81 | |
| 82 | /* find 2nd axis that is most misaligned with first axis and has minimum ID */ |
| 83 | float bestCos = 1.0f; |
| 84 | Vec3fa axis1 = axis0; |
| 85 | bestGeomPrimID = -1; |
| 86 | for (size_t i=set.begin(); i<set.end(); i++) |
| 87 | { |
| 88 | const uint64_t geomprimID = prims[i].ID64(); |
| 89 | Vec3fa axisi = direction(prims[i]); |
| 90 | float leni = length(axisi); |
| 91 | if (leni == 0.0f) continue; |
| 92 | axisi /= leni; |
| 93 | float cos = abs(dot(axisi,axis0)); |
| 94 | if ((cos == bestCos && (geomprimID < bestGeomPrimID)) || cos < bestCos) { |
| 95 | bestCos = cos; axis1 = axisi; |
| 96 | bestGeomPrimID = geomprimID; |
| 97 | } |
| 98 | } |
| 99 | |
| 100 | /* partition the two strands */ |
| 101 | size_t lnum = 0, rnum = 0; |
| 102 | BBox3fa lbounds = empty, rbounds = empty; |
| 103 | const LinearSpace3fa space0 = frame(axis0).transposed(); |
| 104 | const LinearSpace3fa space1 = frame(axis1).transposed(); |
| 105 | |
| 106 | for (size_t i=set.begin(); i<set.end(); i++) |
| 107 | { |
| 108 | PrimRef& prim = prims[i]; |
| 109 | const Vec3fa axisi = normalize(direction(prim)); |
| 110 | const float cos0 = abs(dot(axisi,axis0)); |
| 111 | const float cos1 = abs(dot(axisi,axis1)); |
| 112 | |
| 113 | if (cos0 > cos1) { lnum++; lbounds.extend(bounds(space0,prim)); } |
| 114 | else { rnum++; rbounds.extend(bounds(space1,prim)); } |
| 115 | } |
| 116 | |
| 117 | /*! return an invalid split if we do not partition */ |
| 118 | if (lnum == 0 || rnum == 0) |
| 119 | return Split(inf,axis0,axis1); |
| 120 | |
| 121 | /*! calculate sah for the split */ |
| 122 | const size_t lblocks = (lnum+(1ull<<logBlockSize)-1ull) >> logBlockSize; |