ゲームプログラマになる前に覚えておきたい技術 Ch.2 - 三角形

C/C++

この本のタイトル長すぎる。しかも上手いこと略せない。

教材のライブラリで unsigned の配列をウィンドウ内の画素に見立てて、その要素を 0xRRGGBB にすると点を打てるものを使って画面に点を打つ、というような内容。

　この章ではこれ以上絵を豪華にすることはしないけれども、もし余裕があれば、三角形や丸を描画する関数を作るとより見やすい画面になるだろう。いろいろ挑戦してみて欲しい。

さらっと言ってるけど三角形ってむずくね？むずいっていうかめんどいっていうか。

大雑把に言うと x, y をずーっと走っていって、そこが色塗るべき場所なら塗る。で丸ならその x, y と円の中心からの距離が円の半径より短ければって条件で（必要な三角関数がわかれば）どうにかなる気がしたんだけど、三角形だと「任意の座標 (x, y) が任意の三角形の範囲に含まれているかどうか」を判断する計算がパッと思いつかなかった。なので朝飯喰いながらチラシの裏に書いて考えた。

三角形 ABC の各辺に対して

  • 点がその辺に対してどっち側にあるか
  • その辺と離れてる頂点がどっち側にあるか

が AB, BC, CA の各辺について全部同じなら三角形の内部だと判断。

まずは lisp で実装してみた。xyzzy に絵を描く機能はないので点が三角形の内部かどうか判断する関数。所要時間1時間強。

(defstruct point  x y)
=> #<structure-definition: point>

(defstruct line  gradient intercept)
=> #<structure-definition: line>

(defun triangle-include-point-p (triangle point)
  (labels ((line (a b)
             "直線 ab の傾きと切片"
             (let ((grad (/ (- (point-y a) (point-y b))
                            (- (point-x a) (point-x b)))))
               (make-line :gradient grad
                          :intercept (- (point-y a) (* (point-x a) grad)))))
           (relation (line point)
             "直線 line に対して point は上にあるか直線上か下にあるか"
             (let ((line-y (+ (* (point-x point) (line-gradient line))
                              (line-intercept line)))
                   (point-y (point-y point)))
               (cond ((> line-y point-y) +1)
                     ((= line-y point-y) 0)
                     ((< line-y point-y) -1)))))
    (let ((ab (line (first triangle) (second triangle)))
          (bc (line (second triangle) (third triangle)))
          (ca (line (third triangle) (first triangle))))
      (and (= (relation ab (third triangle)) (relation ab point))
           (= (relation bc (first triangle)) (relation bc point))
           (= (relation ca (second triangle)) (relation bc point))))))
=> triangle-include-point-p

(triangle-include-point-p
 (list (make-point :x 3 :y 4)
       (make-point :x 8 :y 5)
       (make-point :x 7 :y 11))
 (make-point :x 7 :y 8))
=> t

でこれをほとんどそのまま C++ に持ってってみた。C++ の仕様に悪戦苦闘しながら小一時間かかった。

#include "GameLib/Framework.h" //ゲームプログラマになる前に... のライブラリ

class Point {
   public:
   int x, y;
   Point (int x, int y) : x(x), y(y) {}
};

class Line {
   public:
   float gradient, intercept;
   Line (Point a, Point b) {
      //最初 int で計算してから cast するという失敗をしたので
      //むやみやたらと cast しておいた
      gradient = ( static_cast< float >(a.y - b.y) /
                   static_cast< float >(a.x - b.x) );
      intercept = ( static_cast< float >(a.y) -
                    static_cast< float >(a.x * gradient) );
   }
};

int relation (const Line l, const Point p);
bool include (const Point* triangle, const Point p);

int relation (const Line l, const Point p) {
   float LineY = (l.gradient * p.x) + l.intercept;
   return ( (p.y > LineY) ? 1 :
            (p.y == LineY) ? 0 :
            -1 ); //(p.y < LineY)
}

bool include (const Point* tri, const Point p) {
   Line ab(tri[0], tri[1]), bc(tri[1], tri[2]), ca(tri[2], tri[0]);
   return ( relation(ab, p) == relation(ab, tri[2]) &&
            relation(bc, p) == relation(bc, tri[0]) &&
            relation(ca, p) == relation(ca, tri[1]) );
}

namespace GameLib {
   /* この関数が毎フレーム実行される。つまり main の代わり。*/
   void Framework::update () {
      unsigned* vram = videoMemory(); //この配列がウィンドウ内のドットになる
      int w = width();
      Point a(40, 10), b(10, 50), c(60, 60); //三角形の各頂点
      Point triangle[] = {a, b, c};

      for ( int y = 0; y <= max(a.y, max(b.y, c.y)); y++ ) {
         for ( int x = 0; x <= max(a.x, max(b.x, c.x)); x++ ) {
            Point p(x, y);
            if ( include(triangle, p) ) {
               vram[y * w + x] = 0xff0000;
            }
         }
      }
   }
}

三角形のどれかの辺が Y 軸と平行だったらダメとか、三角形がウィンドウからはみ出てないかチェックしてないとかはあるんだけど、それより三角形の計算ってもっとスマートなやり方があるような気がして仕方ない。数学の勉強しないとダメだな。

C++ だと変数の宣言が `Point p` とかなので変数名自体は短くても（宣言を見れば）なんなのかわかりやすいのはちょっと助かる。lisp だと単純に p とかになってしまうので変数名自体を descriptive にしたくなる。
あとコンストラクタって便利だなとか思った。lisp のは labels で作ったローカルの line がコンストラクタみたいなもんなんだけど。