양우 동 - 바스 카 이 커팅 알고리즘

Cyrus 와 Beck 은 Cohen - Sutherland 보다 더 효과 적 인 알고리즘 을 매개 변수 화 방법 으로 제시 했다.이후 양우 동과 바스 카 이 는 독립 적 으로 더 빠 른 매개 변수 화 선분 재단 알고리즘 을 제 시 했 고 리 안 - 바스 카 이 (LB) 알고리즘 이 라 고도 불 렀 다.
     1. 양우 동 - Barsky 재단 알고리즘 사상:
우 리 는 한 개의 양 끝 점 이 P1 (x1, y1), P2 (x2, y2) 인 선분 은 매개 변수 방정식 형식 으로 표시 할 수 있다 는 것 을 알 고 있다.
 
x= x1+ u·（x2-x1）= x1+ u·Δx y= y1+ u·（y2-y1）= y1+ u·Δy
0≤u≤1
（3-9）
식 중,Δx=x2-x1，Δy = y2 - y1, 매개 변수 u 는 0 ~ 1 사이 에 값 을 추출 합 니 다. P (x, y) 는 이 라인 의 한 점 을 대표 합 니 다. 그 값 은 매개 변수 u 에 의 해 확정 되 고 공식 적 으로 알 수 있 습 니 다. u = 0 일 때 이 점 은 P1 (x1, y1) 이 고 u = 1 일 때 이 점 은 P2 (x2, y2) 입 니 다.점 P (x, y) 가 좌표 (xwmin, ywmin) 와 (xwmax, ywmax) 가 정 한 창 에 있 으 면 다음 식 으로 성립 됩 니 다.
 
xwmin≤x1+ u·Δx≤xwmaxywmin≤y1+ u·Δy≤ywmax
（3-10）
이 네 개의 부등식 은 다음 과 같다.
u·pk ≤qk ， k=1，2，3，4
（3-11）
그 중에서 p, q 는 다음 과 같이 정의 합 니 다.
 
p1=-Δx， q1=x1-xwminp2=Δx， q2=xwmax-x1p3=-Δy， q3=y1-ywminp4=Δy， q4=ywmax-y1
（3-12）
(3 - 12) 식 에서 알 수 있 듯 이 창의 한 경계 에 평행 하 는 모든 직선 은 pk = 0 (그러나 모든 Pk 가 0 이 아니 라 pk = 0 이 존재 한 다 는 뜻 입 니 다. 창의 한 경계 에 평행 하 는 그림 은 (p1 & & p 2) | | (p3 & & p4) = 0 의 경우), k 값 은 해당 하 는 경계 (k = 1, 2, 3, 4 는 왼쪽, 오른쪽, 아래, 윗 경계) 에 대응 합 니 다.qk < 0 (기본 x1 이 가장 왼쪽 점 입 니까? 기본 경사 율 이 0 보다 1 보다 작 습 니까?) 을 만족 시 키 면 선분 은 경계 밖 에 있 으 므 로 이 선분 을 버 려 야 합 니 다.만약 pk = 0 및 qk ≥ 0 이 라면 선분 은 창의 특정한 경계 와 평행 하고 창 안에 있 으 며 그림 에서 보 여 줍 니 다.공식 (3 - 12) 식 은 우리 에 게 도 알려 준다.
1. pk < 0 시 선분 은 경계 연장선 을 자 르 는 외부 에서 내부 로 연장 합 니 다.
2. pk > 0 시 선분 은 경계 연장선 을 자 르 는 내부 에서 외부 로 연장 합 니 다.
가령Δx ≥ 0 시 왼쪽 경계 p1 < 0 (p1 = -Δx) 왼쪽 경계 외부 에서 내부 까지 라인;
오른쪽 경계 p2 > 0 (p2 =Δx) 오른쪽 경계 내부 에서 외부 까지 라인.
... 해 야 한다Δy < 0 시, 아래 경계 p3 > 0 (p3 = -Δy) 라인 은 아래 경계 내부 에서 외부 로;
상단 경계 p4 < 0 (p4 =Δy), 선분 은 상경 계 의 외부 에서 내부 로.
pk ≠ 0 시 매개 변수 u 의 값 을 계산 할 수 있 습 니 다. 무한 연장 의 직선 과 연장 하 는 창 경계 k 의 교점 에 대응 합 니 다. 즉,:
（3-13）
각 직선 에 대해 매개 변수 u1 과 u2 를 계산 할 수 있 습 니 다. 이 값 은 창 에 있 는 선분 부분 을 정의 합 니 다.
1. u1 의 값 은 선분 이 밖에서 안 으로 만 나 는 사각형 경계 에 의 해 결정 된다 (pk < 0). 이 경계 에 대해 rk = qk / pk, u1 은 0 과 각 r 값 중 최대 값 을 계산한다.
2. u2 의 값 은 선분 이 안에서 밖으로 만 나 는 사각형 경계 에 의 해 결정 된다 (pk > 0). 이 경계 에 대해 rk = qk / pk, u2 는 0 과 각 r 값 중의 최소 값 을 계산한다.
3. u1 > u2 가 있 으 면 선분 이 재단 창 밖 에 완전히 떨 어 지고 버 려 져 야 합 니 다.그렇지 않 으 면 잘 린 선분 의 단점 은 u1 과 u2 로 계산 할 수 있다.
2. 양 우 동 - Barsky 재단 알고리즘 실현:
1. 선분 교점 의 매개 변 수 를 초기 화 합 니 다: u1 = 0, u2 = 1;
2. 각 재단 경계의 pk, qk 값 (k = 1, 2, 3, 4) 을 계산한다.
3. [호출 함수 클립 테스트 ()] 는 함수 에서 p, q 에 따라 선분 을 버 리 는 지 교점 을 바 꾸 는 지 판단 합 니 다.(계산 rk = qk / pk, 근거 (1), (2) · · · 집행)
(1) p < 0 시 매개 변수 r 는 u1 을 업데이트 하 는 데 사 용 됩 니 다.　　　　　（u1=max{u1，…，rk}）
(2) p > 0 시 인자 r 는 u2 를 업데이트 하 는 데 사 용 됩 니 다.　　　　　（u2=min{u2，…，rk}）
(3) u1 또는 u2 를 업데이트 한 후 u1 > u2 를 사용 하면 이 라인 을 버 립 니 다.
(4) p = 0 및 q < 0 시 선분 이 경계 에 평행 하고 경계 밖 에 있 기 때문에 이 선분 을 버린다.다음 그림 에서 보 듯 이.
4. p, q 의 네 가지 값 을 판단 한 후에 이 선분 이 버 려 지지 않 으 면 선분 의 점 좌 표 는 매개 변수 u1 과 u2 의 값 에 의 해 결정 된다.
3. 양 우 동 - Barsky 재단 알고리즘 특징:
양우 동 - Barsky 알고리즘 은 직사각형 창의 경우 에 만 적 용 됩 니 다.보통 양우 동 - Barsky 알고리즘 은 Cohen - Sutherland 알고리즘 보다 효율 이 높 습 니 다. 계산 해 야 할 교점 수가 줄 어 들 었 기 때 문 입 니 다.매개 변수 u1, u2 를 업데이트 하려 면 한 번 의 나눗셈 만 필요 합 니 다.선분 과 창 경계 의 교점 은 한 번 만 계산 하면 u1, u2 의 마지막 값 을 계산 합 니 다.이에 비해 한 라인 이 재단 창 에 완전히 떨 어 지 더 라 도 Cohen - Sutherland 알고리즘 은 교점 을 반복 적 으로 구하 고 매번 계산 할 때마다 곱셈 법 을 해 야 한다.
양우 동 - Barsky 와 Cohen - Sutherland 알고리즘 은 3 차원 커팅 알고리즘 으로 도 확장 할 수 있다.
4. 양우 동 - Barsky 재단 알고리즘 프로그램:
        MFC 에서 작 성 된 프로그램 (소스 코드 포함):http://download.csdn.net/detail/marcnuth/4938143
        양우 동 알고리즘 핵심 소스 코드:

#include "graphics.h"
int clipTest(float p,float q,float *u1,float *u2) 
{
　int flag=1; /*flag     ，0：    ；1：    。*/
　float r;
　if(p<0.0) 
　{
　　r=q/p;
　　if(r>*u2)
　　　flag=0;
　　else if(r>*u1) 
　　　*u1=r; /*u1 "  "       */
　}
　else if(p>0.0) 
　{
　　r=q/p;
　　if(r0.0)
　　　　　{
　　　　　　x1=x1+u1*dx; /*  u1      p1  */
　　　　　　y1=y1+u1*dy;
　　　　　}
　　　　　line(x1,y1,x2,y2); /*        */
　　　　}
　　}
}

본문 출처: http://course.cug.edu.cn/cugThird/CGOL_NET/CLASS/course/3-2-3-a.htm