Vol. 42 No. 5 Web3D 1171 Web3D CAD/CG Web3D 3D Gregory 8) CAD/CAM Rounding Operations 10) 12) 1 1 Web3D VRML 13) VRML XML extensible Markup Language 1

Size: px

Start display at page:

Download "Vol. 42 No. 5 Web3D 1171 Web3D CAD/CG Web3D 3D Gregory 8) CAD/CAM Rounding Operations 10) 12) 1 1 Web3D VRML 13) VRML XML extensible Markup Language 1"

まいえいさし
5 years ago
Views:

1 Vol. 42 No. 5 May 2001 Web3D VRML Web3D 3D VRML A Compact and Qualified Web3D Representation Based on Lattice Structure Akira Wakita, Makoto Yajima, Tsuyoshi Harada, Hiroshi Toriya and Hiroaki Chiyokura The data size of Web3D representation based on polygon meshes is so large that transferring practical data fast is a hard problem. This paper proposes lattice structure, a new framework for compact 3D representation with high quality surface shape. By utilizing a free-form surface technique, qualified surfaces are transferred with limited amount of data size and rendered. Lattice structure can be regarded as both polygon meshes and free-form surfaces. Therefore, it can be easily integrated to existing Web3D data formats, for example VRML. Lattice structure also enables modeling free-form surface shapes intuitively with polygon modeling-like operations. 1. 3D Web3D VRML Virtual Reality Modeling Language ISO Web3D NURBS CAD/CAM Graduate School of Media and Governance, Keio University Lattice Technology, Inc. CG CAD 3D 1),2) CAD/CG Subdivision Surfaces 3) 7) VRML97, ISO/IEC :

2 Vol. 42 No. 5 Web3D 1171 Web3D CAD/CG Web3D 3D Gregory 8) CAD/CAM Rounding Operations 10) 12) 1 1 Web3D VRML 13) VRML XML extensible Markup Language 14) X3D extensible 3D X3D 15) XML DTD Document Type Definition 2 Web3D 3 4 VRML XML 5 CAD/CAM 6 2. Web3D 2.1 3D Web3D VRML CG VRML Web3D Hoppe 1)

1172 May 2001 Abadjev 2) Hoppe 3D Web3D 2.2 Subdivision Surfaces Doo 3) Catmull 4) Loop 5) Zorin 6) Loop Lee 7) Loop CAD/CG NURBS 2.3 Web3D Web3D 1 Fig. 1 Lattice structure.

3 1172 May 2001 Abadjev 2) Hoppe 3D Web3D 2.2 Subdivision Surfaces Doo 3) Catmull 4) Loop 5) Zorin 6) Loop Lee 7) Loop CAD/CG NURBS 2.3 Web3D Web3D 1 Fig. 1 Lattice structure. The left one is the base mesh and the right one is the corresponding lattice surface. Topologies of these models have one to one correspondence. CG CAD/CAM Web3D Web3D Gregory 8)

4 Vol. 42 No. 5 Web3D 1173 CAD/CAM 3. 3 Gregory 3 Gregory 3.1 Gregory 3 Gregory 8) 3 Gregory Coons Gregory 9) 3 Bézier 2 3 Gregory 2 3 Gregory 20 P ijk (i =0,...,3; j =0,...,3; k =0, 1) 3 Gregory 2 3 Gregory Fig. 2 Gregory patch. S(u, v) = 3 i=0 j=0 3 Bi 3 (u)bj 3 (v)q ij (u, v) (1) (0 u 1, 0 v 1) Bi 3 (u) Bj 3 (v) Bernstein P ijk (i =0,...,3; j =0,...,3; k = 0, 1) Q ij (i =0,...,3; j =0,...,3) i 1, 2 j 1, 2 Q ij (u, v) =P ij0 (2) i =1, 2 j =1, 2 Q 11 (u, v) = up vp 111, u + v Q 12 (u, v) = up 120 +(1 v)p 121, u +(1 v) Q 21 (u, v) = (1 u)p vp 211, (1 u)+v Q 22 (u, v) = (1 u)p 220 +(1 v)p 221 (3) (1 u)+(1 v) 0 u 1, 0 v 1 3 Bézier 3 Bézier Cross Boundary Derivative u v G 1 3 Gregory NURBS 16) CAD/CAM 3.2 Rounding Operations 10) 12) 3 STEP1

5 1174 May 2001 STEP2 STEP3 STEP1 3 (a) V i (i =0...n) 3 (b) V 0 V 0 V 0 F 0 3 (c) (d) V i 1 1 F i (i =0...n) F i P i (i =0...n) P i V i Fig. 3 3 Calculation of vertices of lattice surface. 1 1 V i P i Doo-Sabin 1 Doo-Sabin STEP2 3 Bézier 3 Gregory 4 (a) V 0 V 1 3 Bézier 4 4 (b) 4 (a) C 0 C 3 STEP1 3 Bézier 2 C 1 C 2 4 (c) STEP1 F 0 Q P 0 (= C 0 ) 3 Bézier R C 3 C 1 C 2 4 Fig. 4 Calculation of curves of lattice surface. C 0 C 1 = 4 3 C 0Q C 3 C 2 = 4 3 C 3R (4) C 0 C 1 C 0 Q 4/3 3 Bézier 4 (d)

6 Vol. 42 No. 5 Web3D 1175 S i,s i+1 C 0 S i S i+1 C 3 C 0 C 1 = 4 C 3 0S i C 3 C 2 = 4 C 3 3S i+1 S i,s i+1 Q R C 0 C 1 C 0 Q 4/3 Bézier 3 Bézier STEP3 STEP2 3 Bézier Chiyokura 8) 3 Gregory 3 Gregory STEP2 8 18) G (b) 3 Bézier C 0 C 1 C 2 C 3 V 0 V 1 C 1 C 2 V 0 V 1 3 Bézier C 0 C 3 V 0 V 1 5 Fig. 5 Weighting. 5 3 Bézier Bézier 3 Bézier P 0 V i P 0 = k i V i (5) k i V 0 V 0 = l j P j (6) l j Bézier C 0 C 1 C 2 C 3 V 0 V 1

7 1176 May Web3D 4.1 Web3D Web3D Web3D VRML97 1 VRML97 13) VRML97 XML extensible Markup Language W3C 14) 3D XML VRML97 Web3D XML VRML X3D extensible 3D 2002 VRML2002 ISO X3D XML X3D Web3D 15) VRML97 X3D 4.2 VRML97 6 VRML VRML XVL extended VRML with Lattice VRML XVL ISO/IEC :1997 1: #VRML V2.0 utf8 2: #### 3: PROTO XVL_EDGE [ 4: field SFFloat round_val 0 5: field SFVec3f round_str : field SFVec3f round_end : ] 8: { Text { string [ "weight of edge " ] } } 9: #### 10: PROTO XVL_STATUS [ 11: field SFString status "XVL_LATTICE" 12: ] 13: { Text { string [ "status of shape" ] } } 14: Group{ 15: children [ 16: #### 17: Group { 18: children [ 19: Shape { 20: geometry IndexedFaceSet { 21: ############################# 22: ## 23: ############################# 24: }}]}, 25: #### 26: Switch { 27: choice [ 28: XVL_STATUS { 29: status "XVL_GREGORY" 30: } 31: XVL_EDGE { 32: round_val : round_str : round_end : } 36: IndexedLineSet { 37: coordindex [ ] 38: } 39: ] 40: whichchoice -1 41: }] 42: } 6 VRML Fig. 6 Method of migrating lattice structure to VRML. 6 XVL Group Switch 2 Group Switch Switch whichchoice 1 XVL XVL choice XVL

8 Vol. 42 No. 5 Web3D 1177 XVL STATUS status XVL GREGORY XVL LATTICE 6 round val round str round end XVL EDGE XVL VERTEX 6 1 IndexedLineSet Group X3D VRML2002 XML DTD Document Type Definition XML DTD DTD 7 CAD/CAM 17) XvlShell Faces Edges Vertices Face Edge Vertex XYZ UV Texture Material CS POLYLN CS BEZIER SS LATTICE SS GREGORY SS POLYGON XvlShellTypes XvlShell Type ID DEF USE Face ix tx Edge ix 1: <!ENTITY % XvlShellTypes " CS_POLYLN CS_BEZIER 2: SS_POLYGON SS_LATTICE SS_GREGORY " > 3: <!ELEMENT XvlShell (XYZ, UV, Faces*, Edges*, Vertices*)> 4: <!ATTLIST XvlShell 5: Type ( %XvlShellTypes; ) #REQUIRED 6: DEF ID \#IMPLIED 7: USE IDREF \#IMPLIED 8: > 9: <!ELEMENT Faces (Material?, Texture?, Face+) > 10: <!ELEMENT Edges (Material?, Edge+) > 11: <!ELEMENT Vertices (Material?, Vertex+) > 12: <!ELEMENT Face (Material?, Texture? %XvlG1T1FaceChild;) > 13: <!ATTLIST Face 14: ix %MFInt32; #REQUIRED 15: tx %MFInt32; #IMPLIED 16: > 17: <!ELEMENT Edge (Material? %XvlG1T1EdgeChild; ) > 18: <!ATTLIST Edge 19: ix %MFInt32; #REQUIRED 20: vec %MFInt32; #IMPLIED 21: WRnd %SFFloat; #IMPLIED 22: > 23: <!ELEMENT Vertex (Material?) > 24: <!ATTLIST Vertex 25: ix %MFInt32; #REQUIRED 26: VRnd %SFFloat; #IMPLIED 27: > 28: <!ELEMENT Texture (EMPTY) > 29: <!ATTLIST Texture 30: url CDATA \#IMPLIED 31: repeats %SFBool; "true" 32: repeatt %SFBool; "true" 33: bin IDREF \#IMPLIED 34: DEF ID \#IMPLIED 35: USE IDREF \#IMPLIED 36: > 37: <!ELEMENT XYZ \#PCDATA > 38: <!ELEMENT UV \#PCDATA > 7 X3D DTD Fig. 7 DTD of lattice structure for X3D. vec WRnd Vertex ix VRnd Texture URL url repeats repeatt

とって非常に直感的な作業であるため変形手法としり詳細度 Level of Details 制御を行う必要性がでて有効である細分割曲面においては最終的に得られてくるその際形状の特徴を損なわずにポリゴン数る情報がポリゴンメッシュの頂点座標値であるがラを削減するために頂点を削除する順番と削除後の頂ティスモデリングの場合は自由曲面の制御点座標値を

9 1178 情報処理学会論文誌ングラティスモデリングでは初期多角形が変形制御格子として機能するため操作が容易であるさらに双 3 次 Gregory パッチ 8) May 2001 になる図 8 に本モデリング手法による例を示す 5.2 詳細度制御の特性により生成さ Web3D ではインタラクティブに形状を操作できるれる形状は G1 連続が確保されるこれは細分割曲ことが必須である VRML のようなポリゴンメッシュ面において初期メッシュを操作することで収束曲面を用いたデータの場合メッシュを構成するポリゴンを変形する操作に類似しているこの操作はユーザに数が多いとインタラクティブな操作は非常に困難であとって非常に直感的な作業であるため変形手法としり詳細度 Level of Details 制御を行う必要性がでて有効である細分割曲面においては最終的に得られてくるその際形状の特徴を損なわずにポリゴン数る情報がポリゴンメッシュの頂点座標値であるがラを削減するために頂点を削除する順番と削除後の頂ティスモデリングの場合は自由曲面の制御点座標値を点座標値の移動ベクトルを指定するための様々な工夫得ることができるこのことはポリゴンモデリングが必要になる一方自由曲面を用いればポリゴンの操作感によって自由曲面モデル生成を実現すること分割する際の分割数を調節することで表示データの精を意味するラティス曲面は NURBS にも変換できるため他の曲面モデリングシステムにデータをエクスポートすることも可能であるさらに重み付けを適用度を制御することができるまた曲面データの各輪することで様々な種類の形状を作製することが可能数の指定に加えて最も荒い精度として初期多角形を表郭線に沿ってポリゴンが作成されるために形状が保持する特徴線が失われることはない本手法では分割示しているこれは大まかな形状把握やモデルが視点座標値から離れた場所にある場合の表示要素として利用する場合に効果的である図 9 に自由曲面の分割数の制御を通した形状の詳細度制御の例を示すところで CAD/CAM システムにおいては精度が非常に高いデータが要求される詳細度制御によって高精度なデータを生成すればデータをこれらの用途に使用することも可能である図 10 にラティス構造図 8 ラティスモデリング初期多角形の操作により内部のラティス曲面を変形した例 Fig. 8 An example of lattice modeling. The internal surface shape is deformed through lattice deformation. によって表現されたデータをもとに CAM システムで生成した実モデルを示す図 9 分割数の制御を通した形状の詳細度制御左から初期多角形分割数 1 分割数 2 分割数 8 のモデルを表している Fig. 9 Level of details controls with division number. From left to right, base mesh, division number 1, division number 2 and division number 8.

Vol. 42 No. 5 Web3D 1179 Table 1 1 Data size and calculation times spent in surface generatons. VRML(div.8) VRML(div.4) XVL Mesh num. Lattice num. Surface gen.

10 Vol. 42 No. 5 Web3D 1179 Table 1 1 Data size and calculation times spent in surface generatons. VRML(div.8) VRML(div.4) XVL Mesh num. Lattice num. Surface gen. (KByte) (second) high-heels oni raptor woman bike CAM Fig. 10 A physical model generated with CAM system VRML 4.2 VRML XVL VRML IndexedFaceSet high-heels oni raptor woman bike 5 XVL 8 VRML(div.8) 4 VRML(div.4) 8 Mesh num. Lattice num. XVL 4 VRML 10% Web3D VRML IndexedFaceSet 2 CAD/CG Surface gen. PentiumIII 933 MHz 256 MB Memory PC Mesh num. PC bike Web3D VRML X3D Web3D Gregory CAD/CAM 2 1

1180 May 2001 VRML X3D Web3D 2 1) Hoppe, H.: Progressive Meshes, Computer Graphics (Proc. SIGGRAPH 96 ), pp.99 108 (1996). 2) Abadjev, A., Rosario, M. del., Lebedev, A., Migdal, A. and Paskhaver, V.

11 1180 May 2001 VRML X3D Web3D 2 1) Hoppe, H.: Progressive Meshes, Computer Graphics (Proc. SIGGRAPH 96 ), pp (1996). 2) Abadjev, A., Rosario, M. del., Lebedev, A., Migdal, A. and Paskhaver, V.: MetaStream, VRML 99 (1999). 3) Doo, D. and Sabin, M.: Behaviour of Recursive Division Surfaces Near Extraordinary Points, Computer Aided Design, pp (1978). 4) Catmull, E. and Clark, J.: Recursively Generated B-spline Surfaces on Arbitrary Topological Meshes, Computer Aided Design, pp (1978). 5) Loop, C.: Smooth Subdivision Surfaces Based on Triangles, Master s thesis, University of Utah, Department of Mathematics (1987). 6) Zorin, D., Schroder, P. and Sweldens, W.: Interactive Multiresolution Mesh Editing, Computer Graphics (Proc. SIGGRAPH 97 ), pp , ACM Press, New York (1997). 7) Lee, A., Moreton, H. and Hoppe, H.: Displaced Subdivision Surfaces, Computer Graphics (Proc. SIGGRAPH 2000), pp.85 94, ACM Press, New York (2000). 8) Chiyokura, H. and Kimura, F.: Design of Solids with Free-form Surfaces, Computer Graphics (Proc. SIGGRAPH 83 ), pp , ACM Press, New York (1983). 9) Gregory, J.A.: Smooth Interpolation without Twist Constraints, Computer Aided Geometric Design, pp.71 87, Academic Press, New York (1974). 10) Harada, T., Toriya, H. and Chiyokura, H.: An Enhanced Rounding Operation between Curved Surfaces in Solid Modeling, CG International 90, pp (1990). 11) Loop, C.: Smooth Spline Surfaces over Irregular Meshes, Computer Graphics (Proc. SIG- GRAPH 94 ), pp , ACM Press, New York (1994). 12) Chiyokura, H.: An Extended Rounding Operation for Modeling Solids with Free-form Surfaces, IEEE Computer Graphics and Applications (1987). 13) Wakita, A., Yajima, M., Harada, T., Toriya, H. and Chiyokura, H.: XVL: A Compact and Qualified 3D Representation with Lattice Mesh and Surface for the Internet, Web3D- VRML2000, pp.45 51, ACM Press, New York (2000). 14) World Wide Web Consortium: Extensible Markup Language (XML). (2000). 15) Lattice Technology,Inc.: Lattice Extensions for X3D. /lattice/latticeproposal.html (2000). 16) Takamura, T., Ohta, M., Toriya, H. and Chiyokura, H.: A Method to Convert a Gregory Patch and a Rational Boundary Gregory Patch to a Rational Bezier Patch and its Application, CG International 90, pp , Springer-Verlag, Tokyo (1990). 17) 3 CAD (1991). 18) (1985). ( ) ( ) 11 Web3D

12 Vol. 42 No. 5 Web3D DESIGNBASE 10 Web3D 58 DESIGNBASE DESIGNBASE 2 9

Fig. 2 Gaussian surfaces with different standard deviations

Fig. 2 Gaussian surfaces with different standard deviations Free-Form Deformations Based on Gaussian Functions - Fundamental Theory for Interactive Modeling- Norimasa YOSHIDA, Ken'ya KANOU and Katsuhiro KITAJIMA Interactive and intuitive modeling is one of the