I am a full Professor of CS at Yale, where I co-lead the Computer Graphics Group alongside Julie Dorsey and Holly Rushmeier.
I research topics in physics-based simulation, including fire, water, and humans.
My work has appeared in over two dozen movies, and I received a SciTech Oscar in both 2012 and 2022. Many of the results can be seen on YouTube,
and extensive source code is available on this page.
Previously, I was a Senior Research Scientist at Pixar Research, where I received
screen credits in Cars 3, Coco, Incredibles 2, and Toy Story 4. My first (uncredited) work appeared on-screen on
the Sorting Hat in Harry Potter and the Sorcerer's Stone. I am an Associate Editor for ACM Transactions on Graphics.
I received a BS in Computer Science in 2001 from Cornell and a PhD in Computer Science from UNC Chapel Hill in 2006 under the supervision of Ming Lin. I was a Post-Doctoral Fellow at IBM TJ Watson Research Center in 2007, and a Post-Doctoral Associate at Cornell University from 2008-2009 under the supervision of Doug James.
From 2011-2015, I was a faculty member at UCSB in the Media Arts and Technology Program and the Department of Computer Science.
While there, I received the UCSB Harold J. Plous Award (Junior Faculty of the Year).
From 2009-2011, I was an Assistant Professor in CS at the University of Saskatchewan.
I interned at the now-defunct but much-missed Rhythm and Hues Studios in 2001 and 2002, and the "world's first graphics company," Evans & Sutherland, in 2000.
Curly-cue: geometric methods for highly coiled hair. Haomiao Wu*, Alvin Shi*, A.M. Darke and T. Kim (* joint 1st authors) Proceedings of SIGGRAPH Asia 2024.
[Abstract]
[PDF]
[Project]
[YouTube]
[Source]
We present geometric methods for generating shapes that are characteristic of highly coiled hair. Different features become visually relevant when hairs are well-approximated by high-frequency helices instead of low-frequency curves, so we present algorithms for three such phenomena. First, a Fourier-based method for phase locking, the process by which disparate helices near the scalp coalesce into a single curl. Second, a method for period skipping which models individual helices deviating from the coalesced curl. Third, a non-linear optimization that directly generates the shapes of switchbacks, a.k.a. helical perversions, which heretofore could only be produced through direct physical simulation. By applying all three methods in tandem, we show that we can achieve richly detailed depictions of highly coiled hair.
We will cover recent advances and ongoing challenges in the depiction of Black hair, otherwise known as kinky, or Afro-textured hair. In computer graphics, the majority of hair research has been in the depiction straight or wavy hair. As a result, many aspects of the aesthetics and mechanics of Black hair remain poorly understood. To help fill this gap, we will present Code My Crown, a free guide to creating Black digital hairstyles that we co-authored in collaboration with a community of game artists and Dove. We also cover styling guidelines for 3D models in the Open Source Afro Hair Library, and present Lifted Curls, our strand simulation technique specifically designed for Afro-textured hair. Finally, we will suggest future directions for hair research.
Into the portal: directable fractal self-similarity. Alexa Schor and T. Kim Proceedings of SIGGRAPH North America 2024.
[Abstract]
[PDF]
[YouTube]
We present a novel, directable method for introducing fractal self-similarity into arbitrary shapes. Our method allows a user to directly specify the locations of self-similarities in a Julia set, and is general enough to reproduce other well-known fractals such as the Koch snowflake. Ours is the first algorithm to enable this level of general artistic control while also maintaining the character of the original fractal shape. We introduce the notion of placing "portals" in the iteration space of a dynamical system, bridging the aesthetics of iterated maps with the fine-grained control of iterated function systems (IFS). Our method is effective in both 2D and 3D.
Modelling a feather as a strongly anisotropic elastic shell. Jean Jouve, Victor Romero, Rahul Narain, Laurence Boissieux, T. Kim, and Florence Bertails-Descoubes Proceedings of SIGGRAPH North America 2024.
[Abstract]
[PDF]
[Project]
[Supplement]
[Video]
Feathers exhibit a highly anisotropic behaviour, governed by their complex
hierarchical microstructure composed of individual hairs (barbs}) clamped
onto a spine (rachis) and attached to each other through tiny
hooks (barbules). Previous methods in computer graphics have approximated
feathers as strips of cloth, thus failing to capture the particular macroscopic
nonlinear behaviour of the feather surface (vane). To investigate the
anisotropic properties of a feather vane, we design precise measurement protocols
on real feather samples. Our experimental results suggest a linear strain-stress
relationship of the feather membrane with orientation-dependent coefficients,
as well as an extreme ratio of stiffnesses in the barb and barbule direction, of the order of 104. From these
findings we build a simple continuum model for the feather vane, where the vane
is represented as a three-parameter anisotropic elastic shell.
However, implementing the model numerically reveals severe locking and
ill-conditioning issues, due to the extreme stiffness ratio between the
barb and the barbule directions. To resolve these issues, we align the mesh along
the barb directions and replace the stiffest modes with an inextensibility constraint. We extensively validate our membrane model
against real-world laboratory measurements, by using
an intermediary microscale model that allows us to limit the number of required lab experiments. Finally, we
enrich our membrane model with anisotropic bending, and show its practicality in
graphics-like scenarios like a full feather and a larger-scale bird.
This article argues that the first important comprehensive efforts by US mathematicians to survey, translate, and disseminate the work of Chinese mathematicians resulted from Cold War geopolitical and scientific competition and economic pressures that emerged in the 1950s and 1960s. The success of the American Mathematical Society's (AMS) translation program and its journal Chinese Mathematics depended less on official diplomatic channels and more on an informal network of Chinese American mathematicians and librarians in the United States, which provided the necessary infrastructure and hidden labor necessary for transnational mathematical exchange and translation. The history of the Chinese translation project demonstrates the importance of moving beyond the biographies and work of established mathematicians to capture the broader transpacific social history of Chinese American mathematical research and technical labor in the early Cold War. Moreover, the article demonstrates the importance of bringing Asian American history and the history of Cold War science together, as the mathematical and linguistic expertise and labor required came from recently immigrated Chinese American mathematicians caught at the nexus of Cold War anticommunist politics and the incomplete repeal of Chinese exclusion. Historians of mathematics have mostly narrated the late 1940s and early 1950s as a time of anti-communist purges that impacted the lives of Chinese scientists and derailed US-China scientific exchange. Meanwhile, the 1960s have remained unexamined. Instead, we see the ways in which the AMS's translation program generated important mathematical exchanges that widely impacted mathematics and adjacent fields.
We examine the life and legacy of pioneering Vietnamese computer scientist Búi Tướng Phong, whose shading and lighting models turned 50 last year.
We trace the trajectory of his life through Vietnam, France, and the United States, and its intersections with global conflicts.
Crucially, we present definitive evidence that his name has been cited incorrectly over the last five decades. His family name appears to be Búi Tướng, not Phong. By presenting these facts at SIGGRAPH, we hope to collect more information about his life, and ensure that his name is remembered correctly in the future.
Note: An earlier version of this article speculated that his family name was Búi. We have since received definitive confirmation that his family name was
Búi Tướng.
We present an isotropic, hyperelastic model specifically designed for the efficient simulation of tightly coiled hairs whose curl radii approach 5 mm. Our model is robust to large bends and torsions, even when they appear at the scale of the strand discretization.
The terms of our model are consistently quadratic with respect to their primary variables, do not require per-edge frames or any parallel transport operators, and can efficiently take large timesteps on the order of 1/30 of a second. Additionally, we show that it is possible to obtain fast, closed-form eigensystems for all the terms in the energy. Our eigenanalysis is sufficiently generic that it generalizes to other models. Our entirely vertex-based formulation integrates naturally with existing finite element codes, and we demonstrate its efficiency and robustness in a variety of scenarios.
We present an efficient new method for computing Mandelbrot-like fractals (Julia sets) that approximate a user-defined shape. Our algorithm is orders of magnitude faster than previous methods, as it entirely sidesteps the need for a time-consuming numerical optimization. It is also more robust, succeeding on shapes where previous approaches failed. The key to our approach is a versor-modulus analysis of fractals that allows us to formulate a novel shape modulus function that directly controls the broad shape of a Julia set, while keeping fine-grained fractal details intact. Our formulation contains flexible artistic controls that allow users to seamlessly add fractal detail to desired spatial regions, while transitioning back to the original shape in others. No previous approach allows Mandelbrot-like details to be "painted" onto meshes.
Angle-based energies appear in numerous physics-based simulation models, including thin-shell bending and isotropic elastic strands. We present a generic analysis of these energies that allows us to analytically filter the negative eigenvalues of the second derivative (Hessian), which is critical for stable, implicit time integration. While these energies are usually formulated in terms of angles and positions, we propose an abstract edge stencil that succinctly parameterizes the edge deformation, and allows us to derive generic, closed-form analytical expressions for the energy eigensystems. The resultant eigenvectors have straightforward geometric interpretations. We demonstrate that our method is readily applicable to a variety of 2D and 3D angle-based elastic energies, including both cloth and strands, and is up to 7x faster than numerical eigendecomposition.
We analyze a wide class of penalty energies used for contact response through the lens of a reduced frame. Applying our analysis to both spring-based and barrier-based energies, we show that we can obtain closed-form, analytic eigensystems that can be used to guarantee positive semidefiniteness in implicit solvers. Our approach is both faster than direct numerical methods, and more robust than approximate methods such as Gauss-Newton. Over the course of our analysis, we investigate physical interpretations for two separate notions of length. Finally, we showcase the stability of our analysis on challenging strand, cloth, and volume scenarios with large timesteps on the order of 1/40 s.
No, AI is most certainly not the new manhattan
project.
T. Kim and Shelly Lesher San Francisco Chronicle 2023.
[Article]
[PDF]
[Note]
Professor Lesher is also the host of the podcast My Nuclear Life.
We present a geometric optimisation framework that can recover fold-over free maps from non-injective initial states using popular flip-preventing distortion energies. Since flip-preventing energies are infinite for folded configurations, we propose a new regularisation scheme that shifts the singular values of the deformation gradient. This allow us to re-use many existing algorithms, especially locally injective methods for initially folded maps. Our regularisation is suitable for both singular value- and invariant-based formulations, and systematically contributes multiple stabilisers to the Hessian. In contrast to proxy-based techniques, we maintain second-order convergence. Compact expressions for the energy eigensystems can be obtained for our extended stretch invariants, enabling the use of fast projected Newton solvers. Although spectral shifting in general has no theoretical guarantees that the global minimum is an injection, extensive experiments show that our framework is fast and extremely robust in practice, and capable of generating high-quality maps from severely distorted, degenerate and folded initialisations.
AI isn't magic. It's just knowledge sausage.
T. Kim Los Angeles Times 2023.
[Article]
[PDF]
[Note]
The actual article has the less informative title Can today's AI truly learn on its own? Not likely. The article is otherwise the same.
The online edition has the more clickbait-y title Five years after Weinstein, Hollywood is enabling a new form of sexual violence. The article is otherwise the same.
Simulating dynamic deformation has been an integral component of Pixar's storytelling since Boo's shirt in Monsters, Inc. (2001). Recently, several key transformations have been applied to Pixar's core simulator Fizt that improve its speed, robustness, and generality. Starting with Coco (2017), improved collision detection and response were incorporated into the cloth solver, then with Cars 3 (2017) 3D solids were introduced, and in Onward (2020) clothing is allowed to interact with a character's body with two-way coupling.
The 3D solids are based on a fast, compact, and powerful new formulation that we have published over the last few years at SIGGRAPH. Under this formulation, the construction and eigendecomposition of the force gradient, long considered the most onerous part of the implementation, becomes fast and simple. We provide a detailed, self-contained, and unified treatment here that is not available in the technical papers. We also provide, for the first time, open-source C++ implementations of many of the algorithms.
This new formulation is only a starting point for creating a simulator that is up challenges of a production environment. One challenge is performance: we discuss our current best practices for accelerating system assembly and solver performance. Another challenge that requires considerable attention is robust collision detection and response. Much has been written about collision detection approaches such as proximity-queries, continuous collisions and global intersection analysis. We discuss our strategies for using these techniques, which provides us with valuable information that is needed to handle challenging scenarios.
Countering racial bias in computer graphics research.
T. Kim, Holly Rushmeier, Julie Dorsey, Derek Nowrouzezahrai, Raqi Syed, Wojciech Jarosz, and A.M. Darke ACM SIGGRAPH Talks (North America) 2022.
[Abstract]
[PDF]
[Supplement]
[arXiv]
Current computer graphics research practices contain racial biases that have resulted in investigations into "skin" and "hair" that focus on the hegemonic visual features of Europeans and East Asians. To broaden our research horizons to encompass all of humanity, we propose a variety of improvements to quantitative measures and qualitative practices, and pose novel, open research problems.
Sex and gender in the computer graphics research literature. Ana Dodik*, Silvia Sellán*, T. Kim, and Amanda Phillips (* joint 1st authors) ACM SIGGRAPH Talks (North America) 2022.
[Abstract]
[PDF]
[Supplement]
[arXiv]
We survey the treatment of sex and gender in the Computer Graphics research literature from an algorithmic fairness perspective. The stablished practices on the use of gender and sex in our community are scientifically incorrect and constitute a form of algorithmic bias with potential harmful effects. We propose ways of addressing these trends as technical limitations.
The rise of tech unions shows workers reckoning with reality.
T. Kim Los Angeles Times 2022.
[Article]
[Cached PDF]
[Note]
This was written in June 2022, six months before the launch of ChatGPT.
Amazon warehouse workers unionized. It's time tech workers do the same.
T. Kim San Francisco Chronicle 2022.
[Article]
[Cached PDF]
[Note]
This was written in April 2022, six months before mass layoffs at Google, Meta, and Microsoft.
Racism in our curriculums isn't limited to history. It's in math, too.
T. Kim The Washington Post 2021.
[Article]
[Cached PDF]
[Note]
This article was originally titled The violent history of the chinese remainder theorem. To learn more about the Chinese Exclusion Act and Asian-American immigration, I highly recommend this episode of American Experience.
AI flaws could make your next car racist.
T. Kim Los Angeles Times 2021.
[Article]
[Cached PDF]
Spiral-spectral fluid simulation. Qiaodong Cui, Timothy Langlois, Pradeep Sen, and T. Kim ACM Transactions on Graphics (SIGGRAPH Asia) 2021.
[Abstract]
[PDF]
[Supplement]
[YouTube]
[Source]
We introduce a fast, expressive method for simulating fluids over radial domains, including discs, spheres, cylinders, ellipses, spheroids, and tori. We do this by generalizing the spectral approach of Laplacian Eigenfunctions, resulting in what we call spiral-spectral fluid simulations. Starting with a set of divergence-free analytical bases for polar and spherical coordinates, we show that their singularities can be removed by introducing a set of carefully selected enrichment functions. Orthogonality is established at minimal cost, viscosity is supported analytically, and we specifically design basis functions that support scalable FFT-based reconstructions. Additionally, we present an efficient way of computing all the necessary advection tensors. Our approach applies to both three-dimensional flows as well as their surface-based, codimensional variants. We establish the completeness of our basis representation, and compare against a variety of existing solvers.
Distortion energy for deep learning-based volumetric finite element mesh generation for aortic valves. Daniel H. Pak, Minliang Liu, T. Kim, Liang Liang, Raymond McKay, Wei Sun, and James S. Duncan Proceedings of MICCAI 2021.
[Abstract]
[Paper]
[Source]
Volumetric meshes with hexahedral elements are generally best for stress analysis using finite element (FE) methods. With recent interests in finite element analysis (FEA) for Transcatheter Aortic Valve Replacement (TAVR) simulations, fast and accurate generation of patient-specific volumetric meshes of the aortic valve is highly desired. Yet, most existing automated image-to-mesh valve modeling strategies have either only produced surface meshes or relied on simple offset operations to obtain volumetric meshes, which can lead to undesirable artifacts. Furthermore, most recent advances in deep learning-based meshing techniques have focused on watertight surface meshes, not volumetric meshes. To fill this gap, we propose a novel volumetric mesh generation technique using template-preserving distortion energies under the deep learning-based deformation framework. Our model is trained end- to-end for image-to-mesh prediction, and our mesh outputs have good spatial accuracy and element quality. We check the FEA-suitability of our model-predicted meshes using a valve closure simulation. Our code is available here.
Anti-racist graphics research.
T. Kim SIGGRAPH Diversity Equity & Inclusion Summit 2021.
[Abstract]
[YouTube]
Many of the basic research problems we take for granted in computer graphics contain insidious assumptions about race. These troubling issues pre-date computer graphics, and can be traced back to the film technology and techniques from the analog era. Far from being incidental, they directly determine the physical formulations and numerical algorithms we use to depict virtual humans today.
Instead of perpetuating the prejudices of previous eras, can we engage in anti-racist research that works to dismantle it?
QLB: collision-aware quasi-bewton solver with cholesky and L-BFGS for nonlinear time integration.
Bethany Witemeyer, Nicholas J. Weidner, T. Kim, Timothy A. Davis, and Shinjiro Sueda Motion, Interaction, and Games (MIG) 2021.
[Abstract]
We advocate for the straightforward applications of the Cholesky and the Limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) algorithms in the context of nonlinear time integration of deformable objects with dynamic collisions. At the beginning of each time step, we form and factor the Hessian matrix, accounting for all internal forces while omitting the implicit cross-coupling terms from the collision forces between multiple dynamic objects or self collisions. Then during the nonlinear solver iterations of the time step, we implicitly update this Hessian with L-BFGS. This approach is simple to implement and can be readily applied to any nonlinear time integration scheme, including higher-order schemes and quasistatics. We show that this approach works well in a wide range of settings involving complex nonlinear materials, including heterogeneity and anisotropy, as well as collisions, including frictional contact and self collisions.
Stream-guided smoke simulations. Syuhei Sato, Yoshinori Dobashi, and T. Kim ACM Transactions on Graphics (SIGGRAPH North America) 2021.
[Abstract]
[PDF]
[Project]
[YouTube]
High-resolution fluid simulations are computationally expensive, so many post-processing methods have been proposed to add turbulent details to low-resolution flows. Guiding methods are one promising approach for adding naturalistic, detailed motions as a post-process, but can be inefficient. Thus, we propose a novel, efficient method that formulates fluid guidance as a minimization problem in stream function space. Input flows are first converted into stream functions, and a high resolution flow is then computed via optimization. The resulting problem sizes are much smaller than previous approaches, resulting in faster computation times. Additionally, our method does not require an expensive pressure projection, but still preserves mass. The method is both easy to implement and easy to control, as the user can control the degree of guiding with a single, intuitive parameter. We demonstrate the effectiveness of our method across various examples.
ConJac: large steps in dynamic simulation. Nicholas J. Weidner, T. Kim, and Shinjiro Sueda Motion, Interaction, and Games (MIG) 2020. (Best Paper Award)
[Abstract]
[PDF]
[Slides]
We present a new approach that allows large time steps in dynamic simulations. Our approach, ConJac, is based on condensation, a technique for eliminating many degrees of freedom (DOFs) by expressing them in terms of the remaining degrees of freedom. In this work, we choose a subset of nodes to be dynamic nodes, and apply condensation at the velocity level by defining a linear mapping from the velocities of these chosen dynamic DOFs to the velocities of the remaining quasistatic DOFs. We then use this mapping to derive reduced equations of motion involving only the dynamic DOFs. We also derive a novel stabilization term that enables us to use complex nonlinear material models. ConJac remains stable at large time steps, exhibits highly dynamic motion, and displays minimal numerical damping. In marked contrast to subspace approaches, ConJac gives exactly the same configuration as the full space approach once the static state is reached. ConJac works with a wide range of moderate to stiff materials, supports anisotropy and heterogeneity, handles topology changes, and can be combined with existing solvers including rigid body dynamics.
The Baraff-Witkin model has been a popular formulation for cloth for 20 years. However, its relationship to the finite element method (FEM) has always been unclear, because the model resists being written as an isotropic, hyperelastic strain energy. In this paper, we show that this is because the Baraff-Witkin model is actually a coupled anisotropic strain energy. We show that its stretching term approximates the isotropic As-Rigid-As-Possible (ARAP) energy, and its shearing term is a cross-fiber coupling energy common in biomechanics. While it has been known empirically for some time that the model can produce indefinite force Jacobians, the conditions under which they occur has never been clear. Our formulation enables a complete eigenanalysis that precisely characterizes exactly when indefiniteness occurs, and leads to fast, analytic, semi-positive-definite projection methods. Finally, our analysis suggests a generalized Baraff-Witkin energy with non-orthogonal warp and weft directions.
A massive fractal in days, not years.
T. Kim and Tom Duff Journal of Computer Graphics Techniques 2020.
[Abstract]
[PDF]
[Source]
We present a new, numerically stable algorithm that allows us to compute a previously-infeasible, fractalized Stanford Bunny composed of 10 billion triangles.
Recent work [Kim 2015] showed that it is feasible to compute quaternion Julia sets that conform to any arbitrary shape.
However, the scalability of the technique was limited because it used high-order rationals requiring 80 bits of precision.
We address the sources of numerical difficulty and allow the same computation to be performed using 64 bits.
Crucially, this enables computation on the GPU, and computing a 10 billion triangle model now takes 17 days instead of 10 years. We show that the resulting mesh is useful a test case for a distributed renderer.
Fast and robust stochastic structural optimization. Qiaodong Cui, Timothy Langlois, Pradeep Sen, and T. Kim Computer Graphics Forum (Eurographics) 2020.
[Abstract]
[PDF]
Stochastic structural analysis can assess whether a fabricated object will break under real-world conditions. While this approach is powerful, it is also quite slow, which has previously limited its use to coarse resolutions (e.g., 26 x 34 x 28). We show that this approach can be made asymptotically faster, which in practice reduces computation time by two orders of magnitude, and allows the use of previously-infeasible resolutions. We achieve this by showing that the probability gradient can be computed in linear time instead of quadratic, and by using a robust new scheme that stabilizes the inertia gradients used by the optimization. Additionally, we propose a constrained restart method that deals with local minima, and a sheathing approach that further reduces the weight of the shape. Together, these components enable the discovery of previously-inaccessible designs.
Anisotropic elasticity for inversion-safety and element rehabilitation.
T. Kim, Fernando de Goes and Hayley Iben ACM Transactions on Graphics (SIGGRAPH North America) 2019.
[Abstract]
[PDF]
[Supplement]
[Matlab/Octave Source]
[Vimeo]
We present an analysis of anisotropic hyperelasticity, specifically transverse isotropy, that obtains closed-form expressions for the eigendecompositions of many common energies. We then use these to build fast and concise Newton implementations. We leverage our analysis in two separate applications. First, we show that existing anisotropic energies are not inversion-safe, and contain spurious stable states under large deformation. We then propose a new anisotropic strain invariant that enables the formulation of a novel, robust, and inversion-safe energy. The new energy fits completely within our analysis, so closed-form expressions are obtained for its eigensystem as well.
Secondly, we use our analysis to rehabilitate badly-conditioned finite elements. Using this method, we can robustly simulate large deformations even when a mesh contains degenerate, zero-volume elements. We accomplish this by swapping the badly-behaved isotropic direction with a well-behaved anisotropic term. We validate our approach on a variety of examples.
Deep fluids: a generative network for parameterized fluid simulations. Byungsoo Kim, Vinicius Azevedo, Nils Thürey, T. Kim, Markus Gross and Barbara Solenthaler Computer Graphics Forum (Eurographics), May 2019.
[Abstract]
[PDF]
[Supplement]
[Code]
[YouTube]
This paper presents a novel generative model to synthesize fluid simulations from a set of reduced parameters. A convolutional neural network is trained on a collection of discrete, parameterizable fluid simulation velocity fields. Due to the capability of deep learning architectures to learn representative features of the data, our generative model is able to accurately approximate the training data set, while providing plausible interpolated in-betweens. The proposed generative model is optimized for fluids by a novel loss function that guarantees divergence-free velocity fields at all times. In addition, we demonstrate that we can handle complex parameterizations in reduced spaces, and advance simulations in time by integrating in the latent space with a second network. Our method models a wide variety of fluid behaviors, thus enabling applications such as fast construction of simulations, interpolation of fluids with different parameters, time re-sampling, latent space simulations, and compression of fluid simulation data. Reconstructed velocity fields are generated up to 700x faster than re-simulating the data with the underlying CPU solver, while achieving compression rates of up to 1300x.
Many strategies exist for optimizing non-linear distortion energies in geometry and physics applications, but devising an approach that achieves the convergence promised by Newton-type methods remains challenging. In order to guarantee the positive semi-definiteness required by these methods, a numerical eigendecomposition or approximate regularization is usually needed. In this paper, we present analytic expressions for the eigensystems at each quadrature point of a wide range of isotropic distortion energies. These systems can then be used to project energy Hessians to positive semi-definiteness analytically. Unlike previous attempts, our formulation provides compact expressions that are valid both in 2D and 3D, and does not introduce spurious degeneracies. At its core, our approach utilizes the invariants of the stretch tensor that arises from the polar decomposition of the deformation gradient. We provide closed-form expressions for the eigensystems for all these invariants, and use them to systematically derive the eigensystems of any isotropic energy. Our results are suitable for geometry optimization over flat surfaces or volumes, and agnostic to both the choice of discretization and basis function. To demonstrate the efficiency of our approach, we include comparisons against existing methods on common graphics tasks such as surface parameterization and volume deformation.
The Laplacian Eigenfunction method for fluid simulation, which we refer to as Eigenfluids, introduced an elegant new way to capture intricate fluid flows with near-zero viscosity. However, the approach does not scale well, as the memory cost grows prohibitively with the number of eigenfunctions. The method also lacks generality, because the dynamics are constrained to a closed box with Dirichlet boundaries, while open, Neumann boundaries are also needed in most practical scenarios. To address these limitations, we present a set of analytic eigenfunctions that supports uniform Neumann and Dirichlet conditions along each domain boundary, and show that by carefully applying the discrete sine and cosine transforms, the storage costs of the eigenfunctions can be made completely negligible. The resulting algorithm is both faster and more memory-efficient than previous approaches, and able to achieve lower viscosities than similar pseudo-spectral methods. We are able to surpass the scalability of the original Laplacian Eigenfunction approach by over two orders of magnitude when simulating rectangular domains. Finally, we show that the formulation allows forward scattering to be directed in a way that is not possible with any other method.
Example-based turbulence style transfer. Syuhei Sato, Yoshinori Dobashi, T. Kim, and Tomoyuki Nishita ACM Transactions on Graphics (SIGGRAPH North America) 2018.
[Abstract]
[PDF]
[Project]
[YouTube]
Generating realistic fluid simulations remains computationally expensive, and animators can expend enormous effort trying to achieve a desired motion. To reduce such costs, several methods have been developed in which high-resolution turbulence is synthesized as a post process.
Since global motion can then be obtained using a fast, low-resolution simulation, less effort is needed to create a realistic animation with the desired behavior.
While much research has focused on accelerating the low-resolution simulation, the problem controlling the behavior of the turbulent, high-resolution motion has received little attention.
In this paper, we show that style transfer methods from image editing can be adapted to transfer the turbulent style of an existing fluid simulation onto a new one.
We do this by extending example-based image synthesis methods to handle velocity fields using a combination of patch-based and optimization-based texture synthesis. Importantly, this approach allows us to incorporate the incompressibility condition.
Using our method, a user can easily and intuitively create high-resolution fluid animations that have a desired turbulent motion.
Clean cloth inputs: removing character self-intersections with volume simulation.
Audrey Wong, David Eberle, and T. Kim ACM SIGGRAPH Talks (North America) 2018.
[Abstract]
[PDF]
Simulation artists frequently work with characters that self-intersect. When these characters are sent as inputs to a cloth simulator, the results can often contain terrible artifacts that must be addressed by tediously sculpting either the input characters or the output cloth. In this talk, we apply volume simulation to character meshes and remove self-intersections before they are sent to the cloth simulator. The technique has successfully dealt with very challenging animation scenarios in a production setting, and was applied to all the characters in the short film Bao.
Robust skin simulation in Incredibles 2.
Ryan Kautzman, Gordon Cameron, and T. Kim ACM SIGGRAPH Talks (North America) 2018.
[Abstract]
[PDF]
Robustly simulating the dynamics of skin sliding over a character's body is an ongoing challenge. Skin can become non-physically "snagged" in curved or creased regions, such as armpits, and create unusable results. These problems usually arise when it becomes ambiguous which kinematic surface the skin should be sliding along. We have found that many of these problems can be addressed by performing 2D ray-tracing over the surface of the mesh. The approach is fast and robust, and has been used successfully in Incredibles 2.
Non-linear hyperelastic energies play a key role in capturing the fleshy appearance of virtual characters. Real-world, volume-preserving biological tissues have Poisson's ratios near 1/2, but numerical simulation within this regime is notoriously challenging. In order to robustly capture these visual characteristics, we present a novel version of Neo-Hookean elasticity. Our model maintains the fleshy appearance of the Neo-Hookean model, exhibits superior volume preservation, and is robust to extreme kinematic rotations and inversions. We obtain closed-form expressions for the eigenvalues and eigenvectors of all of the system's components, which allows us to directly project the Hessian to semi-positive-definiteness, and also leads to insights into the numerical behavior of the material. These findings also inform the design of more sophisticated hyperelastic models, which we explore by applying our analysis to Fung and Arruda-Boyce elasticity. We provide extensive comparisons against existing material models.
Seeing and hearing the eigenvectors of a fluid. Aaron Demby-Jones, JoAnn Kuchera-Morin, and T. Kim Bridges: Mathematics, Music, Art, Architecture, Culture 2017.
[Abstract]
[PDF]
[YouTube]
The intricate shapes and sounds that arise from vibrating Chladni plates are a well-known phenomenon. They are also quantitatively well understood, as the spatial patterns correspond to the eigenvectors of the underlying plate, and the audio frequencies arise from the plate's eigenvalues. We explore a generalization of the phenomenon by computing analogous quantities for a computational fluid dynamics simulation. Unlike the Chladni plate case, direct analytic expressions are not available, so we instead compute a set of "empirical" eigenvectors and eigenvalues. We find that these vectors form abstract, turbulent patterns in space. In another departure from the Chladni plate case, the eigenvalues no longer have a natural sonic mapping, so we construct a sonification that allows us to "listen" to the eigenvectors of the fluid. The united visual and sonic forms comprise a multimodal compositional palette that has great artistic potential.
Eulerian solid-fluid coupling. Yun Teng, David I.W. Levin, and T. Kim ACM Transactions on Graphics (SIGGRAPH Asia) 2016.
[Abstract]
[PDF]
[Project]
[Source]
[YouTube]
We present a new method that achieves a two-way coupling between deformable solids and an incompressible fluid where the underlying geometric representation is entirely Eulerian. Using the recently developed Eulerian Solids approach [Levin et al. 2011], we are able to simulate multiple solids undergoing complex, frictional contact while simultaneously interacting with a fluid. The complexity of the scenarios we are able to simulate surpasses those that we have seen from any previous method. Eulerian Solids have previously been integrated using explicit schemes, but we develop an implicit scheme that allows large time steps to be taken. The incompressibility condition is satisfied in both the solid and the fluid, which has the added benefit of simplifying collision handling.
Dispersion kernels for water wave simulation. José Angel Canabal, David Miraut, Nils Thüerey, T. Kim, Javier Portilla, and Miguel Otaduy ACM Transactions on Graphics (SIGGRAPH Asia) 2016.
[Abstract]
[PDF]
[Project]
[YouTube]
We propose a method to simulate the rich, scale-dependent dynamics of water waves. Our method preserves the dispersion properties of real waves, yet it supports interactions with obstacles and is computationally efficient. Fundamentally, it computes wave accelerations by way of applying a dispersion kernel as a spatially variant filter, which we are able to compute efficiently using two core technical contributions. First, we design novel, accurate, and compact pyramid kernels which compensate for low-frequency truncation errors. Second, we design a shadowed convolution operation that efficiently accounts for obstacle interactions by modulating the application of the dispersion kernel. We demonstrate a wide range of behaviors, which include capillary waves, gravity waves, and interactions with static and dynamic obstacles, all from within a single simulation.
Subspace fluid simulations, also known as reduced-order simulations, can be extremely fast, but also require basis matrices that consume an enormous amount of memory. Motivated by the extreme sparsity of Laplacian eigenfunctions in the frequency domain, we design a frequency-space codec that is capable of compressing basis matrices by up to an order of magnitude. However, if computed naively, decompression can be highly inefficient and dominate the running time, effectively negating the advantage of the subspace approach. We show how to significantly accelerate the decompressor by performing the key matrix-vector product in the sparse frequency domain. Subsequently, our codec only adds a factor of three or four to the overall runtime. The compression preserves the overall quality of the simulation, which we show in a variety of examples.
Surface turbulence for particle-based liquid simulations. Olivier Mercier, Cynthia Beauchemin, Nils Thüerey, T. Kim, and Derek Nowrouzezahrai ACM Transactions on Graphics (SIGGRAPH Asia) 2015.
[Abstract]
[Project]
[PDF]
[Source (MantaFlow)]
[YouTube]
We present a method to increase the apparent resolution of particle-based liquid simulations. Our method first outputs a dense, temporally coherent, regularized point set from a coarse particle-based liquid simulation. We then apply a surface-only Lagrangian wave simulation to this high-resolution point set. We develop novel methods for seeding and simulating waves over surface points, and use them to generate high-resolution details. We avoid error-prone surface mesh processing, and robustly propagate waves without the need for explicit connectivity information. Our seeding strategy combines a robust curvature evaluation with multiple bands of seeding oscillators, injects waves with arbitrarily fine-scale structures, and properly handles obstacle boundaries. We generate detailed fluid surfaces from coarse simulations as an independent post-process that can be applied to most particle-based fluid solvers.
Subspace condensation: full space adaptivity for subspace deformations. Yun Teng, Mark Meyer, Tony DeRose, and T. Kim ACM Transactions on Graphics (SIGGRAPH North America) 2015.
[Abstract]
[Project]
[PDF]
[Source]
[YouTube]
Subspace deformable body simulations can be very fast, but can behave unrealistically when behaviors outside the prescribed subspace, such as novel external collisions, are encountered. We address this limitation by presenting a fast, flexible new method that allows full space computation to be activated in the neighborhood of novel events while the rest of the body still computes in a subspace. We achieve this using a method we call subspace condensation, a variant on the classic static condensation precomputation. However, instead of a precomputation, we use the speed of subspace methods to perform the condensation at every frame. This approach allows the full space regions to be specified arbitrarily at runtime, and forms a natural two-way coupling with the subspace regions. While condensation is usually only applicable to linear materials, the speed of our technique enables its application to non-linear materials as well. We show the effectiveness of our approach by applying it to a variety of articulated character scenarios.
We present the first 3D algorithm capable of answering the question: what would a Mandelbrot-like set in the shape of a bunny look like? More concretely, can we find an iterated quaternion rational map whose potential field contains an isocontour with a desired shape? We show that it is possible to answer this question by casting it as a shape optimization that discovers novel, highly complex shapes. The problem can be written as an energy minimization, the optimization can be made practical by using an efficient method for gradient evaluation, and convergence can be accelerated by using a variety of multi-resolution strategies. The resulting shapes are not invariant under common operations such as translation, and instead undergo intricate, non-linear transformations.
Simulating articulated subspace self-contact. Yun Teng, Miguel A. Otaduy, and T. Kim ACM Transactions on Graphics (SIGGRAPH North America) 2014.
[Abstract]
[Project]
[PDF]
[Source]
[YouTube]
We present an efficient new subspace method for simulating the self-contact of articulated deformable bodies, such as characters. Self-contact is highly structured in this setting, as the limited space of possible articulations produces a predictable set of coherent collisions. Subspace methods can leverage this coherence, and have been used in the past to accelerate the collision detection stage of contact simulation. We show that these methods can be used to accelerate the entire contact computation, and allow self-contact to be resolved without looking at all of the contact points. Our analysis of the problem yields a broader insight into the types of non-linearities that subspace methods can efficiently approximate, and leads us to design a pose-space cubature scheme. Our algorithm accelerates self-contact by up to an order of magnitude over other subspace simulations, and accelerates the overall simulation by two orders of magnitude over full-rank simulations. We demonstrate the simulation of high resolution (100K - 400K elements) meshes in self-contact at interactive rates (5.8 - 50 FPS).
Subspace fluid re-simulation.
T. Kim and John Delaney ACM Transactions on Graphics (SIGGRAPH North America) 2013.
[Abstract]
[Project] [PDF]
[Source]
[YouTube]
We present a new subspace integration method that is capable of efficiently adding and subtracting dynamics from an existing high-resolution fluid simulation. We show how to analyze the results of an existing high-resolution simulation, discover an efficient reduced approximation, and use it to quickly "re-simulate" novel variations of the original dynamics. Prior subspace methods have had difficulty re-simulating the original input dynamics because they lack efficient means of handling semi-Lagrangian advection methods. We show that multi-dimensional cubature schemes can be applied to this and other advection methods, such as MacCormack advection. The remaining pressure and diffusion stages can be written as a single matrix-vector multiply, so as with previous subspace methods, no matrix inversion is needed at runtime. We additionally propose a novel importance sampling-based fitting algorithm that asymptotically accelerates the precomputation stage, and show that the Iterated Orthogonal Projection method can be used to elegantly incorporate moving internal boundaries into a subspace simulation. In addition to efficiently producing variations of the original input, our method can produce novel, abstract fluid motions that we have not seen from any other solver.
Closest point turbulence for liquid surfaces.
T. Kim, Jerry Tessendorf, and Nils Thürey ACM Transactions on Graphics, January 2013.
[Abstract]
[Project] [PDF]
[Source]
[YouTube]
We propose a method of increasing the apparent spatial resolution of an existing liquid simulation. Previous approaches to this "up-resing" problem have focused on increasing the turbulence of the underlying velocity field. Motivated by measurements in the free surface turbulence literature, we observe that past certain frequencies, it is sufficient to perform a wave simulation directly on the liquid surface, and construct a reduced-dimensional surface-only simulation. We sidestep the considerable problem of generating a surface parameterization by employing an embedding technique known as the Closest Point Method (CPM) that operates directly on a 3D extension field. The CPM requires 3D operators, and we show that for surface operators with no natural 3D generalization, it is possible to construct a viable operator using the inverse Abel transform. We additionally propose a fast, frozen core closest point transform, and an advection method for the extension field that reduces smearing considerably. Finally, we propose two turbulence coupling methods that seed the high resolution wave simulation in visually expected regions.
Over the last decade, the special effects industry has embraced physics simulations as a highly useful tool for creating realistic scenes ranging from a small camp fire to the large scale destruction of whole cities. While fluid simulations are now widely used in the industry, it remains inherently difficult to control large scale simulations, and there is an constant struggle for increasing visual detail.
In this course, we will tackle these problems using turbulence methods. Turbulent detail is what makes typical fluid simulations look impressive, and the underlying physics motivate a powerful approach for control: they allow for an elegant split of large scale motion and small scale turbulent detail. This results in a two-stage work flow that is highly convenient for artists: first, a rough, and fast initial simulation is performed, which is then turned into a more detailed one by adding turbulent effects.
This course aims at giving an overview and providing practical guide to employing turbulence modeling techniques for fluid simulations in computer graphics. After reviewing the basics of fluid solvers, and the popular wavelet turbulence approach, we will present several powerful methods to capture advanced effects such as boundary layers, and turbulence with directional preferences. In addition, the difficulties of liquid simulations will be explained, and an approach for liquid turbulence that is based on wave dynamics will be presented.
Physics-based character skinning using multi-domain subspace deformations.
T. Kim and Doug James Symposium on Computer Animation (SCA) 2011. (Best Paper Award)
[Abstract]
[Project] [PDF] [Source]
[YouTube]
We propose a domain-decomposition method to simulate articulated deformable characters entirely within a subspace framework. The method supports quasistatic and dynamic deformations, nonlinear kinematics and materials, and can achieve interactive time-stepping rates. To avoid artificial rigidity, or "locking," associated with coupling low-rank domain models together with hard constraints, we employ penalty-based coupling forces. The multi-domain subspace integrator can simulate deformations efficiently, and exploits efficient subspace-only evaluation of constraint forces between rotated domains using the so-called Fast Sandwich Transform (FST). Examples are presented for articulated characters with quasistatic and dynamic deformations, and interactive performance with hundreds of fully coupled modes. Using our method, we have observed speedups of between three and four orders of magnitude over full-rank, unreduced simulations.
Skipping steps in deformable simulation with online model reduction.
T. Kim and Doug James ACM Transactions on Graphics (SIGGRAPH Asia) 2009.
[Abstract]
[Project] [PDF] [Source]
[YouTube]
Finite element simulations of nonlinear deformable models are computationally costly, routinely taking hours or days to compute the motion of detailed meshes. Dimensional model reduction can make simulations orders of magnitude faster, but is unsuitable for general deformable body simulations because it requires expensive precomputations, and it can suppress motion that lies outside the span of a pre-specified low-rank basis. We present an online model reduction method that does not have these limitations. In lieu of precomputation, we analyze the motion of the full model as the simulation progresses, incrementally building a reduced-order nonlinear model, and detecting when our reduced model is capable of performing the next timestep. For these subspace steps, full-model computation is "skipped" and replaced with a very fast (on the order of milliseconds) reduced order step. We present algorithms for both dynamic and quasistatic simulations, and a "throttle" parameter that allows a user to trade off between faster, approximate previews and slower, more conservative results. For detailed meshes undergoing low-rank motion, we have observed speedups of over an order of magnitude with our method.
We present a novel wavelet method for the simulation of fluids at high spatial resolution. The algorithm enables large- and small-scale detail to be edited separately, allowing high-resolution detail to be added as a post-processing step. Instead of solving the Navier-Stokes equations over a highly refined mesh, we use the wavelet decomposition of a low-resolution simulation to determine the location and energy characteristics of missing high-frequency components. We then synthesize these missing components using a novel incompressible turbulence function, and provide a method to maintain the temporal coherence of the resulting structures. There is no linear system to solve, so the method parallelizes trivially and requires only a few auxiliary arrays. The method guarantees that the new frequencies will not interfere with existing frequencies, allowing animators to set up a low resolution simulation quickly and later add details without changing the overall fluid motion.
Optimizing cubature for efficient integration of subspace deformations.
Steven An, T. Kim, and Doug James ACM Transactions on Graphics (SIGGRAPH Asia) 2008.
[Abstract]
[Project] [PDF] [Source]
[YouTube]
We propose an efficient scheme for evaluating nonlinear subspace forces (and Jacobians) associated with subspace deformations. The core problem we address is efficient integration of the subspace force density over the 3D spatial domain. Similar to Gaussian quadrature schemes that efficiently integrate functions that lie in particular polynomial subspaces, we propose cubature schemes (multi-dimensional quadrature) optimized for efficient integration of force densities associated with particular subspace deformations, particular materials, and particular geometric domains. We support generic subspace deformation kinematics, and nonlinear hyperelastic materials. For an r-dimensional deformation subspace with O(r) cubature points, our method is able to evaluate subspace forces at O(r^2) cost. We also describe composite cubature rules for runtime error estimation. Results are provided for various subspace deformation models, several hyperelastic materials (St.Venant-Kirchhoff, Mooney-Rivlin, Arruda-Boyce), and multimodal (graphics, haptics, sound) applications. We show dramatically better efficiency than traditional Monte Carlo integration.
Hardware-aware analysis and optimization of Stable Fluids.
T. Kim Symposium on Interactive 3D Computer Graphics and Games (I3D) 2008.
[Abstract]
[Project] [PDF]
[YouTube]
We perform a detailed flop and bandwidth analysis of Jos Stam's Stable Fluids algorithm on the CPU, GPU, and Cell. In all three cases, we find that the algorithm is bandwidth bound, with the cores sitting idle up to 96% of the time. Knowing this, we propose two modifications to accelerate the algorithm. First, a Mehrstellen discretization for the pressure solver which reduces the running time of the solver by a third. Second, a static caching scheme that eliminates roughly 99% of the random lookups in the advection stage. We observe a 2x speedup in the advection stage using this scheme. Both modifications apply equally well to all three architectures.
A simple boiling module.
T. Kim and Mark Carlson Symposium on Computer Animation (SCA) 2007.
[Abstract]
[Project] [PDF]
[Source]
[YouTube]
Recent efforts to visually capture the phenomena of boiling have proposed monolithic approaches that extend the basic techniques underlying existing fluid solvers. In this work, we show that if we instead treat boiling as a separate computational module to be loosely coupled to an existing solver, a very easy to implement, highly efficient algorithm can be designed that produces excellent visual results, even on coarse (643) grids. The algorithm is also highly SIMD-amenable, allowing the boiling computation to be farmed out to a GPU or Playstation 3 Cell processor. Our algorithm takes less than 100 lines of commented, readable C++, and can be integrated into an existing particle level set fluid solver with virtually no modifications. A serial implementation consumes between 3-5% of the overall running time, and a preliminary SIMD implementation shows that a 643 simulation runs at 130 FPS, making the computational cost of the module totally negligible.
Feature-guided dynamic texture synthesis on continuous flows.
Rahul Narain, Vivek Kwatra, Huai-Ping Lee, T. Kim, Mark Carlson, Ming Lin Eurographics Symposium on Rendering (EGSR) 2007.
[Abstract]
[Project] [PDF]
We present a technique for synthesizing spatially and temporally varying textures on continuous flows using image or video input, guided by the physical characteristics of the fluid stream itself. This approach enables the generation of realistic textures on the fluid that correspond to the local flow behavior, creating the appearance of complex surface effects, such as foam and small bubbles. Our technique requires only a simple specification of texture behavior, and automatically generates and tracks the features and texture over time in a temporally coherent manner. Based on this framework, we also introduce a technique to perform feature-guided video synthesis. We demonstrate our algorithm on several simulated and recorded natural phenomena, including river streams and lava flows. We also show how our methodology can be extended beyond realistic appearance synthesis to more general scenarios, such as temperature-guided synthesis of complex surface phenomena over a liquid during boiling.
Stable advection-reaction-diffusion with arbitrary anisotropy.
T. Kim and Ming Lin Computer Animation and Social Agents (CASA) 2007.
[Abstract]
[Project]
[PDF]
[YouTube]
Turing first theorized that many biological patterns arise through the processes of reaction and diffusion. Subsequently, reaction-diffusion systems have been studied in many fields, including computer graphics. We first show that for visual simulation purposes, reaction-diffusion equations can be made unconditionally stable using a variety of straightforward methods. Second, we propose an anisotropy embedding that significantly expands the space of possible patterns that can be generated. Third, we show that by adding an advection term, the simulation can be coupled to a fluid simulation to produce visually appealing flows. Fourth, we couple fast marching methods to our anisotropy embedding to create a painting interface to the simulation. Unconditional stability to maintained throughout, and our system runs at interactive rates. Finally, we show that on the Cell processor, it is possible to implement reaction-diffusion on top of an existing fluid solver with no significant performance impact.
Fast animation of lightning using an adaptive mesh.
T. Kim and Ming Lin IEEE Transactions on Visualization and Computer Graphics (TVCG) 2007.
[Abstract]
[Project] [PDF] [Source]
We present a fast method for simulating, animating, and rendering lightning using adaptive grids. The "dielectric breakdown model" is an elegant algorithm for electrical pattern formation that we extend to enable animation of lightning. The simulation can be slow, particularly in 3D, because it involves solving a large Poisson problem. Losasso et al. recently proposed an octree data structure for simulating water and smoke, and we show that this discretization can be applied to the problem of lightning simulation as well. However, implementing the incomplete Cholesky conjugate gradient (ICCG) solver for this problem can be daunting, so we provide an extensive discussion of implementation issues. ICCG solvers can usually be accelerated using "Eisenstat's trick," but the trick cannot be directly applied to the adaptive case. Fortunately, we show that an "almost incomplete Cholesky" factorization can be computed so that Eisenstat's trick can still be used. We then present a fast rendering method based on convolution that is competitive with Monte Carlo ray tracing but orders of magnitude faster, and we also show how to further improve the visual results using jittering.
Fast simulation of laplacian growth.
T. Kim, Jason Sewell, Avneesh Sud, Ming Lin IEEE Computer Graphics and Applications (CG&A) 2007.
[Abstract]
[Project]
[PDF]
[YouTube]
Laplacian instability is the physical mechanism that drives pattern formation in many disparate natural phenomena. However, current algorithms for simulating this instability are impractically slow and memory intensive. We present a new algorithm that is over three orders of magnitude faster than previous methods and decreases memory use by two orders of magnitude. Our algorithm is based on the dielectric breakdown model from physics, but is faster, more intuitive, easier to implement, and simpler to control. We demonstrate the ability of our algorithm to simulate various natural phenomena and compare its performance with previous techniques.
Texturing fluids.
Vivek Kwatra, David Adalsteinsson, T. Kim, Nipun Kwatra, Mark Carlson, Ming Lin IEEE Transactions on Visualization and Computer Graphics (TVCG) 2007.
[Abstract]
[Project] [PDF]
We present a novel technique for synthesizing textures over dynamically changing fluid surfaces. We use both image textures as well as bump maps as example inputs. Image textures can enhance rendering of the fluid by imparting novel realistic appearance to it, whereas bump maps enable the generation of complex micro-structures on the surface of the fluid that may be very difficult to synthesize using simulation. To generate temporally coherent textures over a fluid sequence, we transport texture information, i.e. color and local orientation, between fluid free surfaces from one time step to the next. This is accomplished by extending the texture information from the first fluid surface to the 3D fluid domain, advecting this information within the fluid domain along the fluid velocity field for one time step, and interpolating it back onto the second surface -- this operation, in part, uses a novel vector advection technique for transporting orientation vectors. We then refine the transported texture by performing texture synthesis over the second surface using our `surface texture optimization algorithm, which keeps the synthesized texture visually similar to the input texture and temporally coherent with the transported one. We demonstrate our novel algorithm for texture synthesis on dynamically evolving fluid surfaces in several challenging scenarios.
Modeling ice dynamics as a thin film stefan problem.
T. Kim, David Adalsteinsson, Ming Lin Symposium on Computer Animation (SCA) 2006.
[Abstract]
[Project]
[PDF]
[YouTube]
Large, 3D ice formations such as icicles exhibit a high degree of geometric and optical complexity. Modeling these features by hand can be a daunting task, so we present a novel physically-based algorithm for simulating this phenomenon. Solidification is usually posed as a so-called `Stefan problem', but the problem in its classic form is inappropriate for simulating the ice typically found in a winter scene. We instead use the `thin-film' variant of the Stefan problem to derive velocity equations for a level set simulation. However, due to the scales involved in the problem, even an adaptive grid level set solver is still insufficient to track the tip of an icicle. Therefore, we derive an analytical solution for the icicle tip and use it to correct the level set simulation. The results appear to be in agreement with experimental data. We also present a physically-based technique for modeling ripples along the ice surface that alleviates the need to explicitly track small-scale geometry. To our knowledge, our approach is the most complete model available, and produces complex visual phenomena that no previous method has been able to capture.
Physically based animation and rendering of lightning.
T. Kim and Ming Lin Pacific Graphics 2004.
[Abstract]
[Project] [PDF]
[YouTube]
We present a physically-based method for animating and rendering lightning and other electric arcs. For the simulation, we present the dielectric breakdown model, an elegant formulation of electrical pattern formation. We then extend the model to animate a sustained, "dancing" electrical arc, by using a simplified Helmholtz equation for propagating electromagnetic waves. For rendering, we use a convolution kernel to produce results competitive with Monte Carlo ray tracing. Lastly, we present user parameters for manipulation of the simulation patterns.
A hybrid algorithm for modeling ice formation.
T. Kim, Michael Henson, Ming Lin Symposium on Computer Animation (SCA) 2004.
[Abstract]
[Project] [PDF]
[YouTube]
We present a novel algorithm that simulates ice formation. Motivated by the physical process of ice growth, we develop a novel hybrid algorithm by synthesizing three techniques: diffusion limited aggregation, phase field methods, and stable fluid solvers. Each technique maps to one of the three stages of solidification. The visual realism of the resulting algorithm appears to surpass that of each technique alone, particularly in animations of freezing. In addition, we present a faster, simplified phase field method, as well as a unified parameterization that enables artistic manipulation of the simulation. We illustrate the results on arbitrary 3D surfaces.
Visual simulation of ice crystal growth.
T. Kim and Ming Lin Symposium on Computer Animation (SCA) 2003.
[Abstract]
[Project] [PDF]
The beautiful, branching structure of ice is one of the most striking visual phenomena of the winter landscape. Yet there is little study about modeling this effect in computer graphics. In this paper, we present a novel approach for visual simulation of ice growth. We use a numerical simulation technique from computational physics, the "phase field method," and modify it to allow aesthetic manipulation of ice crystal growth. We present acceleration techniques to achieve interactive simulation performance, as well as a novel geometric sharpening algorithm that removes some of the smoothing artifacts from the implicit representations. We have successfully applied this approach to generate ice crystal growth on 3D object surfaces in several scenes.
Inside the levy dragon.
Scott Bailey, T. Kim, Robert Strichartz The American Mathematical Monthly 2002.
[Abstract]
[Project]
The Lévy Dragon is a well-known fractal introduced by Paul Lévy in 1938. It is a connected subset of the plane with interior (in fact it tiles the plane) but the interior is disconnected. Although the dragon has a fractal boundary of dimension 1.934007..., we show that each component of the interior has a polygonal boundary (with perhaps infinitely many edges) of finite length. There are infinitely many components, but we conjecture that they are all similar to one of sixteen different shapes. We show pictures of these shapes and some of the ways they interweave when two smaller dragons combine to make a larger dragon. We explain how we used the computer as a kind of "microscope" to reveal this structure. More pictures and programs are available on the web site http://www.mathlab.cornell.edu/~twk6/.
The geometric and optical complexity of ice has been a constant source of wonder and inspiration for scientists and artists. It is a defining seasonal characteristic, so modeling it convincingly is a crucial component of any synthetic winter scene. Like wind and fire, it is also considered elemental, so it has found considerable use as a dramatic tool in visual effects. However, its complex appearance makes it difficult for an artist to model by hand, so physically-based simulation methods are necessary. In this dissertation, I present several methods for visually simulating ice formation. A general description of ice formation has been known for over a hundred years and is referred to as the Stefan Problem. There is no known general solution to the Stefan Problem, but several numerical methods have successfully simulated many of its features. I will focus on three such methods in this dissertation: phase field methods, diffusion limited aggregation, and level set methods. Many different variants of the Stefan problem exist, and each presents unique challenges. Phase field methods excel at simulating the Stefan problem with surface tension anisotropy. Surface tension gives snowflakes their characteristic six arms, so phase field methods provide a way of simulating medium scale detail such as frost and snowflakes. However, phase field methods track the ice as an implicit surface, so it tends to smear away small-scale detail. In order to restore this detail, I present a hybrid method that combines phase fields with diffusion limited aggregation (DLA). DLA is a fractal growth algorithm that simulates the quasi-steady state, zero surface tension Stefan problem, and does not suffer from smearing problems. I demonstrate that combining these two algorithms can produce visual features that neither method could capture alone. Finally, I present a method of simulating icicle formation. Icicle formation corresponds to the thin-film, quasi-steady state Stefan problem, and neither phase fields nor DLA are directly applicable. I instead use level set methods, an alternate implicit front tracking strategy. I derive the necessary velocity equations for level set simulation, and also propose an efficient method of simulating ripple formation across the surface of the icicles.
ACM SIGGRAPH Asia Technical Papers, 2016-2017,2020-2021
ACM SIGGRAPH Technical Papers, 2015,2018-2019
Pacific Graphics, 2011-2012,2015-2016,2019
ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, 2011-2017
Eurographics Full Papers, 2016-2017
Eurographics Short Papers, 2011-2012
Graphics Interface, 2010, 2012
Eurographics Workshop on Natural Phenomena, 2007,2009
Teaching
Confronting euro-centrism and erasure in discrete math.
T. Kim, January 2021.
[Abstract]
[Project]
[PDF]
This is a summary of measures I took in Fall 2020 to confront Euro-Centrism and the historical erasure of non-Western figures in a discrete math course, CPSC 202: Mathematical Tools for Computer Science. These measures included investigations of Boolean logic and Pascal's Triangle, and an examination of the naming double standards applied to Euclid's Algorithm vs. the Chinese Remainder Theorem. Students were given the opportunity to investigate the history further as an optional bonus assignment in the run-up to the 2020 US presidential election. I also summarize some of their remarkable findings.
Assembling a talk: two wrong ways and a right way.
T. Kim, November 2019.
[Abstract]
[Project]
[PDF]
I present two bad algorithms for assembling a technical talk, and one good one. There's more than one way to make a good talk. You don't have to use mine. Just don't use the bad ones.
CPSC 679: Physics Simulation for Movies and Games, Fall 2019, Spring 2022 CPSC 202: Mathematical Methods for Computer Science, Fall 2020, 2021 CPSC 478/578: Introduction to Computer Graphics, Spring 2021, Fall 2023 CPSC 478/578: Introduction to Computer Graphics, Spring 2020 MAT 200C: Pattern Formation, Spring 2015 [Webpage] [Tumblr] MAT 200C: Pattern Formation, Spring 2014 [Webpage] [Tumblr] MAT 594G / CS 290I: Physically Based Simulation and Animation, Winter 2014 CS 180: Computer Graphics, Fall 2013 MAT 200C: Pattern Formation, Spring 2013 [Webpage] [Tumblr] MAT 594G / CS 290I: Physically Based Simulation and Animation, Winter 2013 CS 280: Advanced Computer Graphics, Fall 2012 [Webpage] MAT 200C: Pattern Formation, Spring 2012 [Webpage] [Tumblr] MAT 594G / CS 290I: Physically Based Simulation and Animation, Winter 2012
