Method and apparatus for simulating movement in multidimensional space with polygonal projections

• US 5,694,531 A
• Filed: 11/02/1995
• Issued: 12/02/1997
• Est. Priority Date: 11/02/1995
• Status: Expired due to Term

• Current Assignee: Immersive Licensing, Inc.
• Original Assignee: Infinite Pictures
• Inventors: Eggert, Jonathan A., Golin, Stuart J.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/552,299
• Time in Patent Office: 761 Days
• Field of Search: 395/118, 395/100, 395/119, 395/125, 395/127, 345/139
• US Class Current: 345/419
• CPC Class Codes: G06T 15/20 Perspective computation

Abstract

A method and apparatus for generating views of an environment with proper perspective and parallax. This invention captures panoramic views at many points in the environment and stores them as planar polygons, which have been extended to include imagery occluded at their viewing position but visible at nearby points. Three-dimensional information on the environmental source of these polygons is determined and stored, enabling the playback system to simulate parallax as well as to produce stereographic images. Given a location and orientation in the environment, the playback system finds a nearby capture point and translates the polygons at that point to the specified location, producing an image. It then rotates that image to the desired orientation which it then displays.

Claims

1. A method for simulating movement within a multidimensional CG or natural environment by displaying an image at a specified viewpoint and orientation within said environment, where said viewpoint and orientation specify the location and direction of a point of view, the method comprising the steps of:

a) forming a database of the environment in a computer-readable storage medium by;

i) determining a set of k-points in the environment, each k-point within said set having a domain within the environment and playback data associated therewith, said k-point domain forming a range of supported viewpoints and orientations, each of said k-points being defined as a center of projection;

ii) projecting the environment onto a planar surface at a predetermined orientation to form a corresponding k-projection;

iii) segmenting said corresponding k-projection into one or more k-polygons; and

iv) for each said k-polygon, determining an e-polygon, said e-polygon being a planar polygon that approximates an area in the environment, said k-polygon being a projection of said area;

b) finding the k-point in the database whose domain supports the specified viewpoint and orientation;

c) mapping the k-projections at said k-point to said viewpoint and orientation to form said image; and

d) displaying said image.

2. The method of claim 1, wherein the step of projecting the environment includes:

a) capturing a fisheye image with a camera having a fisheye lens;

b) mapping said fisheye image to a sphere to form a mapped fisheye image; and

c) projecting said mapped fisheye image onto a planar surface at a predetermined orientation to form a corresponding k-projection.

3. The method of claim 1, wherein the step of projecting the environment includes capturing said k-projection with a planar camera.

4. The method of claim 1, wherein the step of projecting the environment includes:

a) capturing a planar projection with a planar camera; and

b) rotating said planar projection to a predetermined orientation to form a corresponding k-projection.

5. The method of claim 1, further including manually determining k-polygons known to be projections of approximately planar areas in the environment, segmenting the k-projections into the determined k-polygons.

6. The method of claim 1, the e-polygons being based on a three-dimensional polygon-based model, wherein the segmentation step further includes:

a) associating an e-polygon with a model polygon;

b) consolidating the e-polygons when the resulting parallax error is lower than a predetermined limit;

c) continuing said consolidation step at least until the number of consolidated e-polygons is reduced to a predetermined limit; and

d) projecting the e-polygons onto a planar surface to form the corresponding k-polygons.

7. The method of claim 1, further including registering a k-polygon at one or more nearby k-points to determine the corresponding e-polygon.

8. The method of claim 1, wherein the k-polygons of a k-point are extended to support the domain of said k-point by:

a) determining an occluded area in the environment that is visible at a viewpoint in said domain but occluded at said k-point;

b) finding a nearby k-point containing said occluded area; and

c) mapping said occluded area from said nearby k-point to said k-point.

9. The method of claim 1, wherein the mapping step further includes translating the k-polygons of a k-projection to the specified viewpoint.

10. The method of claim 9, further including consolidating the e-polygons and their corresponding k-polygons.

11. The method of claim 9, further including translating a second time to produce stereographic images.

12. The method of claim 1, wherein the mapping step further includes rotating the orientations of said k-polygons or k-projections to the specified orientation.

13. The method of claim 1, wherein the mapping step further includes translating the k-polygons to the specified viewpoint and rotating the orientations of said k-polygons or k-projections to the specified orientation.

14. The method of claim 1, further including compressing said k-polygons or said k-projections.

15. The method of claim 1, further including identifying the list-priority order of the k-polygons in said database.

16. The method of claim 1, wherein mapping further includes using nearby k-images to compensate for occlusion.

17. The method of claim 1, wherein the environment is projected to a non-planar surface, such as that of a cylinder.

18. The method of claim 1, wherein the segmentation is into curved areas.

19. The method of claim 1, wherein all information is determined from a CG model.

20. A method for constructing a 3-dimensional model of an environment consisting of the following steps:

selecting a reference image having image pixels;

selecting a target image having image pixels;

manually segmenting the reference image into at least one polygon, said polygon being a projection of an area in the environment that is approximately planar;

defining a planar model of said area;

defining registration results as the relationship between image pixels in the reference image and those of the target image;

registering the polygon in the reference image with the target image, determining said registration results; and

fitting the registration results to the planar model.

21. The method of claim 20, wherein the registration step further includes applying an epipolar constraint.

22. The method of claim 20, wherein the registration step further includes:

segmenting the polygons into a plurality of blocks; and

separately registering the blocks.

23. The method of claim 22, further including:

determining confidence weights for each of the blocks; and

applying said confidence weights when fitting the registration results to the planar model.