Chulalongkorn University Theses and Dissertations (Chula ETD)

Collapse-based mesh simplification using angular deviation and regularity bias

Other Title (Parallel Title in Other Language of ETD)

การลดทอนรายละเอียดเมชแบบยุบโดยใช้การตั้งค่าคะแนนด้วยการเบี่ยงเบนเชิงมุมและความปรกติของหน้า

Year (A.D.)

2010

Document Type

Thesis

First Advisor

Pizzanu Kanongchaiyos

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

Doctor of Engineering

Degree Level

Doctoral Degree

Degree Discipline

Computer Engineering

DOI

10.58837/CHULA.THE.2010.1716

Abstract

A major research topic in computer graphics is mesh simplification, reducing the face count of complex 3D models to improve rendering performance while retaining visual quality. Current research prefers edge contraction based methods, such as Garland and Heckbert's Quadric Error Metric, as such methods lend themselves well to level-of-detail structures. Various research has suggested improvements to QEM based on curvature-based scoring; however, using the two principal curvatures and their directions can help reduce the inherent ambiguity of using a single score. The proposed extension to Garland and Heckbert's method calculates the principal curvatures and their directions for each vertex, to calculate the absolute normal curvature in the direction of contraction. Also, the regularity and the angular and dihedral deviations of the resulting faces are used to apply penalties. A heap updating scheme that only updates the top portion of the heap to save time is also described. The proposed method has been observed to reduce the average Hausdorff distance, a measure of mesh difference, in a range between 12%-70% from 5% to 50% face count, although QEM still produces lower distances at lower face count. Although the proposed algorithm retains an O(n log n) time complexity, the partial heap update scheme has improved the overall process by a factor of 5.4 compared to using full heap updates.

Other Abstract (Other language abstract of ETD)

หัวข้อวิจัยคอมพิวเตอร์กราฟิกส์ที่สำคัญคือ การลดทอนเมช หรือการลดจำนวนหน้าของโมเดลสามมิติที่ซับซ้อน เพื่อเพิ่มสมรรถภาพในการเรนเดอร์โดยที่ยังคงคุณภาพของรูปภาพ งานวิจัยในปัจจุบันจะใช้วิธีการที่ใช้การยุบเส้นขอบ เช่น ค่า error metric ยกกำลังสองของ Garland และ Heckbert เนื่องจากวิธีการเหล่านี้สามารถใช้ได้ดีกับโครงสร้างข้อมูลที่เก็บระดับความละเอียด ได้มีผลงานวิจัยที่แสดงการปรับปรุงวิธีการของ Garland และ Heckbert โดยใช้คะแนนที่มีฐานจากความโค้ง อย่างไรก็ดี การใช้ความโค้งสำคัญ (principal curvature) ทั้งสองค่า รวมทั้งทิศทาง สามารถลดความคลุมเครือที่เกิดจากการใช้คะแนนค่าเดียวได้ การปรับปรุงวิธีการเดิมของ Garland และ Heckbert ที่นำเสนอคำนวณหาค่าของความโค้งสำคัญและทิศทางของแค่ละเวอร์เท็กซ์ เพื่อคำนวณหาค่าสัมบูรณ์ของค่าความโค้งเส้นปกติในทิศทางขอบที่ลด นอกจากนี้ มีการใช้ความปรกติของและการเบี่ยงเบนของมุมของหน้าที่ได้ เพื่อคำนวณคะแนนโทษด้วย และมีการอธิบายถึงวิธีการปรับค่าในฮีพที่ปรับค่าเฉพาะส่วนบนสุด เพื่อลดเวลาที่ใช้ในการทำงาน ได้สังเกตว่า วิธีการใหม่ทำให้ได้ค่าเฉลี่ยของระยะ Hausdorff ซึ่งใช้ในการวัดค่าต่างของเมช ที่น้อยกว่า QEM ในช่วง 12% ถึง 70% ระหว่างช่วง 5% ถึง 50% ของจำนวนหน้าเดิม อย่างไรก็ดี QEM ยังให้ระยะที่น้อยกว่า เมื่อลดเป็นจำนวนหน้าที่น้อยกว่า อัลกอริทึมที่เสนอยังคงมีระยะเวลาที่ใช้ O(n log n) แต่วิธีการปรับปรุงฮีพบางส่วนสามารถเพิ่มความเร็วของกระบวนการถึง 5.4 เท่าเมื่อเทียบการการปรับปรุงฮีพทั้งหมด

Link to Full Text

Share

COinS