Microsoft Word - 13-杨冰陈喜等.doc ISSN 1078-6236 International Institute for General Systems Studies, Inc. Real-time 3D Smoking Simulation Based on Computational Fluid Dynamics and GPU Computation for Virtual Surgery� Bing Yang, Xi Chen, Cheng Yang, Jiaxiang Guo, Jie Han, Jiayu Tang and Zhiyong Yuan School of Computer, Wuhan University, Wuhan 430072, China Email: zhiyongyuan@whu.edu.cn (* Corresponding author) Abstract In this paper a smoking simulation model based on Computational Fluid Dynamics (CFD) for virtual surgery is proposed. Navier-Stokes equations are used to model smoke as a constant and incompressible fluid. In order to realize the visual effects of real-time 3D smoking, we utilize GPU (Graphics Processing Unit) and CUDA (Compute Unified Device Architecture) computing technology to perform the massive parallel computation by executing multithreading concurrently. The rendering of the smoke is implemented by the ray-tracing algorithm based on hardware. The visual effects of the real-time dynamic smoking simulation are given by the paper. The results show that the methods applied to the smoking simulation are elucidating and practical. Keywords Virtual surgery CFD GPU 3D Smoking simulation 1. Introduction Virtual surgery training system based on virtual reality can be used to improve the skill level of the surgeons and to reduce the incidence of complications in surgical practice. The ultimate advantage of this simulation system is to bridge the gap between the basic training of surgeon and the practical operation on patients, which means a real configurable training environment without the limitation of repeated training. However, the current surgical training systems have not yet reached the necessary level of sufficient reality, and the application of the simulation technology to the field of surgery has not yet been widely accepted [1]. The real simulation of smoke is an important research which has not yet been soundly solved. By far, there are few researches referring to smoke simulation in the virtual surgical simulation. Considering that smoke is a kind of fluid, a fluid dynamics method is adopted to solve the problems. Usually, Navier-Stokes equations are used to represent the accurate mathematic equations of fluid dynamics [2], but this method is only applicable under simple conditions. With the * The research work described in this paper was supported by the National Natural Science Foundation of China (Grant no. 61070079) and the Fundamental Research Funds for the Central Universities of China (Grant no. 6081006). ∗ ∗ Advances in Systems Science and Applications (2011), Vol.11, No.1-2 173-179 development of computer technology, it has been possible to compute the equations by numerical calculation and as a result, a new subject, computational fluid dynamics, has been born. In 1997, Foster and Metaxas [3, 4] adopted incompressible Navier-Stokes equations to a coarse mesh and solved nonlinearity partial differential equations by explicit differential equations, but it was too slow to show real-time animations. In 1999, Stam proposed a fluid solution with unconditionally stable and simulated the flow of the fluid with a random time step [5]. Because the simulation process of virtual surgery requires great visual effect and excellent quality of real-time, on the premise of great visual effect, the solution to the smoke model built by Navier-Stokes equations should meet the need of high real-time. Therefore, this paper implements a rapid solution to the three-dimensional smoke simulation model by CUDA+GPU technology. CUDA is a development environment for GPU computation. It is a new software and hardware structure based on C programming language. The code which runs in the display core can be wrote directly by C language and it is unnecessary to learn the special commands or structures of the display core [6]. It can perform large-scale parallel computation by executing multithreading concurrently, which offers a significant opportunity to meet the need of real-time simulation. Therefore, this paper accomplishes a rapid solution to Navier-Stokes equations by CUDA technology so as to meet the challenge of real-time. Compared with CPU, the result of this paper represents great advantages. To meet the need of real-time quality and real visual effect of the smoke simulation during the surgical training process, this paper adopts a real-time smoke synthesis and simulation model based on computational fluid dynamics. Navier-Stokes equations are adopted to model smoke as a constant, incompressible fluid with stable temperature. In order to simulate the smoke with a real-time effect, the Gauss-Seidel iterative method is employed to obtain diffusive items of the density field governing equations. Successive over relaxation method is used to derive the amended velocity field which meets the mass conservation condition. And then, ray tracing algorithm is used to implement smoke rendering [7]. For the purpose of getting real-time smoke, the solutions to Navier-Stokes equations based on GPU are performed by CUDA. 2. Modeling of Smoking Simulation 2.1 Smoking Model Smoke state is determined by its density, temperature and velocity. Supposing that smoke is incompressible fluids with a stable temperature, then the smoking model can be expressed by incompressible Navier-Stokes governing equations: continuity equation and momentum equation [8]. 0=⋅∇ V (1) 174 Yang: Real-time 3D Smoking Simulation Based on Computational Fluid Dynamics…… fVvVV t v +∇+∇⋅−= ∂ ∂ 2)( (2) SkV t +∇+∇⋅−= ∂ ∂ ρρρ 2)( (3) Equation (1) is the conservative differential form of incompressible smoke Navier-Stokes continuity equation. Where V⋅∇ is called the divergence of velocity (divergence). In the 3D space, divergence is defined as ),,()( z w y v x uVdivV ∂ ∂ ∂ ∂ ∂ ∂ ==⋅∇ . Equation (2) is a simplified incompressible Navier-Stokes smoking velocity momentum equation, while ignoring the pressure gradient item. V is velocity vector, ν represents the kinematic viscosity coefficient and F corresponds to the vector of external body forces. Equation (3) is the smoking density momentum equation, in which ρ is the density of the smoke, k is the diffusion constant and S is the scalar field of the amount of substance injected. 2.2 Solving the Smoking Model In 3D space fluid model, we consider smoke fluid to be stored in a discrete grid of a cube. The density field is divided into a N×N×N grid. Each cell in it has a number which stands for the density of the cell. If the number is 0, it means that there is no fluid particle in this cell. The larger the number is, the greater the density is. The density field is shown in Fig. 1, in which a) shows the three-dimensional fluid mesh and b) is the density distribution of each layer. a) 3D fluid grid b) Distribution of density field in each layer of fluid gird Fig. 1 Density field In each layer of the 3D fluid gird, the outermost ring is the boundary of grid. There are five state types for the boundary: No Slip, Free slip, inflow, outflow and periodic. In this paper, we employ free slip for the smoking simulation, which means that the density values on boundary are set to 0. The structure of velocity field is similar to the density field. Each cell in the grid is a velocity vector, which includes 3 velocity component values at position (x, y, z) of a cell. FDM Advances in Systems Science and Applications (2011), Vol.11, No.1-2 175 method is used to solve the governing equations. For convenience, density field is solved first, and then the velocity field. Solution by parts is used to resolve governing equation of the density field. The detailed steps are as follows: when solving the equation, two of the three items of the right side of equation are set to zero. Therefore, the solving process can be divided into 3 steps: solving the adding source item, solving the diffusion item by G-S Relaxation method; solving the advection item using tracing backwards method to get the solution. At this point, the calculation of the density field is completed. Governing equation of smoke simulation velocity field is exactly the same format with the density field equation. Therefore we only need to modify the density field equation and apply the Solution by parts to solve the velocity field. For the time being, we complete the calculation of velocity field and velocity field to be amended. The sequences of solving the smoking model governing equation are solving velocity field equations, solving to be amended velocity field which meets mass conservation conditions, solving density field governing equation, repeating till the end of calculation. 3. 3D Smoking Simulation Based on GPU Computing Considering that smoke is a constant and incompressible fluid with stable temperature, the smoking model can be expressed by incompressible Navier-Stokes governing equations. The algorithms for the smoking model are highly data-parallel and therefore a good match for the CUDA based on GPU programming model to improve the reality of the simulation. 3.1 CUDA+GPU Model In CUDA+GPU architecture, the main function is executed in CPU host and the parallel running data is transferred to the GPU device to implement the parallel computation. All of the tasks executed by CUDA are finished by a series of threads in the device allocated by the user. An array of threads is specified as a block. All the blocks are distributed in a parallel running gird. The programming frame based on CUDA+GPU is shown in Fig. 2 Fig. 2 CUDA+GPU programming architecture 3.2 3D Smoking Simulation Model Based on CUDA+GPU 176 Yang: Real-time 3D Smoking Simulation Based on Computational Fluid Dynamics…… In 3D fluid model, the smoke is considered to be saved in a discrete mesh of a square. At first, the CUDA API functions transfer the data of velocity field and density field into the DRAM of the device and then the corresponding computation of resolving the velocity field and density field is executed in the device. In the end, the result obtained in the device is transferred to the host so as to implement the rendering. The whole frame is shown in Fig. 3. Fig. 3 Simulation model of 3D smoking based on CUDA+GPU Considering that the bandwidth between the device and device memory is much higher than that between device memory and host memory, it is highly necessary to minimize the data transmission between the host and the device. In our test, the velocity field and the density field are initialized in the host firstly, and then they are sent to the device. At time t, the simulation model is resolved in device and as a result the velocity field and the density field of time t+1 can be got. For the reason that the final rendering is implemented in the host, the computation result in the device should be written back into the host. Considering that only the data of density filed is used when rendering, it just need to write the density filed to the host. Meanwhile, the velocity field and the density filed at time t+1 exchange with the data of time t to prepare for the next iteration. In the detailed running process, the 3D mesh is corresponding to the parallel running grid in the device, the slice of each layer in the fluid mesh is corresponding to the thread block in the device and the gird in the slice to the thread in the device. The final solving of the smoking model is implemented by the allocated thread. 4. Smoking Simulation Results The rendering of the smoke is implemented by the ray-tracing algorithm based on hardware [7]. G-S iterative method is applied to solve the diffusive item of smoking density governing equation. SOR method is utilized to solve Possion equation and the velocity field to be amended which meets the mass conservation condition [8]. The ray tracing method is used to render the Advances in Systems Science and Applications (2011), Vol.11, No.1-2 177 smoke. CUDA+GPU technology is employed to solve the Navier-Stokes equations based on GPU to obtain a visual effect of real-time smoking. In the following, the smoking simulation based on CUDA+GPU is implemented, and the results are displayed in OpenGL. The hardware configuration of our experimental platform is as follows: Dell Precision T3500, Intel(R) Xeon(R) W3503 2.40GHz CPU, 4GB memory, NVIDIA Tesla C1060. The software configuration is: Windows Vista, Visual C++.net 2005. The size of the fluid mesh in the investigation is 323232 ×× . We forced our codes to execute 1000 times in order to get an objective running time of the smoking model. A frame of dynamic smoking simulation results is shown in Fig. 4. Besides , the efficiency of the whole smoking simulation for virtual surgery (including the spatial positioning of the surgical instruments) is tested and the real-time smoking simulation result for virtual surgery is shown in Fig. 5. Fig. 4 A frame of dynamical smoking simulation Fig. 5 Real-time smoking s imulation for virtual surgery The performance of the smoking simulation system implemented on the CPU and CUDA+GPU are compared in Table 1. We get 36.0 speedup for the mesh. The result listed in Table 1 shows that significant increase of the performance is achieved and the frame per second of the whole system reaches to 56.2, which meets the requirement of real-time simulation for virtual surgery. 178 Yang: Real-time 3D Smoking Simulation Based on Computational Fluid Dynamics…… Table 1 Performance comparison on the CPU and the CUDA+GPU Data processing location Total running time (ms) Average running time (ms) Speedup ratio Frame per second (FPS) CPU 193384 193.384 - 4.7 CUDA+GPU 5370 5.370 36.0 56.2 5. Conclusion This paper investigates the methods for building the real-time dynamical smoking model based on CFD and employs the incompressible Navier-Stokes equations as the governing model to the smoke to be constant and incompressible. In order to develop a realistic simulation of smoking, we apply G-S iterative method to solve the diffusive item of smoking density governing equation. SOR method is utilized to solve Possion equation and the velocity field to be amended which meets the mass conservation condition. The ray tracing method is used to render the smoke and CUDA technology is employed to solve the Navier-Stokes equations based on GPU to obtain a real-time smoking visual effect. The results show that the smoking simulation model proposed is practical and elucidating. References [1] Montgomery K., Bruyns C., Wildermuth S. et al. Surgical Simulator for Operative Hysteroscopy. IEEE Visualization 2001, Washington DC, pp.14-17, 2001. [2] Jiyuan TU, Guan Heng YEOH, Chaoqun LIU. Computational Fluid Dynamics: A Practical Approach. 1st Ed., Oxford: Butterworth-Heinemann, 2007. [3] Foster N., Metaxas D. Controlling Fluid Animation. Proceedings of the CGI_97, Belgium: IEEE Computer Society, pp.178-188, 1997. [4] Foster N., Metaxas D. Modeling the Motion of a Hot, Turbulent Gas. Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. New York, pp. 181-188, 1997. [5] Stam J. Stable Fluids. SIGGRAPH 99 Conference Proceedings, Annual Conference Series, Los Angeles, pp. 121-128, August 1999. [6] NVIDIA: CUDA Programming Guide Ver. 2.0. [7] Ronald Fedkiw, Jos Stam, HenrikWann Jensen. Visual Simulation of Smoke. In SIGGRAPH 2001 Conference Proceedings, Annual Conference Series, pp.15-22, August 2001. [8] Zhiyong Yuan, Qian Yin, Shikun Feng, Jun Hu. Real-time Dynamic Bleeding Synthesis and Simulation of Endoscopic Images. Geomatics and Information Science of Wuhan University, 34(3): 317-320, 2009. (In Chinese) Advances in Systems Science and Applications (2011), Vol.11, No.1-2 179