Tuesday, October 27, 2009

symmetry papers

Symmetry is a very much under-explored area in procedural modelling. Here's some papers talking about things you can do with it.

Constructing Regularity Feature Trees for Solid Models ( doi | springer | 2006 )M. Li, F. C. Langbein and R. R. Martin

"Reverse Engineering" is a phrase I normally associate with software engineering, but in the geometric-meaning of the word, it's used to describe recovering the structure from a model. Typically, given a mesh, you want to find out which primitives were combined to create the mesh.

This paper takes the approach that you have a 3D mesh and want to recreate the constructive-solid-geometry primitives and operations used to create that mesh.

The idea is to identify recoverable vertices, edges and faces that the original mesh hints at. These might be external to the volume defined by the mesh, or internal. This is done by intersecting existing features (such as edges or faces) to recovered features (such as vertices or edges).

There's an additional note that gives more credit to Leyton's book.

Partial and approximate symmetry detection for 3D geometry ( pdf | web | doi | video | 2006 )
Niloy J. Mitra, Leonidas J. Guibas, Mark Pauly

The idea here is to define the symmetry as a set of parameters that we can define as points, and then cluster, to reveal the strongest symmetries. For example the equation of a line when looking for 2D reflection symmetries. These parameters can then be clustered and analysed for density to find the most common symmetry constraints. This would give an O(n^2) algorithm in the number of points analysed, however by quickly rejecting pairs biased on the local features (eg: the normals around a point aren't symmetrical over the proposed symmetry line), the number of points to compare is reduced by an order of magnitude.

Mean shift-clustering is used to merge nearby points. This walks uphill on a landscape of Gaussian-splatted data points. Because the Euclidean symmetry space used is 7 dimensional, there is little chance of the maxima converging. Clustering is needed because noisy input mesh is rarely perfectly symmetrical.

To identify mesh patches from the located point pairs, corresponding pairs of input points are grown outwards while the symmetrical surface is within a given tolerance.

As the number of possible symmetries increase, it is desirable to compress the required symmetries to a minimal set. For example two "translate by 10" symmetries should be expressed as two "translate by 5" symmetries. This is process is referred to as "finding a reduced symmetry basis" (frame image, above).

Convincing results, such as the decimation of the above castle mesh to 14% of it's original size (transparent boxes are removed data) make this an interesting technique.

Discovering Structural Regularity in 3D Geometry ( pdf | doi | web | 2008 )
Mark Pauly, Niloy J. Mitra, Johannes Wallner, Helmut Pottmann, Leonidas Guibas

This is an extension of the previous paper (Partial and approximate symmetry detection for 3D geometry, above), presented a few years later. They use the symmetry matching techniques developed to reconstruct data from scattered point samples.

We only consider scale, rotations and translations using one or two parameters - this assumption nicely decreases the number of degrees of freedom to compute. By identifying repeated patches, and accumulating the possible transforms, it is possible to identify the parameters of the transform, even in noisy data. The paper discusses these as "generator functions", that take one (below left four examples) or two (right three examples) parameters, as the basis for symmetry.

A set of random patches from the surface are grouped according the their local feature descriptors (polynomial fitting of osculating jets). Each of these are then locally aligned, and analysed in a cunningly designed space such that their two parameters will be revealed in a lattice (below in one dimension). By plotting all the found dimensions, the most frequent transform (T) becomes the most plotted location. We know the identity transform must be a member of the set of generator functions, and this limits the search space. An energy minimisation function/RANSAC is then used to identify the lattice.

The results include reconstructing a castle and the Colosseum from partial point cloud data.

Symmetry Detection Using Line Features ( pdf | doi | web )
M. Bokeloh A. Berner M. Wand H.-P. Seidel & A. Schilling

The above papers cluster symmetries to identify them. However if two different symmetries are clustered together in symmetry space, they it becomes very difficult to separate.

The routine take a cloud of points-with-normals and create feature identifiers, then then run a couple of loops through these identifiers looks for similar clusters of points to call symmetrical.

The first step Poisson down-sample the input cloud to find points with one linear degree of slippage locally. That is they search for extruded (elongated) features, such as the edge of window frame or column. These are locally clustered into bases, non-slippable graphs of local features. A RANSAC-like algorithm is then used to find similar bases over the model, while flipping a couple of the coordinates to account for mirroring. The features' curvatures are compared between bases to find compatible bases. Region growing maximizes each of these regions, and a geometry matching stage ensures that the base abstraction really matches the input point set. Because of the simplicity of the bases, and their tendency to be localized, many comparisons can be made.

Once symmetry has between detected, the usual things can be done - holes filled, missing sections reconstructed, and data compressed.

The system doesn't really find nested symmeteries, just repeated instances or flipped instances.

Very curiously, in future work these guys mention
In future work, we would like to build morphable statistical models of symmetric parts to better represent subtle variations beyond the accuracy of the region growing algorithm
which is one of the thoughts I've been having a lot recently for generative, rather that reconstructive procedural modelling.

No comments:

Post a Comment