Leksykon IT › Programowanie › Sutherland–Hodgman

Sutherland–Hodgman

Programowanie Svenska → Zaktualizowano: 2026-10-27

Algorytm obcinający wielokąt do obszaru wypukłego przez odcinanie po kolei tego, co leży poza jedną krawędzią.

Ivan Sutherland i Gary Hodgman opublikowali w 1974 roku „Reentrant Polygon Clipping”. Pomysł to potok: obcina się wielokąt względem jednej płaszczyzny, przekazuje wynik dalej, obcina względem następnej, aż wszystkie krawędzie obszaru obcinania zostaną obsłużone. Każda krawędź wielokąta wpada w jeden z czterech przypadków — oba końce wewnątrz, oba na zewnątrz albo po jednym z każdej strony — które decydują, które wierzchołki przechodzą dalej i gdzie powstają nowe.

Obszar obcinania musi być wypukły; wklęsłe dane wejściowe mogą zostawić zdegenerowane krawędzie wzdłuż granicy, co rasteryzatorowi rzadko przeszkadza. Technika żyje tam, gdzie trójkąty przecinają bliską płaszczyznę bryły widzenia, oraz w silnikach fizyki, jak Box2D, które obcinają ścianę incydentną płaszczyznami bocznymi ściany odniesienia, by zbudować manifold kontaktów.

← Wróć do leksykonu