计算机图形学2

1、Lecture 2Core problems of Graphics ProcessingXiaoShuangjiuXiaoShuangjiu Digital Art Lab of Software School of SJTUDigital Art Lab of Software School of SJTUMain TopicslModelinglAnimationlRenderinglInteraction Question 1lWhats for Modeling? 2.1 Techniques of Modeling2.1.1 Model RepresentationPolygona

2、l TechniquesParametric Curve and SurfaceImplicit SurfaceSubdivision Curve and SurfaceDeformable SurfaceSolid GeometryGrammar-based ModelingHuge Scene-BSP treeFractal GeometryParticle SystemCellular Automata2.1.1 Model RepresentationlPolygonal Techniques2.1.1 Model Representation左边：均匀网格左边：均匀网格 ，9000个

3、三角形。右边：自适应细分网格个三角形。右边：自适应细分网格 ，三角形数目，三角形数目基本相同。右边的阴影和轮廓看起来比左边的要好。基本相同。右边的阴影和轮廓看起来比左边的要好。2.1.1 Model RepresentationlTriangle mesh are probably the most common data structure for representing surfaces .lA significant amount of algorithms from modeling to rendering take advantage of their compact and e

4、fficient naturelIn current Graphic Pipeline and Hardware Architectures, all graphics are rendered as triangles.2.1.1 Model RepresentationlDrawbacks of Triangle meshFine tessellation is required to overcome the coarse piecewise linear approximation. Because a triangle mesh is only C0-continuous, norm

5、als and curvature of a tessellated surface are usually interpolated between values estimated at the vertices.do not need to be manifolds, so they can contain self-intersections and holes that are not found in surfaces of real-world objects2.1.1 Model RepresentationlParametric Curve and surface2.1.1

6、Model RepresentationP.E.Bzier ( a French Engineer of Renault Company) presented a kind of Parameter Curve based on spline approximate Bzier CurvesBzier Basis FunctionsEquation from P.E.Bzier niiitft0)()(ap nijj1i1jjnjiitCC)1()t (fa0a1a2a3ai is the vectors of relative position 333223210t) t (ft2t3) t

7、 (ftt3t3) t (f1) t (f When n=3f0(t)f1(t)f2(t)f3(t)110Bernstein Definition of Bzier Curveln次Bzier曲线上各点的Bernstein基插值公式为,0( )( )nii niC tPBtBernstein Basis function,!( )(1)!()!in ii nnBttti niCotrol Pointsi.e. cubic Bzier curve(n=3),the Bernstein Basis function32230,31,32,33,3( )(1) , ( )3 (1) , ( )3 (

8、1) , ( )BttBtttBtttBttThen, the equation of cubic Bzier curve is 32230123( )(1)3 (1)+3 (1)C ttPttPtt Pt P Bernstein Basis function- of cubic Bzier curve,!( )(1)!()!in ii nnBttti ni01tB0,3B1,3B2,3B3,330,3( )(1) Btt21,3( )3 (1) Bttt22,3( )3 (1) Bttt33,3( )BttProperties of Basis Function Non-negativity

9、Weight of Unity Recursive,( )0, 0,1 0,( )0, (0,1) 1,2,., -1i ni nBttinBttin,0( )1, (0,1)ni niBtt,11,1( )(1)( )( )i ni ninBtt BttBt Properties of Basis Function SymmetryExtreme PointMax Value,( )(1) i nn i nBtBtelseiBni, 00, 1) 0(,elseniBni, 0, 1) 1 (,( )/ i nBtti n在 处达到最大值 Properties of Basis Functi

10、on Derivable ascending order,1,1,1( )( )( )i nini nBtn BtBt,1(1)( )(1)( )1i ni nitBtBtn,1 ,11()()1ininit BtBtn,11,11( )(1)( )( )11i ni niniiBtBtBtnn Properties of Basis Function Partitionable Integra,0( )( )( )ni ni jj njBctBc Bt1,01( )1i nBu dunProperties of Bzier Curve Extreme PointTangent vector

11、at extreme point P0 P1 P2 P3T0T3nPCPC) 1 (,)0(01,110( )( )()ni niiiCtnBtPP)() 1 (),()0(101nnPPnCPPnCProperties of Bzier Curve curvature at extreme point P0 P1 P2 P3011230121131|1(0)|1(1)|nnnnnnPPPPnKnPPPPP PnKnP P221,20 ( )(1)(2)( )niiii niCtnnPPPBt21012(0)(1)(2)(1)(1)(2)nnnCn nPPPCn nPPP Properties

12、 of Bzier Curve Symmetry Geometric invariability Convex Hull Property Variation Diminishing Property Affine Invariance P0 P1 P2 P3Recursive interpolating construction of Bzier curve lde Casteljau AlgorithmPresented by Paul de CasteljauConstructing Bezier curve by multiple linear interpolationA recur

13、sive method calculating Bernstein polynomial of Bzier curve Construct Bzier Curve with de Casteljau method For example, Bubic Bzier Curve Calculate the Position of C(t) 1001(1)Pt PtP P0 P1 P2 P3P01 C(t) P11 P21 P02 P12P03P01 C(t) P11 P21 P02 P12P30 1112(1)Pt PtP211112(1)Pt PtP211001(1)Pt PtP1223(1)P

14、t PtP322001(1)Pt PtP Construct Bzier Curve with de Casteljau method Casteljau Recursive Formula for n-Order Bzier Curve 1( )(1)( )( )1,2,., , 0,1,., , (0,1)rr ir iiiiP tt PttPtrninrtl Berstein多项式表示的Bzier 曲面片Suppose that there are (n+1)(m+1) control points pi,j(i=0,1,n; j=0,1,m), m n- order Bzier pat

15、ch could be described as ,00( , )( )( ) ,0,1nmi nj mi jijS u vBu Bv Pu vn Cotrol Mesh Bzier Surfacerijuv16 control points rij determine a 3 3 Bezier patch (1) Generate 4 cubic Bezier curves along v direction3 , 2 , 1 , 0)()(3,30ivBrvrjjiji (2) Calculate points on the four (2) Calculate points on the

16、 four v v- -curves with certain internal curves with certain internal of of ， then generate 4 cubic Bezier curves along u direction303,*)()()(iiiuBvrurq Bzier Patch 1 , 0*vCombining the Combining the u&v curves equationcurves equation30303 ,3 ,303 ,)(),()()()(),(ijjiiiivBjiruBuBvrvuruvV*uv2.1.1

17、Model RepresentationlSpline InterpolationLinear InterpolationQuadratic interpolation Cubic interpolation2.1.1 Model RepresentationlImplicit surface2.1.1 Model RepresentationlImplicit surface2.1.1 Model RepresentationlSubdivision Curve and surfaceConner Cutting Curve 2.1.1 Model RepresentationlSubdiv

18、ision Curve and surfaceConner Cutting Curve 2.1.1 Model RepresentationlSubdivision Curve and surfaceConner Cutting Curve 2.1.1 Model RepresentationlSubdivision Curve and surfaceConner Cutting Curve 2.1.1 Model RepresentationlSubdivision Curve and surfaceConner Cutting Curve 2.1.1 Model Representatio

19、nlSubdivision Curve and surfaceDoo-Sabin Subdivision Surface2.1.1 Model RepresentationlSubdivision Curve and surfaceDoo-Sabin Subdivision Surface2.1.1 Model RepresentationlGrammar-based ModelingManfred Lau, Akira Ohgawara, Jun Mitani, Takeo Igarashi. Converting 3D Furniture Models to Fabricatable Pa

20、rts and Connectors.SIGGRAPH,20112.1.1 Model RepresentationlGrammar-based ModelingDefined the Modeling GrammarManfred Lau, Akira Ohgawara, Jun Mitani, Takeo Igarashi. Converting 3D Furniture Models to Fabricatable Parts and Connectors.SIGGRAPH,2011 (N ; ; P ; S) N is the set of non-terminal symbols =

21、 nodes; edges is the set of terminal symbols for nodes and edgesP is the set of production rulesS N is the start symbol2.1.1 Model RepresentationlGrammar-based ModelingDefine the Terminal Symbol Manfred Lau, Akira Ohgawara, Jun Mitani, Takeo Igarashi. Converting 3D Furniture Models to Fabricatable P

22、arts and Connectors.SIGGRAPH,2011Each type of terminal symbol is defined as t (Shapet; ExampleDimt ; Dimt ) t t has a pre-defined primitive shape ShapetExampleDimt is a set of example dimensions comes from measurements of real IKEA cabinets. Dimt is the dimensions of specific instantiation of a part

23、2.1.1 Model RepresentationlGrammar-based ModelingDefine the ConnectionsManfred Lau, Akira Ohgawara, Jun Mitani, Takeo Igarashi. Converting 3D Furniture Models to Fabricatable Parts and Connectors.SIGGRAPH,2011Each type of connection a b (a; b ) is defined as (Dima;Dimb; Typec;Numberc; Transformation

24、sc)Typec is the type of connector (i.e. type of screw)Numberc is the number of connectorsTransformationsc contains the position and orientation of each connector relative to parts a and b. 2.1.1 Model RepresentationlGrammar-based ModelingManfred Lau, Akira Ohgawara, Jun Mitani, Takeo Igarashi. Conve

25、rting 3D Furniture Models to Fabricatable Parts and Connectors.SIGGRAPH,20112.1.1 Model RepresentationlTask 1 (only for discussion) Modeling and display a tree About Tree ModelingL.Wang W.e Wang,J.Dorsey, X. Yang B. Guo H.Shum. Real-Time Rendering of Plant Leaves. ACM SIGGRAPH 2005 About Tree Modeli

26、nglHow?About Tree ModelingL-System TreesUnfoliaged About Tree ModelingJason Weber & Joseph Penn, SIGGRAPH1995Luis D. Lopez, Yuanyuan Ding, and Jingyi Yu. Modeling Complex Unfoliaged Trees from a Sparse Set of Images. Pacific Graphics 2010.4 input imagesLeft: recovered 3D skeleton tree; Right: re

27、constructed 3D tree modelLuis D. Lopez, Yuanyuan Ding, and Jingyi Yu. Modeling Complex Unfoliaged Trees from a Sparse Set of Images. Pacific Graphics 2010.Ilya Shlyakhter, Max Rozenoer, Julie Dorsey, and Seth Teller. MIT.Reconstructing 3D Tree Models from Instrumented Photographs. IEEE Computer Grap

28、hics and Applications 2001Image + L-systemS.Hong*, B. Simpson and G. V. G. Baranoski. Interactive venation-based leaf shape Modeling. Comp. Anim. COMPUTER ANIMATION AND VIRTUAL WORLDSVirtual Worlds 2005; 16: 415427Focus on Details of TreeLeaflets simulating aging sequence (clockwise order).L.Wang W.

29、e Wang,J.Dorsey, X. Yang B. Guo H.Shum. Real-Time Rendering of Plant Leaves. ACM SIGGRAPH 2005 Realistic Rendering2.1.1 Model RepresentationlTask 2 (only for discussion) Amount of trees modeling for a large 3D scene which could be roamed virtuallyTask 2Lightweight Tree ModelingR.Sun, J. Jiay, H. Liz

30、, M. Jaeger. Image-based Lightweight Tree Modeling. VRCAI 2009, Yokohama, Japan, December 14 15, 2009Lightweight Tree ModelingY. Livny, S. Pirk, Z. Cheng, F. Yan, O. Deussen, D.Cohen-Or , B. Chen. Texture-Lobes for Tree Modeling. SIGGRAPH,2011Lightweight Tree ModelingY. Livny, S. Pirk, Z. Cheng, F. Yan, O. Deussen, D