Ⅰ. 클리핑 알고리즘 설계와 구현

1. 비디오 메모리와 클리핑

• 클리핑(Clipping)
  • 보이는 영역에서 벗어난 부분을 잘라내는 것
• 클리핑 처리하는 가장 간단한 방안
  • ‘픽셀을 출력할 때마다, 매번 보이는 위치에 있는지 확인’하는 것이다.
  • 단점은 출력할 픽셀이 많아져, 시간이 오래 걸리는 것이기 때문에, 픽셀을 많이 출력하지 않는 도형에 쓸만한 방법이다.
• MINT OS에서 클리핑 처리하는 방안
  • 픽셀이 적은 점과 선을 사용한 속이 빈 사각형과 속이 빈 원은 매번 확인하는 방법으로 처리한다.
  • 픽셀이 많은 속이 찬 사각형과 속이 찬 원, 문자는 보이는 영역을 미리 계산하여, 매번 비교하지 않는 방법으로 처리한다.

2. 점 클리핑 처링

• 그래픽 모드의 화면 크기를 기준으로 클리핑을 수행하는 점 그리기 함수의 코드

  inline void kDrawPixel( int iX, int iY, COLOR stColor ){
      VBEMODEINFOBLOCK* pstModeInfo;
  
      // 모드 정보 블록 반환
      pstModeInfo = kGetVBEModeInfoBlock();
  
      // 클리핑 처리
      // 화면에 표시되는 영역이 아니면 그리지 않음
      if( ( iX < 0 ) || ( pstModeInfo->wXResolution <= iX ) ||
          ( iY < 0 ) || ( pstModeInfo->wYResolution <= iY ) )
      {
              return ;
      }
  
      // Physical Address를 COLOR 타입으로 하면 픽셀 오프셋으로 계산 가능
      *((( COLOR* ) pstModeInfo->dwPhysicalBasePointer ) + 
              pstModeInfo->wXResolution * iY + iX ) = stColor;
  }
  

• 사각형 영역의 정보와 점 정보를 저장하는 자료구조

  • 현재는 그래픽 모드 영역이 지정되어 있지만, 나중에 윈도우 구현 시에는 윈도우 영역을 기준으로 클리핑을 처리해야 한다.
  • 윈도우 경우, 크기가 정해져 있지 않고 언제든 변경이 가능하므로, 해당 크기를 파라미터로 전달 받아야 한다.
  • 파라미터로 전달 받으려니, 파라미터가 많아서 자료구조를 사용하여 정의한다.

  // 사각형의 정보를 담는 자료구조
  typedef struct kRectangleStuct
  {
      // 왼쪽 위(시작점)의 X좌표
      int iX1;
      // 왼쪽 위(시작점)의 Y좌표
      int iY1;
  
      // 오른쪽 아래(끝점)의 X좌표
      int iX2;
      // 오른쪽 아래(끝점)의 Y좌표
      int iY2;
  } RECT;
  
  // 점의 정보를 담는 자료구조
  typedef struct kPointStruct
  {
      // X와 Y의 좌표
      int iX;
      int iY;
  } POINT;
  

• 파라미터로 전달받은 정보를 기준으로 클리핑을 수행하는 점 그리기 함수의 코드

  // (x, y)가 사각형 영역 안에 있는지 여부를 반환
  inline BOOL kIsInRectangle( const RECT* pstArea, int iX, int iY ){
      // 화면에 표시되는 영역을 벗어났다면 그리지 않음
      if( ( iX < pstArea->iX1 ) || ( pstArea->iX2 < iX ) ||
          ( iY < pstArea->iY1 ) || ( pstArea->iY2 < iY ) )
      {
          return FALSE;
      }
      return TRUE;
  }
  
  // 사각형의 너비를 반환
  inline int kGetRectangleWidth( const RECT* pstArea ){
      int iWidth;
  
      iWidth = pstArea->iX2 - pstArea->iX1 + 1;
  
      if( iWidth < 0 ){
          return -iWidth;
      }
  
      return iWidth;
  }
  
  // 사각형의 높이를 반환
  inline int kGetRectangleHeight( const RECT* pstArea ){
      int iHeight;
  
      iHeight = pstArea->iY2 - pstArea->iY1 + 1;
  
      if( iHeight < 0 ){
          return -iHeight;
      }
  
      return iHeight;
  }
  
  // 점 그리기
  inline void kInternalDrawPixel( const RECT* pstMemoryArea, COLOR* pstMemoryAddress,
          int iX, int iY, COLOR stColor )
  {
      int iWidth;
  
      // 클리핑 처리
      // 화면에 표시되는 영역을 벗어났다면 그리지 않음
      if( kIsInRectangle( pstMemoryArea, iX, iY ) == FALSE ){
          return ;
      }
  
      // 출력할 메모리 영역의 너비를 구함
      iWidth = kGetRectangleWidth( pstMemoryArea );
  
      // 픽셀 오프셋으로 계산하여 픽셀 출력
      *( pstMemoryAddress + ( iWidth * iY ) + iX ) = stColor;
  }
  

3. 직선 클리핑 처리

• RECT 자료구조를 채우는 함수와 두 사각형 영역이 겹치는지 판단하는 함수의 코드

  // 사각형 자료구조를 채움
  //      x1과 x2, y1과 y2를 비교해서 x1 < x2, y1 < y2가 되도록 저장
  inline void kSetRectangleData( int iX1, int iY1, int iX2, int iY2, RECT* pstRect )
  {
      // x1 < x2가 되도록 RECT 자료구조에 X좌표를 설정
      if( iX1 < iX2 ){
          pstRect->iX1 = iX1;
          pstRect->iX2 = iX2;
      }
      else{
          pstRect->iX1 = iX2;
          pstRect->iX2 = iX1;
      }
  
      // y1 < y2가 되도록 RECT 자료구조에 Y좌표를 설정
      if( iY1 < iY2 ){
          pstRect->iY1 = iY1;
          pstRect->iY2 = iY2;
      }
      else{
          pstRect->iY1 = iY2;
          pstRect->iY2 = iY1;
      }
  }
  
  // 두 개의 사각형이 교차하는가 판단하여 결과를 반환
  inline BOOL kIsRectangleOverlapped( const RECT* pstArea1, const RECT* pstArea2 ){
      // 영역 1의 끝점이 영역 2의 시작점보다 작은 경우나
      // 영역 11의 시작점이 영역 2의 끝점보다 큰 경우는 서로 겹치는 부분이 없음
      if( ( pstArea1->iX1 > pstArea2->iX2 ) || ( pstArea1->iX2 < pstArea2->iX1 ) ||
          ( pstArea1->iY1 > pstArea2->iY2 ) || ( pstArea1->iY2 < pstArea2->iY1 ) )
      {
          return FALSE;
      }
      return TRUE;
  }
  

• 클리핑 처리가 추가된 직선 그리기 함수의 코드

  void kInternalDrawLine( const RECT* pstMemoryArea, COLOR* pstMemoryAddress,
          int iX1, int iY1, int iX2, int iY2, COLOR stColor )
  {
      int iDeltaX, iDeltaY;
      int iError = 0;
      int iDeltaError;
      int iX, iY;
      int iStepX, iStepY;
      RECT stLineArea;
  
      // 클리핑 처리
      // 직선이 그려지는 영역과 메모리 영역이 겹치지 않으면 그리지 않아도 됨
      kSetRectangleData( iX1, iY1, iX2, iY2, &stLineArea );
      if( kIsRectangleOverlapped( pstMemoryArea, &stLineArea ) == FALSE ){
          return ;
      }
      
      // 변화량 계산
      iDeltaX = iX2 - iX1;
      iDeltaY = iY2 - iY1;
  
      // X축 변화량에 따라 X축 증감 방향 계산
      if( iDeltaX < 0 ) 
      {
          iDeltaX = -iDeltaX; 
          iStepX = -1; 
      } 
      else 
      { 
          iStepX = 1; 
      }
  
      // Y축 변화량에 따라 Y축 증감 방향 계산 
      if( iDeltaY < 0 ) 
      {
          iDeltaY = -iDeltaY; 
          iStepY = -1; 
      } 
      else 
      {
          iStepY = 1; 
      }
  
      // X축 변화량이 Y축 변화량보다 크다면 X축을 중심으로 직선을 그림
      if( iDeltaX > iDeltaY )
      {
          // 기울기로 매 픽셀마다 더해줄 오차, Y축 변화량의 2배
          // 시프트 연산으로 * 2를 대체
          iDeltaError = iDeltaY << 1;
          iY = iY1;
          for( iX = iX1 ; iX != iX2 ; iX += iStepX )
          {
              // 점 그리기
              kInternalDrawPixel( pstMemoryArea, pstMemoryAddress, iX, iY, stColor );
  
              // 오차 누적
              iError += iDeltaError;
  
              // 누적된 오차가 X축 변화량보다 크면 위에 점을 선택하고 오차를 위에 점을
              // 기준으로 갱신
              if( iError >= iDeltaX )
              {
                  iY += iStepY;
                  // X축의 변화량의 2배를 빼줌
                  // 시프트 연산으로 *2를 대체
                  iError -= iDeltaX << 1;
              }
          }
          // iX == iX2인 최종 위치에 점 그리기
          kInternalDrawPixel( pstMemoryArea, pstMemoryAddress, iX, iY, stColor );
      }
      // Y축 변화량이 X축 변화량보다 크거나 같다면 Y축을 중심으로 직선을 그림
      else
      {
          // 기울기로 매 픽셀마다 더해줄 오차, X축 변화량의 2배
          // 시프트 연산으로 * 2를 대체
          iDeltaError = iDeltaX << 1;
          iX = iX1;
          for( iY = iY1 ; iY != iY2 ; iY += iStepY )
          {
              // 점 그리기
              kInternalDrawPixel( pstMemoryArea, pstMemoryAddress, iX, iY, stColor );
  
              // 오차 누적
              iError += iDeltaError;
  
              // 누적된 오차가 Y축 변화량보다 크면 위에 점을 선택하고 오차를 위에 점을
              // 기준으로 갱신
              if( iError >= iDeltaY )
              {
                  iX += iStepX;
                  // Y축의 변화량의 2배를 빼줌
                  // 시프트 연산으로 *2를 대체
                  iError -= iDeltaY << 1;
              }
          }
  
          // iY == iY2인 최종 위치에 점 그리기
          kInternalDrawPixel( pstMemoryArea, pstMemoryAddress, iX, iY, stColor );
      }
  }
  

4. 사각형 클리핑 처리와 원 클리핑 처리

• 속이 찬 원은 속이 찬 사각형 함수를 사용하므로, 속이 찬 사각형만 클리핑 처리하면 속이 찬 원도 해결된다.

• 두 사각형의 시작점과 끝점의 관계를 이용하여, 시작점과 끝 점의 x, y좌표를 각각 비교하고 서로 겹치는 영역을 찾아 해당 영역만 채워 사각형을 그리면 된다.

• 두 사각형 영역이 겹치는 영역을 반환하는 함수의 코드

  // 영역 1과 영역 2의 겹치는 영역을 반환
  inline BOOL kGetOverLappedRectangle( const RECT* pstArea1, const RECT* pstArea2,
          RECT* pstIntersection )
  {
      int iMaxX1;
      int iMinX2;
      int iMaxY1;
      int iMaxY2;
  
      // X축의 시작점은 두 점 중에서 큰 것을 찾음
      iMaxX1 = MAX( pstArea1->iX1, pxtArea2->iX1 );
      // X축의 끝점은 두 점 중에서 작은 것을 찾음
      iMinX2 = MIN( pstArea1->iX2, pstArea2->iX2 );
      // 계산한 시작점의 위치가 끝점의 위치보다 크다면 두 사각형은 겹치지 않음
      if( iMinX2 < iMaxX1 ){
          return FALSE;
      }
  
      // Y축의 시작점은 두 점 중에서 큰 것을 찾음
      iMaxY1 = MAX( pstArea1->iY1, pstArea2->iY1 );
      // Y축의 끝점은 두 점 중에서 작은 것을 찾음
      iMinY2 = MIN( pstArea1->iY2, pstArea2->iY2 );
      // 계산한 시작점의 위치가 끝점의 위치보다 크다면 두 사각형은 겹치지 않음
      if( iMinY2 < iMaxY1 )
      {
          return FALSE;
      }
  
      // 겹치는 영역의 정보 저장
      pstIntersection->iX1 = iMaxX1;
      pstIntersection->iY1 = iMaxY1;
      pstIntersection->iX2 = iMinX2;
      pstIntersection->iY2 = iMinY2;
  
      return TRUE;
  }
  

• 클리핑 처리가 추가된 사각형 그리기 함수의 코드

  void kInternalDrawRect( const RECT* pstMemoryArea, COLOR* pstMemoryAddress,
          int iX1, int iY1, int iX2, int iY2, COLOR stColor, BOOL bFill )
  {
      int iWidth;
      int iTemp;
      int iY;
      int iMemoryAreaWidth;
      RECT stDrawRect;
      RECT stOverlappedArea;
  
      // 채움 여부에 따라 코드를 분리
      if( bFill == FALSE ){
          // 네 점을 이웃한 것끼리 직선으로 연결
          kInternalDrawLine( pstMemoryArea, pstMemoryAddress, iX1, iY1, iX2, iY1, stColor );
          kInternalDrawLine( pstMemoryArea, pstMemoryAddress, iX1, iY1, iX1, iY2, stColor );
          kInternalDrawLine( pstMemoryArea, pstMemoryAddress, iX2, iY1, iX2, iY2, stColor );
          kInternalDrawLine( pstMemoryArea, pstMemoryAddress, iX1, iY2, iX2, iY2, stColor );
      }
      else
      {
          // 출력할 사각형의 정보를 RECT 자료구조에 저장
          kSetRectangleData( iX1, iY1, iX2, iY2, &stDrawRect );
  
          // 출력할 메모리 영역과 사각형 영역이 겹치는 부분을 계산하여 클리핑 처리
          if( kGetOverlappedRectangle( pstMemoryArea, &stDrawRect,
                  &stOverlappedArea ) == FALSE )
          {
              // 겹치는 영역이 없으면 그릴 필요 없음
              return ;            
          }
  
          // 클리핑된 사각형의 너비를 계산
          iWidth = kGetRectangleWidth( &stOverlappedArea );
  
          // 출력할 메모리 영역의 너비를 계산
          iMemoryAreaWidth = kGetRectangleWidth( pstMemoryArea );
  
          // 출력할 메모리 어드레스의 시작 위치를 계산
          // 파라미터로 전달된 사각형을 그대로 그리는 것 아니라 클리핑 처리된 사각형을
          // 기준으로 그림
          pstMemoryAddress += stOverlappedArea.iY1 * iMemoryAreaWidth + 
              stOverlappedArea.iX1;
  
          // 루프를 돌면서 각 Y축마다 값을 채움
          for( iY = stOverlappedArea.iY1 ; iY < stOverlappedArea.iY2 ; iY++ ){
              // 메모리에 사각형의 너비만큼 픽셀을 채움
              kMemSetWord( pstMemoryAddress, stColor, iWidth );
  
              // 출력할 비디오 메모리 어드레스 갱신
              // x, y좌표로 매번 비디오 메모리 어드레스를 계산하는 것을 피하려고
              // x축 해상도를 이용하여 다음 라인의 y좌표 어드레스를 계산
              pstMemoryAddress += iMemoryAreaWidth;
          }
  
          // 메모리에 사각형의 너비만큼 픽셀을 채움, 마지막 줄 출력
          kMemSetWord( pstMemoryAddress, stColor, iWidth );
      }
  }
  

5. 문자 클리핑 처리