In this sequel, three images of the Utah Teapot are shown with color maps that represents the Gaussian (left), Mean (middle), and sum of squares of principle curvatures (sqrt(k1^2 + k2^2)). These curvature properties were computed as scalar fields using tools provided in the IRIT modeling environment, were represented in piecewise polynomial parametric form, and were rendered back on top of the Utah Teapot using the IRIT rendering tool that supports texture mapping of scalar fields. In all three images, Red denotes high values, Blue low values, and Green intermediate values.
The bisector surface of a curve and a point is rational! These examples show the shape of the bisector surface for a parabolic arc and a point in the plane (left) and out of the plane (right). The left image shows that the point-curve bisector is a special case of the curve-curve bisector with a vertical line. Created using the IRIT modeling environment as a joint work with Postech, Korea.
The bisector surface of two rational space curves in general 3-space position is rational! These examples show the shape of the bisector surface for an ellipse and a line and for a round square and a line. Both surfaces were computed symbolically and are represented using rational forms. Created using the IRIT modeling environment as a joint work with Postech, Korea.
The bisector surface of a point and a surface in 3-space is rational! These examples show the shape of the bisector surface between a point and a sphere (left), a point and a cylinder (middle) and a point and a torus (right). In the cases of the sphere and the torus, the point is inside the surface. All three surfaces were computed symbolically and are represented using rational forms. Created using the IRIT modeling environment as a joint work with Postech, Korea.
This work classifies some of these special cases that are related to constructive solid geometry (CSG). We consider the bisector surfaces between points, lines, planes, spheres, cylinders, cones, and tori. Many cases are shown to yield rational bisector surfaces, while several other cases are still left as open questions. The image on the left shows the rational bisector between a cylinder and a sphere while the image on the right shows the rational bisector of a torus and a sphere. Created using the IRIT modeling environment as a joint work with Postech, Korea.
The bisector of two rational surfaces in R^3 is non rational, in general. This work suggests a new computational model for approximating the curve-surface and surface-surface bisectors. The curve-surface bisector problem is reformulated as a trivariate zero-set finding problem, whereas the surface-surface bisector problem is reduced to that of finding the common zero-set of two four-variate functions. The image on the left shows the rational bisector approximation of a curve and a surfaces whereas the right image shows the rational bisector approximation of two surfaces (self intersecting!). Created using the IRIT modeling environment as a joint work with Seoul National University, Korea.
We present algorithms for computing the convex hull and kernel 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. The kernel computation can also be reduced to a zero-set finding problem. Using a plane-point duality, this work explores a duality relationship between the kernel and the convex hull. The image on the left show one example fo a kernel of a freeform 8-shape surface.
We present an algorithm for generating Voronoi cells for a set of planar piecewise C^1-continuous closed rational curves, which is precise up to machine precision. The algorithm starts with the symbolically generated bisectors for pairs of C^1-continuous curve segments (C(t), C_i(r)). The bisectors are represented implicitly in the tr-parameter space. Then, they are properly trimmed after being split into monotone pieces. The trimming procedure uses the orientation of the original curves as well as their curvature fields, resulting in a set of trimmed-bisector segments represented as implicit curves in a parameter space. A lower-envelope algorithm is then used in the parameter space of the curve whose Voronoi cell is sought. The lower envelope represents the exact boundary of the Voronoi cell. The algorithm also supports piecewise C^1-continuous curves and generates the Voronoi cell of such input curves using additional point/curve bisector segments.
We present a robust and efficient algorithm for trimming both local and global self-intersect-ions 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 bivariate 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. Two examples demonstrate the effectiveness of our approach, a 2D curve case and a 3D surface case.
The problem of computing the minimum enclosing circle of a point set is a classical problem in computational geometry. It is known to be an LP-type problem, hence it has a very efficient algorithm whose running time on average is linear in the number of points. In this work we generalize this approach to smooth curves in the plane. We prove the LP characteristics of the problem and provide details of our implementation of the algorithm. Two examples, result of this algorithm, are shown here.
The problem of computing the minimum enclosing sphere of a point set is a classical problem in Computational Geometry. As an LP-type problem, its expected running time on the average is linear in the number of points. In this paper, we generalize this approach to compute the minimum enclosing sphere of free-form hypersurfaces, in arbitrary dimensions. This paper makes the bridge between discrete point sets (for which indeed the results are well-known) and continuous curves and surfaces, showing that the general solution for the former can be adapted for the latter. Antipodal constraints are applied when a pair of hypersurfaces is involved. For more than a pair, equidistance constraints along with tangency constraints are applied. These constraints yield a finite set of solution points which is used to identify the minimum enclosing sphere. The algorithm uses the LP-characteristic of the problem to process the input set. Furthermore, an optimization procedure that uses the convex hull of sampled points from the hypersurfaces is also described. Finally, results from our implementation are presented.
A method of finding the precise ellipse of minimal area, enclosing a finite set of regular planar curves (and points), is presented. We start with a direct approach of prescribing the problem using a set of algebraic constraints and solving them. This approach turns out to be intractable using contemporary memory support and computing power and several improvements are presented to alleviate these difficulties: the number of degrees of freedom and constraints is limited and the search domain is restricted. As a result, an alternative set of algebraic constraints is created whose solution is found in a reasonable amount of memory size and/or computing time. The image shows the minimal ellipse bounding three freeform closed curves along with their 'active' regions in bold, following a pruning preprocess.
A bounding region for spiral curve segments shaped by two circular arcs, parts of the osculating circles at the spiral's endpoints, and two lines is introduced. This bounding region, denoted Spiral Fat Arc (SFA) is simple to construct and process, and shows a cubic approximation order to a given spiral curve. Given a general planar parametric curve, it can be split at curvature extrema (and inflection points), solving for the parametric locations for which kappa' = 0 (and kappa = 0), kappa being the signed curvature field, to yield a set of spiral curves. Each of the spirals is then fitted with a bounding SFA. Finding the intersection locations of two free-form planar curves is a fundamental task in geometric computing and computer aided design, and can immediately benefit from this new SFA bounding region. A recursive curve-curve intersection (CCI) algorithm that efficiently computes the intersection location of two parametric curves using SFAs is also introduced. The image shows two possible configurations of two SFAs intersecting.
This work present a coherent computational framework to efficiently, and more so robustly, evaluate, interrogation and compute a whole variety of characteristic curves on freeform parametric rational surfaces represented as (piecewise) polynomial or rational functions. These characteristic curves are expressed as zero sets of bivariate rational functions and include silhouette curves and isoclines from a prescribed viewing direction and/or point, reflection lines and reflection ovals, and highlight lines. This zero set formulation allows for a better treatment of singular cases whiel these characteristic curves are crucial for various applications, from visualization through interrogation to design and manufacturing. The image on the left shows an example of reflection ovals off a bi-quadratic B-spline surface.
The connection between kinematics and mechanisms to algebraic constraints is well known. This work presents a general kinematics simulator that allows end users to define planar and/or spatial arrangements, even along freeform curves and surfaces. The mechanical arrangement is then converted into a set of algebraic constraints and the motion of the arrangements is computed with the aid of a multivariate polynomial constraint solver. The image shows Two vertices (in blue and yellow) of a rigid triangle that are constrained to move along the two (blue) curve trajectories. The third vertex must follow the bottom surface in green. Six different possible placements are shown.
We present algorithms to derive the precise Hausdorff distance and/or the minimal distance between two freeform shapes, either curves or surfaces, in R^2 or R^3. The events at which the Hausdorff minimal distance can occur are identified and means to efficiently compute these events are presented. Examples are also shown and the extension to arbitrary dimensions is briefly discussed. The picture on the left shows four different events where the Hausdorff distance can accur between two curves: End points - end point, end point - Orthogonal case, bi-orthogonal case, and bisector - orthogonal case.
We present an exact algorithm for computing the precise Hausdorff distance between two general polyhedra represented as triangular meshes. The locus of candidate points, events where the Hausdorff distance may occur, is fully classified. These events include simple cases where foot points of vertices are examined as well as more complicated cases where extreme distance evaluation is needed on the intersection curve of one mesh with the medial axis of the other mesh. No explicit reconstruction of the medial axis is conducted and only bisectors of pairs of primitives (i.e. vertex, edge, or face) are analytically constructed and intersected with the other mesh, yielding a set of conic segments. For each conic segment, the distance functions to all primitives are constructed and the maximum value of their low envelope function may correspond to a candidate point for the Hausdorff distance. The algorithm is fully implemented and several experimental results are also presented. The picture on the left shows two different events where the Hausdorff distance can accur between two polygons: End points - end point case and bisector - orthogonal case.
This work presents a scheme to globally compute, bound, and analyze the Gaussian and mean curvatures of an entire volumetric data set, using a trivariate B-spline volumetric representation. The proposed scheme is not only precise and insensitive to aliasing, but also provides a method to globally segment the images into volumetric regions that contain convex or concave elliptic iso-surfaces, planar or cylindrical parabolic iso-surfaces, and volumetric regions with saddle-like hyperbolic iso-surfaces, regardless of the value of the iso-surface level. This scheme, which derives a new differential scalar field for a given scalar field, could easily be adapted to other differential properties. The image on the left presents the parabolic sheets of the geometry of an Iron protein volumetric data set.
We present a compact representation for the bounding volume hierarchy (BVH) of freeform NURBS surfaces using Coons patches. Following the Coons construction, each subpatch can be bounded very efficiently using the bilinear surface determined by the four corners. The BVH of freeform surfaces is represented as a hierarchy of Coons patch approximation until the difference is reduced to within a given error bound. Each leaf node contains a single Coons patch, where a detailed BVH for the patch can be represented very compactly using two lists (containing curve approximation errors) of length proportional only to the height of the BVH. We demonstrate the effectiveness of our compact BVH representation using several experimental results from real-time applications in collision detection and minimum distance computation for freeform models. The picture shows collision computation of 1000 Utah teapots.
Free Form Deformation (FFD) has become an acceptable design paradigm. Contemporary deformation tools let designers modify the geometry of the deformed model. This approach can be restrictive if the designer wants to incorporate holes or gaps into a model while deforming it into a different shape. This work presents a variant of FFD that would let the designer incorporate iso-parametric discontinuities into the deformation function. The input model is automatically split at these discontinuities, allowing the deformed model to reflect topological discontinuity changes. We demonstrate the deformation algorithm using two different applications. The first application wraps a moving model around obstacles in a scene, splitting and then re-forming it. The second application works locally, enabling the end-user to insert arbitrarily shaped cuts into the surface of the model. The image on the left shows a moving robot as it splits while passing through 3 vertical bars, only to merge again, afterwards.
In recent years, there has been a growing interest in computer graphics and geometric modeling in the ability to create and manipulate Seemingly Impossible Models (SIMs). Methods to create derivative work and modify drawings and paintings of SIMs made by artists were suggested. Similarly, 3D realization of SIMs of some of these drawings were also offered. In this work, we further explore the nature of SIMs and identify a class of SIMs that can be realized and modeled in 3D. As part of this analysis we show an invariance whose preservation allows one to model SIM artifacts that are completely realizable. We further present a mini-modeling package that allow end-users to realize whole new SIMs in two stages: modeling a regular 3D model and then converting it into a SIM using special deformations. We conclude with some examples, a discussion on the current limitations, and a layout of possible future work. The stool presented was created using this min-modeling package for SIMs, showed from two different view directions.
- Manufacturing, Accessibility & Visibility
- Symbolic Computation on Freeforms
- (NP) Rendering & Texturing of Freeforms