# US 10,504,271 B2 · Method, program and system for simulating a 3D scene with a set of computing resources running in parallel

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,504,271 B2
- Document ID: US10504271B2
- Status: Granted
- Kind: B2
- Application number: 15/719,267
- Filed: 2017-09-28
- Published: 2018-04-05
- Granted: 2019-12-10
- Earliest claimed: 2016-09-30
- Assignees: Dassault Systemes
- Applicants: Dassault Systemes
- Inventors: Malika Boulkenafed; Philippe Robert Felix Belmans
- Web page: https://patentgrep.com/patent/US10504271B2

## CPC

- G06T 15/005: {General purpose rendering architectures}
- G06F 9/5083: {Techniques for rebalancing the load in a distributed system}
- G06F 30/00: Computer-aided design [CAD]
- G06T 7/10: Segmentation; Edge detection (motion-based segmentation G06T7/215)
- G06T 17/00: Three-dimensional [3D] modelling for computer graphics
- G06T 2200/04: involving 3D image data
- G06T 2200/16: involving adaptation to the client's capabilities
- G06T 2210/52: Parallel processing
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

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

## Claims

### Claim 1

A computer-implemented method for simulating a 3D scene, the simulation being carried out with a set of computing resources, implemented by processing circuitry, running in parallel, comprising:
partitioning, by the processing circuity, 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, by the processing circuity, each zone of the plurality to a computing resource;
computing, by the processing circuity, an estimation of a load of each computing resource (Si) and determining whether one or more computing resources are over-loaded or under-loaded;
computing, for each zone and by the processing circuitry a contribution of the zone to the load of the computing resource to which the zone is assigned; and
reassigning, by the processing circuity, 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.

### Claim 2 (depends on 1)

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 perfonns computation for a zone that is neighbor of the reassigned one or more zones.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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·(Tmax−Ti)/Tmax
wherein λi (%) is a percentage of the estimated load λi, Tmax is the maximum time allocated to a computing resource for computing a time step of the simulation, Ti is the elapsed time used by a computing resource for computing a time step of the simulation.

### Claim 5 (depends on 1)

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

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 1)

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.

### Claim 9 (depends on 1)

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.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 1)

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

### Claim 12 (depends on 1)

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.

### Claim 13 (depends on 1)

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.

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