메쉬 생성

Mesh generation
곡선 영역의 사변측정감시 유한요소 망사.

메쉬 생성은 연속적인 기하학적 공간을 이산 기하학적 및 위상학적 세포로 분할하는 메쉬를 만드는 연습이다. 종종 이 세포들은 단순한 복합체를 형성한다. 보통 셀들은 기하학적 입력 영역을 분할한다. 메쉬 셀은 더 큰 영역의 이산 로컬 근사치로 사용된다. 메쉬는 도메인의 복잡성과 원하는 메쉬의 유형에 따라 종종 GUI를 통한 인간지도를 통해 컴퓨터 알고리즘에 의해 만들어진다. 고품질(잘 생긴) 셀로 입력 영역 기하학을 정확하게 포착하는 메쉬를 만들고, 후속 계산을 난해하게 할 만큼 많은 셀이 없는 것을 목표로 한다. 그물망도 후속 계산에 중요한 영역에서는 미세해야 한다(작은 요소가 있어야 한다).

메쉬는 컴퓨터 스크린에 렌더링하고 유한요소해석이나 계산유체역학 같은 물리적 시뮬레이션에 사용된다. 메쉬는 삼각형처럼 단순한 셀로 구성되어 있는데, 예를 들어 유한요소계산(엔지니어링)이나 삼각형(컴퓨터그래픽)과 같은 연산을 삼각형에서 할 줄 알지만, 복잡한 공간이나 도로교와 같은 형태에서 이러한 연산을 직접 수행할 줄 모르기 때문이다. 각 삼각형에 대한 계산을 수행하고 삼각형 사이의 상호작용을 계산함으로써 브리지의 강도를 시뮬레이션하거나 컴퓨터 화면에 그릴 수 있다.

주요 구분은 정형화된 메싱과 비정형적인 메싱이다. 구조화된 메싱에서 메쉬는 배열과 같은 일반적인 격자로, 요소들 간의 암묵적인 연결을 가지고 있다. 비정형 메싱에서는 불규칙한 패턴으로 요소들이 서로 연결될 수 있으며, 보다 복잡한 도메인을 캡처할 수 있다. 이 페이지는 주로 비정형 메시에 관한 것이다. 메쉬가 삼각측량일 수 있지만, 메싱의 과정은 입력에 없는 정점을 추가할 수 있는 자유를 포함한다는 점에서 점 집합 삼각측량과는 구별된다. 드래프트를 위한 "조립"(삼각형) CAD 모델은 정점을 추가할 수 있는 자유는 같지만 가능한 적은 수의 삼각형을 사용하여 모양을 정확하게 나타내며 개별 삼각형의 모양은 중요하지 않다. 텍스쳐의 컴퓨터 그래픽 렌더링과 사실적인 조명 조건은 메쉬를 대신 사용한다.

많은 메쉬 생성 소프트웨어는 그것의 입력을 정의하는 CAD 시스템과 그것의 출력을 얻기 위한 시뮬레이션 소프트웨어와 결합된다. 입력은 매우 다양하지만 일반적인 형태는 솔리드 모델링, 기하학적 모델링, NURBS, B-rep, STL 또는 포인트 클라우드 입니다.

용어.

"메쉬 생성", "그리드 생성", "메싱" 및 "그리드딩"이라는 용어는, 엄밀히 말하면 후자의 두 용어는 더 광범위하고 메쉬 개선을 포괄하지만, 그 위에서 수행될 수 있는 수치 계산의 속도나 정확도를 증가시킨다는 목표로 메쉬를 변화시키는 것 등, 메쉬를 대체하여 사용하는 경우가 많다. 컴퓨터 그래픽 렌더링과 수학에서 메쉬를 테셀레이션이라고 부르기도 한다.

메쉬 면(셀, 실체)은 그 치수와 메쉬가 사용될 상황에 따라 다른 이름을 갖는다. 유한요소에서는 최고차원 메시 실체를 "요소"라고 하고, "에지"는 1D, "노드"는 0D라고 한다. 요소가 3D인 경우, 2D 실체는 "faces"이다. 계산 기하학에서 0D 점을 정점이라고 한다. 테트라헤드라는 흔히 "테트"로 약칭된다; 삼각형은 "트리스"이고, 4각측정은 "쿼드"이고, 육각형은 "헥스"이다.

기술

표면의 Catmull-Clark 하위 분할
암묵적 표면에서 생성된 망사

많은 메싱 기법은 루퍼트의 알고리즘과 같이 정점을 추가하는 규칙과 함께 델로나이 삼각측량 원리에 기초하여 구축된다. 구별되는 특징은 전체 공간의 초창기 굵은 망사가 형성된 다음 정점과 삼각형이 추가된다는 점이다. 이와는 대조적으로 전진하는 전방 알고리즘은 도메인 경계에서 시작하여 내부를 점점 채우는 요소를 추가한다. 하이브리드 기법은 둘 다 한다. 전진하는 전방 기법의 특별한 등급은 유체 흐름을 위한 원소의 얇은 경계 층을 만든다. 구조화된 메쉬 생성에서 전체 메쉬는 정사각형의 일반 격자와 같은 격자형 그래프가 된다. 정규 그리드를 위한 구조화된 메쉬 생성은 전체 분야 그 자체로, 고순도 순서의 그리드 라인이 솔루션 공간을 원활하고 정확하게 따르도록 하기 위해 수학적 기법이 적용되었다. 블록 구조 메싱에서 도메인은 큰 하위 영역으로 나뉘는데, 각각은 구조화된 메쉬다. 일부 직접 방법은 블록 구조 메쉬로 시작한 다음 입력에 맞게 메쉬를 이동시킨다. 폴리큐브 기반 자동 육각 메쉬 생성을 참조하십시오. 또 다른 직접적인 방법은 도메인 경계로 구조화된 셀을 절단하는 것이다; 행진 큐브를 기반으로 한 조각을 참조하라.

어떤 종류의 메시는 다른 것들보다 훨씬 더 만들기 어렵다. 단순한 메시는 입체 메쉬보다 쉬운 경향이 있다. 중요한 범주는 고정된 쿼드 표면 망사에 적합한 육각 망사를 생성하는 것이다. 한 연구 하위 영역은 사방 사다리꼴과 같은 특정한 작은 구성의 존재와 생성을 연구하고 있다. 이 문제의 어려움 때문에 좋은 기하학적 실현을 만들어 내는 문제와 별개로 결합형 육각 메쉬의 존재가 연구되어 왔다. 알려진 알고리즘은 최소한의 품질을 보증하는 간단한 메쉬를 생성하지만, 그러한 보장은 입체 메쉬에 드물며, 많은 인기 있는 구현은 일부 입력에서 반전(내부) 16진수를 생성한다.

메쉬는 종종 워크스테이션에서 직렬로 만들어지는데, 심지어 메쉬를 통한 후속 계산이 슈퍼컴퓨터에서 병렬로 수행될 때에도 그러하다. 이는 대부분의 메쉬 생성기가 대화형이라는 한계와 일반적으로 해결사 시간에 비해 메쉬 생성 런타임이 미미하기 때문이다. 단, 메쉬가 너무 커서 단일 시리얼 머신의 메모리에 맞지 않거나, 시뮬레이션 중에 메쉬를 교체(첨부)해야 하는 경우에는 메싱이 병렬로 이루어진다.

세포 위상

보통 세포는 다변형 또는 다면형이며 도메인을 분할하는 망사를 형성한다. 2차원 원소의 중요한 등급은 삼각형(단순형)과 4차원(상상 사각형)을 포함한다. 3차원에서는 가장 일반적인 세포가 4면체(단순체)와 6면체(위상 정육면체)이다. 단순화된 메시는 어떤 차원일 수 있으며 중요한 경우로서 삼각형(2D)과 사방형(3D)을 포함한다. 입체 메쉬는 쿼드(2D)와 16진(3D)을 포함하는 범차원 범주다. 3D에서는 4면 피라미드와 3면 프리즘이 혼합 세포 유형의 순응 메쉬로 나타난다.

세포 치수

그물망(mesh)은 전형적으로 2차원이나 3차원 기하학적 공간에 박혀 있는데, 때로는 시간차원(time-dimension)을 더하여 치수가 1차원씩 증가하는 경우도 있다. 더 높은 차원의 메쉬가 틈새 환경에 사용된다. 1차원 메쉬도 유용하다. 중요한 범주는 표면 메쉬로, 곡면을 나타내기 위해 3D에 내장된 2D 메쉬다.

이중성

이중 그래프는 메싱에 여러 가지 역할을 한다. 딜라우나이 삼각측량 단순 망사를 이원화하여 다면 보로노이 다이어그램 망사를 만들 수 있다. 표면 배열을 생성하고 교차 그래프를 이원화하여 입체 망사를 만들 수 있다. 공간 트위스트 연속체를 참조하라. 때로는 원초 메시와 이중 메시가 모두 동일한 시뮬레이션에 사용된다. Hodge star 연산자를 참조한다. 이것은 플럭스 & 복티시티 또는 전기 & 자력과 같은 발산 및 컬(수학) 연산자를 포함하는 물리학에서 발생한다. 여기에는 한 변수가 원시 면에 자연적으로 살고 그 반대 변수는 이중 면에 존재한다.

용도별 망사형

유한요소해석을 위해 만들어진 3차원 메시는 사면체, 피라미드, 프리즘 또는 육면체로 구성되어야 한다. 유한 체적 방법에 사용되는 것은 임의의 다면체로 구성될 수 있다. 유한 차이 방법에 사용되는 것은 다블록 구조화된 메쉬라고 알려진 육면체의 조각 구조화된 배열로 구성된다. 4면 피라미드는 쐐기와 일치하게 연결하는데 유용하다. 3면 프리즘은 물체의 원내부의 테트 메쉬에 적합한 경계 층에 사용된다.

표면 메쉬는 물체의 표면이 빛을 반사하고(표면 아래 산란도 포함) 완전한 3D 메쉬가 필요하지 않은 컴퓨터 그래픽에서 유용하다. 표면 메쉬는 또한 자동차 제조의 판금이나 건축의 건물 외벽과 같은 얇은 물체를 모형화하는 데 사용된다. 높은 차원(예: 17)의 입체 메시는 천체물리학 및 끈 이론에서 흔히 볼 수 있다.

수학적 정의 및 변형

메쉬의 정확한 정의는 무엇인가? 모든 맥락에서 적용되는 보편적으로 받아들여지는 수학적 설명은 없다. 그러나 일부 수학적인 물체는 분명히 메쉬다: 단순화된 콤플렉스는 단순함으로 구성된 메쉬다. 대부분의 다면체(예: 입체) 메시는 순응적인 것으로, 단순화 콤플렉스의 일반화인 CW 콤플렉스의 세포 구조를 가지고 있다는 것을 의미한다. 메쉬는 셀의 임의적인 부분집합이 반드시 셀이 아니기 때문에 단순할 필요는 없다. 예를 들어, 쿼드의 세 개의 노드가 셀을 정의하지 않는다. 그러나 두 개의 셀이 셀에서 교차한다: 예를 들어 쿼드는 내부에 노드가 없다. 두 셀의 교차점은 여러 셀일 수 있다. 예를 들어, 두 쿼드는 두 가장자리를 공유할 수 있다. 교차점이 둘 이상의 셀인 경우는 때때로 금지되고 거의 원하지 않는다. 일부 메쉬 개선 기법(예: 베개)의 목적은 이러한 구성을 제거하는 것이다. 어떤 맥락에서, 임베딩이 특정 품질 기준을 만족하는 위상 메시와 기하학적 메시를 구별한다.

CW 콤플렉스가 아닌 중요한 메쉬 변형에는 셀이 완전히 대면하여 충족되지 않는 비적합 메쉬가 포함되지만 그럼에도 불구하고 셀은 도메인을 분할한다. 이것의 예는 요소 면이 인접한 요소의 면에 의해 분할될 수 있는 8진법이다. 그러한 메시는 플럭스 기반 시뮬레이션에 유용하다. 오버셋 그리드에는 기하학적으로 겹치고 도메인을 분할하지 않는 여러 개의 정합성 메쉬가 있다. 예를 들어 오버플로우, OPERset 그리드 FLOW 해결기 등을 참조한다. 이른바 메쉬리스(meshless) 또는 메쉬프리스(meshfree) 방법이라고 하는 것은 도메인의 어떤 메쉬 같은 디스커트(discretation)를 이용하는 경우가 많으며, 중복 지원을 하는 기본 기능을 가지고 있다. 때때로 각 시뮬레이션 자유도 지점 근처에 국부 메쉬가 생성되며, 이러한 메쉬가 겹쳐서 서로 호환되지 않을 수 있다.

암묵적 삼각형은 삼각주 콤플렉스에 기초한다: 각 삼각형의 가장자리 길이와 면 가장자리 사이의 접착 맵. (확대하십시오)

고차원소

많은 메시는 선형 요소를 사용하는데, 여기서 추상적인 요소에서 실현된 요소로의 매핑은 선형이고, 메쉬 가장자리는 직선 세그먼트다. 고차 다항식 매핑이 일반적이며, 특히 2차 매핑이 일반적이다. 고차 요소의 일차적인 목표는 메쉬 내부에서도 정확도 이점이 있지만 도메인 경계를 보다 정확하게 표현하는 것이다. 입체 메쉬에 대한 동기 중 하나는 선형 입체 원소들이 2차 단순화 원소들과 동일한 수치적 이점을 가지고 있다는 것이다. 등기하 분석 시뮬레이션 기법에서 도메인 경계를 포함하는 메쉬 셀은 선형 또는 다항식 근사 대신 CAD 표현을 직접 사용한다.

메쉬 개선

참고 항목: 딜라우나이 정제

망사 개선에는 이산 연결성, 세포의 연속 기하학적 위치 또는 둘 다의 변경이 포함된다. 이산형 변경의 경우 단순 요소의 경우 가장자리를 교환하고 노드를 삽입/제거한다. 가능한 수술은 적고 국지적인 변화가 전지구적인 결과를 가져오지만 입체(쿼드/헥스) 메시에 대해서도 동일한 종류의 수술이 이루어진다. 예를 들어, 육각 망사의 경우, 두 개의 노드를 병합하면 16진수가 아닌 셀이 생성되지만, 4각형의 대각선 반대쪽 노드가 병합되어 이것이 얼굴 연결 열인 16진수를 모두 붕괴시키는 것으로 전파된다면, 나머지 모든 셀은 여전히 16진수가 된다. 적응형 메쉬 정교화에서는 계산되는 함수의 구배가 높은 영역에서 요소를 분할(h-refinement)한다. 메쉬도 응고되어 효율을 위한 요소를 제거한다. 멀티그리드 방식은 수치해결 속도를 높이기 위해 정교하고 조여지는 것과 비슷한 일을 하지만 메쉬를 실제로 바꾸지 않는다.

연속적인 변경의 경우, 노드가 이동하거나, 요소의 다항식 순서를 변경하여 고차원 면을 이동시킨다. 품질을 향상시키기 위해 노드를 이동하는 것을 "스무팅" 또는 "r-refine"이라고 하며 요소의 순서를 증가시키는 것을 "p-refine"이라고 한다. 노드는 또한 시간이 지남에 따라 물체의 모양이 변하는 시뮬레이션에서 이동된다. 이것은 원소의 모양을 떨어뜨린다. 물체가 충분히 변형되면 전체 물체가 리메싱되고 기존 그물망에서 새 그물망으로 현재 용액이 매핑된다.

연구 공동체

실무자

이 분야는 수학, 컴퓨터 공학, 공학 분야에서 기여도가 발견될 정도로 학제간 융합성이 높다. Meshing R&D는 계산 기하학에서와 마찬가지로 이산 및 연속 산술과 연산에 대한 동일한 초점에 의해 구별되지만, 그래프 이론(구체적)과 수치 분석(연속적)과는 대조적이다. 메쉬 생성은 개념적으로 어렵다: 인간은 주어진 물체의 메쉬를 만드는 방법을 보는 것은 쉽지만, 임의의 입력에 대해 좋은 결정을 내리도록 컴퓨터를 프로그래밍하는 것은 선험적으로 어렵다. 자연과 인간이 만든 물체에서 발견되는 기하학의 다양성은 무한히 다양하다. 많은 메쉬 세대 연구자들은 메쉬의 첫번째 사용자였다. 메쉬 세대는 메쉬를 만드는 인간 시간이 메쉬가 완성되면 설정과 계산을 해결하는 시간을 왜소하기 때문에 계속해서 광범위한 관심과 지원, 자금을 받고 있다. 컴퓨터 하드웨어와 간단한 방정식 해결 소프트웨어가 개선되면서 사람들은 더 큰 충실도, 과학적 통찰력, 예술적 표현을 위해 더 크고 복잡한 기하학적 모델에 끌리게 되었기 때문에 이것은 수치 시뮬레이션과 컴퓨터 그래픽이 발명된 이후 항상 있는 상황이었다.

저널스

메싱 연구는 광범위한 학술지에 게재된다. 이는 진척되기 위해 필요한 연구의 학제간 특성 및 메쉬를 사용하는 다양한 응용 분야와도 일치한다. 매년 약 150개의 메싱 출판물이 20개의 저널에 걸쳐 등장하며, 어떤 저널에도 최대 20개의 출판물이 나타난다. 주요 주제가 메싱인 저널은 없다. 매년 최소 10편의 메싱 논문을 발표하는 저널은 대담하다.

컨퍼런스

(메싱이 주요 주제인 콘퍼런스는 굵게 표시됨)

워크샵

주요 주제가 메싱인 워크샵은 대담하다.

  • 지오메트리 컨퍼런스: 이론 및 응용 프로그램 CGTA
  • EuroCG 연산지오메트리에 관한 연구
  • 가을철 전산기하학 워크숍
  • 유체 FEF의 유한요소
  • MeshTrends 심포지엄(WCCM 또는 USNCCM 격년)
  • 수학과 공학의 다상요소법
  • 사면체 작업장

참고 항목

참조

  • Edelsbrunner, Herbert (2001), "Geometry and Topology for Mesh Generation", Applied Mechanics Reviews, Cambridge University Press, 55 (1): B1–B2, Bibcode:2002ApMRv..55B...1E, doi:10.1115/1.1445302, ISBN 978-0-521-79309-4.
  • Frey, Pascal Jean; George, Paul-Louis (2000), Mesh Generation: Application to Finite Elements, Hermes Science, ISBN 978-1-903398-00-5.
  • P. Smith and S. S. Sritharan (1988), "Theory of Harmonic Grid Generation" (PDF), Complex Variables, 10 (4): 359–369, doi:10.1080/17476938808814314
  • S. S. Sritharan (1992), "Theory of Harmonic Grid Generation-II", Applicable Analysis, 44 (1): 127–149, doi:10.1080/00036819208840072
  • Thompson, J. F.; Warsi, Z. U. A.; Mastin, C. W. (1985), Numerical Grid Generation: Foundations and Applications, North-Holland, Elsevier.
  • CGAL 전산지오메트리
  • Oden, J.Tinsley; Cho, J.R. (1996), "Adaptive hpq-Finite Element Methods of Hierarchical Models for Plate- and Shell-like Structures", Computer Methods in Applied Mechanics and Engineering, 136 (3): 317–345, Bibcode:1996CMAME.136..317O, doi:10.1016/0045-7825(95)00986-8
  • Steven J. Owen (1998), A Survey of Unstructured Mesh Generation Technology, International Meshing Roundtable, pp. 239–267, S2CID 2675840
  • Shimada, Kenji; Gossard, David C. (1995). Bubble Mesh: Automated Triangular Meshing of Non-Manifold Geometry by Sphere Packing. ACM Symposium on Solid Modeling and Applications, SMA. ACM. pp. 409-419. doi:10.1145/218013.218095. ISBN 0-89791-672-7. S2CID 1282987.

외부 링크

메쉬 생성기

많은 상용 제품 설명은 시뮬레이션을 가능하게 하는 메싱 기술보다는 시뮬레이션을 강조한다.

다중 도메인 분할 메시 생성기

이러한 도구는 복합 재료 유한 요소 모델링에 필요한 분할된 메쉬를 생성한다.

  • MDM(Multiple Domain Meshing)은 이질적인 물질로 구성된 복합 영역에 대해 구조화되지 않은 사면 및 육면 메쉬를 자동으로, 그리고 효율적으로 생성한다.
  • QMDM(Quality Multi-Domain Meshing)은 여러 도메인에 대해 고품질, 상호 일관적인 삼각형 표면 매쉬를 생산한다.
  • QMDMNG(Quality Multi-Domain Meshing with No Gap)는 각각 2차원 다지관과 인접한 두 메스 사이의 간극이 없는 품질 매쉬를 생산한다.
  • SOFA_mesh_partitioning_tools는 CGAL을 기반으로 복합 재료 FEM에 대해 분할된 사면 메쉬를 생성한다.
기사들
연구 그룹 및 사람
모델 및 메쉬

메싱 알고리즘과 메쉬를 비교하기 위한 유용한 모델(입력)과 메쉬(출력)

CAD 모델

도메인 지오메트리를 나타내는 메쉬 생성 소프트웨어와 연결된 모델링 엔진.

메쉬 파일 형식

메쉬를 설명하기 위한 공통(출력) 파일 형식.

메쉬 시각화기
자습서