Xerox Corporation

Andrew S Glassner

Maureen C Stone

David H Marimont

A method for coloring pixels of a pixelated display to present a simulated image of a view of objects illuminated by light from light sources and light reflected off the objects is used in an apparatus for coloring pixels to create an image. According to the method, a space is defined, along with objects and light sources in the space. A view point is taken and a view surface is divided into unit areas corresponding to pixels in the image. As the illumination of points on surfaces of objects in the space is found, a data structure is saved for that point indicating its location, its orientation, and the rays of illumination which reach the point, each ray described by a direction, source, color, propagator object, and propagator type. Rays from those propagator types which identify diffuse reflections off significantly diffuse objects are saved as nearby diffuse estimators, and are used for finding the illumination at a nearby shading point without searching the entire space above the shading point for diffuse reflections.

Image rendering system with local, adaptive estimation of incident

Methods for modifying shapes for display, represented as non-self-intersecting, simply connected, triangulated polyhedron of genus-O, defined as a plurality of triangular faces, each triangular face defined as a set of three coordinate points, eliminate concave edges in the shapes by performing pop or slide procedures on the concave edges. These procedures result in a visually smooth transformation of the concave shape to its convex hull, or to other shapes located therebetween.

Methods for converting concave polyhedra to their convex hulls

A method of rendering a color image on a designated output medium is disclosed which maps colors to the gamut of the designated output medium while preserving the semantic consistency of the object color and illumination information in the image. The method performs gamut mapping earlier in the image synthesis process than current gamut method methods, at the point where information about object primitives and their spectral attributes in a scene description is available, but after the fixed scene geometry has been determined by the rendering system. The method makes use of the output of a symbolic rendering system which produces symbolic pixel expressions, having basis spectra variables which represent the interplay of light and object primitives in the scene description, and spectral data having color information about the light and object primitives in the scene, and which is indexed to the basis spectra variables. The method performs spectral change calculations using the symbolic pixel expressions, the spectral data, and spectral information about the gamut of the specific output medium to determine the modifications to the original spectral data that need to be made to the individual object primitives in the scene in order to produce image pixel colors which are in the gamut of the output medium. The resulting image colors are locally and globally consistent with the semantics of the image, make effective use of as much of the available gamut of the display device as is possible, and require no further post-rendering gamut mapping prior to display or reproduction on the designated medium.

Method of rendering a color image for an output medium from symbolic

Methods for modifying shapes represented as non-self-intersecting, simply connected, triangulated polyhedra of genus-0, defined as a plurality of triangular faces, each triangular face defined as a set of three coordinate points, determine an ordering of concave edge elimination procedures which are required to smoothly convert a concave shape to its convex hull. The ordering technique attempts to avoid self-intersections and degeneracies in the metamorphs produced between the starting concave shape and its convex hull.

Sequencing and scheduling moves for converting concave polyhedra to

A method for constructing object-local sampling histories for efficient path tracing. The present invention provides a technique for efficiently producing computer generated two-dimensional synthetic images of three-dimensional scenes. Objects within in the scene (10) are assigned packs (30,36) containing one or more elements (32,38). For light reflective objects (19,O1), each element (32) of the object's pack (30) represents a region of the object's reflection hemisphere (30) through which incident light is equally likely to be reflected. For light transmissive objects (19,O1), the elements (32) represent analogous regions of equal transmission. For light emitting objects (L1), each element (38) of the object's pack (36) represents a region of equal light emission probability. In a recursive ray or path tracing algorithm, the pack (30,26) of each object (O1,L1) is interrogated to provide unused elements (32a,38a) corresponding to directional regions for sending transmitted (T1) or reflected (R1) backward-going rays, or for emitting illumination rays (I1 ). As each unused element (32a,38a) of an object's pack (30,36) is used, that element is marked as unavailable (32b,38b) until are elements are marked, when all elements are then unmarked (32a,38a) and the element selection process continues. The methods of the present invention insure that rays are directed through the scene in an image synthesis algorithm in directions most important for scene reconstruction, but ensuring that full coverage of all directions is maintained.

Growing community of inventors

San Francisco, CA, United States of America

Andrew S Glassner