Methods and apparatus for transmission and rendering of complex 3D models over networks using mixed representations

• US 6,684,255 B1
• Filed: 01/12/2000
• Issued: 01/27/2004
• Est. Priority Date: 10/26/1999
• Status: Expired due to Term

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Martin, Ioana Maria
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Qureshi, Shabana
• Application Number:
  US09/482,176
• Time in Patent Office: 1,476 Days
• Field of Search: 345/419-421, 345/427, 345/423, 345/440, 700/232, 700/233, 700/231, 700/226, 709/102, 707/1, 704/9
• US Class Current: 709/231
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2210/08 Bandwidth reduction
• CPC Class Codes: G06T 2210/36 Level of detail
• CPC Class Codes: G06T 2210/61 Scene description

Abstract

Three dimensional models having one or more model components stored in model databases, accessed by servers, and being viewed interactively from client computers are processed for transmission over a network. A model hierarchy is built with one or more nodes, by clustering together one or more of the model components based on one or more clustering criteria. One or more representations are associated with each node in the hierarchy. A cost function is associated with the model hierarchy and used to determine a cost of each representation at each node. A visibility of each node in the hierarchy is evaluated and associated with the respective node. A contribution of each node to an image of the 3D model to be rendered by one or more of the clients is evaluated. The 3D model hierarchy is traversed to select one or more of the representations to be transmitted to the client using a prioritization scheme that accounts for the visibility and contribution of each respective nodes.

Claims

1. A method for adaptive transmission of 3D models comprising one or more model components expressed in at least one representation, viewed from a viewpoint, the transmission being over a network from one or more servers to a set of one or more client computers, each of said client computers with corresponding display capabilities and network capabilities, the method comprising the steps of:

building a model hierarchy, with one or more nodes, by clustering together one or more of the model components based on one or more clustering criteria;

associating one or more representations with each node in the hierarchy;

associating a cost function with each representation and using the cost function to determine a combined cost for the entire model hierarchy;

receiving from a requesting client a set of user preferences specifying parameters of an image transmission, including capabilities of client apparatus;

receiving from said requesting client a request for a transmission of requested image data from said viewpoint;

dynamically evaluating the transmission context of transmissions over said network at the time of the request including at least estimated parameter values for available bandwidth, server loads and client loads;

establishing a resource budget for the transmission based on said parameters and estimated parameter values;

evaluating a visibility of each node in the hierarchy from said viewpoint and associating the visibility with the respective node;

establishing a prioritization scheme for the resource budget;

evaluating, with respect to the transmission context, a contribution of each node to an image of the 3D model to be rendered by one or more of the clients; and

traversing the 3D model hierarchy to select adaptively, in response to the transmission context, a transmission set of one or more of the representations to be transmitted to the client using a prioritization scheme that dynamically selects or rejects a node for transmission to a requesting client based on both the visibility and contribution of each respective nodes and the display and network capabilities of the requesting client and

transmitting the transmission set of representations to the client.

2. A method, as in claim 1, where the prioritization scheme comprises the following steps:

starting with a root node of the model hierarchy, recursively processing each of the nodes by discarding the node if the node is not visible and otherwise determining if a combined cost of one or more children of the node fits within a cost budget; and

if the combined cost is within the cost budget, recursively processing each of the children in an order of contribution, and if the combined cost is not within the cost budget, selecting, instead of the children, one of the representations of the node for transmission and rejecting other representations of the node.

3. A method, as in claim 1, in which said set of one or more client computers comprises at least two client computers having different capabilities and said parameters of an image transmission comprise parameters specifying data compatible with the display and network capabilities of said client apparatus.

4. A method, as in claim 3, further comprising a step of defining a multi-factor order relation, based on transmission time and at least one other criterion, over the set of all representations associated with a model component, thereby allowing comparisons between representations.

5. A method, as in claim 3, further comprising a step of defining a multi-factor order relation, based on transmission time and at least one other criterion, over the set of all representations associated with a model component, thereby allowing comparisons between representations.

6. A method, as in claim 4, where the combination criteria include any one or more of the following:

a spatial proximity and a semantic proximity.

7. A method, as in claim 1, where the representation may be one or more of the following:

a 2D object, a 2D object that describes one of the components, a 2D object that describes one or more clusters of components, a 3D object, a 3D object that describes one of the components, and a 3D object that describes one or more clusters components.

8. A method, as in claim 1, where each view independent representation is generated only once and subsequently stored with the hierarchy.

9. A method, as in claim 1, wherein the cost function is a function of a time to deliver one of the representations from the server to the client along with a representation quality and a degree of interactivity.

10. A method, as in claim 1, where a transmission history is recorded and said transmission context is re-evaluated in view of said transmission history to manage multiple transmissions of the same representation.

11. A method, as in claim 1, where representations selected for transmission are a mixture of representations and the mixture is rendered by the client.

12. A computer system for communicating three dimensional models, comprising:

one or more central processing units (CPU) and one or more memories;

one or more network connections to one or more networks;

one or more three dimensional models stored in one or more of the memories, each of the models being divided into one or more components that are viewed from a viewpoint, each component having one or more representations;

a communication process that adaptively communicates one or more of the representations through the network interface to at least two client computers by performing the following steps;

building a model hierarchy, with one or more nodes, by clustering together one or more of the model components based on one or more clustering criteria;

associating one or more representations with each node in the hierarchy;

associating a cost function with each representation and using the cost function to determine a combined cost for the entire model hierarchy;

receiving from a requesting client a set of user preferences specifying parameters of an image transmission, including capabilities of client apparatus;

receiving from said requesting client a request for a transmission of requested image data from said viewpoint;

dynamically evaluating the transmission context of transmissions over said network at the time of the request including at least estimated parameter values for available bandwidth, server loads and client loads;

establishing a resource budget for the transmission based on said parameters and estimated parameter values;

evaluating a visibility of each node in the hierarchy from said viewpoint and associating the visibility with the respective node;

establishing a prioritization scheme for the resource budget;

evaluating, with respect to the transmission context, a contribution of each node to an image of the 3D model to be rendered by one or more of the clients; and

traversing the 3D model hierarchy to select adaptively, in response to the transmission context, a transmission set of one or more of the representations to be transmitted to the client using a prioritization scheme that dynamically selects or rejects a node for transmission to a requesting client based on both the visibility and contribution of each respective nodes and the display and network capabilities of the requesting client and

transmitting the transmission set of representations to the client.

13. A system, as in claim 12, in which said set of one or more client computers comprises at least two client computers having different capabilities and said parameters of an image transmission comprise parameters specifying data compatible with the display and network capabilities of said client apparatus.

14. A method, as in claim 13, further comprising a step of defining a multi-factor order relation, based on transmission time and at least one other criterion, over the set of all representations associated with a model component, thereby allowing comparisons between representations.

15. A system, as in claim 12, where a transmission history is recorded and said parameters of said transmission context are re-evaluated in view of said transmission history to manage multiple transmissions of the same representation.

21. A method, as in claim 12, further comprising a step of defining a multi-factor order relation, based on transmission time and at least one other criterion, over the set of all representations associated with a model component, thereby allowing comparisons between representations.

16. An article of manufacture comprising a computer program product including computer-readable instruction means which performs the steps of:

building a model hierarchy, with one or more nodes, by clustering together one or more of the model components based on one or more clustering criteria;

associating one or more representations with each node in the hierarchy;

associating a cost function with each representation and using the cost function to determine a combined cost for the entire model hierarchy;

receiving from a requesting client a set of User preferences specifying parameters of an image transmission, including capabilities of client apparatus;

receiving from said requesting client a request for a transmission of requested image data from said viewpoint;

dynamically evaluating the transmission context of transmissions over said network at the time of the request including at least estimated parameter values for available bandwidth, server loads and client loads;

establishing a resource budget for the transmission based on said parameters and estimated parameter values;

evaluating a visibility of each node in the hierarchy from said viewpoint and associating the visibility with the respective node;

establishing a prioritization scheme for the resource budget;

evaluating, with respect to the transmission context, a contribution of each node to an image of the 3D model to be rendered by one or more of the clients; and

traversing the 3D model hierarchy to select adaptively, in response to the transmission context, a transmission set of one or more of the representations to be transmitted to the client using a prioritization scheme that dynamically selects or rejects a node for transmission to a requesting client based on both the visibility and contribution of each respective nodes and the display and network capabilities of the requesting client and transmitting the transmission set of representations to the client.

17. An article of manufacture according to claim 16, in which said set of one or more client computers comprises at least two client computers having different capabilities and said parameters of an image transmission comprise parameters specifying data compatible with the display and network capabilities of said client apparatus.

18. A method, as in claim 16, further comprising a step of defining a multi-factor order relation, based on transmission time and at least one other criterion, over the set of all representations associated with a model component, thereby allowing comparisons between representations.

19. A system, as in claim 17, where a transmission history is recorded and said parameters of said transmission context are re-evaluated in view of said transmission history to manage multiple transmissions of the same representation.

20. A method, as in claim 17, further comprising a step of defining a multi-factor order relation, based on transmission time and at least one other criterion, over the set of all representations associated with a model component, thereby allowing comparisons between representations.