Adaptive algorithm for polyhedral approximation of 3D solids
Keywords:
Solid mesh, regular sets, space partitioning, orthogonal projection, best approximation.Abstract
In this paper we discuss theoretical foundations of developing general methods for volume-based approximation of three-dimensional solids. We construct an iterative method that can be used for approximation of regular subsets of Rd (d 2 N) in particular R3. We will define solid meshes and investigate the connection between solid meshes, regular sets and polyhedra. First the general description of the method will be given. The main idea of our algorithm is a kind of space partitioning with increasing atomic -algebra sequences. In every step one atom will be divided into two nonempty atoms. We define a volume based distance metric and we give suffcient conditions for the convergence and monotonicity of the method. We show a possible application, a polyhedral approximation (or approximate convex decomposition) of triangular meshes.
Mathematics Subject Classification (2010): 41A35, 41A63.
References
Alliez, P., Schmitt, F., Mesh Approximation Using a Volume-Based Metric, Proceedings of 7th Pacific Conference on Computer Graphics and Applications, 1999, 292-301.
Andujar, C., Brunet, P., Ayala, D., Topology-Reducing Surface Simplification Using a Discrete Solid Representation, ACM Transactions on Graphics, 21(2002), no. 2, 88-105.
Bernstein, G., Fussel, D., Fast, Exact, Linear Booleans, Proceedings of the Symposium on Geometry Processing, 2009, 1269-1278.
Bernstein, G., Wojtan, C., Putting Holes in Holey Geometry: Topology Change for Arbitrary Surfaces, ACM Transactions on Graphics, 32(2013), no. 4.
Campen, M., Attene, M., Kobbelt, L., A Practical Guide to Polygon Mesh Repairing, ACM Transactions on Graphics, 21(2002), no. 2, 88-105.
Chazelle, B., Dobkin, D.P., Intersection of Convex Objects in Two and Three Dimensions, Journal of the ACM, 34(1987), no. 1, 1-27.
Cheney, E.W., Introduction to Approximation Theory, AMS Chelsea Pub., 1982.
Doob, J.L., Measure Theory (Graduate Text in Mathematics), Springer, 1994.
Ericson, C., Real-Time Collision Detection, Elsevier, 2005.
Foley, J.D. et al., Computer Graphics: Principles and Practice (Second Edition in C), Addison-Wesley, 1995.
Ghali, S., Introduction to Geometric Computing, Springer, 2008.
Ghosh, M. et al., Fast approximate convex decomposition using relative concavity, Computer-Aided Design, 45(2013), no. 2, 494-504.
Fabian, G., Gergo, L., Fast Algorithm to Split and Reconstruct Triangular Meshes, Studia Univ. Babes-Bolyai, Informatica, Special Issue 1(2014), 90-102.
Goodman, J.E., O'Rourke, J., Handbook of Discrete and Computational Geometry, Chapman & Hall/CRC, 2004.
Lee, J.M., Introduction to Topological Manifolds, Springer, 2011.
Muller, M., Chentanez, N., Kim, T., Real Time Dynamic Fracture with Volumetric Approximate Convex Decompositions, ACM Transactions on Graphics, 32(2013), no. 4, Art.
no. 115.
Natanson, I.P., Constructive Function Theory (Vol. I. Uniform Approximation), Frederick
Ungar Publishing Co., 1964.
Neveu, J., Discrete Parameter Martingales, Elsevier, 1975.
Owen, S.J., A Survey of Unstructured Mesh Generation Technology, International Meshing Roundtable, 1998, 239-267.
Requicha, A.A.G., Representations for Rigid Solids: Theory, Methods and Systems, ACM Computing Surveys - CSUR, 12(1980), no. 4, 437-464.
Schipp, F., On Adapted Orthonormed Systems, East Journal on Approximation, 6(2000), no. 2, 157-188.
Tate, S.R., Xu, K., Chapman & Hall/CRC, 2004.
Taylor, M.E., Measure Theory and Integration, Graduate Studies in Mathematics, 76(2006).
https://graphics.stanford.edu/software/scanview/models/bunny.html, 2014.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2015 Studia Universitatis Babeș-Bolyai Mathematica
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
