Partition Of A 3D Scene Into A Plurality Of Zones Processed By A Computing Resource

• US 20140176552A1
• Filed: 12/16/2013
• Published: 06/26/2014
• Est. Priority Date: 12/21/2012
• Status: Active Grant

• Current Assignee: Dassault Systemes SA
• Original Assignee: Dassault Systemes SA
• Inventors: Belmans, Philippe, Boulkenafed, Malika
• Granted Patent: US 9,454,842 B2
• Time in Patent Office: Days
• US Class Current: 345/427
• 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 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.

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 three-dimensional scene; 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 any of claim 1, wherein the step of filling each location with its 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 any of claim 1, further comprising the steps of:

extracting, for each location of the three-dimensional scene, static objects located on said each location, an 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 three-dimensional scene, a print of the static objects on said each location of the three-dimensional scene.

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

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

7. The computer-implemented method of any of claim 1, wherein computing the maximum computing cost density comprises computing a ratio P/A, wherein P is a measured percentage of a computing resource required for processing the location and A is an area of the location in the three-dimensional scene.

8. The computer-implemented method of any 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 zone is under a predefined threshold.

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

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

11. A computer program comprising instructions for execution by a computer, the instructions being adapted for partitioning a three-dimensional scene into a plurality of zones, each zone being processed by a computing resource, by performing the steps of:

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.

12. A computer readable storage medium having recorded thereon a computer program according to claim 11.

13. A computerized system comprising:

a storage system for storing a three-dimensional scene comprising one or more objects;

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 being adapted for partitioning the three-dimensional scene into a plurality of zones by performing the steps of;

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.