1、计算机图形学总复习 1Ch1.a survey of CS2Graphics 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.3n凡是
2、能够在人的视觉系统中形成视觉印象的客观对象都称为图形图形。n(1)自然景物n(2)照片和图片n(3)工程图、设计图和方框图n(4)人工美术绘画、雕塑品n(5)用数学方法描述的图形（包括几何图形、代数方程、分析表达式或列表所确定的图形）什么是图形？4Vectorgraph and bitmap(1).vectorgraph(1).vectorgraphAny curves are approached with many short linesAny curves are approached with many short lines(2).bitmap(2).bitmapEvery curv
3、e must be consist of several pixelsEvery curve must be consist of several pixels5n几何要素几何要素：刻画对象的轮廓、形状等(几何模型)n非几何要素非几何要素:刻画对象的颜色、材质等(物理属性)计算机图形学中的图形要素6What is Computer Graphics？nThe technology for generating the images on the computer screen with algorithms and programs is called the computer graphic
4、s.n计算机图形学计算机图形学(Computer Graphics,CG)是。7Relationship 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）研究内容（学科学科）8Computer Graphics Applicationsn图形用户界面(GUI)n计算机辅助设计与制造（CAD/CAM）n娱乐游戏及计算机动画(entertainment/game/animation)n计算机艺术(computer art)n地理信息系统(GIS)n科学技术与信息可视化(Visualization)n虚拟现实(Virtual Reality)n图形用户界面(GUI)n9Research Hotspotn真实感显示Realistic
6、Displayn变形技术 Morphing Technologyn数字城市 Digital Cityn识别技术 Recognize Technologyn基于图像的建模 Image Based Modelingn自然对象的建模 Nature Objects Modelingn离散数据建模 Discrete Data Modelingn网络漫游 Web 3Dn 10CRT(Cathode Ray Tube)nThe beam emits electrons(cathode).nRay intensity is controlled by the grid.nThe focus forces th
7、e 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 CRT111213当前研究动态n(1)造型技术
8、n规则形体：欧氏几何方法n不规则形体：n分形几何方法、粒子系统、纹理映射n实体造型n基于物理的造型n基于图像的造型14当前研究动态n(2)真实感图形绘制技术n光照明模型n绘制算法n快速算法n基于图像的绘制n（非真实感图形绘制技术）15当前研究动态n(3)人机交互技术n(4)与计算机网络技术的紧密结合与计算机网络技术的紧密结合n远程医疗与诊断n远程导航与维修n远程教育16研究热点nModelingnAnimationnRendering17Ch2.Introduction to OpenGL/GLUT18What is OpenGL?nA software interface to graphi
9、cs hardwarenGraphics rendering API(Low Level)nHigh-quality color images composed of geometric and image primitivesnWindow system independentnOperating system independent19OpenGL and GLUTnGLUT(OpenGL Utility Toolkit)nAn auxiliary librarynA portable windowing APInEasier to show the output of your Open
10、GL application nNot officially part of OpenGLnHandles:nWindow creation,nOS system calls nMouse buttons,movement,keyboard,etc nCallbacks20How 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 files21Sample Program#include#include void main(int argc,char*argv)int mode=GLUT_RGB|GLUT_DOUBLE;glutInitDisplayMode(mode);glutInitWindowSize(500,500);glutCreateWindow(“Simple”);init();g
12、lutDisplayFunc(display);glutKeyboardFunc(key);glutMainLoop();22OpenGL 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);23GLUT 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.24GLUT 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_f
15、unc);nglutIdleFunc(my_idle_func);nglutKeyboardFunc(my_key_events_func);nglutMouseFunc(my_mouse_events_func);25Event Queue KeyboardMouseWindow.MainLoop()Event queue window_callback().Mouse_callback().Keypress_callback().26Rendering CallbacknCallback function where all our drawing is donenEvery GLUT p
16、rogram 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();27Idle CallbacknUse for animation and continuous updatenCan us
17、e glutTimerFunc or timed callbacks for animationsnglutIdleFunc(idle);void idle(void)/*change something*/t+=dt;glutPostRedisplay();28User 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 r
18、:case R:rotate=GL_TRUE;break;29Mouse 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)30OpenGL Geometric PrimitivesnThe geometry is specified by vertices.nThere are ten primitive types:31
19、An 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();32Ch3.Geometric Primitives几何图元绘制33What is rastering?nThe raster display technology requires to brake down graphic primitives
20、into 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.34n将图形数字化为一组像素强度值，并存放在帧缓存中。这个数字化过程称为扫描转换(scan
21、 conversion)35Line-Drawing Algorithmsn1)DDA algorithmn2)Bresenham algorithm36DDA algorithm(p94)nThe digital differential analyzer(DDA，数字微分分析法)is a scan-conversion line algorithm based on calculating differences based on the slope of the line.37DDA algorithmnA line can be described by the equationy=m
22、x+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.38DDA algorithmnSince 0m1,swap the coordinates axes.4142DDA algorithmnThe DDA algorithm easily ca
23、n 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 algo
24、rithm allows us to do just that.43Bresenham 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 coordina
25、te(y-coordinate)is either increased by one as well or left unchanged,depending on the distance to the next grid point.44Bresenham 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 cent
26、er 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 path45Bresenham algorithm11Next point to plot is:the lower p
27、ixel,if 0 the upper pixel,1 otherwise kkkkkyyEyy(1)(1)klowerkupperkym xbdyydyy2(1)221klowerupperkkEm xydbddupperyxkxk+1=xk+1 dlowerykyk+1line path46Bresenham 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 sta
28、rting point(,):Atxyyyxbx47Bresenham algorithmnCan Ek be caculated recursively?Yes!111 2 2 22kkkkkkEy xx ycEy xx yc 0122022otherwisekkkkEyxEyEEEyx 1112()2()kkkkkkEEy xxx yy 1122()kkkkEEyx yy 48Bresenham algorithm011112If 02 else22 1kkkkkkkkkEyxEEEyyyEEyxyy Note:ONLY integer operations are used!Bresen
29、ham 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+2*dy;else e=e+2*dy-2*dx;y=y+1;setPixel(x,y);49Bresenham 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)
30、11(1,1)2-1(2,2)37(3,2)45(4,3)53(5,4)50Midpoint Circle Algorithm(Hearn&Baker,Section 3-9,P103)nExtension of Bresenham 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 circle51Midpoint Circle AlgorithmnAssume that weve just plot
31、ted(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:yk xk xk+1 xk+2 yk-152Midpoint Circle ChoicesnInside:f(x,y)0 choose lower pixel53Midpoint Circle ChoicesnEvaluate f at midpoint(xk+1,yk-1/2)nDefine Predictor:Pk=f(xk+1,yk-1/2)Pk0 outsid
32、e(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 relation for P.54Midpoint Circle ChoicesnTop Case:(xk+1=xk+1,yk+1=yk)55Midpoint Circle ChoicesnBottom Case:(xk+1=xk+1,yk+1=yk-1)56Midpoint Circle AlgorithmnInitial Pk:57Midpoint Circle Al
33、gorithmnInitial 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+1-yk+1)+1 yk xk xk+1 xk+2 yk-158Set8PixelSet8Pixel59Circles not centered on originnNew Set8Pixel()Function:60Ch4.Attributes of Geometric Primitives几何图元的属性611.Area Fill Algorithms(区域填充算
34、法)(Hearn&Baker,Section 3-14/15,P123;Section 4-10/11/12/13,P196)62Scan-line methods(扫描线填充算法)nWorks row by row from top to bottomnA pixel inside the current scan line is only drawn if it is located inside the polygon.逐点判断法逐点判断法nGreedy approach very slow!63CoherencenEdge Coherence(边的连贯性)n某条边与当前扫描线相交，也可
35、能与下一条扫描线相交nScan-line Coherence(扫描线的连贯性)n当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序可能相同或类似nSpan Coherence(区间的连贯性)n同一区间上的像素取同一颜色属性64Scan-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 polygon65Scan-line methods:ExampleExam
36、ple: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 polygon1x4:inside the polygon 4x8:outside the polygon66Scan-line methodsnThe simple ordered edge list algorithm (有序边表算法)nMethod:preprocessing+scan conversion67Ordered Edge List Alg
37、orithmnPreprocessing(1)Determine for every edge of the polygon the intersections with the scan lines at the pixel centers;ignore horizontal edges.(2)Store every intersection(x,y)in a list.(3)Sort list from top to bottom,left to right.68Ordered Edge List AlgorithmnScan conversion(1)Consider pairs of
38、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 preprocessing 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();n115#define DEG_TO_RAD 1
39、.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();116
