skip to main content
research-article

Triangle surfaces with discrete equivalence classes

Published: 26 July 2010 Publication History

Abstract

We propose a technique that takes a triangulated surface as input and outputs a surface with the same topology but altered geometry such that each polygon falls into a set of discrete equivalence classes. We begin by describing an error function that measures how close the polygons are to satisfying this criteria. To optimize this error function, we first cluster triangles into discrete sets such that the assignment of sets minimizes our error. We then find canonical polygons for each set using nonlinear optimization. Next, we solve a Poisson equation to find positions of vertices such that the surface polygons match the canonical polygons as close as possible. We also describe how to incorporate a fairness criteria into the optimization to avoid oscillations of the surface. We iterate this entire process until we reach a user specified tolerance, possibly adding clusters during iteration to guarantee convergence. We have been able to successfully reduce the number of unique triangles to lie within a small percentage of the total number of triangles in the surface and demonstrate our technique on various examples.

Supplementary Material

JPG File (tp011-10.jpg)
MP4 File (tp011-10.mp4)

References

[1]
Arthur, D., and Vassilvitskii, S. 2007. k-means++: the advantages of careful seeding. In Proceedings of the 18th annual ACM-SIAM symposium on Discrete algorithms, 1027--1035.
[2]
Arun, K. S., Huang, T. S., and Blostein, S. D. 1987. Least-squares fitting of two 3-d point sets. IEEE Trans. Pattern Anal. Mach. Intell. 9, 5, 698--700.
[3]
Cutler, B., and Whiting, E. 2007. Constrained planar remeshing for architecture. In Proceedings GI '07, ACM, New York, NY, USA, 11--18.
[4]
Dos Passos, V. A., and Walter, M. 2008. 3d mosaics with variable-sized tiles. Vis. Comput. 24, 7, 617--623.
[5]
Drew, P. 2008. New Tent Architecture. Thames & Hudson, June.
[6]
Eigensatz, M., Kilian, M., Schiftner, A., Mitra, N., Pottmann, H., and Pauly, M., 2010. Paneling architectural freeform surfaces. To appear in ACM SIGGRAPH.
[7]
Elber, G., and Wolberg, G. 2003. Rendering traditional mosaics. The Visual Computer 19, 67--78.
[8]
Frandsen, P. E., Jonasson, K., Nielsen, H. B., and Tingleff, O., 2004. Unconstrained optimization, 3rd edition.
[9]
Fu, C.-W., Lai, C.-F., He, Y., and Cohen-Or, D., 2010. K-set tilable surfaces. To appear in ACM SIGGRAPH.
[10]
Grünbaum, B., and Shephard, G. C. 1986. Tilings and patterns. W. H. Freeman & Co., New York, NY, USA.
[11]
Kim, J., and Pellacini, F. 2002. Jigsaw image mosaics. In ACM SIGGRAPH '02, ACM, New York, NY, USA, 657--664.
[12]
Lai, Y.-K., Hu, S.-M., and Martin, R. R. 2006. Surface mosaics. Vis. Comput. 22, 9, 604--611.
[13]
Liu, Y., Pottmann, H., Wallner, J., Yang, Y.-L., and Wang, W. 2006. Geometric modeling with conical meshes and developable surfaces. In ACM SIGGRAPH '06, ACM, New York, NY, USA, 681--689.
[14]
Pavic, D., Ceumern, U., and Kobbelt, L. 2009. Gizmos: Genuine image mosaics with adaptive tiling. Comput. Graph. Forum 28, 8, 2244--2254.
[15]
Pottmann, H., Liu, Y., Wallner, J., Bobenko, A., and Wang, W. 2007. Geometry of multi-layer freeform structures for architecture. In ACM SIGGRAPH '07, ACM, New York, NY, USA, 65.
[16]
Pottmann, H., Schiftner, A., Bo, P., Schmiedhofer, H., Wang, W., Baldassini, N., and Wallner, J. 2008. Freeform surfaces from single curved panels. In ACM SIGGRAPH '08, ACM, New York, NY, USA, 1--10.
[17]
Schiftner, A., Höbinger, M., Wallner, J., and Pottmann, H. 2009. Packing circles and spheres on surfaces. In ACM SIGGRAPH Asia '09, ACM, New York, NY, USA, 1--8.
[18]
Wang, L., Yu, Y., Zhou, K., and Guo, B. 2009. Example-based hair geometry synthesis. In ACM SIGGRAPH '09, ACM, New York, NY, USA, 1--9.
[19]
Yu, Y., Zhou, K., Xu, D., Shi, X., Bao, H., Guo, B., and Shum, H.-Y. 2004. Mesh editing with poisson-based gradient field manipulation. In ACM SIGGRAPH '04, ACM, New York, NY, USA, 644--651.

Cited By

View all
  • (2025)Design and optimisation of grid shells for maximising both structural performance and panel similarityEngineering Structures10.1016/j.engstruct.2025.119820329(119820)Online publication date: Apr-2025
  • (2024)Computational Design of a Kit of Parts for Bending Active StructuresACM Transactions on Graphics10.1145/368796643:6(1-16)Online publication date: 19-Dec-2024
  • (2024)Designing triangle meshes with controlled roughnessACM Transactions on Graphics10.1145/368794043:6(1-20)Online publication date: 19-Dec-2024
  • Show More Cited By

Index Terms

  1. Triangle surfaces with discrete equivalence classes

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Transactions on Graphics
    ACM Transactions on Graphics  Volume 29, Issue 4
    July 2010
    942 pages
    ISSN:0730-0301
    EISSN:1557-7368
    DOI:10.1145/1778765
    Issue’s Table of Contents
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 26 July 2010
    Published in TOG Volume 29, Issue 4

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. discrete sets
    2. equivalence classes
    3. mesh discretization

    Qualifiers

    • Research-article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)18
    • Downloads (Last 6 weeks)5
    Reflects downloads up to 07 Mar 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2025)Design and optimisation of grid shells for maximising both structural performance and panel similarityEngineering Structures10.1016/j.engstruct.2025.119820329(119820)Online publication date: Apr-2025
    • (2024)Computational Design of a Kit of Parts for Bending Active StructuresACM Transactions on Graphics10.1145/368796643:6(1-16)Online publication date: 19-Dec-2024
    • (2024)Designing triangle meshes with controlled roughnessACM Transactions on Graphics10.1145/368794043:6(1-20)Online publication date: 19-Dec-2024
    • (2024)Clustering and optimization of nodes, beams and panels for cost-effective fabrication of free-form surfacesEngineering Structures10.1016/j.engstruct.2024.117912307(117912)Online publication date: May-2024
    • (2024)Bending-Reinforced Grid Shells for Free-form Architectural SurfacesComputer-Aided Design10.1016/j.cad.2023.103670168(103670)Online publication date: Mar-2024
    • (2023)Masonry Shell Structures with Discrete Equivalence ClassesACM Transactions on Graphics10.1145/359209542:4(1-12)Online publication date: 26-Jul-2023
    • (2023)Reducing the number of different nodes in space frame structures through clustering and optimizationEngineering Structures10.1016/j.engstruct.2023.116016284(116016)Online publication date: Jun-2023
    • (2023)Modeling with discrete equivalence classes of planar quadsComputers & Graphics10.1016/j.cag.2023.07.032115(404-411)Online publication date: Oct-2023
    • (2023)Reducing the Number of Different Faces in Free-Form Surface Approximations Through Clustering and OptimizationComputer-Aided Design10.1016/j.cad.2023.103633(103633)Online publication date: Oct-2023
    • (2022)Rationalizing Architectural Surfaces Based on Clustering of JointsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.308568528:12(4274-4288)Online publication date: 1-Dec-2022
    • Show More Cited By

    View Options

    Login options

    Full Access

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media