อัลกอริทึมCatmull–Clark เป็นเทคนิคที่ใช้ในกราฟิกคอมพิวเตอร์ 3 มิติเพื่อสร้างพื้นผิวโค้งโดยใช้ การสร้าง แบบจำลองพื้นผิวแบบแบ่งย่อยคิดค้นโดยEdwin CatmullและJim Clarkในปี 1978 โดยเป็นการขยาย พื้นผิว B-spline แบบ bi-cubic uniformไปสู่โทโพโลยีแบบ ใดก็ได้ ^{[ 1 ]}

ในปี 2005/06 เอ็ดวิน แคทมุลล์ ร่วมกับโทนี่ เดอโรสและโจส สแตมได้รับรางวัลออสการ์สาขาความสำเร็จทางเทคนิคจากการคิดค้นและประยุกต์ใช้พื้นผิวแบบแบ่งย่อย (subdivision surfaces) เดอโรสเขียนเกี่ยวกับ "การประมาณค่าแบบมีประสิทธิภาพและยุติธรรม" และการสร้างแอนิเมชั่นตัวละคร ส่วนสแตมอธิบายเทคนิคสำหรับการประเมินพื้นผิวขีดจำกัดโดยตรงโดยไม่ต้องใช้การเรียกซ้ำ

พื้นผิว Catmull–Clark ถูกกำหนดแบบวนซ้ำโดยใช้รูปแบบการปรับปรุง ดังต่อไปนี้ ^{[ 1 ]}

เริ่มต้นด้วยตาข่ายของทรงหลาย เหลี่ยมใดๆ จุดยอดทั้งหมดในตาข่ายนี้จะเรียกว่าจุดเริ่มต้น

• สำหรับแต่ละด้าน ให้เพิ่มจุดบนใบหน้า
  • กำหนดให้จุดแต่ละจุดบนใบหน้าเป็นค่าเฉลี่ย ของ จุดเริ่มต้นทั้งหมดสำหรับใบหน้านั้นๆ

    

• สำหรับแต่ละขอบ ให้เพิ่มจุดขอบเข้าไป
  • กำหนดจุดขอบแต่ละจุดให้เป็นค่าเฉลี่ยของจุดหน้าสองจุดที่อยู่ติดกัน(A,F)และจุดปลายทั้งสองของขอบ(M,E) ^{[ 2 ]}${\displaystyle {\frac {A+F+M+E}{4}}}$

    

• For each original point (P), take the average (F) of all n (recently created) face points for faces touching P, and take the average (R) of all n edge midpoints for original edges touching P, where each edge midpoint is the average of its two endpoint vertices (not to be confused with new edge points above). (Note that from the perspective of a vertex P, the number of edges neighboring P is also the number of adjacent faces, hence n)
  • Move each original point to the new vertex point${\displaystyle {\frac {F+2R+(n-3)P}{n}}}$ (This is the barycenter of P, R and F with respective weights (n − 3), 2 and 1)

    

• Form edges and faces in the new mesh
  • Connect each new face point to the new edge points of all original edges defining the original face

    

  • Connect each new vertex point to the new edge points of all original edges incident on the original vertex

    

  • Define new faces as enclosed by edges

    

The new mesh will consist only of quadrilaterals, which in general will not be planar. The new mesh will generally look "smoother" (i.e. less "jagged" or "pointy") than the old mesh. Repeated subdivision results in meshes that are more and more rounded.

The arbitrary-looking barycenter formula was chosen by Catmull and Clark based on the aesthetic appearance of the resulting surfaces rather than on a mathematical derivation, although they do go to great lengths to rigorously show that the method converges to bicubic B-spline surfaces.^[1]

It can be shown that the limit surface obtained by this refinement process is ${\displaystyle G^{1}}$ (tangent plane) continuous at extraordinary vertices (valence not equal to 4) and ${\displaystyle {\mathcal {C}}^{2}}$ continuous at regular points (valence equal to 4).^[3] (when n indicates how many derivatives are continuous, we speak of ${\displaystyle {\mathcal {C}}^{n}}$continuity). After one iteration, the number of extraordinary points on the surface remains constant.

พื้นผิวลิมิตของพื้นผิวการแบ่งย่อย Catmull–Clark สามารถประเมินได้โดยตรงโดยไม่ต้องมีการปรับปรุงแบบวนซ้ำ ซึ่งสามารถทำได้โดยใช้เทคนิคของJos Stam (1998) ^{[ 4 ]}วิธีนี้ปรับเปลี่ยนกระบวนการปรับปรุงแบบวนซ้ำให้เป็น ปัญหา เลขชี้กำลังของเมทริกซ์ซึ่งสามารถแก้ไขได้โดยตรงโดยใช้การหาค่าเฉพาะของเมท ริกซ์

พื้นผิว Catmull–Clark ได้รับการขยายเพื่อรองรับรอยพับกึ่งคมโดยใช้กฎการแบ่งย่อยที่แตกต่างกันสำหรับจำนวนรอบคงที่ที่กำหนดโดยค่าความคมชัด^{[ 5 ]}แนวทางนี้ซึ่งนำเสนอโดยTony DeRoseและคณะในปี 1998 ช่วยให้สามารถเปลี่ยนจากกฎการแบ่งย่อยที่คมไปเป็นกฎการแบ่งย่อยที่เรียบได้อย่างควบคุม

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

• Derose, T.; Kass, M.; Truong, T. (1998). "พื้นผิวแบบแบ่งย่อยในแอนิเมชั่นตัวละคร" (PDF) . รายงานการประชุมประจำปีครั้งที่ 25 ว่าด้วยกราฟิกคอมพิวเตอร์และเทคนิคเชิงโต้ตอบ - SIGGRAPH '98 . หน้า  85 . CiteSeerX  10.1.1.679.1198 . doi : 10.1145/280814.280826 . ISBN 978-0897919999. S2CID  1221330 .
• Loop, C.; Schaefer, S. (2008). "การประมาณพื้นผิวการแบ่งย่อย Catmull-Clark ด้วยแพทช์ bicubic" (PDF) . ACM Transactions on Graphics . 27 : 1– 11. CiteSeerX  10.1.1.153.2047 . doi : 10.1145/1330511.1330519 . S2CID  6068564 .
• Kovacs, D.; Mitchell, J.; Drone, S.; Zorin, D. (2010). "พื้นผิวแบ่งย่อยโดยประมาณแบบพับแบบเรียลไทม์พร้อมการเคลื่อนที่" (PDF) . IEEE Transactions on Visualization and Computer Graphics . 16 (5): 742– 51. doi : 10.1109/TVCG.2010.31 . PMID  20616390 . S2CID  17138394 .บทความฉบับร่าง
• Matthias Nießner, Charles Loop, Mark Meyer, Tony DeRose, " การเรนเดอร์พื้นผิวแบบ Catmull-Clark Subdivision ด้วย GPU ที่ปรับตามคุณลักษณะ ", ACM Transactions on Graphics เล่มที่ 31 ฉบับที่ 1 มกราคม 2012, doi : 10.1145/2077341.2077347 , demo
• Nießner, Matthias; Loop, Charles; Greiner, Günther: การประเมินรอยพับกึ่งเรียบอย่างมีประสิทธิภาพในพื้นผิวแบบแบ่งย่อย Catmull-Clark : ภาคผนวก Eurographics 2012: บทความสั้น (Eurographics 2012, Cagliary) 2012, หน้า 41–44
• Wade Brainerd, Tessellation ใน Call of Duty: Ghostsยังถูกนำเสนอเป็นบทช่วยสอน SIGGRAPH2014 อีกด้วย[1]
• D. Doo และ M. Sabin: พฤติกรรมของพื้นผิวการหารแบบเรียกซ้ำใกล้จุดพิเศษ , Computer-Aided Design, 10 (6) 356–360 (1978), ( doi , pdf )