------------------------------------------------------------------------------------------------ Returns an iterator for all positions close to the given position.
| 122 | // ------------------------------------------------------------------------------------------------ |
| 123 | // Returns an iterator for all positions close to the given position. |
| 124 | void SpatialSort::FindPositions(const aiVector3D &pPosition, |
| 125 | ai_real pRadius, std::vector<unsigned int> &poResults) const { |
| 126 | ai_assert(mFinalized && "The SpatialSort object must be finalized before FindPositions can be called."); |
| 127 | const ai_real dist = CalculateDistance(pPosition); |
| 128 | const ai_real minDist = dist - pRadius, maxDist = dist + pRadius; |
| 129 | |
| 130 | // clear the array |
| 131 | poResults.clear(); |
| 132 | |
| 133 | // quick check for positions outside the range |
| 134 | if (mPositions.size() == 0) |
| 135 | return; |
| 136 | if (maxDist < mPositions.front().mDistance) |
| 137 | return; |
| 138 | if (minDist > mPositions.back().mDistance) |
| 139 | return; |
| 140 | |
| 141 | // do a binary search for the minimal distance to start the iteration there |
| 142 | unsigned int index = (unsigned int)mPositions.size() / 2; |
| 143 | unsigned int binaryStepSize = (unsigned int)mPositions.size() / 4; |
| 144 | while (binaryStepSize > 1) { |
| 145 | if (mPositions[index].mDistance < minDist) |
| 146 | index += binaryStepSize; |
| 147 | else |
| 148 | index -= binaryStepSize; |
| 149 | |
| 150 | binaryStepSize /= 2; |
| 151 | } |
| 152 | |
| 153 | // depending on the direction of the last step we need to single step a bit back or forth |
| 154 | // to find the actual beginning element of the range |
| 155 | while (index > 0 && mPositions[index].mDistance > minDist) |
| 156 | index--; |
| 157 | while (index < (mPositions.size() - 1) && mPositions[index].mDistance < minDist) |
| 158 | index++; |
| 159 | |
| 160 | // Mow start iterating from there until the first position lays outside of the distance range. |
| 161 | // Add all positions inside the distance range within the given radius to the result array |
| 162 | std::vector<Entry>::const_iterator it = mPositions.begin() + index; |
| 163 | const ai_real pSquared = pRadius * pRadius; |
| 164 | while (it->mDistance < maxDist) { |
| 165 | if ((it->mPosition - pPosition).SquareLength() < pSquared) |
| 166 | poResults.push_back(it->mIndex); |
| 167 | ++it; |
| 168 | if (it == mPositions.end()) |
| 169 | break; |
| 170 | } |
| 171 | |
| 172 | // that's it |
| 173 | } |
| 174 | |
| 175 | namespace { |
| 176 |
no test coverage detected