다각형 채우기 : 와인딩 규칙의 성능 대 이상한 규칙

Question

복잡한 다각형 (예 : 자체 교차)의 경우 와인딩 또는 짝수 충전 규칙 사이의 선택은 다각형이 채워지는 방식에 차이를 만듭니다.

그러나 비 교차 다각형의 경우 와인딩 또는 홀수 충전 규칙 사이에는 성능 차이가 있습니다. 나는 그것이 구현 특이적일 것이라는 것을 이해하지만 어떤 알고리즘이 비 복잡한 다각형에 대해 더 효과적입니다.

후속 질문 각 알고리즘의 복잡성 (예 : 무엇?) 성능을 향상시키기 위해 다각형 (주로 복제물 또는 같은 라인에있는 중복 또는 같은 점)에서 일부 포인트를 제거 할 가치가 있는지 알고 싶습니다.

추신 : 중요하다면 xlib를 사용하고 있습니다.

PPS : 다른 그래픽 카드를 사용하면 성능이 변경되지 않기 때문에 문제가 하드웨어가 관련되어 있지 않음을 확인할 수 있습니다.

Answer 1

오늘날 대부분의 X 구현은 그래픽 카드의 2D 하드웨어를 사용하므로 둘 사이의 차이는 무시할 수 있습니다.

이것은 성능 문제이므로 내 대답이 정확할 가능성은 약 10%입니다 (성능을 발휘하면 측정하지 않고 잘못 될 가능성이 90%입니다). 확실히 원한다면 소규모 성능 테스트를 작성하고 직접 볼 수있는 방법이 없습니다.

x11perf 도움이 될 수 있습니다.

하드웨어 독립 다각형 필에 대한 알고리즘을 여기에서 찾을 수 있습니다. http://cvsweb.xfree86.org/cvsweb/xc/programs/xserver/mi/mipolygen.c?rev=head

다각형이 볼록한 것으로 확신하면 훨씬 빠른 두 번째 버전이 있습니다. http://cvsweb.xfree86.org/cvsweb/xc/programs/xserver/mi/mipolycon.c?rev=head

두 번째 버전은 채우기 규칙을 무시합니다 (볼록 다각형에는 적용되지 않음). 알고리즘에 대한 의견 : http://cvsweb.xfree86.org/cvsweb/xc/programs/xserver/mi/mipoly.h?rev=head

알고리즘은 이런 방식으로 작동합니다. 개요를 계산 한 다음 가장자리 사이에 스팬 객체 (단지 도끼, Y 좌표 및 너비)를 만듭니다. Evenodd 규칙을 사용하는 경우 교차로가 있으면 더 많은 범위 객체가 생성됩니다. 없는 경우 (예를 들어, 다각형이 볼록한 경우), 충전 규칙이 MifillPolygon의 기본 루프에서 부울 변수에 해당하기 때문에 런타임 차이를 알지 못할 것입니다 (즉, 대부분의 코드는 모두 동일합니다. 규칙을 채우십시오).

다각형의 개요를 최적화하여 성능을 향상 시키려고 시도하면 다각형이 불필요한 포인트가 매우 많다는 것을 아는 경우를 제외하고는 공동 사례에서 많은 것을 사지 않을 것입니다 (예 : 일반적인 경우). <10 포인트로 다각형을 최적화하면 달성하는 것보다 더 많은 비용이들 것입니다.

그러나 다시 : 이것은 모두 장의 느낌이나 오래된 기사에 대한 지식을 기반으로합니다. GFX 카드 드라이버의 버그가 결과를 엉망으로 만드는지 알고 싶다면 손을 더럽 히고 각 케이스의 시간을 측정하는 테스트를 작성해야합니다. 외부 요인으로 인해 간단히 보면 복잡한 알고리즘의 런타임을 알 수있는 방법이 없습니다 : 메모리 할당 루틴의 속도, 자유 메모리 양 (스왑 시작시기), 사용할 수있는 CPU 코어 수, 수 다른 프로세스는 CPU를 위해 당신과 싸울 것입니다. 화면에서 최종 다각형의 클리핑, 구현 세부 사항 및 최적화, 버그 등.