トポロジ分割

トポロジ分割はメッシュトポロジを指定されたサブディビジョンルールに従って 分割し、新しいトポロジ（頂点・エッジ・面）を作る処理です。この処理は純粋に トポロジのみに依存しており、特定の頂点データ（座標など）とは無関係に行います。

トポロジ分割は均一にも適当的にも行う事ができます。適応型分割の場合は 非正則な特徴は自動的に分類されて処理されます。 （feature adaptive subdivision を参照してください）

Far のトポロジクラスは Vtr が担う分割機能の公開インタフェースとして使えます。

トポロジ分割に関連する Far の主要なクラスは:

Primvar Refinement

頂点データ (Primvar) 分割

頂点データ分割は指定されたサブディビジョン規則に従った重みを用いて頂点データ （座標、色、法線、テクスチャ座標など）を計算する処理です。頂点データ分割を トポロジ分割とは別に行うことには様々なメリットがありますが、同じトポロジ分割から アニメーションする複数の頂点データを計算することも一つの利点です。

Far はトポロジ分割頂点における頂点データ、またリミットサーフェス上の任意の 場所での頂点データの計算をサポートしています。

Far の中の頂点データ分割に関連する主要なクラスは：

Patch Arrays

The patch table is a collection of control vertex indices. Meshes are decomposed into a collection of patches, which can be of different types. Each type has different requirements for the internal organization of its control-vertices. A PatchArray contains a sequence of multiple patches that share a common set of attributes.

While all patches in a PatchArray will have the same type, each patch in the array is associated with a distinct PatchParam which specifies additional information about the individual patch.

Each PatchArray contains a patch Descriptor that provides the fundamental description of the patches in the array.

The PatchArray ArrayRange provides the indices necessary to track the records of individual patches in the table.

Patch Types

The following are the different patch types that can be represented in the PatchTable:

The type of a patch dictates the number of control vertices expected in the table as well as the method used to evaluate values.

Patch Parameterization

Each patch represents a specific portion of the parametric space of the coarse topological face identified by the PatchParam FaceId. As topological refinement progresses through successive levels, each resulting patch corresponds to a smaller and smaller subdomain of the face. The PatchParam UV origin describes the mapping from the uv domain of the patch to the uv subdomain of the topological face. We encode this uv origin using log2 integer values for compactness and efficiency.

It is important to note that this uv parameterization is the intrinsic parameterization within a given patch or coarse face and is distinct from any client specified face-varying channel data.

Patches which result from irregular coarse faces (non-quad faces in the Catmark scheme, or non-trianglular faces in the Loop scheme) are offset by the one additional level needed to "quadrangulate" or "triangulate" the irregular face.

A patch along an interpolated boundary edge is supported by an incomplete sets of control vertices. For consistency, patches in the PatchTable always have a full set of control vertex indices and the PatchParam Boundary bitmask identifies which control vertices are incomplete (the incomplete control vertex indices are assigned values which duplicate the first valid index). Each bit in the boundary bitmask corresponds to one edge of the patch starting from the edge from the first vertex and continuing around the patch. With feature adaptive refinement, regular B-spline basis patches along interpolated boundaries will fall into one of the eight cases (four boundary and four corner) illustrated below:

Transition edges occur during feature adaptive refinement where a patch at one level of refinement is adjacent to pairs of patches at the next level of refinement. These T-junctions do not pose a problem when evaluating primvar data on patches, but they must be taken into consideration when tessellating patches (e.g. while drawing) in order to avoid cracks. The PatchParam Transition bitmask identifies the transition edges of a patch. Each bit in the bitmask corresponds to one edge of the patch just like the encoding of boundary edges.

After refining an arbitrary mesh, any of the 16 possible transition edge configurations might occur. The method of handling transition edges is delegated to patch drawing code.

Single-Crease Patches

Using single-crease patches allows a mesh with creases to be represented with many fewer patches than would be needed otherwise. A single-crease patch is a variation of a regular BSpline patch with one additional crease sharpness parameter.

Local Points

The control vertices represented by a PatchTable are primarily refined points, i.e. points which result from applying the subdivision scheme uniformly or adaptively to the points of the coarse mesh. However, the final patches generated from irregular faces, e.g. patches incident on an extraordinary vertex might have a representation which requires additional local points.

Legacy Gregory Patches

Using Gregory patches to approximate the surface at the final patches generated from irregular faces is an alternative representation which does not require any additional local points to be computed. Instead, when Legacy Gregory patches are used, the PatchTable must also have an alternative representation of the mesh topology encoded as a vertex valence table and a quad offsets table.

Advantages

Stencils are used to factorize the interpolation calculations that subdivision schema apply to vertices of smooth surfaces. If the topology being subdivided remains constant, factorizing the subdivision weights into stencils during a pre-compute pass yields substantial amortizations at run-time when re-posing the control cage.

Factorizing the subdivision weights also allows to express each subdivided vertex as a weighted sum of vertices from the control cage. This step effectively removes any data inter-dependency between subdivided vertices : the computations of subdivision interpolation can be applied to each vertex in parallel without any barriers or constraint. The Osd classes leverage these properties by exploiting CPU and GPU parallelism.

Principles

Iterative subdivision algorithms converge towards the limit surface by successively refining the vertices of the coarse control cage. Each successive iteration interpolates the new vertices by applying polynomial weights to a basis of supporting vertices.

The interpolation calculations for any given vertex can be broken down into sequences of multiply-add operations applied to the supporting vertices. Stencil table encodes a factorization of these weighted sums : each stencils is created by combining the list of control vertices from the 1-ring.

With iterative subdivision, each refinement step is dependent upon the previous subdivision step being completed, and a substantial number of steps may be required in order approximate the limit : each subdivision step incurs an O(4ⁿ) growing amount of computations.

Instead, once the weights of the contributing coarse control vertices for a given refined vertex have been factorized, it is possible to apply the stencil and directly obtain the interpolated vertex data without having to process the data for the intermediate refinement levels.

Cascading Stencils

Client-code can control the amount of factorization of the stencils : the tables can be generated with contributions all the way from a basis of coarse vertices, or reduced only to contributions from vertices from the previous level of refinement.

The latter mode allows client-code to access and insert modifications to the vertex data at set refinement levels (see hierarchical vertex edits). Once the edits have been applied by the client-code, another set of stencils can be used to smoothe the vertex data to a higher level of refinement.

See implementation details, see the Far cascading stencil tutorial

Limit Stencils

Stencil tables can be trivially extended from discrete subdivided vertices to arbitrary locations on the limit surface. Aside from extraordinary points, every location on the limit surface can be expressed as a closed-form weighted average of a set of coarse control vertices from the 1-ring surrounding the face.

The weight accumulation process is similar : the control cage is adaptively subdivided around extraordinary locations. A stencil is then generated for each limit location simply by factorizing the bi-cubic Bspline patch weights over those of the contributing basis of control-vertices.

The use of bi-cubic patches also allows the accumulation of analytical derivatives, so limit stencils carry a set of weights for tangent vectors.

Once the stencil table has been generated, limit stencils are the most direct and efficient method of evaluation of specific locations on the limit of a subdivision surface, starting from the coarse vertices of the control cage.

Also: just as discrete stencils, limit stencils that are factorized from coarse control vertices do not have inter-dependencies and can be evaluated in parallel.

For implementation details, see the glStencilViewer code example.

Sample Location On Extraordinary Faces

Each stencil is associated with a singular parametric location on the coarse mesh. The parametric location is defined as face location and local [0.0 - 1.0] (u,v) triplet:

In the case of face that are not quads, a parametric sub-face quadrant needs to be identified. This can be done either explicitly or implicitly by using the unique ptex face indices for instance.

Code example

When the control vertices (controlPoints) move in space, the limit locations can be very efficiently recomputed simply by applying the blending weights to the series of coarse control vertices:

class StencilType {
public:

    void Clear() {
        memset( &x, 0, sizeof(StencilType));
    }

    void AddWithWeight( StencilType const & cv, float weight  ) {
        x += cv.x * weight;
        y += cv.y * weight;
        z += cv.z * weight;
    }

    float x,y,z;
};

std::vector<StencilType> controlPoints,
                         points,
                         utan,
                         vtan;

// Update points by applying stencils
controlStencils.UpdateValues<StencilType>( &controlPoints[0], &points[0] );

// Update tangents by applying derivative stencils
controlStencils.UpdateDerivs<StencilType>( &controlPoints[0], &utan[0], &vtan[0] );