Method, program and system for simulating a 3d scene with a set of computing resources running in parallel

Patent metadata

Field	Value
Publication number	US-2018096514-A1
Application number	US-201715719267-A
Country	US
Kind code	A1
Filing date	Sep 28, 2017
Priority date	Sep 30, 2016
Publication date	Apr 5, 2018
Grant date	—

Abstract

The invention notably relates to a computer-implemented method for simulating a 3D scene. The simulation is carried out with a set of computing resources running in parallel. The method comprises partitioning a 3D scene into a plurality of zones. Each zone is sized to satisfy real-time computing constraint by one computing resource of the set. The method comprises assigning each zone of the plurality to a computing resource, computing an estimation of a load of each computing resource and determining whether one or more computing resources are over-loaded or under-loaded, computing, for each zone, a contribution of the zone to the load of the computing resource to which the zone is assigned, reassigning one or more zones of a computing resource that is over-loaded or under-loaded to another computing resource, the reassignment resulting from the computed contributions of the zones with a combinatorial optimization algorithm.

First claim

1 . A computer-implemented method for simulating a 3D scene, the simulation being carried out with a set of computing resources running in parallel, comprising:
partitioning a 3D scene into a plurality of zones, each zone being sized to satisfy real-time computing constraint by one computing resource of the set; assigning each zone of the plurality to a computing resource; computing an estimation of a load of each computing resource (S i ) and determining whether one or more computing resources are over-loaded or under-loaded; computing, for each zone, a contribution of the zone to the load of the computing resource to which the zone is assigned; and reassigning one or more zones of a computing resource that is over-loaded or under-loaded to another computing resource, the reassignment resulting from the computed contributions of the zones with a combinatorial optimization algorithm.

2 . The computer-implemented method of claim 1 , wherein the reassignment of one or more zones to another computing resource is carried out according to one or more of the following criterions:
the number of computing resources is minimal; the number of zones reassigned to another computing resource is minimal; and the one or more zones are reassigned to another computing resource that already performs computation for a zone that is neighbor of the reassigned one or more zones.

3 . The computer-implemented method of claim 1 , wherein the reassignment of one or more zones to another computing resource is carried out such that a resulting load of each computing resource verifies
λ min ≦λ i ′≦λ max

wherein λ min is the minimum load of a computing resource, λ max is the maximum load of a computing resource.

4 . The computer-implemented method of claim 1 , wherein the estimation of the load (λ i ) of each computing resource is computed with the relation λ i (%)=100·(T max −T i )/T max
wherein λ i (%) is a percentage of the estimated load λ i , T max is the maximum time allocated to a computing resource for computing a time step of the simulation, T i is the elapsed time used by a computing resource for computing a time step of the simulation.

5 . The computer-implemented method of claim 1 , wherein the contribution of a zone is computed with the formula £A i =μ i ·λ i
wherein μ i is a weight factor with a value that belongs to a range [0; 1].

6 . The computer-implemented method of claim 5 , wherein the weight factor μ i is estimated from one or more selected among:
a surface or a volume of a zone;
a number of dynamic objects of a zone;
an analytical model of the computer resource of load λ i .

7 . The computer-implemented method of claim 1 , wherein one or more zones of the plurality of zones is a 2D zone, wherein a 2D zone is 2D surface in the 3D scene.

8 . The computer-implemented method of claim 1 , wherein one or more zones of the plurality of zones is a 3D zone, wherein a 3D zone is 3D volume of the 3D scene.

9 . The computer-implemented method of claim 1 , wherein the steps of computing the estimation of the load and determining whether one or more computing resources are over-loaded or under-loaded are performed each P time step of the simulation, wherein P is a natural number.

10 . The computer-implemented method of claim 9 , wherein the contribution of a zone is computed after that one or more computing resources have been determined as over-loaded or under-loaded.

11 . The computer-implemented method of claim 1 , wherein all the computing resources are identical.

12 . The computer-implemented method of claim 1 , wherein reassigning one or more zones of a computing resource that is over-loaded or under-loaded to another computing resource further comprises:
identifying, by the computing resource with a zone to be reassigned, objects of the 3D scene that are located within the zone to be reassigned; instantiating, by the computing resource receiving the zone to be reassigned, the identified objects; suppressing, by the computing resource with a zone to be reassigned, the identified objects; reassigning the zone to the computing resource receiving the zone.

13 . A non-transitory computer readable storage medium having recorded thereon a computer program that when executed by a computer causes the computer to execute the method of claim 1 .

14 . A system for simulating a 3D scene, the simulation being carried out with a set of computing resources running in parallel, comprising:
processing circuitry coupled to a memory, the memory having recorded thereon the computer program that when executed causes the processing circuitry to be configured to
partition a 3D scene into a plurality of zones, each zone being sized to satisfy real-time computing constraint by one computing resource of the set,
assign each zone of the plurality to a computing resource,
compute an estimation of a load of each computing resource and determine whether one or more computing resources are over-loaded or under-loaded,
compute, for each zone, a contribution of the zone to the load of the computing resource to which the zone is assigned, and
reassign one or more zones of a computing resource that is over-loaded or under-loaded to another computing resource, the reassignment resulting from the computed contributions of the zones with a combinatorial optimization algorithm.

Assignees

• Dassault Systemes

Inventors

• Boulkenafed Malika
• Belmans Philippe Robert Felix

Classifications

• G06F9/5083 Primary

  Techniques for rebalancing the load in a distributed system · CPC title

• G06F30/00

  Computer-aided design [CAD] · CPC title

• G06T7/10

  Segmentation; Edge detection (motion-based segmentation G06T7/215) · CPC title

• G06T2210/52

  Parallel processing · CPC title

• G06T19/00

  Manipulating three-dimensional [3D] models or images for computer graphics · CPC title