Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-02-25
2004-03-30
Padmanabhan, Mano (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S581000, C345S582000
Reexamination Certificate
active
06714195
ABSTRACT:
The present invention is concerned with image processing apparatus, and is particularly concerned with the processing of images consisting of scenes involving objects in three dimensions (3D).
In the field of computer graphics, an object surface is commonly represented by means of a series of polygons, most usually triangles. Those triangles can be described in terms of the coordinates of their vertices in 3D space, which can be stored as 3D object data in a memory. The representation of an object surface is computationally inexpensive in the event that the object surface is generally free of detailed relief. In that case, the object surface can be represented by relatively large triangles, which results in relatively little object data being created to describe the triangles. In that way, relatively little memory is required in the computer in order to describe the object surface.
However, if a surface has quite detailed surface relief features, then a large number of very small triangles may be required in order to describe that surface. In that case, the description of the surface can result in the creation of a large amount of object data, the conversion of which into image data can be computationally expensive.
Therefore, in the past, it has been found convenient to describe an object surface in two stages which are briefly described below.
Firstly, the general outline of the object surface is described, using the method described above involving a mesh of triangles. It will be understood that alternative methods of describing an object surface are available, such as by using control points to define a bezier (or other spline) surface, or by providing a mathematical equation of which the surface is a locus.
Secondly, a texture bit map is overlaid over the triangles forming the general outline of the object surface. That texture bit map includes detail which gives the viewer the impression that a relief feature is present, but where the feature is actually described by areas of contrasting colour and shading. The texture bit map may itself be defined over a unit square in a two dimensional space with coordinates (u,v). In the case that a texture bit map is not defined over a unit square, it is possible to map the definition space to that of a unit square. Vertices in the 3D space are given (u,v) coordinates, and the bit map can be clipped to triangles in the mesh by interpolation between the vertices, and finding correspondences between points in the triangles and points in the bit map.
For example, an object consisting of a graphical representation of a metalled road can be described in terms of a series of relatively large triangles, in view of the fact that the object has a generally flat overall surface. However, in order to represent the roughness of the road, or potholes in the road, using triangles, a large number of relatively small triangles would be required. Therefore, it is convenient to illustrate a feature such as a pothole or surface roughness in terms of its appearance, without being concerned with its shape. Accordingly, a texture bit map can be overlaid over the general outline surface of the road (defined by a mesh of large triangles), the texture bit map including a region shaded a darker colour than the rest of the road to represent the appearance of the pothole. The texture bit map could include a “mottled” pattern in order to represent the appearance of surface roughness.
That depiction of relief features of an object is reasonably effective when the viewpoint of the object is some distance away from the object. However, it becomes apparent to the viewer how the relief feature has been simulated once the viewpoint becomes much closer to the object. This can lead to deterioration in the overall impression of the quality of the image, and is therefore undesirable.
“Shade Trees” by Robert L Cook (Computer Graphics Volume 18 Number 3, July 1984, pp 223-231) proposes the use of displacement maps to simulate texture more effectively than texture maps. Displacement maps modify positions of points in the final shading process, whichever process is employed.
A first aspect of the invention provides apparatus and a method which augments a texture bit map with further geometry which allows an object to which the texture bit map is applied to include real 3D geometry corresponding to the texture apparently modelled by the texture bit map.
This contrasts with the method described in the paper by Cook, which merely modifies point positions on a piecemeal basis. The present invention is advantageous because it incorporates the further geometry into the data structure defining the object to be illustrated.
A second aspect of the invention provides computer graphic apparatus comprising means for storing information defining a three dimensional object to be displayed, means for storing information defining a texture to be applied to the object, and means for storing information defining additional three dimensional geometry to be superimposed over the texture in use.
A third aspect of the invention provides means for graphically representing a three dimensional object, including first storage means for storing information defining the underlying shape of said object, and second storage means for storing information defining detailed shape of said object, and means for imposing said information in said second storage means over said information in said first storage means.
In that third aspect, the imposition means may be operative to impose provided that said underlying shape is closer to a nominal viewer than a predetermined threshold.
Preferably, the further geometry includes means for indicating whether or not an individual element of that geometry is to be displayed. In that way, finer control of edges of underlying geometry can be achieved, potentially reducing aliasing.
REFERENCES:
patent: 5253339 (1993-10-01), Wells et al.
patent: 5563989 (1996-10-01), Billyard
patent: 5579454 (1996-11-01), Billyard et al.
patent: 5602979 (1997-02-01), Loop
patent: 5666472 (1997-09-01), Huddy
patent: 5757321 (1998-05-01), Billyard
patent: 5777620 (1998-07-01), Billyard
patent: 6128019 (2000-10-01), Crocker et al.
patent: 6208347 (2001-03-01), Migdal et al.
patent: 6246414 (2001-06-01), Kawasaki
patent: 6356280 (2002-03-01), Kamen et al.
patent: 6456287 (2002-09-01), Kamen et al.
patent: 0 366 463 (1990-05-01), None
patent: 0 590 995 (1994-04-01), None
patent: 0 596 667 (1994-05-01), None
patent: 0 806 744 (1997-11-01), None
patent: 0 996 094 (2000-04-01), None
patent: 03-271877 (1991-03-01), None
patent: WO 99/53445 (1999-10-01), None
Rabinovich et al (“Visualization of Large Terrains in Resource-Limited Computing Environments”: 0-8186-8262-0/97 1997 IEEE.*
Miyata (“A Method of Generating Cloud Images Using Density Contour Lines”: The Transactions of the IEICE, vol.E.72, No. 6 Jun. 1989).*
R. Cook, “Shade Trees”, Computer Graphics, vol. 18, No. 3, Jul. 1984, pp. 223-231.
J. Foley et al., “Illumination and Shading”, Computer Graphics, Second Edition, Principles and Practice, pp. 806-812.
A.A.M. Kuijk et al., “Faster Phong Shading Via Angular Interpolation”, Computer Graphics Forum, No. 8, pp. 315-324, (1989).
M. Shantz et al., “Shading Bicubic Patches”, Computer Graphics, vol. 21, No. 4, pp. 189-196, (Jul. 1987).
C. Bajaj et al., “Smoothing Polyhedra Using Implicit Algebraic Splines”, Computer Graphics, vol. 26, No. 2, pp. 79-88, (Jul. 1992).
G. Farin, “Triangular Bernstein-Bézier pa”, Computer Aided Geometric Design, No. 3, pp. 83-127, (1986).
M.J. Castro Diaz, “Mesh Refinement Over Triangulated Surfaces”, Inria Research Report, pp. 1-40, (Oct. 1994).
Xia, Julie C. et al., “Adaptive Real-Time Level-of-Detail-Based Rendering for Polygonal Models”, IEEE Transactions on Visualization and Computer Graphics, IEEE Service Center, vol. 3, No. 2, pp. 171-183, (Apr. 1, 1997).
J. Foley et al., Computer Graphics Principles and Practice, Second Edition, pp. 664-680.
Barequet, Gill et al., “RSVP: A Geometric Toolkit for Controlled Repair of Solid Models”, IEEE Transactions on Visualizati
Billyard Adam Michael
Ezra Rabin
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Padmanabhan Mano
LandOfFree
Image processing apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image processing apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image processing apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3222391