Despite the growing interest in subdivision surfaces within the computer graphics and geometric processing communities, subdivision approaches have been receiving much less attention in solid modeling. This paper presents a powerful new framework for a subdivision scheme that is defined over a simplicial complex in any $n$-D space. We first present a series of definitions to facilitate topological inquiries during the subdivision process. The scheme is derived from the double $(k+1)$-directional box splines over $k$-simplicial domains. Thus, it guarantees a certain level of smoothness in the limit on a regular mesh. The subdivision rules are modified by spatial averaging to guarantee $C^1$ smoothness near extraordinary cases. Within a single framework, we combine the subdivision rules that can produce 1-, 2-, and 3-manifold in arbitrary $n$-D space. Possible solutions for non-manifold regions between the manifolds with different dimensions are suggested as a form of selective subdivision rules according to user preference. We briefly describe the subdivision matrix analysis to ensure a reasonable smoothness across extraordinary topologies, and empirical results support our assumption. In addition, through modifications, we show that the scheme can easily represent objects with singularities, such as cusps, creases, or corners. We further develop local adaptive refinement rules that can achieve level-of-detail control for hierarchical modeling. Our implementation is based on the topological properties of a simplicial domain. Therefore, it is flexible and extendable. We also develop a solid modeling system founded on our theoretical framework to show potential benefits of our work in industrial design, geometric processing, and other applications.

This paper presents a new, volumetric subdivision scheme for interpolation of arbitrary hexahedral meshes. To date, nearly every existing volumetric subdivision scheme is approximating i.e., with each application of the subdivision algorithm, the geometry shrinks away from its control mesh. Often, an approximating algorithm is undesirable and inappropriate, producing unsatisfactory results for certain applications in solid modeling and engineering design (\eg, finite element meshing). We address this lack of smooth, interpolatory subdivision algorithms by devising a new scheme founded upon the concept of tri-cubic Lagrange interpolating polynomials. We show that our algorithm is a natural generalization of the Butterfly subdivision surface scheme to a tri-variate, volumetric setting.

Subdivision has gained popularity in computer graphics and shape modeling during the past two decades, yet volumetric subdivision has received much less attention. In this paper, we develop a new subdivision scheme which can interpolate all of the initial control points in 3D and generate a continuous volume in the limit. We devise a set of solid subdivision rules to facilitate a simple subdivision procedure. The conversion between the subdivided mesh and a simplicial complex is straightforward and effective, which can be directly utilized in solid meshing, finite element simulation, and other numerical processes. In principle, our solid subdivision process is a combination of simple linear interpolations in 3D. Affine operations of neighboring control points produce new control points in the next level, yet inherit the original control points and achieve the interpolatory effect. A parameter is offered to control the tension between control points. The interpolatory property of our solid subdivision offers many benefits which are desirable in many design applications and physics simulations, including intuitive manipulation on control points and ease of constraint enforcement in numerical procedures. We outline a proof that can guarantee the convergence and $C^1$ continuity of our volumetric subdivision and limit volumes in regular cases. In addition to solid subdivision, we derive special rules to generate $C^1$ surfaces as B-reps and to model shapes of non-manifold topology. Several examples demonstrate the ability of our subdivision to handle complex manifolds easily. Numerical experiments and future research suggestions for extraordinary cases are also presented.

During the past twenty years, much research has been undertaken to study surface representations based on B-splines and box splines. In contrast, volumetric splines have received much less attention as an effective and powerful solid modeling tool. In this paper, we propose a novel solid subdivision scheme based on tri-variate box splines over tetrahedral tessellations in 3D. A new data structure is devised to facilitate the straightforward implementation of our simple, yet powerful solid subdivision scheme. The subdivision hierarchy can be easily constructed by calculating new vertex, edge, and cell points at each level as affine combinations of neighboring control points at the previous level. The masks for our new solid subdivision approach are uniquely obtained from tri-variate box splines, thereby ensuring high-order continuity. Because of rapid convergence rate, we acquire a high fidelity model after only a few levels of subdivision. Through the use of special rules over boundary cells, the B-rep of our subdivision solid reduces to a subdivision surface. To further demonstrate the modeling potential of our subdivision solid, we conduct several solid modeling experiments including free-form deformation. We hope to demonstrate that our box-spline subdivision solid (based on tetrahedral geometry) advances the current state-of-the-art in solid modeling in the following aspects: (1) unifying CSG, B-rep, and cell decomposition within a popular subdivision framework; (2) overcoming the shortfalls of tensor-product spline models; (3) generalizing both subdivision surfaces and free-form spline surfaces to a solid representation of arbitrary topology; and (4) taking advantage of triangle-driven, accelerated graphics hardware.

Reconstruction of missing or damaged portions of images is an ancient practice used extensively in artwork restoration. Recently, a few digital inpainting models based on the use of partial differential equations have been proposed. Unfortunately, these algorithms are computationally expensive, usually taking a few minutes to restore small portions of an image, which makes them inappropriate for interactive applications. We discuss the causes of inefficiency of these algorithms and present asimple inpainting model that is two to three orders of magnitude faster, while producing results comparable the ones obtained with current methods.

In this survey paper, we discuss subdivision geometry, subdivision schemes, its analysis and applications, especially from the view of solid modeling. Subdivision technique has been widely accepted in computer graphics and geometric design applications. However, it has been largely ignored in solid modeling. The first few sections are devoted to the history of subdivision modeling and the review of existing subdivision schemes in detail. We also briefly review other solid modeling techniques. Next, we discuss the current mathematical technique to analyze subdivision schemes on both regular and extraordinary topologies. We provide examples of analysis on the schemes in prior sections. We discuss problems involving solid scheme analysis and suggest possible solutions. In addition, we review prior work using subdivision technique in various applications. The latter part of the paper devote to our novel subdivision solid schemes, ongoing research topics, and new ideas. We demonstrate the potential of subdivision solids by a variety of examples. Attractive features of subdivision solids are compared and addressed. We conclude the paper with the summary and the expectation for future of subdivision technique in solid modeling.