Pattern-based quadrangulation for N-sided patches

Kenshi Takayama, Daniele Panozzo, Olga Sorkine-Hornung

Research output: Contribution to journalArticle

Abstract

We propose an algorithm to quadrangulate an N-sided patch (2 ≤ N ≤ 6) with prescribed numbers of edge subdivisions at its boundary. Our algorithm is guaranteed to succeed for arbitrary valid input, which is proved using a canonical simplification of the input and a small set of topological patterns that are sufficient for supporting all possible cases. Our algorithm produces solutions with minimal number of irregular vertices by default, but it also allows the user to choose other feasible solutions by solving a set of small integer linear programs. We demonstrate the effectiveness of our algorithm by integrating it into a sketch-based quad remeshing system. A reference C++ implementation of our algorithm is provided as a supplementary material.

Original languageEnglish (US)
Pages (from-to)177-184
Number of pages8
JournalComputer Graphics Forum
Volume33
Issue number5
DOIs
StatePublished - Aug 2014

Keywords

  • Categories and Subject Descriptors (according to ACM CCS)
  • I.3.3 [Computer Graphics]: Computational Geometry and Object Modeling - Geometric algorithms, languages, and systems

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Pattern-based quadrangulation for N-sided patches'. Together they form a unique fingerprint.

  • Cite this