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

Patent metadata

Field	Value
Publication number	US-11087052-B2
Application number	US-202016824372-A
Country	US
Kind code	B2
Filing date	Mar 19, 2020
Priority date	Dec 21, 2016
Publication date	Aug 10, 2021
Grant date	Aug 10, 2021

Abstract

Described is a computer-implemented method for partitioning a 3D scene into a plurality of zones, each zone representing an area or a volume of the 3D scene and being processed by a computing resource. The method comprises obtaining a 3D scene comprising one or more objects, each object generating a computing resource cost, computing a first map that represents a density of computing costs of the provided 3D scene, defining a second map that represents constraints on the shapes of zones that will be obtained as a result of a partitioning of the 3D scene, discretizing the obtained 3D scene into cells by computing a space quantization of the 3D scene free of dynamic objects, computing, for each cell, a computing cost from the first map of the 3D scene, aggregating the cells into one or more zones in accordance with the second map.

First claim

The invention claimed is:

1. A computer-implemented method for partitioning a 3D scene into a plurality of zones, each zone representing an area or a volume of the 3D scene and being processed by a computing resource, the method comprising:
obtaining a 3D scene comprising one or more objects, each object generating a computing resource cost;
computing a first map that represents a density of computing costs of the obtained 3D scene;
defining a second map that represents constraints on the shapes of zones that will be obtained as a result of a partitioning of the 3D scene;
computing a value of a space quantization of the 3D scene free of dynamic objects, a dynamic object being an object that is moveable in the 3D scene;
discretizing the provided 3D scene into cells of a same size limited by the computed value;
computing, for each cell, a computing cost from the first map of the 3D scene; and
aggregating the cells into one or more zones in accordance with the second map, each zone having a computing cost that is the sum of the computing costs of the cells belonging to the zone, the computing cost of the zone allowing a real-time simulation of the zone on a computing resource,
wherein the computation of the space quantization of the 3D scene further comprises:
computing a surface quantum S q defined by the relation
S q =(CPU CA )/(density of computing costs) Max ,

wherein (CPU CA ) represents an accuracy of a computer resource cost for processing the zones and (density of computing costs) Max is the highest density represented on the first map, and
discretizing the provided 3D scene into cells, each cell having a size equal to the surface quantum S q .

2. The computer-implemented method of claim 1 , wherein the aggregation of the cells into one or more zones is further carried out with a combinatorial optimization algorithm.

3. The computer-implemented method of claim 2 , wherein the combinatorial optimization algorithm is an Ant colony algorithm.

4. The computer-implemented method of claim 2 , wherein an objective function of the combinatorial optimization algorithm is formulated for increasing at least when:
a number N of zones has increased as a result of a new aggregation of the cells into one or more zones,
the shapes of zones are jagged border, and
the number of disconnected zones is larger than zero.

5. The computer-implemented method of claim 1 , further comprising, before the aggregation of the cells:
computing one or more clusters of one or more cells in accordance with the second map,
wherein the aggregating step further comprises aggregating the clusters into one or more zones, each zone having a computing cost that is the sum of the computing costs of the cells belonging to the zone, the computing cost of the zone allowing a real-time simulation of the zone on a computing resource.

6. The computer-implemented method of claim 1 , wherein the constraints on the shapes of the zones represented on the second map are obtained by:
identifying in the 3D scene one or more static objects of the 3D scene, a static object being an object that cannot move in the 3D scene and that cannot be traversed by another object, and
for each static object identified, computing a geometry that is associated with a rule that creates one or more clusters of one or more cells.

7. The computer-implemented method of claim 6 , wherein the association of a geometry and a rule for creating clusters of cells is one among:
the geometry is a polygon and the rule creates a cluster of the cells that are included in the polygon,
the geometry is a polygon and the rule creates a cluster of the cells that extends from the polygon according to a direction and a magnitude that are represented by a vector, and
the geometry is a polyline and the rule triggers the creation of a cluster for each cell that borders the polyline.

8. The computer implemented-method of claim 7 , wherein the association of a rule with a computed geometry is performed upon user action.

9. The computer-implemented method of claim 6 , wherein the identification in the 3D scene of one or more static objects of the 3D scene is performed upon user action.

10. The computer-implemented method of claim 1 , wherein the computation of the first map that represents a density of computing costs of the provided 3D scene, further comprises:
determining a set of locations in the 3D scene,
filling each location with its maximum occupancy of objects that reaches the most expensive computing cost,
computing, for each location of the 3D scene, the maximum computing cost, and
for each location, 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.

11. The computer-implemented method of claim 10 , wherein the step of filling each location with its maximum occupancy of objects is performed for dynamic objects.

12. The computer-implemented method of claim 1 , wherein computing, for each cell, a computing cost from the first map of the 3D scene further comprises computing the product between the surface quantum S q and density of computing cost of the cell.

13. A non-transitory computer readable medium having stored thereon a program comprising instructions that when executed by a computer causes the computer to perform a method for partitioning a 3D scene into a plurality of zones, each zone representing an area or a volume of the 3D scene and being processed by a computing resource, the method comprising:
obtaining a 3D scene comprising one or more objects, each object generating a computing resource cost;
computing a first map that represents a density of computing costs of the obtained 3D scene;
defining a second map that represents constraints on the shapes of zones that will be obtained as a result of a partitioning of the 3D scene;
computing a value of a space quantization of the 3D scene free of dynamic objects, a dynamic object being an object that is moveable in the 3D scene;
discretizing the provided 3D scene into cells of a same size limited by the computed value;
computing, for each cell, a computing cost from the first map of the 3D scene; and
aggregating the cells into one or more zones in accordance with the second map, each zone having a computing cost that is the sum of the computing costs of the cells belonging to the zone, the computing cost of the zone allowing a real-time simulation of the zone on a computing resource,
wherein the computation of the space quantization of the 3D scene further comprises:
computing a surface quantum S q defined by the relation
S q =(CPU CA )/(density of computing costs) Max ,

wherein (CPU CA ) represents an accuracy of a computer resource cost for processing the zones and (density of computing costs) Max is the highest density represented on the first map, and
discretizing the provided 3D scene into cells, each cell having a size equal to the surface quantum S q .

14. The non-transitory computer readable medium of claim 13 , wherein the aggregation of the cells into one or more zones is further carried out with a combinatorial optimization algorithm.

15. The non-transitory computer readable medium of claim 14 , wherein the combinatorial optimization algorithm is an Ant colony algorithm.

16. The non-transitory computer readable medium of claim 13 , wherein the method further comprises, before the aggregation of the cells: computing one or more clusters of one or more cells in accordance with the second map, and
wherein the aggreg

Assignees

• Dassault Systemes

Inventors

• Boulkenafed Malika
• Belmans Philippe Robert Felix

Classifications

• G06T19/20 Primary

  Editing of three-dimensional [3D] images, e.g. changing shapes or colours, aligning objects or positioning parts · CPC title

• G06T15/005

  General purpose rendering architectures · CPC title

• G06T2210/52

  Parallel processing · CPC title

• G06T2219/2016

  Rotation, translation, scaling · CPC title

• G06T2219/2008

  Assembling, disassembling · CPC title