Trinity College Dublin

Skip to main content.

Top Level TCD Links

Sitemap

Module MA3461: Computational Geometry & Computer Graphics

**Please note this is a Tentative Description of the module**
Credit weighting (ECTS)
5 credits
Semester/term taught
Michaelmas term 2014-15
Contact Hours
11 weeks, 2 lectures and 2 labs per week
Lecturer
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.
THEORY:
  • Graphs and graph planarity
  • Euler's Formula
  • 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
 
Module Prerequisite
 
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.