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.

This paper reports a generic solution to the problem of constructing Catmull-Clark subdivision surfaces to interpolate arbitrarily intersecting meshes of curves, which is less constrained than already published solutions following this approach.

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.

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.

This paper reports a case study in applying constraint satisfaction techniques to university and school timetabling. It involves the construction of a substantial, carefully specified, fully tested and fully operational system. The software engineering aspect of constraint satisfaction is emphasized. Constraint satisfaction problems are expressed in a language more familiar to the formal software engineering community. This brings constraint satisfaction one step closer to formal specification, program verification and transformation; issues extensively studied in software engineering. In problem formulation, explicit domain constraints and heuristic information are made explicit. Moreover, the user's needs are considered more closely; for instance, when the program fails to find a solution, useful indications are produced to help in relaxation or reformulation of the problem.