Bezier Clipping


< to my homepage | Publication list | SampleImages| Animation| CG Links| Research topics(in Japanese) >

このページのスライド画像はクリックすると拡大画像が表示されます。        (2014/11 作成)

OutLine
西田は1970年来,40年間ものCG研究を行っており、研究分 野(右 図参照)はかなり 広いがそのなかでもRenderingl関係で特にBezier Clippingに関する研究を紹介する。
この方法は、私が米国BYUに滞在中(1989)にT.W.Sederbergとの共同で開発した手法です . 最初は曲面のレイトレーシング法としてSIGGRAPH 1990で発表しましたが、広く応用する論文を多数発表した。曲線(や曲面)の交差判定に有効ばかりでなく、高次多項式の解を求めるのにも有効な方法であ る。

< Radiosity | Soft shadow | Bezier Clipping | Light Scattering | Natural phenomena >

研究分野



Bezier Clippingとは





Bezier Clippingは上のように多くの応用があります。

Bezier Clippingを紹介してる書籍

Hoschk, Lasser, "Fundamentals of Computer Aided Geometric Design", AK Peters, (1989)
・鳥谷、千代倉、「3次元CADの基礎と応用」共立出版(1991):
・ G.Farin, "Curves and Surfaces for CAGD" 4th Ed.,Academic Press (1996)
・T.Akenine-Noller, E.Haines,"Real-time Renderin", AK Peters (2002)
・G.Farin, "Handbook of Computer Aided Geometric Design," North-Holland, Elsevier 2002
・T.A.-Moller,etc., "Real-Time Rendering", A.K.Petters, 2008

Bezier Clippingを紹介してるサイト

・ Bezier clipping - ウィキペディア

・ 直 線との交点(Bezier Clipping) | ProgrammingCity

・ 交 点 | ProgrammingCity

・ Bezier clipping 

Bezier Clippingの解説(旧版)

・Bezier Clippingの英文解説(pdf)




Bezier Clippingの誕生、原理


西田は1989年から米国ユタ州のBYUに滞在するチャンスを得た。このときまでBezier曲線に関する知識はなかったが、T.W.Sederberg のGCADの講義で知った。その後彼との議論の際に、Bezei clipping法が生まれた。Bezier曲線を分割(clip)を繰り返すことで解をえられるということで、彼がネーミングをBezei clipping法とした。

多項式は必ずBezier曲線(関数)に変換できます(上のは3次式の例)。Bezier関数の解は必ず、その関数の制御多角形と軸との交差区間に存在し ます。


直線とbezier曲線との距離はBezier関数となる。この関数が0になる点が交点である。



多項式の解(交点)が複数ある場合も求められます。収束が遅い場合関数を2分割し、それぞれにclippingを適用すれば、複数解でも収束します。


曲線同志の交差判定もできます。これには曲線の凸包を含む幅のある線(FAT LINEと称す)で相手の曲線をクリップし、交互に適用すると両社の曲線の 幅は狭くなり、かつ短くない、最終的には直線同志の交差と等価になります。


CGの歴史上重要な技術の開発と受賞者(SIGGRAPH S.A.Coons賞など)との関係


共同開発者のSederberg

著者らのBezierClipping関連論文;

"Ray tracing trimmed rational surface patches" by T Nishita, TW Sederberg, M Kakimoto - ACM SIGGRAPH Computer Graphics, 1990

"Curve intersection usingBezier clipping" by TW Sederberg, T Nishita - Computer-Aided Design, 1990 - Elsevier

"Applications of bezier clipping method and their java applets" by T Nishita - Proceedings of SCCG. Budmerice, 1998

" by T. Nishita, E. Nakamae - Computer Graphics Forum, 1994
"

Hidden curve elimination of trimmed surfaces usingbezier clipping" by T Nishita, S Takita, E Nakamae - Visual Computing, 1992 - Springe " 

A display algorithm of brush strokes using Bezier functions by T Nishita, S Takita, E Nakamae - Communicating with virtual worlds, 1993 - Springer

"

A scanline algorithm for displaying trimmed surfaces by using Bézier clipping" by T Nishita, K Kaneda, E Nakamae - The Visual Computer, 1991 - Springer

http://www.nishitalab.org/user/nis/cdrom/pg/Pacific96bezier.pdf

A modeling and rendering method for snow by using metaballs"

by T Nishita, H Iwasaki,Y Dobashi… - Computer Graphics …, 1997

A display algorithm of brush strokes using Bezier functions by T Nishita, S Takita, E Nakamae - Communicating with virtual worlds, 1993 - Springer

A scanline algorithm for displaying trimmed surfaces by using Bézier clipping" by T Nishita, K Kaneda, E Nakamae - The Visual Computer, 1991 - Springer

A shading model of parallel cylindrical light sources" by T Nishita, S Takita, E Nakamae - Visual Computing, 1992 - Springer

Animation of water droplet flow on curved surfaces by K Kaneda, Y Zuyama, H Yamashita… - Proc. Pacific …, 1996 - hiroshima-u.ac.jp

A new radiosity approach using area sampling for parametric patches " by T Nishita, E Nakamae - Computer Graphics Forum, 1993 - Wiley Online Library

"Geometric hermite approximation of surface patch intersection curves" by TW Sederberg, T Nishita - Computer Aided Geometric Design, 1991 - Elsevier

A scan line algorithm for rendering curved tubular objects" by T Nishita, H Johan - Computer Graphics and Applications, 1999 …, 1999 - ieeexplore.ieee.org

GPU‐based Fast Ray Casting for a Large Number of Metaballs  by  2008 - Wiley Online Library

西田 ”Bezier Clippingおよびその計算機支援設計への応用” 福山大 工学部紀要Vol.13、1991 pp.45-57
西田 ”自由曲面を忠実に実現するレンダリング手法”、日経CG、1991 pp.158-173
.

西田の方法を引用してる論文(200以上 の論文が引用してる)

Ray tracing of spline surfaces: Bézier clipping, Chebyshe

v "boxing, and bounding volume hierarchy–a critical comparison with new results"

by S Campagna, P Slusallek, HP Seidel- The Visual Computer, 1997

A conciseBézier clipping technique for solving inverse kinematics problems” by C Bombín, L Ros, F Thomas - Advances in Robot Kinematics, 2000 - Springer

Bezier  Clippingによる曲面のレイトレーシング 



Bezier ClippingはTrimmed Bezeir曲面を対象にしたレイトレーシング法として開発したものである。Trimmed Bezeir曲面とは、 曲面に穴が開いているものを示す(上図の下参照)。曲面のレイトレーシングとは、スクリーンに投影された曲面において、スクリーン座標(x、y)を指定す ると、それに対応する曲面に曲面座標(u,v)を算出する問題である。普通は(u,v)を与えると、それに対応する(X,Y,Z)座標が求まり、それをス クリーンに投影したものが(x,y)である。それに対してスクルーンの座標から、(u,v)を算出する逆問題であり、その計算は難易度の高い。
Kajiyaやこの問題に挑戦した。彼によると双3次曲面の場合368次式を解く必要がある。これは1次式の繰り返しのみで解けるようにしたのが、 Bezier Clippingである。

スクリーン上の点(x,y)から曲面座標(u,v)を算出する問題を考える。(x,y)を通過する2本の直線を考える。この直線からの制御点の距離(1次 式で計算できる)をuに関する関数としてプロットしたのが右図である。これらの凸包の中に必ず解は存在する。同じようにvにおいても求められる。解は必ず u軸と凸包の交差区間に存在するから。この区間で曲面を再分割する。するとこの曲面は小さくなり平面に近づく。v成分についても同じ操作をする。

上の左図はuの存在区間[umin, umax]を求めており。v成分も同様に求め、右図はその区間で曲面を分割したものである。わずか3回の分割でほぼ点になる。このときの(u,v)が解で あ る。

SIGGRAPH 1990:Sederbergの提唱したFFD法により曲面を自由変形し、その後にレイトレーショング法で描画

CG界では良く使用される、ユタのティーポットはBezier 曲面で構成されており、この曲面をレイトレーシング法で表示した例。

Bezier Clippingの応用



CGI'92 :曲面の隠線消去に応用

Scan Line法は、走査線を動かし、走査線単位で可視領域を抽出する方法である(1991年)。走査線と重なるいくつかのサブパッチはBezier clipping法で抽出できる。

TVC('91) ;曲面(穴のあるtrimmed Bezier曲面に適用可)のスキャンライン法に応用


CGI'93 ;NPRへの応用(輪郭と濃淡がBezier曲線で指定されている)


EG93  曲面を含むラジオシテイに応用した例。



Bezier Clipping を用いた 2 次元画像の自由形状変形法




Bezier Clipping関連の著者らの論文
  1. T. Nishita, T. Sederberg, M. Kakimoto, "Ray Tracing Trimmed Rational Surface Patches," Computer Graphics, Vol.24, No.4, 1990-8, pp.337-345.
  2. Y. Kanamori, Z. Szego,T. Nishita, "GPU-based Fast Ray Casting for a Large Number of Metaballs," Computer Graphics Forum (Proc. EUROGRAPHICS 2008), Vol.27, No., pp.. 2008-4
  3. T. Nishita, E. Nakamae, "A Method for Displaying Metaballs by using Bezier Clipping," Computer Graphics Forum, Vol.13, No.3, 1994-9, pp.271-280.
  4. T. Nishita, E. Nakamae, "A New Radiosity Approach Using Area Sampling for Parametric Patches," Computer Graphics Forum, Vol.12, No.3, 1993, pp.385-393.
  5. T. Nishita, "A Display System for Bezier Surfaces and Metaballs using Bezier Clipping," Pacific Graphics 96, pp.66-79, 1996-8
  6. T. Nishita, K. Fujii, E. Nakamae, "Metamorphosis using Bezier Clipping," Pacific Graphics 93, pp.162-173, 1993
  7. T. Nishita, S. Takita, E. Nakamae, "A Display Algorithm of Brush Strokes using Bezier Functions," Computer Graphics International 93, pp.244-257, 1993-6
  8. T. Nishita, S. Takita, E. Nakamae, "Hidden Curve Elimination of Trimmed Surfaces Using Bezier Clipping," Computer Graphics International 92, pp.595-619, 1992-6
  9. T. Nishita, K. Kaneda, E. Nakamae, "A Scanline Algorithm for Displaying Trimmed Surfaces by using Bezier Clipping," The Visual Computer, Vol.7, No.5, pp.269-258, 1991-9
  10. T. Sederberg, T. Nishita, "Curve Intersection using Bezier Clipping," CAD, Vol.22, No.9, pp.337-345, 1990-11
  11. T. Nishita, K. Kaneda, E. Nakamae, "High-Quality Rendering of Parametric Surfaces by Using a Robust Scanline Algorithm," Computer Graphics International 90, pp.493-506, 1990-6

 

Bezier Clippingを利用したメタボール表示


メタボールは、Blinnがblobと呼んで最初に発表し、独立に大阪大学がmetaballと称し た。

西田らは、メタボールの表示を数倍早くする方法をEUROGRAPHICSで発表した。メタボールの密度関数は6次の多項式で表現できるので(ここでは6 次式)、多項式の解 を算出するのにBezier Clippingが有効である。

左の図のように、メタボールは中心をピークとした密度分布で与えられている。メタボースが接近するとこれらの密度は加算される。指定した閾値の面を抽出す ることで、表面を求める。この方法は陰関数表現された面と言える。




EUROGRAPHICS'94; 右の図は楕円体のメタボールを組合わせてものである。


SIGGRAPH'94: シャチは800個以上のメタボールで構成している。ボールなので泳ぎに合わせて変形するのは容易である。


Pacific Graphics 1996 (金田筆頭): ポットの表面に流れる水滴をメタボールで表現した。これはアニメーションの一部


ShapeModeling'99: 日本人女性の標準体系形のデータを入手し、その形状にフィットしたメタボールを生成して人体を作成した。加えて、そ れに洋服 を着せるシミュレーーションを行った。

 


EUROGRAPHICS08(金森の筆頭論文):GPUを使用し、動的に変化するメタボールを高速に表示できるようにした。


最近、GPUを使い高速化(ほぼリアルタイム)した方法をEUROGRAPHICSで発表した(金森が筆頭)




Java アプレットを用いて、メタボールの会話的に入力し、それを表示する。
他にも、多項式の解、曲線同志の交差判定、曲線と任意の点との最短距離の抽出などのアプレットを作成した。

西田らのメタボールの表示例




メタボールとは限らないが、粒子として表現する描画法の計算例





謝辞;
この研究に関し、元指導教授の中前教授に加え、共同研究者の金田先生、岩崎先生、金森先生に感謝する。

Bezier Clippingを利用した描画ソフトの商業化



西田の論文(1990)を読んで、レイトレーシング法を商品化したものであ る。これはNKエクサ社が実用化。










 




 


  Up to my homepage.