1、计算机图形学总复习 Ch1.a survey of CS3Graphics ConceptnIn narrow sensen位图(bitmap)-图像Image，n矢量图(vectorgraph)GraphicnIn general,graphics can be any object w h i c h i s a b l e t o g i v e v i s i o n impression in mans vision system.It include various geometry graphics,views,pictures,patterns,and images.4n凡是能
2、够在人的视觉系统中形成视觉印象的客观对象都称为图形图形。n(1)自然景物n(2)照片和图片n(3)工程图、设计图和方框图n(4)人工美术绘画、雕塑品n(5)用数学方法描述的图形（包括几何图形、代数方程、分析表达式或列表所确定的图形）什么是图形？5Vectorgraph and bitmap(1).vectorgraph(1).vectorgraphAny curves are approached with many short linesAny curves are approached with many short lines(2).bitmap(2).bitmapEvery curve
3、 must be consist of several pixelsEvery curve must be consist of several pixels6n几何要素几何要素：刻画对象的轮廓、形状等(几何模型)n非几何要素非几何要素:刻画对象的颜色、材质等(物理属性)计算机图形学中的图形要素7What is Computer Graphics？nThe technology for generating the images on the computer screen with algorithms and programs is called the computer graphics
4、.n计算机图形学计算机图形学(Computer Graphics,CG)是。8Relationship with other subjects数字图像数字图像Digital Images数据模型数据模型Data Models图像生成 Image Rendering（计算机图形学（计算机图形学 Computer Graphics）模型/特征的提取 Model/Feature Extraction（计算机视觉计算机视觉 Computer Vision,模式识别模式识别 Pattern Recognition）模型变换 Model Transformation（计算几何计算几何 Computer G
5、eometry）图像变换 Image Transformation（图像处理（图像处理 Image Processing）研究内容（学科）学科）9Computer Graphics Applicationsn图形用户界面(GUI)n计算机辅助设计与制造（CAD/CAM）n娱乐游戏及计算机动画(entertainment/game/animation)n计算机艺术(computer art)n地理信息系统(GIS)n科学技术与信息可视化(Visualization)n虚拟现实(Virtual Reality)n图形用户界面(GUI)n10Research Hotspotn真实感显示Realist
6、ic Displayn变形技术 Morphing Technologyn数字城市 Digital Cityn识别技术 Recognize Technologyn基于图像的建模 Image Based Modelingn自然对象的建模 Nature Objects Modelingn离散数据建模 Discrete Data Modelingn网络漫游 Web 3Dn 11CRT(Cathode Ray Tube)nThe beam emits electrons(cathode).nRay intensity is controlled by the grid.nThe focus forces
7、 the electrons towards a convergence path.nDeflectors force the ray to point at a specific screen point.nThe ray stuns over the phosphor.Phosphor emits lights.nPhosphor emission declines very fast(refreshment required)Figure 2-4 Electrostatic deflection of the electron beam in a CRT121314当前研究动态n(1)造
8、型技术n规则形体：欧氏几何方法n不规则形体：n分形几何方法、粒子系统、纹理映射n实体造型n基于物理的造型n基于图像的造型15当前研究动态n(2)真实感图形绘制技术n光照明模型n绘制算法n快速算法n基于图像的绘制n（非真实感图形绘制技术）16当前研究动态n(3)人机交互技术n(4)与计算机网络技术的紧密结合与计算机网络技术的紧密结合n远程医疗与诊断n远程导航与维修n远程教育17研究热点nModelingnAnimationnRenderingCh2.Introduction to OpenGL/GLUT19What is OpenGL?nA software interface to graph
9、ics hardwarenGraphics rendering API(Low Level)nHigh-quality color images composed of geometric and image primitivesnWindow system independentnOperating system independent20OpenGL and GLUTnGLUT(OpenGL Utility Toolkit)nAn auxiliary librarynA portable windowing APInEasier to show the output of your Ope
10、nGL application nNot officially part of OpenGLnHandles:nWindow creation,nOS system calls nMouse buttons,movement,keyboard,etc nCallbacks21How to install GLUT?nDownload GLUTnhttp:/www.opengl.org/resources/libraries/glut.htmlnCopy the files to following folders:nglut.h VC/include/gl/nglut32.lib VC/lib
11、/nglut32.dll windows/system32/nHeader Files:n#include n#include n Include glut automatically includes other header files22Sample Program#include#include void main(int argc,char*argv)int mode=GLUT_RGB|GLUT_DOUBLE;glutInitDisplayMode(mode);glutInitWindowSize(500,500);glutCreateWindow(“Simple”);init();
12、glutDisplayFunc(display);glutKeyboardFunc(key);glutMainLoop();23OpenGL InitializationnSet up whatever state youre going to usenDont need this much detail unless working in 3Dvoid init(void)glClearColor(0.0,0.0,0.0,0.0);glViewport(0,0,width,height);glMatrixMode(GL_PROJECTION);glLoadIdentity();glOrtho
13、(-10,10,-10,10,-10,20);glMatrixMode(GL_MODELVIEW);glLoadIdentity();glEnable(GL_LIGHT0);glEnable(GL_LIGHTING);glEnable(GL_DEPTH_TEST);24GLUT Callback functions nEvent-driven:Programs that use windowsnInput/OutputnWait until an event happens and then execute some pre-defined functions according to the
14、 users inputn Events key press,mouse button press and release,window resize,etc.25GLUT Callback FunctionsnCallback function:Routine to call when an event happensnWindow resize or redrawnUser input(mouse,keyboard)nAnimation(render many frames)n“Register”callbacks with GLUTnglutDisplayFunc(my_display_
15、func);nglutIdleFunc(my_idle_func);nglutKeyboardFunc(my_key_events_func);nglutMouseFunc(my_mouse_events_func);26Event Queue KeyboardMouseWindow.MainLoop()Event queue window_callback().Mouse_callback().Keypress_callback().27Rendering CallbacknCallback function where all our drawing is donenEvery GLUT
16、program must have a display callbackn glutDisplayFunc(my_display_func);/*this part is in main.c*/void my_display_func(void)glClear(GL_COLOR_BUFFER_BIT);glBegin(GL_TRIANGLE);glVertex3fv(v0);glVertex3fv(v1);glVertex3fv(v2);glEnd();glFlush();28Idle CallbacknUse for animation and continuous updatenCan u
17、se glutTimerFunc or timed callbacks for animationsnglutIdleFunc(idle);void idle(void)/*change something*/t+=dt;glutPostRedisplay();29User Input CallbacksnProcess user inputnglutKeyboardFunc(my_key_events);void my_key_events(char key,int x,int y)switch(key)case q:case Q:exit(EXIT_SUCCESS);break;case
18、r:case R:rotate=GL_TRUE;break;30Mouse CallbacknCaptures mouse press and release eventsnglutMouseFunc(my_mouse);void myMouse(int button,int state,int x,int y)if(button=GLUT_LEFT_BUTTON&state=GLUT_DOWN)31OpenGL Geometric PrimitivesnThe geometry is specified by vertices.nThere are ten primitive types:3
19、2An Examplevoid drawParallelogram(GLfloat color)glBegin(GL_QUADS);glColor3fv(color);glVertex2f(0.0,0.0);glVertex2f(1.0,0.0);glVertex2f(1.5,1.118);glVertex2f(0.5,1.118);glEnd();Ch3.Geometric Primitives几何图元绘制34What is rastering?nThe raster display technology requires to brake down graphic primitives i
20、nto pixels within the raster.nThis process is called rastering(栅格化栅格化).nscan conversion（扫描转换）This is usually done by the graphics hardware.However,it is useful to understand how this process works in order to be able to achieve good graphics performance.35n将图形数字化为一组像素强度值，并存放在帧缓存中。这个数字化过程称为扫描转换(scan
21、conversion)36Line-Drawing Algorithmsn1)DDA algorithmn2)Bresenham algorithm37DDA algorithm(p94)nThe digital differential analyzer(DDA，数字微分分析法)is a scan-conversion line algorithm based on calculating differences based on the slope of the line.38DDA algorithmnA line can be described by the equationy=mx
22、+bnWithout loss of generality,we can assume 0 m 1.Otherwise we can mirror or interchange the coordinates as needed.nNow,we need to compute the series of points(xk,yk),k=0,n that best describes the line.39DDA algorithmnSince 0m1,swap the coordinates axes.4243DDA algorithmnThe DDA algorithm easily can
23、 be extended to other graphics primitives,such as circles,ellipses,etc.nDDA is Good,but Still Not Fast Enough!nFloating point multiply gone from y=mx+bnBut loop still has a floating point addnAnd a round()nWE CAN DO BETTER!nBest performance:Only integer adds/subtracts inside loopnThe Bresenham algor
24、ithm allows us to do just that.44Bresenham algorithm(p95)nAgain,we assume without loss of generality that the slope is 0m 1;hence,the line is located in the first octant.nIdeanno matter what the slope is,we increase one coordinate by one(x-coordinate)similar to the DDA algorithm.nThe other coordinat
25、e(y-coordinate)is either increased by one as well or left unchanged,depending on the distance to the next grid point.45Bresenham algorithmnIn order to decide which point to pick,we introduce an error E which is proportional to the difference between the exact point on the straight line and the cente
26、r between the two possible grid points on the raster.nThe sign of E can then be used as a criterion for the decision.nEither point 1 or point 2 is drawn,depending on which is closer to the straight line.dupperyxkxk+1=xk+1 dlowerykyk+1line path46Bresenham algorithm(1)(1)klowerkupperkym xbdyydyy2(1)22
27、1klowerupperkkEm xydbddupperyxkxk+1=xk+1 dlowerykyk+1line path47Bresenham algorithmnIf we scale E usingx,then we can eliminate m.()22klowerupperkkEx ddy xx yc where is a constant:2(21)ccyxb 0and we have 2Eyx 0000 starting point(,):Atxyyyxbx48Bresenham algorithmnCan Ek be caculated recursively?Yes!11
28、1 2 2 22kkkkkkEy xx ycEy xx yc 1112()2()kkkkkkEEy xxx yy 1122()kkkkEEyx yy 49Bresenham algorithm011112If 02 else22 1kkkkkkkkkEyxEEEyyyEEyxyy Note:ONLY integer operations are used!Bresenham Algorithm/(x1,y1),(x2,y2),x1 x2x=x1;y=y1;dx=x2-x1;dy=y2-y1;e=2*dy-dx;setPixel(x,y);while(x x2)x=x+1;if(e 0)e=e+
29、2*dy;else e=e+2*dy-2*dx;y=y+1;setPixel(x,y);50Bresenham algorithmxkEkplot(xk,yk)dx=5,dy=4,2*dy=8,2*dy-2*dx=-2E0=2*dy-dx=3 if(e 0)e=e+2*dy;else e=e+2*dy-2*dx;y=y+1;xkEkplot(xk,yk)03(0,0)11(1,1)2-1(2,2)37(3,2)45(4,3)53(5,4)51Midpoint Circle Algorithm(Hearn&Baker,Section 3-9,P103)nExtension of Bresenha
30、m ideasnCircle equation:x2+y2=r2nDefine a circle function:f(x,y)=x2+y2-r2nf(x,y)=0 (x,y)is on circlenf(x,y)0 (x,y)is outside circle52Midpoint Circle AlgorithmnAssume that weve just plotted(xk,yk)nStepping in x,next pixel is either:n(xk+1,yk)-the“top”casen(xk+1,yk-1)-the“bottom”casenLook at midpoint:
31、yk xk xk+1 xk+2 yk-153Midpoint Circle ChoicesnInside:f(x,y)0 choose lower pixel54Midpoint Circle ChoicesnEvaluate f at midpoint(xk+1,yk-1/2)nDefine Predictor:Pk=f(xk+1,yk-1/2)Pk0 outside(choose bottom pixel)nPk=(xk+1)2+(yk-1/2)2-r2 =xk2+2xk+5/4+yk2-yk-r2 n!As for Bresenham,try to get a recurrence re
32、lation for P.55Midpoint Circle ChoicesnTop Case:(xk+1=xk+1,yk+1=yk)56Midpoint Circle ChoicesnBottom Case:(xk+1=xk+1,yk+1=yk-1)57Midpoint Circle AlgorithmnInitial Pk:58Midpoint Circle AlgorithmnInitial Pk:P0=1-rnTop Case:(xk+1=xk+1,yk+1=yk)Pk+1=PK+2xk+1+1nBottom Case:(xk+1=xk+1,yk+1=yk-1)Pk+1=PK+2(xk
33、+1-yk+1)+1 yk xk xk+1 xk+2 yk-159Set8PixelSet8Pixel60Circles not centered on originnNew Set8Pixel()Function:Ch4.Attributes of Geometric Primitives几何图元的属性1.Area Fill Algorithms(区域填充算法)(Hearn&Baker,Section 3-14/15,P123;Section 4-10/11/12/13,P196)63Scan-line methods(扫描线填充算法)nWorks row by row from top t
34、o bottomnA pixel inside the current scan line is only drawn if it is located inside the polygon.逐点判断法逐点判断法nGreedy approach very slow!64CoherencenEdge Coherence(边的连贯性)n某条边与当前扫描线相交，也可能与下一条扫描线相交nScan-line Coherence(扫描线的连贯性)n当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序可能相同或类似nSpan Coherence(区间的连贯性)n同一区间上的像素取同一颜色属性65Sca
35、n-line methods:ExampleExample:Scan line y=2:-intersection with polygon at x=1,8 -we can subdivide the scan line into 3 sections:x8:outside the polygon66Scan-line methods:ExampleExample:Scan line y=4:-intersection with polygon at x=1,4,6,8-we can subdivide the scan line into 5 sections:x1:outside the
36、 polygon1x4:inside the polygon 4x8:outside the polygon67Scan-line methodsnThe simple ordered edge list algorithm (有序边表算法)nMethod:preprocessing+scan conversion68Ordered Edge List AlgorithmnPreprocessing(1)Determine for every edge of the polygon the intersections with the scan lines at the pixel cente
37、rs;ignore horizontal edges.(2)Store every intersection(x,y)in a list.(3)Sort list from top to bottom,left to right.69Ordered Edge List AlgorithmnScan conversion(1)Consider pairs of subsequent intersections(x1,y1)and(x2,y2)in the list,i.e.list element 1 and 2,list element 3 and 4,)(2)Due to the prepr
38、ocessing step,we know that for every scan line y:y=y1=y2,x1x2(3)Draw all pixels along the scan line y for which:x1x=360.0)theta-=360.0;n glutPostRedisplay();n116#define DEG_TO_RAD 1.0/57.29578#include GLfloat theta=0.0void mydisplay()glClear(GL_COLOR_BUFFER_BIT);glBegin(GL_POLYGON);glVertex2f(cos(DEG_TO_RAD*theta),sin(DEG_TO_RAD*theta);glVertex2f(-sin(DEG_TO_RAD*theta),cos(DEG_TO_RAD*theta);glVertex2f(-cos(DEG_TO_RAD*theta),-sin(DEG_TO_RAD*theta);glVertex2f(sin(DEG_TO_RAD*theta),-cos(DEG_TO_RAD*theta);glEnd();glFlush();
