본 논문은 2차원 평면상의 그림으로부터 3차원 물체를 복원하는 방법을 제시한다. 사용자가 입력하는 2차원 평면 그림은 3차원 물체의 윤곽선을 그린 것으로, 자신의 일부분이나 다른 물체에 의해 가려진 부분이 있는 윤곽선도 허용하는 것이 특징이다. 따라서, 복원된 3차원 물체 역시 자신의 일부, 혹은 다른 물체에 의해 가려진 부분이 존재할 수 있다. 본 논문에서 제안하는 방법은 2차원 윤곽선 분석, 3차원 골격 계산, 그리고 3차원 물체 복원의 세가지 단계로 구성된다. 본 논문의 주된 기여는 기여는 자신이나 다른 물체에 의해 가려진 2차원 윤곽선으로부터 3차원 골격을 계산하는 방법이며, 이를 위하여 일련의 최적화 문제를 정의하고 해결하였다. 최적화 문제는 골격의 생성, 물체의 충돌 제한, 그리고 C1 연속성 유지를 위하여 사용된다. 결과적으로, 제안된 방법은 기존의 실루엣 기반의 스케칭 인터페이스를 사용한 3차원 물체 모델링에 대하여, 상호 폐색 (가림/가려짐) 이 존재하는 형태에서도 허용되도록 확장하였다.
본 논문은 2차원 평면상의 그림으로부터 3차원 물체를 복원하는 방법을 제시한다. 사용자가 입력하는 2차원 평면 그림은 3차원 물체의 윤곽선을 그린 것으로, 자신의 일부분이나 다른 물체에 의해 가려진 부분이 있는 윤곽선도 허용하는 것이 특징이다. 따라서, 복원된 3차원 물체 역시 자신의 일부, 혹은 다른 물체에 의해 가려진 부분이 존재할 수 있다. 본 논문에서 제안하는 방법은 2차원 윤곽선 분석, 3차원 골격 계산, 그리고 3차원 물체 복원의 세가지 단계로 구성된다. 본 논문의 주된 기여는 기여는 자신이나 다른 물체에 의해 가려진 2차원 윤곽선으로부터 3차원 골격을 계산하는 방법이며, 이를 위하여 일련의 최적화 문제를 정의하고 해결하였다. 최적화 문제는 골격의 생성, 물체의 충돌 제한, 그리고 C1 연속성 유지를 위하여 사용된다. 결과적으로, 제안된 방법은 기존의 실루엣 기반의 스케칭 인터페이스를 사용한 3차원 물체 모델링에 대하여, 상호 폐색 (가림/가려짐) 이 존재하는 형태에서도 허용되도록 확장하였다.
In this paper, we propose a method for reconstructing a 3D object (or a set of objects) from a 2D drawing provided by a designer. The input 2D drawing consists of a set of contours that may partially overlap each other or be self-overlapping. Accordingly, the resulting 3D object(s) may occlude each ...
In this paper, we propose a method for reconstructing a 3D object (or a set of objects) from a 2D drawing provided by a designer. The input 2D drawing consists of a set of contours that may partially overlap each other or be self-overlapping. Accordingly, the resulting 3D object(s) may occlude each other or be self-occluding. The proposed method is composed of three major steps: 2D contour analysis, 3D skeleton computation, and 3D object construction. Our main contribution is to compute the 3D skeleton from the self-intersecting 2D counterpart. We formulate the 3D skeleton construction problem as a sequence of optimization problems, to shape the skeleton and place it in the 3D space while satisfying C1-continuity and intersection-free conditions. Our method is mainly for a silhouette-based sketching interface for the design of 3D objects including self-intersecting objects.
In this paper, we propose a method for reconstructing a 3D object (or a set of objects) from a 2D drawing provided by a designer. The input 2D drawing consists of a set of contours that may partially overlap each other or be self-overlapping. Accordingly, the resulting 3D object(s) may occlude each other or be self-occluding. The proposed method is composed of three major steps: 2D contour analysis, 3D skeleton computation, and 3D object construction. Our main contribution is to compute the 3D skeleton from the self-intersecting 2D counterpart. We formulate the 3D skeleton construction problem as a sequence of optimization problems, to shape the skeleton and place it in the 3D space while satisfying C1-continuity and intersection-free conditions. Our method is mainly for a silhouette-based sketching interface for the design of 3D objects including self-intersecting objects.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
3차원 물체의 모델링을 위한 스케칭 인터페이스에 대한 관련 연구들을 살펴보겠다. 이들은 모델링하는 형상 의 클래스에 따라 분류할 수 있는데, 가장 일반적인 방법은 사용자로 하여금 직선으로 이루어진 물체의 보여 지는 윤곽과 감춰진 윤곽을 사용자가 그림으로써 모델 링하는 방법이다[6-8].
골격 둘레에 복원될 3차원 형상의 휨 에너지를 직접 측정하는 대신, 골격의 휨 에너지를 계산하여 2차원 골 격에 적절한 z 좌표를 할당하는 것으로 대치하고자 한다. 안타깝게도, 곡선의 휨 에너지는 비선형이몌22], 이는 최적화 문제로 다루기 복잡하다.
마지막으로 정의할 목적 함수는 복원된 물체가 스케 칭 평면으로부터 최소화의 거리를 갖기 위한 것이다. 골 격상의 각 정점 质为, 方)에 대한 목적함수는 z; 이다; 모든 점에 대해 정의된 목적함수는 따라서,
본 논문에서는 자신 혹은 다른 물체에 의해 가려진 부분이 있는 물체를 대상으로 하여 스케치 입력으로부터 3차원 물체를 복원하는 방법을 제안하였다. 그림 11 에 보인 예제들은 제안된 방법의 효용성을 잘 나타낸다.
본 논문에서는 자신 혹은 다른 물체에 의해 가려진 부분이 있는 자유형태 물체를 모델링하는 것에 초점을 두었다. 자신으로부터 가려진 부분이 있는 3차원 물체를 효율적으로 복원하는 부분이 본 연구의 기여이다.
이러한 최근 연구로는 합성곱 곡 면(convolution surface)[2], 볼륨 메트릭 형상(volumetric shape)[3], 변분 음함수 곡면(variatianal implicit surface) [4], 음함수 곡면(implicit surface) 관련 연귀51 등이 있다. 본 논문은 기존 스케칭 인터페이스에서 불가능 했던 종류의 물체들, 즉 그림 1에서 보인 것과 같이 자신이나 다른 물체에 의해 가려진 부분이 있는 물체들도 모델링 할 수 있음을 보임으로써 스케치 기반 모델링의 영역을 확장한다. 앞서 소개한 Teddy와 같은 기존 모델러를 사용하여 이런 형태의 물체를 모델링을 하기란 매우 어렵 고, 실제로 불가능하다고 할 수 있겠다.
본 논문은 이러한 문제에 대한 통합적인 해결 방법을 제안한다.
각각의 곡선을 교 차점에서 잘라(cut) 교차가 없는 여러 개의 곡선 세그먼 트들로 나누었고, 각각의 곡선 세그먼트는 깊이 정보, 즉, 현시점에서 바라보았을 때 곡선을 가리는 곡면의 갯 수로 라벨링 되었다(그림 2(c)). 본 연구에서 우리의 목 표는 생성될 3차원 물체의 실루엣이 입력으로 주어진 윤곽선 그림과 일치하되, 상호 충돌이나 표면 교차가 일 어나지 않도록 3차원 물체의 좌표점을 찾아내는 것이다. 앞으로 본 눈문에서는 스케칭 평면은 z=0인 xy평면이 며, 윤곽선 그림은 3차원 물체를 스케칭 평면에 직교 투 영한 것을 그린 것이라고 가정하겠다.
본 절에서는 3차원 물체를 복원하기 위한 알고리즘을 기술한다. 3절에서 설명한 윤곽선 분석 단계에서 우리는 닫힌 곡선의 집합을 얻을 수 있었다.
이 골격은 그림 10 예제 스케치(a)로부터의 복원 결과: (b) 곡률, (c)거리, (d) 오리엔테이션 목적 함수를 각각 작은 값으로 주었을 때 결과 또한 휨과 오리엔테이션, 그리고 스케칭 평면과의 거리 를 최소화한다. 이제 이렇게 얻어진 골격 주위에 3차원 메쉬를 어떻게 생성하는지에 대해 기술하겠다.
본 논문에서는 자신 혹은 다른 물체에 의해 가려진 부분이 있는 자유형태 물체를 모델링하는 것에 초점을 두었다. 자신으로부터 가려진 부분이 있는 3차원 물체를 효율적으로 복원하는 부분이 본 연구의 기여이다. 사용자 입력으로부터 2차원 곡선이 주어졌을 때, 3차원 물체 의 복원은 다음과 같은 세 가지 단계로 진행된다.
가설 설정
그림 5에도 보였듯이, 골격 에지는 자신의 두 점을 통과하는 곡면과 대웅된다. 골격 z좌표가 할당됨에 따라, 대웅되는 곡면도 따라서 변형될 것이다. 이렇듯 골격 자체 대신 곡면을 사용하면, 골격의 곡률 에너지 계산을 단순화할 수 있다.
본 연구에서 우리의 목 표는 생성될 3차원 물체의 실루엣이 입력으로 주어진 윤곽선 그림과 일치하되, 상호 충돌이나 표면 교차가 일 어나지 않도록 3차원 물체의 좌표점을 찾아내는 것이다. 앞으로 본 눈문에서는 스케칭 평면은 z=0인 xy평면이 며, 윤곽선 그림은 3차원 물체를 스케칭 평면에 직교 투 영한 것을 그린 것이라고 가정하겠다.
제안 방법
(1) 물체의 곡률(휨) 에너지; 틀어진 물체보다는 구부러지 지 않은 물체를 더 자연스러운 형상으로 평가한다.
3절에서 설명한 윤곽선 분석 단계에서 우리는 닫힌 곡선의 집합을 얻을 수 있었다. 각각의 곡선을 교 차점에서 잘라(cut) 교차가 없는 여러 개의 곡선 세그먼 트들로 나누었고, 각각의 곡선 세그먼트는 깊이 정보, 즉, 현시점에서 바라보았을 때 곡선을 가리는 곡면의 갯 수로 라벨링 되었다(그림 2(c)). 본 연구에서 우리의 목 표는 생성될 3차원 물체의 실루엣이 입력으로 주어진 윤곽선 그림과 일치하되, 상호 충돌이나 표면 교차가 일 어나지 않도록 3차원 물체의 좌표점을 찾아내는 것이다.
구현된 시스템을 다양한 스케치 예제에 대하여 적용하여 3차원 형상 복원을 테스트해 보았다. 실험에서 스 케치를 위해 타블렛을 사용하였고, 그림 11은 예제 스케 치와 복원 결과들을 보인다.
안타깝게도, 곡선의 휨 에너지는 비선형이몌22], 이는 최적화 문제로 다루기 복잡하다. 따라서 본 연구에서는 각각의 골격 에지에 대응되는 조각 다항식 곡면 (piecewise polynomial surface)의 집합으로 골격을 표 현한다. 그림 5에도 보였듯이, 골격 에지는 자신의 두 점을 통과하는 곡면과 대웅된다.
실루엣의 폭이 좁은 곳이 복원되면 3차원 모델의 얇은 부분을 이루고, 폭이 넓은 곳은 두꺼 운 부분에 대응되는 일반적인 속성을 사용한다. 또한 생성된 모델을 자르기, 덧붙이기, 구부리기, 또는 메쉬 위에 직접 그리기와 같이 모델을 인터액티브하게 변형시 킬 수 있는 편집 도구들을 제공함으로써 생성된 물체에 변경을 더해 나갈 수 있도록 한다.
이 윤곽선들을 적절 히 연결하여 최종적으로 하나 이상의 닫힌 곡선들로 표 현해야 한다(윤곽선 완성). 또한 손으로 그려진 스트로 크는 노이즈가 심하므로 이것을 없애기 위한 필터링 과 정이 필요한데, 그러한 과정은 [16-18]에서 이미 다루었 고, 본 연구에서도 그러한 방법을 참조하여 구현하였다.
또한, I诚이 악조건(ill condition)0] 되지 않도록 가중치의 범위를 제안하였다. 그렇지 않으면 최소화 과 정은 수치적 에러가 커져 실패할 수도 있다.
문제를 단순화하기 위하여, 2차원 윤곽선의 z좌표를 직접 계산하기 보다는, 윤곽선의 골격에 대하여 z 좌표 를 먼저 계산한 다음, 이것으로부터 나머지 부분에 대한 z좌표를 추론해 내도록 하였다. 마지막으로, 2차원 윤곽 선이 실제 3차원 물체의 실루엣과 일치하도록 3차원 골 격 주위에 3차원 볼륨을 생성한다.
Alexe 외는 실루엣 곡 선에 음함수 곡면을 일치시키기 위한 구형 음함수 곡면 의 반지름 계산법을 제안했다. 본 논문에서는 구형 음 함수 곡면의 식을 약간 변경하여, 곡면을 이루는 각각의 음함수를 가중치와 거리의 함수가 아닌 가중치만의 함수로 대치하고, 다음의 선형시스템의 최소 제곱해를 구하였다.
일반적으로 결과는 그림 10에서 보는 것처럼 가중치 (WCun, WOrient, 1如诚)의 선택에 의해 영향을 받는다. 본 연구에서는 사용자가 가중치를 모든 복원된 물체에 대 해, 혹은 물체별로 조절할 수 있게 하였다.
상수 D는 Young(곡면의 탄력 계수)의 계수이고, V는 Poission의 비율이다. 실질적으로 Poission의 비율은 0 에서 1/2 사이의 값을 사용하는 것이 일반적이며, 본 연구에서는 D=2, 으로 설정하여 실험하였다. 에지 Vi=(.
앞서 이미 설명한 바와 같이, 3차원 형상은 스켈리톤 을 중심으로 하여 원형의 절단면을 가지는 볼륨을 생성 함으로써 계산한다. 2차원 골격의 3차원 공간상에서의 위치를 계산하기 위해 골격의 각 정점 山 二(心 V)에서 의 z 좌표 n와 법선벡터의 방향(曲, 改)을 계산하여 할당하는데, 이는 충돌을 피하고 연속성을 유지하면서 4.
사용자 입력으로부터 2차원 곡선이 주어졌을 때, 3차원 물체 의 복원은 다음과 같은 세 가지 단계로 진행된다. 우선 2차원 윤곽선을 분석하고, 다음으로 3차원 골격을 분석한 후, 마지막으로 3차원 물체를 생성한다. 다음 절들에서 각 단계의 세부 내용을 기술한다.
최저 화 알고리즘은 Intel Math Kernel 라이브러리[25]를 사용하여 구현하였다. 이 수치해석용 패키지는 본 논문에서 정의한 최소 제곱 문제에 포함된 선형 시스템을 풀 기 위한 효율적인 방법들을 제공한다.
이론/모형
2차원 드로우잉 툴과 3차원 형상 복원 소프트웨어 모두 상용 그래픽스 패키지인 Maya[26]의 플러그인을 사용하여 구현하였다. 사용자가 직교투영 화면에 스트로크 를 그리면 결과는 원근투영 화면에 보여지게 된다.
위 식에서 “은 M—xj의 6개행 중 5행으로 구성되어 있으며, 이것은 순위부족(rank deficient) 하지 않다. 등식 제약 조건을 가지는 최소 제곱 문제를 풀기 위한 방법으로 직접소거법[24]을 사용하였다. 우선 주어진 행렬들을 다음과 같이 분할(partitioning) 한다:
또한, 완성된 윤곽선이 위상적으로 맞는지 도 함께 검사한다(그림 2 참조). 본 논문에서는 Wil- liamsH91 의 방법을 참조하였다. 즉, 닫힌 윤곽선을 만들 기 위해 가능한 모든 윤곽선 세그먼트의 연결 후보 중 길이와 곡률을 고려하여 선택된 윤곽선 세그먼트의 끝 점을 큐빅 베이지어 스플라인으로 보간한다.
이와 같은 작업을 수행하기 위한 여러가지 방법 들이 제안되었는데, 대부분이 음함수 곡면(implicit sur- face)을 사용하여 곡면을 계산한다[4, 2]. 본 논문에서는 구현이 비교적 간단한 Alexe 외가 제안한 곡면 모델링 방법[5]을 선택하였다. 그 방법에 의하면, 임의의 곡면 은 골격을 따라 위치시킨 여러 개의 구형 음함수 곡면 들을 블렌딩함으로써 생성된다.
이를 위하여 골격을 구성하는 정점들의 z좌표에 일련의 부둥식 제약조건을 두었다 우선, 충돌의 가능성이 있는 부분, 즉 부등식 제약조건이 정의되어야 하는 골격 부분 의 정점의 쌍을 찾아야 한다. 본 연구에서는 Williams [19]의 패널링(paneling) 구축을 사용하였다. 패널링은 스케치 평면에 2차원 패널(혹은 영역)의 집합을 만든다.
윤곽선이 3차원 공간에서 물리적으로 가능한 곡선인 지 아닌지를 판단하여 주어진 곡선 세그먼트의 집합이 위상적으로 맞는지 검사가 필요한데, 본 연구에서는 역시 Williams가 공식화한 정수 선형 프로그래밍을 사용하였다. 이 방법은 윤곽선의 교차 횟수가 안쪽, 그리고 바깥쪽 윤곽선의 개수와 같은 위상적인 성질을 이용하며, 정수 선형 프로그래밍의 해가 있으면 위상적으로 맞 다고 판단한다.
사용자가 직교투영 화면에 스트로크 를 그리면 결과는 원근투영 화면에 보여지게 된다. 최저 화 알고리즘은 Intel Math Kernel 라이브러리[25]를 사용하여 구현하였다. 이 수치해석용 패키지는 본 논문에서 정의한 최소 제곱 문제에 포함된 선형 시스템을 풀 기 위한 효율적인 방법들을 제공한다.
성능/효과
그렇지 않으면 최소화 과 정은 수치적 에러가 커져 실패할 수도 있다. 실험적으로 가장 큰 가중치와 가장 작은 가중치의 비율이 IO, 보다 작을 때 좋은 결과가 나왔다. 그림 10(b)~(c)는 서로 다른 가중치를 사용하여 복원된 결과를 보인다.
후속연구
향후에는 본 모델링 기법을 확장하여 대화형 편집 및 변경이 가능하도록 할 것이다. 예를 들어 Teddy에서오* 같이 사용자가 이미 생성된 모델에 대해 자르기, 돌출 (extrude), 왜곡 (distort)과 같은 연산을 수행할 수 있을 것이다.
참고문헌 (26)
T. Igarashi, S. Matsuoka, H. Tanaka. 'Teddy: A Sketching Interface for 3D Freeform Design,' SIGGRAPH 99 Conference Proceedings, pp. 409-416, 1999
C.-L. Tai, H. Zhang, J. C. Fong, 'Prototype Modeling from Sketched Silhouettes based on Convolution Surfaces,' Computer Graphics Forum 23(1): 71-84, 2004
S. Owada, F. Nielsen, K. Nakazawa, T. Igarashi:'A sketching interface for modeling the internal structures of 3D shapes,' Proc. 3rd International Symposium on Smart Graphics, Springer-Verlag, Berlin, pp. 49-57, 2003
O. Karpenko, J. F. Hughes, R. Raskar, 'Free-form sketching with variational implicit surfaces,' Computer Graphics Forum 21(3), 2002
I. A. Alexe, V. Gaildrat, L. Barthe, 'Interactive modelling from sketches using spherical implicit functions,' Afrigraph 2004: 25-34
H. Lipson, M.Shpitalni, 'Optimization-based reconstruction of a 3D object from a single free-hand line drawing,' Computer-aided Design 28(8): 651-663, 1996
H.Lipson, M.Shpitalini, 'Correlation-based reconstruction of a 3d object from a single freehand sketch,' AAAI Spring Symposium on Sketch Understanding, pp. 99-104, 2002
A. Piquer, R. Martin, P. Company, 'Using skewed mirror symmetry for optimisation-based 3d line-drawing recognition. In Proc. 5th IAPR International Workshop on Graphics Recognition,' pp, 182-193, 2003
R. C. Zeleznik, K. P. Herndon, J. F. Hughes: 'SKETCH: An interface for sketching 3D scenes,' In Proceedings of ACM SIGGRAPH 96, Addison-Wesley, Boston, Massachusetts, pp. 163-170
A. Shesh, B. Chen, 'SMARTPAPER: An Inter-active and User Friendly Sketching System,' Computer Graphics Forum 23(3): 301-310, 2004
O. Tolba, J. Dorsey, L. McMillan, 'A projective drawing system,' Proc. I3D Symposium on Inter-active 3D Graphics, 2001
J. Cohen, L. Markosian, R. Zeleznik, J. Hughes, and R. Barzel, 'An interface for sketching 3D curves,' ACM Symposium on Interactive 3D Graphics, pp. 17-21, 1999
B. Kerautret, X. Granier and A. Braquelaire, 'Intujtive Shape Modeling by Shading Design,' Proc. the 5th International Symposium on Smart Graphics, pp. 163-174, LNCS 3638, SpringerVerlag 2005
Y. Kho and M. Garland, 'Sketching mesh deformations,' Proceedings of the ACM Symposium on Interactive 3D Graphics, April 2005
T. Pavlidis, C. J. Van Wyk, 'An automatic beautifier for drawings and illustrations,' ACM SIGGRAPH Computer Graphics, Volume 19, Issue 3, pp. 225-234, July 1985
M. Shpitalni, H. Lipson, 'Classification of sketch strokes and corner detection using conic sections and adaptive clustering,' ASME Journal of Mechanical Design 119(2): 131-135, 1997
T. M. Sezgin and R. Davis. 'Handling Overtraced Strokes in Hand-Drawn Sketches,' In Making Pen-Based Interaction Intelligent and Natural. 2004
L.R. Williams, 'Perceptual Completion of Occluded Surfaces,' PhD dissertation, Dept. of Computer Science, University of Massachusetts, Amherst, Mass., 1994
L. Prasad, 'Morphological analysis of shapes,' CNLS Newsletter, 139: 1-18, July 1997
F. Cordier, O. Cheong, 'Delaunay triangulation of self-intersecting polygons,' technical report, CS Depts., 2005, KAIST
W. Wesselink. 'Variational Modeling of Curves and Surfaces,' PhD thesis, University of Technology, Eindhoven, 1996
L. Landau, E. Lifshitz, 'Theory of Elasticity,' Butterworth-Heinemann, Boston, Mass., 1995
C. Lawson and R. Hanson, 'Solving Least Squares Problems,' Englewood Cliffs, NJ: Prentice-Hall, 1974
Intel Math Kernel Library 8.0, http://www.intel.com, 2005
※ AI-Helper는 부적절한 답변을 할 수 있습니다.