------------------------------------------------------------------------------ Shoot random rays and count the number of intersections
| 732 | //------------------------------------------------------------------------------ |
| 733 | // Shoot random rays and count the number of intersections |
| 734 | int vtkPolyhedron::IsInside(const double x[3], double tolerance) |
| 735 | { |
| 736 | bool initialized = false; |
| 737 | if (this->IsRandomSequenceSeedInitialized.compare_exchange_strong(initialized, true)) |
| 738 | { |
| 739 | this->RandomSequence->SetSeed(static_cast<int>(std::time(nullptr))); |
| 740 | } |
| 741 | |
| 742 | // do a quick bounds check |
| 743 | this->ComputeBounds(); |
| 744 | double* bounds = this->Bounds; |
| 745 | if (x[0] < bounds[0] || x[0] > bounds[1] || x[1] < bounds[2] || x[1] > bounds[3] || |
| 746 | x[2] < bounds[4] || x[2] > bounds[5]) |
| 747 | { |
| 748 | return 0; |
| 749 | } |
| 750 | |
| 751 | // It's easiest if these computations are done in canonical space |
| 752 | this->GenerateFaces(); |
| 753 | |
| 754 | // This algorithm is adaptive; if there are enough faces in this |
| 755 | // polyhedron, a cell locator is built to accelerate intersections. |
| 756 | // Otherwise brute force looping over cells is used. |
| 757 | vtkIdType nfaces = this->Faces->GetNumberOfCells(); |
| 758 | if (nfaces > 25) |
| 759 | { |
| 760 | this->ConstructLocator(); |
| 761 | } |
| 762 | |
| 763 | // We need a length to normalize the computations |
| 764 | double length = sqrt(this->Superclass::GetLength2()); |
| 765 | |
| 766 | // Perform in/out by shooting random rays. Multiple rays are fired |
| 767 | // to improve accuracy of the result. |
| 768 | // |
| 769 | // The variable iterNumber counts the number of rays fired and is |
| 770 | // limited by the defined variable VTK_MAX_ITER. |
| 771 | // |
| 772 | // The variable deltaVotes keeps track of the number of votes for |
| 773 | // "in" versus "out" of the surface. When deltaVotes > 0, more votes |
| 774 | // have counted for "in" than "out". When deltaVotes < 0, more votes |
| 775 | // have counted for "out" than "in". When the delta_vote exceeds or |
| 776 | // equals the defined variable VTK_VOTE_THRESHOLD, then the |
| 777 | // appropriate "in" or "out" status is returned. |
| 778 | // |
| 779 | double rayMag, ray[3], xray[3], t, pcoords[3], xint[3]; |
| 780 | int i, numInts, iterNumber, deltaVotes, subId; |
| 781 | vtkIdType idx, numCells; |
| 782 | double tol = tolerance * length; |
| 783 | |
| 784 | for (deltaVotes = 0, iterNumber = 1; |
| 785 | (iterNumber < VTK_MAX_ITER) && (std::abs(deltaVotes) < VTK_VOTE_THRESHOLD); iterNumber++) |
| 786 | { |
| 787 | // Define a random ray to fire. |
| 788 | do |
| 789 | { |
| 790 | for (i = 0; i < 3; i++) |
| 791 | { |