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

Patent metadata

Field	Value
Publication number	US-2018173827-A1
Application number	US-201715845620-A
Country	US
Kind code	A1
Filing date	Dec 18, 2017
Priority date	Dec 21, 2016
Publication date	Jun 21, 2018
Grant date	—

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

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; discretizing the provided 3D scene into cells by computing a space quantization of the 3D scene free of dynamic objects, a dynamic object being an object that can potentially move in the 3D scene; 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.

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 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.

5 . 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 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.

6 . The computer-implemented method of claim 5 , 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 border the polyline.

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

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

9 . 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.

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

11 . The computer-implemented method of claim 1 , 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 .

12 . The computer-implemented method of claim 10 , 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 . 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.

14 . 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; discretizing the provided 3D scene into cells by computing a space quantization of the 3D scene free of dynamic objects, a dynamic object being an object that can potentially move in the 3D scene; 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.

15 . A system comprising:
a processor coupled to a memory and a graphical user interface, the memory having recorded thereon the computer program 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, that when executed causes the processor to be configured to: obtain a 3D scene comprising one or more objects, each object generating a computing resource cost, compute a first map that represents a density of computing costs of the obtained 3D scene, define 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, discretize the provided 3D scene into cells by computing a space quantization of the 3D scene free of dynamic objects, a dynamic object being an object that can potentially move in the 3D scene, compute, for each cell, a computing cost from the first map of the 3D scene, and aggregate 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 belo

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

• G06T7/11

  Region-based segmentation · CPC title

• G06F2111/04

  Constraint-based CAD · CPC title

• A63F13/00

  Video games, i.e. games using an electronically generated display having two or more dimensions · CPC title