tessellation.txt

// Copyright (c) 2015-2016 The Khronos Group Inc.
// Copyright notice at https://www.khronos.org/registry/speccopyright.html

[[tessellation]]
= Tessellation

Tessellation involves three pipeline stages. First, a
<<shaders-tessellation-control,tessellation control shader>> transforms
control points of a patch and can: produce per-patch data. Second, a
fixed-function tessellator generates multiple primitives corresponding to a
tessellation of the patch in (u,v) or (u,v,w) parameter space. Third, a
<<shaders-tessellation-evaluation,tessellation evaluation shader>>
transforms the vertices of the tessellated patch, for example to compute
their positions and attributes as part of the tessellated surface. The
tessellator is enabled when the pipeline contains both a tessellation
control shader and a tessellation evaluation shader.


== Tessellator

If a pipeline includes both tessellation shaders (control and evaluation),
the tessellator consumes each input patch (after vertex shading) and
produces a new set of independent primitives (points, lines, or triangles).
These primitives are logically produced by subdividing a geometric primitive
(rectangle or triangle) according to the per-patch outer and inner
tessellation levels written by the tessellation control shader. These levels
are specified using the <<interfaces-builtin-variables,built-in variables>>
code:TessLevelOuter and code:TessLevelInner, respectively.
This subdivision is performed in
an implementation-dependent manner. If no tessellation shaders are present
in the pipeline, the tessellator is disabled and incoming primitives are
passed through without modification.

The type of subdivision performed by the tessellator is
specified by an code:OpExecutionMode instruction in the tessellation
evaluation or tessellation control shader using one of execution modes
code:Triangles, code:Quads, and code:IsoLines. Other
tessellation-related execution modes can: also be specified in either the
tessellation control or tessellation evaluation shaders, and if they are
specified in both then the modes must: be the same.

Tessellation execution modes include:

  * code:Triangles, code:Quads, and code:IsoLines. These control the type of
    subdivision and topology of the output primitives. One mode must: be set
    in at least one of the tessellation shader stages.
  * code:VertexOrderCw and code:VertexOrderCcw. These control the
    orientation of triangles generated by the tessellator. One mode must: be
    set in at least one of the tessellation shader stages.
  * code:PointMode. Controls generation of points rather than triangles or
    lines. This functionality defaults to disabled, and is enabled if either
    shader stage includes the execution mode.
  * code:SpacingEqual, code:SpacingFractionalEven, and
    code:SpacingFractionalOdd. Controls the spacing of segments on the edges
    of tessellated primitives. One mode must: be set in at least one of the
    tessellation shader stages.
  * code:OutputVertices. Controls the size of the output patch of the
    tessellation control shader. One value must: be set in at least one of
    the tessellation shader stages.

For triangles, the tessellator subdivides a triangle primitive into
smaller triangles. For quads, the tessellator subdivides a rectangle
primitive into smaller triangles. For isolines, the tessellator
subdivides a rectangle primitive into a collection of line segments arranged
in strips stretching across the rectangle in the latexmath:[$u$] dimension
(i.e. the coordinates in code:TessCoord are of the form (0,x) through (1,x)
for all tessellation evaluation shader invocations that share a line).

Each vertex produced by the tessellator has an associated (u,v,w) or (u,v)
position in a normalized parameter space, with parameter values in the range
latexmath:[$[0,1\]$], as illustrated in figure
<<img-tessellation-topology>>.

[[img-tessellation-topology]]
image::images/tessparam.{svgpdf}[align="center",title="Domain parameterization for tessellation primitive modes",{fullimagewidth}]

For triangles, the vertex's position is a barycentric coordinate (u,v,w),
where u + v + w = 1.0, and indicates the relative influence of the three
vertices of the triangle on the position of the vertex. For quads and
isolines, the position is a (u,v) coordinate indicating the relative
horizontal and vertical position of the vertex relative to the subdivided
rectangle. The subdivision process is explained in more detail in subsequent
sections.


== Tessellator Patch Discard

A patch is discarded by the tessellator if any
relevant outer tessellation level is less than or equal to zero.

Patches will also be discarded if any relevant outer tessellation level
corresponds to a floating-point NaN (not a number) in implementations
supporting NaN.

No new primitives are generated and the tessellation evaluation shader is
not executed for patches that are discarded. For code:Quads, all four outer
levels are relevant. For code:Triangles and code:IsoLines, only the first
three or two outer levels, respectively, are relevant. Negative inner levels
will not cause a patch to be discarded; they will be clamped as described
below.


[[tessellation-tessellator-spacing]]
== Tessellator Spacing

Each of the tessellation levels is used to determine the number and
spacing of segments used to subdivide a corresponding edge. The method
used to derive the number and spacing of segments is specified by an
code:OpExecutionMode in the tessellation control or tessellation evaluation
shader using one of the identifiers code:SpacingEqual,
code:SpacingFractionalEven, or code:SpacingFractionalOdd.

If code:SpacingEqual is used, the floating-point tessellation level is first
clamped to latexmath:[$[1,\mathit{maxLevel}\]$], where
latexmath:[$\mathit{maxLevel}$] is the implementation-dependent maximum
tessellation level
(sname:VkPhysicalDeviceLimits::pname:maxTessellationGenerationLevel). The
result is rounded up to the nearest integer latexmath:[$n$], and the
corresponding edge is divided into latexmath:[$n$] segments of equal length
in (u,v) space.

If code:SpacingFractionalEven is used, the tessellation level is first
clamped to latexmath:[$[2,\mathit{maxLevel}\]$] and then rounded up to the
nearest even integer latexmath:[$n$]. If code:SpacingFractionalOdd is used,
the tessellation level is clamped to latexmath:[$[1,\mathit{maxLevel}-1\]$]
and then rounded up to the nearest odd integer latexmath:[$n$]. If
latexmath:[$n$] is one, the edge will not be subdivided. Otherwise, the
corresponding edge will be divided into latexmath:[$n-2$] segments of equal
length, and two additional segments of equal length that are typically
shorter than the other segments. The length of the two additional segments
relative to the others will decrease monotonically with
latexmath:[$n-f$], where latexmath:[$f$] is the clamped floating-point
tessellation level. When latexmath:[$n-f$] is zero, the additional segments
will have equal length to the other segments. As latexmath:[$n-f$]
approaches 2.0, the relative length of the additional segments approaches
zero. The two additional segments should: be placed symmetrically on
opposite sides of the subdivided edge. The relative location of these two
segments is implementation-dependent, but must: be identical for any pair of
subdivided edges with identical values of latexmath:[$f$].

When the tessellator produces triangles (in the code:Triangles or
code:Quads modes), the orientation of all triangles is specified with
an code:OpExecutionMode of code:VertexOrderCw or code:VertexOrderCcw in the
tessellation control or tessellation evaluation shaders. If the order is
code:VertexOrderCw, the vertices of all generated triangles will have
clockwise ordering in (u,v) or (u,v,w) space. If the order is
code:VertexOrderCcw, the vertices will have counter-clockwise ordering.

The vertices of a triangle have counter-clockwise ordering if

[latexmath]
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\[
  a = u_0 v_1 - u_1 v_0 + u_1 v_2 - u_2 v_1 + u_2 v_0 - u_0 v_2
\]
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

is positive, and clockwise ordering if latexmath:[$a$] is negative.
latexmath:[$u_i$] and latexmath:[$v_i$] are the latexmath:[$u$] and
latexmath:[$v$] coordinates in normalized parameter space of the
latexmath:[$i$]th vertex of the triangle.

[NOTE]
.Note
====
The value latexmath:[$a$] is proportional (with a positive factor) to the
signed area of the triangle.

In code:Triangles mode, even though the vertex coordinates have a
latexmath:[$w$] value, it does not participate directly in the computation
of latexmath:[$a$], being an affine combination of latexmath:[$u$] and
latexmath:[$v$].
====

For all primitive modes, the tessellator is capable of generating points
instead of lines or triangles. If the tessellation control or tessellation
evaluation shader specifies the code:OpExecutionMode code:PointMode, the
primitive generator will generate one point for each distinct vertex
produced by tessellation. Otherwise, the tessellator will produce a
collection of line segments or triangles according to the primitive mode.
When tessellating triangles or quads in point mode with fractional odd
spacing, the tessellator may: produce _interior vertices_ that are
positioned on the edge of the patch if an inner tessellation level is less
than or equal to one. Such vertices are considered distinct from vertices
produced by subdividing the outer edge of the patch, even if there are pairs
of vertices with identical coordinates.

The points, lines, or triangles produced by the tessellator
are passed to subsequent pipeline stages in an
implementation-dependent order.


[[tessellation-triangle-tessellation]]
== Triangle Tessellation

If the tessellation primitive mode is code:Triangles, an equilateral
triangle is subdivided into a collection of triangles covering the area of
the original triangle. First, the original triangle is subdivided into a
collection of concentric equilateral triangles. The edges of each of these
triangles are subdivided, and the area between each triangle pair is filled
by triangles produced by joining the vertices on the subdivided edges. The
number of concentric triangles and the number of subdivisions along each
triangle except the outermost is derived from the first inner tessellation
level. The edges of the outermost triangle are subdivided independently,
using the first, second, and third outer tessellation levels to control the
number of subdivisions of the latexmath:[$u=0$] (left), latexmath:[$v=0$]
(bottom), and latexmath:[$w=0$] (right) edges, respectively. The second
inner tessellation level and the fourth outer tessellation level have no
effect in this mode.

If the first inner tessellation level and all three outer tessellation
levels are exactly one after clamping and rounding, only a single triangle
with (u,v,w) coordinates of (0,0,1), (1,0,0), and (0,1,0) is generated.
If the inner tessellation level is one and any of the outer tessellation
levels is greater than one, the inner tessellation level is treated as
though it were originally specified as latexmath:[$1+\epsilon$] and will
result in a two- or three-segment subdivision depending on the tessellation
spacing. When used with fractional odd spacing, the three-segment
subdivision may: produce _inner vertices_ positioned on the edge of the
triangle.

If any tessellation level is greater than one, tessellation begins by
producing a set of concentric inner triangles and subdividing their edges.
First, the three outer edges are temporarily subdivided using the clamped
and rounded first inner tessellation level and the specified tessellation
spacing, generating latexmath:[$n$] segments. For the outermost inner
triangle, the inner triangle is degenerate -- a single point at the center
of the triangle -- if latexmath:[$n$] is two. Otherwise, for each corner of
the outer triangle, an inner triangle corner is produced at the intersection
of two lines extended perpendicular to the corner's two adjacent edges
running through the vertex of the subdivided outer edge nearest that corner.
If latexmath:[$n$] is three, the edges of the inner triangle are not
subdivided and is the final triangle in the set of concentric triangles.
Otherwise, each edge of the inner triangle is divided into latexmath:[$n-2$]
segments, with the latexmath:[$n-1$] vertices of this subdivision produced
by intersecting the inner edge with lines perpendicular to the edge running
through the latexmath:[$n-1$] innermost vertices of the subdivision of the
outer edge. Once the outermost inner triangle is subdivided, the previous
subdivision process repeats itself, using the generated triangle as an outer
triangle. This subdivision process is illustrated in <<img-innertri,Inner
Triangle Tessellation>>.

[[img-innertri]]
image::images/innertri.{svgpdf}[align="center",title="Inner Triangle Tessellation",{fullimagewidth}]

// TODO: Add caption:
//  Inner triangle tessellation with inner tessellation
//  levels of (a) five and (b) four, respectively (not to scale). Solid
//  black circles depict vertices along the edges of the concentric
//  triangles. The edges of inner triangles are subdivided by intersecting
//  the edge with segments perpendicular to the edge passing through each
//  inner vertex of the subdivided outer edge. Dotted lines depict edges
//  connecting corresponding vertices on the inner and outer triangle
//  edges.

Once all the concentric triangles are produced and their edges are
subdivided, the area between each pair of adjacent inner triangles is
filled completely with a set of non-overlapping triangles. In this
subdivision, two of the three vertices of each triangle are taken from
adjacent vertices on a subdivided edge of one triangle; the third is one
of the vertices on the corresponding edge of the other triangle. If the
innermost triangle is degenerate (i.e., a point), the triangle containing
it is subdivided into six triangles by connecting each of the six vertices
on that triangle with the center point. If the innermost triangle is not
degenerate, that triangle is added to the set of generated triangles
as-is.

After the area corresponding to any inner triangles is filled, the
tessellator generates triangles to cover the area between the outermost
triangle and the outermost inner triangle. To do this, the temporary
subdivision of the outer triangle edge above is discarded. Instead, the
latexmath:[$u=0$], latexmath:[$v=0$], and latexmath:[$w=0$] edges are
subdivided according to the first, second, and third outer tessellation
levels, respectively, and the tessellation spacing. The original subdivision
of the first inner triangle is retained. The area between the outer and
first inner triangles is completely filled by non-overlapping triangles as
described above. If the first (and only) inner triangle is degenerate, a set
of triangles is produced by connecting each vertex on the outer triangle
edges with the center point.

After all triangles are generated, each vertex in the subdivided triangle
is assigned a barycentric (u,v,w) coordinate based on its location
relative to the three vertices of the outer triangle.

The algorithm used to subdivide the triangular domain in (u,v,w) space into
individual triangles is implementation-dependent. However, the set of
triangles produced will completely cover the domain, and no portion of the
domain will be covered by multiple triangles. The order in which the
generated triangles passed to subsequent pipeline stages and the order of
the vertices in those triangles are both implementation-dependent. However,
when depicted in a manner similar to <<img-innertri,Inner Triangle
Tessellation>>, the order of the vertices in the generated triangles will be
either all clockwise or all counter-clockwise, according to the vertex order
layout declaration.


[[tessellation-quad-tessellation]]
== Quad Tessellation

If the tessellation primitive mode is code:Quads, a rectangle is subdivided
into a collection of triangles covering the area of the original rectangle.
First, the original rectangle is subdivided into a regular mesh of
rectangles, where the number of rectangles along the latexmath:[$u=0$] and
latexmath:[$u=1$] (vertical) and latexmath:[$v=0$] and latexmath:[$v=1$]
(horizontal) edges are derived from the first and second inner tessellation
levels, respectively. All rectangles, except those adjacent to one of the
outer rectangle edges, are decomposed into triangle pairs. The outermost
rectangle edges are subdivided independently, using the first, second,
third, and fourth outer tessellation levels to control the number of
subdivisions of the latexmath:[$u=0$] (left), latexmath:[$v=0$] (bottom),
latexmath:[$u=1$] (right), and latexmath:[$v=1$] (top) edges, respectively.
The area between the inner rectangles of the mesh and the outer rectangle
edges are filled by triangles produced by joining the vertices on the
subdivided outer edges to the vertices on the edge of the inner rectangle
mesh.

If both clamped inner tessellation levels and all four clamped outer
tessellation levels are exactly one, only a single triangle pair covering
the outer rectangle is generated. Otherwise, if either clamped inner
tessellation level is one, that tessellation level is treated as though it
were originally specified as latexmath:[$1+\epsilon$] and will result in a
two- or three-segment subdivision depending on the tessellation spacing.
When used with fractional odd spacing, the three-segment subdivision may:
produce _inner vertices_ positioned on the edge of the rectangle.

If any tessellation level is greater than one, tessellation begins by
subdividing the latexmath:[$u=0$] and latexmath:[$u=1$] edges of the outer
rectangle into latexmath:[$m$] segments using the clamped and rounded first
inner tessellation level and the tessellation spacing. The latexmath:[$v=0$]
and latexmath:[$v=1$] edges are subdivided into latexmath:[$n$] segments
using the second inner tessellation level. Each vertex on the
latexmath:[$u=0$] and latexmath:[$v=0$] edges are joined with the
corresponding vertex on the latexmath:[$u=1$] and latexmath:[$v=1$] edges to
produce a set of vertical and horizontal lines that divide the rectangle
into a grid of smaller rectangles. The primitive generator emits a pair of
non-overlapping triangles covering each such rectangle not adjacent to an
edge of the outer rectangle. The boundary of the region covered by these
triangles forms an inner rectangle, the edges of which are subdivided by the
grid vertices that lie on the edge. If either latexmath:[$m$] or
latexmath:[$n$] is two, the inner rectangle is degenerate, and one or both
of the rectangle's _edges_ consist of a single point. This subdivision is
illustrated in Figure <<img-innerquad,Inner Quad Tessellation>>.

[[img-innerquad]]
image::images/innerquad.{svgpdf}[align="center",title="Inner Quad Tessellation",{fullimagewidth}]

// TODO: Add caption:
//  Inner quad tessellation with inner tessellation
//  levels of
//  (a) $(4,2)$ and (b) $(7,4)$, respectively. Gray regions on the
//  bottom figure
//  depict the 10 inner rectangles, each of which will be subdivided
//  into two triangles.
//  Solid black circles depict vertices on the boundary of the outer and
//  inner rectangles,
//  where the inner rectangle on the top figure
//  is degenerate (a single line segment). Dotted lines depict the
//  horizontal and vertical edges connecting corresponding
//  vertices on the inner and outer rectangle edges.

After the area corresponding to the inner rectangle is filled, the
tessellator must: produce triangles to cover the area between the inner and
outer rectangles. To do this, the subdivision of the outer rectangle edge
above is discarded. Instead, the latexmath:[$u=0$], latexmath:[$v=0$],
latexmath:[$u=1$], and latexmath:[$v=1$] edges are subdivided according to
the first, second, third, and fourth outer tessellation levels,
respectively, and the tessellation spacing. The original subdivision of the
inner rectangle is retained. The area between the outer and inner rectangles
is completely filled by non-overlapping triangles. Two of the three vertices
of each triangle are adjacent vertices on a subdivided edge of one
rectangle; the third is one of the vertices on the corresponding edge of the
other triangle. If either edge of the innermost rectangle is degenerate, the
area near the corresponding outer edges is filled by connecting each vertex
on the outer edge with the single vertex making up the _inner edge_.

The algorithm used to subdivide the rectangular domain in (u,v) space into
individual triangles is implementation-dependent. However, the set of
triangles produced will completely cover the domain, and no portion of the
domain will be covered by multiple triangles. The order in which the
generated triangles passed to subsequent pipeline stages and the order of
the vertices in those triangles are both implementation-dependent.
However, when depicted in a manner similar to <<img-innerquad,Inner Quad
Tessellation>>, the order of the vertices in the generated triangles will be
either all clockwise or all counter-clockwise, according to the vertex order
layout declaration.


[[tessellation-isoline-tessellation]]
== Isoline Tessellation

If the tessellation primitive mode is code:IsoLines, a set of independent
horizontal line segments is drawn. The segments are arranged into
connected strips called _isolines_, where the vertices of each isoline
have a constant v coordinate and u coordinates covering the full range
[0,1]. The number of isolines generated is derived from the first outer
tessellation level; the number of segments in each isoline is derived from
the second outer tessellation level. Both inner tessellation levels and
the third and fourth outer tessellation levels have no effect in this
mode.

As with quad tessellation above, isoline tessellation begins with a
rectangle. The latexmath:[$u=0$] and latexmath:[$u=1$] edges of the
rectangle are subdivided according to the first outer tessellation level.
For the purposes of this subdivision, the tessellation spacing mode is
ignored and treated as equal_spacing. An isoline is drawn connecting each
vertex on the latexmath:[$u=0$] rectangle edge to the corresponding vertex
on the latexmath:[$u=1$] rectangle edge, except that no line is drawn
between (0,1) and (1,1). If the number of isolines on the subdivided
latexmath:[$u=0$] and latexmath:[$u=1$] edges is latexmath:[$n$], this
process will result in latexmath:[$n$] equally spaced lines with constant v
coordinates of 0, latexmath:[$\frac{1}{n}, \frac{2}{n}, \ldots,
\frac{n-1}{n}$].

Each of the latexmath:[$n$] isolines is then subdivided according to the
second outer tessellation level and the tessellation spacing, resulting in
latexmath:[$m$] line segments. Each segment of each line is emitted by the
tessellator.

The order in which the generated line segments are passed to subsequent
pipeline stages and the order of the vertices in each generated line
segment are both implementation-dependent.


== Tessellation Pipeline State

The pname:pTessellationState member of slink:VkGraphicsPipelineCreateInfo
points to a structure of type sname:VkPipelineTessellationStateCreateInfo.

The sname:VkPipelineTessellationStateCreateInfo structure is defined as:

include::../structs/VkPipelineTessellationStateCreateInfo.txt[]

  * pname:sType is the type of this structure.
  * pname:pNext is `NULL` or a pointer to an extension-specific structure.
  * pname:flags is reserved for future use.
  * pname:patchControlPoints number of control points per patch.

include::../validity/structs/VkPipelineTessellationStateCreateInfo.txt[]