Overte C++ Documentation
GeometryUtil.h
1 //
2 // GeometryUtil.h
3 // libraries/shared/src
4 //
5 // Created by Andrzej Kapolka on 5/21/13.
6 // Copyright 2013 High Fidelity, Inc.
7 //
8 // Distributed under the Apache License, Version 2.0.
9 // See the accompanying file LICENSE or http://www.apache.org/licenses/LICENSE-2.0.html
10 //
11 
12 #ifndef hifi_GeometryUtil_h
13 #define hifi_GeometryUtil_h
14 
15 #include <glm/glm.hpp>
16 #include <vector>
17 #include "BoxBase.h"
18 
19 class Plane;
20 
21 glm::vec3 computeVectorFromPointToSegment(const glm::vec3& point, const glm::vec3& start, const glm::vec3& end);
22 
29 bool findSpherePenetration(const glm::vec3& point, const glm::vec3& defaultDirection,
30  float sphereRadius, glm::vec3& penetration);
31 
32 bool findSpherePointPenetration(const glm::vec3& sphereCenter, float sphereRadius,
33  const glm::vec3& point, glm::vec3& penetration);
34 
35 bool findPointSpherePenetration(const glm::vec3& point, const glm::vec3& sphereCenter,
36  float sphereRadius, glm::vec3& penetration);
37 
38 bool findSphereSpherePenetration(const glm::vec3& firstCenter, float firstRadius,
39  const glm::vec3& secondCenter, float secondRadius, glm::vec3& penetration);
40 
41 bool findSphereSegmentPenetration(const glm::vec3& sphereCenter, float sphereRadius,
42  const glm::vec3& segmentStart, const glm::vec3& segmentEnd, glm::vec3& penetration);
43 
44 bool findSphereCapsulePenetration(const glm::vec3& sphereCenter, float sphereRadius, const glm::vec3& capsuleStart,
45  const glm::vec3& capsuleEnd, float capsuleRadius, glm::vec3& penetration);
46 
47 bool findPointCapsuleConePenetration(const glm::vec3& point, const glm::vec3& capsuleStart,
48  const glm::vec3& capsuleEnd, float startRadius, float endRadius, glm::vec3& penetration);
49 
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);
53 
54 bool findSpherePlanePenetration(const glm::vec3& sphereCenter, float sphereRadius,
55  const glm::vec4& plane, glm::vec3& penetration);
56 
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);
68 
69 bool findCapsuleSpherePenetration(const glm::vec3& capsuleStart, const glm::vec3& capsuleEnd, float capsuleRadius,
70  const glm::vec3& sphereCenter, float sphereRadius, glm::vec3& penetration);
71 
72 bool findCapsulePlanePenetration(const glm::vec3& capsuleStart, const glm::vec3& capsuleEnd, float capsuleRadius,
73  const glm::vec4& plane, glm::vec3& penetration);
74 
75 glm::vec3 addPenetrations(const glm::vec3& currentPenetration, const glm::vec3& newPenetration);
76 
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);
81 
82 bool findRaySphereIntersection(const glm::vec3& origin, const glm::vec3& direction,
83  const glm::vec3& center, float radius, float& distance);
84 
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);
87 
88 bool findRayCapsuleIntersection(const glm::vec3& origin, const glm::vec3& direction,
89  const glm::vec3& start, const glm::vec3& end, float radius, float& distance);
90 
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);
93 
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);
96 
97 bool findParabolaRectangleIntersection(const glm::vec3& origin, const glm::vec3& velocity, const glm::vec3& acceleration,
98  const glm::vec2& dimensions, float& parabolicDistance);
99 
100 bool findParabolaSphereIntersection(const glm::vec3& origin, const glm::vec3& velocity, const glm::vec3& acceleration,
101  const glm::vec3& center, float radius, float& distance);
102 
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);
105 
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);
108 
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);
111 
117 void swingTwistDecomposition(const glm::quat& rotation,
118  const glm::vec3& direction, // must be normalized
119  glm::quat& swing,
120  glm::quat& twist);
121 
122 /*@jsdoc
123  * A triangle in a mesh.
124  * @typedef {object} Triangle
125  * @property {Vec3} v0 - The position of vertex 0 in the triangle.
126  * @property {Vec3} v1 - The position of vertex 1 in the triangle.
127  * @property {Vec3} v2 - The position of vertex 2 in the triangle.
128  */
129 class Triangle {
130 public:
131  glm::vec3 v0;
132  glm::vec3 v1;
133  glm::vec3 v2;
134  glm::vec3 getNormal() const;
135  float getArea() const;
136  Triangle operator*(const glm::mat4& transform) const;
137 };
138 
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);
142 }
143 
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);
147 }
148 
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);
151 
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);
156 
157 // calculate the angle between a point on a sphere that is closest to the cone.
158 float coneSphereAngle(const glm::vec3& coneCenter, const glm::vec3& coneDirection, const glm::vec3& sphereCenter, float sphereRadius);
159 
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;
167  return true;
168  } else {
169  // ray is parallel to the plane
170  return false;
171  }
172 }
173 
174 typedef glm::vec2 LineSegment2[2];
175 
176 // Polygon Clipping routines inspired by, pseudo code found here: http://www.cs.rit.edu/~icss571/clipTrans/PolyClipBack.html
177 class PolygonClip {
178 
179 public:
180  static void clipToScreen(const glm::vec2* inputVertexArray, int length, glm::vec2*& outputVertexArray, int& outLength);
181 
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;
186 
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;
191 
192 private:
193 
194  static void sutherlandHodgmanPolygonClip(glm::vec2* inVertexArray, glm::vec2* outVertexArray,
195  int inLength, int& outLength, const LineSegment2& clipBoundary);
196 
197  static bool pointInsideBoundary(const glm::vec2& testVertex, const LineSegment2& clipBoundary);
198 
199  static void segmentIntersectsBoundary(const glm::vec2& first, const glm::vec2& second,
200  const LineSegment2& clipBoundary, glm::vec2& intersection);
201 
202  static void appendPoint(glm::vec2 newVertex, int& outLength, glm::vec2* outVertexArray);
203 
204  static void copyCleanArray(int& lengthA, glm::vec2* vertexArrayA, int& lengthB, glm::vec2* vertexArrayB);
205 };
206 
207 // given a set of points, compute a best fit plane that passes as close as possible through all the points.
208 bool findPlaneFromPoints(const glm::vec3* points, size_t numPoints, glm::vec3& planeNormalOut, glm::vec3& pointOnPlaneOut);
209 
210 // plane equation is specified by ax + by + cz + d = 0.
211 // the coefficents are passed in as a vec4. (a, b, c, d)
212 bool findIntersectionOfThreePlanes(const glm::vec4& planeA, const glm::vec4& planeB, const glm::vec4& planeC, glm::vec3& intersectionPointOut);
213 
214 void generateBoundryLinesForDop14(const std::vector<float>& dots, const glm::vec3& center, std::vector<glm::vec3>& linesOut);
215 
216 bool computeRealQuadraticRoots(float a, float b, float c, glm::vec2& roots);
217 
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);
221 
222 bool isWithin(float value, float corner, float size);
223 bool aaBoxContains(const glm::vec3& point, const glm::vec3& corner, const glm::vec3& scale);
224 
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);
231 
232 #endif // hifi_GeometryUtil_h