Кіріспе
3D компьютерлік графикадағы техника. Catmull–Clark алгоритмі — 3D компьютерлік графикада қисық беттерді жасау үшін қолданылатын, субдивизиялық беттік модельдеуді пайдаланатын техника. Оны Эдвин Кэтмулл мен Джим Кларк 1978 жылы кез келген топологияға бікубтық біркелкі B-сплайн беттерін жалпылау ретінде ойлап тапты. Кез келген полиэдрдің торынан бастаңыз. Осы тордың барлық төбелері бастапқы нүктелер деп аталады. Әрбір жақ үшін жақ нүктесін қосыңыз. Әр жақ нүктесін тиісті жақ үшін барлық бастапқы нүктелердің орташасы ретінде белгілеңіз. Әр қабырға үшін қабырға нүктесін қосыңыз. Әр қабырға нүктесін екі көрші жақ нүктелерінің (A, F) және қабырғаның екі соңғы нүктесінің (M, E) орташасы ретінде белгілеңіз. Әр бастапқы нүкте (P) үшін P-ге жанасқан жақтар үшін барлық n (жақында жасалған) жақ нүктелерінің орташасын (F) және P-ге жанасқан бастапқы қабырғалардың барлық n қабырға ортасының орташасын (R) алыңыз, мұнда әр қабырға ортасы оның екі соңғы нүктесінің ортасы болып табылады (жоғарыдағы жаңа қабырға нүктелерімен шатастыруға болмайды). (P нүктесінің тұрғысынан қарағанда, P-ге көршілес қабырғалардың саны сонымен қатар іргелес жақтардың саны, сондықтан n). Әр бастапқы нүктені жаңа төбелік нүктеге жылжытыңыз (Бұл P, R және F-тің барицентрі, тиісті салмақтары (n − 3), 2 және 1). Жаңа тордағы қабырғалар мен жақтарды құрастырыңыз. Әр жаңа жақ нүктесін бастапқы жақты анықтайтын барлық бастапқы қабырғалардың жаңа қабырға нүктелеріне қосыңыз. Әр жаңа төбелік нүктені бастапқы қабырғаға жанасқан барлық бастапқы қабырғалардың жаңа қабырға нүктелеріне қосыңыз. Жаңа жақтарды қабырғалармен қоршалғандай анықтаңыз.
The Catmull–Clark algorithm is a technique used in 3D computer graphics to create curved surfaces by using subdivision surface modeling. It was devised by Edwin Catmull and Jim Clark in 1978 as a generalization of bi cubic uniform B spline surfaces to arbitrary topology. Start with a mesh of an arbitrary polyhedron. All the vertices in this mesh shall be called original points. For each face, add a face point
Set each face point to be the average of all original points for the respective face
For each edge, add an edge point. Set each edge point to be the average of the two neighbouring face points (A,F) and the two endpoints of the edge (M,E)
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 (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
Қасиеттері
Жаңа тор тек төртбұрыштардан тұрады, олар көбінесе жазық болмайды. Жаңа тор әдетте ескі торға қарағанда "тегіс" (яғни "тікенді" немесе "бұрышты" аз) көрінеді. Қайта-қайтала бөлу нәтижесінде желілік бұрыштар дөңгелене түседі. Катмулл мен Кларк барицентрдің кездейсоқ сияқты көрінетін формуласын математикалық есептеуге емес, нәтижедегі беттердің эстетикалық түріне сүйене отырып таңдады, бірақ олар осы әдіс бикубтық B-сплайн беттеріне жақындайтынын дәлелдеу үшін көп еңбек жұмсады. Бұл әдіс рекурсивтік жетілдіру процесін матрицалық экспонента мәселесіне айналдырады, оны матрицалық диагональдау арқылы тікелей шешуге болады.