The increasing interest in B-spline volumetric representations for representing material attributes and for performing simulations has promoted research into volume completion with semi-structured trivariate B-splines. Because of the lack of a watertight representation, such techniques have not been extensible to trimmed B-spline B-reps, the results of Boolean operations on surface models. Starting with a trimmed B-spline B-rep, using recently developed hybrid watertight B-reps, we create a representation for hybrid volume completion. A discussion of the volume completion problem is presented, as well as the new method and results.

In this paper, we introduce a volumetric partitioning strategy based on a generalized sweeping framework to seamlessly partition the volume of an input triangle mesh into a collection of deformed cuboids. This is achieved by a user-designed volumetric harmonic function that guides the decomposition of the input volume into a sequence of two-manifold level sets. A skeletal structure whose corners correspond to corner vertices of a 2D parameterization is extracted for each level set. Corners are placed so that the skeletal structure aligns with features of the input object. Then, a skeletal surface is constructed by matching the skeletal structures of adjacent level sets. The surface sheets of this skeletal surface partition the input volume into the deformed cuboids. The collection of cuboids does not exhibit T-junctions, significantly simplifying the hexahedral mesh generation process, and in particular, it simplifies fitting trivariate B-splines to the deformed cuboids. Intersections of the surface sheets of the skeletal surface correspond to the singular edges of the generated hex-meshes. We apply our technique to a variety of 3D objects and demonstrate the benefit of the structure decomposition in data fitting.

In this article, we investigate the use of quadratic finite elements for graphical animation of deformable bodies. We consider both integrating quadratic elements with conventional linear elements to achieve a computationally efficient adaptive-degree simulation framework as well as wholly quadratic elements for the simulation of nonlinear rest shapes. In both cases, we adopt the Bézier basis functions and employ a co-rotational linear strain formulation. As with linear elements, the co-rotational formulation allows us to precompute per-element stiffness matrices, resulting in substantial computational savings. We present several examples that demonstrate the advantages of quadratic elements in general and our adaptive-degree system in particular. Furthermore, we demonstrate, for the first time in computer graphics, animations of volumetric deformable bodies with nonlinear rest shapes.

Peak finding provides more accurate classification for direct volume rendering by sampling directly at local maxima in a transfer function, allowing for better reproduction of high-frequency features. However, the 1D peak finding technique does not extend to higherdimensional classification. In this work, we develop a new method for peak finding with multidimensional transfer functions, which looks for peaks along the image of the ray. We use piecewise approximations to dynamically sample in transfer function space between world-space samples. As with unidimensional peak finding, this approach is useful for specifying transfer functions with greater precision, and for accurately rendering noisy volume data at lower sampling rates. Multidimensional peak finding produces comparable image quality with order-of-magnitude better performance, and can reproduce features omitted entirely by standard classification. With no precomputation or storage requirements, it is an attractive alternative to preintegration for multidimensional transfer functions.

Abstract We introduce a novel mid‐structure called the generalized swept mid‐structure (GSM) of a closed polygonal shape, and a framework to compute it. The GSM contains both curve and surface elements and has consistent sheet‐by‐sheet topology, versus triangle‐by‐triangle topology produced by other mid‐structure methods. To obtain this structure, a harmonic function, defined on the volume that is enclosed by the surface, is used to decompose the volume into a set of slices. A technique for computing the 1D mid‐structures of these slices is introduced. The mid‐structures of adjacent slices are then iteratively matched through a boundary similarity computation and triangulated to form the GSM. This structure respects the topology of the input surface model is a hybrid mid‐structure representation. The construction and topology of the GSM allows for local and global simplification, used in further applications such as parameterization, volumetric mesh generation and medical applications.

In this paper, we present a novel isosurface visualization technique that guarantees the accurate visualization of isosurfaces with complex attribute data defined on (un)structured (curvi)linear hexahedral grids. Isosurfaces of high-order hexahedral-based finite element solutions on both uniform grids (including MRI and CT scans) and more complex geometry representing a domain of interest that can be rendered using our algorithm. Additionally, our technique can be used to directly visualize solutions and attributes in isogeometric analysis, an area based on trivariate high-order NURBS (Non-Uniform Rational B-splines) geometry and attribute representations for the analysis. Furthermore, our technique can be used to visualize isosurfaces of algebraic functions. Our approach combines subdivision and numerical root finding to form a robust and efficient isosurface visualization algorithm that does not miss surface features, while finding all intersections between a view frustum and desired isosurfaces. This allows the use of view-independent transparency in the rendering process. We demonstrate our technique through a straightforward CPU implementation on both complex-structured and complex-unstructured geometries with high-order simulation solutions, isosurfaces of medical data sets, and isosurfaces of algebraic functions.

This paper addresses the problem of computing the geodesic distance map from a given set of source vertices to all other vertices on a surface mesh using an anisotropic distance metric. Formulating this problem as an equivalent control theoretic problem with Hamilton-Jacobi-Bellman partial differential equations, we present a framework for computing an anisotropic geodesic map using a curvature-based speed function. An ordered upwind method (OUM)-based solver for these equations is available for unstructured planar meshes. We adopt this OUM-based solver for surface meshes and present a triangulation-invariant method for the solver. Our basic idea is to explore proximity among the vertices on a surface while locally following the characteristic direction at each vertex. We also propose two speed functions based on classical curvature tensors and show that the resulting anisotropic geodesic maps reflect surface geometry well through several experiments, including isocontour generation, offset curve computation, medial axis extraction, and ridge/valley curve extraction. Our approach facilitates surface analysis and processing by defining speed functions in an application-dependent manner.

Ridges are extremal curves of principal curvatures on a surface that indicate salient intrinsic features of its shape. This paper presents a novel approach for extracting ridges of improved quality from isosurfaces of volumetric scalar-valued grids by converting them to implicit trivariate B-spline representations. A robust tracing approach demonstrated to extract ridges accurately from parametric B-spline surfaces is extended to extract ridges directly from the implicit representations resulting in accurate and hence smoother, connected ridge curves as compared to approaches that extract ridges directly from discrete representations. This approach can also be used to extract ridges directly from smooth representations such as isosurfaces of volumetric B-Spline CAD models and algebraic functions, and extended to extract ridges from polygonal meshes, as demonstrated in the paper. Most of the existing approaches for ridge extraction address only crests, a certain subset of the ridges on a surface. The approach presented in this paper enables extraction of all types of generic ridges on a surface thereby presenting a complete solution.

Ridges are characteristic curves of a surface that mark salient intrinsic features of its shape and are therefore valuable for shape matching, surface quality control, visualization and various other applications. Ridges are loci of points on a surface where either of the principal curvatures attain a critical value in its respective principal direction. These curves have complex behavior near umbilics on a surface, and may also pass through certain turning points causing added complexity for ridge computation. We present a new algorithm for numerically tracing ridges on B-Spline surfaces that also accurately captures ridge behavior at umbilics and ridge turning points. The algorithm traverses ridge segments by detecting ridge points while advancing and sliding in principal directions on a surface in a novel manner, thereby computing connected curves of ridge points. The output of the algorithm is a set of curve segments, some or all of which, may be selected for other applications such as those mentioned above. The results of our technique are validated by comparison with results from previous research and with a brute-force domain sampling technique.

Abstract Semi‐regular meshes describe surface models that exhibit a structural regularity that facilitates many geometric processing algorithms. We introduce a technique to construct semi‐regular, quad‐only meshes from input surface meshes of arbitrary polygonal type and genus. The algorithm generates a quad‐only model through subdivision of the input polygons, then simplifies to a base domain that is homeomorphic to the original mesh. During the simplification, a novel hierarchical mapping method,keyframe mapping, stores specific levels‐of‐detail to guide the mapping of the original vertices to the base domain. The algorithm implements a scheme for refinement with adaptive resampling of the base domain and backward projects to the original surface. As a byproduct of the remeshing scheme, a surface parameterization is associated with the remesh vertices to facilitate subsequent geometric processing, i.e. texture mapping, subdivision surfaces and spline‐based modeling.

Abstract In this paper we introduce a coarsening algorithm for quadrilateral meshes that generates quality, quad‐only connectivity during level‐of‐coarseningcreation. A novel aspect of this work is development and implementation of a localized adaptation of thepolychordcollapse operator to better control and preserve important surface components. We describe a novel weighting scheme for automatic deletion selection that considers surface attributes, as well as localized queue updates that allow for improved data structures and computational performance opportunities over previous techniques. Additionally, this work supports optional and intuitive user controls for tailored simplification results.

B-spline multiplication, that is, finding the coefficients of the product B-spline of two given B-splines is useful as an end result, in addition to being an important prerequisite component to many other symbolic computation operations on B-splines. Algorithms for B-spline multiplication standardly use indirect approaches such as nodal interpolation or computing the product of each set of polynomial pieces using various bases. The original direct approach is complicated. B-spline blossoming provides another direct approach that can be straightforwardly translated from mathematical equation to implementation; however, the algorithm does not scale well with degree or dimension of the subject tensor product B-splines. To addresses the difficulties mentioned heretofore, we present the Sliding Windows Algorithm (SWA), a new blossoming based algorithm for the multiplication of two B-spline curves, two B-spline surfaces, or any two general multivariate B-splines.

We present a methodology based on discrete volumetric harmonic functions to parameterize a volumetric model in a way that it can be used to fit a single trivariate B-spline to data so that simulation attributes can also be modeled. The resulting model representation is suitable for isogeometric analysis [Hughes T. J. 2005], Imput data consists of both a closed triangle mesh representing the exterior geometric shape of the object and interior triangle meshes that can represent material attributes or other interior features. The trivariate B-spline geometric and attribute representations are generated from the resulting parameterization, creating trivariate B-spline material property representations over the same parameterization in a way that is related to [Martin and Cohen 2001] but is suitable for application to a much larger family of shapes and attributes. The technique constructs a B-spline representation with guaranteed quality of approximation to the original data. Then we focus attention on a model of simulation interest, a femur, consisting of hard outer cortical bone and inner trabecular bone. The femur is a reasonably complex object to model with a single trivariate B-spline since the shape overhangs make it impossible to model by sweeping planar slices. The representation is used in an elastostatic isogeometric analysis, demonstrating its ability to suitably represent objects for isogeometric analysis.

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.

The distribution of geometric features is anisotropic by its nature. Intrinsic properties of surfaces such as normal curvatures, for example, varies with direction. In this paper this characteristic of a shape is used to create a new anisotropic geodesic (AG) distance map on parametric surfaces. We first define local distance (LD) from a point as a function of both the surface point and a unit direction in its tangent plane and then define a total distance as an integral of that local distance. The AG distance between points on the surface is then defined as their minimum total distance. The path between the points that attains the minimum is called the anisotropic geodesic path. This differs from the usual geodesic in ways that enable it to better reveal geometric features. Minimizing total distances to attain AG distance is performed by associating the LD function with the tensor speed function that controls wave propagation of the convex Hamilton-Jacobi (H-J) equation solver. We present two different, but related metrics for the local distance function, a curvature tensor and a difference curvature tensor. Each creates a different AG distance. Some properties of both new AG distance maps are presented, including parametrization invariance. We then demonstrate the effectiveness of the proposed geodesic map as a shape discriminator in several applications, including surface segmentation and partial shape matching.

We introduce a simplification algorithm for meshes composed of quadrilateral elements. It is reminiscent of edge-collapse based methods for triangle meshes, but takes a novel approach to the challenging problem of maintaining the quadrilateral connectivity during level-of-detail creation. The method consists of a set of unit operations applied to the dual of the mesh, each designed to improve mesh structure and maintain topological genus. Geometric shape is maintained by an extension of a quadric error metric to quad meshes. The technique is straightforward to implement and efficient enough to be applied to real-world models. Our technique can handle models with sharp features, and can be used to re-mesh general polygonal, i.e. tri- and quad-dominant, meshes into quadonly meshes.

B-spline multiplication, that is, finding the coefficients of the product B-spline of two given B-splines, is useful as an end result, in addition to being an important prerequisite component to many other symbolic computation operations on B-splines. Algorithms for B-spline multiplication standardly use indirect approaches such as nodal interpolation or computing the product of each set of polynomial pieces using various bases. The original direct approach is complicated. B-spline blossoming provides another direct approach that can be straightforwardly translated from mathematical equation to implementation; however, the algorithm does not scale well with degree or dimension of the subject tensor product B-splines. We present the Sliding Windows Algorithm (SWA), a new blossoming based algorithm for B-spline multiplication that addresses the difficulties mentioned heretofore.

We present an efficient and robust algorithm for computing the minimum distance between a point and freeform curve or surface by lifting the problem into a higher dimension. This higher dimensional formulation solves for all query points in the domain simultaneously, therefore providing opportunities to speed computation by applying coherency techniques. In this framework, minimum distance between a point and planar curve is solved using a single polynomial equation in three variables (two variables for a position of the point and one for the curve). This formulation yields two-manifold surfaces as a zero-set in a 3D parameter space. Given a particular query point, the solution space's remaining degrees-of-freedom are fixed and we can numerically compute the minimum distance in a very efficient way. We further recast the problem of analyzing the topological structure of the solution space to that of solving two polynomial equations in three variables. This topological information provides an elegant way to efficiently find a global minimum distance solution for spatially coherent queries. Additionally, we extend this approach to a 3D case. We formulate the problem for the surface case using two polynomial equations in five variables. The effectiveness of our approach is demonstrated with several experimental results.

Symbolic computation of NURBS plays an important role in many areas of NURBS-based geometric computation and design. However, any nontrivial symbolic computation, especially when rational B-splines are involved, would typically result in B-splines with high degrees. In this paper we develop degree reduction strategies for NURBS symbolic computation on curves. The specific topics we consider include zero curvatures and critical curvatures of plane curves, various ruled surfaces related to space curves, and point/curve bisectors and curve/curve bisectors.

This paper introduces the rational forward difference operator for differential computation on a rational Bezier patch based on its control mesh. With this rational version of the forward difference operator, and by ignoring the appropriate dependent (on lower order derivatives) terms of various derivatives, the derivatives themselves have the same expressions as their polynomial counterparts; the curvature and torsion, and the first and second fundamental forms, all have very similar expressions as those equations from classical differential geometry. This new approach also allows straightforward generalization to higher dimensional rational Bezier patches, the special co-dimension 1 case of which is treated with the result of the first and second fundamental forms.

This paper describes a haptic rendering algorithm for arbitrary polygonal models using a six degree-of-freedom haptic interface. The algorithm supports activities such as virtual prototyping of complex polygonal models and adding haptic interaction to virtual environments. The underlying collision system computes local extrema in distance between the model controlled by the haptic device and the rest of the scene. The haptic rendering computes forces and torques on the moving model based on these local extrema. The system is demonstrated on models with tens of thousands of triangles and developed in an accessibility application for finding collision-free paths.

Decorating arbitrary meshes with Celtic knots requires polygonal meshes with regular connectivity and close to regular face geometry. Because these properties are often irregular, especially in scanned or reconstructed models, the Celtic knots produced may be erratic and undesirable. In this paper we remesh models based on planar tilings defined by the user. Such pattern-oriented surfaces allow us to decorate models with attractive Celtic knots in a consistent fashion and may be applicable to a large number of algorithms that are sensitive to mesh structure.

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.

Article Share on Spatialized normal come hierarchies Authors: David E. Johnson Univ. of Utah, Salt Lake City Univ. of Utah, Salt Lake CityView Profile , Elaine Cohen Univ. of Utah, Salt Lake City Univ. of Utah, Salt Lake CityView Profile Authors Info & Claims I3D '01: Proceedings of the 2001 symposium on Interactive 3D graphicsMarch 2001 Pages 129–134https://doi.org/10.1145/364338.364380Published:01 March 2001Publication History 27citation550DownloadsMetricsTotal Citations27Total Downloads550Last 12 Months13Last 6 weeks1 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 present an approach for automatically generating complete process plans, including fixturing and CNC code, from high level shape feature part descriptions. The demonstration system is targeted at a broadly useful class of machined prismatic parts which includes sculpted exterior profiles and features requiring four and five axis indexing for manufacture. The approach introduces a set of process plan templates which are schemas for a family of process plans embodying a variety of fixturing strategies. The knowledge built into the process plan templates can adapt existing part hole features to be used for fixturing, can modify the workpiece to enable fixturing, and can create custom fixturing components for stages of the process plan. The process plan template system automatically transforms a given part design into a complete process plan. The user can provide optional guidance for this transformation and also can edit the resulting process plan to further extend the usefulness of this approach through customization. Domain knowledge in the process plan then automatically generates CNC code for a target machining center. This research is implemented as an experimental subsystem within our Alpha 1 modeling and manufacturing testbed environment, and has been used to design and manufacture working components for outside client applications.

Previous interactive works have used springs, heuristics, and dynamics for surface placement applications. We present an analytical technique for kilohertz rate manipulation of CAD models with virtual surface and trimming constraints. The optimization approach allows best placement and sensitivity analysis for mechanical design objectives and parametric domain objectives. Such objectives are not readily incorporated into previous interactive methods. Force feedback is rendered to the user using previously developed haptics principles.

Minimum distance computations on complex geometry commonly employ hierarchies of bounding volumes that are pruned through establishment of upper and lower bounds. In this paper we describe a novel time coherence scheme which utilizes coherence on these bounds, rather than coherence derived from the geometry of the bounding volumes or from the geometry of the underlying model. This method is thus independent of the bounding volume and model representations. In tests, we find using this approach can more than double the speed of a noncoherent approach.

We present a solution to the general problem of characterizing shadows in scenes involving a uniform polygonal area emitter and a polygonal occluder in arbitrary position by manifesting shadow irradiance as a spline function.Studying generalized prism-like constructions generated by the emitter and the occluder in a fourdimensional (shadow) space reveals a simpler intrinsic structure of the shadow as compared to the more complicated 2D projection onto a receiver.A closed form expression for the spline shadow irradiance function is derived by twice applying Stokes' theorem to reduce an evaluation over a 4D domain to an explicit formula involving only 2D faces on the receiver, derived from the scene geometry.This leads to a straightforward computational algorithm and an interactive implementation.Moreover, this approach can be extended to scenes involving multiple emitters and occluders, as well as curved emitters, occluders, and receivers.Spline functions are constructed from these prism-like objects.We call them generalized polyhedral splines because they extend the classical polyhedral splines to include curved boundaries and a density function.The approach can be applied to more general problems such as some of those occurring in radiosity, and other related topics.

We present a method for painting texture maps directly onto trimmed NURBS models using a haptic interface. The haptic interface enables an artist to use a natural painting style while creating a texture. It avoids the traditional difficulty of mapping between the 2D texture space and the 3D model space by using parametric information available from our haptic tracing algorithm. The system maps user movement in 3D to movement in the 2D texture space and adaptively resizes the paintbrush in texture space to create a uniform stroke on the model.

A fast design variation technique for mechanical systems is presented. It is used to interactively optimize mechanical characteristics while “self‐assembling” or satisfying large systems of mechanical constraints. The high speed method is central to providing inverse dynamics force feedback in haptics and control applications. Performance advantages with the use of augmented coordinates for inverse dynamics of closed loop topologies are also noted. The interaction framework allows manipulation of complex assemblies while maintaining kinematically admissible configurations though linkage and joint limit constraints. Furthermore, design variables such as link length can be treated as free variables and optimized to meet design criteria such as assembly dexterity. Assemblies with flexible bodies fit naturally within this framework. Thus, the contribution of this paper is the advancement of techniques in augmented coordinates for the kinematic and force feedback interaction with virtual mechanical assembly design optimization at force control rates.

We present a framework for minimum distance computations that allows efficient solution of minimum distance queries on a variety of surface representations, including sculptured surfaces. The framework depends on geometric reasoning rather than numerical methods and can be implemented straightforwardly. We demonstrate performance that compares favorably to other polygonal methods and is faster than reported results for other methods on sculptured surfaces.

Phong-shaded 3D imagery does not provide geometric information of the same richness as human-drawn technical illustrations.A non-photorealistic lighting model is presented that attempts to narrow this gap.The model is based on practice in traditional technical illustration, where the lighting model uses both luminance and changes in hue to indicate surface orientation, reserving extreme lights and darks for edge lines and highlights.The lighting model allows shading to occur only in mid-tones so that edge lines and highlights remain visually prominent.In addition, we show how this lighting model is modified when portraying models of metal objects.These illustration methods give a clearer picture of shape, structure, and material composition than traditional computer graphics methods.

A new tracing algorithm is described that supports haptic rendering of NURBS surfaces without the use of any intermediate representation. By using this tracing algorithm in conjunction with algorithms for surface proximity testing and surface transitions, a complete haptic rendering system for sculptured models has been developed. The system links an advanced CAD modeling system with a Sarcos force-reflecting exo-skeleton arm. A method for measuring the quality of the tracking component of the haptic rendering separately from the haptic device and force computation is also described.

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

We present an interactive approach for helping designers describe, revise, analyze, and illustrate assemblies of mechanical parts within the context of a common data structure and set of assembly features. This paper describes an implementation used to test the validity of these ideas, which has been integrated into an existing spline-based geometric modeling system.

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.

Hand-sketching is a particularly attractive solution to providing an intuitive design interface for modeling. The goal is to reduce the data collected from the input strokes and to construct a curve that faithfully represents the sketched data. This paper presents a new approach to interactive realtime handsketching in two or three dimensions and is-based on the new approach to general spline datafitting presented in [10,8,9].The goal of our approach is to obtain approximating curves with reasonable accuracy at real-time interactive speeds, and at the same time significantly reduce in the number of coefficients for the curve representation over the original data representation. The approach taken here to obtain realtime interaction is to reduce the data incrementally using new local algorithms while the data is still being sketched.

Physically based modeling has recently become a subject of widespread interest. This paper defines a model of elastic and plastic B-spline surfaces which supports both animation and design operations, including the interference detection, within the "Eplastics"/Alpha_1 modeling environment. We develop "refinement" operations for spring and hinge B-spline models which are compatible with the physics and the mathematics of B-spline models, including refinement. It is also a step towards a more continuous physical representation of a physical model than the more standard discretized geometry point mass models. We present some interactive operations currently in real-time and some which could be real-time with further optimization and use of multiple processors on machines such as the SGI Iris 4D/240GTX. A movie is used to illustrate the results.

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.

Recently there has been a great deal of interest in the use of “tension” parameters to augment control mesh vertices as design handles for piecewise polynomials. A particular local cubic basis called B-splines, which has been termed a “generalization of B-splines, v has been proposed as an appropriate basis. These functions are defined only for floating knot sequences. This paper uses the known property of B-splines that with appropriate knot vectors span what are called here spaces of tensioned splines, and that particular combinations of them, called LT-splines, form bases for the spaces of tensioned splines. In addition, this paper shows that these new proposed bases have the variation diminishing property, the convex hull property, and straightforward knot insertion algorithms, and that both curves and individual basis functions can be easily computed. Sometimes it is desirable to interpolate points and also use these tension parameters, so interpolation methods using the LT-spline bases are presented. Finally, the above properties are established for uniform and nonuniform knot vectors, open and floating end conditions, and homogeneous and nonhomogeneous tension parameter pairs.

Stable and efficient algorithms for degree-raising of curves (or surfaces) represented as arbitrary B-splines are presented as a application of the solution to the theoretical problem of rewriting a curve written as a linear combination of m th order B-splines as a linear combination of ( m + 1)st order B-splines with a minimal number of knot insertions. This approach can be used to introduce additional degrees of freedom to a curve (or surface), a problem which naturally arises in certain circumstances in constructing mathematical models for computer-aided geometric design.

Vocoders based on linear models of the vocal tract such as LPC result in an inverse polynomial fit of the spectrum, and along with homomorphic vocoders require pitch estimation. Analysis/synthesis using B-spline basis functions is proposed in this preliminary paper. This is a local approximation scheme which permits a concentration of parameters in regions of greater importance and employs easily computed least square coefficients. It can be used with pitch based vocoders or as a standalone nonpitch based vocoder. An experimental system, not yet optimized using special properties of human speech, has been applied to samples of male speech, female speech, simultaneous speech with two speakers, and noisy speech. Empirical results on tape will be presented.