News Column

Patent Application Titled "Method for Optimized Polygon Reduction of Computer Graphics" Published Online

May 15, 2014



By a News Reporter-Staff News Editor at Politics & Government Week -- According to news reporting originating from Washington, D.C., by VerticalNews journalists, a patent application by the inventors Lindahl, Ulrik (LJUNGSBRO, SE); Johansson, Gustaf (STOCKHOLM, SE), filed on October 19, 2012, was made available online on May 1, 2014.

The assignee for this patent application is Donya Labs Ab.

Reporters obtained the following quote from the background information supplied by the inventors: "The creation and interactive visualization of artificial computer graphics (CG) environments is an important application in the field of computer graphics. Many applications, such as CAD, architectural walkthroughs, simulations, medical visualization and computer games include interactive navigation, i.e., being able to move around a computer model/scene at greater than 10 frames per second.

"A common trend within the field of interactive computer graphics is the increasing amount of CG datasets. Large CG datasets require specialized graphics systems used to accelerate the process. However, models exist that cannot be rendered at interactive speeds even with current high-end computer hardware. The development of computer hardware is not likely to solve the described problems since the size of the CG data and the size of the secondary computer memory is increasing at faster rates than the development of thereto related hardware.

"CG data is often represented using triangle meshes, or even more generally using a plurality of polygons. These meshes are typically not optimized for display or simulation performance. In most applications, the initial meshes can usually be replaced by optimized versions that could be approximations with far fewer faces, or containing other properties that make them more suited for particular applications such as mentioned above.

"To prevent a decrease in calculation speed, an automatic technique of creating three-dimensional GC data with a small number of triangles/polygons in advance is often employed. However, in employing an automated process for polygon reduction, sometimes an undesirable visual error occurs. Generally, the graphical designer responsible for the specific GC dataset must then manually make suitable adjustments for achieving a visually appealing, but still polygon reduced, GC dataset. Accordingly, it would be desirable to allow for further automation of the polygon reduction process, reducing cost and possibly achieving a more optimized polygon reduced GC dataset."

In addition to obtaining background information on this patent application, VerticalNews editors also obtained the inventors' summary information for this patent application: "According to a first aspect of the invention, the above is at least partly alleviated by a computer implemented method for optimizing polygon reduction of an initial three-dimensional graphics image, the method comprising performing a first polygon reduction process, resulting in a first three-dimensional graphics image being a polygon reduced representation of the initial three-dimensional graphics image, comparing the first three-dimensional graphics image with the initial three-dimensional graphics image, determining a visual error metric based on the result of the comparison between the first three-dimensional graphics image and the initial three-dimensional graphics image, and performing a second polygon reduction process, resulting in a second three-dimensional graphics image being a polygon reduced representation of the initial three-dimensional graphics object, if the visual error metric is outside of a predetermined error range.

"By means of the invention, it is possible to automate the identification of visual error appearing when executing a polygon reduction process, thus resulting in the advantage of reducing cost by minimizing the amount of manual labor needed for achieving e.g. a visually appealing resulting polygon reduced image. This is according to the present invention achieved by determining a difference between an 'original' image and an image resulting from an initial polygon reduction process. In case a visual error metric being a result of the comparison/determination, exceeds (or being less than) a predetermined error range, an adaptation is made to the polygon reduction process (i.e. the second polygon reduction process) for the purpose of re-iterating the polygon reduction such that a resulting image (e.g. to be displayed on a computer screen) better matches a desired 'quality level'.

"It should within the context of the present invention be understood that the visual error metric could be based on a single as well as plurality of different 'views' of the three-dimensional image. In the case with a plurality of views of the three-dimensional image, this plurality of views may e.g. be merged or accumulated into one single view-independent visual error metric or represented with a separate view-dependent visual error metric for each (or at least some) of the plurality of views of the three-dimensional image.

"The error range may for example be based on a desired visual appearance of the resulting image, and/or in combination with a predetermined polygon reduction ratio (i.e. when comparing the initial with the resulting image in relation to number of polygons) or 'polygon budget' for the resulting image.

"Generally, the initial, the first and the second three-dimensional graphics image is a polygonal image comprising a plurality of polygons forming a 3-D computer graphics image. As discussed above, three-dimensional computer graphics may for example be used in relation to real-time visualization, computer games, CAD related software, etc.

"Furthermore, an exemplary advantage with the invention relates to the possibility of pin-pointing 'problem areas' within the original and/or the polygon reduced image(s). Such an advantage provides for the possibility of introducing a less exact and faster visual error metric, thereby giving a faster iterative initial result that is then further refined by multiple passes of the full version of the selected (i.e. second) polygon reduction process.

"In a preferred embodiment, the second polygon reduction process introduces a lower level of polygon reduction as compared to the first polygon reduction process. Accordingly, in case the visual error metric exceeds the predetermined error range, the second polygon reduction process is selected to not reduce the number of polygons as 'hard' as was initially achieved using the first polygon reduction process.

"However, alternatively the second polygon reduction process may instead introduce a higher level of polygon reduction as compared to the first polygon reduction process. Thus, conversely, in case the determined visual error metric is identified to be less than what was desired (or expected), it may be possible to select a second polygon reduction process configured to achieve a higher level of polygon reduction (i.e. resulting in fewer polygons in regards to the second image as compared to the first image).

"Based on the above, it should be understood (but not a necessity) that the method according to the invention may be performed only once, or iterated for a plurality of times. For example, in case a comparison between the second image and initial image results in a visual error metric being outside of the error range, a further adjustment may be made in relation to the selection/configuration of the polygon reduction process for providing the resulting image.

"Preferably, the second polygon reduction process is selected from one of a plurality of predetermined polygon reduction processes. In any case, the expression 'polygon reduction process' should be interpreted broadly, e.g. completely different types of polygon reduction processes may be applied, as well as allowing a specific (for example proprietary) polygon reduction process to be configurable in regards to the level of polygon reduction.

"In a preferred embodiment, the method further comprises segmenting the three-dimensional graphics image into a plurality of portions, wherein the determination of the visual error metric is performed for each of the plurality of portions of the three-dimensional graphics image (and possibly for a plurality of different views of the image). In such an embodiment, the three-dimensional graphics image, e.g. being one of the initial, the first and the second three-dimensional graphics image is subdivided in to a plurality of sub-sections, where the visual error metric is determined for each of the sub-sections. Thereby, the selection of polygon reduction processes may then in a suitable manner be made based on the 'severity' of error for that specific portion, e.g. different 'types' (or configured) polygon reduction processes may be selected for two adjacently arranged portions of the image. Any number of portions may be selected from the graphics image. According to the invention, the segments may also (or alternatively) be formed based on a 'clustering technique where 'error areas' are formed based on adjacent errors.

"In a possible embodiment of the present invention, it may additionally be possible to provide the visual error metric to a user, and (then) receive a user adjusted visual error metric, wherein providing the visual error metric and receiving the user adjusted visual error metric are performed prior to performing the second polygon reduction process. Accordingly, by such an addition it may for example be possible to, prior to performing the second (adjusted) polygon reduction process, e.g. visualize the visual error metric to a user performing the polygon optimization process. Such a visualization may allow the user to e.g. make manual adjustments to the visual error metric, thus providing for the possibility of using the users prior knowledge of a specific feature of the three-dimensional image (e.g. future placement within a game, or areas where higher error may be allowable), thus further optimizing the polygon reduction process.

"According to another aspect of the present invention there is provided an image processing apparatus for optimizing polygon reductions of a three-dimensional graphics object, comprising means for performing a first polygon reduction process, resulting in a first three-dimensional graphics image being a polygon reduced representation of the initial three-dimensional graphics image, means for comparing the first three-dimensional graphics image with the initial three-dimensional graphics image, means for determining a visual error metric based on the result of the comparison between the first three-dimensional graphics image and the initial three-dimensional graphics image, and means for performing a second polygon reduction process, resulting in a second three-dimensional graphics image being a polygon reduced representation of the initial three-dimensional graphics object, if the visual error metric is outside of a predetermined error range. This aspect of the invention provides similar advantages as discussed above.

"In an embodiment, the image processing apparatus is further configured to allow for display of at least one of the initial, the first or the second three-dimensional graphics image on a computer screen.

"The invention is preferably provided on a computer-readable storage medium storing a program which causes a computer to execute an image processing method as discussed above.

"According to further aspect of the invention there is provided a computer program product comprising a computer readable medium having stored thereon computer program means for controlling an image processing apparatus configured for optimizing polygon reductions of a three-dimensional graphics object, wherein the computer program product comprises code for performing a first polygon reduction process, resulting in a first three-dimensional graphics image being a polygon reduced representation of the initial three-dimensional graphics image, code for comparing the first three-dimensional graphics image with the initial three-dimensional graphics image, code for determining a visual error metric based on the result of the comparison between the first three-dimensional graphics image and the initial three-dimensional graphics image, and code for performing a second polygon reduction process, resulting in a second three-dimensional graphics image being a polygon reduced representation of the initial three-dimensional graphics object, if the visual error metric is outside of a predetermined error range. Also this aspect of the invention provides similar advantages as discussed above in relation to the previous aspects of the invention.

"The image processing apparatus is preferably a server, a general computer, a micro processor or any other type of computing device. Similarly, the computer readable medium may be any type of memory device, including one of a removable nonvolatile random access memory, a hard disk drive, a floppy disk, a CD-ROM, a DVD-ROM, a USB memory, an SD memory card, or a similar computer readable medium known in the art.

"In an embodiment and in a similar manner as discussed above, the computer program product is further configured to allow for display of at least one of the initial, the first or the second three-dimensional graphics image on a computer screen.

"Further features of, and advantages with, the present invention will become apparent when studying the appended claims and the following description. The skilled addressee realize that different features of the present invention may be combined to create embodiments other than those described in the following, without departing from the scope of the present invention.

BRIEF DESCRIPTION OF THE DRAWINGS

"The various aspects of the invention, including its particular features and advantages, will be readily understood from the following detailed description and the accompanying drawings, in which:

"FIGS. 1a and 1b show an example of an original and a polygon reduced three-dimensional graphics image, respectively;

"FIG. 2 illustrates a conceptual image processing system according to a currently preferred embodiment of the invention;

"FIG. 3 shows a flow chart of method steps according to an embodiment of the invention, and

"FIGS. 4a, 4b, 4c and 4d illustrate three-dimensional graphics images at different processes of the inventive method."

For more information, see this patent application: Lindahl, Ulrik; Johansson, Gustaf. Method for Optimized Polygon Reduction of Computer Graphics. Filed October 19, 2012 and posted May 1, 2014. Patent URL: http://appft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&u=%2Fnetahtml%2FPTO%2Fsearch-adv.html&r=4233&p=85&f=G&l=50&d=PG01&S1=20140424.PD.&OS=PD/20140424&RS=PD/20140424

Keywords for this news article include: Donya Labs Ab.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Politics & Government Week


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters