Partition of a 3D scene into a plurality of zones processed by a computing resource

• US 9,454,842 B2
• Filed: 12/16/2013
• Issued: 09/27/2016
• Est. Priority Date: 12/21/2012
• Status: Active Grant

• Current Assignee: Dassault Systemes SA
• Original Assignee: Dassault Systemes SA
• Inventors: Belmans, Philippe, Boulkenafed, Malika
• Primary Examiner(s): Tung, Kee M
• Assistant Examiner(s): Sheng, Xin
• Application Number:
  US14/107,984
• Publication Number:
  US 20140176552A1
• Time in Patent Office: 1,016 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: A63F 13/12 involving interaction between a plurality of game devices, e.g. transmisison or distribution systems protocols for networked virtual reality, networked games H04L29/06034
• CPC Class Codes: A63F 13/25 Output arrangements for video game devices
• CPC Class Codes: A63F 13/30 Interconnection arrangements between game servers and game devices; Interconnection arrangements between game devices; Interconnection arrangements between game servers
• CPC Class Codes: A63F 2300/531 Server assignment
• CPC Class Codes: A63F 2300/534 for network load management, e.g. bandwidth optimization, latency reduction
• CPC Class Codes: A63F 2300/535 for monitoring, e.g. of user parameters, terminal parameters, application parameters, network parameters
• CPC Class Codes: G06T 15/08 Volume rendering

Abstract

The invention is directed to a computer-implemented method for partitioning a three-dimensional scene into a plurality of zones, each zone being processed by a computing resource. The method comprises

• • providing a three-dimensional scene comprising one or more objects, each object generating a computing resource cost;
  • determining a set of locations in the three-dimensional scene;
  • filling each location with its maximum occupancy of objects that reaches the most expensive computing cost;
  • computing, for each location of the three-dimensional scene, the maximum computing cost density; and
  • grouping adjacent locations into one or more zones, each zone having a resulting computing cost density guarantying a real-time performance of the zone.

Claims

1. A computer-implemented method for partitioning a three-dimensional scene into a plurality of zones, each zone being processed by a computing resource, the method comprising:

providing a three-dimensional scene comprising one or more objects, each object generating a computing resource cost;

determining a set of locations in the three-dimensional scene;

filling each location of the determined set with a corresponding maximum occupancy of objects that reaches a respective most expensive computing cost;

computing, for each given location of the determined set, a maximum computing cost density, wherein the computing comprises computing a ratio P/A, and wherein P is a measured percentage of a computing resource required for processing the given location, and A is an area or a volume of the given location in the three-dimensional scene; and

grouping adjacent locations into one or more zones, each zone having a resulting computing cost density guarantying a real-time performance of the respective zone, resulting in the three-dimensional scene being partitioned into the one or more zones.

2. The computer-implemented method of claim 1, further comprising the steps of:

aggregating the maximum computing cost densities computed for the locations of the determined set; and

building a map of cost density of the three-dimensional scene from the aggregated maximum computing cost densities.

3. The computer-implemented method of claim 1, wherein the step of filling each location of the determined set with the corresponding maximum occupancy of objects is performed for dynamic objects, a dynamic object being an object that can potentially move in the three-dimensional scene.

4. The computer-implemented method of claim 1, further comprising the steps of:

extracting, for each location of the determined set, static objects located on said each location, a static object being an object that cannot move in the three-dimensional scene and that cannot be traversed by another object; and

building a map of constraints of the three-dimensional scene from the extracted static objects.

5. The computer-implemented method of claim 4, wherein the step of extracting the static objects further comprises:

extracting, for each location of the determined set, a print of the static objects on said each location.

6. The computer-implemented method of claim 4, further comprising a step of:

aggregating the maps of cost density of the three-dimensional scene and the constraints of the three-dimensional scene.

7. The computer-implemented method of claim 1, wherein, at the step of grouping, the resulting computing cost density of each zone is such that the computing resource required for processing the respective zone is under a predefined threshold.

8. The computer-implemented method of claim 1, wherein, at the step of grouping, the resulting computing cost density between two or more zones is sensibly equivalent.

9. The computer-implemented method of claim 1, wherein the step of grouping is further performed taking into account a use of the computing resource made in the past by each zone.

10. A computer program product comprising:

a non-transitory computer readable storage medium, the computer readable storage medium having instructions configured to partition a three-dimensional scene into a plurality of zones, each zone being processed by a computing resource, by;

providing a three-dimensional scene comprising one or more objects, each object generating a computing resource cost;

determining a set of locations in the three-dimensional scene;

filling each location of the determined set with a corresponding maximum occupancy of objects that reaches a respective most expensive computing cost;

computing, for each given location of the determined set a maximum computing cost density, wherein the computing comprises computing a ratio P/A, and wherein P is a measured percentage of a computing resource required for processing the given location, and A is an area or a volume of the given location in the three-dimensional scene; and

grouping adjacent locations into one or more zones, each zone having a resulting computing cost density guarantying a real-time performance of the respective zone, resulting in the three-dimensional scene being partitioned into the one or more zones.

11. A computerized system comprising:

a storage system configured in computer memory for storing a three-dimensional scene comprising one or more objects;

at least one processor coupled to the storage system, the at least one processor configured as a processing unit for processing a plurality of zones partitioning the three-dimensional scene, each zone being processed by a computing resource of the processing unit, the processing unit partitioning the three-dimensional scene into a plurality of zones by;

providing a three-dimensional scene comprising one or more objects, each object generating a computing resource cost;

determining a set of locations in the three-dimensional scene;

filling each location of the determined set with a corresponding maximum occupancy of objects that reaches a respective most expensive computing cost;

computing, for each given location of the determined set a maximum computing cost density, wherein the computing comprises computing a ratio P/A, and wherein P is a measured percentage of a computing resource required for processing the given location, and A is an area or a volume of the given location in the three-dimensional scene; and

grouping adjacent locations into one or more zones, each zone having a resulting computing cost density guarantying a real-time performance of the respective zone, resulting in the three-dimensional scene being partitioned into the one or more zones.

12. The computerized system of claim 11, wherein the processing unit partitions the three-dimensional scene into a plurality of zones by further:

aggregating the maximum computing cost densities computed for the locations of the determined set; and

building a map of cost density of the three-dimensional scene from the aggregated maximum computing cost densities.

13. The computerized system of claim 11, wherein the processing unit performs the filling of each location of the determined set with the corresponding maximum occupancy of objects for dynamic objects, a dynamic object being an object that can potentially move in the three-dimensional scene.

14. The computerized system of claim 11, wherein the processing unit partitions the three-dimensional scene into a plurality of zones by further:

extracting, for each location of the determined set, static objects located on said each location, a static object being an object that cannot move in the three-dimensional scene and that cannot be traversed by another object; and

building a map of constraints of the three-dimensional scene from the extracted static objects.

15. The computerized system of claim 14, wherein the processing unit extracts the static objects by further:

extracting, for each location of the determined set, a print of the static objects on said each location; and

aggregating the maps of cost density of the three-dimensional scene and the constraints of the three-dimensional scene.

16. The computerized system of claim 11, wherein the resulting computing cost density of each zone is such that the computing resource required for processing the respective zone is under a predefined threshold.

17. The computerized system of claim 11, wherein the resulting computing cost density between two or more zones is sensibly equivalent.

18. The computerized system of claim 11, wherein the processing unit performs the grouping by taking into account a use of the computing resource made in the past by each zone.