【遊戲框架系列】用C++畫光（二）——矩形

在上篇文章的基礎上，做了許多調整，修復了許多BUG。在解決bug的過程中，我逐漸領悟到一個要領：枯燥地一步步調試太痛苦了，找不到問題的根源！所以我選擇將中間結果打到圖片上。如：

（注意，裡面的點是我隨便點的，有互動了吧）

這就非常爽了！

本文分兩個部分，一個是交並差的實現，一個是矩形的實現。

基本數據結構

// 點信息nstruct Geo2DPointn{n Geo2DPoint();n Geo2DPoint(float distance, const vector2& position, const vector2& normal);nn const Geo2DPoint& operator = (const Geo2DPoint& r);nn float distance{ FLT_MAX }; // 光線起點到交點距離n vector2 position; // 交點位置n vector2 normal; // 交點法向量（指向物體外部）n};nn// 相交測試nstruct Geo2DResultn{n Geo2DResult();n Geo2DResult(const Geo2DShape* body, bool inside, Geo2DPoint min_pt, Geo2DPoint max_pt);nn Geo2DResult(const Geo2DResult& r);n const Geo2DResult& operator = (const Geo2DResult& r);nn const Geo2DShape* body{ nullptr };n bool inside{ false };n Geo2DPoint min_pt, max_pt;//交點較小解和較大解的信息n};n

每次發出一道光線，需要計算：

1. 如果光線與某物體相交，返回該物體指針body
2. 光線起點是否在物體內部inside
3. 光線與物體最近的交點信息，包括交點坐標、光線起點到交點的距離、交點法線，如果此時光線起點位於物體內部，那麼交點可能不是最近的（因為這裡的最近指的是解二次方程時的較小根）
4. 光線與物體最遠的交點信息

說明：

• 即使光線與物體未有交點，還是要計算出所有交點信息
• 不只是最近的交點信息很重要，最遠的交點同樣重要

原因：

• 上面的數據結構是為了解決圖形間交並差的問題！！
• 如兩圓相交，ABAB的光線路徑，那麼光線與物體相交的兩個點不同時是光線離A、B的最近點，所以最遠點的信息是必須要計算的
• 為什麼要用inside？同樣是與A、B相交，光線起點在物體內部和在物體外部所產生的效果是不一樣的！因為我們還要計演算法線呢！
• ……因此促成了現在的數據結構

圖形間的交、並、差

上一篇文章中，雖然實現了交並差，但是還不完善：交點信息和法向量沒有計算正確，因此做了調整（並集沒有調整）：

【計算交集】

https://github.com/bajdcc/GameFramework/blob/master/CCGameFramework/base/pe2d/Geometries2D.cpp#L70

if (op == t_intersect)n{n const auto r1 = obj1->sample(ori, dst);n if (r1.body)n {n const auto r2 = obj2->sample(ori, dst);n if (r2.body)n {n const auto rd = ((r1.inside ? 1 : 0) << 1) | (r2.inside ? 1 : 0);n switch (rd)n {n case 0: // not(A or B)n if (r1.min_pt.distance < r2.min_pt.distance)n {n if (r2.min_pt.distance > r1.max_pt.distance) // AABBn break;n if (r2.max_pt.distance < r1.max_pt.distance) // ABBAn return r2;n auto r(r2); // ABABn r.max_pt = r1.max_pt;n return r;nn }n if (r2.min_pt.distance < r1.min_pt.distance)n {n if (r1.min_pt.distance > r2.max_pt.distance) // BBAAn break;n if (r1.max_pt.distance < r2.max_pt.distance) // BAABn return r1;n auto r(r1); // BABAn r.max_pt = r2.max_pt;n return r;n }n break;n case 1: // Bn if (r1.min_pt.distance < r2.max_pt.distance)n {n if (r1.max_pt.distance > r2.max_pt.distance) // ABAn {n auto r(r1);n r.max_pt = r2.max_pt;n return r;n }n else // AABn {n auto r(r1);n r.max_pt = r1.max_pt;n return r;n }n }n break;n case 2: // An if (r2.min_pt.distance < r1.max_pt.distance)n {n if (r2.max_pt.distance > r1.max_pt.distance) // BABn {n auto r(r2);n r.max_pt = r1.max_pt;n return r;n }n else // BBAn {n auto r(r2);n r.max_pt = r2.max_pt;n return r;n }n }n break;n case 3: // A and Bn if (r1.min_pt.distance > r2.min_pt.distance)n {n if (r1.max_pt.distance > r2.max_pt.distance) // BAn {n auto r(r2);n r.min_pt = r1.min_pt;n return r;n }n else // ABn {n return r1;n }n }n elsen {n if (r2.max_pt.distance > r1.max_pt.distance) // ABn {n auto r(r1);n r.min_pt = r2.min_pt;n return r;n }n else // ABn {n return r2;n }n }n default:n break;n }n }n }n}n

【計算差集】

這裡注意的是某些情況下需要做法向量翻轉

https://github.com/bajdcc/GameFramework/blob/master/CCGameFramework/base/pe2d/Geometries2D.cpp#L171

if (op == t_subtract)n{n const auto r1 = obj1->sample(ori, dst);n const auto r2 = obj2->sample(ori, dst);n const auto rd = ((r1.body ? 1 : 0) << 1) | (r2.body ? 1 : 0);n switch (rd)n {n case 0: // not(A or B)n break;n case 1: // Bn break;n case 2: // An if (r1.inside) // AAn {n if (r2.max_pt.distance == FLT_MAX)n return r1;n if (r1.min_pt.distance > r2.max_pt.distance)n return r1;n auto r(r1);n r.min_pt = r2.max_pt;n r.min_pt.normal = -r.min_pt.normal;n return r;n }n elsen return r1;n case 3: // A and Bn if (r1.inside && r2.inside)n {n if (r2.max_pt.distance < r1.max_pt.distance) // BAn {n auto r(r1);n r.min_pt = r2.max_pt;n r.min_pt.normal = -r.min_pt.normal;n r.inside = false;n return r;n }n else // ABn {n break;n }n }n else if (r2.inside)n {n if (r1.max_pt.distance > r2.max_pt.distance)n {n if (r2.max_pt.distance > r1.min_pt.distance) // ABAn {n auto r(r1);n r.min_pt = r2.max_pt;n r.min_pt.normal = -r.min_pt.normal;n r.inside = false;n return r;n }n else // BAAn {n return r1;n }n }n else // AABn break;n }n else if (r1.inside) // BABn {n auto r(r1);n r.max_pt = r2.min_pt;n return r;n }n elsen {n if (r1.min_pt.distance < r2.min_pt.distance)n {n if (r2.min_pt.distance > r1.max_pt.distance) // AABBn return r1;n if (r2.max_pt.distance < r1.max_pt.distance) // ABBAn return r1;n auto r(r1); // ABABn r.max_pt = r2.min_pt;n r.max_pt.normal = -r.max_pt.normal;n return r;n }n elsen {n if (r1.min_pt.distance > r2.max_pt.distance) // BBAAn return r1;n if (r1.max_pt.distance < r2.max_pt.distance) // BAABn break;n auto r(r1); // BABAn r.min_pt = r2.max_pt;n r.min_pt.normal = -r.min_pt.normal;n return r;n }n }n default:n break;n }n}n

想知道代碼為什麼這麼寫，需要拿張紙比劃一下（逃

為什麼這麼多if？？？因為我可以調試啊（最開始兩張圖），當什麼問題都解決完的時候，代碼就變這麼長了。

矩形的實現

一開始圓的實現非常簡單，因為算個距離很快，法向量就更簡單，而矩形不同。

【矩形】

static int SignBit(const float& a)//返回a的符號n{n if (fabs(a) < EPSILON)n {n return 0;//接近0n }n return a > 0 ? 1 : -1;n}nnstatic bool IntersectWithLineAB(const vector2& ori, const vector2& dir, const vector2& p1, const vector2& p2, float& t, vector2& p)n{n//利用直線的參數方程計算一直線與另一直線的交點n const auto tAB1 = dir.y * (p2.x - p1.x) - dir.x * (p2.y - p1.y);//計算平行n if (fabs(tAB1) > EPSILON)//不平行必有交點n {n t = ((ori.x - p1.x) * (p2.y - p1.y) - (ori.y - p1.y) * (p2.x - p1.x)) / tAB1;//計算距離n p = ori + dir * t;//計算交點n return (SignBit(p1.x - p.x) == SignBit(p.x - p2.x)) && (SignBit(p1.y - p.y) == SignBit(p.y - p2.y));//交點是否在p1p2間n }n return false;//兩直線平行，無交點n}nnGeo2DResult Geo2DBox::sample(vector2 ori, vector2 dir) constn{n const auto _A = vector2(costheta * -s.x + sintheta * -s.y, costheta * -s.y - sintheta * -s.x);n const auto _B = vector2(costheta * s.x + sintheta * -s.y, costheta * -s.y - sintheta * s.x);n const auto A = center + _A;n const auto B = center + _B;n const auto C = center - _A;n const auto D = center - _B;n const vector2 pts[4] = { A,B,C,D };nn static int m[4][2] = { {0,1},{1,2},{2,3},{3,0} };n float t[2];//保存兩交點的距離n vector2 p[2];//保存兩交點的位置n int ids[2];//保存與矩形哪一條邊相交n int cnt = 0;n for (int i = 0; i < 4 && cnt < 2; i++)n {n if (IntersectWithLineAB(ori, dir, pts[m[i][0]], pts[m[i][1]], t[cnt], p[cnt]))n {n ids[cnt++] = i;n }n }n if (cnt == 2)//有兩個交點n {n const auto td = ((t[0] >= 0 ? 1 : 0) << 1) | (t[1] >= 0 ? 1 : 0);n switch (td)n {n case 0: // 雙反，無交點，在外n break;n case 1: // t[1]，有交點，在內n//只與t1相交，那麼t0肯定是另一交點，p0肯定為負n return Geo2DResult(this, false,n Geo2DPoint(t[0], p[0], Normalize(pts[m[ids[0]][0]] + pts[m[ids[0]][1]] - center - center)),n Geo2DPoint(t[1], p[1], Normalize(pts[m[ids[1]][0]] + pts[m[ids[1]][1]] - center - center)));n case 2: // t[0]，有交點，在內n//只與t0相交，那麼t1肯定是另一交點，p1肯定為負n return Geo2DResult(this, false,n Geo2DPoint(t[1], p[1], Normalize(pts[m[ids[1]][0]] + pts[m[ids[1]][1]] - center - center)),n Geo2DPoint(t[0], p[0], Normalize(pts[m[ids[0]][0]] + pts[m[ids[0]][1]] - center - center)));n case 3: // 雙正，有交點，在外n if (t[0] > t[1])//都相交？就看看哪個交點更近了n {n return Geo2DResult(this, false,n Geo2DPoint(t[1], p[1], Normalize(pts[m[ids[1]][0]] + pts[m[ids[1]][1]] - center - center)),n Geo2DPoint(t[0], p[0], Normalize(pts[m[ids[0]][0]] + pts[m[ids[0]][1]] - center - center)));n }n elsen {n return Geo2DResult(this, false,n Geo2DPoint(t[0], p[0], Normalize(pts[m[ids[0]][0]] + pts[m[ids[0]][1]] - center - center)),n Geo2DPoint(t[1], p[1], Normalize(pts[m[ids[1]][0]] + pts[m[ids[1]][1]] - center - center)));n }n default:n break;n }n }n return Geo2DResult();n}n

其實過程不複雜（我一晚上竟然能搞定哈哈，這歸功於調試方法的先進性），計演算法向量很簡單，就是兩個對角線的疊加方向。。

有幾個注意點：

• 求符號SignBit自己寫的，用fsignbit導致gg（算我不會用吧），我相信編譯器的優化能力
• 知矩形中心點、兩軸距離、旋轉角度後，要計算出四點的坐標，這時有計算順序，一開始只能將旋轉矩陣應用於(sx,sy)軸向量！不能用於四點的真實坐標，相當於先在矩形的本地坐標系中應用旋轉，最後才加上矩形自身的位置偏移
• 為什麼要用參數方程做，不用y=kx+b做：如果這時的直線是豎直方向的呢？y=kx+b就不能表達了
• 求出了交點，要判斷交點是否在線段AB上，做法是x坐標和y坐標相減判斷同符號，不能用y=kx+b算距離求比值在0~1間，這樣即不正確也不高效

小結

矩形會做之後，多邊形應該都能搞定了，如三角形，只要考慮一下三邊的方向即向（即判斷是在內還是在外）。

做完之後，在做反射、折射，這簡單了！因為距離呀交點呀法向量全部求出來了。

讀過用C++畫光（一） 後，看了他的代碼https://github.com/lilypuye/cppLight2d/blob/master/Shape.h#L281， @浦夜 他的差集沒有實現出來，一方面是設計思路的問題，另一方面是debug繁瑣的問題（運行一下，打開一張圖片，當然煩了），其實本質是缺少一個可視化界面，有了界面，問題就變得簡單了。他的光色散我要嘗試下，簡直太美。

至於我為什麼要在框架中實現這個效果：一者，可視化+互動；二者，與眾不同；三者，框架要有例子才能證明好用啊。