Method for adaptively providing near phong grade shading for patterns in a graphics display system

Abstract

A method for producing realistic shading of three-dimensional objects depicted in a graphics display system. Computationally efficient Gouraud shading is practiced in the rendering of images which routinely require Phong shading to obtain suitable realism. Gouraud shading is adaptively applied to polygon regions of preferably triangular shape at a granularity defined by heuristically derived relationships using surface normal vectors, incident light vectors and relative pixel separation information. When division of the base triangle is dictated, the methodology produces a mesh of polygons sized to be individually rendered with Gouraud shading yet provide Phong-like realism for the whole of the original polygon region.

We claim: 
     
       1. An adaptive method for shading patterns in a graphics rendering system, comprising the steps of: selecting a polygon within a graphic pattern to be shaded, said selected polygon having a plurality of vertices, each vertex having vector characteristics;   comparing the vector characteristics of the vertices;   dividing the selected polygon into further polygons, thereby defining at least one new vertex, when the selected polygon vector characteristics differ materially from each other;   computing vector characteristics of the at least one new vertex; and   using interpolation to shade the polygons.   
     
     
       2. The method recited in claim 1, wherein the selected polygon is a triangle. 
     
     
       3. The method recited in claim 2, wherein the vector characteristics for each vertex includes a selected surface normal vector and an incident light vector. 
     
     
       4. The method recited in claim 3, wherein the interpolation includes Gouraud shading the polygons. 
     
     
       5. The method recited in claim 1, wherein the vector characteristics relate to selected surface normal vectors and incident light vectors at the polygon vertices. 
     
     
       6. The method recited in claim 5, wherein the interpolation includes Gouraud shading the polygons. 
     
     
       7. A method for using interpolation to shade a graphic pattern including three-dimensional objects in a graphic display system, comprising the steps of: selecting a polygon within the graphic pattern to be shaded, said selected polygon having multiple vertices, each vertex having vector characteristics;   comparing the vector characteristics of the vertices including related surface normal vectors and incident light vectors;   dividing the selected polygon, thereby defining at least one new vertex, when the vector characteristics differ materially from each other;   computing vector characteristics of the at least one new vertex; and   using Gouraud shading to determine lighting for the polygons.   
     
     
       8. The method recited in claim 7, wherein the polygon is a triangle. 
     
     
       9. The method recited in claim 8, wherein the step of dividing includes partitioning the selected triangle into two or more triangles. 
     
     
       10. A method for using interpolation to shade three-dimensional objects in a graphic display system, comprising the steps of: a) selecting a triangle within the graphic pattern to be shaded, said selected triangle having multiple vertices, each vertex having vector characteristics;   b) comparing the vector characteristics of the vertices using related surface normal vectors and incident light vectors, said comparing including the steps of: i) calculating cross products of selected surface normal vectors and a related incident light vector;   ii) calculating a dot product of two cross products to determine an orientation of the related incident light vector;   iii) calculating first and second dot products of the selected surface normal vectors and the related incident light vector;   iv) relating the first and second dot products and the orientation of the incident light vector to a distance between the selected surface normal vectors; and     c) dividing the selected triangle into two or more triangles, thereby defining at least one new vertex, when the vector characteristics differ materially from each other and the distance between the surface normal vectors is large;   d) computing vector characteristics of the at least one new vertex; and   e) using Gouraud shading to determine the lighting for the triangles.   
     
     
       11. The method recited in claim 10, wherein the step of dividing is comprised of: selecting a triangle edge having a largest number of vertices;   projecting triangle division lines from the selected edge to a vertex opposite that edge; and   further partitioning regions defined by the partitioning in relation to a number of vertices ascribed to a second side of the triangle.