Constrained Planar Remeshing For Architecture

To appear in Proceedings of Graphics Interface 2007the work by Turk [23], Alliez et al. [1], and Surazhsky et al. [22](among others) would be very applicable.The work of Cohen-Steiner et al. [6] was particularly motivatingto us, and on first glance is the exact tool to solve the non-planarityissues that challenged the project described in the previous section.In their work a pre-specified number of face clusters are fit to theoriginal surface geometry using Lloyd’s relaxation (a k-means clustering technique). Then planar proxies are fit to these clusters andconnected to create a polygonal mesh. This work is effective forsimplification and working with polygons rather than triangles reduces the number of vertices that must be sent to the graphics hardware. Unfortunately, the final polygon vertices are computed by averaging the projection of an original mesh vertex onto each proxyas illustrated below and in general the final vertex position does notlie on the proxy planes. Thus, facets which have more than threevertices will likely be non-planar.irregular triangular meshes that do not meet the requirements discussed earlier and lack the user control that is necessary for applications in architectural design.1.4OverviewThe contributions of this paper are: An algorithm to fit planar polygonal panels to arbitrary inputgeometry; A user-controllable metric for clustering the surface that controls the distribution and shape of the resulting panels; Control of relative panel shape and density through a paintbrush metaphor or procedural scripting; Consideration of important structural and fabrication issuesincluding offset planes for chamfering; and A full-featured prototype system implementation that wasused in an architectural design seminar and integrated into afabrication pipeline.Furthermore, for any but the simplest shapes the vertices fromthis remeshing cannot simply be moved such that the all facets areplanar. Attempting to do so for non-trivial inputs will require vertexand neighborhood shuffling (discussed in Sections 2.2 & 2.3 and illustrated in Figures 6 & 7). Furthermore the positions cannot betrivially optimized to be planar since the solution space is highlydiscontinuous. The neighborhood of a particular facet is not stablefrom iteration to iteration preventing the incorporation of optimization terms to constrain the vertices appropriately.Alternatively, we could view this planar remeshing task as anincremental simplification problem and attempt to use an edge orface collapse technique [8, 11, 12, 20] to incrementally convergeon a polygonal model. This strategy has the advantage of creating a continuum of legally constructable intermediate meshes, butmay quickly become stuck in a local minimum due to complications with the polygonal planarity requirement. We plan to explorethis avenue in future work.The planar quadrilateral meshing work of Liu et al. [15] sharesmany challenges with our project. Their solution involves determining an appropriate local parameterization along which theyalign a regular quad mesh. Their mesh is further constrained to alsofit an offset surface suitable for fabrication (avoiding the chamferproblem discussed earlier). Furthermore, their work extends nicelyto generate developable surfaces which are of significant interestfor architectural applications.Other research projects have tackled various fabrication challenges. Chen et al. [5], Mitani et al. [16], and Haeberli [9] examinehow to subdivide a target shape into strips or patches that are wellapproximated by a developable surface, which can be formed froma material such as sheet metal or paper that allows bending but notstretching. Branco and Soares [3] modify a developable surfaceby cutting and separating or overlapping the material (similar toa tailor’s darts) to build surfaces with double curvature. Julius etal. [13] generate quasi-developable patches within a specified tolerance for applications where minor stretching is allowed. Wu andKobbelt [25] further generalize the cluster based remeshing strategy to fit portions of the model to spheres and cylinders. A complex blend operation is required to fuse the different elements of themodel together.The area of dimensionality reduction, and specifically the Locally Linear Embedding framework [4, 18], contains interestingparallels to our project. The work of Kirasanov and Gortler [14]can be used to obtain a piecewise planar approximation of an arbitrary mesh, but the memory usage and performance could be prohibitively high. Furthermore, the output of these techniques are2P LANAR R EMESHING A LGORITHMThe reluctant acceptance of non-planar facets by the architects forthe project described in Section 1.2 emphasizes the challenges offabrication remeshing. In general it is not possible to simply adjustthe facet vertices in a post-process. We illustrate some of thesedifficulties in images throughout this paper. Instead, we approachthe problem by choosing planes and place vertices where the planesintersect. The initial stages of our method closely follow that ofCohen-Steiner et al. [6] to select a good distribution of planes usingthe randomized optimization method. Here is the basic pipeline ofthe system:Cluster Metric tPlanesPlanarPanelsInitially we choose n random seed triangles on the surface ofthe mesh, where n is the target number of planes specified by theuser. Then we divide the remaining triangles in the model into clusters around these seeds, ensuring that the triangles in each clusterare contiguous. The clustering step is iterated by computing a newcenter/seed for each cluster and then re-clustering. For an initialconfiguration of well-distributed random seeds, ten to twenty iterations is generally sufficient for convergence and to evenly distributethe triangles across the surface and into clusters of similar area (Figure 5).In the following sections we describe our contributions; in particular, how to intersect the resulting proxy planes and form a closedmodel. If the intersection fails, it is necessary to pipe this information back into the clustering stage and try again.2.1Determining the Local NeighborhoodOnce the clustering has reached a fixed point (or converged sufficiently), we must intersect the planes with their neighbors to find aplanar polygonal remeshing. For convex shapes we could use anystandard O(n log n) algorithm to compute the half space intersection [7]. Since the neighborhood information is available in ourdata structure, we can actually do this in O(n) time by walking theboundary of each cluster and intersecting it with the proxy planescorresponding to neighboring clusters. This method works for both3

To appear in Proceedings of Graphics Interface 2007a)b)c)d)e)f)Figure 5: The basic algorithm begins by a) selecting random seed triangles from the original mesh. Next the mesh is b&c) iteratively clusteredabout these seeds and the seeds are repositioned; d) shows a visualization of the original mesh triangles projected onto the corresponding proxyplanes; e) using the vertices and neighbors from the clusters we render non-planar polygons, similar to Cohen-Steiner et al. [6]; and f) the properintersection of the neighboring planes.convex and non-convex objects. In convex portions of the modelthe result is identical to a half-space intersection. In areas of negative curvature, the concept of a cluster center and the local neighborhood facilitates the construction of a corresponding polygonalremeshing.However, since the cluster neighborhoods are a function of boththe underlying triangular mesh and the cluster metric, this methodis not robust and often requires some cleanup. This is due to thefact that the set of cluster neighbors is not necessarily the sameas the set of neighbors that define consistently intersected panels.Figure 6 shows an example where the polygonal boundary of a facetself-intersects, we call this geometric error a flipped edge.be more complicated and expensive (Figure 3).In our system we allow concave facets. This decision made theimplementation of various tasks from rendering to area computationfar more challenging. We do restrict all panels to be star-shaped(that is, have a non-null kernel). By comparing the orientation ofeach facet edge relative to a point in the kernel, we can quicklydetect geometric anomalies such as flipped edges (Figure 6). Wehave not found this restriction to limit the surfaces we are able toremesh with planar panels. Furthermore, with the implementationof alternate methods for rendering and detection of flipped edgesthis restriction can be lifted to allow general concave facets.2.32.2Complex Curvature and Panel ShapeThe largest challenge for the algorithm is that not every clusteringof the original triangles will lead to a legal planar remeshing. Insome cases the problem is simply that too few clusters were specified by the user to solve the target geometry. For example, it isimpossible to intersect three planes to achieve a closed remeshingthat approximates a genus zero shape. Some of these cases couldbe resolved by analyzing the surface (or a portion of the surface)to determine the minimum number of panels necessary to matchthe topology and genus of the input shape. However, this will nothandle all cases. Consider the configuration below in cross section.The red curved input shape has been approximated by three blueplanar proxy surfaces that happen to be parallel. Since these planesdo not intersect, we cannot use them to find a planar remeshing.Trying the basic algorithm on non-convex target surface shapes uncovers a key challenge in this fabrication problem. To mesh theneighborhood at a saddle point (or generally, areas with negativecurvature) we must either a) allow concave panels or b) have morethan three panels meeting at some vertices. A simple non-convexshape is shown in Figure 8. Depending on the material to be usedfor construction, one of these two solutions may be more desirable.For example, it is impractical to make concave inner corner cuts inglass; thus, non-convex facets must be split at the concave corners.If we choose to allow four or more planes at these vertices, wemust ensure that all planes intersect at a single point (within therequired construction tolerance). Furthermore, we will encounteran interesting offset problem in fabrication. The panels will havenon-zero thickness and we need to make sure that not only do thefour planes intersect at the single surface vertex, but that the fouroffset planes also intersect cleanly. If this offset problem is notsolved, the construction process will require extra chamfering anda)b)Challenging Proxy Plane ConfigurationsAlso consider the more general case below where the planes dointersect, but not where they are supposed to intersect. The intersection is on the wrong side of the patch and though the algorithm cansuccessfully compute vertices for each facet, the facets will havemany flipped edges and will be rendered inconsistently.c)We detect this “spike” problem vertex (Figure 7b) by computingthe distance between the cluster boundary vertex and the planar intersection vertex. An intersection vertex is flagged if this distance isgreater than a reasonable threshold (we use 0.2 * the average clusterdiameter). The algorithm attempts to resolve these problems withtwo different techniques.First, the three proxy planes defining a flagged vertex are tiltedto bring the intersection closer to the cluster boundary vertex. Typically, the normal of a planar proxy is computed for a collectionof triangles as the eigenvector of the smallest eigenvalue (L2 ) ORthe average of the triangle normals weighted by area (L2,1 ) [6]. ForFigure 6: In the initial clustering of this object, a) four patchesmeet at a single original mesh vertex. The proxy intersection routine randomly chooses how to structure the local neighborhood todefine vertices at the intersection of three planes. b) In this example, the random choice is incorrect, causing self-intersection of thepolygon boundaries for the pink and gray facets. This is detected asa mis-oriented or flipped edge and visualized with a red triangle. c)Once detected, this problem is easily fixed by switching the neighborassignments.4

To appear in Proceedings of Graphics Interface 2007a)b)c)d)e)f)Figure 7: One way to detect potential problems in the a) triangle clustering is to b) study the difference vector from the vertex where threeor more clusters meet (green) to the vertex found when the corresponding proxy planes are intersected (red). When this vector is relativelylarge, we may have c) difficulty resolving this particular set of planes into a topologically consistent mesh. This information is used to refine thesolution and create d) a constructable planar remeshing. To simplify rendering we require that all panels be star-shaped, i.e., that they have e)a non-null kernel. Any point within the kernel can be used to f) draw the star-shaped panels and easily detect flipped edges (Figure 6).planes surrounding a flagged vertex we average this result with theplane that passes through the proxy center and the cluster boundary vertex. We do not include this term for non-spike intersectionvertices because it could inappropriately bias the solution.Second, we shuffle the planes (Cohen-Steiner et al. [6] refer tothis as teleportation). We split a plane (seed a new cluster) near theproblem area and merge two planes elsewhere in the model whereperhaps the extra detail is less important. To ensure that the newcluster does not float away immediately, we flag the new clusterseed and its immediate neighbors as sticky and restrict its movement for several iterations. Figure 9 shows examples of challengingsurfaces which require these techniques.The detection and correction of these problems bound the errorof our planar approximation, although we have not formalized theerror bounds.2.4meet at the boundary, we define a panel vertex. This point is placedon the intersection line between the two neighboring planes andclosest to the boundary. Each cluster that touches the boundary isassigned one or more extra vertices along the border to ensure thatthe chamfered edge detail of the boundary is planar. More than oneextra vertex is used as necessary to ensure that the overall area ofthe polygonal remeshing closely matches the area of the input shape(Figure 11).3The algorithms described above were implemented in parallel withan architectural design seminar consisting of a half dozen designstudents. The participants applied the software and the various visualization tools for developing designs with complex curved geometry. They were exposed to and struggled with real-world fabricationconstraints as they tried to coax their visions into shapes that couldbe constructed within the projected budget. Their experiences werecritical in pushing the limits of the algorithm’s robustness.Multiple Clusters per Proxy PlaneOccasionally the optimal partitioning by a particular cluster metric suggests an impossible facet neighborhood. While the clustering method ensures contiguous clusters, it does not guarantee thata cluster is not completely surrounded by another cluster, or thata cluster does not have a hole, etc. Examples of neighborhoodsthat cannot be resolved are shown in Figure 10. These issues cannot always be corrected simply by adjusting or changing the cluster metric. It is necessary to automatically detect these conditionsand break the cluster into separate pieces. As above, we make thischange sticky to prevent it from being un-done immediately.To prevent numerical issues when computing the intersection ofnearly coplanar proxies, neighboring clusters whose normal differsby less than an angular threshold (we use 1 ) will be snapped to thesame master plane, as shown in Figure 11.2.5U SER C ONTROL3.1Surface PreparationThe input NURBS or subdivision surface must first be discretized:in our system the discrete mesh elements are triangles. Furthermore, the input geometry should be re-triangulated as necessary toensure an appropriate resolution and density for the target shapeand the number of panels that will be fit to its surface. The maximum edge length of the triangulated mesh bounds the quality ofthe iterative clustering optimization. This algorithm is a discreteoptimization both in partitioning triangles into clusters and in determining the local neighborhood of the panels. Longer edge lengthsreduce the number of possible discrete partitionings and possibleBoundary ConditionsOur prototype implementation also handles non-closed shapes, asshown in many of the examples in this paper. Normally, a panelvertex is defined where three clusters intersect. The boundary istreated as a special NULL cluster object. Thus, where two clustersFigure 8: For non-convex input geometry, the intersection of proxyplanes becomes more challenging. At the saddle point in the centerof this example we must have either three facets of which at leastone is non-convex (left) or four or more convex facets (right).Figure 9: Computing a proper planar remeshing of surface twists likethe helix example on the left is challenging. In particular, note thesharp, non-convex, bowtie-shaped facets created where the surfacehas double curvature.5

To appear in Proceedings of Graphics Interface 2007Figure 10: In the left image, the dark purple cluster is contiguous,but has a hole in the center. This cluster cannot be resolved witha single panel in our system and will be broken into multiple panels.In the right image, we see an alternate partitioning (using a greaternumber of seeds) that requires the blue, orange, and green clustersto intersect at two different points, which is impossible unless theplanes are degenerate.Figure 11: Although the wide band of triangles surrounding the bumpin this model match very well using the L2 and L2,1 metrics, theycannot all be grouped together to form a single panel in our system,which requires that the planar facets be star-shaped. To ensurenumerical stability, neighboring proxy planes with similar normal aresnapped to a single master plane. Also, note that panels on theboundary of the geometry are assigned one or more extra vertices toensure adequate coverage (Section 2.5).solutions. The total number of triangles dictates the performance.A single iteration of the clustering stage runs in O(m log m) time toassign m triangles, using a priority queue containing as many as melements.3.2Clustering Metric ParametersThe designer using the tool has significant influence over the ultimate planar remeshing. First and foremost the user controls thenumber of panels, which is the dominating factor in the cost ofthe physical object. Using more panels will result in a surface thatmore accurately matches the original surface, but will most likelycost more to machine and assemble.The designer also controls the general shape of the panels usingthe cluster metric. This is done by offering the designer a selection of simple metrics that can be used singly or combined into alarger function by weighting the different terms. The first metric weimplemented was the Euclidean distance measured from the centerof each triangle to the proxy centroid. This metric results in clusters that are generally round with uniform size, similar to the earlyVoronoi cell remeshing project (Section 1.2). We also implementedthe two metrics demonstrated by Cohen-Steiner et al. [6]: the L2and L2,1 metrics, which orient cells along the surface based on local curvature. With the fourth metric, the user can paint a densitymap over the surface to control the relative size of the panels. Thesefour terms are applicable during all clustering iterations. Once theneighborhood of a cluster has been determined and the boundariesof a facet have been computed, our fifth metric is available. Weproject the centroid of a triangle to the target proxy plane and compare it to the boundary of the corresponding facet. If this point lieswithin the boundary the value of the final metric is zero. If it liesoutside, the value is the distance to the boundary.In order to combine these separate terms into a single useful metric, it is crucial

To appear in Proceedings of Graphics Interface 2007 the work by Turk [23], Alliez et al. [1], and Suraz