JP7105993B2 - Collision detection device - Google Patents

Description

The present invention relates to a collision detection device for detecting collisions between objects.

In the design field, it is important to detect whether or not objects collide with each other in work such as assembly verification or workability examination in VR (Virtual Reality) space using CAD (Computer-Aided Design) data. In collision determination using CAD data, it is necessary to determine whether or not there is interference between all polygons forming the shape of an object. However, the shapes of objects used in the design field are very precise and the number of polygons is very large, so it is difficult to perform collision determination in real time. Therefore, it is necessary to specify portions that do not need to perform collision determination and reduce the amount of processing. Collision determination that has been used in recent years often involves two-step processing for speeding up.

In the first step, simple determination is performed to exclude objects that have no possibility of collision from being processed, thereby reducing the amount of processing in the second step. In the second step, detailed determination is performed to determine whether or not there is interference between objects that may collide.

As a two-step process, there is a method of selecting an object based on the user's recognition and perception, as disclosed in Patent Document 1, for example. However, in this method, objects are not selected in a range invisible to the user and in a range unconscious of the user.
On the other hand, when working in a VR space using CAD data, it is necessary to detect interference of objects that occur in a range invisible to the user and in a range unconscious of the user. Therefore, the above method is not suitable for collision detection in the above work.

JP 2005-71285 A

As described above, with the conventional method, it is difficult to automatically and accurately detect collisions between objects while reducing the amount of collision determination processing.

The present invention has been made to solve the above-mentioned problems, and it is possible to automatically and accurately detect collisions between objects while reducing the amount of collision determination processing compared to the conventional configuration. It is an object of the present invention to provide a collision detection device.

A collision detection device according to the present invention includes a creation unit that creates a boundary volume for each of a plurality of objects including at least one moving body; a first simple determination unit for detecting a bounding volume and specifying an object corresponding to the detected bounding volume; A second simple determination unit for detecting polygons interfering with the volume, a polygon to be processed that constitutes an object detected by the second simple determination unit, and a polygon to be processed that constitutes a moving object, and perform collision determination. and when all the vertex coordinates of one polygon are shared by other polygons, one of the polygons sharing the vertex coordinates is excluded from the processing target. and the second simple determination unit performs processing using polygons to be processed that form the object after processing by the exclusion unit .

According to the present invention, since it is configured as described above, it is possible to automatically and accurately detect the collision between objects while reducing the amount of processing for collision determination as compared with the conventional configuration.

1 is a diagram showing a configuration example of a collision detection device according to Embodiment 1; FIG. 4 is a flowchart showing an operation example of the collision detection device according to Embodiment 1; 4 is a diagram for explaining processing by an exclusion unit according to Embodiment 1; FIG. 4A and 4B are diagrams for explaining processing by the creation unit according to Embodiment 1. FIG. FIG. 4 is a diagram for explaining processing by a first simple determination unit according to Embodiment 1; FIG. FIG. 10 is a diagram for explaining processing by a second simple determination unit according to Embodiment 1; FIG. FIG. 10 is a diagram for explaining processing by a second simple determination unit according to Embodiment 1; FIG. FIG. 10 is a diagram for explaining processing by a second simple determination unit according to Embodiment 1; FIG. FIG. 10 is a diagram for explaining processing by a second simple determination unit according to Embodiment 1; FIG. 10A and 10B are diagrams illustrating hardware configuration examples of the collision detection device according to Embodiment 1. FIG.

BEST MODE FOR CARRYING OUT THE INVENTION Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
Embodiment 1.
FIG. 1 is a diagram showing a configuration example of a collision detection device 1 according to Embodiment 1. As shown in FIG.
A collision detection device 1 detects a collision between objects 5 . The object 5 includes one or more moving bodies 5a. Objects 5 include, for example, parts or assemblies. The collision detection device 1, as shown in FIG. A determination unit 106 is provided.

The storage unit 101 stores various data handled by the collision detection device 1 . The storage unit 101 stores in advance CAD data (three-dimensional data) indicating the shape of the object 5 to be subjected to collision detection. The collision detection device 1 can acquire information indicating the triangular polygons forming the object 5 and the vertex coordinates forming the polygons from the CAD data indicating the shape of the object 5 .

FIG. 1 shows a case where a storage unit 101 is provided inside the collision detection device 1 . However, without being limited to this, the storage unit 101 may be provided outside the collision detection device 1 .
The storage unit 101 includes, for example, non-volatile or volatile semiconductor memory such as RAM (Random Access Memory), ROM (Read Only Memory), flash memory, EPROM (Erasable Programmable ROM), EEPROM (Electrically EPROM), Magnetic discs, flexible discs, optical discs, compact discs, mini discs, DVDs (Digital Versatile Discs), and the like are applicable.

The excluding unit 102 excludes a part of the polygons forming the object 5 from the object to be processed for each object 5 to be subjected to collision detection. At this time, if the polygons forming the object 5 share all the vertex coordinates forming one polygon with other polygons, the exclusion unit 102 selects one of the polygons that share the vertex coordinates. It may be excluded from the processing target. Alternatively, the exclusion unit 102 may randomly exclude some of the polygons forming the object 5 from the processing targets.

Note that the exclusion unit 102 is not an essential component of the collision detection device 1 and may be removed from the collision detection device 1 .

The creation unit 103 creates a boundary volume 6 for each object 5 to be subjected to collision detection. The bounding volume 6 is, for example, an AABB (Axis-Aligned Bounding Box) or a sphere.

The simple determination unit 104 uses the boundary volume 6 created by the creation unit 103 to perform simple determination in the first step. At this time, the simple determination unit 104 first detects the bounding volume 6 that interferes with the bounding volume 6a of the moving body 5a. The simple determination unit 104 then identifies the object 5 corresponding to the detected bounding volume 6 .

The simple determination unit 105 performs simple determination in the second step based on the determination result of the simple determination unit 104 . At this time, the simple determination unit 105 detects polygons interfering with the boundary volume 6a of the moving body 5a among the polygons to be processed that constitute the object 5 specified by the simple determination unit 104. FIG. When the collision detection device 1 is provided with the exclusion unit 102, the simple determination unit 105 determines the boundary volume 6a of the moving object 5a among the polygons to be processed that constitute the object 5 after processing by the exclusion unit 102. Detect interfering polygons.
In addition, the simple determination unit 105 may detect polygons interfering with the boundary volume 6 of the object 5 specified by the simple determination unit 104, among the processing target polygons forming the moving body 5a. When the collision detection device 1 is provided with the exclusion unit 102, the simple determination unit 105 determines the polygons specified by the simple determination unit 104 among the polygons to be processed that constitute the moving body 5a after the processing by the exclusion unit 102. Detect polygons that interfere with the bounding volume 6 of the object 5 .

Further, the simple determination unit 105 may perform simple determination in the third step. At this time, the simple determination unit 105 excludes some of the polygons to be processed that constitute the moving body 5a from the processing targets based on the traveling direction of the moving body 5a.

Detailed determination section 106 performs detailed determination based on the determination result of simple determination section 105 . At this time, the detailed determination unit 106 performs collision determination based on the polygons to be processed forming the object 5 detected by the simple determination unit 105 and the polygons to be processed forming the moving body 5a.
Further, when the simple determination unit 105 has also detected the polygons to be processed that constitute the moving body 5a, the detailed determination unit 106 determines the polygons to be processed that constitute the object 5 detected by the simple determination unit 105 and Collision determination is performed based on the polygons to be processed that constitute the moving body 5a.

Next, an operation example of the collision detection device 1 according to Embodiment 1 shown in FIG. 1 will be described with reference to FIG.
The collision detection apparatus 1 according to Embodiment 1 detects polygons to be processed for detailed determination by two or more consecutive simple determinations, and performs collision determination between the detected polygons by detailed determination. Below, the case where the collision detection apparatus 1 performs three steps of simple determinations is shown.

In the operation example of the collision detection device 1 according to Embodiment 1 shown in FIG. 1, as shown in FIG. Some of the polygons are excluded from processing (step ST1).

At this time, as shown in FIG. 3, in the polygons forming the object 5, if all the vertex coordinates forming one polygon are shared by other polygons, the exclusion unit 102 One of the polygons to be processed may be excluded from the processing target. As a result, the collision detection device 1 according to Embodiment 1 can be used without changing and reducing the number of vertex coordinates forming polygons forming the object 5, that is, without changing the size and shape of the object 5. , the number of polygons to be processed can be reduced. In FIG. 3, the object 5 has a cubic shape, and the exclusion unit 102 excludes polygons in the hatched portion from the processing targets.
When collision determination is performed on a polygon-to-polygon basis, strictly speaking, the exclusion of polygons from the objects to be processed affects the accuracy. On the other hand, for safety reasons, most of the products distributed in the world are not considered to have sharp and long shapes that pass through the polygons excluded from processing, and are composed of continuous curved surfaces or flat surfaces. It is thought that Therefore, exclusion of polygons from processing targets by the exclusion unit 102 does not pose a substantial problem.

Alternatively, the exclusion unit 102 may randomly exclude some of the polygons forming the object 5 from the processing targets.
The shape of the object 5 indicated by CAD data is composed of many polygons. Therefore, even if polygons are randomly excluded from processing targets by the exclusion unit 102, the probability that adjacent polygons will be excluded from processing targets is considered to be low if the ratio is constant. Therefore, even with this, the collision detection apparatus 1 according to Embodiment 1 can adjust the size and shape of the object 5 without changing and reducing the number of vertex coordinates forming the polygons forming the object 5. The number of polygons to be processed can be reduced without changing.

Further, the creation unit 103 creates a boundary volume 6 for each object 5 to be subjected to collision detection (step ST2). 4A shows the case where a sphere is used as the bounding volume 6, and FIG. 4B shows the case where AABB is used as the bounding volume 6. FIG. The storage unit 101 associates the bounding volume 6 created by the creating unit 103 with the object 5 corresponding to the bounding volume 6 using a unique ID and stores them.

Next, the simple determination unit 104 uses the boundary volume 6 created by the creation unit 103 to perform the simple determination of the first step (step ST3). At this time, as shown in FIG. 5, the simple determination unit 104 first detects the bounding volume 6 that interferes with the bounding volume 6a of the moving body 5a. Then, the simple determination unit 104 identifies the object 5 corresponding to the detected boundary volume 6 . In FIG. 5, in a region 501, the boundary volume 6b of the stationary object 5b interferes with the boundary volume 6a of the moving object 5a.
Note that in FIG. 5, the polygons are represented by quadrilaterals instead of triangles in order to make the drawing easier to see. The same applies to FIGS.

Next, the simple determination section 105 performs the second step of simple determination based on the determination result of the simple determination section 104 (step ST4).
At this time, first, the simple determination unit 105 detects polygons interfering with the boundary volume 6a of the moving body 5a among the polygons to be processed that constitute the object 5 specified by the simple determination unit 104 . In FIG. 6, the stationary object 5b interferes with the boundary volume 6a of the moving object 5a in a region 601 portion. Here, the simple determination unit 105 detects polygons interfering with the boundary volume 6 of the object 5 specified by the simple determination unit 104, among the polygons to be processed that form the moving object 5a. In FIG. 7, the moving object 5a interferes with the boundary volume 6b of the stationary object 5b in a region 701 portion.
It should be noted that the simple determination processing of the second step by the simple determination unit 105 is extremely low-cost processing, and can be implemented even when there are many objects 5 .

By the simple determination of the second step by the simple determination unit 105, the collision detection device 1 according to the first embodiment can limit polygons to be processed in the object 5 for which detailed determination is required, and the processing amount in the detailed determination is can be reduced.

Next, the simple determination section 105 performs a simple determination of the third step (step ST5). At this time, the simple determination unit 105 excludes some of the polygons to be processed that constitute the moving body 5a from the processing targets based on the traveling direction of the moving body 5a.

As shown in FIG. 8, the collision of the moving object 5a with the stationary object 5b occurs only in the traveling direction of the moving object 5a. Therefore, the simple determination unit 105 may process only the polygons on the front side in the direction of travel that are likely to collide with each other, among the polygons to be processed that form the moving body 5a. Thereby, the collision detection device 1 according to Embodiment 1 can further reduce the amount of processing in the detailed determination.

As a specific processing method in this case, first, as shown in FIG. A motion vector is calculated from each position. The simple determination unit 105 then normalizes the normal vector and the calculated movement vector for each polygon. Then, the simple determination unit 105 calculates the inner product value of the normalized normal vector and the normalized movement vector for each polygon. For each polygon, if the calculated inner product value is equal to or greater than the threshold value and equal to or less than 1, the simple determination unit 105 determines that the polygon exists on the front side in the traveling direction and treats the polygon as a processing target. Note that the threshold is an arbitrary value of 0 or more and less than 1. On the other hand, if the value of the inner product calculated for each polygon is a negative value, the simple determination unit 105 determines that there is no possibility of collision because the polygon exists on a side other than the front side in the traveling direction. Exclude from coverage.
Since the object 5 has a shape closed by polygons, the object 5 always has a polygon facing the front side in the traveling direction.

In the above description, the simple determination unit 105 excludes some of the polygons to be processed that constitute the moving body 5a from the processing target based on the traveling direction of the moving body 5a. However, the present invention is not limited to this, and the simple determination unit 105 configures the object 5 specified by the simple determination unit 104 (the object 5 that may collide with the moving object 5a) based on the traveling direction of the moving object 5a. A part of the polygons to be processed may be excluded from being processed.
As a specific processing method in this case, first, the simple determination unit 105 calculates and normalizes the motion vector of the moving body 5a. The method of obtaining this normalized motion vector is the same as described above. Then, the simple determination unit 105 normalizes the normal vector for each polygon to be processed that constitutes the object 5 . Then, the simple determination unit 105 calculates the inner product value of the normalized normal vector and the normalized movement vector for each polygon. Then, if the calculated inner product value for each polygon is equal to or less than the threshold value and equal to or greater than -1, the simple determination unit 105 determines that the polygon exists on the front side facing the moving body 5a, and determines that the polygon is the object of processing. treated as Note that the threshold is an arbitrary value greater than -1 and less than or equal to 0. On the other hand, if the value of the inner product calculated for each polygon is positive, the simple determination unit 105 determines that there is no possibility of collision because the polygon exists outside the front facing the moving body 5a. to exclude from processing.

Further, the simple determination unit 105 excludes a part of the polygons to be processed that constitute the moving object 5a from the processing targets based on the traveling direction of the moving object 5a. Some of the polygons to be processed that constitute the identified object 5 may be excluded from being processed.

In this manner, the collision detection apparatus 1 according to Embodiment 1 gradually reduces polygons to be processed in detailed determination by performing simple determination in two or more steps by the simple determination unit 104 and the simple determination unit 105 . As a result, the collision detection device 1 according to Embodiment 1 significantly reduces the amount of processing in detailed determination even when there are many objects 5 existing in the space or when there are many polygons constituting the objects 5. can.

Next, detailed determination section 106 performs detailed determination based on the determination result of simple determination section 105 (step ST6). At this time, the detailed determination unit 106 performs collision determination based on the polygons to be processed forming the object 5 detected by the simple determination unit 105 and the polygons to be processed forming the moving body 5a. For example, the detailed determination unit 106 uses an arithmetic unit such as a GPU (Graphics Processing Unit) to perform round-robin determination of polygons to be processed in parallel, thereby determining the object 5 and its part that the moving object 5a interferes with. Identify. It should be noted that an existing technique can be used to determine the collision (interference determination) between polygons, and the detailed description of that process will be omitted.

Note that the collision detection device 1 may limit the frames on which the above process is performed. For example, the collision detection device 1 excludes frames in which the object 5 is not moving from the processing targets. Further, for example, the collision detection device 1 may set the interval between frames to be processed within a range that does not affect the user's perception even when the object 5 is moving. As a result, the collision detection device 1 can reduce the occupation rate of processing on the arithmetic processor. In actual use of VR, the arithmetic processor performs not only calculation processing for collision determination but also other processing. Therefore, by reducing the occupancy of the arithmetic processor by the calculation processing of collision determination, the capacity of the arithmetic processor can be allocated to other processing, which leads to an improvement in the overall perceived speed.

When the moving speed of the moving body 5a is slow, the collision detection device 1 performs collision detection in units of 0.1 second (in the case of an image of 60 frames/second), for example, if processing is performed once every 6 frames. can. Further, when the moving speed of the moving body 5a is high, considering that the positional relationship of the object 5 changes greatly in each frame, the collision detection device 1 performs processing once every three frames, for example, Collision detection can be performed in units of 0.05 seconds, enabling more detailed determination processing.

In the figure, the determination of collision between the moving object 5a and the stationary object 5b is taken as an example. However, not limited to this, the collision detection device 1 according to Embodiment 1 can also determine a collision between the moving bodies 5a. For example, the collision detection device 1 according to Embodiment 1 can also detect whether or not tools held in both hands of the operator collide with each other.

As described above, according to the first embodiment, the collision detection apparatus 1 includes the creating unit 103 that creates the boundary volumes 6 for each of the plurality of objects 5 including at least one moving object 5a, and the creating unit 103 A simple determination unit 104 that detects the bounding volume 6 that interferes with the bounding volume 6 of the moving body 5a using the bounding volume 6 created by and identifies the object 5 corresponding to the detected bounding volume 6; A simple determination unit 105 that detects polygons interfering with the boundary volume 6a of the moving object 5a from among the polygons to be processed that constitute the object 5 specified by 104, and the object 5 detected by the simple determination unit 105. A detailed determination unit 106 that performs collision determination based on the polygon to be processed and the polygon to be processed that constitutes the moving body 5a. As a result, the collision detection device 1 according to the first embodiment can automatically and accurately detect collisions between objects 5 while reducing the amount of processing for collision determination as compared with the conventional configuration. Further, the collision detection device 1 according to Embodiment 1 does not cause variations in accuracy depending on the size and complexity of the object 5 .

Finally, a hardware configuration example of the collision detection device 1 according to the first embodiment will be described with reference to FIG. 10 .
The processing circuit 51 may be dedicated hardware, as shown in FIG. 10A, or a CPU (Central Processing Unit, central processing unit, It may be a processing device, an arithmetic device, a microprocessor, a microcomputer, a processor, or a DSP (Digital Signal Processor) 52 .

If the processing circuit 51 is dedicated hardware, the processing circuit 51 may be, for example, a single circuit, a composite circuit, a programmed processor, a parallel programmed processor, an ASIC (Application Specific Integrated Circuit), an FPGA (Field Programmable Gate). Array), or a combination thereof. The functions of the exclusion unit 102, the creation unit 103, the simple determination unit 104, the simple determination unit 105, and the detailed determination unit 106 may be realized by the processing circuit 51, or the functions of each unit may be collectively realized by the processing circuit 51. You may

When the processing circuit 51 is the CPU 52, the functions of the exclusion unit 102, the creation unit 103, the simple determination unit 104, the simple determination unit 105, and the detailed determination unit 106 are realized by software, firmware, or a combination of software and firmware. Software and firmware are written as programs and stored in the memory 53 . The processing circuit 51 implements the function of each part by reading and executing the program stored in the memory 53 . That is, the collision detection device 1 includes a memory 53 for storing a program that, when executed by the processing circuit 51, results in execution of the steps shown in FIG. 2, for example. It can also be said that these programs cause a computer to execute the procedures and methods of the exclusion unit 102, the creation unit 103, the simple determination unit 104, the simple determination unit 105, and the detailed determination unit 106. FIG. Examples of the memory 53 include nonvolatile or volatile semiconductor memories such as RAM, ROM, flash memory, EPROM, and EEPROM, magnetic disks, flexible disks, optical disks, compact disks, minidisks, DVDs, and the like. do.

Note that the functions of the exclusion unit 102, the creation unit 103, the simple determination unit 104, the simple determination unit 105, and the detailed determination unit 106 are partly implemented by dedicated hardware and partly implemented by software or firmware. can be For example, the function of the exclusion unit 102 is realized by the processing circuit 51 as dedicated hardware, and the processing circuit 51 of the creation unit 103, the simple determination unit 104, the simple determination unit 105, and the detailed determination unit 106 is stored in the memory 53. Its function can be realized by reading and executing the stored program.

Thus, the processing circuitry 51 can implement each of the functions described above by means of hardware, software, firmware, or a combination thereof.

It should be noted that, within the scope of the present invention, any component of the embodiment can be modified or any component of the embodiment can be omitted.

A collision detection device according to the present invention can automatically detect a collision between objects while reducing the amount of processing for collision determination as compared with the conventional configuration, and can detect collisions between objects. suitable for use in

1 collision detection device 5 object 5a moving object 5b stationary object 6, 6a, 6b boundary volume 51 processing circuit 52 CPU 53 memory 101 storage unit 102 exclusion unit 103 creation unit 104 simple determination unit (first simple determination unit), 105 simple determination unit (second simple determination unit), 106 detailed determination unit.

Claims (4)

a creation unit that creates boundary volumes for each of a plurality of objects including at least one moving object;
a first simple determination unit that detects a bounding volume that interferes with the bounding volume of the moving object using the bounding volume created by the creating unit and identifies an object that corresponds to the detected bounding volume;
a second simple determination unit that detects polygons interfering with a boundary volume of a moving object among the polygons to be processed that form the object identified by the first simple determination unit;
a detailed determination unit that performs collision determination based on the polygons to be processed that constitute the object detected by the second simple determination unit and the polygons to be processed that constitute the moving object;
an exclusion unit for excluding one of the polygons sharing the vertex coordinates from the processing target when all the vertex coordinates of one polygon are shared by other polygons in the polygons constituting the object. ,
The collision detection device, wherein the second simple determination unit performs processing using polygons to be processed that form an object after processing by the exclusion unit. a creation unit that creates boundary volumes for each of a plurality of objects including at least one moving object;
a first simple determination unit that detects a bounding volume that interferes with the bounding volume of the moving object using the bounding volume created by the creating unit and identifies an object that corresponds to the detected bounding volume;
a second simple determination unit that detects polygons interfering with a boundary volume of a moving object among the polygons to be processed that form the object identified by the first simple determination unit;
a detailed determination unit that performs collision determination based on the polygons to be processed that constitute the object detected by the second simple determination unit and the polygons to be processed that constitute the moving object;
an exclusion unit that randomly excludes some of the polygons that make up the object from being processed;
The collision detection device, wherein the second simple determination unit performs processing using polygons to be processed that form an object after processing by the exclusion unit. a creation unit that creates boundary volumes for each of a plurality of objects including at least one moving object;
a first simple determination unit that detects a bounding volume that interferes with the bounding volume of the moving object using the bounding volume created by the creating unit and identifies an object that corresponds to the detected bounding volume;
a second simple determination unit that detects polygons interfering with a boundary volume of a moving object among the polygons to be processed that form the object identified by the first simple determination unit;
a detailed determination unit that performs collision determination based on the polygons to be processed that constitute the object detected by the second simple determination unit and the polygons to be processed that constitute the moving object;
The second simple determination unit determines, based on the traveling direction of the moving object, at least one of the polygons to be processed that constitute the moving object and the polygons to be processed that constitute the object specified by the first simple determination unit. A collision detection device characterized by excluding a part of polygons of one of them from processing targets. The second simple determination unit detects polygons interfering with the boundary volume of the object specified by the first simple determination unit, among the polygons to be processed that constitute the moving body,
2. The detailed determination unit performs collision determination based on the polygons to be processed that constitute the object and the polygons to be processed that constitute the moving object detected by the second simple determination unit. 4. The collision detection device according to any one of claims 3 to 4 .

Images