Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
godotengine
GitHub Repository: godotengine/godot
 Path: blob/master/thirdparty/msdfgen/core/sdf-error-estimation.cpp
14710 views
1


2
#include "sdf-error-estimation.h"

3


4
#include <cmath>

5
#include "arithmetics.hpp"

6


7
namespace msdfgen {

8


9
void scanlineSDF(Scanline &line, const BitmapConstSection<float, 1> &sdf, const Projection &projection, double y, YAxisOrientation yAxisOrientation) {

10
    if (!(sdf.width > 0 && sdf.height > 0))

11
        return line.setIntersections(std::vector<Scanline::Intersection>());

12
    double pixelY = clamp(projection.projectY(y)-.5, double(sdf.height-1));

13
    if (yAxisOrientation == Y_DOWNWARD)

14
        pixelY = sdf.height-1-pixelY;

15
    int b = (int) floor(pixelY);

16
    int t = b+1;

17
    double bt = pixelY-b;

18
    if (t >= sdf.height) {

19
        b = sdf.height-1;

20
        t = sdf.height-1;

21
        bt = 1;

22
    }

23
    bool inside = false;

24
    std::vector<Scanline::Intersection> intersections;

25
    float lv, rv = mix(*sdf(0, b), *sdf(0, t), bt);

26
    if ((inside = rv > .5f)) {

27
        Scanline::Intersection intersection = { -1e240, 1 };

28
        intersections.push_back(intersection);

29
    }

30
    for (int l = 0, r = 1; r < sdf.width; ++l, ++r) {

31
        lv = rv;

32
        rv = mix(*sdf(r, b), *sdf(r, t), bt);

33
        if (lv != rv) {

34
            double lr = double(.5f-lv)/double(rv-lv);

35
            if (lr >= 0 && lr <= 1) {

36
                Scanline::Intersection intersection = { projection.unprojectX(l+lr+.5), sign(rv-lv) };

37
                intersections.push_back(intersection);

38
            }

39
        }

40
    }

41
#ifdef MSDFGEN_USE_CPP11

42
    line.setIntersections((std::vector<Scanline::Intersection> &&) intersections);

43
#else

44
    line.setIntersections(intersections);

45
#endif

46
}

47


48
template <int N>

49
void scanlineMSDF(Scanline &line, const BitmapConstSection<float, N> &sdf, const Projection &projection, double y, YAxisOrientation yAxisOrientation) {

50
    if (!(sdf.width > 0 && sdf.height > 0))

51
        return line.setIntersections(std::vector<Scanline::Intersection>());

52
    double pixelY = clamp(projection.projectY(y)-.5, double(sdf.height-1));

53
    if (yAxisOrientation == Y_DOWNWARD)

54
        pixelY = sdf.height-1-pixelY;

55
    int b = (int) floor(pixelY);

56
    int t = b+1;

57
    double bt = pixelY-b;

58
    if (t >= sdf.height) {

59
        b = sdf.height-1;

60
        t = sdf.height-1;

61
        bt = 1;

62
    }

63
    bool inside = false;

64
    std::vector<Scanline::Intersection> intersections;

65
    float lv[3], rv[3];

66
    rv[0] = mix(sdf(0, b)[0], sdf(0, t)[0], bt);

67
    rv[1] = mix(sdf(0, b)[1], sdf(0, t)[1], bt);

68
    rv[2] = mix(sdf(0, b)[2], sdf(0, t)[2], bt);

69
    if ((inside = median(rv[0], rv[1], rv[2]) > .5f)) {

70
        Scanline::Intersection intersection = { -1e240, 1 };

71
        intersections.push_back(intersection);

72
    }

73
    for (int l = 0, r = 1; r < sdf.width; ++l, ++r) {

74
        lv[0] = rv[0], lv[1] = rv[1], lv[2] = rv[2];

75
        rv[0] = mix(sdf(r, b)[0], sdf(r, t)[0], bt);

76
        rv[1] = mix(sdf(r, b)[1], sdf(r, t)[1], bt);

77
        rv[2] = mix(sdf(r, b)[2], sdf(r, t)[2], bt);

78
        Scanline::Intersection newIntersections[4];

79
        int newIntersectionCount = 0;

80
        for (int i = 0; i < 3; ++i) {

81
            if (lv[i] != rv[i]) {

82
                double lr = double(.5f-lv[i])/double(rv[i]-lv[i]);

83
                if (lr >= 0 && lr <= 1) {

84
                    float v[3] = {

85
                        mix(lv[0], rv[0], lr),

86
                        mix(lv[1], rv[1], lr),

87
                        mix(lv[2], rv[2], lr)

88
                    };

89
                    if (median(v[0], v[1], v[2]) == v[i]) {

90
                        newIntersections[newIntersectionCount].x = projection.unprojectX(l+lr+.5);

91
                        newIntersections[newIntersectionCount].direction = sign(rv[i]-lv[i]);

92
                        ++newIntersectionCount;

93
                    }

94
                }

95
            }

96
        }

97
        // Sort new intersections

98
        if (newIntersectionCount >= 2) {

99
            if (newIntersections[0].x > newIntersections[1].x)

100
                newIntersections[3] = newIntersections[0], newIntersections[0] = newIntersections[1], newIntersections[1] = newIntersections[3];

101
            if (newIntersectionCount >= 3 && newIntersections[1].x > newIntersections[2].x) {

102
                newIntersections[3] = newIntersections[1], newIntersections[1] = newIntersections[2], newIntersections[2] = newIntersections[3];

103
                if (newIntersections[0].x > newIntersections[1].x)

104
                    newIntersections[3] = newIntersections[0], newIntersections[0] = newIntersections[1], newIntersections[1] = newIntersections[3];

105
            }

106
        }

107
        for (int i = 0; i < newIntersectionCount; ++i) {

108
            if ((newIntersections[i].direction > 0) == !inside) {

109
                intersections.push_back(newIntersections[i]);

110
                inside = !inside;

111
            }

112
        }

113
        // Consistency check

114
        float rvScalar = median(rv[0], rv[1], rv[2]);

115
        if ((rvScalar > .5f) != inside && rvScalar != .5f && !intersections.empty()) {

116
            intersections.pop_back();

117
            inside = !inside;

118
        }

119
    }

120
#ifdef MSDFGEN_USE_CPP11

121
    line.setIntersections((std::vector<Scanline::Intersection> &&) intersections);

122
#else

123
    line.setIntersections(intersections);

124
#endif

125
}

126


127
void scanlineSDF(Scanline &line, const BitmapConstSection<float, 3> &sdf, const Projection &projection, double y, YAxisOrientation yAxisOrientation) {

128
    scanlineMSDF(line, sdf, projection, y, yAxisOrientation);

129
}

130
void scanlineSDF(Scanline &line, const BitmapConstSection<float, 4> &sdf, const Projection &projection, double y, YAxisOrientation yAxisOrientation) {

131
    scanlineMSDF(line, sdf, projection, y, yAxisOrientation);

132
}

133


134
template <int N>

135
double estimateSDFErrorInner(const BitmapConstSection<float, N> &sdf, const Shape &shape, const Projection &projection, int scanlinesPerRow, FillRule fillRule) {

136
    if (sdf.width <= 1 || sdf.height <= 1 || scanlinesPerRow < 1)

137
        return 0;

138
    double subRowSize = 1./scanlinesPerRow;

139
    double xFrom = projection.unprojectX(.5);

140
    double xTo = projection.unprojectX(sdf.width-.5);

141
    double overlapFactor = 1/(xTo-xFrom);

142
    double error = 0;

143
    Scanline refScanline, sdfScanline;

144
    for (int row = 0; row < sdf.height-1; ++row) {

145
        for (int subRow = 0; subRow < scanlinesPerRow; ++subRow) {

146
            double bt = (subRow+.5)*subRowSize;

147
            double y = projection.unprojectY(row+bt+.5);

148
            shape.scanline(refScanline, y);

149
            scanlineSDF(sdfScanline, sdf, projection, y, shape.getYAxisOrientation());

150
            error += 1-overlapFactor*Scanline::overlap(refScanline, sdfScanline, xFrom, xTo, fillRule);

151
        }

152
    }

153
    return error/((sdf.height-1)*scanlinesPerRow);

154
}

155


156
double estimateSDFError(const BitmapConstSection<float, 1> &sdf, const Shape &shape, const Projection &projection, int scanlinesPerRow, FillRule fillRule) {

157
    return estimateSDFErrorInner(sdf, shape, projection, scanlinesPerRow, fillRule);

158
}

159
double estimateSDFError(const BitmapConstSection<float, 3> &sdf, const Shape &shape, const Projection &projection, int scanlinesPerRow, FillRule fillRule) {

160
    return estimateSDFErrorInner(sdf, shape, projection, scanlinesPerRow, fillRule);

161
}

162
double estimateSDFError(const BitmapConstSection<float, 4> &sdf, const Shape &shape, const Projection &projection, int scanlinesPerRow, FillRule fillRule) {

163
    return estimateSDFErrorInner(sdf, shape, projection, scanlinesPerRow, fillRule);

164
}

165


166
// Legacy API

167


168
void scanlineSDF(Scanline &line, const BitmapConstSection<float, 1> &sdf, const Projection &projection, double y, bool inverseYAxis) {

169
    scanlineSDF(line, sdf, projection, y, inverseYAxis ? MSDFGEN_Y_AXIS_NONDEFAULT_ORIENTATION : MSDFGEN_Y_AXIS_DEFAULT_ORIENTATION);

170
}

171


172
void scanlineSDF(Scanline &line, const BitmapConstSection<float, 3> &sdf, const Projection &projection, double y, bool inverseYAxis) {

173
    scanlineSDF(line, sdf, projection, y, inverseYAxis ? MSDFGEN_Y_AXIS_NONDEFAULT_ORIENTATION : MSDFGEN_Y_AXIS_DEFAULT_ORIENTATION);

174
}

175


176
void scanlineSDF(Scanline &line, const BitmapConstSection<float, 4> &sdf, const Projection &projection, double y, bool inverseYAxis) {

177
    scanlineSDF(line, sdf, projection, y, inverseYAxis ? MSDFGEN_Y_AXIS_NONDEFAULT_ORIENTATION : MSDFGEN_Y_AXIS_DEFAULT_ORIENTATION);

178
}

179


180
void scanlineSDF(Scanline &line, const BitmapConstSection<float, 1> &sdf, const Vector2 &scale, const Vector2 &translate, bool inverseYAxis, double y) {

181
    scanlineSDF(line, sdf, Projection(scale, translate), y, inverseYAxis);

182
}

183


184
void scanlineSDF(Scanline &line, const BitmapConstSection<float, 3> &sdf, const Vector2 &scale, const Vector2 &translate, bool inverseYAxis, double y) {

185
    scanlineSDF(line, sdf, Projection(scale, translate), y, inverseYAxis);

186
}

187


188
void scanlineSDF(Scanline &line, const BitmapConstSection<float, 4> &sdf, const Vector2 &scale, const Vector2 &translate, bool inverseYAxis, double y) {

189
    scanlineSDF(line, sdf, Projection(scale, translate), y, inverseYAxis);

190
}

191


192
double estimateSDFError(const BitmapConstSection<float, 1> &sdf, const Shape &shape, const Vector2 &scale, const Vector2 &translate, int scanlinesPerRow, FillRule fillRule) {

193
    return estimateSDFError(sdf, shape, Projection(scale, translate), scanlinesPerRow, fillRule);

194
}

195


196
double estimateSDFError(const BitmapConstSection<float, 3> &sdf, const Shape &shape, const Vector2 &scale, const Vector2 &translate, int scanlinesPerRow, FillRule fillRule) {

197
    return estimateSDFError(sdf, shape, Projection(scale, translate), scanlinesPerRow, fillRule);

198
}

199


200
double estimateSDFError(const BitmapConstSection<float, 4> &sdf, const Shape &shape, const Vector2 &scale, const Vector2 &translate, int scanlinesPerRow, FillRule fillRule) {

201
    return estimateSDFError(sdf, shape, Projection(scale, translate), scanlinesPerRow, fillRule);

202
}

203


204
}

205


206