------------------------------------------------------------------------------
| 126 | |
| 127 | //------------------------------------------------------------------------------ |
| 128 | void vtkModifiedBSPTree::BuildLocatorInternal() |
| 129 | { |
| 130 | vtkIdType numCells; |
| 131 | if (!this->DataSet || (numCells = this->DataSet->GetNumberOfCells()) < 1) |
| 132 | { |
| 133 | vtkDebugMacro(<< "No Cells to divide"); |
| 134 | return; |
| 135 | } |
| 136 | vtkDebugMacro(<< "Creating BSPTree for " << numCells << " cells"); |
| 137 | |
| 138 | // Make sure the appropriate data is available |
| 139 | this->FreeSearchStructure(); |
| 140 | |
| 141 | // create the root node |
| 142 | this->mRoot = std::make_shared<BSPNode>(); |
| 143 | this->mRoot->mAxis = rand() % 3; |
| 144 | this->mRoot->depth = 0; |
| 145 | |
| 146 | this->ComputeCellBounds(); |
| 147 | |
| 148 | // sort the cells into 6 lists using structure for subdividing tests |
| 149 | Sorted_cell_extents_Lists* lists = new Sorted_cell_extents_Lists(numCells); |
| 150 | vtkSMPTools::For(0, numCells, |
| 151 | [&](vtkIdType begin, vtkIdType end) |
| 152 | { |
| 153 | double cellBounds[6], *cellBoundsPtr; |
| 154 | cellBoundsPtr = cellBounds; |
| 155 | for (uint8_t i = 0; i < 3; ++i) |
| 156 | { |
| 157 | for (vtkIdType j = begin; j < end; ++j) |
| 158 | { |
| 159 | this->GetCellBounds(j, cellBoundsPtr); |
| 160 | lists->Mins[i][j].min = cellBoundsPtr[i * 2]; |
| 161 | lists->Mins[i][j].max = cellBoundsPtr[i * 2 + 1]; |
| 162 | lists->Mins[i][j].cell_ID = j; |
| 163 | lists->Maxs[i][j].min = cellBoundsPtr[i * 2]; |
| 164 | lists->Maxs[i][j].max = cellBoundsPtr[i * 2 + 1]; |
| 165 | lists->Maxs[i][j].cell_ID = j; |
| 166 | } |
| 167 | } |
| 168 | }); |
| 169 | for (uint8_t i = 0; i < 3; i++) |
| 170 | { |
| 171 | // Sort |
| 172 | vtkSMPTools::Sort(lists->Mins[i], lists->Mins[i] + numCells, |
| 173 | [&](const cell_extents& tA, const cell_extents& tB) { return tA.min < tB.min; }); |
| 174 | vtkSMPTools::Sort(lists->Maxs[i], lists->Maxs[i] + numCells, |
| 175 | [&](const cell_extents& tA, const cell_extents& tB) { return tA.max > tB.max; }); |
| 176 | } |
| 177 | // call the recursive subdivision routine |
| 178 | vtkDebugMacro(<< "Beginning Subdivision"); |
| 179 | |
| 180 | Subdivide(this->mRoot.get(), lists, this->DataSet, numCells, 0, this->MaxLevel, |
| 181 | this->NumberOfCellsPerNode, this->Level); |
| 182 | delete lists; |
| 183 | |
| 184 | // Child nodes are responsible for freeing the temporary sorted lists |
| 185 | this->BuildTime.Modified(); |
no test coverage detected