Fundamental Algorithms for Computer Graphics NATO Advanced Study Institute directed by J.E. Bresenham, R.A. Earnshaw, M.L.V. Pitteway

Algorithms provide the basic foundation for all computational processes. This volume presents algorithms at the foundational level and also at the various levels between this level and the user application. Some of these algorithms are classical and have become well established in the field. This material is therefore a rich source of information and is still relevant and up to date. The basic primitives of computer graphics have remained unchanged: lines, circles, conics, curves and characters. This volume contains reference material in all these areas. The higher levelsof contouring and surface drawing are also well covered. Developments in hardware architectures have continued since the first printing, but the basic principles of hardware/software trade-offs remain valid. This reprint is being published as a Study Edition to make the material more accessible to students and researchers in the field of computer graphics andits applications. The continuing popularity of the original book demonstrates the value and timeliness of its contents.

Section 1. Line and Area Algorithms.- Invited Papers.- “Theoretical and Linguistic Methods for Describing Straight Lines”.- “Run Length Slice Algorithm for Incremental Lines”.- “The Relationship between Euclid’s Algorithm and Run-Length Encoding”.- “Antialiasing in Practice”.- Submitted Papers.- “An Application of Euclid’s Algorithm to Drawing Straight Lines”.- “The Accuracy of the Digital Representation of a Straight Line”.- “Experience in Practical Implementation of Boundary-Defined Area Fill”.- “The Implementation of Fill Area for GKS”.- “A Simple Algorithm for Determining whether a Point Resides within an Arbitrarily Shaped Polygon”.- Section 2. Arcs, Circles and Conics.- Invited Papers.- “Algorithms for Circular Arc Generation”.- “Algorithms of Conic Generation”.- Submitted Papers.- “A High-Precision Digital Differential Analyzer for Circle Generation”.- “An Ellipse-Drawing Algorithm for Raster Displays”.- “An Algorithm for Determining the Draw Start Point of a Hyperbola given the System Direction of Draw and the Coordinates of the Video Window”.- Section 3. Curves and Curve Drawing.- Invited Papers.- “A Review of Curve Drawing Algorithms”.- “Methods for Drawing Curves”.- Submitted Paper.- “Generation of ?-Spline Curves using a Recurrence Relation”.- Section 4. Character Generation and Display.- Invited Papers.- “Character Generation and Display”.- “Font Information and Device-Independent Output”.- Section 5. Contouring and Surface Drawing.- Invited Papers.- “Contouring — the State of the Art”.- “A Review of Geostatistical Techniques for Contouring”.- “Algorithms for Three-Dimensional Interpolation between Planar Slices”.- Submitted Papers.- “GENSURF: A System forGeneral Surface Definition and Manipulation”.- “An Interesting Modification to the Bresenham Algorithm for Hidden-Line Solution”.- “Efficient Hidden Line Removal for Surface Plots Utilising Raster Graphics”.- Section 6. Hardware Architectures and Algorithms.- Invited papers.- “Graphics Software Standards and their Evolution with Hardware Algorithms”.- “Hardware Enhancements for Raster Graphics”.- “Systolic Array Architectures for High Performance CAD/CAM Workstations”.- “Parallel Architectures for High Performance Graphics Systems”.- Section 7. Computational Geometry and CAD.- Invited Paper.- “Computational Geometry in Practice”.- Submitted Papers.- “An Algorithm for Direct Display of CSG Objects by Spatial Subdivision”.- “Computational Geometry and Prolog”.- “Subdivision Techniques for Processing Geometric Objects”.- Section 8. Theoretical Aspects and Models.- Invited Papers.- “Random Fractal Forgeries”.- “The Algebra of Algorithms”.- “Theoretical Considerations in Algorithm Design”.- “Technology for the Protection of Graphics Algorithms”.- “Spatial Concepts in 3D”.- Submitted Papers.- “Shortest Paths in 3-Space, Voronoi Diagrams with Barriers, and Related Complexity and Algebraic Issues”.- “Geometric Data Structures for Computer Graphics”.- “A Model for Raster Graphics Language Primitives”.- “Theoretical Framework for Shape Representation and Analysis”.- Section 9. Human-Computer Interface Issues.- Invited Papers.- “Aspects of Human Machine Interface”.- “Visual Perception and Computer Graphics”.- Section 10. Computer Animation.- Invited Paper.- “Object and Movement Description Techniques for Animation — An Informal Review”.- Scientific Organising Committee.- Lecturers.-Participants.