SpringerOpen Newsletter

Receive periodic news and updates relating to SpringerOpen.

Open Access Highly Accessed Research

Geometric computing for freeform architecture

Johannes Wallner12* and Helmut Pottmann23

Author Affiliations

1 TU Graz, Kopernikusgasse 24, 8010, Graz, Austria

2 TU Wien, Wiedner Hauptstr. 8-10, 1040, Wien, Austria

3 King Abdullah University of Science and Technology, Thuwal, Saudi Arabia

For all author emails, please log on.

Journal of Mathematics in Industry 2011, 1:4  doi:10.1186/2190-5983-1-4


The electronic version of this article is the complete one and can be found online at: http://www.mathematicsinindustry.com/content/1/1/4


Received:8 December 2010
Accepted:3 June 2011
Published:3 June 2011

© 2011 Wallner, Pottmann; licensee Springer

This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Geometric computing has recently found a new field of applications, namely the various geometric problems which lie at the heart of rationalization and construction-aware design processes of freeform architecture. We report on our work in this area, dealing with meshes with planar faces and meshes which allow multilayer constructions (which is related to discrete surfaces and their curvatures), triangles meshes with circle-packing properties (which is related to conformal uniformization), and with the paneling problem. We emphasize the combination of numerical optimization and geometric knowledge.

1 Background

The time of writing this survey paper coincides with the summing up of a six-year so-called national research network entitled Industrial geometry which was funded by the Austrian Science Fund (FWF). By serendipity at the same point in time where the first Ph.D. students started their work in this project, a whole new direction of research in applied geometry turned up: meshes and three-dimensional geometric structures which are relevant for rationalization and construction-aware design in freeform architecture. It turned out to be fruitful and rewarding, and of course it is also a topic which perfectly fits the heading of ‘Industrial Geometry’.

It seems that everybody who is in the business of actually realizing freeform architectural designs as a steel-glass construction, or in concrete, or by means of a wooden paneling, quickly encounters the limits of the tools which are commercially available. Some of the problems whose solutions are on top of the list of desiderata are in fact very hard. As a consequence there is great demand for a systematic approach and, most importantly, a full understanding of the geometric possibilities and obstructions inherent in obstacles which present themselves.

We were able to expand knowledge in this direction by applying geometry, differential geometry, and geometric algorithms to some of those problems. Cooperation with industry was essential here. We were fortunate to work with with Waagner-Biro Stahlbau (Vienna), RFR (Paris), and Evolute (Vienna), who provided much-need validation, information on actual problems, and real-world data. Remarkably the process of applying he known theory to practical problems also worked in reverse: applications have directly led to research in pure mathematics. In this paper we survey some developments which we see as significant:

– The discrete differential geometry of quadrilateral meshes and the sphere geometries of Möbius, Laguerre, and Lie, are closely related to the realization of freeform shapes as steel-glass constructions with so-called torsion free nodes.

– Conformal uniformization appears in connection with circle-packing meshes and derived triangle and hexagonal meshes.

– Optimization using various ideas ranging from combinatorial optimization to image processing is instrumental in solving the paneling problem, that is, the rationalization of freeform shapes via decomposition into simple and repetitive elements.

Our research is part of the emerging interdisciplinary field of architectural geometry. The interested reader is referred to the proceedings volume [1] which collects recent contributions from different areas (mathematics, engineering, architecture), the textbook [2], and the articles [3-5]. Our aim is to convince the reader that many issues in freeform architecture can be dealt with by meshes or other geometric structures with certain local properties. Further, that we are capable of formulating target functionals for optimization which - if successful - achieve these properties. It is however important to know that in many cases optimization without additional geometric knowledge (utilized, for example, by way of initialization) does not succeed.

2 Multilayer structures

In this section we deal with the remarkable interrelation between the discrete differential geometry of polyhedral surfaces on the one hand, and problems regarding multilayer structures and torsion-free nodes in steel-glass constructions on the other hand.

2.1 Torsion-free nodes

In order to realize a designer’s intended shape as a steel-glass construction, it is in principle easy to find a triangle mesh which approximates that shape, and let beams follow the edges of this mesh, with glass panels covering the faces. This is in fact a very common method. Experience shows that here often the manufacturing of nodes is more complex than one would wish (see Figures 1 and 2), which is caused by the phenomenon that the symmetry planes of beams which run into a vertex do not intersect nicely in a common node axis. The basic underlying geometric question is phrased in the following terms:

thumbnailFigure 1. Node with torsion. Manufacturing a vertex where symmetry planes of incoming beams do not intersect properly is demanding, especially the central part (image courtesy Waagner-Biro Stahlbau).

thumbnailFigure 2. Nodes without torsion. If we can align symmetry planes of beams along edges such that they intersect in a common axis, node construction is much simplified.

DefinitionAssume that all edges of a mesh are equipped with a plane which contains that edge. A vertex where the intersection of planes associated with adjacent edges is a straight line is called a node without torsion, and that line is called the node axis.

ProblemIs it possible to find meshes (and associated planes) such that vertices do not exhibit torsion, possibly by minimally changing an existing mesh?

The answer for triangle meshes is no, there are not enough degrees of freedom available. For a quadrilateral mesh this is different, and we demonstrate an example which has actually been built: The outer skin of the Yas Island hotel in Abu Dhabi which was completed in 2009 exhibits a quadrilateral mesh with non-planar faces which are not covered by glass in a watertight way. Figure 3 illustrates the tools from Geometric Modeling (subdivision) employed in generating the mesh, the final result is illustrated by Figure 4.

thumbnailFigure 3. Mesh design. Top: In order to achieve a mesh which follows the architects’ design one can employ an iterative procedure which consists of a subdivision process [6], a switch to diagonals, and mesh optimization such that the resulting mesh can be equipped with beams without node torsion (image courtesy Evolute GmbH). Bottom: final mesh corresponding to Figure 4 (image courtesy Waagner-Biro Stahlbau, cf. [7]).

thumbnailFigure 4. Yas Island Hotel during construction. At bottom left one can see a detail of the outer skin which exhibits torsion-free nodes (images courtesy Waagner-Biro Stahlbau).

2.2 Meshes with planar faces

Very often a steel construction is required to have planar faces for the simple reason that its faces have to be covered by planar glass panels. The planarity is of course easy to fulfill in case of triangle meshes (which do not admit torsion-free nodes), but this is not the case for quad meshes. From the architects’ side quad meshes have therefore become attractive (see, for example, [8,9]), but actual designs relied on simple constructions of meshes, such as parallel translation of one polyline along another polyline. The following problem turned out to be not so easy:

ProblemApproximate a given surface by a quad mesh<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M1','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M1">View MathML</a>with planar faces. The same question is asked for slightly more general combinatorics (quad-dominant meshes).

We call such meshes PQ meshes. R. Sauer (see the monograph [10]) has already remarked that a discrete surface’s PQ property is analogous to the conjugate property of a smooth surface <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M2','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M2">View MathML</a>, which reads

<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M3','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M3">View MathML</a>

(1)

In [11] the convergence of PQ meshes towards smooth conjugate surfaces is treated in a rigorous way. Numerical optimization of a mesh towards the PQ property has been done by [12]. Meanwhile it has turned out that from the viewpoint of numerics, planarity of quads is best achieved if we employ a target functional which penalizes non-intersecting diagonals of quadrilaterals:

<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M4">View MathML</a>

(2)

where the symbol ‘∨’ means the straight line spanned by two points. In practice this target functional has to be augmented by terms which penalize deviation from the reference surface and by a regularization term (for example, one which penalizes deviation of 2nd order differences from their previous values).

Since (2) - like any other equivalent target functional whose minimization expresses planarity - is highly nonlinear and non-convex, proper initialization is important. Essential information on how to initialize is provided by (1): A mesh covering a given surface Φ can be successfully optimized to become PQ only if the mesh polylines follow the parameter lines of a conjugate parametrization of the surface Φ. One example of such a curve network is the network of principal curvature lines, as demonstrated by Figure 5.

thumbnailFigure 5. Surface analysis - Islamic Art Museum in the Louvre, Paris (Bellini Architects). Top: A quad-dominant mesh which follows a so-called network of conjugate curves can be made such that faces are planar. Unfortunately this surface geometry does not leave us sufficient degrees of freedom to achieve a satisfactory quad mesh [14]. Bottom: Hybrid tri/quad mesh solutions with planar faces posses more degrees of freedom (images courtesy A. Schiftner). The one at bottom right has been realized.

Caveat. Design of freeform architecture does not work such that an amorphous ‘shape’ is created, and this shape is subsequently approximated by a PQ mesh for the purpose of making a steel-glass structure. The edges of such a decomposition into planar parts are highly visible and therefore must be part of the original design process. Nowadays it is possible to incorporate the PQ property already in the design phase, for instance by a plugin for the widely used software Rhino (see [13]).

2.3 Meshes with offsets

For multilayer constructions the following question is relevant:

ProblemFind an offset pairM, <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M5','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M5">View MathML</a>of PQ meshes which approximate a given surface (meaning these meshes are at constant distance from each other).

The distance referred to here can be measured between planes (which are then parallel), leading to a face offset pair of meshes; or it can be measured between edges (an edge offset pair, implying the same parallelity) or between vertices (if corresponding edges are parallel, we call this a vertex offset pair). For a systematic treatment of this topic we refer to [15]. A weaker requirement is the existence of a parallel mesh<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M6','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M6">View MathML</a> which is combinatorially equivalent to M but whose edges are parallel to their respective corresponding edge in M (here translated and scaled copies of M do not count).

There are several nice relations and characterizations of the various properties of meshes mentioned above. We use the term ‘polyhedral surface’ to emphasize that the faces of a mesh are planar.

– A polyhedral surface is capable of torsion-free nodes essentially if and only if it has a nontrivial parallel mesh. This is illustrated by Figure 6.

thumbnailFigure 6. Relation torsion-free nodes - multilayer structures. This image shows an ‘outer’ layer in front and an ‘inner’ layer behind it; these two layes are based on parallel meshes. One can clearly observe that the planes which connect corresponding edges serve as the symmetry planes of beams, and for each vertex these planes intersect in a node axis, which connects corresponding vertices (image courtesy B. Schneider).

– A polyhedral surface has a face/edge/vertex offset if and only if there is a parallel mesh whose faces/edges/vertices are tangent to the unit sphere.

– A PQ mesh has a face offset if and only if in each vertex the two sums of opposite angles between edges are equal. Optimization of a quadrilateral mesh such that its faces become planar, and such that in addition it has a face-offset, is done by augmenting (2) further by the functional (see Figure 7):

<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M7','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M7">View MathML</a>

(3)

thumbnailFigure 7. This mesh which possesses a face-face offset at constant distance has been created by an iterative design process which employs subdivision and optimization using both (2) and (3) in an alternating way (image courtesy B. Schneider).

– Similarly, a PQ mesh with convex faces has a vertex offset if and only if in each face the sums of opposite angles are equal (these sums then equal π).

– Any surface can be approximated by a PQ mesh which has vertex offsets, and the same for face offsets: initialize optimization from the network of principal curves. The class of meshes with edge offsets is more restricted. For more details see [12,15].

2.4 Curvatures of polyhedral surfaces

A pair of parallel meshes M, <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M8','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M8">View MathML</a> which are thought to be at distance d can be used to define curvatures of the faces of M. Note that the set of meshes combinatorially equivalent to M is a linear space, and the meshes parallel to M constitute a linear subspace. Consider the vertex-wise linear combination <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M9','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M9">View MathML</a> and the area <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M10','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M10">View MathML</a> of a face of <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M11','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M11">View MathML</a> as r changes: it is not difficult to see that we have

<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M12','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M12">View MathML</a>

(4)

The coefficients <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M13','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M13">View MathML</a>, <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M14','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M14">View MathML</a> are expressible via areas and so-called mixed areas of corresponding faces in M, <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M15','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M15">View MathML</a>. This expression is analogous to the well-known Steiner’s formula: The area of an offset surface <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M16','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M16">View MathML</a> at distance r of a smooth surface Φ is given by the surface integral

<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M17','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M17">View MathML</a>

(5)

where H, K are Gaussian and mean curvatures, respectively. It therefore makes sense to call <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M18','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M18">View MathML</a>, <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M19','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M19">View MathML</a> in (4) the mean curvature and Gaussian curvature of the face f (w.r.t. to the offset <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M20','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M20">View MathML</a>).

This definition is remarkable in so far as notable constructions of discrete minimal surfaces such as [16] turn out to have zero mean curvature in this sense. For details and further developments we refer to [11,17,18].

3 Conformal uniformization

Uniformization in general refers to finding a list of model domains and model surfaces such that ‘all’ domains/surfaces under consideration can be conformally mapped to one of the models. The unit disk and the unit sphere serve this purpose for the simply connected surfaces with boundary and for the simply connected closed surfaces without boundary, respectively.

Surfaces which are topologically equivalent to an annulus are conformally equivalent to a special annulus of the form <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M21','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M21">View MathML</a>, but the ratio <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M22','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M22">View MathML</a> is a conformal invariant, and there is a continuum of annuli which are mutually non-equivalent via conformal mappings. A classical theorem states that planar domains with n holes are conformally equivalent to a circular domain with n circular holes, and that domain is unique up to Möbius transformations. A similar result, whose statement requires the concept of Riemann surface, is true for surfaces of higher genus with finitely many boundary components.

3.1 Circle-packing meshes

It is very interesting how the previous paragraph is related to the following question, which for designers of freeform architecture is interesting to know the answer to:

ProblemFind a covering (within tolerance) of a surface by a circle pattern of mainly regular-hexagonal combinatorics.

It turns out that this and similar questions can be answered if one can solve the following:

ProblemGiven is a triangle meshM. Find a triangle mesh<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M23','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M23">View MathML</a>such that all pairs of neighbouring incircles of<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M24','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M24">View MathML</a>have a common point, but such that<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M25','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M25">View MathML</a>approximates M.

The property involving incircles - illustrated by Figure 8 - is called the circle-packing (‘CP’) property, and it is not difficult to see that such meshes are characterized by certain edge length equalities as shown by Figure 9. We can therefore set up a target functional for optimization of a mesh M which approximates a surface Φ:

<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M26','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M26">View MathML</a>

(6)

<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M27','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M27">View MathML</a>

The distances are measured to the tangent plane in the closest-point projection onto Φ; and similarly for the boundary curve’s tangent.

thumbnailFigure 8. Optimization of an irregular triangle mesh towards the circle-packing (CP) property.

thumbnailFigure 9. A triangle pair as shown has the incircle-packing property ⇔ <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M29','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M29">View MathML</a>.

We can further see from Figure 9 that a vertex has the same distance from all incircle contact points on adjacent edges: It follows that the CP property is equivalent to the existence a packing of vertex-centered balls: balls touch each other if and only if the corresponding vertices are connected by an edge (see Figure 10).

thumbnailFigure 10. The CP property is equivalent to the existence of a ball packing with centers in the vertices. Here red balls correspond to vertices with valence ≠6.

In [19] we discuss the relevance of these meshes for freeform architecture which is mainly due to the fact that we can cover surfaces with approximate circle patterns of hexagonal combinatorics, with hybrid tri-hex structures with excellent statics, and other derived constructions (see Figures 11 and 12).

thumbnailFigure 11. Structures derived from CP meshes: approximate circle packing with hexagonal combinatorics which covers a freeform design.

thumbnailFigure 12. Structures derived from CP meshes: hybrid tri-hex structure with planar facets and support structure derived from a CP mesh [19].

Numerical experiments show that optimizing a triangle mesh towards the CP property works in exactly those cases where topological equivalence implies conformal equivalence, but does not work otherwise. In the case of a surface topologically equivalent to an annulus (Figure 13) optimization works only if one of the two boundary curves is allowed to move freely.

thumbnailFigure 13. CP-optimization. Top: Great Court Roof, British Museum, London. Triangle mesh by Chris Williams (as built). Bottom: Combinatorially equivalent mesh with the CP property which approximates the same surface and its outer boundary. The inner boundary could move freely during optimization.

3.2 Discrete conformal mappings

If we had optimized triangular subdivisions of planar domains instead of spatial triangle meshes, the reason for the behaviour of numerical optimization mentioned in the previous paragraph would be clear. This is because in the planar case the CP meshes and associated ball packings are the same as the circle packings as studied by [20], and for these much is known: Two combinatorially equivalent circle packings constitute a discrete-conformal mapping of domains, and one can show convergence to the classical conformal mappings when packings are refined (in fact, this approach to conformal mappings was used in the proof of an extension of the Koebe normal form theorem to more general domains by He and Schramm in [21]).

To sum up, if a planar CP mesh M covers a domain D, then the conformal equivalence class of D is stored in M’s combinatorics. We can optimize a general triangle mesh which overs D towards the CP property only if the conformal class of D agrees with the conformal class stored in the combinatorics of the mesh. Except for topological disks and topological spheres, it is unlikely that this equality happens. As to surfaces, we state

ProblemShow that the natural correspondence between combinatorially equivalent CP meshes approximates a conformal mapping of surfaces (and make this statement precise by using an appropriate notion of refinement).

Unfortunately this problem - the only one in this paper which involves mathematics and not applications - is currently unsolved. There is, however, strong numerical evidence for an affirmative answer, and there is the known analogous planar case.

4 The paneling problem

An important part of the realization process of free-form skins is their decomposition into smaller parts (called panels) such that the entire cost of manufacturing and handling is as small as possible, and such that the numerous side-conditions concerning dimensions, overall smoothness, and so on are satisfied. In addition any resolution of the given design into panels must not visibly deviate from the original architect’s design (see Figures 14 and 15).

thumbnailFigure 14. A freeform design (National Holding Headquarters, Abu Dhabi, by Zaha Hadid Architects).

thumbnailFigure 15. Optimal decomposition into panels. Top: the design of Figure 14 is cut into panels along a given network of curves. Panels are of various types (planar, cylindrical, and so on). The total cost depends on the required quality.

4.1 Global panel optimization

A simple decomposition of a freeform facade typically leads to individual panels with no two of them being identical: in the worst case, their manufacturing is possible only by first manufacturing a mold for each. [22] presents a procedure which combines both combinatorial and continuous optimization in an effort to reduce the total cost, and which is based on the concept of mold reuse. The idea is that a guiding curve network is given. Such guiding curves are highly visible on the finished building so it is safe to assume the architect has firm ideas on their shape! We seek a decomposition of the facade into pieces which are easily manufacturable.

The production processes employed here may be of different kinds: Flat pieces are easily made by cutting them out from readily available panels; cylinder-shaped pieces have to be bent by a machine which is not cheap; truly freeform pieces have to be shaped by hot bending, using a mold which has to be specially made and which is far from cheap. Note that once a mold is available, we can use it to manufacture any surface which by a Euclidean congruence transformation can be moved so as to be a subset of the mold surface. Using the word ‘mold’ for all kinds of production processes, we state:

ProblemFind out how the given panels may be replaced by other panels which can be produced by a small number of molds, thereby minimizing production cost under the side condition that the overall surface does not change visibly.

A more precise problem statement is the following: Given a network of curves on a freeform surface which is thereby dissected into a collection P of panels,

(1) specify a set M of admissible molds. Each mold m has an integer type <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M29','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M29">View MathML</a> and a shape <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M30','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M30">View MathML</a> which typically is some n-tuple of reals. There are costs <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M31','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M31">View MathML</a> of providing a mold of type i, and costs <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M32','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M32">View MathML</a> of producing a panel from such a mold;

(2) find an assignment <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M33">View MathML</a> of molds to panels, such that the total cost

<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M34','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M34">View MathML</a>

is minimal, under the side-conditions of bounded deviation from the curve network and bounded kink angles.

An implication of this simple cost model is that one should favour cheap production processes/molds, and if an expensive one is necessary it should be used to produce more than just one panel. Optimization contains a discrete part similar to set cover (the mold type assignment) and a continuous part (choosing the mold shapes). An example is shown by Figures 1416.

thumbnailFigure 16. Reflection lines help in visually inspecting the achieved surface quality for the three examples (a)–(c) shown by Figure 15.

The high complexity of this optimization task is caused by the sheer number of panels (thousands) and the coupling of different panels if they are assigned to the same mold. It turns out that it contains an NP hard subproblem. Several devices for acceleration are employed, for example, fast estimates from above of the distance of molds in shape space. For details we refer to [22,23].

4.2 Wooden panels: level set methods

If a bendable rectangle is forced to lie on a surface, it roughly follows a geodesic curve on that surface (see, for example, [25]). These geodesics are defined by having zero geodesic curvature, and at the same time they are the shortest paths on the surface. The covering of a surface by such panels requires the solution of the following geometric problem:

ProblemFind a layout of a pattern of geodesics which are (within tolerance) at equal distance from each other.

The literature contains suggestions for experimental solutions of this problem (see Figure 17). Firstly it must be said that very few surfaces possess patterns of geodesics which run parallel at constant distance: They exist precisely on the intrinsically flat surfaces with vanishing Gaussian curvature. For infinitesimally close geodesics, the distance has the form <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M35','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M35">View MathML</a>, where <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M36','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M36">View MathML</a>s is an arc length parameter, and <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M37','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M37">View MathML</a> obeys the Jacobi differential equation <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M38','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M38">View MathML</a>, where K is the Gaussian curvature. If <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M39','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M39">View MathML</a> it is not difficult to show that every interval longer than <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M40','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M40">View MathML</a> contains a zero of <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M41','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M41">View MathML</a>, so it is not even possible that two geodesics run side by side without intersection [26].

thumbnailFigure 17. Experimental geodesic pattern [24].

In [27,28] we have shown how to algorithmically approach the problem of laying out a pattern of near-geodesics which have approximately constant distance from each other. A level set method turns out to be useful: It is well known that equidistant curves may be seen as level sets of a function ϕ for which

<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M42','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M42">View MathML</a>

(7)

vanishes (that is, ϕ fulfills the eikonal equation). The geodesic property of level sets is expressed by vanishing of

<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M43','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M43">View MathML</a>

(8)

(see [26], p. 142]). We accordingly minimize a target functional which combines the competing <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M44','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M44">View MathML</a> norms of both (7) and (8) together with <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M45','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M45">View MathML</a> and additional terms which penalize deviation from other desired properties like prescribed directions, and so on.

This is numerically done by describing the underlying surface as a triangle mesh with typically <106 vertices, and considering ϕ as function on the vertices, with piecewise-linear interpolation in the faces of the mesh. The gradient of such a function is then piecewise constant, and for any vector field X and vertex v, we evaluate <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M46','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M46">View MathML</a> from the flux of X through the boundary of v’s intrinsic Voronoi cell. The resulting optimization problem is solved by standard Gauss-Newton methods (similar to the other problems of numerical optimization we considered above), augmented by CHOLMOD for sparse Cholesky factorization [29].

4.3 Segmentation: image processing methods

In general it is not possible to cover a surface by a smooth pattern of panels which in their un-bent state are rectangular or at least cut from rectangles. It is necessary to perform segmentation into panelizable parts. This can be formulated as follows:

ProblemDecompose a given surface Φ into a finite number of domains with piecewise-smooth boundaries each of which may be covered by a (within tolerance) constant-distance pattern of geodesics.

For that purpose we describe families of curves as integral curves of a unit vector field. It turns out that the geodesic property can be characterized by the symmetry of the covariant derivative mapping <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M47','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M47">View MathML</a>, which is linear within each tangent space:

<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M48','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M48">View MathML</a>

(9)

The dependence on the point <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M49','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M49">View MathML</a> is indicated by the subscript to the scalar products. The norm <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M50','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M50">View MathML</a> measures how far V deviates from the geodesic property locally around the point p.

Any unit vector field W, and in particular one which has been created interactively by a designer, can now be approximated by a piecewise geodesic vector field V which occurs as a minimizer of a target functional suitable constructed from weighted integrals of the functions

<a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M51','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M51">View MathML</a>

together with regularizing terms. For details we refer to [27]. The function ρ could be any of the heavy-tailed functions used in image sharpening (cf. [30]), we used the Geman-McClure estimator [31]. This causes high values of <a onClick="popup('http://www.mathematicsinindustry.com/content/1/1/4/mathml/M52','MathML',630,470);return false;" target="_blank" href="http://www.mathematicsinindustry.com/content/1/1/4/mathml/M52">View MathML</a> to be concentrated along curve-like regions which become the boundaries of domains. For the actual segmentation we employed the method of [32]. An example is shown by Figures 18 and 19.

thumbnailFigure 18. Piecewise-geodesic vector fields. Left: A design vector field W. Right: A piecewise-geodesic vector field V which approximates W and whose discontinuities lead to segmentation of the underlying surface [27].

thumbnailFigure 19. A design with bent rectangular panels based on segmentation of the surface of Figure 18. The underlying patterns of geodesics have been found by a further method not described in this paper (see [27]).

Competing interests

The authors declare that they have no competing interests.

Acknowledgements

This article surveys results obtained within the framework oft the National Research Network ‘Industrial Geometry’ (grants No. S9206, S9209, Austrian Science Fund). It was partly supported by the 7th framework programme of EU (grant agreement ‘ARC’ No. 230520) and by grant No. 813391 of the Austrian Science Promotion Agency (FFG). We are grateful to coauthors of all papers referenced in the paper for the use of figures, and to Waagner Biro Stahlbau, Vienna, to Zaha Hadid Architects, London, to RFR, Paris, and to Evolute GmbH, Vienna, for making geometry data available to us.

References

  1. Ceccato, C, Hesselgren, P, Pauly, M, Pottmann, H, Wallner, J: Advances in Architectural Geometry 2010, Springer, New York (2010)

  2. Pottmann, H, Asperl, A, Hofer, M, Kilian, A: Architectural Geometry, Bentley Institute Press, Exton, PA (2007)

  3. Pottmann, H: Geometry and new and future spatial patterns. Archit. Des.. 79(6), 60–65 (2009)

  4. Pottmann, H: Architectural geometry as design knowledge. Archit. Des.. 80(4), 72–77 (2010)

  5. Pottmann, H, Wallner, J: Freiformarchitektur und Mathematik. Mitt. DMV. 18(2), 88–95 (2010)

  6. Warren, J, Weimer, H: Subdivision Methods for Geometric Design: A Constructive Approach, Morgan Kaufmann, San Francisco (2001)

  7. Frey, H, Reiser, B, Ziegler, R: Yas Island Marina-Hotel – Pole position in Abu Dhabi. Stahlbau. 78(10), 758–763 (2009). Publisher Full Text OpenURL

  8. Glymph, J, Shelden, D, Ceccato, C, Mussel, J, Schober, H: A parametric strategy for freeform glass structures using quadrilateral planar facets. Proc. Acadia. 303–321 (2002)

  9. Schober, H: Freeform Glass Structures. Glass Processing Days. 46–50 (2003)

  10. Sauer, R: Differenzengeometrie, Springer, Berlin (1970)

  11. Bobenko, A, Suris, Y: Discrete Differential Geometry: Integrable Structure, American Math. Soc., Providence, RI (2008)

  12. Liu, Y, Pottmann, H, Wallner, J, Yang, YL, Wang, W: Geometric modeling with conical meshes and developable surfaces. ACM Trans. Graph.. 25(3), 681–689 (2006). Publisher Full Text OpenURL

  13. Evolute GmbH: Evolutetools for Rhino. http://www.evolute.at (2010)

  14. Zadravec, M, Schiftner, A, Wallner, J: Designing quad-dominant meshes with planar faces. Comput. Graph. Forum. 29(5), 1671–1679 (2010). Publisher Full Text OpenURL

  15. Pottmann, H, Liu, Y, Wallner, J, Bobenko, A, Wang, W: Geometry of multi-layer freeform structures for architecture. ACM Trans. Graph.. 26(3), (2007)

  16. Bobenko, A, Hoffmann, T, Springborn, B: Minimal surfaces from circle patterns: geometry from combinatorics. Ann. Math.. 164, 231–264 (2006). Publisher Full Text OpenURL

  17. Bobenko, A, Pottmann, H, Wallner, J: A curvature theory for discrete surfaces based on mesh parallelity. Math. Ann.. 348, 1–24 (2010). Publisher Full Text OpenURL

  18. Müller, C, Wallner, J: Oriented mixed area and discrete minimal surfaces. Discrete Comput. Geom.. 43, 303–320 (2010). Publisher Full Text OpenURL

  19. Schiftner, A, Höbinger, M, Wallner, J, Pottmann, H: Packing circles and spheres on surfaces. ACM Trans. Graph.. 28(5), (2009)

  20. Stephenson, K: Introduction to Circle Packing, Univ. Press, Cambridge (2005)

  21. He, ZX, Schramm, O: Fixed points, Koebe uniformization and circle packings. Ann. Math.. 137, 369–406 (1993). Publisher Full Text OpenURL

  22. Eigensatz, M, Kilian, M, Schiftner, A, Mitra, N, Pottmann, H, Pauly, M: Paneling architectural freeform surfaces. ACM Trans. Graph.. 29(4), (2010)

  23. Eigensatz, M, Deuss, M, Schiftner, A, Kilian, M, Mitra, NJ, Pottmann, H, Pauly, M: Case studies in cost-optimized paneling of architectural freeform surfaces. In: Ceccato C., Hesselgren P., Pauly M., Pottmann H., Wallner J. (eds.) Advances in Architectural Geometry 2010, pp. 49–72. Springer, New York (2010)

  24. Spuybroek, L: NOX: Machining Architecture, Thames & Hudson, London (2004)

  25. Pirazzi, C, Weinand, Y: Geodesic lines on free-form surfaces: optimized grids for timber rib shells. Proc. World Conference on Timber Engineering. 7 (2006)

  26. do Carmo, MP: Riemannian Geometry, Birkäuser, Boston (1992)

  27. Pottmann, H, Huang, Q, Deng, B, Schiftner, A, Kilian, M, Guibas, L, Wallner, J: Geodesic patterns. ACM Trans. Graph.. 29(4), (2010)

  28. Wallner, J, Schiftner, A, Kilian, M, Flöry, S, Höbinger, M, Deng, B, Huang, Q, Pottmann, H: Tiling freeform shapes with straight panels: algorithmic methods. In: Ceccato C., Hesselgren P., Pauly M., Pottmann H., Wallner J. (eds.) Advances in Architectural Geometry 2010, pp. 73–86. Springer, New York (2010)

  29. Chen, Y, Davis, TA, Hager, WW, Rajamanickam, S: Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate. ACM Trans. Math. Softw.. 35(3), (2008)

  30. Levin, A, Fergus, R, Durand, F, Freeman, WT: Image and depth from a conventional camera with a coded aperture. ACM Trans. Graph.. 26(3), (2007)

  31. Geman, S, McClure, DE: Statistical methods for tomographic image reconstruction. Bull. Inst. Internat. Stat.. 52(4), 5–21 (1987)

  32. Pauly, M, Keiser, R, Gross, M: Multi-scale feature extraction on point-sampled surfaces. Comput. Graph. Forum. 22(3), 281–290 (2003). Publisher Full Text OpenURL