루브 골드버그 기계의 합성을 위한 예제 기반 접근방법
이강훈
광운대학교 컴퓨터소프트웨어학과
[email protected]
An Example-Based Approach to the Synthesis of Rube Goldberg Machines
Kang Hoon Lee
Dept. of Computer Science, Kwangwoon University
요 약
본 논문은 물리 시뮬레이션 환경에서 일련의 강체 요소가 인과 사슬에 따라 연쇄적으로 구동되는 가상의 루브 골드버그 기계를 합성하기 위한 예제 기반 접근방법을 제안한다. 일련의 요소 집합이 주어졌을 때, 본 논문의 목표는 사용자가 명시한 이동의 시작 및 종료 위치, 그리고 경계 영역 조건을 만족하는 범위에서 이들 요소로만 구성된 루브 골드버그 기 계를 자동으로 구축하는 것이다. 이를 위하여, 먼저 적은 개수의 요소로 구성된 소규모 컴포넌트들을 무작위로 추출한 후 모든 컴포넌트 쌍에 대한 결합 가능성을 하나의 그래프 구조로 표현한다. 이 그래프 위에서의 경로 탐색을 통하여 공간 상에 펼쳤을 때 사용자가 지정한 요구 조건을 만족시키는 경로를 찾고, 해당 경로에 따라 순차적으로 컴포넌트를 조립함으로써 기계를 구축한다. 완성된 기계가 물리 시뮬레이션 환경에서 정확히 동작함을 보장하기 위하여, 끝으로 간단한 그리디 알고리즘을 적용하여 조립된 컴포넌트들의 위치를 정교하게 조절한다. 다섯 종류의 요소만을 이용하여 만든 다양한 구조의 루브 골드버그 기계를 보임으로써 본 논문에서 제안한 방법의 유용성을 보인다.
Abstract
We present an example-based approach to synthesizing physically simulated Rube Goldberg machines in which a series of rigid body elements are sequentially triggered and driven along the causal chain. Given a set of elements, our goal is to automatically instantiate and arrange those elements to meet the user-specified requirements including the start and end positions, and the boundary of movement. To do so, we first sample small-scale machines consisting of only a few elements randomly, and represent the connectivity between every pair of components as a graph structure. Searching over possible paths in this graph solves our problem by finding a path that can be unrolled to satisfy the given requirements, and then assembling components sequentially along the solution path. In order to ensure that the machine works precisely in a physically simulated environment, we finally elaborate the layout of assembled components by a simple greedy algorithm. We demonstrate the usefulness of our approach by displaying a large diversity of Rube Goldberg machines built with only five kinds of elements.
키워드: 컴퓨터 애니메이션, 강체 시뮬레이션, 예제 기반 합성, 루브 골드버그
Keywords: computer animation, rigid body simulation, example-based synthesis, Rube Goldberg
1. 서론
미국 태생의 만화가이자 발명가인 루브 골드버그 (Rube Gold- berg)는 아주 단순한 작업을 의도적으로 복잡하게 처리하는 기 계 장치를 표현한 일련의 만화 작품을 통하여 잘 알려져 있다.
예를 들어, ‘스스로 작동하는 냅킨’ (Self-Operating Napkin)이 라는 작품에서는 식사 중에 숟가락을 들어올려 입으로 가져 가면 이로 인하여 과자, 앵무새, 로켓, 시계추 등이 연쇄적으로 움직여서 최종적으로 냅킨이 입을 닦아주는 복잡하고 우스꽝
한국컴퓨터그래픽스학회 Vol. 20, No. 2, P. 25~32
스러운 장치를 선보이고 있다 [1]. 흔히 루브 골드버그 기계로 지칭되는 이러한 장치는 이후 많은 영화, 애니메이션, 게임 등 에 차용되면서 적지 않은 문화적 영향을 미쳤고, 오늘날 루브 골드버그 기계는 공학이나 예술 분야에서 지적 호기심을 자 극하고 창의성을 유도하는 교육적인 목적으로 활용되기도 한 다 [2].
본 논문은 컴퓨터 그래픽스 분야의 기술에 기초하여 가상 의 루브 골드버그 기계를 구성하고 그 움직임을 애니메이션 형식으로 합성하는 방법을 제시한다. 루브 골드버그 기계는 일련의 연쇄적 과정을 통하여 단순한 목표를 복잡한 방식으로 달성한다는 것 외에는 별다른 제약조건이 없으므로 잠재적으 로는 무한히 다양한 종류의 구성 요소와 결합 방식을 허용한 다. 예를 들어, 불, 물, 전자 회로, 심지어는 동물과 사람까지도 그 구성 요소가 될 수 있다. 이처럼 포괄적인 표현 범위를 제공 하는 하나의 일반화된 애니메이션 합성 방법을 도출하는 것은 매우 어려운 문제이다. 본 논문에서는 실용적인 범위 안에서 다양한 형태의 루브 골드버그식 애니메이션을 합성할 수 있 도록 하기 위하여, 보편적인 강체 시뮬레이션 기술에 의하여 움직임을 합성할 수 있는 다음 세 종류의 요소로만 구성된 루 브 골드버그 기계를 가정한다.
• 이동 요소 (mobile elements): 중력, 마찰력, 반작용력 등 물 리적인 외력에 의하여 수동적으로 이동하는 요소.
• 추진 요소 (driving elements): 움직이는 이동 요소에 힘을 가하여 그 속력과 방향을 변화시키는 요소.
• 촉발 요소 (triggering elements): 움직이는 이동 요소의 힘 을 멈춰있던 다른 이동 요소에 전달하여 연쇄 작용을 유 도하는 요소.
본 논문은 임의의 요소 집합이 주어졌을 때, 사용자가 움직 임의 시작과 종료 위치, 경계 영역 등의 제약 조건을 명시하 면 자동화된 과정을 통하여 이들 제약 조건을 충족하는 루브 골드버그 기계를 생성하는 문제를 해결하고자 한다. 완성된 루브 골드버그 기계에 대하여 강체 시뮬레이션을 실행하면, 먼저 시작 위치에 놓인 첫 번째 이동 요소가 움직임을 시작하 고, 이후 추진 요소와 촉발 요소를 통한 연쇄 작용이 일어나서 최종적으로는 마지막 이동 요소가 종료 위치에 도달하도록 할 것이다. 요소 간의 연쇄 작용은 접촉 시간이나 충돌 지점의 미 묘한 차이에 의하여서도 급격하게 변화할 수 있기 때문에, 미 리 정의된 닫힌 형태의 수식에 기초하여 절차적으로 기계를 합성하는 방식은 이 문제에 적용하기가 어렵다. 또한 이와 대 비되는 방법으로서, 제약 조건을 만족할 때까지 반복적으로 무작위적으로 요소들을 배치한 후 강체 시뮬레이션을 실행하 는 시행착오 방법은 그 탐색 공간의 엄청난 규모로 인하여 현 실적인 접근방법으로 보기 어렵다.
본 논문에서는 연쇄 작용의 예제에 해당되는 작은 규모의 부분적인 루브 골드버그 기계(이후 ‘컴포넌트’로 지칭)를 무
작위적으로 추출한 다음, 이들 예제를 결합하기 위한 절차적 규칙을 미리 식별하여 놓음으로써, 실행 시간에는 절차적 규 칙에 의하여 표현 가능한 제한된 탐색 공간 내에서 효율적으 로 사용자의 제약 조건을 만족시키는 해를 구하는 접근방법을 택한다. 본 논문에서 제안하는 방법의 전체 과정은 다음과 같 이 요약할 수 있다. 먼저 임의로 생성된 다수의 이동, 추진, 촉 발 요소에 대하여 물리 시뮬레이션을 수행한 후, 이동 요소와 상호작용하는 추진 혹은 촉발 요소를 파악함으로써 일련의 컴 포넌트들을 추출한다 (3장). 한 컴포넌트의 이동 요소 궤적이 다른 컴포넌트의 이동 요소 궤적과 부드럽게 연결될 수 있는 모든 컴포넌트 쌍에 대하여 연결 가능성을 표시하여 그래프 구조를 생성한다 (4장). 컴포넌트 조립 그래프를 공간 상에 전 개하여 기계를 구축하는 과정은 충돌 검사 등의 많은 계산 비 용을 요구하기 때문에, 보다 높은 효율성을 위하여 그래프의 각 노드에 대하여 미리 전개된 트리를 구성하고, 사용자가 명 시한 제약 조건을 만족하는 범위에서 이들 트리를 병합하여 나감으로써 루브 골드버그 기계를 생성한다 (5장). 컴포넌트 조립 그래프는 다소 간의 연결 오차를 허용하기 때문에, 최종 적으로 시뮬레이티드 어닐링 알고리즘에 기초하여 각 개체의 레이아웃을 미세하게 조정함으로써 제약 조건 및 요소 간의 연쇄 작용을 정밀하게 만족시키는 루브 골드버그 기계를 구 한다 (6장).
2. 관련 연구
컴퓨터 그래픽스 분야에서는 비교적 단순한 형상 혹은 동작의 예제들을 재조합하여 사용자 요구사항, 디자인 지침, 혹은 구 조적 제약조건 등에 부합되는 범위에서 새로운 모양과 움직임 을 합성하는 예제 기반 접근 방법이 활발히 연구되어 왔다. 특 히 예제 기반의 형상 합성은 2차원 이미지 [3, 4], 텍스처 [5, 6], 3차원 기하 형상 [7, 8], 그리고 건물, 도시, 인테리어 등을 위한 다수 3차원 객체의 배치 [9, 10] 등 여러 세부 응용 분야에서 꾸 준히 흥미로운 결과들을 만들어 왔다. 이들 연구가 주로 예제 의 공간적인 재배열에 기초하고 있다면, 비디오 편집 [11, 12], 캐릭터 애니메이션 [13, 14, 15], 군중 시뮬레이션 [16, 17] 등 시 계열 데이터를 다루는 응용 분야에서는 시간과 공간을 함께 고려하여 예제를 재배열하는 방법들이 개발되어 왔다. 본 연 구의 접근방법 역시 기계의 형상과 그에 따른 동작을 동시에 합성하기 위하여 기본적으로 이러한 예제의 시공간적 재배열 에 기초하고 있다.
본 논문의 주제와 가장 밀접하게 관련된 연구 결과로서, 조 형물, 장난감, 혹은 인형을 원하는 방식에 따라 제어하기 위 하여 기어나 크랭크, 캠 등의 요소들을 최적의 방식으로 조립 하여 자동으로 기계 장치를 구성하는 방법들이 최근 연달아 제시되고 있다 [18, 19, 20]. 하지만 이들 방법은 주로 요소들 이 직접 맞물린 상태에서 운동을 전달하는 기구학적 연쇄에 기초하고 있기 때문에, 루브 골드버그 기계에서 흔히 볼 수 있
그림 1: 본 연구의 실험에 사용된 경사로와 송풍기(상), 회전문 (중), 도미노(하) 등의 요소가 포함된 컴포넌트의 추출 과정.
는 동역학적 움직임과 충돌 반응에 의한 연쇄 작용을 합성하 는데 적합하지 않다. 본 연구는 물리 시뮬레이션을 이용하여 요소 간의 연쇄 작용을 무작위적으로 추출하여 예제 컴포넌 트들을 획득하고, 이들 컴포넌트 간의 연결 관계를 그래프 형 태로 표현한 후 탐색하는 방법을 통하여 사용자의 요구조건을 만족하는 루브 골드버그 기계를 효율적으로 생성하는 방법을 제시한다.
다수 강체의 상호작용이 개입된 복잡한 애니메이션의 대화 형 제어는 컴퓨터 애니메이션 분야에서 도전적인 문제의 하나 로 다루어져 왔다. Popovi´c 등은 수치적 최적화와 이산적 탐색 에 기초하여, 시뮬레이션을 통하여 획득된 다수 강체의 이동 궤적을 직접적으로 조작할 수 있는 대화형 기법을 제안하였 다 [21]. 또한 Twigg와 James는 다수 강체의 시뮬레이션 예제 들을 대규모로 추출한 후, 사용자가 편리한 대화형 질의 인터 페이스를 통하여 원하는 예제를 선택하고 수정하여 새로운 애 니메이션을 합성하는 방법을 제시하였다 [22]. 본 논문 역시 무 작위적으로 추출된 시뮬레이션 예제들을 활용한다는 점에서 이와 유사한 측면이 있지만, 비교적 제한된 주제인 다수 강체 의 연쇄작용에 초점을 맞추어 그래프 탐색에 기초한 효율적인 대화형 합성 알고리즘을 제시한다는 점에서 본 논문의 차별성 이 있다.
3. 컴포넌트 추출
본 논문에서 컴포넌트는 이동 요소의 궤적이 기록되어 있는 작은 규모의 루브 골드버그 기계로서 서로 간의 결합을 통하 여 보다 큰 규모의 기계를 구축하기 위한 기본 빌딩 블록이다.
구체적으로, 각 컴포넌트는 다음 세 가지 정보를 포함한다.
• 초기 상태: 컴포넌트에 포함된 모든 이동, 추진, 촉발 요소 의 목록과 각 요소의 초기 속성 (위치, 크기, 마찰력 등)
• 진입 궤적: 추진 혹은 촉발 요소와 처음으로 접촉하는 이 동 요소의 접촉 이전 궤적
• 진출 궤적: 추진 혹은 촉발 요소와 마지막으로 접촉하는 이동 요소의 분리 이후 궤적
서로 다른 초기 상태와 진입/진출 궤적을 갖는 많은 수의 컴 포넌트를 효과적으로 추출할 수만 있다면 그 구체적인 방법 에는 특별한 제약이 없다. 본 연구의 실험에서는 추진 요소를 통하여 이동 요소의 속도와 방향을 제어하는 컴포넌트, 그리 고 촉발 요소를 이용하여 두 이동 요소 간의 연쇄 작용을 매 개하는 컴포넌트를 별도의 방법으로 추출하였다. 두 종류의 컴포넌트 모두 아래에 기술된 바와 같이 자동화된 방식으로 추출할 수 있으므로, 일괄적인 반복 작업을 통하여 충분히 많 은 개수의 컴포넌트를 얻을 수 있었다.
추진 요소에 의한 이동 요소 제어 컴포넌트를 추출할 때에 는, 제한된 경계 영역 안에 여러 개의 추진 요소들과 하나의 이동 요소를 서로 중첩되지 않은 범위에서 무작위로 배치한 상태에서 강체 시뮬레이션을 실행하였다 (그림 1 (상)). 시뮬 레이션 과정에서, 이동 요소가 새로운 추진 요소와 접촉할 때 마다 이 두 요소로 구성된 새로운 컴포넌트를 추가한 후, 이전 추진 요소와 분리된 이후에 움직인 궤적을 진입 궤적, 다음 추 진 요소와 접촉하기 이전까지 움직인 궤적을 진출 궤적으로 기록하였다. 반면 촉발 요소에 의한 연쇄작용 매개 컴포넌트 를 추출할 때에는, 하나의 촉발 요소와 하나의 이동 요소를 고 정된 위치에 배치한 상태에서, 다른 하나의 이동 요소의 발사 위치와 방향을 바꿔가면서 연쇄 작용이 성공할 때까지 시뮬 레이션을 반복하였다 (그림 1 (중)과 (하)). 연쇄 작용이 성공적 으로 이루어지면 이들 세 요소로 이루어진 새로운 컴포넌트를 추가한 후, 발사된 이동 요소가 촉발 요소와 접촉하기 이전까 지 움직인 궤적을 진입 궤적, 고정된 이동 요소가 촉발 요소와 접촉한 이후 움직인 궤적을 진출 궤적으로 기록하였다.
4. 그래프 생성
임의의 두 컴포넌트에 대하여, 한 컴포넌트의 진출 궤적이 다 른 컴포넌트의 진입 궤적과 부드럽게 연결될 수 있도록 서로 간의 충돌 없이 배치할 수 있으면 이들 두 컴포넌트는 결합 가 능하다고 판단한다. 각 컴포넌트를 하나의 노드로 표현하고
결합 가능한 컴포넌트 쌍을 진출 컴포넌트로부터 진입 컴포 넌트로 향하는 방향성 에지로 연결하면 하나의 그래프 구조 로 전체 컴포넌트 서로 간의 결합 가능성을 나타낼 수 있다.
일단 이러한 그래프를 생성하고 나면, 그래프 상의 경로에 따 라서 컴포넌트를 결합하여 점층적으로 루브 골드버그 기계를 확장할 수 있고, 나아가서 그래프 경로의 탐색을 통하여 제약 조건을 만족하는 루브 골드버그 기계를 구축할 수 있다. 임의 크기의 기계를 합성할 수 있도록 하기 위하여, 완성된 그래프 로부터 강연결 요소들 (strongly connected components)을 식별 하고 그 중 가장 큰 규모의 요소만 남겨둔다.
한 컴포넌트 P 로부터 다른 컴포넌트 Q로의 결합 가능성을 판단하기 위하여 먼저 P 의 진출 궤적에 속한 한 지점과 Q의 진입 궤적에 속한 한 지점 간의 위치 및 속도 차이가 임계 범 위 이내에 속하도록 만들 수 있는 Q의 평행 이동 T (∈ R
2
)가 존재하는지 여부를 확인한다. 이 첫 번째 검사를 통과할 경우, 다음으로 P 에 속한 모든 요소 및 진출 궤적이 평행 이동된 Q 에 속한 모든 요소 및 진입 궤적과 중첩되지 않는지 추가적 으로 확인한다. 이 두 번째 검사까지 통과하면 컴포넌트 Q를 컴포넌트 P 로부터 T만큼 이동시켜서 결합할 수 있는 것으로 판단한다. 이때 위치와 속도 차이의 임계 범위가 충분히 작다 면, P 와 Q를 결합한 기계에 대하여 강체 시뮬레이션 적용시 처음에 P 의 진입, 진출 궤적에 따라 움직이던 이동 요소는 자 연스럽게 Q의 진입, 진출 궤적으로 연결되어 움직일 가능성이 높다.모든 컴포넌트 쌍에 대하여 진입/진출 궤적의 각 지점 간 위 치와 속도 차이를 일일이 계산하는 것은 비록 전처리 과정이 라 하여도 매우 많은 계산 시간을 필요로 한다. 본 논문에서는 전처리 시간을 단축하기 위한 방법으로서, 먼저 이동 궤적에 서 나타나는 속도 데이터를 제한된 개수의 군집으로 분류한 후 궤적 간 연결 가능성을 판단할 때에는 간단히 소속 군집의 동일성만을 판단하는 근사적인 방법을 사용한다. 모든 진입/
진출 궤적의 각 지점마다 속도를 계산하여 이를 속력과 방향 성분으로 분리하여 별도의 집합 {s
1
, s2
,· · · }와 {θ1
, θ2
,· · · }를 얻는다. 이 두 집합에 대하여 별도로 K-평균 군집화 알고리 즘을 적용하여 미리 정해진 개수의 군집으로 분류한다. 이 때, 속력 집합에 속한 임의의 두 원소 si
와 sj
에 대하여 ds
(si
, sj
) =|s
i
− sj
|2
,방향 집합에 속한 임의의 두 원소 θi
와 θj
에 대하여 da
(θi
, θj
) = arccos((cos θi
, sin θi
) · (cos θj
, sin θj
))의 거리 함수 를 사용한다.일단 분류가 이루어지고 나면, 특정 궤적의 속도 정보는 속 력 및 방향 군집의 번호쌍 집합 V = {(ˆs
1
, ˆa1
), (ˆs2
, ˆa2
), · · · }으 로 표현할 수 있다. 임의의 두 컴포넌트 P 와 Q가 주어지면, P 의 진출 궤적에 해당되는 속도 집합 VP
와 Q의 진입 궤적에 해 당되는 속도 집합 VQ
간의 교집합을 계산함으로써 신속하게 결합 가능성을 검사할 수 있다. 교집합이 공집합인 경우에는 두 컴포넌트는 결합 불가능한 것으로 판정한다. 그렇지 않은 경우에는, 각각의 대응되는 지점 쌍에 대하여 두 지점이 일치그림 2: 그래프의 특정 노드로부터 최대 깊이 3의 범위까지 미 리 전개된 트리의 두 가지 예시. 회색 곡선들은 각 노드에 포함 된 진입, 진출 궤적을 나타내고, 각 트리마다 대표적으로 하나 의 경로에 대응되는 컴포넌트들이 표시되어 있다.
하도록 Q를 T만큼 평행 이동시킨 후 충돌 여부를 검사하여 최종적인 결합 가능성을 판정한다. 두 컴포넌트 P 와 Q가 결 합 가능할 경우, 대응되는 두 노드를 평행 이동 T가 기재된 방향성 에지로 연결한다.
5. 기계 합성
컴포넌트 조립 그래프의 한 노드를 선택하여 첫 번째 컴포넌트 를 생성하고, 이후 반복적으로 인접 노드 중 하나를 선택하여 이전 컴포넌트와의 평행 이동 관계에 부합하도록 배치하는 방 식으로 루브 골드버그 기계를 점차 확장한다. 그래프 노드를 n으로 표현하면, 현재까지 확장된 루브 골드버그 기계는 하나 의 그래프 경로 (n
1
→ n2
→ · · · → nk
)에 대응된다. 여기에서 nk
의 인접 노드 중 하나인 nk+1
을 경로의 마지막에 추가하기 위하여서는, nk+1
의 컴포넌트가 이전 노드들인 n1
,· · · , nk
의 컴포넌트들과 서로 충돌하지 않음이 보장되어야 한다. 그래프 생성 단계에서 서로 인접한 두 노드 nk+1
과 nk
간의 충돌 방지 는 보장하고 있지만, 나머지 (k − 1)개 노드와의 충돌 여부는 미리 확인되지 않았으므로 이를 경로 확장 단계에서 검사할 필요가 있다. 이러한 충돌 검사는 매우 많은 계산 비용을 요구 하기 때문에, 경로 탐색 과정에서 매번 이 작업을 수행하여야 한다면 대화형 조작을 가능케 할 만한 짧은 반응 시간을 제공 하기 어렵다.실행 시간의 충돌 검사를 최소화하기 위한 방법으로서, 본 논문은 그래프의 각 노드로부터 제한된 깊이까지 가능한 모 든 미충돌 경로를 미리 트리 형태로 전개하여 놓은 후, 실행 시간에는 원본 그래프 대신 이들 트리를 이용하여 경로를 탐 색하고 확장하도록 한다 (그림 2). 그래프 전개는 그래프 상
의 한 노드에 대응되는 트리의 루트 노드 t
root
를 원점에 배치 하는 것으로 시작한다. 이후 반복적으로, 가장 최근에 추가된 각 트리 노드 tcurr
마다 그래프 상에서 그와 인접한 모든 노 드 {t1 next
,t2 next
,· · · }를 tcurr
와 결합될 수 있도록 공간적으로 배치하고, 배치 후 기존 트리와 충돌하지 않을 경우에만 자식 노드로서 추가하여 트리를 확장한다. tcurr
의 위치를 p라고 할 때, 한 인접 노드 tnext
의 위치는 그래프에서 두 노드를 연결하 는 에지에 기재된 평행 이동 T만큼 이동된 (p + T)로 계산한 다. 또한 tnext
의 충돌 여부는 그 노드의 요소 및 진출 궤적이 그로부터 루트 노드까지 거슬러 올라가는 경로에 포함된 각 노드의 요소 및 진입 궤적과 중첩되는지 여부를 검사하여 판 단한다.사용자가 움직임의 시작 위치 p
s
와 종료 위치 pe
,그리고 경 계 영역 R을 지정하면, 미리 전개된 트리 중 하나를 임의로 선 택하여 그 루트 노드의 진입 궤적 시작 지점이 ps
에 놓이도록 배치한 후, pe
와의 거리가 충분히 가까운 트리 노드가 발견되 거나 혹은 더 이상 확장이 불가능할 때까지 새로운 트리를 반 복적으로 병합한다 (그림 3). 기존 트리에 포함된 모든 노드가 pe
와 임계값 이상의 거리만큼 떨어져 있다면, 그 중 pe
에 가장 가까운 리프 노드를 선택하고 해당 그래프 노드로부터 전개 된 트리를 그 자식 트리로서 병합한다. 그렇지 않고 pe
로부터 임계값 미만의 거리만큼 떨어진 트리 노드 tnear
가 발견되었 다면, 트리의 루트 노드로부터 해당 노드까지 연결되는 경로 (troot
→ · · · → tnear
)를 해답으로 선택한다. 트리 생성과 병 합 과정에서는 모두 깊이 우선 탐색 순서로 노드를 배치하고, 매번 새로운 노드가 R 외부에 놓이거나 혹은 기존 트리에 속 한 요소 및 경로와 중첩될 때에는 미리 가지치기하여 그 후손 노드들을 더 이상 배치하지 않고 넘어감으로써 트리에 속한 노드가 경계 영역을 벗어나거나 충돌을 일으키지 않도록 보 장한다. 해를 찾지 못한 상태에서 더 이상 트리를 확장할 수 없는 경우에는 탐색이 실패한 것으로 판단하고, 사용자로 하 여금 새로운 제약 조건을 제시하도록 한다 (그림 3 (우)).6. 배치 정교화
그래프 탐색을 통하여 획득된 경로에 따라 컴포넌트를 배치 하면 하나의 루브 골드버그 기계가 구축되지만, 그래프 생성 과정에서 이미 다소 간의 오차를 허용하고 있기 때문에 이 기 계가 사용자 제약 조건의 충족을 완전하게 보장하지는 않는 다. 따라서 그래프 탐색 결과로 생성된 루브 골드버그 기계를 최종 해가 아닌 그와 매우 가까운 초기 추측으로 간주하고, 이 로부터 각 요소의 위치를 정교하게 수정하는 최적화 과정을 통하여 최종적인 루브 골드버그 기계를 완성시킨다.
최적화 과정은 첫 번째 컴포넌트부터 마지막 컴포넌트까지 순차적으로 진행하고, 각 컴포넌트에 대하여 물리 시뮬레이 션에 의한 이동 궤적과 컴포넌트에 기록된 이동 궤적 간의 오 차를 평가하여 그 오차가 임계값 미만에 도달할 때까지 소속
요소들의 위치를 미세하게 조절하여 오차를 최소화하는 이동 궤적을 얻는다. 구체적으로, 이전 컴포넌트까지 최적화된 이 동 궤적을 (p
1
,p2
,· · · , pf
)라고 할 때, 이번 컴포넌트의 차례 에는 pf−1
지점에서(p
f−p Δt
f−1)
의 속도로 이동 요소를 발사한 후 (Δt는 시분할 간격), 일정 시간 동안의 추가적인 이동 궤적 (pf+1
,· · · pf+T
)가 컴포넌트에 기록된 진출 궤적의 종료 지점 과 얼마나 가까워지는지 다음 오차 식에 의하여 측정한다.E = min
t=1,··· ,T
||p
f+t
− pend
||2
+ ||vf+t
− vend
||2
(1)여기에서 p
end
와 vend
는 각각 진출 궤적의 마지막 위치 및 속도를 나타낸다. 오차 E의 값이 임계값보다 작다면, 해당 오 차를 얻은 시점 ˆt까지의 이동 궤적 (pf+1
,· · · , pf+ˆt
)을 최적화 된 이동 궤적에 추가하고 다음 컴포넌트로 넘어간다. 그렇지 않다면, 소속 요소의 위치를 제한된 범위 안에서 무작위 변위 만큼 이동시킨 후 이동 요소 발사 및 오차 측정을 다시 시행 한다. 임계값보다 작은 오차를 얻기 전까지, 매 시행마다 이전 보다 오차가 증가하면 소속 요소를 이전 위치로 복귀시킨 뒤 다시 그 위치로부터 무작위 변위만큼 이동시킨다. 미리 정해 진 횟수만큼의 반복적 위치 수정에도 불구하고 오차가 여전히 임계값보다 클 경우에는 최적화가 실패한 것으로 판단하고 실 행을 중단한다.위의 최적화 과정에서 첫 번째 컴포넌트와 마지막 컴포넌트 에 대하여서는 예외적으로 고려할 사항이 있다. 첫 번째 컴포 넌트의 경우, 이전까지 최적화된 이동 궤적이 없는 상태에서 시작하기 때문에 이동 요소의 초기 위치 및 속도는 진입 궤적 의 시작 지점에서와 동일하게 부여한다. 또한 마지막 컴포넌 트의 경우에는, 진출 궤적의 종료 위치 및 속도 대신 사용자가 명시한 종료 위치와만 비교하여 오차를 산출한다. 중간 과정 의 컴포넌트들은 다음 컴포넌트로의 전이를 보장하기 위하여 위치뿐 아니라 속도까지 함께 고려하여 오차를 계산하지만, 마지막 컴포넌트에서는 단순히 종료 위치까지의 도달만 보장 하면 되기 때문이다.
7. 실험 결과
본 연구의 실험에서는 한 가지 종류의 이동 요소와 두 가지 추진 요소, 그리고 두 가지 촉발 요소의 총 5가지 요소를 사용 하였다 (그림 1). 하나의 기계에는 이들 각각의 요소마다 서로 다른 속성을 가진 여러 개의 개체가 포함될 수 있다. 예를 들어, 추진 요소의 하나인 경사로는 길이, 기울기, 마찰력, 탄성계수 등 4개의 속성을 가지며, 각 경사로 개체는 제한된 범위 안에 서 이들 속성의 값을 자유롭게 가질 수 있다. 추진 요소가 포함 된 컴포넌트 1071개, 촉발 요소가 포함된 컴포넌트 250개를 무 작위적으로 추출하였고, 이들 컴포넌트의 진입/진출 궤적에서 관찰된 속도 정보를 72개의 속력 군집과 72개의 방향 군집으
그림 3: 사용자가 명시한 제약 조건을 만족하는 그래프 탐색 결과의 예시. 빨간 색과 파란 색 원은 각각 이동의 시작 및 종료 지점을 나타낸다. 왼쪽 두 개의 결과는 탐색에 성공한 경우, 가장 오른쪽의 결과는 탐색에 실패한 경우를 보이고 있다.
로 분류하였다. 속력 및 방향 군집에 기초하여 컴포넌트 간의 결합 가능성을 나타내는 그래프를 생성한 후, 그 중 가장 큰 강 연결 요소만을 남겨둔 결과 721개의 노드와 9329개의 에지가 확보되었다. 전처리 과정의 마지막 단계로서, 그래프에 포함 된 모든 노드에 대하여 최대 깊이 3의 범위까지 미리 전개하여 일련의 트리를 생성하였다 (그림 2).
미리 전개된 트리를 이용한 기계 합성 과정은 대화형 인터 페이스를 통하여 실시간으로 이루어진다. 실험의 편의상 경 계 영역 및 시작 위치는 고정하였고, 사용자는 원하는 위치에 서 마우스를 클릭하여 종료 위치를 지정할 수 있도록 하였다.
종료 위치가 지정될 때마다 수 초 정도의 시간 동안 경로 탐 색이 진행되고, 최적의 경로가 발견되면 해당 경로에 따라서 배치된 컴포넌트들이 화면에 표시된다. 종료 위치에 임계값 이하로 가깝게 도달할 수 있는 경로를 발견하지 못할 경우, 경 로 탐색에 실패하였음을 알린다. 짧은 경로 탐색 시간 덕분에 사용자는 컴포넌트를 조합할 수 있는 여러 가능성을 탐색하면 서 원하는 기계를 선택할 수 있다. 또한 선택된 기계에 대하여 배치 정교화 과정을 수행함으로써 강체 시뮬레이션 환경에서 정확히 동작하는 기계를 얻을 수 있다 (그림 4).
8. 결론 및 향후 연구
본 논문은 강체 요소 간의 물리적 연쇄 작용에 기초한 루브 골 드버그 기계를 합성할 수 있는 예제 기반 접근방법을 제시하였 다. 소규모 기계에 해당되는 컴포넌트의 무작위 추출, 컴포넌 트 간의 결합 관계에 기초한 그래프 생성, 미리 전개된 트리의 반복적 병합을 통한 경로 탐색, 끝으로 정확한 기계 작동을 보 장하기 위한 요소 배치의 정교화가 그 구체적인 과정으로서 포함된다. 제약 조건을 명시하면 그 결과로서 생성된 기계를 즉각적으로 확인할 수 있는 대화형 인터페이스를 통하여, 사 용자는 다양한 규모와 복잡도를 가지는 루브 골드버그 기계를
짧은 시간 안에 편리한 방식으로 만들 수 있음을 확인하였다.
본 논문에서 제안한 방법은 다음과 같은 몇 가지 한계점을 가지고 있다. 우선, 컴포넌트의 추출과 연결, 경로 탐색 등 본 논문에서 기술한 절차는 모두 2차원 시뮬레이션 환경을 가정 하고 있다. 단순히 3차원 형태와 동작을 지원하도록 이들 절차 를 확장하는 것은 그리 어려워 보이지 않지만, 새롭게 추가된 차원에 따른 탐색 공간의 확대는 보다 많은 예제와 보다 긴 탐 색 시간을 필요로 할 것이다. 또한, 본 연구의 실험에서는 추진 요소나 촉발 요소에 대하여서는 여러 종류와 다양한 속성을 허 용하는 반면, 이동 요소는 그 속성이 고정된 한 가지 종류로만 제한하고 있다. 여러 종류의 이동 요소를 허용할 경우, 각각에 대하여 추진 혹은 촉발 요소와 상호작용하는 컴포넌트를 별 도로 추출하여야 하고 이는 역시 필요한 예제의 개수 및 탐색 시간을 증가시키는 요인이 된다. 이들 한계점은 공통적으로 정보의 매개화, 근사화 등 예제 데이터를 보다 압축적으로 표 현할 수 있는 방법을 도입함으로써 어느 정도 극복할 수 있을 것으로 예상한다. 나아가서, 본 연구의 결과를 다수 3차원 개 체가 개입된 복잡한 상호작용의 제어 방법으로 확장하는 것은 향후 주된 연구 방향의 하나이다.
감사의 글
이 논문은 2012년도 광운대학교 교내학술연구비 지원에 의하 여 수행된 연구임. 또한 이 논문은 2012년도 정부(교육과학기 술부)의 재원으로 한국연구재단의 지원을 받아 수행된 연구임 (NRF-2010-0012759).
참고 문헌
[1] M. F. Wolfe, Rube Goldberg: Inventions! Simon & Schuster, 2011.
그림 4: 경로 탐색과 배치 정교화를 거쳐 생성된 최종 루브 골드버그 기계의 몇 가지 예시.
[2] Y. Kim and N. Park, “Development and application of steam teaching model based on the rube goldberg’s invention,” in Computer Science and its Applications, 2012, vol. 203, pp.
693–698.
[3] T. Ijiri, R. Mˆech, T. Igarashi, and G. Miller, “An example- based procedural system for element arrangement,” Com- puter Graphics Forum, vol. 27, no. 2, pp. 429–436, 2008.
[4] M.-M. Cheng, F.-L. Zhang, N. J. Mitra, X. Huang, and S.-M.
Hu, “Repfinder: Finding approximately repeated scene ele- ments for image editing,” ACM Trans. Graph., vol. 29, no. 4, pp. 83:1–83:8, 2010.
[5] Y. Liu, W.-C. Lin, and J. Hays, “Near-regular texture analysis and manipulation,” ACM Trans. Graph., vol. 23, no. 3, pp.
368–376, 2004.
[6] C. Ma, L.-Y. Wei, and X. Tong, “Discrete element textures,”
ACM Trans. Graph., vol. 30, no. 4, pp. 62:1–62:10, 2011.
[7] T. Funkhouser, M. Kazhdan, P. Shilane, P. Min, W. Kiefer, A. Tal, S. Rusinkiewicz, and D. Dobkin, “Modeling by exam- ple,” ACM Trans. Graph., vol. 23, no. 3, pp. 652–663, 2004.
[8] Y. Zheng, D. Cohen-Or, and N. J. Mitra, “Smart variations:
Functional substructures for part compatibility,” Computer Graphics Forum, vol. 32, no. 2pt2, pp. 195–204, 2013.
[9] P. M¨uller, G. Zeng, P. Wonka, and L. Van Gool, “Image- based procedural modeling of facades,” ACM Trans. Graph., vol. 26, no. 3, 2007.
[10] L.-F. Yu, S.-K. Yeung, C.-K. Tang, D. Terzopoulos, T. F.
Chan, and S. J. Osher, “Make it home: Automatic optimiza- tion of furniture arrangement,” ACM Trans. Graph., vol. 30, no. 4, pp. 86:1–86:12, 2011.
[11] A. Sch¨odl, R. Szeliski, D. H. Salesin, and I. Essa, “Video textures,” in Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, 2000, pp.
489–498.
[12] A. Agarwala, K. C. Zheng, C. Pal, M. Agrawala, M. Cohen, B. Curless, D. Salesin, and R. Szeliski, “Panoramic video tex- tures,” ACM Trans. Graph., vol. 24, no. 3, pp. 821–827, 2005.
[13] J. Lee, J. Chai, P. S. A. Reitsma, J. K. Hodgins, and N. S.
Pollard, “Interactive control of avatars animated with human
motion data,” ACM Trans. Graph., vol. 21, no. 3, pp. 491–
500, 2002.
[14] K. H. Lee, M. G. Choi, and J. Lee, “Motion patches: Building blocks for virtual environments annotated with motion data,”
ACM Trans. Graph., vol. 25, no. 3, pp. 898–906, 2006.
[15] M. Kim, Y. Hwang, K. Hyun, and J. Lee, “Tiling motion patches,” in Proceedings of the ACM SIG- GRAPH/Eurographics Symposium on Computer Animation, 2012, pp. 117–126.
[16] T. Kwon, K. H. Lee, J. Lee, and S. Takahashi, “Group motion editing,” ACM Trans. Graph., vol. 27, no. 3, pp. 80:1–80:8, 2008.
[17] B. Yersin, J. Ma¨ım, J. Pettr´e, and D. Thalmann, “Crowd patches: Populating large-scale virtual environments for real- time applications,” in Proceedings of the 2009 Symposium on Interactive 3D Graphics and Games, 2009, pp. 207–214.
[18] L. Zhu, W. Xu, J. Snyder, Y. Liu, G. Wang, and B. Guo,
“Motion-guided mechanical toy modeling,” ACM Trans.
Graph., vol. 31, no. 6, pp. 127:1–127:10, 2012.
[19] S. Coros, B. Thomaszewski, G. Noris, S. Sueda, M. For- berg, R. W. Sumner, W. Matusik, and B. Bickel, “Computa- tional design of mechanical characters,” ACM Trans. Graph., vol. 32, no. 4, pp. 83:1–83:12, 2013.
[20] D. Ceylan, W. Li, N. J. Mitra, M. Agrawala, and M. Pauly,
“Designing and fabricating mechanical automata from mocap sequences,” ACM Trans. Graph., vol. 32, no. 6, pp. 186:1–
186:11, 2013.
[21] J. Popovi´c, S. M. Seitz, M. Erdmann, Z. Popovi´c, and A. Witkin, “Interactive manipulation of rigid body simula- tions,” in Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, 2000, pp.
209–217.
[22] C. D. Twigg and D. L. James, “Many-worlds browsing for control of multibody dynamics,” ACM Trans. Graph., vol. 26, no. 3, 2007.
<저 자 소 개 >
이강훈
․2000년 서울대학교 컴퓨터공학과 학사
․2002년 서울대학교 컴퓨터공학부 석사
․2007년 서울대학교 컴퓨터공학부 박사
․2008년~2013년 광운대학교 컴퓨터소 프트웨어학과 조교수
․2014년~현재 광운대학교 컴퓨터소프 트웨어학과 부교수
․관심분야: 컴퓨터 애니메이션, 휴먼 컴퓨터 인터페이스, 컴퓨터 게임
