CN112802203B - Spatial hash continuous collision detection method based on features - Google Patents
Spatial hash continuous collision detection method based on features Download PDFInfo
- Publication number
- CN112802203B CN112802203B CN202110062332.2A CN202110062332A CN112802203B CN 112802203 B CN112802203 B CN 112802203B CN 202110062332 A CN202110062332 A CN 202110062332A CN 112802203 B CN112802203 B CN 112802203B
- Authority
- CN
- China
- Prior art keywords
- collision
- detected
- grid model
- physical
- edge
- 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.)
- Active
Links
- 238000001514 detection method Methods 0.000 title claims abstract description 64
- 239000002245 particle Substances 0.000 claims abstract description 51
- 238000000034 method Methods 0.000 claims abstract description 42
- 238000004088 simulation Methods 0.000 claims description 11
- 238000005452 bending Methods 0.000 claims description 5
- 238000009877 rendering Methods 0.000 claims description 5
- 230000008030 elimination Effects 0.000 abstract description 8
- 238000003379 elimination reaction Methods 0.000 abstract description 8
- 230000009471 action Effects 0.000 description 5
- 238000004422 calculation algorithm Methods 0.000 description 5
- 230000008569 process Effects 0.000 description 5
- 230000000694 effects Effects 0.000 description 4
- 241000208199 Buxus sempervirens Species 0.000 description 3
- 238000004364 calculation method Methods 0.000 description 3
- 238000005457 optimization Methods 0.000 description 3
- 238000000638 solvent extraction Methods 0.000 description 3
- 230000004048 modification Effects 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- YTAHJIFKAKIKAV-XNMGPUDCSA-N [(1R)-3-morpholin-4-yl-1-phenylpropyl] N-[(3S)-2-oxo-5-phenyl-1,3-dihydro-1,4-benzodiazepin-3-yl]carbamate Chemical compound O=C1[C@H](N=C(C2=C(N1)C=CC=C2)C1=CC=CC=C1)NC(O[C@H](CCN1CCOCC1)C1=CC=CC=C1)=O YTAHJIFKAKIKAV-XNMGPUDCSA-N 0.000 description 1
- 239000003153 chemical reaction reagent Substances 0.000 description 1
- 238000005094 computer simulation Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 239000004744 fabric Substances 0.000 description 1
- 230000005484 gravity Effects 0.000 description 1
- 230000006872 improvement Effects 0.000 description 1
- 238000002372 labelling Methods 0.000 description 1
- 239000002994 raw material Substances 0.000 description 1
- 230000003068 static effect Effects 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
- G06T17/20—Finite element generation, e.g. wire-frame surface description, tesselation
- G06T17/205—Re-meshing
Landscapes
- Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Computer Graphics (AREA)
- Geometry (AREA)
- Software Systems (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
- Image Analysis (AREA)
Abstract
A method for feature-based spatial hash sequential collision detection, the method comprising the steps of: acquiring a physical grid model of an object to be detected; acquiring adjacent information of each feature in the physical grid model; establishing a structural constraint relation of the physical grid model according to the adjacency information; calculating the predicted position of each particle in the physical grid model at the next moment; and detecting the actually collided feature pairs in the physical grid model based on the spatial hash collision of each feature. Compared with a spatial hash collision detection method based on a triangle, the spatial hash continuous collision detection method based on the characteristics has the advantages of complete elimination of repeated detection and high elimination efficiency; compared with other BVH methods based on characteristics, the method has the advantages of avoiding extra time-consuming steps, having smaller development difficulty and easy parallelism, and being capable of realizing collision and self-collision detection without difference; the method has the advantages of high collision detection efficiency, less time consumption and easy realization.
Description
Technical Field
The invention belongs to the technical field of continuous collision detection, and particularly relates to a spatial hash continuous collision detection method based on features.
Background
The physical modeling of various objects (including rigid, soft and flexible objects) in the real world based on physical simulation technology, and the demonstration of dynamic realistic effect by using the calculation and rendering capability of a computer have been widely applied in the fields of movie industry, electronic games, virtual reality, etc. Collision detection is a very important and time-consuming part, and many methods are currently used to accelerate collision detection, and can be roughly classified into two types, one is based on object partitioning, such as a hierarchical bounding box tree (BVH) method, and the other is based on spatial partitioning, such as a spatial octree, a binary spatial partitioning tree (BSP), a K-d tree, and a spatial hashing method. However, bac i u g, et al, noted that graphics primitive-based collision detection algorithms suffer from a large number of duplicate detections, and for this reason they propose a method of random labeling that uniquely assigns each feature (i.e., vertex and edge) to a contiguous triangle, thereby avoiding duplicate detection of collision pairs. Hutter M. and the like find that besides a large amount of repeated detection, the problem of low rejection efficiency exists in the collision detection based on the graphic primitives, so that the rejection efficiency is improved by introducing a characteristic bounding box for vertexes and edges, the repeated detection is avoided by using a Bac i u G method, and the efficiency and the speed of the collision detection are further improved. Manocha d. et al propose a hierarchical bounding box tree method based on "representing triangles" on the two ideas, and use feature bounding boxes to improve rejection efficiency.
Although the above collision detection methods have respective advantages and can eliminate duplicate detection and solve the problem of low elimination efficiency, the following problems still exist: 1.
(1) Eliminating the need for repeated collision detection to assign each feature to a unique adjacent triangle, which requires additional time consumption, especially when the mesh topology changes, requiring reassignment of the fracture site;
(2) The improved algorithms are based on the hierarchical bounding box tree, and for flexible objects such as cloth and the like, when large deformation occurs, the elimination efficiency of the BVH is greatly reduced, the BVH tree needs to be adjusted and even rebuilt when necessary, and the collision detection performance is seriously influenced;
(3) The BVH tree method needs to use different traversal methods for inter-object collision detection and object self-collision detection, and needs to select an optimization strategy to adjust the BVH tree, which increases the difficulty in implementing the algorithm.
In contrast, the spatial hash method can avoid the above points and can easily implement parallel computation, but as far as the applicant knows, no feature-based spatial hash continuous collision detection method exists at present.
Disclosure of Invention
In view of the above, the present invention provides a feature-based spatial hash continuous collision detection method that overcomes or at least partially solves the above mentioned problems.
In order to solve the technical problem, the invention provides a spatial hash continuous collision detection method based on features, which comprises the following steps:
acquiring a physical grid model of an object to be detected;
acquiring adjacent information of each feature in the physical grid model;
establishing a structural constraint relation of the physical grid model according to the adjacency information;
calculating the predicted position of each particle in the physical grid model at the next moment;
and detecting the actually collided feature pairs in the physical grid model based on the spatial hash collision of each feature.
Preferably, the acquiring adjacency information of each feature in the physical grid model includes:
importing the physical grid model into a physical simulation system;
reading vertex position information, triangle information and normal information of the physical grid model;
initializing state information of each particle of the physical grid model;
and generating adjacency information of each feature according to the connection relation of the vertexes in the physical mesh model.
Preferably, the establishing of the structural constraint relationship of the physical grid model according to the adjacency information comprises the following steps:
acquiring the initial position of each particle in the physical grid model;
acquiring mechanical characteristics of the object to be detected;
establishing a distance constraint relation between two vertexes of each edge in the physical grid model;
and establishing a dihedral angle bending constraint relation between two co-edge triangles in the physical grid model.
Preferably, the step of calculating the predicted position of each particle in the physical grid model at the next time comprises the steps of:
acquiring the time step length and the current time of a physical simulation system;
acquiring an external force borne by each particle in the physical grid model at the current moment;
acquiring a semi-implicit Euler integral formula;
and predicting the predicted position of each particle at the next moment according to Newton's second law and the semi-implicit Euler integral formula.
Preferably, the detecting the feature pair actually collided in the physical grid model based on the spatial hash collision of each feature comprises the steps of:
acquiring a spatial grid covered by a spatial bounding box of a swept volume within a time step from a current moment to a next moment;
acquiring a triangular hash table and a side hash table corresponding to the spatial grid;
correspondingly adding the triangles in the physical grid model into the triangle hash table;
correspondingly adding edges in the physical grid model into the edge hash table;
detecting point-face collision pairs in the physical grid model;
detecting edge-edge collision pairs in the physical grid model.
Preferably, the detecting of the point-face collision pair in the physical mesh model comprises the steps of:
traversing each vertex in the physical mesh model;
obtaining the swept track of each vertex in the time step from the current moment to the next moment;
acquiring all spatial grids covered by the bounding boxes of the track;
judging whether the track is intersected with a bounding box of the space grid;
if yes, traversing all triangles in the spatial grid;
if not, skipping;
judging whether the vertex is the vertex of the triangle or not;
if so, skipping over the channel,
if not, judging whether the vertexes and the triangles are detected or not;
if yes, skipping;
if not, judging whether the track is intersected with the triangular bounding box or not;
if so, carrying out continuous collision detection on the vertex and the triangle to generate a point-surface collision pair constraint relation, and marking the point-surface collision pair as detected;
if not, skipping, and marking the point-surface collision pair as detected.
Preferably, the step of determining whether the vertex and the triangle have been detected comprises the steps of:
setting an integer array with the length of the number of triangles and a timer;
resetting both the elements in the integer array and the timer to 0 when intersection detection begins;
incrementing the value of the timer by 1 each time a vertex is traversed;
judging whether the value of the integer array is equal to the current value of the timer or not;
if yes, judging that the vertex and the triangle are detected;
if not, judging that the vertex and the triangle are not detected.
Preferably, the detecting edge-edge collision pairs in the physical mesh model comprises the steps of:
traversing the edge hash table;
forming a side-to-side collision pair to be detected between any two sides in each side hash table;
judging whether two edges in any edge-edge collision pair to be detected share a vertex;
if yes, skipping;
if not, judging whether the side-to-side collision pair to be detected is detected;
if yes, skipping;
if not, judging whether the swept volume space bounding boxes of the two sides are intersected;
if so, carrying out continuous collision detection on the side-side collision pair to generate a side-side collision pair constraint relation, and marking the side-side collision pair as detected;
if not, skipping and marking the side-side collision pair as detected.
Preferably, the determining whether the edge-edge collision pair to be detected has been detected comprises:
setting an unsigned integer array bitFlags with the length of (S + 31)/32;
obtaining the bit index number of the unsigned integer array bitFlags
Judging whether the index number of the bit is 1;
if so, judging that the side-to-side collision pair to be detected is detected;
if not, judging that the side-to-side collision pair to be detected is not detected;
wherein S = M (M-1)/2,M is the total number of edges in the physical grid model; i and j are the pair of side-to-side collisions to be detected (e) i ,e j ) The lower corner of (1).
Preferably, after the detecting the feature pairs actually collided in the physical mesh model based on the spatial hash collision of each of the features, the method further comprises the following steps:
performing constraint projection iteration on the structural constraint relation and the collision constraint relation;
correcting the predicted positions of all the particles to satisfy the structural constraint relationship and the collision constraint relationship;
acquiring the positions of all the particles in a collision-free state;
correcting the velocity of all the particles by using the positions of all the particles;
and rendering according to the current positions of all the particles to obtain an image.
One or more technical solutions in the embodiments of the present invention have at least the following technical effects or advantages: the characteristic-based spatial hash continuous collision detection method can eliminate repeated detection of point-surface collision pairs and edge-edge collision pairs, and simultaneously introduces the characteristic bounding box to further improve the elimination efficiency; through tests, compared with a space hash method based on graphic primitives, the method is greatly improved; meanwhile, compared with other conventional BVH algorithms based on characteristics, the method does not need to perform a characteristic distribution step, avoids a complex BVH tree adjustment process, can indiscriminately realize collision and self-collision between objects, is low in development difficulty and can easily realize parallel optimization.
Drawings
In order to more clearly illustrate the technical solutions in the embodiments of the present invention, the drawings required to be used in the description of the embodiments are briefly introduced below, and it is obvious that the drawings in the description below are some embodiments of the present invention, and it is obvious for those skilled in the art to obtain other drawings based on the drawings without creative efforts.
Fig. 1 is a schematic flowchart of a feature-based spatial hash continuous collision detection method according to an embodiment of the present invention;
fig. 2 shows an edge-to-edge collision detection bit flag array and an index in a spatial hash continuous collision detection method according to an embodiment of the present invention.
Detailed Description
The present invention will be described in detail below with reference to specific embodiments and examples, and the advantages and various effects of the present invention will be more clearly apparent therefrom. It will be understood by those skilled in the art that these specific embodiments and examples are illustrative of the invention and are not to be construed as limiting the invention.
Throughout the specification, unless otherwise specifically noted, terms used herein should be understood as having meanings as commonly used in the art. Accordingly, unless defined otherwise, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. If there is a conflict, the present specification will control.
Unless otherwise specifically stated, various raw materials, reagents, instruments, equipment and the like used in the present invention are commercially available or can be prepared by existing methods.
As shown in fig. 1, in the embodiment of the present application, the present invention provides a method for detecting continuous collision based on spatial hash based on features, where the method includes the steps of:
s1: acquiring a physical grid model of an object to be detected;
in the embodiment of the application, a physical grid model of an object to be detected can be designed and manufactured by using three-dimensional modeling software, and then a corresponding physical grid model data file is obtained from the three-dimensional modeling software. Of course, it is also possible to use an existing physical mesh model of the object to be detected, which has already been made.
S2: acquiring adjacent information of each feature in the physical grid model;
in this embodiment of the present application, the acquiring adjacency information of each feature in the physical grid model includes:
importing the physical grid model into a physical simulation system;
reading vertex position information, triangle information and normal information of the physical grid model;
initializing state information of each particle of the physical grid model;
and generating adjacency information of each feature according to the connection relation of the vertexes in the physical mesh model.
In this embodiment of the present application, when the adjacency information of each feature in the physical mesh model is obtained, the data in the physical mesh model file is input into the physical simulation system interface, and the physical simulation system reads the position information, the triangle information, and the normal information of each vertex in the object mesh model, and initializes the state information of each particle in the physical mesh model according to the position information, the triangle information, and the normal information, including the mass m of the particle i Reciprocal of mass w i Position x i And velocity v i Where i ∈ (1,.., n), n is the total number of vertices of all physical mesh models contained in the physical mesh model. In particular, m i And w i Initialise to 1, m for a fixed vertex i And w i Initialization is 0; position x i Initialisation to the coordinates of the vertices of the physical mesh model, velocity v i The initialization is 0. And then acquiring adjacency information of each feature (namely vertex, edge and triangle) in the physical mesh model according to the connection relation of the vertices of the physical mesh model, wherein the adjacency information specifically comprises a vertex set V, an edge set E and a triangle set T. For arbitrary vertex v i E, V, wherein the adjacent information specifically comprises an edge index list and a triangle index list adjacent to the edge index list; for any edge e i E, the adjacency information of the E specifically comprises two vertex indexes of the E and two triangle indexes participating in composition, specifically, for a boundary edge, the adjacency information only participates in composition of 1 triangle, and the second face index of the E is set to-1; for arbitrary triangles t i E T, and the adjacency information specifically comprises three vertex indexes and three edge indexes.
S3: establishing a structural constraint relation of the physical grid model according to the adjacency information;
in this embodiment of the present application, the establishing a structural constraint relationship of the physical grid model according to the adjacency information includes:
acquiring the initial position of each particle in the physical grid model;
acquiring the mechanical characteristics of the object to be detected;
establishing a distance constraint relation between two vertexes of each edge in the physical grid model;
and establishing a dihedral angle bending constraint relation between two co-edge triangles in the physical grid model.
In the embodiment of the present application, when the structural constraint relationship of the physical grid model is established according to the adjacency information, the structural constraint relationship between the particles is established according to the initial position of each particle in the physical grid model and the mechanical characteristics of the object to be detected, so as to describe the internal force action between the particles. Specifically, the structural constraint relationship includes a distance constraint between two vertexes of each edge, a dihedral angle bending constraint between two co-edge triangles, and the like, and the stiffness coefficient of the constraint is determined according to the mechanical properties of the object. Specifically, the distance constraint relationship is described as the formula: c (p) 1 ，p 2 )＝|p 1 -p 2 |-l 0 Wherein p is 1 And p 2 The initial positions of two particles,/, respectively 0 The original length of the edge; the dihedral bending constraint relationship is described by the equation:
wherein p is 1 、p 2 Two vertex positions, p, of a common edge 3 And p 4 The vertex positions of the non-common sides of the two triangular shapes,
is the initial dihedral angle between the two triangular shapes.
S4: calculating the predicted position of each particle in the physical grid model at the next moment;
in this embodiment of the present application, the calculating a predicted position of each particle in the physical grid model at a next time includes:
acquiring a time step length and a current moment of a physical simulation system;
acquiring an external force borne by each particle in the physical grid model at the current moment;
acquiring a semi-implicit Euler integral formula;
and predicting the predicted position of each particle at the next moment according to Newton's second law and the semi-implicit Euler integral formula.
In the embodiment of the application, when the predicted position of each particle in the physical grid model at the next moment is calculated, the time step delta t of the physical simulation system and the current moment t are obtained, and then the external force f borne by each particle in the physical grid model at the current moment t is calculated ext (including gravity, air resistance, friction, etc.), and then predicting the position of the particle i at the next time t +1 according to Newton's second law and semi-implicit Euler integral formula
The specific calculation formula is as follows:
wherein,
representing the predicted velocity of the particle i at the next instant,
representing the velocity, w, of the particle i at the current time i Representing the inverse mass of the particle i,
representing the location of particle i at the current time.
S5: and detecting the feature pairs which actually collide in the physical grid model based on the spatial Hash collision of each feature.
In this embodiment of the present application, the detecting a feature pair actually collided in the physical grid model based on the spatial hash collision of each feature includes:
acquiring a spatial grid covered by a spatial bounding box of a swept volume within a time step from a current moment to a next moment;
acquiring a triangular hash table and a side hash table corresponding to the spatial grid;
correspondingly adding the triangles in the physical grid model into the triangle hash table;
correspondingly adding the edges in the physical grid model into the edge hash table;
detecting point-face collision pairs in the physical grid model;
detecting edge-edge collision pairs in the physical grid model.
In this embodiment of the application, when detecting a feature pair actually collided in the physical mesh model based on a spatial hash collision of each feature, a triangle hash table and an edge hash table corresponding to the spatial mesh are first obtained, and then a triangle and an edge are respectively and correspondingly added to the triangle hash table and the edge hash table, so as to perform intersection detection on a point-surface (V-F) collision pair and an edge-edge (E-E) collision pair. In particular, for feature f i (triangle or edge) that needs to be added to the hash bucket corresponding to the spatial grid Cell covered by the spatial bounding box of the swept volume within the time step j The corresponding relation with the hash bucket is according to Cell j Coordinate (X) of j ,Y j ,Z j ) And performing hash operation and then performing modulo on the size N of the hash table to obtain the hash table. The specific hash function can be selected according to practice, and the common hash functions include XOR hash and DJB2 hash, and the calculation formula of the XOR hash function is as follows: h = X · p 1 xor Y·p 2 xor Z·p 3 Wherein h represents a hash value, X, Y and Z are coordinate components of the spatial grid respectively, and p1, p2 and p3 are three larger prime numbers, which can be taken as 73856093, 19349663 and 83492791 respectively.
In an embodiment of the present application, the detecting a point-surface collision pair in the physical mesh model includes:
traversing each vertex in the physical mesh model;
obtaining the swept track of each vertex in the time step from the current moment to the next moment;
acquiring all spatial grids covered by the bounding boxes of the track;
judging whether the track is intersected with a bounding box of the space grid;
if yes, traversing all triangles in the spatial grid;
if not, skipping;
judging whether the vertex is the vertex of the triangle or not;
if so, skipping over the channel,
if not, judging whether the vertexes and the triangles are detected or not;
if yes, skipping;
if not, judging whether the track is intersected with the triangular bounding box or not;
if yes, performing continuous collision detection on the vertexes and the triangles to generate a point-surface collision pair constraint relation, and marking the point-surface collision pairs as detected;
if not, skipping, and marking the point-surface collision pair as detected.
In the embodiment of the present application, when detecting a point-surface collision pair in the physical mesh model, for the point-surface (V-F) collision pair, each vertex in the physical mesh model needs to be traversed, and for the vertex V i Trace s swept over in this time step i And a locus s i Any space grid Cell covered by the bounding box j First, the trajectory s is determined i Whether or not to mesh Cell with space j The bounding boxes of (1) intersect, if so, traverse the spatial grid Cell j All triangles t in (1) k If not, skipping; then, it is determined whether the vertex i is a triangle t k If yes, skipping, if no, judging the vertex v i And triangle t i Whether the detection is already carried out or not, if so, skipping, and if not, further judging the track s i Whether or not to match the triangle t k The bounding boxes of (c) intersect, and if so, further vertex v is made i And triangle t i To generate a point-to-surface collision pair constraint relationship C VF (p 0 ,p 1 ,p 2 ,p 3 ) And marking the point-surface collision pair as detected; if not, skipping and marking the point-face collision pair as detected.
In an embodiment of the present application, the determining whether the vertex and the triangle have been detected includes:
setting an integer array with the length of the number of triangles and a timer;
resetting both the elements in the integer array and the timer to 0 when intersection detection begins;
incrementing the value of the timer by 1 each time a vertex is traversed;
judging whether the value of the integer array is equal to the current value of the timer or not;
if yes, judging that the vertex and the triangle are detected;
if not, judging that the vertex and the triangle are not detected.
In the present embodiment, a timestamp method is used to avoid duplicate detection of vertices and triangles for point-to-face (V-F) collision pairs. Specifically, the number N of triangles with one length is set t When intersection detection is started, resetting elements in the integer array timetags and the timer counter to 0, increasing the value of the timer counter by 1 when traversing a vertex, and judging that the value of the integer array timetags is equal to the current value of the timer counter i And the triangle t i Has already been detected; otherwise, judging the vertex v i And the triangle t i Was not detected.
In an embodiment of the present application, the detecting an edge-edge collision pair in the physical grid model includes:
traversing the edge hash table;
forming a side-to-side collision pair to be detected between any two sides in each side hash table;
judging whether two edges in any edge-edge collision pair to be detected share a vertex;
if yes, skipping;
if not, judging whether the side-to-side collision pair to be detected is detected;
if yes, skipping;
if not, judging whether the swept volume space bounding boxes of the two sides are intersected;
if so, carrying out continuous collision detection on the side-side collision pair to generate a side-side collision pair constraint relation, and marking the side-side collision pair as detected;
if not, skipping and marking the side-side collision pair as detected.
In the embodiment of the application, when detecting edge-edge collision pairs in the physical grid model, the edge hash tables can be traversed, and for edges in each edge hash table, an edge-edge (E-E) collision pair to be detected is formed between every two edges. For arbitrary edge-to-edge collision pairs (e) i ,e j ) First, judge (e) i ,e j ) If the two edges of the pair are in common vertex, skipping, otherwise, judging the edge-edge collision pair (e) i ,e j ) Whether the detection is carried out or not is carried out, if so, skipping is carried out, otherwise, whether the swept volume space bounding boxes of the two edges are intersected or not is judged, if so, the edge-edge collision pair continuous collision detection is carried out, and the edge-edge collision pair constraint relation C is generated EE (p 1 ,p 2 ,p 3 ,p 4 ) And marking the edge-edge collision pair as detected; if not, skipping and marking the edge-edge collision pair as detected.
In the embodiment of the present application, the determining whether the edge-to-edge collision pair to be detected has been detected includes:
setting an unsigned integer array bitFlags with the length of (S + 31)/32;
obtaining the bit index number of the unsigned integer array bitFlags
Judging whether the bit index number is 1 or not;
if so, judging that the side-to-side collision pair to be detected is detected;
if not, judging that the side-to-side collision pair to be detected is not detected;
wherein S = M (M-1)/2,M is the total number of edges in the physical grid model; i and j areDetecting edge-to-edge collision pairs (e) i ,e j ) The lower corner of (1).
In the embodiment of the application, the bit marking method is used for the side-to-side (E-E) collision pair to avoid repeated detection of the side and the edge. Specifically, for the E-E collision pair (E) i ,e j ) Wherein i is<j, using a bit to mark whether it has been detected, specifically, assuming that the total number of edges in the physical grid model is M, the total number of possible E-E collision pairs is S = M (M-1)/2, as shown in fig. 2. Each unsigned integer contains 32 bits, and then an unsigned integer array bitFlags with the length of (S + 31)/32 is applied to represent the detection state of all E-E collision pairs. For any E-E collision pair (E) i ,e j ) Wherein i<j, bit index number in its corresponding bitFlags is
Wherein S = M (M-1)/2,M is the total number of edges in the physical grid model; i and j are the pair of side-to-side collisions to be detected (e) i ,e j ) The lower corner of (1). Judging whether the bit is 1, if so, detecting the side-to-side collision pair to be detected; otherwise, it is not detected.
In this embodiment of the present application, after detecting a feature pair actually collided in the physical grid model based on the spatial hash collision of each feature, the method further includes:
s6: performing constraint projection iteration on the structural constraint relation and the collision constraint relation;
s7: correcting the predicted positions of all the particles to satisfy the structural constraint relationship and the collision constraint relationship;
s8: acquiring the positions of all the particles in a collision-free state;
s9: correcting the velocity of all the particles by using the positions of all the particles;
s10: and rendering according to the current positions of all the particles to obtain an image.
In the embodiment of the application, when the spatial hash collision detection based on each feature detects the actual collision in the physical grid modelAfter the collision characteristic pair, performing constraint projection iteration on the static structural constraint relation and the dynamic collision constraint relation together, correcting the predicted positions of all mass points to meet the constraint relation, and obtaining a collision-free state through multiple iterations, wherein the obtained mass point position is the correct position p under the combined action of external force and internal constraint i . Then use the correct position p of all particles i Correcting the velocity v of the corresponding particle i And rendering according to the current positions of all the particles to obtain a frame of image. And (5) taking the updated particle position and velocity as the initial state of the next time step, and repeating the steps S4-S10 to realize the continuous dynamic simulation effect until a complete simulation animation is obtained.
The characteristic-based spatial hash continuous collision detection method can eliminate repeated detection of point-surface collision pairs and edge-edge collision pairs, and simultaneously introduces the characteristic bounding box to further improve the elimination efficiency; through tests, compared with a space hash method based on graphic primitives, the method is greatly improved; meanwhile, compared with other conventional BVH algorithms based on characteristics, the method does not need to perform a characteristic distribution step, avoids a complex BVH tree adjustment process, can indiscriminately realize collision and self-collision between objects, is low in development difficulty and can easily realize parallel optimization.
Compared with a spatial hash collision detection method based on a triangle, the spatial hash continuous collision detection method based on the characteristics has the advantages of complete elimination of repeated detection and high elimination efficiency; compared with other BVH methods based on characteristics, the method has the advantages of avoiding extra time-consuming steps, having smaller development difficulty and easy parallelism, and being capable of realizing collision and self-collision detection without difference; the method has the advantages of high collision detection efficiency, less time consumption and easy realization.
It is noted that, in this document, relational terms such as "first" and "second," and the like, may be used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. Also, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, an element defined by the phrases "comprising a," "8230," "8230," or "comprising" does not exclude the presence of additional like elements in a process, method, article, or apparatus that comprises the element. The above description is merely exemplary of the present application and is presented to enable those skilled in the art to understand and practice the present application. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the application. Thus, the present application is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.
In short, the above description is only a preferred embodiment of the present invention, and is not intended to limit the scope of the present invention. Any modification, equivalent replacement, or improvement made within the spirit and principle of the present invention should be included in the protection scope of the present invention.
Claims (9)
1. A method for detecting continuous collision of spatial hash based on characteristics is characterized in that the method comprises the following steps:
acquiring a physical grid model of an object to be detected;
acquiring adjacent information of each feature in the physical grid model;
establishing a structural constraint relation of the physical grid model according to the adjacency information;
calculating the predicted position of each particle in the physical grid model at the next moment;
detecting the actually collided feature pairs in the physical grid model based on the spatial hash collision of each feature, specifically:
acquiring a spatial grid covered by a spatial bounding box of a swept volume in a time step between a current moment and a next moment;
acquiring a triangular hash table and a side hash table corresponding to the spatial grid;
correspondingly adding the triangles in the physical grid model into the triangle hash table;
correspondingly adding edges in the physical grid model into the edge hash table;
detecting point-face collision pairs in the physical grid model;
detecting edge-edge collision pairs in the physical grid model.
2. The method according to claim 1, wherein the step of obtaining the adjacency information of each feature in the physical grid model comprises the steps of:
importing the physical grid model into a physical simulation system;
reading vertex position information, triangle information and normal information of the physical grid model;
initializing state information of each particle of the physical grid model;
and generating adjacency information of each feature according to the connection relation of the vertexes in the physical mesh model.
3. The feature-based spatial hash sequential collision detection method according to claim 1, wherein said building a structural constraint relation of said physical grid model according to said adjacency information comprises the steps of:
acquiring the initial position of each particle in the physical grid model;
acquiring the mechanical characteristics of the object to be detected;
establishing a distance constraint relation between two vertexes of each edge in the physical grid model;
and establishing a dihedral angle bending constraint relation between two triangles sharing the same edge in the physical grid model.
4. The method according to claim 1, wherein the step of calculating the predicted position of each particle in the physical grid model at the next time comprises the steps of:
acquiring the time step length and the current time of a physical simulation system;
acquiring an external force borne by each particle in the physical grid model at the current moment;
acquiring a semi-implicit Euler integral formula;
and predicting the predicted position of each particle at the next moment according to Newton's second law and the semi-implicit Euler integral formula.
5. The feature-based spatial hash sequential collision detection method according to claim 1, wherein said detecting point-surface collision pairs in said physical mesh model comprises the steps of:
traversing each vertex in the physical mesh model;
obtaining the swept track of each vertex in the time step from the current moment to the next moment;
acquiring all spatial grids covered by the bounding boxes of the track;
judging whether the track is intersected with a bounding box of the space grid;
if yes, traversing all triangles in the spatial grid;
if not, skipping;
judging whether the vertex is the vertex of the triangle or not;
if so, skipping over the channel,
if not, judging whether the vertexes and the triangles are detected or not;
if yes, skipping;
if not, judging whether the track is intersected with the triangular bounding box or not;
if yes, performing continuous collision detection on the vertexes and the triangles to generate a point-surface collision pair constraint relation, and marking the point-surface collision pairs as detected;
if not, skipping and marking the point-surface collision pair as detected.
6. The feature-based spatial hash sequential collision detection method according to claim 5, wherein said determining whether said vertex and said triangle have been detected comprises:
setting an integer array with the length of the number of triangles and a timer;
resetting both the elements in the integer array and the timer to 0 when intersection detection begins;
incrementing the value of the timer by 1 each time a vertex is traversed;
judging whether the value of the integer array is equal to the current value of the timer or not;
if yes, judging that the vertex and the triangle are detected;
if not, judging that the vertex and the triangle are not detected.
7. The feature-based spatial hash sequential collision detection method according to claim 1, wherein said detecting edge-edge collision pairs in said physical mesh model comprises the steps of:
traversing the edge hash table;
forming a side-to-side collision pair to be detected between any two sides in each side hash table;
judging whether two edges in any edge-edge collision pair to be detected share a vertex;
if yes, skipping;
if not, judging whether the side-to-side collision pair to be detected is detected;
if yes, skipping;
if not, judging whether the swept volume space bounding boxes of the two sides are intersected;
if so, carrying out continuous collision detection on the side-side collision pair to generate a side-side collision pair constraint relation, and marking the side-side collision pair as detected;
if not, skipping, and marking the side-side collision pair as detected.
8. The feature-based spatial hash sequential collision detection method according to claim 7, wherein said determining whether said to-be-detected edge-to-edge collision pair has been detected comprises:
setting an unsigned integer array bitFlags with the length of (S + 31)/32;
obtaining the bit index number of the unsigned integer array bitFlags
Judging whether the index number of the bit is 1;
if so, judging that the side-to-side collision pair to be detected is detected;
if not, judging that the side-to-side collision pair to be detected is not detected;
wherein S = M (M-1)/2,M is the total number of edges in the physical mesh model; i and j are the pair of side-to-side collisions to be detected (e) i ,e j ) The lower corner of (1).
9. The feature-based spatial hash sequential collision detection method according to claim 5 or 7, further comprising, after said detecting the feature pairs actually collided in the physical grid model based on the spatial hash of each of said features, the steps of:
performing constraint projection iteration on the structural constraint relation and the collision constraint relation;
correcting the predicted positions of all the particles to satisfy the structural constraint relationship and the collision constraint relationship;
acquiring the positions of all the particles in a collision-free state;
correcting the velocity of all the particles by using the positions of all the particles;
and rendering according to the current positions of all the particles to obtain an image.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202110062332.2A CN112802203B (en) | 2021-01-18 | 2021-01-18 | Spatial hash continuous collision detection method based on features |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202110062332.2A CN112802203B (en) | 2021-01-18 | 2021-01-18 | Spatial hash continuous collision detection method based on features |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN112802203A CN112802203A (en) | 2021-05-14 |
| CN112802203B true CN112802203B (en) | 2023-02-28 |
Family
ID=75810067
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202110062332.2A Active CN112802203B (en) | 2021-01-18 | 2021-01-18 | Spatial hash continuous collision detection method based on features |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN112802203B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113609667B (en) * | 2021-07-30 | 2024-03-15 | 深圳市创想三维科技股份有限公司 | Model layout method, apparatus, computer device and storage medium |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1996388A (en) * | 2006-12-21 | 2007-07-11 | 上海交通大学 | Method for detecting real-time conflict of deformed bodies in virtual operation system |
| CN102708017A (en) * | 2012-05-18 | 2012-10-03 | 浙江大学 | Non-collinear-elimination-based detection method for continuous collision in flexible scene |
| CN106407605A (en) * | 2016-11-01 | 2017-02-15 | 南京大学 | Particle computer dynamic simulation method for 3D garment |
| CN107330972A (en) * | 2017-06-28 | 2017-11-07 | 华中科技大学鄂州工业技术研究院 | Simulate the real-time soft tissue deformation method and system of biomechanics characteristic |
| CN110047143A (en) * | 2019-03-04 | 2019-07-23 | 南昌大学 | A kind of method for detecting continuous collision based on space subdivision and dynamic encompassing box |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7191104B2 (en) * | 2002-07-11 | 2007-03-13 | Ford Global Technologies, Llc | Method of real-time collision detection between solid geometric models |
| CN102722910B (en) * | 2012-05-18 | 2014-08-13 | 浙江大学 | Volume mesh scene continuous collision detection method based on separation axis removal |
| CN103324784B (en) * | 2013-05-30 | 2016-05-18 | 杭州电子科技大学 | A kind of grid model collision processing method based on local restriction |
-
2021
- 2021-01-18 CN CN202110062332.2A patent/CN112802203B/en active Active
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1996388A (en) * | 2006-12-21 | 2007-07-11 | 上海交通大学 | Method for detecting real-time conflict of deformed bodies in virtual operation system |
| CN102708017A (en) * | 2012-05-18 | 2012-10-03 | 浙江大学 | Non-collinear-elimination-based detection method for continuous collision in flexible scene |
| CN106407605A (en) * | 2016-11-01 | 2017-02-15 | 南京大学 | Particle computer dynamic simulation method for 3D garment |
| CN107330972A (en) * | 2017-06-28 | 2017-11-07 | 华中科技大学鄂州工业技术研究院 | Simulate the real-time soft tissue deformation method and system of biomechanics characteristic |
| CN110047143A (en) * | 2019-03-04 | 2019-07-23 | 南昌大学 | A kind of method for detecting continuous collision based on space subdivision and dynamic encompassing box |
Non-Patent Citations (7)
| Title |
|---|
| Collision-Streams: Fast GPU-based Collision Detection for Deformable Models;Min Tang等;《http://gamma.cs.unc.edu/CSTREAMS/》;20111231;第1-8页 * |
| Fast collision detection for deformable models using representative-triangles. in: Proceedings of the 2008 symposium on Interactive 3D graphics and games;S. Curtis等;《Redwood City》;20081231;第61-69页 * |
| 变形物体碰撞检测技术研究;王天柱;《中国博士学位论文全文数据库 信息科技辑》;20070515;第I138-23页 * |
| 图形硬件加速的柔性物体连续碰撞检测;唐敏等;《计算机学报》;20101015(第10期);第2022-2029页 * |
| 基于OBB层次包围盒的碰撞检测算法改进;王鹏等;《计算机工程与设计》;20090716(第13期);第3196-3208 * |
| 基于网格拓扑优化的连续碰撞检测算法;张龙涛等;《计算机工程》;20141215(第12期);第292-301页 * |
| 应急仿真中的碰撞检测算法研究;周进广等;《计算机安全》;20091015(第10期);第12-15页 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN112802203A (en) | 2021-05-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US10198847B2 (en) | Physically based simulation methods for modeling and animating two-and three-dimensional deformable objects | |
| US7098907B2 (en) | Method for converting explicitly represented geometric surfaces into accurate level sets | |
| Ernst et al. | Early split clipping for bounding volume hierarchies | |
| JP6159807B2 (en) | Computer graphics method for rendering a three-dimensional scene | |
| Dionne et al. | Geodesic voxel binding for production character meshes | |
| Weller | New geometric data structures for collision detection and haptics | |
| Eppstein et al. | Motorcycle graphs: Canonical quad mesh partitioning | |
| US7468730B2 (en) | Volumetric hair simulation | |
| US20130127895A1 (en) | Method and Apparatus for Rendering Graphics using Soft Occlusion | |
| WO2024037116A1 (en) | Three-dimensional model rendering method and apparatus, electronic device and storage medium | |
| CN112802203B (en) | Spatial hash continuous collision detection method based on features | |
| Bender et al. | Adaptive cloth simulation using corotational finite elements | |
| Trusty et al. | The shape matching element method: direct animation of curved surface models | |
| Friston et al. | Real-time collision detection for deformable characters with radial fields | |
| Bender et al. | Efficient Cloth Simulation Using an Adaptive Finite Element Method. | |
| CN114254501B (en) | Large-scale grassland rendering and simulating method | |
| Dequidt et al. | Time‐critical animation of deformable solids | |
| CN113591208A (en) | Oversized model lightweight method based on ship feature extraction and electronic equipment | |
| CN104346822A (en) | Texture mapping method and device | |
| Hinks et al. | Wind-driven snow buildup using a level set approach | |
| Svensson | Real-time rendering of deformable snow covers | |
| Abdelnaim et al. | Fluid-structure interactions simulation and visualization using ISPH approach | |
| US8010330B1 (en) | Extracting temporally coherent surfaces from particle systems | |
| Shepherd et al. | Quality improvement and feature capture in hexahedral meshes | |
| Mihalef | The marker level set method: applications to simulation of liquids |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |