okkyの日記： CGの特許は効率の問題ではすまない場合があるのがいやらしい…

表の記事を見て。

大抵の場合、効率を犠牲にすれば特許回避はできる。逆に特許料と言うのは犠牲になる分の効率で得られるメリット以上の値段をつけることはない。

が、CGの特許はこれが当てはまらないことがある。描画している絵の見てくれが変わっちゃう場合があるからだ。

.........

たとえば OpenGL の場合。これは特許だったか違ったか忘れた上に、特許だったとしても SGI は今回のケースに関しては自由に使わせてくれると思うが… Diamon Exit Rule というのがある。これは連続した点列間を直線などで結んでいったときに「端の点を描画するかどうか」を決める規則だ。

.

たとえば、3つの点 a, b, c を考えて欲しい。それぞれが画面上にピクセルがあり、それらはダブらないとする。 a→b の直線を引くために点を打っていくが、この時に「完全上書きではなく、背景のピクセルの色を 50%, 線の色として「R=1.0, G=0.0, B=0.0」を 50% 混ぜた色を打つ必要があるとしよう。a 点も b 点も含めて描画するとしよう。あ、色は Red, Green, Blue それぞれ 0.0 から 1.0 までであらわすとしよう。

同様に b→c の直線を引くために同じルールを適用する。b点もc点も描画する。線の色も一緒だ。

さて、何が起こったか?

実は b の点1点だけ、不必要に「赤々とした点」になっているはずだ。最初の色 C=(r,g,b) に対して、

1. まず a→b の時、50% の赤を混ぜたので、新しい点 b の色は (r*0.5+0.5, g*0.5, b*0.5) になっている。
2. b→c の時、50% の赤を混ぜたので、新しい点bの色は ( r*0.25+0.75, g*0.25, b*0.25 )

他の点は全て赤を 50% 混ぜただけの色になるはずなので、bという「頂点」だけ、赤々しいのは一般には、まずい。

.

Diamond Exit Rule はこの問題を解決してくれる。

まず、ピクセルを「理想点」ではなく「正方形」であると見なす。縦横それぞれ1の長さを持っている正方形だとするわけ。で、この正方形の中に丁度納まる形の「ひし形」を考える。このひし形が Diamond。トランプのダイヤだね。

点を描こうとすると、本当の理想の直線というのが存在するはずだ。bの点も「ピクセル」じゃなく、もっと厳密な点があるはず。その「理想の点 b」へ向けて、「理想の点 a」から矢がバーンと放射されることを考えて欲しい。

さて。この矢。bというピクセルのどこかに当たったはずだ。で、その際「何が起こったか?」を見る。

b というピクセルの中のひし形。あのひし形の「中から飛び出す」事ができたら、ピクセルbは描画する。「ひし形の中から飛び出さなかったら」ピクセル b は描画しない。これが、Diamond Exit Rule。

たとえば、理想点 b がきっかりピクセル b の中にあるひし形の中に存在したとしよう。a→bを描画するとき、矢はbの中のひし形から出てきていないので a→b の段階ではピクセル b は上書きしない。その代わり、b→c の際にひし形から出て行くかもしれない。そのときに初めて b を描く。

理想点 b は最初からひし形の外にあるかもしれない。で、理想点 b と、理想点 a の間には、ピクセル b のひし形がいる場合を考えよう。aから出た矢はひし形を突き抜ける。結果として矢は「ひし形から出てくる」ので、ピクセル b は描画対象になる。もし、ピクセルcがaと隣接していたりすると、b→cの場合ももう一度矢はひし形bを突き抜けるかもしれない。その場合はピクセルbを2度上書きする事になるが、線が2本通っているのだから、その分赤々しくなっても構わない、と言うわけだ。

.

この Diamond Exit Rule。ある点を描くかどうか、に関わっているので、はっきり言って逃げられない。これを回避すると OpenGL としての本来あるべき画像じゃなくなってしまう。だから、もし、Diamond Exit Rule が特許だったら逃げられない。

もちろん、Diamond Exit Rule は一見すごくややこしいが、実際にはブレゼンハムアルゴリズムの拡張みたいな方法で、簡単に判別できる。それは確実に SGI の特許だったと思う。今でも有効かどうかは知らないが(もう切れたんじゃないかなぁ)、その巧妙さと、
「SGI の GL をデザインした段階で、Diamond Exit Rule を入れ込んでおいた賢さ」
に舌を巻いた記憶がある。

.

このように、CGの特許は 「見てくれに関する特許そのもの」なので、回避が難しい、というお話でした。