קטמול-קלרק

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

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

• על כל פאה מוסיפים נקודת פאה (face point) שהיא נקודת שיווי המשקל בין הקודקודים המקוריים של הפאה.
• על כל צלע מוסיפים נקודת צלע (edge point) שהיא ממוצע שתי נקודות הפאה הסמוכות ושתי נקודות הקצה המקורית של הצלע.
• לכל נקודת פאה מוסיפים צלע המקשרת לצלעות הפאה. כלומר צלע המקשרת את נקודת הפאה עם נקודות הצלע המתאימות.
• לכל נקודה מקורית $P$ מגדירים את $F$ להיות ממוצע נקודות הפאה שיצרנו שנוגעות ב-$P$, ומגדירים את $R$ להיות ממוצע נקודות האמצע לצלעות הנוגעות ב-$P$. כל נקודה מקורית מוזזת ל$\frac{F+2R+(n-3)P}{n}$.
• מחברים בצלע כל קודקוד לנקודות הצלע של כל הצלעות המקוריות שבהן היה הקודקוד המקורי.
• מגדירים את הפאות החדשות בעזרת הצלעות שנוספו בבנייה.

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

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

פרק זה טעון עריכה. אנא תרמו לוויקיפדיה ועזרו לערוך אותו.

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)