행군 큐브

Marching cubes
마칭 큐브를 사용하여 150개의 MRI 슬라이스에서 추출한 머리와 뇌 구조(숨김) (약 150,000개의 삼각형)

행진 큐브는 로렌센과 [1]클라인에 의해 1987년 SIGGRAPH에서 발표된 컴퓨터 그래픽 알고리즘으로, 3차원 이산 스칼라 필드(복셀이라고도 함)에서 등각면의 폴리곤 메쉬를 추출하기 위한 것입니다.이 알고리즘의 적용은 주로 CT 및 MRI 스캔 데이터 영상과 같은 의료 시각화, 메타볼 또는 기타 메타서프로 불리는 특수 효과 또는 3-D 모델링과 관련이 있다.행진 큐브 알고리즘은 3-D에 사용되도록 되어 있으며, 이 알고리즘의 2-D 버전은 행진 제곱 알고리즘이라고 불립니다.

역사

이 알고리즘은 윌리엄 E에 의해 개발되었습니다. 제너럴 일렉트릭 연구 결과 로렌센(1946-2019)과 하비 클라인.General Electric에서는 CT [2]및 MRI 장치의 데이터를 효율적으로 시각화하는 방법을 연구했습니다.

알고리즘의 전제는 입력 볼륨을 개별 큐브 세트로 나누는 것입니다.선형 재구성 필터링을 가정하면 큐브 정점의 샘플 값이 목표 등각면 값을 넘어야 하기 때문에 주어진 등각면의 일부를 포함하는 각 큐브를 쉽게 식별할 수 있다.등각면의 단면을 포함한 각 큐브에 대해 내부 큐브 내의 삼선형 보간체의 거동을 근사하는 삼각형 메쉬를 생성한다.

이 알고리즘의 첫 번째 공개된 버전은 회전 대칭과 반사 대칭을 이용했으며 15개의 고유한 사례로 테이블을 구축하기 위한 변경 사항도 표시했습니다.그러나, 큐브 면과 내부에서의 삼선형 보간 거동의 모호성 때문에, 행군 큐브에 의해 추출된 메시는 불연속성과 위상 문제를 나타냈다.그리드의 입방체를 지정하면 면 꼭지점에 교대로 기호가 있을 때 면 모호성이 발생합니다.즉, 이 면의 한 대각선의 정점은 양이고 다른 면의 정점은 음입니다.이 경우 면 꼭지점의 부호는 등각면을 삼각 측량하는 올바른 방법을 결정하기에 불충분합니다.마찬가지로, 정육면체 정점의 부호가 올바른 표면 삼각측량을 결정하기에 충분하지 않은 경우, 즉 동일한 정육면체 구성에 대해 여러 삼각측량이 가능한 경우 내부 모호성이 발생합니다.

Marching Cubes의 인기와 그 광범위한 채택으로 알고리즘이 몇 가지 개선되어 모호성에 대처하고 보간자의 동작을 올바르게 추적하게 되었습니다.1988년[3] 더스트는 로렌센과 클라인에 의해 제안된 삼각측량표가 불완전하고 특정 Marching Cubes 사례가 다중 삼각측량을 허용한다는 것을 최초로 주목했다.Durst의 '추가 참조'는 Wyvill, Wyvill 및 McPeiters의 [5]초기, 보다 효율적인 등수면 폴리곤화 알고리즘(de[4] Araujo 참조)에 대한 것이었다.이후 1991년 니엘슨과 하만은[6] 입방체 표면의 보간 거동에 모호성의 존재를 관찰했다.그들은 입방체 면에 있는 보간물을 정확하게 추적하기 위해 점근 디시더라고 불리는 테스트를 제안했다.실제로 1994년 나타라잔이[7] 관찰한 바와 같이, 이 모호성 문제는 큐브 내부에서도 발생합니다.저자는 자신의 연구에서 보간 임계점에 기초한 모호성 검정을 제안하고, 행군 큐브 삼각 측량 표에 4개의 새로운 사례(사례 3, 4, 6, 7의 하위 사례)를 추가했다.이 시점에서 알고리즘과 삼각 측량 테이블에 제안된 모든 개선사항에도 불구하고, Marching Cubes에 의해 생성된 메시는 여전히 위상 부호가 있었다.

1995년 체르냐예프가[8] 제안한 행진 큐브 33은 삼선형 보간체의 위상을 보존하기 위한 최초의 등서면 추출 알고리즘 중 하나이다.Chernyev는 그의 연구에서 삼각 측량 룩업 테이블의 사례 수를 33개까지 확장했습니다.그런 다음 그는 점근적 결정자에 기초한 내부 모호성을 해결하기 위해 다른 접근법을 제안한다.이후 2003년 니엘슨은[9] 체르냐예프의 룩업 테이블이 완전하고 삼선형 보간체의 가능한 모든 동작을 나타낼 수 있다는 것을 증명했고, 르위너 [10]등은 알고리즘에 대한 구현을 제안했다.또한 2003년에는 [7]Lopes and Brodlie가[11] Natarajan이 제안한 테스트를 확장했습니다.2013년,[12] 관리자 등은 체르냐예프가 [8]제안한 행진 큐브 33 알고리즘에 의해 생성된 메쉬의 위상적 정확성을 훼손하는 알고리즘의 부정확성에 주목하고 수정했다.

원래 공개된 15개의 큐브 구성

알고리즘.

알고리즘은 스칼라 필드를 통과하여 한 번에 8개의 인접 위치를 취하여(따라서 가상 큐브를 형성하고), 이 큐브를 통과하는 등각면의 부분을 나타내는 데 필요한 폴리곤을 결정합니다.그런 다음 개별 폴리곤이 원하는 표면에 융합됩니다.

이는 큐브 내에서 가능한 256개의 폴리곤 구성(2=256)으로8 구성된 사전 계산된 배열에 대한 인덱스를 생성하여 8비트 정수의 비트로 각 스칼라 값을 처리함으로써 수행됩니다.스칼라 값이 iso 값보다 높으면(즉, 지표면 내부에 있음) 적절한 비트가 1로 설정되고 낮으면(외부) 0으로 설정됩니다.8개의 스칼라를 모두 체크한 후 마지막 값은 폴리곤 인덱스 배열에 대한 실제 인덱스입니다.

마지막으로 생성된 폴리곤의 각 정점은 해당 모서리에 의해 연결된 2개의 스칼라 값을 선형으로 보간함으로써 입방체의 모서리를 따라 적절한 위치에 배치된다.

각 격자점에서 스칼라 장의 기울기는 또한 그 지점에서 통과하는 가상의 등각면의 정규 벡터이다.따라서 이러한 노멀은 생성된 정점의 노멀을 찾기 위해 각 큐브의 가장자리를 따라 보간될 수 있으며, 이는 결과적인 메쉬를 어떤 조명 모델로 음영시키는 데 필수적인 것이다.

원천

  1. ^ Lorensen, William E.; Cline, Harvey E. (1 August 1987). "Marching cubes: A high resolution 3D surface construction algorithm". ACM SIGGRAPH Computer Graphics. 21 (4): 163–169. CiteSeerX 10.1.1.545.613. doi:10.1145/37402.37422.
  2. ^ "System and method for the display of surface structures contained within the interior region of a solid body". 5 June 1985. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  3. ^ Dürst, Martin J. (1988-10-01). "Letters: additional reference to marching cubes". ACM SIGGRAPH Computer Graphics. 22 (5): 243. doi:10.1145/378267.378271. ISSN 0097-8930. S2CID 36741734.
  4. ^ de Araujo, Bruno; Lopes, Daniel; Jepp, Pauline; Jorge, Joaquim; Wyvill, Brian (2015). "A Survey on Implicit Surface Polygonization". ACM Computing Surveys. 47 (4): 60:1–60:39. doi:10.1145/2732197. S2CID 14395359.
  5. ^ Wyvill, Geoff; Wyvill, Brian; McPheeters, Craig (1986). "Data structures for soft objects". The Visual Computer. 2 (4): 227–234. doi:10.1007/BF01900346. S2CID 18993002.
  6. ^ Nielson, G.M.; Hamann, B. (1991). "The asymptotic decider: Resolving the ambiguity in marching cubes". Proceeding Visualization '91. pp. 83–91. doi:10.1109/visual.1991.175782. ISBN 978-0818622458. S2CID 35739150.
  7. ^ a b Natarajan, B. K. (January 1994). "On generating topologically consistent isosurfaces from uniform samples". The Visual Computer. 11 (1): 52–62. doi:10.1007/bf01900699. ISSN 0178-2789. S2CID 526698.
  8. ^ a b V., Chernyaev, E. (1995). Marching Cubes 33 : construction of topologically correct isosurfaces : presented at GRAPHICON '95, Saint-Petersburg, Russia, 03-07.07.1995. CERN. Computing and Networks Division. OCLC 897851506.
  9. ^ Nielson, G.M. (2003). "On marching cubes". IEEE Transactions on Visualization and Computer Graphics. 9 (3): 283–297. doi:10.1109/TVCG.2003.1207437.
  10. ^ Lewiner, Thomas; Lopes, Hélio; Vieira, Antônio Wilson; Tavares, Geovan (January 2003). "Efficient Implementation of Marching Cubes' Cases with Topological Guarantees". Journal of Graphics Tools. 8 (2): 1–15. doi:10.1080/10867651.2003.10487582. ISSN 1086-7651. S2CID 6195034.
  11. ^ Lopes, A.; Brodlie, K. (2003). "Improving the robustness and accuracy of the marching cubes algorithm for isosurfacing" (PDF). IEEE Transactions on Visualization and Computer Graphics. 9: 16–29. doi:10.1109/tvcg.2003.1175094. hdl:10316/12925.
  12. ^ Custodio, Lis; Etiene, Tiago; Pesco, Sinesio; Silva, Claudio (November 2013). "Practical considerations on Marching Cubes 33 topological correctness". Computers & Graphics. 37 (7): 840–850. CiteSeerX 10.1.1.361.3074. doi:10.1016/j.cag.2013.04.004. ISSN 0097-8493. S2CID 1930192.

「 」를 참조해 주세요.

외부 링크

Wikimedia Commons에는 행진 큐브와 관련된 미디어가 있습니다.