CN117036642A - Grid collision detection method and device and electronic equipment - Google Patents
Grid collision detection method and device and electronic equipment Download PDFInfo
- Publication number
- CN117036642A CN117036642A CN202310910336.0A CN202310910336A CN117036642A CN 117036642 A CN117036642 A CN 117036642A CN 202310910336 A CN202310910336 A CN 202310910336A CN 117036642 A CN117036642 A CN 117036642A
- Authority
- CN
- China
- Prior art keywords
- target
- model
- subspace
- tree
- directed distance
- 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.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; 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
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
- G06T17/005—Tree description, e.g. octree, quadtree
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T19/00—Manipulating 3D models or images for computer graphics
- G06T19/003—Navigation within 3D models or images
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T2210/00—Indexing scheme for image generation or computer graphics
- G06T2210/21—Collision detection, intersection
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T2210/00—Indexing scheme for image generation or computer graphics
- G06T2210/41—Medical
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Software Systems (AREA)
- Computer Graphics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Geometry (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Computer Hardware Design (AREA)
- General Engineering & Computer Science (AREA)
- Image Analysis (AREA)
Abstract
The invention provides a grid collision detection method, a device and electronic equipment, wherein the grid collision detection method comprises the following steps: acquiring a tree-shaped directed distance graph of a pre-established target model; the tree-shaped directed distance graph comprises a plurality of subspaces obtained by combining adjacent leaf nodes, and each subspace is provided with a corresponding conversion matrix and a directed distance graph; acquiring coordinate information of a to-be-detected point, inquiring the tree-shaped directed distance graph based on the coordinate information, and determining a target subspace where the to-be-detected point is located; calculating target coordinates of the to-be-detected point in the target subspace based on coordinate information of the to-be-detected point and a conversion matrix corresponding to the target subspace; and determining the shortest distance between the to-be-detected point and the target model based on the target coordinates and the directed distance map corresponding to the target subspace, and judging the collision condition between the to-be-detected point and the target model based on the shortest distance. The invention can ensure the detection precision and accuracy of collision detection and improve the collision detection efficiency.
Description
Technical Field
The present invention relates to the field of collision detection technologies, and in particular, to a method and an apparatus for detecting a grid collision, and an electronic device.
Background
Collision detection is a technology commonly used in the field of virtual reality such as game development and operation simulation. The method is mainly applied to the fields of game development, operation simulation and the like, and the collision detection results among virtual characters, virtual objects and virtual environments determine the authenticity and accuracy of the interaction simulation results. The technology detects collision conditions among virtual objects, and calculates object intersection information required by subsequent interaction simulation according to detection results. For example, it is necessary to detect collisions between particles constituting the fluid and the surrounding environment when simulating the movement of the fluid, and it is necessary to detect collisions between a bullet moving at a high speed and a target when simulating the shooting of the bullet.
The existing collision detection technology generally comprises a collision detection mode based on surface parameterization of a grid model, a collision detection mode based on a space division tree and a collision detection mode based on a directed distance graph, wherein the collision detection mode based on surface parameterization of the grid model has higher efficiency in detecting collision between objects with simple parameterization, such as spheres, cubes and capsules, but for a model with complex surface morphology, the method is difficult to perform better parameterization fitting on the surface of the model, and cannot achieve higher collision detection precision; when the calculated objects are spheres and the number is large, the situation that the grids penetrate out easily occurs in a collision detection mode based on the space division tree, and the collision detection accuracy is low; the collision detection method based on the directed distance graph has higher detection precision, but for a model with complex geometric forms, the time required for generating the directed distance graph is longer, and the collision detection efficiency is lower. Therefore, the conventional collision detection technology has the problems of low collision detection accuracy and low collision detection efficiency.
Disclosure of Invention
Accordingly, the invention aims to provide a grid collision detection method, a grid collision detection device and electronic equipment, which can ensure the detection precision and accuracy of collision detection and improve the collision detection efficiency.
In order to achieve the above object, the technical scheme adopted by the embodiment of the invention is as follows:
in a first aspect, an embodiment of the present invention provides a method for detecting a grid collision, including: acquiring a tree-shaped directed distance graph of a pre-established target model; the tree-shaped directed distance graph comprises a plurality of subspaces obtained by combining adjacent leaf nodes, and each subspace is provided with a corresponding conversion matrix and a directed distance graph; acquiring coordinate information of a to-be-detected point, inquiring the tree-shaped directed distance graph based on the coordinate information, and determining a target subspace where the to-be-detected point is located; calculating target coordinates of the detection point in the target subspace based on the coordinate information of the detection point and the conversion matrix corresponding to the target subspace; determining the shortest distance between the to-be-detected point and the target model based on the target coordinates and the directed distance map corresponding to the target subspace, and judging the collision condition between the to-be-detected point and the target model based on the shortest distance.
Further, the embodiment of the present invention provides a first possible implementation manner of the first aspect, where the step of building a tree-shaped directed distance graph of the target model includes: acquiring a bounding box of the target model; wherein the target model is a two-dimensional grid model or a three-dimensional grid model; dividing sub-nodes from the central point of the bounding box until the number of model vertexes in the sub-nodes is smaller than the preset number, so as to obtain a segmentation tree model; deleting empty leaf nodes outside the target model in the segmentation tree model; the empty leaf nodes are leaf nodes which do not internally comprise edge points or edge line segments of the target model; for the segmentation tree model with the empty leaf nodes deleted, establishing an adjacent relation for adjacent leaf nodes which are not in the same branch structure, calculating the unit complexity of the model in the space of each leaf node, and merging the adjacent leaf nodes meeting the preset merging condition in the segmentation tree model into subspaces based on the unit complexity and the adjacent relation; and calculating a directed distance graph corresponding to each subspace to obtain a tree-shaped directed distance graph of the target model.
Further, the embodiment of the present invention provides a second possible implementation manner of the first aspect, wherein the unit complexity is calculated according to the following formula:
wherein Q is the unit complexity, V is the space volume of the leaf node, N is the number of vertices in the space of the leaf node, sigma is the variance of the angle between adjacent edges or faces, a is the weight parameter of the number of vertices, and b is the weight coefficient of the variance.
Further, the embodiment of the present invention provides a third possible implementation manner of the first aspect, where the step of merging, based on the unit complexity and the adjacency relation, adjacent leaf nodes in the partition tree model that meet a preset merging condition into a subspace includes: calculating the difference value of the unit complexity of two adjacent leaf nodes, merging the spaces of the two adjacent leaf nodes with the difference value smaller than a preset threshold value, and recalculating the unit complexity of the space of the node after merging until the difference value of the unit complexity of each adjacent node is larger than the preset threshold value, thereby obtaining a plurality of subspaces after merging.
Further, the embodiment of the present invention provides a fourth possible implementation manner of the first aspect, where the step of calculating a directed distance map corresponding to each subspace includes: calculating a directed distance map of each subspace based on a preset isosurface extraction algorithm; the number of sampling points of the subspace is in a proportional relation with the number of vertexes in the subspace.
Further, an embodiment of the present invention provides a fifth possible implementation manner of the first aspect, wherein the determining, based on the target coordinates and a directed distance map corresponding to the target subspace, a shortest distance between the to-be-detected point and the target model, and judging, based on the shortest distance, a collision situation between the to-be-detected point and the target model, includes: calculating the shortest distance from the point to be detected to the contour surface of the target model in the tree-shaped directed distance graph; when the shortest distance is a positive value, determining that the to-be-detected point is positioned outside the target model; when the shortest distance is a negative value, determining that the to-be-detected point is positioned in the target model; and when the shortest distance is zero, determining that the to-be-detected point is positioned on the surface of the target model.
Further, the embodiment of the present invention provides a sixth possible implementation manner of the first aspect, wherein a calculation formula of the target coordinates is: p '=mp, where P' is the target coordinate, M is the transformation matrix corresponding to the target subspace, and P is the coordinate of the to-be-detected point.
In a second aspect, an embodiment of the present invention further provides a mesh collision detection apparatus, including: the acquisition module is used for acquiring a tree-shaped directed distance graph of a pre-established target model; the tree-shaped directed distance graph comprises a plurality of subspaces obtained by combining adjacent leaf nodes, and each subspace is provided with a corresponding conversion matrix and a directed distance graph; the determining module is used for acquiring coordinate information of a to-be-detected point, inquiring the tree-shaped directed distance graph based on the coordinate information and determining a target subspace where the to-be-detected point is located; the calculation module is used for calculating the target coordinates of the detection point in the target subspace based on the coordinate information of the detection point and the conversion matrix corresponding to the target subspace; and the judging module is used for determining the shortest distance between the to-be-detected point and the target model based on the target coordinates and the directed distance graph corresponding to the target subspace, and judging the collision condition between the to-be-detected point and the target model based on the shortest distance.
In a third aspect, an embodiment of the present invention provides an electronic device, including: a processor and a storage device; the storage means has stored thereon a computer program which, when executed by the processor, performs the method according to any of the first aspects.
In a fourth aspect, embodiments of the present invention provide a computer-readable storage medium having stored thereon a computer program which, when executed by a processor, performs the steps of the method of any of the first aspects described above.
The embodiment of the invention provides a grid collision detection method, a device and electronic equipment, wherein the grid collision detection method comprises the following steps: acquiring a tree-shaped directed distance graph of a pre-established target model; the tree-shaped directed distance graph comprises a plurality of subspaces obtained by combining adjacent leaf nodes, and each subspace is provided with a corresponding conversion matrix and a directed distance graph; acquiring coordinate information of a to-be-detected point, inquiring the tree-shaped directed distance graph based on the coordinate information, and determining a target subspace where the to-be-detected point is located; calculating target coordinates of the to-be-detected point in the target subspace based on coordinate information of the to-be-detected point and a conversion matrix corresponding to the target subspace; and determining the shortest distance between the to-be-detected point and the target model based on the target coordinates and the directed distance map corresponding to the target subspace, and judging the collision condition between the to-be-detected point and the target model based on the shortest distance. According to the invention, the advantages of the space division tree and the advantages of the directed distance map are combined by establishing the tree-shaped directed distance map with the combination of the division tree and the directed distance map, so that the detection precision and the accuracy of collision detection are ensured; by acquiring the pre-established and stored tree-shaped directed distance graph, the collision detection is performed only according to the position of the point to be detected in the directed distance graph, so that the detection speed is high, and the collision detection efficiency is improved.
Additional features and advantages of embodiments of the invention will be set forth in the description which follows, or in part will be obvious from the description, or may be learned by practice of the embodiments of the invention.
In order to make the above objects, features and advantages of the present invention more comprehensible, preferred embodiments accompanied with figures are described in detail below.
Drawings
In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings that are needed in the description of the embodiments or the prior art will be briefly described, and it is obvious that the drawings in the description below are some embodiments of the present invention, and other drawings can be obtained according to the drawings without inventive effort for a person skilled in the art.
FIG. 1 shows a flowchart of a method for detecting grid collisions according to an embodiment of the present invention;
FIG. 2 is a schematic diagram of a two-dimensional model bounding box according to an embodiment of the present invention;
FIG. 3 illustrates a schematic diagram of a segmentation tree model of a two-dimensional model component provided by an embodiment of the present invention;
FIG. 4 is a schematic diagram showing a partition tree model empty leaf node marked as obsolete according to an embodiment of the present invention;
FIG. 5 is a schematic diagram of a partition tree model after deletion of empty leaf nodes according to an embodiment of the present invention;
FIG. 6 is a schematic diagram of a segmentation tree model after merging subspaces according to unit complexity according to an embodiment of the present invention;
FIG. 7 shows a schematic diagram of a simulated vascular mesh model provided by an embodiment of the present invention;
FIG. 8a shows a visual result of one layer of a directed distance map in a subspace of a simulated right femoral artery vessel provided by an embodiment of the present invention;
FIG. 8b shows a visualization of one layer of a directed distance map in a subspace in which a simulated intracranial vessel resides, in accordance with an embodiment of the present invention;
fig. 9 shows a schematic structural diagram of a mesh collision detection device according to an embodiment of the present invention.
Detailed Description
For the purpose of making the objects, technical solutions and advantages of the embodiments of the present invention more apparent, the technical solutions of the present invention will be described below with reference to the accompanying drawings, and it is apparent that the described embodiments are some embodiments of the present invention, but not all embodiments.
Currently, existing collision detection techniques generally include a collision detection method based on mesh model surface parameterization, a collision detection method based on a spatial segmentation tree, and a collision detection method based on a directed distance map.
Collision detection method based on surface parameterization of grid model, and method thereofFitting the surface of the grid model by using a function, and then transmitting the position of the vertex to be detected into the parameter to obtain the relative position relationship between the vertex to be detected and the surface. For example, when a certain point is combined with a certain sphere (sphere center position (x) 0 ,y 0 ,z 0 ) Radius: r) in collision detection, the method uses a formula To represent the surface of the sphere. Substituting the position of the vertex to be detected into the formula, wherein the absolute value of the value is the nearest distance of the vertex from the surface of the sphere.
A collision detection method based on a space division tree is provided, which divides the space where a three-dimensional (grid) object is located step by step and constructs a data structure of a tree for storage, such as a space octree. The leaf nodes of each tree structure store a partial triangle of the three-dimensional mesh. When collision detection is carried out, the vertex to be detected can quickly find the leaf node of the space division tree where the vertex to be detected is located according to the coordinate of the vertex to be detected in space, and the triangle stored in the leaf node is the triangle which is closest to the vertex to be detected in space and is the triangle most likely to collide. And then further intersecting the triangles with the vertices to be detected to obtain an accurate collision detection result. The method rapidly screens triangles which are likely to collide by constructing a space division tree for the triangle mesh.
The collision detection method based on the directed distance map stores the information of the shortest distance from each spatial point in the spatial bounding box where the three-dimensional grid is located to the grid. The method first generates a directed distance map for a three-dimensional (mesh) object, the result typically being stored in the form of a three-dimensional image (texture). When collision detection is carried out, only the value in the directed distance graph corresponding to the coordinate position of the vertex to be detected is required to be inquired.
The existing collision detection method based on the grid model and the space division tree generally has the defect of insufficient precision in collision detection, and when the model is complex and the number of triangle faces is large, a long time is needed to construct the space division tree, and the speed of collision detection is reduced along with the reduction of the number of triangle faces. The method for collision detection by using the constructed directed distance map has higher speed, but the accuracy depends on the sampling accuracy of the distance map, and the higher the accuracy is, the higher the memory occupied by the distance map information is, and the longer the time required for generating the distance map is. Therefore, the existing collision detection technology has the problem of lower detection precision or lower detection efficiency.
In order to improve the above problems, the embodiment of the present invention provides a method, an apparatus, and an electronic device for detecting a grid collision, and the following details of the embodiment of the present invention are described.
The embodiment provides a grid collision detection method, which can be applied to electronic equipment such as a computer, and the like, and is shown in a flow chart of the grid collision detection method shown in fig. 1, and the method mainly comprises the following steps:
step S102, a tree-shaped directed distance graph of a pre-established target model is obtained.
The tree-shaped directed distance graph comprises a plurality of subspaces obtained by combining adjacent leaf nodes, and each subspace is provided with a corresponding conversion matrix and a directed distance graph. The target model can be a two-dimensional model or a three-dimensional model, and the corresponding tree-shaped directed distance graph is a two-dimensional model or a three-dimensional model.
The tree-shaped directed distance graph can be that a segmentation tree model is generated based on a target model, then the tree structure is reorganized, adjacent sub-nodes with similar complexity in the tree structure are combined to obtain a plurality of subspaces, a triangle set in the subspace in the tree structure is replaced by a directed distance vector graph, a corresponding coordinate transformation matrix is calculated for each subspace, and coordinate values of a to-be-detected point can be transformed into a local coordinate system corresponding to the subspace through the coordinate transformation matrix.
Step S104, obtaining coordinate information of the to-be-detected point, inquiring a tree-shaped directed distance graph based on the coordinate information, determining a target subspace where the to-be-detected point is located, and calculating target coordinates of the to-be-detected point in the target subspace based on the coordinate information of the to-be-detected point and a conversion matrix corresponding to the target subspace.
When the target model is a two-dimensional model, the coordinates of the to-be-detected point are two-dimensional coordinates; when the target model is a three-dimensional model, the coordinates of the to-be-detected point are three-dimensional coordinates. Searching a tree-shaped directed distance graph according to the coordinates of the to-be-detected points, finding out the subspace of the to-be-detected points, marking the subspace as a target subspace, acquiring a transformation matrix and the directed distance graph associated with the target subspace, transforming the coordinates of the to-be-detected points into the coordinates under a local coordinate system in the target subspace based on the transformation matrix, and marking the coordinates as target coordinates.
In a specific embodiment, the calculation formula of the target coordinates is: p '=mp, where P' is the target coordinate, M is the transformation matrix corresponding to the target subspace, and P is the coordinate of the point to be detected.
And S106, determining the shortest distance between the to-be-detected point and the target model based on the target coordinates and the directed distance map corresponding to the target subspace, and judging the collision condition between the to-be-detected point and the target model based on the shortest distance.
Inquiring the shortest distance between the to-be-detected zone and the target model in a directed distance graph of the target subspace based on the local coordinate value of the to-be-detected point in the target subspace, namely the target as an index, and judging the collision condition of the to-be-detected point and the target model according to the size of the shortest distance value, wherein the collision condition comprises that the to-be-detected point is positioned inside the model, outside the model or on the surface of the model.
In a specific embodiment, calculating the shortest distance between the point to be detected and the contour surface of the target model in the tree-shaped directed distance graph; when the shortest distance is a positive value, determining that the to-be-detected point is positioned outside the target model; when the shortest distance is a negative value, determining that the to-be-detected point is positioned in the target model; and when the shortest distance is zero, determining that the to-be-detected point is positioned on the surface of the target model.
The shortest distance may be a vertical distance from the point to be detected to the edge line segment of the two-dimensional model, or a vertical distance from the point to be detected to the surface of the three-dimensional model, when the distance is positive, the point to be detected is located outside the model, when the distance is negative, the point to be detected is located inside the model, and when the distance is 0, the point to be detected is located on the surface of the model.
According to the grid collision detection method provided by the embodiment, the advantages of the space division tree and the advantages of the directed distance map are combined by establishing the tree-shaped directed distance map with the combination of the division tree and the directed distance map, so that the detection precision and the accuracy of collision detection are ensured; by acquiring the pre-established and stored tree-shaped directed distance graph, the collision detection is performed only according to the position of the point to be detected in the directed distance graph, so that the detection speed is high, and the collision detection efficiency is improved.
In one embodiment, the present embodiment provides an implementation manner of building a tree-shaped directed distance graph of a target model, which may be specifically performed with reference to the following steps:
step (1): acquiring a bounding box of the target model; wherein the target model is a two-dimensional grid model or a three-dimensional grid model;
a bounding box is created under the coordinate system that can completely enclose the object model, which can be represented by the geometric center point and the extension on the coordinate axes. Taking the target model as a two-dimensional grid model as an example, see a schematic diagram of a two-dimensional model bounding box as shown in fig. 2, wherein a point C is a geometric center point of the bounding box, and e x And e y Is the distance extending from the center to the boundary.
Step (2): dividing the sub-nodes from the central point of the bounding box until the number of model vertexes in the sub-nodes is smaller than the preset number, so as to obtain a segmentation tree model;
dividing the bounding box along the directions parallel to the coordinate axes by taking the geometric center point of the bounding box as the center, obtaining 4 child nodes with the same size if the target model is a two-dimensional model, and obtaining 8 child nodes with the same size if the target model is a three-dimensional model. Each subspace has a partial line segment (the inner surface of the subspace is a face when the target model is a three-dimensional model) forming the model surface, and the generated subspace Space with the number of vertexes larger than the preset number in the nodes is continuously divided until the number of vertexes in the generated subspace is smaller than the preset number N t The partitioning is stopped, such as the preset number may be 2, and when the number of model vertices within the subspace is 1.
The spatial division Tree used in the present embodiment includes, but is not limited to, an octree parallel to the coordinate axes used in the present embodiment, and a spatial division structure such as a kd-Tree or a direction bounding box Tree (OBB-Tree) may be used.
Referring to a schematic diagram of a segmentation tree model of a two-dimensional model member shown in fig. 3, after the two-dimensional model is subjected to sub-node division, a quadtree model is obtained (when the target model is a three-dimensional model, an octree model can be obtained), each node has 4 sub-nodes, 4 subspaces respectively correspond to each node, and each leaf node (i.e. a node without a sub-node) stores a line segment or a plane of the model in the space corresponding to the node.
Step (3): deleting empty leaf nodes outside the target model in the segmentation tree model; the empty leaf nodes are leaf nodes which do not internally comprise edge points or edge line segments of the target model;
for the obtained segmentation tree model of the target model, each leaf node of the segmentation tree model is empty or stores a certain number of edges or faces (namely boundary points or boundary faces of the model), a reverse layer sequence traversing mode is adopted from the leaf node of the segmentation tree model to the direction of a root node, all leaf nodes which are empty and are located at the boundary of an original bounding box are marked as abandoned, and the leaf nodes are removed from the segmentation tree model. Referring to the split tree model empty leaf nodes labeled as obsolete schematic shown in FIG. 4, all leaf nodes labeled as obsolete are identified by crosses. Since the otherwise empty leaf nodes are deleted from the segmentation tree model, all remaining leaf nodes on the segmentation tree model have edges or faces.
Step (4): for the segmentation tree model with the empty leaf nodes deleted, establishing an adjacent relation for adjacent leaf nodes which are not in the same branch structure, calculating the unit complexity of the model in the space of each leaf node, and merging the adjacent leaf nodes meeting the preset merging condition in the segmentation tree model into subspaces based on the unit complexity and the adjacent relation;
for all leaf nodes in the segmentation tree model after the empty leaf nodes are deleted in the step, an adjacency relation with adjacent nodes is established, namely, leaf nodes which are not originally in the same branch but are adjacent in space can be found through the current leaf nodes. Referring to the schematic diagram of the split tree model after the deletion of empty leaf nodes as shown in fig. 5, the leaf nodes U and V, V and W in fig. 5 are adjacent leaf nodes not in the same branch structure.
The unit complexity of the model is used for reflecting the complexity of geometric form information of the two-dimensional grid model or the three-dimensional grid model in a unit space, and the unit complexity of each leaf node is calculated by adopting an evaluation method of the unit space model complexity.
In a specific embodiment, the above computational formula of unit complexity is:
where Q is the unit complexity, V i For the spatial volume of the leaf node i, N is the number of vertices in the space of the leaf node, σ is the variance of the angle between adjacent edges or faces, a is the weight parameter of the number of vertices, and b is the weight coefficient of the variance.
In a specific embodiment, calculating the difference value of the unit complexity of two adjacent leaf nodes, merging the spaces of two adjacent leaf nodes with the difference value smaller than a preset threshold, and recalculating the unit complexity of the space of the node after merging until the difference value of the unit complexity of each adjacent node is larger than the preset threshold, so as to obtain a plurality of subspaces after merging.
The adjacent leaf nodes comprise two adjacent leaf nodes under the same branch mechanism, and the adjacent leaf nodes not in the same branch structure are included in the established adjacent relation. And comparing the unit complexity of two adjacent leaf nodes, if the difference of the unit complexity of the adjacent leaf nodes is less than 10%, merging the adjacent leaf nodes, recalculating the unit complexity of the space of the merged node, and continuously merging the space of the two adjacent leaf nodes with the difference of the unit complexity being less than a preset threshold until the difference of the unit complexity of each adjacent node is greater than the preset threshold. Referring to the schematic diagram of the segmentation tree model after merging subspaces according to unit complexity as shown in fig. 6, subspaces with adjacent child nodes and similar unit complexity are merged to obtain 4 subspaces.
Step (5): and calculating a directed distance graph corresponding to each subspace to obtain a tree-shaped directed distance graph of the target model.
And calculating a directed distance graph of each subspace obtained by combining so as to facilitate subsequent collision detection result query, and setting the sampling points on different coordinate axes to be k x M when calculating the directed distance graph for one subspace with M vertexes, namely, the number of the sampling points in the subspace is in direct proportion to the number of the vertexes, so that the sampling number in the space is ensured to be high enough to ensure that the details of an internal model are reserved.
In a specific embodiment, the directed distance map for each subspace may be calculated based on a preset iso-surface extraction algorithm, which may be a fast iso-surface extraction algorithm (Fast Marching Method, FMM); in the process of calculating the directed distance graph, the number of sampling points of the subspace is in a proportional relation with the number of vertexes in the subspace.
Compared with the traditional method based on the directed distance graph, the method has the advantages that the space is divided and recombined according to the complexity of the unit space, the sampling rates of different subspaces are dynamically set, and the high sampling rate is applied to the subspace area with high local complexity, so that the memory occupation space of the directed distance graph of the model can be reduced while the detailed information of the model is kept. On the premise of retaining the detailed characteristics of the complex model, the method has higher space utilization rate.
The target model adopted in the embodiment is an artificial arterial blood vessel model, the arterial blood vessel model extends from the lower part to the femoral artery and extends to the intracranial artery, the space spanned by the arterial blood vessel model is large, and the local complexity of the blood vessel model at different parts is greatly changed. Referring to the schematic diagram of the simulated vascular mesh model shown in fig. 7, the mesh models on the middle and right are respectively a front view and a side view of the partially fused subspace (the fused subspace in the gray frame) generated by the mesh collision detection method according to the present embodiment. It can be seen from fig. 7 that the head vessel is fused into a separate subspace due to the higher complexity of the unit space model of the head vessel model, whereas the heart model is more complex in the unit space model than the other vessel branches connected thereto, so that a separate subspace is formed, and the other parts are the same.
Referring to the visualization of one of the layers of the directed distance map in the subspace of the simulated right femoral artery vessel as shown in fig. 8a, the black dot-like region in fig. 8a represents the interior of the vessel, and the point within that region is mapped to the interior of the vessel; the gray area represents an area outside the blood vessel, and a point mapped to the area is located outside the blood vessel. The shortest distance between the detection point and the blood vessel can be obtained by directly reading the value from the graph.
Referring to the visual result of one layer of the directed distance map in the subspace of the simulated intracranial blood vessel shown in fig. 8b, the black dot-shaped region in fig. 8b represents the inside of the blood vessel, and because the complexity of the unit space of the blood vessel in the region is high, the scheme adopts a sampling rate higher than that of the femoral artery subspace to generate the directed distance map, so that the blood vessel data with smaller inner diameter can be calculated, and the accuracy of the collision detection result is ensured.
On the basis of the foregoing embodiment, the present embodiment provides an example of collision detection by applying the foregoing grid collision detection method, and may specifically be performed with reference to the following steps:
the first stage: hierarchical directed distance graph construction stage
And 1, constructing a space division tree.
A bounding box of the three-dimensional mesh model is obtained, which can be represented by its geometric center and the extension on the coordinate axes. As shown in FIG. 2, point C is the center of the bounding box, e x And e y For the distance of extension from the center to the boundary,dividing the bounding box along the directions parallel to the coordinate axes by taking the point C as the center, and obtaining 4 subspaces (8 subspaces in the three-dimensional space) with the same size, wherein partial line segments (triangles in the three dimensions) forming the model surface exist in each subspace. Partitioning the generated subspace until the number of vertexes in the generated subspace is less than N t Until a quadtree (octree if three-dimensional grid) is obtained, each node has 4 sub-nodes, corresponding to 4 subspaces respectively, and each leaf node (i.e. the node without sub-node) stores the line segment or triangle in the space corresponding to the node.
And 2, constructing cross-branch adjacency information.
Each leaf node of the spatial segmentation tree obtained by the above steps is empty or stores a certain amount of edge/triangle data. And marking all the leaf nodes which are empty and are positioned at the boundary of the original bounding box as obsolete in a reverse layer sequence traversing mode from the leaf nodes of the space division tree to the root nodes, and removing the leaf nodes from the tree structure. Since the otherwise empty leaf node is deleted from the partition tree, there are edges or triangles in all the remaining leaf node space on the spatial partition tree structure.
And establishing adjacency relation between all leaf nodes of the adjusted tree structure and adjacent nodes, namely finding out leaf nodes which are not originally in the same branch but are adjacent in space through the current leaf node.
And 3, calculating the unit complexity of the node model.
The complexity of the unit space of the model is used for reflecting the complexity of geometric form information of a three-dimensional grid model in the unit space, and the size of the complexity feels that the sampling rate is high and low when the directional distance map is generated in the area. The unit complexity of the model is denoted by Q, which we define as:
Where Q is the unit complexity，V i For the spatial volume of the leaf node i, N is the number of vertices in the space of the leaf node, σ is the variance of the angle between adjacent edges or faces, a is the weight parameter of the number of vertices, and b is the weight coefficient of the variance.
The unit space complexity is calculated for the three-dimensional model in the space of each leaf node. And comparing the space complexity of the adjacent nodes according to the calculated adjacent information of the leaf nodes, if the difference of the space complexity is less than 10%, combining the two leaf nodes corresponding to the two spaces, and recalculating the space complexity of the combined nodes.
And 4, generating a directed distance graph.
In the last step, subspaces are merged by calculating the unit model complexity within the subspaces. In the step, a rapid iso-surface extraction algorithm (Fast Marching Method, FMM) is adopted to calculate a directed distance graph of the subspace finally obtained in the previous step, so that subsequent collision detection result inquiry is facilitated. For a subspace with M vertexes, when a directed distance graph is calculated, the sampling points on different coordinate axes are all set to be 2M, so that the sampling quantity in the subspace is high enough to ensure that the details of an internal model are reserved.
And 5, generating a tree-shaped directed distance graph.
After the directed distance graph of each subspace is generated in the previous step, the original tree structure is reorganized, the limit of the number of the child nodes of the tree structure is removed, the triangle set in the child nodes is replaced by the directed distance graph generated in the previous step, a coordinate transformation matrix M is calculated for each node, and the original bounding box center point C can be transformed to the bounding box center point C of the current subspace through the matrix sub I.e. mc=c sub 。
And a second stage: collision detection phase
In this stage, a collision detection process suitable for hierarchical directed distance maps is mainly proposed. Taking the example of detecting the collision of a certain point P with the mesh model. Firstly, inquiring a tree-shaped directed distance graph according to the three-dimensional coordinates of a point to be detected, and finding out a subspace where the point is located, a conversion matrix M associated with the subspace and directed distance graph information. Then, the conversion matrix of the subspace is multiplied by the three-dimensional coordinate of the point to be detected to obtain a coordinate value P 'of the point to be detected in the subspace coordinate system, namely, P' =mp. And finally, using a local coordinate value P' of the point to be monitored in the subspace as an index, inquiring the shortest distance between the point and the model in the directed distance graph of the subspace, and judging and detecting the collision condition between the point to be monitored and the model according to the inquired shortest distance. If the shortest distance is positive, the to-be-detected point is outside the model; if the shortest distance is negative, the point to be detected is inside the model; if the shortest distance is 0, the point to be detected is on the surface of the model.
The above embodiment provided by the present embodiment has the following advantages:
1) The collision detection efficiency is high. Since the most time-consuming directed distance graph construction all occurs in the initialization phase of the program, the directed distance graph of the model can be pre-generated and stored as an external file. When the program runs, the collision detection process only queries the directed distance graph according to the vertex position, and the operation speed is high, so that the collision detection efficiency is improved.
2) On the premise of retaining the detailed characteristics of the complex model, the method has higher space utilization rate. Compared with the traditional method based on the directed distance graph, the method has the advantages that the space is divided and recombined according to the complexity of the unit space, the sampling rates of different subspaces are dynamically set, the high sampling rate is applied to the subspace area with high local complexity, and the (memory) space occupation of the directed distance graph of the whole model can be reduced while the detailed information of the model is kept.
Corresponding to the grid collision detection method provided in the above embodiment, the embodiment of the present invention provides a grid collision detection device, referring to a schematic structural diagram of the grid collision detection device shown in fig. 9, which includes the following modules:
An obtaining module 91, configured to obtain a tree-shaped directed distance graph of a pre-established target model; the tree-shaped directed distance graph comprises a plurality of subspaces obtained by combining adjacent leaf nodes, and each subspace is provided with a corresponding conversion matrix and a directed distance graph;
the determining module 92 is configured to obtain coordinate information of a to-be-detected point, query a tree-shaped directed distance graph based on the coordinate information, determine a target subspace where the to-be-detected point is located, and calculate a target coordinate of the to-be-detected point in the target subspace based on the coordinate information of the to-be-detected point and a transformation matrix corresponding to the target subspace;
the judging module 93 is configured to determine a shortest distance between the to-be-detected point and the target model based on the target coordinates and the directed distance map corresponding to the target subspace, and judge a collision condition between the to-be-detected point and the target model based on the shortest distance.
According to the grid collision detection device provided by the embodiment, the advantages of the space division tree and the advantages of the directed distance map are combined by establishing the tree-shaped directed distance map with the combination of the division tree and the directed distance map, so that the detection precision and the accuracy of collision detection are ensured; by acquiring the pre-established and stored tree-shaped directed distance graph, the collision detection is performed only according to the position of the point to be detected in the directed distance graph, so that the detection speed is high, and the collision detection efficiency is improved.
In one embodiment, the apparatus further comprises:
the building module is used for obtaining a bounding box of the target model; wherein the target model is a two-dimensional grid model or a three-dimensional grid model; dividing the sub-nodes from the central point of the bounding box until the number of model vertexes in the sub-nodes is smaller than the preset number, so as to obtain a segmentation tree model; deleting empty leaf nodes outside the target model in the segmentation tree model; the empty leaf nodes are leaf nodes which do not internally comprise edge points or edge line segments of the target model; for the segmentation tree model with the empty leaf nodes deleted, establishing an adjacent relation for adjacent leaf nodes which are not in the same branch structure, calculating the unit complexity of the model in the space of each leaf node, and merging the adjacent leaf nodes meeting the preset merging condition in the segmentation tree model into subspaces based on the unit complexity and the adjacent relation; and calculating a directed distance graph corresponding to each subspace to obtain a tree-shaped directed distance graph of the target model.
In one embodiment, the establishing module is configured to calculate a directed distance graph of each subspace based on a preset iso-surface extraction algorithm; wherein the number of sampling points in the subspace is in direct proportion to the number of vertices in the subspace.
In one embodiment, the above computational formula of unit complexity is:
wherein Q is unit complexity, V is the space volume of the leaf node, N is the number of vertices in the space of the leaf node, sigma is the variance of angles between adjacent edges or adjacent faces, a is a weight parameter of the number of vertices, and b is a weight coefficient of the variance.
In one embodiment, the establishing module is configured to calculate a difference value of unit complexity of two adjacent leaf nodes, combine spaces of two adjacent leaf nodes with a difference value smaller than a preset threshold, and recalculate the unit complexity of the space of the combined node until the difference value of the unit complexity of each adjacent node is greater than the preset threshold, so as to obtain a plurality of combined subspaces.
In one embodiment, the determining module 93 is configured to calculate, in the tree-shaped directed distance graph, a shortest distance between the point to be detected and the contour surface of the object model; when the shortest distance is a positive value, determining that the to-be-detected point is positioned outside the target model; when the shortest distance is a negative value, determining that the to-be-detected point is positioned in the target model; and when the shortest distance is zero, determining that the to-be-detected point is positioned on the surface of the target model.
In one embodiment, the calculation formula of the target coordinates is: p '=mp, where P' is the target coordinate, M is the transformation matrix corresponding to the target subspace, and P is the coordinate of the point to be detected.
The device provided in this embodiment has the same implementation principle and technical effects as those of the foregoing embodiment, and for brevity, reference may be made to the corresponding content in the foregoing method embodiment for a part of the description of the device embodiment that is not mentioned.
The embodiment of the invention provides electronic equipment, which comprises a processor and a memory, wherein the memory stores a computer program capable of running on the processor, and the processor realizes the steps of the method provided by the embodiment when executing the computer program.
Embodiments of the present invention provide a computer readable medium storing computer executable instructions that, when invoked and executed by a processor, cause the processor to implement the methods described in the above embodiments.
It will be clear to those skilled in the art that, for convenience and brevity of description, the specific working process of the system described above may refer to the corresponding process in the foregoing embodiment, which is not described in detail herein.
The grid collision detection method, the grid collision detection device and the computer program product of the electronic device provided by the embodiment of the invention comprise a computer readable storage medium storing program codes, and the instructions included in the program codes can be used for executing the method described in the method embodiment, and specific implementation can be referred to the method embodiment and will not be repeated here.
In addition, in the description of embodiments of the present invention, unless explicitly stated and limited otherwise, the terms "mounted," "connected," and "connected" are to be construed broadly, and may be, for example, fixedly connected, detachably connected, or integrally connected; can be mechanically or electrically connected; can be directly connected or indirectly connected through an intermediate medium, and can be communication between two elements. The specific meaning of the above terms in the present invention will be understood in specific cases by those of ordinary skill in the art.
The functions, if implemented in the form of software functional units and sold or used as a stand-alone product, may be stored in a computer-readable storage medium. Based on this understanding, the technical solution of the present invention may be embodied essentially or in a part contributing to the prior art or in a part of the technical solution, in the form of a software product stored in a storage medium, comprising several instructions for causing a computer device (which may be a personal computer, a server, a network device, etc.) to perform all or part of the steps of the method according to the embodiments of the present invention. And the aforementioned storage medium includes: a U-disk, a removable hard disk, a Read-Only Memory (ROM), a random access Memory (RAM, random Access Memory), a magnetic disk, or an optical disk, or other various media capable of storing program codes.
In the description of the present invention, it should be noted that the directions or positional relationships indicated by the terms "center", "upper", "lower", "left", "right", "vertical", "horizontal", "inner", "outer", etc. are based on the directions or positional relationships shown in the drawings, are merely for convenience of describing the present invention and simplifying the description, and do not indicate or imply that the devices or elements referred to must have a specific orientation, be configured and operated in a specific orientation, and thus should not be construed as limiting the present invention. Furthermore, the terms "first," "second," and "third" are used for descriptive purposes only and are not to be construed as indicating or implying relative importance.
Finally, it should be noted that: the above examples are only specific embodiments of the present invention, and are not intended to limit the scope of the present invention, but it should be understood by those skilled in the art that the present invention is not limited thereto, and that the present invention is described in detail with reference to the foregoing examples: any person skilled in the art may modify or easily conceive of the technical solution described in the foregoing embodiments, or perform equivalent substitution of some of the technical features, while remaining within the technical scope of the present disclosure; such modifications, changes or substitutions do not depart from the spirit and scope of the technical solutions of the embodiments of the present invention, and are intended to be included in the scope of the present invention. Therefore, the protection scope of the present invention shall be subject to the protection scope of the claims.
Claims (10)
1. A mesh collision detection method, comprising:
acquiring a tree-shaped directed distance graph of a pre-established target model; the tree-shaped directed distance graph comprises a plurality of subspaces obtained by combining adjacent leaf nodes, and each subspace is provided with a corresponding conversion matrix and a directed distance graph;
acquiring coordinate information of a to-be-detected point, inquiring the tree-shaped directed distance graph based on the coordinate information, and determining a target subspace where the to-be-detected point is located;
calculating target coordinates of the detection point in the target subspace based on the coordinate information of the detection point and the conversion matrix corresponding to the target subspace;
determining the shortest distance between the to-be-detected point and the target model based on the target coordinates and the directed distance map corresponding to the target subspace, and judging the collision condition between the to-be-detected point and the target model based on the shortest distance.
2. The method of claim 1, wherein the step of building a tree-shaped directed distance graph of the object model comprises:
acquiring a bounding box of the target model; wherein the target model is a two-dimensional grid model or a three-dimensional grid model;
Dividing sub-nodes from the central point of the bounding box until the number of model vertexes in the sub-nodes is smaller than the preset number, so as to obtain a segmentation tree model;
deleting empty leaf nodes outside the target model in the segmentation tree model; the empty leaf nodes are leaf nodes which do not internally comprise edge points or edge line segments of the target model;
for the segmentation tree model with the empty leaf nodes deleted, establishing an adjacent relation for adjacent leaf nodes which are not in the same branch structure, calculating the unit complexity of the model in the space of each leaf node, and merging the adjacent leaf nodes meeting the preset merging condition in the segmentation tree model into subspaces based on the unit complexity and the adjacent relation;
and calculating a directed distance graph corresponding to each subspace to obtain a tree-shaped directed distance graph of the target model.
3. The method of claim 2, wherein the computational formula for the unit complexity is:
wherein Q is the unit complexity, V i For the spatial volume of the leaf node i, N is the number of vertices in the space of the leaf node, σ is the variance of the angle between adjacent edges or faces, a is the weight parameter of the number of vertices, and b is the weight coefficient of the variance.
4. The method of claim 2, wherein the step of merging neighboring leaf nodes in the segmentation tree model that satisfy a preset merge condition into a subspace based on the unit complexity and the adjacency relation comprises:
calculating the difference value of the unit complexity of two adjacent leaf nodes, merging the spaces of the two adjacent leaf nodes with the difference value smaller than a preset threshold value, and recalculating the unit complexity of the space of the node after merging until the difference value of the unit complexity of each adjacent node is larger than the preset threshold value, thereby obtaining a plurality of subspaces after merging.
5. The method of claim 2, wherein the step of computing a directed distance map for each subspace comprises:
calculating a directed distance map of each subspace based on a preset isosurface extraction algorithm; the number of sampling points of the subspace is in a proportional relation with the number of vertexes in the subspace.
6. The method according to claim 1, wherein the step of determining the shortest distance between the to-be-detected point and the target model based on the target coordinates and the directed distance map corresponding to the target subspace, and determining the collision situation between the to-be-detected point and the target model based on the shortest distance includes:
Calculating the shortest distance from the point to be detected to the contour surface of the target model in the tree-shaped directed distance graph;
when the shortest distance is a positive value, determining that the to-be-detected point is positioned outside the target model;
when the shortest distance is a negative value, determining that the to-be-detected point is positioned in the target model;
and when the shortest distance is zero, determining that the to-be-detected point is positioned on the surface of the target model.
7. The method of claim 1, wherein the target coordinates are calculated as: p (P) ′ =p, where P ′ And for the target coordinates, M is a transformation matrix corresponding to the target subspace, and P is the coordinates of the detection point to be detected.
8. A mesh collision detection device, characterized by comprising:
the acquisition module is used for acquiring a tree-shaped directed distance graph of a pre-established target model; the tree-shaped directed distance graph comprises a plurality of subspaces obtained by combining adjacent leaf nodes, and each subspace is provided with a corresponding conversion matrix and a directed distance graph;
the determining module is used for acquiring coordinate information of a to-be-detected point, inquiring the tree-shaped directed distance graph based on the coordinate information and determining a target subspace where the to-be-detected point is located;
The calculation module is used for calculating the target coordinates of the detection point in the target subspace based on the coordinate information of the detection point and the conversion matrix corresponding to the target subspace;
and the judging module is used for determining the shortest distance between the to-be-detected point and the target model based on the target coordinates and the directed distance graph corresponding to the target subspace, and judging the collision condition between the to-be-detected point and the target model based on the shortest distance.
9. An electronic device, comprising: a processor and a storage device;
the storage means has stored thereon a computer program which, when executed by the processor, performs the method of any of claims 1 to 7.
10. A computer-readable storage medium, on which a computer program is stored, characterized in that the computer program, when being executed by a processor, performs the steps of the method of any of the preceding claims 1 to 7.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202310910336.0A CN117036642A (en) | 2023-07-21 | 2023-07-21 | Grid collision detection method and device and electronic equipment |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202310910336.0A CN117036642A (en) | 2023-07-21 | 2023-07-21 | Grid collision detection method and device and electronic equipment |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN117036642A true CN117036642A (en) | 2023-11-10 |
Family
ID=88634543
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202310910336.0A Pending CN117036642A (en) | 2023-07-21 | 2023-07-21 | Grid collision detection method and device and electronic equipment |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN117036642A (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118885945A (en) * | 2024-09-29 | 2024-11-01 | 广州中科医疗美容仪器有限公司 | A method and system for monitoring operating status parameters of ultrasonic therapeutic apparatus |
-
2023
- 2023-07-21 CN CN202310910336.0A patent/CN117036642A/en active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118885945A (en) * | 2024-09-29 | 2024-11-01 | 广州中科医疗美容仪器有限公司 | A method and system for monitoring operating status parameters of ultrasonic therapeutic apparatus |
| CN118885945B (en) * | 2024-09-29 | 2024-12-31 | 广州中科医疗美容仪器有限公司 | Ultrasonic therapeutic apparatus running state parameter monitoring method and system |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Jones et al. | 3D distance fields: A survey of techniques and applications | |
| CN109410332B (en) | Three-dimensional space geometric virtual model detail level cutting method based on point, line and surface | |
| US8711143B2 (en) | System and method for interactive image-based modeling of curved surfaces using single-view and multi-view feature curves | |
| CN113706713B (en) | Live-action three-dimensional model clipping method and device and computer equipment | |
| CN111581776B (en) | An isogeometric analysis method based on geometric reconstruction model | |
| US8988431B2 (en) | Conservative cell and portal graph generation | |
| CN104616345B (en) | Octree forest compression based three-dimensional voxel access method | |
| CN103400372B (en) | A 3D Topological Information Extraction Method Based on Reeb Diagram Description | |
| CN101281654A (en) | A large-scale complex 3D scene processing method based on octree | |
| CN107657659A (en) | The Manhattan construction method for automatic modeling of scanning three-dimensional point cloud is fitted based on cuboid | |
| WO2023024482A1 (en) | Interior structured reconstruction method and apparatus, and computer-readable storage medium | |
| JP2004521423A (en) | Generation of 3D representation from many images using octree | |
| CN102890828A (en) | Point cloud data compacting method based on normal included angle | |
| CN115984511B (en) | A CAD-based method for volume-average conformal meshing of parallelepipeds | |
| CN115082699B (en) | Contour shape extraction method and device, electronic equipment and storage medium | |
| Wu et al. | Occluder generation for buildings in digital games | |
| CN117036642A (en) | Grid collision detection method and device and electronic equipment | |
| US8948498B1 (en) | Systems and methods to transform a colored point cloud to a 3D textured mesh | |
| Wiemann et al. | Automatic Map Creation For Environment Modelling In Robotic Simulators. | |
| CN114092663B (en) | Three-dimensional reconstruction method, device, equipment and medium for urban information model building | |
| CN114140508B (en) | A method, system, device and readable storage medium for generating three-dimensional reconstruction model | |
| Guo et al. | Improved marching tetrahedra algorithm based on hierarchical signed distance field and multi-scale depth map fusion for 3D reconstruction | |
| JP3739209B2 (en) | Automatic polygon generation system from point cloud | |
| Kunert et al. | Efficient point cloud rasterization for real time volumetric integration in mixed reality applications | |
| Durix et al. | Towards skeleton based reconstruction: From projective skeletonization to canal surface estimation |
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 |