Images and Pictures of Recent Research Projects:

Metamorphosis of freeform surfaces

This sequence of three images contains samples of a small animation created by a metamorphosis process of freeform NURBs surfaces.

Matching of freeform curves

A matching algorithm is introduced to generate an improve metamorphosis of freeform curves. The left shows direct convex combination while the right shows the result of applying the matching algorithm. Note the back and tail of the Oryx.

Sculptured Surface Modeling

This model of the B58 plane was modeled using the IRIT modeling environment and raytraced using the rayshade ray tracer.

Another high quality scene that was modeled using the IRIT modeling environment and raytraced using the rayshade ray tracer. This scene as well as the B58 above were constructed using various freeform surface modeling tools such as ruled surface (wings of B58), surface of revolution (the table and dishes), sweep (the cushion and base of chairs), and skinning (the fuselage of the B58). Similar geometries such as the engines of the B58 or the chair were instantiated several times using rigid motion transformations.

Depth Cueing based Rendering

Rendering with depth cueing for both rendered using rayshade images (left) and postscript figures (right). The postscript version also supports haloed lines. Both examples were created using tools that are part of the IRIT modeling environment.

Line Art Rendering Using Adaptive Isocurves

Adaptive extraction of isoparametric curves is employed herein to create illustrative imagery exploiting different shaders. The image on the left enhances silhouette regions while the image on the right uses cosine shader.

Line Art Rendering of Parametric and Implicit Forms

Line art illustrations are created in this project, using strokes that are developed out of point distributions on the freeforms. This scheme can be employed for both parametric and implicit forms. Here, the chess set and the light bulbs are two examples of parametric forms, whereas the tubes' joint is a result of an implicit iso surface defined over a trivariate polynomial function and the facial figure is an output of an iso surface extraction out of the MRBrain model from UNC. both last examples employs the principal curvatures as the direction of the strokes. Created using the IRIT modeling environment.

Interactive Line Art Rendering of Freeform Surfaces

This work presents a line art rendering method for freeform polynomial and rational surfaces that is capable of achieving real time and interactive display. A careful preprocessing stage that combines an a-priori construction of line art strokes with proper classification of the strokes, allows one to significantly alleviate the computational cost of sketching based rendering, and enable interactive real time line art display. The images of the Utah teapot and the transparent light bulb were extract off an interactive session on an O2 SGI whereas the chess set was extracted off an interactive session on an Onyx Reality Engine SGI. All examples were created using tools that are part of the IRIT modeling environment.

Ruled Tracing

Ruled tracing of adaptive isoparametric curves is a novel rendering technique to directly scan convert freeform parametric surfaces. Herein, special effects such as texture and bump mapping are intermixed with shadow computation. No polygonal approximation of the freeform surfaces is involved in this process. Joint work with Postech, Korea.

Curvature Analysis of Freeform Surfaces

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.

Point-Curve Bisector Surface

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.

Curve-Curve Bisector Surface

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.

Point-Surface Bisector Surface

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.

Rational Bisectors of CSG Primitives

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.

Approximating Curve-Surface and Surface-Surface Bisectors in R^3

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.

Virtual Reality and the WWW

This project investigates the mean to map various data (text, images, movies, sound, etc.) onto virtual environments. The two images provided herein show examples of a simple virtual environment where the images displayed are the result of a query posted to the network. Created using the IRIT modeling environment, Performer from SGI and W3QS WWW query language.

Minimally Distorted Parametric Texture Mapping

This work proposes an efficient and simple scheme for a distance preserving texture mapping that is based on the adaptive isoparametric curves' rendering technique (direct surface rendering scheme with no polygonal approximation). The proposed scheme employs information that already exists in the renderer and, hence, can become much more efficient compared to previous parametric texture mapping techniques that minimizes the distance distortion. Nevertheless, like the output from all mapping techniques for planar texture patterns onto general sculptured surfaces, the output from this algorithm cannot be an Isometry, in general. The images show a camouflaged f16 plane with the wings painted using a uniform grid. The left image shows a tradition parametric grid texture, while the image on the right shows the same texture, minimally distorted. A joint work with the University of Utah.

Surface Design Using Global Constraints on Total Curvature

Tensor product surfaces are now widely used in application areas from industrial design to computer animation. Yet, the quest for more effective design methods continues. This work considered a new approach to the design of free form surfaces using global second order differential geometric constraints defined over the entire domain of the surface or a prescribed subset of it. Three cases of convexity preservation, developability preservation, and minimal surfaces have been considered. The image on the left shows a portion of a cockpit surface automatically shaped into the right image, preserving convexity. Created with the aid of the IRIT modeling environment.

Three Dimensional Freeform Sculpting Via Zero Sets of Scalar Trivariate Functions

This works experiments with a three dimensional interactive sculpting paradigm that employs a collection of scalar uniform trivariate B-spline functions. The sculpted object is evaluated as the zero set of the sum of the collection of the trivariate functions defined over a three dimensional working space, resulting in multi-resolution control capabilities. The continuity of the sculpted object is governed by the continuity of the trivariates. The manipulation of the objects is conducted by modifying the scalar control coefficients of the meshes of the participating trivariates. Real time visualization is achieved by incrementally computing a polygonal approximation via the Marching Cubes algorithm. The exploitation of trivariates in this context benefits from the different properties of the B-spline's representation such as subdivision, refinement and convex hull containment.
The image on the left is a result of modeling a kids' slide in this system while etching the "slide" at a higher resolution.
The image on the right is the result of employing a 3D scanner data to reconstruct the model using trivariates while further manipulations is conducted (removal of the pupils) in the modeling environment.

Interactive Direct Rendering of Trivariate B-spline Scalar Functions

This work presents an interactive direct rendering paradigm of trivariate B-spline functions, that can be employed in trivariate modeling sessions, such as interactive volumetric sculpting. The rendering is conducted from a fixed viewpoint and in two phases. The first, preprocessing, stage accumulates the affect that the coefficients of the trivariate function have on the pixels in the image. This preprocessing stage is conducted off line and once only per trivariate and viewing direction. The second stage allows the rendering of trivariate functions, at rates of several frames per second. During a sculpting operation, the artist can sculpt the volume and get displayed feedback, in interactive rates.

Image Morphing with Feature Preserving Texture

Image metamorphosis as an animation tool has mostly been employed in the context of the entire image. This work explores the use of isolated and focused image based metamorphosis between two-dimensional objects, while capturing the features, colors, and textures of the objects. This pinpointed approach allows one to independently overlay several such dynamic shapes, without any bleeding of one shape into another. Hence, shape blending and metamorphosis of two-dimensional objects can be exploited as animated sequences of clip arts.
The image on the left shows a morphing sequence of two gazelles to two topis. Note the constant background in the image throughout the morphing sequence. A joint work with the EE department, Technion.

Arbitrary precise Orientation Specification for Layout of Text

A new method for the layout of text strings over some given free-form parametric base curves is considered. Each letter of the string is represented by a collection of cubic and linear Bezier curves. The layout of the string over the free-form parametric curve is derived as a symbolic composition of the string geometry (i.e. a sequence of Bezier curves) and a free-form parametric surface S(u,v) with the parameters u, v between zero and one, and S(u,0) is given by the base curve. This method has proven to provide great flexibility and give high quality results in layout of text. Similar text is also seen in the image on the left laid down along a spiral.

Surface Rendering Using Layout of Text

An artistic rendering method of free-form surfaces with the aid of half-toned text that is laid-out on the given surface is presented. The layout of the text is computed using symbolic composition of the free-form parametric surface S(u,v) with cubic or linear Bezier curve segments C(t) = { cu(t), cv(t) }, comprising the outline of the text symbols. Once the layout is constructed on the surface, a shading process is applied to the text, affecting the width of the symbols as well as their color, according to some shader function. The shader function depends on the surface orientation and the view direction as well as the color and the direction or position of the light source.

Rendering Traditional Mosaics

This work discusses the principles of traditional mosaics, and describes a technique for implementing a digital mosaicing system. The goal of this work is to transform digital images into traditional mosaic-like renderings. We achieve this effect by recovering freeform feature curves from the image and laying rows of tiles along these curves. Composition rules are applied to merge these tiles into an intricate jigsaw that conforms to classical mosaic styles. Mosaic rendering offers the user flexibility over every aspect of this craft, including tile arrangement, shapes, and colors. The result is a system that makes this wonderful craft more flexible and widely accessible than previously possible.

Rendering with Parallel Stripes

This work presents an artistic rendering scheme that is based on parallel stripes and inspired by Victor Vasarely's art work. The rendering process is conducted using parallel planar curves that are warped and translated in the projection plane an amount that is a function of the depth of the object, at that location. In this work, the parallel stripes are derived as a set of isoparametric curves out of a warped injective B-spline surface that is derived from a Z map of a Z-buffer of the scene.

Curve Evaluation and Interrogation on Surfaces

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.

Texture Details using Geometric Deformation-Displacement Maps

This work presents an extended texture mapping view allows one to precisely assign a single surface location with few continuously deformed displacements, each with possibly different texture color or normal, employing trivariate functions in a similar way to FFDs. As a consequence, arbitrary regular geometry could be employed as part of the presented scheme as supplementary surface texture details. This work also augments recent results on texturing and parameterization of surfaces of arbitrary topologies by providing more flexible control over the phase of texture modeling. By completely and continuously parameterizing the space above the surface of the object, as a trivariate vector function, we are able, in this work, to not only control the mapping of the texture on the surface but also to control this mapping in the volume surrounding the surface.

Placement of Deformable Objects

With the increasing complexity of photo-realistic scenes, the question of building and placing objects in three-dimensional scenes is becoming ever more difficult. While the question of placement of rigid objects has captured the attention of researchers in the past, this work presents an intuitive and interactive scheme to properly place deformable objects with the aid of free-form deformation tools. The presented scheme can also be used to animate the locomotion of non-rigid objects, most noticeably animals, and adapt the motion to arbitrary terrain. The automatic construction of our free-form deformation tool is completely hidden from the end user, and hence, circumvents the difficulties typically faced in manipulating these deformation functions. Further, a precise bound on the error that is introduced by applying free-form deformations to polygonal models is presented, along with an almost-optimal adaptive refinement algorithm to achieve certain accuracy in the mapping.

Silhouette Curves for Volumetric Data Sets

This work presents an algorithm for near interactive silhouette extraction from volumetric data sets. Trivariate tensor product B-spline functions are used to represent the data. An off-line phase that arranges the data in a lookup table is employed to improve the computation time during an interactive session. A subdivision scheme is employed to extract the silhouette curves from an implicit trivariate B-spline function. The produced results are smooth, high quality, silhouette curves of volumetric data set compared to voxel-based silhouettes extraction schemes. The silhouettes of the jaw bone on the left were rendered using a tri-quadratic volume.

The Convex Hull and Kernel of Freeform Surfaces

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.

Generalized Functional and Decorative Filleting and Blending Operations

The use of blending and filleting operations in solid modeling and computer-aided geometric design is well established. The question of filling a gap between two (or more) surface boundaries or rounding a sharp edge has been extensively investigated. The vast majority of the prior work on blending and filleting concentrated on a wide variety of fitting schemes as well as attempts to establish and guarantee better continuity conditions. This work extends the notion of filleting and blending modeling tools and elevates them into shaping operations that are either functional or ornamental in nature. The extended shaping operations can be conducted between two boundaries of two adjacent surfaces, much like traditional blending or filleting methods. Furthermore, the presented extended forms can also be applied to the interior of a single surface, guided by arbitrary parametric curves in the domain of the patch.

Global Curvature Analysis and Segmentation of Volumetric Data Sets using Trivariate B-spline Functions

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.

Real-time Incision Simulation Using Discontinuous Free Form Deformation

Surgical simulation with the aid of computers is a topic of increasingly extensive research. Real-time response and interactivity are crucial components of any such system and a major effort has been invested in finding ways to improve the performance of existing systems. In this work, we propose the use of a new variant of Free Form Deformations that supports discontinuities (DFFD) in complex real time surgical simulations. The proposed scheme can benefit from an a priori or, alternatively, interactive low resolution, physical simulation of the incision procedure that is encoded into the DFFD. The DFFD is then applied to the geometry of the tissue in hand, a two-dimensional skin shape or a three-dimensional volumetric representation, capturing the incision's shape as well as the behavior of the neighborhood geometry over time.

Discontinuous Free Form Deformations

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.

Generalized Functional and Decorative Filleting and Blending Operations

The use of blending and filleting operations in solid modeling and computer-aided geometric design is well established. The question of filling a gap between two (or more) surface boundaries or rounding a sharp edge has been extensively investigated. The vast majority of the prior work on blending and filleting concentrated on a wide variety of fitting schemes as well as attempts to establish and guarantee better continuity conditions. This work extends the notion of filleting and blending modeling tools and elevates them into shaping operations that are either functional or ornamental in nature. The extended shaping operations can be conducted between two boundaries of two adjacent surfaces, much like traditional blending or filleting methods. Furthermore, the presented extended forms can also be applied to the interior of a single surface, guided by arbitrary parametric curves in the domain of the patch. The image on the left presents several examples of C^1 blends between the Utah teapot's body and its spout.

Importance-based Non-Photorealistic Rendering

When pictorial information is presented, details of importance are typically emphasized. These include discontinuities in the geometry, highly curved regions, silhouettes, etc. This work analyzes the probability that certain smooth surface regions or polygonal edges possess silhouettes. This probability analysis is then associated with the visual importance of the local neighborhood, which is capable of capturing discontinuities and highly curved regions. A non-photorealistic rendering technique is subsequently proposed to take advantage of the silhouette-based importance. Based on this importance analysis, a completely automatic algorithm is presented that creates line-art that captures visual features in the model in an appealing way.

Precise Global Collision Detection in Multi-Axis NC-Machining

We introduce a new approach to the problem of collision detection in multi-axis NC-machining. Due to the directional nature (tool axis) of multi-axis NC-machining, space subdivision techniques are adopted from ray-tracing algorithms and are extended to suit the peculiarities of the problem in hand. We exploit the axial-symmetry inherent in the tool's rotational motion to derive a precise (to within machine precision) polygon-tool intersection algorithm which, combined with the proper data structure, also yields efficient computation times. Other advantages of the proposed method is the separation of the entire computation into a preprocessing stage that is executed only once, allowing more than one toolpath to be efficiently verified thereafter, and the introduced ability to test for collisions against arbitrary shaped tools such as flat-end or ball-end, or even test for interference with the tool holder or other parts of the NC-machine. Support for continuous analysis along the tools path is also possible. The image on the left presents a 5-axes tool path that was analyzed, intersections detected, and corrected by rotating the ball end tool's orientation.

Two-Dimensional Visibility Charts for Continuous Curves

This work considers computation of visibility for two-dimensional shapes whose boundaries are C^1 continuous curves. We assume we are given a one-parameter family of candidate viewpoints, which may be interior or exterior to the object, and at finite or infinite locations. We consider how to compute whether the whole boundary of the shape is visible from some finite set of viewpoints taken from this family, and if so, how to compute a minimal set of such viewpoints. The viewpoint families we can handle include (i) the set of viewing directions from infinity, (ii) viewpoints on a circle located outside the object (for inspection from a turntable), and (iii) viewpoints located on the walls of the shape itself. We compute a structure called a visibility chart, which simultaneously encodes the visible part of the shape's boundary from every view in the family. Using such a visibility chart, finding a minimal set of viewpoints reduces to the set-covering problem over the reals. Practical algorithms are obtained by a discrete sampling of the visibility chart. For exterior visibility problems, a reasonable approach is to compute an almost-optimal solution (in terms of number of viewpoints), which can be done in almost-linear time. For interior visibility problems, or when a more correct solution is required, we solve the general set-covering problem, guaranteeing an optimal solution but taking exponential time. In either case, conservative solutions are obtained, ensuring that no part of the curve remains invisible from some viewpoint. Examples are given to illustrate our algorithm. The presented image shows (from left to right) the visible portion (in yellow) of the curve from one view, the visibility chart in the middle, and the three views that covers the entire domain (right). These three views could be used to create a 2D mold of 3 pieces.

Precise Voronoi Cell Extraction of Free-form Rational Planar Closed Curves

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.

Trimming Local and Global Self-intersections in Offset Curves and Surfaces using Distance Maps

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.

Computing the Minimum Enclosing Circle of a Set of Planar Curves

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.

Computing Minimum Enclosing Balls of Freeform Manifolds in Arbitrary Dimensionss

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.

On the Computation of the Minimal Ellipse Enclosing a Set of Planar Curves

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.

Spiral Fat Arcs - a Bounding Region with Cubic Convergence

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.

Modeling (Seemingly) Impossible Models

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.

Kinematic Simulation of Planar and Spatial Mechanisms Using a Polynomial constraints Solver

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.

Hausdorff and Minimal Distances between Parametric Freeforms in R^2 and R^3

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.

Precise Hausdorff Distance Computation Between Polygonal Meshes

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.

Coons BVH for Freeform Geometric Models

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.