You have just completed your registration at OpenAire.
Before you can login to the site, you will need to activate your account.
An e-mail will be sent to you with the proper instructions.
Important!
Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version
of the site upon release.
The detection of the number of disjoint components is a well-known procedure for surface objects. However, this problem has not been solved for solid models defined with scalar fields in the so-called implicit form. In this paper, we present a technique which allows for detection of the number of disjoint components with a predefined tolerance for an object defined with a single scalar function. The core of the technique is a reliable continuation of the spatial enumeration based on the interval methods. We also present several methods for separation of components using set-theoretic operations for further handling these components individually in a solid modelling system dealing with objects defined with scalar fields.
[1] B. Wyvill, A. Guy, E. Galin, Extending the CSG Tree. Warping, blending and Boolean operations in an implicit surface modeling system, Computer Graphics Forum 18 (2) (1999) 149-158.
[2] V. Adzhiev, R. Cartwright, E. Fausett, A. Ossipov, A. Pasko, V. Savchenko, HyperFun project: a framework for collaborative multidimensional F-Rep modelling, in: Proc Implicit Surfaces '99, Eurographics/ACM SIGGRAPH Workshop, J. Hughes and C. Schlick (Eds.), 1999, pp. 59-69.
[3] D. M. Mount, Intersection detection and separators for simple polygons, in: Proceedings of the eighth annual symposium on Computational geometry, SCG '92, ACM, New York, NY, USA, 1992, pp. 303-311.
[4] J. R. Rossignac, Solid and Physical Modeling, John Wiley & Sons, Inc., 2007.
[5] J. W. Boyse, Interference detection among solids and surfaces, Commun. ACM 22 (1) (1979) 3-9.
[6] R. B. Tilove, A null-object detection algorithm for constructive solid geometry, Commun. ACM 27 (7) (1984) 684-694.
[7] S. Bandi, D. Thalmann, An adaptive spatial subdivision of the object space for fast collision detection of animated rigid bodies, Computer Graphics Forum 14 (3) (1995) 259-270.
[8] J. C. Hart, Morse theory for implicit surface modeling, in: H.-C. Hege, K. Polthier (Eds.), Mathematical Visualization, Springer Berlin Heidelberg, 1998, pp. 257-268.
[9] B. T. Stander, J. C. Hart, Guaranteeing the topology of an implicit surface polygonization for interactive modeling, in: Proceedings of the 24th annual conference on Computer graphics and interactive techniques, SIGGRAPH '97, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 1997, pp. 279-286.
[11] W. Harvey, O. Rbel, V. Pascucci, P.-T. Bremer, Y. Wang, Enhanced topology-sensitive clustering by Reeb graph shattering, in: R. Peikert, H. Hauser, H. Carr, R. Fuchs (Eds.), Topological Methods in Data Analysis and Visualization II, Mathematics and Visualization, Springer Berlin Heidelberg, 2012, pp. 77-90.
[12] T. Nieda, A. Pasko, T. L. Kunii, Detection and classification of topological evolution for linear metamorphosis, The Visual Computer 22 (5) (2006) 346-356.
[14] J.-D. Boissonnat, J. Czyzowicz, O. Devillers, J. Urrutia, M. Yvinec, Computing largest circles separating two sets of segments, in: Proceedings of the 8th Canadian Conference on Computational Geometry, Carleton University Press, 1996, pp. 173-178.
[15] L. H. de Figueiredo, J. Stolfi, Self-Validated Numerical Methods and Applications, Brazilian Mathematics Colloquium monographs, IMPA/CNPq, Rio de Janeiro, Brazil, 1997.
[16] L. H. de Figueiredo, J. Stolfi, Affine arithmetic: Concepts and applications, Numerical Algorithms 37 (2004) 147-158.
[18] L. H. D. Figueiredo, J. Stolfi, Adaptive enumeration of implicit surfaces with affine arithmetic, Computer Graphics Forum 15 (1996) 287-296.
[19] J. Bloomenthal et al. (Ed.), Introduction to Implicit Surfaces, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1997.
[20] D. Kalra, A. H. Barr, Guaranteed ray intersections with implicit surfaces, SIGGRAPH Comput. Graph. 23 (3) (1989) 297-306.
[21] J. M. Snyder, Interval analysis for computer graphics, SIGGRAPH Comput. Graph. 26 (2) (1992) 121-130.
[22] A. Gomes, I. Voiculescu, J. Jorge, B. Wyvill, C. Galbraith, Implicit Curves and Surfaces: Mathematics, Data Structures and Algorithms, 1st Edition, Springer Publishing Company, Incorporated, 2009.
[23] D. Storti, C. Finley, M. Ganter, Interval extensions of signed distance functions: iSDF-reps and reliable membership classification, Journal of Computing and Information Science in Engineering 10 (2) (2010) 1-8.
[24] S. F. Frisken, R. N. Perry, A. P. Rockwood, T. R. Jones, Adaptively sampled distance fields: a general representation of shape for computer graphics, in: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, SIGGRAPH '00, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 2000, pp. 249-254.
[25] C. Ericson, Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3D Technology), Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2004.