![]() |
by C.G. Sleuth December,
2020
|
Quadrilaterals - four-sided polygons - might be more common in design than we realize. For some applications, like display of font characters or representation of ruled surfaces, surfaces of revolution, or patches, they are a more natural design element than triangles. You might know that OpenGL divides all quadrilaterals into triangles before rendering, but did you know there can be a problem inherent with this division?
When
OpenGL divides a quadrilateral into separately rasterized triangles, the
results are often artifact-free, such as the following square with a
grid texture.
The
geometry (the four points that define the square) and the texture domain
(defined by the four corresponding points on the texture map) have the
same, square shape. In perspective, the geometry appears as a trapezoid,
but the texture-mapped image remains artifact-free. If, rather than a
square, we start with a trapezoid as our geometry and divide it into two
triangles that are rendered separately, the result contains a C1
discontinuity along the diagonal.
Why does the trapezoid below have an artifact but the trapezoid above
does not?
Figure 2: Texture-mapped trapezoid rendered as two triangles
To answer this question, let's consider a single, non-degenerate triangle defined by three screen-space points and an associated triangle of three texture-space points (i.e., uv-coordinates). A unique, affine transformation exists that maps the screen triangle to the texture triangle. This guarantees that the parallel rows of pixels produced when rasterizing the screen-space triangle will correspond with parallel rows of samples along a texture map.
Let us now add a fourth screen-space point and a corresponding fourth texture point, creating a second screen triangle and a second texture triangle. The rows of pixels in the two screen triangles obviously align with each other, but for the rows of samples to align between the two texture triangles, the affine transformation described above must be applied to the new screen location to determine the new texture location. If the new texture-space point is placed elsewhere, a discontinuity in the texture gradient occurs at the shared boundary of the triangles.
The appendix provides
code to test whether a quad's texture coordinates are affinely related
to its corner locations.
It isn't always possible that the texture shape is an affine image of the geometric shape. For example, the longitude/latitude parameterization typical of a sphere implies that the quad geometry becomes increasingly trapezoidal the closer the quad is to a pole, whereas its texture domain remains rectangular. As the foreshortening increases, the texture discontinuity increases.
In the extreme, at the pole, Q2 is a quadrilateral whose degenerate upper edge is a point. When divided into triangles, geometrically, one triangle covers no pixels, so its corresponding texture is ignored.
The C1
texture discontinuity has been of concern since the
late 1970s. In 2004, Hormann and Tarini proposed
a quadrilateral
rendering primitive that uses generalized barycentric
coordinates to produce a bilinear interpolation of vertex
attributes.
Their method can be implemented with the following OpenGL geometry shader. With GL_LINES_ADJACENCY as the first argument to glDrawArrays or glDrawElements, four vertices from the vertex shader are sent to the geometry shader as an array, for each quad (the geometry shader does not accept GL_QUADS as an input primitive, but GL_LINES_ADJACENCY achieves the same result).
The
perspective space coordinates of the vertices (gpos0-3), and the
texture coordinates (guv0-3) are then sent to the rasterizer (as
separate variables, not arrays) and then to the pixel shader for use in
computing the proper uv-coordinates.
In UV(), below, the built-in gl_FragCoord input to the pixel shader is converted to perspective-space coordinates and used to compute the barycentric weights with respect to the quad corners, gpos0-3. The perspective-corrected weights are applied to guv0-3 to determine the correct, bilinearly interpolated uv-coordinates for the pixel. Note the use of double precision in BarycentricWeights() and UV().
const char *pixelShader = R"(
The diagonals in the texture above appear curved due to the curvature of the sphere. When viewed in perspective, however, lines can appear curved, even on a flat surface, if the barycentric weights are not corrected for perspective. The correction is performed by the division by gpos0-4.w when computing v[ ] in BarycentricWeights() and f[ ] in UV(). As a result, straight lines remain straight, as they should.
C1 discontinuity also occurs when shading a quad without texture. A perspective-correct bilinear interpolation can be made by replacing guv0-3 in the geometry and pixel shaders with gcolor0-3.
The OpenGL SuperBible
(6th ed., ch. 8, Rendering Quads using a Geometry Shader) and a blog
post by Izdebski (How to Correctly Interpolate
Vertex Attributes on a Parallelogram Using Modern GPUs) consider
this shading issue, although the proposed solutions do not eliminate
texture discontinuity.
An alternative method to reduce the triangulation artifact is to increase resolution. For example, for the sphere, the number of circles of latitude can be increased, especially near the poles. Even at twice the resolution, however, the artifact remains problematic.
UV() requires 100+
arithmetic operations,
so one good
strategy is to invoke bilinear interpolation only for quads whose
geometric and texture coordinates are not affinely related.
If a quad's texture coordinates are an affine image of (i.e., affinely related to) its corners, the rate and direction of texture samples will match across the triangles and there will be no texture gradient discontinuity. If they are not an affine image, bilinear quad interpolation can be used to avoid the discontinuity.
Here
is a simple test for affinity. For
each corner of the quad, compute its barycentric coordinates with
respect to the other three corners
(this is a
different use for barycentric coordinates than the use above for
bilinear interpolation).
Also compute the barycentric coordinates of the corresponding
texture-space location with respect to the other three texture
locations. If there is affinity, these two barycentric coordinates will
match.