Publications - Master's Thesises

1. Myoung-Jun Kim. A Heuristic Approach For Strip Packing. Master's thesis, CS Dept., KAIST, 1991.
   Keywords
   packing rectangle, computer graphics
   Abstract
   The two-dimensional strip-packing problem arises frequently in stock-cutting, scheduling, and VLSI design. In this problem, a finite list of rectangles is to be packed into a rectangular bin of finite width and infinite height. The objective is to minimize the height of the region occupied by the packed rectangles. Since the problem in Np-hard, heuristic algorithms have been used for finding a good solution. This thesis proposes three new heuristic algorithms for solving the two-dimensinal strip packing problem. The first two algorithms are employed as underlying strategies for the last. Based on the idea of filling the lowest place in the bin, these two strategic algorithms show similar behavisors to the well-known Baker's bottom-left algorithms. However, both of them can pack n rectangles in O(nlogn) time, which lowers the O(n2) upper bound in time complexity for the Baker's algorithms. The last algorithm adopts a strategy of combining the better aspects of the two algorithms. Specifically, it starts with the width-based algorithm and then changes to the height-based one as it is appropriate. Experimental results support that the strategy-combining algorithm outperforms other algorithms including the two strategic ones.
    
2. Nak-Hun Baek. An Effective Text Processing Method For CGM. Master's thesis, CS Dept., KAIST, 1992.
   Keywords
   computer graphics, graphical user interfaces, text processing
   Abstract
   While many grayscale displays have appeared on the scene, few text output techniques utilize their capability effectively. Additionally, a higher-quality text representation method is required when using computer graphics standards such as CGM(Computer Graphics Metafile) and CGI(Computer Gramphics Interface). In this paper, a bitmap-based text output method for grayscale output devices is described. This method supports two-dimensional graphics operations by handing both character images and bitmap representations equivalently. An improved filtering technique on bitmap images is adapted to this task. Given method outperforms traditional bitmap font techniques in the aspects of space-requirement, flexibility, quality, and font design cost. Higher flexibility of this method makes it possible to fully support the specifications of CGM and CGI, which cannot be directly satisfied by ordinary text output methods. In addition, higher-quality bitmap images can be displayable.
    
3. Dae Seoung Kim. A Linear Time Algorithm For Constructing The Circular Visibility Region Of A Simple Polygon. Master's thesis, CS Dept., KAIST, 1992.
   Keywords
   visibility, polygons, computer algorithms
   Abstract
   Given a simple polygon P, two points in P are said to be visible if they can be connected by a line segment contained in P. Since a line segment can be regarded as an arc of infinite radius, the notion of visibility can be generalized as follows : two points in P are circularly visible if there exists an arc contained in P joining them. In this paper we represent a linear time algorithm for constructing the potion of P that can be circularly visible from a fixed point lying inside P.
    
4. Gu-Jin Kim. A Bottleneck Finding Algorithm And Its Applications. Master's thesis, CS Dept., KAIST, 1992.
   Keywords
   computer graphics, computer algorithms, polygons
   Abstract
   The graphic command called "hollow drawing" is a primitive of graphic operations, which renders the boundary of a given polygon. When drawing a hollow on a simple polygon, it is hard for a hollow pattern neither to self-intersect nor to be drawn outside of the polygon. These difficulties are characterized by formulating the notion of a bottleneck in a simple polygon. Using the Voronoi diagram of a simple polygon, we present an O(n long n) time algorithm for finding all bottlenecks of the simple polygon with n vertices. This leads to an efficient algorithm for drawing a hollow. It also gives a fast method for generating NC milling tool paths.
    
5. Dong Jin Kim. An Approach For Animating A Flexible Object. Master's thesis, CS Dept., KAIST, 1993.
   Keyword
   computer animation
   Abstract
   This paper proposes a physically-based model for flexible objects such as cloth, rubber, paper, vinyl, and flexible metals. Properties of a flexible object are determined by its basic components such as atoms molecules, and particles, their underlying structure, and their interaction forces. Since even a very thin object such as a cloth has its volume in physical worlds, we decompose a flexible object into and array of unit volumes containing basic components so that they form a crystal structure of basic components and use the elasticity theory to control their interaction forces. The proposed model naturally describes varous properties of flexible objects such as stretching, bending, and shearing effects. This model can consistently manipulate both thick and thin objects and also describe the different behavious between a very flexible object and a somewhat rigid one in a uniform way.
    
6. Gyou-Hwan Oh. An Effective Texture Generation Method Using The Surface Characteristics. Master's thesis, CS Dept., KAIST, 1993.
   Keywords
   computer graphics, texture
   Abstract
   This thesis proposes an effective method for generating two dimensional texture patterns useful for fashion objects such as cloths, neck-ties, scarfs, curtains, carpets, and wall-papers. This method is based on the visualization of surface charcteristics, so that a generated image reflects the shape of the surface. The texture generation process consists of three procedures surface construction, vector extration, and mapping a vector to a color. The surface construction is a procedure for interactively designing a B-spline surface. The vector extraction is for calculating a geometric vector from the characteristics of a surface. The color mapping is a visualization procedure which converts the geometric vector onto a color. The proposed method provides an effective controls on the shape and colors of an image, its fast generation, its local deformation. In addition, this model is easily expandable by introducting a new class of geometric vectors or color tables. It can also be extended for texture mapping and solid texturing.
    
7. In-Hyeok Paek. Physically-based Flame Modeling. Master's thesis. CS Dept., KAIST, 1993.
   Keywords
   computer graphics, flame, flame visualization
   Abstract
   This thesis presents a new method for generating flame images based on an approximation of their physical process. The approximation includes combustion of fuels and analysis of fluid flows in a combustion field. A set of partial differential equations from fluid dynamics are employed and simplified to analyze fluid flows in the combustion field. These equations are solved with a modified version of an alternating direction implicit method. The combustion field is divied into uniform staggered grid cells. Each iteration of the method consists of adding fuels to cells combusting fuels, updating state variables and generating a 2D flame image. This model accounts for laminar flames with premixed and diffusion combustion. Unlike previous flame models in computer graphics, the proposed model can naturally generate special effects such as a wind effect by changing parameters.
    
8. Tae-Joon Park. Physically-based Surface Triangulation For Parametric Surfaces. Master's thesis, CS Dept., KAIST, 1993.
   Keywords
   triangulation, computer graphics
   Abstract
   This thesis proposes an efficient physically-based method to generate a triangular mesh that approximates a parametric surface. As an approximation of the curvature characteristics of a surface region, we propose the curvature feature, that is a computationally simple but effective measure of the surface curvedness. In the proposed algorithm, the curvature feature of a surface region is regarded as an attracting force, and applied to a vertex using a spring model. The surface curvedness is distributed uniformly over the mesh by this algorithm. To determine the location of each vertex in the mesh, an initial triangulation is formed using the restricted quadtree and iteratively optimized based on the spring model. Since our approach uses a local optimization instead of a global optimization to determine the location of each vertex at each optimization step, a mesh can be generated fast enough for interactive applications.
    
9. Young-Seop Shin. Simplification Of Triangular Mesh. Master's thesis, CS Dept., KAIST, 1994.
   Keywords
   triangulation, computational complexity
   Abstract
   Triangular mesh simplification is to reduce the number of triangles in a triangular mesh while preserving the topology and geometry. This thesis presents an efficient algorithm that simplifies a given mesh by reducing the number of vertices. As a removal criteria, we propose the area feature that is a weighted sum of the total curvature and the area. By adjusting the weighting factor, we are able to control the shape of the resulting mesh. An approximation method of the total curvature in the triangular mesh is also presented. Because the proposed method uses only local information, it is fast enough to be used in interactive applications.
    
10. Ho Kyung Kim. Three-dimensional Metamorphosis Between Sweeping Objects. Master's thesis, CS Dept., KAIST, 1994.
    Keywords
    computer graphics, metamorphosis. 3-dimensional metamorphosis
    Abstract
    Metamorphosis between two objects has gained a lot of attention because of its astonishing effect in computer animation. In many applications, twodimensional metamorphosis has been used and shows the excellent results. However, it has many limitations due to its lacks of the three-dimensional information. Therefore, metamorphosis between two three-dimensional objects is required to make a vivid and smooth transformation. This paper presents an effective three-dimensional metamorphosis algorithm which smoothly changes the shape of one sweeping object to another. By using the sweeping object's characteristics, an efficient method of transformation is found. The proposed algorithm finds the correspondence between a pair of given sweeping objects and generates the intermediate objects by interpolating the corresponding vertices of source and destination objects. This algorithm provides the fast and smooth transformation, and generates the meaningful inbetween objects.
     
11. Jehee Lee. Computer-aided Sculpturing Based On Boolean Operations And Extended Recursive Subdivision. Master's thesis, CS Dept., KAIST, 1995.
    Keywords
    computer graphics, computer-aided design
    Abstract
    A computer-aided sculpturing system is a geometric modeling system possessing sculpturing operators. A real world sculptor carves a statue through chiseling, sandpapering, and so on. Computer-aided sculpturing systems adapt these sculpturing methods for the geometric modeling domain. In this paper, we propose a sculpturing system based on sculpturing operators, chiseling, gluing and rounding. Chiseling can cut off a part of a sculpture, and gluing paste a lump of material. We implemented chiseling and gluing using sweeping operators and boolean operators for polyhedra. A global shape design method based on three-view shillouettes is also suggested. Rounding operators generate smooth surfaces which connect sharp corners smoothly. As rounding operators of our system, we present extended recursive subdivision by localizing Catmull and Clark's recursive subdivision methods. The proposed subdivision methods can generate blended shapes of curved and planar surfaces. As applications of these methods, we present a unified local algorithm for vertex-based, edge-based, and region-based roundings.
     
12. Seok-Hoon Ko. Effective Soft Shadow Generation Using An Iso-lux Contour Mesh. Master's thesis, CS Dept., KAIST, 1995.
    Keywords
    computer graphics, wire netting, image reproduction
    Abstract
    Mesh generation techniques are useful for synthesizing realistic images with limited computational resources. When images are generated from meshes, we can enhance image quality with considering discontinuities, orientations, and shapes of meshes. This thesis presents a new mesh generation technique which can be used to produce soft shadows, one of the most effective features for realistic images. We first present efficient penumbra and umbra generating algorithms in O(n + m) and O(m + nlogn) time, respectively, where m and n are the number of vertices of a convex polygonal light source and an object. We also propose a new mesh generation algorithm, called an iso-lux contour meshing, which subdivides meshes along the iso-lux contour. Since this method reflects properties of intensity such as irradiance gradients, we can rapidly generate realistic images with the small number of large scaled mesh elements. Our mesh generation technique can be used for interactive applications such as virtual reality and walkthrough.
     
13. Seong-Jin Yoon. Partial Generation Of Random Fractal And Its Applications. Master's thesis, CS Dept., KAIST, 1995.
    Keywords
    computer animation, fractals, reproduction
    Abstract
    Fractal modeling, based on fractional Brownian motion(fBm), is one of the most popular methods used for modeling natural objects. To reflect complex shapes of natural objects, objects modeled by fractal modeling require a vast amount of data, which consumes much memory space, generation time, and rendering time compared to artificial objects. In this paper, we propose a new method for partial generation of fractal objects with appropriate levels of detail to reduce memory usage and thus efficiently synthesize fractal images. This can be achieved by generating only the parts of fractal objects within a view volume and by avoiding unnecessary data ampilification while satisfying given levels of detail. The proposed partial generation scheme is successfully applied to efficient animation of a walkthrough over fractal objects according to the movement of a view. For faster animation, we also propose a method to incrementally generate fractal objects using the object-level coherency when the view is slightly changed.
     
14. Hyung-Woo Kang. Interactive Pattern Design With Image Simplification Process. Master's thesis, CS Dept., KAIST, 1996.
    Keywords
    pattern design, motif design, drawing techniques, apparel CAD, graphics
    Abstract
    Computer-aided-pattern design systems are now widely used by designers to reduce the time and expences in generating new patterns. However, currently-available commercial systems are either restricted to generate geometric patterns, or not yet enough to offer an automatic and efficient tools for making natural patterns. In this thesis, we develop an interactive pattern design system, which generates aesthetic patterns from scanned images. Pattern is generated in our system by the following four steps: motif extraction, motif simplification, motif drawing, motif placement. In developing our system, we have tried to make the system satisfy both of the two conflicting demands: minimizing manual tasks and maximizing interactivity. We enhance interactive techniques for motif extraction and simplification. We also propose various drawing tools to add artistic effects on a simplified motif. Using our system, designers can easily generate a nice pattern from an initial image by interactively following the given steps. Experimental results show how each technique is used and what effect it has.
     
15. Hyung-Jin Ha. A New Camera Control Method Preserving View-up Vectors. Master's thesis, CS Dept., KAIST, 1996.
    Keywords
    common view-up vector, quaternion, camera Animation, graphics
    Abstract
    In 3D computer animation, a virtual camera moves while preserving the upward direction of 3D space, which is given by the view up vector. For many applications, it is necessary to specify arbitrary view up vectors. However, traditional camera methods to do this cause severe singularity and redundancy in their parametrizations. In this thesis, we present a new camera control method which is free from the problems. We first introduce the notion of the common view up vector, which is the view up vector shared by two camera orientations. From a camera motion, we isolate the rotation component determining the path of the common view up vector. We present a new orientation curve, called an optimal camera otientation curve, which minimizes the torque history of this component. The optimal camera orientation curve has the camera upright property, i.e., it preserves the direction of a common view up vector as much as possible. We obtain an analytical formula of an optimal camera orientation curve passing two camera orientations, called a Clerp. To find an optimal camera orientation curve satisfying general boundary conditions, we extend traditional unconstrained optimization techniques in Euclidean space to the unit quaternion space for numerically computing camera orientation curves. We finally give a number of practical camera path construction schemes to generate curves with the camera upright property.
     
16. Bomjun Kwon. An Efficient Walkthrough System Using Visiility Layers. Master's thesis, CS Dept., KAIST, 1996.
    Keywords
    visibility, walkthrough, rendering, invisible face, graphics
    Abstract
    Given a large geometric model like a building, it is an important issue in computer graphics to develop an efficient walkthrough algorithm for interactively rendering the model. We can significantly speed up the rendering by accelerating a clipping operation and precomputing invisible polygons. Kim et al. suggested Visibility layers which provide efficient visibility operations from a given source. The visibility layers maintain the polygons in the geometric model in a sequence of layers according to their visibility relationship with respect to the source. For each layer, they constructed the shadow region from the source cast by the polygons in the layer. Every ray shot from the source intersects the boundary of the shadow region at most once. From this fact, they developed an efficient clipping operation for a viewer in the source. In order to generate an image from an arbitrary points, we divide the 3D scene space into cells using grids, octrees or binary space partition trees, and then construct visibility layers for each cell. These visibility layers efficiently support the clipping operation from any view point in the 3D scene space. Moreover, in order to increase the performance of the clipping operation, we develop compact $visibility$ $layers$ to reduce the number of layers. We also suggest an algorithm for efficiently eliminating the invisible polygons from each cell. Our experiment shows that this method is well adapted to various environments including densely occluded models and sparsely occluded models.
     
17. Hyun-Joon Shin. An Impulse-based Model For Multiple Point Collisions In Dynamic Simulation. Master's thesis, CS Dept., KAIST, 1997.
    Keywords
    dynamic simulation, impulse, collision response, multiple point, animation
    Abstract
    This thesis presents an impulsive-based multi-point collision response model. Most previous approaches solve single point collisions, and a regional collision is approximated as a sequence of single point collisions. For more stable simulations, this thesis introduces the distribution of impulses over a collision region. The total impulse for the region is calculated from its impulse distribution. This model eliminates abnormal oscillations in which conventional models have experienced. Therefore, colliding objects are converging to their stable positions more quickly. Moreover, this model can incorporate friction on the collision region. Since previous impulse-based models are short in handling multi-point collisions, additional physical model are required for multi-point contacts. In contrast, this model take a unified approach that is capable of covering both collisions and contacts. Therefore, this model clearly resolves the difficulty in transition between collision and contact.
     
18. Cheol-Min Lee. A Scripting Language For Real-time Interactive Animation. Master's thesis, CS Dept., KAIST, 1997.
    Keywords
    script, scripting language, animation, interactive animation
    Abstract
    Scripting languages (or animation languages) are useful tools to describe computer animations, especially suitable for producing animation prototypes and designing interactive animations. Scripting languages should be designed to describe various aspects of animation in a natural way. In interactive animations, it is sometimes necessary to describe non-predetermined actions. Actions are called non-predetermined when their occurring moments cannot be predicted in advance. This thesis presents ARIA, a new scripting language for real-time interactive animations in 3D virtual environments. Using this scripting language, the animators can effectively produce the synthetic world in which human-directed avatars and computer-controlled agents interact with each other in real-time. ARIA provides features for describing non-predetermined actions and synchronization among actions in interactive animations. To execute the features of the ARIA scripting language, the ARIA script system uses the concepts of execution trees and events.
     
19. Ja-Hee Kim. Extened Light Buffers For Efficient Visibility Operations. Master's thesis, CS Dept., KAIST, 1997.
    Keywords
    visibility, light buffer, soft shadow, ray tracing, rendering, invisible face, graphics
    Abstract
    It is important issue to increase the efficiency of visibility operations in rendering since the most of rendering time is spent for performing visibility operations. In this paper, we present light buffers of area light sources, which provide efficient visibility operations from the sources. The light buffers are extended to support visibility operations not originated from the sources. We also explore their applications such as shadow generation, raytracing and radiosity. Our experimental results show that the light buffers support more efficient visibility operations than the previously developed data structures including linear grids, and octrees.
     
20. Min-Gyu Choi. Walking Trajectory Planning For Virtual Humans. Master's thesis, CS Dept., KAIST, 1998.
    Keywords
    walking motion, trajectory planning, footprints
    Abstract
    For a virtual human, it is one of the most fundamental activities to walk from one location to another while avoiding collision with obstacles. The walking trajectory planning, that is composed of the path planning in 2D and the footprint generation, is very important in providing a virtual human with such an activity. Beside the collision avoidance, the characteristics of the human behavior should be reflected to give realistic movements in the path planning. In the footprint generation, a sequence of footprints, from which a realistic walking motion can be readily obtained, should be sought. In this thesis, we present an efficient walking trajectory planning algorithm for virtual humans. We first decompose the workspace into sparse and dense regions, and introduce the hybrid roadmap that combines the tangent visibility graph of sparse regions and the Voronoi skeleton of dense regions to reflect the responsive behavior of an actual human. The roadmap is used to efficiently obtain a center-site path of the polygonal mover that is the projection of the articulated human figure. In order to generate a sequence of footprints following the obtained path, we introduce a characteristic volume that stores the model-dependent relation between two legs and determines omni-directional step positions efficiently. Using a characteristic volume and the bisection technique, we keep the stance foot from blocking the swing foot, the swing foot from colliding with obstacles, and two feet from intersecting each other to obtain footprints from which a walking motion can be readily generated.
     
21. Tae-Hoon Kim. Real-time Capturing Of Facial Expressions Using Contour Model And Head Tracking. Master's thesis, CS Dept., KAIST, 1999.
    Keywords
    facial expression capture, head tracking
    Abstract
    Producing facial expressions is very important for realistically animating a virtual actor. It is difficult to make facial expressions interactively because of their subtlety. Therefore, realistic facial expressions of the virtual actor are often produced automatically by capturing the facial expressions of a puppeteer with a video camera and mapping them to the actor. Capturing facial expressions needs to not only extract feature points but also track head motion from the input image. Because the image is largely affected by lighting conditions and noises, an important issue is to improve the stability of capturing and its performance. This thesis describes the real-time capturing of facial expressions that tracks both the movements of facial feature points and head motion directly from the input image. In CMYK and HSV color spaces, M and H values of lips are different from those of skin. Moreover, K and V values of eyes or eyebrows are also different from those of skin. Therefore, we transform the color space of the input image to that composed of M, K, H, V color values for easy facial feature segmentation. We use a contour model based on the Bezier curve of degree 3 that is a simple parameterized curve to represent the shape of a facial feature. This model fits the curve to the contour of the feature, which can robustly capture the shape of each facial feature even with a noisy image. To track the head motion, we choose a number of points on the face fixed with respect to the evolution of facial expressions. We select every triple of the points in turn which are not colinear and track their 3D positions. It is well-known that the 3D positions of those points are not uniquely determined. We use the coherency of head motion to choose the correct solution. Finally, we combine the tracking results of all triples for robust head tracking.
     
22. Soon-Hyoung Pyo. Tour Into The Picture (TIP) Using A Vanishing Line. Master's thesis, CS Dept., KAIST, 1999.
    Keywords
    3D graphics, image-based modeling/rendering, animation
    Abstract
    Tour into the picture(TIP) proposed by Horry et al.\cite{horry} is a technique that uses only one reference image to construct a 3D environment and generates a new image viewed from an arbitrary view point using the 3D structure. This feature differentiates TIP from other image based rendering(IBR) techniques that use several reference images. The method of Horry et al. makes good results by intuitively extracting and analysing 3D information from an image. However, their method can be applied to images where only one vanishing point exists. In this thesis, we propose a new background modeling method and an interface that work well with any images regardless of the number of vanishing points. In the proposed method we use vanishing line instead of vanishing point. Since the vanishing line has a characteristic of dividing image into two regions corresponding to the ground and the space above it, we construct environment with two planes which represent both regions. Moreover, because vanishing line is a set of vanishing points, we can apply our method to images with multiple vanishing points.
     
23. Juno Kim. An Effective Cell Division Method For Directed Line Classification. Master's thesis, CS Dept., KAIST, 1999.
    Keywords
    direct line classification, ray classification, cell division, visibility operation
    Abstract
    In computer graphics, there have been developed various kinds of rendering methods for the last three decades, to generate more realistic images faster. An important issue in rendering is to develop a data structure which provides efficient visibility oprerations, because the most of the rendering time is spent for performing them. Kwon et. al\cite{Kwon:1998:ERC} present a new ray classification scheme, called directed line classification, that considerably reduces memory consumption while preserving the time efficiency of Arvo and Kirk\cite{Arvo:1987:FRT}'s scheme. In that scheme, they use two kinds of cell division scheme such as uniform subdivision, hierarchical subdivision. In the hierarchical subdivision scheme, they subdivide the boundary faces of both origin and destination at the same time. In this thesis, we present a new cell subdivision scheme, called origin first hierarchical subdivision, which gives an adaptive structure reducing memory requirement and an improvement for more applicability. Our scheme subdivides the origin faces first, and then subdivides destination faces. By using this scheme, each cell has a more adaptive shape to the spartial distribution of objects to have different sizes of origin and destination faces. This subdividing scheme is effective for point-to-region or region-to-region visibility operations. We can further reduce memory requirements by using candidate elevation and cell merging which take a good advantage of the coherency between the objects saved in each cells which appeared near location in data structure. Our experiments indicate that the origin first hierarchical subdivision scheme improves the efficiency of the rendering process for various types of visibility operations in the advanced rendering applications such as ray tracing and radiosity.
     
24. Sung Yong Kim. Generation of curved path locomotion using motion data. Master's thesis, CS Dept., KAIST, 2000.
    Keywords
    Locomotion, Motion editing, Spacetime constraint
    Abstract
    Generating realistic animation of human locomotion is an important issue in computer graphics. Recently, motion capture technique is widely used to obtain realistic motion data in character animation. In this thesis, we propose a new method that generates human locomotion along a given curved path using prescribed motion clips. Provided with various realistic motion segments such as straight walking, turning to left and turning to right, we perform the following three steps. First, we select appropriate motion segments for the given path and stitch them to yield an initial motion. Then, we specify foot positions and orientations to deform the initial motion to follow the given path, and finally we adjust the initial motion to meet the specified foot positions and orientations. We exploit curvature profiles of the given path and the body trajectory of each motion to select appropriate motion segments. Obtained by simply stitching those motion segments, the initial motion may not be appropriate for a human-like figure to follow the given path. Therefore, we deform the initial motion to adapt for the path. We extract the postions and orientations of stance foot from the initial motion, and transform them along the path to specify the desired positions and orientations for curved path locomotion. Then, we adjust the initial motion to satisfy the desired foot positions and orientations. This problem can be formulated as a motion editing problem with spacetime constriants. We adopt a hierarchical displacement mapping technique[11] to deform the body and other joint angles so that the motion meet the constraints such as foot positions and orientations. We demonstrate that the suggested method produce a realistic locomotion. The method also enables a human-like figure to perform a variety of movement such as walking, jogging, and so on.
     
25. Shin, Seung-Hyup. Real-time Human Body Deformation Based on Rotation Angle Interpolation. Master's thesis, CS Dept., KAIST, 2000.
    Keywords
    Body deformation, Quaternion, Delaunay triangulation
    Abstract
    Human body deformation is widely used to generate a realistic animation. In such an animation, a human body is generally modeled as a one-skin mesh, and is deformed by adjusting vertex positions according to its posture. However, it is difficult to compute in real time the new vertex positions that preserve the characteristics of the human body. In this thesis, we propose a new approach to real-time human body deformation based on the interpolation of the rotation angle of each vertex of the mesh. We focus on preserving the skin characteristics such as shrinking and expanding resulting from the rotation angle interpolation. Hence, a vertex position is adjusted according to the interpolation result. That is, when a link segment rotates by a certain angle, the vertices associated with the segment also rotate by certain angles. Those vertices are decided by the Delaunay triangulation on both the center points of link segments and the vertices of the mesh. Given the rotation angle of a link segment, each associate vertex is assigned its own rotation angle depending on the distance from the link center. Thereby, the distance between neighboring vertices may be changed due to vertex rotation, which reflects the characteristics of the real human skin. While preserving the characteristics of a human body, our approach is fast enough for real-time applications since deformation can be done by vertex rotation only.
     
26. Kim, Dohan. Motion Tracking of 3D Articulated Figure from 2D Information of A Single Video Stream. Master's thesis, CS Dept., KAIST, 2001.
    Keywords
    3D Motion Tracking, Articulated Figure, extended Kalman filter, 2D video
    Abstract
    A Huge amount of human activities and motions are recorded in a single sequence of uncalibrated video images. In this thesis, we present a method for reconstructing the 3D human motions with respect to 2D motion information contained in a single video stream. 2D information is formed as a sequence of 2D position set and acquired by interactive marking. The reconstruction process can be formulated as an inverse kinematics problem. We model a human body as a non-linear dynamic system and adopt a extended Kalman filter as a inverse kinematics solver so as to resolve depth ambiguity. Our Kalman filter tracks the joint motion spanning entire orientation space by parameterizing the orientations incrementally with rotation vector. We augment the measurement model with the angle-bound constraints prevent infeasible motions. To avoid singularities which arise in inverse kinematics problem, the analyses on the Singularity-Robust inverse [17, 9] are adapted to make the Kalman filter avoid singular states.
     
27. Kim, Hee-Jeong. Vitual MR Tagging Method for Verification of 3D Motion Reconstruction Techniques. Master's thesis, CS Dept., KAIST, 2001.
    Keywords
    Virtual MR tagging, SPAMM
    Abstract
    Recently, MR tagging techniques have been getting a lot of attention from researchers since they provide non-invasively suitable data sets for cardiac motion analysis. Several different techniques have been developed to analyze 3D cardiac wall motion from such data sets. Unfortunately, due to the lack of gold standard data sets to be tested on, most of the techniques are not fully evaluated. In this dissertation, we have developed a virtual MR tagging method which generates MR tagging images, in particular SPAMM (Spatial Modulation of Magnetization) images, on a virtual deformable model. At the initial undeformed state, the user lays out tagging planes, which are orthogonal to the image plane, by specifying their locations and spacing in-between to tag a grid on the cardiac wall. During the simulation of deforming the model, the grid tagged on the model move together to reflect the underlying tissue motion in 3D. On the image plane, the deformed grid is computed and displayed to give virtual SPAMM images. These images have the similar characteristics of SPAMM images that we would obtain using a real MR machine. The virtual images can be used to fit the model using a technique to be evaluated and to compare the results with the known, actual 3D deformation information.
     
28. Junkyu Oh. Hierarchical Behavior Generation Framework for Evevt Driven Crowd Simulation and Its Application to Long Distance Race. Master's thesis, CS Dept., KAIST, 2002.
    Keywords
    computer graphics, crowd simulation, behavior generation
    Abstract
    A large number of people in streets, parks, or public squares form a crowd to show complicated scenes often appeared in applications such as computer games and movie films. Crowd simulation is a technique to automatically generate a crowd scene by simulating the behavior of the crowd. In this paper, we address two problems in crowd simulation. First is the time complexity problem. It cost a plenty of time to simulate a crowd because a crowd is usually large in number. To address this problem we adopt the event driven collision detection algorithm. The second problem is the difficulty of designing powerful behavior generation framework. It must be powerful enough to generate many crowd behaviors especially complex ones. To address this problem, we propose a hierarchical behavior generator. Hierarchical structure decompose a complex behavior into many simple behaviors. Therefore we can assemble simple low level behaviors to make a complex high level behavior easily. Furthermore, for variety of the crowd behavior, behavior generation framework enable the animator to define the motions and the decisions specifically. To do this, we use an external module for motion generation and decision making. Proposed event driven crowd simulator is fast enough to simulate many virtual characters. Also the hierarchical behavior generation framework can cover the various and complex crowd behaviors.
     
29. Yoon, Keun Chang. Motion Synthesis with Extended Posture Transition Graph and Dynamic Motion Balancing. Master's thesis, CS Dept., KAIST, 2002.
    Keywords
    Posture Transition Graph, Dynamic Balancing, Zero Moment Point, Motion Synthesis, Character Animation
    Abstract
    This paper presents a technique for generating DDR dance motion interactively according to the specified user input. In generating a dance motion, we have to consider that the same sequence of steps does not necessarily mean the same movement. In order to generate a variety of dance motion, we have introduced an Extended Posture Transition Graph for storing example motion clips and searching them efficiently. The EPTG allows multiple motion clips for a given input so that the resulting motions can have diversity in their traits even with the same user inputs. In the run-time, when a user specifies an input sequence, the EPTG will be traversed according to the input to retrieved a desired motion clip. Each retrieved motion clip is concatenated with motion transition technique to remove jerkiness. The resulting motion is further enhanced with the dynamic motion balancing technique to meet physical property of the motion.
     

This page is managed by web@cg.kaist.ac.kr

last update on 12 July 2002