mathUtils.h
Engine/source/math/mathUtils.h
Classes:
class
Used by mTriangleDistance() to pass along collision info.
class
A simple helper struct to define a line.
class
A simple helper struct to define a line segment.
class
A simple helper struct to define a clockwise winding quad.
Namespaces:
namespace
Miscellaneous math utility functions.
Detailed Description
1 2//----------------------------------------------------------------------------- 3// Copyright (c) 2012 GarageGames, LLC 4// 5// Permission is hereby granted, free of charge, to any person obtaining a copy 6// of this software and associated documentation files (the "Software"), to 7// deal in the Software without restriction, including without limitation the 8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or 9// sell copies of the Software, and to permit persons to whom the Software is 10// furnished to do so, subject to the following conditions: 11// 12// The above copyright notice and this permission notice shall be included in 13// all copies or substantial portions of the Software. 14// 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21// IN THE SOFTWARE. 22//----------------------------------------------------------------------------- 23 24#ifndef _MATHUTILS_H_ 25#define _MATHUTILS_H_ 26 27#ifndef _MPOINT3_H_ 28#include "math/mPoint3.h" 29#endif 30 31#ifndef _MMATRIX_H_ 32#include "math/mMatrix.h" 33#endif 34 35#ifndef _MRECT_H_ 36#include "math/mRect.h" 37#endif 38 39#ifndef _TVECTOR_H_ 40#include "core/util/tVector.h" 41#endif 42 43#ifndef _MATHUTIL_FRUSTUM_H_ 44#include "math/util/frustum.h" 45#endif 46 47 48class Box3F; 49class RectI; 50class Frustum; 51 52 53/// Miscellaneous math utility functions. 54namespace MathUtils 55{ 56 /// A simple helper struct to define a line. 57 struct Line 58 { 59 Point3F origin; 60 VectorF direction; 61 }; 62 63 /// A ray is also a line. 64 typedef Line Ray; 65 66 /// A simple helper struct to define a line segment. 67 struct LineSegment 68 { 69 Point3F p0; 70 Point3F p1; 71 }; 72 73 /// A simple helper struct to define a clockwise 74 /// winding quad. 75 struct Quad 76 { 77 Point3F p00; 78 Point3F p01; 79 Point3F p10; 80 Point3F p11; 81 }; 82 83 /// Used by mTriangleDistance() to pass along collision info 84 struct IntersectInfo 85 { 86 LineSegment segment; // Starts at given point, ends at collision 87 Point3F bary; // Barycentric coords for collision 88 }; 89 90 /// Rotate the passed vector around the world-z axis by the passed radians. 91 void vectorRotateZAxis( Point3F &vector, F32 radians ); 92 void vectorRotateZAxis( F32 radians, Point3F *vectors, U32 count ); 93 94 /// Generates a projection matrix with the near plane 95 /// moved forward by the bias amount. This function is a helper primarily 96 /// for working around z-fighting issues. 97 /// 98 /// @param bias The amount to move the near plane forward. 99 /// @param frustum The frustum to generate the new projection matrix from. 100 /// @param outMat The resulting z-biased projection matrix. Note: It must be initialized before the call. 101 /// @param rotate Optional parameter specifying whether to rotate the projection matrix similarly to GFXDevice. 102 /// 103 void getZBiasProjectionMatrix( F32 bias, const Frustum &frustum, MatrixF *outMat, bool rotate = true ); 104 105 /// Creates orientation matrix from a direction vector. Assumes ( 0 0 1 ) is up. 106 MatrixF createOrientFromDir( const Point3F &direction ); 107 108 /// Creates an orthonormal basis matrix with the unit length 109 /// input vector in column 2 (up vector). 110 /// 111 /// @param up The non-zero unit length up vector. 112 /// @param outMat The output matrix which must be initialized prior to the call. 113 /// 114 void getMatrixFromUpVector( const VectorF &up, MatrixF *outMat ); 115 116 /// Creates an orthonormal basis matrix with the unit length 117 /// input vector in column 1 (forward vector). 118 /// 119 /// @param forward The non-zero unit length forward vector. 120 /// @param outMat The output matrix which must be initialized prior to the call. 121 /// 122 void getMatrixFromForwardVector( const VectorF &forward, MatrixF *outMat ); 123 124 /// Creates random direction given angle parameters similar to the particle system. 125 /// 126 /// The angles are relative to the specified axis. Both phi and theta are in degrees. 127 Point3F randomDir( const Point3F &axis, F32 thetaAngleMin, F32 thetaAngleMax, F32 phiAngleMin = 0.0, F32 phiAngleMax = 360.0 ); 128 129 /// Returns a random 3D point within a sphere of the specified radius 130 /// centered at the origin. 131 Point3F randomPointInSphere( F32 radius ); 132 133 /// Returns a random 2D point within a circle of the specified radius 134 /// centered at the origin. 135 Point2F randomPointInCircle( F32 radius ); 136 137 /// Returns yaw and pitch angles from a given vector. 138 /// 139 /// Angles are in RADIANS. 140 /// 141 /// Assumes north is (0.0, 1.0, 0.0), the degrees move upwards clockwise. 142 /// 143 /// The range of yaw is 0 - 2PI. The range of pitch is -PI/2 - PI/2. 144 /// 145 /// <b>ASSUMES Z AXIS IS UP</b> 146 void getAnglesFromVector( const VectorF &vec, F32 &yawAng, F32 &pitchAng ); 147 148 /// Returns vector from given yaw and pitch angles. 149 /// 150 /// Angles are in RADIANS. 151 /// 152 /// Assumes north is (0.0, 1.0, 0.0), the degrees move upwards clockwise. 153 /// 154 /// The range of yaw is 0 - 2PI. The range of pitch is -PI/2 - PI/2. 155 /// 156 /// <b>ASSUMES Z AXIS IS UP</b> 157 void getVectorFromAngles( VectorF &vec, F32 yawAng, F32 pitchAng ); 158 159 /// Returns the angle between two given vectors 160 /// 161 /// Angles is in RADIANS 162 /// 163 F32 getAngleBetweenVectors(VectorF vecA, VectorF vecB); 164 165 166 /// Simple reflection equation - pass in a vector and a normal to reflect off of 167 inline Point3F reflect( Point3F &inVec, Point3F &norm ) 168 { 169 return inVec - norm * ( mDot( inVec, norm ) * 2.0f ); 170 } 171 172 /// Collide two capsules (sphere swept lines) against each other, reporting only if they intersect or not. 173 /// Based on routine from "Real Time Collision Detection" by Christer Ericson pp 114. 174 bool capsuleCapsuleOverlap(const Point3F & a1, const Point3F & b1, F32 radius1, const Point3F & a2, const Point3F & b2, F32 radius2); 175 176 /// Return capsule-sphere overlap. Returns time of first overlap, where time 177 /// is viewed as a sphere of radius radA moving from point A0 to A1. 178 bool capsuleSphereNearestOverlap(const Point3F & A0, const Point3F A1, F32 radA, const Point3F & B, F32 radB, F32 & t); 179 180 /// Intersect two line segments (p1,q1) and (p2,q2), returning points on lines (c1 & c2) and line parameters (s,t). 181 /// Based on routine from "Real Time Collision Detection" by Christer Ericson pp 149. 182 F32 segmentSegmentNearest(const Point3F & p1, const Point3F & q1, const Point3F & p2, const Point3F & q2, F32 & s, F32 & t, Point3F & c1, Point3F & c2); 183 184 /// Transform bounding box making sure to keep original box entirely contained. 185 void transformBoundingBox(const Box3F &sbox, const MatrixF &mat, const Point3F scale, Box3F &dbox); 186 187 bool mProjectWorldToScreen( const Point3F &in, 188 Point3F *out, 189 const RectI &view, 190 const MatrixF &world, 191 const MatrixF &projection ); 192 bool mProjectWorldToScreen( const Point3F &in, 193 Point3F *out, 194 const RectI &view, 195 const MatrixF &worldProjection ); 196 197 void mProjectScreenToWorld( const Point3F &in, 198 Point3F *out, 199 const RectI &view, 200 const MatrixF &world, 201 const MatrixF &projection, 202 F32 far, 203 F32 near); 204 205 /// Clip @a inFrustum by the given polygon. 206 /// 207 /// @note The input polygon is limited to 58 vertices. 208 /// 209 /// @param points Polygon vertices. 210 /// @param numPoints Number of vertices in @a points. 211 /// @param viewport Screen viewport. Note that this corresponds to the root frustum and not necessarily to @a inFrustum. 212 /// @param world World->view transform. 213 /// @param projection Projection matrix. 214 /// @param inFrustum Frustum to clip. 215 /// @param rootFrustum Frustum corresponding to @a viewport. 216 /// @param outFrustum Resulting clipped frustum. 217 /// 218 /// @return True if the frustum was successfully clipped and @a outFrustum is valid, false otherwise 219 /// (if, for example, the input polygon is completely outside @a inFrustum). 220 bool clipFrustumByPolygon( const Point3F* points, 221 U32 numPoints, 222 const RectI& viewport, 223 const MatrixF& world, 224 const MatrixF& projection, 225 const Frustum& inFrustum, 226 const Frustum& rootFrustum, 227 Frustum& outFrustum ); 228 229 /// Returns true if the test point is within the polygon. 230 /// @param verts The array of points which forms the polygon. 231 /// @param vertCount The number of points in the polygon. 232 /// @param testPt The point to test. 233 bool pointInPolygon( const Point2F *verts, U32 vertCount, const Point2F &testPt ); 234 235 /// Remove all edges from the given polygon that have a total length shorter 236 /// than @a epsilon. 237 /// 238 U32 removeShortPolygonEdges( const Point3F* verts, U32 vertCount, F32 epsilon ); 239 240 /// Calculates the shortest line segment between two lines. 241 /// 242 /// @param outSegment The result where .p0 is the point on line0 and .p1 is the point on line1. 243 /// 244 void mShortestSegmentBetweenLines( const Line &line0, const Line &line1, LineSegment *outSegment ); 245 246 /// Returns the greatest common divisor of two positive integers. 247 U32 greatestCommonDivisor( U32 u, U32 v ); 248 249 /// Returns the barycentric coordinates and time of intersection between 250 /// a line segment and a triangle. 251 /// 252 /// @param p1 The first point of the line segment. 253 /// @param p2 The second point of the line segment. 254 /// @param t1 The first point of the triangle. 255 /// @param t2 The second point of the triangle. 256 /// @param t2 The third point of the triangle. 257 /// @param outUVW The optional output barycentric coords. 258 /// @param outT The optional output time of intersection. 259 /// 260 /// @return Returns true if a collision occurs. 261 /// 262 bool mLineTriangleCollide( const Point3F &p1, const Point3F &p2, 263 const Point3F &t1, const Point3F &t2, const Point3F &t3, 264 Point3F *outUVW = NULL, 265 F32 *outT = NULL ); 266 267 /// Returns the uv coords and time of intersection between 268 /// a ray and a quad. 269 /// 270 /// @param quad The quad. 271 /// @param ray The ray. 272 /// @param outUV The optional output UV coords of the intersection. 273 /// @param outT The optional output time of intersection. 274 /// 275 /// @return Returns true if a collision occurs. 276 /// 277 bool mRayQuadCollide( const Quad &quad, 278 const Ray &ray, 279 Point2F *outUV = NULL, 280 F32 *outT = NULL ); 281 282 /// Returns the distance between a point and triangle 'abc'. 283 F32 mTriangleDistance( const Point3F &a, const Point3F &b, const Point3F &c, const Point3F &p, IntersectInfo* info=<a href="/coding/file/types_8lint_8h/#types_8lint_8h_1a070d2ce7b6bb7e5c05602aa8c308d0c4">NULL</a> ); 284 285 /// Returns the normal of the passed triangle 'abc'. 286 /// 287 /// If we assume counter-clockwise triangle culling, normal will point 288 /// out from the 'solid' side of the triangle. 289 /// 290 Point3F mTriangleNormal( const Point3F &a, const Point3F &b, const Point3F &c ); 291 292 /// Returns the closest point on the segment defined by 293 /// points a, b to the point p. 294 Point3F mClosestPointOnSegment( const Point3F &a, 295 const Point3F &b, 296 const Point3F &p ); 297 298 /// Sort the passed verts ( Point3F ) in a clockwise or counter-clockwise winding order. 299 /// Verts must be co-planar and non-collinear. 300 /// 301 /// @param quadMat Transform matrix from vert space to quad space. 302 /// @param clockwise Sort clockwise or counter-clockwise 303 /// @param verts Array of Point3F verts. 304 /// @param vertMap Output - Array of vert element ids sorted by winding order. 305 /// @param count Element count of the verts and vertMap arrays which must be allocated prior to this call. 306 /// 307 void sortQuadWindingOrder( const MatrixF &quadMat, bool clockwise, const Point3F *verts, U32 *vertMap, U32 count ); 308 309 /// Same as above except we assume that the passed verts ( Point3F ) are already 310 /// transformed into 'quad space'. If this was done correctly and the points 311 /// are coplanar this means their z components will all be zero. 312 void sortQuadWindingOrder( bool clockwise, const Point3F *verts, U32 *vertMap, U32 count ); 313 314 /// 315 /// WORK IN PROGRESS 316 /// 317 /// Creates an orthonormal basis matrix from one, two, or three unit length 318 /// input vectors. If more than one input vector is provided they must be 319 /// mutually perpendicular. 320 /// 321 /// @param rvec Optional unit length right vector. 322 /// @param fvec Optional unit length forward vector. 323 /// @param uvec Optional unit length up vector. 324 /// @param pos Optional position to initialize the matrix. 325 /// @param outMat The output matrix which must be initialized prior to the call. 326 /// 327 void buildMatrix( const VectorF *rvec, const VectorF *fvec, const VectorF *uvec, const VectorF *pos, MatrixF *outMat ); 328 329 /// 330 bool reduceFrustum( const Frustum& frustum, const RectI& viewport, const RectF& area, Frustum& outFrustum ); 331 332 /// Build the frustum near plane dimensions from the parameters. 333 void makeFrustum( F32 *outLeft, 334 F32 *outRight, 335 F32 *outTop, 336 F32 *outBottom, 337 F32 fovYInRadians, 338 F32 aspectRatio, 339 F32 nearPlane ); 340 341 void makeFovPortFrustum( Frustum *outFrustum, 342 bool isOrtho, 343 F32 nearDist, 344 F32 farDist, 345 const FovPort &inPort, 346 const MatrixF &transform = MatrixF(1) ); 347 348 /// Build a GFX projection matrix from the frustum parameters 349 /// including the optional rotation required by GFX. 350 void makeProjection( MatrixF *outMatrix, 351 F32 fovYInRadians, 352 F32 aspectRatio, 353 F32 nearPlane, 354 F32 farPlane, 355 bool gfxRotate ); 356 357 /// Build a projection matrix from the frustum near plane dimensions 358 /// including the optional rotation required by GFX. 359 void makeProjection( MatrixF *outMatrix, 360 F32 left, 361 F32 right, 362 F32 top, 363 F32 bottom, 364 F32 nearPlane, 365 F32 farPlane, 366 bool gfxRotate ); 367 368 /// Build an orthographic projection matrix from the frustum near 369 /// plane dimensions including the optional rotation required by GFX. 370 void makeOrthoProjection( MatrixF *outMatrix, 371 F32 left, 372 F32 right, 373 F32 top, 374 F32 bottom, 375 F32 nearPlane, 376 F32 farPlane, 377 bool gfxRotate ); 378 379 /// Find the intersection of the line going from @a edgeA to @a edgeB with the triangle 380 /// given by @a faceA, @a faceB, and @a faceC. 381 /// @param edgeA Starting point of edge. 382 /// @param edgeB End point of edge. 383 /// @param faceA First vertex of triangle. 384 /// @param faceB Second vertex of triangle. 385 /// @param faceC Third vertex of triangle. 386 /// @param intersection If there is an intersection, the point of intersection on the triangle's 387 /// face is stored here. 388 /// @param True if there is an intersection, false otherwise. 389 bool edgeFaceIntersect( const Point3F &edgeA, const Point3F &edgeB, 390 const Point3F &faceA, const Point3F &faceB, const Point3F &faceC, const Point3F &faceD, Point3F *intersection ); 391 392 /// Find out whether the given polygon is planar. 393 /// @param vertices Array of vertices of the polygon. 394 /// @param numVertices Number of vertices in @a vertices. 395 /// @return True if the polygon is planar, false otherwise. 396 bool isPlanarPolygon( const Point3F* vertices, U32 numVertices ); 397 398 /// Find out whether the given polygon is convex. 399 /// @param vertices Array of vertices of the polygon. 400 /// @param numVertices Number of vertices in @a vertices. 401 /// @return True if the polygon is convex, false otherwise. 402 bool isConvexPolygon( const Point3F* vertices, U32 numVertices ); 403 404 /// Extrude the given polygon along the given direction. 405 U32 extrudePolygonEdges( const Point3F* vertices, U32 numVertices, const Point3F& direction, PlaneF* outPlanes ); 406 407 /// Extrude the edges of the given polygon away from @a fromPoint by constructing a set of planes 408 /// that each go through @a fromPoint and a pair of vertices. 409 /// 410 /// The resulting planes are in the same order as the vertices and have their normals facing *inwards*, 411 /// i.e. the resulting volume will enclose the polygon's interior space. 412 /// 413 /// @param vertices Vertices of the polygon in CCW or CW order (both are acceptable). 414 /// @param numVertices Number of vertices in @a vertices. 415 /// @param fromPoint 416 /// @param outPlanes Array in which the resulting planes are stored. Must have room for at least as many 417 /// planes are there are edges in the polygon. 418 /// 419 /// @return 420 /// 421 /// @note The input polygon does not necessarily need to be planar but it must be convex. 422 U32 extrudePolygonEdgesFromPoint( const Point3F* vertices, U32 numVertices, 423 const Point3F& fromPoint, 424 PlaneF* outPlanes ); 425 426 //void findFarthestPoint( const Point3F* points, U32 numPoints, const Point3F& fromPoint, ) 427 428 /// Build a convex hull from a cloud of 2D points, first and last hull point are the same. 429 void mBuildHull2D(const Vector<Point2F> inPoints, Vector<Point2F> &hullPoints); 430 431} // namespace MathUtils 432 433#endif // _MATHUTILS_H_ 434