United States Patent [19]
`Miller et al.
`
`[54] TEXTURED SPHERE AND SPHERICAL
`ENVIRONMENT MAP RENDERING USING
`TEXTURE MAP DOUBLE INDIRECTION
`
`[75]
`
`Inventors: Gavin S. P. Miller, Mountain View;
`Shenchang E. Chen, Sunnyvale, both
`of Calif.
`[73] Assignee: Apple Computer, Inc., Cupertino,
`Calif.
`
`[21] Appl. No.: 205,137
`Feb.28, 1994
`[22] Filed:
`
`Related U.S. Application Data
`[63] Continuation of Ser. No. 880,240, May 8, 1992, aban(cid:173)
`doned.
`Int. Cl,6 .............................................. G06F 15/72
`[51]
`[52] U.S. CI .. : ................................... 395/125; 395/137
`[58] Field of Search ............... 395/125, 127, 129, 130,
`395/137, 119
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,736,436 4/1988 Yasukawa eta!. .................... 382/16
`4,752,836 6/1988 Blanton eta!. ...................... 358/342
`4,807,158 2/1989 Blanton eta!. ...................... 395/125
`4,821,212 4/1989 Heartz ................................. 395/125
`4,841,292 6/1989 Zeno et al. .......................... 345/121
`4,899,293 2/1990 Dawson et al. ..................... 395/125
`4,935,879 6/1990 Ueda ................................... 395/130
`5,051,734 9/1991 Lake, Jr .............................. 364/731
`5,161,013 11/1992 Rylander et al .................... 395/125
`5,175,808 12/1992 Sayre ................................... 395/125
`5,179,638 1/1993 Dawson et al. ..................... 395/125
`5,204,944 4/1993 Walberg eta!. .................... 395/119
`5,224,208 6/1993 Miller, Jr. eta!. .................. 395/125
`
`OTHER PUBLICATIONS
`Foley, James D. et al., "Computer Graphics: Principals
`and Practice", 2nd ed., 1990, pp. 91, 657, 680,715, 1156.
`Williams, Lance, "Pyramidal Parametrics," Computer
`Graphics, vol. 17, No.3, Jul. 1983 pp. 1-11.
`Greene, Ned, "Environment Mapping and Other Appli(cid:173)
`cations of World Projections," IEEE Computer Graph-
`
`111111111111111111111111111111111111111111111111111111111111111111111111111
`US005446833A
`5,446,833
`[II] Patent Number:
`[45] Date of Patent: Aug. 29, 1995
`
`ics and Applications, vol. 6, No. 11, Nov. 1986, pp.
`21-29.
`Gardner, Geoffrey Y., "Simulation of Natural Scenes
`Using Textured Quadric Surfaces," Computer Graph(cid:173)
`ics, vol. 18, No. 3, Jul. 1984, pp. 11-20.
`Ken Perlin, "An Image Synthesizer," Computer Graph(cid:173)
`ics, vol. 19, No. 3, 1985 pp. 287-296.
`Primary Examiner-Mark R. Powell
`Assistant Examiner-Huynh Ba
`Attorney, Agent, or Firm-Blakely, Sokoloff, Taylor &
`Zafman
`ABSTRACT
`[57]
`A method and apparatus for rendering textured spheres
`and spherical environment maps. The method of the
`present invention provides for real time rotation of a
`textured sphere and panning of the view into a spherical
`environment map, along multiple axes without the need
`for special rendering hardware. A two-level indexing
`scheme for accessing pixel data in a texture map, is used
`to identify shading values for pixels in a display win(cid:173)
`dow. The two-level indexing scheme is comprised of a
`screen look-up table and a parametric look-up table.
`The screen look-up table has the dimensions of the
`display window, whereas the parametric look-up table
`has the dimensions of the parametric sphericai environ(cid:173)
`ment map (wherein the pixel addresses are rotated 90
`degrees from the origin). The method for the present
`invention is comprised primarily of the steps of: provid(cid:173)
`ing a parametric spherical environment map of the
`image to be viewed, generating a screen look-up table
`comprised of look-up addresses, generating a paramet(cid:173)
`ric look-up table comprised of index values into the
`parametric spherical environment map, and for each
`look-up address in the screen look-up table, mapping to
`an entry in the parametric look-up table, retrieving the
`value in the entry, and using the value to retrieve pixel
`values from the parametric spherical environment map.
`Rotation or movement of the view being seen is accom(cid:173)
`plished by adding offsets to the look-up address and/or
`the index values.
`
`22 Claims, 8 Drawing Sheets
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 29, 1995
`Aug. 29, 1995
`
`Sheet 1 of 8
`Sheet 1 of 8
`
`5,446,833
`5,446,833
`
` .Hll
`
`uni-Hull“!!!
`
`GOOGLE EXHIBIT 1008, Page 2 of 18
`
`

`

`U.S. Patent
`
`Aug. 29, 1995
`
`Sheet 2 of 8
`
`5,446,833
`
`FIG_:::-
`
`DATA STORAGE
`DEVICE
`205
`
`KEYBOARD
`206
`
`CURSOR CONTROL
`DEVICE
`207
`
`HARDCOPY
`DEVICE
`208
`
`FRAME
`BUFFER
`209
`
`DISPLAY
`DEVICE
`210
`
`GRAPHICS
`t-----tACCELERATOR
`211
`
`

`

`U.S. Patent
`
`Aug. 29, 1995
`
`Sheet 3 of 8
`
`5,446,833
`
`START
`
`l
`
`GENERATE AND PROVIDE A TEXTURE MAP
`
`GENERATE A SCREEN LOOK-UP TABLE HAVING
`ENTRIES WHICH ARE (U,V) COORDINATES
`CORRESPONDING TO THE DESIRED PROJECTED VIEW
`
`•
`
`~· 301
`
`302
`~:
`
`+
`CORRESPONDING TO THE DIMENSIONS OF THE TEXTURE v
`
`GENERATE A PARAMETRIC LOOK-UP TABLE
`
`MAP, WHERE EACH ENTRY IS AN INDEX INTO THE
`TEXTURE MAP
`
`303
`
`+
`
`FOR EACH PIXEL ENTRY IN THE SCREEN LOOK-UP TABLE,
`USE THE PIXEL ENTRY TO MAP TO AN ENTRY IN THE
`PARAMETRIC LOOK-UP TABLE, ADDING AN OFFSET IF
`THE VIEW IS TO BE ROTATED ABOUT A HORIZONTAL AXIS
`
`:_....--:
`304
`
`~
`TABLE, RETREIVE A PIXEL VALUE FROM THE TEXTURE MAP, v-3
`
`05
`
`USING THE INDEX FROM THE PARAMETRIC LOOK-UP
`
`ADDING AN OFFSET TO THE INDEX IF THE VIEW IS TO BE
`ROTATED ABOUT THE POLAR AXIS OF THE TEXTURE MAP
`
`~
`
`PROVIDE THE PIXEL VALUE TO A DISPLAY BUFFER AT A
`LOCATION CORRESPONDING TO THE PIXEL ADDRESS OF THE r--3 06
`SCREEN MAP
`
`~
`
`END
`
`

`

`U.S. Patent
`
`Aug. 29, 1995
`
`Sheet 4 of 8
`
`5,446,833
`
`:::FIG-~
`
`PARAMETRIC
`LOOK-UP TABLE
`408
`
`TEXTURED
`MAP INDEX
`407
`
`HORIZONTAL
`AXIS 412
`
`HORIZONTAL
`AXIS
`412
`
`HORIZONTAL
`AXIS 412
`
`+U' OFFSET
`409
`
`POLAR
`AXIS
`414
`
`PIXEL VALUE AT
`(U',V') +U' OFFSET
`411
`
`401 POLAR
`AXIS 414
`
`HORIZONTAL
`AXIS 412
`
`POLAR AXIS
`414
`
`TEXTURE MAP
`410
`
`

`

`U.S. Patent
`
`Aug. 29, 1995
`
`Sheet 5 of 8
`
`5,446,833
`
`501
`
`604
`
`F IG_7
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 29, 1995
`Aug. 29, 1995
`
`Sheet 6 of 8
`Sheet 6 of 8
`
`5,446,833
`5,446,833
`
`TIE ___3
`
`
`
`GOOGLE EXHIBIT 1008, Page 7 of 18
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 29, 1995 ‘
`Aug. 29, 1995
`
`Sheet 7 of 8
`Sheet 7 of 8
`
`5,446,833
`5,446,833
`
`Ell} __. El
`
`
`
`905
`
`GOOGLE EXHIBIT 1008, Page 8 of 18
`
`

`

`U.S. Patent
`
`Aug. 29, 1995
`
`Sheet 8 of 8
`
`5,446,833
`
`I'!'IGi _11:::1
`
`:o:F'I~ _ I I
`
`I
`
`I
`
`t/1102
`r----- -x-1101
`;:
`!(
`
`1105
`
`L-----...J
`
`1104
`
`+\.1103
`
`

`

`1
`
`5,446,833
`
`2
`
`Dy=cos (II) cos (cj>)
`
`Dz=sin (II)
`
`TEXTURED SPHERE AND SPHERICAL
`ENVIRONMENT MAP RENDERING USING
`TEXTURE MAP DOUBLE INDIRECTION
`
`5
`
`Typically, a parametric spherical environment map is
`twice as wide as it is high since a sphere is twice the
`distance around the equator as it is from pole to pole.
`All regions are sampled at least as much as at the equa(cid:173)
`tor. Regions near the poles are oversampled. FIG. 1
`10 shows a parametric spherical environment of a museum
`atrium. The parametric spherical environment map
`contains the pixel values which are used to display the
`parametric spherical environment.
`Parametric spherical environment maps have a num(cid:173)
`ber of useful properties.
`The environment is stored in a single contiguous
`image.
`They sample the environment completely.
`Translation along the equatorial direction in the map
`corresponds with rotation about the poles of the
`sphere.
`The environment is always sampled at least as fre(cid:173)
`quently as at the equator.
`Means for viewing a spherical environment map may
`be characterized by the algorithm used for display and
`by the speed with which different degrees of freedom
`for. the view point may be updated.
`KNOWN TECHNIQUES FOR RENDERING
`SPHERICAL ENVIRONMENT MAPS
`A related area to such rendering is termed texture
`mapping. In texture mapping a texture file (or image) is
`applied to points on an object being rendered. This is
`conceptually analogous to putting a decal on a solid
`object. In any event, rendering spherical environment
`maps and textured spheres may be done using a number
`of different known approaches. The most appropriate
`approach for doing this will depend on the number of
`40 degrees of freedom required during an interactive view(cid:173)
`ing session. In any event, when rendering a parametric
`spherical environment map, one may consider the envi(cid:173)
`ronment to be a texture on the surface of a sphere in 3-D
`space. A viewpoint with respect to the sphere will de(cid:173)
`termine what is seen by the viewer. For example, the
`viewpoint may be outside the sphere looking at it as a
`whole, or it may be a perspective view from within the
`sphere.
`
`45
`
`This is a continuation of application Ser. No.
`07/880,240, filed May 8, 1992, abandoned.
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The present invention relates to the field of pixel
`rendering, in particular to the field of rendering tex~
`tured spheres and spherical environment maps.
`2. Description of the Related Art
`Pixel rendering refers to the generation of pixel val- 15
`ues for displaying an image. An environment map is an
`image or collection of images which characterize the
`appearance of a scene when viewed from a particular
`position. Each type of environment map has an associ(cid:173)
`ated projection which is used to compute the appear- 20
`ance along a ray traveling in a particular direction
`towards the camera. Not all types of environment maps
`capture the scene in every direction.
`A variety of different forms of environment maps
`have been used in the past. An orthographic projection 25
`of a reflecting sphere to characterize the illumination of
`a scene is described by Williams in "Pyramidal Para(cid:173)
`metrics", Computer Graphics, Vol. 17, No.3, pgs. 1-11,
`July, 1983. The intention was to use the environment
`map as an aid to the rapid computation of specular 30
`reflections. In an article by Greene entitled "Environ(cid:173)
`ment Mapping and Order Applications of Worlds Pro(cid:173)
`jections", IEEE Computer Graphics and Applications,
`Vol. 6, No. 11, pgs. 21-29, November, 1986, six images
`on the faces of a cube are used for a "cubic environment 35
`map". This mapping was used to resample synthetic
`images of a scene to be redisplayed in the form of an
`Omnimax wide angle lens projection system as well as
`for the computation of reflections.
`Spherical Environment Maps
`There are a number of types of spherical projection
`which may be used to store environment maps. Two are
`of particular interest, namely spherical reflection maps,
`and parametric spherical maps.
`Spherical reflection maps store an image of the envi(cid:173)
`ronment as an orthographic projection of a sphere
`shaded with a perfect reflection of the surrounding
`scene. Typically, these maps are circular images of
`spheres within a square array of pixels. These maps are 50
`useful for the computation of reflections and illumina(cid:173)
`tion when rendering specular surfaces. They do, in fact,
`sample the entire orientation space. However, they
`have the disadvantage that the orientations near the
`silhouette of the sphere are very sparsely sampled. This 55
`renders them unsuitable as a representation for all(cid:173)
`round interactive viewers.
`Parametric spherical environment maps store the
`environment data in a rectangular image where the (x,
`y) coordinates of a pixel, map linearly to points on a 60
`sphere which are defined by the (8, 4>) spherical (or
`angular) coordinates of a corresponding direction vec(cid:173)
`tor.
`The relationship between the direction vector and the
`angular coordinates is given by:
`
`Direct Scan-Con Version
`For the general perspective case, i.e. unrestricted
`directions of manipulation, one approach is to compute
`the analytic form of the intersection between a plane
`(formed by the viewpoint and a scanline) and the
`sphere. In an article entitled "Simulation of Natural
`Scenes Using Textur~d Quadric Surfaces", Computer
`Graphics, Geoffrey Y. Gardner, Vol. 18, No. 3, pgs.
`11-20, July, 1984, such a scheme was used for textured
`ellipsoids. Because the surface texture was a procedural
`texture which only depended on the surface (x, y, z)
`point, the (u, v) parameters for the surface were not
`required. The additional computational requirements
`for the (u, v) values make this general approach suitable
`for a non-real time system, but prohibitive for real-time
`use on personal computers without special rendering
`hardware. Such special hardware may significantly
`increase the cost of the computer system.
`
`65
`
`Dx=COS (II) sin (cj>)
`
`

`

`3
`Texture Map Indirection
`An alternative approach is to restrict the degrees of
`freedom with which the viewer may manipulate the
`sphere. If the sphere is in a fixed position, with a fixed
`size, a technique called texture map indirection may be
`used. The sphere is first rendered into a look-up-table,
`which is the same size as the final image. This is known
`as the screen look-up-table. Each look-up-table pixel
`contains the surface (u, v) value for the rendered sphere. 10
`The "u" index is along the equator; while the "v"
`index is between the poles. When computing the final
`image, the contents of the screen look-up-table are used
`to index into the parametric spherical environment map.
`If this is done directly, this process would always obtain 15
`the same image of the sphere. However, if the sphere u
`index is offset before being used to look up the texture
`value, the spherical texture appears to rotate about an
`axis passing through the poles. This has the effect of
`allowing a single rotational degree of freedom for the 20
`textured sphere or spherical environment. This tech(cid:173)
`nique is similar to that described in an article entitled
`"An Image Synthesizer", Ken Perlin, Computer Graph-
`ics. Vol. 19, No.3, pgs. 287-296, 1985. In the article, the
`shading is being changed for a fixed geometric scene. 25
`OBJECT OF THE PRESENT INVENTION
`It is desirable to provide a rendering means which
`allows for rotation of textured spheres and spherical
`environment maps along multiple axes without the re- 30
`quirement of specialized hardware rendering devices.
`Thus, it is an object for the present invention to provide
`a means for rendering textured spheres and spherical
`environment maps that may be rotated and viewed
`along multiple axes in real-time, and in a cost-effective 35
`manner.
`
`SUMMARY
`A method and apparatus for rendering textured
`spheres and spherical environment maps is disclosed. 40
`The present invention describes a rapid scheme for
`viewing textured spheres and spherical environment
`maps. The intention is to let the user interact with tex(cid:173)
`tured spheres and environment maps in real-time, with
`the view direction and field of view under user control. 45
`The viewing screen is assumed to be flat, such as a
`computer monitor. The real-time interaction may be
`done without the use of any special purpose graphics
`hardware. The method of the present invention pro(cid:173)
`vides for real time rotation along multiple axes. A two- 50
`level indexing scheme for accessing pixel data in a para(cid:173)
`metric spherical environment map (or texture map), is
`used to identify shading values for pixels in a display
`window. The two-level indexing scheme is comprised
`of a screen look-up table and a parametric look-up table. 55
`The screen look-up table has the dimensions of the
`display window, whereas the parametric look-up table
`has the dimensions of the parametric spherical environ(cid:173)
`ment map. The screen look-up table is similar to the
`screen look-up table for texture map indirection except 60
`that it is rotated by ninety degrees, so that the polar axis
`is horizontal. The parametric look-up table is a transfor(cid:173)
`mation of a spheres u,v coordinates having the polar
`axis along the Z axis, to a sphere with u,v, coordinates
`having the polar axis along the Y axis.
`The method for the present invention is comprised
`primarily of the steps of: providing a parametric spheri(cid:173)
`cal environment map of the image to be viewed, gener-
`
`65
`
`5,446,833
`
`4
`ating a screen look-up table comprised of look-up ad(cid:173)
`dresses, generating a parametric look-up table com(cid:173)
`prised of index values into the parametric spherical
`environment map, and for each look-up address in the
`screen look-up table, mapping to an entry in the para(cid:173)
`metric look-up table, retrieving the value in the entry,
`and using the value to retrieve pixel values from the
`parametric spherical environment map. Rotation or
`movement of the view being seen is accomplished by
`adding offsets to the look-up address and/or the index
`values.
`The method of the present invention may be prac(cid:173)
`ticed on a computer system that does not require spe(cid:173)
`cialized rendering hardware. However, certain embodi(cid:173)
`ments of the present invention as described herein may
`derive benefits of dedicated hardware facilities.
`BRIEF DESCRIETION OF THE FIGURES
`FIG. 1 illustrates a texture map, in this case a para(cid:173)
`metric spherical environment map, as may be used by
`the preferred embodiment of the present invention.
`FIG. 2 is a block diagram of a computer system as
`may be utilized by the preferred embodiment of the
`present invention.
`FIG. 3 is a flow chart illustrating the overall method
`of the preferred embodiment of the present invention.
`FIG. 4 illustrates the relationships between the vari(cid:173)
`ous tables, computer screen display, and the texture
`map as utilized by the preferred embodiment of the
`present invention.
`FIG. 5 illustrates the geometry of a sphere for the
`creation of a screen look-up table for orthographic
`projections, as may be utilized in the preferred embodi(cid:173)
`ment of the present invention. The screen look-up table
`corresponds to the screen look-up table of FIG. 4 ro(cid:173)
`tated by ninety (90) degrees in the plane of the screen.
`FIG. 6 illustrates the geometry for the creation of a
`screen look-up table where the view position is at the
`center of the sphere and the viewing direction is in the
`plane of the sphere, as may be utilized by the preferred
`embodiment of the present invention. The screen look(cid:173)
`up table corresponds to the screen look-up table of FIG.
`4 rotated by ninety (90) degrees in the plane of the
`screen.
`FIG. 7 further illustrates the creation of a screen
`look-up table of FIG. 6, in particular, the vertical scan(cid:173)
`lines as planes through a sphere as may be utilized by
`the preferred embodiment of the present invention.
`FIG. 8 is an example of a textured sphere, i.e. a globe,
`as may be rendered using the preferred embodiment of
`the present invention.
`FIG. 9 illustrates the axis of rotation for a textured
`sphere as may be utilized by the preferred embodiment
`of the present invention.
`FIG. 10 is an example of a spherical environment map
`projected onto a viewing plane, where the viewing
`position is at the center of the sphere, i.e. of a museum
`atrium, as may be rendered using the preferred embodi(cid:173)
`ment of the present invention.
`FIG. 11 illustrates the effect of and direction of pan(cid:173)
`ning through a parametric spherical environment map,
`as may be performed by the preferred embodiment of
`the present invention.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`A method and apparatus for rendering textured
`spheres and spherical environment maps, is described.
`
`

`

`5,446,833
`
`6
`system of fixed functionality. For example, it would be
`apparent to one skilled in the art to provide a fixed set
`of screen look-up tables stored in ROM, wherein views
`of data are limited to mappings to the fixed set of screen
`look-up tables. Alternatively, a graphics accelerator, as
`described above, may be designed which embodies the
`present invention.
`
`5
`In the following description, numerous specific details
`are set forth such as the conversion of angular coordi(cid:173)
`nates to dimensional coordinates, in order to provide a
`thorough understanding of the present invention. It will
`be apparent, however, to one skilled in the art that the 5
`present invention may be practiced without these spe(cid:173)
`cific details. In other instances, specific implementation
`details, such as table data structures, have not been
`shown in detail in order not to unnecessarily obscure
`the present invention.
`
`10
`
`OVERVIEW OF RENDERING METHOD OF THE
`CURRENTLY PREFERRED EMBODIMENT
`OVERVIEW OF A COMPUTER SYSTEM IN THE
`The rendering method of the currently preferred
`PREFERRED EMBODIMENT
`embodiment is referred to as texture map double indi-
`The computer system of the preferred embodiment is
`rection. The name is derived from the use of two dis-
`described with reference to FIG. 2. The present inven- 15 tinct maps for identifying pixel values in a texture map
`tion may be implemented on a general purpose mi-
`for rendering a particular object. In a currently pre-
`crocomputer, such as one of the members of the App-
`ferred and implemented embodiment, the texture map is
`le ® Macintosh® family, one of the members of the
`a parametric spherical environment map, such as de-
`IBM Personal Computer family, or one of several
`scribed in the prior art. However, it would be apparent
`work-station or graphics computer devices which are 20 to one skilled in the art to use other forms of a texture
`presently commercially available. In any event, a com-
`map, without departing from the spirit and scope of the
`puter system as may be utilized by the preferred em-
`present invention. In any event, the terms parametric
`bodiment generally comprises a bus or other communi-
`cation means 201 for communicating information, a
`spherical environment map and texture map are used
`processor means 202 coupled with said -bus 201 for 25 interchangeably in this description. FIG. 3 is a flow
`processing information, a random access memory
`chart illustrating the overall flow of the method of the
`(RAM) or other storage device 203 (commonly referred
`preferred embodiment. It is important to note, that it
`to as a main memory) coupled with said bus 201 for
`would be apparent to one skilled in the art that certain
`storing information and instructions for said processor
`steps, namely steps 301-303, could be performed in a
`202, a read only memory (ROM) or other static storage 30 different order. The order in which each of these steps
`device 204 coupled with said bus 201 for storing static
`is presented in FIG. 3 is merely one sequence in which
`information and instructions for said processor 202, a
`they can be performed. First, a texture map, i.e. a para-
`data storage device 205, such as a magnetic disk and
`metric spherical environment map, is generated and
`disk drive, coupled with said bus 201 for storing infor-
`provided to a rendering means, step 301. Next, a screen
`mation and instructions, an alphanumeric input device 35 look-up table is generated, step 302. The screen look-up
`206 including alphanumeric and other keys coupled to
`table will have (u,v) coordinates as entries. As noted
`said bus 201 for communicating information and com-
`previously, the u index is along the equator, whereas the
`mand selections to said processor 202, a cursor control
`v index is between the poles. These (u,v) entries corre-
`device 207, such as a mouse, track-ball, cursor control
`spond to the desired projected view. Typically, the
`keys, etc, coupled to said bus 201 for communicating 40 screen look-up table will be created by rendering the
`information and command selections to said processor
`202 and for controlling cursor movement. Additionally,
`object or perspective of the desired projected view.
`it is useful if the system includeJ> a hardcopy device 208,
`Next, the parametric look-up table is generated, step
`such as a printer, for providing permanent copies of
`3?3. The p~ramet?c look-up table will have (u',.v') coer-
`information. The hardcopy device 208 is coupled with 45 dmate entnes whtch are orthogonal to the destred pro-
`the processor 202 through bus 201.
`jected view of the screen look-up table. The parametric
`Also coupled to the computer system of the preferred
`look-up table will have dimensions which are identical
`embodiment is a frame buffer 2o9 which is further cou-
`to the texture map. Once the foregoing steps have been
`pled to a display device 210, preferably a display device
`completed, an image may be rendered.
`capable of displaying color graphics images or high 50
`Pixel rendering occurs, by identifying a pixel value
`resolution monochrome graphical images. The frame
`for each pixel entry in the screen look-up table. For
`buffer 209 contains the pixel data for driving the display
`each pixel in the screen look-up table, a corresponding
`device 210. In some implementations, the display device
`entry in the parametric look-up table is obtained, step
`210 may be optionally COUP_led to a rendering ~evice
`304. If rotation about a horizontal axis of the displayed
`211, also kn~wn as ~ grap~tcs accelerator. Typically, 55 sphere is desired, an offset is added to the u index of the
`such a re~de~mg d.evtce 2llts coupled to the bus 201 for
`entry from the screen look-up table in order to find the
`commumcat10n wtth the p~ocess~r ~02 and frame buffer
`entry in the parametric look-up table. Using the index
`209. The preferred embodtment ts Implemented for use
`bt · d f
`th
`t · 1 k
`t bl
`· 1
`·1
`·
`h@"
`f
`.1 bl
`f
`o ame
`rom
`e parame nc oo -up a e, a ptxe
`on Macmtos R
`,amt y o computers avat a e rom
`f
`305 If
`h
`t
`t
`· b
`· d
`1
`Apple® Computer, Inc. of Cupertino, Calif.
`60 va u~ rom t e ex ure rna~ ts o tam.e , step
`.
`.a
`It should be noted that the processor 202 performs
`rot~t10n about the. polar axts of the, ~tsplayed sph~re ts
`various parts of the rendering method, such as table
`destred, an offset 1~ added to the u m~ex of the m~ex
`creation and table look-ups. Further, such created tables
`from the ~arametnc look-up table. F~nally, ~he ptxel
`and other data may be stored in RAM 203 (for data that
`value obtamed from the texture map ts provtded to a
`is dynamic in nature), or in data storage device 205 or 65 display buffer at a location corresponding to the pixel
`ROM 204 (for data that is static in nature).
`address described in the screen look-up table, step 306.
`Finally, it should be noted that an alternative embodi-
`As noted above, the foregoing steps 304-306 are re-
`ment of the present invention may be practiced on a
`peated for each pixel entry in the screen look-up table.
`
`

`

`7
`Relationship Between Tables, Texture Map and
`Display
`FIG. 4 illustrates a relationship between the screen
`look-up table, the parame~ric look-up table, the texture 5
`map (i:e., the parametric spherical environment map),
`and the rendered object on a display screen. In this
`illustration a globe is rendered. A screen look-up table
`404 is used to represent a rendered object 402, here a
`sphere, on a display screen 401. In this case the screen 10
`look-up table 404 is for an orthographic projection of a
`sphere. For each surface point 403 on rendered object
`402 a corresponding pixel address 405 exists in screen
`look-up table 404. During rendering, a pixel address 405
`is used to find an entry in a parametric look-up table 15
`408. The parametric look-up table 408 is generated so as
`to flip the "sphere" ninety degrees about an axis perpen(cid:173)
`dicular to a north south vector of the texture map. As
`noted above, the parametric look-up table 408 will con(cid:173)
`tain indices into a texture map, here texture map 410 20
`(here a spherical environment map for a globe). Here,
`the pixel address 405 maps to a texture map index 407.
`The texture map index 407 is used to obtain a pixel value
`in a texture map 410. Here, the texture map index 407,
`indexes the pixel value at (u',v') 411. This pixel value 25
`411 corresponds to the pixel value for the surface point
`403. As noted with reference to FIG. 3, if a rotation
`about a horizontal axis is desired, a u offset 406 is added
`to the u index of the pixel address 405, which is used to
`find the entry in the parametric look-up table 408. Simi- 30
`larly, if rotation about a polar axis is desired, a u' offset
`409 is added to the u' index of the texture map index 407
`which is used to find the pixel value 411.
`Also illustrated in FIG. 4 are the axes of rotation. The
`screen look-up table 404 has a rotation axis 412 which is 35
`horizontal. The creation of the screen look-up table is
`described in more detail below. With respect to the
`parametric look-up table 408, the screen X-axis (screen
`look-up table horizontal axis) 412 is illustrated. Finally,
`a polar axis 414 of texture map 410 is illustrated on 40
`display screen 401. This reflects the ninety (90) degree
`rotation of the orientation of the parametric look-up
`table 408. The horizontal rotation axis 412 is also illus(cid:173)
`trated on the display screen 401.
`Parametric Spherical Environment Map
`Known techniques exist for creating a parametric
`spherical environment map that is utilized in the pre(cid:173)
`ferred embodiment. Thus, no discussion concerning the
`creation of a parametric spherical environment map is 50
`deemed necessary.
`
`45
`
`GENERATION OF THE SCREEN LOOK-UP
`TABLE
`When computing the screen look-up-table, a number 55
`of approaches may be used. The image (e.g., the sphere)
`can be rendered using ray-tracing or scan-conversion
`algorithms. If the sphere size and location and the view(cid:173)
`ing position are unchanged, the table is computed only
`once. If however, some parameters change frequently, 60
`it is beneficial to optimize this calculation. In the pre(cid:173)
`ferred embodiment, two cases are worth considering.
`The first is an orthographic projection of a sphere. The
`second is when the viewing position is at the center of
`the sphere looking at the environment map on the 65
`sphere's surface using a perspective projection.
`It should be noted that the screen look-up table de(cid:173)
`scribed herein may be utilized in the texture map indi-
`
`5,446,833
`
`8
`rection of the prior art or the texture map double indi(cid:173)
`rection of the present invention.
`However, in a single texture map indirection case, the
`axes are flipped so that offsetting the screen table u
`index rotates the sphere about the polar axis which is
`vertical (i.e., screen parallel to the y-axis.).
`Orthographic Projections
`Rendering textured spheres in orthographic projec(cid:173)
`tion is useful in two applications. The first is rendering
`globes of terrestrial or planetary databases. The second
`is when rendering environment maps as if viewed
`through a fish-eye lens. The zoom factor for the render(cid:173)
`ing may change when the user wants to examine the
`center of the spherical projection in more detail, such as
`when zooming in on a globe. This would cause a re(cid:173)
`computation of the screen look-up table.
`FIG. 5 shows the geometry of such a configuration.
`Referring to FIG. 5, a sphere 501 is shown with respect
`to a circle 503 with a set of scanlines. What will be
`computed is how the scanlines intersect with the sphere.
`The screen look-up-table will be used to rotate the
`sphere 501 about a vertical axis 502.
`The symmetry of a sphere in orthographic projection
`has a number of simplifying characteristics. For a hori(cid:173)
`zontal row of pixels, the v parameter (from pole to pole)
`is constant. For each row of pixels, the u parameter
`variation is a scaled version of the variation for the
`central row of pixels. This means that the screen look(cid:173)
`up-table u parameter may be computed very rapidly by
`scaling a 1-D look-up-table for a single scanline.
`The screen look-up-table does not have to be com(cid:173)
`puted exactly because the subsequent table look-up for
`display, will preferably use a method which works with
`nearest pixel arithmetic. Because of this, the inverse sine
`function may be stored as entries in a small inverse sine
`look-up-table to be used in calculating screen look-up
`table entries, negating the need for interpolation.
`TABLE A contains pseudo-code which describes the
`definition of the screen look-up-table for a sphere in an
`orthographic projection. It assumes that the image dis(cid:173)
`played on tile screen is square. In the pseudo-code,"&"
`means logical AND "I" means logical OR, and < <
`means logical left shift.
`TABLE A
`I. Generate an inverse sine look-up table;
`2. zoom = zoom factor for the display of the sphere;
`3. Repeat lines 4 and 5 for each column of the screen
`look-up-table;
`4. normalizedY = (y-coordinate of the scanline -
`halfScreenYSize)/