지오메트리 처리

Mario Botsch 등의 폴리곤 메쉬 가공은 지오메트리 ^[1]가공의 주제에 관한 교과서입니다.

기하학 처리(mesh processing)는 응용 수학, 컴퓨터 과학 및 엔지니어링의 개념을 사용하여 복잡한 3D 모델의 획득, 재구성, 분석, 조작, 시뮬레이션 및 전송을 위한 효율적인 알고리즘을 설계하는 연구 영역입니다.이름에서 알 수 있듯이 많은 개념, 데이터 구조 및 알고리즘은 신호 처리 및 이미지 처리와 직접 유사합니다.예를 들어, 이미지 평활이 라플라스 연산자를 사용하여 형성된 블러 커널로 강도 신호를 합성할 수 있는 경우, 기하학적 평활은 라플라스-벨트라미 연산자를 사용하여 형성된 블러 커널로 표면 형상을 합성함으로써 달성될 수 있다.

지오메트리 처리 알고리즘의 응용 분야는 멀티미디어, 엔터테인먼트 및 클래식 컴퓨터 지원 설계에서 생물의학 컴퓨팅, 리버스 엔지니어링 및 과학 ^[1]컴퓨팅에 이르기까지 이미 광범위합니다.

지오메트리 프로세싱은 SIGGRAPH의 공통 연구 주제이며, 최초의 컴퓨터 그래픽 학술 회의이며, 매년 열리는 지오메트리 프로세싱 심포지엄의 주요 주제입니다.

라이프 사이클로서의 지오메트리 처리

각도결함법을 이용하여 각 정점의 가우스 곡률을 나타내는 선인장의 메쉬.

지오메트리 처리에는 쉐이프가 임의의 치수의 공간에 존재할 수 있지만 일반적으로 2D 또는 3D로 작업하는 것이 포함됩니다.형상의 과정은 라이프 사이클이라고 알려진 세 단계를 포함한다."태어날 때" 모양은 모형, 수학적 표현 또는 스캔의 세 가지 방법 중 하나를 통해 인스턴스화할 수 있습니다.형상이 탄생한 후에는 주기적으로 반복적으로 분석 및 편집할 수 있습니다.이것은 보통 형상의 점들 사이의 거리, 형상의 부드러움 또는 오일러 특성과 같은 다른 측정치를 획득하는 것을 포함합니다.편집에는 노이즈 제거, 변형 또는 견고한 변환 수행이 수반될 수 있습니다.형상의 "수명"의 마지막 단계에서, 그것은 소비된다.이는 예를 들어 시청자가 게임이나 동영상에서 렌더링된 자산으로 소비한다는 것을 의미합니다.형상의 수명 끝은 형상에 대한 결정에 의해 정의될 수도 있습니다. 예를 들어 형상이 어떤 기준을 충족하는지 여부입니다.또는 3D 프린팅이나 레이저 커팅과 같은 방법으로 실제 세계에서 제작할 수도 있습니다.

도형의 이산 표현

다른 모양과 마찬가지로 지오메트리 처리에 사용되는 모양에는 지오메트리 및 토폴로지와 관련된 특성이 있습니다.쉐이프의 지오메트리는 공간, 접선, 법선 및 곡면에서의 쉐이프 점의 위치와 관련이 있습니다.또한 형상이 존재하는 치수( $R^{2}$ : $R^{2}$ 2 $(\$ R $^{2})$ $R^{3}$ R $R^{3}$ (\ $displaystyle$ R $^{3}))$ 도 포함됩니다.셰이프의 토폴로지는 셰이프에 부드러운 변환이 적용된 후에도 변경되지 않는 속성 모음입니다.이는 형상의 방향성뿐만 아니라 구멍의 수와 경계와 같은 치수와 관련이 있습니다.방향을 잡을 수 없는 형상의 한 예는 뫼비우스 띠입니다.

컴퓨터에서는 모든 것을 분리해야 한다.지오메트리 처리에서 쉐이프는 보통 삼각형 메시로 표현되며, 이는 그래프로 볼 수 있습니다.그래프의 각 노드는 정점(일반적으로 R $(\$ R $^{3}})$ 으로, 위치가 있습니다.셰이프의 형상을 인코딩합니다.방향 모서리는 이러한 정점을 삼각형으로 연결하고, 이 삼각형은 오른쪽 규칙에 따라 정규선이라는 방향을 가집니다.각 삼각형은 망사의 면을 형성합니다.이들은 본질적으로 조합적이며 형상의 토폴로지를 인코딩합니다.삼각형 외에 더 일반적인 폴리곤 메쉬 클래스를 사용하여 모양을 나타낼 수도 있습니다.프로그레시브 메쉬와 같은 보다 고도의 표현은 일련의 변환과 함께 거친 표현을 부호화합니다.이러한 표현은 일단 적용된 형상의 미세 또는 고해상도 표현을 생성합니다.이러한 메시는 지오모형, 프로그레시브 전송, 메시 압축 및 선택적 ^[2]미세화 등 다양한 애플리케이션에서 유용합니다.

유명한 스탠포드 토끼의 망사입니다.쉐이프는 보통 쉐이프의 윤곽을 나타내는 폴리곤 집합인 메시로 표시됩니다.

도형의 속성

오일러 특성

3D 형상의 특히 중요한 특성 중 하나는 오일러의 특성으로, 오일러의 속성에 따라 다르게 정의할 수 있습니다.연속적인 의미의 공식은 $\chi =2c-2h-b$ $\chi =2c-2h-b$ $\chi =2c-2h-b$ - $\chi =2c-2h-b$ - $\chi =2c-2h-b$ $(\$ $displaystyle$ \ $chi$ = $\chi =2c-2h-b$ 2 c - $\chi =2c-2h-b$ b $\chi =2c-2h-b$ )입니다. $c$ 서c { $displaystyle$ c}는 $c$ 연결부품의 수,h { $displaystyle$ h $}$ 는 $h$ 구멍의 수(도넛 구멍, torus 참조), $b$ { $displaystyle$ b}는 $b$ 경계 연결부품의 수표면.그 구체적인 예가 바지 망사입니다.경계에는 1개의 연결된 컴포넌트, 0개의 구멍 및 3개의 연결된 컴포넌트(허리와 2개의 다리 구멍)가 있습니다.따라서 이 경우 오일러 특성은 -1입니다.이를 이산 세계에 도입하기 위해 메시의 오일러 특성은 정점, 가장자리 및 면의 관점에서 계산됩니다. $\chi =|V|-|E|+|F|$ = $\chi =|V|-|E|+|F|$ - $E$ + $F {\displaystyle$ \chi = $V -$ E + F $\chi =|V|-|E|+|F|$ }.

이 이미지는 오일러 특성 -1을 가진 바지 한 벌의 망사를 보여줍니다.이것은 2c - 2h - b의 특성을 계산하는 방정식으로 설명됩니다.메시에는 연결된 구성 요소 1개, 위상 구멍 0개 및 경계(허리 구멍과 각 다리 구멍) 3개(2 - 0 - 3 = - 1)가 있습니다.

표면 재구성

표면점에서 망사까지의 포아송 재구성

삼각형 메시는 점 구름으로 구성됩니다.도형이 도형 표면의 샘플링된 점 집합인 "점 구름"으로만 초기화되는 경우도 있습니다.종종 이러한 점 구름을 메시로 변환해야 합니다.

형상이 초기화되거나 "생성"되는 방법에 따라 형상은 우주에서 표면을 나타내는 표본 추출된 점의 성운으로만 존재할 수 있습니다.표면 점을 망사로 변환하기 위해 포아송 재구성^[3] 전략을 사용할 수 있습니다.이 방법은 공간의 어떤 점이 형상의 표면에 속하는지 결정하는 함수인 지시 함수를 실제로 표본 추출된 점으로부터 계산할 수 있음을 나타냅니다.핵심 개념은 지표 함수의 기울기가 내부 표면 법선과 동일한 표본 추출 지점을 제외하고 모든 위치에서 0이라는 것이다.좀 더 형식적으로 지표면에서 샘플링된 점의 컬렉션을 S $(\displaystyle$ S $S$ 로 $나타내고$ 공간 내의 각 $p_{i}$ 을 $pi$ (\ $displaystyle p_$ i})로 나타내며, 대응하는 $n_{i}$ 을 $n_{i}$ (\ $displaystyle n_$ i})로 나타냅니다.그런 다음 표시기 함수의 구배를 다음과 같이 정의합니다.

$\displaystyle \ledown g=case{case}{\textbf {n}_{i},\forall p_{i}\in S\0,\text{othery}}\end{case}}}$

그러면 재구성 작업이 변동적인 문제가 됩니다.지표의 인디케이터 함수를 구하려면 $\lVert \triangledown \chi -{\textbf {V}}\rVert$ ▽ $\lVert \triangledown \chi -{\textbf {V}}\rVert$ - V ${\$ \ $displaystyle$ \ $lVert$ \ $sledown \ chi$ - { \ $textbf$ { $V$ } \ $rVert }$ 이 $\chi$ $\lVert \triangledown \chi -{\textbf {V}}\rVert$ ( $)$ $\chi$ 되도록 $함수 {\$ { \ $displaystyle$ \ $textbf$ { V $}$ $\chi$ }을 ${\textbf {V}}$ (를) 찾아야 합니다.변분 문제로서 미니마이저 $\chi$ {\(\ $displaystyle \chi)$ 를 $\chi$ 푸아송 ^[3]방정식의 해로 볼 수 있다. ${\$ { $displaystyle$ $\chi$ } $\chi$ $\sigma$ $\chi (x,y,z)=\sigma$ $\sigma$ $\chi (x,y,z)=\sigma$ ( $(x,y,z)$ （ $\chi (x,y,z)=\sigma$ $(x,y,z)$ , $(x,y,z)$ , $\chi (x,y,z)=\sigma$ $）$ $\chi (x,y,z)=\sigma$ {\ { $displaystyle$ $\chi (x,y,z)=\sigma$ \chi ( $(x,y,z)$ $\chi (x,y,z)=\sigma$ , $y$ , z ) = $display$ { $displaystyle$ \ $chi ( x$ , y , z ) $\chi (x,y,z)=\sigma$ } $(x,y,z)$ on $(x,y,z)$ on on on on on on on on on on on on on on on on on on on $(x,y,z)$ on on on on on on on on on on on on $\sigma$ on on on t 함수 ${\(\style\chi)$ 의 삼각형 메쉬를 사용하여 후속 컴퓨터 그래픽 응용 프로그램에 적용할 수 있습니다.

등록.

부분 메쉬를 완전한 메쉬에 등록하고 투영 함수의 부분적인 일정한 근사치를 가지는 애니메이션.

위와 동일하지만 투영 함수의 선형 근사치가 있는 등록 절차를 그린 애니메이션입니다.컨버전스 속도가 훨씬 빠릅니다.

지오메트리 처리에서 흔히 볼 수 있는 문제 중 하나는 서로 다른 각도 또는 위치에서 캡처된 단일 개체의 여러 뷰를 병합하는 방법입니다.이 문제를 등록이라고 합니다.등록 시 $X$ 와 $Y$ 를 정렬하는 최적의 강성 변환을 찾고자 합니다. 보다 형식적으로 $P_{Y}(x)$ Y $x)$ { $displaystyle$ $P_{Y}(x$ $Y$ 가 표면X에서 $Y(\displaystyle$ X $X$ $Y$ $Y$ 으로 투영된 점이라면 $P_{Y}(x)$ 과 같이 해야 합니다.다음과 같은 목적 함수를 최소화하는 최적의 회전 $행렬$ R(\ $displaystyle$ R $)$ 과 $R$ 변환 $벡터$ t(\ $displaystyle$ t $)$ 를 $t$ 구한다.

$\displaystyle \int _{x\in X} Rx+t-P_{Y}(x) dx}$

일반적으로 회전은 비선형이지만 작은 회전은 스큐-대칭 행렬로 선형화할 수 있습니다.또한 $x-P_{Y}(x)$ - $x-P_{Y}(x)$ Y $x-P_{Y}(x)$ ( $x-P_{Y}(x)$ ) { $displaystyle x-P_{Y}(x)}$ 는 $x-P_{Y}(x)$ 비선형이나 X{ $displaystyle$ X $}$ 의 $X$ 변화가 작을 경우 선형 근사에 적합하다.따라서 반복적 근접점(ICP)과 같은 반복적 솔루션을 사용하여 잠재적으로 큰 변환에 대해 한 번에 해결하는 것이 아니라 작은 변환에 대해 반복적으로 해결합니다.ICP에서는 X $(\displaystyle$ X $)$ 에서 $X$ n개의 랜덤 샘플 포인트가 선택되어 Y $(\displaystyle$ Y $Y$ 에 투영됩니다.삼각형 메쉬의 표면 전체에 걸쳐 랜덤으로 점들을 샘플링하기 위해 랜덤 샘플링은 삼각형 내에서 균일한 샘플링 포인트와 불균일한 샘플링 삼각형의 두 단계로 분할됩니다.각 삼각형의 연관 확률은 표면적에 ^[4]비례합니다.그 후 각 $x와$ 그 투영값의 $x$ 차이에 따라 최적의 변환이 계산됩니다.다음 반복에서는 이전 변환을 표본에 적용한 결과에 따라 투영도가 계산됩니다.이 프로세스는 컨버전스가 될 때까지 반복됩니다.

스무딩

형상을 정의하거나 스캔할 때 표면에 작용하는 신호 또는 실제 표면 형상에 노이즈가 발생할 수 있습니다.전자의 노이즈 감소는 데이터 노이즈 제거라고 하며, 후자의 노이즈 감소는 표면 페어링이라고 합니다.기하학적 평활 작업은 신호 소음 감소와 유사하며, 결과적으로 유사한 접근방식을 사용한다.

최소화하는 해당 라그랑지안은 초기 ${\bar {f}}$ f ${\$ {\ $displaystyle {f}}$ 에 ${\bar {f}}$ 대한 적합성과 중량 ${\$ {\ $displaystyle \lambda$ 에 따른 구배 크기에 근사한 결과 신호의 부드러움을 기록함으로써 도출됩니다.

${\mathcal {L}}(f)=\int _{\Omega }\|f-{\bar {f}}\|^{2}+\lambda \|\nabla f\|^{2}dx$ ( ${\mathcal {L}}(f)=\int _{\Omega }\|f-{\bar {f}}\|^{2}+\lambda \|\nabla f\|^{2}dx$ ) ${\mathcal {L}}(f)=\int _{\Omega }\|f-{\bar {f}}\|^{2}+\lambda \|\nabla f\|^{2}dx$ ${\mathcal {L}}(f)=\int _{\Omega }\|f-{\bar {f}}\|^{2}+\lambda \|\nabla f\|^{2}dx$ ${\mathcal {L}}(f)=\int _{\Omega }\|f-{\bar {f}}\|^{2}+\lambda \|\nabla f\|^{2}dx$ - f ${\mathcal {L}}(f)=\int _{\Omega }\|f-{\bar {f}}\|^{2}+\lambda \|\nabla f\|^{2}dx$ 2 + ${\mathcal {L}}(f)=\int _{\Omega }\|f-{\bar {f}}\|^{2}+\lambda \|\nabla f\|^{2}dx$ f ${\mathcal {L}}(f)=\int _{\Omega }\|f-{\bar {f}}\|^{2}+\lambda \|\nabla f\|^{2}dx$ ${\mathcal {L}}(f)=\int _{\Omega }\|f-{\bar {f}}\|^{2}+\lambda \|\nabla f\|^{2}dx$ ${\mathcal {L}}(f)=\int _{\Omega }\|f-{\bar {f}}\|^{2}+\lambda \|\nabla f\|^{2}dx$ $x$ 2 d ${\mathcal {L}}(f)=\int _{\Omega }\|f-{\bar {f}}\|^{2}+\lambda \|\nabla f\|^{2}dx$ x \ displaystyle \ $mathcal$ { $L}$ （ f ) $=$ \int _ { \ $Omega }$ \ f - { $f$ - { $f }$ + \ $bar$ { f \ $la$ f \ { $}$ }

L $(\$ 에서 ${\mathcal {L}}$ 변형 $\delta f$ f $(\displaystyle\delta$ f $)$ 를 $\delta f$ 취하면 필요한 조건이 발생합니다.

$0=\delta {\mathcal {L}}(f)=\int _{\Omega }\delta f(\mathbf {I} +\lambda \nabla ^{2})f-\delta f{\bar {f}}dx$ $0=\delta {\mathcal {L}}(f)=\int _{\Omega }\delta f(\mathbf {I} +\lambda \nabla ^{2})f-\delta f{\bar {f}}dx$ $0=\delta {\mathcal {L}}(f)=\int _{\Omega }\delta f(\mathbf {I} +\lambda \nabla ^{2})f-\delta f{\bar {f}}dx$ L ( $0=\delta {\mathcal {L}}(f)=\int _{\Omega }\delta f(\mathbf {I} +\lambda \nabla ^{2})f-\delta f{\bar {f}}dx$ f ) $0=\delta {\mathcal {L}}(f)=\int _{\Omega }\delta f(\mathbf {I} +\lambda \nabla ^{2})f-\delta f{\bar {f}}dx$ ( I + $0=\delta {\mathcal {L}}(f)=\int _{\Omega }\delta f(\mathbf {I} +\lambda \nabla ^{2})f-\delta f{\bar {f}}dx$ ) $0=\delta {\mathcal {L}}(f)=\int _{\Omega }\delta f(\mathbf {I} +\lambda \nabla ^{2})f-\delta f{\bar {f}}dx$ - $0=\delta {\mathcal {L}}(f)=\int _{\Omega }\delta f(\mathbf {I} +\lambda \nabla ^{2})f-\delta f{\bar {f}}dx$ f $x$ d $0=\delta {\mathcal {L}}(f)=\int _{\Omega }\delta f(\mathbf {I} +\lambda \nabla ^{2})f-\delta f{\bar {f}}dx$ x \ $display$ 0 = \ $display$ { \ $mathcal$ { $L$ } = \ $int$ _ { \ $Omega$ } \ $display f($ \ $mathbf$ { I } + \ $la$ ^ $2$ . $f ) f$

이것을 우리가 얻은 정점에 있는 우리의 신호와 함께 조각적으로 일정한 요소들로 분해함으로써

${displaystyle} \sum _{i} \delta f_{i} &=\sum _{i} M_{i} \delta f_{i} \sum _{j} \delta f_{I} +\sum f_{i} \displayda f_i$

소음이 심한 구체가 반복적으로 평활됩니다.

여기서 $\nabla ^{2}$ $({$ ^{ $2}})$ 를 $\nabla ^{2}$ 코탄젠트 $\mathbf {L}$ L(\ $displaystyle \mathbf {L})$ 에 $\mathbf {L}$ 대해 $M^{-1}\mathbf {L}$ M - $M^{-1}\mathbf {L}$ L(\ $displaystyle$ M^-1}\ $mathbf {L})$ 로 $M^{-1}\mathbf {L}$ 선택하고 $M^{-1}$ $M^{-1}$ - $M^{-1}$ 1(\ $displaystyle M^{-$ $1$ $M^{-1}$ })을 랩 이미지에 대한 맵으로 선택합니다.변동은 자유롭기 때문에 ${\bar {f}}=(M+\lambda \mathbf {L} )f.$ $\lambda$ {\\ $displaystyle \lambda$ ${\bar {f}}=(M+\lambda \mathbf {L} )f.$ : f ${\bar {f}}=(M+\lambda \mathbf {L} )f.$ ${\bar {f}}=(M+\lambda \mathbf {L} )f.$ ( $M$ + $λ$ L ) ${\bar {f}}=(M+\lambda \mathbf {L} )f.$ . { $displaystyle { f$ } = ( M + \ $lambda$ \ $mathbf {L}$ ) f . laaclian ${\bar {f}}=(M+\lambda \mathbf {L} )f.$ } $l$ }}}}}}}}}} }}}}}}}}}}}}}}}}}}}}}}}}}} }}}}}}}}}}}}}}}}}}}}}}}}}}}}망사에 연결된 삼각형의 기하학적 구조를 분석하는 것입니다.

$(\displaystyle L_{ij}=begin{case}{\frac {1}{2}}(\cot(\alpha _{ij})+\cot(\displaystyle _{ij})))&{\text{edge ij exists}\-\sum \sum _{i\neq j}L_{ij}&i=j\0&{\text{그렇지 않으면}}\end{cases}}}$

$\alpha _{ij}$ 서 $\alpha _{ij}$ $\alpha _{ij}$ j \ $displaystyle \alpha$ _ ${ij}$ $\beta _{ij}$ $\beta _{ij}$ $\beta _{ij}$ j \ $displaystyle \beta$ _ ${ij}$ 는 $\beta _{ij}$ $(i,j)$ ^[5] $(i,j)$ 엣지( $(i,j)$ $(i,j)$ j $(i,j)$ ) { $displaystyle (i , j$ )} 연산자로서의 질량행렬 M은 함수 값의 로컬 적분을 계산하며 종종 다음과 같이 m개의 삼각형으로 설정됩니다.

$M_{ij}=casesbegin{cases}{\frac {1}{3}\sum _{t=1}^{m}{\cases}{\cases}}면적(t)&{\text{삼각형 t에 꼭지점 i}\0&{\text{cases}\end{cases}}&{\text{i=j}}\0&{\text{cases}}}$

파라미터화

때때로 우리는 3D 표면을 평평한 평면으로 평평하게 만들어야 합니다.이 프로세스를 파라미터화라고 합니다.목표는 왜곡을 최소화하기 위해 표면을 매핑할 수 있는 좌표 u와 v를 찾는 것입니다.이와 같이 파라미터화는 최적화 문제로 볼 수 있습니다.메쉬 파라미터화의 주요 용도 중 하나는 텍스처 맵핑입니다.

매스 스프링법

Tutte Embedding은 딱정벌레의 측면에 매끄럽지 않은 매개변수화를 보여줍니다.

매핑 프로세스에서 발생하는 왜곡을 측정하는 한 가지 방법은 2D 매핑의 모서리 길이가 원래 3D 표면 길이와 얼마나 다른지 측정하는 것입니다.좀 더 공식적인 용어로, 목적 함수는 다음과 같이 쓸 수 있다.

${U}{\text{min}}\sum _{ij\in E}u_{i}-u_{j}^{2$

$E$ 서E {\ $displaystyle$ E $}$ 는 $E$ 메시 엣지 $U$ 이고U {\ $displaystyle$ U $}$ 는 $U$ 정점 세트입니다.그러나 이 목적 함수를 최적화하면 모든 정점을 uv 좌표의 단일 정점에 매핑하는 솔루션이 생성된다.그래프 이론에서 아이디어를 차용하여, 우리는 투테 매핑을 적용하고 메쉬의 경계 정점을 단위 원이나 다른 볼록 폴리곤에 제한합니다.이렇게 하면 매핑을 적용할 때 정점이 단일 정점으로 축소되는 것을 방지할 수 있습니다.그런 다음 비경계 정점은 인접 정점의 중심 보간에 배치된다.그러나 Tutte 매핑은 모서리 길이를 같게 하려고 시도하기 때문에 여전히 심각한 왜곡으로 인해 실제 표면 메쉬의 삼각형 크기를 올바르게 고려하지 않습니다.

최소 제곱 등각 매핑

Tutte Embedding과 최소 제곱 적합-매핑 모수화의 비교.딱정벌레의 측면에서 LSCM 파라미터화가 얼마나 매끄럽게 이루어지는지 주목하십시오.

왜곡을 측정하는 또 다른 방법은 u 및 v 좌표 함수의 변화를 고려하는 것입니다.매스 스프링 방법의 흔들림 및 왜곡은 u 및 v 좌표 함수의 변화가 크기 때문입니다.이 접근방식을 사용하면 목적 함수는 u와 v의 디리클레 에너지가 됩니다.

${u,v}{\text{min}}\int _{S}\nabla u ^{2}+ \nabla v ^{2}dA$

고려해야 할 몇 가지 다른 사항이 있습니다.직교성을 유지하기 위해 각도 왜곡을 최소화하고 싶습니다. $\nabla u=\nabla v^{\perp }$ , $\nabla u=\nabla v^{\perp }$ u $=$ 】【{displaystyle $\displayla$ u =\ $displayla$ v $^{\perp$ 를 희망합니다.또, 오리지날과 같은 크기의 영역을 맵핑 해 주셨으면 합니다.따라서 u 및 v 좌표 함수의 야코비안이 1로 설정됩니다.

${\dfrac u} {\dfrac u} {\frac } {\frac v} {\frac x} {\frac {\frac v} {\frac y} \end {bmatrix$

이러한 요건을 종합하면 디리클레 에너지를 증강하여 목적 함수를 다음과 같이 ^[6]^[7]만들 수 있습니다.

${u,v}{\text{min}}\int _{S}{\frac {1}{2}+{\frac {1}}\nabla v ^{2}-\nabla u\cdot \nabla v^{\perp}}$

모든 정점이 단일 점에 매핑되는 문제를 피하기 위해 최적화 문제에 대한 솔루션이 0이 아닌 노름을 가져야 하며 사소한 솔루션과 직교해야 한다.

변형

as-rigid-as-possible 변형 예시.

변형은 일부 정지 형태를 새로운 모양으로 변형하는 것과 관련이 있습니다.일반적으로 이러한 변환은 연속적이며 쉐이프의 토폴로지를 변경하지 않습니다.최신 메쉬 기반 형상 변형 방법은 핸들(메쉬의 선택된 정점 또는 영역)의 사용자 변형 제약을 충족하고 이러한 핸들 변형을 세부 사항을 제거하거나 왜곡하지 않고 나머지 형상으로 부드럽게 전파한다.일반적인 대화형 변형 형태로는 포인트 기반, 스켈레톤 기반 및 케이지 기반 ^[8]등이 있습니다.점 기반 변형에서는 사용자가 형상의 핸들이라고 하는 작은 점 세트에 변환을 적용할 수 있습니다.스켈레톤 기반 변형은 쉐이프에 대한 스켈레톤을 정의하며 이를 통해 사용자는 골격을 이동하고 관절을 회전할 수 있습니다.케이지 기반 변형에서는 케이지가 모양 전체 또는 일부 주위에 그려져야 합니다. 따라서 사용자가 케이지의 포인트를 조작할 때 케이지가 둘러싸이는 볼륨이 그에 따라 변경됩니다.

포인트 베이스 변형

핸들은 변형에 대한 희박한 제약 조건을 제공합니다. 즉, 사용자가 한 지점을 이동할 때 다른 지점은 제자리에 있어야 합니다.

$\mathbb {R} ^{3}$ 에 담근 ${\hat {S}}$ S $^$ ${\displaystyle$ $\mathbb {R}$ ^{ $3}}$ 는 $\mathbb{R} ^{3}$ ${\hat {x}}:\Omega \rightarrow \mathbb {R} ^{3}$ x ${\hat {x}}:\Omega \rightarrow \mathbb {R} ^{3}$ : ${\hat {x}}:\Omega \rightarrow \mathbb {R} ^{3}$ ${\hat {x}}:\Omega \rightarrow \mathbb {R} ^{3}$ ${\hat {x}}:\Omega \rightarrow \mathbb {R} ^{3}$ 3 ${\displaystyle {x}:$ $\Omega$ \ $rightarrow \mathbb {R}$ ^{ $3}}$ 。여기서 $\Omega$ \ $displaystyle$ \ $Omega }$ 는 $\Omega$ 2D 파라미터 도메인입니다.변환된 $S$ 에 대한 $다른$ 매핑x(\ $displaystyle$ x $S$ 에서도 $x$ 같은 작업을 수행할 수 있습니다. 변환된 모양은 원본에 가능한 한 왜곡을 주지 않는 것이 이상적입니다.이러한 왜곡을 모델링하는 한 가지 방법은 라플라시안 기반 ^[9]에너지로 d $d=x-{\hat {x}}$ - $d=x-{\hat {x}}$ $^$ { $displaystyle$ d $=x-{\hat {x}}$ 의 $d=x-{\hat {x}}$ 변위에 관한 것입니다.이러한 매핑에 Laplace 연산자를 적용하면 점의 위치가 인접 지역에 비해 어떻게 변화하는지 측정하여 핸들을 부드럽게 유지할 수 있습니다.따라서 최소화하고 싶은 에너지는 다음과 같이 나타낼 수 있습니다.

$\min _{\textbf {d}}\int _{\Omega }||\Delta {\textbf {d}}||^{2}dA$ d $\min _{\textbf {d}}\int _{\Omega }||\Delta {\textbf {d}}||^{2}dA$ $\min _{\textbf {d}}\int _{\Omega }||\Delta {\textbf {d}}||^{2}dA$ 2 d 2 $\min _{\textbf {d}}\int _{\Omega }||\Delta {\textbf {d}}||^{2}dA$ $\min _{\textbf {d}}\int _{\Omega }||\Delta {\textbf {d}}||^{2}dA$ { $displaystyle \min$ _ { \ $textbf$ { d $\min _{\textbf {d}}\int _{\Omega }||\Delta {\textbf {d}}||^{2}dA$ } $int$ _ { \ $Omega$ } \ $Delta$ \ $textbf$ { $d$ } ^ {2 $} dA$ }

이 메서드는 변환 불변이지만 회전을 설명할 수는 없습니다.As-Rigid-As-Possible 변형 $x_{i}=R{\hat {x_{i}}}+t$ 은^[10] 강성 변환 x $x_{i}=R{\hat {x_{i}}}+t$ $x_{i}=R{\hat {x_{i}}}+t$ $x_{i}=R{\hat {x_{i}}}+t$ x $x_{i}=R{\hat {x_{i}}}+t$ + $x_{i}=R{\hat {x_{i}}}+t$ t \ $displaystyle x_{i$ } $=$ $각$ 핸들 i에 대한 R ${\hat {x_{i}}+t$ $R\in SO(3)\subset \mathbb {R} ^{3}$ 서 R $R\in SO(3)\subset \mathbb {R} ^{3}$ S $R\in SO(3)\subset \mathbb {R} ^{3}$ (3 $R\in SO(3)\subset \mathbb {R} ^{3}$ $R\in SO(3)\subset \mathbb {R} ^{3}$ 3 \ $displaystyle$ R $\in SO(3)\subset \mathbb {R} ^{3$ } $t\in \mathbb {R} ^{3}$ 3 \ $displaystyle$ t $\in \mathbb {R} ^{$ 3} ^ $3$ 은 벡터 변환이다.아쉽게도 사전에 회전을 알 수 있는 방법은 없기 때문에 변위를 최소화하는 "최적의" 회전을 선택합니다.그러나 국부 회전 불변성을 달성하려면 ${\textbf {R}}:\Omega \rightarrow SO(3)$ : ${\textbf {R}}:\Omega \rightarrow SO(3)$ ${\textbf {R}}:\Omega \rightarrow SO(3)$ ${\textbf {R}}:\Omega \rightarrow SO(3)$ ${\textbf {R}}:\Omega \rightarrow SO(3)$ ( ${\textbf {R}}:\Omega \rightarrow SO(3)$ ) ${\textbf {R}}:\Omega \rightarrow SO(3)$ {\ $displaystyle {Textbf {R}}:$ $\Omega$ \ $rightarrow$ SO $(3)$ - 표면의 ${\textbf {R}}:\Omega \rightarrow SO(3)$ 모든 점에 대해 최적의 회전을 출력합니다 $.$ 그 결과 발생하는 에너지는 ${\textbf {R}}$ $(\displaystyle$ $\$ $textbf$ {x $})$ 와 R(\ $displaystyle\$ textbf ${R$ ${\textbf {x}}$ 에 ${\textbf {x}}$ 대해 최적화되어야 합니다.

$\displaystyle \min _{\textbf {x,R}\int _{\Omega }\nabla {textbf {x}-{\textbf {R}}\nabla {textbf {x}}^{2}dA}$

변환은 일정한 구배를 가지므로 변환 벡터는 최종 목적 함수에 존재하지 않습니다.

내부 외부 세그먼트화

외관상으로는 사소한 일이지만, 대부분의 경우 삼각형 메쉬의 바깥쪽에서 내부를 판별하는 것은 쉬운 문제가 아닙니다.일반적으로 $표면$ S {\ $displaystyle$ S $}$ 에서 $S$ 이 문제를 제기합니다. 이 $isInside(q)$ 는 $isInside(q)$ { $isInside(q)$ $isInside(q)$ 의 $q$ 를 $isInside(q)$ $isInside(q)$ 하는 것입니다. 이 $isInside(q)$ 는 점 $q$ { $displaystyle$ q $}$ 가 $q$ S {\ $displaystyle$ S $S$ 안에 $있으면$ 1 {\ $displaystyle$ 1 $}$ 을 $1$ $0$ 반환하고 $그렇지$ 않으면0을 반환합니다.

가장 간단한 경우 셰이프가 닫혀 있습니다.이 경우 q $\displaystyle$ q $q$ \ $displaystyle$ q $r$ \displaystyle r $\$ $displaystyle$ r $\$ displaystyle $count_{r}$ 의 $count_{r}$ $count_{r}$ 를 세어 지표면 안쪽에 $있는지$ 여부를 $count_{r}$ 할 수 있습니다.q{ $displaystyle$ q}가 $q$ S {\ $displaystyle$ S $}$ $S$ 에 $S$ 있는 $경우$ 광선이S {\ $count_{r}=0$ S $=$ { $displaystyle count_{r$ }= $0$ 을 $S$ 할 수 없거나 S{ $displaystyle$ S $}$ 에 $S$ 들어갈 때마다 광선이 두 번 통과해야 합니다.따라서q(\ $displaystyle$ q)가 $q$ 외부에 있는 $경우$ c $count_{r}$ $count_{r}$ t $(\$ 은 $count_{r}$ 짝수입니다.마찬가지로 q ${displaystyle$ q}가 $q$ 내부에 있는 $q$ 에도 이전 케이스에도 동일한 논리가 적용되지만, 광선은S{ $displaystyle$ S $S$ 에서 처음 나올 때S{ $displaystyle$ S $}$ 를 $S$ 한 번 더 교차해야 합니다.

$\displaystyle isInside_{r}(q)=\left\{\begin{array}{ll}1&count_{r}\는 홀수입니다\0&count_{r}\는 짝수입니다\\end{array}\right.}$

현재 우리는 종종 S $(디스플레이$ 스타일 S $)$ 가 $S$ 닫혔다고 보장할 수 없습니다.이 기사의 맨 위에 있는 바지 예를 들어 보세요.허리와 다리에 구멍이 뚫려 있어도 안과 밖이 시멘틱한 메쉬입니다.

다양한 수의 광선에 대해 쿼리 포인트에서 광선을 발사하여 내부 외부 분할을 근사화합니다.

이 문제를 해결하기 위한 순진한 시도는 많은 광선을 무작위로 쏘고 대부분의 광선이 S $(\displaystyle$ S $)$ 와 $S$ 홀수 횟수 교차하는 경우에만q(\ $displaystyle$ q)를 $q$ 내부에 있는 것으로 $q$ 하는 것입니다.이를 정량화하기 위해 k $(\displaystyle$ $k)$ $,$ $r_{1},r_{2},\dots ,r_{k}$ , $r_{2},\display, r_{k$ 을(를) $k$ 한다고 가정합니다 $.$ 는 숫자 r $rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)$ $rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)$ $rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)$ $)$ $rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)$ $rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)$ $rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)$ $rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)$ i $rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)$ $rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)$ k $rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)$ $rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)$ $rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)$ i $rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)$ $rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)$ $style$ ( test $rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)$ )각 광선의 $isInside_{r}$ I/ $isInside_{r}$ / $/$ 값 $isInside_{r}$ .그 때문에,

$isInside(q)=\left\{\begin{array}{ll}1&rayTest(q)\geq 0.5\rayTest(q)<0.5\\end {array}\right.$

다수의 광선을 쏘는 한계에서는 오픈 메쉬를 취급하지만 정확성을 높이기 위해서는 광선이 너무 많이 필요하기 때문에 계산적으로 이상적입니다.대신, 보다 강력한 접근법은 일반화된 권선 ^[11]번호입니다.2D 와인딩 번호에서 영감을 얻어 이 접근법은 메시 내 각 삼각형의 q $\displaystyle$ q $q$ \ $displaystyle$ $q$ \displaystyle q\ $displaystyle$ q $\$ displaystyle q $\$ displaystyle q $q$ \displaystyle $q$ q ${$ $displaystyle$ q $q$ , $wn(q)$ ( $wn(q)$ ) { $displaystyle wn ( q$ ) 에서의 $wn(q)$ 일반화 와인딩 번호의 값은 메쉬 내의 각 삼각형으로부터의 입체각 기여도의 합계에 비례합니다.

$wn(q)=sum frac {1}{4\pi }}\sum _{t\in F}solid Angle(t)$

닫힌 메쉬의 경우 w $wn(q)$ ( $wn(q)$ ) { $displaystyle wn(q)}$ 은 $wn(q)$ $($ 는) S { $displaystyle$ S $S$ 로 나타나는 볼륨의 특성 함수와 동일합니다.따라서 다음과 같습니다.

$isInside(q)=\left\{\begin{array}{lll(q)\geq 0.5\\0&wn(q)<0.5\\end {array}\right.$

$wn(q)$ { $displaystyle wn(q)}$ 은 $wn(q)$ (는) 고조파 $wn(q)$ 이므로 정상적으로 열화되므로 닫힌 메쉬에 구멍을 뚫어도 내부 외부 분할은 크게 변경되지 않습니다.이 때문에, Generalized Winding Number 는 오픈 메쉬를 강력하게 처리합니다.안쪽과 바깥쪽의 경계가 그물 구멍 위를 부드럽게 통과합니다.실제로 한계에서는 광선의 수가 무한대에 도달하기 때문에 일반화 권선 수는 광선 주조 방법과 동일합니다.

적용들

컴퓨터 지원 설계(CAD)
3D 표면 재구성(예: 공항 보안의 범위 스캐너, 자율 차량, 의료 스캐너 데이터 재구성)
이미지 투 월드 등록(예: 이미지 가이드 수술)
아키텍처(예: 생성, 리버스 엔지니어링)
물리 시뮬레이션
컴퓨터 게임(예: 충돌 감지)
지질 모델링
시각화(그래픽) 정보 시각화, 수학적 시각화 등
텍스처 매핑
생체 시스템 모델링(예: 근육 및 뼈 모델링, 실시간 손 추적)

「」를 참조해 주세요.

변분법
컴퓨터 그래픽스
- 3D 컴퓨터 그래픽스
- 그래픽스 처리 장치(GPU)
컴퓨터 지원 설계(CAD)
디지털 이미지
- 디지털 이미지 처리
이산 미분 기하학
미분 지오메트리 및 위상 용어집
산업용 CT 스캔
인터랙티브 지오메트리 소프트웨어 목록
메쉬랩
신호 처리
- 디지털 신호 처리
- 디지털 신호 프로세서(DSP)
토폴로지

레퍼런스

^ ^a ^b Botsch, Mario; Kobbelt, Leif; Pauly, Mark; Alliez, Pierre (2010). Polygon Mesh Processing. CRC Press. ISBN 9781568814261.
^ Hugues Hoppe. "Progressive Meshes" (PDF).
^ ^a ^b "Poisson surface reconstruction". hhoppe.com. Retrieved 2017-01-26.
^ Szymon Rusinkiewicz, Marc Levoy. "Efficient Variants of the ICP Algorithm" (PDF).
^ "Chris Tralie : Laplacian Meshes". www.ctralie.com. Retrieved 2017-03-16.
^ Desbrun, Mathieu (2002). "Intrinsic Parameterizations of Surface Meshes" (PDF). Eurographics. 21.
^ Levy, Bruno (2002). "Least squares conformal maps for automatic texture atlas generation" (PDF). ACM Transactions on Graphics. 21 (3): 362–371. doi:10.1145/566654.566590.
^ Jacobson, Alec; Baran, Ilya; Popović, Jovan; Sorkine, Olga (2011). "Bounded Biharmonic Weights for Real-Time Deformation" (PDF). ACM Transactions on Graphics. 30 (4): 1. doi:10.1145/2010324.1964973.
^ Marc, Alexa (2003). "Differential coordinates for local mesh morphing and deformation". The Visual Computer. 19 (2): 105–114. doi:10.1007/s00371-002-0180-0. S2CID 6847571.
^ Sorkine, Olga; Alexa, Marc (2007). "As-Rigid-As-Possible Surface Modeling" (PDF). Proceedings of EUROGRAPHICS/ACM SIGGRAPH Symposium on Geometry Processing: 109–116.
^ Jacobson, Alec; Ladislav, Kavan; Sorkine-Hornung, Olga (2013). "Robust Inside-Outside Segmentation using Generalized Winding Numbers" (PDF). ACM Transactions on Graphics. 32 (4): 1. doi:10.1145/2461912.2461916. S2CID 207202533.

외부 링크

지오메트리 처리 심포지엄
Caltech, Multi-Res Modeling Group
베를린 자유 대학교 수학 기하학 처리 그룹
RWTH 아헨 대학교 컴퓨터 그래픽스 그룹
폴리곤 메쉬 처리 북
폴리곤 메쉬 처리 라이브러리
이산 미분 형상: Keenan Crane 등의 코스 노트, 응용 소개.
SGP 2017 대학원 비디오 튜토리얼
libigl 지오메트리 처리 라이브러리
CGAL 계산기하학 알고리즘 라이브러리 (폴리곤 메쉬 처리 섹션 참조)

[PMP2010-1] Botsch, Mario; Kobbelt, Leif; Pauly, Mark; Alliez, Pierre (2010). Polygon Mesh Processing. CRC Press. ISBN 9781568814261.

[2] Hugues Hoppe. "Progressive Meshes" (PDF).

[:0-3] "Poisson surface reconstruction". hhoppe.com. Retrieved 2017-01-26.

[4] Szymon Rusinkiewicz, Marc Levoy. "Efficient Variants of the ICP Algorithm" (PDF).

[5] "Chris Tralie : Laplacian Meshes". www.ctralie.com. Retrieved 2017-03-16.

[6] Desbrun, Mathieu (2002). "Intrinsic Parameterizations of Surface Meshes" (PDF). Eurographics. 21.

[7] Levy, Bruno (2002). "Least squares conformal maps for automatic texture atlas generation" (PDF). ACM Transactions on Graphics. 21 (3): 362–371. doi:10.1145/566654.566590.

[8] Jacobson, Alec; Baran, Ilya; Popović, Jovan; Sorkine, Olga (2011). "Bounded Biharmonic Weights for Real-Time Deformation" (PDF). ACM Transactions on Graphics. 30 (4): 1. doi:10.1145/2010324.1964973.

[9] Marc, Alexa (2003). "Differential coordinates for local mesh morphing and deformation". The Visual Computer. 19 (2): 105–114. doi:10.1007/s00371-002-0180-0. S2CID 6847571.

[10] Sorkine, Olga; Alexa, Marc (2007). "As-Rigid-As-Possible Surface Modeling" (PDF). Proceedings of EUROGRAPHICS/ACM SIGGRAPH Symposium on Geometry Processing: 109–116.

[11] Jacobson, Alec; Ladislav, Kavan; Sorkine-Hornung, Olga (2013). "Robust Inside-Outside Segmentation using Generalized Winding Numbers" (PDF). ACM Transactions on Graphics. 32 (4): 1. doi:10.1145/2461912.2461916. S2CID 207202533.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Search

지오메트리 처리

네임스페이스

더

목차

라이프 사이클로서의 지오메트리 처리