은선제거

Hidden-line removal
은선제거를 이용한 와이어프레임 이미지

고체 물체는 보통 컴퓨터 표현에서 다면체로 모델링된다. 다면체의 면은 직선 세그먼트로 경계된 평면 다각형이며, 가장자리라고 한다. 곡선 표면은 보통 폴리곤 망사로 근사치를 구한다. 불투명 물체의 선 도면을 위한 컴퓨터 프로그램은 물체 자체 또는 다른 물체에 의해 어떤 가장자리나 가장자리의 어떤 부분이 가려지는지를 결정할 수 있어야 한다. 이 문제는 은선 제거라고 알려져 있다.

숨겨진 선의 문제에 대한 최초의 알려진 해결책은 1963년 L. G. 로버츠에[1] 의해 고안되었다. 그러나, 그것은 모델을 심각하게 제한한다: 그것은 모든 물체가 볼록하도록 요구한다. 루스 A. Bell Labs의 Weiss는 이 문제에 대한 그녀의 1964년 해결책을 1965년 논문에 기록했다.[2] 1966년 이반 E. 서덜랜드는 컴퓨터 그래픽에 미해결 문제 10가지를 열거했다.[3] 7번 문제는 "숨은 선 제거"였다. 계산 복잡성 측면에서 이 문제는 1986년 데바이에 의해 해결되었다.[4]

예를 들어 컴퓨터 지원 설계에서 모델은 수천 또는 수백만 개의 가장자리를 가질 수 있다. 따라서 문제 크기의 함수로 시간, 메모리 등의 자원 요구사항을 표현하는 계산 복합성 접근법이 중요하다. 시간 요건은 인터랙티브 시스템에서 특히 중요하다.

은선 제거를 위한 문제 크기는 모델 가장자리의 총 수 n과 가장자리의 가시적인 세그먼트의 총 수 v이다. 가장자리 영상의 교차점에서 가시성이 변경될 수 있다. k는 가장자리 이미지의 교차점 총 수를 나타낸다. k = θ(n2)과 v = θ(n2) 모두 최악의 경우 [4]θ(n)이지만 대개 v < k.

알고리즘

1984년[5][6][7][8] 이전에 발표된 히든라인 알고리즘은 가장자리를 이미지의 교차점별로 선 세그먼트로 나눈 다음 각 세그먼트를 모델의 각 면에 대해 가시성을 테스트한다. 오일러의 공식에 따르면 ologically(n) 면은 faces(n) 면이며, 표면학적으로 각 면의 경계가 구와 동등한 다면체 집합 모델을 assuming(n) 면은 θ(n) 면이다. θ(n) 면에 대해 θ(n2) 라인 세그먼트를 테스트하는 데는 최악의 경우 θ(n3) 시간이 걸린다.[4] 가시성 오류가 후속 세그먼트 끝점으로 전파되기 때문에 Appel의 알고리즘도[5] 불안정하다.[9]

Ottmann 및 Widmayer와[10] Ottmann, Widmayer 및 Wood는[11] O(n + k) 시간2 히든라인 알고리즘을 제안했다. 그 후 누르미는 실행시간을 O(n + k) log n)로 개선했다[12]. 이러한 알고리즘은 최악의 경우 각각 θ(n2 log2 n), θ(n2 log n) 시간이 걸리지만, k가 2차 미만일 경우 실제로는 더 빠를 수 있다.

모든 은선 알고리즘은 최악의 경우 n개의 가장자리에서 hidden(n) 은닉 간격의 조합을 결정해야 한다. Ω(n log n)은 n구간의 결합을 결정하는 하한값이기 때문에 [13]hope(n2 log n) 최악의 경우 θ(n log n)가 가장 기대되는 것으로 보이며, 따라서 누르미의 알고리즘이 최적이다.

그러나 로그 n 인자는 데바이에 의해 제거되었는데,[4] 데바이는 숨겨진 표면 제거에 대해 동일한 최적의 O(n2) 상한이 존재하는지 여부에 대해 개방적인 문제를 제기했다. 이 문제는 1987년 맥케나에 의해 해결되었다.[14]

교차로에[10][11][12] 민감한 알고리즘은 주로 계산 지리학 문헌에 알려져 있다. 이차적 상한은 컴퓨터그래픽 문헌에서도 인정받고 있다. Ghali는 Devai와 McKenna의 알고리즘이 "가시성 알고리즘의 이정표"를 나타내며, N 에지의 장면을 처리하기 위한 이론적 장벽을 O(n2 log n)에서 O(n2)로 깨뜨렸다고 지적한다[15].

Devai가 제기한 또 다른 개방형 문제는 O(n log n + v) 시간 히든라인 알고리즘이 존재하는지 여부인데,[4] 여기서 v는 위에서 언급한 바와 같이 가시적인 세그먼트의 수로서, 여전히 작성 시점에서 해결되지 않고 있다.

병렬 알고리즘

1988년 Devai는 동시 읽기 전용 쓰기(CRW) 병렬 RAM(Parallel Random-Access Machine) 모델의 히든라인 문제에 대해 n개의2 프로세서를 사용하는 O(log n) 시간 병렬 알고리즘을 제안했다[16]. 프로세서 번호와 실행 시간의 산출물이 점증적으로 ((n2)보다 크므로 문제의 순차적 복잡성인 알고리즘이 작업 최적성은 아니지만, 은선 문제가 복잡도 등급 NC에 있음을 증명한다. 즉, 다항식 프로세서를 사용하여 다항식 시간에 해결할 수 있다.

숨겨진 표면 알고리즘은 은선 제거에 사용될 수 있지만 반대로 사용할 수는 없다. Reif와 Sen은 다면체 지형의 제한된 모델에 O4(n + v)/log n) CREAM PRAM 프로세서를 사용하여 숨겨진 표면 문제에 대한 O(log n) 시간 알고리즘을 제안했다. 여기서 v는 출력 크기다.

2011년 Devai는 O(log n)-time hidden-surface와 보다 단순한 O(log n)-time, hiddle-line 알고리즘을 발표했다[18]. n2/log n CRUE PRAM 프로세서를 사용하는 숨겨진 표면 알고리즘은 작업 최적이다.

은선 알고리즘은 n개의2 전용 읽기 전용 쓰기(EREW) PRAM 프로세서를 사용한다. ERW 모델은 실제 기계에 가장 가까운 PRAM 모델이다. Hidden-line 알고리즘은2 O(n log n) 작업을 하는데, 이는 실무에서 사용되는 최선의 순차 알고리즘의 상한이다.

Cook, Dwork 및 Reischuk은 동시 쓰기 없이 모든 PRAM의 무한히 많은 프로세서를 허용하는 최대 n의 정수를 찾기 위해 Ω(log n) 하한을 부여했다.[19] 최대 n개의 정수를 찾는 것은 n개의 프로세서를 사용하여 은선 문제를 일정 시간 줄일 수 있다. 그러므로 히든라인 알고리즘은 시간 최적이다.[18]

참조

  1. ^ L. G. 로버츠 3차원 고형물에 대한 기계 인식. 1963년 매사추세츠 공과대학 박사학위 논문.
  2. ^ Ruth A. Weiss [https://ohiostate.pressbooks.pub/app/uploads/sites/45/2017/09/bevision-wiss.pdf BE VISION, IBM 7090 FORTRAN 프로그램의 패키지 평면과 4중 표면 조합의 직교적 뷰 그리기 ]
  3. ^ I. E. 서덜랜드. 컴퓨터 그래픽의 미해결 문제 10가지. Datamisation, 12(5):22–27, 1966.
  4. ^ a b c d e F. 데바이. 은선 제거를 위한 2차 한계. Proc. 제2회 연산 기하학 연차 심포지엄에서 SCG '86, 페이지 269–275, 뉴욕, 뉴욕, 미국, 1986.
  5. ^ a b A. 아펠. 정량적 투명성의 개념과 고형물의 기계 렌더링. Proc. 22차 전국 컨퍼런스, ACM '67, 페이지 387–393, 뉴욕, 미국, 1967.
  6. ^ R. 갈림베르티와 U. 몬타나리. 은선 제거를 위한 알고리즘. 코뮌. ACM, 12:206–211, 1969년 4월.
  7. ^ 호릉. 계산 최소화된 은선 알고리즘에 대한 접근법. 컴퓨터 & 그래픽스, 6(3):121–126, 1982.
  8. ^ P. P. Loutrel. 컴퓨터가 그린 다면체의 은선 문제에 대한 해결책. IEEE 트랜스. 계산, 19(3):205–213, 1970년 3월.
  9. ^ J. F. 블린 부분적 투명성. IEEE Compute. 그래프. 적용, 8:77–84, 1988년 11월.
  10. ^ a b Th. Ottmann과 P. 위드마이어. 스켈레톤 구조를 사용하여 가시성 문제 해결 Proc. Mathematical Foundation of Computer Science 1984, 페이지 459–470, 영국 런던, 1984. 스프링거-베를라크.
  11. ^ a b Th. Ottmann, P. Widmayer, D. 목재. 은선 제거를 위한 최악의 경우 효율적인 알고리즘. 인터내타트. J. 컴퓨터 수학, 18(2):93–119, 1985.
  12. ^ a b O. 누르미. 숨겨진 라인 제거를 위한 빠른 라인 스위프 알고리즘. BIT, 25:466–472, 1985년 9월.
  13. ^ M. L. Fredman과 B. ui[a], bi]의 계산 복잡성에 대하여. 코뮌. ACM, 21:540–544, 1978년 7월.
  14. ^ M. 매케나. 최악의 경우 최적의 숨김 표면 제거. ACM Trans. 그래프, 1987년 1월 6:19–28.
  15. ^ 샬갈리. 실제 객체 공간 가시성 알고리즘의 조사. SIGGRAPH 자습서 노트, 1(2), 2001.
  16. ^ F. 데바이. O(log N) 병렬 시간 정확한 은선 알고리즘. 컴퓨터 그래픽 하드웨어 II, 페이지 65–73, 1988의 진보.
  17. ^ J. H. 레이프와 S. 센. 효율적인 출력에 민감한 숨겨진 표면 제거 알고리즘 및 병렬화. Proc. 제4회 연산 기하학 연감 88, 페이지 193–200, 뉴욕, 뉴욕, 미국, 1988.
  18. ^ a b F. 데바이. 최적의 숨겨진 표면 알고리즘과 병렬화. ICCSA 2011의 컴퓨터 과학 및 응용 분야에서는 컴퓨터 과학 강의 노트 6784권, 페이지 17–29. 스프링거 베를린/하이델베르크, 2011.
  19. ^ 요리사, C D워크, 그리고 R. 리스추크. 동시 쓰기가 없는 병렬 랜덤 액세스 시스템의 시간 상한 및 하한. SIAM J. Compute, 15:87–97, 1986년 2월.

외부 링크

  • Patrick-Gilles Maillot의 논문, 3D 은선 제거를 위한 브레센햄 라인 그리기 알고리즘의 확장; 또한 CAD/CAM 및 컴퓨터 그래픽에 관한 MICAD '87 절차' 591페이지에 발표되었다. ISBN2-86601-084-1.
  • 벡터 히든 라인 제거(Vector Hidden Line Removal)는 월터 헤거의 (병리학적 사례에 대한 추가 설명)와 더 많은 인용구들을 담은 글이다.