Pattern-based quadrangulation for N-sided patches

Kenshi Takayama; Daniele Panozzo; Olga Sorkine-Hornung

doi:10.1111/cgf.12443

Pattern-based quadrangulation for N-sided patches

Kenshi Takayama, Daniele Panozzo, Olga Sorkine-Hornung

Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	177-184
Number of pages	8
Journal	Computer Graphics Forum
Volume	33
Issue number	5
DOIs	https://doi.org/10.1111/cgf.12443
State	Published - 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

Access to Document

10.1111/cgf.12443

Cite this

@article{05c365771c4743d6884f21c9d2a44293,

title = "Pattern-based quadrangulation for N-sided patches",

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.",

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

author = "Kenshi Takayama and Daniele Panozzo and Olga Sorkine-Hornung",

year = "2014",

month = aug,

doi = "10.1111/cgf.12443",

language = "English (US)",

volume = "33",

pages = "177--184",

journal = "Computer Graphics Forum",

issn = "0167-7055",

publisher = "Wiley-Blackwell Publishing Ltd",

number = "5",

}

TY - JOUR

T1 - Pattern-based quadrangulation for N-sided patches

AU - Takayama, Kenshi

AU - Panozzo, Daniele

AU - Sorkine-Hornung, Olga

PY - 2014/8

Y1 - 2014/8

N2 - 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.

AB - 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.

KW - Categories and Subject Descriptors (according to ACM CCS)

KW - I.3.3 [Computer Graphics]: Computational Geometry and Object Modeling - Geometric algorithms, languages, and systems

UR - http://www.scopus.com/inward/record.url?scp=84906673997&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84906673997&partnerID=8YFLogxK

U2 - 10.1111/cgf.12443

DO - 10.1111/cgf.12443

M3 - Article

AN - SCOPUS:84906673997

SN - 0167-7055

VL - 33

SP - 177

EP - 184

JO - Computer Graphics Forum

JF - Computer Graphics Forum

IS - 5

ER -

Pattern-based quadrangulation for N-sided patches

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this