| // Graphite-specific vertex shader code |
| |
| // Wang's formula gives the minimum number of evenly spaced (in the parametric sense) line segments |
| // that a bezier curve must be chopped into in order to guarantee all lines stay within a distance |
| // of "1/precision" pixels from the true curve. Its definition for a bezier curve of degree "n" is |
| // as follows: |
| // |
| // maxLength = max([length(p[i+2] - 2p[i+1] + p[i]) for (0 <= i <= n-2)]) |
| // numParametricSegments = sqrt(maxLength * precision * n*(n - 1)/8) |
| // |
| // (Goldman, Ron. (2003). 5.6.3 Wang's Formula. "Pyramid Algorithms: A Dynamic Programming Approach |
| // to Curves and Surfaces for Geometric Modeling". Morgan Kaufmann Publishers.) |
| |
| const float $Degree = 3; |
| const float $Precision = 1; |
| const float $LengthTerm = ($Degree * ($Degree - 1) / 8.0) * $Precision; |
| const float $LengthTermPow2 = (($Degree * $Degree) * (($Degree - 1) * ($Degree - 1)) / 64.0) * |
| ($Precision * $Precision); |
| |
| // Returns the length squared of the largest forward difference from Wang's cubic formula. |
| float wangs_formula_max_fdiff_pow2(float2 p0, float2 p1, float2 p2, float2 p3, |
| float2x2 matrix) { |
| float2 d0 = matrix * (fma(float2(-2), p1, p2) + p0); |
| float2 d1 = matrix * (fma(float2(-2), p2, p3) + p1); |
| return max(dot(d0,d0), dot(d1,d1)); |
| } |
| |
| float wangs_formula_cubic(float _precision_, float2 p0, float2 p1, float2 p2, float2 p3, |
| float2x2 matrix) { |
| float m = wangs_formula_max_fdiff_pow2(p0, p1, p2, p3, matrix); |
| return max(ceil(sqrt($LengthTerm * _precision_ * sqrt(m))), 1.0); |
| } |
| |
| float wangs_formula_cubic_log2(float _precision_, float2 p0, float2 p1, float2 p2, float2 p3, |
| float2x2 matrix) { |
| float m = wangs_formula_max_fdiff_pow2(p0, p1, p2, p3, matrix); |
| return ceil(log2(max($LengthTermPow2 * _precision_ * _precision_ * m, 1.0)) * .25); |
| } |
| |
| float wangs_formula_conic_pow2(float _precision_, float2 p0, float2 p1, float2 p2, float w) { |
| // Translate the bounding box center to the origin. |
| float2 C = (min(min(p0, p1), p2) + max(max(p0, p1), p2)) * 0.5; |
| p0 -= C; |
| p1 -= C; |
| p2 -= C; |
| |
| // Compute max length. |
| float m = sqrt(max(max(dot(p0,p0), dot(p1,p1)), dot(p2,p2))); |
| |
| // Compute forward differences. |
| float2 dp = fma(float2(-2.0 * w), p1, p0) + p2; |
| float dw = abs(fma(-2.0, w, 2.0)); |
| |
| // Compute numerator and denominator for parametric step size of linearization. Here, the |
| // epsilon referenced from the cited paper is 1/precision. |
| float rp_minus_1 = max(0.0, fma(m, _precision_, -1.0)); |
| float numer = length(dp) * _precision_ + rp_minus_1 * dw; |
| float denom = 4 * min(w, 1.0); |
| |
| return numer/denom; |
| } |
| |
| float wangs_formula_conic(float _precision_, float2 p0, float2 p1, float2 p2, float w) { |
| float n2 = wangs_formula_conic_pow2(_precision_, p0, p1, p2, w); |
| return max(ceil(sqrt(n2)), 1.0); |
| } |
| |
| float wangs_formula_conic_log2(float _precision_, float2 p0, float2 p1, float2 p2, float w) { |
| float n2 = wangs_formula_conic_pow2(_precision_, p0, p1, p2, w); |
| return ceil(log2(max(n2, 1.0)) * .5); |
| } |
| |
| float2 middle_out_curve(float resolveLevel, float idxInResolveLevel, float4 p01, float4 p23) { |
| float2 localcoord; |
| if (isinf(p23.z)) { |
| // This patch is an exact triangle. |
| localcoord = (resolveLevel != 0) ? p01.zw |
| : (idxInResolveLevel != 0) ? p23.xy |
| : p01.xy; |
| } else { |
| float2 p0=p01.xy, p1=p01.zw, p2=p23.xy, p3=p23.zw; |
| float w = -1; // w < 0 tells us to treat the instance as an integral cubic. |
| float maxResolveLevel; |
| if (isinf(p23.w)) { |
| // Conics are 3 points, with the weight in p3. |
| w = p3.x; |
| maxResolveLevel = wangs_formula_conic_log2(4, p0, p1, p2, w); |
| p1 *= w; // Unproject p1. |
| p3 = p2; // Duplicate the endpoint for shared code that also runs on cubics. |
| } else { |
| // The patch is an integral cubic. |
| maxResolveLevel = wangs_formula_cubic_log2(4, p0, p1, p2, p3, float2x2(1.0)); |
| } |
| if (resolveLevel > maxResolveLevel) { |
| // This vertex is at a higher resolve level than we need. Demote to a lower |
| // resolveLevel, which will produce a degenerate triangle. |
| idxInResolveLevel = floor(ldexp(idxInResolveLevel, |
| int(maxResolveLevel - resolveLevel))); |
| resolveLevel = maxResolveLevel; |
| } |
| // Promote our location to a discrete position in the maximum fixed resolve level. |
| // This is extra paranoia to ensure we get the exact same fp32 coordinates for |
| // colocated points from different resolve levels (e.g., the vertices T=3/4 and |
| // T=6/8 should be exactly colocated). |
| float fixedVertexID = floor(.5 + ldexp(idxInResolveLevel, int(5 - resolveLevel))); |
| if (0 < fixedVertexID && fixedVertexID < 32) { |
| float T = fixedVertexID * (1 / 32.0); |
| |
| // Evaluate at T. Use De Casteljau's for its accuracy and stability. |
| float2 ab = mix(p0, p1, T); |
| float2 bc = mix(p1, p2, T); |
| float2 cd = mix(p2, p3, T); |
| float2 abc = mix(ab, bc, T); |
| float2 bcd = mix(bc, cd, T); |
| float2 abcd = mix(abc, bcd, T); |
| |
| // Evaluate the conic weight at T. |
| float u = mix(1.0, w, T); |
| float v = w + 1 - u; // == mix(w, 1, T) |
| float uv = mix(u, v, T); |
| |
| localcoord = (w < 0) ? /*cubic*/ abcd : /*conic*/ abc/uv; |
| } else { |
| localcoord = (fixedVertexID == 0) ? p0.xy : p3.xy; |
| } |
| } |
| return localcoord; |
| } |
| |
| float2 middle_out_wedge(float resolveLevel, float idxInResolveLevel, float4 p01, float4 p23, |
| float2 fanPointAttrib) { |
| if (resolveLevel < 0) { |
| // A negative resolve level means this is the fan point. |
| return fanPointAttrib; |
| } else { |
| return middle_out_curve(resolveLevel, idxInResolveLevel, p01, p23); |
| } |
| } |