다각형과 픽셀 겹침 : 효율적인 (주사선 형식) 알고리즘

Question

문제 사양 : 나는 정사각형 좌표 (i, j), (i + 1, j), (i, j) +1), (i + 1, j + 1) [i = 0, ..., m-1; (x_1, y_1), ..., (x_n, y_n)을 갖는 폴리곤 P를 생성한다. 이제는 P와 겹치는 모든 픽셀의 백분율을 효율적으로 계산하고 싶습니다. P는 비 볼록 또는 자체 교차 일 수 있습니다.

본질적으로 이것은 픽셀 중심이 다각형의 내부/외부에있을 경우 효율적으로 검사하는 스캔 라인 래스터 화 알고리즘의 "소프트"일반화입니다.

나는 다음과 같은 방법을 생각할 수

:

(1) (배 * 10 10 예) 이미지 업 샘플, 서브 픽셀 센터 (100) 문제로 다각형 내부에 거짓말을하고, 분할 얼마나 많은 수 : 시간 효율성, 메모리 효율성, 정확성.

(2) 조금 더 크고 (0.5,0.5) 번역 된 격자로 스캔 라인 알고리즘을 사용하여 완전히 안쪽/바깥쪽에있는 픽셀을 계산하고, "경계선"픽셀의 목록을 만들고, 시계 반대 방향으로 걷습니다 길을 따라 모든 픽셀과 교차 영역을 계산합니다. 문제 : 미묘한 코딩이 필요하고 버그를 쉽게 도입 할 수 있어야합니다.

내 질문 : 이미이 문제가 발생한 사람이 있습니까? 그리고 세 번째로 우수한 접근 방법을 알고 있습니까? 그리고 그렇지 않다면 (1) 또는 (2)로 더 나은 경험을 했습니까? 이 문제는 앤티 엘리 어싱과 관련하여 발생할 수 있다고 생각합니까? 화소가 부분적으로 중첩되면

Answer 1

정확한 기하학적 분석을 수행하는 것이 그리 어려운 일은 아닙니다.

먼저 다각형으로 부분적으로 덮여있는 픽셀을 처리하십시오. technique from ray-tracing을 사용하여 다각형 모서리와 교차하는 모든 픽셀을 빠르게 찾을 수 있습니다. Cohen-Sutherland 알고리즘을 사용하면 가장자리와 픽셀 간의 교차점을 효율적으로 찾을 수 있으므로 해당 픽셀의 적용 범위를 계산할 수 있습니다.

인접한 픽셀이 세그먼트 교차점을 공유하므로 Cohen-Sutherland와 관련된 두 가지 클리핑 작업 중 하나를 피할 수 있습니다. 예를 들어 - 당신이 두 개의 인접한 픽셀이있는 경우 포인트 a1, a2, b1 및 b2, 다음 a2 및 b1에서 세그먼트 p->q 교차 A 및 B은 동일합니다. B에 대해 클리핑 할 때 세그먼트 a2->q을 루틴에 전달하면 작업을 반복하지 않아야합니다.

폴리곤 정점이있는 픽셀은 특별히 처리해야하지만 너무 까다로워서는 안됩니다. Cohen-Sutherland도 여기에서 도움이됩니다.

자기 교차 폴리곤은 두 개 이상의 가장자리와 교차하는 픽셀 인 특수한 경우를 처리합니다. 모든 상황에서 정확하게 처리하는 것은 까다로울 수 있으므로 상향식 샘플링 방식을 사용하는 것이 좋습니다.

일단 이러한 가장자리 픽셀이 식별되면 표준 스캔 라인을 사용하여 다각형의 내부 픽셀을 채울 수 있습니다.

편집 : 사실, 이제 더 자세히 생각해 보면, 코헨 서덜랜드 단계를 완전히 건너 뛸 수 있습니다. 연결된 종이에있는 알고리즘을 쉽게 확장하여 세그먼트와 픽셀 그리드 사이의 교차점을 반환 할 수 있습니다. 세그먼트는 주어진 픽셀을 min(tMaxX, tMaxY)에 남겨 둡니다. 다음 픽셀의 엔트리 포인트로 다시 사용하려면 마지막 종료점을 추적하십시오.

Answer 2

I)의 업 샘플링을

1A 할 것이다 :

아니라 전체 화상 만 현재의 픽셀을 체크하기 위해, 또는 현재의 주사선의 모든 픽셀이 있다면 도움이됩니다.

메모리 인수가 없습니다.

속도? 16x16까지 나는 그 속도가 문제라고 생각하지 않는다.