קטמול-קלרק

אלגוריתם קטמול-קלרק (באנגלית: Catmull–Clark) הוא אלגוריתם בגרפיקה ממוחשבת שמטרתו ליצור משטחים חלקים באמצעות חלוקה חוזרת של משטח התחלתי. האלגוריתם הוצג לראשונה ב-1978 על ידי שני מדעני המחשב האמריקניים אדווין קטמול וג'יימס קלרק.

האלגוריתם פועל בצורה רקורסיבית כשבכל שלב נעשה עידון בצורה הבאה:
מתחילים ממודל של פאון, וכל הקודקודים בו נקראים קודקודים מקוריים.
על כל פאה מוסיפים נקודת פאה (face point) שהיא נקודת שיווי המשקל הממוצעת בין הקודקודים המקוריים של הפאה.
על כל צלע מוסיפים נקודת צלע (edge point) שהיא ממוצע שתי נקודות הפאה הסמוכות ושתי נקודות הקצה המקורית של הצלע.
לכל נקודת פאה מוסיפים צלע המקשרת לצלעות הפאה. כלומר צלע המקשרת את נקודת הפאה עם נקודות הצלע המתאימות.
לכל נקודה מקורית  מגדירים את  להיות ממוצע נקודות הפאה שיצרנו שנוגעות ב-, ומגדירים את  להיות ממוצע נקודות האמצע לצלעות הנוגעות ב-. כל נקודה מקורית מוזזת ל.
מחברים בצלע כל קודקוד לנקודות הצלע של כל הצלעות המקוריות שבהן היה הקודקוד המקורי.
מגדירים את הפאות החדשות בעזרת הצלעות שנוספו בבנייה.

הפעלה חוזרת של האלגוריתם מחלקת צורה עם מעט פאות לצורה עם הרבה פאות ומחליקה את הקצוות ה"חדים" וה"משוננים" למשטח שמשתנה בצורה הדרגתית וחלקה יותר.

קישורים חיצוניים

E. Catmull and J. Clark: Recursively generated B-spline surfaces on arbitrary topological meshes, Computer-Aided Design 10(6):350-355 (November 1978), (doi, pdf)

קטגוריה:גרפיקה ממוחשבת