@techreport{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 = aug,
number = "TR-193-02-2020-3",
address = "Favoritenstrasse 9-11/E193-02, A-1040 Vienna, Austria",
institution = "Research Unit of Computer Graphics, Institute of Visual
Computing and Human-Centered Technology, Faculty of
Informatics, TU Wien ",
note = "human contact: technical-report@cg.tuwien.ac.at",
keywords = "point clouds, point-based rendering, level of detail",
URL = "/research/publications/2020/SCHUETZ-2020-MPC/",
}
@article{erler-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 = aug,
journal = "todo",
volume = "todo",
pages = "todo--todo",
keywords = "surface reconstruction, implicit surfaces, point clouds,
patch-based, local and global, deep learning, generalization",
URL = "/research/publications/2020/erler-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 = "/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,
doi = "10.1111/cgf.13395",
issn = "1467-8659",
journal = "Computer Graphics Forum",
number = "1",
volume = "38",
pages = "126--137",
keywords = "curve fitting, noisy samples, guarantees, curve
reconstruction",
URL = "/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 = "/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,
booktitle = "Proceedings of Pacific Graphics 2018",
editor = "H. Fu, A. Ghosh, and J. Kopf (Guest Editors)",
event = "Pacific Graphics 2018",
isbn = "978-3-03868-073-4",
location = "Hong Kong",
pages = "1--4",
keywords = "Denoising, Curve reconstruction, Optimization",
URL = "/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,
booktitle = "Proceedings of Graphics Interface 2017",
doi = "10.20380/GI2017.11",
event = "Graphics Interface 2017",
location = "Edmonton, Alberta, CA",
publisher = "Canadian Human-Computer Communications Society /
Soci{\'e}t{\'e} canadienne du dialogue humain-machine",
pages = "82--89",
URL = "/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. ",
issn = "1467-8659",
journal = "Computer Graphics Forum",
number = "5",
volume = "35",
pages = "167--176",
keywords = "sampling condition, curve reconstruction, curve sampling",
URL = "/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,
booktitle = "Proceedings of the 2014 Graphics Interface Conference",
event = "Graphics Interface 2014",
isbn = "978-1-4822-6003-8",
issn = "0713-5424",
location = "Montreal, Quebec, Canada ",
publisher = "Canadian Information Processing Society",
pages = "25--33",
keywords = "bounding volumes, layered depth images, collision detection,
point cloud, dynamic",
URL = "/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",
number = "8",
volume = "32",
pages = "72--88",
keywords = "curve reconstruction, boundary representation, sampling
condition, computational geometry",
URL = "/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,
issn = "0097-8493",
journal = "Computers & Graphics (Proceedings of Shape Modeling
International 2013)",
number = "6",
volume = "37",
pages = "645--658",
keywords = "point cloud, reconstruction",
URL = "/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 = "/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,
booktitle = "Poster Proceedings",
event = "Eurographics 2012 (Best Poster Award)",
location = "Cagliari, Italy",
publisher = "Eurographics Association",
note = "Poster presented at Eurographics 2012 (Best Poster Award)
(2012-05-13--2012-05-18)",
pages = "25--26",
keywords = "Point Cloud, Point Set, Reconstruction, Surface Construction",
URL = "/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 = "/research/publications/2011/ohrhallinger_stefan-2011-001/",
}