메쉬 생성: 컴퓨터 비전 메시 생성의 발전과 응용

By Fouad Sabry

메시 생성이란 무엇입니까

메시 생성은 연속적인 기하학적 공간을 별개의 기하학적 및 토폴로지 셀로 세분화하는 메쉬를 만드는 방법입니다.종종 이러한 셀은 단순 복합체. 일반적으로 셀은 기하학적 입력 영역을 분할합니다. 메쉬 셀은 더 큰 영역의 개별 로컬 근사치로 사용됩니다. 메시는 도메인의 복잡성과 원하는 메시 유형에 따라 종종 GUI를 통한 인간의 안내에 따라 컴퓨터 알고리즘에 의해 생성됩니다. 일반적인 목표는 고품질( 모양이 잘 잡힌) 셀이며, 후속 계산을 다루기 어려울 정도로 셀이 너무 많지 않습니다. 메쉬는 후속 계산에 중요한 영역에서도 괜찮아야 합니다.

혜택을 받는 방법

(I) 다음 주제에 대한 통찰력 및 검증:

1장: 메시 생성

2장: 유한 요소 방법

3장: 편미분 방정식

4장: 전산유체역학

5장: 편미분 방정식의 수치적 방법

6장: 타원 부분 미분 방정식

7장: 유한 차분법

8장: 수치 연속

9장: 유한 체적법

10장: 아이소지오메트릭 분석

(II) 메쉬 생성에 관한 대중의 주요 질문에 답합니다.

(III) 다양한 분야에서 메쉬 생성 사용에 대한 실제 사례.

이 책은 누구를 위한 책인가요?

전문가, 학부 및 대학원생, 매니아, 취미생활자, 모든 종류의 메시 세대를 위한 기본 지식이나 정보를 넘어서고 싶은 사람들.

 

 

• Language: 한국어
• Publisher: 10 억 지식이 걸립니다 [Korean]
• Release date: May 4, 2024

Book preview

1 장 : 메시 생성

메쉬 생성은 연속적인 기하학적 공간을 별개의 기하학적 셀과 위상 셀로 나누어 메쉬를 형성하는 과정입니다. 종종, 단순 복합체는 이러한 세포에 의해 형성됩니다. 일반적으로 셀은 입력 기하학적 영역을 나눕니다. 더 넓은 영역의 이산 국소 근사치로 메쉬 셀이 사용됩니다. 도메인의 복잡성과 원하는 메시의 종류에 따라 메시는 컴퓨터 알고리즘에 의해 생성되며, 종종 GUI를 통해 사람의 도움을 받습니다. 일반적인 목표는 입력 도메인 지오메트리를 정확하게 나타내고, 고품질(모양이 좋은) 셀을 포함하며, 향후 계산을 관리할 수 없을 정도로 지나치게 조밀하지 않은 메시를 생성하는 것입니다. 또한 메시는 후속 계산에 중요한 영역에서 미세해야 합니다(작은 구성 요소 포함).

메시는 전산 유체 역학 및 컴퓨터 화면 렌더링과 같은 프로그램에서 물리적 시뮬레이션에 사용됩니다. 메시는 삼각형과 같은 기본 빌딩 블록으로 만들어지는데, 예를 들어 삼각형에 대해서는 유한 요소 계산(엔지니어링용)이나 레이 트레이싱(컴퓨터 그래픽용)을 수행할 수 있지만 도로 위의 다리와 같은 더 복잡한 형태와 장소에서는 수행할 수 없기 때문입니다. 각 삼각형에 대한 계산을 완료하고 삼각형 간의 상호 작용이 어떻게 상호 작용하는지 파악하여 다리의 강도를 모델링하거나 컴퓨터 화면에 묘사할 수 있습니다.

조직화된 메싱과 구조화되지 않은 메싱의 차이는 상당합니다. 배열과 같은 일반 격자는 요소 간의 연결성이 유추된 구조화된 메싱에 사용됩니다. 구조화되지 않은 메싱을 사용하면 더 복잡한 도메인을 캡처할 수 있으며 부품 간의 불규칙한 연결 패턴이 발생할 수 있습니다. 이 페이지의 주요 주제는 구조화되지 않은 메시입니다. 메시를 삼각 측량할 수 있지만, 메시는 입력에 포함되지 않은 꼭짓점을 추가할 수 있다는 점에서 점 집합 삼각 측량과 다릅니다. 제도 작업을 위해 CAD 모델을 패싯(삼각 측량)할 때도 정점을 추가할 수 있는 동일한 자유가 존재하지만, 목표는 가능한 한 가장 적은 수의 삼각형으로 모양을 정확하게 묘사하는 것입니다. 개별 삼각형의 모양은 중요하지 않습니다. 메시는 사실적인 조명 상황을 컴퓨터 그래픽으로 묘사하기 위해 텍스처 대신 사용됩니다.

많은 메쉬 생성 프로그램은 입력을 정의하는 CAD 시스템과 출력을 수신하는 시뮬레이션 프로그램에 연결됩니다. 입력은 다양한 형태를 취할 수 있지만 일반적인 형태에는 포인트 클라우드, 솔리드 모델링, 기하학적 모델링, NURBS 및 B-rep이 포함됩니다.

메쉬 생성, 그리드 생성, 메싱 및 그리딩이라는 용어는 종종 같은 의미로 사용되지만, 기술적으로 후자의 두 용어는 메쉬에 대해 실행될 수치 계산의 속도를 높이거나 향상시키기 위해 메쉬를 변경하는 프로세스인 메쉬 개선을 다룹니다. 때때로, 메시는 수학과 컴퓨터 그래픽 렌더링 모두에서 테셀레이션이라고 합니다.

치수와 메쉬가 활용될 컨텍스트에 따라 메쉬 면(셀, 개체)에는 여러 이름이 있습니다. 유한 요소에서 가장 높은 차원의 메시 엔터티를 요소라고 하며, 가장자리는 1D이고 노드는 0D입니다. 요소가 3D인 경우 2D 엔터티는 면입니다. 꼭짓점은 계산 기하학의 0D 점입니다. 사면체는 때때로 tets라고 불리는 반면 삼각형, 사변형 및 육면체(위상 큐브)는 각각 tris, quads 및 hex라고 합니다.

Ruppert의 방법 및 Delaunay 삼각분할과 같은 많은 꼭짓점 추가 규칙은 여러 메싱 접근 방식의 기초입니다. 한 가지 독특한 특징은 전체 공간의 거친 초기 메시가 생성된 후 정점과 삼각형이 추가된다는 것입니다. 이에 비해, 전진 정면 알고리즘은 경계를 시작으로 영역의 내부에 요소를 점진적으로 도입합니다. 하이브리드 방법은 두 가지를 결합합니다. 유체 흐름을 위한 요소의 얇은 경계층은 고유한 등급의 전진 선단 절차를 사용하여 생성됩니다. 구조화된 메시 생성에 의해 생성된 전체 메시는 정사각형의 일반 그리드와 같은 격자 그래프입니다. 도메인은 크기가 큰 하위 영역으로 분할되며, 각 하위 영역은 블록 구조 메싱에서 구조화된 메쉬입니다. 일부 직접적인 접근 방식은 블록 구조의 메시로 시작한 다음 입력에 맞게 조정합니다. 자세한 내용은 Automatic Hex-Mesh Generation based on Polycube 항목을 참조하십시오. 추가적인 직접적인 방법으로 도메인 경계로 조직된 셀을 자릅니다. Marching cube sculpture를 참조하십시오.

일부 메쉬 유형은 다른 유형보다 만들기가 훨씬 더 어렵습니다. 입방체 메쉬와 비교할 때 단순 메쉬는 일반적으로 더 간단합니다. 고정된 쿼드 표면 메쉬를 준수하는 육각 메쉬를 생성하는 것은 중요한 범주이며, 정방형 사다리꼴과 같은 특정 작은 구성을 가진 메쉬의 존재 및 생성을 연구하는 것은 연구 하위 영역입니다. 조합 육각 메쉬의 존재는 이 주제의 어려움으로 인해 고품질 기하학적 구현을 생성하는 문제와 별도로 조사되었습니다. 알려진 알고리즘은 최소한의 품질 보증으로 간단한 메시를 생성하지만 동일한 보증을 갖는 입방체 메시는 거의 없으며 널리 사용되는 많은 구현은 일부 입력에서 반전된(내부-외부) 헥스를 생성합니다.

메시에 대한 후속 계산이 슈퍼컴퓨터에서 병렬로 수행되더라도 메시는 워크스테이션에서 직렬로 생성되는 경우가 많습니다. 이는 대부분의 메시 생성기가 대화형이라는 단점과 메시 생성 기간이 솔버 시간에 비해 무시할 수 있는 경우가 많다는 사실 때문입니다. 그러나 메쉬가 너무 커서 단일 직렬 프로세서의 메모리에 맞지 않거나 시뮬레이션 전체에서 수정(조정)해야 하는 경우 메싱이 병렬로 수행됩니다.

수학적 보간 함수는 대수학에서 사용되는 그리드 생성 프로세스의 기초 역할을 합니다.

잘 알려진 기능을 하나로 활용하고, 다양한 모양의 단면을 2차원 또는 3차원으로 사용합니다.

컴퓨팅 도메인이 정사각형이 아닐 수도 있지만 단순하게 유지하기 위해 도메인이 직사각형이라고 가정합니다.

이 접근 방식의 주요 이점은 물리적 그리드의 모양과 간격을 명시적으로 조절한다는 것입니다.

정규화 변환은 경계에 맞는 계산 메시를 만드는 데 사용할 수 있는 가장 간단한 방법입니다. 노즐을 사용하기 위해, 설명 기능을 사용하면 y=x^{2} x 방향에서 균등한 간격의 증분으로 y 방향으로 균일 한 분할을 사용하여 그리드를 쉽게 생성 할 수 있으며,

\xi =x\,\eta ={\frac {y}{y_{\max }}}\,

여기서 y_{\max } 는 노즐 벽의 Y 좌표를 나타냅니다.

주어진 ( \xi , \eta ) 값에 대해 ( x , y ) 값을 쉽게 복구할 수 있습니다.

미분 방정식을 기반으로 하는 그리드 생성 기술은 수학에서 사용되는 기술과 유사합니다. 편미분 방정식(PDE)을 사용하면 그리드 생성 방정식의 해를 활용하여 메시를 생성할 수 있다는 이점이 있습니다. 세 종류의 편미분 방정식을 모두 사용하여 그리드를 만들 수 있습니다.

타원 편미분방정식의 해는 일반적으로 매우 매끄러워서 매끄러운 윤곽을 만듭니다.

이점으로 부드러움 극대화 야코비 행렬은 조화 함수에 대한 최대 원리의 결과로 양수로 밝혀졌으므로 라플라스 방정식을 사용하는 것이 좋습니다.

그리드를 생성하기 위해 타원 편미분방정식에 대한 상당한 작업을 수행한 후 Crowley(1962)와 Winslow(1966)에 의해 수행되었습니다.

푸아송 그리드가 있는 생성기에서 매핑은 물리적 영역의 경계에 원하는 그리드 점을 표시하여 수행 (x,y) 되며, 내부 포인트 분포는 다음 방정식을 풀어서 결정됩니다

\xi _{{xx}}+\xi _{{yy}}=P(\xi ,\eta )\eta _{{xx}}+\eta _{{yy}}=Q(\xi ,\eta )

여기서 (\xi,\eta) 는 계산 영역의 좌표이고, P와 Q는 D 내부의 점 간격을 제어합니다.

계산 공간에서 앞서 언급한 방정식을 변경하면 다음과 같은 형식의 타원 편미분방정식 쌍이 생성됩니다.

\alpha x_{{\xi \xi }}-2\beta x_{{\xi \eta }}+\gamma x_{{\eta \eta }}=-I^{2}(Px_{\xi }+Qx_{\eta })\alpha y_{{\xi \xi }}-2\beta y_{{\xi \eta }}+\gamma y_{{\eta \eta }}=-I^{2}(Py_{\xi }+Qy_{\eta })

어디

{\displaystyle {\begin{aligned}\alpha &=x_{\eta }^{2}+y_{\eta }^{2}\\\beta &=x_{\eta }x_{\xi }+y_{\xi }y_{\eta }\\\gamma &=x_{\xi }^{2}+y_{\xi }^{2}\\I&={\frac {\delta (x,y)}{\delta (\xi ,\eta )}}=y_{\eta }x_{\xi }-y_{\xi }x_{\eta }\end{aligned}}}

이러한 방정식 시스템은 물리적 공간의 각 점의 좌표 (x,y) 를 제공하는 균일한 간격의 그리드의 계산 평면에서 해결 됩니다.

타원 PDE를 사용하면 타원 PDE와 연결된 해와 생성된 그리드가 모두 매끄럽다는 장점이 있습니다.

그러나 P와 Q를 지정하는 것은 어려운 작업이되어 단점이 증가합니다.

또한 각 시간 단계에는 그리드를