by C.G. Sleuth December,
2020

Quadrilaterals  foursided 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 artifactfree, 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 texturemapped image remains artifactfree. 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 C^{1}
discontinuity along the diagonal.
Why does the trapezoid below have an artifact but the trapezoid above
does not?
Figure 2: Texturemapped trapezoid rendered as two triangles
To answer this question, let's consider a single, nondegenerate triangle defined by three screenspace points and an associated triangle of three texturespace points (i.e., uvcoordinates). A unique, affine transformation exists that maps the screen triangle to the texture triangle. This guarantees that the parallel rows of pixels produced when rasterizering the screenspace triangle will correspond with parallel rows of samples along a texture map.
Let us now add a fourth screenspace 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 texturespace 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 square. 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 C^{1}
texture discontinuity has been of concern since the
late 1970s. In 2004, Hormann and Tarini proposed
a quad rasterizer (A
Quadrilateral Rendering Primitive) that uses generalized
barycentric coordinates to produce a bilinear interpolation of
vertex attributes.
Their method can be implemented with an OpenGL geometry shader, below. 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 (gpos03), and the
texture coordinates (guv03) are then sent to the rasterizer (as
separate variables, not arrays) and then to the pixel shader for use in
computing the proper uvcoordinates.
In UV(), below, the builtin gl_FragCoord input to the pixel shader is converted to perspectivespace coordinates and used to compute the barycentric weights with respect to the quad corners, gpos03. The perspectivecorrected weights are applied to guv03 to determine the correct, bilinearly interpolated uvcoordinates for the pixel. Note the use of double precision in BarycentricWeights() and UV().
const char *pixelShader = R"(
The diagonals present in the texture above appear curved due to the curvature of the sphere. When viewed in perspective, however, the diagonals will appear curved, even on a flat surface, if the barycentric weights are not corrected. The perspective correction is performed by the division by gpos04.w when computing v[ ] in BarycentricWeights() and f[ ] in UV(). As a result, the diagonals remain straight, as they should.
C^{1} discontinuity also occurs when shading a quad without texture. A perspectivecorrect bilinear interpolation can be made by replacing guv03 in the geometry and pixel shaders with gcolor03.
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
texturespace location with respect to the other three texture
locations. If there is affinity, these two barycentric coordinates will
match.