Journal publications with the IRIT modeling environment

This file lists the set of Journal papers that were implemented with the aid of the IRIT solid modeling tool.

Surface Rendering Using Layout of Text

Tatiana Surazhsky and Gershon Elber

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.

Exact and Efficient Computation of Moments of Free-Form Surface and Trivariate Based Geometry

Octavian Soldea, Gershon Elber, and Ehud Rivlin

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.

Multiresolution Curve Editing with Linear Constraints

Gershon Elber

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

Convex Hull of Rational Plane Curves

Gershon Elber, Myung-Soo Kim, and Hee-Seok Heo

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.

Curve Evaluation and Interrogation on Surfaces

Gershon Elber

This paper presents a coherent computational framework to efficiently, and more so robustly, evaluate, interrogate 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 while these characteristic curves are crucial for various applications, from visualization through interrogation to design and manufacturing.

The Journal of Graphical Models, Vol 63, pp 197-210, May 2001.

Bisectors and alpha-Sectors of Rational Varieties

Gershon Elber, Gill Barequet, and Myung-Soo Kim

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.

Interactive Direct Rendering of Trivariate Bspline Scalar Functions

Alon Raviv and Gershon Elber

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.

Rendering with Parallel Stripes

Gershon Elber

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.

Three Dimensional Freeform Sculpting Via Zero Sets of Scalar Trivariate Functions

Alon Raviv and Gershon Elber

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.

Computing Rational Bisectors

Gershon Elber and Myung Soo Kim

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.

Interactive Line Art Rendering of Freeform Surfaces

Gershon Elber

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.

Bisector Curves of Planar Rational Curves

Gershon Elber and Myung Soo Kim

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.

Self-Intersection Elimination in Metamorphosis of Two-Dimensional Curves

Tatiana Samoilov and Gershon Elber

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.

Cone Visibility Decomposition of Freeform Surfaces

Gershon Elber and Eyal Zussman

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.

Line Art Illustrations of Parametric and Implicit Forms

Gershon Elber

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.

Polynomial/Rational Approximation of Minkowski Sum Boundary Curves

In-Kwon Lee, Myung Soo Kim and Gershon Elber

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.

The Bisector Surface of Freeform Rational Space Curves

Gershon Elber and Myung-Soo Kim

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.

Geometric Shape Recognition of Freeform Curves and Surfaces

Gershon Elber and Myung-Soo Kim

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.

Global Error Bounds and Amelioration of Sweep Surfaces

Gershon Elber

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.

Orthogonal Decomposition of Non-Uniform Bspline Spaces using Wavelets

Roman Kazinnik and Gershon Elber

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.

Comparing Offset Curve Approximation Methods

Gershon Elber, In-Kwon Lee, and Myung-Soo Kim

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

Inferring 3D models from freehand sketches and constraints

Lynn Eggli, Ching-yao Hsu, Beat D. Bruderlin, and Gershon Elber

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

Ruled Tracing

Gershon Elber, Jung-Ju Choi, and Myung-Soo Kim

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

Matching of Freeform Curves

Shmuel Cohen, Gershon Elber, and Reuven Bar Yehuda

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.

Planar Curve Offset Based on Circle Approximation

In-Kwon Lee, Myung-Soo Kim, and Gershon Elber

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.

Line Art Rendering via a Coverage of Isoparametric Curves

Gershon Elber

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.

Line Illustrations in Computer Graphics

Gershon Elber

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.

Error Bounded Piecewise Linear Approximation of Freeform Surfaces.

Gershon Elber

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.

Symbolic and Numeric Computation in Curve Interrogation

Gershon Elber

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.