Feature-aware partitions from the motorcycle graph

Erkan Gunpinar*, Masaki Moriguchi, Hiromasa Suzuki, Yutaka Ohtake

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


Today's quad-meshing techniques generate high-quality quadrilateral meshes whose extraordinary vertices (i.e., not four-valence vertices except on the boundary) are generally located in highly curved regions. The motorcycle graph (MCG) algorithm of Eppstein et al. can be used to generate structured partitions of such quadrilateral meshes. However, it is not always possible for it to capture feature curves in the highly-curved parts of the model on the partition boundaries because model geometry is not taken into account. This study investigated feature-aware algorithms representing extensions of the MCG algorithm. Initial partitioning is first performed using a speed control algorithm identical to the MCG algorithm except that it assigns variable rather than constant speed to particles. Partition boundaries are then improved via local path flipping operations. The MCG algorithm and the speed control algorithm are intended to trace as many feature curves as possible, but do not necessarily trace all of them. For this reason, feature curves are extracted and integrated into the proposed framework by adding seeds located at ordinary vertices in addition to extraordinary seeds. The proposed algorithm generates partitions that are still structured, and has been tested with quadrilateral mesh models generated using the mixed integer quadrangulation technique of Bommes et al.

Original languageEnglish
Pages (from-to)85-95
Number of pages11
JournalCAD Computer Aided Design
Publication statusPublished - 2014
Externally publishedYes


FundersFunder number
Japan Society for the Promotion of Science22246018, 22101006


    • Mesh segmentation
    • Motorcycle graph
    • Quadrilateral mesh


    Dive into the research topics of 'Feature-aware partitions from the motorcycle graph'. Together they form a unique fingerprint.

    Cite this