Multi-resolution geometry

Abstract

A system, method, and apparatus is disclosed for creating a three-dimensional visual representation of an object having multiple resolutions by retrieving a vertex list for the object, determining a collapse order for the vertices identified in the vertex list, reordering the vertices identified in the vertex list responsive to the determined collapse, order, and creating a vertex collapse list responsive to the collapse order, where the vertex collapse list specifies, for a target vertex, a neighbor vertex to collapse to. The vertex list may comprise 3D coordinates of vertices without referring to other vertex attributes or, in alternate embodiments, the vertex list may refer to other vertex attributes such as colors or normals. A runtime manager is disclosed which dynamically manages the polygon counts for objects and frames based upon the location, velocity, and area of the object. Polygon counts are also adjusted based upon a target frame rate and a target polygon count. A system is also disclosed for continuous transfer of data across a remote connection in which different levels of resolution are transmitted individually.

1. A method for creating a three-dimensional visual representation of an object having multiple resolutions, comprising the steps of:
 retrieving coordinates of vertices for the object; 
 determining, using a processing device, a collapse order for the vertices identified in the of a vertex list for the object, across all levels of detail of the object; 
 reorderingordering the vertices identified in the vertex list responsive to the determined collapse order; 
 creating, using the processing device, a vertex collapse list responsive to the collapse order, where wherein the vertex collapse list specifies, for a each target vertex, a neighbor vertex of the object to which the target vertex  collapse to  collapses, for at least one level of detail of the object, and wherein each vertex collapse operation at a respective level of detail collapses a respective target vertex to a neighbor vertex directly connected to the target vertex at the respective level of detail; 
 specifying a level of detail at which the object is to be rendered; 
 using the vertex collapse list and a level of detail to identify at least one display vertex of the object; and 
 rendering the display vertex to produce a three-dimensional visual representation of the object at the specified level of detail using the vertex list and the vertex collapse list. 
 
     
     
       2. The method of  claim 1  wherein determining the collapse order comprises the steps of:
 determining a set of collapse paths available at a level of detail; 
 selecting a collapse path from the set of collapse paths; 
 computing a visual distortion factor factors for the selected each collapse path in the set of collapse paths; and 
 responsive to the computed visual distortion factors, determining a collapse value for the selected each collapse path in the set of collapse paths; 
 repeating selecting a collapse path, computing visual distortion factors, determining a collapse value for each collapse path; 
 selecting a next vertex to be collapsed as a vertex having a collapse path causing the least visual distortion to the object; 
 collapsing the next vertex to be collapsed along the corresponding collapse path; and 
 repeating the above steps until a minimum resolution level is attained. 
 
     
     
       3. The A method of  claim 2  wherein for creating a three-dimensional visual representation of an object at a selected level of detail, comprising:
 determining, using a processing device, a collapse order for vertices of the object, comprising:
 determining a set of collapse paths; 
 computing a visual distortion factors comprises the steps of factor for each collapse path in the set of collapse paths, including:
 computing an area change factor for the selected each collapse path; 
 computing an angular deviation factor for the selected each collapse path; and 
 computing a local volume change factor for the selected each collapse path; and 
 
 responsive to the computed visual distortion factors, determining a collapse value for each collapse path in the set of collapse paths; 
 
 ordering the vertices in a vertex list responsive to the determined collapse order; 
 creating, using the processing device, a vertex collapse list responsive to the collapse order, where the vertex collapse list specifies, for a target vertex, a neighbor vertex of the object to which the target vertex collapses; 
 specifying a level of detail at which the object is to be rendered; and 
 rendering a three-dimensional visual representation of the object at the specified level of detail using the vertex collapse list. 
 
     
     
       4. The method of  claim 3  wherein the computing an area change factor for each collapse path further comprises:
 computing an area of the object after collapsing the a first target vertex along the a first collapse path; and 
 subtracting the computed area from an area of the object prior to the collapse. 
 
     
     
       5. The method of  claim 3  wherein the computing a volume change factor for the selected each collapse path comprises:
 computing a volume of the object after collapsing the a first target vertex along the a first collapse path; and 
 subtracting the computed volume from a volume of the object prior to the collapse. 
 
     
     
       6. The method of  claim 5 , wherein the step of computing a volume further comprises:
 selecting the first target vertex to be an apex for a pyramid; 
 forming a base of the pyramid from a triangle connecting three consecutive neighbor vertices to the first target vertex; 
 computing a volume of the pyramid; 
 constructing a next pyramid from a next set of three consecutive neighbor vertices; 
 computing a volume of the next pyramid; 
 repeating the constructing a next pyramid and computing a volume steps for all unique three consecutive neighbor vertex sets; and 
 summing the volumes of the pyramids to obtain a volume of the object. 
 
     
     
       7. The method of  claim 2  further comprising the step of receiving an input from a user specifying a priority weight for a the visual distortion factor, and the wherein determining a collapse value step further comprises, responsive to the computed visual distortion factors and priority weights, determining a collapse value for the selected collapse path that is responsive to the priority weight. 
     
     
       8. The method of  claim 2  wherein, responsive to collapsing the next vertex to be collapsed along the corresponding collapse path, collapse paths local to the next vertex are identified and the computing visual distortion factors for the selected collapse path and the determining a collapse value for the selected collapse path steps are repeated only for the local collapse paths. 
     
     
       9. The method of  claim 2  wherein determining a set of collapse paths further comprises:
 selecting a first target vertex; 
 receiving input specifying a maximum number of neighbor vertices for a target vertex; 
 identifying a number of neighbor vertices, responsive to the a received input; and 
 determining a plurality of collapse path paths responsive to coordinates of the first target vertex and an identified neighbor vertex; 
 repeating the determining step for all the identified number of neighbor vertices; 
 repeating the selecting a target vertex, identifying, determining, and repeating steps for a plurality of vertices. 
 
     
     
       10. The method of  claim 2  further comprising the steps of:
 responsive to selecting a collapse path, displaying the object prior to collapsing the object along the selected path; 
 collapsing the object along the specified path; 
 displaying the object after being collapsed along the specified path; 
 responsive to receiving an input selecting the collapse path, storing the collapse path and corresponding vertex on the collapse order list as the next vertex to be collapsed. 
 
     
     
       11. The method of  claim 1 , further comprising receiving an input specifying a set of minimum vertices, and the wherein determining the collapse order step further comprises determining a collapse order in which the specified set of minimum vertices are not collapsed. 
     
     
       12. The method of  claim 1  wherein multiple resolution levels of the object exist, further comprising the steps of:
 ordering the resolution levels from highest to lowest resolution; 
 selecting a highest resolution level for collapsing; and 
 thewherein determining a collapse order step comprises determining a collapse order for vertices of the highest selected resolution level, wherein vertices in the next lowest resolution level are not collapsed; and 
 repeating the selecting and determining steps for each resolution level. 
 
     
     
       13. The method of  claim 1  wherein the each of the vertices of the object includes vertex coordinates are and associated with vertex attributes. 
     
     
       14. The method of claim  2  13 wherein each of the vertices have coordinates in a has texture map, further comprising the steps of coordinates, and the rendering comprises:
 responsive to a selected collapse path collapsing a first vertex into a second vertex to create a new vertex, and assigning the texture map coordinates of the second vertex to prior to collapsing the first vertex into the second vertex as the texture map coordinates of the second vertex after collapsing the first vertex into the new second vertex; 
 responsive to the first and second vertex being on an edge of a texture discontinuity, identifying the collapse path as a collapse path not to be used. 
 
     
     
       15. The method of claim  2  13 wherein each of the vertices have coordinates in a has normal map, further comprising the steps of coordinates, and the rendering comprises:
 responsive to a selected collapse path collapsing a first vertex into a second vertex to create a new vertex, and assigning the normal map coordinates of the second vertex to prior to collapsing the first vertex into the second vertex as the normal map coordinates of the second vertex after collapsing the first vertex into the new second vertex. 
 
     
     
       16. The method of claim  2  13 wherein each of the vertices have coordinates in a has color map, further comprising the steps of coordinates, and the rendering step comprises:
 responsive to a selected collapse path collapsing a first vertex into a second vertex to create a new vertex, and assigning the color map coordinates of the second vertex to prior to collapsing the first vertex into the second vertex as the color map coordinates of the second vertex after collapsing the first vertex into the new second vertex; and 
 responsive to the first and second vertex being on an edge of a color discontinuity, identifying the collapse path as a collapse path not to be used. 
 
     
     
       17. A method for displaying an object, wherein a vertex list and a neighbor list is stored for the object, and vertices in the vertex list are identified by a collapse priority and the neighbor list identifies the path of a collapse for the vertices, comprising the steps of:
 performing, using a processing device, a collapse of the object responsive to the a vertex list and a neighbor list for the object,
 wherein vertices in the vertex list for the object are arranged in a collapse priority, across all levels of detail of the object, 
 wherein the neighbor list specifies, for each target vertex in the vertex list, a neighbor vertex of the object to which the target vertex collapses, for at least one level of detail of the object, and wherein each vertex collapse operation at a respective level of detail collapses a respective target vertex to a neighbor vertex directly connected to the target vertex at the respective level of detail, and 
 wherein following the collapse the object is in a first collapse level; 
 
 storing vertex, in memory associated with the processing device, information for each collapse level relating to the collapse, wherein the vertex information indicates which vertices exist in of the object exist in the a second collapse level immediately higher and lower having at least one more vertex than the current first collapse level and in a third collapse level having at least one fewer vertex than the first collapse level; 
 receiving input requesting a collapse level for the object; 
 responsive to the requested a request for a collapse level requiring a higher resolution more vertices than a current the first collapse level, automatically adding vertices to a vertex from the vertex list for the object responsive to the vertex list and the stored vertex information; 
 responsive to the requested a request for a collapse level requiring a lower resolution fewer vertices than a current the first collapse level, automatically collapsing vertices a vertex in the vertex list of for the object responsive to the vertex list and the stored vertex information; and 
 automatically rendering the vertices in the vertex list for each requested collapse level to produce a three-dimensional visual representation of the object. 
 
     
     
       18. The method of  claim 17  further comprising the step of wherein storing information regarding the collapse includes:
 storing extended collapse information, wherein the extended collapse information includes triangle connectivity information for the at least some of the vertices. 
 
     
     
       19. A method for displaying an object, wherein a vertex list and a neighbor list is stored for the object, and vertices in the vertex list are identified by a collapse priority, and the neighbor list identifies the path of a collapse for the vertices, comprising the steps of:
 performing a collapse of the object responsive to the vertex list and neighbor list; 
 storing vertex in memory information for each collapse level, wherein the vertex information regarding a collapse of the object,
 wherein the object includes a vertex list and a neighbor list, 
 wherein vertices in the vertex list are arranged in a collapse priority, across all resolutions of the object, 
 wherein the neighbor list specifies, for each target vertex in the vertex list, a neighbor vertex of the object to which the target vertex collapses, for at least one resolution of the object, and wherein each vertex collapse operation at a respective resolution of the object collapses a respective target vertex to a neighbor vertex directly connected to the target vertex at the respective resolution of the object, and 
 wherein the information indicates which vertices of the vertex list exist in the object in the at a collapse level immediately higher and lower than the a current collapse level of the object; 
 
 analyzing the object using a processing device to determine a the current collapse level of the object; and
 responsive to the determined collapse level a determination requiring the object to be rendered at a resolution higher than a resolution of the current collapse level, adding vertices to a vertex from the vertex list for the object responsive to the vertex list and stored vertex information; and 
 responsive to the determined collapse level a determination requiring the object to be rendered at a resolution lower than the resolution of the current collapse level, collapsing vertices a vertex in the vertex list for the object responsive to the vertex list and stored vertex information; and 
 
 automatically rendering the vertices in the vertex list for the required resolution to produce a three-dimensional visual representation of the object. 
 
     
     
       20. The method of  claim 19  wherein the step of analyzing the object further comprises:
 determining a velocity of the object; and 
 determining a projected area of the object. 
 
     
     
       21. The method of claim  20  19 wherein the step of analyzing the object further comprises:
 determining the number of polygons currently being displayed; 
 comparing the determined number of polygons to a predefined target number of polygons; and 
 responsive to a determination that the number of polygons currently being displayed being is less than the predefined target number, adding polygons to the object a vertex from the vertex list for the object. 
 
     
     
       22. The method of  claim 19  wherein the step of analyzing the object further comprises:
 determining a current frame rate; 
 comparing the current frame rate to a predefined frame rate; and 
 responsive to a determination that the current frame rate being is less than the predefined frame rate, collapsing vertices in the object a vertex in the vertex list for the object. 
 
     
     
       23. A method for transferring data across a remote connection, in a system in which a minimal resolution of an object is stored and separate packets of information comprising data for creating higher resolutions of the object are stored, comprising the steps of:
 receiving as input to a processing device a request for a transmission of an the object to be displayed at a target resolution version of the object; 
 transmitting, using the processing device, via a remote connection, a minimal resolution version of the object responsive in response to receiving the received request; and 
 selectively transmitting, using the processing device, via the remote connection, a separate, successive packet of information comprising data for creating a comprising the vertices required to increase a collapse level of the object to a respective, predetermined, next higher resolution version of the object in response to a respective determination that the target resolution version of the object has not been met; 
 determining whether a target resolution of the object has been met; and 
 responsive to a target resolution of the object not being met, repeating the transmitting a packet of information comprising data for creating a next higher resolution version of the object step. 
 
     
     
       24. The method of claim 2, wherein computing a visual distortion factor comprises:
 computing an area change factor for each collapse path;   computing an angular deviation factor for each collapse path; and   computing a local volume change factor for each collapse path.   
     
     
       25. The method of claim 24, wherein computing an area change factor for each collapse path further comprises:
 computing an area of the object after collapsing a first target vertex along a first collapse path; and   subtracting the computed area from an area of the object prior to the collapse.   
     
     
       26. The method of claim 24, wherein computing a volume change factor for each collapse path comprises:
 computing a volume of the object after collapsing a first target vertex along a first collapse path; and   subtracting the computed volume from a volume of the object prior to the collapse.   
     
     
       27. The method of claim 26, wherein computing a volume further comprises:
 selecting the first target vertex to be an apex for a pyramid;   forming a base of the pyramid from a triangle connecting three consecutive neighbor vertices to the first target vertex;   computing a volume of the pyramid;   constructing a next pyramid from a next set of three consecutive neighbor vertices;   computing a volume of the next pyramid;   repeating the constructing a next pyramid and computing a volume for all unique three consecutive neighbor vertex sets; and   summing the volumes of the pyramids to obtain a volume of the object.   
     
     
       28. The method of claim 23, further comprising:
 storing the minimal resolution version of the object and the separate packets of information in memory.   
     
     
       29. The method of claim 23, wherein the target resolution version of the object is intermediate of the minimal resolution version of the object and a maximum resolution version of the object. 
     
     
       30. A method for creating a three-dimensional visual representation of an object, comprising:
 determining, using a processing device, a collapse order for vertices of the object, wherein said determining the collapse order comprises:
 determining a set of collapse paths available at a level of detail, including:
 selecting a first target vertex; 
 identifying a number of neighbor vertices, responsive to a received input; and 
 determining a plurality of collapse paths responsive to coordinates of the first target vertex and the identified number of neighbor vertices; 
 
 computing a visual distortion factor for each collapse path in the set of collapse paths; and 
 responsive to the computed visual distortion factors, determining a collapse value for each collapse path in the set of collapse paths; 
   ordering the vertices of the object in a vertex list responsive to the determined collapse order;   creating, using the processing device, a vertex collapse list responsive to the collapse order, wherein the vertex collapse list specifies, for each target vertex, a neighbor vertex of the object to which the target vertex collapses, for at least one level of detail of the object, and wherein each vertex collapse operation at a respective level of detail collapses a respective target vertex to a neighbor vertex directly connected to the target vertex at the respective level of detail;   specifying a level of detail at which the object is to be rendered; and   automatically rendering a three-dimensional visual representation of the object at the specified level of detail using the vertex list and the vertex collapse list.   
     
     
       31. An apparatus for creating a three-dimensional visual representation of an object, comprising:
 a processing device configured to:
 determine a collapse order for vertices of a vertex list for the object, across all levels of detail of the object; 
 order the vertices in the vertex list responsive to the determined collapse order; 
 create a vertex collapse list responsive to the collapse order, wherein the vertex collapse list specifies, for each target vertex, a neighbor vertex of the object to which the target vertex collapses, for at least one level of detail of the object, and wherein each vertex collapse operation at a respective level of detail collapses a respective target vertex to a neighbor vertex directly connected to the target vertex at the respective level of detail; 
 receive input specifying a level of detail at which the object is to be rendered; and 
 responsive to the received input, render a three-dimensional visual representation of the object at the specified level of detail using the vertex list and the vertex collapse list. 
   
     
     
       32. A non-transient computer-readable storage medium having stored thereon computer executable instructions, execution of which by a processing device causes the processing device to perform operations for creating a three-dimensional visual representation of an object, the operations comprising:
 determining a collapse order for vertices of a vertex list for the object, across all levels of detail of the object;   ordering the vertices in the vertex list responsive to the determined collapse order;   creating a vertex collapse list responsive to the collapse order, wherein the vertex collapse list specifies, for each target vertex, a neighbor vertex of the object to which the target vertex collapses for at least one level of detail of the object, and wherein each vertex collapse operation at a respective level of detail collapses a respective target vertex to a neighbor vertex directly connected to the target vertex at the respective level of detail;   specifying a level of detail at which the object is to be rendered; and   rendering a three-dimensional visual representation of the object at the specified level of detail using the vertex list and the vertex collapse list.   
     
     
       33. An apparatus for creating a three-dimensional visual representation of an object, comprising:
 a processing device configured to:
 determine a collapse order for vertices of the object, including:
 determining a set of collapse paths available at a level of detail, including:
 selecting a first target vertex; 
 identifying a number of neighbor vertices, responsive to a received input; and 
 determining a plurality of collapse paths responsive to coordinates of the first target vertex and the identified number of neighbor vertices; 
 
 computing a visual distortion factor for each collapse path in the set of collapse paths; and 
 responsive to the computed visual distortion factors, determining a collapse value for each collapse path in the set of collapse paths; 
 
 order the vertices of the object in a vertex list responsive to the determined collapse order; 
 create a vertex collapse list responsive to the collapse order, wherein the vertex collapse list specifies, for each target vertex, a neighbor vertex of the object to which the target vertex collapses, for at least one level of detail of the object, and wherein each vertex collapse operation at a respective level of detail collapses a respective target vertex to a neighbor vertex directly connected to the target vertex at the respective level of detail; 
 receive input specifying a level of detail at which the object is to be rendered; and 
 in response to the received input, automatically render a three-dimensional visual representation of the object at the specified level of detail using the vertex list and the vertex collapse list. 
   
     
     
       34. A non-transitory computer-readable storage medium having stored thereon computer executable instructions, execution of which by a processing device causes the processing device to perform operations for creating a three-dimensional visual representation of an object, the operations comprising:
 determining a collapse order for vertices of the object, wherein said determining the collapse order comprises:
 determining a set of collapse paths available at a level of detail, including:
 selecting a first target vertex; 
 identifying a number of neighbor vertices, responsive to a received input; and 
 determining a plurality of collapse paths responsive to coordinates of the first target vertex and the identified number of neighbor vertices; 
 
 computing a visual distortion factor for each collapse path in the set of collapse paths; and 
 responsive to the computed visual distortion factors, determining a collapse value for each collapse path in the set of collapse paths; 
   ordering the vertices of the object in a vertex list responsive to the determined collapse order;   creating a vertex collapse list responsive to the collapse order, wherein the vertex collapse list specifies, for each target vertex, a neighbor vertex of the object to which the target vertex collapses, for at least one level of detail of the object, and wherein each vertex collapse operation at a respective level of detail collapses a respective target vertex to a neighbor vertex directly connected to the target vertex at the respective level of detail;   specifying a level of detail at which the object is to be rendered; and   automatically rendering a three-dimensional visual representation of the object at the specified level of detail using the vertex list and the vertex collapse list.   
     
     
       35. The method of claim 1, wherein, in said determining a collapse order, each vertex of the object has a fixed coordinate offset relative to each other vertex of the object across all levels of detail of the object.