Raster image mapping

This invention relates to computer graphics and, more particularly, to a method of mapping a two-dimensional raster based image onto surfaces of a three-dimensional vector based image model.

Background

Computer graphics software and technology is used to creates visual images from digital data. Images may be created in two dimensions (2-D) or, alternatively, images may be generated from object models defined in three dimensions (3-D).

Two dimensional images may be created and stored as either resolution-dependent raster images or as resolution-independent vector images. Raster images are composed of a predetermined number of picture elements (pixels). The level of detail in a raster image is determined by the number of pixels in the image and is therefore limited when the image is created. Alternatively, two dimensional images may be stored as vector images. Vector images are created and stored as resolution-independent mathematically defined lines and curves. Prior to printing or display, a 2-D rendering process converts the mathematically defined lines and curves to pixels. Vector image 2-D rendering may be accomplished by software in the computer system or may be accomplished by software residing in the display device, such as by a PostScript™ interpreter in a laser printer.

Three dimensional models may also be used to create graphic images. Three dimensional resolution-dependent models may be created using a 3-D array of discrete volume elements known as voxels. The level of detail in a voxel based 3-D model is determined by the number of discrete voxel elements and generally cannot be increased. Voxel based 3-D models are not further addressed in this disclosure.

Three dimensional models may also be created in a resolution-independent format. Resolution-independent 3-D models may be stored as parametric surfaces mathematically defined on x, y, and z axes, alternatively, polygon based surface models in which modeled object surfaces are approximated by many small polygonal facets may be used, still other modeling alternatives include, for example, non polygon-based models as well as alternative coordinate systems, such as polar coordinate systems.

To print or display a 3-D model, a 3-D rendering process is used to create a 2-D view of 3-D object surfaces as if the object were being viewed from a particular point in 3-D space. The 3-D rendering process may be either resolution-dependent or resolution-independent. Resolution-dependent rendering produces a 2-D view having a fixed number of pixels. Resolution-dependent 3-D rendering is described in, for example, Foley, et al., Computer Graphics: Principles and Practice, 2nd ed., Addison Wesley Publishing company, 1990, ISBN 0-201-12110-7. Alternatively, 3-D rendering may be resolution-independent. Resolution-independent 3-D rendering produces a 2-D vector image view of the modeled object. A 2-D rendering process is subsequently used to enable printing or display of the produced 2-D vector image. Resolution independent 3-D rendering is provided by software products such as Adobe Dimensions 2.0™ and is described in U.S. Pat. No. 5,544,291 entitled Resolution-Independent Method For Displaying a Three Dimensional Model in Two-Dimensional Display Space.

During 3-D rendering, details may be added to rendered 3-D model surfaces by use of image mapping techniques. Mapping of 2-D raster images to 3-D object surfaces during resolution dependent 3-D rendering is known and described by, for example, Foley, et al. Similarly, mapping of 2-D vector images to 3-D object surfaces during resolution-independent 3-D rendering is known and is provided by, for example, Adobe Dimensions 2.0™ software. Graphic image creation would be further aided by computer graphics systems allowing precise mapping of 2-D raster images to resolution-independent 3-D renderings.

Summary

In general, in one aspect, the invention features a method for rendering a 2-D resolution-dependent raster image mapped onto 3-D resolution-independent surface-modeled object surface. The method includes mapping the 2-D raster image to a portion of a 2-D parametric map of a 3-D object, rendering the 3-D object as a 2-D vector resolution-independent output, and mapping the mapped raster image from the 2-D parametric map to a 2-D output space.

Preferred embodiments of the invention include one or more of the following features. The method includes creating a 3-D parametric surface model of the object. The method includes using the 3-D parametric surface model to define a 2-D parametric representation of at least a portion of the surface of the object. The method includes clipping the 2-D vector output of the model according to the projected outline in the 2-D display space. The method includes displaying the 2-D parametric representation to a user. The method includes displaying a 2-D resolution-dependent raster image on the displayed parametric representation in response to user input. The method includes defining outline of the raster image by establishing an outline curve around the raster image. The raster image to be applied to the 3-D model is a portion of a larger raster image, and the outline defines the portion of the larger image that is to be applied. The outline curve is established automatically as the outline of the raster image as displayed on the parametric representation. The outline curve is established before the raster image is placed on the displayed parametric representation. The outline curve is established by an edge detection process applied by the user to the raster image. The outline curve is established by the user creating a mask on the raster image , the outline of the mask defining the outline curve. The method includes displaying orientation information on the display of the parametric representation of the surface. Displaying orientation information includes displaying marks selected from the group consisting of a silhouette curve showing a boundary of consistent-facing regions of the surface and a set of grid lines in two dimensions. The method includes integrating the clipped raster image with the 2-D vector output to generate a final output. The method includes mapping the raster image to the 3-D space of the model and projecting the mapped raster image to the 2-D display space, and clipping the projected raster image according to the projected outline in the 2-D display space. The method includes integrating the clipped raster image with the 2-D vector output to generate a final output. The method includes delivering the projected raster image, a clipping path made according to the projected outline, and the 2-D vector output to an output device having a print engine operating to render the 2-D vector output to device raster output. The output device is a PostScript language printing device.

In general, in another aspect, the invention features a computer program, residing on a computer-readable medium, having instructions for causing a computer to render a two-dimensional resolution-dependent raster image as applied to a three-dimensional surface modeled object, in accordance with the methods of the invention.

Among the advantages of this invention are the ability to map 2-D resolution dependent raster images onto 3-D resolution independent surface rendering thereby providing a high quality two-dimensional output. Additionally, the invention allows precise placement of 2-D raster images on the 3-D surfaces and provide a three-dimensional rendering method that is compatible with existing computer display and printing equipment. A further advantage of the present invention is a reduction in computer and printer memory required by high resolution images. The reduction of memory is realized by eliminating the rasterization of the 3-D vector part of the image before combining with the 2-D raster images.

Other features and advantages of the invention will become apparent from the following description and from the claims.

Description of the Drawing

<ul id="ul0001" list-style="none" compact="compact"><li>Fig. 1A is a two-dimensional raster image.</li><li>Fig. 1B is a two-dimensional vector image.</li><li>Fig 2A is a wire frame representation of a 3-D sphere and a 3-D cube.</li><li>Fig. 2B is a rendered view of the objects in Fig. 2A.</li><li>Fig. 3 is a flowchart of a computer program implementation of the method of the invention.</li><li>Fig. 4 is a detailed flowchart of a computer program implementation of the rendering step of the method of the invention.</li><li>Fig. 5 is a 3-D object with Indicated Parametric Space Mapping paths u and v.</li><li>Fig. 6 is a Parametric Space Mapping of the Sphere of Fig. 5.</li><li>Fig. 7 illustrates a 2-D raster image of a leaf being associated with parametric space areas by dragging the leaf image onto portions of the parametric space.</li><li>Figs. 8A and 8B illustrate the application of a clipping path to a raster image.</li><li>Fig. 9A and 9B illustrates a rendering of a 2-D raster image and a 3-D vector image, as viewed from two different points in 3-D space, according to the invention.</li><li>Fig. 10 illustrates a computer and computer elements suitable for implementing the invention.</li></ul>

Detailed Description

Referring to Fig. 1A, a two-dimensional (2-D) raster image 100 is shown. A raster image, such as image 100, consist of a grid, or raster, of discrete picture elements known as pixels. The grid is typically defined having discrete points along two orthogonal axes. Referring to Fig 1B, a 2-D vector image 150 is shown. 2-D vector images are made up of mathematically defined lines, curves, and paths called vectors. 2-D vectors are typically defined on a pair of continuously defined orthogonal axes.

Referring to Fig. 2A, a "wire frame" view 200 of a 3-D model is illustrated. The view 200 shows 3-D object surfaces and relative object positions. Referring to Fig. 2B, a "rendered" view 250 of a 3-D model may also be displayed. In a rendered view, surface features such as surface color and shading may be displayed.

Referring to Figs. 3 and 5, in an illustrative computer program implementation of a 3-D modeling and drawing program, the method of the invention begins in step 301 with the input of a 3-D object 500 that has surfaces defined in 3-D modeling space along, for example, coordinates (x, y, z). The object 500 may be input from a computer hard disk or other storage media or may be created by a user of the modeling program. Next, in step 302, all or a selected portion of the surfaces of the 3-D object are mapped from three-dimensional space back to points in two-dimensional parametric space.

The mapping of the surface of an object in 3-D space to 2-D space is known as a parametric space mapping. A parametric space mapping relates coordinates along a continuously defined 3-D surface to coordinates in two-dimensional space. Referring to Figs. 5 and 6, to perform the parametric space mapping of the object 500, a two-dimensional parametric space 600 with axes (u, v) is defined. Points in the defined parametric space 600 may be associated with points on the 3-D object 500 by defining corresponding parameters (u, v) on the surface of the 3-D object 500. Mapping from points in the 2-D (u, v) parametric space to surfaces defined in 3-D space along coordinates (x, y, z) is performed using a mapping function f defined such that <maths id="math0001" num=""><math display="inline"><mrow><mtext>(x, y, z) = f(u, v)</mtext></mrow></math><img file="EP0889437A2_D0001.tif" /></maths>. This function is reversible using the inverse function f^-1 such that <maths id="math0002" num=""><math display="inline"><mrow><msup><mrow><mtext>(u, v) = f</mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mtext>(x, y, z)</mtext></mrow></math><img file="EP0889437A2_D0002.tif" /></maths>, thereby allowing points to be mapped from the 3-D surface back to the 2-D parameter space.

For example, still referring to Figs. 5 and 6, a parametric space mapping of a sphere 500 relative to a rectangular two-dimensional coordinate system may be created by defining u and v along the surface of the sphere 500 such that u and v form orthogonal paths on the surface. Using the defined u and v paths, the curved surfaces of the sphere is mapped to a two-dimensional parametric space 600. Note that although the illustrated mapping has a rectangle parametric space mapping 600, alternative parametric space mapping functions may be advantageously employed yielding non-rectangular mapping spaces. Familiar examples from cartography include cylindrical, pseudo-cylindrical, conic, and azimuthal mappings. Mapping may be based on tables of coordinates, rather than a formula, such as in the Robinson cartographic projection.

As indicated in Step 304, a two-dimensional parametric space may include optional display features indicating 3-D model characteristics. For example 3-D models have forward facing surfaces that are visible from a particular viewpoint and have backward facing surfaces that are not visible from the viewpoint. Forward and backward facing surfaces may be indicated in the displayed 3-D parametric surface mapping by the use of a silhouette function. A silhouette function applies predetermined colors or patterns to distinguish the backward and forward facing surfaces. Referring to Fig. 6, the backward facing surfaces of sphere 500 are represented by a gray silhouette 602 and the forward facing surfaces are represented without shading 601. Additionally, the 3-D model and the 2-D parametric space may include grid lines to aid in the accurate placement of 2-D raster images on the surface of the 3-D model, for example grid line 505 in Fig. 5 and grid line 605 in Fig. 5.

Referring to Figs. 1, 3 and 7, in step 305 of the method, a 2-D raster image 100 that is to be mapped to the 3-D surface 500 is selected. The two-dimensional raster image 100 may optionally be shown in a separate graphic user interface window. Subsequently, in step 306, the user designates the mapping of the 2-D raster image 100 to the surface of the 3-D model by associating regions of the 2-D raster image with regions of the parametric space 600. Using a conventional graphical user interface, this association of regions may be accomplished by using a computer pointing device, such as a mouse, to move displayed sections of the raster image over displayed sections of the parametric space. This is illustrated in Fig. 7 in which a raster image 100 (See Fig. 1 description of the raster image) is placed on the parametric space of the sphere 500, thereby invoking software functionality to associate the 2-D raster image 100 with the parametric space sections the raster image covers.

Referring now to Fig. 4, in Step 307, mapping of the raster image and rendering of the 3-D image begins. In step 308, a 3-D rendering of the object 500 produces a resolution independent 2-D vector image of the object as viewed from a particular point in 3-D space. During this rendering step, shading may be applied to the surfaces of the object in known fashion. Subsequently, in step 309, the 2-D vector image produced by step 308 is mapped to discrete display space coordinates (x', y').

Additionally, the raster image is mapped from parametric space back to display space. Mapping of the raster image from parametric space to display space begins in step 310. In step 310, the raster image 100 is mapped from (u, v) space to three dimensional space (x, y, z) by the parametric space mapping function f. Optionally, the raster image, as projected in 3-D space may have surface details such as shading and bump mapping applied. Shading and bump mapping methods is described by, for example, Foley, et al., and is represented herein by the function D(x, y, z). The projected and optionally shaded surface is subsequently projected from (x, y, z) space to output device space (x', y') by the device space mapping function <maths id="math0003" num=""><math display="inline"><mrow><mtext>(x', y') = g(x, y, z)</mtext></mrow></math><img file="EP0889437A2_D0003.tif" /></maths>. Thus, a complete raster image mapping from 2-D parametric space to discrete output device coordinates may be represented by the mapping function<maths id="math0004" num=""><math display="block"><mrow><mtext>(x', y') = g(D(f(u, v)))</mtext></mrow></math><img file="EP0889437A2_D0004.tif" /></maths> applied to raster image points on the (u, v) mapping.

In step 314, a clipping path may optionally be applied to the raster image projection of step 310. Application of a clipping path to the projected raster image improves the sharpness of the projected raster image's edges and enables precise alignment of raster image edges on surfaces of the rendered 3-D model.

Determination of the clipping path begins in step 311. In step 311, the clipping path is determined with reference to the placement of the raster image in (u, v) parametric space. This clipping path may be determined by, for example, a software program module or a separate software program such as the Adobe Streamline™ program. Alternatively, the clipping path can be determined by user input such as by the user inputting a clipping path using a graphical computer interface and a pointing device such as a mouse. Next, in step 312, the clipping path as determined in (u, v) space is projected from (u, v) space to 3-D space (x, y, z) and, in step 210, from the 3-D space to display space coordinates (x', y').

For illustrative purposes, application of an oval clipping path to a raster image is shown in Figs. 8A and 8B. In Fig. 8A an oval clipping path 825 is defined on a raster image 100. As seen in Fig. 8B, application of the clipping path 825 to the image 100 results in an oval shaped raster image 850.

The method completes in step 315 wherein the rendered 2-D vector image produced in step 309 is combined with the raster image output from step 314 and displayed. Sample images produced according to the invention are shown in Figs. 9A and 9B. These images illustrate a sample raster image 100 mapped to a 3-D surface 500 as viewed from differing points in 3-D space.

In a preferred approach, steps 308, 310, and 313 produce output in the PostScript™ page description language. Steps 309, 314, and 315 may then performed by a PostScript™ interpreter in, for example, a laser printer. Use of PostScript™ permits a clipping path to be defined in a resolution-independent manner with clipping path edges that accurately correspond to the edges of the 3-D vector model.

The described method allows precise placement of separately defined 2-D raster image graphics art on the surfaces of models. Two-dimensional graphics art might, for example, include a label designed for a bottle, which is subsequently applied to the modeled surface of the bottle for rendering as a combined three-dimensional image.

Referring to Fig. 10, the invention may be implemented in digital electronic circuitry or in computer hardware, firmware, software, or in combinations of them. Apparatus of the invention may be implemented in a computer program product tangibly embodied in a machine-readable storage device for execution by a computer processor; and method steps of the invention may be performed by a computer processor executing a program to perform functions of the invention by operating on input data and generating output. Suitable processors 1020 include, by way of example, both general and special purpose microprocessors. Generally, a processor will receive instructions and data from a read-only memory 1022 and/or a random access memory 1021. Storage devices suitable for tangibly embodying computer program instructions include all forms of non-volatile memory, including by way of example semiconductor memory devices, such as EPROM, EEPROM, and flash memory devices; magnetic disks such as internal hard disks and removable disks 1040; magneto-optical disks; and CD-ROM disks. Any of the foregoing may be supplemented by, or incorporated in, specially-designed ASICs (application-specific integrated circuits).

By way of example, a printing device 1000 implementing an interpreter for a page description language, such as the PostScript® language, includes a microprocessor 1002 for executing program instructions stored on a printer random access memory (RAM) 1004 and a printer read-only memory (ROM) 1006 and controlling a print marking engine 1008. The RAM 1004 is optionally supplemented by a mass storage device such as a hard disk or high-capacity removable disk (not shown). The essential elements of a computer are a processor for executing instructions and a memory. A computer can generally also receive programs and data from a storage medium such as an internal disk (not shown) or a removable disk 1040. These elements will be found in a conventional desktop or workstation computer 1010 as well as other computers suitable for executing computer programs implementing the methods described here, which may be used in conjunction with any digital print engine or marking engine, display monitor, or other raster output device capable of producing color or gray scale pixels on paper, film, display screen, or other output medium.

It should be understood that the foregoing description is only illustrative of an embodiment of the invention. Other embodiments are within the scope of the following claims.