한국컴퓨터그래픽스학회 Korea Computer Graphics Society Vol. 24, No. 2, P.11~20 액체시뮬레이션의얇은특징을빠르게표현하기위한 CPU 와 GPU 이기종컴퓨팅기술 김종현 강남대학교 jonghyunkim@kangnam.ac.kr A CPU and GPU Heterogeneous Computing Techniques for Fast Representation of Thin Features in Liquid Simulations Jong-Hyun Kim Kangnam University 요약 우리는유체의얇은막을명시적으로표현하고보존할수있는 CPU GPU 이기종컴퓨팅기반의유체시뮬레이션기법을소개한다. 본논문에서가장큰기여는얇은유체표면에서쪼개지거나밀도가높은지점에서붕괴되어유체표면에나타나는 Hole을방지하는입자기반프레임워크를 GPU를활용한다는것이다. 유체표면을추적하는기존의방법과는달리, 제안된프레임워크는 CPU GPU 프레임워크상에서수치적확산이나꼬임문제없이안정적으로토폴로지변화를처리할수있다. 얇은표면의특징은이방성커널 (Anisotropic kernel) 과주성분분석 (Principal component analysis; PCA) 을 GPU상에서수행하여유체의방향성을빠르게찾고, 새로운유체입자의위치를결정하기위해계산하는, 후보위치추출과정의효율성을 CPU GPU 이기종컴퓨팅기술기반으로빠르게계산한다. 제안된알고리즘은직관적으로구현되며, 병렬화가쉽고시각적으로디테일한액체의얇은표면을빠르게애니메이션할수있다. Abstract We propose a new method particle-based method that explicitly preserves thin liquid sheets for animating liquids on CPU GPU heterogeneous computing framework. Our primary contribution is a particle-based framework that splits at thin points and collapses at dense points to prevent the breakup of liquid on GPU. In contrast to existing surface tracking methods, the our method does not suffer from numerical diffusion or tangles, and robustly handles topology changes on CPU GPU framework. The thin features are detected by examining stretches of distributions of neighboring particles by performing PCA(Principle component analysis), which is used to reconstruct thin surfaces with anisotropic kernels. The efficiency of the candidate position extraction process to calculate the position of the fluid particle was rapidly improved based on the CPU GPU heterogeneous computing techniques. Proposed algorithm is intuitively implemented, easy to parallelize and capable of producing quickly detailed thin liquid animations. 키워드 : 이기종컴퓨팅, 액체의얇은막, 유체시뮬레이션, 표면추적 Keywords: Heterogeneous computing, Thin sheets of liquid, Fluid simulation, Surface tracking *corresponding author: Jong-Hyun Kim/Kangnam University(jonghyunkim@kangnam.ac.kr) Received : 2017.12.09./ Review completed : 1st 2018.02.14. / Accepted : 2018.04.30. DOI : 10.15701/kcgs.2018.24.2.11 ISSN : 1975-7883(Print)/2383-529X(Online) - 11 -
1. 서론 2. 관련연구 유체와고체의상호작용으로부터표현되는디테일한유체의난류를표현하는것은물리기반시뮬레이션분야에서핫이슈이다. 특히, 난류를포함하는유체를애니메이션할때세밀한디테일을생성하고표현하는것은굉장히중요한부분이다. 이문제를개선하기위해많은기법들이제안되어왔다. 물리기반 [1, 2, 3], 노이즈와텍스쳐기반 [4, 5, 6] 기법들은유체시뮬레이션분야에서꾸준히소개되어왔다. 적응형격자와멀티그리드방법들은유체시뮬레이션에서다양하게표현되는난류흐름을모델링하기위해널리사용되었다 [7, 8, 9]. 더높은해상도를갖는격자공간에서 Navier- Stokes 방정식을풀어냄으로써작은디테일의와류현상을일시적으로표현할수있다. 그러나와류가고해상도격자공간에서부터멀어지면그디테일한움직임을보존하기어려워진다. 이러한문제를해결하여작은난류의움직임까지표현하고자, 격자가아닌입자들을이용하여와류를표현하는하이브리드프레임워크기법들이소개되어왔다 [10, 11]. Muller et al. 가제안한 SPH(Smoothed particle hydrodynamics) 기법 [12] 이후로입자기반시뮬레이션분야는많은발전이있었다 [13, 14, 15]. 기존의입자기반방법은거품이나스플래시애니메이션에는적합하지만스프링력 (Spring force) 으로인한진동문제가발생하기때문에얇은유체의특징을표현하기에는충분하지못하다. 격자 입자하이브리드접근법들이많이제안되었지만유체의얇은특징을표현하기에는충분하지않으며 [16, 17, 18], 격자의해상도나입자의개수를많이사용하여표현될수있는접근법또한큰계산량을요구하기때문에실제로유용하게사용되지않는다. 본논문에서는액체의얇은특징을보존하는새로운입자기반 CPU GPU 이기종프레임워크를소개한다. 제시된방법을사용하면유체표면의추적뿐만아니라얇은표면이사라지는부분을찾아내고새로운입자를추가하거나삭제할수있다. 우리는 Particle-in-cell(PIC)/Fluid-implicit-particle(FLIP) 방법을기반유체해법으로사용하며, 결과적으로입자기반유체시뮬레이션에서표현되는얇은유체의특징을캡처하는 CPU GPU 이기종프레임워크이다 ( 그림 1 참조 ). 얇아서소실되는액체의표면은새로운유체입자를추가하여보존하고, 추가된입자는유체의얇은특징이추출될수있는부분이아닌곳 ( 예 : Deep water 영역 ) 에들어가면제거된다. 본연구는 Yu and Turk 이제안한이방성커널방법에영향을많이받는다 [19]. 이방법은주변입자들의위치를이용하여 PCA를수행하고, 결과적으로날카롭고매끄러운유체표면을복원하기위해입자의신축 (Stretch) 과방향 (Orientation) 을계산한다. 우리는 GPU 기반솔루션을활용하여 PCA를수행하고 [20], 유체입자를삽입할지여부를결정하는기준으로이신축값을사용한다. 액체의최신표면추적기술은두가지접근방식으로분류할수있다 : Implicit 방법과 Explicit 방법. Osher and Sethian [21] 이제안한 Level-set 방법은가장널리사용되는 Implicit 방법중하나이다. Level-set 방법에서는각그리드노드에서가장가까운표면위치로부터거리함수를계산하고, 거리값이 0 인곳에서암시적 (Implicit) 으로표면을정의한다. 이방법은그동안다양한측면에서개선되고수정되었다. Enright et al. [22], Wang et al. [23], and Mihalef et al. [24] 은 Lagrangian 입자를배치하여수치적손실을막았다. Bargteil et al. 은정확한유체의표면을추적하기위해복원된표면메쉬로부터부호거리장을업데이트하는방법을제안했다 [25]. Heo and Ko는스펙트럼으로정제된 Level-set과고차재초기방법 (High-order reinitialization) 으로유체표면의디테일을보존했다 [26]. 위와같은 Implicit한방법을고해상도격자에서풀게되면전반적인유체의디테일을높일수있다. 그러나이러한접근법을활용하여도유체의얇은막과같은특징을캡처하기에는충분하지않다. Explicit한접근법중 Hirt and Nichols [27] 는전체셀에대해서유체의비율을이용하는 Volume of fluid(vof) 기법을제안하여불연속적인인터페이스를효율적으로표현하였다. 좀더다른방향으로는지난수십년동안의료영상분석및유체역학과같은다양한연구분야를통해다양한메쉬기반 (Meshbased) 표적추적기법들이제안되었다 [28, 29, 30]. 일반적으로메쉬기반표면추적기법에서는메쉬의정점과같은명시적인표면요소들을유체의흐름에따라이류시킨다. 그러나, 이방법은자기교차 (Self-intersection) 나복잡한토폴리지 (Complex topology) 변형은어렵기때문에일반적으로자주쓰이는방법은아니다. 이러한문제는인접한격자위치를재검색하여다시샘플링함으로써해결할수있지만, 이전략은여러복잡한상황을모두고려해야하기때문에알고리즘을복잡하게만든다. 입자기반접근법은 Explicit 접근법처럼메쉬의정점을보유하지않고오직입자를이용하여유체의표면을표현하기때문에알고리즘측면에서도복잡하지않다. SPH 방법 [12, 31, 32], Moving particle semi-implicit(mps) 방법 [33, 34], Meshless 물리기반시뮬레이션 [35, 36, 37] 과같은입자기반방법들은일반적으로물리기반시뮬레이션뿐만아니라유체의표면을복원하는데에도종종사용되곤한다. Blinn [38], Zhu and Bridson [17], Adams et al. [39], Yu and Turk [19] 는 Point cloud 로부터좀더정확하게표면을복원할수있는방법을제안했다. 본논문에서활용하는분할가능한 (Splittable) 입자기반접근법은적응형입자방법의범주에속한다. 우리방법과이방법의가장큰차이점으로는유체의얇은막과같은특징을지속적으로유지할수있도록제작된반면, 다른하나는입자의크기를다르게하여샘플링함으로써유체의시각적인디테일을유지하면서계산비용을줄이는것이다. - 12 -
(a) Particle-based fluids (b) Our method Figure 1: Water splash by our method with CPU-GPU heterogeneous framework. Right two columns in (b): A visualized splash with particles. A thin surface generated by GPU-based anisotropic kernels. 3. 제안하는프레임워크 제안하는방법에서는 FLIP [17, 40] 기반의 3차원유체입자들을이용하여유체의얇은특징을생성하고유지하는최적화된 CPU GPU 이기종프레임워크이며, 이알고리즘은아래와같은순서로수행된다. Step1:[GPU] 유체입자의밀도계산, 표면입자추출 Step2:[GPU] 입자의방향성계산, 유체입자의 Pair 찾기, 새롭게추가될유체입자의후보위치추출 Step3:[CPU Parallel] 후보위치최적화 Step4:[CPU Serial] 새로운유체입자추가및삭제 Step5:[GPU] 수치적행렬해법을이용한압력계산 Step6:[CPU Parallel] 유체입자의이류 Step7:[GPU] 유체표면복원 1 r 2 /h 2, 0 r h, W smooth (r,h)= 0, otherwise. 위수식들을사용하여계산된공분산행렬 C i 와 SVD(Singular value decomposition) 를이용하여입자의분포에대한고유벡터와고유값을계산한다. 이값으로부터인접입자사이의스트레칭과방향성을추출한다. C i = e T 1 e T 2 e T 3 T σ 1 σ 2 σ 3 e T 1 e T 2 e T 3 (3), (4) 3.1 이기종프레임워크를이용한액체의얇은막유지기법 3.1.1 얇은 (Thin) 입자추출 제안하는방법은유체의막을유지할수있는 Ando의방법을기반으로한다 [40]. 먼저이방성커널을사용하여입자들의분포를분석한다. 입자의방향성을추출하기위해우선다음과같이입자마다가중치평균공분산 C i 를계산한다 ( 수식 1 참조 ). Figure 2: Pseudo code for computation of particle density in GPU. j C i = (p j p i )(p j p i ) T W smooth (p j p i,α 1 d 0 ) j W, (1) smooth(p j p i,α 1 d 0 ) 여기에서 d 0 는유체입자들사이의초기거리값이며, α 1 은초기거리값 d 0 을조절하는변수이다. j p i = p jw smooth (p j p i,α 1 d 0 ) j W smooth(p j p i,α 1 d 0 ), (2) Figure 3: Pseudo code for computation of covariance matrix and singular value decomposition in GPU. 여기서 e n 은분산에의해추출된주축성분을나타내며 σ n - 13 -
Figure 4: Selected thin particles from water particles (thin particles are colored violet and lie on the outer edge of the fluid body). 는스트레칭정도를나타낸다. 얇은표면에존재하는 Thin입자는 σ 3 α 2 σ 1 를검사하여추출한다. 여기서 α 2 는두께의정도를결정하는임계값이다. 그림 2와 3은유체입자의밀도와공분산행렬을이용한 SVD 계산까지의과정을 CUDA kernel로계산한 Pseudo code이다. 이과정은 3장에서설명한 Step1:[GPU] 과 Step2:[GPU] 에해당한다. 그림 2는유체입자의밀도값을이용하여대략적으로표면입자를분류하는 Pseudo code이며 ( 그림 4 참조 ), 그림 3은인접입자들과의거리값을이용하여공분산행렬을계산하는 Pseudo code이다. 최종적으로 SVD를이용하여고유벡터와고유값을계산하는부분은 GPU 기반의병렬프로그래밍을통해계산한다 [20]. Figure 5: Pseudo code for pair collection in CPU. 해서 3가지조건을모두검색하여중복없이만족하는 Pair를찾기때문에계산시간이오래걸린다. 우리는이를효율적으로처리하기위해 CPU GPU 이기종병렬프레임워크로분할하여계산한다. 3.1.2 후보위치추출과최적화추출된 Thin입자들은 Hole 부분에새로운입자를추가하는데사용된다. 우리는 Hole을채워넣을때사용하는입자들의 Pair 인 (i, j) 를찾는다. Pair의중심위치인 (p i +p j )/2는분할 (Splitting) 을하기위한후보위치로사용하기위해저장시키고, 아래조건을모두만족하는 Pair를최종적으로선택한다 : α 3 d 0 p i p j α 4 d 0, (5a) W smooth ((p i + p j )/2 p k,α 3 d 0 )=0, (5b) k (p i p j ) (u i u j ) > 0, (5c) 여기서 α 3 와 α 4 는각후보위치사이의최소거리와최대거리를제어하는상수이며, u는입자의속도이다. 수식 5a는두입자가서로적당한거리에있는지검사하는것이다. 수식 5b 는반지름 α 3 에새로운입자를추가하기에적당한지를판단하기위한조건이며, 후보위치주변에유체입자가없는지, 다시말해, 희박한영역인지를검사하는것이다. 수식 5c에서는한쌍의유체입자들사이의거리가시간이지남에따라증가하는지확인한다. 결과적으로위조건을모두만족하는 Pair의중간위치를중복없이 S에저장시킨다. 그림 5는후보위치들을추출하기위한과정을 CPU 기반병렬모듈로계산한 Pseudo code이며, 이과정은 Step3:[GPU] 에해당한다. Ando et al. [40] 의방법에서는모든유체입자에대 Figure 6: Pseudo code for optimization of candidate position in GPU. 그림 5는수식 5를만족하는 Pair를찾기위한과정을처리하는 Pseudo code이다. 본논문에서 CPU 기반병렬처리는 OpenMP를이용하였으며 CPU에서제공하는최대스레드개수 (omp_get_max_threads()) 만큼 Pair버퍼를생성하고, 수식 5a와 5c 조건들을만족하는 Pair를각스레드인덱스에맞는 Pair버퍼에저장시킨다 (m_pair[omp_get_thread_num()]). 이과정에서계산된 Pair집합들에서는많은수의후보 Pair들이추출되기때문에모든인접입자들을필요로하는수식 5b는계산시간이오래걸린다. 우리는이과정을효율적으로계산하기위해 - 14 -
u (x) = i m iu i W sharp (p i x,α 5 d 0 ) i m iw sharp (p i x,α 5 d 0 ), (8) ρ (x) = i m i W smooth (p i x,α 1 d 0 ), (9) 여기서 α 5 는속도 u 의크기를조절하는변수이고, W sharp 커널은아래와같다. Figure 7: Pseudo code for compuing S buffer in CPU. GPU 기반병렬처리로수행한다 ( 그림 6 참조 ). 최종적으로 GPU 상에서계산된 Pair 버퍼 (m_paircuda) 를 CPU 로전달한 다 (m_pair[i][]). 그림 7 은이과정을수행하는 Pseudo code 이며결과적으로 S 버퍼를구성한다. 다음장에서는이버퍼를 이용하여새로운유체입자의추가와삭제방법을설명한다. 3.1.3 유체입자추가와삭제 추출한후보위치리스트인 S 의개수가많기때문에이를간소 화하기위한방법이필요하다. 이번장에서는불필요한유체 입자들을필터링하고, 유체의얇은표면을유지하기위해필 요한최소개수의유체입자로 Hole-filling 하는방법에대해설 명한다. 추가된후보위치들의최종버퍼를 I 라고부르며지금 부터이버퍼를결정하는방법을설명한다. 이버퍼에서첫번 째입자인 I 1 에는 S 에서밀도를기반으로가장희박한 (Sparse) 후보위치를저장한다 ( 수식 6 참조 ): I 1 = argmin (ρ j s j ), (6) j size S 여기서 ρ j 는유체입자 j 의밀도이다. S 에서 I 1 을결정한후, 우리는 s I1 의주변입자들로부터반경이 α 3 d 0 내에존재하는 후보입자들을삭제한다. 다음단계에서는 s I1 의주변입자들 로부터반지름 α 3 외부에있는입자들을검색하여 N I1 에추가 한다. N I1 에있는입자들중가장가까운입자 s j 를 I 2 에추가 한다 ( 수식 7 참조 ): I 2 = argmin j N I1 s j s I1. (7) I 2 가 I 1 에서발견되는검색방법을 I n+1 = search(i n ) 으로정립할수있고, 이작업을반복하면서 I 3,I 4,I 5..., I n+1 를순차 적으로처리한다. 만약에검색이실패하여적당한유체입자를 찾지못하면수식 6 을대신사용한다. 유체입자가분할된후에분할된각입자들의속도와무게값 들은선형보간으로할당된다. 아래수식을이용하여 Eulerian 격자에매핑된속도 u 와입자의밀도 ρ 를계산한다 : W sharp (r,h)= { h 2 / r 2 1, 0 r h, 0, otherwise. (10) 추가된유체입자 i 는다음두가지중하나를만족하면삭제 한다 : ρ i >α 6 ρ 0 and α 3 α2σ 1, p i p j <α 7 d 0, for any j =i, (11a) (11b) 여기서 α 6 은최대밀도계수를나타내고, α 7 은입자사이의 최소거리를나타낸다. 수식 11 을만족하는유체입자들은모 두삭제를한다. 이과정에서한번에많은양의입자들이삭제 되면깜빡거리는문제가발생하는데이를줄이기위해난수 값을이용하여삭제되는시점을조금씩다르게하였다. 이유체입자를추가 / 삭제하는과정은 I n 이처리된다음 I n+1 이처리되어야하는 Serial 한구조이기때문에 Ando et al. [40] 가제안한알고리즘과동일하게처리하였다. 3.1.4 유체의표면복원 수식 4 의 SVD 값은이방성커널에재사용할수있기때문에 Yu et al. [19] 알고리즘에재사용하여얇은표면을재구성하는 데사용한다 ( 수식 12 참조 ). φ (x) =min ( G i (p i x) ), (12) i 여기서 G i 는유체입자 i 에대한변형행렬을나타낸다. G i = 1 k s e T 1 e T 2 e T 3 T σ 1 σ 2 σ 3 1 e T 1 e T 2 e T 3 (13) 여기서 k s 는스케일링상수이다. 중요한스트레칭부분을보 존하기위해서 σ n 은일정범위내로제한한다. 좀더자세한 설명은 Yu et al. [19] 연구를참조하길추천한다. 본논문에서 는 GPU 기반 Marhcing Cube 알고리즘을사용했으며 [41], 이 방법과맞물려서얇은유체표면이잘캡처되도록최소스트 레칭을격자너비의절반보다크게설정하였다. - 15 -
(a) Water particles (b) Water surfaces Figure 8: GPU-based fluid surface reconstruction. 4. 구현 제안된방법이구현된환경은아래와같다 : Intel i7-2600k 3.40 GHz CPU 16GB RAM, NVIDIA GeForce GTX 480 graphics card. FLIP기반유체해법을기반액체 (Underlying water) 시뮬레이션으로사용했으며, 유체의압력을계산하는수치적행렬해법은 GPU 기반 Preconditioned conjugate gradient [42] 방법을이용하였고, GPU 기반 SVD계산은 Lahabar의방법을활용하였다 [20]. FLIP격자의경우모든운동량은 Staggered Marker-and- Cell 방법을사용하여저장했으며 [43], 표면재복원을위해추가적인격자를사용하였다. 물과고체의충돌처리를위해변량 (Variational) 프레임워크를사용했다 [44]. Figure 10: Thin sheet surfaces of liquid by our method. (Filaments) 를빠르고명확하게표현했다. 그림 11은제안된기법의결과품질을비교한결과이다. Zhu and Bridson방법은얇은막이표현되는부분에서표면소실이많이일어나며 ( 그림 11a 참조 ), 이런문제를줄이고자표면의 Level-set값을 Smoothing 시키면수치적으로는좀나아지지만시각적으로개선이크게되지않는다 ( 그림 11b 참조 ). 최근에 Bhatacharya et al. [45] 은유체표면을좀더정확하게캡처하고자 Biharmonic smoothing기법을제안했다. 이논문은 Laplacian smoothing에비해좀더부드러운유체의표면을캡처하여개선된결과를보여주지만, 얇은유체의막부분에서여전히소실문제가발생한다 ( 그림 11c 참조 ). 하지만우리의방법은결과적으로소실문제를최소화하여디테일한유체의표면을표현하였으며, GPU 프레임워크로기존방법보다빠르게장면을제작하였다. 장면구성과성능개선은그림 10의결과와같다. Figure 9: Pseudo code of our framework. 그림 9는본논문에서제안하는얇은유체의특징을보존하는알고리즘의 Pseudo code이다. 격자와유체입자사이에서운동량을전달하거나압력을계산하는모든전반적인계산이 CPU와 GPU 기반병렬프레임워크에서수행된다. (a) Zhu and Bridson [17] (b) Zhu and Bridson [17] with Laplacian smoothing 5. 결과 제안하는프레임워크를다양한방면으로분석하기위해 5가지시나리오에서우리의방법을비교했다. 우리는간단한테스트시나리오상에서제안하는기법의우수성을입증하기위해구형액체를위에서떨어뜨리는장면을제작했다 ( 그림 10 참조 ). 이장면에서기반유체를표현하기위해타입스텝을 0.006으로설정하고, 30만개의유체입자들을사용하였다. 우리의기법은 CPU 기반기법인 Ando et al. [40] 의방법과동일한결과를만들어내면서결과적으로 6배빠른결과를보여주었다. 그림 10에서보듯이구형액체가메인유체와충돌됨에따라나타나는유체의얇은막과필라멘트 (c) Bhatacharya et al. [45] (d) Our method Figure 11: Comparison results: dropping a liquid sphere. 유체의얇은표면이나타나는디테일한특징은고체와유체가충돌되는커플링장면에서도쉽게확인할수있다. 제안하는모델이커플링장면에서도잘동작한다는것을입증하기 - 16 -
Figure 12: Deformable pumpkins thrown from various directionos. (a) Water surfaces (b) Water particles (red: inserted thin particle) Figure 13: Water pouring off a box cliff. (a) Water splash (b) Water pouring off a box cliff Figure 14: Results with Ando s method [40]. 위해, 우리는변형체모델을유체에던져자연스럽게스플래시현상이나타나도록하였다 ( 그림 12 참조 ). 호박 (Pumpkins) 모델이물에닿는순간표현되는 Water crown 형태를잘표현한다. 뿐만아니라바운더리에물이닿았을때도유체표면이깨지지않고깔끔하게유체표면을표현하였다. 이장면에서는 120만개의유체입자들을사용하였고, Ando et al. [40] 의방법과동일한결과를만들어내면서결과적으로 10배빠른결과를보여주었다. 제안된방법을이용했을때실제로어떤부분에서 Thin입자들이추가되어결과적으로유체의얇은표면을유지할수있는지를보여주기위해 Water pouring 장면을제작하였다. 그림 13a는 Water pouring으로인해물이상단에서하단으로떨어지면서표현되는유체의얇은표면을보여주고있으며, 같은장면에서유체입자는그림 13b에서보여준다. 이장면은다른장면에비해유체의얇은막이많이표현되는장면이며, 이같은특징은유체입자에서도컬러로쉽게보여진다. 빨간색은새롭게추가된 Thin입자이며, 이입자들로인해유체의 얇은막들이표현된다. 이결과는 Ando et al. [40] 의방법에서도동일하게만들어낼수있지만, 제안된기법은 Ando의기법보다 7배정도빠른결과를보여주었다. 그림 14는 Ando et al. [40] 의결과이며, 제안된결과는 Ando의기법과시각적비교했을때큰차이없이비슷한결과를만들어냈다. 그림 14a 는 Water splash를표현한결과이며, 그림 1b와그림 10의결과와비교했을때유체의얇은막을잘표현했다. 그림 14b 또한그림 13와비교했을때시각적으로유사한결과를만들어냈다. 유체의얇은막을유지하려는추가적인입자들의개수가많아지기때문에증가되는계산시간을이기종프레임워크로최적화하였다. 일반적으로는압력을계산하는 Pressure solver 부분이계산양이크다는점과는다소차이점이있다. 그림 15는물을박스로마구휘젓는장면이며, 다른장면들과마찬가지로유체의디테일한특징을잘캡처하였다. 이장면에서사용한유체입자는약 100만개이며, 우리의방법은 Ando의기법보다 4배정도빠른결과를보여주었다. 6. 결론및향후연구 우리는유체의얇은막을효율적으로표현하기위한 CPU GPU 기반이기종프레임워크를설명했다. 계산양이큰부분은 GPU를이용하였고, 그렇지않은부분은 CPU 기반병렬기법을사용했다. GPU는병렬계산을위해 CPU에서 GPU로데이터를복사하고, 계산된결과를다시반영하기위해 GPU에서 CPU로다시복사하는과정이추가된다. 우리는이불필요한과정을줄이기위해계산양이크지않은부분은 CPU 기반병렬기법을사용했다. - 17 -
[3] D. Kim, O.-y. Song, and H.-S. Ko, Stretching and wiggling liquids, ACM Transactions on Graphics, vol. 28, no. 5, pp. 120:1 120:7, 2009. [4] T. Kim, N. Thürey, D. James, and M. Gross, Wavelet turbulence for fluid simulation, in ACM Transactions on Graphics, vol. 27, no. 3, 2008, p. 50. [5] T. Pfaff, N. Thuerey, J. Cohen, S. Tariq, and M. Gross, Scalable fluid simulation using anisotropic turbulence particles, ACM Transactions on Graphics, vol. 29, no. 6, p. 174, 2010. Figure 15: Water pool interacting wth a stirring box. 앞에서본결과들에서성능개선을측정하기위한방법은유체의얇은막이계산되는부분만측정했으며, 모든결과에서 Ando et al. [40] 의프레임워크보다빠른시간내에결과를만들어냈다. 장면마다성능개선정도가다르지만제안된알고리즘은장면내Thin입자들의개수에비례하여성능개선이되었다. 3.1.2장에서설명한후보위치의개수또한 Thin입자의개수에비례해서생성된다. 결과적으로제안된프레임워크는초기장면에서생성한전체유체입자의개수와그로인해생성되는 Thin입자의개수가제안된프레임워크의성능에영향을끼쳤다. 제안된기법의한계점은메모리부족으로인해고해상도의장면을제작하기어렵다는것이다. 유체의얇은막을표현하기위해서는초기장면에설정된유체입자의개수보다많은입자들이필요하며, 장면마다 Thin입자들의개수가많이증가될수있다. GPU에서는가용메모리의크기가제약적이기때문에큰스케일의장면을제작하기위해서는최적화된메모리관리기법이필요하며, 향후우리는이메모리관리를효율적으로사용하여큰스케일의유체시뮬레이션을모델링할수있는방법에대해연구할계획이다. 참고문헌 [1] J.-M. Hong, T. Shinar, and R. Fedkiw, Wrinkled flames and cellular patterns, ACM Transactions on Graphics, vol. 26, no. 3, 2007. [2] D. Kim, S. W. Lee, O.-y. Song, and H.-S. Ko, Baroclinic turbulence with varying density and temperature, IEEE Transactions on Visualization and Computer Graphics, vol. 18, no. 9, pp. 1488 1495, 2012. [6] T. Pfaff, N. Thuerey, A. Selle, and M. Gross, Synthetic turbulence using artificial boundary layers, in ACM SIG- GRAPH Asia, 2009, pp. 121:1 121:10. [7] Y. Dobashi, Y. Matsuda, T. Yamamoto, and T. Nishita, A fast simulation method using overlapping grids for interactions between smoke and rigid objects, in Computer Graphics Forum, vol. 27, no. 2, 2008, pp. 477 486. [8] B. M. Klingner, B. E. Feldman, N. Chentanez, and J. F. O brien, Fluid animation with dynamic meshes, in ACM Transactions on Graphics, vol. 25, no. 3, 2006, pp. 820 825. [9] F. Losasso, F. Gibou, and R. Fedkiw, Simulating water and smoke with an octree data structure, in ACM Transactions on Graphics, vol. 23, no. 3, 2004, pp. 457 462. [10] D. Kim, S. W. Lee, O.-y. Song, and H.-S. Ko, Baroclinic turbulence with varying density and temperature, IEEE Transactions on Visualization and Computer Graphics, vol. 18, no. 9, pp. 1488 1495, 2012. [11] A. Selle, N. Rasmussen, and R. Fedkiw, A vortex particle method for smoke, water and explosions, in ACM Transactions on Graphics, vol. 24, no. 3, 2005, pp. 910 914. [12] M. Müller, D. Charypar, and M. Gross, Particle-based fluid simulation for interactive applications, in Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, 2003, pp. 154 159. [13] P. Goswami, P. Schlegel, B. Solenthaler, and R. Pajarola, Interactive sph simulation and rendering on the gpu, in Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2010, pp. 55 64. [14] T. Harada, S. Koshizuka, and Y. Kawaguchi, Smoothed particle hydrodynamics on gpus, in Computer Graphics International, 2007, pp. 63 70. - 18 -
[15] H. Yan, Z. Wang, J. He, X. Chen, C. Wang, and Q. Peng, Real-time fluid simulation with adaptive sph, Computer Animation and Virtual Worlds, vol. 20, no. 2-3, pp. 417 426, 2009. [16] F. Sin, A. W. Bargteil, and J. K. Hodgins, A point-based method for animating incompressible flow, in Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2009, pp. 247 255. [17] Y. Zhu and R. Bridson, Animating sand as a fluid, in ACM Transactions on Graphics, vol. 24, no. 3, 2005, pp. 965 972. [18] F. Losasso, J. Talton, N. Kwatra, and R. Fedkiw, Twoway coupled sph and particle level set fluid simulation, IEEE Transactions on Visualization and Computer Graphics, vol. 14, no. 4, pp. 797 804, 2008. [19] J. Yu and G. Turk, Reconstructing surfaces of particlebased fluids using anisotropic kernels, ACM Transactions on Graphics, vol. 32, no. 1, p. 5, 2013. [20] S. Lahabar and P. Narayanan, Singular value decomposition on gpu using cuda, in Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on, 2009, pp. 1 10. [21] S. Osher and J. A. Sethian, Fronts propagating with curvature-dependent speed: algorithms based on hamiltonjacobi formulations, Journal of computational physics, vol. 79, no. 1, pp. 12 49, 1988. [22] D. Enright, R. Fedkiw, J. Ferziger, and I. Mitchell, A hybrid particle level set method for improved interface capturing, Journal of Computational physics, vol. 183, no. 1, pp. 83 116, 2002. [23] Z. Wang, J. Yang, and F. Stern, An improved particle correction procedure for the particle level set method, Journal of Computational Physics, vol. 228, no. 16, pp. 5819 5837, 2009. [24] V. Mihalef, D. Metaxas, and M. Sussman, Textured liquids based on the marker level set, in Computer Graphics Forum, vol. 26, no. 3, 2007, pp. 457 466. [25] A. W. Bargteil, T. G. Goktekin, J. F. O brien, and J. A. Strain, A semi-lagrangian contouring method for fluid simulation, ACM Transactions on Graphics (TOG), vol. 25, no. 1, pp. 19 38, 2006. [26] N. Heo and H.-S. Ko, Detail-preserving fully-eulerian interface tracking framework, ACM Transactions on Graphics, vol. 29, no. 6, p. 176, 2010. [27] C. W. Hirt and B. D. Nichols, Volume of fluid (vof) method for the dynamics of free boundaries, Journal of computational physics, vol. 39, no. 1, pp. 201 225, 1981. [28] M. Kass, A. Witkin, and D. Terzopoulos, Snakes: Active contour models, International journal of computer vision, vol. 1, no. 4, pp. 321 331, 1988. [29] J. Glimm, J. W. Grove, X. L. Li, K.-m. Shyue, Y. Zeng, and Q. Zhang, Three-dimensional front tracking, SIAM Journal on Scientific Computing, vol. 19, no. 3, pp. 703 727, 1998. [30] G. Tryggvason, B. Bunner, A. Esmaeeli, D. Juric, N. Al- Rawahi, W. Tauber, J. Han, S. Nas, and Y.-J. Jan, A fronttracking method for the computations of multiphase flow, Journal of Computational Physics, vol. 169, no. 2, pp. 708 759, 2001. [31] M. Becker and M. Teschner, Weakly compressible sph for free surface flows, in Proceedings of the 2007 ACM SIG- GRAPH/Eurographics symposium on Computer animation, 2007, pp. 209 217. [32] B. Solenthaler and R. Pajarola, Predictive-corrective incompressible sph, in ACM Transactions on Graphics, vol. 28, no. 3, 2009, p. 40. [33] S. Koshizuka, A particle method for incompressible viscous flow with fluid fragmentation, Comput. Fluid Dynamics Journal, vol. 4, p. 29, 1995. [34] S. Premžoe, T. Tasdizen, J. Bigler, A. Lefohn, and R. T. Whitaker, Particle-based simulation of fluids, in Computer Graphics Forum, vol. 22, no. 3, 2003, pp. 401 410. [35] M. Pauly, R. Keiser, B. Adams, P. Dutré, M. Gross, and L. J. Guibas, Meshless animation of fracturing solids, ACM Transactions on Graphics, vol. 24, no. 3, pp. 957 964, 2005. [36] R. Keiser, B. Adams, D. Gasser, P. Bazzi, P. Dutré, and M. Gross, A unified lagrangian approach to solid-fluid animation, in Point-Based Graphics, 2005. Eurographics/IEEE VGTC Symposium Proceedings, 2005, pp. 125 148. [37] D. Gerszewski, H. Bhattacharya, and A. W. Bargteil, A point-based method for animating elastoplastic solids, in Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2009, pp. 133 138. - 19 -
[38] J. F. Blinn, A generalization of algebraic surface drawing, ACM Transactions on Graphics, vol. 1, no. 3, pp. 235 256, 1982. [39] B. Adams, M. Pauly, R. Keiser, and L. J. Guibas, Adaptively sampled particle fluids, in ACM SIGGRAPH, 2007. [40] R. Ando and R. Tsuruno, A particle-based method for preserving fluid sheets, in ACM SIGGRAPH/Eurographics symposium on computer animation, 2011, pp. 7 16. [41] C. Dyken and G. Ziegler, Gpu-accelerated data expansion for the marching cubes algorithm, in Proc. PGU Technology Conf, 2010, pp. 115 123. < 저자소개 > 김종현 2008 년세종대학교컴퓨터학과공학사 2010 년고려대학교컴퓨터학과공학석사 2016 년고려대학교컴퓨터학과공학박사 2013 년 -2016 년 ( 주 ) 텐일레븐책임연구원 2016 년 - 현재강남대학교소프트웨어응용학과조교수 관심분야 : 물리기반시뮬레이션, 가상현실, 지오메트리프로세싱 [42] R. Li and Y. Saad, Gpu-accelerated preconditioned iterative linear solvers, The Journal of Supercomputing, vol. 63, no. 2, pp. 443 466, 2013. [43] F. H. Harlow and J. E. Welch, Numerical calculation of timedependent viscous incompressible flow of fluid with free surface, The physics of fluids, vol. 8, no. 12, pp. 2182 2189, 1965. [44] C. Batty, F. Bertails, and R. Bridson, A fast variational framework for accurate solid-fluid coupling, in ACM Transactions on Graphics (TOG), vol. 26, no. 3, 2007, p. 100. [45] H. Bhatacharya, Y. Gao, and A. Bargteil, A level-set method for skinning animated particle data, in ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2011, pp. 17 24. [46] T. Jang, R. Blanco i Ribera, J. Bae, and J. Noh, Simulating sph fluid with multi-level vorticity, International Journal of Virtual Reality, vol. 10, no. 1, p. 21, 2011. [47] B. Yang and X. Jin, Turbulence synthesis for shapecontrollable smoke animation, Computer Animation and Virtual Worlds, vol. 25, no. 3-4, pp. 465 472, 2014. - 20 -