Abstract:
Modifying a three-dimensional model includes constructing a bones infrastructure for a polygon mesh, removing edges of polygons in the polygon mesh to reduce a resolution of the polygon mesh, receiving an instruction to reduce a number of bones in the bones infrastructure, reducing the number of bones in the bones infrastructure in response to the instruction, and associate the polygon mesh with the bones infrastructure having a reduced number of bones.

Description:
TECHNICAL FIELD 
   This invention relates to modifying a three-dimensional (3D) model and, in particular, to reducing a resolution of the 3D model by decreasing the number of bones in the 3D model. 
   BACKGROUND 
   A 3D model includes a virtual skeleton/infrastructure comprised of bones that are arranged in a hierarchical tree structure. Surrounding the bones is a polygon mesh, comprised of polygons such as triangles, which represents the skin of the 3D model. Movement of the polygon mesh is tied to the movement of the bones so that the 3D model approximates real-life movement when the bones are re-positioned. 
   The 3D model inhabits a virtual world, in which the distance to a virtual camera dictates perspective. That is, objects farther away from the virtual camera are depicted as smaller than objects closer to the virtual camera. Objects that are farther away can be depicted with less detail without significantly affecting the quality of the 3D animation. 

   
     DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a view of a 3D model. 
       FIG. 2  is a view of bones in the 3D model. 
       FIG. 3  is a block diagram of a bones hierarchy. 
       FIG. 4  is a flowchart showing a process for reducing the resolution of bones in a 3D model. 
       FIG. 5  is a view of polygons in a polygon mesh. 
       FIG. 6  is a view of a 3D virtual environment. 
       FIG. 7  is a block diagram of a computer system on which the process of  FIG. 4  may be executed. 
       FIG. 8  is a block diagram of a reduced-resolution bones hierarchy. 
   

   DESCRIPTION 
     FIG. 1  shows a 3D model  10 , which is rendered from 3D data. As shown in  FIG. 1 , 3D model  10  is comprised of a polygon mesh  12 . The polygons are triangles in this embodiment; however, other types of polygons may be used. Polygon mesh  12  define the “skin” surface of 3D model  10 . 
   The 3D data for model  10  also includes bone data. The bone data defines a rigid skeletal structure  14  of model  10  (FIG.  2 ). The skeletal structure corresponds to the bones of a living being. In this embodiment, the “bones” in the skeletal structure are Cartesian XYZ-space vectors. 
   The bones of model  10  are linked together in a tree-like hierarchical structure, with higher-resolution “child” bones branching off from lower-resolution “parent” bones.  FIG. 3  shows an example of the hierarchical structure. In more detail, root bone  16 , which may represent the body of a 3D model, branches down to left upper arm bone  18  and right upper arm bone  20 . These bones, in turn, branch down to left forearm bone  22  and right forearm bone  24 , respectively, and so on. Bones at the bottom of the hierarchy, such as finger bones  26  and  28  are referred to as “higher resolution” bones than bones that are further up in the hierarchy, such as finger bones  30  and  32 . This is so because bones further down in the hierarchy provide higher resolution for the 3D model. That is, the additional bones provide added detail. 
   Each vertex of a polygon  12  ( FIG. 1 ) is associated with one or more bones of the 3D model. This association is defined in the 3D data that makes up 3D model  10 . A polygon deforms around a bone that the polygon is associated with, much the same way that skin surrounding living bone deforms in response to an applied force. The bones may change location in response to such force, but do not change shape. Referring to  FIG. 4 , a process  34  is shown for modifying a 3D model to reduce its resolution. Process  34  constructs ( 401 ) the 3D model, including a bones infrastructure. This may be done manually, automatically (i.e., without user intervention), or a combination of manually and automatically. 
   In more detail, a user (author) creates a high-resolution 3D polygon mesh. This may be done using conventional 3D graphics generation tools. The author also creates a high-resolution bones infrastructure underneath the 3D polygon mesh and associates ( 402 ) individual bones with vertices of the mesh. That is, the author stores data that relates each bone to one or more vertices of polygons in the 3D mesh. The association may be made using a standard 3D graphics tool (i.e., computer program/application) that operates automatically or interactively in response to user input. 
   Process  34  reduces ( 403 ) the resolution of the 3D polygon mesh. One technique that may be used to reduce the resolution is the multi-resolution mesh (MRM) technique. This technique involves removing edges of polygons, particularly edges that are interior to a 3D model, and then connecting unconnected vertices to form new, larger polygons. By way of example, as shown in  FIG. 5 , edge  38  of polygon  40  is interior to 3D model  42 . Consequently, its removal will not have a dramatic effect either way on the resolution of the 3D model. Accordingly, edge  38  can be removed, along, e.g., with edges  42  and  44  to combine the smaller polygons and produce a larger polygon  50 . Any vertices that are unconnected (no unconnected vertices are shown) may be connected to other vertices. 
   It is noted that multi-resolution mesh is but one example of a process that may be used to reduce the resolution of the 3D polygon mesh. Other such processes may be used instead of, or in addition to, the multi-resolution mesh. Furthermore, the resulting output of the polygon reduction process ( 404 ) may be modified manually by a user, if desired. 
   Process  34  reduces ( 404 ) the resolution of bones in the 3D polygon mesh. Generally, the reduction in resolution of the bones is commensurate with the reduction in resolution of the 3D polygon mesh; however, this is not a requirement. Process  34  may reduce the resolution of the bones either manually, automatically or a combination of the two. 
   Taking the manual case first, the user selects bones to be removed from the hierarchical bones infrastructure. For example, referring to hand  40  of  FIG. 3 , the user may select to remove finger bones  28  and  32  for one of its fingers. The resulting reduced-resolution 3D model is shown in FIG.  8 . As shown in  FIG. 8 , the lower-resolution finger bones  28  and  32  are removed, resulting in a “one-bone” finger  42 . Assuming that the reduced-resolution 3D model is far enough away from the virtual camera, or that it is not the focus of a scene, the resulting visual should not be significantly affected. 
   Process  34  may achieve the same effect as in  FIG. 8  using an automatic (or interactive) bone reduction technique. In more detail, process  34  may provide the user with a graphical display that allows the user to “dial down” the number of bones in the 3D model. That is, process  34  receives an instruction from the user to reduce the resolution of the bones and reduces their resolution in response to the received instruction. For example, the user may be given the opportunity to reduce the number of bones in the 3D model by a certain percentage. A linear or logarithmic scale may be used to reduce the number of bones in the 3D model. For example, if the reduction is 50%, only 50% of the bones down each path (e.g., arm  24 ) are used. As another alternative, if the number of polygons in the 3D polygon mesh has been reduced by a certain percentage, the number of bones in the 3D model may also be reduced by that same percentage. Alternatively, the reductions in polygons and bones in the 3D model may be related by another mathematical formula. 
   Instead of removing the lowest resolution bone/bones (e.g., bones  28  and  32  of  FIG. 3 ) from a 3D model, lower resolution bones may be retained, while still reducing the overall resolution of the 3D model. That is, referring to  FIG. 3 , the bones of a 3D model are arranged hierarchically such that a lower-resolution bone  40  branches down to two or more succeeding bones  42 ,  32 , and  28  and such that each of the succeeding bones (e.g., bone  32 ) has a higher-resolution than its predecessor (e.g., bone  42 ). In this embodiment, process  34  reduces the number of bones in the 3D model by connecting one of the succeeding, higher-resolution bones to the lower-resolution bone and removing the remaining intervening (i.e., “in between”) high-resolution bones. Finally, the vertices of the polygons associated with the old bone structure are re-mapped to the new, lower resolution bone structure. 
   By way of example, process  34  may connect high-resolution bone  28  to lower-resolution bone  40 . Once those two bones are connected, process  34  removes the remaining intervening bones  32  and  42 . This way, process  34  essentially retains the same level of resolution in the 3D model, while still reducing the number of bones. Removing the intervening high-resolution bones may have an effect on the mobility of the 3D model. However, depending upon the placement and scale of the 3D model in the 3D environment, this effect may be relatively insignificant in comparison to the reduction in data. 
   Process  34  may remove both highest-resolution bones and intervening bones. For example, referring to  FIG. 4 , process  34  may connect bone  32  to bone  40  and then remove highest-resolution bone  28  and intervening bone  42 . Which bones that are to be removed may be selected automatically, using a mathematical reduction process, or manually using an interactive graphics tool. In this regard, the user may allow the automatic process to take place, and then go back and make changes to the resulting 3D model manually. Any number of contingencies are within the scope of process  34 . 
   Process  34  associates ( 405 ) the reduced-resolution 3D polygon mesh with the reduced-resolution bones infrastructure. That is, process  34  conforms the 3D polygon mesh to the bones infrastructure. For example, process  34  checks all associations between polygon vertices and bones and assigns or removes such associations, where necessary. 
   Thereafter, process  34  stores 3D data for the modified 3D model in memory. Using this data, 3D animation that includes the model may be generated. 
   Process  34  has particular applicability to 3D models that are in the “background” of a 3D environment or that are far from a virtual camera. For example,  FIG. 6  shows a 3D environment  46 , with plane  48  corresponding to the location of a virtual camera (not shown). Thus, object  50  is closer to the virtual camera than is object  52 . Reducing the resolution of object  52  using process  34  will have less of an effect on the resulting 3D animation/display than reducing the resolution of object  50 , since object  52  is farther away from the virtual camera than object  50 . Thus, process  34  may be performed only on objects that are greater than a predetermined distance from the virtual camera. However, process  34  may be used to reduce the resolution of any and/or all objects in a given 3D environment. 
   Reducing the resolution of 3D objects by removing bones reduces the amount of data required to render those objects. Since less data is required, 3D animation can be rendered more quickly and with less powerful microprocessors. Moreover, reductions in the amount of data for a model facilitates transmission over limited-bandwidth transmission media. 
   Process  34  may be performed only once on a set of data for a particular 3D model. Process  34  may also be performed for each keyframe of an animation sequence. A keyframe, in this context, is a frame of animation where significant movement of 3D model  10  has occurred. Keyframes thus provide a snapshot of 3D model  10  at a moment in time. Interim animation is obtained by interpolating between the keyframes. 
   In the “manual” case described above, process  34  downloads additional keyframes for later segments of animation. The additional keyframes are used to interpret additional steps of animation. For the “automatic” case described above, process  34  uses one set of keyframes. In this case, higher-resolution bones are automatically associated with lower-resolution bones when bones are removed or not yet downloaded. 
     FIG. 7  shows a computer  54  for reducing the resolution of 3D models using process  34 . Computer  54  includes a processor  56 , a memory  58 , and a storage medium  60  (e.g., a hard disk) (see view  62 ). Storage medium  60  stores 3D data  64 , which defines a 3D model, and machine-executable instructions  66 , which are executed by processor  56  out of memory  58  to perform process  34  on 3D data  64 . 
   Process  34 , however, is not limited to use with the hardware and software of  FIG. 7 ; it may find applicability in any computing or processing environment. 
   Process  34  may be implemented in hardware, software, or a combination of the two. Process  34  may be implemented in computer programs executing on programmable machines that each includes a processor, a storage medium readable by the processor (including volatile and non-volatile memory and/or storage elements), at least one input device, and one or more output devices. Program code may be applied to data entered using an input device, such as a mouse or a keyboard, to perform process  34  and to generate output information. 
   Each such program may be implemented in a high level procedural or object-oriented programming language to communicate with a computer system. However, the programs can be implemented in assembly or machine language. The language may be a compiled or an interpreted language. 
   Each computer program may be stored on a storage medium or device (e.g., CD-ROM, hard disk, or magnetic diskette) that is readable by a general or special purpose programmable computer for configuring and operating the computer when the storage medium or device is read by the computer to perform process  34 . Process  34  may also be implemented as an article of manufacture, such as a machine-readable storage medium, configured with a computer program, where, upon execution, instructions in the computer program cause the machine to operate in accordance with process  34 . 
   Other embodiments not described herein are also within the scope of the following claims.