A general and efficient method for finding cycles in 3D curve networks

ACM Transactions on Graphics 32(6), Proceedings of SIGGRAPH Asia 2013
Yixin Zhuang1,2, Ming Zou2, Nathan Carr3, Tao Ju2
1National University of Defense Technology (China), 2Washington University in St. Louis (USA), 3Adobe

A curve network (misc2) representing a genus-7 mechanical part (left), cycles found by our algorithm (middle), and surface patches generated from the cycles (right). The curve network contains 410 curves. Our algorithm completed in half a second.


Generating surfaces from 3D curve networks has been a longstanding problem in computer graphics. Recent attention to this area has resurfaced as a result of new sketch based modeling systems. In this work we present a new algorithm for finding cycles that bound surface patches. Unlike prior art in this area, the output of our technique is unrestricted, generating both manifold and non-manifold geometry with arbitrary genus. The novel insight behind our method is to formulate our problem as finding local mappings at the vertices and curves of our network, where each mapping describes how incident curves are grouped into cycles. This approach lends us the efficiency necessary to present our system in an interactive design modeler, whereby the user can adjust patch constraints and change the manifold properties of curves while the system automatically re-optimizes the solution.


Fast Forward



We thank the authors of [Bae et al. 2008; Schmidt et al. 2009] for providing the curve sketches, WiZ WORX for the wireframe of Gehaeuse, Open CASCADE shape factory for misc2 and FIRST CAD library for kk35. The work is supported in part by NSF grants (IIS-0846072, IIS-1302142) and a gift from Adobe.


title={A general and efficient method for finding cycles in 3D curve networks},
author={Zhuang, Yixin and Zou, Ming and Carr, Nathan and Ju, Tao},
journal={ACM Transactions on Graphics (TOG)},