Module

The main library catalogue currently lists several computational geometry texts by various authors.

Required reading:

O'Rourke,J.  Computational Geometry in C, Cambridge University Press, ISBN 0-521-440343

Supplementary Reading:

• Laszlo,M. J.  Computational Geometry and Computer Graphics in C++,Prentice Hall,  ISBN 0-13-290842-5
• Preparata,F. P.  and Shamos,M. I.  Computational Geometry - An Introduction,Springer-Verlag, ISBN 0-387-96131-3
• Foley, J.D., van Dam, A., Feiner, S.K. and Hughes, Computer Graphics: Principles and Practice. 2nd Edition in C, J.F.Addison-Wesley, ISBN 0-201-84840-6 (Obtainable second-hand from the net. This is recommended for the pre-requisite units and it is expected that all students taking this unit will have purchased their own copy.)
• de Berg,M.,  van Krefeld,M. and Overmars,M. and Schwarzkopf,O.  Computational Geometry Algorithms and Applications, Springer ISBN 3-540-61270

Submission:

Written coursework should be submitted by following the standard CMP practice. Students are advised to refer to the Guidelines and Hints on Written Work in CMP.

Deadlines:

If coursework is handed in after the deadline day or an agreed extension:
 

Saturdays and Sundays will NOT be taken into account for the purposes of calculation of marks deducted.

All extension requests will be managed through the LTS Hub. A request for an extension to a deadline for the submission of work for assessment should be submitted by the student to the appropriate Learning and Teaching Service Hub, prior to the deadline, on a University Extension Request Form accompanied by appropriate evidence. Extension requests will be considered by the appropriate Learning and Teaching Service Manager in those instances where (a) acceptable extenuating circumstances exist and (b) the request is submitted before the deadline. All other cases will be considered by a Coursework Coordinator in CMP.

For more details, including how to apply for an extension due to extenuating circumstances download Submission for Work Assessment (PDF, 39KB)
 

Plagiarism:

Plagiarism is the copying or close paraphrasing of published or unpublished work, including    the work of another student; without due acknowledgement. Plagiarism is regarded a serious offence by the University, and all cases will be investigated. Possible consequences of plagiarism include deduction of marks and disciplinary action, as detailed by UEA's Policy on Plagiarism and Collusion.

Module specific:

• Review the analysis of algorithms and compare the performance of geometric algorithms in theory and practice
• Introduce fundamental geometric data structures and study their use in applications such as computer graphics
• Introduce a variety of convex hull algorithms in 2D and 3D and discuss their implementations
• Consider important triangulation techniques and their applications
• Study Voronoi diagrams and algorithms to generate them in 2D
• Study of simple geometric searching and sorting techniques
• Investigate algorithms for finding the intersection of convex and non-convex polygons
• Introduce the problems of robustness in geometric computation
• Introduce Ray Tracing
• Introduce Radiosity
• Introduce Particle systems
• study 3D curves and surfaces
• study Solid modelling
• study Volume modelling and rendering
• Understand Recent developments in modelling and rendering
• Introduce haptic devices and haptic rendering algorithms

Transferable skills:

• To gain further experience in the analysis and implementation of algorithms that depend on general sorting and searching techniques
• To emphasise the usefulness of mathematical analysis of algorithms
• To develop a methodical approach to problem solving and design through stepwise refinement and object decomposition.
• To recognise and deal with the problem of numerical inaccuracy and lack of robustness in computation

On completion of this module students should be able to:

• Describe the important 3D convex hull algorithms and have experience of their implementation
• Understand how to carry out a complexity analysis of all the geometric algorithms studied in the course
• Describe an algorithm for computing a Voronoi diagram and be aware of its applications
• Implement geometric data structures and apply them to algorithms studied on the course
• Describe various triangulation, geometric searching and sorting algorithms.
• Understand and implement polygon intersection algorithms
• Understand theoretical and practical methods for achieving robustness in geometric implementations.
• Understand ray tracing algorithms
• Understand particle systems
• Understand and implement 3D curves and surfaces
• Describe solid modelling techniques
• Understand volume modelling and rendering

This module is delivered as a programme of lectures, supported by workshops and laboratory classes.

Total Hours: 50

Lectures: 20; Hours 20; Content:

1. Review of complexity analysis
2. Polygon intersection algorithms
3. Introduction to Triangulation algorithms
4. Triangulation & applications
5. Geometric searching/sorting
6. Robustness in geometric computation
7. 2D convex hull algorithms
8. 3D convex hull algorithms
9. Voronoi digrams introduction
10. Voronoi diagram algorithms and the quad-edge data structure
11. Ray Tracing
12. Radiosity
13. Particle systems
14. 3D curves and surfaces
15. Solid modelling
16. Volume modelling and rendering
17. Haptics
18. Recent developments in modelling and rendering

Workshops: 0 hours

Laboratory work: 30; Hours: 30; Content:

1. Implementation of geometric data structures
2. Implementation of curve algorithms
3. Triangulation programs
4. Implementation of coursework.