PROVISIONAL
`APPLICATION
`
`NUM6BEOR I 2
`
`a.
`42(;7
`
`SERIAL NUMBER
`
`FILING DATE CLASS
`
`SUBCLASS
`
`GROUP ART UNIT
`
`EXAMINER
`
`:-(
`
`FOF~F I
`
`FILING
`
`ICENSE GRANTED UO/~G/96
`
`ATTORNEY'S
`DOCKET NO.
`
`U.S. DEPT. OF
`
`PAT. & TM-PT0-436L
`
`Form PT0-1625
`(Rev. 5/95
`
`~~
`
`(FACE)
`
`

`

`PATENT APPLICATION
`IIIII/II/III IIIII lllllllllllllllllllllllllllllllll
`60022428
`
`~--9·------------------
`10. - - - - - - - - - - - - - -
`~-----
`- - - - - - 11. - - - - - - - - - - - - -
`____ 12. - - - - - - - - - - - -
`
`- - - - - - -
`---------
`
`_____ 13. - - - - - - - - - - -
`____ 14. - - - - - - - - - - - - - - - - - - - - (cid:173)
`____ 15. - - - - - - - - - - - - -
`
`____ 16. - - - - - - - - - - -
`
`____ 17. - - - - - - - - - -
`
`- - - - - (cid:173)
`------(cid:173)
`____ 18. - - - - - - - - - - - - -
`- - - - - - - (cid:173)
`- - - -19 . - - - - - - - - - - - - - - - - - - - -
`- - - -20 . - - - - - - - - - - - - - - - - - -
`_____ 21. - - - - - - - - - - - - - - - (cid:173)
`- - - -22 . - - - - - - - - - -
`- - - -23 . - - - - - - - - - - - - - - - - - -
`- - - - -24 . - - -o r - - - - - - - - - - - - -
`- - - -25 . - - - - - - - - - - - - - - - -
`- - - -26 . - - - - - - - - - - - - - - - - -
`- - - -27 . - - - - - - - - - - - - - - - - - -
`___ ___,.._
`- - - - -28 . - - - - - - - - - - -
`- - - -29 . - - - - - - - - - - - - - - - - - - - -
`- - - -30 . - - - - - - - - - - - - -
`
`____ 31. - - - - - - - - - - - - - - - (cid:173)
`____ 32. - - - - - - - - - - -
`
`(FRONT)
`
`

`

`60/0224~8
`PATENT APPLICATION SERIAL NO,_.------
`
`U.S. DEPARTMENT OF COMMERCE
`PATENT AND TRADEMARK OFFICE
`FEE RECORD SHEET
`
`320 EE 09·0468 08/13/96 60022428
`00055 114
`150.00CH YQ996-147
`
`PT0-1556
`(5/87)
`
`

`

`.. ,,llllllllllllllllllllllllllllllllllllllllllll
`
`U.S. PATENT APPLICATION
`
`.RIAL NUMBER
`
`60/022,428
`PROVISIONAL
`
`FILING DATE
`
`CLASS
`
`GROUP ART UNIT
`
`08/05/96
`
`WILLIAM L LUKEN, YORKTOWN HEIGHTS, NY.
`
`**CONTINUING DATA*********************
`VERIFIED
`
`**FOREIGN/PCT APPLICATIONS************
`VERIFIED
`
`FOREIGN FILING LICENSE GRANTED 08/20/96
`STATE OR
`TOTAL
`COUNTRY
`CLAIMS
`
`SHEETS
`DRAWING
`
`INDEPENDENT
`CLAIMS
`
`NY
`
`14
`
`JAY P SBROLLINI
`IBM CORPORATION
`INTELLECTUAL PROPERTY LAW DEPARTMENT
`P 0 BOX 218
`YORKTOWN HEIGHTS NY 10598
`
`FILING FEE
`RECEIVED
`
`ATIORNEY DOCKET NO.
`
`$150.00
`
`Y0996-147
`
`POLYHEDRAL ENVIRONMENT MAP UTILIZING A TRIANGULAR DATA
`STRUCTURE
`
`This is to certify that annexed hereto is a true copy from the records of the United States
`Patent and Trademark Office of the application wh1ch is identified above.
`By authority of the
`COMMISSIONER OF PATENTS AND TRADEMARKS
`
`Date
`
`Certifying Officer
`
`

`

`" .... ,..~,,~"\"
`,//'\\'
`This is a ~guest',for fil~ng a PROVISIONAL APPLICATION under 37 CFR 1.53{b){2).
`/~:.,'
`Y0996-147
`DOCKET
`I
`i
`NUMBER
`
`It\\\"'_::;
`
`''
`;,'\
`
`~f)
`._.(...
`
`'
`
`:;
`
`PRO~,~~:~~~~~A.L..t APPLICATION _:!OV~ .¢tJ!2:f 2 8
`
`Express Mail Label # EM501209916US
`Date of 1' ~»sit: August 5, 1996
`
`Type a plus I+)
`inside this box
`
`+
`
`,_;'...;
`
`INVENTOR{s)/APPLICANT{s)
`~(..
`. "'
`LA~M~E , \·.:~)' FIRST NAME
`..... ~ ·.
`\ ~
`~ Ti'"\'\t.\'>"
`,\f", ··.~·"'/
`.,,
`
`MIDDLE
`INITIAL
`
`RESIDENCE {City and either
`State or Foreign Country)
`
`Luken
`
`William
`
`L.
`
`Yorktown Heights, New York
`
`TITLE OF THE INVENTION {280 characters max)
`
`POLYHEDRAL ENVIRONMENT MAP UTILIZING A TRIANGULAR DATA STRUCTURE
`
`CORRESPONDENCE ADDRESS
`Jay P. Sbrollini; IBM Corporation; Intellectual Property Law Dept.;
`P.O. Box 218; Yorktown Heights, New York 10598
`I New York
`
`ZIP CODE
`
`10598
`
`COUNTRY
`
`STATE
`
`~ Specification
`~ Drawing{s)
`
`ENCLOSED APPLICATION PARTS {check all that apply)
`Number of Pages 130
`Number of Sheets 114
`METHOD OF PAYMENT {check one)
`
`I D Small Entity Statement
`I D Other {specify) 1
`
`0 A check or money order is enclosed to cover
`the Provisional filing fees
`
`PROVISIONAL
`FILING FEE
`AMOUNT
`{$)
`
`USA
`
`I
`
`$150.00
`
`~ The Commissioner is hereby authorized to
`charge filing fees and credit Deposit
`Account Number
`09-0468
`The ~nvent~on was made by an agency of the Un~ted States Government or under a contract w~t
`an agency of the United States Government.
`
`~ No
`0 Yes, the name of the u.s. Government agency and the Government contract number are:
`
`-.
`
`Date: August 5, 1996
`
`Jay P. Sbrollini
`36,266
`
`0 Additional inventors are being named on separately numbered sheets attached hereto.
`PROVISIONAL APPLICATION FILING ONLY
`
`

`

`Atty. Docket No. Y0996-147
`M,~ Q·3?
`MJG -5 fN THEL.UNITED STATES PATENT AND TRADEMARK OFFICE
`pplica;~~"Jf: William L. Luken
`N;.<;~ "-: \l,V·'y"
`"'~-:.:~~/
`Examiner:
`Filed: (Herewith)
`For:
`POLYHEDRAL ENVIRONMENT MAP UTILIZING A TRIANGULAR DATA
`STRUCTURE
`
`Group Art Unit:
`
`Commissioner of Patents and Trademarks
`Washington, D.C. 20231
`
`EXPRESS MAIL CERTIFICATE
`
`"Express Mail" label number: EM501209916US
`Date of Deposit: August 5, 1996
`
`I hereby certify that the following attached paper or fee
`
`Patent Application (Provisional)
`Fourteen ( 14) sheets informal drawings
`Provisional Application Cover Sheet
`Acknowledgement Card
`
`is being deposited with the United States Postal Service "Express Mail Post Office to
`Addressee" service under 37 CFR 1.10 on the date indicated above and is addressed
`to the Commissioner of Patents and Trademarks, Washington, D.C. 20231.
`
`Sandra M. Emma
`(Typed or printed name of person mailing paper or fee)
`
`NOTE: Each paper must have its own certificate and the "Express Mail" label nwnber as a part thereof or attached
`is presented on a separate sheet, that sheet must (1) be slgned and (2)
`thereto. When, as here, the certification
`fully ldentlfY and be securely attached to the paper or fee lt accompanies.
`Identification should include the
`serial nwnber and filing date of the application as well as the type of paper being filed, e.g., complete
`application, specification and drawings, responses
`to rejection or refusal, notice of appeal, etc.
`If the serial
`nwnber of the application is not known, the identification should include at least the name of the inventor(s) and
`the title of the invention.
`It should, however, be placed on the first page of each
`NOTE: The label nwnber need not be placed on each page.
`separate docwnent, such as, a new application, amendment, assignment, and transmittal
`letter for a fee, along
`with the certificate of mailing by "Express Mail". Although the label nwnber may be on checks, such a practice
`In order not to deface formal drawings,
`is not required.
`it is suggested
`that the label nwnber be placed on the
`back of each formal drawing or the drawings be accompanied by a set of informal drawings on which the label
`nwnber is placed.
`
`

`

`Express Mail Label # EM501209916US
`Date of
`it: August 5, 1996
`
`/~·:·-\. i'.
`/: .
`YO 9 9 6 - 1£-~:·
`~,\\1--; -j
`
`t"..'...!'-·
`
`5
`
`10
`
`Polyhedral Environment Map Utilizing
`a Triangular Data Structure
`
`Cross Reference to Related Applications
`
`The present application is related to U.S. Patent
`Application Serial No.
`(Attorney Docket No. Y0996-148), and U.S.
`Patent Application Serial No.
`(Attorney Docket No. Y0996-149),
`both filed concurrently herewith and assigned to the common
`assignee of the present invention, herein incorporated by
`reference in their entirety.
`
`Background of the Invention
`
`15
`
`1.
`
`Technical Field
`
`The invention relates generally to image processing systems,
`and, more particularly, to image processing systems that utilize
`spherical environment maps to create and view three dimensional
`images from data representing multiple views of a scene.
`
`

`

`,
`
`~
`
`YO 996-147
`
`2. Description of the Related Art
`
`5
`
`10
`
`15
`
`20
`
`25
`
`An environment map is a data structure representing the
`colors and/or other information that is characteristic of a set
`of samples defined with respect to a fixed point in space. A
`complete environment contains data for a set of directional
`samples distributed over all possible angles (4n 2 steradians) . A
`partial environment map may represent any subset of the possible
`solid angles. The directional samples are all defined with
`respect to a single point in space which forms the origin or
`center of the environment map.
`
`The data contained in an environment map may be used to
`determine an image that is characteristic of any direction and
`field of view contained within the solid angles represented by
`the environment map. The image is typically composed of a
`rectangular grid of elements or pixels, each of which is
`characteristic of a direction with respect to the origin of the
`environment map. The characteristic direction the elements of
`the image may be associated with one or more directional samples
`of the environment map.
`In the simplest case, known as a point-
`sampled image, each element of the image is associated with the
`single sample of the environment map that corresponds to a
`direction that most closely matches the direction associated with
`the element of the image. More elaborate sampling and filtering
`techniques are also possible in which each element of the image
`is associated with multiple samples of the environment map that
`corresponds to directions that match the directions associated
`with the element of the image.
`
`An environment map may also be used to approximate the
`effects of light reflected by the surface of a three dimensional
`
`- 2 -
`
`

`

`YO 996-147
`
`object located at or near the origin of the environment map. For
`example, consider a point on a three dimensional object which is
`characterized by coordinates (xp,yp,zp) and a unit normal vector
`N.
`In order to generate a view of the object from a direction
`DO,
`the color associated with the object at the coordinates
`(xp,yp,zp) may be determined partly or entirely by the values of
`the environment associated with the
`Direction De= D - 2N*(N o D).
`
`In principle, any set of flat or curved surfaces may be used
`to define an environment map. For example, the QuicktimeVR
`product from Apple Corp of Cupertino, CA, utilizes a cylindrical
`environment map to support panoramic image generation and the
`RenderMan product from Pixar Animation Studios of Port Richmond,
`California uses both spherical environment maps and environment
`maps based on six sides of a cube. All of these examples take
`advantage of the ability to represent the constituent surfaces
`with a rectangular two dimensional coordinate system. The
`cylindrical environment map is based on azimuth and elevational
`coordinates. The spherical environment map uses latitude and
`longitude coordinates. The cube-face environment map utilizes
`standard row and column addressing for each of the six faces of
`the cube.
`
`Each of these environment maps have distinct limitations
`that restrict their usefulness.
`
`The spherical environment map has an inefficient
`distribution of samples with higher densities of samples near the
`poles of the sphere than around the equator of the sphere.
`In
`principle, a sphere treats all directions is space equally.
`However, imposition of a latitude and longitude coordinate system
`
`5
`
`10
`
`15
`
`20
`
`25
`
`- 3
`
`-
`
`

`

`YO 996-147
`
`on a sphere breaks this symmetry and requires designation of a
`preferred axis (i.e., the polar axis) in space. This leads to
`unequal treatment of the polar regions with respect to the
`equatorial regions. The use of latitude and longitude coordinate
`system also tends to require frequent evaluation of trigonometric
`functions which may be prohibitively intensive for use in some
`applications and/or systems.
`
`More specifically, the choice of the direction of the polar
`axis of the spherical environment map is completely arbitrary;
`and, after choosing the direction of the polar axis, the
`resulting combination of a sphere and polar axis no longer has
`the full symmetry of the sphere itself. Only the symmetry of a
`cylinder remains. Thus, it is possible to rotate the sphere and
`polar axis combination about the polar axis without changing the
`polar axis, but rotating this combination about any other
`direction moves the polar axis. Moving the polar axis is
`equivalent to choosing a new polar axis, and this does not
`preserve the original polar axis choice.
`
`After choosing a polar axis, a latitude and longitude
`coordinate system may be defined. The latitude and longitude
`coordinate system include an angle e running from ~/2 at one pole
`to -~/2 at the other pole, and a second (azimuthal) angle ~
`running from 0 to 2~ starting at some arbitrary direction
`perpendicular to the polar axis. The resulting lines of constant
`e and constant ~ converge on the poles. Near the 11 equator 11
`(the
`line with 8=0), the lines of constant e and ~ form a rectangular
`grid. Near the poles, however, the lines of constant 8
`(latitude) form concentric circles around the poles, and lines of
`constant ~ (longitude) form spokes radiating from the poles. The
`circles and spokes patterns seen near the poles is quite distinct
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`- 4 -
`
`

`

`YO 996-147
`
`from the grid pattern seen near the equator, but the underlying
`sphere has exactly the same shape in both regions. The circles
`and spokes patterns seen near the poles are not properties of the
`sphere itself. These are only consequences of the arbitrary
`decision to impose a polar axis on the sphere.
`
`In contrast, the cylindrical and cube-face environment maps
`have relatively uniform distributions of directional samples.
`However, the cylindrical environment is open at both ends which
`prevents it from being used for view directions approaching the
`axis of the cylinder. The ends of the cylinder may be capped
`with additional top and bottom images as set forth in u.s. Patent
`Application No. (Attorney Docket No. Y0996-148), filed
`concurrently herewith and commonly assigned to the assignee of
`the present application, incorporated by reference above in its
`entirety. However, the resulting data structure requires special
`treatment for directions having elevations above, within, or
`below the cylindrical data.
`In addition, the algorithms required
`for viewing the top and bottom images may be more laborious than
`the algorithms required to view the data within the cylindrical
`region.
`
`With respect to the cube-face environment map, the
`algorithms required to determine which faces of the cube are
`intersected by the viewing frustrum are computationally
`intensive, and may impact the performance of the system.
`
`Thus, there is a need in the art to provide for an efficient
`system for generating and viewing three dimensional panoramic
`images based environment maps, and thus provide an improved level
`of interactive graphical feedback.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`- 5 -
`
`

`

`YO 996-147
`
`Summary of the Invention
`
`The above-stated problems and related problems of the prior
`art are solved with the principles of the present invention,
`polyhedral environment map utilizing a triangular data structure.
`
`5
`
`Brief Description of the Drawings
`
`FIG. 1 is a functional block diagram of a computer
`processing system that may be utilized by the preferred
`embodiment of the present invention.
`
`FIG. 2 is a pictorial illustration of a rectangular data
`structure.
`
`10
`
`FIG. 3 is a pictorial illustration of a triangular data
`structure.
`
`FIG. 4 is a pictorial illustration of the eight faces of an
`octahedral environment map.
`
`FIG. 5 illustrates the mapping of the triangular data
`structure of FIG. 3 to each of the eight faces of the octahedral
`environment map of FIG. 4 according to the present invention.
`
`FIGS. 6(A) and (B) illustrate six rectangular images that
`may be mapped to the octahedral environment map of the present
`invention.
`
`15
`
`20
`
`FIG. 7 is a flow chart illustrating operation of mapping the
`rectangular images of FIGS. 6(A) and (B)
`to the octahedral
`environment map of the present invention.
`
`- 6 -
`
`

`

`YO 996-147
`
`FIG. 8 is a flow chart illustrating the operation of
`generating the direction vectors DO,D1, ... D7 for a given pixel
`element of the faces of the octahedral environment map.
`
`FIG. 9 is a flow chart illustrating the operation of
`determining the rectangular image intersected by each of the
`direction vectors DO,D1 ... D7, and for determining the pixel of
`the intersected image that corresponds to each of the direction
`vectors DO,D1 ... D7.
`
`FIG. 10 is a flow chart illustrating operation of the system
`in rendering the polyhedral environment map of the present
`invention for display.
`
`FIG. 11 illustrates the relationship of the view vector, up
`vector and right vector with respect to the eye.
`
`5
`
`10
`
`15
`
`FIG. 12 illustrates the relationship between the view
`vector, right vector, eye, horizontal field of view and the
`viewing window.
`
`FIG. 13 illustrates the relationship between the view
`vector, up vector, eye, vertical field of view and the viewing
`window.
`
`20
`
`FIG. 14 is a flow chart illustrating the operation of
`mapping the polyhedral environment map of the present invention
`to the view window.
`
`FIG. 15 illustrates the ncol columns of the view plane and
`the horizontal step vector.
`
`- 7 -
`
`

`

`YO 996-147
`
`FIG. 16 illustrates the nrow rows of the view plane and the
`vertical step vector.
`
`FIG. 17 illustrates the direction vectors that correspond to
`the elements of the view window, and the relationship of the
`horizontal and vertical step vectors of FIGS. 15 and 16 to such
`direction vectors.
`
`5
`
`Detailed Description of the Present Invention
`
`A method and apparatus for generating an image from a
`polyhedral environment map that utilizes a triangular data
`structure is set forth herein. The present invention may be
`implemented on any computer processing system including, for
`example, a personal computer, a workstation, or a graphics
`adapter that works in conjunction with a personal computer or
`workstation. As shown in FIG. 1, a computer processing system as
`may be utilized by the present invention generally comprises
`memory 101, at least one central processing unit (CPU) 103 (one
`shown), and at least one user input device 107 (such as a
`keyboard, mouse, joystick, voice recognition system, or
`handwriting recognition system).
`In addition, the computer
`processing system includes non-volatile storage, such as a read
`only memory (ROM), and/or other non-volatile storage devices 108,
`such as a fixed disk drive, that stores an operating system and
`one or more application programs that are loaded into the memory
`101 and executed by the CPU 103.
`In the execution of the
`operating system and application program(s), the CPU may use data
`stored in the non-volatile storage device 108 and/or memory 101.
`
`10
`
`15
`
`20
`
`25
`
`In addition, the computer processing system includes a frame
`buffer 104 coupled between the CPU 103 and a display device 105
`
`- 8 -
`
`

`

`YO 996-147
`
`such as a CRT display or LCD display. The frame buffer 104
`contains pixel data for driving the display device 105.
`In some
`systems, a rendering device (not shown), also known as a graphics
`accelerator, may be coupled between the CPU 103 and the frame
`buffer 104.
`
`In addition, the computer processing system may include a
`communication link 109 (such as a network adapter, RF link, or
`modem) coupled to the CPU 103 that allows the CPU 103 to
`communicate with other computer processing systems over the
`communication link, for example over the Internet. The CPU 103
`may receive portions of the operating system, portions of the
`application program(s), or portions of the data used by the CPU
`103 in executing the operating system and application program(s).
`
`It should be noted that the application program(s) executed
`by the CPU 103 may perform the rendering methods of the present
`invention described below. Alternatively, portions or all of the
`rendering methods described below may be embodied in hardware
`that works in conjunction with the application program executed
`by the CPU 103.
`
`What will now be described is the polyhedral environment map
`that utilizes a triangular data structure, techniques for
`creating such a polyhedral environment map, and techniques for
`rendering views of such polyhedral environment maps.
`
`In order to illustrate a polyhedron environment map that
`utilizes a triangular data structure, first consider a
`conventional rectangular array. As shown in FIG. 2, a
`rectangular array includes data values stored in a computer's
`memory as nrow successive blocks of memory each having ncol
`
`5
`
`10
`
`15
`
`20
`
`25
`
`- 9 -
`
`

`

`YO 996-147
`
`elements. The address of any element may be calculated as
`follows:
`
`A(i,j) = address of A(O,O)
`
`+
`
`(size of each element)*(i + j*(ncol)),
`
`5
`
`10
`
`15
`
`20
`
`25
`
`where i and j represent the column and row of the
`element, respectively.
`
`In order to find the data for the element (i, j), one must know
`the column dimension (ncol), as well as the values of (i) and
`( j ) .
`
`A triangular data structure is illustrated in FIG. 3.
`Instead of every row having ncol elements, the first row has one
`element, the second row has two elements, etc. Like the
`rectangular array, a triangular array is mapped into linear
`memory using a well-defined algorithm. The triangular array,
`however, uses a different algorithm. Thus the location of
`element T(i,j) is determined as follows:
`
`T(i,j) = address of T(O, 0) +
`(size of each element)*(i + j*(j+1)/2),
`
`where i and j represent the column and row of the
`element, respectively.
`
`Unlike the rectangular array, this does not have independent row
`and column dimensions.
`In effect nrow=ncol. Moreover, unlike
`the rectangular array, it is not necessary to know the array
`dimension(s) to find the address of any array element (Since the
`address of the element is based on j*(j+1)/2 instead of j*ncol.
`
`- 10 -
`
`

`

`YO 996-147
`
`Moreover, because j and j+1 are successive integers, one is even
`and one is odd, so the product j*(j+1) is always even and exactly
`divisible by 2. In addition, the values of j*(j+1)/2 may be
`stored in an array to reduce the number of operations needed to
`generate an address for an element of the array.
`
`According to the present invention, a polyhedral environment
`map is provided that utilizes a triangular data structure to
`store the information related to the elements of each facet of
`the polyhedral environment map. For the sake of description, an
`octahedral environment map that utilizes such a triangular data
`structure is set forth below. However, the present invention is
`not limited in this respect and can be applied to other
`polyhedral environment maps, for example environment maps based
`on a tetrahedron or an icosahedron. However, the use of a
`triangular data structure for the octahedral environment map is
`particularly advantageous in terms of limiting the computations
`required to determine which face of the octahedron is associated
`with a given direction vector (i.e., look at the signs of the x,
`y, and z values).
`
`FIG. 3 shows an octahedron with its eight faces and the
`three coordinate axes x,y,z. Each coordinate axis is divided
`into (+) and (-) directions associated with the six vertices of
`the octahedron. FIG. 4 shows the eight faces of the octahedron
`with corners labelled by the corresponding coordinate axes and
`directions. Each face is partitioned into a triangular grid of
`elements (or pixels) , for example a 4X4 triangular grid of
`elements as shown. For each element of the grid of elements, the
`triangular data structure preferably stores information that is
`associated with the element. The information preferably includes
`color data that identifies the color of the element. The color
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`- 11 -
`
`

`

`YO 996-147
`
`data may represent the red, green and blue components of the
`color of the pixel (true color) or an index to a color palette
`(palette color). The information stored for a given element may
`also include Z data that represents the depth of the image at the
`given element.
`In addition, the information stored for each
`pixel may include additional data related to the element. For
`example, the data may be actions related to the element,
`including, but not limited to, a hyperlink to another panorama, a
`command to play a sound, or a command to launch an external
`application.
`
`Having described a octahedral environment map that utilizes
`a triangular data structure to store the information related to
`the elements of each facet of the octahedron, a technique to map
`six rectangular images to the octahedral environment map of the
`present invention is now set forth with reference to FIG. 7.
`Preferably, the six rectangular images are faces of an
`axis-aligned rectangular solid as shown in FIG. 6(A). The six
`images will be referred to as the top image, bottom image, and
`four side images (side 0, side 1 side 2 and side 3). FIG. 6(B)
`is a top view of xy plane of the rectangular solid of FIG. 6(A)
`illustrating the four side images. Side 0 is on the positive x
`axis, side 1 along the positive y axis, side 2 along the negative
`x axis, and side 3 along the negative y axis.
`
`As shown in FIG. 7, the operation of mapping the six
`rectangular images to the octahedral environment map of the
`present invention begins in step 701 by selecting a row index
`irow.
`In step 703 a column index icol is selected. The value of
`irow runs from 0 to nrow-1 where nrow is the dimension of the
`triangular arrays comprising the octahedron. For each value of
`irow, the value of icol runs from 0 to irow. Each pair of irow
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`- 12 -
`
`

`

`."""""
`
`YO 996-147
`
`and icol values identifies a pixel in each face of the
`octahedron.
`
`In step 705, for each face of the octahedron, a direction
`vector is generated that corresponds to the pixel (irow,icol) in
`the particular face of the octahedron. Preferably, the direction
`vector corresponding to the pixel (irow,icol) represents the
`direction from the origin of the octahedron to the pixel (irow,
`icol). Moreover, the direction vector preferably has the form
`D = (SxDx,SyDy,SzDz) where Sx,Sy,Sz corresponds to a particular
`face of the octahedron and Dx,Dy,Dz corresponds to a particular
`pixel in the faces of the octahedron. Preferably Sx,Sy,Sz is
`mapped to the faces of the octahedron as follows:
`
`Face
`---------------
`FO
`(+x,+y,+z)
`(- x, +y, +z)
`F1
`F2 (-x, -y,+z)
`F3 (+x,-y,+z)
`F4 (+x,+y, -z)
`(-X, +y, - Z)
`F5
`F6 (-x, -y, -z)
`(+x, -y, -z)
`F7
`
`Sx
`
`1
`-1
`- 1
`1
`1
`-1
`-1
`1
`
`Sy
`
`1
`1
`- 1
`-1
`1
`1
`- 1
`-1
`
`Sz
`
`1
`1
`1
`1
`- 1
`- 1
`- 1
`- 1
`
`5
`
`10
`
`15
`
`20
`
`This results in the generation of eight direction vectors
`DO,D1,D2 ... D7 that correspond to the pixel (irow,icol) in each
`of the eight faces of the octahedron where
`
`25
`
`DO = (Dx,Dy,Dz)
`D1 = (- Dx, Dy, Dz)
`D2 = (- Dx, - Dy, Dz)
`
`- 13 -
`
`

`

`5
`
`10
`
`15
`
`20
`
`25
`
`YO 996-147
`
`D3 = (Dx, -Dy,Dz)
`D4 = ( Dx, Dy, - D z)
`D5 = (-Dx,Dy,-Dz)
`D6 = (- Dx, - Dy, - Dz)
`D7 = ( Dx, - Dy, - D z)
`
`An example of a technique that generates the components Dx,Dy,Dz
`of the direction vectors DO,D1,D2 .. D7 is set forth below with
`respect to FIG. 8.
`
`In step 707, for each of the eight direction vectors
`DO,D1,D2 .. D7, it is determined which of the six rectangular
`images is intersected by the direction vector Di (where i ranges
`from 0 to 7), and which pixel of the particular rectangular image
`intersected by the direction vector Di corresponds to the
`direction vector Di. An example of a technique to identify the
`pixel of the rectangular image that corresponds to the direction
`vector Di is set forth below with respect to FIG. 9.
`
`In step 711, for each direction vector Di, the color value
`of the pixel of the rectangular image that corresponds to the
`direction vector Di is stored as the color value of the pixel
`(irow,icol) of the face Fi of the octahedral environment map,
`where face Fi corresponds to the direction vector Di.
`
`In step 713, it is determined if the last column (icol=irow)
`of the row (irow) of the faces of the octahedron has been
`processed in steps 705-711.
`If not, operation returns to step
`703 to select the next column index in the range. As described
`above, the column index ranges from 0 to irow. Otherwise,
`operation continues to step 715.
`
`- 14 -
`
`

`

`5
`
`10
`
`15
`
`20
`
`25
`
`YO 996-147
`In step 715, i t is determined if the last row (irow=nrow-1)
`of the faces of the octahedron has been processed in steps 705-
`If not, operation returns to step 701 to select the next
`711.
`row index in the range. As described above, the row index ranges
`from 0 to nrow-1. Otherwise, when the last row of the faces of
`the octahedron have been processed, the operation ends.
`FIG. 8 illustrates a technique for generating the components
`Dx,Dy,Dz of the direction vectors DO,D1,D2 .. D7 for the pixel
`identified by the indices (irow,icol). The operation begins in
`step 801 by checking whether the indices (irow,icol) are set to
`(0,0), thus indicating that the current pixel is the initial
`If in step 801 the indices
`pixel of the faces of the octahedron.
`(irow,icol) are set to (0,0), operation continues to step 803
`where the components Dx,Dy,Dz are initialized to values 0,0,1,
`respectively and the operation ends.
`If in step 801 the indices (irow,icol) are not set to (0,0),
`operation continues to step 805 to check whether the index icol
`thus indicating that the current pixel is located at
`is set to 0,
`the beginning of the row irow on the faces of the octahedron.
`If in step 805, i t is determined that the index icol is set
`then in step 807 the components Dx,Dy,Dz of the current
`to 0,
`pixel are set as follows:
`
`(1/(nrow-1))
`
`=
`=
`=
`
`DzN·l-
`- DZN
`1
`0
`
`where DxN, DyN, DzN are the Dx,Dy,Dz components for the
`is the Dz component
`current pixel (irow,icol) and DzN·l
`
`- 15 -
`
`

`

`YO 996-147
`
`for the pixels of the previous row, which is identified
`by the row index (irow=irow-1).
`
`If in step 805 it is determined that the index icol is not
`set to 0, then in step 809 the components are set as follows:·
`
`DyN =
`
`(1/(nrow-1))
`DYN-l + ( 1/ (nrow-1) )
`
`where DxN, DyN, DzN are the Dx,Dy,Dz components for the
`current pixel ( irow, icol) and DxN_ 1 , DyN_ 1 , DzN. 1 are the
`Dx,Dy, Dz components for the previous pixel, which is
`identified by the indices (irow,icol-1).
`
`FIG. 9 illustrates a technique for identifying the pixel of
`the rectangular image that correspond to the direction vectors
`DO,D1 ... D7, respectively. This example assumes that the top
`and bottom images are square and all four side images have an
`aspect ratio AR. As described above, the direction vectors
`DO,D1, ... D7 are composed of the components Dx,Dy,Dz as follows:
`
`DO = (Dx, Dy, Dz)
`D1 = ( -Dx, Dy, Dz)
`( - Dx, - Dy, Dz)
`D2 =
`D3 = (Dx, -Dy,Dz)
`D4
`(Dx,Dy, -Dz)
`(- Dx, Dy, - Dz)
`D5 =
`D6 = ( -Dx, -Dy, -Dz)
`D7 =
`(Dx, -Dy, -Dz)
`
`The operation begins in step 901 by comparing Dx to Dy.
`
`If Dx is
`
`- 16 -
`
`5
`
`10
`
`15
`
`20
`
`25
`
`

`

`YO 996-147
`
`greater than Dy, the operation continues to step 903; otherwise,
`the operation continues to step 905.
`
`In step 903, Dz is compared to the product Dx*AR.
`If in
`step 903 it is determined that Dz is greater than the product
`Dx*AR, then:
`
`5
`
`DO,D1,D2,D3 intersect the top image, and
`
`D4,D5,D6,D7 intersect the bottom image.
`
`The operation then continues to the processing of case 1 as set
`forth below to determine, for each direction vector Di, the pixel
`within the top or bottom image intersected by the direction
`vector Di that corresponds to the direction vector Di.
`
`10
`
`If in step 903 it is determined that Dz is less than or
`equal to the product Dx*AR, then:
`
`DO,D3,D4,D7 intersect side 0, and
`
`15
`
`D1,D2,D5,D5 intersect side 2.
`
`The operation then continues to the processing of case 2 as set
`forth below to determine, for each direction vector Di, the pixel
`within side 0 or side 2 intersected by the direction vector Di
`that corresponds to the direction vector Di.
`
`20
`
`In step 905, Dz is compared to the product Dy*AR.
`If in
`step 905 it is determined that Dz is greater than the product
`Dy*AR, then:
`
`- 17 -
`
`

`

`YO 996-147
`
`DO,D1,D2,D3 intersect the top image, and
`
`D4,D5,D6,D7 intersect the bottom image.
`
`The operation then continues to the processing of case 3 as set
`forth below to determine, for each direction vector Di, the pixel
`within the top or bottom image intersected by the direction
`vector Di that corresponds to the direction vector Di.
`
`5
`
`If in step 905 it is determined that Dz is less than or
`equal to the product Dy*AR, then:
`
`DO,D1,D4,D5 intersect side 1, and
`
`10
`
`D2,D3,D6,D7 intersect side 3.
`
`The operation then continues to th