@article{marin-2022-sigdt, title = " SIGDT: 2D Curve Reconstruction", author = "Diana Marin and Stefan Ohrhallinger and Michael Wimmer", year = "2022", abstract = "Determining connectivity between points and reconstructing their shape boundaries are long-standing problems in computer graphics. One possible approach to solve these problems is to use a proximity graph. We propose a new proximity graph computed by intersecting the to-date rarely used proximity-based graph called spheres-of-influence graph (SIG) with the Delaunay triangulation (DT). We prove that the resulting graph, which we name SIGDT, contains the piece-wise linear reconstruction for a set of unstructured points in the plane for a sampling condition superseding current bounds and capturing well practical point sets' properties. As an application, we apply a dual of boundary adjustment steps from the CONNECT2D algorithm to remove the redundant edges. We show that the resulting algorithm SIG-CONNECT2D yields the best reconstruction accuracy compared to state-of-the-art algorithms from a recent comprehensive benchmark, and the method offers the potential for further improvements, e.g., for surface reconstruction.", month = oct, journal = "Computer Graphics Forum", volume = "41", number = "7", issn = "1467-8659", doi = "10.1111/cgf.14654", booktitle = "Pacific Graphics 2022", pages = "12", publisher = "The Eurographics Association and John Wiley & Sons Ltd.", pages = "25--36", keywords = "Curve reconstruction, Spheres-of-influence graph", URL = "https://www.cg.tuwien.ac.at/research/publications/2022/marin-2022-sigdt/", } @talk{ohrhallinger_stefan-2022-it1, title = "Curve/Surface Reconstruction and Occlusion-enabled Applications", author = "Stefan Ohrhallinger", year = "2022", abstract = "Curve reconstruction from unstructured points in a plane is a fundamental problem with many applications that has generated research interest for decades. Involved aspects like handling open, sharp, multiple, and non-manifold outlines, runtime, and provability as well as its extension to 3D for surface reconstruction have led to many different algorithms. The presented algorithms spans the range from improved interpolation of manifold curves over fitting noisy points with better accuracy, requiring fewer points for successful reconstruction to proving the lower limit of required samples with regard to local feature size, or provable statistical accuracy for noise-infected samples. A new sampling condition is introduced that can be expressed as a simple function of the long-standing epsilon-sampling, and permits to reconstruct curves with even fewer samples. As a side product, an algorithm for sampling curves is designed as well. A survey paper compares this body of work with all related work in this now mature field and includes an open source benchmark that allows to easily evaluate competing algorithms in multiple aspects and highlights their relative strengths. For selected 2D algorithms, extensions to 3D are given, as well as offering many novel perspectives for 3D reconstruction, where important open problems remain. As a different topic, when visualizing point clouds, occlusion can be inferred for almost free by exploiting the fact that point clouds representing surfaces are inherently 2D and squashing them in a view-based 2D data structure. This permits novel real-time methods on large point clouds such as collision detection, surface processing like cutting or editing, and efficient exploration. ", month = may, event = "Invited Talk", location = "LiX Polytechnique, Saclay-Paris, France", keywords = "curve reconstruction, surface reconstruction, occlusions", URL = "https://www.cg.tuwien.ac.at/research/publications/2022/ohrhallinger_stefan-2022-it1/", } @misc{marin-2022-sig, title = "SIG-based Curve Reconstruction", author = "Diana Marin and Stefan Ohrhallinger and Michael Wimmer", year = "2022", abstract = "We introduce a new method to compute the shape of an unstructured set of two-dimensional points. The algorithm exploits the to-date rarely used proximity-based graph called spheres-of-influence graph (SIG). We filter edges from the Delaunay triangulation belonging to the SIG as an initial graph and apply some additional processing plus elements from the Connect2D algorithm. This combination already shows improvements in curve reconstruction, yielding the best reconstruction accuracy compared to state-of-the-art algorithms from a recent comprehensive benchmark, and offers potential of further improvements.", month = apr, publisher = "The Eurographics Association", location = "Reims, France", issn = "1017-4656", isbn = "978-3-03868-171-7", event = "Eurographics 2022 - 43rd Annual Conference of the European Association for Computer Graphics", editor = "Sauvage, Basile and Hasic-Telalovic, Jasminka", doi = "10.2312/egp.20221013", booktitle = "Eurographics 2022 - Posters", pages = "2", Conference date = "Poster presented at Eurographics 2022 - 43rd Annual Conference of the European Association for Computer Graphics (2022-04-25--2022-04-29)", keywords = "Curve reconstruction, Spheres-of-influence graph, Computing methodologies, Point-based models", URL = "https://www.cg.tuwien.ac.at/research/publications/2022/marin-2022-sig/", } @inproceedings{ohrhallinger_stefan-2022-tut, title = "Shape Reconstruction: From Theory to Practice", author = "Stefan Ohrhallinger and Amal Dev Parakkat and Jiju Peethambaran", year = "2022", abstract = "Curve reconstruction from unstructured points in a plane is a fundamental problem with many applications that has generated research interest for decades. Involved aspects like handling open, sharp, multiple and non-manifold outlines, run-time and provability as well as potential extension to 3D for surface reconstruction have led to many different algorithms. We survey the literature on 2D curve reconstruction and then present an open-sourced benchmark for the experimental study. Our unprecedented evaluation of a selected set of planar curve reconstruction algorithms aims to give an overview of both quantitative analysis and qualitative aspects for helping users to select the right algorithm for specific problems in the field. Our benchmark framework is available online to permit reproducing the results and easy integration of new algorithms.", month = apr, booktitle = "Eurographics 2022 - Tutorials", keywords = "curve reconstruction, region reconstruction, benchmark", URL = "https://www.cg.tuwien.ac.at/research/publications/2022/ohrhallinger_stefan-2022-tut/", } @article{Radwan_2021_Occ, title = "Fast occlusion-based point cloud exploration", author = "Mohamed Radwan and Stefan Ohrhallinger and Michael Wimmer", year = "2021", abstract = "Large-scale unstructured point cloud scenes can be quickly visualized without prior reconstruction by utilizing levels-of-detail structures to load an appropriate subset from out-of-core storage for rendering the current view. However, as soon as we need structures within the point cloud, e.g., for interactions between objects, the construction of state-of-the-art data structures requires O(NlogN) time for N points, which is not feasible in real time for millions of points that are possibly updated in each frame. Therefore, we propose to use a surface representation structure which trades off the (here negligible) disadvantage of single-frame use for both output-dominated and near-linear construction time in practice, exploiting the inherent 2D property of sampled surfaces in 3D. This structure tightly encompasses the assumed surface of unstructured points in a set of bounding depth intervals for each cell of a discrete 2D grid. The sorted depth samples in the structure permit fast surface queries, and on top of that an occlusion graph for the scene comes almost for free. This graph enables novel real-time user operations such as revealing partially occluded objects, or scrolling through layers of occluding objects, e.g., walls in a building. As an example application we showcase a 3D scene exploration framework that enables fast, more sophisticated interactions with point clouds rendered in real time.", month = sep, journal = "The Visual Computer Journal", volume = "37", issn = "1432-2315", doi = "10.1007/s00371-021-02243-x", booktitle = "The Visual Computer", pages = "13", publisher = "Springer", pages = "2769--2781", keywords = "Software, Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition", URL = "https://www.cg.tuwien.ac.at/research/publications/2021/Radwan_2021_Occ/", } @article{ohrhallinger-2021-egs, title = "2D Points Curve Reconstruction Survey and Benchmark", author = "Stefan Ohrhallinger and Jiju Peethambaran and Amal Dev Parakkat and Tamal K Dey and Ramanathan Muthuganapathy", year = "2021", abstract = "Curve reconstruction from unstructured points in a plane is a fundamental problem with many applications that has generated research interest for decades. Involved aspects like handling open, sharp, multiple and non-manifold outlines, run-time and provability as well as potential extension to 3D for surface reconstruction have led to many different algorithms. We survey the literature on 2D curve reconstruction and then present an open-sourced benchmark for the experimental study. Our unprecedented evaluation on a selected set of planar curve reconstruction algorithms aims to give an overview of both quantitative analysis and qualitative aspects for helping users to select the right algorithm for specific problems in the field. Our benchmark framework is available online to permit reproducing the results, and easy integration of new algorithms.", month = mar, journal = "Computer Graphics Forum", volume = "1", pages = "22", publisher = "Eurographics Association", pages = "611--632", keywords = "curve reconstruction, state-of-the-art report, benchmark", URL = "https://www.cg.tuwien.ac.at/research/publications/2021/ohrhallinger-2021-egs/", } @article{SCHUETZ-2020-MPC, title = "Fast Out-of-Core Octree Generation for Massive Point Clouds", author = "Markus Sch\"{u}tz and Stefan Ohrhallinger and Michael Wimmer", year = "2020", abstract = "We propose an efficient out-of-core octree generation method for arbitrarily large point clouds. It utilizes a hierarchical counting sort to quickly split the point cloud into small chunks, which are then processed in parallel. Levels of detail are generated by subsampling the full data set bottom up using one of multiple exchangeable sampling strategies. We introduce a fast hierarchical approximate blue-noise strategy and compare it to a uniform random sampling strategy. The throughput, including out-of-core access to disk, generating the octree, and writing the final result to disk, is about an order of magnitude faster than the state of the art, and reaches up to around 6 million points per second for the blue-noise approach and up to around 9 million points per second for the uniform random approach on modern SSDs.", month = nov, journal = "Computer Graphics Forum", volume = "39", number = "7", issn = "1467-8659", doi = "10.1111/cgf.14134", pages = "13", publisher = "John Wiley & Sons, Inc.", pages = "1--13", keywords = "point clouds, point-based rendering, level of detail", URL = "https://www.cg.tuwien.ac.at/research/publications/2020/SCHUETZ-2020-MPC/", } @inproceedings{erler-2020-p2s, title = "Points2Surf: Learning Implicit Surfaces from Point Clouds", author = "Philipp Erler and Paul Guerrero and Stefan Ohrhallinger and Michael Wimmer and Niloy Mitra", year = "2020", abstract = "A key step in any scanning-based asset creation workflow is to convert unordered point clouds to a surface. Classical methods (e.g., Poisson reconstruction) start to degrade in the presence of noisy and partial scans. Hence, deep learning based methods have recently been proposed to produce complete surfaces, even from partial scans. However, such data-driven methods struggle to generalize to new shapes with large geometric and topological variations. We present Points2Surf, a novel patch-based learning framework that produces accurate surfaces directly from raw scans without normals. Learning a prior over a combination of detailed local patches and coarse global information improves generalization performance and reconstruction accuracy. Our extensive comparison on both synthetic and real data demonstrates a clear advantage of our method over state-of-the-art alternatives on previously unseen classes (on average, Points2Surf brings down reconstruction error by 30% over SPR and by 270%+ over deep learning based SotA methods) at the cost of longer computation times and a slight increase in small-scale topological noise in some cases. Our source code, pre-trained model, and dataset are available on: https://github.com/ErlerPhilipp/points2surf ", month = oct, isbn = "978-3-030-58558-7", series = "Lecture Notes in Computer Science", publisher = "Springer International Publishing", location = "Glasgow, UK (online)", address = "Cham", event = "ECCV 2020", editor = "Vedaldi, Andrea and Bischof, Horst and Brox, Thomas and Frahm, Jan-Michael", doi = "10.1007/978-3-030-58558-7_7", booktitle = "Computer Vision -- ECCV 2020", journal = "Computer Vision – ECCV 2020", pages = "17", volume = "12350", pages = "108--124", keywords = "surface reconstruction, implicit surfaces, point clouds, patch-based, local and global, deep learning, generalization", URL = "https://www.cg.tuwien.ac.at/research/publications/2020/erler-2020-p2s/", } @article{leimer_2020-cag, title = "Pose to Seat: Automated design of body-supporting surfaces", author = "Kurt Leimer and Andreas Winkler and Stefan Ohrhallinger and Przemyslaw Musialski", year = "2020", abstract = "The design of functional seating furniture is a complicated process which often requires extensive manual design effort and empirical evaluation. We propose a computational design framework for pose-driven automated generation of body-supports which are optimized for comfort of sitting. Given a human body in a specified pose as input, our method computes an approximate pressure distribution that also takes frictional forces and body torques into consideration which serves as an objective measure of comfort. Utilizing this information to find out where the body needs to be supported in order to maintain comfort of sitting, our algorithm can create a supporting mesh suited for a person in that specific pose. This is done in an automated fitting process, using a template model capable of supporting a large variety of sitting poses. The results can be used directly or can be considered as a starting point for further interactive design.", month = apr, journal = "Computer Aided Geometric Design", volume = "79", event = "Conference", pages = "1--1", keywords = "pose estimation, furniture, computational design", URL = "https://www.cg.tuwien.ac.at/research/publications/2020/leimer_2020-cag/", } @article{ohrhallinger_stefan-2018-cgf, title = "FitConnect: Connecting Noisy 2D Samples by Fitted Neighborhoods", author = "Stefan Ohrhallinger and Michael Wimmer", year = "2019", abstract = "We propose a parameter-free method to recover manifold connectivity in unstructured 2D point clouds with high noise in terms of the local feature size. This enables us to capture the features which emerge out of the noise. To achieve this, we extend the reconstruction algorithm HNN-Crust, which connects samples to two (noise-free) neighbors and has been proven to output a manifold for a relaxed sampling condition. Applying this condition to noisy samples by projecting their k-nearest neighborhoods onto local circular fits leads to multiple candidate neighbor pairs and thus makes connecting them consistently an NP-hard problem. To solve this efficiently, we design an algorithm that searches that solution space iteratively on different scales of k. It achieves linear time complexity in terms of point count plus quadratic time in the size of noise clusters. Our algorithm FitConnect extends HNN-Crust seamlessly to connect both samples with and without noise, performs as local as the recovered features and can output multiple open or closed piece-wise curves. Incidentally, our method simplifies the output geometry by eliminating all but a representative point from noisy clusters. Since local neighborhood fits overlap consistently, the resulting connectivity represents an ordering of the samples along a manifold. This permits us to simply blend the local fits for denoising with the locally estimated noise extent. Aside from applications like reconstructing silhouettes of noisy sensed data, this lays important groundwork to improve surface reconstruction in 3D. Our open-source algorithm is available online.", month = feb, journal = "Computer Graphics Forum", volume = "38", number = "1", issn = "1467-8659", doi = "10.1111/cgf.13395", pages = "126--137", keywords = "curve fitting, noisy samples, guarantees, curve reconstruction", URL = "https://www.cg.tuwien.ac.at/research/publications/2019/ohrhallinger_stefan-2018-cgf/", } @xmascard{ohrhallinger_stefan-2019-xms, title = "X-Mas Card 2019", author = "Stefan Ohrhallinger and Adam Celarek", year = "2019", abstract = "See right for correct solution of our connect-the-dots game :-) Of course, we not only reconstruct members of our institute but also highly noisy point clouds, additionally denoise the reconstruction, and specify the minimum number of samples required for that. Eduard Gr\"{o}ller See here for the mystery present in the crib: youtu.be/-oVwXaaJNtY Die Aufl\"{o}sung unseres Punkte-verbinden-Spiels ist hier rechts :-) Wir rekonstruieren nicht nur Institutsmitglieder, sondern auch stark verrauschte Punktewolken, entfernen das Rauschen und berechnen die Mindestanzahl der ben\"{o}tigten Messpunkte. Hier ist das Geschenk in der Krippe zu sehen: youtu.be/-oVwXaaJNtY", keywords = "curve reconstruction, sampling", URL = "https://www.cg.tuwien.ac.at/research/publications/2019/ohrhallinger_stefan-2019-xms/", } @inproceedings{ohrhallinger_stefan-2018-pg, title = "StretchDenoise: Parametric Curve Reconstruction with Guarantees by Separating Connectivity from Residual Uncertainty of Samples", author = "Stefan Ohrhallinger and Michael Wimmer", year = "2018", abstract = "We reconstruct a closed denoised curve from an unstructured and highly noisy 2D point cloud. Our proposed method uses a two-pass approach: Previously recovered manifold connectivity is used for ordering noisy samples along this manifold and express these as residuals in order to enable parametric denoising. This separates recovering low-frequency features from denoising high frequencies, which avoids over-smoothing. The noise probability density functions (PDFs) at samples are either taken from sensor noise models or from estimates of the connectivity recovered in the first pass. The output curve balances the signed distances (inside/outside) to the samples. Additionally, the angles between edges of the polygon representing the connectivity become minimized in the least-square sense. The movement of the polygon's vertices is restricted to their noise extent, i.e., a cut-off distance corresponding to a maximum variance of the PDFs. We approximate the resulting optimization model, which consists of higher-order functions, by a linear model with good correspondence. Our algorithm is parameter-free and operates fast on the local neighborhoods determined by the connectivity. %We augment a least-squares solver constrained by a linear system to also handle bounds. This enables us to guarantee stochastic error bounds for sampled curves corrupted by noise, e.g., silhouettes from sensed data, and we improve on the reconstruction error from ground truth. Source code is available online. An extended version is available at: https://arxiv.org/abs/1808.07778", month = aug, isbn = "978-3-03868-073-4", location = "Hong Kong", event = "Pacific Graphics 2018", editor = "H. Fu, A. Ghosh, and J. Kopf (Guest Editors)", booktitle = "Proceedings of Pacific Graphics 2018", pages = "1--4", keywords = "Denoising, Curve reconstruction, Optimization", URL = "https://www.cg.tuwien.ac.at/research/publications/2018/ohrhallinger_stefan-2018-pg/", } @inproceedings{Radwan-2017-Occ, title = "Cut and Paint: Occlusion-Aware Subset Selection for Surface Processing", author = "Mohamed Radwan and Stefan Ohrhallinger and Elmar Eisemann and Michael Wimmer", year = "2017", abstract = "User-guided surface selection operations are straightforward for visible regions on a convex model. However, concave surfaces present a challenge because self-occlusions require multiple camera positions to get unobstructed views. Therefore, users often have to locate and switch to new unobstructed views in order to continue the operation. Our novel approach enables operations like painting or cutting in a single view, even on the backside of objects and for arbitrary depth complexity, with interactive performance. Continuous projection of a curve drawn in screen space onto the mesh guarantees seamless brush strokes or manifold cuts, unaffected by any occlusions. Our occlusion-aware surface-processing method enables a number of applications in an easy way. As examples, we show continuous painting on the surface, selecting regions for texturing, creating illustrative cutaways from nested models and animation of cutaways.", month = may, publisher = "Canadian Human-Computer Communications Society / Soci{\'e}t{\'e} canadienne du dialogue humain-machine", location = "Edmonton, Alberta, CA", event = "Graphics Interface 2017", doi = "10.20380/GI2017.11", booktitle = "Proceedings of Graphics Interface 2017", pages = "82--89", URL = "https://www.cg.tuwien.ac.at/research/publications/2017/Radwan-2017-Occ/", } @article{ohrhallinger-2016-sgp, title = "Curve Reconstruction with Many Fewer Samples", author = "Stefan Ohrhallinger and Scott A. Mitchell and Michael Wimmer", year = "2016", abstract = "We consider the problem of sampling points from a collection of smooth curves in the plane, such that the Crust family of proximity-based reconstruction algorithms can rebuild the curves. Reconstruction requires a dense sampling of local features, i.e., parts of the curve that are close in Euclidean distance but far apart geodesically. We show that epsilon<0.47-sampling is sufficient for our proposed HNN-CRUST variant, improving upon the state-of-the-art requirement of epsilon<1/3-sampling. Thus we may reconstruct curves with many fewer samples. We also present a new sampling scheme that reduces the required density even further than epsilon<0.47-sampling. We achieve this by better controlling the spacing between geodesically consecutive points. Our novel sampling condition is based on the reach, the minimum local feature size along intervals between samples. This is mathematically closer to the reconstruction density requirements, particularly near sharp-angled features. We prove lower and upper bounds on reach rho-sampling density in terms of lfs epsilon-sampling and demonstrate that we typically reduce the required number of samples for reconstruction by more than half. ", journal = "Computer Graphics Forum", volume = "35", number = "5", issn = "1467-8659", pages = "167--176", keywords = "sampling condition, curve reconstruction, curve sampling", URL = "https://www.cg.tuwien.ac.at/research/publications/2016/ohrhallinger-2016-sgp/", } @inproceedings{Radwan-2014-CDR, title = "Efficient Collision Detection While Rendering Dynamic Point Clouds", author = "Mohamed Radwan and Stefan Ohrhallinger and Michael Wimmer", year = "2014", abstract = "A recent trend in interactive environments is the use of unstructured and temporally varying point clouds. This is driven by both affordable depth cameras and augmented reality simulations. One research question is how to perform collision detection on such point clouds. State-of-the-art methods for collision detection create a spatial hierarchy in order to capture dynamic point cloud surfaces, but they require O(NlogN) time for N points. We propose a novel screen-space representation for point clouds which exploits the property of the underlying surface being 2D. In order for dimensionality reduction, a 3D point cloud is converted into a series of thickened layered depth images. This data structure can be constructed in O(N) time and allows for fast surface queries due to its increased compactness and memory coherency. On top of that, parts of its construction come for free since they are already handled by the rendering pipeline. As an application we demonstrate online collision detection between dynamic point clouds. It shows superior accuracy when compared to other methods and robustness to sensor noise since uncertainty is hidden by the thickened boundary.", month = may, isbn = "978-1-4822-6003-8", publisher = "Canadian Information Processing Society", location = "Montreal, Quebec, Canada ", issn = "0713-5424", event = "Graphics Interface 2014", booktitle = "Proceedings of the 2014 Graphics Interface Conference", pages = "25--33", keywords = "bounding volumes, layered depth images, collision detection, point cloud, dynamic", URL = "https://www.cg.tuwien.ac.at/research/publications/2014/Radwan-2014-CDR/", } @article{ohrhallinger_stefan-2013-c2d, title = "An Efficient Algorithm for Determining an Aesthetic Shape Connecting Unorganised 2D Points", author = "Stefan Ohrhallinger and Sudhir Mudur", year = "2013", abstract = "We present an efficient algorithm for determining an aesthetically pleasing shape boundary connecting all the points in a given unorganised set of 2D points, with no other information than point coordinates. By posing shape construction as a minimisation problem which follows the Gestalt laws, our desired shape Bmin is non-intersecting, interpolates all points and minimises a criterion related to these laws. The basis for our algorithm is an initial graph, an extension of the Euclidean minimum spanning tree but with no leaf nodes, called as the minimum boundary complex BCmin. BCmin and Bmin can be expressed similarly by parametrising a topological constraint. A close approximation of BCmin, termed BC0 can be computed fast using a greedy algorithm. BC0 is then transformed into a closed interpolating boundary Bout in two steps to satisfy Bmin’s topological and minimization requirements. Computing Bmin exactly is an NP-hard problem, whereas Bout is computed in linearithmic time. We present many examples showing considerable improvement over previous techniques, especially for shapes with sharp corners. Source code is available online.", month = dec, journal = "Computer Graphics Forum", volume = "32", number = "8", pages = "72--88", keywords = "curve reconstruction, boundary representation, sampling condition, computational geometry", URL = "https://www.cg.tuwien.ac.at/research/publications/2013/ohrhallinger_stefan-2013-c2d/", } @article{ohrhallinger_stefan-2013-smi, title = "Minimizing Edge Length to Connect Sparsely Sampled Unorganized Point Sets", author = "Stefan Ohrhallinger and Sudhir Mudur and Michael Wimmer", year = "2013", abstract = "Most methods for interpolating unstructured point clouds handle densely sampled point sets quite well but get into trouble when the point set contains regions with much sparser sampling, a situation often encountered in practice. In this paper, we present a new method that provides a better interpolation of sparsely sampled features. We pose the surface construction problem as finding the triangle mesh which minimizes the sum of all triangles’ longest edge. The output is a closed manifold triangulated surface Bmin. Exact computation of Bmin for sparse sampling is most probably NP-hard, and therefore we introduce suitable heuristics for its computing. The algorithm first connects the points by triangles chosen in order of their longest edge and with the requirement that all edges must have at least 2 incident triangles. This yields a closed non-manifold shape which we call the Boundary Complex. Then we transform it into a manifold triangulation using topological operations. We show that in practice, runtime is linear to that of the Delaunay triangulation of the points.", month = oct, journal = "Computers & Graphics (Proceedings of Shape Modeling International 2013)", volume = "37", number = "6", issn = "0097-8493", pages = "645--658", keywords = "point cloud, reconstruction", URL = "https://www.cg.tuwien.ac.at/research/publications/2013/ohrhallinger_stefan-2013-smi/", } @phdthesis{ohrhallinger-stefan-2012-the, title = "The Intrinsic Shape of Point Clouds", author = "Stefan Ohrhallinger", year = "2012", abstract = "Given a point cloud, in the form of unorganized points, the problem of automatically connecting the dots to obtain an aesthetically pleasing and piecewise-linear closed interpolating boundary shape has been extensively researched for over three decades. In R3 , it is even more complicated to find an aesthetic closed oriented surface. Most previous methods for shape reconstruction exclusively from coordinates work well only when the point spacing on the shape boundary is dense and locally uniform. The problem of shape construction from non-dense and locally non-uniformly spaced point sets is in our opinion not yet satisfactorily solved. Various extensions to earlier methods do not work that well and do not provide any performance guarantees either. Our main thesis in this research is that a point set, even with non-dense and locally non-uniform spacing, has an intrinsic shape which optimizes in some way the Gestalt principles of form perception. This shape can be formally defined as the minimum of an energy function over all possible closed linear piece-wise interpolations of this point set. Further, while finding this optimal shape is NP-hard, it is possible to heuristically search for an acceptable approximation within reasonable time. Our minimization objective is guided by Gestalt’s laws of Proximity, Good Continuity and Closure. Minimizing curvature tends to satisfy proximity and good continuity. For computational simplification, we globally minimize the longest-edge-in-simplex, since it is intrinsic to a single facet and also a factor in mean curvature. And we require a closed shape. Using such an intrinsic criterion permits the extraction of an approximate shape with a linearithmic algorithm as a simplicial complex, which we have named the Minimum Boundary Complex. Experiments show that it seems to be a very close approximation to the desired boundary shape and that it retains its genus. Further it can be constructed locally and can also handle sensor data with significant noise. Its quick construction is due to not being restricted by the manifold property, required in the boundary shape. Therefore it has many applications where a manifold shape is not necessary, e.g. visualization, shape retrieval, shadow mapping, and topological data analysis in higher dimensions. The definition of the Minimum Boundary Complex is our first major contribution. Our next two contributions include new methods for constructing boundary shapes by transforming the boundary complex into a close approximation of the minimum boundary shape. These algorithms vary a topological constraint to first inflate the boundary complex to recover a manifold hull and then sculpture it to extract a Minimum Boundary approximation, which interpolates all the points. In the R3 method, we show how local minima can be avoided by covering holes in the hull. Finally, we apply a mesh fairing step to optimize mean curvature directly. We present results for shape construction in R2 and R3 , which clearly demonstrate that our methods work better than the best performing earlier methods for non-dense and locally non-uniformly spaced point sets, while maintaining competitive linearithmic complexity. ", month = jul, address = "Favoritenstrasse 9-11/E193-02, A-1040 Vienna, Austria", school = "Institute of Computer Graphics and Algorithms, Vienna University of Technology ", keywords = "Surface Reconstruction, Manifold Reconstruction, Point Cloud, Shape Boundary, Gestalt, Curve Reconstruction", URL = "https://www.cg.tuwien.ac.at/research/publications/2012/ohrhallinger-stefan-2012-the/", } @misc{ohrhallinger_stefan-2012-mle, title = "Minimising Longest Edge for Closed Surface Construction from Unorganised 3D Point Sets", author = "Stefan Ohrhallinger and Sudhir Mudur", year = "2012", abstract = "Given an unorganised 3D point set with just coordinate data, we formulate the problem of closed surface construction as one requiring minimisation of longest edge in triangles, a criterion derivable from Gestalt laws for shape perception. Next we define the Minimum Boundary Complex (BCmin ), which resembles the desired surface Bmin considerably, by slightly relaxing the topological constraint to make it at least two triangles per edge instead of exactly two required by Bmin . A close approximation of BCmin can be computed fast using a greedy algorithm. This provides a very good starting shape which can be transformed by a few steps into the desired shape, close to Bmin. Our method runs in O(n log n) time, with Delaunay Graph construction as largest run-time factor. We show considerable improvement over previous methods, especially for sparse, non-uniform point spacing. ", month = may, publisher = "Eurographics Association", location = "Cagliari, Italy", event = "Eurographics 2012 (Best Poster Award)", booktitle = "Poster Proceedings", Conference date = "Poster presented at Eurographics 2012 (Best Poster Award) (2012-05-13--2012-05-18)", note = "25--26", pages = "25 – 26", keywords = "Point Cloud, Point Set, Reconstruction, Surface Construction", URL = "https://www.cg.tuwien.ac.at/research/publications/2012/ohrhallinger_stefan-2012-mle/", } @article{ohrhallinger_stefan-2011-001, title = "Interpolating an unorganized 2D point cloud with a single closed shape", author = "Stefan Ohrhallinger and Sudhir Mudur", year = "2011", abstract = "Given an unorganized two-dimensional point cloud, we address the problem of efficiently constructing a single aesthetically pleasing closed interpolating shape, without requiring dense or uniform spacing. Using Gestalt’s laws of proximity, closure and good continuity as guidance for visual aesthetics, we require that our constructed shape be a minimal perimeter, non-self intersecting manifold. We find that this yields visually pleasing results. Our algorithm is distinct from earlier shape reconstruction approaches, in that it exploits the overlap between the desired shape and a related minimal graph, the Euclidean Minimum Spanning Tree (EMST). Our algorithm segments the EMST to retain as much of it as required and then locally partitions and solves the problem efficiently. Comparison with some of the best currently known solutions shows that our algorithm yields better results. ", month = jan, issn = "0010-4485", journal = "Computer-Aided Design", number = "1", volume = "43", pages = "1629--1638", keywords = "EMST, Curve, Point cloud, Reconstruction, Shape Construction, Boundary, Computational geometry, Point set", URL = "https://www.cg.tuwien.ac.at/research/publications/2011/ohrhallinger_stefan-2011-001/", }