This article describes three algorithms for distance field generation on triangulated model: brute force algorithm, single-threaded algorithm based on spatial partition and multi-threaded algorithm based on spatial pa...This article describes three algorithms for distance field generation on triangulated model: brute force algorithm, single-threaded algorithm based on spatial partition and multi-threaded algorithm based on spatial partition. Spatial partition algorithm use equidistant network divide the bounding box into equal-sized cubes, calculates the maximum and minimum distances between the sample point and each of the small cubes,taking the minimum value from the maximum distance as the minimum distance from the sample point to the model named d1, comparing d1 with the distance from sample point to every little cube's minimum distance d2, if d1 <d2, the sample point's distance to all triangles inside this cube are greater than d1, skip this cube, otherwise, calculated the distance from the point to all the triangles intersect with the cube, then alternative d1 with the minimum value, circulate all small cubes intersect with the model. Comparing the calculation results, it can be seen that the algorithm about the multi-threaded distance field relative to the other two algorithms in computational speed is greatly improved especially for complex models.展开更多
Taking advantage of the characteristic of distance field and octree, we brought up a method which can discrete any triangle-geometry into voxel. As many triangles used for cutting simulation are unoriented, non-manifo...Taking advantage of the characteristic of distance field and octree, we brought up a method which can discrete any triangle-geometry into voxel. As many triangles used for cutting simulation are unoriented, non-manifold or self-intersecting, which leads to ambiguity in mathematical terms. The algorithm firstly computes sign distance field and use the threshold value to reconstruct the surface, which is very close to the original mode. At last, the reconstructed surface is voxelized. Also we can produce voxelized model which is suitable for cutting simulation.展开更多
文摘This article describes three algorithms for distance field generation on triangulated model: brute force algorithm, single-threaded algorithm based on spatial partition and multi-threaded algorithm based on spatial partition. Spatial partition algorithm use equidistant network divide the bounding box into equal-sized cubes, calculates the maximum and minimum distances between the sample point and each of the small cubes,taking the minimum value from the maximum distance as the minimum distance from the sample point to the model named d1, comparing d1 with the distance from sample point to every little cube's minimum distance d2, if d1 <d2, the sample point's distance to all triangles inside this cube are greater than d1, skip this cube, otherwise, calculated the distance from the point to all the triangles intersect with the cube, then alternative d1 with the minimum value, circulate all small cubes intersect with the model. Comparing the calculation results, it can be seen that the algorithm about the multi-threaded distance field relative to the other two algorithms in computational speed is greatly improved especially for complex models.
文摘Taking advantage of the characteristic of distance field and octree, we brought up a method which can discrete any triangle-geometry into voxel. As many triangles used for cutting simulation are unoriented, non-manifold or self-intersecting, which leads to ambiguity in mathematical terms. The algorithm firstly computes sign distance field and use the threshold value to reconstruct the surface, which is very close to the original mode. At last, the reconstructed surface is voxelized. Also we can produce voxelized model which is suitable for cutting simulation.