Eötvös Loránd University

Faculty of Informatics

Department of Numerical Analysis

Computational models and approximationmethods of three dimensional solids and surfaces

Theses of the PhD Dissertation

Gábor Fábián

Supervisors: Lajos Gergó, associate professor, PhDFerenc Weisz, full professor, DSc

Budapest, 2020

Doctoral School: ELTE Doctoral School of InformaticsHead of School: Erzsébet Csuhaj-Varjú, full professor, DScDoctoral Program: Numeric and Symbolic CalculusHead of Program: Ferenc Weisz, full professor, DSc

1 Gábor Fábián

Introduction

In my PhD dissertation I was dealing with mathematical models, compu-tational representations and approximation methods of solids and surfaces inparticular focusing on computer applications.

In general the users of computer graphics systems do not keep in mind thecorrectness or simplicity of a graphics model of some surface, the only prefer-ence is the preservation of the visual information. Unfortunately many weirdphenomena can be observed in dynamic simulation as well as in illuminationbecause of the incorrectness of the model.

Ensuring the proper behaviour of the physics based algorithms it is essentialto apply correct models. On the one hand, in some cases it is easier to replacean incorrect model with a correct one, that is sufficiently good approximationof the original model, than fix the topological errors. On the other hand, eventhe model is correct, it is often useful to approximate it with other modelscontaining less geometric elements to increase the computing capacity. Thesewere two demands, that led us to set the main objectives of this dissertation. Iwould have liked to find or construct right surface and solid models to combinethe advantageous properties different models defined in various fields of science.The most important aspect was, that the model should be used efficiently incomputer applications, the main geometric and topological properties could becalculated algorithmically. The precise mathematical definition is necessary toinvestigate its properties and to formulate and prove theorems about them. Iwould like to give a mathematical model, for which the geometric, topologi-cal and computer graphics considerations, theorems and algorithms could beapplied.

After the model has been fixed, I look for answers like: "what kind ofoperations can be defined on these models?", "how can we define new modelsby splitting a single one?", "how can we calculate the dynamic properties ofobjects represented by these kind of models?", "what is the distance of models?"and "how can we approximate a subset of the three dimensional space withthese kind of models?".

Theses of the PhD Dissertation 2

Theses

In the followings I summarize the main results of the PhD dissertationin form of theses. In the Introduction I gave a short survey about the basicconcepts, definitions and theorems that are necessary to understand clearlythe further chapters. I introduced the matrix schema for defining surfaces in away, that best fits to the GPU representation of objects in computer graphics.I defined some useful operations, like inserting and rearranging rows, renameelements and I introduced some equivalence relations.

In th 2nd Chapter I collected all the relevant solid and surface models thatare used in different fields of mathematics and computer graphics, I revealedsome connections between the models, and I compared them to each other.I introduced the concept of physical solid and physical surface, that are in-clude the most important properties of mathematical models discussed earlier.In order to represent models computationally the computer graphics surfacemodel was defined. The relationship between computational and the mathe-matical model was investigated. To explore some topological properties I gavesufficient and sufficient and necessary conditions.

I demonstrated some of the next statements in Targu Mures in Romaniain 2015 on the 5th International Conference on Mathematics and Informaticswith the title: On topological properties of polygonal meshes [5].

Thesis 1 I collected the solid and surface models that are used in differentfields of mathematics, topology, geometry and computer graphics. I comparedthe models and identified the properties, that specify physical solids and surfacesin the real world. I defined the physical solids and surfaces, and I investigatedthe relationship between the new models and the common mathematical models.I defined the concept of computer graphics surface model as a proposal of thecomputational representation of surfaces. I formulated some theorems about

3 Gábor Fábián

checking the topological requirements of being a physical surface. I gave somefast algorithms for calculating the vertex/edge/face adjacencies. I compared theimplementation of the computer graphics surface model to the half-edge datastructure, and I found, that some basic operations can be performed generallyfaster in the new representation.

In the 3rd Chapter I dealt with the operations of polygonal meshes. Sincethe computer graphics surface model is itself a polygonal mesh, the previouslyintroduced concepts were used for uniformity of discussion. Using the renamingand rearranging operations of matrices I introduced the attach, detach and thehole capping operations of models. Furthermore I gave a fast algorithm forsplitting a polygonal mesh by a plane. The splitting is defined using the detachand cap operations. Theses results was presented on 10th Joint Conferenceon Mathematics and Computer Science in Cluj in 2014 with the title: Fastalgorithm to split and reconstruct triangular meshes[7]. The result was alsopublished in the same year with the same title [4].

Thesis 2 I developed a fast algorithm for real time computation of splitting atriangular mesh by a plane. Unlike other solutions can be found in the litera-

Theses of the PhD Dissertation 4

ture, I construct an adjacency matrix before the cut, which can be regeneratedduring sorting and splitting of the triangles, and attach to the resulting meshes.I showed that, if the input mesh is an orientable connected compact 2-manifold,then the resulting meshes have the same topological properties after the cut. Iinvestigated the time complexity of the steps of the algorithm, and I foundthat – according to the statements can be found in literature – the algorithm isnearly optimal.

The dynamic properties of solids represented by triangular meshes, likevolume and centroid, can be calculated by evaluating volume integrals of scalarfunctions. These volume integrals can be transformed to surface integrals usingthe Gauss-Ostrogradsky divergence theorem. I dedicated a separate chapterfor determining the exact integrals of multivariate continuous functions overpolygons and polyhedra. I demonstrated my results on 11th Joint Conferenceon Mathematics and Computer Science in Eger in 2016 with the title: Integralsof scalar fields over polygonal meshes [6].

Thesis 3 I determined successive integral formulas for exact computation ofintegrals of continuous scalar functions over two- and three dimensional poly-gons and polyhedra. Particularly the well-known formulas for calculating areaof polygons and calculating integrals of polynomials over polygons are includedin my results. Therefore my result can be considered as the generalization ofthe formulas can be found in the literature. In a separate section I discussed

5 Gábor Fábián

the integrals of polynomials over polyhedra. I investigated, how the coefficientsof a multivariate polynomials are changed due to the effect of a linear trans-formation. I gave a method for calculating an optimal rotation angle, that canminimize the numerical error of the integral formula. The results in this sec-tion allows the efficient computational application of the formulas, using theresults calculations of integrals over polgonal domains are becoming easier.

In the 4th Chapter I constructed an adaptive volume based method, whichbased on the article: Adaptive algorithm for polyhedral approximation of 3Dsolids [2], on the proceedings of the conference: On constructing volume basedapproximation algorithms of spatial subsets [3], on the conference talk with thesame title on the 6th European Conference on Computer Science [9] in 2015, aswell as on the article: Planning data structure for space partitioning algorithms[1] published in 2016.

Theses of the PhD Dissertation 6

Thesis 4 I showed, that the Lebesgue-measure of symmetric difference of reg-ular sets is not just a semi-metric, but a metric. I proved, that the regular setsare uniquely determined by their boundary. Using the theory of Fourier-seriesin Hilbert-space I showed, how can we define adaptive approximation method,which functionality can be adjusted by few input parameters, the initial ap-proximation, the dividing operation, the choosing operation and the toleranceof the error of the approximation. With appropriate choice of parameters theconvergence and the monotonicity of the method can be guaranteed. In a specialcase the algorithm was investigated in more detail. In this case the dividingoperation is is a splitting by a plane, and the initial approximation is a convexpolyhedron containing the set to be approximated. I showed a few possible ap-plications, moreover I came to the conclusion, that for all connected boundedregular subset of the three dimensional Euclidean space can be arbitrary pre-cisely approximated with physical solids defined by computer graphics surfacemodels.

7 Gábor Fábián

References

[1] G. Fábián, L. Gergó. Planning Data Structure for Space Partitioning Al-gorithms. International Journal of Applied Mathematics and Informatics,10:77–85, 2016.

[2] G. Fábián, L. Gergó. Adaptive algorithm for polyhedral approximation of3D solids. Studia Universitatis Babes-Bolyai Mathematica, 60 (2): 275–291, 2015.

[3] G. Fábián, L. Gergó. On constructing volume based approximation algo-rithms of spatial subsets. Advances in Computer Science (Proceedings ofthe 6th European Conference of Computer Science, pp. 60-65, 2015.

[4] G. Fábián, L. Gergó. Fast algorithm to split and reconstruct triangularmeshes, Studia Universitas Babes-Bolyai Series Informatica, 59 (1):90-102, 2014.

[5] G. Fábián. On topological properties of polygonal meshes (conferencetalk). 5th International Conference on Mathematics and Informatics,Targu Mures, Romania, 2-5th of September, 2015.

[6] G. Fábián. Integrals of scalar fields over polygonal meshes (conferencetalk). 11th Joint Conference on Mathematics and Computer Science, Eger,Hungary, 20-22th of May, 2016.

[7] G. Fábián. Fast algorithm to split and reconstruct triangular meshes (con-ference talk). 12th Joint Conference on Mathematics and Computer Sci-ence, Cluj, Romania, 21-25th of May, 2014.

[8] G. Fábián, L. Gergó. Adaptive volume based algorithm for polyhedralapproximation of 3D solids (conference talk). 3rd International Conferenceon Numerical Analysis and Approximation Theory, Cluj, Romania, 17-20th of September, 2014.

[9] G. Fábián, L. Gergó. On constructing volume-based approximation algo-rithm of spatial subsets (conference talk). 6th European Conference onComputer Science. Rome, Italy, 7-9th of November, 2015.