Abstract:
An apparatus and method for simplifying 3-Dimensional (3D) mesh data are disclosed. The method includes measuring discrete curvature at each point of received 3D mesh data, calculating an error based on distance-curvature error metrics including the discrete curvature, first sorting a low curvature one of the calculated error values in a heap in ascending order, selecting a minimum error among the calculated errors, determining if the minimum error is less than a threshold, contracting an edge if the selected minimum error is greater than the threshold, and recalculating an error of a surface neighboring to a surface on which the contracted edge belongs and re-sorting the calculated error values.

Description:
CLAIM OF PRIORITY 
     This application claims the benefit of the earlier filing date, under 35 U.S.C. §119(a), to that Korean Patent Application entitled “APPARATUS AND METHOD FOR SIMPLIFYING THREE-DIMENSIONAL MESH DATA” filed in the Korean Intellectual Property Office on Jan. 3, 2008 and assigned Serial No. 10-2008-0000558, the contents of which are herein incorporated by reference. 
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to 3-Dimensional (3D) mesh data imaging and, more particularly, to an apparatus and method for extending a Quadric Error Metrics (QEM) algorithm by discrete curvature for simplifying 3D mesh data. 
     2. Description of the Related Art 
     With the recent progress of advanced automation and development into information society, applications of computer graphic have increased rapidly, e.g., animation, simulation, etc. Amid this, the recent introduction of 3-Dimensional (3D) graphic techniques into electronic equipments leads to paying attention to the development of a high speed graphic processing technology for processing large numbers of polygons and efficiently processing special effects, such as lighting effects, in order to configure a little more realistic graphic. 
     Mesh simplification is a technique to retain the original desired shape and feature of a 3D model while reducing the number of polygons necessary to render the shape and features. That is, mesh simplification refers a process of removing polygons having topological and geometrical information more than needed from an initial model, thus simplifying the initial model. A technology for simplifying such a 3D model has been utilized in many fields such as a Level of Detail (LOD) control technology of a computer animation and 3D game, a 3D graphic solution of the Internet, a real-time 3D graphic simulation, etc. 
     A goal of mesh simplification is to provide good approximation to retain geometrical information on the original model and a phase with less vertex and face. An advantage of mesh simplification is to reduce the amount of storage space required for rendering a large size model, reduce a data-structure building time, and visualize a model at high speed. 
     A conventional simplification algorithm can give rise to a change of a volume of the original mesh model during the simplification process. Performance of the mesh simplification algorithm depends on an execution time for simplifying the original mesh model and a quality of approximation of the simplified model. Thus, a volume of a simplified mesh model has been considered using a distance based QEM algorithm of several simplification algorithms that uses the sum of squares of distances from one point on a plane providing relatively good performance. 
     The QEM algorithm is an algorithm for simplifying a mesh model using iterative edge contraction in which a method of selecting an edge to contract is of importance. The QEM algorithm determines a vertex whose distance error is minimal at each edge as a position of a new vertex after edge contraction, using a cost function of prioritizing an edge to contract (i.e., so-called QEM), first selects an edge at which the vertex has the least distance error among edges, and contracts the selected edge. 
     However, the QEM algorithm performs quick and high quality simplification, but there is a problem that it cannot keep a feature of the original 3D model when completing a simplification step of simplifying the original 3D model. 
     SUMMARY OF THE INVENTION 
     According to one aspect of the present invention, a method for simplifying 3-Dimensional (3D) mesh data in an electronic equipment is provided. The method includes measuring discrete curvature at each point in said 3D mesh data, calculating an error based on distance-curvature error metrics comprising the discrete curvature measured at each point, selecting a minimum error among the calculated errors, contracting a corresponding edge of said 3D when the minimum error is more than the threshold to obtain a simplified version of said edge, recalculating an error of a surface neighboring to a surface on which the contracted edge belongs, and re-sorting said calculated error values. 
     According to another aspect of the present invention, an apparatus for simplifying 3-Dimensional (3D) mesh data is provided. The apparatus includes a controller and a graphic engine. The controller controls a function of measuring discrete curvature at each point, calculating an error based on distance-curvature error metrics including the measured discrete curvature, first sorting a low curvature one of the calculated error values of respective points in ascending order, determining if a minimum error among the calculated errors is less than a threshold, contracting an edge if the minimum error is more than the threshold, recalculating an error of a surface neighboring to a surface on which the edge contracts, and re-sorting the calculated errors. The graphic engine performs simplification by contracting an edge of the 3D mesh data under control of the controller. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The above features and advantages of the present invention will become more apparent from the following detailed description when taken in conjunction with the accompanying drawings in which: 
         FIG. 1  is a block diagram illustrating a construction of an apparatus for simplifying 3-Dimensional (3D) mesh data according to an exemplary embodiment of the present invention; 
         FIG. 2  is a flow diagram illustrating a process of simplifying 3D mesh data in according to an exemplary embodiment of the present invention; 
         FIG. 3  is a diagram illustrating simplified data according to an exemplary embodiment of the present invention; and 
         FIG. 4  is a diagram illustrating simplified data according to an exemplary embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Exemplary embodiments of the present invention will be described herein below with reference to the accompanying drawings. In the following description, well-known functions or constructions are not described in detail as they would obscure the invention in unnecessary detail. 
       FIG. 1  is a block diagram illustrating a construction of an apparatus for simplifying 3-Dimensional (3D) mesh data according to an exemplary embodiment of the present invention. 
     In this case, the apparatus refers to a plurality of equipments for processing graphic such as a portable terminal, a personal computer, a mobile communication terminal, etc. or may represent one component or equipment among the plurality of the graphic processing equipments. 
     Referring to  FIG. 1 , the apparatus includes a controller  100 , a graphic engine  102 , a memory  104 , a display unit  106 , and an input unit  108 . 
     The controller  100  controls a general operation of the apparatus and in addition to a general function, controls and processes a function of receiving 3D mesh data, measuring discrete curvature, measuring an error based on distance and curvature, first sorting and simplifying a middle point having less error, and providing an output to the display unit  106  according to an exemplary embodiment of the present invention. 
     Under control of the controller  100 , the graphic engine  102  measures discrete curvature of the received 3D mesh data, measures an error based on distance and curvature, first sorts and simplifies a point having less error, and provides an output to the controller  100 . The graphic engine  102  also directly outputs simplified 3D mesh data to the display unit  106 . 
     The memory  104  stores a program for controlling a general operation of the electronic equipment, temporary data generated during an operation of the electronic equipment, a system parameter, and other depository data. In particular, the memory  104  stores a program for simplifying 3D mesh data. Memory  104  may be composed of well-known memory types such a PROM, RAM, and/or Flash. 
     The display unit  106  displays state information generated during an operation of the apparatus, and limited number of numerals and characters. The display unit  128  outputs a simplification model whose feature is preserved according to an exemplary embodiment of the present invention. 
     The input unit  108  includes keys for receiving numeral or character information and function keys for setting various kinds of functions, and outputs functions corresponding to the keys pressed by a user to the controller  100 . 
       FIG. 2  is a flow diagram illustrating a process of simplifying 3D mesh data according to an exemplary embodiment of the present invention. 
     Referring to  FIG. 2 , upon receiving 3D data in step  201 , measurement of discrete curvature is performed at each point at step  203 . The discrete curvature, a surface curvature of mesh constituted of a discrete surface, is calculated using geometrical information on the mesh. As the discrete curvature, there are an average curvature, a Gaussian curvature, and a principal curvature, and each curvature has a different characteristic. 
     Then, in step  205 , an error is calculated based on distance-curvature error metrics and then, in step  207 , a sort of the calculated errors. 
     Then, in step  208 , a minimum error is selected from among the errors and then, in step  209 , a determination is made whether the minimum error is less than a threshold value. If the minimum error is less than the threshold, in step  213 , an edge of a vertex is contracted and in step  215 , an error of a surface neighboring to a surface on which the edge contracts, is recalculated the calculated errors are resorted. Then, processing returns to step  209  and again performs the processing steps illustrated. 
     If the minimum error is less than the threshold value, then in step  211 , the simplified data is outputted and processing is terminated according to the illustrated exemplary embodiment of the present invention. 
     With regard to the error calculation, a distance from one point on a plane of a triangular mesh is measured and the measured distance is used as an error, and is given in Equation 1 as:
 
 d (   v ,p   i )= n   i   ·  v +c   i   (1)
 
     wherein d(  v ,p i ) represents a distance from a new vertex  v =(  v   x ,  v   y ,  v   z ) on a plane (p i ), and n=(n ix , n iy , n iz ) represents a vector of the plane (p i ). 
     Discrete curvature for the vertex  v =(  v   x ,  v   y ,  v   z ) represents a curved degree at the vertex. 
     An error obtained using the discrete curvature is substituted for c i  in Equation 1. By the thus measured numerical value, a distance error (i.e., QEM) is extended into distance-curvature error metrics including discrete curvature(s). The distance-curvature error metrics change a sequence (order) of a heap to simplify a high curvature part last and simplify a low curvature part (i.e., a flat part) first by changing a sequence of the computed errors. For example, an error is measured by measuring discrete curvatures at vertexes (v 1 ) and (v 2 ) in Equation 2 and substituting the thus measured values in Equation 3. 
     
       
         
           
             
               
                 
                   
                     
                       
                         H 
                         
                           1 
                           , 
                           2 
                         
                       
                       = 
                       
                         
                           
                             ∑ 
                             
                               j 
                               = 
                               0 
                             
                             n 
                           
                           ⁢ 
                           
                             { 
                             
                               
                                 ( 
                                 
                                   
                                     ( 
                                     
                                       
                                         v 
                                         
                                           j 
                                           - 
                                           1 
                                         
                                       
                                       - 
                                       
                                         v 
                                         
                                           1 
                                           , 
                                           2 
                                         
                                       
                                     
                                     ) 
                                   
                                   × 
                                   
                                     ( 
                                     
                                       
                                         v 
                                         j 
                                       
                                       - 
                                       
                                         v 
                                         
                                           1 
                                           , 
                                           2 
                                         
                                       
                                     
                                     ) 
                                   
                                 
                                 ) 
                               
                               · 
                               
                                 ( 
                                 
                                   
                                     ( 
                                     
                                       
                                         v 
                                         
                                           j 
                                           + 
                                           1 
                                         
                                       
                                       - 
                                       
                                         v 
                                         
                                           1 
                                           , 
                                           2 
                                         
                                       
                                     
                                     ) 
                                   
                                   × 
                                   
                                     ( 
                                     
                                       
                                         v 
                                         j 
                                       
                                       - 
                                       
                                         v 
                                         
                                           1 
                                           , 
                                           2 
                                         
                                       
                                     
                                     ) 
                                   
                                 
                                 ) 
                               
                             
                             } 
                           
                         
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               0 
                             
                             n 
                           
                           ⁢ 
                           
                              
                             
                               
                                 ( 
                                 
                                   
                                     v 
                                     j 
                                   
                                   - 
                                   
                                     v 
                                     
                                       1 
                                       , 
                                       2 
                                     
                                   
                                 
                                 ) 
                               
                               × 
                               
                                 ( 
                                 
                                   
                                     v 
                                     
                                       j 
                                       + 
                                       1 
                                     
                                   
                                   - 
                                   
                                     v 
                                     
                                       1 
                                       , 
                                       2 
                                     
                                   
                                 
                                 ) 
                               
                             
                              
                           
                         
                       
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           i 
                           , 
                           
                             j 
                             = 
                             1 
                           
                         
                         n 
                       
                       ⁢ 
                       
                         d 
                         ⁡ 
                         
                           ( 
                           
                             
                               v 
                               _ 
                             
                             , 
                             
                               p 
                               
                                 i 
                                 , 
                                 j 
                               
                             
                           
                           ) 
                         
                       
                     
                     = 
                     
                       
                         
                           ∑ 
                           
                             i 
                             , 
                             
                               j 
                               = 
                               1 
                             
                           
                           n 
                         
                         ⁢ 
                         
                           
                             n 
                             
                               i 
                               , 
                               j 
                             
                           
                           · 
                           
                             v 
                             _ 
                           
                         
                       
                       + 
                       
                         ( 
                         
                           
                             c 
                             
                               i 
                               , 
                               j 
                             
                           
                           + 
                           
                             H 
                             1 
                           
                           + 
                           
                             H 
                             2 
                           
                         
                         ) 
                       
                     
                   
                   ⁢ 
                   
                       
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         Q 
                         e 
                       
                       ⁡ 
                       
                         ( 
                         
                           v 
                           _ 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           , 
                           
                             j 
                             = 
                             1 
                           
                         
                         n 
                       
                       ⁢ 
                       
                         
                           d 
                           ⁡ 
                           
                             ( 
                             
                               
                                 v 
                                 _ 
                               
                               , 
                               
                                 p 
                                 
                                   i 
                                   , 
                                   j 
                                 
                               
                             
                             ) 
                           
                         
                         2 
                       
                     
                   
                   ⁢ 
                   
                       
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     The error obtained from Equations 2 and 3 is put in a heap for simplification and, among error values, an error value of a high curvature part moves to a rear part of the heap. By doing so, simplification is, although much, done with a feature of the original 3D mesh data that is preserved. 
       FIG. 3  is a diagram illustrating simplified data according to an exemplary embodiment of the present invention. 
     Referring to  FIG. 3 , upon simplification, a conventional QEM method expresses a part  301  of the original 3D mesh data model like a part  303  (see  FIG. 3(B) ). However, in the exemplary embodiment of the present invention received herein, if a high curvature part is simplified last, simplification is performed with a feature preserved like a part  305  (see  FIG. 3(C) ). In  FIG. 3 , “T” denotes number of triangles marked on a model.  FIG. 4  is a diagram illustrating simplified data according to an exemplary embodiment of the present invention. 
     Referring to  FIG. 4 , upon simplification, a conventional QEM method expresses parts  401  and  403  (see FIG.  4 (A)), of the original 3D mesh data model a represented by parts  405  and  407  (see  FIG. 4(B) ). In an exemplary embodiment of the present invention, if a high curvature part is simplified last, simplification is performed with a feature preserved like parts  409  and  411 . (see  FIG. 4(   c )). In  FIG. 4 , “T” denotes number of triangles marked on a model. 
     The above-described methods according to the present invention can be realized in hardware or as software or computer code that can be stored in a recording medium such as a CD ROM, an RAM, a floppy disk, a hard disk, or a magneto-optical disk or downloaded over a network, so that the methods described herein can be rendered in such software using a general purpose computer, or a special processor or in programmable or dedicated hardware, such as an ASIC or FPGA. As would be understood in the art, the computer, the processor or the programmable hardware include memory components, e.g., RAM, ROM, Flash, etc. that may store or receive software or computer code that when accessed and executed by the computer, processor or hardware implement the processing methods described herein. 
     As described above, an exemplary embodiment of the present invention has an effect of, upon simplification of 3D mesh data, being able to first simplify a specific part of the 3D mesh data model and thus increase the accuracy of a contour and a shape of the simplified model, by extending a QEM algorithm by discrete curvature and simplify a high discrete curvature part last. 
     While the invention has been shown and described with reference to certain preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.