# US 8,275,805 B2 · Method of decreasing a total computation time for a visual simulation loop in a virtual world application

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

- Number: US 8,275,805 B2
- Document ID: US8275805B2
- Status: Granted
- Kind: B2
- Application number: 12/732,392
- Filed: 2010-03-26
- Published: 2011-09-29
- Granted: 2012-09-25
- Earliest claimed: 2010-03-26
- Assignees: Intel Corporation
- Inventors: Jatin Chhugani; Bryan Catanzaro; Sanjeev Kumar; Changkyu Kim; Nadathur Rajagopalan Satish
- Web page: https://patentgrep.com/patent/US8275805B2

## CPC

- G06T 15/00: Three-dimensional [3D] image rendering
- G06T 13/00: Animation
- G06T 17/005: {Tree description, e.g. octree, quadtree}
- G06T 2200/28: involving image processing hardware
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A method of decreasing a total computation time for a visual simulation loop includes sharing a common data structure across each phase of the visual simulation loop by adapting the common data structure to a requirement for each particular phase prior to performing a computation for that particular phase.

## Claims

### Claim 1

A method of enabling a visual representation on an electronic display of a virtual scene generated by a visual simulation loop, the method comprising:
building a data structure for a first phase of the visual simulation loop;
performing a first computation for the first phase using the data structure;
adapting the data structure for a second phase of the visual simulation loop; and
performing a second computation for the second phase using the adapted data structure.

### Claim 2 (depends on 1)

The method of claim 1 further comprising:
adapting the data structure for each additional phase of the visual simulation loop; and
performing a subsequent computation for each additional phase of the visual simulation loop using a corresponding one of the adapted data structures.

### Claim 3 (depends on 1)

The method of claim 1 wherein:
the visual simulation loop comprises a physical simulation phase, a visibility computation phase, an artificial intelligence phase, and a rendering phase.

### Claim 4 (depends on 3)

The method of claim 3 wherein:
the visual simulation loop is handled by a first processing device and a second processing device;
the first processing device performs the artificial intelligence phase, the visibility computation phase, and a first instance of the physical simulation phase; and
the second processing device performs the rendering phase and a second instance of the physical simulation phase.

### Claim 5 (depends on 1)

The method of claim 1 wherein:
the data structure comprises one of a kd-tree and a bounding volume hierarchy.

### Claim 6 (depends on 1)

The method of claim 1 wherein:
the first phase is a physical simulation phase and the second phase is a rendering phase; and
adapting the data structure comprises performing a Surface Area Heuristic.

### Claim 7 (depends on 1)

The method of claim 1 wherein:
the first phase is a rendering phase and the second phase is a physical simulation phase; and
adapting the data structure comprises:
identifying a spatial hierarchy structure comprising a root node and leaf nodes;
identifying a plurality of primitives used by the rendering phase;
populating the leaf nodes with particular ones of the plurality of primitives.

### Claim 8 (depends on 7)

The method of claim 7 wherein:
populating the leaf nodes is performed in linear time.

### Claim 9

A method of decreasing a total computation time for a visual simulation loop, the method comprising:
sharing a common data structure across each phase of the visual simulation loop by adapting the common data structure to a requirement for each particular phase prior to performing a computation for that particular phase.

### Claim 10 (depends on 9)

The method of claim 9 wherein:
the visual simulation loop comprises a physical simulation phase, a visibility computation phase, an artificial intelligence phase, and a rendering phase.

### Claim 11 (depends on 10)

The method of claim 10 wherein:
the visual simulation loop is handled at a first processing device and a second processing device;
the first processing device performs the artificial intelligence phase, the visibility computation phase, and a first instance of the physical simulation phase; and
the second processing device performs the rendering phase and a second instance of the physical simulation phase.

### Claim 12 (depends on 9)

The method of claim 9 wherein:
the common data structure comprises either a kd-tree or a bounding volume hierarchy.

### Claim 13 (depends on 9)

The method of claim 9 wherein:
a first phase of the visual simulation loop is a physical simulation phase and a second phase of the visual simulation loop is a rendering phase; and
adapting the common data structure comprises performing a Surface Area Heuristic.

### Claim 14 (depends on 9)

The method of claim 9 wherein:
a first phase of the visual simulation loop is a rendering phase and a second phase of the visual simulation loop is a physical simulation phase; and
adapting the common data structure comprises:
identifying a spatial hierarchy structure comprising a root node and leaf nodes;
identifying a plurality of primitives used by the rendering phase; and
populating the leaf nodes with particular ones of the plurality of primitives.

### Claim 15 (depends on 14)

The method of claim 14 wherein:
populating the leaf nodes is performed in linear time.

### Claim 16

A method of handling a visual simulation loop in a Virtual World application, the method comprising:
for each image update frame of the visual simulation loop:
building exactly one data structure;
performing a first computation using an original or an adapted version of the data structure on a server processing device; and
performing a second computation using the original or an adapted version of the data structure on a client processing device.

### Claim 17 (depends on 16)

The method of claim 16 wherein:
the data structure resides in an on-chip cache of the client processing device.

### Claim 18 (depends on 16)

The method of claim 16 wherein:
the first computation and the second computation are the only computations performed during the image update frame.

### Claim 19 (depends on 16)

The method of claim 16 wherein:
the data structure comprises one of a kd-tree and a bounding volume hierarchy.