We present a precise approach to the generation of optimized collision-free and gouging-free tool paths for 5-axis CNC machining of freeform NURBS surfaces using flat-end and rounded-end (bull nose) tools having cylindrical shank. To achieve high approximation quality, we employ analysis of hyper-osculating circles (HOCs) (Wang et al., 1993a,b), that have third order contact with the target surface, and lead to a locally collision-free configuration between the tool and the target surface. At locations where an HOC is not possible, we aim at a double tangential contact among the tool and the target surface, and use it as a bridge between the feasible HOC tool paths. We formulate all such possible two-contact configurations as systems of algebraic constraints and solve them. For all feasible HOCs and two-contact configurations, we perform a global optimization to find the tool path that maximizes the approximation quality of the machining, while being gouge-free and possibly satisfying constraints on the tool tilt and the tool acceleration. We demonstrate the effectiveness of our approach via several experimental results.

• Computer Aided Design, Vol 58, pp 220-229, January 2015.

We present a subdivision based algorithm to compute the solution of an under-constrained piecewise polynomial system of n-2 equations with n unknowns, exploiting properties of B-spline basis functions. The solution of such systems is, typically, a two-manifold in Rn. To guarantee the topology of the approximated solution in each sub-domain, we provide subdivision termination criteria, based on the (known) topology of the univariate solution on the domain�s boundary, and the existence of a one-toone projection of the unknown solution on a two dimensional plane, in Rn. We assume the equation solving problem is regular, while sub-domains containing points that violate the regularity assumption are detected, bounded, and returned as singular locations of small (subdivision tolerance) size. This work extends (and makes extensive use of) topological guarantee results for systems with zero and one dimensional solution sets. Test results in R^3 and R^4 are also demonstrated, using error-bounded piecewise linear approximations of the two-manifolds.

• Computer Aided Design, Vol 58, pp 210-219, January 2015.

Ruled surfaces play an important role in many manufacturing and construction applications. In this work, we explore a multi-dimensional dynamic programming based ruled surface fitting scheme to a given freeform rational surface, S. Considering two initial opposite boundaries of S, sampled into a discrete piecewise linear polyline representation, the ruled surface fitting problem is reduced to a pairing-search between the polylines and elevations above the polylines, in the normal directions of S. A four-dimensional dynamic programming solution is sought for the four dimensions prescribed by the two polylines and the two elevation levels along the surface normals. This multi-dimensional dynamic programming is evaluated using highly parallel algorithms running on GPUs that ensures the best fit to the sampled data. In order to evaluate the fitting error with respect to S, we derive a scheme to compute a bound from above on the maximal error between a bilinear surface patch (formed by two consecutive pointpairs) and its corresponding surface region on S. Surface-surface composition is employed to extract the corresponding surface region on S to compare against. Finally, the above ruled surface fitting approach is also extended into a discrete algorithm to find the non-isoparametric subdivision curve on S when a discrete recursive piecewise-ruled surface fitting is considered. A five- or seven-dimensional dynamic programming solution is employed towards this end and once again, surface-surface composition is employed to extract the two subdivided patches as tensor products.

• Computer Aided Design, Vol 51, pp 39-49, 2014.

This paper presents an efficient algorithm for generating a continuous precise contact motion between planar geometric models bounded by piecewise polynomial C1-continuous parametric B-spline curves. A system of algebraic constraint equations is formulated and then efficiently solved for the two/three-contact configuration between two planar B-spline curves. The result is essentially the same as the generation of configuration space obstacle for a moving curve (with translation and rotation) against a stationary curve. The two-contact motion can be characterized as the intersection curve in the boundary of the configuration space obstacle. The topology of the reconstructed solution is guaranteed to be correct up to a prescribed tolerance and we demonstrate the effectiveness of the proposed approach using several test examples of continuous contact motion among planar freeform smooth geometric models.

• Graphical Model, Vol 76, pp 580-592, 2014.

Given a three dimensional object B in R^3, the visual hull of B (a concept introduced by Laurentini in 1992) is the smallest set VB in R^3 containing B with the following property: for each point p on the boundary of VB there exists a direction from which p is on a silhouette of VB. The notion of the visual hull has applications in computer graphics (visibility and silhouette based algorithms), manufacturing (accessibility, wire EDM and hot wire cutting), and more.
We present a tractable algorithm for computing a decomposition of a C^1 smooth, closed parametric surface S in R^3, positioned in an arrangement with other occluding surfaces, into those regions that belong to the visual hull and those that do not (later referred to as the "line-accessible" or "line-inaccessible" regions). For efficiency, our method introduces two early domain pruning criteria, using a recursive subdivision of the parameter domain, along with a tangent plane bounding cone: one criterion detects regions that are guaranteed to belong to the visual hull, while the other detects regions that cannot belong to it (both use sufficient and not necessary conditions). Only to those sub-domains that remain after this significant domain reduction, an algebraic (subdivision based) solver is applied, to solve two sets of algebraic equations, already presented by Laurentini in 1999, gaining one to two orders of magnitude improvement in the computation times. We provide a derivation of these equations via a different approach, compared to Laurentini in 1999, using the model we refer to as the dynamic SSI solution of the surface and the moving tangent plane. Concrete computational examples are provided as well.

• Graphical Model, Vol 76, pp 301-311, 2014.

We present a general, unified framework to resolve geometric covering problems. The problem is reduced to a set~cover search in parametric space. We propose and implement different methods for solving the set~cover problem, allowing for flexible trade-offs between solution quality and computation time. Our framework relies on computer graphics techniques and heavily exploits GPU based computations.
Results are demonstrated in two specific applications: firstly, multi-visibility/accessibility analysis of 3D scenes that guarantees coverage, possibly redundant, of the target shape(s) by a minimal number of observers. Secondly, illumination design in 3D environments that ensures the satisfaction of local constraints on illuminance levels using a minimal set of lamps.

• The Computer & Graphics Journal, Vol 38, No 1, pp 222-229, February 2014.

Functional composition can be computed efficiently, robustly, and precisely over polynomials and piecewise polynomials represented in the B�zier and B-spline forms. Nevertheless, the applications of functional composition in geometric modeling have been quite limited. In this work, as a testimony to the value of functional composition, we first recall simple applications to curve-curve and curve-surface composition, and then more extensively explore the surface�surface composition (SSC) in geometric modeling. We demonstrate the great potential of functional composition using several non-trivial examples of the SSC operator, in geometric modeling applications: blending by composition, untrimming by composition, and surface distance bounds by composition.

• Computer Aided Design, Vol 46, pp 200-204, 2014.

We present an interactive-speed algorithm for computing the precise convex hull of freeform geometric models. The algorithm is based on two pre-built data structures: (i) a Gauss map organized in a hierarchy of normal pyramids and (ii) a Coons bounding volume hierarchy (CBVH) which eectively approximates freeform surfaces with a hierarchy of bilinear surfaces. For the axis direction of each normal pyramid, we sample a point on the convex hull boundary using the CBVH. The sampled points together with the hierarchy of normal pyramids serve as a hierarchical approximation of the convex hull, with which we can eliminate the majority of redundant surface patches. We compute the precise trimmed surface patches on the convex hull boundary using a numerical tracing technique and then stitch them together in a correct topology while lling the gaps with tritangent planes and bitangent developable scrolls. We demonstrate the eectiveness of our algorithm using experimental results.

• Computer Aided Design, Vol 46, pp 252-257, 2014.

We present an interactive-speed algorithm for computing the Hausdorff Distance (HD) between two freeform geometric models represented with NURBS surfaces. The algorithm is based on an effective technique for matching a surface patch from one model to the corresponding nearby surface patch on the other model. To facilitate the matching procedure, we employ a bounding volume hierarchy (BVH) for freeform NURBS surfaces, which provides a hierarchy of Coons patches and bilinear surfaces approximating the NURBS surfaces (Kim et al., 2011 [1]). Comparing the local HD upper bound against a global HD lower bound, we can eliminate the majority of redundant surface patches from further consideration. The resulting algorithm and the associated data structures are considerably simpler than the previous BVH-based HD algorithms. As a result, we can compute the HD of two freeform geometric models efficiently and robustly even when the two models are in close proximity. We demonstrate the effectiveness of our approach using several experimental results

• Computer-Aided Design, Vol 45, Issue 2, Pages 270-276, February 2013.

In this work, we present a single unified framework that can solve many geometric covering queries such as inspection and mold design. The suggested framework reduces a geometric covering query to the classic computer science set-covering problem. The solution is of exponential complexity due to the inherent complexity of the classic set-covering problem. However, in practice, we are able to efficiently offer almost optimal solutions for small-scale problems of several covering entities. Finally, using the portrayed framework, we demonstrate some results on the mold-design problem in manufacturing

• Computer-Aided Design, Vol 45, Issue 2, Pages 243-251, February 2013.

We present an efficient algorithm for trimming both local and global self-intersections in planar offset curves. The algorithm is based on a G^1-continuous biarc approximation of the given planar curves. We first consider an implementation that employs a distance map which can be stored in the graphics hardware depth buffer. The depth-buffer approach is easier to implement than a different approach that is based on a biarc-tree, a hierarchical data structure for the biarc approximation of the given planar curves. Though more involved technically, the biarc-tree algorithm is more efficient both in computing time and in memory space needed for storing the data structure. We demonstrate the real-time performance of our algorithm using several experimental results.

• Computer Aided Geometric Design, Vol 29, No 7, pp 555-564, June 2012.

Boolean sum is a well known surface construction operation [3]. In the light of the growing interest in trivariate Bspline and NURBs, for example in isogeometry analysis, in this work we extend this operator for trivariate volumetric elements. Consider six arbitrary tensor product B-spline and/or NURBs surfaces that share boundaries along a cubelike topology. The volume that is enclosed by these six surfaces is parameterized using a volumetric extension of the Boolean sum for surfaces, while the boundaries of the proposed volumetric extension interpolate the six input surfaces. Finally, a generalization of the Boolean sum idea is presented for the general multivariate case.

• Computer Aided Geometric Design, Vol 29, No 7, pp 532-540, June 2012.

We present an algorithm which is capable of globally solving a well-constrained transcendental system over some sub-domain D �� Rn, isolating all roots. Such a system consists of n unknowns and n regular functions, where each may contain non-algebraic (transcendental) functions like sin, exp or log. Every equation is considered as a hyper-surface in Rn and thus a bounding cone of its normal (gradient) field can be defined over a small enough subdomain of D. A simple test that checks the mutual configuration of these bounding cones is used that, if satisfied, guarantees at most one zero exists within the given domain. Numerical methods are then used to trace the zero. If the test fails, the domain is subdivided. Every equation is handled as an expression tree, with polynomial functions at the leaves, prescribing the domain. The tree is processed from its leaves, for which simple bounding cones are constructed, to its root, which allows to efficiently build a final bounding cone of the normal field of the whole expression. The algorithm is demonstrated on curve.curve intersection, curve.surface intersection, ray-trap and geometric constraint problems and is compared to interval arithmetic

• Computer Aided Geometric Design, Vol 29, No 5, pp 265-279, June 2012.

Free-Form Deformation (FFD) is a well established technique for deforming arbitrary object shapes in space. Although more recent deformation techniques have been introduced, among them skeleton-based deformation and cage-based deformation, the simple and versatile nature of FFD is a strong advantage, and justifies its presence in nowadays leading commercial geometric modeling and animation software systems. Since its introduction in the late 1980s, many improvements have been proposed to the FFD paradigm, including control lattices of arbitrary topology, direct shape manipulation and GPU implementation. Several authors have addressed the problem of volumepreserving FFD. These previous approaches either make use of expensive nonlinear optimization techniques, or resort to first order approximation suitable only for small-scale deformations. In this paper we take advantage of the multi-linear nature of the volume constraint in order to derive a simple, exact and explicit solution to the problem of volumepreserving FFD. Two variants of the algorithm are given, without and with direct shape manipulation. Moreover, the linearity of our solution enables to implement it efficiently on GPU.

• The Visual Computer, Vol 28, No 3, pp 231-245, 2012.

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.

• ACM Transcation on Graphics Vol 3, No 6, pp 169:1-8, Siggraph Asia 2011.

We present an algorithm which robustly computes the intersection curve(s) of an underconstrained piecewise polynomial system consisting of n equations with n+1 unknowns. The solution of such a system is typically a curve in R^(n+1). This work extends the single solution test of Hanniel and Elber (2007) [6] for a set of algebraic constraints from zero-dimensional solutions to univariate solutions, in Rn+1. Our method exploits two tests: a no-loop test (NLT) and a single-component test (SCT) that together isolate and separate domains D where the solution curve consists of just one single component. For such domains, a numerical curve tracing is applied. If one of those tests fails, D is subdivided. Finally, the single components are merged together and, consequently, the topological configuration of the resulting curve is guaranteed. Several possible applications of the solver, namely solving the surface-surface intersection problem, computing 3D trisector curves, flecnodal curves or kinematic simulations in 3D are also discussed.

• Computer Aided Design, Vol 43, No 8, pp 1035-1044, August 2011.

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 Computer & Graphics Journal, Vol 35, No 3, pp 632-638, June 2011.

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 k' = 0 (and k = 0), k 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 Journal of Graphical Models. Vol 73, No 2, pp 50-57, March 2011.

The problem of computing the minimum enclosing sphere (MES) 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. To compute the MES of a pair of hypersurfaces, each one having a contact point (a point at which the sphere touches the hypersurface), antipodal constraints are employed. For more than a pair, equidistance constraints along with tangency constraints are applied. These constraints yield a finite set of solution points which are 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.

• Computer Aided Design, Vol 43, No 3, pp 247-257, March 2011.

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.

• Computer Aided Geometric Design, Vol 27, No 8, pp 580-591, November 2010.

This work draws upon a recent result (Pekerman et al., 2008) [3] on self-intersection detection and elimination for planar curves, which attempted to eliminate redundant algebraic components. We extend this result to surfaces and bivariate functions. An algebraic decomposition is presented that reformulates the surface self-intersection problem using an alternative set of constraints, while removing the redundant components. Extensions to higher dimensions are also briefly discussed

• Computer Aided Design, Vol 41, No 12, pp 1060-1066, December 2009.

In recent years, several quite successful attempts have been made to solve systems of polynomial constraints, using geometric design tools, by making use of subdivision based solvers. This broad class of methods includes both binary domain subdivision as well as the projected polyhedron method of Sherbrooke and Patrikalakis [13]. One of the main difficulties in using subdivision solvers is their scalability. When the given constraint is represented as a tensor product of all its independent variables, it grows exponentially in size as a function of the number of variables. In this work, we show that for many applications, especially geometric, the exponential complexity of the constraints can be reduced to a polynomial one by representing the underlying problem structure in the form of expression trees that represent the constraints. We demonstrate the applicability and scalability of this representation and compare its performance to that of tensor product constraint representation, on several examples.

• IEEE Transactions on Visualization and Computer Graphics, Vol 15, No 4, pp 596-604, July/August 2009.

We present algorithms for evaluating and performing modeling operations on NURBS surfaces using the programmable fragment processor on the Graphics Processing Unit (GPU). We extend our GPU-based NURBS evaluator that evaluates NURBS surfaces to compute exact normals for either standard or rational B-spline surfaces for use in rendering and geometric modeling. We build on these calculations in our new GPU algorithms to perform standard modeling operations such as inverse evaluations, ray intersections, and surface-surface intersections on the GPU. Our modeling algorithms run in real time, enabling the user to sketch on the actual surface to create new features. In addition, the designer can edit the surface by interactively trimming it without the need for re-tessellation. We present a GPU-accelerated algorithm to perform surface-surface intersection operations with NURBS surfaces that can output intersection curves in the model space as well as in the parametric spaces of both the intersecting surfaces at interactive rates. We also extend our surface-surface intersection algorithm to evaluate self-intersections in NURBS surfaces.

• IEEE Transactions on Visualization and Computer Graphics, Vol 15, No 4, pp 530-543, July/August 2009.

We present an algorithm for computing the Voronoi cell for a set of planes, spheres and cylinders in R3. The algorithm is based on a lower envelope computation of the bisector surfaces between these primitives, and the projection of the trisector curves onto planes bounding the object for which the Voronoi cell is computed, denoted the base object. We analyze the different bisectors and trisectors that can occur in the computation. Our analysis shows that most of the bisector surfaces are quadric surfaces and five of the ten possible trisectors are conic section curves. We have implemented our algorithm using the IRIT library and the Cgal 3D lower envelope package. All presented results are from our implementation.

• Computer Aided Geometric Design. Vol 26, No 6, pp 695-710, August 2009.

Geometric constraints have proved to be helpful for shape modeling. Moreover, they are efficient aids in controlling deformations and enhancing animation realism.
The present paper addresses the deformation of B-spline surfaces while constraining the volume enclosed by the surface. Both uniform and non-uniform frameworks are considered. The use of level-of-detail (LoD) editing allows the preservation of fine details during coarse deformations of the shape. The key contribution of this paper is the computation of the volume with respect to the appropriate basis for LoD editing: the volume is expressed through all levels of resolution as a trilinear form and recursive formulas are developed to make the computation efficient. The volume constrained is maintained through a minimization process for which we develop closed solutions. Real-time deformations are reached thanks to sparse data structures and efficient algorithms.

• Computer Aided Geometric Design, Vol 25, pp 678-696, 2008.

We introduce an algorithm for approximating a 2- manifold 3D mesh by a set of developable surfaces. Each developable surface is a generalized cylinder represented as a strip of triangles not necessarily taken from the original mesh. Our algorithm is automatic, creates easy-to-assemble pieces, and provides L�� global error bounds. The approximation quality is controlled by a user-supplied parameter specifying the allowed Hausdorff distance between the input mesh and its piecewise-developable approximation. The strips generated by our algorithm may be parameterized to conform with the parameterization of the original mesh, if given, to facilitate texture mapping. We demonstrate this by physically assembling papercraft models from the strips generated by our algorithm when run on several polygonal 3D mesh data sets.

• Computer Aided Geometric Design, Vol 25, pp 576-591, 2008.

We present several algorithms for self-intersection detection, and possible elimination, in freeform planar curves and surfaces. Both local and global self-intersections are eliminated using a binormal-line criterion and a simple direct algebraic elimination procedure that enables the direct solution of the algebraic (self-)intersection constraints.
All algorithms have been fully implemented and tested. Examples are presented for applications in self-intersection detection, self-intersection-free metamorphosis of curves, and proper trimming of self-intersections in offset curves.

• Computer Aided Design, Vol 40, No 2, pp 150-159, February 2008.

We present an algorithm for generating the Voronoi cells for a set of rational $C^1$-continuous planar closed curves, which is precise up to machine precision. Initially, bisectors for pairs of curves, $(C(t), C_i(r))$, are generated symbolically and represented as implicit forms in the $tr$-parameter space. Then, the bisectors 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 International Journal of Computational Geometry and Applications, Vol 17, No 5, pp 453-496, 2007.

Computer-aided surgical simulation is a topic of increasingly extensive research. Computer graphics, geometric modeling and finite-element analysis all play major roles in these simulations. Furthermore, real-time response, interactivity and accuracy are crucial components in any such simulation system. A major effort has been invested in recent years to find ways to improve the performance, accuracy and realism of existing systems.
In this paper, we extend the work of [16], in which we used Discontinuous Free Form Deformations (DFFD) to artificially simulate real-time surgical operations. The presented scheme now uses accurate data from a Finite-Element Model (FEM), which simulates the motion response of the tissue around the scalpel, during incision. The data is then encoded once into the DFFD, representing the simulation over time. In real-time, The DFFD is applied to the vertices of the surface mesh at the actual incision location and time. The presented scheme encapsulates and takes advantage of both the speed of the DFFD application, and the accuracy of a FEM. In addition, the presented system uses a haptic force feedback device in order to improve realism and ease of use

• Computer Aided Design, Vol 39, No 8, pp 685-693, August 2007.

We present a scheme which, given two 3D geometric models, creates a third, synergetic model with resemblance to one input model from one viewing direction and the other input model from another, orthogonal, viewing direction. Our scheme automatically calculates the necessary constraints needed to deform the first model's silhouette into the second model's in 2D, and creates a 3D deformation function based on these constraints while minimizing the object's distortion in all areas but the silhouette. The motivation of this work stems from the artwork of conceptual artists such as Shigeo Fukuda and Markus Raetz.

• The Visual Computer, Vol 23, pp 219-229, March 2007.

The need for robust solutions for sets of nonlinear multivariate constraints or equations needs no motivation. Subdivision-based multivariate constraint solvers typically employ the convex hull and subdivision/domain clipping properties of the B?zier/B-spline representation to detect all regions that may contain a feasible solution. Once such a region has been identified, a numerical improvement method is usually applied, which quickly converges to the root. Termination criteria for this subdivision/domain clipping approach are necessary so that, for example, no two roots reside in the same sub-domain (root isolation).
This work presents two such termination criteria. The first theoretical criterion identifies subdomains with at most a single solution. This criterion is based on the analysis of the normal cones of the multiviarates and has been known for some time. Yet, a computationally tractable algorithm to examine this criterion has never been proposed. In this paper, we present a dual representation of the normal cones as parallel hyperplanes over the unit hypersphere, which enables us to construct an algorithm for identifying subdomains with at most a single solution. Further, we also offer a second termination criterion, based on the representation of bounding parallel hyperplane pairs, to identify and reject subdomains that contain no solution.
We implemented both algorithms in the multivariate solver of the IRIT solid modelling system and present examples using our implementation.

• Computer Aided Design, Vol 39, pp 369-378, 2007.

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.

• The Visual Computer, Vol 22, No 9-11, pp 793-804, September 2006.

A robust and efficient algorithm for trimming both local and global self-intersections in offset curves and surfaces is presented. 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, all local and global self-intersection regions in offset curves or surfaces can be detected. The zero-set of polynomial equation(s) corresponds to the self-intersection regions. These regions are trimmed 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, a numerical marching method is employed, which provides a highly precise scheme for self-intersection elimination in both offset curves and surfaces. The effectiveness of our approach is demonstrated using several experimental results. q 2005 Elsevier Ltd. All rights reserved

• Computer Aided Design, Vol 38, No 3, pp 183-193, March 2006.

This paper presents a method to globally segment volumetric images into 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. The proposed scheme relies on a novel approach to globally compute, bound, and analyze the Gaussian and mean curvatures of an entire volumetric data set, using a trivariate B-spline volumetric representation. This scheme derives a new differential scalar field for a given volumetric scalar field, which could easily be adapted to other differential properties. Moreover, this scheme can set the basis for more precise and accurate segmentation of data sets targeting the identification of primitive parts. Since the proposed scheme employs piecewise continuous functions, it is precise and insensitive to aliasing

• Pattern Analysis and Machine Intelligence Vol 28, No 2, pp 265-278, February 2006.

Striving for photorealism, texture mapping and its more advanced variations, bump and displacement mapping, have all become fundamental tools in computer graphics. Recently, the introduction of programmable graphics hardware has enabled the employment of displacement mapping in real-time applications. While displacement mapping facilitates the actual modi�cation of the underlying geometry, it is constrained by being an injective mapping. Further, it is also limited because it usually maps the geometry of the (low-resolution) smooth base surfaces, typically by displacing their vertices. Drawing from a recent work on Deformation- Displacement Mapping (DDM), in this work we offer real-time solutions to both these limitations. Our solutions make it possible to employ the DDM paradigm on programmable graphics hardware. By reversing the roles of the base surfaces and their geometric details, both the one-to-one constraint and the base surface resolution limitation are resolved. Furthermore, this role-reversal also paves the way for other benefits such as a tremendous decrease in the memory consumption of geometric detail information in the DDM and the ability to animate the details over the base surface. We show that the presented scheme can be used effectively to generate highly complex renderings and animations, in real-time, on modern graphics hardware. The capabilities of the proposed method are demonstrated for both rational parametric base surfaces and polygonal base surfaces.

• The Visual Computer, Vol 21, No 8-10, pp 791-800, August 2005.

We introduce a new approach to the problem of collision detection between a rotating milling-cutter of an NC-machine and a model of a solid workpiece, as the rotating cutter continuously moves near the workpiece. Having five degrees of motion freedom, this problem is hard to solve exactly and we approximate the motion of the tool by a sequence of sub-paths of pure translations interleaved with pure rotations. The detection problem along each sub-path is then solved by using radial projection of the obstacles (the workpiece and other parts of the NC-machine) around the tool axis to obtain a collection of critical surface patches in R^3, and by examining planar silhouettes of these surface patches. We thus reduce the problem to successive computations of the lower envelope of a set of planar curves --- this reduction is exact, and incurs no loss of accuracy. We have implemented our algorithm in the IRIT environment for solid modeling, using an extension package of the CGAL library for computing envelopes. The algorithm, combined with the proper data structures, solves the collision detection problem in a robust manner, yet it yields efficient computation times as our experiments show. Our approach produces exact results in case of purely translational motion, and provides guaranteed (and good) approximation bounds in case the motion includes rotation

• The International Journal of Computational Geometry & Applications, Vol 15, No 4, pp 351-377, August 2005.

• IEEE CG&A, Vol 25, No 4, pp 66-76, July-August 2005.

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 Journal of Graphical Models, Vol 67, No 3, pp 189-203, May 2005.

In manufacturing processes like injection molding or die casting, a 2-piece mold is required to be separable, that is, be able to have both pieces of the mold remove in opposite directions while interfering neither with the mold nor with each other. The fundamental problem is to nd a viewing (i.e. separating) direction, from which a valid partition line (i.e. the contact curves of the two mold pieces) exists. While previous research work on this problem exists for polyhedral models, verifying and nding such a partition line for general freeform shapes, represented by NURBS surfaces, is still an open question. This paper shows that such a valid partition exists for a compact surface of genus g, if and only if there is a viewing direction from which the silhouette consists of exactly g+1 non-singular disjoint loops. Hence, the 2-piece mold separability problem is essentially reduced to the topological analysis of silhouettes. In addition we deal with removing almost vertical surface regions from the mold so that the form can more easily be extracted from the mold. It follows that the aspect graph, which gives all topologically distinct silhouettes, allows one to determine the existence of a valid partition as well as to nd such a partition when it exists. In this paper, we present an aspect graph computation technique for compact free-form objects represented as NURBS surfaces. All the vision event curves (parabolic curves, ecnodal curves, and bi-tangency curves) relevant to mold separability are computed by symbolic techniques based on the NURBS representation, combined with numerical processing. An image dilation technique is then used for robust aspect graph cell decomposition on the sphere of viewing directions. Thus, an exact solution to the 2-piece mold separability problem is given for such models.

• The Journal of Computing & Information Science in Engineering, Vol 5, No 2, pp 79-85, June 2005.

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 highly precise polygon/surface�tool intersection algorithms that, combined with the proper data structure, also yields efficient computation times. Other advantages of the proposed method are 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.

• Computer Aided Design, Vol 37, No 9, pp 909-920, August 2005.

The pocketing operation is a fundamental procedure in NC machining. Typical pocketing schemes compute uniform successive offsets or parallel cuts of the outline of the pocket, resulting in a toolpath with C1 discontinuities. These discontinuities render the toolpath quite impractical in the context of high speed machining (HSM).This work addresses and fully resolves the need for a C1 continuous toolpath in HSM and offers MATHSM, a C1 continuous toolpath for arbitrary C1 continuous pockets. MATHSM automatically generates a C1 continuous toolpath that consists of primarily circular arcs while maximizing the radii of the generated arcs and, therefore, minimizing the exerted radial acceleration. MATHSM is especially suited for machining of elongated narrow pockets.

• Computer Aided Design, Vol 37, No 2, pp 241-250, February 2005.

With the increasing complexity of photorealistic scenes, the question of building and placing objects in threedimensional 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 nonrigid 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 a certain accuracy in the mapping

• Computer Graphics forum, Vol 23, No 4, pp 727-739, 2004.

This paper 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 free-form 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.

• The Visual Computer, Vol 19, No 1, pp 67-78, 2003.

Two schemes for computing moments of free-form objects are developed and analyzed. In the first scheme, we assume that the boundary of the analyzed object is represented using parametric surfaces. In the second scheme, we represent the boundary of the object as a constant set of a trivariate function. These schemes rely on a pre-computation step which allows fast re-evaluation of the moments when the analyzed object is modified. Both schemes take advantage of a representation that is based on the B-spline blending functions.

• Computer Aided Design, Vol 34, No 7, pp 529-539, June 2002.

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.

• Computer Graphics forum, Vol 21, No 2, pp 99-110 (12), June 2002.

Two schemes for computing moments of free-form objects are developed and analyzed. In the first scheme, we assume that the boundary of the analyzed object is represented using parametric surfaces. In the second scheme, we represent the boundary of the object as a constant set of a trivariate function. These schemes rely on a pre-computation step which allows fast reevaluation of the moments when the analyzed object is modified. Both schemes take advantage of a representation that is based on the B-spline blending functions.

• Computer Aided Design, Vol 34, No 7, pp 529-539, June 2002.

The use of multiresolution control toward the editing of freeform curves and surfaces has already been recognized as a valuable modeling tool. Similarly, in contemporary computer aided geometric design, the use of constraints to precisely prescribe freeform shape is considered an essential capability. This paper presents a scheme that combines multiresolution control with linear constraints into one framework, allowing one to perform multiresolution manipulation of nonuniform B-spline curves, while specifying and satisfying various linear constraints on the curves. Positional, tangential, and orthogonality constraints are all linear and can be easily incorporated into a multiresolution freeform curve editing environment, as will be shown. Moreover, we also show that the symmetry as well as the area constraints can be reformulated as linear constraints and similarly incorporated. The presented framework is extendible and we also portray this same framework in the context of freeform surfaces.

• The Journal of Computing & Information Science in Engineering, Vol 1, No 4, pp. 347-355, December 2001. Also the Sixth ACM/IEEE Symposium on Solid Modeling and Applications, Ann Arbor, Michigan, pp 109-119, June 2001

We present an algorithm that computes the convex hull of multiple rational curves in the plane. The problem is reformulated as one of finding the zero-sets of polynomial equations in one or two variables; using these zero-sets we characterize curve segments that belong to the boundary of the convex hull. We also present a preprocessing step that can eliminate many redundant curve segments.

• The Journal of Graphics Models and Image Processing, Vol 63, pp 151-162, 2001.

The bisector of two rational varieties in R^d is, in general, non-rational. However, there are some cases in which such bisectors are rational; we review some of them, mostly in R^2 and R^3. We also describe the alpha-sector, a generalization of the bisector, and consider a few interesting cases where alpha-sectors become quadratic curves or surfaces. Exact alpha-sectors are non-rational even in special cases and in configurations where the bisectors are rational. This suggests the pseudo alpha-sector which approximates the alpha-sector with a rational variety. Both the exact and the pseudo alpha-sectors identify with the bisector when alpha = 1/2.

• Computing, Supplement 14, pp 73-88, 2001.

This paper presents a direct rendering paradigm of trivariate B-spline functions, that is able to incrementally update complex volumetric data sets, in the order of millions of coefficients, at interactive rates of several frames per second, on modern workstations. This incremental rendering scheme can hence be employed in modeling sessions of volumetric trivariate functions, offering interactive volumetric sculpting capabilities. The rendering is conducted from a fixed viewpoint and in two phases. The first, preprocessing, stage accumulates the effect that the coefficients of the trivariate function have on the pixels in the image. This preprocessing stage is conducted off-line and only once per trivariate and viewing direction. The second stage conducts the actual rendering of the trivariate functions. As an example, during a volumetric sculpting operation, the artist can sculpt the volume and get a displayed feedback, in interactive rates.

• IEEE Transactions on Visualization and Computer Graphics, Vol 7, No 2, pp 109-120, April-June 2001.

This paper 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.

• Computer Graphics and Applications, Vol 21, No 3, pp 44-52, May/June 2001.

This paper presents a three dimensional interactive sculpting paradigm that employs a collection of scalar uniform trivariate Bspline 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 Bspline's representation such as subdivision, refinement and convex hull containment. A system developed using the presented approach has been used in various modeling applications including reverse engineering.

• CAD, Vol 32, No 8/9, pp 513-526, July/August 2000.

This article shows that the bisector of a point and a rational surface in R^3 is also a rational surface. This result implies that the bisector of a sphere and a surface with rational offsets is also a rational surface. Simple surfaces (planes, spheres, cylinders, cones, tori), Dupin cyclides, and rational canal surfaces (defined by rational spline curves and rational radius functions) all belong to this class of surfaces with rational offsets.

• Computer Graphics and Applications, Vol 19, No 6, pp 76-81, November-December 1999.

In recent years, synthetically created sketched based drawings and line art renderings has reached quality levels that are both esthetically pleasing and informatively enhancing. While a growing interest in this type of rendering methods has yielded successful and appealing results, the developed techniques were, for the most part, too slow to be embedded in real time interactive display. This paper 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.

• Computer Graphics forum, Vol 18, No 3, pp 1-12, September 1999. Also Eurographics 99, Milano, Italy, September 1999.

This paper presents a simple and robust method for computing the bisector of two planar rational curves. We represent the correspondence between the foot points on two planar rational curves C1(t) and C2(r) as an implicit curve F(t,r) = 0, where F(t,r) is a bivariate polynomial B-spline function. Given two rational curves of degree m in the xy-plane, the curve F(t,r) = 0 has degree 4m-2, which is considerably lower than that of the corresponding bisector curve in the xy-plane.

• CAD, Vol 30, No 14, pp 1089-1096, December 1998.

Metamorphosis, or morphing is the gradual and continuous transformation of one shape into another. The morphing problem has been investigated in the context of two-dimensional images, polygons and polylines curves, and even voxel-based volumetric representations. This work considers two methods of self-intersection elimination in metamorphosis of freeform planar curves. To begin with, both algorithms exploit the matching algorithm of and construct the best correspondence of the relative parameterizations of the initial and final curves.

• The Visual Computer, Vol 14, No 8-9, pp 415-428, 1998.

We present a scheme to preplan the set of viewing directions that are necessary to Laser scan a freeform surface. A Laser scanner is limited by the orientation of the normal of the scanned surface and a large deviation from the normal direction can hinder the ability to detect the reflected ray of the Laser. In this work, we present a freeform surface decomposition into regions, so that each region can be properly scanned from a prescribed viewing direction. The union of all these freeform surface regions forms a coverage of the entire original surface.

• CAD, Vol 30, No 4, pp 315-320, April 1998.

A technique is presented for line art rendering of scenes composed of freeform surfaces. The line art that is created for parametric surfaces is practically intrinsic and is globally invariant to changes in the surface parameterization. This method is equally applicable for line art rendering of implicit forms, creating a unified line art rendering method for both parametric and implicit forms. This added flexibility exposes a new horizon of special, parameterization independent, line art effects. Moreover, the production of the line art illustrations can be combined with traditional rendering techniques such as transparency and texture mapping. Examples that demonstrate the capabilities of the proposed approach are presented for both the parametric and implicit forms.

• IEEE Transactions on Visualization and Computer Graphics, Vol 4, No 1, pp 71-82, January-March 1998.

Given two planar curves, their convolution curve is defined as the set of all vector sums generated by all pairs of curve points which have the same curve normal direction. The Minkowski sum of two planar objects is closely related to the convolution curve of the two object boundary curves. That is, the convolution curve is a superset of the Minkowski sum boundary. By eliminating all redundant parts in the convolution curve, one can generate the Minkowski sum boundary. The Minkowski sum can be used in various important geometric computations, especially for collision detection among planar curved objects. Unfortunately, the convolution curve of two rational curves is not rational, in general. Therefore, in practice, one needs to approximate the convolution curves with polynomial/rational curves. Conventional approximation methods of convolution curves typically use piecewise linear approximations, which is not acceptable in many CAD systems due to data proliferation. In this paper, we generalize conventional approximation techniques of offset curves and develop several new methods for approximating convolution curves. Moreover, we introduce efficient methods to estimate the error in convolution curve approximation. This paper also discusses various other important issues in the boundary construction of the Minkowski sum.

• Graphics Models and Image Processing, Vol 60, No 2, pp 136-165, March 1998.

Given a point and a rational curve in the plane, their bisector curve is rational. However, in general, the bisector of two rational curves in the plane is not rational. Given a point and a rational space curve, this paper shows that the bisector surface is a rational ruled surface. Moreover, given two rational space curves, we show that the bisector surface is rational (except for the degenerate case in which the two curves are coplanar).

• ACM Transactions on Graphics, Vol 17, No 1, pp 32-50, January 1998.

Recognizing the construction methods of (piecewise) polynomial or rational curves and surfaces is of great importance, e.g., for geometrical data exchange between two different modeling systems. We formulate intrinsic conditions that are parameterization independent whenever possible. These conditions can detect: (i) whether a curve segment is a line, a circle, or a planar curve, (ii) whether a surface patch is a plane, a sphere, a cylinder, or a cone, and (iii) whether a surface is constructed as a surface of revolution/extrusion, a ruled/developable surface, or a generalized cylinder.

• Graphics Models and Image Processing, Vol 59, No 6, pp 417-433, November 1997.

With the prescription of a (piecewise) polynomial or rational cross section and axis curves, contemporary sweep or generalized cylinder constructors are incapable of creating an exact or even an approximation with a bounded error of the actual sweep surface that is represented in the same functional space, in general. An approach is presented to bound the maximal error of the sweep approximation. This bound is automatically exploited to adaptively refine and improve the sweep approximation to match a prescribed tolerance. Finally, methods are considered to eliminate the self intersecting regions in the sweep surface resulting from an axis curve with large curvature.

• CAD, Vol 29, No 6, pp 441-449, 1997.

We take advantage of ideas of an orthogonal wavelet complement to produce multiresolution orthogonal decomposition of nonuniform Bspline (NUB) spaces. The editing of NUB curves and surfaces can be handled at different levels of resolutions. Applying Multiresolution decomposition to, possibly C^1 discontinuous surfaces, one can preserve the general shape on one hand and local features on the other of the free-form models, including geometric discontinuities. The Multiresolution decomposition of the NUB tensor product surface is computed via the symbolic computation of inner products of Bspline basis functions. To find a closed form representation for the inner product of the Bspline basis functions, an equivalent interpolation problem is solved. As a one example for the strength of the Multiresolution decomposition, a tool demonstrating the Multiresolution editing capabilities of NUB surfaces was developed and is presented as part of this work, allowing interactive 3D editing of NUB free-form surfaces.

• Computer Graphics forum, Vol 16, No 3, pp 27-38, September 1997. Eurographics 1997.

 

• Computer Graphics and Applications, Vol 17, No 3, pp 62-71, May-June 1997.

This paper describes `Quick-sketch', a 2d and 3d modeling tool for pen based computers. Users of this system define a model by simple pen strokes, drawn directly on the screen of a pen-based PC. Exact shapes and geometric relationships are interpreted from the sketch. The system can be used to also sketch three-dimensional solid objects and B-spline surfaces. These objects may be refined by defining two- and three-dimensional geometric constraints. A novel graph-based constraint solver is used to establish the geometric relationships, or to maintain them when manipulating the objects interactively. The approach presented here, is a first step towards a conceptual design system. Quick-sketch can be used as a hand sketching front-end to more sophisticated modeling-, rendering- or animation systems.

• CAD, Vol 29, No 2, pp 101-112, February 1997

The traditional ray tracing technique based on a ray--surface intersection is reduced to a ruled- or developable-surface surface intersection problem, enabling direct freeform surface rendering. By exploiting the spatial coherence gained in the ruled/developable surface tracing approach presented in this work, the emulation of shadows, specular reflections and/or refractions in a freeform surface environment can all be efficiently implemented. The approach proposed herein provides a direct freeform surface rendering alternative to ray tracing. An implementation of a direct freeform surface renderer that emulates shadows as well as specular reflections is discussed. This renderer processes isoparametric curves as its basic building block, eliminating the need for any polygonal approximation.

• The Visual Computer, Vol 13, pp 78-94, 1997

Freeform parametric curves are extensively employed in various fields such as computer graphics, computer vision, robotics, and geometric modeling. While many applications exploit and combine univariate freeform entities into more complex forms such as sculptured surfaces, the problem of a fair or even optimal relative parameterization of freeforms, under some norm, has been rarely considered. In this work, we present a scheme that closely approximates the optimal relative matching between two or even n given freeform curves, under a user's prescribed norm that is based on differential properties of the curves. This matching is computed as a reparameterization of n-1 of the curves that can be applied explicitly using composition. The proposed matching algorithm is completely automatic and has been successfully employed in different applications with several demonstrated herein: metamorphosis of freeform curves with feature preservations, key frame interpolation for animation, self intersection free ruled surface construction, and automatic matching of rail curves of blending surfaces.

• CAD, Vol 29, No 5, pp 369-378, 1997.

An algorithm is presented to approximate planar offset curves within an arbitrary tolerance epsilon > 0. Given a planar parametric curve C(t) and an offset radius r, the circle of radius r is first approximated by piecewise quadratic Bezier curve segments within the tolerance epsilon. The exact offset curve Cr(t) is then approximated by the convolution of C(t) with the quadratic Bezier curve segments. For a polynomial curve C(t) of degree d, the offset curve Cr(t) is approximated by planar rational curves, Car(t)'s, of degree 3d-2. For a rational curve C(t) of degree d, the offset curve is approximated by rational curves of degree 5d-4. When they have no self-intersections, the approximated offset curves, Car(t)'s, are guaranteed to be within epsilon-distance from the exact offset curve Cr(t). The effectiveness of this approximation technique is demonstrated in the offset computation of planar curved objects bounded by polynomial/rational parametric curves.

• CAD, Vol 28, No 8, pp 617-630, August 1996.

A line-art non-photorealistic rendering scheme of scenes composed of freeform surfaces is presented. A freeform surface coverage is constructed using a set of isoparametric curves. The density of the isoparametric curves is set to be a function of the illumination of the surface determined using a simple shading model, or of regions of special importance such as silhouettes. The outcome is one way at achieving an aesthetic and attractive line-art rendering that employs isoparametric curve based drawings that is suitable for printing publication.

• IEEE Transactions on Visualization and Computer Graphics, Vol 1, No 3, pp 231-239, September 1995.

The revolution of the computer graphics field during the last two decades made it possible to create high quality synthetic images that even experts find it difficult to differentiate from real imagery. In this paper, we explore a partially overlooked theme of computer graphics that aims at conveying simple information using simple line drawings and illustrations of polygonal as well as freeform objects.

• The Visual Computer, Vol 11, No 6, 1995.

We present two models for piecewise linear approximation of freeform surfaces. One model exploits global curvature bounds and the other employs an intermediate bilinear approximation. In both models, a norm that minimizes the maximal deviation of the piecewise linear approximation from the freeform surface is used.

• CAD, Vol 28, No 1, pp 51-57, January 1996.

The control of shape of curves is of great importance in computer aided geometric design. Determination of planar curves' convexity, the detection of inflection points, coincident regions, and self intersection points, the enclosed area of a closed curve, and the locations of extreme curvature are important features of curves that can affect the design, in modeling environments. In this paper, we investigate the ability to robustly answer the above queries and related questions using an approach which exploits both symbolic computation and numeric analysis.

• Computer Graphics forum, Vol 14, No 1, pp 25-34, March 1995.