Lecturer	Irina Voiculescu
Degrees	Schedule B2 — Computer Science Schedule B2 — Mathematics and Computer Science
Term	Hilary Term 2010  (16 lectures)

Overview

This is an introductory course in modelling techniques for 3D objects. It covers a wide range of different ways of representing the geometry of real objects, depending on their functionality and application. The emphasis in this course will be on the theory and basic principles of constructing models; hence the practicals will not use CAD-specific software, but rather a programming environment suitable for reasoning about the mathematics of models.

Learning outcomes

 At the end of the course, the student will:

• understand the need for, and the different applications of geometric modelling techniques
• understand some of the technical solutions
• be able to reason about the range of solutions to problems involving 3D objects

Prerequisites

Knowledge of basic matrix and vector algebra is assumed, as is basic set theory.

The course does not deal with the rendering of such models: this is left to Computer Graphics. Neither does it deal with any of the applications once the models have been created: this is left to Computer Animation. Whilst there are obvious links between these three courses, they have been designed to be independent of each other.

Synopsis

• Parametric line equations. The arithmetic of intervals. Tests for relative positions of points and line segments. [1]
• Voronoi diagram, Delaunay triangulation, spanning trees. [1]
• Polyhedra and their basic properties. Convex hull. [1]
• Polygonal meshes. Construction. Decimation. [2]
• Boundary representation. Data representation issues. [2]
• Parametric curves, splines, NURBS. [3]
•  Implicit curves. Point membership classification. [1]
• Basics of set theory and its applications to geometry.  Constructive Solid Geometry. Octrees, subdivision techniques. [2]
• Spatial and structural divide-and-conquer. Computing integral properties (area, volume, mass) of shapes. [1]
• Rigid body transformations. Bounding volumes. [1]
• Conversions between different representations. Their respective advantages and disadvantages. Efficiency issues. [1]

Syllabus

• Parametric line equations. The arithmetic of intervals. Tests for relative positions of points and line segments.
• Voronoi diagram, Delaunay triangulation, spanning trees.
• Polyhedra and their basic properties.
• Convex hull.
• Polygonal meshes. Construction. Decimation.
• Boundary representation. Data representation issues.
• Parametric curves, splines, NURBS.
• Implicit curves. Point membership classification.
• Basics of set theory and its applications to geometry.
• Constructive Solid Geometry. Octrees, subdivision techniques.
• Spatial and structural divide-and-conquer. Computing integral properties (area, volume, mass) of shapes.
• Rigid body transformations. Bounding volumes.
• Conversions between different representations. Their respective advantages and disadvantages. Efficiency issues.

Reading list

Unfortunately there is no single textbook that covers the syllabus. The following have been part of reading lists for past courses and might be useful:

For B-rep modelling (all rather vague - ask me if you want to see a copy)

• Martti Mäntylä, Solid Modeling, Computer Science Press, 1988. (out of print)
• Hiroaki Chiyokura, Solid Modeling with Designbase, Addison-Wesley, 1988 (out of print)
• Ian Stroud, Boundary Representation Modelling Techniques, Springer Verlag, 2006

For CSG

• The svlis manual contains a very good introduction to CSG and related issues
• A J P Gomes, I Voiculescu, J Jorge, B Wyvill, C Galbraith, Implicit Curves and Surfaces: Mathematics, Data Structures and Algorithms, Springer 2009, ISBN 978-1-84882-405-8 (not compulsory)
• J R Woodwark, Blends in geometric modelling, in The Mathematics of Surfaces (R.R. Martin, ed.) (Proceedings of the 2nd IMA Conference on the Mathematics of Surfaces, Cardiff, 1986) (255--297), Oxford University Press, 1987

For parametric curves, splines and NURBS

• E Cohen, R Riesenfeld, G Elber, Geometric Modelling with Splines: an intr oduction, A K Peters 2001. (thorough, but theoretical)
• Les Piegl, Wayne Tiller, The NURBS Book, Springer 1997. (B-splines and NURBS)
• G Farin, Curves and surfaces for computer aided geometric design, Academic Press, 1990. (practical applications)

For positions of points, lines and segments, also for convex hull and Voronoi diagrams:

• O'Rourke, J Computational Geometry in C, Cambridge University Press, 1994. (classic in computational geometry)

For a summary of various topics:

• J D Foley, A Van Dam, S K Feiner, J F Hughes and R L Phillips, Introduction to Computer Graphics, Addison-Wesley 1996. (chapters on B-rep and CSG, also rigid body transforms)
• T H Cormen, C E Leiserson and R L Rivest, Introduction to Algorithms, MIT Press, 1990. (general algorithms and complexity)

To be continued...

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.