Method for increasing efficiency of continuous collision detection

一种碰撞检测、效率的技术，应用在仪器、计算、图像数据处理等方向，能够解决不能保证测试实时性、过滤算法大计算花销、计算时间长等问题

Inactive Publication Date: 2015-05-20
EAST CHINA NORMAL UNIV
View PDF2 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0004] Among them, the continuous collision detection algorithm is defined as in a time parameter interval [t 0 ,t 1 ] to detect whether there is any collision between all objects and other objects. The biggest defect is that it is impossible to exclude adjacent pairs of primitives that have not collided with each other, even if it is a very flat deformable triangular mesh without self-collision. It is also impossible to rule out, so many false positives (False Positives) are generated, and the rejection rate is very low, and each false positive needs to perform a point-surface basic test or an edge-edge basic test, that is, a cubic equation needs to be solved, so , so that most of the collision detection time is spent on false positives, resulting in a large amount of calculation and slow detection speed. In some complex simulation environments, the real-time performance of the test cannot be guaranteed.
However, the calculation time of these two algorithms is long, and the filtering algorithm itself has a large calculation cost.

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0034] refer to figure 1 with figure 2 , the method for improving the efficiency of continuous collision detection in the present invention is as follows:

[0035] Step 1: Get Coordinates

[0036] For a pair of moving or deforming triangles, assuming that their vertices move with a constant velocity in the time interval t ∈ [0,1], the continuous collision detection of two moving or deforming triangles consists of six point-surface tests ( figure 2 A) and nine edge-edge tests ( figure 2 B). Each point-surface collision or edge-edge collision involves four vertices, set four vertices x → i ( t ) ( i = 1,2,3,4 ) .

[0037] Step 2, get the cubic function

[0038] Set constant velocity for four vertices Then the point-surface distance or edge-edge distance f(t) can be ex...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

PUM

No PUM Login to view more

Abstract

The invention provides a method for increasing efficiency of continuous collision detection. The method comprises the steps of acquiring coordinates of vertexes of two triangles required to be subjected to collision detection in a space, obtaining cubic equations for collision according to vector coplanarity, obtaining a Sturm sequence of a cubic function according to the definition of the Sturm sequence, substituting boundary values of a specified interval into the sequence so as to respectively obtain two symbolic variable values of boundary value sequences, finally, determining the existence circumstances of the equations in specified interval roots by a difference value between the two symbolic variable values according to Sturm's theorem, and filtering out the cubic equations without roots, which indicate that the collision cannot occur. According to the method, the majority of detection pairs, which cannot be subjected to collision, can be effectively filtered out, the filtering ratio can reach 90% to the highest, and the efficiency of a continuous collision detection algorithm can be remarkably increased.

Description

technical field [0001] The invention relates to a method capable of improving the efficiency of continuous collision detection, in particular to a CCD filtering calculation method based on Sturm's theorem. Background technique [0002] In applications such as physics-based simulation, robot motion planning, tactile rendering, and tolerance verification of virtual prototypes, non-penetrating constraints are widely applied to movable or deformable objects to achieve collision results. Continuous collision detection is a primary technique for maintaining non-penetrating constraints and better handling of collision feedback. [0003] The reason why collision detection is required between objects is that two or more impenetrable objects cannot exist in the same space area in the real world. With the rise of virtual reality, computer animation and other technologies, people are eager to simulate the real environment and the imagined environment that does not exist objectively, an...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

Application Information

Patent Timeline
no application Login to view more
Patent Type & Authority Applications(China)
IPC IPC(8): G06T17/00
Inventor 张新宇刘要
Owner EAST CHINA NORMAL UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap