Abstract:
A system, method, and computer program for for organizing elements for compression, comprising nesting a hierarchical topological structure having a plurality of elements; arranging said plurality of elements in a pattern to facilitate data compression; representing said pattern as four arrays; and compressing said plurality of elements from said arrays, and appropriate means and computer-readable instructions.

Description:
PRIORITY OF APPLICATION  
       [0001]     The present application claims priority of U.S. provisional application Ser. No. 60/822,133 filed Aug. 11, 2006, which is incorporated herein by reference.  
       CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0002]     This application is related to U.S. Ser. No. ______, entitled “VISUAL FILE REPRESENTATION” and U.S. Ser. No. ______, entitled “METHOD AND SYSTEM FOR TRIMMED SURFACE TESSELLATION”, both filed on even date herewith, which applications are incorporated by reference here.  
     
    
     TECHNICAL FIELD  
       [0003]     The presently preferred embodiment of the innovations described herein relate generally to computer graphics software applications. More specifically, the presently preferred embodiment relates to system and method to organize topology elements for better compression.  
       BACKGROUND  
       [0004]     Geometric representation that is capable of comprehensive functionality requirements is becoming increasingly important for engineering visualization industry as three-dimensional (“3D”) data usage is being expanded to non-engineering purposes such as training, maintenance, etc. 3D representation can result in geometric files growing in size from “light weight” (also “light” or “lw”) files can be less than 500 kilobytes to “heavy weight” (also “heavy” or “hw”) files can be more than 2, 5 or 20 megabytes, for example. Light-weight 3D representation is crucial for collaborative visualization, where the visualization activity occurs in a distributed enterprise environment with the data being physically located on a different computer in the network (particularly if the visualization data must be transferred via LAN, WAN, email or any other low-bandwidth transmission medium).  
         [0005]     Two important visualization functionalities are fast graphics display and accurate geometric analysis. Most visualization systems today use mesh representation in their file formats for maximum speed to reduce conversions from the file format to the graphics hardware, given that current graphics hardware is designed in a way such that its performance is best when the input data is represented in mesh format consisting of a collection of planar triangles. For better performance, several mesh representations of different details, usually call Level-Of-Detail or LOD, for the same part geometry may simultaneously exist in the file so that the graphics engine can choose to use less-detailed version for objects that are considered visually less significant in the scene. There are three major issues with LOD representation. First, LOD resolutions are fixed in the file format, so the curved surface may not appear smooth when zoomed-in, or magnified, thereby creating undesirable visual artifacts. Second, flat facets in mesh representation are merely linear approximations to the real object geometry. Some geometric operations, such as derivative computation, may not be meaningful at all for mesh, and other operations may not result in the desired accuracy. Third, LOD representations can be heavy even with state-of-art advanced compression. Fundamentally, flat facets, the basic element of LOD representation, does not exploit the intrinsic property of curved surface geometry.  
         [0006]     An alternative format called Boundary Representation, or BREP, can be used for graphics display in the file format BREP contains accurate geometry description of object geometry in which the modeling primitives can be curved. BREP representation is also the industry standard for 3D representation in CAD packages where the engineering models are authored, and therefore contains necessary information for all kinds of geometric operations with required accuracy. However, BREP representation is heavy and frequently heavier than typical LOD representation. In addition, BREP surface representation in general can&#39;t be directly accepted by mainstream graphics APIs such as OpenGL and DirectX. Facet representation needs to be generated by BREP with a process commonly called tessellation, before the object can be displayed on screen. The speed of BREP tessellation is therefore critical for graphics performance. Including both LOD and BREP representations in the file would fulfill most graphics and geometry operations and requirements, but only at the cost of making the file size even bigger.  
         [0007]     What is needed is a system, process, and method for a design representation that takes advantage of topological elements for arithmetic compression algorithms.  
       SUMMARY  
       [0008]     To achieve the foregoing, and in accordance with the purpose of the presently preferred embodiment as broadly described herein, the present application provides a method for organizing elements for compression, comprising nesting a hierarchical topological structure having a plurality of elements; arranging said plurality of elements in a pattern to facilitate data compression; representing said pattern as four arrays; and compressing said plurality of elements from said arrays. The method, further comprising aggregating together a plurality of numerical values according to type. The method, wherein said data compression is lossy.  
         [0009]     Another advantage of the presently preferred embodiment is to provide a computer-program product tangibly embodied in a machine readable medium to perform a method for organizing topology elements for compression, comprising instructions operable to cause a computer to nest a hierarchical topological structure having a plurality of elements; arrange said plurality of elements in a pattern to facilitate data compression; represent said pattern as four arrays; and compress said plurality of elements from said arrays. The computer-program product, further comprising instructions to aggregate together a plurality of numerical values according to type. The computer-program, wherein said data compression is lossy.  
         [0010]     And another advantage of the presently preferred embodiment is to provide a method for organizing elements for compression, comprising: aggregating a plurality of values into characteristic types; traversing each of said characteristic types for identification of aggregated values; quantizing said plurality of values; compressing said quantized plurality of values along with said plurality of values that are of an integer characteristic type.  
         [0011]     And yet another advantage of the presently preferred embodiment is to provide a A system for organizing elements for compression, comprising: an model representation; a type table having a plurality of characteristic types; a quantization engine; and a compression engine whereby said quantization engine and said compression engine compress a plurality of geometric elements from said model representation.  
         [0012]     And still another advantage of the presently preferred embodiment is to provide a data processing system having at least a processor and accessible memory to implement a method for organizing elements for compression, comprising means for nesting a hierarchical topological structure having a plurality of elements; means for arranging said plurality of elements in a pattern to facilitate lossless data compression; means for representing said pattern as four arrays; and means for compressing said plurality of elements from said arrays.  
         [0013]     Other advantages of the presently preferred embodiment will be set forth in part in the description and in the drawings that follow, and, in part will be learned by practice of the presently preferred embodiment. The presently preferred embodiment will now be described with reference made to the following Figures that form a part hereof. It is understood that other embodiments may be utilized and changes may be made without departing from the scope of the presently preferred embodiment.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]     A presently preferred embodiment will hereinafter be described in conjunction with the appended drawings, wherein like designations denote like elements, and:  
         [0015]      FIG. 1  is a flow diagram illustrating a visualization system;  
         [0016]      FIG. 2  is an illustration of a light model definition;  
         [0017]      FIG. 3  is an illustration of a light logical topology structure;  
         [0018]      FIG. 4  is an abstraction of a topology structure;  
         [0019]      FIG. 5  is a illustration of an abstraction of topology structure for a cube topology;  
         [0020]      FIG. 6  is an illustration of organizing light model geometry data for better compression;  
         [0021]      FIG. 7  is a flow chart of a technique employed by the presently preferred embodiment;  
         [0022]      FIG. 8  is a block diagram of a computer environment in which the presently preferred embodiment may be practiced.  
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0023]     The numerous innovative teachings of the present application will be described with particular reference to the presently preferred embodiments. It should be understood, however, that this class of embodiments provides only a few examples of the many advantageous uses of the innovative teachings herein. The presently preferred embodiment provides, among other things, a system and method for organizing topology elements for better compression. Now therefore, in accordance with the presently preferred embodiment, an operating system executes on a computer, such as a general-purpose personal computer.  FIG. 8  and the following discussion are intended to provide a brief, general description of a suitable computing environment in which the presently preferred embodiment may be implemented. Although not required, the presently preferred embodiment will be described in the general context of computer-executable instructions, such as program modules, being executed by a personal computer. Generally program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implementation particular abstract data types. The presently preferred embodiment may be performed in any of a variety of known computing environments.  
         [0024]     Referring to  FIG. 8 , an exemplary system for implementing the presently preferred embodiment includes a general-purpose computing device in the form of a computer  800 , such as a desktop or laptop computer, including a plurality of related peripheral devices (not depicted). The computer  800  includes a microprocessor  805  and a bus  810  employed to connect and enable communication between the microprocessor  805  and a plurality of components of the computer  800  in accordance with known techniques. The bus  810  may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. The computer  800  typically includes a user interface adapter  815 , which connects the microprocessor  805  via the bus  810  to one or more interface devices, such as a keyboard  820 , mouse  825 , and/or other interface devices  830 , which can be any user interface device, such as a touch sensitive screen, digitized pen entry pad, etc. The bus  810  also connects a display device  835 , such as an LCD screen or monitor, to the microprocessor  805  via a display adapter  840 . The bus  810  also connects the microprocessor  805  to a memory  845 , which can include ROM, RAM, etc.  
         [0025]     The computer  800  further includes a drive interface  850  that couples at least one storage device  855  and/or at least one optical drive  860  to the bus. The storage device  855  can include a hard disk drive, not shown, for reading and writing to a disk, a magnetic disk drive, not shown, for reading from or writing to a removable magnetic disk drive. Likewise the optical drive  860  can include an optical disk drive, not shown, for reading from or writing to a removable optical disk such as a CD ROM or other optical media. The aforementioned drives and associated computer-readable media provide non-volatile storage of computer readable instructions, data structures, program modules, and other data for the computer  800 .  
         [0026]     The computer  800  can communicate via a communications channel  865  with other computers or networks of computers. The computer  800  may be associated with such other computers in a local area network (LAN) or a wide area network (WAN), or it can be a client in a client/server arrangement with another computer, etc. Furthermore, the presently preferred embodiment may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices. All of these configurations, as well as the appropriate communications hardware and software, are known in the art.  
         [0027]     Software programming code that embodies the presently preferred embodiment is typically stored in the memory  845  of the computer  800 . In the client/server arrangement, such software programming code may be stored with memory associated with a server. The software programming code may also be embodied on any of a variety of non-volatile data storage device, such as a hard-drive, a diskette or a CD-ROM. The code may be distributed on such media, or may be distributed to users from the memory of one computer system over a network of some type to other computer systems for use by users of such other systems. The techniques and methods for embodying software program code on physical media and/or distributing software code via networks are well known and will not be further discussed herein.  
         [0000]     System  
         [0028]      FIG. 1  is a flow diagram illustrating a visualization system. Referring to  FIG. 1 , a light model visualization system, generally illustrated at  100 , has a light model format stored on disk  105  produced from a BREP model  110  derived from CAD data by a light model production component  115 , written to disk by a light model compression component  120 , and consumed by a tessellation kernel  125 , a visualization kernel  130 , and a geometric kernel  135  to fulfill engineering visualization functions such as to a graphics display  140  or a geometric analysis  145 .  
         [0000]     Operation  
         [0029]      FIG. 2  is an illustration of a light model definition. Referring to  FIG. 2 , from a topological perspective, the light model definition  105  has a region  200  that contains one or more shells  205  each of which corresponds to an isolated three-dimensional (3D) object with manifold topology. Each shell  200  consists of a collection of faces  210  covering the manifold geometry. Each face  210  is associated with a surface  215  that describes its geometry in the 3D Euclidean space. The surface  215  representation is parametric, meaning that its geometry is the result of mapping from a rectangular box in 2D parametric space to 3D model space through a mapping function. The face geometry can be a trimmed portion of the surface geometry, and such trimming if it exists is represented by one anti-hole loop and zero or more hole loops in the parameter space, where the anti-hole loop contains all the hole loops, generally illustrated at  220 . Each loop  220  consists of one or more coedges  225 , and each coedge  225  has its geometry in the parametric space as a parametric space curve  230 . The adjacency information between different faces is established between pairs of coedges. Assuming manifold geometry, each pair of coedges corresponds to a single edge  235  with geometry in the model space as a model space curve  240 . The location where multiple edges  235  join is called a vertex  245  with geometry in the model space as a point  250 . The geometric description of light model surfaces and curves is in parametric form, mapping from NURBS basis functions together with a set of control points to the parameterized description of analytic geometry. Example analytic geometric forms can be plane, cylinder, cone, sphere, and torus. Example analytic geometric forms in the parametric space curve  230  are UVline and UVcircle. Example analytic geometric forms in the model space curve  240  are XYZline and XYZcircle.  
         [0030]      FIG. 3  is an illustration of a light model logical topology structure. Referring to  FIG. 3 , the hierarchical topological structure, where the first region  200  of the light model structure denoted as R 0  starts at shell  205  S r     0     s  and ends at shell  205  S r     1     e , in which shell  205  S r     0     s  starts at face  210  F s     0     s  and ends at face  210  F s   e , face  210  F s     0     s  starts at loop  220  L f     0     s  and ends at loop  220  L f     0     e , while loop  220  L f     0     s  starts at coedge  225  C l     0     s  and ends at coedge  225  C l     0     e .  
         [0031]     These elements are arranged in the following pattern to facilitate compression: (a) all the shells belonging to the same region are contiguous in a shell array; (b) all the faces belonging to the same shell are contiguous in a face array; (c) all the loops belonging to the same face are contiguous in a loop array; and (d) all the coedges belonging to the same loop are contiguous in a coedge array. This arranged pattern is expressed by mathematical formula as: 
 
 r   k   s=r   k−1   e +1, 0 &lt;k&lt;N   r  
 
 s   k   s=s   k−1   e +1, 0 &lt;k&lt;N   s  
 
 f   k   s=f   k−1   e +1, 0 &lt;k&lt;N   f  
 
 l   k   s=l   k−1   e +1, 0 &lt;k&lt;N   l  
 
 where N r , N s , N f  and N l  are the total number of regions  200 , shells  205 , faces  210 , and loops  220  in the light model structure, respectively, and k is the index for each array. 
 
         [0032]      FIG. 4  is an abstraction of a topology structure. Referring to  FIG. 4 , given the above pattern, the relationship can be represented as four integer arrays, one for each topology type: 
   r   k   n=r   k   e−r   k   s +1, 0 &lt;=k&lt;N   r      s   k   n=s   k   e−s   k   s +1, 0 &lt;=k&lt;N   s      f   k   n=f   k   e−f   k   s +1, 0 &lt;=k&lt;N   f      l   k   n=r   l   e−r   l   s +1, 0 &lt;=k&lt;N   l    
 where the first array is the region-shell relation, the second array is the shell-face relation, the third array is the face-loop relation, and the fourth array is the loop-coedge relation. There is a good chance that N x , where x={r,s,f,l}, in each array are of similar magnitude. 
 
         [0033]      FIG. 5  is an illustration of an abstraction of topology structure for a cube topology. Referring to  FIG. 5  as an example, the arrays for a cube topology are defined by 1 region, 1 shell, 6 faces, 6 loops, and 24 coedges. The region-shell relation array is seen at  500  that indicates for one region, there is one shell. The shell-face relation array is seen at  505  that indicates for the one shell, there are six faces. With six entries for the faces, the face-loop relation array is seen at  510  that indicates for the six faces, there is one loop per face. The loop-coedge relation array is seen at  515  that indicates for the six faces, there are four coedges per loop. Because the index of each coedge must be contiguous in each loop, first loop has coedges with index 0 to 3, and the second loop has coedges with index 4 to 7, etc. The array elements contain a pattern that can be greatly compressed by currently available compression algorithms such as arithmetic coding.  
         [0034]     To take further advantage of one of the distinct characteristics of light model geometry is to aggregate together numerical values according to type. The geometry data in light model structure is classified into twelve types as shown in Table 1. By aggregating the values into types more patterns are provided that can be exploited by a lossy compression algorithm such as arithmetic compression for better compression.  FIG. 6  is an illustration of organizing light model geometry data for better compression. Referring to  FIG. 6 , of the twelve types  600  in light model geometry data, the first three are of an integer characteristic  605 , and the remaining nine have a more complex characteristic  610 . On the more complex characteristics  610 , the presently preferred embodiment passes each through a quantization engine  615  in any of the manners well understood in the art of lossy compression techniques. Likewise, those types identified by the integer characteristic  605  are passed to an integer compression engine  620  in a manner well understood in the art. According to the presently preferred embodiment, all of the integers that indicate “Degree of NURBS identity” (see Table 1, column description) are sequentially written on disk. Next, all of the integers that indicate “Number of control points of NURBS entity” are sequentially written on disk. This sequence preferably occurs according to the order of Table 1 so that numbers that are written sequentially are similar to each other in their expected values and such a pattern can be exploited by lossy compression algorithms to produce better compression results, as is understood in the art of compression algorithms.  
         [0035]     Summary  
         [0036]     Given the system and operation,  FIG. 7  is a technique for organizing topology elements for compression, beginning with nesting a hierarchical topological structure having a plurality of elements (Step  700 ). Next, arrange the plurality of elements in a pattern to facilitate lossy data compression (Step  705 ). Then represent the pattern as four arrays for each topological structure (Step  710 ). Lastly compress the elements from the arrays (Step  715 ). In an alternate embodiment also aggregate together a plurality of numerical values according to type for additional lossless compression.  
         [0000]     Conclusion  
         [0037]     The presently preferred embodiment may be implemented in digital electronic circuitry, or in computer hardware, firmware, software, or in combinations thereof. An apparatus of the presently preferred embodiment may be implemented in a computer program product tangibly embodied in a machine-readable storage device for execution by a programmable processor; and method steps of the presently preferred embodiment may be performed by a programmable processor executing a program of instructions to perform functions of the presently preferred embodiment by operating on input data and generating output.  
         [0038]     The presently preferred embodiment may advantageously be implemented in one or more computer programs that are executable on a programmable system including at least one programmable processor coupled to receive data and instructions from, and to transmit data and instructions to, a data storage system, at least one input device, and at least one output device. The application program may be implemented in a high-level procedural or object-oriented programming language, or in assembly or machine language if desired; and in any case, the language may be a compiled or interpreted language.  
         [0039]     Generally, a processor will receive instructions and data from a read-only memory and/or a random access memory. Storage devices suitable for tangibly embodying computer program instructions and data include all forms of nonvolatile 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; 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).  
         [0040]     A number of embodiments have been described. It will be understood that various modifications may be made without departing from the spirit and scope of the presently preferred embodiment. Therefore, other implementations are within the scope of the following claims.