Variational Methods and Numerical Algorithms for Geometry Processing

In this work we address the problem of shape partitioning which enables the decomposition of an arbitrary topology object into smaller and more manageable pieces called partitions. Several applications in Computer Aided Design (CAD), Computer Aided Manufactury (CAM) and Finite Element Analysis (FEA) rely on object partitioning that provides a high level insight of the data useful for further processing. In particular, we are interested in 2-manifold partitioning, since the boundaries of tangible physical objects can be mathematically defined by two-dimensional manifolds embedded into three-dimensional Euclidean space. To that aim, a preliminary shape analysis is performed based on shape characterizing scalar/vector functions defined on a closed Riemannian 2-manifold. The detected shape features are used to drive the partitioning process into two directions – a human-based partitioning and a thickness-based partitioning. In particular, we focus on the Shape Diameter Function that recovers volumetric information from the surface thus providing a natural link between the object’s volume and its boundary, we consider the spectral decomposition of suitably-defined affinity matrices which provides multi-dimensional spectral coordinates of the object’s vertices, and we introduce a novel basis of sparse and localized quasi-eigenfunctions of the Laplace-Beltrami operator called Lp Compressed Manifold Modes. The partitioning problem, which can be considered as a particular inverse problem, is formulated as a variational regularization problem whose solution provides the so-called piecewise constant/smooth partitioning function. The functional to be minimized consists of a fidelity term to a given data set and a regularization term which promotes sparsity, such as for example, Lp norm with p ∈ (0, 1) and other parameterized, non-convex penalty functions with positive parameter, which controls the degree of non-convexity. The proposed partitioning variational models, inspired on the well-known Mumford Shah models for recovering piecewise smooth/constant functions, incorporate a non-convex regularizer for minimizing the boundary lengths. The derived non-convex non-smooth optimization problems are solved by efficient numerical algorithms based on Proximal Forward-Backward Splitting and Alternating Directions Method of Multipliers strategies, also employing Convex Non-Convex approaches. Finally, we investigate the application of surface partitioning to patch-based surface quadrangulation. To that aim the 2-manifold is first partitioned into zero-genus patches that capture the object’s arbitrary topology, then for each patch a quad-based minimal surface is created and evolved by a Lagrangian-based PDE evolution model to the original shape to obtain the final semi-regular quad mesh. The evolution is supervised by asymptotically area-uniform tangential redistribution for the quads.

In questo lavoro affrontiamo il problema della partizione delle forme il cui scopo è la decomposizione di un oggetto di topologia arbitraria in parti più piccole e meglio gestibili chiamate partizioni. Svariate applicazioni in Computer Aided Design (CAD), Computer Aided Manufactury (CAM) e Finite Element Analysis (FEA) sfruttano tali decomposizioni in quanto forniscono un’informazione globale sulla forma. In particolare, siamo interessati al partizionamento di varietà topologiche di dimensioni 2, in quanto il bordo di oggetti fisici tangibili può essere definito matematicamente da varietà bidimensionali immerse nello spazio euclideo tridimensionale. A tale scopo, viene eseguita un’analisi preliminare sulla forma che fa uso di diverse funzioni scalari/vettoriali definite sulla varietà. Il processo di partizionamento si può affrontare da due punti di vista: uno basato sulla percezione visiva umana e un altro basato sullo spessore delle componenti della forma in esame. In particolare, ci concentriamo sulla funzione ’Diametro di forma’ che recupera informazioni volumetriche dalla superficie, fornendo così un naturale legame tra il volume dell’oggetto e il suo bordo; inoltre studiamo la decomposizione spettrale di opportune matrici di affinità che fornisce coordinate spettrali multidimensionali caratterizzanti la forma dell’oggetto; infine introduciamo una nuova base, denominata Lp Compressed Manifold Modes, di quasi-autofunzioni sparse e localizzate dell’operatore Laplace-Beltrami. Il problema di partizionamento può essere considerato un particolare problema inverso, pertanto è fomulato come un problema di regolarizzazione variazionale che ha come soluzione la cosiddetta funzione di partizionamento. Il funzionale da minimizzare è somma di un termine di fedeltà a un determinato set di dati e di un termine di regolarizzazione che promuove la sparsità, come ad esempio la norma Lp con p ∈ (0, 1) o altre funzioni di penalizzazione non convesse e parametrizzate, con parametro positivo, che controlla il grado di non convessità. I metodi proposti per ottenere la funzione di partizione, ispirati ai modelli variazionali di Mumford-Shah di funzionali costanti o smooth a tratti, incorporano un regolarizzatore non convesso per ridurre al minimo le lunghezze del contorno delle partizioni. Per la soluzione dei problemi di ottimizzazione non convessi e non smooth si propongono metodi numerici basati su Proximal Forward-Backward Splitting, Alternating Directions Method of Multipliers e strategie Convex Non-Convex. Inoltre, studiamo un’applicazione del partizionamento di forma nell’ambito della patchbased surface quadrangulation. A questo scopo la varietà viene prima suddivisa in patch di genere zero che catturano la topologia arbitraria dell’oggetto, quindi per ogni patch viene creata una superficie minima ad elementi quadrilateri che si evolve secondo un modello differenziale alle derivate parziali, seguendo un approccio Lagrangiano per ottenere una rappresentazione a griglie quadrilatere semi-regolari. L’evoluzione è supervisionata da una ridistribuzione tangenziale uniforme dell’area-asintotica dei quadrilateri.