## 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.