קטמול-קלרק

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

האלגוריתם פועל בצורה רקורסיבית כשבכל שלב נעשה עידון בצורה הבאה: מתחילים ממודל של פאון, וכל הקודקודים בו נקראים קודקודים מקוריים.

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

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

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

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)