Polygon Clipping (Sutherland–Hodgman algorithm)

폴리곤 클리핑에는 여러가지 알고리즘이 있는데 Sutherland–Hodgman 알고리즘을 사용했다.

알고리즘의 요점은 클립의 각 선분을 무한히 늘려서 거기에 걸리는 부분을 모두 잘라내버린다.
그림으로 보면 좀더 이해하기가 쉬운데 위키백과에서 찾아왔다.

 

클립하는 붉은색 다각형의 각 선분을 무한히 늘린뒤 걸리는놈들은 다 잘라내버린다.

  List outputList = subjectPolygon;  for (Edge clipEdge in clipPolygon) do     List inputList = outputList;     outputList.clear();     Point S = inputList.last;     for (Point E in inputList) do        if (E inside clipEdge) then           if (S not inside clipEdge) then              outputList.add(ComputeIntersection(S,E,clipEdge));           end if           outputList.add(E);        else if (S inside clipEdge) then           outputList.add(ComputeIntersection(S,E,clipEdge));        end if        S = E;     done  done

알고리즘의 슈도코드인데 따로 뭐 설명할 꺼리가 없다.
E inside clipEdge 의 경우에는 crossproduct (외적)를 이용하는데 계산한 값이 양수이냐 음수이냐에 따라서 inside인지
not inside 판별하게된다. (폴리곤이 반시계 방향일때는 양수이면 안쪽, 시계방향일때는 음수이면 안쪽이된다.)

알고리즘이 참 간단한데 한가지 문제가 있다.

보이는가? 검정색 선이 클리핑된 폴리곤인데 각 폴리곤이 분할이 안되있다.
저게 그림으로써의 클리핑이라면 연결된 선은 두께가 없다는 가정하에 그려지지 않는다. 그런데 물리엔진이다. 라고 한다면 저 이어진 선이 있으면 안된다.
따라서 분할된 폴리곤들을 원한다면 Weiler–Atherton 알고리즘을 써야한다.
게다가 컨벡스 폴리곤 간의 클리핑이라면 저런 문제가 안생기니 상황에 따라 잘 사용하자.

그런데 W 를 자르는 그림에서 안쪽을 자르는게 아니라 바깥쪽을 자르고 싶다. 라고하면 잘려나간부분을 저장하면된다.

012

근데 한덩어리로 잘라주는게 아니라 갈갈이 썰어버린다....
끝나고 나서 뭉쳐줄 필요가 있다.