Think Stitch
PRINCIPIA  最近の更新


切り捨て関数と切り上げ関数

不思議な計算ループで切り捨て関数 floor と切り上げ関数 ceiling が役に立つといったので、ほんのささやかな例を書きます。 (体調が悪いので、開発から逃避して古いネタを引っ張りだしているだけなんです。)

切り捨て関数と切り上げ関数の定理

切り捨て関数と切り上げ関数でよく使うのは、次の4つ同値関係です。 ここで x は実数、n は整数です。

どれも一方向は自明ですけど、反対方向はちょっとだけ驚きます。 でも背理法を使ったり、x を整数部分と少数部分に分けてみるとすぐに納得できます。

線分の描画

この GPU 全盛時代に線分描画の話なんです。何せ Z80 で育っているのでしかたがないんです。 原点から点 (a, b) まで線分を引くとします。 座標が整数である点を、ピクセルの中心に置く流儀と、ピクセルの境界に置く流儀とあると思うのですが、ここでは中心に置くとします。 (どっちが多く使われているのでしょう?) 点 (a, b) は第1象限の y = x 以下にあるとします。 つまり 0 <= b, 0 < a, b <= a とします。

整数座標 (x, y) を考えたとき、このピクセルを描画するのは、y 軸と並行 ^H ^H 平行なピクセルの中心線が数学的な線分と交わる点がピクセルの内部にあるときです。 ちょうど境界線にあるときにはどちらか好きな方を選べばよいので、ここでは下を含めることにします。

これを条件式で表すと次のようになります。

ピクセル線分の方程式

式 (5) の各辺に 1/2 を加えると次のようになります。

この左側の不等式を見ると、左辺は整数で右辺は実数で、不等号には = が入っています。 したがって式 (2) のパターンです。 よって次のものと同値です。

次に右側の不等式を見ると、左辺は実数で右辺は整数で、不等号には = が入っていません。 したがって式 (1) のパターンです。 よって次のものと同値です。

この両辺は整数ですから、さらに次のものと同値です。

(7) と (9) から、結局次がわかりました。

これがピクセル線分の方程式というわけです。 ただ、それだけのことなんですけどね。

クリッピング

b > 0 とします。今度は式 (5) から b/a をはらって次の式を得ます。

左側の不等式を見ると、左辺は実数、右辺は整数、不等号には = が入っていますから式 (3) のパターンです。 したがってこの式を満たす最小の整数 xmin は次のようになります。

つまり、与えられた y に初めて達する点は (xmin, y) です。 したがって、y 未満の範囲でクリッピングしたい場合は、xmin - 1 まで描画すればいいことがわかります。 分数を1つにまとめると次のとおりです。 ただ、それだけのことなんですけどね。

切り捨て関数と切り上げ関数のプログラムでの計算

x, y が正の整数である場合、ほとんどの CPU やプログラミング言語で、整数の除算は次式を満たすと思います。

x, y の少なくとも一方が負の場合は CPU や言語によってさまざまです。 困ったものです。

正整数の場合は次式が成り立ちます。 もうちょっとシンプルな公式もありますけど、負の数を経由する場合があるのでこちらの方が安全です。

整数除算だと次のようになります。

これはメモリブロックのサイズ計算でよく使いますよね(そんなことはもう誰もしないのか)。

ただそれだけの話でした。これで8月も終わりです。

2013/08/31
© 2013,2014,2015 PRINCIPIA Limited