2020: Martin Skrodzki, Eric Zimmermann, and Konrad Polthier
In: Computer Aided Geometric Design, Vol. 80
In this work, we present a translation of the complete pipeline for variational shape approximation (VSA) to the setting of point sets. First, we describe an explicit example for the theoretically known non-convergence of the currently available VSA approaches. The example motivates us to introduce an alternate version of VSA based on a switch operation for which we prove convergence. Second, we discuss how two operations – split and merge – can be included in a fully automatic pipeline that is in turn independent of the placement and number of initial seeds. Third and finally, we present two approaches how to obtain a simplified mesh from the output of the VSA procedure. This simplification is either based on simple plane intersection or based on a variational optimization problem. Several qualitative and quantitative results prove the relevance of our approach.
2020: Martin Skrodzki
In: VisGap - The Gap between Visualization Research and Visualization Software
The JavaView visualization framework was designed at the end of the 1990s as a software that provides-among other services- easy, interactive geometry visualizations on web pages.We discuss how this and other design goals were met and present several applications to highlight the contemporary use-cases of the framework. However, as JavaView's easy web exports was based on Java Applets, the deprecation of this technology disabled one main functionality of the software. The remainder of the article uses JavaView as an example to highlight the effects of changes in the underlying programming language on a visualization toolkit. We discuss possible reactions of software to such challenges, where the JavaView framework serves as an example to illustrate development decisions. These discussions are guided by the broader, underlying question as to how long it is sensible to maintain a software.
2020: Martin Skrodzki and Eric Zimmermann
In: SPM/SMI 2020 Conference Poster Proceedings
We evaluate a weighting scheme for neighborhoods in point sets, which takes the normal information of the points into account. We utilize a sigmoid to define the weights based on the normal variation. For an evaluation, we turn to a Shannon entropy model for feature separation and evaluate our weight terms on a large scale of models.
2019: Martin Skrodzki, Eric Zimmermann, and Konrad Polthier
In: International Geometry Summit 2019 – Poster Proceedings
This work proposes an algorithm for point set segmentation based on the concept of Variational Shape Approximation (VSA), which uses the k-means approach. It iteratively selects seeds, grows flat planar proxy regions according to normal similarity, and updates the proxies. It is known that this algorithm does not converge in general. We provide a concrete example showing that the utilized error measure can indeed grow during the run of the algorithm. To reach convergence, we propose a modification of the original VSA. Further, we provide two new operations applied to the proxy regions, namely split and merge, which enqueue in the pipeline and act according to a user-given parameter. The advantages over regular VSA are independence of both a prescribed number of proxies and a (manual) selection of seeds. Especially the latter is a common drawback of region-growing approaches in segmentation.
Constraint-based point set denoising using normal voting tensor and restricted quadratic error metrics
2018: Sunil Kumar Yadav, Ulrich Reitebuch, Martin Skrodzki, Eric Zimmermann, and Konrad Polthier
In: Computers & Graphics, Volume 74
In many applications, point set surfaces are acquired by 3D scanners. During this acquisition process, noise and outliers are inevitable. For a high fidelity surface reconstruction from a noisy point set, a feature preserving point set denoising operation has to be performed to remove noise and outliers from the input point set. To suppress these undesired components while preserving features, we introduce an anisotropic point set denoising algorithm in the normal voting tensor framework. The proposed method consists of three different stages that are iteratively applied to the input: in the first stage, noisy vertex normals, are initially computed using principal component analysis, are processed using a vertex-based normal voting tensor and binary eigenvalues optimization. In the second stage, feature points are categorized into corners, edges, and surface patches using a weighted covariance matrix, which is computed based on the processed vertex normals. In the last stage, vertex positions are updated according to the processed vertex normals using restricted quadratic error metrics. For the vertex updates, we add different constraints to the quadratic error metric based on feature (edges and corners) and non-feature (planar) vertices. Finally, we show our method to be robust and comparable to state-of-the-art methods in several experiments.
Combinatorial and Asymptotical Results on the Neighborhood Grid Data Structure
2018: Martin Skrodzki, Ulrich Reitebuch, Konrad Polthier, and Shagnik Das
In: EuroCG 2018 Extended Abstracts
In 2009, Joselli et al. introduced the Neighborhood Grid data structure for fast computation of neighborhood estimates in point sets. Even though the data structure has been used in several applications and shown to be practically relevant, it is theoretically not yet well understood. The purpose of this paper is to give results on the complexity of building algorithms – both singlecore and parallel – for the neighborhood grid. Furthermore, current investigations on related combinatorial questions are presented.
2018: Martin Skrodzki, Johanna Jansen, and Konrad Polthier
In: Computer Aided Geometric Design, Volume 64
With the emergence of affordable 3D scanning and printing devices, processing of large point clouds has to be performed in many applications. Several algorithms are available for surface reconstruction, smoothing, and parametrization. However, many of these require the sampling of the point cloud to be uniform or at least to be within certain controlled parameters. For nonuniformly sampled point clouds, some methods have been proposed that deal with the nonuniformity by adding additional information such as topological or hierarchical data. In this paper, we focus on point clouds sampling surfaces in R3. We present the notion of local directional density measure that can be intrinsically computed within the point cloud, that is without further knowledge of the geometry despite the given point samples. Specifically, we build on previous work to derive a local, directed, and discrete measure for density. Furthermore, we derive another discrete and a smooth density measure and compare these three experimentally. Each of the three considered measures gives density weights to use in discretizations of operators such that these become independent of sampling uniformity. We demonstrate the effectiveness of our method on both synthetic and real world data.
2019: Martin Skrodzki
The thesis covers three topics all centered in the context of point set processing. The first topic concerns notions of neighborhood and corresponding data structures. The second main topic of this thesis deals with manifold structures for point set surfaces. Third and finally, algorithms have to work efficiently and robustly on the point set. While meshed geometries provide an intuitive and natural weighting by the areas of the faces, point sets can at most work with distances between the points. This introduces a new level of difficulty to be overcome by any point set processing algorithm. This final chapter introduces a novel weighting scheme to counteract non-uniformity in point sets, a feature detection algorithm with mathematical guarantees, and an iterative denoising scheme for point sets.
2014: Martin Skrodzki
In this thesis we present data structures for efficient neighborhood computation of point set surfaces. Given data structures are tested within a smoothing application implemented in the JavaView geometry framework.
2020: Martin Skrodzki
Mathematical objects are generally abstract and not very approachable. Illustrations and interactive visualizations help both students and professionals to comprehend mathematical material and to work with it. This approach lends itself particularly well to geometrical objects. An example for this category of mathematical objects are hyperbolic geometric spaces. When Euclid lay down the foundations of mathematics, his formulation of geometry reflected the surrounding space, as humans perceive it. For about two millennia, it remained unclear whether there are alternative geometric spaces that carry their own, unique mathematical properties and that do not reflect human every-day perceptions. Finally, in the early 19th century, several mathematicians described such geometries, which do not follow Euclid's rules and which were at first interesting solely from a pure mathematical point of view. These descriptions were not very accessible as mathematicians approached the geometries via complicated collections of formulae. Within the following decades, visualization aided the new concepts and two-dimensional versions of these illustrations even appeared in artistic works. Furthermore, certain aspects of Einstein's theory of relativity provided applications for non-Euclidean geometric spaces. With the rise of computer graphics towards the end of the twentieth century, three-dimensional illustrations became available to explore these geometries and their non-intuitive properties. However, just as the canvas confines the two-dimensional depictions, the computer monitor confines these three-dimensional visualizations. Only virtual reality recently made it possible to present immersive experiences of non-Euclidean geometries. In virtual reality, users have completely new opportunities to encounter geometric properties and effects that are not present in their surrounding Euclidean world.
Experimental visually-guided investigation of sub-structures in three-dimensional Turing-like patterns
2020: Martin Skrodzki, Ulrich Reiteuch, and Eric Zimmermann
In his 1952 paper "The chemical basis of morphogenesis", Alan M. Turing presented a model for the formation of skin patterns. While it took several decades, the model has been validated by finding corresponding natural phenomena, e.g. in the skin pattern formation of zebrafish. More surprising, seemingly unrelated pattern formations can also be studied via the model, like e.g. the formation of plant patches around termite hills. In 1984, David A. Young proposed a discretization of Turing's model, reducing it to an activator/inhibitor process on a discrete domain. From this model, the concept of three-dimensional Turing-like patterns was derived.
In this paper, we consider this generalization to pattern-formation in three-dimensional space. We are particularly interested in classifying the different arising sub-structures of the patterns. By providing examples for the different structures, we prove a conjecture regarding these structures within the setup of three-dimensional Turing-like pattern. Furthermore, we investigate - guided by visual experiments - how these sub-structures are distributed in the parameter space of the discrete model. We found two-fold versions of zero- and one-dimensional sub-structures as well as two-dimensional sub-structures and use our experimental findings to formulate several conjectures for three-dimensional Turing-like patterns and higher-dimensional cases.
2020: Sunil Kumar Yadav, Martin Skrodzki, Eric Zimmermann, and Konrad Polthier
During a surface acquisition process using 3D scanners, noise is inevitable and an important step in geometry processing is to remove these noise components from these surfaces (given as points-set or triangulated mesh). The noise-removal process (denoising) can be performed by filtering the surface normals first and by adjusting the vertex positions according to filtered normals afterwards. Therefore, in many available denoising algorithms, the computation of noise-free normals is a key factor. A variety of filters have been introduced for noise-removal from normals, with different focus points like robustness against outliers or large amplitude of noise. Although these filters are performing well in different aspects, a unified framework is missing to establish the relation between them and to provide a theoretical analysis beyond the performance of each method.
In this paper, we introduce such a framework to establish relations between a number of widely-used nonlinear filters for face normals in mesh denoising and vertex normals in point set denoising. We cover robust statistical estimation with M-smoothers and their application to linear and non-linear normal filtering. Although these methods originate in different mathematical theories - which include diffusion-, bilateral-, and directional curvature-based algorithms - we demonstrate that all of them can be cast into a unified framework of robust statistics using robust error norms and their corresponding influence functions. This unification contributes to a better understanding of the individual methods and their relations with each other. Furthermore, the presented framework provides a platform for new techniques to combine the advantages of known filters and to compare them with available methods.
2020: Martin Skrodzki and Eric Zimmermann
In this paper, we present an approach to take the shape of the geometry into account when weighting its neighborhoods. This makes the obtained neighborhoods more reliable in the sense that connectivity also depends on the orientation of the point set. For example, these neighborhoods grow on a comparably flat part of the geometry and do not include points on a nearby surface patch with differently oriented normals. We utilize a sigmoid to define a neighborhood weighting scheme based on the normal variation. For its evaluation, we turn to a Shannon entropy model for feature separation. Based on this model, we apply our weight terms to a large scale of clean and to several real world models. This evaluation provides results regarding the choice of a weighting scheme and the neighborhood size.
2019: Martin Skrodzki and Ulrich Reitebuch
In 2009, Joselli et al introduced the Neighborhood Grid data structure for fast computation of neighborhood estimates in point clouds. Even though the data structure has been used in several applications and shown to be practically relevant, it is theoretically not yet well understood. The purpose of this paper is to present a polynomial-time algorithm to build the data structure. Furthermore, it is investigated whether the presented algorithm is optimal. This investigation leads to several combinatorial questions for which partial results are given. Finally, we present several limits and experiments regarding the quality of the obtained neighborhood relation.
The k-d tree data structure and a proof for neighborhood computation in expected logarithmic time
2019: Martin Skrodzki
For practical applications, any neighborhood concept imposed on a finite point set P is not of any use if it cannot be computed efficiently. Thus, in this paper, we give an introduction to the data structure of k-d trees, first presented by Friedman, Bentley, and Finkel in 1977. After a short introduction to the data structure (Section 1), we turn to the proof of efficiency by Friedman and his colleagues (Section 2). The main contribution of this paper is the translation of the proof of Freedman, Bentley, and Finkel into modern terms and the elaboration of the proof.
2020: Martin Skrodzki, Ulrich Reitebuch, Henriette Lipschütz, and Konrad Polthier
In: Proceedings of Bridges 2020: Mathematics, Music, Art, Architecture, Education, Culture.
In February 2019, the video artist Kristina Paustian honored the Russian futurist Velimir Khlebnikov with her solo exhibition Laws of Time. The future calculations by Velimir Khlebnikov in Berlin, Germany. Among other aspects, she focused on his poetry and the mathematics used in his works. In this paper, we rephrase Khlebnikov’s ideas and thoughts in mathematical terms. Furthermore, we prove that his method of foretelling the future by analyzing several events which took place in the past produces only random results. Finally, we describe the corresponding mathematical part of the exhibition and provide an artistic exploration of Khlebnikov’s methodology.
2020: Martin Skrodzki and Henriette Lipschütz
In: Proceedings of Bridges 2020: Mathematics, Music, Art, Architecture, Education, Culture.
The artist Paul Klee describes and analyzes his use of symbols and colors in his book “Pädagogisches Skizzenbuch” (pedagogical sketchbook, 1925). He uses arrows for means of illustrations and also discusses the arrow itself as an element of his repertoire of symbols. Interestingly, his point of view on arrows matches the way in which vector fields are represented graphically. Based on this connection of mathematics and Klee’s artwork, we developed a concept for a summer school course for gifted high-school students. Its aim was to both introduce the participants to higher-level mathematics and to let them create their own piece of artwork related to the art of Paul Klee and vector fields. This article elaborates on the connection between Klee’s art and mathematics. It furthermore presents details of the summer course and an evaluation of its goals, including resulting artwork from participating students. Image Credit: Birgit Zickler.
AI and Arts – A Workshop to Unify Arts and Science
2019: Martin Skrodzki
In: w/k - Zwischen Wissenschaft & Kunst
Throughout the last years, new methods in artificial intelligence have revolutionized several scientific fields. These developments affect arts twofold. On the one hand, artists discover machine learning as a new tool. On the other hand, researchers apply the new techniques to the creative work of artists to better analyze and understand it. The workshop AI and Arts brings these two perspectives together and starts a dialog between artists and researchers. It was a satellite workshop of the KI 2019 conference in September 2019 in Kassel, Germany. The conference is the 42nd edition of the German Conference on artificial intelligence organized in cooperation with the AI Chapter of the German Society for Computer Science (GI-FBKI). Image Credit: Martin Pham.
A Leap Forward: A User Study on Gestural Geometry Exploration
2019: Martin Skrodzki, Ulrike Bath, Kevin Guo, and Konrad Polthier
In: Journal of Mathematics and the Arts
Teaching mathematics in high school and university context often proves hard for both teachers and professors respectively. However, it can be supported by technology. Appliances for 3D digital setups are widely available. They have transcended their intended use as simple in- or output devices and nowadays also play a part in many artistic setups. Thus, they change the way we both perceive and create (digital) models. These changes have to be kept in mind when creating, working with, and presenting 3D art in a digital context.
In this paper, we examine the use of gesture-based controllers in the exploration of mathematical content. A user study was conducted as part of the scientific art and education exhibition “Long Night of Science”. To validate the results, a control group was presented with the same questionnaire and physical models of the mathematical objects (instead of the controller) were used. The participants of the study rated the controllers or the physical models respectively by their individually felt intuitiveness and influence on the perception of the underlying mathematical content. From the data obtained, a connection between the intuitiveness of the controller and a positive influence on the perception of the presented mathematics is shown.
2019: Martin Skrodzki
In: Timo Kehren, Carolin Krahn, Georg Oswald, and Christoph Poetsch (Editors), Staunen. Perspektiven eines Phänomens zwischen Natur und Kultur, Fink.
Aus den einleitenden Reflexionen: „Martin Skrodzki untersucht in seinem Beitrag die Ambivalenz des Staunens, wie es sich im Umgang mit mathematischen Problemlösungen zeigt und sich so als Triebfeder wie Hemmnis in der Geschichte mathematischer Forschung auffinden lässt, wobei er die Reduktion und Eliminierung des Staunens als Grundmotiv dieser Forschung ausmacht.“
2019: Ulrich Reitebuch, Martin Skrodzki, and Konrad Polthier
In: Proceedings of Bridges 2019: Mathematics, Music, Art, Architecture, Education, Culture.
We present a discrete gyroid surface. The gyroid is a triply periodic minimal surface, our discrete version has the same symmetries as the smooth gyroid and can be constructed from simple translational units.
Eine Datenanalyse der Persistenz und Leistung von Schulkindern im Wettbewerb „Mathe im Advent“
2018: Milena Damrau, Hernán Villamizar, and Martin Skrodzki
In: Beiträge zum Mathematikunterricht 2018
„Mathe im Advent“ ist ein Wettbewerb, der 2008 von der Deutschen Mmathematiker-Vereinigung initiiert wurde. Jedes Jahr im Dezember öffnen Schüler*innen 24 virtuelle Türchen, hinter denen sich mathematische Probleme verstecken – verpackt in kurzen Geschichten über Wichtel. Zu jeder Frage gibt es vier Antworten, von denen genau eine richtig ist. Die Teilnehmer*innen werden dazu aufgefordert, die Aufgaben mit ihren Mitschüler*innen zu besprechen und haben einen Tag Zeit, ihre Lösungen abzugeben. Hochwertige Preise sollen zu guter Leistung motivieren. Auf Grundlage der Daten von mehr als 100.000 Schüler*innen, die 2016 am Wettbewerb teilgenommen haben, untersuchen wir den Einfluss verschiedener Faktoren auf die Leistung und auf die Wahrscheinlichkeit, dass die Schüler*innen möglichst lange am Wettbewerb teilnehmen. Dabei berücksichtigen wir Kriterien auf Basis von Einzel- und Gruppenspiel sowie den Schultyp und bestimmen durch eine Regressionsanalyse und Ereignisszeitanalyse die wichtigsten Aspekte, die zur Leistung und Persistenz beitragen.
2018: Martin Skrodzki and Konrad Polthier
In: Proceedings of Bridges 2018: Mathematics, Music, Art, Architecture, Education, Culture.
The artist Piet Mondrian (1872 – 1944) is most famous for his abstract works utilizing primary colors and axes-parallel black lines. A similar structure can be found in visualizations of the KdTree data structure used in computational geometry for range searches and neighborhood queries. In this paper, we systematically explore these visualizations and their connections to Mondrian’s work and give a dimension-independent generalization of Mondrian-like pieces.
2017: Martin Skrodzki and Konrad Polthier
In: Proceedings of Bridges 2017: Mathematics, Music, Art, Architecture, Education, Culture.
Beginning with their introduction in 1952 by Alan Turing, Turing-like patterns have inspired research in several different fields. One of these is the field of cellular automata, which have been utilized to create Turing-like patterns by David A. Young and others. In this paper we provide a generalization of these patterns to the third dimension. Several visualizations are given to illustrate the created models.
2016: Martin Skrodzki, Ulrich Reitebuch and Konrad Polthier
In: Proceedings of Bridges 2016: Mathematics, Music, Art, Architecture, Education, Culture.
In his 1802 book “Acoustics”, Ernst Florens Friedrich Chladni describes how to visualize different vibration modes using sand, a metal plate, and a violin bow. We review the underlying physical and mathematical formulations and lift them to the third dimension. Finally, we present some of the resulting three dimensional Chladni figures.
2020: Martin Skrodzki and Ulrike Bath
In: Art Abstracts of the ALife2020 Conference
Why do tigers and zebras have stripes while other animals like cows or leopards are spotted? This is part of the broader question of morphogenesis. One person to attempt an answer to this question was Alan M. Turing. In this artistic video, we explore a three-dimensional version of his model.
2020: Martin Skrodzki, Caroline J. Klivans, and Pedro F. Felzenszwalb
In: “Illustrating Mathematics”, Diana Davis (Ed.), AMS
Chip firing is a process on a graph, which is a network of vertices connected by edges. Initially, a stack of “chips” is placed on each vertex. A vertex is allowed to “fire” its chips if it has at least one chip for each vertex to which it is connected (its “neighbors”). When a vertex fires, it sends one chip to each neighbor. We repeat this process until no vertex has enough chips to fire, which we call a “final configuration.”
2018: Ulrich Reitebuch and Martin Skrodzki
Der MATHEON-Kalender bietet pfiffigen Schüler*innen ab der 10. Klasse sowie Studierenden, Lehrkräften und allen Interessierten faszinierende Einblicke in aktuelle Mathematikforschung und den Berufsalltag von Mathematiker*innen. Gemeinsam mit Ulrich Reitebuch habe ich 2018 eine Aufgabe gestellt.
2017: Ulrich Reitebuch and Martin Skrodzki
Der MATHEON-Kalender bietet pfiffigen Schüler*innen ab der 10. Klasse sowie Studierenden, Lehrkräften und allen Interessierten faszinierende Einblicke in aktuelle Mathematikforschung und den Berufsalltag von Mathematiker*innen. Gemeinsam mit Ulrich Reitebuch habe ich 2017 eine Aufgabe gestellt.
Wie schnell sortiert man Menschenmassen?
2017: Martin Skrodzki
In: Expuls – Zeitung für den CdE
Sudokus und magische Quadrate sind bekannte Zahlenrätsel. In der Rubrik „Ungelöste Fragen“ geht es um Quadrate, in die nicht eine, sondern gleich zwei Zahlen eingetragen werden. Deren Sortierungen können dann zum Beispiel in Simulationen von Menschenmengen genutzt werden.
2017: Martin Skrodzki, Ulrich Reitebuch, and Konrad Polthier
In: ADMC 2017 catalogue
In 1802, Ernst Florens Friedrich Chladni published his book “Acoustics”. The book describes amongst other things an experiment by which different modes of vibration can be visualized. We generalize Chladni's concept to the third dimension. However, we do not build a physical experiment, but simulate the outcome of it, to print it via a 3D-printer. Applications of our method can be found for example in Architecture, where the printed model gives an impression of the acoustics of a given room.