×

Consistently oriented dart-based 3D modelling by means of geometric algebra and combinatorial maps. (English) Zbl 1452.68248

Summary: The modelling of real world objects is not a straightforward subject. There are many different schemes; constructive solid geometry (CSG), cell decomposition, boundary representation, etcetera. Obviously, somehow, any scheme will be related to any other since they have a common goal. The paper shows how to model general polyhedra as an unordered discrete and finite set of geometric numbers of a projective Clifford algebra or geometric algebra (GA). Clearly, not any randomly generated finite set of geometric numbers will have the structure of an object, this set must have some well defined properties. The topological properties extracted from this set are mapped to a boundary representation scheme based on a type of combinatorial map called generalised map or \(n\)-gmap. The \(n\)-gmaps have different types of orbits (in the mathematical sense) to which an attribute can be attached. When the attribute has a geometrical meaning, it is said that it is the geometrical embedding of the \(n\)-gmap. In this way the \(n\)-gmap holds explicitly the topology or structure already defined by the discrete geometry. In our proposal, each single element of a \(n\)-gmap is consistently embedded into a geometrical number also known as multi-vector. The scheme has been implemented by modifying an open source code (http://moka-modeller.sourceforge.net/) of \(n\)-gmaps. This representation has interesting properties. GA and \(n\)-gmaps complement and reinforce each other. For instance; it improves the robustness when computing the structure from the geometrical information. It is capable of computing lengths, areas and volumes of any polyhedral complex (with or without holes) using the orbits of the \(n\)-gmap (some examples are given). Finally the paper gives hints about other potentialities.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
15A66 Clifford algebras, spinors
51M20 Polyhedra and polytopes; regular figures, division of spaces
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alayrangues, S., Damiand, G., Lienhardt, P., Peltier, S.: A Boundary Operator for Computing the Homology of Cellular Structures, Technical report, 71 pages, (2011). HAL id: hal-00683031, https://hal.archives-ouvertes.fr/hal-00683031. Accessed 07 May 2018 · Zbl 1331.68241
[2] Alayrangues, S., Daragon, X., Lachaud, J., Lienhardt, P.: Equivalence between closed connected n-G-maps without multi-incidence and n-surfaces. J. Math. Imaging Vis. 32, 122 (2008). https://doi.org/10.1007/s10851-008-0084-3 · Zbl 1113.68568 · doi:10.1007/s10851-008-0084-3
[3] Alayrangues, S., Fuchs, L., Lienhardt, P., Peltier, S.: Incremental Computation of the Homology of Generalized Maps: An Application of Effective Homology Results, (2015). HAL id: hal-01142760v2 https://hal.archives-ouvertes.fr/hal-01142760. Accessed 07 May 2018
[4] Baig, S.U., Alizadehashrafi, B.: 3D Generalization of Boundary Representation (B-Rep) of Buildings, FIG Congress 2014, Kuala Lumpur, Malaysia, 16-21 June (2014)
[5] Bellet, T., Arnould, A., Charneau, S., Fuchs, L.: Modélisation nD à base d’algèbres géométriques, (2008) HAL id: hal-00354183 https://hal.archives-ouvertes.fr/hal-00354183. Accessed 07 May 2018
[6] Bellet, T., Arnould, A., Fuchs, L.: Polyhedral embedding of a topological structure. Applied Geometric Algebras in Computer Science and Engineering (AGACSE 2010), Amsterdam, Netherlands (2010) HAL id: hal-00488183 https://hal.archives-ouvertes.fr/hal-00488183. Accessed 07 May 2018
[7] Braulio-Gonzalo, M., Bovea, M.D.: Environmental and cost performance of buildings envelope insulation materials to reduce energy demand: Thickness optimisation. Energy Build. 150, 527-545 (2017). https://doi.org/10.1016/j.enbuild.2017.06.005 · doi:10.1016/j.enbuild.2017.06.005
[8] Brisson, E.: Representing geometric structures in d dimensions: topology and order. Discrete Comput. Geometry 9, 387426 (1993) · Zbl 0783.68129 · doi:10.1007/BF02189330
[9] Chard, J.A., Shapiro, V.: A multivector data structure for differential forms and equations. Math. Comput. Simul. 54, 3364 (2000). https://doi.org/10.1016/S0378-4754(00),00198-1 · doi:10.1016/S0378-4754(00),00198-1
[10] Chaïm Zonnenberg, PhD. thesis: Conformal Geometric Algebra Package, Utrecht University Department of Information and Computing Sciences, (July 23, 2007)
[11] Chisolm, E.: Geometric Algebra, (2012) arXiv: 1205.5935v1 [math-ph]
[12] Conradt, O.: Mathematical physics in space and counterspace,(Arbeitshefte, KLEINE REIHE, Band 4), Mathematisch-Astronomische Sektion am Goetheanum und Verlag am Goetheanum, CH-4143 Dornarch, (2008), ISBN-13: 978-3723513330
[13] Conradt, O.: Mechanics in space and counterspace, Journal of Mathematical Physics 41 (6995-7028) (Oct 2000). https://doi.org/10.1063/1.1288495 · Zbl 0988.70014
[14] Crawley, D.B., Lawrie, L.K., Winkelmann, F.C., Buhl, W.F., Huang, Y.J., Pedersen, C.O., Strand, R.K., Liesen, R.J., Witte, D.E.J. Glazer, J.: EnergyPlus: creating a new-generation building energy simulation program. Energy Build. 33(4), 319-331 (2001) https://energyplus.net/. Accessed 07 May 2018
[15] Damiand, G., Lienhardt, P.: Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing. CRC Press, Boca Raton, (2015), ISBN: 978-1-4822-0653-1 · Zbl 1305.68012
[16] Damiand, G., Teillaud, M.: A Generic Implementation of dD Combinatorial Maps in CGAL, International Meshing Roundtable, Oct 2014, Londres, United Kingdom. 82, pp.46 - 58, (2014), https://doi.org/10.1016/j.proeng.2014.10.372 HAL id: hal-01090011 http://doc.cgal.org/ (Linear Cell Complex). Accessed 07 May 2018
[17] Damiand, G.: Contributions aux Cartes Combinatoires et Cartes Généralises : Simplification, Modèles, Invariants Topologiques et Applications, HAL Id: tel-00538456 (2010)
[18] Diakité, A.A., Damiand, G., Maercke, D.V.: Topological reconstruction of complex 3d buildings and automatic extraction of levels of detail, Eurographics Workshop on Urban Data Modelling and Visualisation.(Strasbourg, France.), hal-01011376, pp. 25-30, (2014). https://doi.org/10.2312/udmv.20141074https://hal.archives-ouvertes.fr/hal-01011376. Accessed 07 May 2018
[19] Dorst, L., Fontijne, D., Mann, S.: Geometric Algebra for Computer Science: An Object-oriented Approach to Geometry, A volume in The Morgan Kaufmann Series in Computer Graphics, (2007). ISBN: 978-0-12-369465-2
[20] Dorst, L.: 3D Oriented Projective Geometry Through Versors of \[{\mathbb{R}}^{3,3}\] R3,3, Advances in Applied Clifford Algebras, https://doi.org/10.1007/s00006-015-0625-y · Zbl 1379.51001
[21] Fradin, D., Meneveaux, D., Lienhardt, P.: Hierarchy of generalized maps for modeling and rendering complex indoor scenes, Tech. Rep., Rapport de recherche No 2005-04, Signal Image Communication laboratory, CNRS, University of Poitiers, France (November 2005)
[22] Francés, V.M.S.: Modified version of MOKA implementing the GA method presented in this paper, https://github.com/vsotofrances/MOKACLIFFORD/tree/multivect. Accessed 07 May 2018
[23] Franklin, W.R.: Polygon properties calculated from the vertex neighborhoods, in: N. ACM New York (Ed.), Proceeding SCG ’87, Proceedings of the third annual symposium on Computational geometry, (1987) ISBN:0-89791-231-4 https://doi.org/10.1145/41958.41969https://www.ecse.rpi.edu/ wrf/Research/Short_Notes/volume.html. Accessed 07 May 2018
[24] Genera3D, automation of the 3D model creation of a building, http://vpclima2.ter.upv.es/. Accessed 07 May 2018
[25] Gunn, C.: Guide to Geometric Algebra in Practice. (Chapter: On the Homogeneous Model of Euclidean Geometry) Ed. Leo Dorst & Joan Lasenby,Springer-Verlag London Limited (2011), ISBN: 978-0-85729-810-2 https://doi.org/10.1007/978-0-85729-811-9 · Zbl 1291.15066
[26] Gunn, C.: On the Homogeneous Model Of Euclidean Geometry. arXiv:1101.4542 [math.MG]. Accessed 07 May 2018 · Zbl 1291.15066
[27] Hestenes, D., Sobczyk, G.: Clifford Algebra to Geometric Calculus: A Unified Language for Mathematics and Physics, D. Reidel Publishing Company, : ISBN-13: 978-9027725615. ISBN- 10, 9027725616 (1984) · Zbl 0541.53059
[28] Hestenes, D., Ziegler, R.: Projective geometry with clifford algebra. Acta Appl. Math. 23, 25-63 (1991) · Zbl 0735.51001 · doi:10.1007/BF00046919
[29] Hitzer, E.: Introduction to Clifford’s geometric algebra. J. Soc. Instrum. Control Eng. 51(4), 338-350 (2012). arXiv:1306.1660. Accessed 07 May 2018
[30] HULC, Unified Tool LIDER-CALENER, Version 1.0.1493.1049. http://www.codigotecnico.org/index.php/menu-recursos/menu-aplicaciones/282-herramienta-unificada-lider-calener (2016). Accessed 01 July 2016
[31] Kraemer, P., Untereiner, L., Jund, T., Thery, S., Cazier, D.: CGoGN:n-dimensional Meshes with Combinatorial Maps, J. Sarrate & M. Staten (eds.). In: Proceedings of the 22nd International Meshing Roundtable, Springer International Publishing Switzerland (2013) https://doi.org/10.1007/978-3-319-02335-9_27https://github.com/cgogn/CGoGN. Accessed 07 May 2018
[32] Li, H., Huang, L., Shao, C., Dong, L.: Three-Dimensional Projective Geometry with Geometric Algebra, (2015). arXiv:1507.06634v1
[33] Lienhardt, P.: Topological models for boundary representation: a comparison with n-dimensional generalized maps. Comput. Aided Des. 23(1), 59-82 (1991). https://doi.org/10.1016/0010-4485(91)90082-8 · Zbl 0754.65018 · doi:10.1016/0010-4485(91)90082-8
[34] Lienhardt, P.: N-dimensional generalized combinatorial maps and cellular quasi-manifolds. Int. J. Comput. Geom. Appl. 4(3), 275324 (1994). https://doi.org/10.1142/S0218195994000173 · Zbl 0821.57016 · doi:10.1142/S0218195994000173
[35] OFF 3D graphics data format. http://paulbourke.net/dataformats/. Accessed 07 May 2018
[36] Pappas, R.: Chapter: Oriented projective geometry with Clifford Algebra, in book titled, Clifford algebras with numeric and symbolic computations, Editors Rafal Ablamowicz, Pertti Lounesto, Josep M. Parra, Birkhäuser, (1996) ISBN: 978-1-4615-8159-8, ISBN 978-1-4615-8157-4 (eBook) https://doi.org/10.1007/978-1-4615-8157-4
[37] Sokolov, A.: A key to projective model of homogeneous metric spaces, (2014) arXiv:1412.8095v1 [math.MG]
[38] Sokolov, A.: Clifford algebra and the projective model of Elliptic spaces, (2013) arXiv:1310.2713v1 [math.MG]
[39] Sokolov, A.: Clifford algebra and the projective model of homogeneous metric spaces: Foundations, (2013) arxiv:1307.2917v1 [math.MG]
[40] Sokolov, A.: Clifford algebra and the projective model of Hyperbolic spaces (2016) arXiv:1602.08562v1 [math.MG]
[41] Sokolov, A.: Clifford algebra and the projective model of Minkowski (pseudo-Euclidean) spaces (2013) arXiv:1307.4179v2 [math.MG]
[42] Stein, P.: geoma v1.2.2007.08.20, C++ software, http://nklein.com/tags/geoma/. Accessed 07 May 2018
[43] Stolfi, J.: Oriented Projective Geometry. A Framework for Geometric Computations , 1st Edition ISBN 9781483265193 , Academic Press, Published 28th July 1991 · Zbl 0732.51003
[44] Stolfi, J.: Primitives for computational geometry, Technical report SRC-RR-36, Systems research center (January 27 1989). http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-36.html. Accessed 07 May 2018
[45] Tonti, E.: Why starting from differential equations for computational physics? J. Comput. Phys. 257, 1260-1290 (2014). https://doi.org/10.1016/j.jcp.2013.08.016 · Zbl 1351.35002 · doi:10.1016/j.jcp.2013.08.016
[46] Vidil, F., Damiand, G., Dexet-Guiard, M., Guiard, N., Ledoux, F., Fousse, A., Fradin, D., Liang, Y., Meneveaux, D., Bertrand, Y.: MOKA. http://moka-modeller.sourceforge.net/ (2002). Accessed 07 May 2018
[47] Zonnenberg, C.: Conformal Geometric Algebra Package, (2007), http://www.cs.uu.nl/groups/MG/gallery/CGAP/index.html. Accessed 07 May 2018
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.