Bezier Clipping (1)
人生に一度くらい誰しもが「曲面と直線の交点を高速で求めたい」と思うときありますよね。曲面と直線の連立方程式を解けばいいのですが解析的に解けない場合も多いです。
そのようなときにはニュートン法を使いたくなります。自由曲面 \(z=f(x,y)\) と直線 \( \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} x_0 \\ y_0 \\ z_0 \end{pmatrix} + t\begin{pmatrix} v_x \\ v_y \\ v_z \end{pmatrix} \) との距離 (の2乗) を次のように定義します.
\( d^2= \left( f(x_0+tv_x, y_0+tv_y) – (z_0+tv_z) \right)^2 \)
すると、\(d^2 = 0\) のときの \( t \) がわかれば、直線の方程式に代入することで交点の座標が求められます。ニュートン法はこのような要望に応えてくれる有名な求解アルゴリズムです。
いま関数 \( f: \mathbb{R} \rightarrow \mathbb{R} \) と \( x \in \mathbb{R} \) を使って、
\( f(x) = 0 \)
となる \( x \) を解くことを考えます。このとき、\( x = x_0 \) まわりのテーラー展開を考えれば、
\( f(x) = f(x_0) + f^{\prime} (x_0) (x-x_0) + O( (x-x_0)^2 ) \)
このとき \( f(x) = 0 \) の解は、上のテーラー展開の一次の項までとれば、
\( x = x_0 -\frac{f(x_0)}{f^{\prime} (x_0)}\)
これを離散的に使うと解が求まります。\( x_n \) を適当にとって、次の漸化式、
\( x_{n+1} = x_n -\frac{f(x_n)}{f^{\prime} (x_n)}\)
を繰り返し使うことでテーラー展開で無視した2次の速さで収束していく気がすると思います。
気がすると書いたのは、ニュートン法は初期値をうまくとらないと収束しないことが知られています。また、解によっては不安定であり収束が悪い場合もあることが知られています。もっといえば、交点の有無すら定かでない場合には使いづらいです。
ここではニュートン法を紹介しましたが、今回の定義のように目的関数が正とわかっている場合には目的関数の最小化ともみなすことができますので、機械学習などで用いられるような最適化アルゴリズムも視野に入ってきます。しかし、それらもニュートン法と同様の欠点を抱えていて使いづらいです。
そこで、ニュートン法より安定で、(経験上) 高速なアルゴリズムであるBezier Clipping法を何回かにわけて紹介したいと思います。たとえば非球面のレイトレースに有用です。Pythonでのサンプルコードも用意しますので参考にどうぞ。