Joon-Kyung Seong   

Post Doctoral Fellow, GDC Group at University of Utah.

Address: School of Computing, 50 Central Campus Drive, University of Utah, Salt Lake City, UT 84112
Phone: 801-581-5884
Email: seong at cs.utah.edu
Web: http://www.cs.utah.edu/~seong/
Curriculum Vitae: CV

Research Interests

Publications

Voronoi Diagram Computations for Planar NURBS Curves (pdf).
Joon-Kyung Seong, Elaine Cohen and Gershon Elber.
Accepted at ACM SPM 2008.

We present robust and efficient algorithms for computing Voronoi diagrams of planar freeform curves. Boundaries of the Voronoi diagram consist of portions of the bisector curves between pairs of planar curves. Our scheme is based on computing critical structures of the Voronoi diagrams, such as self-intersections and junction points of bisector curves. Since the geometric objects we consider in this paper are represented as freeform NURBS curves, we were able to reformulate the solution to the problem of computing those critical structures into the zero-set solutions of a system of nonlinear piecewise rational equations in parameter space. We present a new algorithm for computing error-bounded bisector curves using a distance surface constructed from error-bounded offset approximations of planar curves. This error-bounded algorithm is fast and produces bisector curves that are correct both in the topology and the geometry. Once bisectors are computed, both local and global self-intersections of the bisector curves are located and trimmed away by solving a system of three piecewise rational equations in three variables. Further, our method computes junction points at which three or more trimmed bisector curves intersect by transforming them into the solutions to a system of piecewise rational equations in the merged parameter space of the planar curves. The bisectors are trimmed at those self-intersection and global junction points. The Voronoi diagram is then computed from the trimmed bisectors using a pruning algorithm. We demonstrate the effectiveness of our approach with several experimental results.

Anisotropic Geodesic Distance Computation for Parametric Surfaces (pdf).
Joon-Kyung Seong, Won-Ki Jeong and Elaine Cohen.
Accepted at IEEE SMI 2008.

The distribution of geometric features is anisotropic by its nature. Intrinsic properties of surfaces such as normal curvatures, for example, varies with direction. In this paper this characteristic of a shape is used to create a new anisotropic geodesic (AG) distance map on parametric surfaces. We first define local distance (LD) from a point as a function of both the surface point and a unit direction in its tangent plane and then define a total distance as an integral of that local distance. The AG distance between points on the surface is then defined as their minimum total distance. The path between the points that attains the minimum is called the anisotropic geodesic path. This differs from the usual geodesic in ways that enable it to better reveal geometric features. Minimizing total distances to attain AG distance is performed by associating the LD function with the tensor speed function that controls wave propagation of the convex Hamilton-Jacobi (H-J) equation solver. We present two different, but related metrics for the local distance function, a curvature tensor and a difference curvature tensor. Each creates a different AG distance. Some properties of both new AG distance maps are presented, including parametrization invariance. We then demonstrate the effectiveness of the proposed geodesic map as a shape discriminator in several applications, including surface segmentation and partial shape matching.

Minimum Distance between Two Sphere-swept Surfaces (pdf).
Kwanhee Lee, Joon-Kyung Seong, Ku-Jin Kim and Sung Je Hong.
To Appear Computer-Aided Design 2007.

We present a simple formula for computing the minimum distance between two sphere-swept surfaces. As examples of sphere-swept surfaces, we consider canal surfaces and bivariate sphere-swept surfaces. For computing the minimum distance between two parametric surfaces, a simple technique is to find two closest points from the given surfaces using the normal vector information. We suggest a novel approach that efficiently computes the minimum distance between two sphere-swept surfaces by treating each surface as a family of spheres. Rather than computing the complicated normal vectors for given surfaces, our method solves the problem by computing the minimum distance between two moving spheres. We prove that the minimum distance between two sphere-swept surfaces is identical to that between two moving spheres. Experimental results of minimum distance computation are given.

Simultaneous Precise Solutions to the Visibility Problem of Sculptured Models (pdf).
Joon-Kyung Seong, Gershon Elber and Elaine Cohen.
GMP 2006.

We present an efficient and robust algorithm for computing continuous visibility for two- or three-dimensional shapes whose boundaries are NURBS curves or surfaces by lifting the problem into a higher dimensional parameter space. This higher dimensional formulation enables solving for the visible regions over all view directions in the domain simultaneously, therefore providing a reliable and fast computation of the \emph{visibility chart}, a structure which simultaneously encodes the visible part of the shape's boundary from every view in the domain. In this framework, visible parts of planar curves are computed by solving two polynomial equations in three variables ($t$ and $r$ for curve parameters and $\theta$ for a view direction). Since one of the two equations is an inequality constraint, this formulation yields two-manifold surfaces as a zero-set in a 3-D parameter space. Considering a projection of the two-manifolds onto the $t\theta$-plane, a curve's location is invisible if its corresponding parameter belongs to the projected region. The problem of computing hidden curve removal is then reduced to that of computing the projected region of the zero-set in the $t\theta$-domain. We recast the problem of computing boundary curves of the projected regions into that of solving three polynomial constraints in three variables, one of which is an inequality constraint. A topological structure of the visibility chart is analyzed in the same framework, which provides a reliable solution to the hidden curve removal problem. Our approach has also been extended to the surface case where we have two degrees of freedom for a view direction and two for the model parameter. The effectiveness of our approach is demonstrated with several experimental results.

A Higher Dimensional Formulation for Robust and Interactive Distance Queries (pdf).
Joon-Kyung Seong, David E Johnson and Elaine Cohen.
SPM 2006.

We present an efficient and robust algorithm for computing the minimum distance between a point and freeform curve or surface by lifting the problem into a higher dimension. This higher dimensional formulation solves for all query points in the domain simultaneously, therefore providing opportunities to speed computation by applying coherency techniques. In this framework, minimum distance between a point and planar curve is solved using a single polynomial equation in three variables (two variables for a position of the point and one for the curve). This formulation yields two-manifold surfaces as a zero-set in a 3D parameter space. Given a particular query point, the solution space's remaining degrees-of-freedom are fixed and we can numerically compute the minimum distance in a very efficient way. We further recast the problem of analyzing the topological structure of the solution space to that of solving two polynomial equations in three variables. This topological information provides an elegant way to efficiently find a global minimum distance solution for spatially coherent queries. Additionally, we extend this approach to a 3D case. We formulate the problem for the surface case using two polynomial equations in five variables. The effectiveness of our approach is demonstrated with several experimental results.

Trimming Local and Global Self-intersections in Offset Curves and Surfaces using Distance Maps (pdf).
Joon-Kyung Seong, Gershon Elber and Myung-Soo Kim.
To Appear Computer-Aided Design.

We present a robust and efficient algorithm for trimming both local and global self-intersections in offset curves and surfaces. Our scheme is based on the derivation of a rational distance map between the original curve or surface and its offset. By solving a univariate polynomial equation for an offset curve or a system of three polynomial equations for an offset surface, we can detect all local and global self-intersection regions in offset curves or surfaces. The zero-set of the polynomial equation(s) corresponds to the self-intersection regions. We trim these regions by projecting the zero-set into an appropriate parameter space. The projection operation simplifies the analysis of the zero-set, which makes the proposed algorithm numerically stable and efficient. Furthermore, in a post-processing step, we employ a numerical marching method, which provides a highly precise scheme for self-intersection elimination in both offset curves and surfaces. We demonstrate the effectiveness of our approach using several experimental results.

Perspective Silhouette of a General Swept Volume(pdf).
Joon-Kyung Seong, Ku-Jin Kim, Myung-Soo Kim and Gershon Elber.
Visual Computer 2005.

We present an efficient and robust algorithm for computing the perspective silhouette on the boundary of a general swept volume. We also construct the topology of connected components of the silhouette. As a three-dimensional object moves along a trajectory, each instance of the moving object touches the envelope surface of the swept volume along a characteristic curve K^t -- a curve K at time t. Moreover, the same instance of the moving object has its silhouette curve L^t on its own boundary. The intersection between K^t and L^t contributes to the silhouette of the general swept volume. We reformulate the problem as a system of two polynomial equations in three variables. Moreover, connected components of a silhouette curve are constructed by detecting the cases where the two curves K^t and L^t intersect tangentially each other on the boundary surface of the moving object.

Sweep-based Human Deformation(pdf).
Dae-Eun Hyun, Seung-Hyun Yoon, Jung-Woo Chang, Joon-Kyung Seong, Myung-Soo Kim and Bert Juttler.
Visual Computer To Appear.

We present a sweep-based approach to human body modeling and deformations. A rigid 3D human model, given as a polygonal mesh is approximated with control sweep surfaces. The vertices on the mesh are bound to nearby sweep surfaces and then follow the deformation of the sweep surfaces as the model bends and twists its arms, legs, spine and neck. Anatomical features including bone-protrusion, muscle-bulge, and skin-folding are supported by a GPU-based collision detection procedure. The volumes of arms, legs, and torso are kept constant by a simple control using a volume integral formula for sweep surfaces. We demonstrate the effectiveness of this sweep-based human deformation in several test animation clips.

Intersecting a Freeform Surface with a Sweep Surface(pdf).
Joon-Kyung Seong, Ku-Jin Kim, Myung-Soo Kim and Gershon Elber.
Computer-Aided Design, 37(5): 473--483, April 2005

We present efficient and robust algorithms for intersecting a freeform surface with a ringed surface of a ruled surface. Ringed surface is given as a one-parameter family of circles. By computing the intersection between a freeform surface and each circle in the family, we can solve the intersection problem. We propose two approaches which are closely related each other. The first approach detects certain critical points; and the intersection curve is constructed by connecting them in a correct topology. The second approach converts the intersection problem to that of finding the zeroset of two polynomial equations in the parameter space. The intersection between a freeform surface and a ruled surface can also be computed in a similar way.

Contouring 1- and 2-Manifolds in Arbitrary Dimensions (pdf).
Joon-Kyung Seong, Gershon Elber and Myung-Soo Kim.
International Conference on Shape Modeling and Applications pp. 216--225, MIT, USA, June 15-17, 2005.

We present an algorithm for contouring k-manifolds (k=1,2) embeded in an arbitrary n-dimensional space. We assume (n-k) geometric constraints are represented as polynomial equations in n variables. The common zero-set of these (n-k) equations is computed as a 1- or 2-manifold, respectively, for k=1 or k=2. In the case of 1-manifolds, this framework is a generalization of techniques for contouring regular intersection curves between two implicitly-defined surfaces of the form F(x,y,z) = G(x,y,z) = 0. Moreover, in the case of 2-manifolds, the algorithm is similar to techniques for contouring iso-surfaces of the form F(x,y,z) = 0, where n=3 and only one (=3-2) constraint is provided. By extending the Dual Contouring technique to higher domensions, we approximate the simultaneous zero-set as a piecewise linear 1- or 2-manifold. There are numerous applications for this technique in data visualization and modeling, including the proessing of various geometric constraints for freeform objects, and the computation of convex hulls, bisectors, blendings ans sweeps.

Geometric Computations in Parameter Space (pdf).
Myung-Soo Kim, Gershon Elber and Joon-Kyung Seong.
Spring Conference on Computer Graphics Bundmerice Castle, Slovak Republic, May 12-14, 2005.

Are Two Curves the Same?(pdf).
Diana Pekerman, Joon-Kyung Seong, Gershon Elber and Myung-Soo Kim.
Computer-Aided Design and Applications 2(1-4): 85--94, 2005.

The Convex Hull of Freeform Surfaces(pdf).
Joon-Kyung Seong, Gershon Elber, John K. Jonestone and Myung-Soo Kim.
Computing,  Volume 72, Numbers 1-2, pp. 171-183, April 2004.

We present an algorithm for computing the convex hull of freeform rational surfaces. The convex hull problem is reformulated as one of finding the zero-sets of polynomial equations; using these zero-sets we characterize developable surface patches and planar patches that belong to the boundary of the convex hull.

Polynomial Decomposition and its Applications(pdf).
Joon-Kyung Seong, Gershon Elber and Myung-Soo Kim.
Israel-Korea Binational Conference on Geometric Modeling and Computer Graphics,   Ramat Aviv, Israel, February 2003, pp. 12-14.

We present a simple algorithm for decomposing a polynomial H(x) into two constituent polynomials H(x) = f(g(x)), if such exist. Reversing a composition of two polynomials is shown to be reducible to a set of non-linear equations with a simple structure. While, in general, the solution of non-linear equations is quite complicated, we show that in this system the solution can be computed exactly using symbolic recurrence relations. We demonstrate the effectiveness of this result using some illustrative examples and also discuss interesting applications in geometric modeling; Reparameterization as an insecure watermarking tool and verifying the identity of a curve in two different representations.

The Minkowski Sum of Two Simple Surfaces Generated by Slope-Monotone Closed Curves (pdf).
Joon-Kyung Seong, Myung-Soo Kim and Kokichi Sugihara.
GMP 2002   Saitama, Japan, 2002, pp. 33-42.

We present an algorithm for computing Minkowski sums among surfaces of revolution and surfaces of linear extrusion, generated by slope-monotone closed curves. The special structure of these simple surfaces allows the process of normal matching between two surfaces to be expressed as an explicit equation. Based on this insight, we also present an efficient algorithm for computing the distance between two simple surfaces, even though they may in general be non-convex. Using an experimental implementation, the distance between two surfaces of revolution was computed in less than 0.5 msec on average.

The Intersection of Two Ringed Surfaces and Some Related Problems (pdf).
Hee-Seok Heo, Sung-Je Hong, Joon-Kyung Seong, Myung-Soo Kim and Gershon Elber.
Graphical Models,   63(4):228-244, November 2001.

We present an efficient and robust algorithm to compute the intersection curve of two ringed surface, each being the sweep generated by a moving circle.

A Physical 3D Trackball (pdf).
Myung-Soo Kim, Joon-Kyung Seong, Dae-Eun Hyun, Kang-Hoon Lee and Yu-Jin Choi.
Pacific Graphics,   Tokyo, 2001, pp. 134-138.

We present a simple method for constructing a physical 3D trackball that can input 3D rotation about an arbitrary axis. This input device is based on multiple sensors that can detect the tangential velocities at certain points on the boundary sphere of the trackball. A mathematical analysis is given for the optimal locations of multiple sensors. A prototype hardware device has been built for the 3D trackball. We demonstrate the effectiveness of this input device in 3D rotation by comparing its performance with the Magellan/SPACE MOUSE.

Academic background

Miscellaneous