WO2015093073A1 - シミュレーション装置 - Google Patents

シミュレーション装置 Download PDF

Info

Publication number
WO2015093073A1
WO2015093073A1 PCT/JP2014/061689 JP2014061689W WO2015093073A1 WO 2015093073 A1 WO2015093073 A1 WO 2015093073A1 JP 2014061689 W JP2014061689 W JP 2014061689W WO 2015093073 A1 WO2015093073 A1 WO 2015093073A1
Authority
WO
WIPO (PCT)
Prior art keywords
node
position information
binary tree
unit
complete binary
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2014/061689
Other languages
English (en)
French (fr)
Inventor
石川　仁
裕史 松生
弘一 吉田
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Sony Interactive Entertainment Inc
Original Assignee
Sony Computer Entertainment Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Sony Computer Entertainment Inc filed Critical Sony Computer Entertainment Inc
Priority to CN201480067196.4A priority Critical patent/CN105874511B/zh
Priority to JP2015553386A priority patent/JP5967786B2/ja
Priority to US15/101,490 priority patent/US10824775B2/en
Priority to EP14871365.4A priority patent/EP3086293B1/en
Publication of WO2015093073A1 publication Critical patent/WO2015093073A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F30/00—Computer-aided design [CAD]
    • G06F30/20—Design optimisation, verification or simulation
    • A—HUMAN NECESSITIES
    • A63—SPORTS; GAMES; AMUSEMENTS
    • A63F—CARD, BOARD, OR ROULETTE GAMES; INDOOR GAMES USING SMALL MOVING PLAYING BODIES; VIDEO GAMES; GAMES NOT OTHERWISE PROVIDED FOR
    • A63F13/00—Video games, i.e. games using an electronically generated display having two or more dimensions
    • A63F13/40—Processing input control signals of video game devices, e.g. signals generated by the player or derived from the environment
    • A63F13/44—Processing input control signals of video game devices, e.g. signals generated by the player or derived from the environment involving timing of operations, e.g. performing an action within a time slot
    • A—HUMAN NECESSITIES
    • A63—SPORTS; GAMES; AMUSEMENTS
    • A63F—CARD, BOARD, OR ROULETTE GAMES; INDOOR GAMES USING SMALL MOVING PLAYING BODIES; VIDEO GAMES; GAMES NOT OTHERWISE PROVIDED FOR
    • A63F13/00—Video games, i.e. games using an electronically generated display having two or more dimensions
    • A63F13/55—Controlling game characters or game objects based on the game progress
    • A63F13/57—Simulating properties, behaviour or motion of objects in the game world, e.g. computing tyre load in a car race game
    • A63F13/577—Simulating properties, behaviour or motion of objects in the game world, e.g. computing tyre load in a car race game using determination of contact between game characters or objects, e.g. to avoid collision between virtual racing cars
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00—Three-dimensional [3D] modelling for computer graphics
    • G06T17/005—Tree description, e.g. octree, quadtree
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2210/00—Indexing scheme for image generation or computer graphics
    • G06T2210/21—Collision detection, intersection
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2210/00—Indexing scheme for image generation or computer graphics
    • G06T2210/52—Parallel processing

Definitions

  • the present invention relates to a simulation apparatus that executes a simulation on a plurality of objects that move in a virtual space with time, a control method therefor, a program, and an information storage medium.
  • collision determination is performed based on the positions of the two objects in the virtual space.
  • it is inefficient to perform collision determination with a brute force for a plurality of objects because the amount of calculation increases as the number of objects increases. Therefore, conventionally, as one method for reducing the number of collision determinations, collision determination using a binary tree that reflects the positional relationship between a plurality of objects in a virtual space is performed. By using a binary tree reflecting the positional relationship between objects, it is possible to skip collision determination between objects whose positions in the virtual space are separated.
  • an area including all objects is a root
  • each divided area obtained by dividing the area into two is a child node
  • each divided area is further divided into two grandchild nodes.
  • the conventional binary tree construction method may not be able to perform parallel processing efficiently because the number of objects included in the divided areas of each layer is different.
  • One of the objects of the present invention is to provide a method for constructing a binary tree that reflects the position of an object in a virtual space for performing object collision determination, which is suitable for parallel processing.
  • the simulation apparatus is a simulation apparatus that determines a collision between objects at each of a plurality of calculation points for a plurality of objects that move in a virtual space with time, and at each of the plurality of calculation points,
  • a complete binary tree creating unit for creating a complete binary tree in which position information indicating the position of the object in the virtual space at the time of the calculation is associated with a leaf, and position information reflecting the position information of the child node is associated with an internal node; , in each layer from one layer above the lowermost layer in the complete binary tree in this order, 2 n (n ⁇ 1) for each number of nodes, associated with a 2 ⁇ 2 n pieces of child nodes respectively belonging to the 2 n pieces of node was based on the positional information, and the node replacement section replacing the 2 ⁇ 2 n pieces of child nodes,
  • the collision determination between objects is performed using the complete binary tree replaced by the node swapping unit has been performed.
  • position information indicating a position of the object is an area that is inscribed the object corresponding the node interchanging unit, 2 ⁇ 2 n pieces of child nodes belonging to the 2 n pieces of node May be replaced with a combination in which the area of the parent node becomes smaller.
  • the node replacement unit randomly sets the size of the region of the parent node in each combination candidate for each of a plurality of combination candidates obtained by replacing the 2 ⁇ 2 n child nodes. is changed to, as regions of varying the size becomes smaller combination candidate, it is also possible to replace the 2 ⁇ 2 n pieces of child nodes belonging to the 2 n pieces of node.
  • the simulation apparatus described above determines whether or not there is an overlap in the area of each node for each two nodes in each layer in order from the top layer. It is good also as including further the judgment part which judges.
  • the determination unit may include the combination of all four child nodes belonging to the two nodes determined to be overlapped by the determination unit in the previous layer in the region of each node. It may be further determined whether or not there is an overlap.
  • the complete binary tree creation unit creates a complete binary tree used for collision determination at the previous calculation time when creating a complete binary tree used for collision determination at the second or later calculation time. It is also possible to create a complete binary tree using the correspondence between leaves and objects.
  • the program according to the present invention provides a simulation apparatus that determines a collision between objects at each of a plurality of determination points for a plurality of objects that move in the virtual space with time.
  • a complete binary tree creating means for creating a complete binary tree in which position information indicating the position of a node is associated with a leaf and the position information reflecting the position information of a child node is associated with an internal node; and from the lowest layer in the complete binary tree Based on the position information associated with each of 2 ⁇ 2 n child nodes belonging to the 2 n nodes, for each 2 n (n ⁇ 1) nodes in each layer in order from the upper layer, 2.2 Program for functioning as node replacement means for replacing n child nodes.
  • This program may be stored in a computer-readable information storage medium.
  • the control method of the simulation apparatus is a control method for controlling a simulation apparatus that determines a collision between objects at each of a plurality of determination points for a plurality of objects that move in a virtual space with time.
  • 2 n (n ⁇ 1) for each number of nodes, associated with a 2 ⁇ 2 n pieces of child nodes respectively belonging to the 2 n pieces of node was based on the positional information, the nodes interchange stearyl replacing the 2 ⁇ 2 n pieces of child nodes Characterized in that it comprises a flop, a.
  • FIG. 11A It is a figure which shows an example of the complete binary tree after the node replacement process about a 3rd layer is completed. It is a figure which shows an example of the acquisition object pair and the object check table which manages allocation of an acquisition object pair. An example of a judgment object pair and a comparison object pair is shown. It is a flowchart which shows an example of the flow of the physical quantity calculation process of the object using the common object pair which concerns on this embodiment. It is a figure which shows an example of the connection procedure of an object. It is a figure which shows typically an example of the connection object connected by the object connection part. It is a figure which shows typically an example of the connection object after updating the pointer value of each object about the connection object shown to FIG. 11A. It is a figure which shows typically an example of the connection object after updating the pointer value of each object about the connection object shown to FIG. 11B. It is a figure which shows transition of the pointer value of each object shown to FIG. 11A.
  • FIG. 1 is a diagram illustrating an example of a configuration of a simulation apparatus 1 according to the present embodiment.
  • the simulation apparatus 1 according to the present embodiment is, for example, a home game machine or a personal computer, and as illustrated in FIG. 1, a control unit 11, a storage unit 12, a communication unit 13, an operation unit 14, and a display unit. 15 is comprised.
  • the control unit 11 includes a CPU 5, a GPU 6, and the like, and executes various types of information processing according to programs stored in the storage unit 12. In the present embodiment, a specific example of processing executed by the control unit 11 will be described later.
  • the storage unit 12 includes a memory element such as a RAM or a ROM, a hard disk drive, and the like, and stores programs executed by the control unit 11 and various data.
  • the storage unit 12 also operates as a work memory for the control unit 11.
  • the communication unit 13 is a communication interface, receives data coming from the outside via a communication network, and outputs it to the control unit 11. Moreover, according to the instruction
  • the operation unit 14 is a keyboard, a mouse, a controller of a consumer game machine, or the like, and receives a user operation input and outputs a signal indicating the content to the control unit 11.
  • the display unit 15 is a display device such as a liquid crystal display, and displays various images in accordance with instructions from the control unit 11.
  • the simulation apparatus 1 may include an optical disk drive, a USB (Universal Serial Bus) port, and the like for reading an optical disk such as a DVD-ROM and a Blu-ray (registered trademark) disk.
  • an optical disk drive such as a DVD-ROM and a Blu-ray (registered trademark) disk.
  • the simulation apparatus 1 for a plurality of objects that move in the virtual space, the positions of the objects that change with time are calculated by a simulation process such as a physical simulation.
  • a simulation process is performed in consideration of the influence on the position of each object due to the collision between the objects.
  • This simulation process is mainly executed by the GPU 6 of the control unit 11, but may be executed by the CPU 5 and other devices.
  • the GPU 6 Since the GPU 6 has a larger number of cores than the CPU 5 and the number of processing units (threads) that can be executed simultaneously, it is suitable for parallel processing. On the other hand, threads that are executed simultaneously are required to have the same processing. Therefore, in order to efficiently execute the simulation process using the GPU 6, it is necessary to perform the process with an algorithm different from the conventional one.
  • each object is associated with ID information (identifier) that is uniquely set to identify the object.
  • ID information identifier
  • attribute information may be associated with each object.
  • the attribute information may be, for example, information indicating the type of object, information defining the outer shape, and other various attribute information according to the type of object.
  • a physical quantity (speed, acceleration, etc.) is given to at least some of the plurality of objects arranged in the virtual space (S1).
  • positioned in virtual space changes with time.
  • constraint conditions for the two objects determined to collide with each other in the process S1 are created (S3).
  • a constraint condition for constraining the movement of such an object is created.
  • a physical quantity given to each object to satisfy the constraint condition is calculated (S4). The process S4 will be described in detail later.
  • the physical quantity given to each object is reflected in the position in the virtual space (S6). That is, the position of each object at the timing of drawing the state of the virtual space is calculated from the physical quantity given to each object. Then, the simulation apparatus 1 draws an image indicating the state of the virtual space in which the object is arranged at the calculated position, and outputs the image to the display unit 15. As a result, each time the unit time d elapses, an image of the virtual space in which each object is arranged at the current position calculated by the simulation apparatus 1 is displayed on the screen of the display unit 15.
  • the object collision determination process in the process S2 the object physical quantity calculation process in the process S4, and the object sleep management process in the process S5 will be described in detail below.
  • FIG. 3 is a functional block diagram illustrating an example of main functions executed by the simulation apparatus 1 according to the present embodiment.
  • the control unit 11 of the simulation apparatus 1 functionally includes, for example, a complete binary tree creation unit 21, a node replacement unit 22, a collision determination unit 23, and an object pair information acquisition unit. 31, a rearrangement unit 32, an identification unit 33, an allocation unit 34, a calculation unit 35, a value addition unit 41, a pointer value overwrite unit 43, a route value overwrite unit 43, and a pointer value update unit 45.
  • These functions are realized by the control unit 11 executing a program stored in the storage unit 12.
  • This program is supplied to the simulation apparatus 1 via a computer-readable information storage medium such as an optical disk, a magnetic disk, a magnetic tape, a magneto-optical disk, or a flash memory, or via communication means such as the Internet.
  • the object collision determination process is realized by the complete binary tree creation unit 21, the node replacement unit 22, and the collision determination unit 23 illustrated in FIG.
  • the complete binary tree creation unit 21 associates position information indicating the position of each of a plurality of objects arranged in the virtual space with the leaf, and associates position information reflecting the position information of the child node with the internal node. Create a complete binary tree.
  • the position information indicating the position of the object in the virtual space is the position of each object in the virtual space based on the attribute information associated with the object (for example, information defining the outer shape) and the coordinate information of the virtual space. It may indicate a relationship.
  • a so-called boundary volume (Boundary Volume) that includes an object is used as position information.
  • This boundary volume is a simplified representation of the position and size of the area inscribed in the virtual space. Since the boundary volume is a simplified shape of the object, the collision determination for the boundary volume can be performed faster than the collision determination for the detailed model of the object.
  • a sphere for example, a sphere (SPHERE), an axis parallel bounding box (Axis-Aligned Bounding Box; AABB), which is a rectangular parallelepiped having sides parallel to each axis (x, y, z axis), or the like is used.
  • AABB axis parallel bounding box
  • the bounding volume is an axis parallel bounding box
  • the coordinate values of the minimum point where the coordinate value of each axis is the minimum and the maximum point where the coordinate value of each axis is the maximum among the vertices of the axis parallel bounding box is This is position information.
  • the center coordinates of the axis parallel bounding box and the distances from the center to each of three planes orthogonal to each other may be used as position information. That is, the position information only needs to indicate the shape of the boundary volume of the object and the position in the virtual space.
  • the complete binary tree creation unit 21 associates information (such as the coordinate value of the minimum point and the coordinate value of the maximum point) of each of the plurality of objects arranged in the virtual space with the leaf as position information. At this time, the complete binary tree creation unit 21 may associate the position information of each object with the leaf in the order of the identifiers associated with each object, or may associate the position information of each object with the leaf at random.
  • the complete binary tree creating unit 21 creates a new inscribed in the boundary volume indicated by each of the two pieces of positional information associated with the two child nodes, with the parent node having two leaves as child nodes.
  • the boundary volume information is associated as position information. Specifically, information on a new axis parallel bounding box including the axis parallel bounding box indicated by the two position information associated with the two leaves that are child nodes of the parent node is used as the position of the parent node. Associate as information.
  • the complete binary tree creation unit 21 performs this process for every two leaves, and associates position information with each parent node.
  • the complete binary tree creation unit 21 includes the axis parallel bounding box indicated by the two pieces of position information associated with the two nodes in the parent node having two nodes associated with the position information as child nodes.
  • the information on the new axis parallel bounding box to be related is related as position information.
  • the complete binary tree creation unit 21 performs this process for every two nodes, and associates position information with each parent node. In this way, the complete binary tree creation unit 21 creates a complete binary tree in which position information is associated with all nodes by executing the process of associating position information with the parent node for every two nodes up to the root. To do.
  • the complete binary tree creating unit 21 includes the second layer, the third layer, and the fourth layer in order, with the leaf as the first layer, and the fourth layer as a root.
  • the leaves of the first layer are the leaves 11 to 18 from the left
  • the nodes of the second layer are the nodes 21 to 24 from the left
  • the nodes of the third layer are the nodes 31 and 32 from the left.
  • the complete binary tree creation unit 21 associates the position information P A to P H of each object with the leaves 11 to 18 in the first layer in the order of identifiers.
  • the complete binary tree creation unit 21, containing a shaft parallel bounding volumes indicated by the positional information P A associated with a leaf 11, a shaft parallel bounding volumes indicated by the position information P B associated with a leaf 12, the the new axis parallel bounding volume to as P AB, associated with node 21.
  • complete binary tree creation unit 21 a shaft parallel bounding volumes indicated by the positional information P C associated with a leaf 13, a shaft parallel bounding volume P D indicated by the positional information associated with the leaves 14, the new axis parallel bounding volume enclosing as P CD, associated with node 22.
  • the complete binary tree creation unit 21 associates a new axis parallel boundary volume containing the axis parallel boundary volume indicated by the position information associated with the two child nodes with the parent node, the node 23 P EF , node 24 is associated with P GH , and node 32 is associated with P EFGH .
  • the position information associated with the root is an axis parallel boundary volume that includes all of the objects A to H arranged in the virtual space.
  • the node exchanging unit 22 converts 2 n (n ⁇ 1) nodes to 2 n nodes from one layer above the lowest layer (leaf layer) of the complete binary tree created by the complete binary tree creating unit 21. based on 2 ⁇ 2 n pieces of child node position information associated with each belonging, replacing the 2 ⁇ 2 n pieces of child nodes.
  • the node replacing unit 22 replaces the position information of each object associated with the leaf of the complete binary tree created by the complete binary tree creating unit 21 into a form reflecting the positional relationship in the virtual space.
  • the process executed by the node replacement unit 22 will be described in detail using the complete binary tree illustrated in FIG.
  • the node replacement unit 22 has two nodes (node 21 and node 22, node 23 and node 24) in the second layer of the complete binary tree created by the complete binary tree creation unit 21.
  • the child nodes are switched based on the four pieces of positional information (P A to P D , P E to P H ) associated with the child nodes (leaf 11 to leaf 14, leaf 15 to leaf 18).
  • P A to P D , P E to P H the processing for the node 21 and the node 22
  • the processing for the node 23 and the node 24 is also executed at the same time.
  • the node replacement section 22 selects position information P B, P C, and P D is out of the axis parallel bounding box respectively, those relatively close relationship with the axis parallel bounding box indicating the position information P A To do.
  • node replacement section 22 position information P A and the position information P B, position information P A and the position information P C, position information P A and the position information P D, the axis parallel bounding box indicating two position information for each of The volume of the new axis parallel bounding box that includes ## EQU1 ## is calculated as V AB , V AC , and V AD , respectively. And it is judged that the position of the axis parallel boundary box which two position information shows is so near that this volume is small.
  • the node replacement unit 22 replaces the position information P A to P D so that the combination with the smallest volume belongs to the node 21. For example, if the volume V AC is determined to smallest, nodes interchanging unit 22, position information P A and the position information P C belongs to node 21, the position information P B and the position information P D belongs to the node 22 as replaces the position information P C and the position information P B.
  • the position information P A and the position information P C is a new axis parallel bounding box enclosing the axis parallel bounding box respectively associated with node 21 as the position information P AC, position information P B and the position information P D, respectively new axis parallel bounding box enclosing the axis parallel bounding box that is associated with node 22 as the position information P BD.
  • the node replacement unit 22 is a child of each of the two nodes (node 31 and node 32) in the third layer of the complete binary tree in which the nodes are replaced for the second layer.
  • the same processing as the processing in the second layer described above is executed for the node.
  • the complete binary tree illustrated in FIG. 4 is up to the fourth layer. However, in a complete binary tree having a deeper hierarchy, such processing is executed in each layer until the uppermost layer (root).
  • the node replacement unit 22 obtains the sum of the volumes of the axis parallel bounding boxes indicated by the position information associated with the nodes 21 and 22 in each combination candidate (V AB + V CD , V AC + V BD , V respectively AD + V BC ). Then, the combination having the smallest value among V AB + V CD , V AC + V BD , and V AD + V BC is selected as the optimal combination. Then, the node replacement unit 22 replaces each node so that the selected optimum combination is obtained.
  • the node replacement unit 22 determines a combination of two axis parallel boundary boxes that are relatively close to each other from the axis parallel boundary boxes associated with each of the plurality of child nodes to be replaced. In order to do this, the volume of the axis parallel bounding box that contains the two axis parallel bounding boxes that are the combination candidates is actually calculated, and the volume is associated with the two axis parallel bounding boxes that are included in the axis parallel bounding box whose volume is small. The child nodes are switched so that the two child nodes belong to the same parent node.
  • the node replacement unit 22 is not limited to such a method, and may determine a combination of two axis parallel bounding boxes that are relatively close to each other by various methods.
  • the node replacement unit 22 uses the numerical values such as the sum of the lengths of the three sides of the axis parallel bounding box including the two axis parallel bounding boxes as the combination candidates and the lengths of the diagonal lines as the determination criteria, and the positional relationship A combination of two axis parallel bounding boxes that are relatively close may be determined. Even in this case, it can be determined that the smaller the numerical value used as a criterion, the smaller the size of the axis parallel boundary box itself that contains the two axis parallel boundary boxes, and the positions of the two axis parallel boundary boxes are relatively close. I can judge.
  • FIG. 5 shows a simplified model of a plurality of objects arranged in the virtual space.
  • the simple model shown in FIG. 5 is an object in which objects of equal size (one grid indicates an object) are arranged in a grid-like two-dimensional space (xy coordinates).
  • eight objects A to H identifiers A to H
  • the axis parallel bounding box as the position information is also represented by a grid.
  • the position information PA of the object A includes the coordinate value (0, 2) of the minimum point at which the coordinate value of each axis is minimum, and
  • the axis parallel bounding box is represented by the coordinate value (1, 3) of the maximum point at which the coordinate value of each axis is maximum.
  • An object is to create a complete binary tree reflecting the positional relationship between the objects A to H in the two-dimensional space.
  • complete binary tree creation unit 21 associated with a leaf 11 to the leaf 18 the position information of the respective objects A ⁇ object H P A ⁇ P H to the identifier order to create a complete binary tree shown in FIG. 6A.
  • the node replacement unit 22 has the position information P A and the position information P B , the position information P A and the position information P C , the position information P A and the position information P D for the node 21 and the node 22 in the second layer. For each, the volume of a new axis parallel bounding box that includes the axis parallel bounding box indicated by the two pieces of position information (corresponding to an area in the simple model) is obtained.
  • the area V (xl ⁇ xs) (yl ⁇ ys).
  • the axis parallel boundary indicated by the position information P A minimum point (0, 2), maximum point (1, 3)) and position information P B (minimum point (5, 4), maximum point (6, 5)).
  • the new axis parallel bounding box P AB that contains the box is represented by a minimum point (0, 2) and a maximum point (6, 5).
  • the axis indicated by the position information P A (minimum point (0, 2), maximum point (0, 3)) and position information P C (minimum point (2, 2), maximum point (3, 3)).
  • the axis parallel bounding box indicated by the position information P A (minimum point (0, 2), maximum point (0, 3)) and position information P D (minimum point (2, 4), maximum point (3, 5))
  • position belongs as position information P B in the information interchanged and P C.
  • the position information P E and position information P F , the position information P E and position information P G , the position information P E and the position information P H are also included for each of the nodes 23 and 24 in the second layer.
  • the node replacement unit 22 performs a node replacement process for the third layer using the complete binary tree of FIG. 6B.
  • the position information P AC and the position information P BD the position information P AC and the position information P EH , the position information P AC and the position information P GF , the axes indicated by the two position information
  • node replacement section 22 replaces the positional information P BD to position information P AC and the position information P EH belongs to the node 31 and the position information P EH, processing by the node replacement section 22 Exit. From the above, the complete binary tree after the node replacement process for the third layer is completed is shown in FIG. 6C. As a result, a complete binary tree reflecting the positional relationship of the objects in the virtual space shown in FIG. 6C is obtained.
  • the complete binary tree creation unit 21 associates the position information P A , P C , P E , P H , P B , P D , P G , and P F from the left of the leaf.
  • the node replacement process based on the positional information associated with the child nodes of 2 n nodes performed by the node replacement unit 22 can be executed with the same algorithm regardless of which 2 n nodes are selected. Become. Therefore, the node replacement unit 22 can execute the node replacement process for each of the 2 n nodes in each layer in parallel.
  • the complete binary tree completed by the node replacement process by the node replacement unit 22 described above may not be an optimal complete binary tree reflecting the positional relationship of objects in the virtual space. This is because, when the node replacement unit 22 divides the object in the virtual space into combinations for each two objects, the local solution is obtained when performing an optimization process for obtaining a combination that minimizes the positional relationship between the two objects. Due to falling into. Therefore, processing for reducing the possibility of falling into a local solution executed by the node replacement unit 22 will be described. As described above, the node replacement unit 22 determines a combination of two pieces of positional information that are relatively close to each other from the positional information associated with each of the plurality of child nodes to be replaced.
  • the node replacement unit 22 obtains a numerical value that quantitatively indicates the positional relationship between the two child nodes in the combination candidate, and either increases or decreases the numerical value. Change randomly (ie, add noise to the number). Then, a combination candidate having a smaller numerical value after the change is adopted, and node replacement processing is executed so as to become the combination candidate.
  • the node replacement unit 22 is a numerical value that quantitatively indicates the positional relationship between two child nodes, and the size of an area that includes the area indicated by each of the two pieces of positional information associated with the two child nodes ( For example, the volume of the axis parallel bounding box is used.
  • the node replacement unit 22 selects a combination that minimizes the sum of the volumes of the axis parallel bounding boxes indicated by the position information associated with each of the node 21 and the node 22 from each combination candidate.
  • the node replacement unit 22 calculates the sum of the volumes of the axis parallel bounding boxes indicated by the position information associated with each of the nodes 21 and 22, the volume of the axis parallel bounding box indicated by the position information associated with each node.
  • Noise is added to (V AB , V CD , V AC, V BD , V AD , V BC ).
  • the sum of the volumes of the axis parallel bounding boxes indicated by the position information associated with each of the node 21 and the node 22 is (1 + ⁇ 1 ) V AB + (1 + ⁇ 2 ) V CD , (1 + ⁇ 3 ) V AC + (1 + ⁇ 4 ) V BD , (1 + ⁇ 5 ) V AD + (1 + ⁇ 6 ) V BC .
  • ⁇ m is determined in advance as three types of values, and may be randomly assigned to each combination candidate.
  • the node replacement unit 22 selects a combination that minimizes the sum of the volumes of the axis parallel bounding boxes indicated by the two pieces of position information to which these noises are added, from each combination candidate, and replaces the nodes.
  • the node replacement unit 22 replaces its child node every two nodes, the possibility of falling into a local solution is reduced, and finally the positional relationship of objects in the virtual space is reflected. An optimal complete binary tree is completed.
  • the node replacement unit 22 uses the size of the area inscribed in the two areas indicated by the two position information as a value that quantitatively indicates the positional relationship between the two child nodes in each combination candidate.
  • the volume of the axis parallel bounding box that includes the axis parallel bounding box indicated by the two pieces of position information is used, but the present invention is not limited to this example.
  • the node exchanging unit 22 quantitatively determines the positional relationship between the two pieces of position information by using a numerical value such as the sum of the lengths of the three sides of the axis parallel bounding box indicated by the two pieces of position information as combination candidates and the length of the diagonal line. It may be used as the value shown.
  • the node replacement unit 22 randomly changes a numerical value used as a value that quantitatively indicates the positional relationship between the two child nodes, and executes a node replacement process based on the changed numerical value.
  • the collision determination unit 23 executes a simulation process for performing a collision determination between objects using the complete binary tree that has been replaced by the node replacement unit 22.
  • the collision determination is performed on the child nodes of each node of the complete binary tree based on the associated positional information.
  • a collision determination method for example, based on position information using a boundary volume of a sphere, it is determined that the boundary volumes of the sphere collide when the distance of the center coordinate is smaller than the sum of two radii. There is a way.
  • the axis parallel boxes collide with each other.
  • the distance of the center coordinates in each axis is two radii (the distance from the center to the surface). )
  • the axis parallel bounding boxes collide with each other when it is determined that the sum is smaller than all three axes.
  • the collision determination by the collision determination unit 23 is performed using the complete binary tree in which the nodes are replaced by the node replacement unit 22.
  • the collision determination unit 23 performs collision determination on the two nodes in each layer in order from the root to the leaf of the complete binary tree based on the positional information associated with each node.
  • the collision determination unit 23 determines the four child nodes of the two nodes. Perform collision detection for all combinations.
  • the collision determination unit 23 performs a collision determination between the child nodes of the two nodes.
  • the process is executed based on the idea that the child nodes can be determined not to collide with each other. Since the position information associated with the node includes the position information of all lower nodes belonging to the node, if it is determined that there is no collision in the position information associated with the upper node, the position information associated with the lower node It can be said that there is no collision. Thereby, the collision determination unit 23 can skip the collision determination between objects that do not collide.
  • the collision determination unit 23 performs the collision determination in each layer in order from the third layer to the first layer of the complete binary tree illustrated in FIG. 6C that has been replaced by the node replacement unit 22.
  • the collision determination unit 23 the node between the third layer (node 31 and node 32), and position information P aceh associated with the node 31, and position information P BDGF associated with the node 32, the Based on the above-described collision determination method, collision determination between objects is performed.
  • the position information PACEH is It is determined that the axis parallel bounding box indicated and the axis parallel bounding box indicated by the position information PBDGFH collide with each other.
  • the collision determination unit 23 Since it is determined that the node 31 and the node 32 have collided, the collision determination unit 23 also performs the collision determination for all the combinations of the child nodes at the time of the collision determination in the second layer. That is, the collision determination unit 23 performs collision determination on the node 21 and the node 22, the node 21 and the node 23, the node 21 and the node 24, the node 22 and the node 23, the node 22 and the node 24, and the node 23 and the node 24, respectively. If it determines using the collision determination method mentioned above, it will determine with the node 21 and the node 22, the node 23, and the node 24 having collided. When the collision determination unit 23 performs the collision determination in the first layer, the collision determination is performed for all combinations of the child nodes, and two objects that collide with each other are identified as a result of the collision determination in the first layer. .
  • the collision determination process in each layer by the collision determination unit 23 determines the collision based on the position information associated with each of the two nodes, it can be associated with the node regardless of which node is selected.
  • the same algorithm processing is performed in which a collision is determined based on the obtained position information. Therefore, it is possible to process each combination of two nodes that perform collision determination in each layer in parallel.
  • the physical quantity calculation process of the object is realized by an object pair information acquisition unit 31, a rearrangement unit 32, a specification unit 33, an allocation unit 34, and a calculation unit 35 illustrated in FIG.
  • the physical quantity to be given to each object in order to satisfy the constraint condition is calculated by solving the constraint condition of the two objects in contact with each other.
  • object pair 1 object A, object B
  • object pair 2 object A, object C
  • both object pairs include the object A in common
  • the calculations for the respective object pairs depend on each other and are difficult to process in parallel. Therefore, a plurality of object pairs that are in contact with each other are grouped into a plurality of stages in which processing is executed at different timings. Each stage has a plurality of threads that can be processed in parallel, and an object pair is assigned to each thread, whereby each object pair can be processed in parallel. Then, at the timing at which each stage is processed, calculations for object pairs assigned to the stage are executed in parallel. Details will be described below.
  • the object pair information acquisition unit 31 sequentially acquires information on object pairs having two objects in contact with each other as constituent elements.
  • the object pair information acquisition unit 31 acquires two objects that the collision determination unit 23 determines to collide as two objects that are in contact with each other.
  • an object pair composed of two objects in contact with each other from which the object pair information acquisition unit 31 acquires information is referred to as an acquisition object pair.
  • the object pair information may be an identifier or attribute information of each object.
  • the allocating unit 34 assigns each of the plurality of acquired object pairs acquired by the object pair information acquiring unit 31 to a plurality of stages so that two or more acquired object pairs including common objects do not belong to the same stage. Assign to one.
  • FIG. 7 is a diagram illustrating an example of an acquired object pair and an object check table that manages allocation of acquired object pairs.
  • the object check table is held in the storage unit 12.
  • the object check table illustrated in FIG. 10 is obtained by associating, for each stage, an identifier for identifying each object and a flag indicating that the object identified by the identifier is subjected to calculation processing. . That is, when the flag is 1 at stage s (s ⁇ 0), this indicates that the object identified by the identifier is to be subjected to calculation processing at stage s, and when the flag is 0, the stage s indicates that the calculation process is not executed. In this object check table, all flags are 0 in the initial state.
  • the assigning unit 34 assigns these acquired object pairs in order from stage 0 of the object check table.
  • the allocation unit 34 acquires the first acquired object pair (object A, object B), it sets the flags of identifier A and identifier B corresponding to stage 0 to 1.
  • the flag of the identifier C corresponding to stage 0 is 0, but the flag of the identifier A is 1, so the acquisition object pair (object A) , Object C) cannot be calculated in thread 0.
  • the assigning unit 34 assigns the object pair (object A, object C) to stage 1. That is, the flags of identifier A and identifier C corresponding to stage 1 are set to 1. Since the assigning unit 34 can assign the next acquired object pair (object D, object E) to stage 0, the flags of identifier D and identifier E corresponding to stage 0 are set to 1. In this way, the flag is set for the acquired object pair. From this object check table, the timing for executing the processing of each acquired object pair can be known.
  • the calculation unit 35 calculates the influence on the position of each object due to the contact of two objects that are in contact with each other.
  • the calculation unit 35 calculates a physical quantity given to each object in order to satisfy the constraint condition by solving the constraint condition of the two objects in contact with each other.
  • the calculation unit 35 calculates the physical quantity given to each object by solving the constraint conditions of the acquired object pair in the order of the stage numbers assigned to the object check table created by the assigning unit 34 for the acquired object pair.
  • the calculation part 35 shall perform a calculation process in an order from the stage 0, as long as each stage is not calculated in parallel, an order will not be ask
  • the process for specifying the common object pair will be specifically described below. The process of specifying the common object is realized by the sorting unit 32 and the specifying unit 33.
  • the specifying unit 33 specifies one of two objects included in the acquired object pair as a reference object and the other as an accompanying object according to a predetermined reference. For example, based on the size of the identifiers of two objects included in the acquired object pair, an object with a small identifier is set as a reference object. Specifically, for the object pair (object A, object B), since the magnitude of the identifier is A ⁇ B, the object A is specified as the reference object and the object B is specified as the accompanying object. An object having a large identifier may be used as the reference object.
  • FIG. 8 shows an example of a determination target pair and a comparison target pair.
  • the determination target pair (A, B) and the comparison target pair (A, B) and (A, D) are connected by a line to correspond as the determination target pair and the comparison target pair. Indicates to do.
  • the comparison target pair is associated with the determination target pair.
  • the specifying unit 33 determines whether or not the accompanying objects are common between the determination target pair (A, B) and the comparison target pairs (A, B) and (A, D).
  • the determination target pair (A, B) is specified as a common object pair.
  • specification part 33 determines whether an accompanying object is common in each determination object pair (A, C) and comparison object pairs (A, B) and (A, D), all will be determination object. Since the accompanying objects differ between the pair and the comparison target pair, the determination target pair (A, C) is specified as a new object pair.
  • the specifying unit 33 specifies the reference object and the accompanying object among the acquired object pairs, and compares the determination target pair and the comparison target pair with which the reference object is common, thereby determining each of the determination target pairs.
  • the number of comparison target pairs to be compared can be narrowed down.
  • the process of determining whether or not the accompanying object is common between the determination target pair and the comparison target pair performed by the specifying unit 33 is to extract a comparison target pair having the same reference object regardless of which determination target pair is selected. It can be executed by a similar algorithm of comparing the accompanying objects. Therefore, the specifying unit 33 can execute in parallel the process of determining whether or not the accompanying object is common to the comparison target pair of each determination target pair.
  • the number of appearances is calculated for each identifier, it becomes A: 2, B: 1, C: 0, D: 1, E: 0, F: 1.
  • the object pair with the reference object identifier A is first to second (from the number of A), and the object pair with the reference object identifier B is third (A and
  • the object pair whose reference object identifier is F can be identified as fifth (from the sum of the numbers A to F and the number of F).
  • the determination target pair (A, B) is specified as a common object pair.
  • the determination target pair (A, D) is specified as a deleted object.
  • the rearrangement unit 32 rearranges the determination target pair and the comparison target pair in the order of the identifier, thereby facilitating the extraction process of the comparison target pair having the common determination target pair and the reference object. 33 can speed up the process of specifying the common object pair.
  • the assigning unit 34 assigns a new object pair to the object check table to which the common object pair has been assigned in the process S104 (S105).
  • the calculation unit 35 synthesizes the common object pair identified in step S102 and the new object pair to form a processing object pair. Then, the calculation unit 35 calculates the physical quantity to be given to each object by solving the constraint condition of the object pair in the order of the stage numbers assigned in the object check table created in process S105 for the process object pair (S106). ).
  • the object sleep management process is realized by an object pair information acquisition unit 31, a value assignment unit 41, a pointer overwrite unit 42, a route value overwrite unit 43, an object connection unit 44, and a pointer value update unit 45 shown in FIG. .
  • the simulation apparatus 1 assigns the same management ID to all objects included in a connected object configured by connecting a plurality of objects that are in contact with each other, so that the plurality of objects that are in contact with each other Are managed as one group.
  • the process of creating a connected object is mainly realized by the object pair information acquisition unit 31, the value assignment unit 41, the route value overwrite unit 42, and the pointer value overwrite unit 43.
  • the object connection unit 44 connects the acquired object pairs acquired by the object pair information acquisition unit 31 described above.
  • the object connecting unit 44 connects any of the three or more objects that are in contact with each other by giving a pointer value indicating the contact destination object to each object as a terminal object. Then, three or more objects connected by the object connecting unit 44 are connected objects.
  • the pointer value is the identifier of the contact object, and the pointer value of the terminal object is always its own identifier. That is, the pointer value of the end object does not indicate another object, and the connected objects are connected in one direction so that each object is directed to the end object.
  • FIG. 10 showing an example of a procedure for linking objects.
  • object A object A
  • object B object B
  • object C object C
  • each object is connected so that an object with a small identifier is a terminal object.
  • the value assigning unit 41 assigns a root value and a pointer value to each object.
  • the root value is a value for determining the direction indicated by the pointer value so that the object having a small identifier is the terminal object.
  • the pointer value is basically set to indicate an object having a small root value from an object having a large root value. Note that an object having a large identifier may be a terminal object. In this case, the pointer value is basically set so as to indicate an object having a large root value from an object having a small root value.
  • the initial state (step 0) is a state in which no object is connected.
  • the value assigning unit 41 assigns the root value and the initial value of the pointer value to each object. To do.
  • the initial value of the root value and pointer value assigned to each object is the identifier of each object.
  • the root value overwrite unit 43 When the acquired object pair (B, C) is acquired in step 1, the root value overwrite unit 43 has an object with a large root value (hereinafter referred to as a large root object) among the objects included in the acquired object pair. Is updated to the root value assigned to an object having a small root value (hereinafter, “root small object”). Then, the pointer value overwrite unit 42 updates the pointer value assigned to the large root object with the identifier of the small root object. That is, the root value and the pointer value given to the object C are B, and a pointer from the object C to the object B is indicated.
  • a large root object hereinafter referred to as a large root object
  • the pointer value overwrite unit 42 updates the pointer value assigned to the large root object with the identifier of the small root object. That is, the root value and the pointer value given to the object C are B, and a pointer from the object C to the object B is indicated.
  • the root value overwrite unit 43 assigns the root value assigned to the large root object (object C) to the small root object (object A). Update to the route value that has been set.
  • the pointer value overwriting unit 42 then updates the pointer value assigned to the large root object with the identifier of the small root object, as in step 1. That is, the route value and pointer value given to the object C are A.
  • the route value overwrite unit 43 assigns the route value assigned to the large root object (object B) to the small root object (object C). Update to the route value that has been set. Then, the pointer value overwrite unit 42 updates the pointer value assigned to the large root object with the identifier of the small root object. That is, the root value of object B is A, the pointer value is C, and a pointer from object B to object C is indicated.
  • step 5 when the acquired object pair (A, C) is acquired, the route values of the object A and the object C are compared.
  • the route value given to the object A is equal to the route value given to the object C.
  • the pointer value overwrite unit 42 updates the pointer value given to the object (object C) having a large identifier with the identifier of the object (object A) having a small identifier. . That is, the pointer value given to the object C is A, and a pointer from the object C to the object A is indicated.
  • step 5 is completed, the objects C and B are connected with the object A as the end.
  • the processing of each step may be executed in parallel.
  • the root value of object B is A
  • the pointer value is C, which is the same state as when step 5 ends.
  • each time the route value overwrite unit 43 updates the route value the updated route value is held, so that a linked object that ends with the object with the smallest identifier can be created. .
  • FIG. 11A is a diagram schematically illustrating an example of a connected object connected by the object connecting unit 44.
  • a connected object is composed of objects A to E, and object A is a terminal object.
  • the arrow points to the contact object indicated by the pointer value given to each object. That is, the pointer value of the object A in FIG. 11A is A, the pointer value of the object B is A, the pointer value of the object C is B, the pointer value of the object D is C, and the pointer value of the object E is D.
  • the pointer value update unit 45 updates the pointer value assigned to each object to the pointer value of the contact destination object indicated by the pointer value of each object.
  • the pointer value update unit 45 updates the pointer value of each object once
  • the pointer value of the object C is updated to the pointer value of the object B, and thus becomes A.
  • the pointer value of the object D is B, which is the pointer value of the object C
  • the pointer value of the object E is C, which is the pointer value of the object D.
  • FIG. 11B shows a diagram in which the pointer value of each object is updated for the connected object shown in FIG. 11A. As shown in FIG.
  • FIG. 11B shows a diagram in which the pointer value of each object is updated for the connected object shown in FIG. 11B.
  • the pointer value of the object D is A that is the pointer value of the object B
  • the pointer value of the object E is A that is the pointer value of the object C.
  • FIG. 12 is a diagram illustrating the transition of the pointer value of each object when the pointer value update unit 45 updates the pointer value of each object for the linked object illustrated in FIG. 11A.
  • the pointer values of all objects indicate the end object (object A) in the second update.
  • the pointer values of all objects can be made to indicate the end objects by the same processing.
  • the update processing by the pointer value update unit 45 can update the pointer values of all objects by log 2 R processing if the number of objects is R, from each object to the terminal object one by one. Processing is faster than tracing.
  • the pointer value update unit 45 can execute the process of updating the pointer value in parallel for each object constituting the connected object.

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Geometry (AREA)
  • Human Computer Interaction (AREA)
  • Computer Graphics (AREA)
  • Software Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Evolutionary Computation (AREA)
  • Computer Hardware Design (AREA)
  • Processing Or Creating Images (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

　並列処理に適した、オブジェクトの衝突判定を行うための仮想空間内のオブジェクトの位置を反映した二分木の構築方法を提供する。　複数の計算時点のそれぞれにおいて、当該計算時点における仮想空間内のオブジェクトの位置を示す位置情報をリーフに関連づけ、子ノードの位置情報を反映した位置情報を内部ノードに関連づけた完全二分木を作成する完全二分木作成部（２１）と、完全二分木における最下層より１つ上層から順に各層において、２ｎ（ｎ≧１）個のノード毎に、当該２ｎ個のノードに属する２・２ｎ個の子ノードそれぞれに関連付けられた位置情報に基づいて、当該２・２ｎ個の子ノードを入れ替えるノード入れ替え部（２２）と、を含み、衝突判定部（２３）が、ノード入れ替え部により入れ替えが行われた完全二分木を用いてオブジェクト同士の衝突判定を行う、シミュレーション装置である。

Description

シミュレーション装置
　本発明は、時間とともに仮想空間内を運動する複数のオブジェクトに関するシミュレーションを実行するシミュレーション装置、その制御方法、プログラム、情報記憶媒体に関する。
　仮想空間内に配置されている複数のオブジェクトの衝突判定を行うシミュレーションにおいて、２つのオブジェクトの仮想空間上の位置に基づいて衝突判定を行う。ここで、複数のオブジェクトを総当たりで衝突判定を行うことは、オブジェクト数が増加するほど計算量が膨大になり非効率である。そこで従来は、衝突判定の回数を減らすための手法の１つとして、仮想空間内の複数のオブジェクトの位置関係を反映する二分木を用いた衝突判定が行われている。オブジェクトの位置関係を反映した二分木を用いることで、仮想空間内の位置が離れているオブジェクト同士の衝突判定をスキップすることができる。
　この二分木の構築方法としては、例えば、全てのオブジェクトを含む領域をルートとし、当該領域を２分割した分割領域それぞれを子ノードとし、さらに分割領域それぞれを２分割した分割領域を孫ノードとする処理を、オブジェクトを１つだけ含む分割領域がリーフとなるまで再帰的に繰り返す方法がある。
　ここで、二分木の構築においてオブジェクト数の増加に伴う処理負荷を低減するため、二分木の構築を並列処理により実行することが望ましい。しかし、従来の二分木の構築方法では、各層の分割領域に含まれるオブジェクト数が異なるので並列処理を効率的に行えない場合がある。
　本発明の目的の一つは、並列処理に適した、オブジェクトの衝突判定を行うための仮想空間内のオブジェクトの位置を反映した二分木の構築方法を提供することにある。
　本発明に係るシミュレーション装置は、時間とともに仮想空間内を運動する複数のオブジェクトについて、複数の計算時点のそれぞれにおけるオブジェクト同士の衝突を判定するシミュレーション装置であって、前記複数の計算時点のそれぞれにおいて、当該計算時点における前記仮想空間内のオブジェクトの位置を示す位置情報をリーフに関連づけ、子ノードの前記位置情報を反映した位置情報を内部ノードに関連づけた完全二分木を作成する完全二分木作成部と、前記完全二分木における最下層より１つ上層から順に各層において、２ｎ（ｎ≧１）個のノード毎に、当該２ｎ個のノードに属する２・２ｎ個の子ノードそれぞれに関連付けられた前記位置情報に基づいて、当該２・２ｎ個の子ノードを入れ替えるノード入れ替え部と、を含み、前記ノード入れ替え部により入れ替えが行われた完全二分木を用いてオブジェクト同士の衝突判定が行われることを特徴とする。
　また、上述のシミュレーション装置において、前記オブジェクトの位置を示す位置情報は対応する前記オブジェクトを内接する領域であり、前記ノード入れ替え部は、前記２ｎ個のノードに属する２・２ｎ個の子ノードを、親ノードの前記領域が小さくなる組み合わせに入れ替える、こととしてもよい。
　また、上述のシミュレーション装置において、前記ノード入れ替え部は、前記２・２ｎ個の子ノードを入れ替えて得られる複数の組み合わせ候補のそれぞれについて、当該組み合わせ候補における親ノードの前記領域の大きさをランダムに変化させ、当該大きさを変化させた領域が小さな組み合わせ候補になるように、前記２ｎ個のノードに属する２・２ｎ個の子ノードを入れ替えることとしてもよい。
　また、上述のシミュレーション装置は、前記ノード入れ替え部により入れ替えが行われた前記完全二分木において、最上層から順に各層において、２個のノード毎に各ノードの前記領域に重なりが有るか否かを判断する判断部、をさらに含む、こととしてもよい。
　また、上述のシミュレーション装置において、前記判断部は、前の層において前記判断部により重なりが有ると判断された２個のノードに属する４個の子ノードすべての組み合わせにおいて、各ノードの前記領域に重なりが有るか否かをさらに判断する、こととしてもよい。
　また、上述のシミュレーション装置において、前記完全二分木作成部は、二回目以降の計算時点における衝突判定に用いる完全二分木を作成する場合に、前回の計算時点における衝突判定に用いた完全二分木におけるリーフとオブジェクトとの対応関係を用いて完全二分木を作成する、こととしてもよい。
　また、本発明に係るプログラムは、時間とともに仮想空間内を運動する複数のオブジェクトについて、複数の判定時点のそれぞれにおけるオブジェクト同士の衝突を判定するシミュレーション装置に、ある判定時点における前記仮想空間内のオブジェクトの位置を示す位置情報をリーフに関連づけ、子ノードの前記位置情報を反映した位置情報を内部ノードに関連づけた完全二分木を作成する完全二分木作成手段、及び、前記完全二分木における最下層より１つ上層から順に各層において、２ｎ（ｎ≧１）個のノード毎に、当該２ｎ個のノードに属する２・２ｎ個の子ノードそれぞれに関連付けられた前記位置情報に基づいて、当該２・２ｎ個の子ノードを入れ替えるノード入れ替え手段、として機能させるためのプログラムである。このプログラムは、コンピュータ読み取り可能な情報記憶媒体に格納されてよい。
　また、本発明に係るシミュレーション装置の制御方法は、時間とともに仮想空間内を運動する複数のオブジェクトについて、複数の判定時点のそれぞれにおけるオブジェクト同士の衝突を判定するシミュレーション装置を制御する制御方法であって、ある判定時点における前記仮想空間内のオブジェクトの位置を示す位置情報をリーフに関連づけ、子ノードの前記位置情報を反映した位置情報を内部ノードに関連づけた完全二分木を作成する完全二分木作成ステップと、前記完全二分木における最下層より１つ上層から順に各層において、２ｎ（ｎ≧１）個のノード毎に、当該２ｎ個のノードに属する２・２ｎ個の子ノードそれぞれに関連付けられた前記位置情報に基づいて、当該２・２ｎ個の子ノードを入れ替えるノード入れ替えステップと、を含むことを特徴とする。
本実施形態に係るシミュレーション装置１の構成の一例を示す図である。 本実施形態における、シミュレーション装置１が実行するシミュレーション処理の流れの一例を示す図である。 本実施形態に係るシミュレーション装置１により実行される主な機能の一例を示す機能ブロック図である。 完全二分木の一例を示す図である。 仮想空間内に配置される複数のオブジェクトの簡易モデルを示す図である。 完全二分木作成部２１が作成した完全二分木の一例を示す図である。 第２層についてのノード入れ替え処理が完了した後の完全二分木の一例を示す図である。 第３層についてのノード入れ替え処理が完了した後の完全二分木の一例を示す図である。 取得オブジェクトペアと、取得オブジェクトペアの割り当てを管理するオブジェクトチェックテーブルとの一例を示す図である。 判定対象ペアと比較対象ペアの一例を示す。 本実施形態に係る共通オブジェクトペアを用いたオブジェクトの物理量算出処理の流れの一例を示すフロー図である。 オブジェクトの連結手順の一例を示す図である。 オブジェクト連結部４４により連結された連結オブジェクトの一例を模式的に示す図である。 図１１Ａに示す連結オブジェクトについて各オブジェクトのポインタ値を更新した後の連結オブジェクトの一例を模式的に示す図である。 図１１Ｂに示す連結オブジェクトについて各オブジェクトのポインタ値を更新した後の連結オブジェクトの一例を模式的に示す図である。 図１１Ａに示す各オブジェクトのポインタ値の推移を示す図である。
　以下、本発明の実施の形態について、図面を参照しながら詳細に説明する。
　図１は、本実施形態に係るシミュレーション装置１の構成の一例を示す図である。本実施形態に係るシミュレーション装置１は、例えば、家庭用ゲーム機やパーソナルコンピュータ等であって、図１に示すように、制御部１１、記憶部１２、通信部１３、操作部１４、及び表示部１５を含んで構成されている。
　制御部１１は、ＣＰＵ５及びＧＰＵ６等を含んで構成され、記憶部１２に格納されているプログラムに従って各種の情報処理を実行する。本実施形態において、制御部１１が実行する処理の具体例については、後述する。
　記憶部１２は、ＲＡＭやＲＯＭ等のメモリ素子、ハードディスクドライブなどを含んで構成されており、制御部１１が実行するプログラムや、各種のデータを記憶する。また、記憶部１２は、制御部１１のワークメモリとしても動作する。
　通信部１３は、通信インタフェースであって、通信ネットワークを介して外部から到来するデータを受信し、制御部１１に対して出力する。また、制御部１１からの指示に従って、通信ネットワークを介して接続された他の情報処理装置に対して各種のデータを送信する。
　操作部１４は、キーボードやマウス、家庭用ゲーム機のコントローラ等であって、ユーザの操作入力を受け付けて、その内容を示す信号を制御部１１に出力する。
　表示部１５は、液晶ディスプレイ等の表示デバイスであって、制御部１１の指示に従って、各種の画像を表示する。
　なお、シミュレーション装置１は、ＤＶＤ－ＲＯＭやＢｌｕ－ｒａｙ（登録商標）ディスクなどの光ディスクを読み取り光ディスクドライブ、ＵＳＢ（Universal Serial Bus）ポートなどを含んでいてもよい。
　以下、本実施形態に係るシミュレーション装置１によって実現される機能の具体例について、説明する。本実施形態では、仮想空間内を運動する複数のオブジェクトについて、時間とともに変化するオブジェクトの位置を、物理シミュレーション等のシミュレーション処理によって計算する。本実施形態では、特に、オブジェクト同士の衝突による各オブジェクトの位置への影響を考慮したシミュレーション処理を実行する。このシミュレーション処理は、主に制御部１１のＧＰＵ６が実行することとするが、ＣＰＵ５、その他の装置が実行することとしてもよい。
　ＧＰＵ６は、ＣＰＵ５よりコア数が多く、同時に実行可能な処理単位（スレッド）の数も多いため、並列処理に適している。一方で、同時に実行されるスレッドは、互いに同じ内容の処理であることが要請される。そこで、ＧＰＵ６を用いてシミュレーション処理を効率的に実行するためには、従来と異なるアルゴリズムで処理を行う必要がある。
　なお、仮想空間内における時間の進行はタイムカウンタｔの値によって表されるものとし、所定の単位時間ｄごとにタイムカウンタｔの値を１だけ加算するとともにシミュレーション処理を実行する。すなわち、オブジェクトの位置を計算する対象となる各計算時点は、タイムカウンタｔ＝０、１、２、３、・・・で表される。また、各オブジェクトにはオブジェクトを識別するためにオブジェクトに固有に設定されるＩＤ情報（識別子）が関連付けられる。さらに各オブジェクトには、属性情報が関連付けられてもよい。属性情報としては、例えば、オブジェクトの種類を表す情報や、外形を規定する情報、その他、オブジェクトの種類に応じた種々の属性情報であってよい。
　ここで、本実施形態における、シミュレーション装置１が実行するシミュレーション処理の流れの一例を図２のフロー図を参照しながら説明する。この図２に示す処理は、タイムカウンタｔの値が加算されるごとに実行される。
　まず、仮想空間内に配置される複数のオブジェクトの少なくとも一部に物理量（速度、加速度など）が与えられる（Ｓ１）。これにより、仮想空間内に配置される複数のオブジェクトの位置が時間とともに変化する。
　次に、オブジェクトの位置を計算する計算時点において、オブジェクト同士の衝突が判定される（Ｓ２）。処理Ｓ２については、後に詳述する。
　そして、処理Ｓ１により互いに衝突していると判定された２つのオブジェクトの拘束条件が作成される（Ｓ３）。ここでは、例えば、互いに衝突していると判定された２つのオブジェクトは衝突点から進行方向にそれ以上位置が変化することのないよう、オブジェクトの動きを拘束する必要がある。そうしないと、衝突したオブジェクト同士がめりこむ、通過するなどの不具合が生じる。処理Ｓ３では、このようなオブジェクトの動きを拘束するための拘束条件が作成される。そして、拘束条件を解くことで、拘束条件を満たすために各オブジェクトに与える物理量が算出される（Ｓ４）。処理Ｓ４については、後に詳述する。
　このとき、仮想空間内を運動する複数のオブジェクトのなかには、その速度がほぼ０であるオブジェクトが存在する。このようなほぼ停止の状態にあるオブジェクトに対して、速度を０にしてスリープさせる（停止状態にする）というスリープ管理が行われる（Ｓ５）。スリープ管理により停止状態にあるオブジェクトが計算対象から除外されることで、計算の処理量が低減する。なお、スリープ管理により停止状態にあるオブジェクトに外力が与えられると、スリープ管理による停止状態が解除され計算対象に加えられる。処理Ｓ５については、後に詳述する。
　そして、各オブジェクトに与える物理量が仮想空間内の位置に反映される（Ｓ６）。つまり、各オブジェクトに与える物理量から、仮想空間の状態を描画するタイミングにおける各オブジェクトの位置が算出される。そしてシミュレーション装置１は、算出した位置にオブジェクトを配置した状態の仮想空間の様子を示す画像を描画して、表示部１５に対して出力する。これにより、単位時間ｄが経過するごとに、シミュレーション装置１が算出したその時点での位置に各オブジェクトが配置された仮想空間の画像が、表示部１５の画面に表示される。
　ここで、処理Ｓ２によるオブジェクトの衝突判定処理、処理Ｓ４によるオブジェクトの物理量算出処理、及び処理Ｓ５によるオブジェクトのスリープ管理処理について、以下に詳細に説明する。
　図３は、本実施形態に係るシミュレーション装置１により実行される主な機能の一例を示す機能ブロック図である。図３に示すように、本実施形態おいてシミュレーション装置１の制御部１１は、機能的には、例えば、完全二分木作成部２１、ノード入れ替え部２２、衝突判定部２３、オブジェクトペア情報取得部３１、並び替え部３２、特定部３３、割り当て部３４、計算部３５、値付与部４１、ポインタ値上書き部４３、ルート値上書き部４３、及びポインタ値更新部４５を含んで構成されている。これらの機能は、記憶部１２に記憶されたプログラムを制御部１１が実行することにより実現されている。このプログラムは、光ディスク、磁気ディスク、磁気テープ、光磁気ディスク、フラッシュメモリ等のコンピュータ可読な情報記憶媒体を介して、あるいは、インターネットなどの通信手段を介してシミュレーション装置１に供給される。
　まず、処理Ｓ２によるオブジェクトの衝突判定処理について説明する。オブジェクトの衝突判定処理は、図３に示す、完全二分木作成部２１、ノード入れ替え部２２、及び衝突判定部２３、によって実現される。
　完全二分木作成部２１は、仮想空間内に配置されている複数のオブジェクトそれぞれの仮想空間内の位置を示す位置情報をリーフに関連付け、子ノードの位置情報を反映した位置情報を内部ノードに関連付けた完全二分木を作成する。
　オブジェクトの仮想空間内の位置を示す位置情報は、オブジェクトに関連付けられている属性情報（例えば、外形を規定する情報）と、仮想空間の座標情報と、に基づいて仮想空間内の各オブジェクトの位置関係を示せるものであってよい。例えば、位置情報として、オブジェクトを内包する、いわゆる境界ボリューム（Boundary Volume）を用いる。この境界ボリュームは、仮想空間内においてオブジェクトを内接する領域の位置と大きさを単純化して示したものである。境界ボリュームはオブジェクトの形状を単純化したものであるため、オブジェクトの詳細モデルに対して衝突判定を行うより、境界ボリュームに対して衝突判定を行う方が高速に処理することができる。境界ボリュームには、例えば、球体（SPHERE）、各軸（ｘ、ｙ、ｚ軸）に並行な辺を有する直方体である軸平行境界ボックス（Axis-Aligned Bounding Box;AABB）等が用いられる。境界ボリュームが球体の場合は、球体の中心座標と半径とを位置情報とする。境界ボリュームが軸並行境界ボックスの場合は、軸並行境界ボックスの頂点のうち、各軸の座標値が最小となる最小点と、各軸の座標値が最大となる最大点と、の座標値を位置情報とする。また、境界ボリュームが軸並行境界ボックスの場合に、軸並行境界ボックスの中心座標と、中心から互いに直交する３面それぞれまでの距離と、を位置情報としてもよい。つまり、位置情報により、オブジェクトの境界ボリュームの形状と仮想空間内の位置とが示せればよい。
　ここでは、位置情報として軸並行境界ボックスを用いた例を示す。完全二分木作成部２１は、仮想空間内に配置されている複数のオブジェクトそれぞれの軸並行境界ボックスの情報（最小点の座標値、及び最大点の座標値等）を位置情報としてリーフに関連付ける。このとき、完全二分木作成部２１は、各オブジェクトの位置情報を、各オブジェクトに関連付けられている識別子順にリーフに関連づけてもよいし、各オブジェクトの位置情報をランダムにリーフに関連づけてもよい。
　そして、完全二分木作成部２１は、２個のリーフを子ノードとする親ノードに、その２個の子ノードに関連付けられている２個の位置情報のそれぞれが示す境界ボリュームを内接する新たな境界ボリュームの情報を、位置情報として関連付ける。具体的には、親ノードの子ノードである２個のリーフに関連付けられている２個の位置情報が示す軸並行境界ボックスを内包する新たな軸並行境界ボックスの情報を、当該親ノードの位置情報として関連付ける。完全二分木作成部２１は、この処理を２個のリーフ毎に行い、それぞれの親ノードに位置情報を関連付ける。そして、完全二分木作成部２１は、位置情報を関連付けたノード２個を子ノードとする親ノードに、その２個のノードに関連付けられている２個の位置情報が示す軸並行境界ボックスを内包する新たな軸並行境界ボックスの情報を位置情報として関連付ける。完全二分木作成部２１は、この処理を２個のノード毎に行い、それぞれの親ノードに位置情報を関連付ける。このように、完全二分木作成部２１は、２個のノード毎に親ノードに位置情報を関連付けていく処理をルートまで実行することで、すべてのノードに位置情報を関連付けた完全二分木を作成する。
　図４に例示する完全二分木を用いて、完全二分木作成部２１が実行する処理を具体的に説明する。図４に示すように、完全二分木は、リーフを第１層として順に第２層、第３層、第４層を構成し、第４層をルートとする。そして、便宜上、第１層の各リーフは左からリーフ１１～リーフ１８、第２層の各ノードは左からノード２１～ノード２４、第３層の各ノードは左からノード３１、ノード３２、として各リーフ及び各ノードの階層と位置を識別することとする。ここで、例えば、仮想空間内にオブジェクトＡ～オブジェクトＨ（Ａ～Ｈを識別子とする）の８個のオブジェクトが配置されているとする。このとき、各オブジェクトの位置情報となる軸並行境界ボックスはＰＡ～ＰＨと記されることとする。この場合、完全二分木作成部２１は、各オブジェクトの位置情報ＰＡ～ＰＨを識別子順にそれぞれ、第１層のリーフ１１～リーフ１８に関連付ける。そして、完全二分木作成部２１は、リーフ１１に関連付けられている位置情報ＰＡの示す軸並行境界ボリュームと、リーフ１２に関連付けられている位置情報ＰＢが示す軸並行境界ボリュームと、を内包する新たな軸並行境界ボリュームをＰＡＢとして、ノード２１に関連付ける。同様にして、完全二分木作成部２１は、リーフ１３に関連付けられている位置情報ＰＣの示す軸並行境界ボリュームと、リーフ１４に関連付けられている位置情報が示す軸並行境界ボリュームＰＤと、を内包する新たな軸並行境界ボリュームをＰＣＤとして、ノード２２に関連付ける。そして、完全二分木作成部２１は、ノード２１に関連付けられている位置情報ＰＡＢの示す軸並行境界ボリュームと、ノード２２に関連付けられている位置情報ＰＣＤが示す軸並行境界ボリュームと、を内包する新たな軸並行境界ボリュームをＰＡＢＣＤとして、ノード３１に関連付ける。このように、完全二分木作成部２１が、２つの子ノードに関連付けられている位置情報が示す軸並行境界ボリュームを内包する新たな軸並行境界ボリュームを親ノードに関連付けていくと、ノード２３にＰＥＦ、ノード２４にＰＧＨ、ノード３２にＰＥＦＧＨが関連付けられることとなる。なお、ルートに関連付けられる位置情報は、仮想空間内に配置されるオブジェクトＡ～オブジェクトＨをすべて内包する軸並行境界ボリュームとなる。
　ノード入れ替え部２２は、完全二分木作成部２１が作成した完全二分木の最下層（リーフ層）より１つ上層から、２ｎ（ｎ≧１）個のノード毎に、２ｎ個のノードに属する２・２ｎ個の子ノードそれぞれに関連付けられた位置情報に基づいて、２・２ｎ個の子ノードを入れ替える。ここでは、ノード入れ替え部２２は、完全二分木作成部２１が作成した完全二分木のリーフに関連付けられている各オブジェクトの位置情報を、仮想空間内の位置関係を反映した形に入れ替える。
　図４に例示する完全二分木を用いて、ノード入れ替え部２２が実行する処理を具体的に説明する。例えば、ｎ＝１とすると、ノード入れ替え部２２は、完全二分木作成部２１が作成した完全二分木の第２層において、２個のノード毎（ノード２１及びノード２２、ノード２３及びノード２４）に、その子ノード（リーフ１１～リーフ１４、リーフ１５～リーフ１８）に関連付けられている４個の位置情報（ＰＡ～ＰＤ、ＰＥ～ＰＨ）に基づいて子ノードを入れ替える。ここで、ノード２１及びノード２２についての処理を説明するが、ノード２３及びノード２４についての処理も同時に実行されることとする。まず、ノード入れ替え部２２は、位置情報ＰＢ、ＰＣ、及びＰＤがそれぞれ示す軸並行境界ボックスのうち、位置情報ＰＡが示す軸並行境界ボックスとの位置関係が比較的近いものを選択する。例えば、ノード入れ替え部２２は、位置情報ＰＡ及び位置情報ＰＢ、位置情報ＰＡ及び位置情報ＰＣ、位置情報ＰＡ及び位置情報ＰＤ、それぞれについて２つの位置情報が示す軸並行境界ボックスを内包する新たな軸並行境界ボックスの体積（それぞれ、ＶＡＢ、ＶＡＣ、ＶＡＤとする）を求める。そして、この体積が小さいほど２つの位置情報が示す軸並行境界ボックスの位置が近いと判断される。ノード入れ替え部２２は、体積が最も小さくなる組み合わせがノード２１に属するよう位置情報ＰＡ～ＰＤを入れ替える。例えば、体積ＶＡＣが最も小さいと判断された場合は、ノード入れ替え部２２は、位置情報ＰＡ及び位置情報ＰＣがノード２１に属し、位置情報ＰＢと位置情報ＰＤがノード２２に属するよう、位置情報ＰＢと位置情報ＰＣとを入れ替える。そして、位置情報ＰＡ及び位置情報ＰＣがそれぞれ示す軸並行境界ボックスを内包する新たな軸並行境界ボックスが位置情報ＰＡＣとしてノード２１に関連づけられ、位置情報ＰＢ及び位置情報ＰＤがそれぞれ示す軸並行境界ボックスを内包する新たな軸並行境界ボックスが位置情報ＰＢＤとしてノード２２に関連づけられる。
　そして、第２層についてノードの入れ替えが完了すると、ノード入れ替え部２２は、第２層についてノードを入れ替えた完全二分木の第３層において、２個のノード（ノード３１及びノード３２）それぞれの子ノードについて上述した第２層における処理と同様の処理を実行する。図４に例示する完全二分木は第４層までであるが、さらに深い階層を有する完全二分木においては、このような処理が最上層（ルート）になるまで各層で実行される。なお、ノード入れ替え部２２による処理について、最下層より１つ上層から、最上層になるまで順に実行してもよいし、各層を任意の順に実行してもよい。
　図４に例示する完全二分木を用いて、ノード入れ替え部２２が実行する別の処理方法について説明する。例えば、ｎ＝１とすると、完全二分木作成部２１が作成した完全二分木の第２層において、ノード２１及びノード２２の子ノード（リーフ１１～リーフ１４）に関連付けられている４個の位置情報（ＰＡ～ＰＤ、ＰＥ～ＰＨ）に基づいて子ノードを入れ替える処理について説明する。まず、ノード２１及びノード２２に関連付けられる位置情報の組み合わせ候補としては、ＰＡＢ及びＰＣＤ、ＰＡＣ及びＰＢＤ、ＰＡＤ及びＰＢＣ、の３通りが考えられる。これら３通りの組み合わせ候補から仮想空間内の位置関係を反映した最適な組み合わせを選択することとする。そこで、ノード入れ替え部２２は、各組み合わせ候補において、ノード２１及びノード２２それぞれに関連付けられる位置情報が示す軸並行境界ボックスの体積の和を求める（それぞれ、ＶＡＢ＋ＶＣＤ、ＶＡＣ＋ＶＢＤ、ＶＡＤ＋ＶＢＣ、となる）。そして、ＶＡＢ＋ＶＣＤ、ＶＡＣ＋ＶＢＤ、ＶＡＤ＋ＶＢＣ、のうち最も値が小さくなる組み合わせが最適な組み合わせとして選択される。そして、ノード入れ替え部２２は、選択された最適な組み合わせとなるよう各ノードを入れ替える。例えば、ＶＡＣ＋ＶＢＤが最も小さい場合は、ノード入れ替え部２２は、位置情報ＰＡ及び位置情報ＰＣがノード２１に属し、位置情報ＰＢと位置情報ＰＤがノード２２に属するよう、位置情報ＰＢと位置情報ＰＣとを入れ替える。
　以上の説明では、ノード入れ替え部２２は、入れ替え対象となる複数の子ノードのそれぞれに関連付けられた軸並行境界ボックスの中から、位置関係が相対的に近い２つの軸並行境界ボックスの組み合わせを決定するために、組み合わせ候補となる２つの軸並行境界ボックスを内包する軸並行境界ボックスの体積を実際に算出し、体積が小さい軸並行境界ボックスに内包される２つの軸並行境界ボックスに関連付けられた２つの子ノードが同じ親ノードに属するように子ノードの入れ替えを行うこととした。しかしながらノード入れ替え部２２は、このような方法に限られず、各種の方法で位置関係が相対的に近い２つの軸並行境界ボックスの組み合わせを決定してもよい。例えばノード入れ替え部２２は、組み合わせ候補となる２つの軸並行境界ボックスを内包する軸並行境界ボックスの３辺の長さの総和や、対角線の長さ等の数値を判断基準として用いて、位置関係が相対的に近い２つの軸並行境界ボックスの組み合わせを決定してもよい。その場合も、判断基準として用いる数値が小さいほど、２つの軸並行境界ボックスを内包する軸並行境界ボックス自体の大きさが小さいと判断でき、２つの軸並行境界ボックスの位置が相対的に近いと判断できる。
　上述した、完全二分木作成部２１、ノード入れ替え部２２による処理を、簡易モデルを用いて実施した例を示す。図５に仮想空間内に配置される複数のオブジェクトの簡易モデルを示す。図５に示す簡易モデルは、格子状の二次元空間（ｘ－ｙ座標）に大きさの等しいオブジェクト（格子１つがオブジェクトを示すこととする）が配置されるものである。ここでは、二次元空間内にオブジェクトＡ～オブジェクトＨ（Ａ～Ｈを識別子とする）の８個のオブジェクトが配置されている。そして、位置情報となる軸並行境界ボックスも格子で表されることなり、例えばオブジェクトＡの位置情報ＰＡは、各軸の座標値が最小となる最小点の座標値（０、２）、及び各軸の座標値が最大となる最大点の座標値（１、３）で表される軸並行境界ボックスとする。この二次元空間内におけるオブジェクトＡ～オブジェクトＨの位置関係を反映した完全二分木を作成することを目的とする。
　まず、完全二分木作成部２１は、オブジェクトＡ～オブジェクトＨそれぞれの位置情報ＰＡ～ＰＨを識別子順にリーフ１１～リーフ１８に関連付け、図６Ａに示す完全二分木を作成する。次に、ノード入れ替え部２２は、第２層のノード２１及びノード２２について、位置情報ＰＡ及び位置情報ＰＢ、位置情報ＰＡ及び位置情報ＰＣ、位置情報ＰＡ及び位置情報ＰＤ、それぞれについて２つの位置情報が示す軸並行境界ボックスを内包する新たな軸並行境界ボックスの体積（簡易モデルにおいては面積に相当する）を求める。ここで、最小点座標（ｘｓ、ｙｓ）、最大点座標（ｘｌ、ｙｌ）とすると、面積ＶはＶ＝（ｘｌ－ｘｓ）（ｙｌ－ｙｓ）となる。まず、位置情報ＰＡ（最小点（０、２）、最大点（１、３））及び位置情報ＰＢ（最小点（５、４）、最大点（６、５））が示す軸並行境界ボックスを内包する新たな軸並行境界ボックスＰＡＢは、最小点（０、２）、最大点（６、５）で表される。そして、軸並行境界ボックスＰＡＢの面積はＶＡＢ＝１８となる。同様にして、位置情報ＰＡ（最小点（０、２）、最大点（０、３））及び位置情報ＰＣ（最小点（２、２）、最大点（３、３））が示す軸並行境界ボックスを内包する新たな軸並行境界ボックスＰＡＣは、最小点（０、２）、最大点（３、３）で表され、面積ＶＡＣ＝３となる。位置情報ＰＡ（最小点（０、２）、最大点（０、３））及び位置情報ＰＤ（最小点（２、４）、最大点（３、５））が示す軸並行境界ボックスを内包する新たな軸並行境界ボックスＰＡＤは、最小点（０、２）、最大点（３、５）で表され、面積ＶＡＤ＝９となる。以上より、新たな軸並行境界ボックスの面積はそれぞれ、ＶＡＢ＝１８、ＶＡＣ＝３、ＶＡＤ＝９となり、ＶＡＣが最も小さくなるので、位置情報ＰＡ及び位置情報ＰＣがノード２１に属するよう位置情報ＰＢと位置情報ＰＣとを入れ替える。そして、第２層のノード２３及びノード２４についても、位置情報ＰＥ及び位置情報ＰＦ、位置情報ＰＥ及び位置情報ＰＧ、位置情報ＰＥ及び位置情報ＰＨ、それぞれについて２つの位置情報が示す軸並行境界ボックスを内包する新たな軸並行境界ボックスの面積ＶＥＦ、ＶＥＧ、ＶＥＨを求めると、ＶＥＦ＝１５、ＶＥＧ＝４２、ＶＥＨ＝５となる。したがって、ＶＥＨが最も小さくなるので、ノード入れ替え部２２は、位置情報ＰＥ及び位置情報ＰＨがノード２３に属するよう位置情報ＰＦと位置情報ＰＨとを入れ替える。以上より、第２層についてのノード入れ替え処理が完了した後の完全二分木は図６Ｂとなる。
　次に、ノード入れ替え部２２は、図６Ｂの完全二分木を用いて第３層についてのノード入れ替え処理を実行する。第３層におけるノード３１及びノード３２について、位置情報ＰＡＣ及び位置情報ＰＢＤ、位置情報ＰＡＣ及び位置情報ＰＥＨ、位置情報ＰＡＣ及び位置情報ＰＧＦ、それぞれについて２つの位置情報が示す軸並行境界ボックスを内包する新たな軸並行境界ボックスの面積を求めると、ＶＡＣＢＤ＝１８、ＶＡＣＥＨ＝１５、ＶＡＣＧＦ＝３０となる。したがって、ＶＡＣＥＨが最も小さくなるので、ノード入れ替え部２２が、位置情報ＰＡＣ及び位置情報ＰＥＨがノード３１に属するよう位置情報ＰＢＤと位置情報ＰＥＨとを入れ替え、ノード入れ替え部２２による処理を終了する。以上より、第３層についてのノード入れ替え処理が完了した後の完全二分木は図６Ｃとなる。これにより、図６Ｃに示す仮想空間内のオブジェクトの位置関係が反映された完全二分木となる。
　さらに、タイムカウンタｔ＝ｎにおいて、完全二分木作成部２１、ノード入れ替え部２２により作成された完全二分木を用いて、タイムカウンタｔ＝ｎ＋１におけるノード入れ替え部２２による処理を実行することとしてもよい。具体的には、例えば、タイムカウンタｔ＝ｎにおいて図６Ｃに示す完全二分木が作成されたとする。そして、タイムカウンタｔ＝ｎ＋１において完全二分木作成部２１が完全二分木を作成する際に、タイムカウンタｔ＝ｎ＋１において仮想空間に配置されているオブジェクトの位置情報を、図６Ｃに示す完全二分木のリーフと同じ順に関連付ける。つまり、完全二分木作成部２１は、リーフの左から、位置情報ＰＡ、ＰＣ、ＰＥ、ＰＨ、ＰＢ、ＰＤ、ＰＧ、ＰＦをそれぞれ関連付ける。なお、タイムカウンタｔ＝ｎ＋１における完全二分木は、図６Ｃのｔ＝ｎにおける完全二分木とは位置情報の順が同じであり、位置情報の内容についてはタイムカウンタｔ＝ｎ＋１における仮想空間内の位置情報が反映されている。これは、タイムカウンタｔ＝ｎとタイムカウンタｔ＝ｎ＋１とにおいて各オブジェクトの位置が劇的に変化することが少ないことから、タイムカウンタｔ＝ｎ＋１においてタイムカウンタｔ＝ｎにおける各オブジェクトとリーフとの対応関係を引き継ぐことで、タイムカウンタを加算するにつれ徐々に完全二分木を最適な形にするものである。
　なお、完全二分木において、すべてのノードは必ず２つの子ノードを有するので、いずれの２ｎ個のノードを選択してもその子ノードの数は等しくなる。よって、ノード入れ替え部２２が行う、２ｎ個のノードの子ノードに関連付けられている位置情報に基づくノード入れ替え処理は、いずれの２ｎ個のノードを選択しても同様のアルゴリズムで実行できることとなる。したがって、ノード入れ替え部２２は、各層における２ｎ個のノードそれぞれについての、ノードの入れ替え処理を並列に実行することができる。
　また、上述したノード入れ替え部２２によるノードの入れ替え処理により完成した完全二分木が、仮想空間内のオブジェクトの位置関係を反映した最適な完全二分木にならない場合がある。これは、ノード入れ替え部２２が、仮想空間内のオブジェクトを２つのオブジェクト毎の組み合わせに分ける場合に、２つのオブジェクトの位置関係が最小となる組み合わせを求める、という最適化処理を行う際に局所解に陥ることに起因する。そこで、ノード入れ替え部２２が実行する、局所解に陥る可能性を低減するための処理について説明する。上述した通り、ノード入れ替え部２２は、入れ替え対象となる複数の子ノードのそれぞれに関連付けられた位置情報の中から、位置関係が相対的に近い２つの位置情報の組み合わせを決定している。ここで、ノード入れ替え部２２は、組み合わせ候補のそれぞれについて、当該組み合わせ候補における２つの子ノードの位置関係を定量的に示す数値を求め、その数値を増加する方向、又は減少する方向のいずれかにランダムに変化させる（すなわち、数値に対してノイズを加える）。そして、変化させた後の数値が小さくなる組み合わせ候補を採用し、その組み合わせ候補になるようにノードの入れ替え処理を実行する。具体例として、ノード入れ替え部２２は、２つの子ノードの位置関係を定量的に示す数値として、２つの子ノードに関連づけられた２つの位置情報のそれぞれが示す領域を内包する領域の大きさ（例えば、軸並行境界ボックスの体積等）を用いる。このように各組み合わせ候補について２つの子ノードの位置関係を定量的に示す値にランダムなノイズを加えて評価することで、大域的な最適解を求めることが可能となる。以下に、ノード入れ替え部２２による局所解に陥る可能性を低減する具体的な処理について、図４を用いて説明する。
　まず、図４に示す完全二分木の第２層において、ノード２１及びノード２２の子ノード（リーフ１１～リーフ１４）に関連付けられている４個の位置情報（ＰＡ～ＰＤ、ＰＥ～ＰＨ）に基づいて子ノードを入れ替える処理について説明する。まず、ノード２１及びノード２２に関連付けられる位置情報の組み合わせの候補としては、ＰＡＢ及びＰＣＤ、ＰＡＣ及びＰＢＤ、ＰＡＤ及びＰＢＣ、の３通りがある。これら３通りの組み合わせから仮想空間内の位置関係を反映した最適な組み合わせを選択することとする。そして、ノード入れ替え部２２は、各組み合わせの候補から、ノード２１及びノード２２それぞれに関連付けられる位置情報が示す軸並行境界ボックスの体積の和が最小になる組み合わせを選択する。ここで、ノード入れ替え部２２は、ノード２１及びノード２２それぞれに関連付けられる位置情報が示す軸並行境界ボックスの体積の和を求める際に、各ノードに関連付けられる位置情報が示す軸並行境界ボックスの体積（ＶＡＢ、ＶＣＤ、ＶＡＣ、ＶＢＤ、ＶＡＤ、ＶＢＣ）にノイズを加える。つまり、各組み合わせの候補において、ノード２１及びノード２２それぞれに関連付けられる位置情報が示す軸並行境界ボックスの体積の和は、（１＋α１）ＶＡＢ＋（１＋α２）ＶＣＤ、（１＋α３）ＶＡＣ＋（１＋α４）ＶＢＤ、（１＋α５）ＶＡＤ＋（１＋α６）ＶＢＣ、と求められる。ここで、αｍ（ｍ＝１～６）は０＜αｍ＜１の範囲でランダムに与えられることとする。また、αｍは、予め３種類の値が定められており、各組み合わせの候補にランダムに割り当てられることとしてもよい。そして、ノード入れ替え部２２は、各組み合わせの候補から、これらのノイズを加えた２つの位置情報が示す軸並行境界ボックスの体積の和が最小となる組み合わせを選択し、ノードを入れ替える。ノード入れ替え部２２が、２ノード毎にその子ノードを入れ替える際にこのような処理を実行することで、局所解に陥る可能性を低減し、最終的に仮想空間内のオブジェクトの位置関係を反映した最適な完全二分木が完成される。
　なお、上述の説明では、ノード入れ替え部２２は、各組み合わせ候補における２つの子ノードの位置関係を定量的に示す値として、２つの位置情報が示す２つの領域を内接する領域の大きさ、より具体的には２つの位置情報が示す軸並行境界ボックスを内包する軸並行境界ボックスの体積を用いているが、この例に限定されない。例えばノード入れ替え部２２は、組み合わせ候補となる２つの位置情報が示す軸並行境界ボックスの３辺の長さの総和や、対角線の長さ等の数値を２つの位置情報の位置関係を定量的に示す値として用いてもよい。その場合も、ノード入れ替え部２２は、２つの子ノードの位置関係を定量的に示す値として用いる数値をランダムに変化させ、当該変化させた数値に基づいてノードの入れ替え処理を実行する。
　衝突判定部２３は、ノード入れ替え部２２により入れ替えが完了した完全二分木を用いてオブジェクト同士の衝突判定を行うシミュレーション処理を実行する。衝突判定は、完全二分木の各ノードの子ノード同士について、それぞれ関連付けられている位置情報に基づいて行われる。衝突判定方法として、例えば、球体の境界ボリュームを用いた位置情報に基づく場合は、中心座標の距離が２つの半径の和より小さくなる場合に、球体の境界ボリューム同士が衝突していると判定する方法がある。また、軸並行境界ボックスを用いた位置情報に基づく場合は、最小点の座標値と、最大点の座標値とに基づいて各軸上で重なりがあるかを判定し、３つの軸上すべてで重なりが有ると判定された場合に、軸並行ボックス同士が衝突していると判定される。また、軸並行境界ボックスにおいて中心座標と、中心から互いに直交する３面それぞれまでの距離と、を位置情報としている場合は、各軸において中心座標の距離が２つの半径（中心から面までの距離）の和より小さくなるかが判定され、３つの軸すべてで小さいと判定された場合に、軸並行境界ボックス同士が衝突していると判定されてもよい。
　本実施形態における衝突判定部２３による衝突判定は、ノード入れ替え部２２によりノードが入れ替えられた完全二分木を用いて実行される。衝突判定部２３は、完全二分木のルートからリーフまで順に各層において２つのノード同士について、それぞれに関連付けられている位置情報に基づいて衝突判定を行う。そして、２つのノード同士について、それぞれに関連付けられている位置情報が示す軸並行境界ボックス同士が衝突していると判定された場合は、衝突判定部２３は、２つのノードの４つの子ノードについて全ての組み合わせにおける衝突判定を行う。そして、２つのノード同士について衝突していないと判定された場合は、衝突判定部２３は、２つのノードそれぞれの子ノード同士について衝突判定を行う。これは、２つのノード同士について衝突していると判定された場合は、その子ノード同士についても衝突していると判定される可能性があり、２つのノード同士について衝突していないと判定された場合は、その子ノード同士は衝突していないと判断できるという考えのもとに実行する処理である。ノードに関連付けられる位置情報は、そのノードに属するすべての下位ノードの位置情報を含むものなので、上位ノードに関連付けられる位置情報において衝突していないと判定されれば、下位ノードに関連づけられる位置情報においても衝突していないといえる。これによって、衝突判定部２３は、衝突しないオブジェクト同士の衝突判定をスキップすることが可能となる。
　ここで、衝突判定部２３により実行される具体的な処理について図５に示す簡易モデルを用いて説明する。衝突判定部２３は、ノード入れ替え部２２により入れ替えが完了した、図６Ｃに示す完全二分木の第３層から第１層まで順に各層において衝突判定を行う。まず、衝突判定部２３は、第３層のノード同士（ノード３１及びノード３２）について、ノード３１に関連付けられている位置情報ＰＡＣＥＨと、ノード３２に関連付けられている位置情報ＰＢＤＧＦと、に基づいて上述した衝突判定方法を用いてオブジェクト同士の衝突判定を行う。ここでは、位置情報ＰＡＣＥＨが示す軸並行境界ボックス（最小点（０、０）、最大点（３、５））と位置情報ＰＢＤＧＦＨが示す軸並行境界ボックス（最小点（２、２）、最大点（６、７））とで各軸において重なりが生じるかを判定すると、最小点（２、２）、最大点（３、５）の範囲で重なりが生じており、位置情報ＰＡＣＥＨが示す軸並行境界ボックスと位置情報ＰＢＤＧＦＨが示す軸並行境界ボックスとは衝突していると判定される。そして、ノード３１及びノード３２について衝突していると判定されたので、衝突判定部２３は、第２層における衝突判定の際に、その子ノードの全ての組み合わせについても衝突判定を行う。つまり、衝突判定部２３は、ノード２１及びノード２２、ノード２１及びノード２３、ノード２１及びノード２４、ノード２２及びノード２３、ノード２２及びノード２４、ノード２３及びノード２４についてそれぞれ衝突判定を行う。上述した衝突判定方法を用いて判定すると、ノード２１及びノード２２、ノード２３及びノード２４について衝突していると判定される。そして、衝突判定部２３は、第１層における衝突判定の際に、その子ノードの全ての組み合わせについても衝突判定を行い、第１層における衝突判定の結果、互いに衝突する２つのオブジェクトが特定される。
　以上のように、衝突判定部２３による各層における衝突判定処理は、２つのノードにそれぞれ関連づけられた位置情報に基づいて衝突の判定を行っているので、いずれのノードを選択してもノードに関連付けられた位置情報に基づいて衝突の判定を行うという、同じアルゴリズムの処理となる。よって、各層において衝突の判定を行う２つのノードの組み合わせそれぞれを並列に処理することができる。
　次に、処理Ｓ４によるオブジェクトの物理量算出処理について説明する。オブジェクトの物理量算出処理は、図３に示す、オブジェクトペア情報取得部３１、並び替え部３２、特定部３３、割り当て部３４、計算部３５、によって実現される。
　ここでは、互いに接触している２つのオブジェクトの拘束条件を解くことで、拘束条件を満たすために各オブジェクトに与えるべき物理量を算出する。しかし、互いに接触しているオブジェクトペアとして、例えば、オブジェクトペア１（オブジェクトＡ、オブジェクトＢ）と、オブジェクトペア２（オブジェクトＡ、オブジェクトＣ）とが、同時に存在する場合がある。この場合、両オブジェクトペアは共通してオブジェクトＡを含んでいるため、それぞれのオブジェクトペアについての計算は相互に依存するものとなり並列に処理することが難しい。そこで、互いに接触している複数のオブジェクトペアを、異なるタイミングで処理が実行される複数のステージにグループ分けする。なお、各ステージは並列処理可能な複数のスレッドを有し、オブジェクトペアが各スレッドに割り当てられることでオブジェクトペアそれぞれを並列に処理することが可能とする。そして、それぞれのステージが処理されるタイミングにおいて、そのステージに割り当てられたオブジェクトペアについての計算を並列に実行する。以下に、詳細を説明する。
　オブジェクトペア情報取得部３１は、互いに接触している２つのオブジェクトを構成要素とするオブジェクトペアの情報を順に取得する。オブジェクトペア情報取得部３１は、衝突判定部２３が衝突すると判定した２つのオブジェクトを互いに接触している２つのオブジェクトとして取得する。また、以下では、オブジェクトペア情報取得部３１が情報を取得する互いに接触している２つのオブジェクトからなるオブジェクトペアを取得オブジェクトペアと表記する。また、オブジェクトペアの情報は各オブジェクトの識別子、属性情報であってよい。
　割り当て部３４は、オブジェクトペア情報取得部３１が取得した複数個の取得オブジェクトペアのそれぞれを、互いに共通するオブジェクトを含んだ２以上の取得オブジェクトペアが同じステージに属さないように、複数のステージのいずれかに割り当てる。
　割り当て部３４が実行する処理を、図７を用いて具体的に説明する。図７は、取得オブジェクトペアと、取得オブジェクトペアの割り当てを管理するオブジェクトチェックテーブルとの一例を示す図である。オブジェクトチェックテーブルは、記憶部１２に保持されることとする。図１０に例示するオブジェクトチェックテーブルは、ステージごとに、各オブジェクトを識別する識別子と、その識別子によって識別されるオブジェクトが計算処理を実行されることを示すフラグと、を対応づけてなるものである。すなわち、ステージｓ（ｓ≧０）においてフラグが１の場合には、その識別子によって識別されるオブジェクトはステージｓで計算処理を実行されることを示しており、フラグが０の場合には、ステージｓで計算処理は実行されないことを示している。このオブジェクトチェックテーブルでは初期状態においてすべてのフラグが０となっている。
　まず、図７に例示するような複数の取得オブジェクトペアが存在するとする。割り当て部３４は、これらの取得オブジェクトペアを、オブジェクトチェックテーブルのステージ０から順に割り当てる。割り当て部３４は、最初の取得オブジェクトペア（オブジェクトＡ、オブジェクトＢ）を取得すると、ステージ０に対応する識別子Ａ、識別子Ｂのフラグを１に設定する。次に、取得オブジェクトペア（オブジェクトＡ、オブジェクトＣ）を取得すると、ステージ０に対応する識別子Ｃのフラグは０であるが、識別子Ａのフラグは１となっているため、取得オブジェクトペア（オブジェクトＡ、オブジェクトＣ）はスレッド０で計算することができない。そこで、次のステージ（ステージ１）に対応する識別子Ａ、識別子Ｃのフラグは０となっているため、割り当て部３４は、オブジェクトペア（オブジェクトＡ、オブジェクトＣ）をステージ１に割り当てることとする。つまり、ステージ１に対応する識別子Ａ、識別子Ｃのフラグが１に設定される。そして、割り当て部３４は、次の取得オブジェクトペア（オブジェクトＤ、オブジェクトＥ）を、ステージ０に割り当てることができるので、ステージ０に対応する識別子Ｄ、識別子Ｅのフラグが１に設定される。このようにして、取得オブジェクトペアについてフラグが設定される。このオブジェクトチェックテーブルにより、取得オブジェクトペアそれぞれの処理を実行するタイミングがわかる。
　計算部３５は、互いに接触している２つのオブジェクトの接触による各オブジェクトの位置への影響を計算する。計算部３５は、互いに接触している２つのオブジェクトの拘束条件を解くことで、拘束条件を満たすために各オブジェクトに与える物理量を算出する。本実施形態では、計算部３５は、取得オブジェクトペアについて、割り当て部３４が作成したオブジェクトチェックテーブルに割り当てられたステージ番号順に、取得オブジェクトペアの拘束条件を解くことで各オブジェクトに与える物理量を算出する。ここで、計算部３５は、ステージ０から順に計算処理を実行するものとするが、各ステージが並列に計算されなければ順序は問わない。
　ここで、仮想空間内を運動する複数のオブジェクトについて、時間とともに変化するオブジェクトの位置を計算する物理シミュレーション等において、例えば、タイムカウンタｔ＝０において互いに接触しているオブジェクトペアは、タイムカウンタｔ＝１においても互いに接触している場合が多い。そこで、タイムカウンタｔ＝ｎにおける複数個の取得オブジェクトペアのうち、タイムカウンタｔ＝ｎ－１におけるいずれかの取得オブジェクトペアと２つの構成要素が共通するオブジェクトペア（以下、共通オブジェクトペアとする）を特定する。そして、計算部３５がタイムカウンタｔ＝ｎにおける計算を実行する際に、共通オブジェクトペアの情報を用いることで計算の処理量が低減される。以下に共通オブジェクトペアを特定する処理について具体的に説明する。共通オブジェクトを特定する処理は、並び替え部３２、特定部３３により実現される。
　まず、特定部３３は、所定の基準により、取得オブジェクトペアに含まれる２つのオブジェクトのうちの一方を基準オブジェクトとして、他方を付随オブジェクトとして特定することとする。例えば、取得オブジェクトペアに含まれる２つのオブジェクトの識別子の大小に基づいて、識別子の小さいオブジェクトを基準オブジェクトとする。具体的に、オブジェクトペア（オブジェクトＡ、オブジェクトＢ）については識別子の大小はＡ＜Ｂとなるため、オブジェクトＡは基準オブジェクト、オブジェクトＢは付随オブジェクトとして特定される。また、識別子の大きいオブジェクトを基準オブジェクトとしてもよい。
　そして、特定部３３は、ｔ＝ｎにおける複数個の取得オブジェクトペアそれぞれを判定対象ペアとして、ｔ＝ｎ－１における複数個の取得オブジェクトペアのうち、基準オブジェクトが判定対象ペアと共通するオブジェクトペアを比較対象ペアとして抽出する。そして、特定部３３は、判定対象ペアと比較対象ペアとで付随オブジェクトが共通するか否かを判定し、付随オブジェクトが共通する場合に当該判定対象ペアを共通オブジェクトペアとして特定する。なお、特定部３３は、付随オブジェクトが共通しない場合は当該判定対象ペアを、ｔ＝ｎ－１においては存在せず、ｔ＝ｎにおいて出現した新規のオブジェクトペア（以下、新規オブジェクトペアとする）として特定する。図８に判定対象ペアと比較対象ペアの一例を示す。図８における、ｔ＝ｎにおける取得オブジェクトペアのうち（Ａ、Ｂ）を判定対象ペアとすると、ｔ＝ｎ－１における取得オブジェクトペアのうち、その基準オブジェクトがＡであるオブジェクトペアが比較対象ペアとなる。つまり、（Ａ、Ｂ）及び（Ａ、Ｄ）が比較対象ペアとなる。図８に示すように、判定対象ペア（Ａ、Ｂ）と、その比較対象ペアとなる（Ａ、Ｂ）及び（Ａ、Ｄ）を線で結ぶことで、判定対象ペア、比較対象ペアとして対応することを示す。その他のオブジェクトペアについても、判定対象ペアに対して比較対象ペアとなるものを対応づけている。そして、特定部３３は、判定対象ペア（Ａ、Ｂ）と、比較対象ペア（Ａ、Ｂ）及び（Ａ、Ｄ）とでそれぞれ付随オブジェクトが共通するか否かを判定する。ここでは、判定対象ペア（Ａ、Ｂ）及び比較対象ペア（Ａ、Ｂ）の両者とも付随オブジェクトがＢであるため、判定対象ペア（Ａ、Ｂ）は共通オブジェクトペアとして特定される。また、特定部３３が、判定対象ペア（Ａ、Ｃ）と、比較対象ペア（Ａ、Ｂ）及び（Ａ、Ｄ）とでそれぞれ付随オブジェクトが共通するか否かを判定すると、いずれも判定対象ペアと比較対象ペアとで付随オブジェクトが異なるため、判定対象ペア（Ａ、Ｃ）は新規オブジェクトペアとして特定される。
　このように、特定部３３が、取得オブジェクトペアのうち、基準オブジェクトと付随オブジェクトを特定し、基準オブジェクトが共通する判定対象ペアと比較対象ペアとの付随オブジェクトを比較することで、判定対象ペアそれぞれについて比較すべき比較対象ペアの数を絞り込める。また、特定部３３が行う判定対象ペアと比較対象ペアとで付随オブジェクトが共通するか否かを判定する処理は、いずれの判定対象ペアを選んでも基準オブジェクトが共通する比較対象ペアを抽出して付随オブジェクトを比較するという同様のアルゴリズムで実行することができることになる。よって、特定部３３は、判定対象ペアそれぞれの、比較対象ペアとで付随オブジェクトが共通するか否かを判定する処理を並列に実行することができる。
　ここで、並び替え部３２が、ｔ＝ｎ－１における複数個の取得オブジェクトペアを、公知のバケットソート処理を用いて、基準オブジェクトの識別子順に並び替えることとしてもよい。例えば、並び替え部３２が、図８に示すｔ＝ｎ－１における取得オブジェクトペアを並び替えると、基準オブジェクトは、Ａ、Ａ、Ｂ、Ｄ、Ｆの順となる。ここで、識別子毎にその出現個数を算出すると、Ａ：２個、Ｂ：１個、Ｃ：０個、Ｄ：１個、Ｅ：０個、Ｆ：１個となる。これにより、並び替えられた取得オブジェクトペアのうち、基準オブジェクトの識別子がＡのオブジェクトペアは１番目から２番目（Ａの個数から）、基準オブジェクトの識別子がＢのオブジェクトペアは３番目（ＡとＢの個数の和及びＢの個数から）、基準オブジェクトの識別子がＦのオブジェクトペアは５番目（Ａ～Ｆの個数の和及びＦの個数から）、と特定することが可能となる。このようにして、特定の識別子を有するオブジェクトペアは、その識別子までの各識別子の個数の和と、その識別子の個数と、によって特定される。よって、ｔ＝ｎ－１における取得オブジェクトペアを基準オブジェクトの識別子順に並び替えることによって、特定部３３は、判定対象ペアに対する比較対象ペアを容易に抽出することができる。なお、並び替え部３２は、ｔ＝ｎにおける複数個の取得オブジェクトペアを、公知のバケットソート処理を用いて、基準オブジェクトの識別子順に並び替えてもよい。
　また、特定部３３は、ｔ＝ｎ－１における複数個の取得オブジェクトペアそれぞれを判定対象ペアとして、ｔ＝ｎにおける複数個の取得オブジェクトペアのうち、基準オブジェクトが判定対象ペアと共通するオブジェクトペアを比較対象ペアとして抽出してもよい。そして、特定部３３は、判定対象ペアと比較対象ペアとで付随オブジェクトが共通するか否かを判定し、付随オブジェクトが共通する場合に、共通オブジェクトペアとして特定する。なお、特定部３３は、付随オブジェクトが共通しない場合は、ｔ＝ｎ－１においては存在しており、ｔ＝ｎにおいては存在しない、削除オブジェクトペアとして特定する。具体的には、特定部３３は、図８における、ｔ＝ｎ－１における判定対象ペア（Ａ、Ｂ）と、ｔ＝ｎにおける比較対象ペア（Ａ、Ｂ）及び（Ａ、Ｃ）とでそれぞれ付随オブジェクトが共通するか否かを判定する。ここでは、判定対象ペア（Ａ、Ｂ）及び比較対象ペア（Ａ、Ｂ）の両者とも付随オブジェクトがＢであるため、判定対象ペア（Ａ、Ｂ）は共通オブジェクトペアとして特定される。また、特定部３３が、判定対象ペア（Ａ、Ｄ）と、比較対象ペア（Ａ、Ｂ）及び（Ａ、Ｃ）とでそれぞれ付随オブジェクトが共通するか否かを判定すると、いずれも判定対象ペアと比較対象ペアとで付随オブジェクトが異なるため、判定対象ペア（Ａ、Ｄ）は削除オブジェクトとして特定される。
　このように、並び替え部３２が、判定対象ペア及び比較対象ペアを識別子順に並び替えることで、判定対象ペアと基準オブジェクトが共通する比較対象ペアの抽出処理を容易にすることができ、特定部３３が共通オブジェクトペアを特定する処理を高速化できる。
　ここで、共通オブジェクトペア特定処理により特定された共通オブジェクトペアを用いた、オブジェクトの物理量算出処理について、図９のフロー図を参照しながら説明する。
　オブジェクトペア情報取得部３１がタイムカウンタｔ＝ｎにおいて互いに接触しているオブジェクトペアの情報を取得する（Ｓ１０１）。
　特定部３３が、処理Ｓ１０１にてオブジェクトペア情報取得部３１が取得したｔ＝ｎにおける取得オブジェクトペアと、タイムカウンタｔ＝ｎ－１においてオブジェクトペア情報取得部３１が取得したオブジェクトペアとを比較することにより、共通オブジェクトペアと、新規オブジェクトペアと、を特定する（Ｓ１０２）。
　割り当て部３４は、記憶部１２に記憶されているタイムカウンタｔ＝ｎ－１におけるオブジェクトチェックテーブルを参照し、処理Ｓ１０２にて特定部３３が特定した共通オブジェクトペアが割り当てられているステージ番号を取得する（Ｓ１０３）。
　割り当て部３４は、タイムカウンタｔ＝ｎにおけるオブジェクトチェックテーブルに、共通オブジェクトペアを割り当てる（Ｓ１０４）。このとき、割り当て部３４は、処理Ｓ１０３にて取得した、タイムカウンタｔ＝ｎ－１におけるステージ番号に割り当てる。つまり、共通オブジェクトペアについては、タイムカウンタｔ＝ｎ－１におけるオブジェクトチェックテーブルと同じフラグ設定を行う。
　割り当て部３４は、処理Ｓ１０４にて共通オブジェクトペアを割り当てたオブジェクトチェックテーブルに新規オブジェクトペアを割り当てる（Ｓ１０５）。そして、作成されたオブジェクトチェックテーブルはタイムカウンタｔ＝ｎと関連付けて記憶部１２に保持される。
　計算部３５は、処理Ｓ１０２にて特定した共通オブジェクトペアと、新規オブジェクトペアと、を合成して処理オブジェクトペアとする。そして、計算部３５は、処理オブジェクトペアについて、処理Ｓ１０５にて作成されたオブジェクトチェックテーブルで割り当てられたステージ番号順に、オブジェクトペアの拘束条件を解くことで各オブジェクトに与えるべき物理量を算出する（Ｓ１０６）。
　物理シミュレーション等において、所定の時間間隔ｄの間でオブジェクトの位置が大きく変化することは少ないので、ｔ＝ｎ－１における取得オブジェクトペアとｔ＝ｎにおける取得オブジェクトペアとを比較すると、新規オブジェクトペアの数より共通オブジェクトペアの数の方が多くなる。このような処理量の多くなる共通オブジェクトペアの割り当てを簡易化することで、割り当て部３４の割り当て処理を高速化できる。
　次に、処理Ｓ５によるオブジェクトのスリープ管理処理について説明する。オブジェクトのスリープ管理処理は、図３に示す、オブジェクトペア情報取得部３１、値付与部４１、ポインタ上書き部４２、ルート値上書き部４３、オブジェクト連結部４４、及びポインタ値更新部４５によって実現される。
　スリープ管理を行う場合には、互いに接触している複数のオブジェクトを１つのグループとして管理し、同じグループに属する複数のオブジェクトを同時にスリープさせたり、同時にスリープから解除させたりする必要がある。そうでないと、例えば一部のオブジェクトのスリープが解除されたが接触する他のオブジェクトはスリープしたままだった場合などにおいて、オブジェクトがポッピングやジッタリングなどの不自然な挙動を示し、挙動の連続性を維持できなくなることがあるからである。具体的に、シミュレーション装置１は、互いに接触している複数のオブジェクトが連結して構成される連結オブジェクトに含まれるすべてのオブジェクトに等しい管理ＩＤを付与することで、互いに接触している複数のオブジェクトを１つのグループとして管理することとする。
　まず、オブジェクト連結部４４が、連結オブジェクトを作成する処理について説明する。連結オブジェクトを作成する処理は、主に、オブジェクトペア情報取得部３１、値付与部４１、ルート値上書き部４２、ポインタ値上書き部４３によって実現される。
　オブジェクト連結部４４は、前述したオブジェクトペア情報取得部３１が取得する取得オブジェクトペアを連結することとする。オブジェクト連結部４４は、互いに接触している３個以上のオブジェクトの何れかを終端オブジェクトとして、各オブジェクトに接触先オブジェクトを示すポインタ値を付与して各オブジェクトを連結する。そして、オブジェクト連結部４４が連結した３個以上のオブジェクトが連結オブジェクトとなる。また、ポインタ値は接触先オブジェクトの識別子とし、終端オブジェクトのポインタ値は必ず自身の識別子となる。つまり、終端オブジェクトのポインタ値が他のオブジェクトを示すことはなく、これにより連結オブジェクトは、各オブジェクトが終端オブジェクトに向かうよう一方向に連結されるものとなる。
　ここで、連結オブジェクトを作成する処理について、オブジェクトの連結手順の一例を示した図１０を用いて説明する。例えば、仮想空間内にオブジェクトＡ、オブジェクトＢ、及びオブジェクトＣの３個のオブジェクトが存在するとする。これらのオブジェクトは、タイムカウンタｔ＝ｎにおいて取得オブジェクトペア（Ａ、Ｃ）及び（Ｂ、Ｃ）としてオブジェクトペア情報取得部３４によって取得される。このような、タイムカウンタｔ＝ｎにおいて互いに接触している３個のオブジェクトを連結することとする。
　連結オブジェクトを作成するための前提として、ここでは、識別子の小さいオブジェクトを終端オブジェクトとするよう各オブジェクトを連結することとする。そのために、まず、値付与部４１が各オブジェクトにルート値とポインタ値とを付与する。ルート値は、識別子の小さいオブジェクトを終端オブジェクトとするようポインタ値の示す方向を決定するための値である。そして、ポインタ値は、基本的にはルート値の大きいオブジェクトからルート値の小さいオブジェクトを示すよう設定されることとする。なお、識別子の大きいオブジェクトを終端オブジェクトとしてもよい。その場合は、ポインタ値は基本的にはルート値の小さいオブジェクトからルート値の大きいオブジェクトを示すよう設定される。
　図１０に示すように、初期状態（ステップ０）は、いずれのオブジェクトも連結していない状態とし、ここで、値付与部４１が各オブジェクトにルート値及びポインタ値の初期値を付与することとする。各オブジェクトに付与するルート値及びポインタ値の初期値は各オブジェクトの識別子とする。
　ステップ１にて、取得オブジェクトペア（Ｂ、Ｃ）が取得されると、ルート値上書き部４３が、取得オブジェクトペアに含まれるオブジェクトのうちそのルート値が大きいオブジェクト（以下、ルート大オブジェクトとする）に付与されているルート値を、ルート値が小さいオブジェクト（以下、ルート小オブジェクト）に付与されているルート値に更新する。そして、ポインタ値上書き部４２が、ルート大オブジェクトに付与されているポインタ値を、ルート小オブジェクトの識別子に更新する。つまり、オブジェクトＣに付与されるルート値及びポインタ値がＢとなり、オブジェクトＣからオブジェクトＢへのポインタが示される。
　ステップ２にて、取得オブジェクトペア（Ａ、Ｃ）が取得されると、ルート値上書き部４３が、ルート大オブジェクト（オブジェクトＣ）に付与されているルート値をルート小オブジェクト（オブジェクトＡ）に付与されているルート値に更新する。そして、ポインタ値上書き部４２が、ステップ１と同様に、ルート大オブジェクトに付与されているポインタ値をルート小オブジェクトの識別子に更新する。つまり、オブジェクトＣに付与されるルート値及びポインタ値はＡとなる。
　ステップ３にて、タイムカウンタｔ＝ｎ＋１となると、各オブジェクトに付与されているポインタ値が初期化される。タイムカウンタｔ＝ｎ＋１となると、オブジェクトペア情報取得部３１がタイムカウンタｔ＝ｎ＋１における取得オブジェクトペアを取得するため、タイムカウンタｔ＝ｎにおける各オブジェクトのポインタ値は初期化されることになる。しかし、各オブジェクトに付与されているルート値はタイムカウンタｔ＝ｎの処理が終了した時点の値とする。
　ステップ４にて、取得オブジェクトペア（Ｂ、Ｃ）が取得されると、ルート値上書き部４３が、ルート大オブジェクト（オブジェクトＢ）に付与されるルート値を、ルート小オブジェクト（オブジェクトＣ）に付与されているルート値に更新する。そして、ポインタ値上書き部４２は、ルート大オブジェクトに付与されているポインタ値を、ルート小オブジェクトの識別子に更新する。つまり、オブジェクトＢのルート値がＡ、ポインタ値がＣとなり、オブジェクトＢからオブジェクトＣへのポインタが示される。
　ステップ５にて、取得オブジェクトペア（Ａ、Ｃ）が取得されると、オブジェクトＡ及びオブジェクトＣのルート値が比較される。ここで、オブジェクトＡに付与されるルート値とオブジェクトＣに付与されるルート値とは等しくなる。このような場合は、オブジェクトの識別子の比較により、ポインタ値上書き部４２が、識別子の大きいオブジェクト（オブジェクトＣ）に付与されているポインタ値を、識別子の小さいオブジェクト（オブジェクトＡ）の識別子に更新する。つまり、オブジェクトＣに付与されるポインタ値がＡとなり、オブジェクトＣからオブジェクトＡへのポインタが示される。そして、ステップ５が終了した時点で、オブジェクトＡを終端としてオブジェクトＣ、オブジェクトＢが連結されたこととなる。
　このように、オブジェクト連結部４４によるタイムカウンタｔ＝ｎにおける処理を終了した時点でのルート値を、タイムカウンタｔ＝ｎ＋１における処理の開始時のルート値に設定することで、一度の処理で連結オブジェクトを作成できない場合でも、タイムカウンタを加算するにつれ識別子の小さいオブジェクトを終端オブジェクトとして各オブジェクトを連結していくことができる。
　なお、上述の例では、タイムカウンタｔ＝ｎにおいて、取得オブジェクトペア（Ｂ、Ｃ）及び（Ａ、Ｃ）を１回ずつ処理することとした。この各ステップの処理は、並列に実行されてよい。さらにオブジェクト連結部４４は、以上説明した取得オブジェクトペア（Ｂ、Ｃ）及び（Ａ、Ｃ）についての処理を、タイムカウンタｔ＝ｎにおいて繰り返し実行することとしてもよい。その場合は、ステップ２の後、取得オブジェクトペア（Ｂ、Ｃ）が取得されると、オブジェクトＢのルート値がＡ、ポインタ値がＣとなり、ステップ５が終了した時点と同じ状態となる。いずれの場合でも、ルート値上書き部４３がルート値を更新する毎に更新されたルート値を保持することで最終的には、識別子の最も小さいオブジェクトを終端とする連結オブジェクトを作成することができる。
　図１１Ａは、オブジェクト連結部４４により連結された連結オブジェクトの一例を模式的に示す図である。図１１Ａに示すように、連結オブジェクトは、オブジェクトＡ～オブジェクトＥにより構成され、オブジェクトＡが終端オブジェクトとなる。そして、矢印は各オブジェクトに付与されるポインタ値の示す接触先オブジェクトを指している。つまり、図１１ＡのオブジェクトＡのポインタ値はＡ、オブジェクトＢのポインタ値はＡ、オブジェクトＣのポインタ値はＢ、オブジェクトＤのポインタ値はＣ、オブジェクトＥのポインタ値はＤ、である。
　ここで、図１１Ａに示すような連結オブジェクトを構成するすべてのオブジェクトに同じ管理ＩＤが付与されることで、これらのオブジェクトがグループ管理される。そこで、すべてのオブジェクトに同じ管理ＩＤが付与されるために、終端オブジェクトを連結オブジェクトの代表として、各オブジェクトがすべて終端オブジェクトを指すようにする。つまり、連結オブジェクトを構成する各オブジェクトのポインタ値がすべて終端オブジェクトの識別子となるようにする。そうすることで、すべてのオブジェクトに終端オブジェクトの識別子が付与され、当該終端オブジェクトの識別子を管理ＩＤとしてグループ管理を行うことができる。
　そこで、ポインタ値更新部４５が、各オブジェクトに付与されたポインタ値を、各オブジェクトのポインタ値が示す接触先オブジェクトのポインタ値に更新する。具体的に、図１１Ａに示す連結オブジェクトについて、ポインタ値更新部４５が各オブジェクトのポインタ値を１回更新すると、オブジェクトＣのポインタ値は、オブジェクトＢのポインタ値に更新されるので、Ａとなる。また、オブジェクトＤのポインタ値は、オブジェクトＣのポインタ値であるＢとなり、オブジェクトＥのポインタ値は、オブジェクトＤのポインタ値であるＣとなる。図１１Ｂに、図１１Ａに示す連結オブジェクトについて各オブジェクトのポインタ値を更新した図を示す。図１１Ｂに示すように、１回の更新ではすべてのオブジェクトのポインタ値が終端オブジェクトを示すようにはならない。そこで、図１１Ｂに示す連結オブジェクトについて、ポインタ値更新部４５が各オブジェクトのポインタ値を再度更新する。図１１Ｃに、図１１Ｂに示す連結オブジェクトについて各オブジェクトのポインタ値を更新した図を示す。図１１Ｃに示すように、オブジェクトＤのポインタ値は、オブジェクトＢのポインタ値であるＡとなり、オブジェクトＥのポインタ値はオブジェクトＣのポインタ値であるＡとなる。図１２は、図１１Ａに示す連結オブジェクトについて、ポインタ値更新部４５が各オブジェクトのポインタ値の更新を行った場合の各オブジェクトのポインタ値の推移を示す図である。図１２にも示されるように、２回目の更新で、すべてのオブジェクトのポインタ値が終端オブジェクト（オブジェクトＡ）を示すものとなる。
　ここでは、オブジェクトが５個の場合を例示しているが、オブジェクトの数が増加しても同様の処理によりすべてのオブジェクトのポインタ値が終端オブジェクトを示すようにすることができる。そして、ポインタ値更新部４５による更新処理は、オブジェクトの数がＲであればlog2Ｒ回の処理ですべてのオブジェクトのポインタ値を更新することが可能となり、各オブジェクトから１つずつ終端オブジェクトまで辿るより処理が高速になる。
　また、ポインタ値更新部４５による更新処理では、いずれのオブジェクトも、ポインタ値をポインタ値が示すオブジェクトのポインタ値に更新するという同様のアルゴリズムにより処理される。よって、ポインタ値更新部４５は、連結オブジェクトを構成するオブジェクトそれぞれについて、ポインタ値を更新する処理を並列に実行できる。

Claims (9)

  1. 　時間とともに仮想空間内を運動する複数のオブジェクトについて、複数の計算時点のそれぞれにおけるオブジェクト同士の衝突を判定するシミュレーション装置であって、
    　前記複数の計算時点のそれぞれにおいて、当該計算時点における前記仮想空間内のオブジェクトの位置を示す位置情報をリーフに関連づけ、子ノードの前記位置情報を反映した位置情報を内部ノードに関連づけた完全二分木を作成する完全二分木作成部と、
    　前記完全二分木における最下層より１つ上層から順に各層において、２ｎ（ｎ≧１）個のノード毎に、当該２ｎ個のノードに属する２・２ｎ個の子ノードそれぞれに関連付けられた前記位置情報に基づいて、当該２・２ｎ個の子ノードを入れ替えるノード入れ替え部と、を含み、
    　前記ノード入れ替え部により入れ替えが行われた完全二分木を用いてオブジェクト同士の衝突判定が行われる
    　ことを特徴とするシミュレーション装置。
  2. 　前記オブジェクトの位置を示す位置情報は対応する前記オブジェクトを内接する領域であり、
    　前記ノード入れ替え部は、前記２ｎ個のノードに属する２・２ｎ個の子ノードを、親ノードの前記領域が小さくなる組み合わせに入れ替える、
    　ことを特徴とする請求項１に記載のシミュレーション装置。
  3. [規則91に基づく訂正 16.10.2014]　
    　前記ノード入れ替え部は、前記２・２ｎ個の子ノードを入れ替えて得られる複数の組み合わせ候補のそれぞれについて、当該組み合わせ候補における親ノードの前記領域の大きさをランダムに変化させ、当該大きさを変化させた領域が小さな組み合わせ候補になるように、前記２ｎ個のノードに属する２・２ｎ個の子ノードを入れ替える
    　ことを特徴とする請求項２に記載のシミュレーション装置。
  4. 　前記ノード入れ替え部により入れ替えが行われた前記完全二分木において、
    　最上層から順に各層において、２個のノード毎に各ノードの前記領域に重なりが有るか否かを判断する判断部、をさらに含む、
    　ことを特徴とする請求項２または３に記載のシミュレーション装置。
  5. [規則91に基づく訂正 16.10.2014]　
    　前記判断部は、
    　前の層において前記判断部により重なりが有ると判断された２個のノードに属する４個の子ノードすべての組み合わせにおいて、各ノードの前記領域に重なりが有るか否かをさらに判断する、
    　ことを特徴とする請求項４に記載のシミュレーション装置。
  6. 　前記完全二分木作成部は、二回目以降の計算時点における衝突判定に用いる完全二分木を作成する場合に、前回の計算時点における衝突判定に用いた完全二分木におけるリーフとオブジェクトとの対応関係を用いて完全二分木を作成する、
    　ことを特徴とする請求項１に記載のシミュレーション装置。
  7. 　時間とともに仮想空間内を運動する複数のオブジェクトについて、複数の判定時点のそれぞれにおけるオブジェクト同士の衝突を判定するシミュレーション装置を制御する制御方法であって、
    　ある判定時点における前記仮想空間内のオブジェクトの位置を示す位置情報をリーフに関連づけ、子ノードの前記位置情報を反映した位置情報を内部ノードに関連づけた完全二分木を作成する完全二分木作成ステップと、
    　前記完全二分木における最下層より１つ上層から順に各層において、２ｎ（ｎ≧１）個のノード毎に、当該２ｎ個のノードに属する２・２ｎ個の子ノードそれぞれに関連付けられた前記位置情報に基づいて、当該２・２ｎ個の子ノードを入れ替えるノード入れ替えステップと、
    　を含むことを特徴とする制御方法。
  8. 　時間とともに仮想空間内を運動する複数のオブジェクトについて、複数の判定時点のそれぞれにおけるオブジェクト同士の衝突を判定するシミュレーション装置を、
    　ある判定時点における前記仮想空間内のオブジェクトの位置を示す位置情報をリーフに関連づけ、子ノードの前記位置情報を反映した位置情報を内部ノードに関連づけた完全二分木を作成する完全二分木作成手段、及び、
    　前記完全二分木における最下層より１つ上層から順に各層において、２ｎ（ｎ≧１）個のノード毎に、当該２ｎ個のノードに属する２・２ｎ個の子ノードそれぞれに関連付けられた前記位置情報に基づいて、当該２・２ｎ個の子ノードを入れ替えるノード入れ替え手段、
    　として機能させるためのプログラム。
  9. [規則91に基づく訂正 16.10.2014]　
    　請求項８に記載されたプログラムを格納したコンピュータ読み取り可能な情報記憶媒体。
PCT/JP2014/061689 2013-12-18 2014-04-25 シミュレーション装置 Ceased WO2015093073A1 (ja)

Priority Applications (4)

Application Number Priority Date Filing Date Title
CN201480067196.4A CN105874511B (zh) 2013-12-18 2014-04-25 模拟设备
JP2015553386A JP5967786B2 (ja) 2013-12-18 2014-04-25 シミュレーション装置
US15/101,490 US10824775B2 (en) 2013-12-18 2014-04-25 Simulation method and device for determining collision between objects
EP14871365.4A EP3086293B1 (en) 2013-12-18 2014-04-25 Simulation device

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2013261857 2013-12-18
JP2013-261857 2013-12-18

Publications (1)

Publication Number Publication Date
WO2015093073A1 true WO2015093073A1 (ja) 2015-06-25

Family

ID=53402434

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2014/061689 Ceased WO2015093073A1 (ja) 2013-12-18 2014-04-25 シミュレーション装置

Country Status (5)

Country Link
US (1) US10824775B2 (ja)
EP (1) EP3086293B1 (ja)
JP (1) JP5967786B2 (ja)
CN (1) CN105874511B (ja)
WO (1) WO2015093073A1 (ja)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2021149943A (ja) * 2020-03-15 2021-09-27 インテル コーポレイション レイトラバーサルハードウェアにおいてボックスクエリを実行するための装置及び方法
CN113713381A (zh) * 2021-09-09 2021-11-30 腾讯科技（深圳）有限公司 对象管理方法、装置、设备、存储介质及系统
JP2023172497A (ja) * 2022-05-24 2023-12-06 株式会社トヨタプロダクションエンジニアリング 情報処理装置、情報処理方法及び情報処理プログラム

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2015093073A1 (ja) * 2013-12-18 2015-06-25 株式会社ソニー・コンピュータエンタテインメント シミュレーション装置
PL3247138T3 (pl) * 2016-05-19 2019-07-31 Bunq B.V. Sposób i system inicjowania protokołu komunikacji
US11210816B1 (en) * 2018-08-28 2021-12-28 Apple Inc. Transitional effects in real-time rendering applications
CN112995283B (zh) * 2021-02-03 2023-03-14 杭州海康威视系统技术有限公司 一种对象关联方法、装置及电子设备

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0927046A (ja) * 1995-07-11 1997-01-28 Fujitsu Ltd 干渉チェック方法
JP2002269588A (ja) * 2001-03-12 2002-09-20 Sony Corp ３次元表示プログラム、３次元表示方法、３次元表示プログラム格納媒体および３次元表示装置

Family Cites Families (16)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5263124A (en) * 1991-02-27 1993-11-16 Neural Systems Corporation Method for producing a binary tree, pattern recognition and binary vector classification method using binary trees, and system for classifying binary vectors
US5613049A (en) 1994-10-26 1997-03-18 The Boeing Company Method for creating spatially balanced bounding volume hierarchies for use in a computer generated display of a complex structure
US8188997B2 (en) * 2000-06-19 2012-05-29 Mental Images Gmbh Accelerated ray tracing using shallow bounding volume hierarchies
US7499053B2 (en) * 2000-06-19 2009-03-03 Mental Images Gmbh Real-time precision ray tracing
US8497875B2 (en) 2009-01-21 2013-07-30 Siemens Product Lifecycle Management Software Inc. System, method, and computer program product for determining a translation vector
WO2010096490A1 (en) * 2009-02-17 2010-08-26 Disney Enterprises, Inc. Methods, systems and media for simulating contact scenarios
CN101593366A (zh) * 2009-06-24 2009-12-02 北京航空航天大学 一种基于平衡二叉树的大规模虚拟场景碰撞检测方法
JP2011053778A (ja) * 2009-08-31 2011-03-17 Namco Bandai Games Inc プログラム、データ生成システム、データ生成方法、情報記憶媒体およびデータ構造
CN102368280A (zh) 2011-10-21 2012-03-07 北京航空航天大学 一种面向虚拟装配的基于aabb-obb混合包围盒的碰撞检测方法
US9396512B2 (en) * 2012-03-09 2016-07-19 Nvidia Corporation Fully parallel construction of k-d trees, octrees, and quadtrees in a graphics processing unit
US20150134302A1 (en) * 2013-11-14 2015-05-14 Jatin Chhugani 3-dimensional digital garment creation from planar garment photographs
WO2015093073A1 (ja) * 2013-12-18 2015-06-25 株式会社ソニー・コンピュータエンタテインメント シミュレーション装置
JP2015118576A (ja) * 2013-12-18 2015-06-25 株式会社ソニー・コンピュータエンタテインメント シミュレーション装置
JP2015118575A (ja) * 2013-12-18 2015-06-25 株式会社ソニー・コンピュータエンタテインメント シミュレーション装置
US9576393B1 (en) * 2014-06-18 2017-02-21 Amazon Technologies, Inc. Dynamic rendering of soft shadows for interface elements
US10062354B2 (en) * 2014-10-10 2018-08-28 DimensionalMechanics, Inc. System and methods for creating virtual environments

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0927046A (ja) * 1995-07-11 1997-01-28 Fujitsu Ltd 干渉チェック方法
JP2002269588A (ja) * 2001-03-12 2002-09-20 Sony Corp ３次元表示プログラム、３次元表示方法、３次元表示プログラム格納媒体および３次元表示装置

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2021149943A (ja) * 2020-03-15 2021-09-27 インテル コーポレイション レイトラバーサルハードウェアにおいてボックスクエリを実行するための装置及び方法
JP7661037B2 (ja) 2020-03-15 2025-04-14 インテル コーポレイション レイトラバーサルハードウェアにおいてボックスクエリを実行するための装置及び方法
US12450833B2 (en) 2020-03-15 2025-10-21 Intel Corporation Apparatus and method for performing box queries in ray traversal hardware
CN113713381A (zh) * 2021-09-09 2021-11-30 腾讯科技（深圳）有限公司 对象管理方法、装置、设备、存储介质及系统
CN113713381B (zh) * 2021-09-09 2023-06-20 腾讯科技（深圳）有限公司 对象管理方法、装置、设备、存储介质及系统
JP2023172497A (ja) * 2022-05-24 2023-12-06 株式会社トヨタプロダクションエンジニアリング 情報処理装置、情報処理方法及び情報処理プログラム

Also Published As

Publication number Publication date
EP3086293A4 (en) 2017-06-07
CN105874511A (zh) 2016-08-17
US10824775B2 (en) 2020-11-03
EP3086293B1 (en) 2020-01-01
EP3086293A1 (en) 2016-10-26
CN105874511B (zh) 2019-04-05
JPWO2015093073A1 (ja) 2017-03-16
JP5967786B2 (ja) 2016-08-10
US20160378892A1 (en) 2016-12-29

Similar Documents

Publication Publication Date Title
JP5967786B2 (ja) シミュレーション装置
US10719973B2 (en) Asynchronous and concurrent ray tracing and rasterization rendering processes
CN107481311B (zh) 三维城市模型渲染方法及装置
CN105261066B (zh) 一种三维地理信息系统实时绘制多线程分配与控制方法
CN110990516B (zh) 地图数据的处理方法、装置和服务器
JP5566632B2 (ja) 情報処理装置、情報処理方法、およびプログラム
CN112352234A (zh) 用于处理并发属性图查询的系统
US20130265298A1 (en) Graphic processing method and apparatus
JP2010160591A (ja) 空間データ管理装置、空間データ管理方法、および、空間データ管理プログラム
CN113034338B (zh) 一种用于gpu的bvh构造方法、装置及存储介质
US12260494B2 (en) Spatial test of bounding volumes for rasterization
US9582247B1 (en) Preserving data correlation in asynchronous collaborative authoring systems
US9953116B2 (en) Methods and apparatus for simulating positions of a plurality of objects in a virtual space, controlling method, program and information storage medium
JP2014219870A (ja) トポロジー図の作成方法及び作成プログラム
CN119919278B (zh) 图形处理器、图形绘制方法、芯片及电子设备
US10089420B2 (en) Simulation apparatus, controlling method, program and information storage medium for the simulation apparatus
CN112988403B (zh) 具有保密功能的集成电路仿真多线程管理并行方法及装置
JP5171904B2 (ja) 分散処理システム及び分散処理方法
JP3617225B2 (ja) 描画処理装置
JP2019040419A (ja) 画像処理装置、及びプログラム
CN121243770A (zh) 区域定位方法、装置、电子设备、存储介质及程序产品
CN121437711A (zh) 光照渲染方法和装置、存储介质及电子设备
CN115438600A (zh) 一种基于gpu八叉树加速和sph算法的流体模拟方法
CN119809913A (zh) 图形处理器、图元输出方法、芯片、服务器及电子设备
CN121074267A (zh) 模型生成方法、装置、设备、介质及产品

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 14871365

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2015553386

Country of ref document: JP

Kind code of ref document: A

REEP Request for entry into the european phase

Ref document number: 2014871365

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 2014871365

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 15101490

Country of ref document: US

NENP Non-entry into the national phase

Ref country code: DE