COMPUTER GRAPHICS
`
`PRINCIPLESOF INTERACTIVE ~
`
`. i3:|
`
`Page 1 of 5
`
`SONY EXHIBIT 1019
`
`

`

`Library of Congress Cataloging in Publication Data
`
`1939-
`Newman, William M
`Principles ofinteractive computer graphics.
`
`=
`
`rr:
`-
`
`=
`(McGraw-Hill computer science series) (McGraw-Hill series in artificial
`&
`intelligence)
`Bibliography:p.
`Includes index.
`
`1, Computergraphics. 2. Interactive computer systems. I. Sproull, Robert F.,
`joint author.
`ILTitle.
`
`T385.N48 1979
`ISBN 0-07-046338-7
`
`001.55
`
`78-23825
`
`‘
`wis
`
`=
`
`PRINCIPLES OF INTERACTIVE COMPUTER GRAPHICS
`
`Copyright © 1979, 1973 by McGraw-Hill, Inc. All rights reserved. Printed in
`the United States of America. No part of this publication may be reproduced,
`stored in a retrieval system, or transmitted, in any form or by any means,
`electronic, mechanical, photocopying, recording or otherwise, without the prior
`written permission of the publisher.
`
`567890DODO 83210
`
`The editors were Charles E. Stewart and Frances A. Neal; the production
`supervisor was Dominick Petrellese. R.R. Donnelley & Sons Company was
`printer and binder.
`
`
`
`
`Page 2 of 5
`
`Page 2 of 5
`
`

`

`RORAL
`
`74 BASIC CONCEPTS
`
`viewport 1
`
`viewport 2
`
`viewport 3
`
`Figure 5-13. Use of viewports for map
`display (1), command menu (2), and
`user messages (3).
`
`5-6 THE WINDOWING TRANSFORMATION
`
`The windowing transformation is so named because it involves specifying a
`window in the world-coordinate space surrounding the information we wish
`displayed. This is by no means the only way such a transformation can be
`specified; for example, we can define the scale factor and translation to be
`applied to the picture, or in place of the translation we can define a world-
`coordinate point we wish transformed to a certain spot on the screen, say the
`screen center. Each of these methods may prove convenient
`in certain
`circumstances; the windowing transformation has the advantageofletting us
`specify directly the rectangle of interest
`in the world-coordinate picture
`definition.
`In addition to the window, wecan also define a viewport, a rectangle on the
`screen where we would like the window’s contents displayed. In doing so, we
`exploit the ability of our clipping algorithm to clip to any right rectangular
`boundary. It is often useful to specify a viewport smaller than the screen, for
`we can then leave room for command menus, system messages, and so forth.
`Each such part of the picture may bedisplayed in a separate viewport, as shown
`in Figure 5-13.
`Figure 5-14 illustrates the full windowing transformation from world to
`screen. We use the window to define what we wantto display; we use the
`viewport to specify where on the screen to put it. Thus we can scan over a large
`picture by keeping the windowsize constant and varying its position; changing
`the windowsize alters the picture magnification. Normally weshall take care to
`keep the window and viewport similar in shape. In Figure 5-14 however, we
`see the distortion that can be achieved by making the shapes different.
`The actual transformation we apply to each point is very simple. Let us
`suppose that the edges of the window are at x = Wy, x = Wxr, y = Wy», and
`y = Wy (see Figure 5-14), all measured in world coordinates, and
`that the
`corresponding edges of the viewport are at x = Vyj, X = Var, y= Vyp, and
`y = V,,, all measured in screen coordinates, Then the point (xy, Yy) in world
`coordinates transformsinto the point(xz, y,) in screen coordinates, as follows:
`
`Page 3 of 5
`
`
`
`
`
`
`
`¢ 5-14 The windowin,
`
`
`
`Xs = xxls
`
`Xs=a
`
`= =
`W
`
`
`
`
`
`
`
`_
`these expressions
`
`yy) within the wi
`
`and corner and i
`viewport. Adding
`
`position of(x5, ys)
`
`_ Equations5-2 redr
`
`
`
`
`
`therefore arranget
`
`= ewport are defin
`
`=)
`ving only two mul
`
`_ the complete win
`
`_ Sansforming the er
`
`ve Mme against the vi
`
`© quickly we nati
`
`@ couple of ways,
`
`én a picture defini
`
`shared endpoints.
`
` Somparing the worlc
`
`‘\ more dramatic
`
`eed by transforming
`
`rectangles, and sin
`
`Page 3 of 5
`
`

`

`
`
`CLIPPING AND WINDOWING 75
`
`gure 5-13 Use of viewports for map
`splay (1), command menu(2), and
`er messages (3).
`
`
`
`
`
`Xs = ——— (X» — Wy) + Vy
`Wyr - Wy!
`
`Vyp
`Vy —
`ye = — 0 — a) + Me
`Wy — Wye
`
`(5-2)
`
`luse it involves specifying a
`ig the information we wish
`
`ich a transformation can be
`
`factor and translation to be
`tion we can define a world-
`
`i spot on the screen, say the
`rove convenient
`in certain
`These expressions are derived by determining the position of the point
`the advantage ofletting us
`
`‘(Xy. Yy) within the window asafraction offull displacement from the bottom
`€ world-coordinate picture
`
`left-hand corner and interpreting this as a fraction offull displacement across
`
`the viewport. Adding the offset of the viewport’s bottom left-hand corner gives
`
`the position of (x,, y,) on the screen,
`
`Equations 5-2 reduce to the form
`
`(5-3)
`y= cyyt+d
`Xs=@QX%ptb
`
`Wetherefore arrange to compute the values of a, b, c, and d when the window
`
`and viewport are defined, so that we can transform each point by a computation
`insformation from world to
`
`involving only two multiplications and two additions,
`vant to display; we use the
`__
`The complete windowingtransformation can then be applied to a picture
`‘hus we can scan overalarge
`
`‘by transforming the endpoints of each line, using Equations 5-3, and clipping
`arying its position; changing
`
`the line against the viewport boundary.
`In the interests of transforming the
`ormally we shall take care to
`
`‘Picture quickly we naturally wish to speed up the computation, and we can do
`{n Figure 5-14 however, we
`
`So in a couple of ways. Thefirst of these is based on the observation that the
`1e shapesdifferent.
`
`lines in a picture definition are often connected as a sequence of line segments
`oint is very simple. Let us
`with shared endpoints. We can avoid transforming each shared endpoint twice
`"ets x= Wy y = Wyo, and
`
`by comparing the world coordinates ofeach pointandits predecessor.
`'d coordinates, and that the
`A more dramatic improvement in the speed of transformation can be
`“, X= Vyr, y = Vyp, and
`
`gained by transformingonlyvisible lines. Since both window and viewport are
`. the point (xy, yy) in world
`‘ightrectangles, and since both circumscribe the displayed information, we may
`-en coordinates, as follows:
`
`i viewport, a rectangle on the
`3 displayed. In doing so, we
`lip to any right rectangular
`smaller than the screen, for
`item messages, and so forth.
`. separate viewport, as shown
`
`___
`
`
`
`Page 4 of 5
`
`Page 4 of 5
`
`

`

`SannEaiaiees
`
`76 BASIC CONCEPTS
`
`use either of them as a clipping region. The more efficient implementation of
`the windowing transformation thereforeclipsfirst, using the windowas clipping
`region, and then performs the transformation of Equations 5-3 on those lines
`which are at least partially visible. When a small portion of a very large picture
`is being vious the advantage of performing clipping before transformation is
`
`considerable.
`
`EXERCISES
`
`
`
`
`
`
`
`
`
`
`{
`
`§-1 Program the Sutherland-Hodgman polygon clipping algorithm in the language of your choice,
`using recursion if possible.
`5-2 The Sutherland-Hodgman algorithm can be used to clip lines against a nonrectangular
`
`boundary. What uses might this have? What modifications to the algorithm would be necessary?
`
`Whatrestrictions would apply to the shape of the clipping region?
`
`5-3 Some displays possess hardware for displaying circular arcs. Design an algorithm to clip circles
`
`and generate arcs suitable for passing to such a display.
`;
`
`5-4 Extendthe clipping program given on page 66 to perform the complete viewing transformation
`
`ofa line from world coordinates to screen coordinates,
`
`5-5 Application programs often use floating-point numbers to define pictures, whereas the display
`
`uses integers. Should the conversion from floating-point to integer format be done before or after
`
`clipping? How should numbers be rounded? Does the decision whether to clip to the window or
`
`viewport depend on the relative speeds of integer and floating-pointarithmetic?
`5-6 Under what circumstances would midpointclipping be preferable to the use ofthe program on
`
`page 66?
`5-7 Whatadditional logic is needed in the clipping algorithm to keep track oflinked visible line
`
`segments?
`
`5-8 The Cohen-Sutherland clipping algorithm is optimized in favor of clipping pictures much
`
`larger than the window. What features would you look for in an algorithm to clip pictures only
`
`slightly larger than the window? Devise such an algorithm.
`
`5-9 Hand-simulate the polygon clipping alrithm to verify that it produces the same result as shown
`
`in Figure 5-9, Copy the figure of the arrow to graph paper and step through the flow chart of
`Figure 5-11.
`
`
`
`
`
`Page 5 of 5
`
`Page 5 of 5
`
`