Abstract Texture mapping is an essential component for creating 3D models and is widely used in both the game and the movie industries. Creating texture maps has always been a complex task and existing methods carefully balance flexibility with ease of use. One difficulty in using texturing is the repeated placement of individual textures over larger areas. In this paper, we propose a method which uses decals to place images onto a model. Our method allows the decals to compete for space and to deform as they are being pushed by other decals. A spherical field function is used to determine the position and the size of each decal and the deformation applied to fit the decals. The decals may span multiple objects with heterogeneous representations. Our method does not require an explicit parametrization of the model. As such, varieties of patterns, including repeated patterns like rocks, tiles and scales can be mapped. We have implemented the method using the GPU where placement, size and orientation of thousands of decals are manipulated in real time.

This paper presents a geometric algorithm for the generation of uniform cubic B-spline curves interpolating a sequence of data points under tangent and curvature vectors constraints. To satisfy these constraints, knot insertion is used to generate additional control points which are progressively repositioned using corresponding geometric rules. Compared to existing schemes, our approach is capable of handling plane as well as space curves, has local control, and avoids the solution of the typical linear system. The effectiveness of the proposed algorithm is illustrated through several comparative examples. Applications of the method in NC machining and shape design are also outlined.

The ability to cut through meshes in real-time is an essential ingredient in a number of practical interactive simulations. Surgical simulation, cloth design, clay sculpting and many other related VR applications require the ability to introduce arbitrary discontinuities through models to separate, reposition, and reshape various pieces of the model as needed for the target application. In addition, in order to provide the necessary realism for these applications, model deformations must be computed from an underlying physically-based model--most commonly a continuum-based finite element model.

Abstract Given an n‐sided region bounded by a loop of n polylines, we present a general algorithm to fill such a region by a quad mesh suitable for a subdivision scheme. Typically, the approach consists of two phases: the topological phase and the geometrical phase. In the first part, the connectivity of the mesh is based on determining a partitioning of the region into rectangular subregions across which regular grid could be constructed. The geometrical phase generalizes discrete Coon's patches to position the vertices in the 3D space. The generated mesh could be taken as input to any quad‐based subdivision scheme, such as that of Catmull–Clark or Doo–Sabin to generate the corresponding limit surface. The goal of the algorithm is to generate smooth meshes with minimum number and less valence of extraordinary vertices deemed undesirable in such subdivision schemes.

Image segmentation is an important task in image analysis and processing. Many of the existing methods for segmenting a multi-component image (satellite or aerial) are very slow and require a priori knowledge of the image that could be difficult to obtain. Furthermore, the success of each of these methods depends on several factors, such as the characteristics of the acquired image, resolution limitations, intensity in-homogeneities and the percentage of imperfections induced by the process of image acquisition. Recently, fuzzy C-means (FCM) and Genetic Algorithms were separately used in segmenting multi-component images but neither of them had successfully addressed the above concerns. GA was enhanced using Hill-climbing, randomising, and modified mutation operators, leading to what is called hybrid dynamic genetic algorithm (HDGA). Coupling HDGA and FCM creates an unsupervised segmentation method which could successfully segment two types of multi-component images (Landsat ETM+, and IKONOS II). Comparison with the four different methods FCM, hybrid genetic algorithm (HGA), self-organizing-maps (SOM), and the combination of SOM and HGA (SOM-HGA) reveals that FCM-HDGA segmentation method gives robust and reliable results, and is more time efficient.

Image segmentation is an essential process for image analysis. Several methods were developed to segment multicomponent images, and the success of these methods depends on several factors including (1) the characteristics of the acquired image and (2) the percentage of imperfections in the process of image acquisition. The majority of these methods requirea prioriknowledge, which is difficult to obtain. Furthermore, they assume the existence of models that can estimate its parameters and fit to the given data. However, such a parametric approach is not robust, and its performance is severely affected by the correctness of the utilized parametric model. In this letter, a new multicomponent image segmentation method is developed using a nonparametric unsupervised artificial neural network called Kohonen's self-organizing map (SOM) and hybrid genetic algorithm (HGA). SOM is used to detect the main features that are present in the image; then, HGA is used to cluster the image into homogeneous regions without anya prioriknowledge. Experiments that are performed on different satellite images confirm the efficiency and robustness of the SOM-HGA method compared to the Iterative Self-Organizing DATA analysis technique (ISODATA).

The past decade witnessed rapid development of constraint satisfaction technologies, where algorithms are now able to cope with larger and harder problems. However, owing to the fact that constraints are inherently declarative, attention is quickly turning toward developing high-level programming languages within which such problems can be modeled and also solved. Along these lines, this paper presents DEPICT, the language. Its use is illustrated through modeling a number of benchmark examples. The paper continues with a description of a prototype system within which such models may be interpreted. The paper concludes with a description of a sample run of this interpreter showing how a problem modeled as such is typically solved.

This paper presents a solution to the problem of constructing Catmull-Clark subdivision surfaces interpolating given meshes of cubic B-spline curves. The solution is supplemented by an account of the continuity of the constructed surfaces at and around the extraordinary points of the corresponding meshes. This is conducted through an analysis of the corresponding subdivision matrix, which comes in parameterized form, thus adding a degree of freedom to the process. This degree of freedom gives room for manipulating the quality of the resulting surface without violating the initial interpolation constraints.

One of the major problems in the generation of skinning B-spline surfaces is the incompatibility of the cross-sectional curves. This occurs when the cross sections are defined by control polygons having different number of control devices. Traditionally, this incompatibility is overcome by knot insertion that makes all control polygons have equal number of vertices. The drawback of this solution is that it can very quickly lead to an explosion in the number of vertices of the control mesh defining the skinning surface. In this paper, we show that this problem can be rectified through the use of subdivision surfaces. We describe an approach to generate a skinning Catmull-Clark subdivision surface through incompatible cross-sections of cubic B-spline curves. The resulting surface has all the properties of subdivision surfaces while requiring a smaller number of control points than those obtained through the more conventional techniques.

Abstract Interpolating curves by subdivision surfaces is one of the major constraints that is partially addressed in the literature. So far, no more than two intersecting curves can be interpolated by a subdivision surface such as Doo‐Sabin or Catmull‐Clark surfaces. One approach that has been used in both of theses surfaces is the polygonal complex approach where a curve can be defined by a control mesh rather than a control polygon. Such a definition allows a curve to carry with it cross derivative information which can be naturally embodied in the mesh of a subdivision surface. This paper extends the use of this approach to interpolate an unlimited number of curves meeting at an extraordinary point on a subdivision surface. At that point, the curves can all meet with either C 0 or C 1 continuity, yet still have common tangent plane. A straight forward application is the generation of subdivision surfaces through 3‐regular meshes of curves for which an easy interface can be used.

This paper presents a generalization of non-uniform B-spline surfaces called T-splines. T-spline control grids permit T-junctions, so lines of control points need not traverse the entire control grid. T-splines support many valuable operations within a consistent framework, such as local refinement, and the merging of several B-spline surfaces that have different knot vectors into a single gap-free model. The paper focuses on T-splines of degree three, which are C 2 (in the absence of multiple knots). T-NURCCs (Non-Uniform Rational Catmull-Clark Surfaces with T-junctions) are a superset of both T-splines and Catmull-Clark surfaces. Thus, a modeling program for T-NURCCs can handle any NURBS or Catmull-Clark model as special cases. T-NURCCs enable true local refinement of a Catmull-Clark-type control grid: individual control points can be inserted only where they are needed to provide additional control, or to create a smoother tessellation, and such insertions do not alter the limit surface. T-NURCCs use stationary refinement rules and are C 2 except at extraordinary points and features.

One essential interpolation constraint on subdivision surfaces is curve interpolation. Subdivision surfaces through predefined meshes of curves can now be generated using either variations of existing subdivision schemes or (in our case) polygonal complexes. This paper goes one step further; given a sequence of cross sectional curves (c/sub i/), each defined by a uniform cubic B-spline control polygon (cp/sub i/), we present a technique for generating a lofted subdivision surface through these curves. The advantages of using polygonal complexes coupled with subdivision surfaces are that curves do not have to be compatible and that it is possible to locally control the cross curvature of a given cross section.

Given a polygonal mesh with a set of tagged control polygons, a subdivision surface that interpolates the B-spline curves of these control polygons can be obtained by constructing a set of polygonal complexes, each of which converges to one of the given curves. The construction process will geometrically and topologically disturb the initial and/or the subdivided polygonal meshes in the vicinity of the polygonal complexes. This may result in poorly shaped surfaces across the interpolated curves. Based on signal fairing, this paper describes a method to fair such a surface and paves the way to achieve further constraints such as interpolating curves with predefined tangent plane or cross curvature.

We present an algorithm for generating a piecewise G1 circular spline curve from an arbitrary given control polygon. For every corner, a circular biarc is generated with each piece being parameterized by its arc length. This is the first subdivision scheme that produces a piecewise biarc curve that can interpolate an arbitrary set of points. It is easily adopted in a recursive subdivision surface scheme to generate surfaces with circular boundaries with pieces parameterized by arc length, a property not previously available. As an application, a modified version of Doo–Sabin subdivision algorithm is outlined making it possible to blend a subdivision surface with other surfaces having circular boundaries such as cylinders.

Given a polyhedral network P/sub 0/ defining a subdivision surface S and an arbitrary mesh of tagged control polygons (cp/sub i/)/sub 1⩽i⩽n/ on P/sub 0/, this paper describes an approach to force the limit surface S to interpolate the B-spline curves of (cp/sub i/). For each control polygon cp/sub i/, we construct a polygonal complex whose mid-polygon is cp/sub i/ or its first subdivided one. A polygonal complex is a sequence of panels such that every two adjacent panels share exactly one edge and the mid-points of these edges make the mid-polygon of the complex. Since the complexes themselves are embodied in the original polyhedron or its first subdivided the limit surface will interpolate the limit curves of these complexes.

Interpolation conditions on recursive subdivision surfaces provide more powerful techniques to manipulate such surfaces. Recently, such conditions were extended to handle interpolation of pre-defined curves by a subdivision surface. Given a curve C/sub i/ defined by a control polygon cp/sub 0/, this consists of constructing a strip complex P/sub i/ as part of the defining polyhedral network M/sub 0/ or its first subdivision M/sub 1/. By repeated subdivision, M/sub i/ converges to a limit surface S which interpolates the curve C/sub i/. We describe an algorithm for constructing strip complexes that interpolate intersecting curves at the boundary of a surface. The algorithm is an important step towards solving the problem of interpolating arbitrary intersecting meshes of curves by subdivision surfaces.

The volume of a solid enclosed by a recursive subdivision surface can be approximated based on the closed‐form representation of regular parts of the subdivision surface and a tight estimate of the local convex hull near extraordinary points. The approach presented is efficient, i.e. non‐exponential, and robust in that it yields rapidly contracting error bounding boxes. An extension to measuring higher‐order moments is sketched.

One of the central issues in computer-aided geometric design is the representation of free-form surfaces which are needed for many purposes in engineering and science. Several limitations are imposed on most available surface systems: the rectangularity of the network describing a surface and the manipulation of surfaces without regard to the volume enclosed are examples. Polyhedral subdivision methods suggest themselves as a solution to these problems. Their use, however, is not widespread for several reasons such as the lack of boundary control, and interpolation and interrogation capabilities. In this paper the original work on subdivision methods is extended to overcome these problems. Two methods are described, one for controlling the boundary curves of such surfaces, and another for interpolating points on irregular networks. A general surface/surface intersection algorithm is also provided: seven decisions need to be made in order to specify a particular implementation. The algorithm is also suitable for intersecting other classes of surfaces amongst which are the popular Bézier and B-spline surfaces.