實際游戲開發中，無論是游戲物理的計算，還是游戲邏輯開發，常常會用到平面、射線、球體、包圍盒等幾何圖元，我們實作了幾個常用的幾何圖元類，
第一個我們要介紹的是射線，射線包含了頂點和方向，與數學上的射線不同，我們用到的射線可以有距離限制，射線的引數化表示為p = o + td，p為射線上的點，o為射線的起始位置，d是射線的方向，t是表示射線長度的標量，射線類Ray代碼如下：
1 template <typename T> 2 class Ray 3 { 4 public: 5 Ray(); 6 Ray(const Vector3<T> &origin, const Vector3<T> &direction); 7 8 inline const Vector3<T> &Origin() const { return _Origin; } 9 inline const Vector3<T> &Direction() const { return _Direction; } 10 inline Vector3<T> &Origin() { return _Origin; } 11 inline Vector3<T> &Direction() { return _Direction; } 12 13 template <typename T1> 14 friend ostream &operator<<(ostream &out, const Ray<T1> &ray); 15 private: 16 Vector3<T> _Origin; 17 Vector3<T> _Direction; 18 }; 19 20 template <typename T> 21 Ray<T>::Ray() 22 :_Origin(Vector3<T>(0, 0, 0)), _Direction(Vector3<T>(0, 0, -1)) 23 { 24 } 25 26 template <typename T> 27 Ray<T>::Ray(const Vector3<T> &origin, const Vector3<T> &direction) 28 :_Origin(origin), _Direction(direction) 29 { 30 } 31 32 template <typename T> 33 ostream &operator<<(ostream &out, const Ray<T> &ray) 34 { 35 return out << ray._Origin << ", " << ray._Direction; 36 } 37 38 typedef Ray<double> Rayd; 39 typedef Ray<float> Rayf;
這里只是簡單的將位置和方向進行封裝，注意在建構式里，我們僅僅是將傳入的方向直接賦值而沒有進行正規化，如果傳入是非單位向量，則射線是有長度的，因此可以根據實際需求傳值，通常射線會與其它各種圖元進行相交檢測，我們將這些檢測放到各自的圖元類內，
下一個最為常用的圖元是平面，引數化的平面方程為pn = d，其中p為平面上任意一點，n為平面的單位法向量，d是平面上任意一點到法線的投影距離，即平面到原點的距離，
有了平面的定義，我們就可以定義平面類Plane：
1 template <typename T> 2 class Plane 3 { 4 public: 5 Plane(const Vector3<T> &normal, T distance); 6 Plane(const Vector3<T> &normal, const Vector3<T> &point); 7 8 T GetSignedDistance(const Vector3<T> &point) const; 9 10 bool Intersect(const Ray<T> &ray, float *maxDistance = nullptr, Vector3<T> *intersection = nullptr) const; 11 bool Intersect(const Sphere<T> &sphere) const; 12 13 template <typename T1> 14 friend ostream &operator<<(ostream &out, const Plane<T1> &plane); 15 16 private: 17 Vector3<T> _Normal; 18 T _Distance; 19 }; 20 21 template <typename T> 22 Plane<T>::Plane(const Vector3<T> &normal, T distance) 23 : _Normal(normal), _Distance(distance) 24 { 25 } 26 template <typename T> 27 Plane<T>::Plane(const Vector3<T> &normal, const Vector3<T> &point) 28 : _Normal(normal), _Distance(point.DotProduct(normal)) 29 { 30 } 31 32 template <typename T> 33 T Plane<T>::GetSignedDistance(const Vector3<T> &point) const 34 { 35 /** 36 * p + an = q; 37 * (p + an)*n = q * n; 38 * p * n = (an) * n = q * n; 39 * d + a = q * n; 40 * a = q * n - d 41 */ 42 return point.DotProduct(_Normal) - _Distance; 43 } 44 45 template <typename T> 46 bool Plane<T>::Intersect(const Ray<T> &ray, float *maxDistance, Vector3<T> *intersection) const 47 { 48 const Vector3<T> &rayOrigin = ray.Origin(); 49 const Vector3<T> &rayDir = ray.Direction(); 50 T toPlaneDis = GetSignedDistance(rayOrigin); 51 if (toPlaneDis < 0 /*只和正平面相交*/ || (maxDistance && *maxDistance < toPlaneDis)) 52 return false; 53 54 T angleCos = -rayDir.DotProduct(_Normal); 55 //射線方向與平面平行 56 if (FLOAT_EQUAL(angleCos, 0)) 57 return false; 58 59 if (intersection) 60 { 61 *intersection = rayOrigin + rayDir * (toPlaneDis / angleCos); 62 } 63 64 return true; 65 } 66 67 template <typename T> 68 bool Plane<T>::Intersect(const Sphere<T> &sphere) const 69 { 70 T distance = GetSignedDistance(sphere.Center()); 71 return std::abs(distance) < sphere.Radius; 72 } 73 74 template <typename T1> 75 ostream &operator<<(ostream &out, const Plane<T1> &plane) 76 { 77 out << plane._Normal << ", " << plane._Distance; 78 return out; 79 } 80 81 typedef Plane<double> Planed; 82 typedef Plane<float> Planef;
Plane類中GetSignedDistance計算了點到平面的有符號距離，如下圖點q的位置為q = p + an，n為平面的法向量，p為q在平面上的最近點，則a為q到平面的距離，等式兩邊同時與n點乘，即qn = pn + ann,根據平面的定義我們知道pn = d，則a = qn - d，這就是計算點到平面距離的公式，我們也可以這樣來理解這個公式，qn為點q在n方向上的投影距離減去平面到原點距離d即是點到平面的有符號距離，
平面的Intersect函式計算了與射線、球體的相交檢測，射線與平面的相交檢測函式中，射線只能和平面正方向相交，首先計算了射線位置到平面的距離，如果距離為負，則射線點在平面的負半面，不能和平面正面相交，然后利用三角函式計算出射線原點到相交點距離，代入到射線方程中，即可求得射線與平面的相交點，平面和球的相交更為簡單，Sphere類通過球所在的位置和半徑來定義一個球體，
1 template <typename T> 2 class Sphere 3 { 4 public: 5 Sphere(const Vector3<T> ¢er, T radius); 6 7 inline const Vector3<T> &Center() const { return _Center; } 8 inline const T &Radius() const { return _Radius; } 9 inline Vector3<T> &Center() { return _Center; } 10 inline T &Radius() { return _Radius; } 11 bool Intersect(const Ray<T> &ray, T *maxDistance = nullptr, Vector3<T> *intersection = nullptr) const; 12 13 template <typename T1> 14 friend ostream &operator<<(ostream &out, const Sphere<T1> &sphere); 15 16 private: 17 Vector3<T> _Center; 18 T _Radius; 19 float a; 20 }; 21 22 template <typename T> 23 Sphere<T>::Sphere(const Vector3<T> ¢er, T radius) 24 : _Center(center), _Radius(radius) 25 { 26 } 27 28 template <typename T> 29 bool Sphere<T>::Intersect(const Ray<T> &ray, T *maxDistance, Vector3<T> *intersection) const 30 { 31 Vector3<T> rayDir = ray.Direction(); 32 rayDir.Normalize(); 33 Vector3<T> ray2Center = _Center - ray.Origin(); 34 T a = ray2Center.DotProduct(rayDir); 35 T e2 = ray2Center.SqrLength(); 36 T a2 = a * a; 37 T radius2 = _Radius * _Radius; 38 T b2 = e2 - a2; 39 40 if (b2 <= radius2) 41 { 42 if (maxDistance || intersection) 43 { 44 //射線點在球內，計算射出時的相交點 45 T t = e2 < radius2 ? a + sqrt(radius2 - b2) : a - sqrt(radius2 - b2); 46 if (maxDistance && *maxDistance < t) 47 return false; 48 49 if (intersection) 50 *intersection = ray.Origin() + ray.Direction() * t; 51 } 52 return true; 53 } 54 55 return false; 56 } 57 58 template <typename T> 59 ostream &operator<<(ostream &out, const Sphere<T> &sphere) 60 { 61 return out << sphere._Center << ", " << sphere._Radius; 62 } 63 64 typedef Sphere<double> Sphered; 65 typedef Sphere<float> Spheref;
判斷平面和球體相交，只需要計算球中心點到平面的距離（非有符號距離，因為即在平面負方向也會相交）與球體半徑的關系即可，同樣球體也定義了與射線的相交檢測函式如下圖，分別是射線原點在球外（上）和球內（下）的情況，這里要計算的是點b的位置，
從圖中可以看到，射線原點到點b的距離等于射線原點到球心的向量在射線方向上的投影距離加（p在球內）或減(p在球外)ab之間的距離，這里ob的距離為球的半徑，通過三角函式即求得ab距離的大小，
另一個常用的圖元是AABB(Axis Aligned Bounding Box，軸對齊包圍盒)，它的每一面都平行于坐標平面，其實作非常簡單，只需要指定最小點和最大點即可表示這個包圍盒，
1 template <typename T> 2 class AABBox 3 { 4 public: 5 AABBox(const Vector3<T> &min, const Vector3<T> &max); 6 void Union(const Vector3<T> &point); 7 void Union(const AABBox<T> &box); 8 inline Vector3<T> Size() const; 9 inline Vector3<T> Center() const; 10 Vector3<T> ClosestPointTo(const Vector3<T> &point) const; 11 bool Contains(const Vector3<T> &point) const; 12 bool Intersect(const Sphere<T> &sphere) const; 13 bool Intersect(const Ray<T> &ray, float *maxDistance = nullptr, Vector3<T> *intersection = nullptr) const; 14 bool Intersect(const AABBox<T> &box, AABBox<T> *intersection = nullptr) const; 15 16 template <typename T1> 17 friend ostream &operator<<(ostream &out, const AABBox<T1> &v); 18 private: 19 Vector3<T> _Min; 20 Vector3<T> _Max; 21 }; 22 23 template <typename T> 24 AABBox<T>::AABBox(const Vector3<T> &min, const Vector3<T> &max) 25 { 26 //保證傳值不正確時得到合法的aabbox 27 for (int i = 0; i < 3; ++i) 28 { 29 _Min[i] = MIN(min[i], max[i]); 30 _Max[i] = MAX(min[i], max[i]); 31 } 32 } 33 34 template <typename T> 35 void AABBox<T>::Union(const Vector3<T> &point) 36 { 37 for (int i = 0; i < 3; ++i) 38 { 39 _Min[i] = MIN(_Min[i], point[i]); 40 _Max[i] = MAX(_Max[i], point[i]); 41 } 42 } 43 44 template <typename T> 45 void AABBox<T>::Union(const AABBox<T> &box) 46 { 47 for (int i = 0; i < 3; ++i) 48 { 49 _Min[i] = MIN(_Min[i], box._Min[i]); 50 _Max[i] = MAX(_Max[i], box._Max[i]); 51 } 52 } 53 54 template <typename T> 55 Vector3<T> AABBox<T>::Size() const 56 { 57 return _Max - _Min; 58 } 59 60 template <typename T> 61 Vector3<T> AABBox<T>::Center() const 62 { 63 return (_Max + _Min) * (T)0.5; 64 } 65 66 template <typename T> 67 Vector3<T> AABBox<T>::ClosestPointTo(const Vector3<T> &point) const 68 { 69 Vector3<T> result; 70 for (int i = 0; i < 3; ++i) 71 { 72 if (point[i] < _Min[i]) 73 result[i] = _Min[i]; 74 else if (point[i] > _Max[i]) 75 result[i] = _Max[i]; 76 else 77 result[i] = point[i]; 78 } 79 return result; 80 } 81 82 template <typename T> 83 bool AABBox<T>::Contains(const Vector3<T> &point) const 84 { 85 return point.x >= _Min.x && point.y >= _Min.y && point.z >= _Min.z && point.x <= _Max.x && point.y <= _Max.y && point.z <= _Max.z; 86 } 87 88 template <typename T> 89 bool AABBox<T>::Intersect(const Sphere<T> &sphere) const 90 { 91 const Vector3<T> &sphereCenter = sphere.Center(); 92 Vector3<T> closestPoint = ClosestPointTo(sphereCenter); 93 return (closestPoint - sphereCenter).SqrLength() < sphere.Radius(); 94 } 95 96 template <typename T> 97 bool AABBox<T>::Intersect(const Ray<T> &ray, float *maxDistance, Vector3<T> *intersection) const 98 { 99 Plane<T> planes[6] = {Plane<T>(-Vector3<T>::right, _Min), Plane<T>(-Vector3<T>::up, _Min), Plane<T>(-Vector3<T>::forward, _Min), 100 Plane<T>(Vector3<T>::right, _Max), Plane<T>(Vector3<T>::up, _Max), Plane<T>(Vector3<T>::forward, _Max)}; 101 102 for (int i = 0; i < 6; ++i) 103 { 104 Vector3<T> intersectPoint; 105 if (planes[i].Intersect(ray, maxDistance, &intersectPoint)) 106 { 107 bool contains = Contains(intersectPoint); 108 if (contains) 109 { 110 if (intersection) *intersection = intersectPoint; 111 return true; 112 } 113 } 114 } 115 116 return false; 117 } 118 119 template <typename T> 120 bool AABBox<T>::Intersect(const AABBox<T> &box, AABBox *intersection) const 121 { 122 for (int i = 0; i < 3; ++i) 123 { 124 if (_Min[i] > box._Max[i]) 125 return false; 126 } 127 128 if (intersection) 129 { 130 for (int i = 0; i < 3; ++i) 131 { 132 intersection->_Min[i] = MAX(_Min[i], box._Min[i]); 133 intersection->_Max[i] = MIN(_Max[i], box._Max[i]); 134 } 135 } 136 137 return true; 138 } 139 140 template <typename T> 141 ostream &operator<<(ostream &out, const AABBox<T> &v) 142 { 143 out << v._Min << ", " << v._Max; 144 return out; 145 }
上面代碼中Union方法可以點或另一個AABB合并到當前AABB，當計算一個模型的AABB時，通過Union模型的每一個頂點，可以最終模型的AABB；ClosestPointTo是通過將點推向AABB的各平面計算出點到包含上最近的位置；Contains計算點是否在包含盒內；Intersect的幾的個函式是用來計算與球、射線 、其它包圍盒的相交性，AABB與球的相交檢測是通過計算球心到AABB上最近的點的距離和球的半徑來判斷的，射線與AABB的相交檢測首先計算射線與AABB的哪一個正平面相交，然后判斷相交點是否在包圍盒上，兩個AABB之間的相交檢測只需要判斷最小點和最大點之間的關系就可以了，同時，將相交部分生成一個新的AABB，
最后在我們還會經常用到三角形，Triangle類代碼如下：
/** * _V0 * /\ * e2/ \e1 * / \ * _V1/______\ _V2 * e0 **/ template <typename T> class Triangle { public: Triangle(const Vector3<T> &v0, const Vector3<T> &v1, const Vector3<T> v2); bool Contains(const Vector3<T> &point) const; bool BarycentricCoord(const Vector3<T> &point, Vector3<T> &out) const; bool Intersect(const Ray<T> &ray, float *maxDistance = nullptr, Vector3<T> *intersection = nullptr) const; Vector3<T> &operator[](int i); const Vector3<T> &operator[](int i) const; template <typename T1> friend ostream &operator<<(ostream &out, const Triangle<T1> &tri); private: union { struct { Vector3<T> _V0, _V1, _V2; }; Vector3<T> _V[3]; }; }; template <typename T> Triangle<T>::Triangle(const Vector3<T> &v0, const Vector3<T> &v1, const Vector3<T> v2) : _V0(v0), _V1(v1), _V2(v2) { } template <typename T> bool Triangle<T>::BarycentricCoord(const Vector3<T> &point, Vector3<T> &out) const { Vector3<T> e0 = _V2 - _V1; Vector3<T> e1 = _V0 - _V2; Vector3<T> e2 = _V1 - _V0; Vector3<T> v0p = point - _V0; Vector3<T> v1p = point - _V1; Vector3<T> v2p = point - _V2; Vector3<T> dir = e2.CrossProduct(-e1); T area012_2 = e2.CrossProduct(-e1).DotProduct(dir); // 退化三角形，面積為0 if (FLOAT_EQUAL(area012_2, 0)) return false; //點在三角形外部時，至少有一個重心坐標值為負， T areaP01_2 = e2.CrossProduct(v0p).DotProduct(dir); T areaP12_2 = e0.CrossProduct(v1p).DotProduct(dir); T areaP20_2 = e1.CrossProduct(v2p).DotProduct(dir); T area012_2_inv = (T)1 / area012_2; out.x = areaP01_2 * area012_2_inv; out.y = areaP12_2 * area012_2_inv; out.z = areaP20_2 * area012_2_inv; return true; } template <typename T> bool Triangle<T>::Contains(const Vector3<T> &point) const { Vector3<T> e0 = _V2 - _V1; Vector3<T> e1 = _V0 - _V2; Vector3<T> e2 = _V1 - _V0; T area012_2 = e2.CrossProduct(-e1).Length(); // 退化三角形，面積為0 if (FLOAT_EQUAL(area012_2, 0)) return false; Vector3<T> v0p = point - _V0; Vector3<T> v1p = point - _V1; Vector3<T> v2p = point - _V2; T areaP01_2 = e2.CrossProduct(v0p).Length(); T areaP12_2 = e0.CrossProduct(v1p).Length(); T areaP20_2 = e1.CrossProduct(v2p).Length(); return FLOAT_EQUAL(areaP01_2 + areaP12_2 + areaP20_2 - area012_2, 0); } template <typename T> bool Triangle<T>::Intersect(const Ray<T> &ray, float *maxDistance, Vector3<T> *intersection) const { Vector3<T> e1 = _V2 - _V0; Vector3<T> e2 = _V1 - _V0; Vector3<T> normal = e2.CrossProduct(e1); Plane<T> plane(normal, _V0); Vector3<T> intersectionPoint; bool intersetWithPlane = plane.Intersect(ray, maxDistance, &intersectionPoint); if (intersetWithPlane) { bool result = Contains(intersectionPoint); if (result && intersection) { *intersection = intersectionPoint; } return result; } return false; } template <typename T> Vector3<T> &Triangle<T>::operator[](int i) { return _V[i]; } template <typename T> const Vector3<T> &Triangle<T>::operator[](int i) const { return _V[i]; } template <typename T> ostream &operator<<(ostream &out, const Triangle<T> &tri) { return out << tri._V0 << ", " << tri._V1 << ", " << tri._V2; } typedef Triangle<double> Triangled; typedef Triangle<float> Trianglef; }
這里主要定義了三個函式，分別用來計算點是否在三角形上（Contains）、求點在三角形上的重心坐標（BarycentricCoord）和射線之間的相交檢測（Intersect），Contains函式的原理是三角形內任意一點到三個頂點所組成的子三角形面積和等于原三角形的面積，
BarycentricCoord函式用到了子三角形的面積與原角形面積的比來計算重心坐標，三角形平面內任意一點可以用重心坐標來表示，即p = b0v0 + b1v1 + b2v2，如果點不在三角形所在的平面，計算出的為點在三角形所在平面投影點的重心坐標，
以上就是常用的一些基本圖元，游戲中還會用到OBB、圓柱、膠囊體內幾何圖元，這些內容會在將來游戲物理章節用到時再進行補充，
本文來自博客園，作者：毅安，轉載請注明原文鏈接：https://www.cnblogs.com/primarycode/p/16514246.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/500200.html
標籤：其他