Direct Simple Computation of Middle Surface Between 3D Point Clouds and/or Discrete Surfaces by Tracking Sources in Distance Function Calculation Algorithms

Kósa, Balázs; Mikula, Karol

doi:10.2478/tmmp-2023-0033

Abstract

In this paper, we introduce novel methods for computing middle surfaces between various 3D data sets such as point clouds and/or discrete surfaces. Traditionally the middle surface is obtained by detecting singularities in computed distance function such as ridges, triple junctions, etc. It requires to compute second order differential characteristics, and also some kinds of heuristics must be applied. Opposite to that, we determine the middle surface just from computing the distance function itself which is a fast and simple approach. We present and compare the results of the fast sweeping method, the vector distance transform algorithm, the fast marching method, and the Dijkstra-Pythagoras method in finding the middle surface between 3D data sets.

References

CHEN, X.—GOLOVINSKIY, A.—FUNKHOUSER, T.: A benchmark for 3D mesh segmentation, ACM Transactions on Graphics 28 (2009). pp. 1–12. https://doi.org/10.1145/1531326.1531379
Search in Google Scholar Back to article
CORMEN, T. H.—LEISERSON, C. E.—RIVEST, R. L.—STEIN, C.: Introduction to Algorithms Third Edition. MIT Press, Cambridge, MA, 2009.
Search in Google Scholar Back to article
DANIELSSON, P.-E.: Euclidean distance mapping, Computer Graphics and Image Processing 14 (1980), 227–248.
Search in Google Scholar Back to article
EBERLY, D.: Distance between point and triangle in 3D, Geometric Tools, Redmond WA 98052, (1999). https://www.geometrictools.com/Documentation/DistancePoint3Triangle3.pdf
Search in Google Scholar Back to article
JONES, M. W.—BAERENTZEN, J. A.—SRAMEK, M.: 3D distance fields: a survey of techniques and applications, IEEE Transactions on Visualization and Computer Graphics 12 (2006), no. 4, 581–599.
Search in Google Scholar Back to article
KIMMEL, R.—SHAKED, D.—KIRYATI, N.—BRUCKSTEIN, A. M.: Skeletonization via distance maps and level sets, Computer Vision and Image Understanding 62 (1995), 382–391.
Search in Google Scholar Back to article
PERSSON, P.-O.: Mesh Generation for Implicit Geometries. PhD Thesis, Department of Mathematics, Massachusetts Institute Of Technology, 2005.
Search in Google Scholar Back to article
ROUY, E.—TOURIN, A.: A viscosity solutions approach to shape-from-shading, SIAM Journal on Numerical Analysis 29 (1992), 867–884.
Search in Google Scholar Back to article
RUMPF, M.—TELEA, A.: A continuous skeletonization method based on level sets, Proceedings of the Symposium on Data Visualisation 2002 (2002), 151–ff.
Search in Google Scholar Back to article
SETHIAN, J. A.: A fast marching level set method for monotonically advancing fronts, Proc. Nat. Acad. Sci. U.S.A. 93 (1996), no. 4, 1591–1595.
Search in Google Scholar Back to article
SIDDIQI, K.—BOUIX, S.—TANNENBAUM, A.—ZUCKER, S.: The hamilton-jacobi skeleton. In: Proc. of the Seventh IEEE International Conference on Computer Vision (ICCV)(September 1999) Vol. 2 (1999), pp. 828-834.
Search in Google Scholar Back to article
SM´_IŠEK, M.: Analysis of 3D and 4D Images of Organisms in Embryogenesis.PhD Thesis, Faculty of Civil Engineering, Slovak University of Technology Bratislava, 2015.
Search in Google Scholar Back to article
TURK, G.—MULLINS, B.: Large Geometric Models Archive. Georgia Institute of Technology, 1999.
Search in Google Scholar Back to article
ZHAO, H.: A fast sweeping method for Eikonal equations, Math. Comput. 74 (2005), 603–627.
Search in Google Scholar Back to article

Direct Simple Computation of Middle Surface Between 3D Point Clouds and/or Discrete Surfaces by Tracking Sources in Distance Function Calculation Algorithms

Abstract

Paradigm

My account