Module MA3461: Computational Geometry & Computer Graphics
**Please note this is a Tentative Description of the module**
Credit weighting (ECTS)
Michaelmas term 2014-15
11 weeks, 2 lectures and 2 labs per week
Prof Colm O'Dunlaing
Learning Outcomes On successful completion of this module, students will be able to:
Basic knowledge of planar graphs, Voronoi diagrams, and convex polytopes.
Ability to produce C code for viewing graphs in 2d.
Ability to produce C code for viewing polyhedra in 3D
Module Content Programming language: C, possibly a little C++ to exploit libraries. OpenGL: GL and glut libraries, a little glu.
Graphs and graph planarity
Convex hulls in 2d; lower bound
Voronoi diagrams and Delaunay triangulations in 2d Barycentric embedding Convex hulls in 3d
Steinitz's Theorem (no proof)
Kuratowski Criterion (partial proof, if any) McMullen's upper bounds Cyclic polytopes ---K_n in 3 dimensions
The Jordan-Schoenflies Theorem
Ben-Or lower bounds
PRACTICE: The following KEYWORDS should indicate the extent of graphics programming envisaged. There is no need to memorise them.
Postscript Programming keywords: postorder, add, sub, mul, div, neg, dup, exch, pop, def, gsave, grestore, moveto, lineto, rotate, scale, stroke, clip, clippath, closepath, setlinewidth, setdash, setgray, showpage, fill, show, BoundingBox
OpenGL Programming keywords: openGL, Glu, GLut: gl.h glu.h glut.h, GL_BACK, BL_COLOR_BUFFER_BIT GL_CULL_FACE GL_DEPTH_BUFFER_BIT GL_DEPTH_TEST GL_FLAT GL_MODELVIEW GL_MODELVIEW_MATRIX GL_PROJECTION GL_PROJECTION_MATRIX, glClear glClearColor glColor3d glCullFace glDisable glEnable glGetFloatv glLoadIdentity glLoadMatrixf gl_matrix glMatrixMode glMultMatrixf glOrtho glRotated glShadeModel glViewport gluLookAt gluOrtho2D gluPerspective glutCreateSubWindow glutCreateWindow glutDisplayFunc glutInit glutInitDisplayMode glutInitWindowSize glutKeyboardFunc glutMainLoop glutPostRedisplay glutReshapeFunc glutSetWindow glutSwapBuffers glutTimerFunc
Assessment Detail Lab assignments will carry a high weighting, 30%, with the balance in the final exam. The final exam questions will be based on theory. There is no need to memorise Postscript or OpenGL commands. Supplemental exam if required will consist of 100% exam.