Compute the initial tetrahedron convex hull
| 891 | |
| 892 | // Compute the initial tetrahedron convex hull |
| 893 | bool QuickHull::computeInitialHull(Array<Vector3>& points, QHHalfEdgeStructure& convexHull, |
| 894 | Array<QHHalfEdgeStructure::Face*>& initialFaces, |
| 895 | Array<uint32>& orphanPointsIndices, |
| 896 | MemoryAllocator& allocator, std::vector<Message>& errors) { |
| 897 | |
| 898 | // Find the extreme points on each X, Y and Z axes |
| 899 | |
| 900 | uint32 extremePointsIndices[6] = {0, 0, 0, 0, 0, 0}; |
| 901 | |
| 902 | const uint32 nbPoints = points.size(); |
| 903 | for (uint32 i=0; i < nbPoints; i++) { |
| 904 | |
| 905 | if (points[i].x < points[extremePointsIndices[0]].x) { |
| 906 | extremePointsIndices[0] = i; |
| 907 | } |
| 908 | else if (points[i].x > points[extremePointsIndices[1]].x) { |
| 909 | extremePointsIndices[1] = i; |
| 910 | } |
| 911 | |
| 912 | if (points[i].y < points[extremePointsIndices[2]].y) { |
| 913 | extremePointsIndices[2] = i; |
| 914 | } |
| 915 | else if (points[i].y > points[extremePointsIndices[3]].y) { |
| 916 | extremePointsIndices[3] = i; |
| 917 | } |
| 918 | |
| 919 | if (points[i].z < points[extremePointsIndices[4]].z) { |
| 920 | extremePointsIndices[4] = i; |
| 921 | } |
| 922 | else if (points[i].z > points[extremePointsIndices[5]].z) { |
| 923 | extremePointsIndices[5] = i; |
| 924 | } |
| 925 | } |
| 926 | |
| 927 | // Find the two extreme points with largest distance |
| 928 | |
| 929 | decimal maxLargestDistSquare = 0; |
| 930 | uint32 iMax = 0; |
| 931 | for (uint32 i=0; i < 3; i++) { |
| 932 | const decimal distSquare = (points[extremePointsIndices[i*2]] - points[extremePointsIndices[i*2+1]]).lengthSquare(); |
| 933 | if (distSquare > maxLargestDistSquare) { |
| 934 | iMax = i; |
| 935 | maxLargestDistSquare = distSquare; |
| 936 | } |
| 937 | } |
| 938 | |
| 939 | if (maxLargestDistSquare < MACHINE_EPSILON) { |
| 940 | errors.push_back(Message("Error during initial hull creation in QuickHull: vertices too close to each other")); |
| 941 | return false; |
| 942 | } |
| 943 | |
| 944 | // The pair of points that have the largest distance between them |
| 945 | uint32 i1 = extremePointsIndices[iMax * 2]; |
| 946 | uint32 i2 = extremePointsIndices[iMax * 2 + 1]; |
| 947 | |
| 948 | // Find a third point that is the furthest from line (v1, v2) |
| 949 | uint32 i3 = 0; |
| 950 | maxLargestDistSquare = 0; |