JP3149389B2 - Method and apparatus for overlaying a bitmap image on an environment map - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates generally to image processing systems, and more particularly, to enabling a user to create and view panoramic three-dimensional images from data representing multiple views of a scene. To an image processing system.

[0002]

2. Description of the Related Art Conventional three-dimensional graphics applications and associated hardware render a scene consisting of one or more three-dimensional objects. Objects are typically represented by geometric primitives, such as triangles. Objects are represented as graphics data representing the position and color of primitives in a model coordinate system. The graphics system renders the scene based on the view point, displaying scene objects as seen in the view window. The user can cruise through the scene by changing the position and orientation of the view point reference (camera). In addition, by cruising through a series of preselected positions and orientations of the view point reference,
Animations can also be performed.

[0003] The rendering operation is a computer intensive process, and is therefore typically performed by specialized graphics hardware. While such systems are powerful, they are still expensive due to the need for specialized hardware dedicated to this purpose.

In addition, in conventional three-dimensional graphics systems, the user has a three-dimensional model of the scene (ie, graphics data representing the positions and colors of the scene's geometric primitives in the model coordinate system). Must be provided. Such models can be created using software with peripheral devices (pen tablets, scanners, cameras, etc.). For example,
Software sold under the trade name CATIA by the French company Daussault allows users to construct a three-dimensional model of the scene. However, such modeling software is expensive and, in addition, modeling even less complex scenes can require a significant investment in labor.

[0005] Due to the high cost associated with conventional three-dimensional graphics systems, dedicated graphics hardware that is effective in creating and viewing three-dimensional scenes but provides limited capabilities. An alternative solution has emerged that is suitable for use on a standard personal computer without the need for hardware. One such method is Ap
Software developed and sold by ple Computer under the brand name Quicktime VR. Quicktime VR
The software is divided into two separate packages. The first package sold to content providers is a teaching aid development tool that allows content providers to generate panoramic 3D images from multiple views of a scene. The second package is a viewer that is distributed to the consumer and allows the consumer to view a panoramic three-dimensional image created by the educational material development support tool. Quicktime VR
For a more detailed description of the operation of the system, see Chen's Quicktim
e VR-An Image-based Approach to Virtual Environment
ent Navigation '' SIGGRAPH 1995, Los Angeles, CA, p
p. 29-38 and U.S. Patent No. 5,396,583 to Chen et al., assigned to Apple Computer.

[0006]

The Quicktime VR system uses a cylindrical environment map to represent a panoramic view of a scene (collection of images). Render different perspective views by mapping the cylindrical environment map to the desired view window. But,
One of the limitations of the Quicktime VR system is that it does not have the ability to integrate a bitmap image separate from the cylindrical environment map into a panoramic scene.

[0007] Therefore, there is a need in the art to provide a cost effective system for generating and viewing three-dimensional panoramic images that can integrate a bitmap image into a panoramic image.

[0008]

SUMMARY OF THE INVENTION The above and related problems associated with the prior art include the color values associated with elements of an environment map representing a scene, and the elements of a bitmap image that are separate from the environment map. The problem is solved by the principles, methods and apparatus of the present invention for overlaying a bitmap image on an environment map, which creates a view of the scene by storing associated color values in a memory. Orient the bitmap image to the environment map coordinate system. Project the environment map into a view window that contains an array of pixels. At least one of the view windows covered by the bitmap image
Pixels, corresponding to the pixels in the view plane,
Determine the elements of the bitmap image and derive the color values of the pixels based on the color values of the corresponding elements of the bitmap image. The derived color values of the pixels of the view window are stored for display.

The present invention also stores in memory a depth value associated with an element of the bitmap image and a depth value associated with a pixel of the view window. In this scenario, when the depth value associated with the pixel and the depth value associated with the element indicate that the element of the bitmap image is closer to the view point than the pixel of the view window, the pixel of the view window Color value of
Derived from the color values of the corresponding elements of the bitmap image, and the derived color values of the pixels are stored for display.

[0010]

DETAILED DESCRIPTION OF THE INVENTION A method and apparatus for generating a panoramic scene from a cylindrical environment map including data defining the top and / or bottom of the cylindrical environment is described below.

The data representing the top and bottom images can be divided into two parts based on circles determined by the minimum and maximum elevation angles, respectively. That is, the top image can be divided into two regions based on a circle determined by the maximum elevation angle,
The bottom image can be divided into two regions based on a circle determined by the minimum elevation angle. The minimum and maximum elevation angles can be determined, for example, by the elevation angles corresponding to the upper and lower edges of the center of the side image. The image data values in the top and bottom image areas located outside these circles are:
When mapped to the cylindrical environment map, it fills the area indicated by X and * in FIG. 12 and additional areas beyond the top and bottom of FIG. 12, so that the vertical height values accessible by the cylindrical environment map Prolong. Hereinafter, a method of integrating the top image and / or the bottom image into the cylindrical environment map will be described in more detail.

The amount of data required to store each portion of the cylindrical environment map increases in proportion to the tangent of the maximum and minimum height maps, such as for maximum and minimum elevation angles greater than 60 °. May become impossible to implement.
Without a top and / or bottom image, extension to a range of height values is not possible.

The image data values in the top and bottom image regions located inside these circles need not be mapped to the cylindrical environment map. Alternatively, these data values can be accessed during the image projection process to further extend the range of height values, which can be used to visualize the data represented by the cylindrical environment map. Can be assisted by the means being done. That is, the color value of a pixel in the projected image corresponding to a height value that exceeds the maximum or minimum height value is determined by the top and bottom angles determined by the minimum and maximum elevation angles.
It can be derived directly from inside the circular area of the image and / or the bottom image. Without the top and bottom images, it is not possible to generate a projection image that depends on such extended height values.

The present invention can be implemented in any computer processing system, including, for example, a personal computer, a workstation or a graphics adapter working with a personal computer or workstation. As shown in FIG. 1, a computer processing system that can be used in accordance with the present invention includes a memory 101 and at least one
Central processing units (CPUs) 103 (one in the figure),
At least one user input device 107 (eg, a keyboard, mouse, joystick, voice recognizer or handwriting recognizer). In addition, the computer processing system may include a non-volatile memory, such as a read only memory (ROM) and / or other non-volatile storage 1
08, including, for example, a fixed disk drive that stores an operating system and one or more application programs loaded into memory 101 and executed by CPU 103. operating·
When executing the system and application programs, the CPU can use the data stored in the nonvolatile storage device 108 and / or the memory 101.

In addition, the computer processing system has a C
It includes a frame buffer 104 coupled between the PU 103 and a display 105, for example, a CRT display or LCD display. Frame buffer 104 includes pixel data for driving display device 105. In some systems, a rendering device (not shown), also known as a graphics accelerator, may be coupled between CPU 103 and frame buffer 104.

Further, the computer processing system may include C
A communication link 10 coupled to the PU 103 that allows the CPU 103 to communicate with other computer processing systems via a communication link, such as the Internet.
9 (e.g., a network adapter, RF link or modem). The CPU 103 executes the operating system part, the application program part, or the operating system and the application program.
3 can receive a portion of the data used.

An application program executed by the CPU 103 can execute the rendering method of the present invention described below. Alternatively,
Some or all of the rendering methods described below,
It may be embodied in hardware that operates together with an application program executed by the CPU 103.

Described next is a cylindrical environment map that includes data defining the top and / or bottom of a cylindrical environment, and techniques for rendering views of such a cylindrical environment map.

A cylindrical environment map is a rectangular array of elements or pixels, each pixel being a portion of a three-dimensional scene contained within a thin pyramid defined by the origin of the cylindrical axis and a rectangular area on the cylindrical surface. Consists of an array that contains data representing

FIG. 2 shows the cylinder, the cylinder axis and the origin of the cylinder axis. The second coordinate axis is perpendicular to the cylinder axis and is determined by a line passing through the origin of the cylinder. The third coordinate axis is perpendicular to both the cylindrical axis and the second coordinate axis, and is similarly determined by a line passing through the origin of the cylindrical axis.
Any point in the plane defined by the second and third coordinate axes is defined as having its height zero. The height of the other points is defined by the distance to the plane determined by the second and third coordinate axes, points above this plane are assigned a positive height and are on the opposite side of this plane Points are assigned a negative height.

FIG. 3 illustrates a method of dividing a cylinder into a number of rectangular areas. The boundaries of these zones are formed by vertical lines parallel to the cylinder axis and circles perpendicular to the cylinder axis. These areas correspond to planar rectangles when the cylinder is expanded to form a large planar rectangle. A given rectangular area of the cylinder is specified by a unique row and column number associated with the side image. Hereinafter, the number of cylinder rows is indicated by PanWdt, and the number of cylinder columns is
Shown in PanHgt.

FIG. 4 shows one rectangular section (a
bcd) and the pyramid region determined by the origin of the cylinder. The base of the pyramid (ABCD) is a rectangular area (abcd)
Can be located at an infinite distance from. Rectangular area (a
The color value associated with bcd) intersects this pyramid and is determined by the three-dimensional object seen from the origin (O) of the cylinder. In the computer-generated image, the color associated with the rectangular area (abcd) starts at the origin (O) and is at the base of the pyramid (AB
CD) can be approximated by the color determined by the line passing through the center. Other values are also in the area (abcd)
Can be related to For example, the depth value can be defined by the distance between the origin and the closest point that intersects a line from the origin (O) that passes through the center of the base of the pyramid (ABCD). Alternatively, the index of the response table may be associated with the area (abcd). Each entry in the response table may define an operation to be performed when a corresponding area (abcd) is selected.

The cylindrical environment map uses a narrow vertical slit to digitally process a panoramic photograph obtained from a panoramic camera that exposes photographic film while rotating the lens and slit about a vertical axis. Can be created by Alternatively, a number of flat images can be projected onto the surface of the cylinder to create a cylindrical environment map. Each flat image is obtained by digitally processing a conventional photograph captured on a flat or planar area of photographic film, or by applying a computer graphics rendering algorithm to a three-dimensional digital model. Can be. In any case, each flat image can be characterized by a horizontal view and a vertical view. If the sum of the horizontal views is equal to 360 °, the cylindrical environment map is defined as complete. If the sum of the horizontal views is less than 360 °, the cylindrical environment map is defined as a partial panorama.

According to the invention, the image data of the cylindrical environment map is stored, preferably in column order. It is common practice to store image data in row order. That is, data representing an image having nCol columns and nRow rows is typically stored as a contiguous series of nRows of data blocks, each containing data for nCol adjacent pixels representing the horizontal band of the image. The data of the corresponding row is stored in order from top to bottom or from bottom to top. In this case, the number of rows represents the height of the image and the number of columns represents the width of the image. Panoramic images based on cylindrical projections have more columns than rows. The number of columns in the panoramic image may be four to five times the number of rows or more. The projected image representing the view of the scene represented by the panoramic image depends on a specific subset of the rows and columns in the panoramic image. This subset can be, for example, half a row to a full and 1/1 a column.
0 to 1/4 can be included. In this case, the conventional storage of image data in row order leads to a very inefficient memory reference pattern when calculating the projected image, if the projected image depends on a small part of each row.

The memory reference patterns required to calculate the projected image can be made more efficient by storing the panoramic images in column order rather than row order. In this case, the same data representing the panoramic image
Store as a series of nCol consecutive blocks, each containing nRow consecutive pixels. Each such block contains data for one column of the panoramic image, and blocks representing successive columns are stored in order of increasing azimuth. In this case, the "width" (number of elements per block) of the image data is the vertical size of the image,
"Height" (the number of data blocks) is the horizontal size of the panoramic image.

The storage of the panoramic images in column order also provides an advantage to the calculation of the projected images in column order, even if the projected images themselves are stored in row order. In this case, it is only necessary to sequentially access the elements of the larger data structure (panoramic image) and calculate a specific operation, for example a trigonometric function of the azimuth, once for each column. The cylindrical environment map of the present invention described below is described in column order in which the width of the image is the vertical size of the image and the height of the image is the horizontal size of the image.

Once a partial or complete environment map is obtained, it is possible to generate an image of the corresponding three-dimensional scene by projecting the elements of the cylindrical environment map onto a plane parallel to the cylinder axis. The part of the cylindrical environment map projected onto this plane is the azimuth angle θ and the height z of the center of the projected image, and the angle of horizontal field α and the angle of vertical field β
Can be characterized by

FIG. 5 shows a projection of a part of a cylinder onto a surface (or vice versa). Points A, C, D and F represent the corners of a planar rectangle parallel to the cylinder axis. Point B is the midpoint of the side (AC) and point E is the midpoint of the side (DF). Rectangular (AC
DF) is in contact with the cylinder along the line (BE = be). The points (a, b, c, d, e and f) are at the origin (O)
Represents the point on the cylinder defined by the point where the straight line from intersects the points (A, B, C, D, E and F) on the planar rectangle.

FIG. 6 is a view of the same cylinder and surface as those shown in FIG. 5 as viewed from above the cylinder axis. In this figure, point A,
B, C, a, b and c are points F, E, D, f,
e and d. The azimuth of the line (BE = be) is indicated by the angle θ. The angle α of the horizontal field of view is the line (a
It depends on the difference between the azimuth of f) and the azimuth of line (cd). In this figure, the lines (af), (be) and (c)
d) are only visible as points since they are all parallel to the cylinder axis (and the direction of the line of sight).

FIG. 7 is a view of the same cylinder and plane as those shown in FIGS. 5 and 6 as viewed from a direction perpendicular to the plane including the cylinder axis and the center line (BE) of the projection plane. Center line (BE)
Is indicated by a point G. The elevation angle φ of the point G is zMid
Corresponds to the height value of The vertical field is indicated by β.

For a complete panorama, there is no limit to the possible azimuthal angles θ and the horizontal viewing angle α is limited only to less than 180 °. For partial panorama covering the azimuth angle θ of 0～Shita _MAX, the azimuth angle θ of the center of a projection image must be within a range of the following equation.

[0032]

(Equation 1)

There are two factors that limit the range of the height value z of the projected image. One is the lack of information about height values beyond the range of the data represented by the cylinder data. The second limitation results from the merging of many flat images into one cylindrical data structure. Each of a number of flat images represents a projection of a three-dimensional scene onto a plane parallel to the cylinder axis. Each of these images has a specific horizontal field of view α and a vertical field of view β. Normal,
These flat images all share the same horizontal and vertical field of view, and the horizontal field of view α is determined by dividing 360 ° by the number of images.

For example, as shown in FIG.
There may be four images with a horizontal field of view of 0 °. As can be seen from the top of the cylinder axis, the cylinder has a radius R
It looks like a circle. R is given by the following equation.

[0035]

(Equation 2)

Here, PanHgt is the number of columns in the cylindrical data structure.

The center of each image touches this circle.
A similar view of one image having a horizontal field of view α is shown in FIG. The distance from the left or right edge to the tangent point is R * tan (α / 2). The distance from the cylindrical axis to the left and right edges is R * sec (α / 2).

FIG. 10 shows a side view of the cylinder of FIG. FIG.
The line of sight in the case of 0 is the direction viewed from the plane AA in FIG. More specifically, the viewing direction in FIG. 10 is a direction as viewed from the center line of the image in contact with the cylinder with the radius R shown in FIG. The vertical field of view of the image is β, and the maximum height Emax is R * tan (β /
2), and the minimum height Emin is -R * tan (β / 2).

Another side view of the cylinder is shown in FIG.
In this case, the line of sight in FIG. 11 is the direction viewed from plane BB in FIG. 9 and is perpendicular to the axis of the cylinder shown in FIG. More specifically, the line of sight in FIG. 11 is not from the center of the image but from the left or right edge of the image.
As shown in FIG. 9, both edges of the image are located at a distance R * sec (α / 2) from the cylinder axis. As a result, the overall height of the image is compressed to a height range from Emax * cos (α / 2) to Emin * cos (α / 2) on the side of the cylinder at a distance R from the cylinder axis. As a result, this image contains E
max * cos (α / 2) -Emax or Emin-Emin
* There is no information corresponding to the height in the range of cos (α / 2).

If the obtained cylinder is developed on a flat surface, the result shown in FIG. 12 is obtained (image 4 of 90 °).
Case). In this case, the four images are Emin / sqr
Fill all elements of the cylinder corresponding to heights in the range t (2) to Emax / sqrt (2). Also, Emin-Emin / sq
Further information is obtained regarding the range of rt (2) and the height in the range of Emax / sqrt (2) to Emax, but the portions of the cylinder marked with "X" and "*" remain undetermined. One solution to this is Emin / sqrt
(2) A method of discarding data corresponding to a height outside the range of Emax / sqrt (2) and limiting the height of the field of view to this reduced range. An alternative method is to allow the height in the range of Emin to Emax, but fill the missing area with solid black or any other color.

According to the present invention, the range of elevation angles over which the projected image can be calculated from the cylindrical environment map is supplemented by adding data defining the top and / or bottom images of the cylindrical environment map. The availability of top and / or bottom images improves the ability to create projected images in two ways. First, these images make it possible to calculate projected images having height values beyond the range covered by the cylindrical area represented by the conventional cylindrical environment map. Second, these images can be used to fill corner regions created by projecting multiple flat images onto a cylinder.

Next, referring to FIG. 20, when assembling the side image into the cylindrical environment map, the top
A procedure for using an image and a bottom image will be described. For the sake of explanation, the side images described below are rectangular, and the top and bottom images are square. However, those skilled in the art will recognize that the present invention is not limited in this respect and is applicable to various polygonal side, top and bottom images.

The process begins at step 201 by generating a side image of a panoramic scene.
As before, each side image, when generated, can be represented by data indicating the color of the side image in a plurality of element areas (or pixels). However, if necessary (eg, when deriving side images from photographs), in step 201, each side image is divided into a plurality of element areas (or pixels), and for each element area, You may need to store color values. As shown in FIG. 21, each side image may be divided into a matrix. A given element area (or pixel) of a side image is
Unique row and column numbers associated with the image (iRow,
iCol). In addition, in step 201,
For each image, the number of rows in the image (indicated by imgHgt) and the number of columns in the image (indicated by imgWdt) are stored. FIG. 22 shows the information stored for each pixel of the side image. The information includes color data identifying the color of the pixel. The color data can represent the red, green, and blue components (true colors) of a pixel color or an index (palette color) into a color palette. The information stored for a given pixel may also include Z data representing the depth of the image at the given pixel. In addition, the information stored for each pixel may include additional data (M data) associated with the pixel. For example, the data may be operations associated with pixels, such as a hyperlink to another panorama, a command to play audio or a command to start an external application.

The side image is a digital processing of a panoramic photograph obtained from a panoramic camera using a thin vertical slit to expose a photographic film while rotating the lens and the slit about a vertical axis. Can be created by Alternatively, the side images can be obtained by digitally processing a conventional photograph captured on a flat or planar area of photographic film, or by applying a computer graphics rendering algorithm to a three-dimensional digital model. Obtainable.

In step 203, a top image and / or a bottom image of the panoramic scene is generated. As before, the top and bottom images, once generated, can be represented by data indicating the color of the image in a plurality of element areas (or pixels). If necessary (for example, when deriving a top and / or bottom image from a photo)
In step 203, the top image and / or the bottom image may be divided into element areas (or pixels), and for each element area, it may be necessary to store the color values of the image in the element areas. As shown in FIG. 23, the top image and the bottom image may be divided into a matrix. For explanation, only the top image is shown. Identify a given element area (or pixel) of the top and bottom images by unique row and column numbers (tRow, tCol) or (bRow, bCol) associated with the top and bottom images, respectively. I do. In addition, in step 203, the number of rows (topH) in the top and / or bottom image
gt and botHgt) and the number of columns in the top and / or bottom images (topWdt and bo
tWdt).

FIG. 24 shows the information stored for each pixel of the top image (or bottom image). The information includes color data identifying the color of the pixel.
The color data can represent the red, green, and blue components (true colors) of a pixel color or an index (palette color) into a color palette. The information stored for a given pixel may also include Z data representing the depth of the image at the given pixel. In addition, the information stored for each pixel may include additional data (M data) associated with the pixel. For example, the data may be operations associated with pixels, such as a hyperlink to another panorama, a command to play audio or a command to start an external application.

The top and bottom images can be created by digitally processing conventional photographs of the top and bottom images obtained from the camera. Alternatively, the top and bottom images can be generated by applying a computer graphics rendering algorithm to the three-dimensional digital model. More specifically, top image and bottom image
An image can be defined by projecting a three-dimensional scene onto a plane perpendicular to the cylinder axis that defines a conventional cylindrical environment map. The top image is defined by projecting the 3D scene onto a plane above the origin of the cylinder axis, and the bottom image is projecting the 3D scene onto a plane below the origin of the cylinder axis. Is defined by

In step 205, for each side image generated in step 201, the range of the column of cylinders corresponding to the given side image is determined. More specifically, each side image is characterized by a horizontal field of view α. Convert the image data of a specific side image to θ
₁ through? ₂ of maps to a column of a cylinder corresponding to the range of the azimuth angle (where, theta ₁ is determined by the sum of the horizontal field of view of all the side image of the preceding, and _{θ 2 = θ 1 + α)} . Thus, given the initial azimuth θ ₁ and the final azimuth θ ₂ of the current image, the range of columns in the resulting cylindrical image corresponding to a particular side image is determined by:

PanCol1 = panHgt * θ ₁ / θ _MAX panCol2 = panHgt * θ ₂ / θ _MAX where θ _MAX is equal to 2π for a complete panorama and less than 2π for a partial panorama.

In addition, in step 205, for each side image, the number of rows of cylinders corresponding to each side image is stored. The number of rows of cylinders corresponding to a given side image is given by:

NumPanCol = panCol2-panCol1

In step 207, for each side image generated in step 201, each column of cylinders within the range of the column determined in step 205, which is associated with a specific side image, is sequentially selected. Generated current side image data values and step 20
3. The top image and / or bottom image generated in
Fill based on image data values. Preferably,
Individual columns are sequentially selected by designating a column index panCol which is initialized to panCol1 and gradually increased by one step until reaching panCol2. Hereinafter, the filling operation for a specific column will be described in more detail with reference to FIG.

In step 209, after processing the range of the column corresponding to each side image, the process ends.

FIG. 25 shows the filling operation for a particular row of cylinders in more detail. More specifically, the index pa
The particular column of the cylinder specified by nCol corresponds to the absolute angle θ and the local angle δ. However,

Θ = θ _MAX * panCol / panHgt δ = θ−θ ₁ − (α / 2)

FIG. 13 shows the relationship between these angles. For each column on the cylinder specified by the index panCol, the index imgCol, determined by:
There is a corresponding column in the side image specified by.

[0057]

(Equation 3)

In step 301, each row of the cylinder indicated by panRow is selected, and the current row panRow of the cylinder is set to the current side row.
Determine whether to enter the image, the top image, or the bottom image. panRow value is 0
From (panWidth-1). Here, panWidth is the number of rows in the cylinder.

At step 303, the pixel index imgRow corresponding to the selected row and column of the cylinder is determined. As shown in FIG. 14, the wall of the cylinder has a radius R from the cylinder axis.
And the corresponding column of the current side image is located at a distance of R * sec (δ) from the cylinder axis,
The pixels in row panRow of the cylindrical wall correspond to the pixels in row imgRow in the current side image.

[0060]

(Equation 4)

In steps 305-309, it is determined whether the current row panRow of the cylinder is in the current side, top or bottom image by evaluating the value of ImgRow. I do. ImgRow
, And performing processing based on such an evaluation, step 310 determines whether the last row of the column has been processed. If not, the process returns to step 301, where the row index panRow is set to the next sequential row in the cylindrical column. If the last row of the column is selected (panRow = panWidth-1), the process ends.

At step 305, if the value of imgRow is greater than or equal to imgHgt, the cylindrical row panRow enters the top image. In this case, in step 311, the current line Pa of the cylinder is
Determine the element (pixel) of the top image identified by the index tRow and tCol, corresponding to nRow and column panCol, and in step 313, preferably the color of the pixel of the cylindrical environment map identified by the index panRow, panCol Is set to correspond to the color of the pixel in the top image identified by the index tRow, tCol.

At step 307, if the value of imgRow is less than 0, the cylindrical row panRow enters the bottom image. In this case, in step 315, the current line panR of the cylinder
index bRow and corresponding to ow and column panCol
The element (pixel) of the bottom image identified by bCol is determined, and in step 317, preferably the color of the pixel of the cylindrical environment map identified by the index panRow, panCol, and the bottom identified by the index bRow, bCol -Set to correspond to the pixel color of the image.

In step 309, the value of imgRow is 0 to im
gHgt range, so the cylindrical row panRow falls into the current side image. In this case, the index pa
The pixels of the cylindrical environment map identified by nRow and panCol correspond to the pixels of the current side image identified by the indexes imgRow, imgCol.
In step 309, preferably the index panRow,
Set the color of the pixel in the cylindrical environment map identified by panCol to correspond to the color of the pixel in the current side image identified by index imgRow, imgCol.

Referring now to FIG. 26, the current row of the cylinder
The operation of the system in determining the elements (pixels) of the top or bottom image corresponding to panRow and column panCol will be described. In step 401, processing begins by determining the radius of a corresponding point in the top (or bottom) image. This is the top
The points in the image are shown in FIG. In this case, the radius of the point in the top image is obtained by the following equation.

Rtop = R * (panHgt / 2) / (panRow−
(PanHgt / 2))

The radius of a point in the bottom image is obtained by the following equation.

Rbot = R * (panHgt / 2) / ((panHgt /
2) -panRow)

In this case, the cylinder can be treated as a unit circle with R = 1. The resulting values of Rtop and Rbot are always greater than 1.0 and correspond to points outside the unit circle.

After the top radius Rtop (or bottom radius Rbot) is determined in step 403, an index for identifying a point in the top (or bottom) image shown in FIG. 16 is determined. For points in the top image,
The row and column indices of the color values in the top image can be determined by:

TRow = topHgt * (1.0−Rtop * sin (θ)) tCol = topWdt * (1.0 + Rtop * cos (θ)) where topHgt and topWdt are the row and column dimensions of the top image. is there.

Similarly, the row and column indices of points in the bottom image can be determined by:

BRow = botHgt * (1.0−Rbot * sin (θ)) bCol = botWdt * (1.0−Rbot * cos (θ))

As described above, the indexes (tRow, tC
The points specified by (ol) and (bRow, bCol) correspond to pixels in the top and bottom images located outside the inscribed circles corresponding to the upper and lower edges of the cylindrical wall. Preferably, the mapping of points of the top (or bottom) image outside this circle to the cylindrical environment map is handled by the projection algorithm used to view panoramic data, described below.

Having described the mechanism for supplementing the cylindrical environment map with data defining the top and / or bottom images of the panoramic scene,
Referring to FIG. 27, a technique for rendering the improved cylindrical environment map for display of the present invention is described.

In step 501, the visual field is determined. The field of view is preferably characterized by the following parameters: azimuth angle θ, elevation angle φ of the center of the projected image, horizontal field α and vertical field β. The selected parameters are
This is shown in FIG. The parameters may be selected, for example, based on user input commands generated in response to a user operating input device 107 of the computer system.

At step 503, the cylindrical environment map is mapped to a view window corresponding to the visual field. The mapping process begins by dividing the view window into ncol equally spaced columns as shown in FIG. Each ncol column can be identified by an index icol in the range 0-ncol-1 and corresponds to an angle δ determined by the following equation.

Δ = tan−1 (tan (α / 2) * (width−
2 * icol) / (2 * width)) where width = ncol-1 is the width of the view window.

Column (icol) of ncol column of view window
In each case, the column panCol of the cylindrical environment map corresponding to the column icol is determined. Preferably, the column panCol of the cylindrical environment map corresponding to the column icol is determined by:

PanCol = panHgt * (θ + δ) / θ _MAX

In addition, select and process nrow pixels in column icol of the view window. Preferably, the nrow pixels in the column are evenly spaced along a line parallel to the cylinder axis at a distance Rpan / cos (8) from the cylinder axis, as shown in FIG. 0 for each nrow pixel
(Bottom of view window)-nrow-1 (view
Index irow with range (top of window)
Can be assigned. Hereinafter, referring to FIG.
Nrow of selected column (indicated by icol) in view window
The processing of the pixel will be described in detail.

In a final step 505 of FIG. 27, after mapping the columns of the cylindrical environment map to the view window, the view window can be mapped to a display device or a portion of a display device. Such mapping may require scaling and translating the view window with respect to the display coordinate system. Such scaling and translation techniques are well-known in the art. However, the scaling process may be avoided to improve the performance of the system. in this case,
The pixels of the view window must be aligned with the pixels of the display window.

FIG. 28 illustrates the operation of the system in mapping a cylindrical environment map to nrow pixels in a selected column (icol) of a view window. As mentioned above, the columns
The column panCol of the cylindrical environment map corresponding to icol is determined by the following equation.

PanCol = panHgt * (θ + δ) / θ _MAX

In step 601, the processing proceeds to the selected column
For icol, one begins by determining the rows of the view window corresponding to the top and bottom edges of the cylinder, denoted by topRow and botRow, respectively. The values of topRow and botRow are preferably determined by the following equation.

TopRow = ctrRow + (0.5 * panHgt / pxlS)
ize) * sec (δ) botRow = ctrRow- (0.5 * panHgt / pxlSize) * sec
(Δ) where pxlSize = 2 * Rpan * tan (α / 2) width is
Pixel size assuming square pixels (vertical pixel size equals horizontal pixel size).

The above values of topRow and botRow depend on the position of the center pixel ctrRow of the view window. If there is no vertical view movement (if the view elevation φ is equal to zero), the pixel of the centerline ctrRow
The index is obtained by the following equation.

CtrRow = 0.5 * height

As the height of the view changes, the center of the view window corresponds to the row of cylinders determined by:

ZMid = Rpan * tan (φ)

As a result, the row of the view window corresponding to the zero height is as follows.

CtrRow = 0.5 * height-zMid / pxlSize

At step 603, the view window
Determines if any of the nrow pixels are below the bottom edge of the cylinder (and therefore in the bottom image), and if so, is below the bottom edge of the cylinder Process the pixels in the view window. Preferably, a value of botRow greater than 0 indicates that one or more pixels of the view window are located below the lower edge of the cylinder, and thus are in the bottom image. In this case, if the value of botRow is greater than 0, pixels in the range 0-botRow-1 will be located below the lower edge of the cylinder. Processing of pixels located below the lower edge of the cylinder will be described later.

In step 605, the view window
Determines if any of the nrow pixels are above the top edge of the cylinder (and therefore in the top image), and if so, is above the top edge of the cylinder Process the pixels in the view window. Preferably, the value of topRow less than nrow-1 is
Indicates that one or more pixels of the view window are located above the top edge of the cylinder and are therefore in the top image. In this case, the value of topRow is nrow-
If less than one, pixels in the range topRow to nrow-1 are located above the top edge of the cylinder. Processing of pixels located above the upper edge of the cylinder will be described later.

Finally, step 607 processes the nrow pixels of the view window that are not below the bottom edge of the cylinder or above the top edge of the cylinder (and thus are in the cylinder environment map). I do. Preferably, nrow pixels that are not below the bottom edge of the cylinder or above the top edge of the cylinder are located in the range botRow to topRow-1. Processing of pixels that are not located above the top edge of the cylinder or below the bottom edge of the cylinder will be described later.

Next, processing of pixels located above the upper edge of the cylinder will be described. As described above, pixels located above the top edge of the cylinder can be identified by an index icol in the range topRow to nrow-1. In this case, for each pixel identified by an index icol in the range topRow to nrow-1, the value of the top radius Rtop corresponding to the pixel is determined by the row index and column index (tRow and tCol) of the pixel in the top image. Decide with. Preferably, the top radius Rtop is determined by the following equation.

Rtop = Rpan * sec (δ) * (0.5 * panW
idth) / (irow-ctrRow)

This is shown in FIG. 19, one of which is width Rpan * s.
Based on a comparison of similar right triangles with ec (δ) and height (irow-ctrRow), the other having width Rtop and height (0.5 * panHgt). In this case,
All that is needed is the ratio of Rtop to Rpan, and the calculation of Rtop is simplified as:

Rtop = radRow / (irow-ctrRow) where radRow = 0.5 * panHgt * sec (δ) is a constant for one example pixel (constant delta).

The row and column indices (tRow, tCol) of the pixels in the top image are preferably determined by:

TRow = topHgt * (1.0−Rtop * sin (θ + δ)) tCol = topWdt * (1.0 + Rtop * cos (θ + δ))

Finally, preferably, the index irow,
Set the color of the pixel in the view window identified by icol to correspond to the color of the pixel in the top image identified by index tRow, tCol.

Next, processing of pixels located below the lower edge of the cylinder will be described. As mentioned above, pixels located below the lower edge of the cylinder can be identified by an index icol in the range 0-botRow-1.
In this case, the index ic in the range of 0 to botRow-1
For each pixel identified by ol, determine the value of the bottom radius Rbot corresponding to the pixel, along with the row and column indices (bRow and bCol) of the pixel in the bottom image.

Preferably, the bottom radius Rbot is determined by the following equation.

Rbot = radRow / (ctrRow-irow)

The row and column indices (bRow, bCol) of the pixels in the bottom image are preferably determined by:

BRow = topHgt * (1.0−Rtop * sin (θ + δ)) bCol = topWdt * (1.0 + Rtop * cos (θ + δ))

Finally, preferably, the index irow,
Set the color of the pixel in the view window identified by icol to correspond to the color of the pixel in the bottom image identified by index bRow, bCol.

Next, processing of a pixel which is not located above the upper edge of the cylinder and which is not located below the lower edge of the cylinder will be described. For each pixel that is not above the top edge of the cylinder or below the bottom edge of the cylinder, the row panRow of the cylinder environment map that corresponds to the row irow of the view window
Is determined by the following equation.

[0110]

(Equation 5)

Preferably, the index irow,
Set the color of the pixel in the view window identified by icol to correspond to the color of the pixel in the cylindrical environment map identified by the index panRow, panCol.

The calculations to determine the projection of the top and bottom images on the view window are more difficult than the calculations required to determine the projection of the cylindrical environment map on the view window. This can result in a loss of performance if a large portion of the projected image is determined by points in the top and / or bottom images. If only a small portion of the projected image is determined by pixels in the top and / or bottom images, the performance loss is very small. There is no performance loss for top and bottom points located outside the unit circle of the cylinder.

The calculation of the indices of the pixels derived from the top and bottom images depends on the sine and cosine trigonometric functions, whose arguments are not the row indices but the column indices (angle δ). Only depends on. Consequently, preferably, these values need only be calculated once per column.

Advantageously, by integrating the top and bottom images into a cylindrical environment map,
The present invention can increase the field of view with only a small increase in data.

In another aspect of the invention, the server comprises:
It is possible to store one or more files containing the cylindrical environment map of the present invention. A client connected to the server via the network can download a file from the server and execute the above-described rendering processing of the present invention. However, communicating files over a network may be very slow due to network communication bandwidth limitations. This may result in a long delay between the start of the network communication step and the appearance of the image in the display window of the display device.

In order to minimize the influence of such network communication delay, the cylindrical environment map of the present invention stored in the server can be represented by a plurality of cylindrical environment maps of different resolutions. The lower resolution environment map
It contains less data than a higher resolution environment map,
Therefore, the time required for communication via the network is short. As is common with other image processing operations, a lower resolution cylindrical environment can be created from one or more higher resolution cylindrical environment maps. For example,
A lower resolution cylindrical environment map having １ ／ of the number of elements (pixels) of the first cylindrical environment map is created by averaging each 2 × 2 block of pixels in the first cylindrical environment map. Can be.

In this scenario, the client is first controlled to request and receive the lowest resolution environment map and render the lowest resolution environment map. After (or in parallel with) rendering the lowest resolution environment map, the client can request and receive a higher resolution environment map and render the higher resolution environment map.
This process can be repeated until the highest resolution environment map is received by the client and rendered for display.

The details of the processing when the client and the server operate a plurality of environment maps having different resolutions are shown in FIGS. In this example, the server transmits a plurality of environment maps LOD0 and LOD0 each having a different resolution.
OD1, LOD2, etc. are stored. The map with the lowest resolution is LOD0. Environment map LOD1, LOD2
And so on, their resolution is gradually increasing. Moreover, the operation of the client is divided into two threads, a display thread and a communication thread. However, the operation of the client is not limited to this, and may be integrated into one thread or divided into three or more threads.

The operation of the client begins, for example, when a user initiates a request to display an environment map stored on a server. This request may be part of a hyperlink that identifies the server, or may be a control file CF0 stored on the server. In this case, the control file CF0 is preferably linked with a plurality of other control files (CF1, CF2, etc.) stored on the server to identify a chain of different resolution environment maps to be downloaded from the server to the client.・
Used as a list data structure. More specifically,
The control file CF0 includes a pointer to the environment map LOD0 and a pointer to the control file CF1, and the control file CF1 includes a pointer to the environment map LOD1 and a pointer to the control file CF2. The same applies to the following.

In this case, the client requests the control file CF0 from the server in response to the user's request. Upon receiving the control file CF0 from the server, the client requests the minimum resolution environment map LOD0 identified by the control file CF0 from the server.

Upon receiving the lowest resolution environment map LOD0 from the server, the client stores the lowest resolution environment map LOD0 locally, renders the lowest resolution environment map LOD0 for display, and preferably, the user Allows navigating within the lowest resolution environment map LOD0. In addition, the client
The control file CF1 is requested from the server. As described above, the control file CF1 preferably stores the next higher resolution environment map LOD1 and the control file CF2.
Contains a pointer to (if necessary).

Upon receiving the control file CF1 from the server, the client requests the next higher resolution environment map LOD1 identified by the control file CF1 from the server. Upon receiving the next higher resolution environment map LOD1 from the server, the client sends the environment map LOD1.
1 is stored locally. In addition, the client stops navigating the lowest resolution environment map LOD0 and renders the next higher resolution environment map LOD1 for display, preferably wherein the user navigates within that environment map LOD1. Forgive. in addition,
The client requests the control file CF2 from the server. As described above, the control file CF2 preferably includes a pointer to the next higher resolution environment map LOD2 and control file CF3 (if needed).

Upon receiving the control file CF2 from the server, the client requests the next higher resolution environment map LOD2 identified by the control file CF2 from the server. Upon receiving the next higher resolution environment map LOD2 from the server, the client sends the environment map LOD2.
2 is stored locally. In addition, the client stops navigating the environment map LOD1, renders the next higher resolution environment map LOD2 for display, and preferably allows the user to navigate within the environment map LOD2.

These processes can be repeated until the highest resolution environment map is received by the client and rendered for display. This process allows the user to quickly look at and navigate through a lower resolution environment map while progressively building a higher resolution environment map, thereby reducing the impact of network communication delays. Provide the ability to minimize.

In another aspect of the invention, a mechanism is provided that allows one or more bitmap images (or sprites) separate from the environment map to be integrated into a panoramic scene. A bitmap image is a two-dimensional array of pixels that represents the color of the image on a pixel-by-pixel basis. Referring to FIG. 32, the process of integrating a bitmap image into a panoramic scene is performed in step 7
Begin at 01 by orienting the bitmap image in the coordinate system of the environment map. As shown in FIG. 2, the coordinate system of the cylindrical environment map is characterized by a cylindrical axis and second and third axes that intersect the cylindrical axis at the origin. The second and third axes are perpendicular to the cylindrical axis and to each other. Preferably, the orientation of the bitmap image is restricted such that the bitmap image lies in a plane parallel to the cylinder axis. In this case, the bitmap image is obtained by assigning a characteristic azimuth angle θ and elevation angle φ to the bitmap image.
It can be oriented in the coordinate system of the environment map.
As shown in FIGS. 33 and 34, the azimuthal angle θ is preferably represented by the angle between the plane of the second coordinate axis and the cylindrical axis and the line from the cylindrical axis to the center pixel M of the bitmap image. Is done. As shown in FIGS. 33 and 35, the elevation angle φ is preferably
It is represented by the angle between the line reaching the center pixel M of the image and the plane of the second and third coordinate axes.

At step 703, the environment map is projected onto the view window as described above with reference to FIG. As a result of the projection step, color values are generated for the pixels in the rows and columns of the view window.

At step 705, the pair (startCol, endCo
Determine the range of columns of the view window covered by the bitmap image, indicated by l), and the range of rows of the view window covered by the bitmap image, indicated by the pair (startRow, endRow).

In step 707, the range of the column (startCol,
For each column icol in endCol), the column index BMCol of the bitmap image corresponding to the particular column icol in the view window is determined, preferably by:

BMCol = icol-startCol

In addition, columns of the view window (icol)
Are sequentially selected in the row range (startRow, EndRow), and processing is performed as follows. First, the row index BMRow of the bitmap image corresponding to the selected row irow of the view window is determined, preferably by:

BMRow = irow-startRow

Next, the color value of the bitmap image of the pixel identified by the indexes BMRow and BMCol is determined by the index (irow,
icol) instead of the color value of the pixel in the view window identified by

The range of columns of the view window covered by the bitmap image (startCol, endCo
After processing l), the processing ends.

The above processing is performed separately from the environment map.
More than one bitmap image can be oriented and displayed in a panoramic scene.

In an alternative embodiment, the mechanism described above may be modified to enhance the integration of the bitmap image with the environment map by associating depth values with the pixels of the bitmap image. In this scenario, step 701 associates a depth value with a pixel of each bitmap image. The depth values of the pixels of the depth map may be constant. Alternatively, the depth values may vary over the pixels of the bitmap image. In this case, the depth value preferably represents the depth of the image relative to the central pixel. Thus, the depth of each pixel in the bitmap image can be determined from the characteristic azimuth and elevation φ of the bitmap image and the relative depth of the pixel to the center pixel associated with a given pixel. . In addition, a default depth value (Dmax) is associated with the pixels of the environment map.

Preferably, a depth buffer is used to store a depth value associated with each pixel of the view window. Initialize the depth value of each pixel to the maximum value (Dmax). At step 703, the depth buffer is not accessed, and therefore the depth value of Dmax is assigned to the pixels of the environment map that are projected into the view window.
At step 707, the depth value (Dnew) of the bitmap image at the pixel (BMRow, BMCol) is stored in the depth buffer location corresponding to the pixel (irow, icol) in the view window. Compare with Bold. If the bitmap image depth value Dnew indicates that the bitmap image is closer to the viewpoint than the stored depth value Dold, the location of the depth buffer corresponding to the pixel (irow, icol). Is updated to store the value Dnew, and the color value of the pixel in the view window identified by the index (irow, icol) is stored in the index (BMRow, B
Bitmap at the pixel identified by MCol)
Overwrite with the color value of the image.

This processing displays the closest bitmap image when partial (or complete) occlusion occurs between a plurality of bitmap images.

In an alternative embodiment, the above mechanism is modified to enhance the integration of the bitmap image with the environment map by associating depth values with the pixels of the bitmap image and the pixels of the environment map. You may. In this scenario, step 701 associates a depth value with a pixel of each bitmap image. Preferably, the depth value represents the depth of the image relative to the central pixel. In this case, the depth of each pixel of the bitmap image may be determined from the characteristic azimuth angle θ and elevation angle φ of the bitmap image and the relative depth of the pixel to the center pixel associated with a given pixel. it can. In addition, the depth values are associated with the pixels of the environment map. For example, for a cylindrical environment map, the depth value associated with a given pixel of the environment map can be determined by the distance from the cylinder origin to the cylinder pixel. In another example, if the cylindrical environment map was derived from a rendering of a three-dimensional scene, the depth values of the pixels in the environment map could be derived from depth information of objects in the scene.

A depth buffer may be used to store the depth value associated with each pixel in the view window.
Initialize the depth value of each pixel in the view window to the maximum value (Dmax). In step 703, projecting the environment map onto the view window, as described above with reference to FIG. 27, updates the depth buffer to relate pixels in the environment map that cover a given pixel in the view window. The depth value to be stored is stored. The projection step also results in the generation of color values for pixels in rows and columns of the view window. In step 707, the depth value Dnew of the bitmap image of the pixel (BMRow, BMCol) is set to the pixel (irow, ic) of the view window.
ol) the depth value stored in the depth buffer location corresponding to
Compare with Dold. Bitmap image depth value Dnew
Is the bitmap image and the stored depth value Dold
Update the position of the depth buffer corresponding to the pixel (irow, icol) to store the value Dnew and to store the value of the view window identified by the index (irow, icol). Overwrites the color value of the pixel with the color value of the bitmap image at the pixel identified by the index (BMRow, MBCol).

This process displays a bitmap image or environment map when partial (or complete) occlusion occurs between a plurality of bitmap images and / or environment maps.

In an alternative embodiment, the above mechanism for associating depth values with pixels of the bitmap image and pixels of the environment map is modified to store a depth value corresponding to each pixel of the view window. A depth buffer may not be required. In this embodiment, at step 701, a depth value is associated with each bitmap image pixel, and the depth value is calculated as described above.
Associated with the pixels of the environment map. In step 703,
As described above with reference to FIG. 27, when projecting the environment map onto the view window, the index (iro
For each pixel of the view window identified by (w, icol), determine whether the pixel of the view window is covered by the bitmap image.

If the view window is not partially covered by the bitmap image, processing continues as described above with reference to FIG.
The color values of the pixels (irow, icol) in the window will now be set to the color values of the appropriate elements in the environment map.

However, if the pixels of the view window are not partially covered by the bitmap image, the row index of the bitmap image corresponding to the selected pixel (irow, icol) of the view window and Determine the column indexes BMRow, BMCol. In addition, the depth value of the bitmap image at the pixel (BMRow, BMCol) is compared with the pixel value of the environment map corresponding to the pixel (irow, icol) of the view window. If the depth value of the bitmap image pixel (BMRow, BMCol) indicates that the bitmap image pixel (BMRow, BMCol) is closer to the view point than the environment map pixel, the view Set the color value of the window pixel (irow, icol) to the color value of the bitmap image at the pixel identified by the index (BMRow, MBCol). Otherwise, set the color value of the view window pixel (irow, icol) to the color value of the corresponding pixel in the environment map.

This process displays a bitmap image or environment map when partial (or complete) occlusion occurs between a plurality of bitmap images and / or environment maps, and displays the viewmap. There is no need for a depth buffer to store depth information for window pixels.

In the embodiment described above which describes a mechanism for integrating a bitmap image with an environment map when generating a panoramic scene, the position and / or orientation of the bitmap image with respect to the environment map is changed to allow such a change. The motion of the bitmap image may be provided. In addition, bitmap images can be selectively displayed,
Image distortion or other desired attributes may be provided. For example, consider four bitmap images each representing the same fish, each having a tail at a different location. In this case, the selection of the appropriate bitmap image can be synchronized with the change in the orientation of the displayed bitmap image to make the fish appear to be swimming.

In addition, a change in the depth value of the bitmap image may be represented by performing an appropriate scaling process (enlargement / reduction) on the bitmap image. For example, if the bitmap image is closer (by depth) to the view point, a zoom-in process can be performed on the bitmap image. However, if the bitmap image is moved further away (by depth) from the view point, a reduction (zoom out) operation can be performed on the bitmap image. In this scenario, the mapping between the view window and the bitmap image will take into account the scaling of the bitmap image.

The mechanism described above allows for the integration of one or more bitmap images into an environment map when rendering a panoramic scene. The environment map may be a cylindrical environment map as described above. However, the mechanism is not so limited and may be used with any type of environment map. For example, an environment map can be a cubic environment map, a spherical environment map,
It may be a polyhedral environment map as described in US patent application Ser. No. 60 / 022,428.

While the invention has been shown and described with reference to specific embodiments, those skilled in the art will recognize that and other modifications, omissions, and forms and details in detail and without departing from the spirit and scope of the invention. It should be understood that additions can be made.

In summary, the following matters are disclosed regarding the configuration of the present invention. (1) A method for generating a view of a scene, comprising: storing in a memory a color value associated with an element of an environment map representing the scene; Storing the color values to be stored in a memory, and orienting the bitmap image with respect to a coordinate system of the environment map.
Projecting the environment map onto a view window that includes an array of pixels; and for at least one pixel of the view window covered by the bitmap image, corresponding to the pixel in the view window. Determining at least one element of the bitmap image;
Deriving a color value of the pixel based on a color value of the at least one element of the bitmap image, and storing the derived color value of the pixel for display. Features method. (2) A method for generating a view of a scene, comprising: storing in a memory a color value associated with an element of an environment map representing the scene; and an element of a bitmap image separate from the environment map. Storing associated color values in memory; storing depth values associated with elements of the bitmap image in memory; orienting the bitmap image with respect to a coordinate system of the environment map. Projecting the environment map onto a view window that includes an array of pixels; and for at least one pixel of the view window covered by the bitmap image, At least one of said bitmap images corresponding to pixels
Determining the number of elements and determining that the depth value associated with the pixel and the depth value associated with the at least one element are such that the at least one element is closer to a view point than the pixel. Deriving, if indicated, a color value of the pixel based on a color value of the at least one element of the bitmap image;
Storing the derived color values of the pixels for display. (3) for the at least one pixel of the view window covered by the bitmap image, the depth value associated with the pixel and the depth value associated with the at least one element are:
If the at least one element indicates that the pixel is further from the view point than the pixel, the color value of the pixel is determined based on the color value of at least one element of the environment map corresponding to the pixel. The method of claim 2, wherein the method further comprises deriving and storing the derived color values of the pixel for display. (4) The method of (3) above, wherein a depth value associated with the pixel of the view window is stored in a depth buffer. (5) for the at least one pixel of the view window covered by the bitmap image, the depth value associated with the pixel and the depth value associated with the at least one element are:
If the at least one element indicates that the pixel is closer to the view point than the pixel, then the view window is displayed according to the depth value associated with the at least one element of the bitmap image. Updating the depth value associated with the pixel (4)
The described method. (6) storing in a memory a depth value associated with the element of the environment map, wherein the depth value associated with the pixel of the view window corresponds to the pixel of the view window. The method of claim 2, wherein the method is derived from a depth value associated with at least one element of the environment map. (7) A machine-readable program storage embodying a program of machine-executable instructions for performing the method steps of generating a view of a scene, wherein the method steps comprise elements of an environment map representing the scene. Storing in memory a color value associated with
Storing color values associated with elements of the bitmap image that are separate from the environment map in a memory; orienting the bitmap image with respect to a coordinate system of the environment map; To a view window that includes an array of pixels; and for at least one pixel of the view window covered by the bitmap image, the bit corresponding to the pixel in the view window Determining at least one element of a map; deriving a color value of the pixel based on a color value of the at least one element of the bitmap image; Storing for display. Beam storage device. (8) A machine-readable program storage embodying a program of machine-executable instructions for performing the method steps of generating a view of a scene, wherein the method comprises: an element of an environment map representing the scene; Storing associated color values in memory; storing color values associated with elements of the bitmap image separate from the environment map in memory; and a depth associated with the elements of the bitmap image. Storing a value in a memory; and orienting the bitmap image with respect to a coordinate system of the environment map;
Projecting the environment map onto a view window that includes an array of pixels; and for at least one pixel of the view window covered by the bitmap image, corresponding to the pixel in the view window. Determining at least one element of the bitmap image;
A depth value associated with the pixel and the at least one
Based on the color value of the at least one element of the bitmap image if the depth value associated with the at least one element indicates that the at least one element is closer to the view point than the pixel. Deriving a color value of the pixel; and storing the derived color value of the pixel for display. (9) for the at least one pixel of the view window covered by the bitmap image, wherein the depth value associated with the pixel and the depth value associated with the at least one element are:
If the at least one element indicates that the pixel is further from the view point than the pixel, the color value of the pixel is determined based on the color value of at least one element of the environment map corresponding to the pixel. The program storage device according to (8), wherein the derived color value is derived and stored for display. (10) The program storage device according to (9), wherein a depth value associated with the pixel of the view window is stored in a depth buffer. (11) for the at least one pixel of the view window covered by the bitmap image, the depth value associated with the pixel and the depth value associated with the at least one element are: If the at least one element indicates that the pixel is closer to the view point than the pixel, then the view window is displayed according to the depth value associated with the at least one element of the bitmap image. The program storage device according to (10), wherein the depth value related to the pixel is updated. (12) storing in the memory a depth value associated with the element of the environment map;
The program storage of claim 8, wherein the depth value associated with the pixel of the window is derived from a depth value associated with at least one element of the environment map corresponding to the pixel of the view window. apparatus.

[Brief description of the drawings]

FIG. 1 is a functional block diagram of a computer processing system that can be used in a preferred embodiment of the present invention.

FIG. 2 is a diagram illustrating a cylinder, a cylinder axis, an axis origin, a second coordinate axis, and a third coordinate axis of the cylinder environment map.

FIG. 3 is a view obtained by dividing the cylinder of FIG. 2 into rectangular areas.

FIG. 4 shows the origin (O) and the rectangular area (ab) of the cylinder of FIG.
FIG. 4 shows a pyramidal volume (OABCD) defined by cd).

FIG. 5 is a diagram in which a part (abcdef) of the cylinder of FIG. 2 is projected on a plane (ABCDEF) parallel to the cylinder axis.

6 is a view of the cylinder and the projection plane of FIG. 5 as viewed from above the cylinder axis.

FIG. 7 is a view of the cylinder and the projection plane of FIG. 5 viewed from a direction perpendicular to a plane including a cylinder axis and a center line (BE) of the projection plane.

FIG. 8 is a view of four images, each having a 90 ° horizontal field of view, mapped onto a cylinder of a cylinder environment map, as viewed from above the cylinder axis.

FIG. 9 is a diagram in which one image having a horizontal field of view α is mapped onto a cylinder of a cylinder environment map as viewed from above a cylinder axis.

10 is a side view of an image having a horizontal field of view α mapped onto a cylinder as viewed from a direction of a plane AA perpendicular to the cylinder axis shown in FIG. 9;

11 is a side view of an image having a horizontal field of view α mapped onto a cylinder, viewed from a direction of a plane BB perpendicular to the cylinder axis shown in FIG. 9;

FIG. 12 shows an expanded cylinder environment map derived from the mapping of the four images to the cylinder shown in FIG.

FIG. 13 shows an angle θ used to map an image to a cylinder of a cylinder environment map according to the present invention;
FIG. 3 is a diagram showing θ ₁ , α and δ.

FIG. 14 is a diagram illustrating the relationship between PanRow and ImgRow used to map an image onto a cylinder.

FIG. 15: PanRow and Rt for points in top image
FIG. 6 is a diagram illustrating a relationship with op.

FIG. 16 is a diagram showing positions of points in a top image.

FIG. 17 is a diagram illustrating a field of view and a view plane corresponding to the field of view where the portion of the cylindrical environment map that falls within the field of view is projected.

FIG. 18 is a side view in which a part of the cylindrical environment map is projected on a view window.

FIG. 19 is a side view in which a part of the cylindrical environment map is projected on a view window.

FIG. 20 is a flow chart illustrating the operation of the system when mapping a side image along with a top image and / or a bottom image to a cylindrical environment map in accordance with the present invention.

FIG. 21 is a diagram showing a side image and data divided into a matrix.

FIG. 22 is a diagram showing data stored for each pixel of the side image of FIG. 21;

FIG. 23 is a diagram showing a top image divided into a matrix.

FIG. 24 is a diagram showing data stored for each pixel of the top image of FIG. 23;

FIG. 25 is a flow chart illustrating the operation of the system in filling the pixels of a column of cylinders inside corresponding pixels in a side, top or bottom image.

FIG. 26 is a flow chart illustrating the operation of the system in determining the pixel in the top or bottom image corresponding to a given pixel in a column of cylinders.

FIG. 27 is a flowchart illustrating the operation of the system when generating a view of a panoramic image mapped to a cylindrical environment map.

FIG. 28 is a flow chart illustrating the operation of the system in rendering pixels in a selected column of a view window in accordance with the present invention.

FIG. 29 is a diagram showing operations of the client and the server when operating a plurality of environment maps stored in the server and having progressively higher resolutions.

FIG. 30 is a diagram illustrating operations of a client and a server when operating a plurality of environment maps stored in the server and having progressively higher resolutions.

FIG. 31 is a diagram illustrating operations of a client and a server when operating a plurality of environment maps whose resolution is gradually increased and stored in the server.

FIG. 32 is a flow chart illustrating the operation of a system for rendering bitmap images and environment maps according to the present invention.

FIG. 33 is a diagram showing a spatial relationship between a bitmap image and a cylindrical environment map.

FIG. 34 is a plan view of a cylinder environment map showing the azimuth characteristic of the bitmap image, with the cylinder axis viewed from above.

FIG. 35 is an illustration of a cylinder environment map viewed from the plane of the cylinder's second and third axes, showing the elevation angles characteristic of the bitmap image.

[Explanation of symbols]

 101 memory 103 CPU 104 frame buffer 105 display device 107 input device 108 non-volatile storage device 109 communication link

Continuing on the front page (72) Inventor William Louis Luken United States 10598, Yorktown Heights Farm Walk Road, New York 2924 (72) Inventor JIP Menon United States 105666, Peakskill Campus Road, New York 55 (56) Reference Reference Japanese Utility Model 3-100892 (JP, U) US Patent 5,396,583 (US, A) (58) Fields investigated (Int. Cl. ⁷ , DB name) G06T 15/00-17/50

Claims (12)

(57) [Claims] 1. A method of generating a view of the scene, data indicating a range of the scene table, calculates the image
Storing color values associated with elements of an environment map including data in a column order, and storing color values associated with elements of a bitmap image that are separate from the environment map in a memory. Orienting the bitmap image with respect to the coordinate system of the environment map; projecting the environment map onto a view window containing an array of pixels; covering with the bitmap image Determining, for at least one pixel of the view window, at least one element of the bitmap image corresponding to the pixel of the view window; Deriving the color value of the pixel based on the color value of one element Data indicating a range for calculating an image of the environment map
Based on the range of pixels beyond the environment map
Deriving a color value, and storing the derived color value of the pixel for display. 2. A method of generating a view of the scene, data indicating a range of the scene table, calculates the image
Storing color values associated with elements of an environment map including data in a column order, and storing color values associated with elements of a bitmap image that are separate from the environment map in a memory. Storing depth values associated with elements of the bitmap image in a memory; orienting the bitmap image with respect to a coordinate system of the environment map; Projecting onto a view window that includes an array of pixels; and for at least one pixel of the view window covered by the bitmap image, the bitmap image corresponding to the pixel in the view window. Determining at least one element of the image; and a depth associated with the pixel. And said at least one
If the depth value associated with the at least one element indicates that the at least one element is closer to the view point than the pixel, based on the color value of the at least one element of the bitmap image Deriving a color value of the pixel; and data indicating a range for calculating an image of the environment map.
Based on the range of pixels beyond the environment map
Deriving a color value, and storing the derived color value of the pixel for display. 3. The depth value associated with the pixel and the depth value associated with the at least one element for the at least one pixel of the view window covered by the bitmap image. Indicates that the at least one element is further from the view point than the pixel, the color of the pixel based on a color value of at least one element of the environment map corresponding to the pixel 3. The method of claim 2, wherein a value is derived and the derived color value of the pixel is stored for display. 4. The method of claim 3, wherein a depth value associated with said pixel of said view window is stored in a depth buffer. 5. The depth value associated with the pixel and the depth value associated with the at least one element for the at least one pixel of the view window covered by the bitmap image. Indicates that the at least one element is closer to the view point than the pixel, according to the depth value associated with the at least one element of the bitmap image. The method of claim 4, wherein the depth value associated with the pixel of a window is updated. 6. The method of claim 1, further comprising the step of storing in a memory a depth value associated with said element of said environment map, wherein said depth value associated with said pixel of said view window is stored in said pixel of said view window. 3. The method according to claim 2, wherein the method derives from a depth value associated with at least one element of the environment map corresponding to. 7. A machine-readable program storage device embodying a program of instructions executable by the machine to perform method steps for generating a view of the scene, said method steps, and tables the scene, Data indicating the range over which to calculate the image
Storing color values associated with elements of an environment map including data in a column order, and storing color values associated with elements of a bitmap image that are separate from the environment map in a memory. Orienting the bitmap image with respect to the coordinate system of the environment map; projecting the environment map onto a view window containing an array of pixels; covering with the bitmap image Determining, for at least one pixel of the view window, at least one element of the bitmap corresponding to the pixel of the view window; and at least one element of the bitmap image. a step based on the color values, to derive the color values of the pixels of the element, said ring Data indicating the range to calculate the image of the map
Based on the range of pixels beyond the environment map
A program storage device , comprising: deriving a color value; and storing the derived color value of the pixel for display. 8. A machine-readable program storage device embodying a program of instructions executable by the machine to perform method steps for generating a view of the scene, the method comprising Represents the scene, image Data indicating the range for calculating
Storing color values associated with elements of an environment map including data in a column order, and storing color values associated with elements of a bitmap image that are separate from the environment map in a memory. Storing depth values associated with elements of the bitmap image in a memory; orienting the bitmap image with respect to a coordinate system of the environment map; Projecting onto a view window that includes an array of pixels; and for at least one pixel of the view window covered by the bitmap image, the bitmap image corresponding to the pixel in the view window. Determining at least one element of the image; and a depth associated with the pixel. And said at least one
If the depth value associated with the at least one element indicates that the at least one element is closer to the view point than the pixel, based on the color value of the at least one element of the bitmap image Deriving a color value of the pixel; and data indicating a range for calculating an image of the environment map.
Based on the range of pixels beyond the environment map
A program storage device , comprising: deriving a color value; and storing the derived color value of the pixel for display. 9. The depth value associated with the pixel and the depth value associated with the at least one element for the at least one pixel of the view window covered by the bitmap image. Indicates that the at least one element is further from the view point than the pixel, the color of the pixel based on a color value of at least one element of the environment map corresponding to the pixel 9. The program storage device according to claim 8, wherein a value is derived, and the derived color value of the pixel is stored for display. 10. The program storage device according to claim 9, wherein a depth value associated with said pixel of said view window is stored in a depth buffer. 11. The at least one of the view windows covered by the bitmap image.
For pixels, the depth value associated with the pixel and the depth value associated with the at least one element indicate that the at least one element is closer to the view point than the pixel. 11. The program storage device of claim 10, further comprising: updating the depth value associated with the pixel of the view window according to the depth value associated with the at least one element of the bitmap image. . 12. The method of claim 11, further comprising the step of storing in a memory a depth value associated with said element of said environment map, wherein said depth value associated with said pixel of said view window is stored in said pixel of said view window. The program storage device according to claim 8, wherein the program storage device is derived from a depth value associated with at least one element of the environment map, which corresponds to the following.