Hausdorff Distance Computation Between Triangle Mesh and Quad Mesh :

강윤구

추천

검색

자료유형: 학위논문

저자정보: 강윤구 (서울대학교, 서울대학교 대학원)

발행연도: 2018

저작권: 서울대학교 논문은 저작권에 의해 보호받습니다.

이용수1

이 논문의 연구 히스토리 (2)

2019

Computation of Near-Zero Hausdorff Distance Between Triangle Mesh and Quad Mesh

강윤구 , 윤승현 , 경민호 외 1명 Journal of KIISE 2019.02 학술저널

2018

Hausdorff Distance Computation Between Triangle Mesh and Quad Mesh

강윤구 전기·컴퓨터공학부 2018.01 학위논문

이 논문의 후속연구가 궁금하신가요?
연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
이 논문의 연구 히스토리 확인하기

초록· 키워드

오류제보하기

본 논문에서는 준정규 사각형 메시의 사용성을 증대시키기 위한 다양한 기하 알고리즘을 소개한다. 우선 기하 연산을 가속화하는 데에 쓰이는 bounding volume hierarchy로 사각형 메시에 특화시킨 새로운 구조를 선보인다. 이를 이용하면 사각형 메시로의 점 투영(최단 거리 계산)을 빠르게 수행할 수 있다. 점 투영은 하우스도르프 거리 계산 및 사각형 메시 재건을 위해 본 논문에서 새롭게 제안하는 알고리즘에서 큰 비중을 차지하는 핵심 연산이다.

한 삼각형 메시와 이를 근사하는 사각형 메시 사이의 하우스도르프 거리는 그 근사 품질을 평가할 수 있는 척도이다. 하지만 물체 정합에도 쓰이는 하우스도르프 거리를 계산하는 일은 메시 모델에 대해 늘 매우 어려운 문제이어 왔고 특히 사각형 메시에 대해서는 아예 연구된 바가 없다. 본 논문에서 소개하는 알고리즘은 질의 모델을 반복적으로 분할하고 무관한 조각들을 제거함으로써 하우스도르프 거리가 발생하는 곳과 하우스도르프 거리의 상한과 하한을 점차 좁혀나간다. 하한을 갱신하는 일과 영향력이 없는 모델 조각을 찾아내는 데에 점 투영이 깊게 관여한다. 상호작용 가능한 속도가 달성되었으며 알고리즘의 높은 정확도는 계산 정밀도의 제약만을 받는다. 이는 모델 근사나 물체 정합에 있어서 선호되는 결과인 하우스도르프 거리가 영에 가까운 상황에도 성립하는데, 사실 가장 난이도가 높은 경우이다.

또한, 본 논문은 사각형 메시를 생성하는 데에 도움을 주는 인터페이스를 제안한다. 주어진 메시 모델이나 점 구름을 사각형 메시로 변환하기 위해 먼저 사용자가 원하는 사각 레이아웃을 그려넣도록 한다. 인터페이스의 알고리즘은 입력 데이터를 레이아웃의 각 패치에 자동으로 할당하고 이를 근사하는 사각형 메시도 자동으로 생성한다. 사각형 메시를 반복적으로 다듬는 과정에서 점 투영은 다시 한 번 큰 비중을 차지한다. 이 사각형 메시는 앞서 제시된 알고리즘을 통해 계산되는 하우스도르프 거리로 평가할 수 있다.

We present various geometric algorithms to facilitate the employment of semi-regular quad meshes. First, a new bounding volume hierarchy?data structure that is used to accelerate geometric operations?is introduced, designed specifically for quad meshes. With this, we can execute rapid point projection, i.e., minimum distance computation from a point to a quad mesh. Point projection is a crucial operation, a main component of our novel algorithms for Hausdorff distance computation and quad mesh reconstruction.

The Hausdorff distance between a triangle mesh and its quad mesh approximation is a measure that can evaluate the quality of the approximation. But computing the Hausdorff distance, which can also be used for shape matching, has always been an extremely difficult problem for mesh models and was never studied specifically for quad meshes. Our algorithm iteratively narrows down where the Hausdorff distance occurs and simultaneously the lower and upper bounds for the Hausdorff distance, by repeatedly partitioning the query model and discarding irrelevant parts. Point projection is heavily involved in updating the lower bound and identifying the inconsequential model parts. We achieve interactive speed and high accuracy that is only capped by the machine’s precision. This is true even for the case where the Hausdorff distance is near zero, which is usually the desired outcome of the approximation or shape matching and also, unfortunately, the most challenging configuration to handle.

In addition, we provide an interface that can assist in creating quad meshes. It converts an existing mesh model or a point cloud into a quad mesh by first letting the user sketch a desired quad layout. Then our algorithm automatically assigns the input data to each patch in the layout, which is then approximated by the quad mesh that is also generated automatically. Point projection is again a large component of the iterative refinement of the approximation. This quad mesh can be evaluated by the Hausdorff distance calculated by our proposed algorithm.

1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Research Objectives and Contributions . . . . . . . . . . . . . . 3
1.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Preliminaries 11
2.1 QuadMesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Interpretation of Quadrilateral Facets . . . . . . . . . . . . . . 13
3 Related Work 17
3.1 Hausdorff Distance Computation . . . . . . . . . . . . . . . . . 17
3.2 QuadMesh Reconstruction . . . . . . . . . . . . . . . . . . . . 19
4 Quad Mesh BVH Operations 21
4.1 Offset Tetrahedron BVH . . . . . . . . . . . . . . . . . . . . . . 21
4.1.1 Proof of the Offset Radius Rule . . . . . . . . . . . . . . 24
4.1.2 Handling Deformation . . . . . . . . . . . . . . . . . . . 26
4.2 Point Projection with the BVH . . . . . . . . . . . . . . . . . . 27
4.3 Point Projection with the UniformGrid . . . . . . . . . . . . . 28
4.4 Collision Detection . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.5 Self-Collision Detection . . . . . . . . . . . . . . . . . . . . . . 30
5 Hausdorff Distance Computation 33
5.1 General Framework . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.1.1 Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . 36
5.1.2 Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . 36
5.1.3 Iterative Partitioning . . . . . . . . . . . . . . . . . . . . 37
5.1.4 Unspecified Elements . . . . . . . . . . . . . . . . . . . . 39
5.2 Triangle-to-Quad HD. . . . . . . . . . . . . . . . . . . . . . . . 40
5.3 TriangleMesh-to-QuadMesh HD . . . . . . . . . . . . . . . . . 44
5.3.1 Matching to Quads as Bilinear Surfaces . . . . . . . . . 45
5.3.2 Matching to Quads as Adjoining Triangles . . . . . . . . 48
5.4 QuadMesh-to-TriangleMesh HD . . . . . . . . . . . . . . . . . 51
5.5 Two-Sided HD . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.6 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . 58
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6 Quad Mesh Reconstruction 85
6.1 Boundary Curve Sketching . . . . . . . . . . . . . . . . . . . . 86
6.1.1 Point Cloud Rendering . . . . . . . . . . . . . . . . . . . 86
6.1.2 Basic Point Input . . . . . . . . . . . . . . . . . . . . . . 87
6.1.3 Curve Editing . . . . . . . . . . . . . . . . . . . . . . . . 89
6.2 Patch Assignment . . . . . . . . . . . . . . . . . . . . . . . . . 92
6.3 Iterative Reconstruction . . . . . . . . . . . . . . . . . . . . . . 95
7 Conclusion 101

최근 본 자료

전체보기

구분	그룹	데이터 항목
AI 학습용 데이터	원문	원문 PDF 파일
AI 학습용 데이터	원문 + 메타 (기본/상세)	원문 PDF 파일 및 서지정보 CSV
대량 구매용 데이터	B2B 구독 방식	특정 자료 한정으로 원문 접근 권한 부여
대량 구매용 데이터	URL 전달 방식	바로 PDF 뷰어를 열람할 수 있는 URL 제공

구분	그룹	데이터 항목
AI 학습용 데이터	기본 메타	발행기관명, 간행물명, 권호명, 권(vol), 호(issue), 통권, 발행연도, 발행월, 논문명, 저자명, 시작페이지, 종료페이지, 전체페이지, 상세페이지URL
상세 메타 데이터	발행기관 메타	발행기관 이명, 영문명, 창립연도, 홈페이지URL, 발행기관 소개
	간행물 메타	부제목, 간행물 유형, ISSN, ISBN, 최초발행연도, 폐간연도, 간행빈도, 발행주기, 등재사항, 이용수, 피인용수, 권호수, 논문수, 표지이미지
	논문 메타	작성 언어, 부제목, 대등제목, 목차, 키워드, 초록, 이미지, 참고문헌, 이용수, 피인용수, 논문활용도, DBpia통합주제분류, KDC분류, DDC분류, 한국연구재단분류, UCI, DOI
	저자 메타	소속기관, 소속부서, 직급, 연구분야, 연구키워드, 이용수, 피인용수, 저자 논문활용도

구분	그룹	데이터 항목
※ 결합형/맞춤형 메타 데이터는 신청 내용에 따라 다양하게 제공 가능
이용순위 정보	주제분야별 많이 이용된 논문	“인문학”에서 많이 이용된 논문 TOP100
	이용기관별 많이 이용된 논문	“중고등학교”에서 많이 이용된 논문 TOP100
	세부기관별 많이 이용된 논문	“서울대학교”에서 많이 이용된 논문 TOP100
	키워드별 많이 이용된 논문	“Chat GPT”에서 많이 이용된 논문 TOP100
키워드 정보	많이 이용된 키워드	특정기간/분야/저널 내 많이 이용된 키워드
	많이 발행된 키워드	특정기간/분야/저널 내 많이 발행된 키워드
	많이 검색된 키워드	특정기간/분야/저널 내 많이 검색된 키워드
	연구 트렌드 키워드	특정 키워드 연관 연구동향 분석 데이터 키워드

논문 기본 정보

이 논문의 연구 히스토리 (2)

초록· 키워드

목차

최근 본 자료

댓글(0)