# Variational Shape Approximation of Point Set Surfaces
This is the readme for a (partial) implementation of the paper "Variational Shape Approximation of Point Set Surfaces" by Martin Skrodzki, Eric Zimmermann, and Konrad Polthier. 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. To cite the paper, please use the following bibtex entry:

```
@article{SKRODZKI2020101875,
    title = "Variational shape approximation of point set surfaces",
    journal = "Computer Aided Geometric Design",
    volume = "80",
    pages = "101875",
    year = "2020",
    issn = "0167-8396",
    doi = "https://doi.org/10.1016/j.cagd.2020.101875",
    url = "http://www.sciencedirect.com/science/article/pii/S0167839620300625",
    author = "Martin Skrodzki and Eric Zimmermann and Konrad Polthier",
    keywords = "Variational shape approximation, Point set segmentation, Simplification"
}
``` 

## Using the implementation
The algorithm is implemented in Java as a part of the [*JavaView*](http://www.javaview.de) framework. There is no need to download or install *JavaView*, all necessary libraries are contained in the packed `.jar` file. 

### Starting the application
To run the implementation, you need a Java virtual machine. Provided that one is installed, the algorithm can be run via the following command:

```
java -jar pointVSA.jar
```

### Loading a geometry
To load your own geometry into the application, click `Browse Computer` on the top left of the Control Panel, navigate to the file you want to load and open it. The file is then loaded into the main window. To fit the view to your file, click into the main window and press `f`.

### Simple run of the algorithm
For a simple test run of the algorithm, click `Init Random Seeds`. This will spawn a number of seed points, with the number indicated as `#seeds` in the settings of the control panel. The normals of these seed points are shown. 

Then click `Whole Process`, which will run `#iter` many iterations on the loaded geometry. The result is a segmentation of the geometry into several planar parts (the planarity can be steered via the `eta` parameter). The segments are distinguished by different colors.

Finally, to obtain a simplification, hit `PlanarIntersection` to obtain a triangle mesh representing the point set.

### Advanced run of the algorithm
Generally, the parameters in the control panel bear the same names as they do in the publication. Therefore, we refer to the publication for further details. However, we would like to highlight two parameters.

The `#split` and `#merge` parameters indicate how many *split* and *merge* operations are to be performed in each iteration. That is, how many regions are to be split or merged, depending on the `eta` value set. Tuning this number and the `eta` value is the most important part for obtaining high-quality segmentations.

### Limitations
Note that the publication mentions an optimization scheme to obtain enhanced simplified regions from the segmentation. This requires a solver for the optimization problem that is not easily integrated into this implementation. Hence, here, we only use a simple plane intersection as proxy. Therefore, results on the geometries might differ from those reported in the paper.