12 #ifndef hifi_GeometryUtil_h
13 #define hifi_GeometryUtil_h
15 #include <glm/glm.hpp>
21 glm::vec3 computeVectorFromPointToSegment(
const glm::vec3& point,
const glm::vec3& start,
const glm::vec3& end);
29 bool findSpherePenetration(
const glm::vec3& point,
const glm::vec3& defaultDirection,
30 float sphereRadius, glm::vec3& penetration);
32 bool findSpherePointPenetration(
const glm::vec3& sphereCenter,
float sphereRadius,
33 const glm::vec3& point, glm::vec3& penetration);
35 bool findPointSpherePenetration(
const glm::vec3& point,
const glm::vec3& sphereCenter,
36 float sphereRadius, glm::vec3& penetration);
38 bool findSphereSpherePenetration(
const glm::vec3& firstCenter,
float firstRadius,
39 const glm::vec3& secondCenter,
float secondRadius, glm::vec3& penetration);
41 bool findSphereSegmentPenetration(
const glm::vec3& sphereCenter,
float sphereRadius,
42 const glm::vec3& segmentStart,
const glm::vec3& segmentEnd, glm::vec3& penetration);
44 bool findSphereCapsulePenetration(
const glm::vec3& sphereCenter,
float sphereRadius,
const glm::vec3& capsuleStart,
45 const glm::vec3& capsuleEnd,
float capsuleRadius, glm::vec3& penetration);
47 bool findPointCapsuleConePenetration(
const glm::vec3& point,
const glm::vec3& capsuleStart,
48 const glm::vec3& capsuleEnd,
float startRadius,
float endRadius, glm::vec3& penetration);
50 bool findSphereCapsuleConePenetration(
const glm::vec3& sphereCenter,
float sphereRadius,
51 const glm::vec3& capsuleStart,
const glm::vec3& capsuleEnd,
52 float startRadius,
float endRadius, glm::vec3& penetration);
54 bool findSpherePlanePenetration(
const glm::vec3& sphereCenter,
float sphereRadius,
55 const glm::vec4& plane, glm::vec3& penetration);
65 bool findSphereDiskPenetration(
const glm::vec3& sphereCenter,
float sphereRadius,
66 const glm::vec3& diskCenter,
float diskRadius,
float diskThickness,
const glm::vec3& diskNormal,
67 glm::vec3& penetration);
69 bool findCapsuleSpherePenetration(
const glm::vec3& capsuleStart,
const glm::vec3& capsuleEnd,
float capsuleRadius,
70 const glm::vec3& sphereCenter,
float sphereRadius, glm::vec3& penetration);
72 bool findCapsulePlanePenetration(
const glm::vec3& capsuleStart,
const glm::vec3& capsuleEnd,
float capsuleRadius,
73 const glm::vec4& plane, glm::vec3& penetration);
75 glm::vec3 addPenetrations(
const glm::vec3& currentPenetration,
const glm::vec3& newPenetration);
77 bool findIntersection(
float origin,
float direction,
float corner,
float size,
float& distance);
78 bool findInsideOutIntersection(
float origin,
float direction,
float corner,
float size,
float& distance);
79 bool findRayAABoxIntersection(
const glm::vec3& origin,
const glm::vec3& direction,
const glm::vec3& invDirection,
80 const glm::vec3& corner,
const glm::vec3& scale,
float& distance, BoxFace& face, glm::vec3& surfaceNormal);
82 bool findRaySphereIntersection(
const glm::vec3& origin,
const glm::vec3& direction,
83 const glm::vec3& center,
float radius,
float& distance);
85 bool pointInSphere(
const glm::vec3& origin,
const glm::vec3& center,
float radius);
86 bool pointInCapsule(
const glm::vec3& origin,
const glm::vec3& start,
const glm::vec3& end,
float radius);
88 bool findRayCapsuleIntersection(
const glm::vec3& origin,
const glm::vec3& direction,
89 const glm::vec3& start,
const glm::vec3& end,
float radius,
float& distance);
91 bool findRayRectangleIntersection(
const glm::vec3& origin,
const glm::vec3& direction,
const glm::quat& rotation,
92 const glm::vec3& position,
const glm::vec2& dimensions,
float& distance);
94 bool findRayTriangleIntersection(
const glm::vec3& origin,
const glm::vec3& direction,
95 const glm::vec3& v0,
const glm::vec3& v1,
const glm::vec3& v2,
float& distance,
bool allowBackface =
false);
97 bool findParabolaRectangleIntersection(
const glm::vec3& origin,
const glm::vec3& velocity,
const glm::vec3& acceleration,
98 const glm::vec2& dimensions,
float& parabolicDistance);
100 bool findParabolaSphereIntersection(
const glm::vec3& origin,
const glm::vec3& velocity,
const glm::vec3& acceleration,
101 const glm::vec3& center,
float radius,
float& distance);
103 bool findParabolaTriangleIntersection(
const glm::vec3& origin,
const glm::vec3& velocity,
const glm::vec3& acceleration,
104 const glm::vec3& v0,
const glm::vec3& v1,
const glm::vec3& v2,
float& parabolicDistance,
bool allowBackface =
false);
106 bool findParabolaCapsuleIntersection(
const glm::vec3& origin,
const glm::vec3& velocity,
const glm::vec3& acceleration,
107 const glm::vec3& start,
const glm::vec3& end,
float radius,
const glm::quat& rotation,
float& parabolicDistance);
109 bool findParabolaAABoxIntersection(
const glm::vec3& origin,
const glm::vec3& velocity,
const glm::vec3& acceleration,
110 const glm::vec3& corner,
const glm::vec3& scale,
float& parabolicDistance, BoxFace& face, glm::vec3& surfaceNormal);
117 void swingTwistDecomposition(
const glm::quat& rotation,
118 const glm::vec3& direction,
134 glm::vec3 getNormal()
const;
135 float getArea()
const;
136 Triangle operator*(
const glm::mat4& transform)
const;
139 inline bool findRayTriangleIntersection(
const glm::vec3& origin,
const glm::vec3& direction,
140 const Triangle& triangle,
float& distance,
bool allowBackface =
false) {
141 return findRayTriangleIntersection(origin, direction, triangle.v0, triangle.v1, triangle.v2, distance, allowBackface);
144 inline bool findParabolaTriangleIntersection(
const glm::vec3& origin,
const glm::vec3& velocity,
145 const glm::vec3& acceleration,
const Triangle& triangle,
float& parabolicDistance,
bool allowBackface =
false) {
146 return findParabolaTriangleIntersection(origin, velocity, acceleration, triangle.v0, triangle.v1, triangle.v2, parabolicDistance, allowBackface);
149 int clipTriangleWithPlane(
const Triangle& triangle,
const Plane& plane, Triangle* clippedTriangles,
int maxClippedTriangleCount);
150 int clipTriangleWithPlanes(
const Triangle& triangle,
const Plane* planes,
int planeCount, Triangle* clippedTriangles,
int maxClippedTriangleCount);
152 bool doLineSegmentsIntersect(glm::vec2 r1p1, glm::vec2 r1p2, glm::vec2 r2p1, glm::vec2 r2p2);
153 bool findClosestApproachOfLines(glm::vec3 p1, glm::vec3 d1, glm::vec3 p2, glm::vec3 d2,
float& t1,
float& t2);
154 bool isOnSegment(
float xi,
float yi,
float xj,
float yj,
float xk,
float yk);
155 int computeDirection(
float xi,
float yi,
float xj,
float yj,
float xk,
float yk);
158 float coneSphereAngle(
const glm::vec3& coneCenter,
const glm::vec3& coneDirection,
const glm::vec3& sphereCenter,
float sphereRadius);
160 inline bool rayPlaneIntersection(
const glm::vec3& planePosition,
const glm::vec3& planeNormal,
161 const glm::vec3& rayStart,
const glm::vec3& rayDirection,
float& distanceOut) {
162 float rayDirectionDotPlaneNormal = glm::dot(rayDirection, planeNormal);
163 const float PARALLEL_THRESHOLD = 0.0001f;
164 if (fabsf(rayDirectionDotPlaneNormal) > PARALLEL_THRESHOLD) {
165 float rayStartDotPlaneNormal = glm::dot(planePosition - rayStart, planeNormal);
166 distanceOut = rayStartDotPlaneNormal / rayDirectionDotPlaneNormal;
174 typedef glm::vec2 LineSegment2[2];
180 static void clipToScreen(
const glm::vec2* inputVertexArray,
int length, glm::vec2*& outputVertexArray,
int& outLength);
182 static const float TOP_OF_CLIPPING_WINDOW;
183 static const float BOTTOM_OF_CLIPPING_WINDOW;
184 static const float LEFT_OF_CLIPPING_WINDOW;
185 static const float RIGHT_OF_CLIPPING_WINDOW;
187 static const glm::vec2 TOP_LEFT_CLIPPING_WINDOW;
188 static const glm::vec2 TOP_RIGHT_CLIPPING_WINDOW;
189 static const glm::vec2 BOTTOM_LEFT_CLIPPING_WINDOW;
190 static const glm::vec2 BOTTOM_RIGHT_CLIPPING_WINDOW;
194 static void sutherlandHodgmanPolygonClip(glm::vec2* inVertexArray, glm::vec2* outVertexArray,
195 int inLength,
int& outLength,
const LineSegment2& clipBoundary);
197 static bool pointInsideBoundary(
const glm::vec2& testVertex,
const LineSegment2& clipBoundary);
199 static void segmentIntersectsBoundary(
const glm::vec2& first,
const glm::vec2& second,
200 const LineSegment2& clipBoundary, glm::vec2& intersection);
202 static void appendPoint(glm::vec2 newVertex,
int& outLength, glm::vec2* outVertexArray);
204 static void copyCleanArray(
int& lengthA, glm::vec2* vertexArrayA,
int& lengthB, glm::vec2* vertexArrayB);
208 bool findPlaneFromPoints(
const glm::vec3* points,
size_t numPoints, glm::vec3& planeNormalOut, glm::vec3& pointOnPlaneOut);
212 bool findIntersectionOfThreePlanes(
const glm::vec4& planeA,
const glm::vec4& planeB,
const glm::vec4& planeC, glm::vec3& intersectionPointOut);
214 void generateBoundryLinesForDop14(
const std::vector<float>& dots,
const glm::vec3& center, std::vector<glm::vec3>& linesOut);
216 bool computeRealQuadraticRoots(
float a,
float b,
float c, glm::vec2& roots);
218 unsigned int solveP3(
float *x,
float a,
float b,
float c);
219 bool solve_quartic(
float a,
float b,
float c,
float d, glm::vec4& roots);
220 bool computeRealQuarticRoots(
float a,
float b,
float c,
float d,
float e, glm::vec4& roots);
222 bool isWithin(
float value,
float corner,
float size);
223 bool aaBoxContains(
const glm::vec3& point,
const glm::vec3& corner,
const glm::vec3& scale);
225 void checkPossibleParabolicIntersectionWithZPlane(
float t,
float& minDistance,
226 const glm::vec3& origin,
const glm::vec3& velocity,
const glm::vec3& acceleration,
const glm::vec2& corner,
const glm::vec2& scale);
227 void checkPossibleParabolicIntersectionWithTriangle(
float t,
float& minDistance,
228 const glm::vec3& origin,
const glm::vec3& velocity,
const glm::vec3& acceleration,
229 const glm::vec3& localVelocity,
const glm::vec3& localAcceleration,
const glm::vec3& normal,
230 const glm::vec3& v0,
const glm::vec3& v1,
const glm::vec3& v2,
bool allowBackface);