ELECTRONICALLY GENERATED PERSPECTIVE IMAGES

• US 3,602,702 A
• Filed: 05/19/1969
• Issued: 08/31/1971
• Est. Priority Date: 05/19/1969
• Status: Expired due to Term

• Current Assignee: University of Utah Research Foundation (State of Utah)
• Original Assignee: John E. Warnock
• Inventors: Warnock, John E.
• Primary Examiner(s): Botz, Eugene G.
• Assistant Examiner(s): Smith, Jerry
• Application Number:
  US04/825,904
• Time in Patent Office: 834 Days
• Field of Search: 235/151,151PL 340/324.1,172.5 33/18C
• US Class Current: 345/421
• CPC Class Codes: G06T 15/10 Geometric effects
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G06T 15/50 Lighting effects
• CPC Class Codes: G09G 1/06 using single beam tubes G09G1/26, G09G1/28 take precedence, e.g. three-dimensional or perspective representation, rotation or translation of display pattern, hidden lines, shadows G09G1/28 takes precedence; stereoscopic TV-systems, details thereof H04N13/00; oscilloscopes for three-dimensional representation G01R13/206; vectorscopes G01R13/208

Abstract

A method and system for electronically generating and displaying shaded two-dimensional perspective images of three-dimensional objects in which sharp resolutions of intersections of the objects is maintained, by providing electrical signals representative of surfaces of the objects and determining the spatial relationship between these surfaces and progressively smaller portions of a two-dimensional view plane or the viewing screen of the display. These spatial relationships are then utilized to determine the surfaces to be displayed within each of the ultimate portions of the view plane or viewing screen.

Claims

1. A method for generating a perspective view display of a three-dimensional object on a two-dimensional display comprising:

providing input data defining surface of an object to be displayed;

converting said input data to represent projections of the surfaces of the objects on a two-dimensional view plane established according to the desired orientation of the objects;

progressively subdividing the area of said view plane into subdivisions;

determining the surfaces defined by the input data that are visible within each subdivision; and

, displaying the surfaces determined to be visible in areas of the display corresponding to the subdivisions.

2. The method of claim 1 wherein the progressive subdivision of the area of the view plane comprises successively subdividing each previous subdivision of a predetermined number of times or until a subdivision is either devoid of surfaces or entirely occupied by a single visible surface.

3. The method of claim 2 and further comprising:

determining the spatial relationship between each surface and the particular subdivision being checked;

ordering the surfaces according to their spatial relationship within the subdivision; and

checking the surfaces in the order established to determine whether the subdivision is devoid of any visible surfaces or entirely occupied by a single visible surface.

4. The method of claim 3 wherein the spatial relationships between each surface and each subdivision is determined by calculating the extent, if any, to which the surface occupies the subdivision, and wherein the ordering of the surfaces is determined in accordance with the calculated extents of occupation by the surfaces of the subdivision.

5. The method of claim 4 wherein the ordering of the surfaces established for a subdivision is retained intact by adjusting only the extents of occupation by the surfaces for successive subdivisions of that subdivision.

6. The method of claIm 1 wherein the object surfaces defined by the input data are planar polygons.

7. The method of claim 1 wherein the visibility of the surfaces defined by the input data is determined by calculating the distances of each surface from the view plane and comparing the calculated distances of the surfaces within each subdivision to determine which surface is closest to the view plane.

8. The method of claim 1 wherein the display is an electronic display, and wherein each visible surface is displayed by modifying the intensity of the display in accordance with a visual characteristic of that visible surface.

9. The method of claim 8 wherein the electronic display utilizes a raster scan display;

and wherein the visual characteristic for each surface is determined by calculating an intensity of illumination from a light source at a predetermined position at the point at which the surface to be displayed enters a scan line and thereafter incrementally changing the intensity of illumination along the scan line for the remainder of the surface to be displayed along that scan line.

10. The method of claim 1 wherein the subdivisions of the area of said view plane are two-dimensional areas.

11. The method of claim 1 wherein the progressive subdivision of the view plane comprises:

subdividing the area of the view plane into four subsquares;

successively subdividing each of said subsquares into four smaller subsquares; and

repeating the subdivision of the progressively smaller subsquares until the resolution limit of the display is reached or until a subsquare is either devoid of surfaces or entirely occupied by a single visible surface.

12. A method for generating a perspective view display of a three-dimensional object on a viewing screen of a two-dimensional display comprising:

providing input data defining surfaces of an object to be displayed;

progressively calculating the spatial relationship of each of said surfaces with subdivisions of the viewing screen of the display;

determining from the calculated spatial relationships which object surface defined by the input data is visible in a predetermined orientation of the object in each subdivision; and

, modifying the intensity of the subdivisions of the viewing screen of the display in accordance with the object surface determined to be visible therein.

13. The method of claim 12 wherein the visible surface within each subdivision is determined by calculating the distances of each surface in the subdivision from the viewing screen of the display and selecting the surface closest to the view plane.

14. The method of claim 12 wherein the object surfaces defined by the input data are planar polygons.

15. The method of claim 12 wherein the intensity of the display is modified by determining a visual characteristic of the visible surface in each subdivision.

16. The method of claim 15 wherein the visual characteristic of each surface is determined by calculating the apparent illumination of the surface from a light source at a predetermined position.

17. The method of claim 16 wherein the display utilizes a raster scan;

and wherein the calculated apparent illumination of each surface for modifying the intensity of the display is determined by calculating the apparent illumination of the surface at the point at which the surface to be displayed enters a scan line and thereafter incrementally varying the apparent illumination along the scan line.

18. The method of claim 12 wherein the subdivisions are established by first subdividing the viewing screen into a plurality of subdivisions and further subdividing each previous subdivision in the same manner until the resolution limit of the display is reached or until a subdivision is either devoid of surfaces or entirely occupied by a single visible surface.

19. The method of claim 18 wherein the visible surface within each subdivision is determined by ordering all of the surfaces for each subdivision according to their spatial relationship with that subdivision;

checking each surface in the order established to determine whether the subdivision is devoid of all surfaces or entirely occupied by a single visible surface;

identifying a view plane according to the predetermined orientation of the objects; and

selecting the single visible surface entirely occupying the subdivision if it exists or the surface determined to be closest to the specified view plane if the resolution limit of the display has been reached.

20. The method of claim 19 wherein the spatial relationships of an object surface within a subdivision is determined by ascertaining the extent to which said surface occupies the subdivision;

and wherein the ordering of the surfaces is in descending degree of occupation of a subdivision.

21. The method of claim 20 wherein the ordering of the surfaces is established for a subdivision and is saved and reused for successive subdivisions of that subdivision.

22. The method of claim 18 wherein the subdivisions of the viewing screen are two-dimensional areas.

23. A method for generating a perspective view of a three-dimensional object on a viewing screen of a two-dimensional display comprising:

supplying electric signals representative of data defining surfaces of an object to be displayed;

electronically calculating the spatial relationship of the surfaces defined by the electrical signals with resPect to progressively smaller subdivisions of the viewing screen of the display;

generating electrical signals representing the spatial relationships determined, electronically calculating from the electrical signals representing the spatial relationships the surface which is to be displayed in each subdivision of the viewing screen of the display, and displaying in each subdivision of the viewing screen of the display the surface calculated to be displayed in that subdivision.

24. The method of claim 23 wherein the subdivisions of the viewing screen are areas in the plane of the viewing screen.

25. The method of claim 23 further comprising:

specifying an observation point from which the objects to be displayed are considered to be viewed, and wherein the surface defined by the electrical signals to be displayed in each subdivision of the viewing screen of the display is determined by selecting the surface closet to said specified observation point.

26. The method of claim 25 wherein the surfaces to be displayed in each subdivision are calculated by storing the electrical signals representative of the spatial relationships in a storage device;

ordering the stored electrical signals according to the extent to which the surfaces represented thereby occupy the subdivision;

calculating from the supplied electrical signals the distance each surface which occupies the subdivision to some extent is behind the subdivision;

comparing the calculated distances to determine which surface is closest to the subdivision; and

displaying the surface determined to be closest to the subdivision.

27. The method of claim 23 wherein the display comprises an electronic raster scan display, and wherein the surface calculated to be displayed in each subdivision is displayed by modifying the intensity of the display in accordance with an electronically calculated apparent illumination of the surface from a predetermined light source at the point at which the surface enters each scan line and incrementally varying the intensity along the scan line until that surface exists therefrom.

28. The method of claim 23 wherein the surfaces defined by the electrical signals are planar polygons specified by electrical signals defining their vertex points.

29. The method of claim 23 wherein the display is an electronic display the intensity of which is modified in accordance with a visual characteristic of the surface to be displayed.

30. The method of claim 29 wherein the visual characteristic of each surface to be displayed is a calculated apparent illumination of that surface from a predetermined light source.

31. The method of claim 23 wherein each of the progressively smaller subdivisions of the viewing screen of the display is formed by first subdividing said viewing screen into a plurality of subdivisions and further subdividing each previous subdivision to a predetermined degree unless the calculated spatial relationships of the surfaces indicate that the subdivision is either devoid of any surfaces or entirely occupied by a single surface which is closest to that subdivision in the desired orientation of the object.

32. A method for generating perspective images of a three-dimensional object on a two-dimensional display comprising, providing input data defining surfaces of the object to be displayed, calculating the spatial relationship of each of said surfaces with respect to subdivisions of the screen of the display, ordering the input data defining the surfaces for each subdivision according to the calculated spatial relationship of the surfaces with respect to that subdivision, checking each surface in the order established to determine the surface visible in the desired orientation of the object in that subdivision, and displaying in each subdivision of the screen the surface determined to be visible in that subdivision.

33. The method of claim 32 wherein the subdivisions of the screen of the display are determined by successively subdividing previous subdivisions until the resolution limit of the display is reached or until a subdivision is either devoid of all surfaces or entirely occupied by a single visible surface.

34. The method of claim 33 wherein the order established for the surfaces for previous subdivisions is retained in the checking performed for subdivisions thereof.

35. The method of claim 34 wherein the visible surface within each subdivision is determined by calculating the distance behind the subdivision of each surface which occupies that subdivision to some extent, comparing the calculated distances to determine which surface is closest to the subdivision, and selecting as the visible surface the surface closest to the subdivision.

36. The method of claim 35 wherein the surfaces defined by the input data are planar polygons specified by their vertex points.

37. The method of claim 36 wherein the subdivisions of the screen are two-dimensional areas of the screen.

38. A system for generating a perspective image of a three-dimensional object comprising:

input means for providing input data representative of the surfaces of an object;

a first calculating means connected to said input means for determining the spatial relationships between said surfaces defined by said input data and calculated subdivisions of an image plane on which the perspective image is formed;

a second calculating means connected to said first calculating means for determining the surfaces to be displayed in said calculated subdivisions; and

display means connected to said second calculating means for displaying the surfaces determined to be displayed by said second calculating means in areas corresponding to said calculated subdivisions.

39. The system as defined in claim 38 and further comprising:

subdivider means connected to said first calculating means for calculating the required subdivisions of said image plane in response to said spatial relationships determined by said first calculating means.

40. The system as defined in claim 39 wherein said subdivider means calculates progressively smaller subdivisions in response to said spatial relationships determined by said first calculating means.

41. The system as defined in claim 39 wherein the spatial relationships determined by said first calculating means is the extent, if any, of the occupation of said subdivisions by said surfaces.

42. The system as defined in claim 41 wherein said subdivider means calculates said progressively smaller subdivisions by subdividing previously calculated subdivisions.

43. The system as defined in claim 42 and further comprising:

a storage means for storing said spatial relationships; and

a control means connected between said storage means and said first calculating means for controlling the operation of said first calculating means in determining the spatial relationships of newly calculated subdivisions in accordance with the spatial relationships determined for said previously calculated subdivisions which were subdivided by said subdivider means to form said newly calculated subdivisions.

44. The system as defined in claim 43 wherein said surfaces represented by said input data re planar polygons.

45. In a method of electrically producing at a display a two-dimensional perspective image of a three-dimensional object:

defining the object in data representing the three-space location of surfaces of the object;

converting three-space data into data descriptive of the location of surfaces of a two-space perspective representation;

relating the two-space data to two-space coordinates of subdivisions of the display;

determining which surfaces of the two-space object are visible within selected subdivisions of the display; and

utilizing the two-space data having to do with the visible surface to create the two-dimensional perspective image at the display.

46. AppAratus for electrically producing on a display a two-dimensional perspective image of a multisurface three-dimensional object, the improvements comprising:

means for providing data representing two-dimensional coordinates of subdivisions of the display;

a visible surface calculator comprising means spatially relating data representing two-dimensional coordinates of surfaces of the objects to two-dimensional coordinates defining subdivisions of the display; and

means segregating the display-related surface coordinate data having to do with visible surfaces from the corresponding data having to do with surfaces which are not visible.

47. An electronic system for generating a perspective image of a three-dimensional object on a two-dimensional display comprising:

input means for supplying electrical signals representative of the surfaces of an object;

a transformation calculating means connected to said input means for converting said electrical signals to represent the projections of said surfaces on a two-dimensional view plane;

a subdivider means for calculating subdivisions of said view plane;

a spatial relation calculating means connected between said transformation calculating means and said subdivider means for determining the spatial relationship of each of said projected surfaces defined by said converted electrical signals with respect to said calculated subdivisions;

control means connected to said spatial relation calculating means and said subdivider means for determining which of said projected surfaces defined by said converted electrical signals would be visible within each of said calculated subdivisions in the desired orienation of the object; and

a two-dimensional display means connected to said control means for displaying said visible surfaces in areas of the display screen corresponding to the calculated subdivision in which said surfaces are visible, said display means receiving electrical signals from said control means representative of the visible surfaces and the calculated subdivisions in which said surfaces are determined to be visible.

48. The electronic system as defined in claim 47 wherein said subdivider means calculates progressively smaller subdivisions by subdividing previously caLculated subdivisions;

and wherein said control means controls the operation of said spatial relation calculating means for newly calculated subdivisions responsive to the spatial relationships determined for said previously calculated subdivisions.

49. The electronic systems as defined in claim 48 wherein said surfaces represented by the electrical signals are planar polygons specified by electrical signals representing the vertex points of said polygons.

50. A method for generating a perspective image of an object on a display comprising:

providing input data representative of the surfaces of an object;

calculating the spatial relationships of said surfaces with spatial subdivisions in relation to said object;

determining from said spatial relationships the surfaces to be displayed; and

displaying said surfaces on a display.

51. A method for generating a perspective image of an object on a display comprising:

providing input data representative of the surfaces of an object;

calculating the spatial relationships of said surfaces with spatial subdivisions selected in accordance with said object;

determining from said spatial relationships the surfaces to be displayed; and

displaying said surfaces on a display.