ebook img

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

1019 Pages·1985·24.72 MB·English
Save to my drive
Quick download
Download
Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.

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

Rae A. Earnshaw (Ed.) Fundamental Algorithms for Computer Graphics NATO Advanced Study Institute directed by J. E. Bresenham, R.A. Earnshaw, M. L. V. Pitteway Springer-Verlag Berlin Heidelberg New York London Paris Tokyo Hong Kong Barcelona Budapest Editor Rae A. Earnshaw University Computing Service University of Leeds Leeds LS2 9JT, UK Proceedings of the NATO Advanced Study Institute on "Fundamental Algorithms for Computer Graphics" held at IIkley, Yorkshire, England, March 30-Apri112, 1985 Published in cooperation with NATO Scientific Affairs Division Second printing of NATO ASI (Advanced Science Institutes) Series F: Computer and Systems Sciences, Vol. 17 ISBN-13:978-3-540-54397 -8 e-ISBN-13:978-3-642-84574-1 001: 10.1007/978-3-642-84574-1 This work is subject to copyright. All rights are reserved. whether the whole or part of the material is concerned. specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other ways, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. C Springer-Verlag Berlin Heidelberg 1991 45/3140-543210 - Printed on acid-free paper Foreword 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 and its applications. Algorithms provide the basic foundation of all computational processing. This volume presents algorithms at the foundation 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 timely and up to date. The basic primitives of computer graphics have remained unchanged, viz lines, circles, conics, curves and characters. This volume contains ref erence material in all these areas. The higher levels of contouring and sur face drawing are also well covered. Developments in hardware architec tures have continued since the first edition, but the basic principles of hardware/software trade-ofts have continued. Two significant areas of computer graphics have become well established since the first edition of this volume: PC graphics and scientific visualisa tion. For the former, users and application developers find the need for access to information about graphics algorithms; this volume can meet that need. For the latter, high level visualisation systems need to incorpo rate algorithms, even though the user may not access them directly, but rather rely on the system to perform the necessary mappings and transfor mations to produce the picture on the selected device. Alongside the developments towards greater sophistication and func tional provision in software, there is the trend towards accepted graphics standards, and standards for file formats. This promotes uniformity and ease of migration and interchange of graphics information, but once again all systems that support standards need to incorporate basic graphics algorithms to perform the necessary processing from one form of the infor mation into another. The popularity of the first edition of this work bears testimony to the timeli ness and relevance of the material. R. A. Earnshaw May 1991 About the Directors Or Jack E Bresenham Dr Bresenham was born on 11 October 1937 in Clovis, New Mexico. He received a BSEE in 1959 from the University of New Mexico, and MS and PhD degrees in Industrial Engineering in 1960 and 1964 respectively from Stanford University. He joined IBM in 1960 at San Jose, California. Dr Bresenham currently is a Senior Technical Staff Member in CPD-HQ System Design Support at IBM's Development laboratory in Research Triangle Park, North Carolina. His work has been recognised within IBM by receipt of a 1967 SOD Outstanding Contribution Award for management of three RPG compilers for System/360; a 1983 First Invention Plateau Award; a 1984 CPO Outstanding Contribution Award for "Bresenham's Algorithms"; and a 1985 Hursley Special Contribution Award for his Algorithmic and Microcode contribution to the IBM PC/GX Graphics Display. Pixel-level algorithms for use in raster graphics displays and programming support is his technical speciality. Dr Bresenham is a member of ACM, SIGGRAPH, Sigma Tau, Sigma Xi, and Phi Kappa Phi. He has worked as an engineer, manager, planner, programmer and administrator at IBM laboratories in Hursley, Research Triangle Park, Milan, Mohansic and San Jose, and a Headquarter Operations in SCD - Harrison and World Trade - White Plains. Or Rae A. Earnshaw Dr Earnshaw was born in York, England and educated at Roundhay School and the University of leeds. He holds the BSc and PhD degrees and has been a faculty staff member for 15 y~ars, and heads the graphics team responsible for campus-wide provision elf computer graphics hardware and software in connection with the central computing facility. His PhD was the first in computer graphics to be awarded by the University. He is a Fellow of the British Computer Society and Chairman of the Displays Group. He has been a Visiting Professor at Illinois Institute of Technology, Chicago, and George Washington University, Washington DC. Dr Earnshaw has acted as a consultant to US companies and the College CAD/CAM Consortium and given seminars at a variety of UK and US institutions and research laboratories. More recently he has been a Visiting Professor in Xian, China, giving lectures on the current state of the art in computer graphics. His current interests are graphics algorithms, human-computer interface issues, integrated graphics and text, and display technology. Professor Mike L. V Pifteway Born in 1934, Professor Pitteway was educated at Felsted School and Queens' College, Cambridge. With the assistance of the EDSAC computers he completed his PhD in 1956 for work in radio physics and then spent 2 years in the USA as a Harkness Fellow. After 3 years at the then Radio Research Station in Slough, he became Director of the Cripps Computing Centre at the University of Nottingham and was then appointed Professor and Head of the Computer Science Department at Brunei University. He is a Fellow of the British Computer Society, the Institute of Mathematics and its Applications, the Institute of Physics, and Associate Editor of Computer Graphics, Vision and Image Processing. Besides computer graphics, he still maintains a lively interest in radio physics and is a regular visitor to the United States to work at los Alamos National laboratories. Acknowledgements The Directors and Authors gratefully acknowledge the encouragement and assistance provided by the NATO Scientific Affairs Division, Brussels, Belgium, and also the following industrial sponsors who supported the venture: Cambridge Interactive Systems Ltd, Hewlett Packard Ltd, IBM UK Laboratories Ltd and Systime Computers Ltd. Without the generous financial and professional support provided by these organisations, this Advanced Study Institute on "Fundamental Algorithms on Computer Graphics" would not have been possible. We are very grateful to Or Craig Sinclair, Director of the NATO ASI Programme, for his advice and guidance during the preparations for the Advanced Study Institute. Thanks and appreciation are also due to the University of Leeds, Brunei University and IBM for their encouragement and moral support of the Directors. A special word of thanks is due to Mrs Frances Johnson and the Conference Office at the University of Leeds for handling all the administrative arrangements during the six month period leading up to the Institute and also dUring the two weeks of the Conference. Mrs Johnson and her staff successfully passed every provocation test with limitless patience, tolerance, and above all, a sense of perspective and good humour. The exceptionally good spirit at Ilkley was due In large measure to Mrs Johnson's personality and hospitality. We also thank the Craiglands Hotel for their support and cooperation in prOViding the venue and framework for the Conference. The Invited and Contributing Lecturers spent many hours In preparing their lectures and also their written papers included in this volume, and in discussion at the Conference ~ we are very grateful to them for their contributions and support, without which there would have been no conference and no book. We thank the delegates who attended and contributed their ideas to the programme. We also thank all the secretaries who assisted us with the production of the many letters, documents, memos, programmes and schedules, and especially to Miss Susan Nemes who typed a number of papers for Inclusion In this volume. Finally, thanks are due to The George Washington University, Washington DC, with whom one of us (RAE) was on assignment during the first semester of 1985, for their full support and encouragement of the Advanced Study Institute. Leeds, England 1 July 1985 Washington DC, USA Jack E. Bresenham Rae A Earnshaw Mike L. V. Pitteway Preface An Advanced Study Institute on the theme "Fundamental Algorithms for Computer Graphics" was held in Ilkley, England on March 30 - April 12, 1985 under the auspices of the Scientific Affairs Division of NATO. The Institute was organised by a Scientific Committee consisting of Or J. E. Bresenham, IBM, Research Triangle Park, USA, Or R.A. Earnshaw, University of Leeds, UK, and Professor M.L.V. Pitteway, Brunei University, UK. This book contains the majority of the formal presentations given at the Institute. In addition, the new book "Procedural Elements for Computer Graphics" by D. F. Rogers, McGraw-Hili, 1985, was used as the basis for the lectures given by Professor Rogers at the Institute. This material therefore does not appear in this volume since Professor Rogers' book is an up-to-date, self-contained presentation of this aspect of the subject. Some 80 lecturers and delegates attended the Institute, representing 14 countries. These included Belgium, Czechoslovakia, Denmark, France, Iceland, India, Italy, Netherlands, Norway, Portugal, Turkey, United Kingdom, USA and Yugoslavia. Academia, industry, and government and research laboratories were represented in about equal proportions. This contributed greatly to the success of the Institute since it promoted effective interchange of information and experiences outside the formal sessions, and encouraged the generation of new ideas and perspectives. The primary objectives of the Institute were to provide a comprehensive review of line, arc, conic, curve and character generation algorithms from the pioneering work of Bresenham in 1963 up to the present time. Thus the basic emphasis was on "fundamentals", i.e. the basic algorithms to enable picture elements to be formulated, described and displayed. This also included a review of encoding and compaction techniques. Upon this foundation higher-level functions and applications could be built and some of these were examined in detail during the second half of the Institute. These included contouring, surface drawing, fractal geometries, picture representation, scene generation, animation, CAD and human factors. Program transformations and automatic algorithm generation were also studied in order to assess the tools currently available for the re-formulation, and hence the generation of new algorithms. Finally the topics of raster workstations, VLSI architectures, constructive solid geometry, and systolic array methodology were examined. All this material was covered principally by the Invited and Contributing Lecturers - each being a recognised authority in their particular area. In addition, the delegates were invited to submit papers on their own work relating to the themes of the Institute. Some sixteen delegate papers were accepted after review, and they also appear in this volume. The ordering of the material is divided into ten main sections, beginning with line and area algorithms, and then moving on through arcs, circles and conics to higher level functions and applications. It is envisaged that the tutorial and review nature of many of the Invited Lecturers' papers will be very useful in bringing together current and previous material together under one cover. The subject matter of this book is therefore suitable for a wide range of interests, ranging from the advanced student through to the graphics system designer and implementor. Portions of the book may be used as a standard text since the sections are fairly self contained and self-explanatory. The following Invited Lecturers contributed to the programme: Or J.E. Bresenham (IBM, Research Triangle Park, USA) Ir R. Brons (Catholic University of Nijmegen, The Netherlands) x Professor J. H. Clark (Stanford University and Silicon Graphics Inc, USA) Dr P Coueignoux (Data Business Vision Inc, USA) Dr P. M Dew (University of Leeds, UK) Dr RA Earnshaw (University of Leeds, UK) Professor A R. Forrest (University of East Anglia, UK) Professor H. Fuchs (University of North Carolina at Chapel Hill, USA) Dr RA Guedj (SiGRID S.3, France) Mr R.J. Lansdown (System Simulation Ltd, UK) Professor M. LV Pitteway (Brunei University, UK) Professor D. F. Rogers (United States Naval Academy, USA) Dr MA Sabin (Fegs Ltd, UK) Dr R. F. Voss (Harvard University and IBM, Yorktown Heights, USA) The following Contributing Lecturers each gave at least one presentation: Dr KW Brodlie (University of Leicester, UK) Mrs H. Brown (University of Kent, UK) Mr c.J. Cartledge (University of Salford, UK) Dr PA Dowd (University of Leeds, UK) Mr D.J. Grover (British Technology Group, UK) Dr AC. Kilgour (University of Glasgow, UK) Mr R. D. Parslow (Brunei University, UK) Professor A de Pennington (University of Leeds, UK) Mr T Sancha (Cambridge Interactive Systems Ltd, UK) Dr C. Sinclair (NATO, Belgium) Dr JV Tucker (University of Leeds, UK) Tom Sancha, Managing Director of Cambridge Interactive Systems, keynoted the Institute with a presentation on "Unsolved Problems in Computer Graphics". With a unique blend of academic flair and industrial experience, the current progress towards solving Ivan Sutherland's 'Ten Unsolved Problems in Computer Graphics" (1966) was reviewed In view of the fact that some of these problems are not yet solved, even after 20 years, it is particularly relevant and timely to give serious attention to reView, study, and appraisal of the fundamentals. Dr Craig Sinclair, Director Advanced Study Institutes Programme (ASI), NATO, also gave a keynote address outlining the purpose and objectives of the NATO ASI Programme. The Institute had a full programme of lectures and presentations. The Invited Lecturers' papers included in this volume contain the substance of these lectures. In some cases the original paper has been revised in the light of discussions at the Institute. Only the revised and up-to-date papers are included in this volume One of the objectives behind the series of Contributing Lectures was to explore tOPICS in neighbourin.g disciplines and review their impact at the interface with computer graphics. If progress is to be made towards solving current problems in computer graphics, some degree of lateral thinking will be necessary. In particular, a study of inter-disciplinary aspects and the contributions they can make to a synthesis of current areas of interest is very valuable. In this connection, the following topics were covered: curve generation, typesetting, area-fill, geostatistical techniques for contouring, 3D interpola tion, graphics algorithm protection, architectures for high-performance systems, 3D visualisation, and theoretical aspects of algorithm design. The Directors wish to thank the NATO Scientific Affairs Division for their financial support of the original proposal, and also Dr Sinclair for his advice and guidance during the six month period leading up to Advanced Study Institute. We thank the Industrial Sponsors for providing financial support for Postgraduate Fellowship Awards. These included Cambridge Interactive Systems Ltd, Hewlett Packard Ltd, IBM UK Laboratories Ltd and Systime Computers Ltd. Thanks and appreciation are also due to the XI University of Leeds for their encouragement and moral support, to Mrs Frances Johnson and the Conference Office at the University of Leeds for all their help and assistance with the administrative arrangements during the SIX month period leading up to the Institute and also during the two weeks of the conference; to the Craiglands Hotel, Ilkley, for their support and cooperation; to the Invited and Contributing Lecturers for giving of their time so freely (and also to their employers for allowing them to come); and to all the delegates who attended and contributed their ideas to the programme. Thanks are also due to The George Washington University - with whom the undersigned was on assignment during the first semester of 1985 - for their full support and encouragement of the Advanced Study Institute. RA Earnshaw 1 July 1985 Table of Contents Section 1. Line and Area Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Invited Papers R. BRONS, Catholic University of Nijmegen, The Netherlands "Theoretical and Linguistic Methods for Describing Straight Lines" .................. 19 J.E. BRESENHAM, IBM, Research Triangle Park, USA "Run Length Slice Algorithm for Incremental Lines" . . . . . . . . . . . . . . . . . . . . . . . . . .. 59 M.L.V. PITIEWAY, Brunei University, UK "The Relationship between Euclid's Algorithm and Run-Length Encoding" . . . . . . . . . . . . .. 105 A R. FORREST, University of East Anglia, UK "Antialiasing in Practice" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 113 Submitted Papers C.M.A. CASTLE and M.L.V. PITIEWAY, Brunei University, UK "An Application of Euclid's Algorithm to Drawing Straight Lines" 135 L. DORST, Delft University of Technology, The Netherlands "The Accuracy of the Digital Representation of a Straight Line" . . . . . . . . . . . . . . . . . . . .. 141 AC. GAY, IBM UK Laboratories Ltd, UK "Experience in Practical Implementation of Boundary-Defined Area Fill". . . . . . . . . . . . . . .. 153 C.J. CARTLEDGE and G.H. WEEKS, University of Salford, UK "The Implementation of Fill Area for GKS" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 A P. SURANY, RCA Government Communications Systems, USA "A Simple Algorithm for Determining whether a Point Resides within an Arbitrarily Shaped Polygon" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 Section 2. Arcs, Circles and Conics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 Invited Papers J.E. BRESENHAM, IBM, Research Triangle Park, USA "Algorithms for Circular Arc Generation". . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 197 M.L.V. PITIEWAY, Brunei University, UK "Algorithms of Conic Generation" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 219

Description:
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 ma
See more

The list of books you might like

Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.