Multi-threaded Fast Distance Field Computation Using Spatial Partition

MIN De-heng JIA Shi-yu ZHANG Xiao-yun

(Qingdao University,Qingdao Shandong 266071,China)

0 Introduction

Distance field is a basic model representation of computer graphics,initially drawn to the body surface and establishment the offset in computer graphics.Distance field is a scalar field,represents a region of the inner surface of a certain minimum distance of all points of the object are similar[1].If the surface is closed,then the distance can bring sign which represents the external or internal objects.Many researchers have proposed a variety of different data structures to represent the distance field.For example,a uniform 3D mesh,octrees,BSP-tree,and so on[2].In recent years,the graphical representation of the object distance field has been widely used in the field of computer graphics.such as threedimensional object deformation,texture mapping,estimated extraction,collision detection.Comprehensive comparison of domestic and international distance field is generated and stored in the structure calculation methods used in the algorithm.In this paper,proposed a a new distance field generation algorithm,this algorithm ensuring operational efficiency and significantly reducing storage space.

1 The basic definition of distance field

Definition 1 Any of a set of three-dimensional space∑,at any point within the space p∈R3to the collection∑ of the nearest point in the unsigned distance field is expressed as.

Definiton 2 Suppose S is a closed surface collections,the functiondefine any point p∈R3about the nearest point to the closed surface S of the signed distance field,among them

2 Unsigned distance field Calculation

A fast and efficient algorithm for generating the distance field requires two conditions:First,the rapid calculation of the distance field function;Second is the right distance field storage mechanism.When reading an existing OBJ model file,read out the information related to the model and the surface vertex information and stored prior to a good set data structure[3].In order to facilitate OpenGL processing and display the relevant data,all the faces of the OBJ model are decomposed into triangles for storage,that is,sequential storage the three vertices of the triangle.

2.1 Brute force algorithm about calculate the distance field

This article uses the lattice method,first draw a cube around the model bounding box,when reading OBJ model file can obtain the maximum value of the coordinates of all the points,bounding box coordinates of the boundary can just take a slightly larger than the maximum,and then divide the bounding box into several cube lattice,then calculate the distance field of sample points[4].Bounding box can be subdivided lattice and adjust the fineness of the crystal lattice by custom width,we can also calculate the amount of indirect control.Brute force computing is loop through all distance field sampling points in the traverse space,and then calculate all points’ minimum distance to the model.Because all of the faces in the model are decomposed into triangles,therefore,a sample point P to the inner space,the minimum distance calculation point P to OBJ model is to calculate the minimum distance of the point to all the triangles in the model.

2.2 Spatial Partition

The basic idea to spatial partition is:The entire space scene along the x,y,z-axis is divided into a series of rows of cells.And only a cell asked questions are related to the calculation.The selection of a data structure shows the 3D space is important,this data structure on the computation time and storage must be flexible and efficient.In this paper,equidistant network segmentation,divide the space into equalsized cubes.After the object model spatial partition,use the array to store the information ofthe cubeswhich triangle intersectwith with tetrahedron.For all the triangles in the model and not intersecting small cubes without storage,in order to save storage space and computing time.Get sample point position in world space then calculate minimum and maximum distances from sample point to filled spatial partition cells and mark the cell with smallest maximum distance,which assumed as the minimum distance from the point P to the model named d1.Then compare all the minimum distance from the point P to the small cubes with the minimum distance d1.If d1 is greater than the minimum distance of a point P to the cube,calculate the distance from the point P to all the triangles intersect with the cube and take all the minimum of the minimum distance alternative d1 as the minimum distance between the point P to the model.If d1 is less than the minimum distance between the point P to a cube,then the distance from the point P to all the triangles intersect with the cube will be larger than d1,ignore the cell because its minimum distance to sample points is larger than current distance field value.Loop through all the cells and set minimum distance as distance field value.

3 Distance Field Sign Compution

After the completion of the unsigned distance field computation,then need to further determine the sign of the distance field,which can characterize the point is outside or inside the body of the object.Generally,when the point outside the object the field is positive,when the point is located inside the model the distance is negative.A value of zero field located at the surface.This article uses the scan line filling algorithm to calculate the intersection about the boundary with the rays,the rays’initial position in the external model,the initial sign of the distance field as positive.If the ray intersects with the boundary,then change the distance field symbol as negative,until the completion of the scan,then determine the ultimate sign of the distance field in the ray direction.We transmitted light through 26 in different directions(3D model),ray directions are(1,0,0),(-1,0,0),(0,1,0),(0,-1,0),(0,0,1),(0,0,-1),(0,1,1),(0,1,-1),(0,-1,1),(0,-1,-1),(1,0,1),(1,0,-1),(-1,0,1),(-1,0,-1),(1,1,0),(1,-1,0),(-1,1,0),(-1,-1,0),(1,1,1),(1,1,-1),(1,-1,1),(1,-1,-1),(-1,1,1),(-1,1,-1)，(-1,-1,1),(-1,-1,-1).After judge the 26 direction of ray intersection,analyzing 26 direction can be obtained for each point on how many times the determination is negative.We set the threshold of the number of symbols judge 13,this means that if there are 26 judges in the 13th judge sign is negative then this point distance field is negative.

4 Calculating Distance Field Using Spatial Partition of single-threaded and multi-threaded

Relative to the brute-force calculation,distance field generation algorithm based on spatial partition effectively improve the computing speed of distance field,in order to better compare,specially selected single-threaded calculation method based on the spatial partition.Because for calculating the distance between the field at any point in the space is independently of each other,therefore,this paper uses multiple threads to all points in the space of distance field calculations.After the program runs,read the computer processor cores,choose no more than the number of parallel threads of computer processor cores,multithreaded computing the minimum distance from all points to the model.

5 Implementation and results

To make it easier to generate the distance field observation,in this paper,the use of red,blue and green color rendering distance field value.When the distance field with a red sign is positive,the distance field is negative symbol blue,when the point at the surface of the model rendered in green.According to the model of the information read to set the vertical slice in X,Y,Z axis,slice size slightly larger than the model on the slice plane X,Y,Z axis length.Control slices moving direction,to observe the changes in each slice layer on the object distance field according to the color change.Run results are shown as in Table 1.

6 Conclusion

By analyzing the results of the calculation of the distance field,known for the same model,in the same grid distance,calculated based on the space division of the single-threaded distance field generation algorithm computing time is much less than brute force.Computing time than the single-threaded multi-threaded space-based segmentationalgorithm to generate the distance field has also been greatly improved.Especially in a larger number of models under the number of vertices and faces situations,space-based segmentation of multi-threaded distance field generation algorithm to calculate the distance to the brute force field generation algorithm has been greatly improved in the computing speed.

Tab.1 The results of three algorithms for distance field generation

[1]Wang Yanlin.Deformable body collision detection algorithm to generate the distance field[D].Central China Normal University,2008.

[2]Zhao Sen.Research and Application of collision detection distance field algorithm[D].Jilin University,2008.

[3]Li Jun.Point to the triangle mesh body signed distance calculation[D].Jiangnan University,2007.

[4]B?rentzen JA,Aan?s H.Generating signed distance fieldsfrom triangle meshes[J].Informatics and Mathematical Modeling,Technical University of Denmark,DTU,2002,20.