ラインスキャン法による三角ポリゴン描画

うむ。こんにちは。ポリゴン描画にいよいよかかります。こいつがいちばんの難所で速度が出る出ないの境目がここにあります。今回はラインスキャンというCPUで描画するのに適した高速かつ穴のないレンダリングを目指します。

ラインスキャンと言う名の通り1行ずつ描画していきます。y方向に1行ずつ増えた時のxの増加量を65536倍して計算しておき、それに沿って描画を行います。zバッファのzの値も線型性を利用してx同様に増加量を計算しておきます。

描画開始点と終了点のそれぞれに対して増加量を計算しておきます。開始地点と終了地点がもとまれば後はzを補間をかけながらzテストを行い描画するだけです。何度も言いますがzは線型性を持つからこれでおkです。

ここでクリップについて考えましょう。今ここではいちばん上の頂点がはみ出しています。描画を開始するx座標は二点になります。たいていの場合はクリップはこれだけ考えておけばなんとかなります(笑

3Dのスキャンライン法では1行ずつ各ポリゴンを描画します。各ポリゴンは複数行にまたがることが多いので描画はその回数分だけ繰り返し行います。

最後に固定小数点の行方について考察します。固定小数点では以下のメリットがあります

もちろんデメリットも

ってところでしょうか？32.32フォーマットだと128ビット計算が必要ですね。これは非現実的です。

PCで実際に動作させたところ、80ポリゴンで6000fpsほどだったので1/200の性能だと仮定すると30fpsは出ると思います。

実際に測ってみると

で20fpsくらいでした。このアルゴリズムの性質上描画する面積に比例して処理速度が増加するため、ドットを置くスピードに強く依存してしまうようです。

例えば60MHz、SPI液晶、など相手だったらかなりスムーズに動くと思います。ただそれでも解像度次第ですね。

あと気になってたんですがアルゴリズム次第ではもう少し上がりそうな気がします。例えば辺の傾きって辺を共有していると計算量が減るとか。その処理には割り算使ってるのでそこが重いんですよ。後は多角形に対応するとか？←これが一番効果ありそう。

gombeのブログ