`
`Page 1 of 5
`
`SONY EXHIBIT 1019
`
`
`
`Library of Congress Cataloging in Publicatitm Data
`
`1939-
`Newman, William M
`Principles of interactive computer graphics.
`
`(Mchme computer science series) (McGrsw-Hill series in artificial
`intelligence)
`Bibliography : 9.
`Includes index.
`
`1. Computer graphics. 2. Interactive computer systems I. Sproull.RobertF..
`joint author.
`[1. Title.
`
`T385.N48 1979
`ISBN 0-07-046338-7
`
`001.55
`
`78-23825
`‘
`
`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.
`
`567890DOD0 83210
`
`The editors were Charles E. Stewart and Frances A. Neal; the production
`supervisor was Dominick Petreliese. RR. Donneiley & Sons Company was
`printer and binder.
`
`
`
`
`Page 2 of 5
`
`Page 2 of 5
`
`
`
`
`
`
`
`..:owl-"hr.--
`
`74 BASIC CONCEPTS
`
`
`
`user messages (3).
`
`“among
`
`Figure 5-13 Use of viewports for map
`display (1). command menu (2). and
`
`5-5 THE WINDDWING TRANSFORMATION
`
`
`
`
`_ = 5-14 'l‘hewindowin,
`
`'
`'
`
`The windowing transformation is so named because it involves specifying a
`window in the world-coordinate space surrounding the information we wish
`dismayed. 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 translatioo we can define a world-
`coordinate point we wish transferran to a certain spot on the screen. say the
`screen center. Each of these methods may prove cenvenient
`in certain
`circumstances: the windowing transformation has the advantage of letting us
`specify directly the rectangle of interest
`in the world-coordinate picture
`definition.
`In addition to the window, we can 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 montages, and so forth.
`Each such part of the picture may be displayed 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 want to 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 window size constant and varying its position; changing
`the window size alters the picture magnification. Normally we shall 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 = Wxg. x = W”, y = W , and
`}: = W” (see Figure 5-14), all measured in world coordinates, and
`t the
`corresponding edges of the viewport are at x = VII, 2: = er, y = if», and
`y = V”, all measured in screen coordinates. Then the point (xw. y”) in world
`coordinates transforms into the point (x, . y,) in screen coordinates. as follows:
`
`
`
`
`
`
`
`»
`'llrese expressions
`
`.7.) within the wi.
`
`(1 corner and i
`viewport. Adding
`
`position of(x,, ys)
`
`.
`: Equations 5-2 redr;
`
`
`
`
`
`tcrefore arrange r
`
`Viewport are definr
`
`.'
`t
`' 3 only two mu]
`
`‘- The complete winr
`
`rimsforming the er
`
`.
`_ he against the vi-
`
`'
`- quickly we nan
`
`.
`I couple of ways.
`
`in a picture defini
`
`dialed endpoints.
`
`..
`_
`r'---
`'ng the work
`
`_ A more dramatic
`
`_
`-- by transforming
`
`males, and sin
`
`xs=a
`
`
`
`Page 3 of 5
`
`Page 3 of 5
`
`
`
` CLIPPING AND WINDowrNG 75
`
`
`gore 5-13 Use of viewporls for map
`splay (1). command menu (2}. and
`er messages (3).
`
`
`
`
`
`‘3'
`
`:4: re 5-14 The windowing transformation.
`
`
`
`er '— V1!
`13 = ———(xw - We) + er
`er — le
`
`yb
`Vyr “'
`J’s = _—"-(yrv _' Wyn) + Vyb
`Wyr _ Wyb
`
`(5‘2)
`
`'
`
`x; = ox... + b
`
`y; = cy”. + d
`
`(5-3)
`
`
`
`
`These expressions are derived by determining the position of the point
`
`: .xw, yw) within the window as a fraction of full displacement from the bottom
`
`' ft-hand corner and interpreting this as 3 Fraction of full displacement across
`
`e viewport. Adding the ofi‘set of the viewport’s bottom left-hand corner gives
`_
`
`e position ofors , ys) on the screen.
`
`Equations 5-2 reduce to the form
`
`
`We therefore arrange to compute the values of a, b. c, and if when the window
`
`In. d viewport are defined. so that we can transform each point by a computation
`
`involving only two multiplications and two additions.
`The complete windowing transformation can then be applied to a picture
`'
`
`day transforming the endpoints of each line, using Equations 5-3, and clipping
`
`"she line against the viewport boundary.
`In the interests of transforming the
`
`{picture quickly we naturally wish to speed up the computation, and we can do
`
`so in a couple of ways. The first of these is based on the observation that the
`
`lines in a picture definition are often connected as a sequence of line segments
`with shared endpoints. We can avoid transforming each shared endpoint twice
`
`Ly comparing the world coordinates of each point and its predecessor.
`
`A more dramatic improvement in the speed of transformation can be
`-
`fly, it = V”. y = Vyb, and
`
`. the point (.icw , y...) in world
`gained by transforming only visible lines. Since both window and viewport are
`
`:en coordinates, as follows:
`‘5 ht rectangles, and since both circumscribe the dismayed information, we may
`
`
`rnsformation from world to
`vent to display; we use the
`hue we can scan over a large
`arying its position; changing
`'orrnally we shall take care to
`in Figure 5-14 however. we
`re shapes different.
`ioint is very simple. Let us
`Ix], x = er,y = W’ub,and
`’d coordinates, and that the
`
`ruse it involves specifying 3.
`mg the information we wish
`rob a transformation can be
`factor and translation to be
`tion we can define a world-
`1 spot on the screen, say the
`rove convenient
`in certain
`
`the advantage of letting us
`.e world-coordinate picture
`
`1 weapon, a rectangle on the
`s 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
`
`
`
`- - -—-_
`
`76 BASIC CONCEPTS
`
`use either of them as a clipping region. The more eificient implementation of
`the windowing transformation therefore clipsfirst, using the window as 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 viewed, the advantage of performing clipping before transformation is
`considerable.
`
`EXERCISES
`
`
`
`
`
`
`
`
`
`
`5-1 Program the Sulherland-Hodgman polygon clipping algorithm in the language of your choice
`using remrsion if possible.
`52 The Sutherland-Hodgman algorithm can be used to clip lines against a nonmetangular
`
`boundary. What uses might this have? What modifications to the algorithm would be necessary?
`
`What restrictions would apply to mediapeof the clipping region?
`
`5-3 Some displays possm hardware for displaying circular arcs. Design an algorithm to ciip eircl
`
`and generate are: suitable for pearls to such a display.
`'
`
`5-4 Extend the clipping program given on page 66 to perform the complete viewing h'ansfomation
`
`ofa line firm] world coordinates to screen wordiuates.
`
`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 site:
`
`clipping? How should numbers be rounded? Does the decision whether to clip to the window or
`
`view-port depend on the relative speeds of integer and floating-point arithmetic?
`'
`5-6 Under what dreumstanees would midpoint clipping be preferable to the use ofthe programon
`
`page 66'?
`5-? What additional logic is needed in the clipping algorithm to keep track of linked visible line
`
`segments?
`
`5-8 The Cohen-Sutherland clipping algorittun is optimized in favor of clipping pictures much
`
`larger than the Window. What features would you look for in an algorithm to clip picture 0111 _
`
`slightly larger than the window? Devise such an algorithm.
`
`5-9 Hand—shoulate the polygon clipping alrithm to verify that it produoes the same result as
`
`in Figure 5-9. Copy the figure of the arrow to graph paper and step through the flow chart »-1.
`
`
`Figure S-lL
`
`
`
`Page 5 of 5
`
`Page 5 of 5
`
`