Method and device for detecting collision between two numerically simulated objects
View Patent ↗In the system for detecting collision between rigid or deformable polyhedral objects simulated numerically and represented by simplicial complexes (K 1 , K 2 ), there is effected in a pre-processor module ( 110 ) at least one step ( 111 ) of calculating a geometrical description of the polyhedral cone corresponding to the normals in the strong sense (n |K| (Int σ)) associated with the faces (σ) of the simplicial complexes, and at least one step ( 113 ) of constructing trees of encompassing volumes. From information obtained from the pre-processing step, the modules ( 121, 122 ) calculate local minimum distances (LMD) and quasi local minimum distances (quasi-LMD). The system for implementing the method can be coupled to a mechanical solver ( 130 ) and to one or more peripherals ( 140 ).
1. A method of detecting collision between at least one first numerically-simulated polyhedral object and at least one second numerically-simulated polyhedral object and of constructing geometrical information about proximity and contact between them;
the method being characterized in that the first and second numerically-simulated polyhedral objects are represented in the form of non-interfering simplicial complexes (K 1 , K 2 ) in R n , where R n designates the Cartesian product of the body of real numbers multiplied by itself n times, with n equal to 2 or 3;
wherein a pre-processing step is carried out for each simplicial complex (K) for which the coordinates of the vertices are given in a fixed system of coordinates;
wherein the pre-processing step consists at least in calculating for each face (σ) of each simplicial complex (K) a geometrical description of the polyhedral cone corresponding to normals in the strong sense (n|K| (Intσ)) associated with that face (σ), determining a label of a contact class to which that face (σ) belongs, and determining for each simplicial complex (K) a tree of encompassing volumes of the object of the simplicial complex (K) from positions of the faces (σ) of the simplicial complex (K) and the sets of associated normals in the strong sense (n|K| (σ)); and
wherein, from information obtained after the pre-processing step, a step of calculating local minimum distances (LMD) and quasi local minimum distances (quasi-LMD) is carried out, an LMD being defined by a pair of points producing a local minimum of a restriction of a distance function to the Cartesian product of said simplicial complexes (K 1 , K 2 ) and by a positive real number d(a,b) characterizing the LMD, each quasi local minimum distance corresponding to a pair of points belonging to respective distinct objects that would define a local minimum distance (LMD) if the position of one object relative to the other were subject to a rotation by a small angle (γmax) below a given threshold.
2. A method according to claim 1 , characterized in that at least one numerically-simulated polyhedral object is rigid.
3. A method according to claim 1 , characterized in that at least one numerically-simulated polyhedral object is deformable.
4. A computer implemented system for detecting collision between at least one first numerically-simulated polyhedral object and at least one second numerically-simulated polyhedral object and for constructing geometrical information about proximity and contact between them , the system comprising:
a processor that is operative to execute instructions to provide:
means for representing the first and second numerically-simulated polyhedral objects in the form of non-interfering simplicial complexes (K 1 , K 2 ) in Rn, where Rn designates the Cartesian product of the body of real numbers multiplied by itself n times, with n equal to 2 or 3;
pre-processing means for each simplicial complex (K) for which the coordinates of the vertices are given in a fixed system of coordinates;
the pre-processing means comprise at least means for calculating for each face (σ) of each simplicial complex (K) a geometrical description of the polyhedral cone corresponding to normals in the strong sense (n|K| (Int σ)) associated with that face (σ), means for determining a label of a contact class to which that face (σ) belongs, and means for determining for each simplicial complex (K) a tree of encompassing volumes of the object of the simplicial complex (K) from positions of the faces (σ) of the simplicial complex (K) and the sets of associated normals in the strong sense (n|K| (σ));
calculation means associated with the pre-processing means for calculating local minimum distances (LMD) and quasi local minimum distances (quasi-LMD), an LMD being defined by a pair of points producing a local minimum of a restriction of a distance function to the Cartesian product of said simplicial complexes (K 1 , K 2 ) and by a positive real number d(a,b) characterizing the LMD each quasi local minimum distance corresponding to a pair of points belonging to respective distinct objects that would define a local minimum distance (LMD) if the position of one object relative to the other were subject to a rotation by a small angle (γmax) below a given threshold; and
the system being coupled to at least one peripheral selected from the group comprising a graphical user interface, a mouse, a movement capture peripheral, a force feedback interface, a touch-sensitive interface, and an audio interface.
5. A method of detecting collision between at least one first numerically-simulated polyhedral object and at least one second numerically-simulated polyhedral object and of constructing geometrical information about proximity and contact between them;
the method being characterized in that the first and second numerically-simulated polyhedral objects are represented in the form of non-interfering simplicial complexes (K 1 , K 2 ) in Rn, where Rn designates the Cartesian product of the body of real numbers multiplied by itself n times, with n equal to 2 or 3;
wherein a pre-processing step is carried out for each simplicial complex (K) for which the coordinates of the vertices are given in a fixed system of coordinates;
wherein the pre-processing step consists at least in calculating for each face (σ) of each simplicial complex (K) a geometrical description of the polyhedral cone corresponding to normals in the strong sense (n|K| (Int σ)) associated with that face (σ), determining a label of a contact class to which that face (a) belongs, and determining for each simplicial complex (K) a tree of encompassing volumes of the object of the simplicial complex (K) from positions of the faces (σ) of the simplicial complex (K) and the sets of associated normals in the strong sense (n|K| (σ)); and
wherein, from information obtained after the pre-processing step, a step of calculating local minimum distances (LMD) and quasi local minimum distances (quasi-LMD) is carried out, an LMD being defined by a pair of points producing a local minimum of a restriction of a distance function to the Cartesian product of said simplicial complexes (K 1 , K 2 ) and by a positive real number d(a,b) characterizing the LMD, each quasi local minimum distance corresponding to a pair of points belonging to respective distinct objects that would define a local minimum distance (LMD) if the position of one object relative to the other were subject to a rotation by a small angle (γmax) below a given threshold;
said calculating step operation is associated with one or more of a mechanical solver or a peripheral device selected from the group consisting of a graphical user interface, a mouse, a movement capture peripheral, a force feedback interface, a touch-sensitive interface, and an audio interface.