Handling Cracks In Adaptive Subdivision Surfaces Method Engineering Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

ABSTRACT

Subdivision surfaces are popular surface representation for the polygonal meshes modeling. Several schemes had been proposed in this area to provide a set of rules to produce smooth surfaces refinement from coarse meshes. Computing and rendering all the vertices are too expensive in terms of memory consumption and runtime while the subdivision process converges to a smooth shape. It will lead to heavy computational loads. However, subdivisions of the entire meshes are not necessary or required. Adaptive subdivision is one of the techniques that gain high interest from researchers to subdivide necessary areas. Although subdivision occurs in the selected areas, the quality of produced surfaces can be preserved similar to regular subdivision. The idea of adaptive subdivision is to handle connectivity inconsistencies that arise when subdividing a subset of faces. Nevertheless, adaptive subdivision suffers with two weaknesses which are the difficulties to select necessary areas needed to be subdivided and to remove cracks created from the subdivision depth difference between the selected and unselected areas. Cracks must be removed because they create artifacts in editing, rendering, and processing of the mesh. This research will be focusing on handling crack issues occurred in adaptive subdivision for triangular meshes. An improvement method of adaptive subdivision will be made to tackle the issues and at the same time able to produce smooth transition from the coarse surface to fine meshes.

Categories and Subject Descriptors

I.3.5 [Computer Graphics]: Computational Geometry and Object

Modeling - surface and object representations.

General Terms

Algorithms, performance, theory

Keywords

Subdivision surfaces, adaptive subdivision, cracks.

INTRODUCTION

The concept of subdivision surfaces is to converged coarse polygonal mesh to become smooth surfaces. The purpose of generating smooth surfaces is to produce a realistic appearance in virtual environment. Subdivision surfaces in not a new application since this approach had already been used in many developments of animation packages and computer game industries. Moreover, it had been used in 3D modeling, games development, and animation packages [1-3]. The examples are Geri's Game, Toy Story and Bug's Life. 3D Light Wave modelling and animation system of Newtek also use subdivision with the same purpose.

Figure 1: Example model of subdivision surfaces, Female head (ear), Ken Cope 2002 [9]

MOTIVATION

Subdivision schemes were applied to the whole coarse meshes and refined globally at every level of subdivision. This can lead to a huge computational load at higher levels of subdivision. Furthermore, after a few subdivision steps, the generated subdivision surfaces were acceptably smooth to represent a fine model. In order to overcome this situation, there is no need for a model to be subdivided to the whole areas in order to obtain smooth surfaces, only some areas where curvatures changes significantly need to be subdivided to make them smoother. Moreover, subdivision of a flat surface still produces a flat surface. It is also important to reduce the unnecessary subdivision to save the render time and the storage space, since the size of mesh otherwise grows exponentially with the level of subdivision. To apply this concept, adaptive subdivision is the method that refines a subset of the surfaces.

The goal of adaptive subdivision is to produce a limited surface that can preserve the similarity as uniform subdivision and all vertices within the selected subdivision areas must have the same connectivity when the entire mesh is subdivided [11].

The concept of adaptive subdivision is simple, connectivity and geometrical inconsistencies that arise when a subset of the faces are subdivided were focused. Although adaptive subdivision was one of the simplification and interesting feature for subdivision surfaces, it has two drawbacks which are to define a selection area to be subdivided while preventing unnecessary locations subdivision and to avoid cracks that are caused by a difference subdivision depth of neighboring faces[12]. The aim of this research is to enhance the method of cracks handling once adaptive subdivision had been implemented to represent 3D modelling in generating smooth surfaces. In order to achieve the targeted goal, these are several objectives that need to be conducted:

To study subdivision scheme and crack issues in adaptive subdivision.

To propose an enhancement technique to handle cracks.

To produce a prototype of an enhancement method in adaptive subdivision.

LITERATURE REVIEW

Previously, NURBS techniques were used widely for modelling. Nevertheless, NURBS had some disadvantages and researchers start looking for a more suitable techniques to overcome the weaknesses faced by NURBS. One of NURBS 's weaknesses are costly surface modification in the techniques. Nowadays, subdivison surfaces were increasingly popular and slowly replacing traditional modelling such as NURBS specifically and surface modeling application. It converges smooth surfaces from a coarse polygonal mesh and can be applied at arbitrary meshes. It was controlled locally and the continuity can be controlled over the surface.

Subdivision surfaces does not require a renovation on surface hence does not involve cost for maintenance. Smoothness of subdivision surface can be maintained because surface smoothness were dependent to subdivision algorithm used.. Recently, many subdivision schemes have been developed including Catmull Clark [4], Doo Sabin [5], Loop [6], Butterfly [7] and Kobbelt [8].

3.1 Subdivision Properties

There are many types of subdivision schemes, with varying properties [1]. Some of the properties are:

3.1.1 Mesh type

Mesh type describe a shape of face made of either triangles or quadrilateral. A triangular scheme operates on triangular control mesh, and a quadrilateral scheme operates on quadrilateral mesh.

3.1.2 Smoothness

Smoothness and continuity refer to the degrees of continuity or smoothness of the limit surface. Schemes are referred to as having Cn continuity, where n determines how many derivatives are continuous [13].

3.1.3 Interpolation and approximation

Interpolating schemes maintain the control points at each level of subdivision. Approximating schemes alter the control points through the subdivision process.

3.1.4 Uniformity

Subdivision schemes are usually stationary in the sense that they use the same subdivision rules at all levels of subdivision. Similarly most subdivision schemes are uniform where uniform means that the same subdivision rules are applied on all areas of the control mesh.

3.1.5 Split

Some schemes work by replacing faces with more faces (face split); others work by replacing vertices with new sets of vertices (vertex split). A few more work by replacing the entire previous mesh, making a "new" mesh.

3.2 Subdivision scheme

3.2.1 Catmull Clark

This scheme was introduced by Edwin Catmull and Jim Clark in 1978. The Catmull Clark is a quadrilateral mesh, approximating scheme and have C2 continuity. At the extraordinary vertices the surface is C1 continuous. The regular parts of the subdivision surface are tensor products and cubic B-splines[4].

ctml.bmp

Figure 2: Subdivision masks for Catmull-Clark scheme [4]

For extraordinary vertices,

β = and γ =

(1)

3.2.2 Doo Sabin

The second subdivision scheme was developed by Donald Doo and Malcom Sabin who successfully extended Chaikin's corner-cutting method for curves to surfaces in 1978. The Doo Sabin scheme is a quadrilateral mesh, approximating scheme and has C1 continuity. Its regular parts are tensor product of quadratic B-splines. At the extraordinary vertices the surface is C1 continuous [5].

ds.bmp

Figure 3: Subdivision masks for Doo-Sabin scheme [3]

α0 = αi =

for i = 1…k-1

(2)

3.2.3 Loop

The Loop scheme is an approximating face split scheme for triangular mesh proposed by Charles Loop in 1987 [6]. The scheme is based on three-directional box spline, which produces C2-continuous surface over regular meshes. A regular mesh is a mesh which has no extraordinary vertices. The extraordinary vertices are those number of adjacent vertices (valence) is not six, while ones with a valence of six are called regular. The Loop scheme produces surfaces that are C2-continuous everywhere except at extraordinary vertices, where they are C1- continuous.

In the Loop scheme, the masks for smooth even and odd vertices are shown in Figure 1.

Figure 4: Masks of Loop subdivision (a) edge mask (b) vertex mask [1].

(3)

3.2.4 Butterfly

The Butterfly scheme is a triangular mesh and interpolating scheme proposed by Dyn, Gregory and Levin in 1990. It is based on the univariate 4-point scheme and gives C1 continuous surfaces in regular meshes. The original scheme has C0 continuity at the extraordinary vertices, while the Modified Butterfly scheme has C1 continuity everywhere [7].

bfly.bmpbfly1.bmp

Figure 5: Subdivision masks for Butterfly scheme [7]

si = k >5

s0 = , s1,2 = - k=3

s0 = , s2 = -, s1,3 = 0 k=4

(4)

3.2.5 Kobbelt

This scheme has been developed by Kobbelt in 2000 and handles arbitrary triangular mesh. It is C2 continuous everywhere except at extraordinary vertices where it is C1 continuous and it offers a natural adaptive refinement when required. This scheme was introduced an interpolating subdivision scheme for quadrilateral control nets which generalizes the tensor-product 4-point scheme and has special subdivision rules near the boundaries [8].

kb.bmp

kb2.bmp

Figure 6: Subdivision masks for Kobbelt scheme [1]

Table 1: Comparison between subdivision schemes

Scheme

Authors

Properties

Doo-Sabin

Donald Doo

Malcom Sabin

(1978)

C1

Interpolation

Quadrilateral

Catmull-Clark

Edwin Catmull

Jim Clark

(1979)

C2

Approximation

Quadrilateral

Loop

Charles Loop

(1987)

C2

Approximation

Triangular

Butterfly

Dyn

Gregory

Levin

(1990)

C1

Interpolation

Triangular

Kobbelt

Leif Kobbelt

(1996)

C1

Interpolation

Quadrilateral

3.3 Adaptive Subdivision

To visualize subdivision surfaces, the meshes were subdivided until it reaches a good approximation of the limit surface. Subdividing the entire mesh increase the number of faces exponentially. To reduce the complexity of a model in a real-time application, it is computed by subdividing the meshes adaptively. Adaptive subdivision produced a better visualization surfaces at a lower cost.

The objective of adaptive subdivision is to subdivide a mesh that produces smooth surfaces and yields the same visual quality as a uniformly subdivided mesh while using as few facets in the approximation as possible. A better approach to achieve the same result is to use local refinement procedure which can be applied adaptively to generate more details in needed areas.

Although adaptive subdivision are some of simplification and interest feature for subdivision surfaces, but it has two drawbacks which is to define a selection area to be subdivided while prevent unnecessary locations and to avoid cracks that are caused by a difference subdivision depth of neighboring faces These cracks prevent some further processing of the mesh and high quality rendering [14].

Figure 7: Comparison of (a) coarse model, (b) adaptive subdivision, and (c) regular subdivision [14].

3.3.1 Selection Criteria

In adaptive subdivision, the faces that need to be subdivided must be selected. This selection criteria is either determined by the application or is specified directly by the user. In modeling applications, users may need control over the level of detail of the model and want to emphasize part of a scene by increasing the detail of that area. Adding features to the mesh generally requires an increase in the level of detail where the features are being added. In these cases, the user selects areas of the mesh, and then they subdivided.

Several criteria determined by application had been proposed. Higher curvature areas of the mesh require more refinement than flat areas. Generally, high curvature areas contain more details which means need more subdivision applied. Dihedral angle [12] measured the angle between the normals of adjacent faces and can be computed efficiently to approximate surface curvature but is not as accurate as Gaussian curvature [15, 16]. Degree of Interest (DoI) function one of the selection criterion which may or may not be subdivide the areas based on the geometric properties of the meshes by comparing the angle between normal vectors of adjacent faces to a certain threshold value [17].

Figure 8: Shows adaptive Loop subdivision of a user defined area [14].

3.3.2 Handling Crack

During a subdivision step, if a face is going to be subdivided but its neighboring face is not going to be subdivided, a crack will be created, as shown below:

T-vertices

Figure 9: Example of creating of crack [14].

Crack or called as T-vertices occurred in adaptive subdivision. If the cracks are not processed properly, the subdivision may fail and produced some artifacts. The resulting cracks must be filled so that the surface can be further subdivided or edited. Several methods for handling cracks solution have been proposed:

3.3.2.1 Simple adaptive

These cracks are being created on the edges shared by faces at different subdivision levels which means between subdivided and unsubdivided faces. The neighborhood of the vertices is incomplete and when they are repositioned a crack is created. Amresh, Farin and Razdan propose a simple triangulation method that splits the neighboring faces into two, three or four faces depending on the number of odd vertices[12]. For each odd vertex, a bisection of the face with lower subdivision depth removes the crack. They call to this odd vertex a T-vertex. The opposite vertex that the T-vertex connects to is an O-vertex. Simple triangulation method removes cracks efficiently, but it has some undesired side-effects. First, it changes the connectivity and valence of odd vertices. This not only alters the limit subdivision surface, but also reduces its smoothness. Secondly, O-vertices have a different subdivision depth than the even vertices of the selected area. Therefore, the even vertices are not repositioned properly if the selected area is subdivided again. Finally, ignoring the irregular connectivity of T-vertex, repeated subdivision and simple triangulation of the selected area produces high valence O-vertices. High valence vertices lead to long faces which create ripple effects on the subdivision surface [14].

O-vertex

T-vertex

Figure 10: A simple triangulation [14]

3.3.2.2 Red-green triangulation

Another method of removing cracks by inserting edges into the mesh is the red-green triangulation method of Bank, Sherman and Weiser [18]. When better approximations are required, the mesh is refined by splitting each edge to half and connecting the new vertices. The red-green algorithm is as follows. Faces with one crack are bisected (green triangulation), and faces with more than one crack per edge are split into four (red triangulation). In other words, T-vertices, O-vertices, and the edges connecting them are temporary. Therefore, the connectivity of the selected region is unaffected. In addition, high valence extraordinary vertices are avoided. The consequence of red triangulations is that the subdivision depth difference of triangles incident to an edge is never larger than one. Therefore, the produced mesh is balanced, but these properties are not sufficient in the context of adaptive subdivision. Example in Loop scheme, the new position of even vertices is computed as a weighted average of its neighbors, and all these vertices must be at the same subdivision depth. The even vertices have neighbors from different subdivision levels in red-green triangulation.

3.3.2.3 Restricted mesh

To avoid any changes in the adaptive subdivision surface, odd and even vertices must be at the same subdivision depth as their neighbors. Zorin, Schröder and Sweldens call a mesh that satisfies the criteria as restricted mesh. To obtain a restricted mesh, faces are constructed so vertices of the selected area and their neighbors have the same subdivision depth. While T-vertices are removed from the subdivision area, even vertices have neighboring vertices from different subdivision depths. A hierarchical data structure is used for reconstruction of faces at different subdivision depths [19].

3.3.2.4 Incremental Adaptive Subdivision

Incremental adaptive subdivision has been proposed by Hamed Reza Pakdel and Faramarz Samavati. In particular, incremental subdivision is fast and does not require a complicated data structure. It is also intuitive and simple to implement. This algorithm expand the selected area and removes cracks outside that so they no longer affect the selection region of the mesh and resulting surfaces change gradually in transition from coarse to fine mesh. The properties of the algorithm make it suitable for modeling applications, and the produced surfaces can be used in high quality renderings and animations [14, 20, 21].

DISCUSSION AND SUGGESTED WORK

An enhancement method of adaptive subdivision will be proposed by tackling the two issues arise which is on selection criteria and handling cracks. Many methods have been proposed in making this selection area such as dihedral angle, distance error, automated segmentation and Gaussian curvature. To make a selection which can accurately find areas that are not flat or high curvature in meshes and can be computed efficiently, an enhancement method that can be proposed in our adaptive subdivision is by using Loop scheme. In this research design, adaptive subdivision uses Face Flatness method to define a local rule to determine whether the local area needs to be subdivided or not. Although the definition of Face Flatness is a little more complicated than dihedral angle, it takes into account the properties of 1-ring neighborhood of a vertex and dihedral angle just considers two triangles sharing an edge [16].

Various methods had been used to handle cracks problem such as red-green triangulation, restricted mesh method and so on. Mostly these prior methods used efficiently but it have some side effects.

Incremental adaptive subdivision capable to handle cracks in adaptive subdivision surfaces with consistent connectivity, consistent geometry, and gradually change of resolution throughout the surface. It is also intuitive and simple to implement. The properties of the algorithm make it suitable for modeling applications, and the produced surfaces can be used in high quality renderings and animations [21].

CONCLUSION Selection criteria had to be carefully observed in order to avoid unnecessary areas subdivided. It should be projecting the suitable mesh refinements based on the properties of its neighboring faces. To overcome this issue, several methods had been proposed to determine if the face needs to be subdivided or not. The planar area in subdivision surfaces had to be analyzed and hoping to select criteria which can accurately find areas that are not flat or with high curvatures in the meshes and can be computed efficiently.

Therefore, removing cracks by adding edge creates a number of extraordinary vertices that are unavoidable in adaptive subdivision algorithm. Extraordinary vertices affect the shape of the limit surfaces and reduce its smoothness.

Selection criteria and the way to fix a crack must be balanced to implement adaptive method that will be avoiding some artifacts and produce a better result of smooth surfaces.

ACKNOWLEDGEMENT

This work was supported by Collision Detection Research Group (CDRG) at Department of Computer Graphics and Multimedia, Faculty of Computer Science and Information System, Universiti Teknologi Malaysia. Special thanks to e-ScienceFund grant for providing financial support of this research.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.