Simulation method and device for determining collision between objects

Patent metadata

Field	Value
Publication number	US-10824775-B2
Application number	US-201415101490-A
Country	US
Kind code	B2
Filing date	Apr 25, 2014
Priority date	Dec 18, 2013
Publication date	Nov 3, 2020
Grant date	Nov 3, 2020

Abstract

Methods and apparatus provide for, at each of plural calculation timings, associating pieces of position information indicating the positions of objects in a virtual space at the calculation timing with leaves and creates a complete binary tree in which position information reflecting pieces of the position information of child nodes is associated with an internal node, and a node shuffling section that shuffles 2·2n (n≥1) child nodes regarding each group of 2n nodes on the basis of the position information associated with each of the 2·2n child nodes belonging to the 2n nodes in each layer sequentially from the immediately-upper layer of the lowermost layer in the complete binary tree; and carrying out collision determination between objects by using the complete binary tree resulting from the shuffling by the node shuffling section.

First claim

The invention claimed is:

1. An apparatus, comprising:
a computer system operating to execute simulation to control objects in a virtual space for display on a display device, where the objects move with respect to one another within the virtual space;
a collision detection section operating to affect controlling the simulation as a function of determine prospective collision between one or more of the objects at each of a plurality of determination timings about over a period of time, wherein the collision detection section includes:
a complete binary tree creating section that, at each of the plurality of calculation timings, associates pieces of position information indicating positions of the objects in the virtual space at the calculation timing with leaves and creates a complete binary tree in which position information reflecting pieces of the position information of child nodes is associated with an internal node; and
a node shuffling section that shuffles 2·2 n (n≥1) child nodes regarding each group of 2 n nodes on a basis of the position information associated with each of the 2·2 n child nodes belonging to the 2n nodes in each layer sequentially from an immediately-upper layer of a lowermost layer in the complete binary tree,
wherein collision determination between objects is carried out by using the complete binary tree resulting from the shuffling by the node shuffling section,
the position information indicating the position of the object is a region in which the object that corresponds is inscribed, and
the node shuffling section shuffles the 2·2 n child nodes belonging to the 2 n nodes into combinations with which the region of a parent node becomes reduced in size.

2. The apparatus according to claim 1 , wherein, regarding each of a plurality of combination candidates obtained by shuffling the 2·2 n child nodes, the node shuffling section randomly changes size of the region of a parent node with the combination candidate, and the node shuffling section shuffles the 2·2 n child nodes belonging to the 2 n nodes to yield the combination candidate with which the region resulting from the change in the size is reduced in size.

3. The apparatus according to claim 2 , further comprising a determining section that determines whether or not overlapping is present between the regions of nodes for each pair of two nodes in each layer sequentially from an uppermost layer in the complete binary tree resulting from the shuffling by the node shuffling section.

4. The apparatus according to claim 3 , wherein the determining section further determines whether or not overlapping is present between the regions of nodes in all combinations of four child nodes belonging to two nodes about which it is determined that overlapping is present by the determining section in a previous layer.

5. The apparatus according to claim 1 , wherein the complete binary tree creating section creates the complete binary tree by using a correspondence relationship between leaves and objects in a complete binary tree used for collision determination at a previous calculation timing in a case of creating a complete binary tree to be used for collision determination at a second or subsequent calculation timing.

6. A method, comprising:
executing computer simulation to control objects in a virtual space for display on a display device, where the objects move with respect to one another within the virtual space;
controlling the simulation as a function of determining prospective collision between one or more of the objects at each of a plurality of determination timings about over a period of time, wherein the determining includes:
associating pieces of position information indicating positions of the objects in the virtual space at a certain determination timing with leaves and creating a complete binary tree in which position information reflecting pieces of the position information of child nodes is associated with an internal node; and
shuffling 2·2 n (n≥1) child nodes regarding each group of 2 n nodes on a basis of the position information associated with each of the 2·2 n child nodes belonging to the 2 n nodes in each layer sequentially from an immediately-upper layer of a lowermost layer in the complete binary tree, wherein:
the position information indicating the position of the object is a region in which the object that corresponds is inscribed, and
the shuffling includes shuffling the 2·2 n child nodes belonging to the 2 n nodes into combinations with which the region of a parent node becomes reduced in size.

7. A non-transitory, computer readable recording medium containing a program for causing a computer system to carry out actions, comprising:
executing computer simulation to control objects in a virtual space for display on a display device, where the objects move with respect to one another within the virtual space;
controlling the simulation as a function of determining prospective collision between one or more of the objects at each of a plurality of determination timings about over a period of time, wherein the determining includes:
associating pieces of position information indicating positions of the objects in the virtual space at a certain determination timing with leaves and creating a complete binary tree in which position information reflecting pieces of the position information of child nodes is associated with an internal node; and
shuffling 2·2 n (n≥1) child nodes regarding each group of 2 n nodes on a basis of the position information associated with each of the 2·2 n child nodes belonging to the 2 n nodes in each layer sequentially from an immediately-upper layer of a lowermost layer in the complete binary tree, wherein:
the position information indicating the position of the object is a region in which the object that corresponds is inscribed, and
the shuffling includes shuffling the 2·2 n child nodes belonging to the 2 n nodes into combinations with which the region of a parent node becomes reduced in size.

Assignees

• Sony Interactive Entertainment Inc

Inventors

• Ishikawa Hitoshi
• Matsuike Hiroshi
• Yoshida Koichi

Classifications

• A63F13/577 Primary

  using determination of contact between game characters or objects, e.g. to avoid collision between virtual racing cars · CPC title

• G06T17/005

  Tree description, e.g. octree, quadtree · CPC title

• G06T2210/52

  Parallel processing · CPC title

• A63F13/44

  involving timing of operations, e.g. performing an action within a time slot · CPC title

• G06T2210/21

  Collision detection, intersection · CPC title