×

Fast equal and biased distance fields for medial axis transform with meshing in mind. (English) Zbl 1228.76070

Summary: A method for robust and efficient medial axis transform (MAT) of arbitrary domains using distance solutions (or level sets) is presented. The distance field, \(d\), is calculated by solving the hyperbolic-natured eikonal equation. The solution is obtained on Cartesian grids. Both the fast-marching method (FMM) and fast-sweeping method (FSM) are used to calculate \(d\). Medial axis point clouds are then extracted based on the distance solution via a simple criterion: the Laplacian or the Hessian determinant of \(d(x)\). These point clouds in the pixel/voxel space are further thinned to single pixel wide so that medial axis curves or surfaces can be connected and splined. As an alternative to other methods, the current \(d\)-MAT procedure bypasses difficulties that are usually encountered by pure geometric methods (e.g. the Voronoi approach), especially in three dimensions, and provides better accuracy than pure thinning methods. It is also shown that the \(d\)-MAT approach provides the potential to sculpt/control the MAT form for specialized solution purposes. Various examples are given to demonstrate the current approach.

MSC:

76F65 Direct numerical and large eddy simulation of turbulence
65M06 Finite difference methods for initial value and initial-boundary value problems involving PDEs
76M20 Finite difference methods applied to problems in fluid mechanics

Software:

DiFi
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fares, E.; Schröder, W., A differential equation for approximate wall distance, Int. J. Numer. Methods Fluids, 39, 743-762 (2002) · Zbl 1010.76073
[2] Tucker, P. G., Differential equation-based wall distance computation for DES and RANS, J. Comput. Phys., 190, 1, 229-248 (2003) · Zbl 1236.76028
[3] Osher, S.; Sethian, J. A., Fronts propagating with curvature dependent speed: algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys., 79, 12-49 (1988) · Zbl 0659.65132
[4] P.G. Tucker, C.L. Rumsey, R.E. Bartels, R.T. Biedron, Transport equation based wall distance computations aimed at flows with time-dependent geometry. NASA-TM 2003-212680, Dec 2003.; P.G. Tucker, C.L. Rumsey, R.E. Bartels, R.T. Biedron, Transport equation based wall distance computations aimed at flows with time-dependent geometry. NASA-TM 2003-212680, Dec 2003.
[5] Sethian, J. A.; Smereka, P., Level set methods for fluid interfaces, Annu. Rev. Fluid Mech., 35, 1, 341-372 (2003) · Zbl 1041.76057
[6] Sethian, J., Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science (1999), Cambridge University Press · Zbl 0973.76003
[7] Tucker, P. G.; Rumsey, C. L.; Spalart, P. R.; Bartels, R. E.; Biedron, R. T., Computation of wall distances based on differential equations, AIAA J., 43, 3 (2005)
[8] Zhao, H., A fast sweeping method for eikonal equations, Math. Comput., 74, 250, 603-627 (2004) · Zbl 1070.65113
[9] Elias, R. N.; Martins, M. A.D.; Coutinho, A. L., Simple finite element-based computation of distance functions in unstructured grids, Int. J. Numer. Meth. Eng., 72, 1095-1110 (2007) · Zbl 1194.65145
[10] Li, T. S.; Mckeag, R. M.; Armstrong, C. G., Hexahedral meshing using midpoint subdivision and integer programming, Comput. Methods Appl. Mech. Eng., 124, 171-193 (1995)
[11] Price, M. A.; Armstrong, C. G., Hexahedral mesh generation by medial surface subdivision: Part II. Solids with flat and concave edges, Int. J. Numer. Methods Eng., 40, 111-136 (1997)
[12] W. Quadros, K. Ramaswami, F.B. Prinz, B. Gurumoorthy, Laytracks: a new approach to automated quadrilateral mesh generation using mat. in: 9th International Meshing Roundtable, 2000, pp. 239-250.; W. Quadros, K. Ramaswami, F.B. Prinz, B. Gurumoorthy, Laytracks: a new approach to automated quadrilateral mesh generation using mat. in: 9th International Meshing Roundtable, 2000, pp. 239-250. · Zbl 1079.74649
[13] W. Quadros, S.J. Owen, M. Brewer, K. Shimada, Finite element mesh sizing for surfaces using skeleton, in: 13th International Meshing Roundtable, 2004, pp. 389-400; W. Quadros, S.J. Owen, M. Brewer, K. Shimada, Finite element mesh sizing for surfaces using skeleton, in: 13th International Meshing Roundtable, 2004, pp. 389-400
[14] D.L. Rigby. Topmaker: A technique for automatic multi-block topology generation using the medial axis, NASA/CR 2004-213044, Apr 2004.; D.L. Rigby. Topmaker: A technique for automatic multi-block topology generation using the medial axis, NASA/CR 2004-213044, Apr 2004.
[15] H. Du, H. Qin. Medial axis extraction and shape manipulation of solid objects using p arabolic pdes, in: SM ’04: Proceedings of the ninth ACM symposium on Solid modeling a nd applications, Eurographics Association, Aire-la-Ville, Switzerland, 2004, pp. 25-35.; H. Du, H. Qin. Medial axis extraction and shape manipulation of solid objects using p arabolic pdes, in: SM ’04: Proceedings of the ninth ACM symposium on Solid modeling a nd applications, Eurographics Association, Aire-la-Ville, Switzerland, 2004, pp. 25-35.
[16] M. Foskey, M.C. Lin, D. Manocha. Efficient computation of a simplified medial axis, in: SM ’03: Proceedings of the eighth ACM symposium on Solid modeling and applications, ACM, New York, NY, USA, 2003, pp. 96-107.; M. Foskey, M.C. Lin, D. Manocha. Efficient computation of a simplified medial axis, in: SM ’03: Proceedings of the eighth ACM symposium on Solid modeling and applications, ACM, New York, NY, USA, 2003, pp. 96-107.
[17] Y. Yang, O. Brock, R.N. Moll. Efficient and robust computation of an approximated medial axis, in: Proceedings of the ACM Symposium on Solid Modeling and Applications, 2004, pp. 15-24.; Y. Yang, O. Brock, R.N. Moll. Efficient and robust computation of an approximated medial axis, in: Proceedings of the ACM Symposium on Solid Modeling and Applications, 2004, pp. 15-24.
[18] Chou, J. J., Voronoi diagrams for planar shapes, IEEE Comput. Graph. Appl., 15, 20, 52-59 (1995)
[19] Näf, M.; Székely, G.; Kikinis, R.; Shenton, M. E.; Kübler, O., 3d voronoi skeletons and their usage for the characterization and recognition of 3d organ shape, Comput. Vis. Image Underst., 66, 2, 147-161 (1997)
[20] P.Y. Ang, C.G. Armstrong, Adaptive curvature-sensitive meshing of the medial axis, in: 10th International Meshing Roundtable, Sandia National Laboratories, Oct 7-10, 2001, pp. 155-165.; P.Y. Ang, C.G. Armstrong, Adaptive curvature-sensitive meshing of the medial axis, in: 10th International Meshing Roundtable, Sandia National Laboratories, Oct 7-10, 2001, pp. 155-165.
[21] T.K. Dey, W. Zhao, Approximate medial axis as a voronoi subcomplex, in: SMA ’02: Proceedings of the seventh ACM symposium on Solid modeling and applications, ACM, New York, NY, USA, 2002, pp. 356-366.; T.K. Dey, W. Zhao, Approximate medial axis as a voronoi subcomplex, in: SMA ’02: Proceedings of the seventh ACM symposium on Solid modeling and applications, ACM, New York, NY, USA, 2002, pp. 356-366.
[22] Ahuja, N.; Chuang, J.-H., Shape representation using a generalized potential field model, IEEE Trans. Pattern Anal. Mach. Intell., 19, 2, 169-176 (1997)
[23] M. Rumpf, A. Telea, A continuous skeletonization method based on level sets, in: VISSYM ’02: Proceedings of the symposium on Data Visualisation 2002, Eurographics Association, Aire-la-Ville, Switzerland, 2002, pp. 151-ff.; M. Rumpf, A. Telea, A continuous skeletonization method based on level sets, in: VISSYM ’02: Proceedings of the symposium on Data Visualisation 2002, Eurographics Association, Aire-la-Ville, Switzerland, 2002, pp. 151-ff.
[24] Sud, A.; Otaduy, M. A.; Manocha, D., Difi: fast 3d distance field computation using graphics hardware, In Eurograph., 557-566 (2004)
[25] Cao, L.; Jia, Z.; Liu, J., Computation of medial axis and offset curves of curved boundaries in planar domains based on the cesaro’s approach, Comput. Aided Geomet. Design (2009) · Zbl 1205.65115
[26] Lam, L.; Lee, S.-W.; Suen, C. Y., Thinning methodologies-a comprehensive survey, IEEE Trans. Pattern Anal. Mach. Intell., 14, 9, 869-885 (1992)
[27] Sheehy, D. J.; Armstrong, C. G.; Robinson, D. J., Shape description by medial surface construction, IEEE Trans. Visualiz. Comput. Graph., 2, 1, 62-72 (1996) · Zbl 0879.68108
[28] Mikolajczyk, K.; Schmid, C., Scale & affine invariant interest point detectors, Int. J. Comput. Vision, 60, 1, 63-86 (2004)
[29] Ait-Ali-Yahia, D.; Habashi, W. G.; Tam, A.; Vallet, M.-G.; Fortin, M., A directionally adaptive methodoloty using an edge-based error estimate on quadrilateral grids, Int. J. Numer. Methods Fluids, 23, 7, 673-690 (1998) · Zbl 0884.76036
[30] Qin, N.; Liu, X., Flow feature aligned grid adaptation, Int. J. Numer. Methods Eng., 67, 6, 62-72 (2006) · Zbl 1113.76059
[31] Guo, Z.; Hall, R. W., Parallel thinning with two-subiteration algorithms, Commun. ACM, 32, 3, 359-373 (1989)
[32] Palágyi, K., A 3D fully parallel surface-thinning algorithm, Theor. Comput. Sci., 406, 1-2, 119-135 (2008) · Zbl 1160.68045
[33] Dijkstra, E., A note on two problems in connection with graphs, Numer. Math., 1, 269-271 (1959) · Zbl 0092.16002
[34] Atkinson, M. D.; Sack, J.-R.; Santoro, B.; Strothotte, T., Min-max heaps and generalized priority queues, Commun. ACM, 29, 10, 996-1000 (1986) · Zbl 0642.68055
[35] Jeong, W.-K.; Whitaker, R. T., A fast iterative method for eikonal equations, SIAM J. Sci. Comput., 30, 5, 2512-2534 (2008) · Zbl 1246.70003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.