Compliant mechanisms have captured the attention of many researchers in recent years, with ever-expanding mechanical and physical behaviors. Moreover, the fabrication of such mechanisms has been greatly simplified with the enabling technology of 3D printing. Drawing from existing lattice construction abilities, in this work we explore the abilities of constructing whole freeform lattices, where the tiles in these lattices are compliant mechanisms, possibly heterogeneous. Specifically, herein we focus on bi-stable and multi-stable tiles, or tiles with two or more mechanical stable states. The introduced approach will be exemplified on a variety of 2D and 3D lattices, fabricated with the aid of additive manufacturing.

Abstract The synthesis of porous, lattice, or microstructure geometries has captured the attention of many researchers in recent years. Implicit forms, such as triply periodic minimal surfaces (TPMS) has captured a significant attention, recently, as tiles in lattices, partially because implicit forms have the potential for synthesizing with ease more complex topologies of tiles, compared to parametric forms. In this work, we show how variable offsets of implicit forms could be used in lattice design as well as lattice analysis, while graded wall and edge thicknesses could be fully controlled in the lattice and even vary within a single tile. As a result, (geometrically) heterogeneous lattices could be created and adapted to follow analysis results while maintaining continuity between adjacent tiles. We demonstrate this ability on several 3D models, including TPMS.

Boolean sum and ruling are two well-known construction operators for both parametric surfaces and trivariates. In many cases, the input freeform curves in or surfaces in are complex, and as a result, these construction operators might fail to build the parametric geometry so that it has a positive Jacobian throughout the domain. In this work, we focus on cases in which those constructors fail to build parametric geometries with a positive Jacobian throughout while the freeform input has a kernel point. We show that in the limit, for high enough degree raising or enough refinement, our construction scheme must succeed if a kernel exists. In practice, our experiments, on quadratic, cubic and quartic Bézier and B-spline curves and surfaces show that for a reasonable degree raising and/or refinement, the vast majority of construction examples are successful.

We present a complete microstructure tiling paradigm for V-rep models, or volumetric models consisting of trimmed trivariates. Existing methods (Massarwi et al., 2018) are employed to tile individual primitive tensor product trivariates in a conformal way, only to handle the intersection of the microstructure tiles with the trimming surfaces of the trivariates. One-to-one and two-to-one bridging tiles are then constructed along the trimmed zones, while tile-clipping is completely avoided. The Boolean operation cases of subtraction, intersection and union are considered. The result is a set of, regular in the interior, possibly heterogeneous, trivariates, that defines the whole microstructure arrangement. This result is fully compatible with iso-geometric analysis as well as heterogeneous additive manufacturing. Examples are presented, including of 3D printed heterogeneous microstructures.

Abstract We present a highly efficient algorithm for computing the minimum distance between two solids of revolution, each of which is defined by a planar cross‐section region and a rotation axis. The boundary profile curve for the cross‐section is first approximated by a bounding volume hierarchy (BVH) of fat arcs. By rotating the fat arcs around the axis, we generate the BVH of fat tori that bounds the surface of revolution. The minimum distance between two solids of revolution is then computed very efficiently using the distance between fat tori, which can be boiled down to the minimum distance computation for circles in the three‐dimensional space. Our circle‐based approach to the solids of revolution has distinctive features of geometric simplification. The main advantage is in the effectiveness of our approach in handling the complex cases where the minimum distance is obtained in non‐convex regions of the solids under consideration. Though we are dealing with a geometric problem for solids, the algorithm actually works in a computational style similar to that of handling planar curves. Compared with conventional BVH‐based methods, our algorithm demonstrates outperformance in computing speed, often 10–100 times faster. Moreover, the minimum distance can be computed very efficiently for the solids of revolution under deformation, where the dynamic reconstruction of fat arcs dominates the overall computation time and takes a few milliseconds.

Moving from the concept of discrete sequences of 2D slides towards smooth 3D multimodal hierarchical presentations promises many improvements in quality and effectiveness of presentations. On the other hand, such a move poses many difficulties, one of which is how to arrange content in a 3D space. This task becomes further complicated when the story-graph of the presentation is evolving and is more complex than a single linear story-path. In this work, we propose a framework for automatically solving the task of 3D content placement, which is based on views --- 3D replacement for slides. We also examplify our proposed approach with two spatial layouts for 3D non-linear presentations: "nested spheres" and a 'building', as well as algorithms that automatically create these layouts from an abstract hierarchical story-graph.

Abstract We present an interactive tree modeling and deformation system that supports an efficient collision detection and avoidance using a bounding volume hierarchy of sweep surfaces. Starting with conventional tree models (given as meshes), we convert them into sweep surfaces and deform their branches interactively while detecting and avoiding collisions with many other branches. Multiple tree models (sharing the same topology) can be generated with great ease using this sweep‐based approach, and they can serve as a basis for the generation of a multiparameter family of trees. We demonstrate the effectiveness of our approach in an automatic generation of similar trees, the colonization of trees to form a forest, and the tree growth, aging, and withering simulations. Copyright © 2015 John Wiley & Sons, Ltd.

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.

We present an algorithm which robustly computes the intersection curve(s) of an under-constrained piecewise polynomial system consisting of n equations with n + 1 unknowns. The solution of such a system is typically a curve in Rn+1. This work extends the single solution test of [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 application of the solver, like 3D trisector curves or kinematic simulations in 3D are discussed.

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.

We present an accurate and efficient algorithm for continuous collision detection between two moving ellipsoids under rational Euclidean or affine motion. We start with a highly optimized implementation of interference testing between two stationary ellipsoids based on an algebraic condition described in terms of the signs of roots of the characteristic equation of two ellipsoids. Then we derive a time-dependent characteristic equation for two moving ellipsoids, which enables us to develop an efficient algorithm for computing the time intervals in which two moving ellipsoids collide. The effectiveness of our approach is demonstrated with several practical examples.

In recent years, several quite successful attempts have been made to solve systems of polynomial constraints, using geometric design tools, exploiting the availability of subdivision-based solvers [7], [11], [12], [15]. This broad range of methods includes both binary domain subdivision as well as the projected polyhedron method of Sherbrooke and Patrikalakis [15]. A prime obstacle 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 ones, the exponential complexity of the constraints can be reduced to a polynomial by representing the underlying structure of the problem 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 through several examples.

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 retessellation. Our GPU-accelerated algorithm to perform surface-surface intersection operations with NURBS surfaces 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.

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.

We present algorithms for evaluating and performing modeling operatyons 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 also 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 present robust and efficient algorithms for computing Voronoi diagrams of planar freeform curves. Boundaries of the Voronoi diagram consist of portions of the bisector curves between pairs of planar curves. Our scheme is based on computing critical structures of the Voronoi diagrams, such as self-intersections and junction points of bisector curves. Since the geometric objects we consider in this paper are represented as freeform NURBS curves, we were able to reformulate the solution to the problem of computing those critical structures into the zero-set solutions of a system of nonlinear piecewise rational equations in parameter space. We present a new algorithm for computing error-bounded bisector curves using a distance surface constructed from error-bounded offset approximations of planar curves. This error-bounded algorithm is fast and produces bisector curves that are correct both in topology and geometry. Once bisectors are computed, both local and global self-intersections of the bisector curves are located and trimmed away by solving a system of three piecewise rational equations in three variables. Further, our method computes junction points at which three or more trimmed bisector curves intersect by transforming them into the solutions to a system of piecewise rational equations in the merged parameter space of the planar curves. The bisectors are trimmed at those self-intersection and global junction points. The Voronoi diagram is then computed from the trimmed bisectors using a pruning algorithm. We demonstrate the effectiveness of our approach with several experimental results.

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.

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_\alpha 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.

No abstract available.

This paper presents a simple yet precise and efficient algorithm for collision prediction of two oriented bounding boxes under univariate (piecewise) rational motion. We present an analytic solution to the problem of finding the time of collision and the feature involved, or declaring that no collision should occur. Our solution can be applied to boxes of any size, under arbitrary rational rigid motion. The algorithm is based on the efficient examination of the Minkowski sum (MS) of the two boxes, using a spherical Gauss map dual representation, and a precise extraction of the collision time, if any, as a solution to a set of rational equations that are automatically derived

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 [Sela et al. 2004], 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.

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.

We present an algorithm for generating the Voronoi cells for a set of rational C1-continuous planar closed curves, which is precise up to machine precision. Initially, bisectors for pairs of curves, (C(t), Ci(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.

This paper considers computation of visibility for two-dimensional shapes whose boundaries are C1 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 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.

We propose an algorithm for contouring k-manifolds (k = 1,2) embedded in an arbitrary n-dimensional space. We assume (n -k) geometric constraints are represented as polynomial equations in n variables. The common zero-set of these (n-k) equations is computed as an 1-or 2-manifold, respectively, for k = 1 or k = 2. In the case of 1-manifolds, this framework is a generalization of techniques for contouring regular intersection curves between two implicitly-defined surfaces of the form F(x,y,z) = G(x,y,z) = 0. Moreover, in the case of 2-manifolds, the algorithm is similar to techniques for contouring iso-surfaces of the form F(x, y, z) = 0, where n = 3 and only one (=3 -2) constraint is provided. By extending the Dual Contouring technique to higher dimensions, we approximate the simultaneous zero-set as a piecewise linear 1or 2-manifold. There are numerous applications for this technique in data visualization and modeling, including the processing of various geometric constraints for freeform objects, and the computation of convex hulls, bisectors, blendings and sweeps.

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

We present efficient and robust algorithms for intersecting a freeform surface with a ringed surface or a ruled surface. A ringed surface is given as a one-parameter family of circles. By computing the intersection between a freeform surface and each circle in the family, we can solve the intersection problem. We propose two approaches which are closely related to each other. The first approach detects certain critical points; and the intersection curve is constructed by connecting them in a correct topology. The second approach converts the intersection problem to that of finding the zero set of two polynomial equations in the parameter space. The intersection between a freeform surface and a ruled surface can be computed in a similar way.

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

Contemporary deformation tools let designers modify the geometry of deformed models. 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 isoparametric 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 reforming it. The second application works locally, enabling the end-user to insert arbitrarily shaped cuts into the surface of the model.

In manufacturing processes like injection molding or die casting, a 2-piece mold is required to be separable, that is, having both pieces of the molds removed in opposite directions while interfering neither with the mold nor with each other. The fundamental problem is to find 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 finding 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 nonsingular disjoint loops. Hence, the 2-piece mold separability problem is essentially reduced to the topological analysis of silhouettes. 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 find such a partition when it exists. We present an aspect graph computation technique for compact free-form objects represented as NURBS surfaces. All the vision event curves (parabolic curves, flecnodal curves, and bitangency 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.

Abstract With the increasing complexity of photorealistic 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 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.

Estimating intrinsic geometric properties of a surface from a polygonal mesh obtained from range data is an important stage of numerous algorithms in computer and robot vision, computer graphics, geometric modeling, industrial and biomedical engineering. This work considers different computational schemes for local estimation of intrinsic curvature geometric properties. Five different algorithms and their modifications were tested on triangular meshes that represent tessellations of synthetic geometric models. The results were compared with the analytically computed values of the Gaussian and mean curvatures of the non-uniform rational B-spline (NURBs) surfaces, these meshes originated from. This work manifests the best algorithms suited for that indeed different algorithms should be employed to compute the Gaussian and mean curvatures.

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.

Texture mapping, bump mapping, and displacement maps are central instruments in computer graphics aiming to achieve photo-realistic renderings. In all these techniques, the mapping is typically one-to-one and a single surface location is assigned a single texture color, normal, or displacement. Other specialized techniques have also been developed for the rendering of supplementary surface details such as fur hair, or scales. This work presents an extended view of these procedures and 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 freeform deformations. As a consequence, an 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.

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 Bézier 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.

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

The bisector of two rational surfaces in R/sup 3/ is, in general, nonrational; and so is the bisector of a rational curve and a rational surface. Thus, bisector surfaces in these two cases must be approximated numerically. Unfortunately, they are algebraic surfaces of very high degree and numerical approximation is non-trivial. This paper suggests a new computational model for constructing curve-surface and surface-surface bisectors in R/sup 3/. The curve-surface bisector problem is reformulated as the search for a trivariate zero-set; and the surface-surface bisector problem is reduced to that of finding the common zero-set of two four-variate functions.

Presents an efficient and robust algorithm to compute the intersection curve of two ringed surfaces, each being the sweep /spl cup//sub u/C/sup u/ generated by a moving circle. Given two ringed surfaces /spl cup//sub u/C/sub 1//sup u/ and /spl cup//sub v/C/sub 2//sup v/, we formulate the condition C/sub 1//sup u//spl cap/C/sub 2//sup v//spl ne/O (i.e. that the intersection of the two circles C/sub 1//sup u/ and C/sub 2//sup v/ is non-empty) as a bivariate equation /spl lambda/(u,v)= 0 of relatively low degree. Except for some redundant solutions and degenerate cases, there is a rational map from each solution of /spl lambda/(u,v)=0 to the intersection point C/sub 1//sup u//spl cap/C/sub 2//sup v/. Thus, it is trivial to construct the intersection curve once we have computed the zero-set of /spl lambda/(u,v)=0. We also analyze some exceptional cases and consider how to construct the corresponding intersection curves.

A novel 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) given by the base curve. This method has proven to provide great flexibility and give high quality results in layout of text.

An algorithm to allow real time interactive extraction and orthographic display of silhouettes of complex two-manifold polygonal object(s) is presented. An off-line pre-processing of all the edges of all polygons enables the efficient extraction of the silhouette edges in real time, once a viewing direction is prescribed. During the interactive session, the time complexity of extracting the silhouette edges is linear in the number of edges in the silhouette, and is typically in the order of O(/spl radic/n), where n is the number of polygons in the scene. The time complexity of the pre-processing stage is linear in n.

In recent years, synthetically created line art renderings have reached quality levels that are aesthetically pleasing. Moreover, the sketch based approach was found to be quite capable at conveying geometrical information in an intuitive manner. While a growing interest in this type of rendering method 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 these strokes, allows one to significantly alleviate the computational cost, in real time, of the sketch based rendering, and enables interactive line art display.

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.

This paper presents a technique to improves the performance of algorithms that exploits visibility based analysis in computer graphics, such as ray tracing. The presented approach maintains a list of visible polygons for each and every one of the polygons in the model as well as for optionally, the light sources in the scene. A pre-processing visibility analysis stage that is view-independent is computed once per scene, creating a Visibility Data Structure (VDS) that becomes part of the model. This, before any visibility intensive computer graphics algorithm takes place. The approach presented may be combined with most acceleration methods for ray tracing such as octree or voxel based spatial subdivision. Furthermore, any algorithm that requires visibility computations can exploit the VDS, from Radiosity to NC machining. Though the presented technique is fairly intuitive, it demonstrates the usability of a visibility data structure of a scene.

Given a point and a rational curve in the plane, their bisector curve is rational [Farouki and Johnston 1994a]. However, in general, the bisector of two rational curves in the plane is not rational [Farouki and Johnstone 1994b]. Given a point and a rational space curve, this art icle 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).

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.

Article The bisector surface of freeform rational space curves Share on Authors: Gershon Elber Department of Computer Science Technion, Israel Institute of Technology, Haifa 32000, Israel Department of Computer Science Technion, Israel Institute of Technology, Haifa 32000, IsraelView Profile , Myung-Soo Kim Department of Computer Science, POSTECH, Pohang 790-784, South Korea Department of Computer Science, POSTECH, Pohang 790-784, South KoreaView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997 Pages 473–474https://doi.org/10.1145/262839.263091Online:01 August 1997Publication History 3citation171DownloadsMetricsTotal Citations3Total Downloads171Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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 C1 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 an 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.

This paper presents a symbolic approach to the computation of blend surfaces across piecewise polynomial and rational surfaces. Curves in the parameter space of the primary surfaces can be specified as the rail curves, also known as trimlines, of the blend. Several techniques which require various levels of user interaction are presented for defining the cross-boundary tangent curves along the rail curves. The resulting blend is represented as a polynomial surface having tangent plane continuity with the primary surfaces to an accuracy bounded only by the machine precision. Also presented is a normalization method that approximates unit vector fields, an approach that might benefit other applications such as offset approximation and animation curve construction. © 1997 by John Wiley & Sons, Ltd.

This paper studies an adaptive polygonization method for parametric surfaces that is physically based. A set of sampled points is distributed by this algorithm according to the curvature field of the surface. A triangulation is then superimposed over this sampled set. The locations of these sampled points are obtained by employing physically based models of interaction of particles. Two physical models are considered in this study: a spring-mass model and a model of electrostatically charged particles. The resulting algorithm equally distributes the approximation error of the triangulation throughout the surface, once the equilibrium state of the physical model is reached.

article Free AccessAdaptive isocurve-based rendering for freeform surfaces Authors: Gershon Elber Computer Science Department, Technion--Israel Institute of Technology, 3200 Haifa, Israel Computer Science Department, Technion--Israel Institute of Technology, 3200 Haifa, IsraelView Profile , Elaine Cohen Computer Science Department, University of Utah, Salt Lake City, UT Computer Science Department, University of Utah, Salt Lake City, UTView Profile Authors Info & Claims ACM Transactions on GraphicsVolume 15Issue 3July 1996 pp 249–263https://doi.org/10.1145/231731.231736Published:15 July 1996Publication History 13citation674DownloadsMetricsTotal Citations13Total Downloads674Last 12 Months19Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Abstract The control of shape of curves is of great importance in computer aided geometric design. Determination of planar curves' convexity, the detection of infection points, coincident regions, and self intersection points, the enclosed area of a closed curve, and the locations of extreme curvature are importantfeatures of curves that can affect the design, in modelling 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.

A line art nonphotorealistic 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 of achieving an aesthetic and attractive line art rendering that employs isoparametric curve based drawings that is suitable for printing publication.>

We present an efficient method to simulate the propagation of wavefronts and approximate the behavior of light in an environment of freeform surfaces. The proposed method can emulate the behavior of a wavefront emanating from a point or spherical light source, and possibly refracted and/or reflected from a freeform surface. Moreover, it allows one to consider and to render images with extreme illumination conditions such as caustics.

Results from analyzing the curvature of a surface can be used to improve the implementation, efficiency, and effectiveness of manufacturing and visualization of sculptured surfaces. We develop a robust method using hybrid symbolic and numeric operators to create trimmed surfaces, each of which is solely convex, concave, or saddle and partitions the original surface. The same method is also used to identify regions whose curvature lies within prespecified bounds.

This paper describes a hidden curve algorithm specifically designed for sculptured surfaces. A technique is described to extract the visible curves for a given scene without the need to approximate the surface by polygons. This algorithm produces higher quality results than polygon based algorithms, as most of the output set has an exact representation. Surface coherence is used to speed up the process. Although designed for sculptured surfaces, this algorithm is also suitable for polygonal data.