Algorytm Catmull‑Clark

Algorytm Catmull‑Clark (ang. Catmull‑Clark subdivision algorithm) to metoda podziału (ang. subdivision) powierzchni używana w grafice komputerowej oraz modelowaniu 3D. Została opracowana w 1978 roku przez Edgara Catmulla i Jamesa Clarka. Dzięki prostemu schematowi przekształcania sieci wielokątnej algorytm umożliwia konwersję dowolnej siatki złożonej z wielokątów (zwykle czworokątów, trójkątów lub mieszanych) w gładką, ciągłą powierzchnię.

Historia

W początkach lat lat 70. badacze poszukiwali technik umożliwiających generowanie realistycznych modeli o wysokiej jakości przy jednoczesnym zachowaniu niskich kosztów obliczeniowych. Praca Catmulla i Clarka, opublikowana na konferencji SIGGRAPH, była jedną z pierwszych, które wprowadziły powierzchnie podziału oparte na prostych regułach lokalnych, co pozwoliło na łatwe implementowanie w systemach renderujących.

Zasada działania

Algorytm działa iteracyjnie – każda iteracja (nazywana poziomem podziału) przekształca istniejącą siatkę w nową, bardziej szczegółową, zachowując przy tym gładkość powierzchni. Poniżej opisano cztery podstawowe kroki jednej iteracji:

1. Punkty ścian (face points): Dla każdego wielokąta w siatce wyznacza się punkt będący średnią (centroid) wszystkich wierzchołków tworzących tę ścianę.
2. Punkty krawędzi (edge points): Dla każdej krawędzi oblicza się punkt będący średnią z jej dwóch końcowych wierzchołków oraz dwóch punktów ścian przylegających do tej krawędzi.
3. Nowe pozycje wierzchołków (vertex points): Każdy oryginalny wierzchołek zostaje przemieszonej według wzoru
   V' = (F + 2E + (n‑3)V) / n gdzie F to średnia z punktów ścian przylegających do wierzchołka, E – średnia z punktów krawędzi przylegających, V – pozycja wierzchołka, a n – liczba krawędzi (stopień wierzchołka).
4. Tworzenie nowych wielokątów: Każdy oryginalny wielokąt zostaje podzielony na nowe wielokąty, łącząc nowe punkty krawędzi, punkt ściany oraz przemie­sowane wierzchołki. W przypadku czworokątów powstają cztery nowe czworokąty, w przypadku trójkątów – trzy nowe trójkąty.

Po wykonaniu powyższych kroków otrzymujemy nową siatkę, która może podlegać kolejnym iteracjom, zwiększając stopień gładkości.

Właściwości

• Gładkość – po kilku iteracjach algorytm generuje powierzchnię klasy C² (ciągłą pochodną drugiego rzędu) z wyjątkiem wierzchołków o nieregularnej topologii, które pozostają jedynie C¹.
• Uniwersalność – może być zastosowany do dowolnej siatki wielokątnej, nie wymaga onego przekształcania w siatkę wyłącznie czworokątów.
• Łatwość implementacji – reguły są lokalne i nie wymagają rozwiązywania równań globalnych.
• Efektywność – złożoność czasowa jednej iteracji wynosi O(V + E + F), gdzie V, E i F to liczby wierzchołków, krawędzi i ścian odpowiednio.

Zastosowania

Algorytm Catmull‑Clark znalazł szerokie zastosowanie w:

• modelowaniu 3D – tworzenie gładkich modeli postaci, pojazdów i obiektów organicznych.
• grafice komputerowej w czasie rzeczywistym – silniki gier (np. w wersjach „subdivision surfaces” w Unity czy Unreal Engine) wykorzystują uproszczone wersje algorytmu.
• Animacji – pozwala na płynne deformacje siatek przy zachowaniu ciągłości powierzchni.
• Projektowaniu przemysłowym – w programach CAD do generowania wygładzonych powierzchni z danych skanów 3D.

Porównanie z innymi metodami podziału

Metoda	Typ podziału	Stopień gładkości	Wymagania topologiczne
Catmull‑Clark	ogólne (dowolne wielokąty)	C² (z wyjątkiem wierzchołków o nieregularnej topologii)	brak
Loop	trójkąty	C²	siatka trójkątna
Do​o‑Sabin	czworokąty	C¹	czworokątna siatka

Implementacja – najważniejsze uwagi

1. Trzeba zachować spójność indeksacji wierzchołków i krawędzi, dlatego w praktyce stosuje się strukturę half‑edge lub winged‑edge.
2. Obliczanie punktów ścian i krawędzi może być zrównoleglone – każda operacja jest niezależna od innych.
3. W wersjach zoptymalizowanych przechowuje się tylko nowe punkty i przelicza się współrzędne wierzchołków „na żądanie”, co redukuje zużycie pamięci.
4. Po ostatniej iteracji zazwyczaj stosuje się normalizację wektorów normalnych w celu uzyskania poprawnego oświetlenia.

Przykładowy kod (pseudo‑kod)

function catmullClark(mesh):
    // 1. Face points
    for each face f in mesh.faces:
        f.point = average(f.vertices)

    // 2. Edge points
    for each edge e in mesh.edges:
        e.point = (e.v1 + e.v2 + e.face1.point + e.face2.point) / 4

    // 3. New vertex positions
    for each vertex v in mesh.vertices:
        n = v.valence               // liczba przyległych krawędzi
        F = average( v.adjacentFaces.points )
        R = average( v.adjacentEdges.points )
        v.newPos = (F + 2*R + (n-3)*v.position) / n

    // 4. Re‑build topology
    newMesh = empty()
    for each face f in mesh.faces:
        for each edge e of f:
            // tworzymy nowy kwadrat (lub trójkąt)
            newMesh.addFace( v_new(e.start), e.point, f.point, e.prev.point )
    return newMesh

Ograniczenia

• W przypadku bardzo nierównej topologii (np. wierzchołki o wysokim stopniu) algorytm może wytworzyć artefakty widoczne jako „szpicowate” fragmenty.
• Podczas intensywnego podziału liczba wielokątów rośnie wykładniczo, co może prowadzić do problemów z wydajnością w aplikacjach czasu rzeczywistego.

Literatura

• Catmull, E.; Clark, J. „Recursively generated B‑splines on arbitrary topological meshes”. Computer-Aided Design, 1978.
• Goldman, R. „Polyhedral Meshes”. Computer Graphics, 1999.
• Hughes, J.F. et al. „Computer Graphics: Principles and Practice”. 3. wyd., 2014 – rozdział o powierzchniach podziału.

Algorytm Catmull‑Clark pozostaje jedną z fundamentalnych technik w grafice komputerowej, a jego prostota oraz uniwersalność sprawiają, że jest on standardem w edukacji oraz w praktycznych zastosowaniach przemysłowych.