Computer Graphics and Geometric Modelling , livre ebook

Maltoni · Maio · Jain · Prbhakar
Computer Graphics and Geometric Modeling
Max K. Agoston
Max K. Agoston
Computer Graphics
and Geometric
Modeling
Implementation and AlgorithmsGOSPR 5/5/2005 5:47 PM Page i
Computer Graphics and Geometric ModelingGOSPR 5/5/2005 5:47 PM Page iii
Max K. Agoston
Computer Graphics and
Geometric Modeling
Implementation and AlgorithmsGOSPR 5/5/2005 5:47 PM Page iv
Max K. Agoston, MA, MS, PhD
Cupertino, CA 95014, USA
British Library Cataloguing in Publication Data
Agoston, Max K.
Computer graphics and geometric modeling:implementation & algorithms
1. Computer graphics 2. Geometry—Data processing 3. Computer-aided design
4. Computer graphics—Mathematics I. Title
006.6
ISBN 1852338180
Library of Congress Cataloging-in-Publication Data
Agoston, Max K.
Computer graphics & geometric modeling/Max K. Agoston.
p. cm.
Includes bibliographical references and index.
Contents: Implementation & algorithms
ISBN 1-85233-818-0 (v. 1 : alk. paper)
1. Computer graphics. 2. Geometry—Data processing. 3. Mathematical models. 4. CAD/CAM
systems. I. Title.
T385.A395 2004
006.6—dc22 2004049155
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as
permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored
or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in
the case of reprographic reproduction in accordance with the terms of licences issued by the Copyright
Licensing Agency. Enquiries concerning reproduction outside those terms should be sent to the
publishers.
ISBN 1-85233-818-0
Springer is part of Springer Science+Business Media
springeronline.com
© Springer-Verlag London Limited 2005
Printed in the United States of America
The use of registered names, trademarks, etc. in this publication does not imply, even in the absence of a
specific statement, that such names are exempt from the relevant laws and regulations and therefore free
for general use.
The publisher makes no representation, express or implied, with regard to the accuracy of the information
contained in this book and cannot accept any legal responsibility or liability for any errors or omissions
that may be made.
Typesetting: SNP Best-set Typesetter Ltd., Hong Kong
34/3830-543210 Printed on acid-free paper SPIN 10971451GOSPR 5/5/2005 5:47 PM Page v
Preface
This book and [AgoM05] grew out of notes used to teach various types of computer
graphics courses over a period of about 20 years. Having retired after a lifetime of
teaching and research in mathematics and computer science, I finally had the time to
finish these books. The two books together present a comprehensive overview of
computer graphics as seen in the context of geometric modeling and the mathematics that
is required to understand the material. Computer graphics itself is a multifaceted
subject, but it has grown up. It is no longer necessary that a book on graphics
demonstrate the diversity of the subject with a long list of “fun” projects at the expense of
the mathematics. From movies, television, and other areas of everyday life, readers
have already seen what graphics is about and what it can do. It follows that one should
be able to present the geometric modeling aspect of the subject in a systematic
fashion. Unfortunately, the sheer amount of material that I wanted to cover meant
that it had to be divided into two parts. This book contains the practical stuff and
describes the various algorithms and implementation issues that one runs into when
writing a geometric modeling program. The book [AgoM05] provides the
mathematical background for the underlying theory. Although each book can be read by itself
without reading the other, one will get the most benefit from them if they are read in
parallel.
The intended audience of this book (and the combined two volumes especially) is
quite broad. It can be used in a variety of computer graphics courses or by those who
are trying to learn about graphics and geometric modeling on their own. In
particular, it is for those who are getting involved in what is referred to as computer-aided
design (CAD) or computer-aided geometric design (CAGD), but it is also for
mathematicians who might want to use computers to study geometry and topology. Both
modeling and rendering issues are covered, but the emphasis is on the former. The
basic prerequisites are that the reader has had an upper division data structure course,
minimally three semesters of calculus, and a course on linear algebra. An additional
course on advanced calculus and modern algebra would be ideal for some of the more
advanced topics. On the companion CD there is a geometric modeling program (GM)
that implements many of the algorithms discussed in the text and is intended to
provide a programming environment both for further experimentation and
application development. Another program (SPACE) on the CD is an application that uses
some of the more advanced geometric modeling concepts to display the intrinsicGOSPR 5/5/2005 5:47 PM Page vi
vi Preface
geometry of two- and three-dimensional manifolds. Both programs were written using
the Microsoft Visual C++ compiler (and OpenGL) and run under Microsoft Windows
98 or later. Their source code and documentation are included on the CD. The ReadMe
file on the CD lists what all is on the CD and also contains instructions for how to use
what is there.
As I began to develop this book on geometric modeling, one concern obviously
was to do a good job in presenting a thorough overview of the practical side of the
subject, that is, the algorithms and their implementation details. However, there were
two other goals that were important from the very beginning. One was to thoroughly
explain the mathematics and the other, to make the material as self-contained as
possible. In other words, pretty much every technical term or concept that is used should
be defined and explained. The reason for putting all the computer graphics–related
material into one book and all the mathematics into the other rather than
interweaving the material was to keep the structure of the implementation of a modeling
program as clear as possible. Furthermore, by separating out the mathematics it is
easier for readers to skip those mathematical topics that they are already familiar with
and concentrate on those with which they are not. In general, though, and in
particular as far as instructors using this book are concerned, the intent is that the
material in the two books be covered in parallel. This is certainly how I always taught my
courses. An added motivation for the given division was that the applied part of
geometric modeling was often a moving target because, largely due to improvements in
hardware (faster CPUs, more memory, more hard disk space, better display devices),
the way that one deals with it is changing and will continue to change in the future.
This is in contrast to the supporting mathematics. There may be new mathematics
relevant to computer graphics in the future but it will be a long time before the
mathematics I do discuss will lose its relevance. A lot of it, in fact, is only now starting
to be used as hardware becomes capable of dealing with computationally expensive
algorithms.
One property that sets this book apart from others on geometric modeling is
its breadth of coverage, but there is another. The combined books, this one and
[AgoM05], differ from other books on computer graphics or geometric modeling in
an important way. Some books concentrate on implementation and basically add the
relevant mathematics by tossing in appropriate formulas or mathematical algorithms.
Others concentrate on some of the mathematical aspects. I attempt to be as
comprehensive on both the implementation and theory side. In [AgoM05] I provide a
complete reference for all the relevant mathematics, but not in a cookbook fashion. A
fundamental guiding principle was to present the mathematics in such a way that the
reader will see the motivation for it and understand it. I was aiming at those
individuals who will want to take the subject further in the future and this is not
possible without such understanding. Just learning a few formulas is not good enough. I
have always been frustrated by books that throw the reader some formulas without
explaining them. Furthermore, the more mathematics that one knows, the less likely
it is that one will end up reinventing something. There are instances (such as in the
case of the term “geometric continuity”) where unfamiliarity with what was known
caused the introduction of confusing or redundant terminology. The success or failure
of the two books should be judged on how much understanding of the mathematics
and algorithms the reader gets. In the case of this book by itself, it is a question of
whether or not the major topics were covered adequately. In any case, because IGOSPR 5/5/2005 5:47 PM Page vii
Preface vii
emphasize understanding what is going on, there is a natural emphasis on theory and
not on tricks of the trade. The reader will also not find any beautiful glossy pictures.
Clearly, no one book can cover all that falls under the general heading of
geometric modeling. As usual, the topics that are in fact covered and the degree to which
they are covered reflect my own bias. In a large field, there are many special topics
and it should not be surprising that some are not discussed at all and others only
briefly in an overview. On the other hand, one would expect to see a discussion of
principles and issues that are basic to the field as a whole. In that regard, I would like
to alert the reader to one topic, namely, the issue of robustness of algorithms and
computations, that really is a central issue in geometric modeling, but is not dealt with
as thoroughly as it should be, given its importance. The only excuse for this is that to
do this topic