การประมวลผลเรขาคณิต

การประมวลผลเรขาคณิตพัฒนาอัลกอริทึมเพื่อวิเคราะห์ ซ่อมแซม และแปลงรูปทรงดิจิทัล โดยปฏิบัติต่อเมช (mesh) คล้ายกับการที่การประมวลผลสัญญาณปฏิบัติต่อสัญญาณที่สุ่มตัวอย่างมา

Definition

การประมวลผลเรขาคณิตคือชุดของวิธีการคำนวณสำหรับการกรอง การลดความซับซ้อน การกำหนดพารามิเตอร์ และการแปลงการนำเสนอพื้นผิวแบบไม่ต่อเนื่อง โดยเฉพาะอย่างยิ่งเมชรูปหลายเหลี่ยม (polygon meshes)

Scope

หัวข้อนี้ครอบคลุมการปรับเรียบและการลดสัญญาณรบกวนของเมช การลดความซับซ้อนและการสร้างระดับรายละเอียด การกำหนดพารามิเตอร์พื้นผิวและการแมปพื้นผิว (texture mapping) การสร้างเมชใหม่และการซ่อมแซม รวมถึงตัวดำเนินการทางเรขาคณิตเชิงอนุพันธ์แบบไม่ต่อเนื่อง เช่น ลาปลาเซียนแบบไม่ต่อเนื่อง (discrete Laplacian) ซึ่งเป็นพื้นฐานของวิธีการเหล่านี้

Core questions

• จะขจัดสัญญาณรบกวนจากการสแกน 3 มิติได้อย่างไรโดยไม่ทำลายคุณสมบัติ?
• จะลดความซับซ้อนของเมชที่มีรายละเอียดได้อย่างไรในขณะที่ยังคงรักษารูปร่างไว้?
• จะทำให้พื้นผิวแบนราบลงบนระนาบสำหรับการทำเท็กซ์เจอร์ได้อย่างไร?
• จะทำให้ตัวดำเนินการเชิงอนุพันธ์แบบต่อเนื่องกลายเป็นแบบไม่ต่อเนื่องบนเมชได้อย่างไร?

Key concepts

• ตัวดำเนินการลาปลาเซียนแบบไม่ต่อเนื่อง
• การปรับเรียบและการลดสัญญาณรบกวนของเมช
• การลดความซับซ้อนของเมช
• การกำหนดพารามิเตอร์พื้นผิว
• การสร้างเมชใหม่และการซ่อมแซม
• ระดับรายละเอียด

Key theories

มุมมองการประมวลผลสัญญาณของเมช

พิกัดพื้นผิวสามารถถูกกรองได้เหมือนสัญญาณโดยใช้เมชลาปลาเซียน ซึ่งช่วยให้การปรับเรียบสามารถลดสัญญาณรบกวนความถี่สูงได้ ในขณะที่ขั้นตอนการตอบโต้จะช่วยป้องกันการหดตัวที่เกิดจากการปรับเรียบแบบธรรมดา

การลดความซับซ้อนของเมชด้วยข้อผิดพลาดแบบควอดริก

การยุบขอบ (edge collapses) จะถูกจัดลำดับโดยเมตริกข้อผิดพลาดแบบควอดริก (quadric error metric) ซึ่งวัดระยะทางกำลังสองไปยังพื้นผิวเดิม ทำให้สามารถลดความซับซ้อนได้อย่างมากในขณะที่ยังคงรักษารูปร่างโดยรวมและคุณสมบัติที่คมชัดไว้ได้

Clinical relevance

การประมวลผลเรขาคณิตมีความสำคัญสำหรับการแปลงข้อมูลสแกน 3 มิติแบบดิบให้เป็นแบบจำลองที่ใช้งานได้ การสร้างสินทรัพย์ระดับรายละเอียดที่มีประสิทธิภาพสำหรับเกม การเตรียมเมชที่กันน้ำ (watertight meshes) สำหรับการพิมพ์ 3 มิติ และการวิเคราะห์พื้นผิวกายวิภาคในการสร้างภาพทางการแพทย์

History

การประมวลผลเรขาคณิตดิจิทัลเกิดขึ้นในทศวรรษ 1990 เมื่อการสแกน 3 มิติสร้างเมชขนาดใหญ่ที่ต้องการการทำความสะอาด การวางกรอบแบบการประมวลผลสัญญาณของ Taubin และการลดความซับซ้อนแบบควอดริก (quadric simplification) ของ Garland และ Heckbert ได้กลายเป็นเทคนิคพื้นฐานในสาขาที่เติบโตขึ้นรอบ ๆ ลาปลาเซียนแบบไม่ต่อเนื่อง

Key figures

• Gabriel Taubin
• Michael Garland
• Paul Heckbert

Seminal works

• taubin1995
• garland1997

Frequently asked questions

เหตุใดการสแกน 3 มิติจึงต้องมีการประมวลผลก่อนใช้งาน?

ข้อมูลสแกนดิบมักมีสัญญาณรบกวน มีรูพรุนและรายละเอียดมากเกินไป และอาจไม่กันน้ำ ดังนั้นจึงจำเป็นต้องมีการปรับเรียบ การเติมรู และการลดความซับซ้อนเพื่อให้สามารถนำไปใช้งานสำหรับการเรนเดอร์ การจำลอง หรือการพิมพ์ได้

การกำหนดพารามิเตอร์พื้นผิวมีไว้เพื่ออะไร?

เป็นการกำหนดพิกัดให้กับแต่ละจุดบนพื้นผิวในโดเมนระนาบ ซึ่งทำให้สามารถห่อหุ้มภาพพื้นผิว 2 มิติลงบนแบบจำลอง 3 มิติได้โดยไม่มีการบิดเบือนมากเกินไป