CN105279788A - Method for generating object space swept volume - Google Patents

Abstract

The invention discloses a method for generating a space sweeping body of an object, relates to the fields of virtual simulation, computer-aided manufacturing (CAM) and product cycle management (PLM), and in particular relates to a method for generating a virtual model moving sweeping body. This method uses the three-dimensional space voxel (Voxel) method to obtain the swept volume formed by the motion transformation of the object in the three-dimensional space, or the envelope volume, envelope space, sweep space, and sweep trajectory. Compared with the current calculation methods for swept volumes, the method proposed by the present invention is suitable for rigid and non-rigid motion transformations of arbitrary complex three-dimensional shapes, and can perform real-time three-dimensional display and analysis of swept volumes at each sampling moment during the motion transformation process. surface reconstruction. In addition, the present invention also proposes a large-scale parallel computing method to accelerate the sweeping volume calculation process, which is superior to existing methods in terms of algorithm calculation efficiency, calculation accuracy and robustness.

Description

A Method for Generating Swept Volume of Object Space

technical field

The invention belongs to the fields of virtual simulation, computer-aided manufacturing (CAM) and product cycle management (PLM), and in particular relates to a method for generating a virtual model motion sweeping body.

Background technique

Space sweep volume, also known as space envelope, envelope space, sweep space, sweep trajectory space, the English term is Swept Volume, which refers to any object along any trajectory line (even a surface) , perform motion transformation in a certain way (translation, rotation, scaling, deformation), and finally generate a sum of all the spaces that the object passes through in the three-dimensional space. The swept volume problem includes a series of sub-problems such as envelope modeling and calculation, envelope curve, surface delineation and 3D display. However, one of the most challenging problems is the generation and visualization of swept volumes. Space swept body technology plays a very important role in the design of complex geometric modeling, feasibility analysis of equipment assembly, large-scale design, and robot motion path planning. It has extraordinary value and significance.

The research on swept volumes began in the 1950s and 1960s. Although it has been developed for more than half a century, a series of methods for generating swept volumes have emerged. However, due to the complexity of the algorithm and the amount of data calculation It is too large, and there are always huge obstacles in its application in actual production practice. Therefore, this technology has always been considered as one of the recognized problems in the fields of computer graphics, visualization, and virtual reality.

In the early stage of swept volume research, the implementation methods were mainly methods based on analytic geometry, such as algorithms based on motion shapes and geometric shapes. The method based on the motion form is based on the envelope surface equation of the curve family, and uses the envelope theory to solve it through the differential equation. For example, Kim and Moon proposed an algebraic algorithm for generating purely rotated swept volumes specifically for algebraic curves and surfaces. The boundary of the swept volume obtained by this method is related to the boundary of the convoluted planar object. Parida and Mudur further add a series of sweeping rules to the more general sweeping volume method. Since then, some researchers have further extended the method and proposed the method of scanning envelope, which realizes the generation of three-dimensional swept volume of polygonal objects. Since the generation of the above-mentioned swept volume involves solving a large number of equations, the calculation efficiency is low, and its algorithm complexity is related to the number of vertices of the polygonal model. The core foundation of swept volume calculations in this period is implicit function theory: multivariate layering and sweeping envelope partial differential equations. Most of the work is to characterize the boundary of the swept volume by giving certain assumptions about the swept path. In this aspect, there are a lot of research reports on how to calculate the intersection calculation of geometric solid modeling surfaces. Although the methods based on geometric calculations can achieve the generation of swept volumes to a certain extent, their common defect is that they are only suitable for simple polygons or simple sweep trajectories, and their versatility is poor. More importantly, their calculation process involves To solve a large number of partial differential equations, in order to obtain accurate swept volumes, the algebraic complexity of the underlying calculations is very high. In addition, all these algorithm implementations for surface intersection calculations have many problems such as processing accuracy and robustness. Therefore, these geometric calculation-based methods cannot accurately calculate the swept volume of any polygon along a given smooth path.

In recent years, with the continuous improvement of computer hardware level and computing power, swept volume technology has been proposed again, and the emergence of a novel graphic representation and operation algorithm - voxel (Voxel) method makes arbitrary complex graphics extend arbitrary complex motion trajectories. Swept volume calculations are now possible. At present, for the space-sweeping volume generation technology of any complex object, only three companies in the world, Boeing (Boeing), Dassault (France), and Siemens (Germany), have launched actual products. They are respectively Boeing's Voxmap PointShell ^TM (VPS), Dassault's CATIA, Siemens' Kineo Wrapping. Boeing's Voxmap PointShell ^TM (VPS) itself is a function library that uses voxels (Voxel) to solve spatial geometry problems. In VPS, the swept volume (Swept Volume) generation module can generate the spatial entity swept by the object through the user-defined object motion trajectory, and complete the surface compensation function of the swept volume. In addition, the meshing function of VPS utilizes the local voxel space topology to quickly generate polygonal models. Dassault's CATIA is an important part of the PLM collaborative solution. Its space-swept volume module implementation method is different from Boeing's Voxmap PointShell ^TM (VPS), which uses geometric topology-based calculus and level-set (Level-set) method, while ensuring calculation accuracy, it also has low computational complexity. The Siemens PLM software Kineo™ Wrapping solution is a general-purpose software library for calculating swept volumes and wrapping. Kineo Wrapping can create a space-swept volume of moving parts during simulation by using externally defined motion space reservations. Additionally, the software supports kinematic swept volume generation for mannequins, robots or articulated systems. Kineo Wrapping is optimized through a series of algorithms, enabling users to obtain simplified mesh models and envelope surfaces directly from swept volumes without storing other intermediate transformations.

Although the above swept volume generation techniques are also based on the Voxel method and have their own characteristics, by analyzing their workflow, it can be found that they all have the following shortcomings:

1. The object model used to generate the swept body can only perform rigid body motion, that is, translation and rotation, but cannot do anything to the swept body generated by non-rigid transformations such as bending, scaling, extrusion, and arbitrary deformation of the free surface. ;

2. Only one final static space sweeping body can be generated, but the space sweeping body at each moment during the movement of the object cannot be dynamically calculated and displayed in real time;

3. The existing space-swept volume calculation algorithm has high complexity and low calculation efficiency, and all of them adopt offline calculation instead of real-time dynamic calculation.

Contents of the invention

The purpose of the present invention is to propose a novel fast calculation method for object space sweeping volume based on three-dimensional space voxel, aiming at the shortcomings in existing space scanning volume calculation. This method converts the object model moving and transforming in three-dimensional space into a voxel model in real time through the accelerated polygon voxelization algorithm, and then merges the voxel models at different times through a fast voxel operation algorithm to generate The voxel model is scanned in space at each moment and displayed in real time in 3D.

The inventive method is realized through the following specific steps:

1. The virtual object model M to be swept is represented in the form of a polygonal patch and vertices, and the coordinate information D of each vertex and the required connection information P of the vertices to form a polygonal patch are recorded;

The 2nd, for the virtual object model M in three-dimensional space, give a continuous motion transformation H whose time length is l ;

Third, the continuous motion transformation H of the virtual object model M in three-dimensional space is discretized and sampled on the time axis, and each sampling point represents the motion transformation H(t) at a certain moment t , where ;

4. At the moment of motion transformation sampling 0 , the virtual object model M represented by the polygonal facet and vertices is converted into a three-dimensional voxel model V ₀ in its own local coordinate system space F _local , and the voxel model V ₀ is copied to the world coordinate system F _world where the object motion transformation space is located, as the swept voxel model SV(0) = V ₀ at the initial 0 moment of object motion transformation;

Fifth, at the moment of motion transformation sampling t , where 1≤t≤l , according to the current motion transformation H(t) of the virtual object model M , recalculate the coordinate information D of the vertices of the polygonal surface of the virtual object model M , and the vertices constitute the polygonal surface The connection information P required by the chip;

Step 6. Retransform the virtual object model M that has undergone motion transformation H(t) in step 5 into a three-dimensional voxel model V _t in its own local coordinate system space F _local , and convert the voxel model V _t Copy to the world coordinate system F _world where the object motion transformation space is located;

Step 7. The sum of the 3D voxel model V _t of the sampling point at time t in step 6 and the 3D voxel model of all previous sampling points from 0 to t-1 Combine with set The method is combined to generate the swept volume voxel model SV(t) = , where 1≤ t ≤ l , and the sum of the 3D voxel models of all previous sampling points from 0 to t-1 In fact, it represents the swept voxel model at time t-1 , that is, SV(t-1)= , so the swept volume 3D voxel model SV(t) at time t can be expressed as SV(t)= V _t SV(t-1) ;

8th, carry out three-dimensional display and save the swept volume voxel model SV(t) at time t generated in step 7;

9. Extract the surface voxel from the swept volume voxel model SV(t) at time t generated in step 7, generate a subset of surface points SS(t) of the swept voxel at time t, perform three-dimensional display and save it;

10. Perform surface three-dimensional reconstruction on the swept volume voxel model SV(t) at time t generated in step 7, generate polygonal patch model SP(t) on the surface of the swept volume at time t, perform three-dimensional display and save;

11. Sampling time t for all motion transformations, , repeat steps 5 to 10 to generate the swept voxel model SV(t) of the object model M at each sampling time t , the swept voxel surface point subset SS(t) , and the polygon of the swept volume surface Surface model SP(t) , and real-time three-dimensional dynamic display.

Wherein, the virtual object model M described in the first step can be a single object model, or a model combination composed of multiple object models;

In the model combination composed of multiple object models described in step 1, the object models can be in a horizontal relationship or a parent-child inheritance relationship with hierarchical connections;

The virtual object model M described in step 1 can be expressed by any 3D model format, such as but not limited to implicit surface, mesh surface, polygonal surface, Nurbs surface, spline area surface, solid geometry, etc.;

The continuous motion transformation H described in the second step includes a rigid transformation for the model M , including: translation, rotation, and non-rigid deformation modification applied to the vertex coordinate information D and the connection information P required by the vertices to form a polygonal patch, for example but Not limited to: scaling, bending, twisting, extrusion, miscutting, vertex displacement free transformation, skin transformation, etc.;

In the process of discretizing the continuous motion transformation H on the time axis described in step 3, the sampling method is not limited to uniform sampling at equal intervals, but non-uniform sampling at variable intervals, and the sampling interval and sampling accuracy can be set arbitrarily ;

The process of converting the virtual object model M described in steps 4 and 6 into a three-dimensional voxel model in its own local coordinate system space F _local is accelerated by parallel computing;

The calculation process of the swept volume three-dimensional voxel model SV(t) at time t described in the 7th step adopts parallel computing to accelerate;

The surface voxel extraction described in step 9 and the surface 3D reconstruction in step 10 are accelerated by parallel computing, and these two steps are optional but not mandatory.

Advantages and beneficial effects of the present invention:

Compared with the traditional calculation method of swept volume based on computational geometry, the method proposed by the present invention has small calculation amount, low complexity and strong robustness; compared with the existing calculation method of swept volume based on voxel, the present invention proposes The method is not only suitable for rigid motion of rotation and translation, but also for sweeping volume calculation of bending, scaling, extrusion and arbitrary non-rigid transformation of free surface. Furthermore, what is more superior than all current sweeping volume generation methods is that this method can calculate and display the spatial sweeping volume at any moment during the motion transformation process of the object in real time, not just a static sweeping volume at the final moment. In addition, the method proposed by the present invention also adopts parallel computing to accelerate the process of polygonal voxelization and voxel operation. The invention has important practical value and good application prospect in the fields of manufacturing, virtual reality, military simulation, ergonomics and the like.

Description of drawings

Fig. 1 is a model object used for space swept volume calculation;

Fig. 2 endows a time length as a continuous motion transformation H of l for the model object used for space-swept volume calculation;

Fig. 3 is that the continuous motion transformation H whose time length is 1 is discretized and sampled;

Fig. 4 voxelizes the model used for the calculation of the space swept volume of the embodiment;

Fig. 5 merges the three-dimensional voxel model of the sampling point at time t with the sum of the three-dimensional voxel models of all sampling points at time 0 to t-1 before merging in the manner of set merge operation;

Fig. 6 is the voxel model of spatially swept voxel obtained by calculating the sampling point at time t ;

Fig. 7 is the final space-swept voxel model obtained after the motion transformation with a time length of l ;

Fig. 8 is a calculation example of a manipulator space swept volume;

Fig. 9 is an example of calculation of a swept volume in human motion space.

Among them, 101 is the original sphere model, 102 is the original cylinder model, 103 is the sphere polygon/vertex model, 104 is the cylinder polygon/vertex model, 105 is the local coordinate system of the model object itself; 106 is the swept body space world coordinate system ; 107 is the voxel model of the model object; 108 is a non-empty voxel at ( i , j , k ); 109 is an empty voxel; 110 is the polygon/vertex model at sampling point t ; 111 is sampling The swept object voxel model at point t time; 112 is the space swept voxel model at t -1 time; 113 is the space swept voxel model at t time; 114 is the final space swept voxel model .

detailed description

In order to make the purpose, technical solutions and advantages of the present invention more clear, the specific embodiments provided below in conjunction with the accompanying drawings are intended as descriptions of examples of the present invention, and are not intended to represent the only form that can be constructed or used in the examples of the present invention. It should be understood that the specific embodiments described here are only used to explain the present invention, illustrate the functions of the examples of the present invention, and the sequence of steps for constructing and operating the examples of the present invention, and are not intended to limit the present invention. However, the same or equivalent functions and sequences can be implemented by different examples.

The method for fast calculation of swept volume in object space proposed by the present invention is characterized in that the method calculates the swept volume formed by motion transformation of the object in three-dimensional space, or called envelope, envelope space, swept space, swept volume, etc. track. The core idea of this method is to convert the object model moving and transforming in three-dimensional space into a voxel model in real time through the accelerated polygon voxelization algorithm, and then merge the voxel models at different times through a fast voxel operation algorithm. , so as to generate a space-swept voxel model at each moment, and perform real-time three-dimensional display.

In a specific embodiment, the object used for swept volume calculation is composed of a sphere 101 and a cylinder 102 , as shown in FIG. 1 . In other embodiments, the object used to calculate the swept volume may be any complex three-dimensional object. The sphere 101 and the cylinder 102 have a hierarchically connected parent-child inheritance relationship, wherein the sphere 101 is a child object, and the cylinder 102 is a parent object of the sphere 101 . That is, unless the preset exclusive motion transformation is only performed on the cylinder 102 , other motion transformations on the cylinder 102 will be passed down to the sphere 101 . Conversely, the motion transformation of the sphere 101 will not be transferred to the cylinder 102 .

The virtual object models of the sphere 101 and the cylinder 102 can be generated by any 3D design tool, and the model format is any format that can express the geometric feature information of the object, as long as the model format can be further converted into a polygon/vertex model. Typical 3D model formats include, but are not limited to, triangular patches, quadrilateral patches, parametric surfaces, solid models, implicit surfaces, etc.

The virtual object model polygon/vertex representations 103 and 104 of the sphere 101 and cylinder 102 can be completed by computer-aided design and any method capable of model format conversion, as long as the generated polygon/vertex models can be further converted into voxel models.

After the polygon/vertex model conversion is completed, the vertex coordinate information of the sphere 103 and the cylinder 104 and the connection information of the vertices constituting the polygon facet are stored in the array D and the array P respectively. In a specific implementation, D and P store data in the following form:

D=(d ₀ ,d ₁ ,d ₂ ,d ₃ ,d ₄ ,d ₅ , … , d _i , … , d _n-1 , d _n )

P=( p ₀ , p ₁ , p ₂ , p ₃ , p ₄ , p ₅ , … , p _j , … , p _m-1 , p _m )

d _i is a three-dimensional vector in three-dimensional space, 0≤i≤n, n is the number of vertices; p _j is an index value used to point to an element in the array D. For example, when p _j = i , it means that p _j points to d _i . The arrangement order of the elements in the array P actually constitutes the polygonal representation of the model. In one embodiment, assuming that the polygons are all triangles, starting from the first element in the array P , every three consecutive elements form a triangle, and m should be an integer multiple of 3 at this time.

The vertex coordinate information value stored in the array D is defined as the displacement relative to the coordinate origin of a local coordinate system 105 . The local coordinate system 105 adopts a Cartesian coordinate system, which is composed of a coordinate origin and three orthogonal coordinate axes X , Y , Z. The local coordinate system 105 can be directly inherited from the original input model, and can also be reset during the conversion process of polygon patch and vertex model. The coordinate origin and the three orthogonal coordinate axes X , Y , and Z can be set arbitrarily.

A continuous motion transformation H with a time length of l is assigned to the three-dimensional space ^Rd where the sphere 103 and the cylinder 104 are located. The coordinate system in the three-dimensional space R ^d is called the world coordinate system 106 , and the origin of the world coordinate system 106 and the three orthogonal coordinate axes U , V , W are set by the user, as shown in FIG. 2 .

In one embodiment, the continuous motion transformation H is a combination of translation and rotation for the sphere 103 and cylinder 104 . In other embodiments, motion transformation includes but not limited to translation and rotation, and non-rigid deformation modification includes but not limited to scaling, bending, twisting , Extrusion, staggering, vertex displacement free transformation, skin transformation, etc.

The general form of the continuous motion transformation H is: Among them, R is a three-dimensional orthogonal rotation matrix, T is a three-dimensional translation vector, S is a three-dimensional scaling vector, and FM represents a non-rigid deformation modification transformation.

Define M _H as the transformation of the model M through the transformation matrix H , that is: As the object M moves, its trajectory can be expressed as a transformation matrix that changes over time , at each time point between t ₀ -t _l , Q produces a new position, orientation, size, and transformation of the vertices of the model.

Furthermore, define the sweeping object along any trajectory Q The swept body formed is :

motion change matrix The change over time is continuous because the movement of any object in the real world cannot be discrete. However, in computer computing, processing objects are generally discrete events, so it is necessary to model virtual objects in three-dimensional space The continuous motion transformation H in is discretized and sampled on the time axis, and each sampling point represents the motion transformation H(t) at a certain moment t , where t is an integer, and .

In the embodiment shown in Fig. 2, the discretization sampling process of the continuous motion transformation H of the sphere 103 and the cylinder 104 on the time axis is uniform sampling at equal intervals, and the sampling interval is 0.025s, that is, the sampling frequency is 40Hz, which means Motion transformation values are collected 40 times per second. In other embodiments, the discretization sampling process performed by the continuous motion transformation H on the time axis may be variable-interval non-uniform sampling, that is, the interval between every two sampling time points does not have to be the same.

After the motion transformation and its discretization sampling are completed, the sphere 103 and cylinder 104 represented by polygonal patches and vertices are converted into a three-dimensional voxel model 107 in their own local coordinate system 105 at the initial time of motion transformation sampling 0 ,As shown in Figure 3.

A voxel (Voxel) represents a value on a regular grid in the three-dimensional space ^Rd . The coordinates of each voxel represent its displacement relative to the origin of the space coordinate system in three-dimensional space. For example, voxel 108 has coordinates ( i , j , k ), then its position relative to the origin of coordinate system 105 is ( i , j , k ). The value of each voxel represents the occupancy of the space occupied by the voxel position. For example, a voxel 108 constituting the voxel model 107 takes a value of 1 to indicate that the space where the voxel 108 is located is occupied, while all voxels except the voxels constituting the sphere 103 and cylinder 104, for example, the voxel 109 takes a value of 0 means that the space where the voxel 109 is located is not occupied.

Voxels represent a storage method for volumetric data. By subdividing the space evenly along mutually orthogonal coordinate axes, a uniformly divided discrete grid space is formed. Objects in this voxel space are represented by a collection of voxels.

The interval between adjacent voxels determines the precision of the transformation from variable patch model to voxel model, and can be set arbitrarily.

Note that in alternative examples, the voxel model can be expressed in ways other than the regular grid described above. For example, data structures such as octrees can be used to further reduce storage space and speed up computation.

The conversion process from the polygonal patch to the voxel can adopt any method that can convert the polygonal patch model into the voxel model, and is not limited to a specific method. In one embodiment, the polygonal mesh model is voxelized using a polygonal scan conversion algorithm. This method simply needs to perform three-step judgment tests on each triangular face in the polygonal model to obtain a mathematically correct voxelization model, and can control the voxelization accuracy by setting conversion conditions.

The conversion from the polygonal patch model to the voxel model can be accelerated in any highly parallelizable way, such as but not limited to multi-processor, multi-thread, GPU processor acceleration, etc. During the parallelization process, the polygonal patches P and vertex information D of the sphere 103 and the cylinder 104 are distributed to parallel processing pipelines for voxelization. After the voxelization process in all parallel pipelines is completed, the voxel data obtained in each pipeline is aggregated to form the final voxel model.

When calculating the swept volume of the voxel model, the voxel model 107 is first copied to the world coordinate system 106 where the object motion transformation space R ^d is located, as the swept voxel model at the initial time 0 of the object motion transformation. During the copying process, all the coordinate information of each voxel in the voxel model is transformed into the world coordinate system 106 .

At the moment of motion transformation sampling t , wherein 1≤t≤l , according to the current motion transformation H(t) of the sphere 103 and the cylinder 104, recalculate the polygon patch vertex coordinate information D of the sphere 103 and the cylinder 104, and the vertices constitute a polygon Patch P , to obtain the transformed model 110 at the sampling time t .

Transform the sphere 103 and the cylinder 104 that have undergone the motion transformation H(t) at time t into a three-dimensional voxel model 111 in their own local coordinate system space 105, and copy the voxel model 111 to the object motion transformation space In the world coordinate system 106 where it is located, as shown in FIG. 4 .

The process of converting the sphere 103 and the cylinder 104 into a three-dimensional voxel model in the space of the local coordinate system 105 where it is located is accelerated by parallel computing, including but not limited to multi-processor, multi-thread, GPU processor acceleration, etc. .

Combining the 3D voxel model 111 of the sampling point at time t with the sum 112 of the 3D voxel models of all previous sampling points from 0 to t-1 combined in a manner to generate a swept volume voxel model 103 up to time t , where 1≤t≤l , as shown in FIG . 6 .

In another embodiment, the combination operation between the voxel models can also be realized by the expansion operation of the mathematical morphology operation. Mathematical morphology represents a mathematical tool for analyzing images based on morphology, and its mathematical basis and language are set theory.

The calculation process of the swept volume 3D voxel model is accelerated by parallel computing, including but not limited to multi-processor, multi-thread, GPU processor acceleration, etc.

The swept voxel model 113 at time t is three-dimensionally displayed and saved. In one embodiment, the voxel three-dimensional display method includes but not limited to direct volume rendering and voxel cube rendering. Among them, volume rendering does not draw intermediate primitives such as points, surfaces, and boundaries, but directly projects three-dimensional voxel data onto the computer screen. Depending on the implementation, volume rendering can be based on ray casting or 3D mapping. The principle of ray casting is to send a ray to each point on the screen from the viewing point of view as the origin. When the ray passes through the volume data field in the scene, the voxel falling on the ray will be from front to back (or from back to front) The RGB color and alpha value of transparency are superimposed to obtain a two-dimensional image. The method based on 3D textures represents the 3D voxel data as a series of textures on the plane, and the final 3D image is obtained by mixing the textures in a specific direction.

When displaying voxel data, multi-resolution display technology (Level of Detail) can be added to improve display speed. Multi-resolution display allows interactive processing of very large voxel data, ie a balance between display efficiency and display quality is sought. The basic idea of multi-resolution display technology is to dynamically adjust the level of detail of the object according to the distance between the current viewpoint and the observed object; when the distance is far away, a low-resolution model is selected; when the distance is short, a high-resolution model is selected, and then observed More details.

Voxel model data can be saved in any standard or custom voxel data format in the form of data stream, such as vox, raw, kv6, binvox, HIPS, MIRA, VTK and other formats. Take the binvox file as an example to illustrate the general data format of the output voxel file.

The Binvox format uses walk-length encoding to reduce file size. Each binvox file consists of an ASCII header followed by binary data.

head :

#binvox1

dim 128 128 128

translate -0.120158 -0.481158 -0.863158

scale 7.24632

data

The version number represented by the first line #binvox 1. next line dim 128 128 128 represents the length, width and height of the voxel data. The next two lines give the normalized left transformation and scaling information. The last line of data indicates the end of the header.

Each voxel in Binvox voxel data can be obtained by ( i , j , k ) coordinates relative to the ( 0 , 0 , 0 ) origin. Binvox uses the fastest way on the y-axis, followed by the z-axis, and the slowest way on the x-axis to update the index.

binary data :

The binary data following the ASCII header consists of a series of byte pairs. Each voxel corresponds to two bytes, the first byte indicates whether the voxel is empty or non-empty, and the second byte indicates how many subsequent voxels have the same value as the current voxel, that is, both empty or non-empty.

The swept voxel model can perform surface voxel extraction to generate a subset of swept voxel surface points. The extraction of surface voxels can be realized by any boundary extraction or surface contour extraction algorithm, as long as the voxels enclosed in the voxel model can be eliminated, and the voxels adjacent to the empty voxels located on the surface of the voxel model can be retained. Surface voxels can be displayed using point rendering. Point rendering uses points as the basic elements of drawing, abandons the traditional triangle slice representation method, and only records point information. These points are different from the input pixels based on image technology, but contain additional geometric information, and point sampling has nothing to do with viewpoints . In one embodiment, the QSplat algorithm of Stanford University is used to render voxels on the swept body surface. QSplat uses a tree-like hierarchical enclosing ball data structure to store data. Each node in the tree contains: the position and radius of the ball, each point The normal vector at , the width of the normal cone, and the color value. When drawing, the hierarchical tree is traversed recursively in a depth-first manner. For each intermediate node, it is first judged whether the ball is completely out of the screen or completely facing away for visibility selection. If at least part of the child nodes of the node are visible, compare the projected size of the node on the screen with a threshold, if it is greater than the threshold, continue to recurse downwards; if it is less than the threshold or has reached the leaf node , draw a small area at the position and size on the screen determined by the ball position and radius of the node. The size of the threshold can be determined dynamically according to the drawing time of the previous frame image, so as to meet the requirement of drawing frames per second specified by the user.

The surface voxel extraction of the swept volume model is accelerated by parallel computing, including but not limited to multi-processor, multi-thread, GPU processor acceleration, etc.

The swept volume voxel model 113 can carry out 3D reconstruction of the surface, generate a polygonal patch model of the swept volume surface, perform 3D display and save it. Surface 3D reconstruction can use any algorithm that can generate polygonal patches from discrete point data, including but not limited to marching cube algorithm (marching Cubes algorithm), marching tetrahedron algorithm (marching tetrahedrons algorithm), Bloomenthal polygonizer (Polygonizer), or other algorithms suitable for polygonization.

The 3D reconstruction of the swept body surface is accelerated by parallel computing, including but not limited to multi-processor, multi-thread, GPU processor acceleration, etc.

Sample instant t for all motion transformations, , generate the swept voxel model 114 of the sphere 103 and the cylinder 104 at each sampling time t , a subset of the voxel surface points of the swept voxel, and a polygonal patch model of the swept volume surface, and perform real-time three-dimensional dynamic display. Wherein, the calculation, display and storage of the swept volume voxel surface point subset and the polygonal patch model of the swept volume surface are not necessarily performed.

Experimental results

The experiment adopts the Visual C++ is used as the development platform of swept body system. Visual C++ is one of the development tools under the current Windows system. It not only provides the MFC class library, but also facilitates program compilation, and can effectively track the execution process of the program and find loopholes. In addition, Visual C++ also provides various graphic interfaces, which is convenient for secondary development, and the program code compiled with Visual C++ also has the advantage of high execution efficiency.

Autodesk's 3DS max software was used to make a three-dimensional object model for sweeping.

The three-dimensional visualization of the swept volume and its envelope is realized by using Coin3d.

In the first example of a swept body, the space swept body formed under the complex motion of the multi-link manipulator is demonstrated, as shown in Figure 8.

In the second instance of swept volume, the space swept volume produced by the moving human body in the process of going up the stairs is simulated, as shown in Figure 9. Compared with other methods for calculating swept volumes, this embodiment can generate corresponding swept volumes for more accurate bone-skinned human models, not just for simple puppet-link rigid human models. Therefore, the calculated swept volume has higher precision.

The descriptions of the embodiments herein are given as examples only and various modifications can be made by those skilled in the art. The above specification, examples and data provide a complete description of the structure and use of exemplary embodiments of the invention. While various embodiments of the invention have been described above with a certain degree of detail, or with reference to one or more single embodiments, those skilled in the art can make use of the disclosed embodiments without departing from the spirit or scope of the invention. Many modifications are made to the embodiment.

Claims (8)

1. A method for generating a spatial swept volume of an object, the method comprising the steps of:

1 st virtual object model to be sweptMExpressed in the form of polygon patch and vertex, and recording coordinate information of each vertexDAnd the connection information required by the polygon patch composed of the vertexesP；

2, as a virtual object modelMIn three-dimensional space, a time length is givenlContinuous motion transformation ofH；

No. 3, will be virtualSimulation object modelMContinuous motion transformation in three-dimensional spaceHDiscretizing sampling on a time axis, wherein each sampling point represents a certain timetMotion transformation ofH(t)Wherein；

4, sampling at motion conversion0Temporal, virtual object model representing polygon patches and verticesMIn its own local coordinate system space _localFTransfer to three-dimensional voxel model ₀VAnd modeling the voxel ₀VCopying to the world coordinate system of the object motion transformation space _worldFAs object motion transformation initiation0Swept volume voxel model of time of daySV(0)= ₀V；

5, sampling at motion conversiontAt the moment, 1 is less than or equal tot≤lFrom a virtual object modelMCurrent motion transformationH(t)Recalculating the virtual object modelMPolygon patch vertex coordinate informationDThe connection information needed by the polygon patch formed by the vertexesP；

6, converting the 5 th step through motionH(t)Virtual object model ofMIn its own local coordinate system space _localFIn-process reconversion to three-dimensional voxel model _tVAnd modeling the voxel _tVCopying to the world coordinate system of the object motion transformation space _worldFPerforming the following steps;

7, carrying out the step 6tThree-dimensional voxel model of time sampling point _tVAll of the previous0Tot-1Summation of three-dimensional voxel models of time-of-day sampling pointsBy a union operationAre combined to generatetUntil the momentSwept volume voxel model ofSV(t)=Wherein 1 is less than or equal tot≤lAnd all before0Tot-1Summation of three-dimensional voxel models of time-of-day sampling pointsIn fact, it representst-1Swept volume voxel model of time instant, i.e.SV(t-1)= ，Therefore, it is not only easy to usetTime-of-day swept volume three-dimensional voxel modelSV(t)And can be expressed as _tSV(t)= V SV(t-1)；

8 th step of generatingtTemporally swept volume voxel modelSV(t)Performing three-dimensional display and storing;

9 th step of generatingtTemporally swept volume voxel modelSV(t)Performing surface voxel extraction to generatetTemporally swept volume voxel surface point subsetsSS(t)Three-dimensional display and storage are carried out;

10 th step of generatingtTemporally swept volume voxel modelSV(t)Performing surface three-dimensional reconstruction to generatetPolygonal patch model of swept surface at timeSP(t)Three-dimensional display and storage are carried out;

11 th, sampling time for all motion transformationt，Repeating the steps 5 to 10 to generate the object modelMAt each sampling instanttSwept volume voxel model ofSV(t)Sweeping a subset of voxel surface pointsSS(t)Polygonal patch model of swept surfaceSP(t)And performing real-time three-dimensional dynamic display.

2. The method of claim 1, wherein the virtual object model of step 1MThe model combination is formed by a single object model or a plurality of object models.

3. The method according to claim 2, wherein in the model combination composed of a plurality of object models, the object models have a hierarchical relationship or a parent-child inheritance relationship with hierarchical connection.

4. The method of claim 1, wherein the virtual object model of step 1MCan be expressed in any three-dimensional model format.

5. The method of claim 4, wherein the three-dimensional model format comprises implicit surfaces, mesh surfaces, polygon patches, NURBS surfaces, spline surfaces, solid geometry.

6. The method of claim 1, wherein the continuous motion transform of step 2HIncluding aiming at the modelMAnd for vertex coordinate informationDConnection information required for forming polygon patch by vertexPA non-rigid deformation modification applied.

7. The method of claim 6, wherein the rigid transformation comprises translation, rotation, and the non-rigid deformation modification comprises: zooming, bending, twisting, extruding, shearing, vertex displacement free transformation and skinning transformation.

8. The method of claim 1, wherein step 3 is performed on the continuous motion transformHThe discretization sampling process is carried out on a time axis, and the sampling mode is equal-interval uniform sampling or variable samplingThe sampling interval and the sampling precision can be set arbitrarily.