CG2014總復(fù)習(xí)3

1、1計(jì)算機(jī)圖形學(xué)總復(fù)習(xí)3授課教師：郭芬紅授課教師：郭芬紅Email: Email: 辦公室辦公室: : 四教西四教西204204北方工業(yè)大學(xué)理學(xué)院數(shù)學(xué)系北方工業(yè)大學(xué)理學(xué)院數(shù)學(xué)系20201 14 42Ch9. 3-D Object Representations三維對(duì)象表示33D Object RepresentationsnGraphics scenes contain many different kinds of objects and material surfaces:nsolid geometric objectsntrees, flowers, clouds, rocks, wate

2、r, .nThere is NO SINGLE method can describe objects that will include all characteristics of these different matrials!43D Object Representationsnfor solid objects : two categories of representation schemesnsurface models = boundary representations (B-Reps) ninterior models = Space-partitioning repre

3、sentationsnfor natural objects : nprocedural modelsnfor nonrigid behavior: nphysically based modelsn5n計(jì)算機(jī)中表示三維形體的模型， 按照幾何特點(diǎn)進(jìn)行分類，大體上可以分為三種：n線框模型n表面模型n實(shí)體模型 Wireframe model Surface model Solid model - Constructive Solid Geometry - Hierarchical Partition Representation - Boundary Representation6n如果按照表示物

4、體的方法進(jìn)行分類，實(shí)體模型基本上可以分為三大類：n層次分解表示 (Hierarchical Partition Repre.)n常用的分解表示法有：四叉樹、八叉樹、多叉樹、BSP樹等等。n構(gòu)造表示CSG（Constructive Solid Geometry）n構(gòu)造表示的主要方法：掃描表示、構(gòu)造實(shí)體幾何表示、特征和參數(shù)化表示。n邊界表示B-Reps（Boundary Representation）n多邊形平面、樣條曲面7主要講述：nII-1: Constructive Solid Geometry 構(gòu)造實(shí)體幾何nII-2: Quadtrees & Octrees空間單元表示法：四叉樹與八叉樹n

5、III. Curves and Surfaces曲線與曲面n分形88n四叉樹將2D平面分為4個(gè)象限(quadrant)。n四叉樹的每個(gè)結(jié)點(diǎn)有4個(gè)數(shù)據(jù)元素，都在此區(qū)域內(nèi)。n如果一個(gè)象限有同樣的顏色，則該結(jié)點(diǎn)的數(shù)據(jù)元素存儲(chǔ)該顏色，不再細(xì)分 。n否則，該象限繼續(xù)細(xì)分，直到該象限有均勻的顏色或細(xì)分為一個(gè)像素不能再細(xì)分為止。四叉樹Quadtree Representation9Quadtree Example 1nExample: quadtree representation for a region containing one foreground-color pixel on a solid b

6、ackground10Quadtree Example 1nExample: quadtree representation for a region containing one foreground-color pixel on a solid background11Quadtree Example 1nExample: quadtree representation for a region containing one foreground-color pixel on a solid background12Quadtree Example 2nsuitable for repre

7、senting (2D) images13Quadtree Example 31414n3D空間的八叉樹表示是2D平面四叉樹表示的擴(kuò)展。n八叉樹編碼將3D區(qū)域分為8個(gè)象限(octant)，每個(gè)結(jié)點(diǎn)存儲(chǔ)8個(gè)數(shù)據(jù)元素。n3D空間的每個(gè)元素稱為體元 voxels。n當(dāng)一個(gè)象限的所有體元有相同類型時(shí)，該類型被存儲(chǔ)在該結(jié)點(diǎn)的相應(yīng)數(shù)據(jù)元素中，結(jié)點(diǎn)不再被細(xì)分。八叉樹Octree representation15Octree Example 116nCubic SplinenHermite InterpolationnBzier Curves and SurfacesnB-Spline Curves and

8、Surfaces17Hermite Interpolation (1)ntangent Dpk+1 specified at each control pointnlocal influence of control points111 (0(0)(1) 0,.,1)(0)kkkkkkkkPDpPPpPpkDpn+=-18Hermite Interpolation (2)19Hermite Interpolation (3) MH: Hermite matrix ( 埃爾米特矩陣埃爾米特矩陣)20Hermite Interpolation (4)21Hermite Interpolation

9、(5)()101231( )( )( )( )( )kkkkkppP uH uH uH uH uDpDp+驏=桫320321323324( )231,( )23( )2( )H uuuH uuuH uuuuH uuu=-+= -+=-+=-22Hermite Interpolation (6)n這些混合函數(shù)比較平滑，但是在計(jì)算機(jī)圖形學(xué)和CAD中并不直接應(yīng)用Hermite形式，因?yàn)槲覀兺ǔＳ械氖菙?shù)據(jù)點(diǎn)，而不是導(dǎo)數(shù)。nHermite形式是Bzier形式的基礎(chǔ)Hk(u): blending functions (混合函數(shù)混合函數(shù))23nCubic SplinenHermite Interpolati

10、onnBzier Curves and SurfacesnB-Spline Curves and Surfaces24Beziers IdeanIn graphics and CAD, we do not usually have derivative datanBezier suggested using the same 4 data points as with the cubic interpolating curve to approximate the derivatives in the Hermite form (用三次插值曲線中同樣的四個(gè)數(shù)據(jù)點(diǎn)逼近Hermite形式中的導(dǎo)數(shù))

11、25Approximating Derivativesp1 located at u=1/3slope p(0)slope p(1)p2 located at u=2/326EquationsnInterpolating conditions are the same:nApproximating derivative conditions:nSolve four linear equations for:27Cubic Bzier Curve Matrix 28Bezier Blending Functions (Bezier混合函數(shù))Note that all zeros are at 0

12、 and 1 which forcesthe functions to be smooth over (0,1)29Bzier Curves Propertiesn(1) P(u) polynomial of degree n, global influencen(2) P(u) interpolates start and endpointn(3) tangents at start and endpointn(4) convex hull property30Convex Hull Property (凸包性質(zhì))nAll Bezier curves lie in the convex hu

13、ll of their control points (所有的Bzier曲線位于它們的控制點(diǎn)形成的凸包內(nèi))nHence, even though we do not interpolate all the data, we cannot be too far away (因此，即使不插值所有的數(shù)據(jù)，所得結(jié)果也不會(huì)離數(shù)據(jù)太遠(yuǎn))31Bernstein polynomials (伯恩斯坦多項(xiàng)式)nBezier混合函數(shù)是Bernstein多項(xiàng)式的一種特殊情形n這些多項(xiàng)式定義了任意次數(shù)Bzier形式的混合多項(xiàng)式n所有零點(diǎn)在0和1處n對(duì)任意次數(shù)，所有多項(xiàng)式的和等于1n在(0,1)內(nèi)它們的值都在0與1之間3

14、2Bezier方法的局限性n控制點(diǎn)的數(shù)目決定曲線的階次,n+1個(gè)頂點(diǎn)產(chǎn)生n次曲線n沒有局部性n逼近的方法33General Bzier Curves nspline approximation for points pi , i=0,., n where blending functions BEZk,n are Bernstein polynomials:342-Dim. Bzier Curves Examplesngenerated from 3, 4, and 5 control points35ExampleGLfloat ctrlPts43 = -40.0, 40.0, 0.0, -

15、10.0, 200.0, 0.0, 10.0, -200.0, 0.0, 40.0, 40.0, 0.0 ; glMap1f(GL_MAP1_VERTEX_3, 0.0, 1.0, 3, 4, *ctrlPts);glEnable(GL_MAP1_VERTEX_3);GLint k;glColor3f(0.0, 0.0, 1.0); glBegin(GL_LINE_STRIP); / generate Bezier curve for ( k=0; k=50; k+) glEvalCoord1f(GLfloat(k)/50.0);glEnd();glColor3f(1.0, 0.0, 0.0)

16、;glPointSize(5.0);glBegin(GL_POINTS); / plot control points for ( k=0; k4; k+) glVertex3fv(&ctrlPtsk0);glEnd(); 3637分形n分形(fractal)是指具有自相似特性的現(xiàn)象、圖像或者物理過(guò)程等。分形學(xué)誕生于1970年代中期，屬于現(xiàn)代數(shù)學(xué)中的一個(gè)分支。分形學(xué)的創(chuàng)始人是具有法國(guó)和美國(guó)雙重國(guó)籍的曼德布羅特Mandelbrot381）F具有具有精細(xì)的結(jié)構(gòu)精細(xì)的結(jié)構(gòu)，即是說(shuō)在任意小的尺度之下，它總，即是說(shuō)在任意小的尺度之下，它總有復(fù)雜的細(xì)節(jié)；有復(fù)雜的細(xì)節(jié)；2）F是如此地是如此地不規(guī)則不規(guī)則，以至它的整