diff options
Diffstat (limited to 'thirdparty')
55 files changed, 5679 insertions, 0 deletions
diff --git a/thirdparty/README.md b/thirdparty/README.md index 1c310eae05..dd2f509516 100644 --- a/thirdparty/README.md +++ b/thirdparty/README.md @@ -482,6 +482,19 @@ Collection of single-file libraries used in Godot components. * License: BSD +## msdfgen + +- Upstream: https://github.com/Chlumsky/msdfgen +- Version: 1.9.1 (1b3b6b985094e6f12751177490add3ad11dd91a9, 2010) +- License: MIT + +Files extracted from the upstream source: + +- `msdfgen.h` +- Files in `core/` folder. +- `LICENSE.txt` and `CHANGELOG.md` + + ## nanosvg - Upstream: https://github.com/memononen/nanosvg diff --git a/thirdparty/msdfgen/CHANGELOG.md b/thirdparty/msdfgen/CHANGELOG.md new file mode 100644 index 0000000000..4b9a752650 --- /dev/null +++ b/thirdparty/msdfgen/CHANGELOG.md @@ -0,0 +1,82 @@ + +## Version 1.9 (2021-05-28) + +- Error correction of multi-channel distance fields has been completely reworked +- Added new edge coloring strategy that optimizes colors based on distances between edges +- Added some minor functions for the library API +- Minor code refactor and optimizations + +## Version 1.8 (2020-10-17) + +- Integrated the Skia library into the project, which is used to preprocess the shape geometry and eliminate any self-intersections and other irregularities previously unsupported by the software + - The scanline pass and overlapping contour mode is made obsolete by this step and has been disabled by default. The preprocess step can be disabled by the new `-nopreprocess` switch and the former enabled by `-scanline` and `-overlap` respectively. + - The project can be built without the Skia library, forgoing the geometry preprocessing feature. This is controlled by the macro definition `MSDFGEN_USE_SKIA` +- Significantly improved performance of the core algorithm by reusing results from previously computed pixels +- Introduced an additional error correction routine which eliminates MSDF artifacts by analytically predicting results of bilinear interpolation +- Added the possibility to load font glyphs by their index rather than a Unicode value (use the prefix `g` before the character code in `-font` argument) +- Added `-distanceshift` argument that can be used to adjust the center of the distance range in the output distance field +- Fixed several errors in the evaluation of curve distances +- Fixed an issue with paths containing convergent corners (those whose inner angle is zero) +- The algorithm for pseudo-distance computation slightly changed, fixing certain rare edge cases and improving consistency +- Added the ability to supply own `FT_Face` handle to the msdfgen library +- Minor refactor of the core algorithm + +### Version 1.7.1 (2020-03-09) + +- Fixed an edge case bug in scanline rasterization + +## Version 1.7 (2020-03-07) + +- Added `mtsdf` mode - a combination of `msdf` with `sdf` in the alpha channel +- Distance fields can now be stored as uncompressed TIFF image files with floating point precision +- Bitmap class refactor - template argument split into data type and number of channels, bitmap reference classes introduced +- Added a secondary "ink trap" edge coloring heuristic, can be selected using `-coloringstrategy inktrap` +- Added computation of estimated rendering error for a given SDF +- Added computation of bounding box that includes sharp mitered corners +- The API for bounds computation of the `Shape` class changed for clarity +- Fixed several edge case bugs + +## Version 1.6 (2019-04-08) + +- Core algorithm rewritten to split up advanced edge selection logic into modular template arguments. +- Pseudo-distance evaluation reworked to eliminate discontinuities at the midpoint between edges. +- MSDF error correction reworked to also fix distances away from edges and consider diagonal pairs. Code simplified. +- Added scanline rasterization support for `Shape`. +- Added a scanline pass in the standalone version, which corrects the signs in the distance field according to the selected fill rule (`-fillrule`). Can be disabled using `-noscanline`. +- Fixed autoframe scaling, which previously caused the output to have unnecessary empty border. +- `-guessorder` switch no longer enabled by default, as the functionality is now provided by the scanline pass. +- Updated FreeType and other libraries, changed to static linkage +- Added 64-bit and static library builds to the Visual Studio solution + +## Version 1.5 (2017-07-23) + +- Fixed rounding error in cubic curve splitting. +- SVG parser fixes and support for additional path commands. +- Added CMake build script. + +## Version 1.4 (2017-02-09) + +- Reworked contour combining logic to support overlapping contours. Original algorithm preserved in functions with `_legacy` suffix, which are invoked by the new `-legacy` switch. +- Fixed a severe bug in cubic curve distance computation, where a control point lies at the endpoint. +- Standalone version now automatically detects if the input has the wrong orientation and adjusts the distance field accordingly. Can be disabled by `-keeporder` or `-reverseorder` switch. +- SVG parser fixes and improvements. + +## Version 1.3 (2016-12-07) + +- Fixed `-reverseorder` switch. +- Fixed glyph loading to use the proper method of acquiring outlines from FreeType. + +## Version 1.2 (2016-07-20) + +- Added option to specify that shape vertices are listed in reverse order (`-reverseorder`). +- Added option to set a seed for the edge coloring heuristic (-seed \<n\>), which can be used to adjust the output. +- Fixed parsing of glyph contours that start with a curve control point. + +## Version 1.1 (2016-05-08) + +- Switched to MIT license due to popular demand. +- Fixed SDF rendering anti-aliasing when the output is smaller than the distance field. + +## Version 1.0 (2016-04-28) + +- Project published. diff --git a/thirdparty/msdfgen/LICENSE.txt b/thirdparty/msdfgen/LICENSE.txt new file mode 100644 index 0000000000..5fb05446bc --- /dev/null +++ b/thirdparty/msdfgen/LICENSE.txt @@ -0,0 +1,21 @@ +MIT License + +Copyright (c) 2016 Viktor Chlumsky + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/thirdparty/msdfgen/core/Bitmap.h b/thirdparty/msdfgen/core/Bitmap.h new file mode 100644 index 0000000000..14407d6c34 --- /dev/null +++ b/thirdparty/msdfgen/core/Bitmap.h @@ -0,0 +1,50 @@ + +#pragma once + +#include "BitmapRef.hpp" + +namespace msdfgen { + +/// A 2D image bitmap with N channels of type T. Pixel memory is managed by the class. +template <typename T, int N = 1> +class Bitmap { + +public: + Bitmap(); + Bitmap(int width, int height); + Bitmap(const BitmapConstRef<T, N> &orig); + Bitmap(const Bitmap<T, N> &orig); +#ifdef MSDFGEN_USE_CPP11 + Bitmap(Bitmap<T, N> &&orig); +#endif + ~Bitmap(); + Bitmap<T, N> & operator=(const BitmapConstRef<T, N> &orig); + Bitmap<T, N> & operator=(const Bitmap<T, N> &orig); +#ifdef MSDFGEN_USE_CPP11 + Bitmap<T, N> & operator=(Bitmap<T, N> &&orig); +#endif + /// Bitmap width in pixels. + int width() const; + /// Bitmap height in pixels. + int height() const; + T * operator()(int x, int y); + const T * operator()(int x, int y) const; +#ifdef MSDFGEN_USE_CPP11 + explicit operator T *(); + explicit operator const T *() const; +#else + operator T *(); + operator const T *() const; +#endif + operator BitmapRef<T, N>(); + operator BitmapConstRef<T, N>() const; + +private: + T *pixels; + int w, h; + +}; + +} + +#include "Bitmap.hpp" diff --git a/thirdparty/msdfgen/core/Bitmap.hpp b/thirdparty/msdfgen/core/Bitmap.hpp new file mode 100644 index 0000000000..cb16cac8d4 --- /dev/null +++ b/thirdparty/msdfgen/core/Bitmap.hpp @@ -0,0 +1,117 @@ + +#include "Bitmap.h" + +#include <cstdlib> +#include <cstring> + +namespace msdfgen { + +template <typename T, int N> +Bitmap<T, N>::Bitmap() : pixels(NULL), w(0), h(0) { } + +template <typename T, int N> +Bitmap<T, N>::Bitmap(int width, int height) : w(width), h(height) { + pixels = new T[N*w*h]; +} + +template <typename T, int N> +Bitmap<T, N>::Bitmap(const BitmapConstRef<T, N> &orig) : w(orig.width), h(orig.height) { + pixels = new T[N*w*h]; + memcpy(pixels, orig.pixels, sizeof(T)*N*w*h); +} + +template <typename T, int N> +Bitmap<T, N>::Bitmap(const Bitmap<T, N> &orig) : w(orig.w), h(orig.h) { + pixels = new T[N*w*h]; + memcpy(pixels, orig.pixels, sizeof(T)*N*w*h); +} + +#ifdef MSDFGEN_USE_CPP11 +template <typename T, int N> +Bitmap<T, N>::Bitmap(Bitmap<T, N> &&orig) : pixels(orig.pixels), w(orig.w), h(orig.h) { + orig.pixels = NULL; + orig.w = 0, orig.h = 0; +} +#endif + +template <typename T, int N> +Bitmap<T, N>::~Bitmap() { + delete [] pixels; +} + +template <typename T, int N> +Bitmap<T, N> & Bitmap<T, N>::operator=(const BitmapConstRef<T, N> &orig) { + if (pixels != orig.pixels) { + delete [] pixels; + w = orig.width, h = orig.height; + pixels = new T[N*w*h]; + memcpy(pixels, orig.pixels, sizeof(T)*N*w*h); + } + return *this; +} + +template <typename T, int N> +Bitmap<T, N> & Bitmap<T, N>::operator=(const Bitmap<T, N> &orig) { + if (this != &orig) { + delete [] pixels; + w = orig.w, h = orig.h; + pixels = new T[N*w*h]; + memcpy(pixels, orig.pixels, sizeof(T)*N*w*h); + } + return *this; +} + +#ifdef MSDFGEN_USE_CPP11 +template <typename T, int N> +Bitmap<T, N> & Bitmap<T, N>::operator=(Bitmap<T, N> &&orig) { + if (this != &orig) { + delete [] pixels; + pixels = orig.pixels; + w = orig.w, h = orig.h; + orig.pixels = NULL; + } + return *this; +} +#endif + +template <typename T, int N> +int Bitmap<T, N>::width() const { + return w; +} + +template <typename T, int N> +int Bitmap<T, N>::height() const { + return h; +} + +template <typename T, int N> +T * Bitmap<T, N>::operator()(int x, int y) { + return pixels+N*(w*y+x); +} + +template <typename T, int N> +const T * Bitmap<T, N>::operator()(int x, int y) const { + return pixels+N*(w*y+x); +} + +template <typename T, int N> +Bitmap<T, N>::operator T *() { + return pixels; +} + +template <typename T, int N> +Bitmap<T, N>::operator const T *() const { + return pixels; +} + +template <typename T, int N> +Bitmap<T, N>::operator BitmapRef<T, N>() { + return BitmapRef<T, N>(pixels, w, h); +} + +template <typename T, int N> +Bitmap<T, N>::operator BitmapConstRef<T, N>() const { + return BitmapConstRef<T, N>(pixels, w, h); +} + +} diff --git a/thirdparty/msdfgen/core/BitmapRef.hpp b/thirdparty/msdfgen/core/BitmapRef.hpp new file mode 100644 index 0000000000..6f9620dcdf --- /dev/null +++ b/thirdparty/msdfgen/core/BitmapRef.hpp @@ -0,0 +1,43 @@ + +#pragma once + +#include <cstdlib> + +namespace msdfgen { + +typedef unsigned char byte; + +/// Reference to a 2D image bitmap or a buffer acting as one. Pixel storage not owned or managed by the object. +template <typename T, int N = 1> +struct BitmapRef { + + T *pixels; + int width, height; + + inline BitmapRef() : pixels(NULL), width(0), height(0) { } + inline BitmapRef(T *pixels, int width, int height) : pixels(pixels), width(width), height(height) { } + + inline T * operator()(int x, int y) const { + return pixels+N*(width*y+x); + } + +}; + +/// Constant reference to a 2D image bitmap or a buffer acting as one. Pixel storage not owned or managed by the object. +template <typename T, int N = 1> +struct BitmapConstRef { + + const T *pixels; + int width, height; + + inline BitmapConstRef() : pixels(NULL), width(0), height(0) { } + inline BitmapConstRef(const T *pixels, int width, int height) : pixels(pixels), width(width), height(height) { } + inline BitmapConstRef(const BitmapRef<T, N> &orig) : pixels(orig.pixels), width(orig.width), height(orig.height) { } + + inline const T * operator()(int x, int y) const { + return pixels+N*(width*y+x); + } + +}; + +} diff --git a/thirdparty/msdfgen/core/Contour.cpp b/thirdparty/msdfgen/core/Contour.cpp new file mode 100644 index 0000000000..ca80d3c55a --- /dev/null +++ b/thirdparty/msdfgen/core/Contour.cpp @@ -0,0 +1,90 @@ + +#include "Contour.h" + +#include "arithmetics.hpp" + +namespace msdfgen { + +static double shoelace(const Point2 &a, const Point2 &b) { + return (b.x-a.x)*(a.y+b.y); +} + +void Contour::addEdge(const EdgeHolder &edge) { + edges.push_back(edge); +} + +#ifdef MSDFGEN_USE_CPP11 +void Contour::addEdge(EdgeHolder &&edge) { + edges.push_back((EdgeHolder &&) edge); +} +#endif + +EdgeHolder & Contour::addEdge() { + edges.resize(edges.size()+1); + return edges.back(); +} + +static void boundPoint(double &l, double &b, double &r, double &t, Point2 p) { + if (p.x < l) l = p.x; + if (p.y < b) b = p.y; + if (p.x > r) r = p.x; + if (p.y > t) t = p.y; +} + +void Contour::bound(double &l, double &b, double &r, double &t) const { + for (std::vector<EdgeHolder>::const_iterator edge = edges.begin(); edge != edges.end(); ++edge) + (*edge)->bound(l, b, r, t); +} + +void Contour::boundMiters(double &l, double &b, double &r, double &t, double border, double miterLimit, int polarity) const { + if (edges.empty()) + return; + Vector2 prevDir = edges.back()->direction(1).normalize(true); + for (std::vector<EdgeHolder>::const_iterator edge = edges.begin(); edge != edges.end(); ++edge) { + Vector2 dir = -(*edge)->direction(0).normalize(true); + if (polarity*crossProduct(prevDir, dir) >= 0) { + double miterLength = miterLimit; + double q = .5*(1-dotProduct(prevDir, dir)); + if (q > 0) + miterLength = min(1/sqrt(q), miterLimit); + Point2 miter = (*edge)->point(0)+border*miterLength*(prevDir+dir).normalize(true); + boundPoint(l, b, r, t, miter); + } + prevDir = (*edge)->direction(1).normalize(true); + } +} + +int Contour::winding() const { + if (edges.empty()) + return 0; + double total = 0; + if (edges.size() == 1) { + Point2 a = edges[0]->point(0), b = edges[0]->point(1/3.), c = edges[0]->point(2/3.); + total += shoelace(a, b); + total += shoelace(b, c); + total += shoelace(c, a); + } else if (edges.size() == 2) { + Point2 a = edges[0]->point(0), b = edges[0]->point(.5), c = edges[1]->point(0), d = edges[1]->point(.5); + total += shoelace(a, b); + total += shoelace(b, c); + total += shoelace(c, d); + total += shoelace(d, a); + } else { + Point2 prev = edges.back()->point(0); + for (std::vector<EdgeHolder>::const_iterator edge = edges.begin(); edge != edges.end(); ++edge) { + Point2 cur = (*edge)->point(0); + total += shoelace(prev, cur); + prev = cur; + } + } + return sign(total); +} + +void Contour::reverse() { + for (int i = (int) edges.size()/2; i > 0; --i) + EdgeHolder::swap(edges[i-1], edges[edges.size()-i]); + for (std::vector<EdgeHolder>::iterator edge = edges.begin(); edge != edges.end(); ++edge) + (*edge)->reverse(); +} + +} diff --git a/thirdparty/msdfgen/core/Contour.h b/thirdparty/msdfgen/core/Contour.h new file mode 100644 index 0000000000..f79b269582 --- /dev/null +++ b/thirdparty/msdfgen/core/Contour.h @@ -0,0 +1,34 @@ + +#pragma once + +#include <vector> +#include "EdgeHolder.h" + +namespace msdfgen { + +/// A single closed contour of a shape. +class Contour { + +public: + /// The sequence of edges that make up the contour. + std::vector<EdgeHolder> edges; + + /// Adds an edge to the contour. + void addEdge(const EdgeHolder &edge); +#ifdef MSDFGEN_USE_CPP11 + void addEdge(EdgeHolder &&edge); +#endif + /// Creates a new edge in the contour and returns its reference. + EdgeHolder & addEdge(); + /// Adjusts the bounding box to fit the contour. + void bound(double &l, double &b, double &r, double &t) const; + /// Adjusts the bounding box to fit the contour border's mitered corners. + void boundMiters(double &l, double &b, double &r, double &t, double border, double miterLimit, int polarity) const; + /// Computes the winding of the contour. Returns 1 if positive, -1 if negative. + int winding() const; + /// Reverses the sequence of edges on the contour. + void reverse(); + +}; + +} diff --git a/thirdparty/msdfgen/core/EdgeColor.h b/thirdparty/msdfgen/core/EdgeColor.h new file mode 100644 index 0000000000..9d49a5a89e --- /dev/null +++ b/thirdparty/msdfgen/core/EdgeColor.h @@ -0,0 +1,18 @@ + +#pragma once + +namespace msdfgen { + +/// Edge color specifies which color channels an edge belongs to. +enum EdgeColor { + BLACK = 0, + RED = 1, + GREEN = 2, + YELLOW = 3, + BLUE = 4, + MAGENTA = 5, + CYAN = 6, + WHITE = 7 +}; + +} diff --git a/thirdparty/msdfgen/core/EdgeHolder.cpp b/thirdparty/msdfgen/core/EdgeHolder.cpp new file mode 100644 index 0000000000..1a8c5f66e9 --- /dev/null +++ b/thirdparty/msdfgen/core/EdgeHolder.cpp @@ -0,0 +1,77 @@ + +#include "EdgeHolder.h" + +namespace msdfgen { + +void EdgeHolder::swap(EdgeHolder &a, EdgeHolder &b) { + EdgeSegment *tmp = a.edgeSegment; + a.edgeSegment = b.edgeSegment; + b.edgeSegment = tmp; +} + +EdgeHolder::EdgeHolder() : edgeSegment(NULL) { } + +EdgeHolder::EdgeHolder(EdgeSegment *segment) : edgeSegment(segment) { } + +EdgeHolder::EdgeHolder(Point2 p0, Point2 p1, EdgeColor edgeColor) : edgeSegment(new LinearSegment(p0, p1, edgeColor)) { } + +EdgeHolder::EdgeHolder(Point2 p0, Point2 p1, Point2 p2, EdgeColor edgeColor) : edgeSegment(new QuadraticSegment(p0, p1, p2, edgeColor)) { } + +EdgeHolder::EdgeHolder(Point2 p0, Point2 p1, Point2 p2, Point2 p3, EdgeColor edgeColor) : edgeSegment(new CubicSegment(p0, p1, p2, p3, edgeColor)) { } + +EdgeHolder::EdgeHolder(const EdgeHolder &orig) : edgeSegment(orig.edgeSegment ? orig.edgeSegment->clone() : NULL) { } + +#ifdef MSDFGEN_USE_CPP11 +EdgeHolder::EdgeHolder(EdgeHolder &&orig) : edgeSegment(orig.edgeSegment) { + orig.edgeSegment = NULL; +} +#endif + +EdgeHolder::~EdgeHolder() { + delete edgeSegment; +} + +EdgeHolder & EdgeHolder::operator=(const EdgeHolder &orig) { + if (this != &orig) { + delete edgeSegment; + edgeSegment = orig.edgeSegment ? orig.edgeSegment->clone() : NULL; + } + return *this; +} + +#ifdef MSDFGEN_USE_CPP11 +EdgeHolder & EdgeHolder::operator=(EdgeHolder &&orig) { + if (this != &orig) { + delete edgeSegment; + edgeSegment = orig.edgeSegment; + orig.edgeSegment = NULL; + } + return *this; +} +#endif + +EdgeSegment & EdgeHolder::operator*() { + return *edgeSegment; +} + +const EdgeSegment & EdgeHolder::operator*() const { + return *edgeSegment; +} + +EdgeSegment * EdgeHolder::operator->() { + return edgeSegment; +} + +const EdgeSegment * EdgeHolder::operator->() const { + return edgeSegment; +} + +EdgeHolder::operator EdgeSegment *() { + return edgeSegment; +} + +EdgeHolder::operator const EdgeSegment *() const { + return edgeSegment; +} + +} diff --git a/thirdparty/msdfgen/core/EdgeHolder.h b/thirdparty/msdfgen/core/EdgeHolder.h new file mode 100644 index 0000000000..c4c5be7616 --- /dev/null +++ b/thirdparty/msdfgen/core/EdgeHolder.h @@ -0,0 +1,41 @@ + +#pragma once + +#include "edge-segments.h" + +namespace msdfgen { + +/// Container for a single edge of dynamic type. +class EdgeHolder { + +public: + /// Swaps the edges held by a and b. + static void swap(EdgeHolder &a, EdgeHolder &b); + + EdgeHolder(); + EdgeHolder(EdgeSegment *segment); + EdgeHolder(Point2 p0, Point2 p1, EdgeColor edgeColor = WHITE); + EdgeHolder(Point2 p0, Point2 p1, Point2 p2, EdgeColor edgeColor = WHITE); + EdgeHolder(Point2 p0, Point2 p1, Point2 p2, Point2 p3, EdgeColor edgeColor = WHITE); + EdgeHolder(const EdgeHolder &orig); +#ifdef MSDFGEN_USE_CPP11 + EdgeHolder(EdgeHolder &&orig); +#endif + ~EdgeHolder(); + EdgeHolder & operator=(const EdgeHolder &orig); +#ifdef MSDFGEN_USE_CPP11 + EdgeHolder & operator=(EdgeHolder &&orig); +#endif + EdgeSegment & operator*(); + const EdgeSegment & operator*() const; + EdgeSegment * operator->(); + const EdgeSegment * operator->() const; + operator EdgeSegment *(); + operator const EdgeSegment *() const; + +private: + EdgeSegment *edgeSegment; + +}; + +} diff --git a/thirdparty/msdfgen/core/MSDFErrorCorrection.cpp b/thirdparty/msdfgen/core/MSDFErrorCorrection.cpp new file mode 100644 index 0000000000..7918597fd2 --- /dev/null +++ b/thirdparty/msdfgen/core/MSDFErrorCorrection.cpp @@ -0,0 +1,495 @@ + +#include "MSDFErrorCorrection.h" + +#include <cstring> +#include "arithmetics.hpp" +#include "equation-solver.h" +#include "EdgeColor.h" +#include "bitmap-interpolation.hpp" +#include "edge-selectors.h" +#include "contour-combiners.h" +#include "ShapeDistanceFinder.h" +#include "generator-config.h" + +namespace msdfgen { + +#define ARTIFACT_T_EPSILON .01 +#define PROTECTION_RADIUS_TOLERANCE 1.001 + +#define CLASSIFIER_FLAG_CANDIDATE 0x01 +#define CLASSIFIER_FLAG_ARTIFACT 0x02 + +const double ErrorCorrectionConfig::defaultMinDeviationRatio = 1.11111111111111111; +const double ErrorCorrectionConfig::defaultMinImproveRatio = 1.11111111111111111; + +/// The base artifact classifier recognizes artifacts based on the contents of the SDF alone. +class BaseArtifactClassifier { +public: + inline BaseArtifactClassifier(double span, bool protectedFlag) : span(span), protectedFlag(protectedFlag) { } + /// Evaluates if the median value xm interpolated at xt in the range between am at at and bm at bt indicates an artifact. + inline int rangeTest(double at, double bt, double xt, float am, float bm, float xm) const { + // For protected texels, only consider inversion artifacts (interpolated median has different sign than boundaries). For the rest, it is sufficient that the interpolated median is outside its boundaries. + if ((am > .5f && bm > .5f && xm <= .5f) || (am < .5f && bm < .5f && xm >= .5f) || (!protectedFlag && median(am, bm, xm) != xm)) { + double axSpan = (xt-at)*span, bxSpan = (bt-xt)*span; + // Check if the interpolated median's value is in the expected range based on its distance (span) from boundaries a, b. + if (!(xm >= am-axSpan && xm <= am+axSpan && xm >= bm-bxSpan && xm <= bm+bxSpan)) + return CLASSIFIER_FLAG_CANDIDATE|CLASSIFIER_FLAG_ARTIFACT; + return CLASSIFIER_FLAG_CANDIDATE; + } + return 0; + } + /// Returns true if the combined results of the tests performed on the median value m interpolated at t indicate an artifact. + inline bool evaluate(double t, float m, int flags) const { + return (flags&2) != 0; + } +private: + double span; + bool protectedFlag; +}; + +/// The shape distance checker evaluates the exact shape distance to find additional artifacts at a significant performance cost. +template <template <typename> class ContourCombiner, int N> +class ShapeDistanceChecker { +public: + class ArtifactClassifier : public BaseArtifactClassifier { + public: + inline ArtifactClassifier(ShapeDistanceChecker *parent, const Vector2 &direction, double span) : BaseArtifactClassifier(span, parent->protectedFlag), parent(parent), direction(direction) { } + /// Returns true if the combined results of the tests performed on the median value m interpolated at t indicate an artifact. + inline bool evaluate(double t, float m, int flags) const { + if (flags&CLASSIFIER_FLAG_CANDIDATE) { + // Skip expensive distance evaluation if the point has already been classified as an artifact by the base classifier. + if (flags&CLASSIFIER_FLAG_ARTIFACT) + return true; + Vector2 tVector = t*direction; + float oldMSD[N], newMSD[3]; + // Compute the color that would be currently interpolated at the artifact candidate's position. + Point2 sdfCoord = parent->sdfCoord+tVector; + interpolate(oldMSD, parent->sdf, sdfCoord); + // Compute the color that would be interpolated at the artifact candidate's position if error correction was applied on the current texel. + double aWeight = (1-fabs(tVector.x))*(1-fabs(tVector.y)); + float aPSD = median(parent->msd[0], parent->msd[1], parent->msd[2]); + newMSD[0] = float(oldMSD[0]+aWeight*(aPSD-parent->msd[0])); + newMSD[1] = float(oldMSD[1]+aWeight*(aPSD-parent->msd[1])); + newMSD[2] = float(oldMSD[2]+aWeight*(aPSD-parent->msd[2])); + // Compute the evaluated distance (interpolated median) before and after error correction, as well as the exact shape distance. + float oldPSD = median(oldMSD[0], oldMSD[1], oldMSD[2]); + float newPSD = median(newMSD[0], newMSD[1], newMSD[2]); + float refPSD = float(parent->invRange*parent->distanceFinder.distance(parent->shapeCoord+tVector*parent->texelSize)+.5); + // Compare the differences of the exact distance and the before and after distances. + return parent->minImproveRatio*fabsf(newPSD-refPSD) < double(fabsf(oldPSD-refPSD)); + } + return false; + } + private: + ShapeDistanceChecker *parent; + Vector2 direction; + }; + Point2 shapeCoord, sdfCoord; + const float *msd; + bool protectedFlag; + inline ShapeDistanceChecker(const BitmapConstRef<float, N> &sdf, const Shape &shape, const Projection &projection, double invRange, double minImproveRatio) : distanceFinder(shape), sdf(sdf), invRange(invRange), minImproveRatio(minImproveRatio) { + texelSize = projection.unprojectVector(Vector2(1)); + } + inline ArtifactClassifier classifier(const Vector2 &direction, double span) { + return ArtifactClassifier(this, direction, span); + } +private: + ShapeDistanceFinder<ContourCombiner<PseudoDistanceSelector> > distanceFinder; + BitmapConstRef<float, N> sdf; + double invRange; + Vector2 texelSize; + double minImproveRatio; +}; + +MSDFErrorCorrection::MSDFErrorCorrection() { } + +MSDFErrorCorrection::MSDFErrorCorrection(const BitmapRef<byte, 1> &stencil, const Projection &projection, double range) : stencil(stencil), projection(projection) { + invRange = 1/range; + minDeviationRatio = ErrorCorrectionConfig::defaultMinDeviationRatio; + minImproveRatio = ErrorCorrectionConfig::defaultMinImproveRatio; + memset(stencil.pixels, 0, sizeof(byte)*stencil.width*stencil.height); +} + +void MSDFErrorCorrection::setMinDeviationRatio(double minDeviationRatio) { + this->minDeviationRatio = minDeviationRatio; +} + +void MSDFErrorCorrection::setMinImproveRatio(double minImproveRatio) { + this->minImproveRatio = minImproveRatio; +} + +void MSDFErrorCorrection::protectCorners(const Shape &shape) { + for (std::vector<Contour>::const_iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour) + if (!contour->edges.empty()) { + const EdgeSegment *prevEdge = contour->edges.back(); + for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) { + int commonColor = prevEdge->color&(*edge)->color; + // If the color changes from prevEdge to edge, this is a corner. + if (!(commonColor&(commonColor-1))) { + // Find the four texels that envelop the corner and mark them as protected. + Point2 p = projection.project((*edge)->point(0)); + if (shape.inverseYAxis) + p.y = stencil.height-p.y; + int l = (int) floor(p.x-.5); + int b = (int) floor(p.y-.5); + int r = l+1; + int t = b+1; + // Check that the positions are within bounds. + if (l < stencil.width && b < stencil.height && r >= 0 && t >= 0) { + if (l >= 0 && b >= 0) + *stencil(l, b) |= (byte) PROTECTED; + if (r < stencil.width && b >= 0) + *stencil(r, b) |= (byte) PROTECTED; + if (l >= 0 && t < stencil.height) + *stencil(l, t) |= (byte) PROTECTED; + if (r < stencil.width && t < stencil.height) + *stencil(r, t) |= (byte) PROTECTED; + } + } + prevEdge = *edge; + } + } +} + +/// Determines if the channel contributes to an edge between the two texels a, b. +static bool edgeBetweenTexelsChannel(const float *a, const float *b, int channel) { + // Find interpolation ratio t (0 < t < 1) where an edge is expected (mix(a[channel], b[channel], t) == 0.5). + double t = (a[channel]-.5)/(a[channel]-b[channel]); + if (t > 0 && t < 1) { + // Interpolate channel values at t. + float c[3] = { + mix(a[0], b[0], t), + mix(a[1], b[1], t), + mix(a[2], b[2], t) + }; + // This is only an edge if the zero-distance channel is the median. + return median(c[0], c[1], c[2]) == c[channel]; + } + return false; +} + +/// Returns a bit mask of which channels contribute to an edge between the two texels a, b. +static int edgeBetweenTexels(const float *a, const float *b) { + return ( + RED*edgeBetweenTexelsChannel(a, b, 0)+ + GREEN*edgeBetweenTexelsChannel(a, b, 1)+ + BLUE*edgeBetweenTexelsChannel(a, b, 2) + ); +} + +/// Marks texel as protected if one of its non-median channels is present in the channel mask. +static void protectExtremeChannels(byte *stencil, const float *msd, float m, int mask) { + if ( + (mask&RED && msd[0] != m) || + (mask&GREEN && msd[1] != m) || + (mask&BLUE && msd[2] != m) + ) + *stencil |= (byte) MSDFErrorCorrection::PROTECTED; +} + +template <int N> +void MSDFErrorCorrection::protectEdges(const BitmapConstRef<float, N> &sdf) { + float radius; + // Horizontal texel pairs + radius = float(PROTECTION_RADIUS_TOLERANCE*projection.unprojectVector(Vector2(invRange, 0)).length()); + for (int y = 0; y < sdf.height; ++y) { + const float *left = sdf(0, y); + const float *right = sdf(1, y); + for (int x = 0; x < sdf.width-1; ++x) { + float lm = median(left[0], left[1], left[2]); + float rm = median(right[0], right[1], right[2]); + if (fabsf(lm-.5f)+fabsf(rm-.5f) < radius) { + int mask = edgeBetweenTexels(left, right); + protectExtremeChannels(stencil(x, y), left, lm, mask); + protectExtremeChannels(stencil(x+1, y), right, rm, mask); + } + left += N, right += N; + } + } + // Vertical texel pairs + radius = float(PROTECTION_RADIUS_TOLERANCE*projection.unprojectVector(Vector2(0, invRange)).length()); + for (int y = 0; y < sdf.height-1; ++y) { + const float *bottom = sdf(0, y); + const float *top = sdf(0, y+1); + for (int x = 0; x < sdf.width; ++x) { + float bm = median(bottom[0], bottom[1], bottom[2]); + float tm = median(top[0], top[1], top[2]); + if (fabsf(bm-.5f)+fabsf(tm-.5f) < radius) { + int mask = edgeBetweenTexels(bottom, top); + protectExtremeChannels(stencil(x, y), bottom, bm, mask); + protectExtremeChannels(stencil(x, y+1), top, tm, mask); + } + bottom += N, top += N; + } + } + // Diagonal texel pairs + radius = float(PROTECTION_RADIUS_TOLERANCE*projection.unprojectVector(Vector2(invRange)).length()); + for (int y = 0; y < sdf.height-1; ++y) { + const float *lb = sdf(0, y); + const float *rb = sdf(1, y); + const float *lt = sdf(0, y+1); + const float *rt = sdf(1, y+1); + for (int x = 0; x < sdf.width-1; ++x) { + float mlb = median(lb[0], lb[1], lb[2]); + float mrb = median(rb[0], rb[1], rb[2]); + float mlt = median(lt[0], lt[1], lt[2]); + float mrt = median(rt[0], rt[1], rt[2]); + if (fabsf(mlb-.5f)+fabsf(mrt-.5f) < radius) { + int mask = edgeBetweenTexels(lb, rt); + protectExtremeChannels(stencil(x, y), lb, mlb, mask); + protectExtremeChannels(stencil(x+1, y+1), rt, mrt, mask); + } + if (fabsf(mrb-.5f)+fabsf(mlt-.5f) < radius) { + int mask = edgeBetweenTexels(rb, lt); + protectExtremeChannels(stencil(x+1, y), rb, mrb, mask); + protectExtremeChannels(stencil(x, y+1), lt, mlt, mask); + } + lb += N, rb += N, lt += N, rt += N; + } + } +} + +void MSDFErrorCorrection::protectAll() { + byte *end = stencil.pixels+stencil.width*stencil.height; + for (byte *mask = stencil.pixels; mask < end; ++mask) + *mask |= (byte) PROTECTED; +} + +/// Returns the median of the linear interpolation of texels a, b at t. +static float interpolatedMedian(const float *a, const float *b, double t) { + return median( + mix(a[0], b[0], t), + mix(a[1], b[1], t), + mix(a[2], b[2], t) + ); +} +/// Returns the median of the bilinear interpolation with the given constant, linear, and quadratic terms at t. +static float interpolatedMedian(const float *a, const float *l, const float *q, double t) { + return float(median( + t*(t*q[0]+l[0])+a[0], + t*(t*q[1]+l[1])+a[1], + t*(t*q[2]+l[2])+a[2] + )); +} + +/// Determines if the interpolated median xm is an artifact. +static bool isArtifact(bool isProtected, double axSpan, double bxSpan, float am, float bm, float xm) { + return ( + // For protected texels, only report an artifact if it would cause fill inversion (change between positive and negative distance). + (!isProtected || (am > .5f && bm > .5f && xm <= .5f) || (am < .5f && bm < .5f && xm >= .5f)) && + // This is an artifact if the interpolated median is outside the range of possible values based on its distance from a, b. + !(xm >= am-axSpan && xm <= am+axSpan && xm >= bm-bxSpan && xm <= bm+bxSpan) + ); +} + +/// Checks if a linear interpolation artifact will occur at a point where two specific color channels are equal - such points have extreme median values. +template <class ArtifactClassifier> +static bool hasLinearArtifactInner(const ArtifactClassifier &artifactClassifier, float am, float bm, const float *a, const float *b, float dA, float dB) { + // Find interpolation ratio t (0 < t < 1) where two color channels are equal (mix(dA, dB, t) == 0). + double t = (double) dA/(dA-dB); + if (t > ARTIFACT_T_EPSILON && t < 1-ARTIFACT_T_EPSILON) { + // Interpolate median at t and let the classifier decide if its value indicates an artifact. + float xm = interpolatedMedian(a, b, t); + return artifactClassifier.evaluate(t, xm, artifactClassifier.rangeTest(0, 1, t, am, bm, xm)); + } + return false; +} + +/// Checks if a bilinear interpolation artifact will occur at a point where two specific color channels are equal - such points have extreme median values. +template <class ArtifactClassifier> +static bool hasDiagonalArtifactInner(const ArtifactClassifier &artifactClassifier, float am, float dm, const float *a, const float *l, const float *q, float dA, float dBC, float dD, double tEx0, double tEx1) { + // Find interpolation ratios t (0 < t[i] < 1) where two color channels are equal. + double t[2]; + int solutions = solveQuadratic(t, dD-dBC+dA, dBC-dA-dA, dA); + for (int i = 0; i < solutions; ++i) { + // Solutions t[i] == 0 and t[i] == 1 are singularities and occur very often because two channels are usually equal at texels. + if (t[i] > ARTIFACT_T_EPSILON && t[i] < 1-ARTIFACT_T_EPSILON) { + // Interpolate median xm at t. + float xm = interpolatedMedian(a, l, q, t[i]); + // Determine if xm deviates too much from medians of a, d. + int rangeFlags = artifactClassifier.rangeTest(0, 1, t[i], am, dm, xm); + // Additionally, check xm against the interpolated medians at the local extremes tEx0, tEx1. + double tEnd[2]; + float em[2]; + // tEx0 + if (tEx0 > 0 && tEx0 < 1) { + tEnd[0] = 0, tEnd[1] = 1; + em[0] = am, em[1] = dm; + tEnd[tEx0 > t[i]] = tEx0; + em[tEx0 > t[i]] = interpolatedMedian(a, l, q, tEx0); + rangeFlags |= artifactClassifier.rangeTest(tEnd[0], tEnd[1], t[i], am, dm, xm); + } + // tEx1 + if (tEx1 > 0 && tEx1 < 1) { + tEnd[0] = 0, tEnd[1] = 1; + em[0] = am, em[1] = dm; + tEnd[tEx1 > t[i]] = tEx1; + em[tEx1 > t[i]] = interpolatedMedian(a, l, q, tEx1); + rangeFlags |= artifactClassifier.rangeTest(tEnd[0], tEnd[1], t[i], am, dm, xm); + } + if (artifactClassifier.evaluate(t[i], xm, rangeFlags)) + return true; + } + } + return false; +} + +/// Checks if a linear interpolation artifact will occur inbetween two horizontally or vertically adjacent texels a, b. +template <class ArtifactClassifier> +static bool hasLinearArtifact(const ArtifactClassifier &artifactClassifier, float am, const float *a, const float *b) { + float bm = median(b[0], b[1], b[2]); + return ( + // Out of the pair, only report artifacts for the texel further from the edge to minimize side effects. + fabsf(am-.5f) >= fabsf(bm-.5f) && ( + // Check points where each pair of color channels meets. + hasLinearArtifactInner(artifactClassifier, am, bm, a, b, a[1]-a[0], b[1]-b[0]) || + hasLinearArtifactInner(artifactClassifier, am, bm, a, b, a[2]-a[1], b[2]-b[1]) || + hasLinearArtifactInner(artifactClassifier, am, bm, a, b, a[0]-a[2], b[0]-b[2]) + ) + ); +} + +/// Checks if a bilinear interpolation artifact will occur inbetween two diagonally adjacent texels a, d (with b, c forming the other diagonal). +template <class ArtifactClassifier> +static bool hasDiagonalArtifact(const ArtifactClassifier &artifactClassifier, float am, const float *a, const float *b, const float *c, const float *d) { + float dm = median(d[0], d[1], d[2]); + // Out of the pair, only report artifacts for the texel further from the edge to minimize side effects. + if (fabsf(am-.5f) >= fabsf(dm-.5f)) { + float abc[3] = { + a[0]-b[0]-c[0], + a[1]-b[1]-c[1], + a[2]-b[2]-c[2] + }; + // Compute the linear terms for bilinear interpolation. + float l[3] = { + -a[0]-abc[0], + -a[1]-abc[1], + -a[2]-abc[2] + }; + // Compute the quadratic terms for bilinear interpolation. + float q[3] = { + d[0]+abc[0], + d[1]+abc[1], + d[2]+abc[2] + }; + // Compute interpolation ratios tEx (0 < tEx[i] < 1) for the local extremes of each color channel (the derivative 2*q[i]*tEx[i]+l[i] == 0). + double tEx[3] = { + -.5*l[0]/q[0], + -.5*l[1]/q[1], + -.5*l[2]/q[2] + }; + // Check points where each pair of color channels meets. + return ( + hasDiagonalArtifactInner(artifactClassifier, am, dm, a, l, q, a[1]-a[0], b[1]-b[0]+c[1]-c[0], d[1]-d[0], tEx[0], tEx[1]) || + hasDiagonalArtifactInner(artifactClassifier, am, dm, a, l, q, a[2]-a[1], b[2]-b[1]+c[2]-c[1], d[2]-d[1], tEx[1], tEx[2]) || + hasDiagonalArtifactInner(artifactClassifier, am, dm, a, l, q, a[0]-a[2], b[0]-b[2]+c[0]-c[2], d[0]-d[2], tEx[2], tEx[0]) + ); + } + return false; +} + +template <int N> +void MSDFErrorCorrection::findErrors(const BitmapConstRef<float, N> &sdf) { + // Compute the expected deltas between values of horizontally, vertically, and diagonally adjacent texels. + double hSpan = minDeviationRatio*projection.unprojectVector(Vector2(invRange, 0)).length(); + double vSpan = minDeviationRatio*projection.unprojectVector(Vector2(0, invRange)).length(); + double dSpan = minDeviationRatio*projection.unprojectVector(Vector2(invRange)).length(); + // Inspect all texels. + for (int y = 0; y < sdf.height; ++y) { + for (int x = 0; x < sdf.width; ++x) { + const float *c = sdf(x, y); + float cm = median(c[0], c[1], c[2]); + bool protectedFlag = (*stencil(x, y)&PROTECTED) != 0; + const float *l = NULL, *b = NULL, *r = NULL, *t = NULL; + // Mark current texel c with the error flag if an artifact occurs when it's interpolated with any of its 8 neighbors. + *stencil(x, y) |= (byte) (ERROR*( + (x > 0 && ((l = sdf(x-1, y)), hasLinearArtifact(BaseArtifactClassifier(hSpan, protectedFlag), cm, c, l))) || + (y > 0 && ((b = sdf(x, y-1)), hasLinearArtifact(BaseArtifactClassifier(vSpan, protectedFlag), cm, c, b))) || + (x < sdf.width-1 && ((r = sdf(x+1, y)), hasLinearArtifact(BaseArtifactClassifier(hSpan, protectedFlag), cm, c, r))) || + (y < sdf.height-1 && ((t = sdf(x, y+1)), hasLinearArtifact(BaseArtifactClassifier(vSpan, protectedFlag), cm, c, t))) || + (x > 0 && y > 0 && hasDiagonalArtifact(BaseArtifactClassifier(dSpan, protectedFlag), cm, c, l, b, sdf(x-1, y-1))) || + (x < sdf.width-1 && y > 0 && hasDiagonalArtifact(BaseArtifactClassifier(dSpan, protectedFlag), cm, c, r, b, sdf(x+1, y-1))) || + (x > 0 && y < sdf.height-1 && hasDiagonalArtifact(BaseArtifactClassifier(dSpan, protectedFlag), cm, c, l, t, sdf(x-1, y+1))) || + (x < sdf.width-1 && y < sdf.height-1 && hasDiagonalArtifact(BaseArtifactClassifier(dSpan, protectedFlag), cm, c, r, t, sdf(x+1, y+1))) + )); + } + } +} + +template <template <typename> class ContourCombiner, int N> +void MSDFErrorCorrection::findErrors(const BitmapConstRef<float, N> &sdf, const Shape &shape) { + // Compute the expected deltas between values of horizontally, vertically, and diagonally adjacent texels. + double hSpan = minDeviationRatio*projection.unprojectVector(Vector2(invRange, 0)).length(); + double vSpan = minDeviationRatio*projection.unprojectVector(Vector2(0, invRange)).length(); + double dSpan = minDeviationRatio*projection.unprojectVector(Vector2(invRange)).length(); +#ifdef MSDFGEN_USE_OPENMP + #pragma omp parallel +#endif + { + ShapeDistanceChecker<ContourCombiner, N> shapeDistanceChecker(sdf, shape, projection, invRange, minImproveRatio); + bool rightToLeft = false; + // Inspect all texels. +#ifdef MSDFGEN_USE_OPENMP + #pragma omp for +#endif + for (int y = 0; y < sdf.height; ++y) { + int row = shape.inverseYAxis ? sdf.height-y-1 : y; + for (int col = 0; col < sdf.width; ++col) { + int x = rightToLeft ? sdf.width-col-1 : col; + if ((*stencil(x, row)&ERROR)) + continue; + const float *c = sdf(x, row); + shapeDistanceChecker.shapeCoord = projection.unproject(Point2(x+.5, y+.5)); + shapeDistanceChecker.sdfCoord = Point2(x+.5, row+.5); + shapeDistanceChecker.msd = c; + shapeDistanceChecker.protectedFlag = (*stencil(x, row)&PROTECTED) != 0; + float cm = median(c[0], c[1], c[2]); + const float *l = NULL, *b = NULL, *r = NULL, *t = NULL; + // Mark current texel c with the error flag if an artifact occurs when it's interpolated with any of its 8 neighbors. + *stencil(x, row) |= (byte) (ERROR*( + (x > 0 && ((l = sdf(x-1, row)), hasLinearArtifact(shapeDistanceChecker.classifier(Vector2(-1, 0), hSpan), cm, c, l))) || + (row > 0 && ((b = sdf(x, row-1)), hasLinearArtifact(shapeDistanceChecker.classifier(Vector2(0, -1), vSpan), cm, c, b))) || + (x < sdf.width-1 && ((r = sdf(x+1, row)), hasLinearArtifact(shapeDistanceChecker.classifier(Vector2(+1, 0), hSpan), cm, c, r))) || + (row < sdf.height-1 && ((t = sdf(x, row+1)), hasLinearArtifact(shapeDistanceChecker.classifier(Vector2(0, +1), vSpan), cm, c, t))) || + (x > 0 && row > 0 && hasDiagonalArtifact(shapeDistanceChecker.classifier(Vector2(-1, -1), dSpan), cm, c, l, b, sdf(x-1, row-1))) || + (x < sdf.width-1 && row > 0 && hasDiagonalArtifact(shapeDistanceChecker.classifier(Vector2(+1, -1), dSpan), cm, c, r, b, sdf(x+1, row-1))) || + (x > 0 && row < sdf.height-1 && hasDiagonalArtifact(shapeDistanceChecker.classifier(Vector2(-1, +1), dSpan), cm, c, l, t, sdf(x-1, row+1))) || + (x < sdf.width-1 && row < sdf.height-1 && hasDiagonalArtifact(shapeDistanceChecker.classifier(Vector2(+1, +1), dSpan), cm, c, r, t, sdf(x+1, row+1))) + )); + } + } + } +} + +template <int N> +void MSDFErrorCorrection::apply(const BitmapRef<float, N> &sdf) const { + int texelCount = sdf.width*sdf.height; + const byte *mask = stencil.pixels; + float *texel = sdf.pixels; + for (int i = 0; i < texelCount; ++i) { + if (*mask&ERROR) { + // Set all color channels to the median. + float m = median(texel[0], texel[1], texel[2]); + texel[0] = m, texel[1] = m, texel[2] = m; + } + ++mask; + texel += N; + } +} + +BitmapConstRef<byte, 1> MSDFErrorCorrection::getStencil() const { + return stencil; +} + +template void MSDFErrorCorrection::protectEdges(const BitmapConstRef<float, 3> &sdf); +template void MSDFErrorCorrection::protectEdges(const BitmapConstRef<float, 4> &sdf); +template void MSDFErrorCorrection::findErrors(const BitmapConstRef<float, 3> &sdf); +template void MSDFErrorCorrection::findErrors(const BitmapConstRef<float, 4> &sdf); +template void MSDFErrorCorrection::findErrors<SimpleContourCombiner>(const BitmapConstRef<float, 3> &sdf, const Shape &shape); +template void MSDFErrorCorrection::findErrors<SimpleContourCombiner>(const BitmapConstRef<float, 4> &sdf, const Shape &shape); +template void MSDFErrorCorrection::findErrors<OverlappingContourCombiner>(const BitmapConstRef<float, 3> &sdf, const Shape &shape); +template void MSDFErrorCorrection::findErrors<OverlappingContourCombiner>(const BitmapConstRef<float, 4> &sdf, const Shape &shape); +template void MSDFErrorCorrection::apply(const BitmapRef<float, 3> &sdf) const; +template void MSDFErrorCorrection::apply(const BitmapRef<float, 4> &sdf) const; + +} diff --git a/thirdparty/msdfgen/core/MSDFErrorCorrection.h b/thirdparty/msdfgen/core/MSDFErrorCorrection.h new file mode 100644 index 0000000000..c2e92fbce7 --- /dev/null +++ b/thirdparty/msdfgen/core/MSDFErrorCorrection.h @@ -0,0 +1,56 @@ + +#pragma once + +#include "Projection.h" +#include "Shape.h" +#include "BitmapRef.hpp" + +namespace msdfgen { + +/// Performs error correction on a computed MSDF to eliminate interpolation artifacts. This is a low-level class, you may want to use the API in msdf-error-correction.h instead. +class MSDFErrorCorrection { + +public: + /// Stencil flags. + enum Flags { + /// Texel marked as potentially causing interpolation errors. + ERROR = 1, + /// Texel marked as protected. Protected texels are only given the error flag if they cause inversion artifacts. + PROTECTED = 2 + }; + + MSDFErrorCorrection(); + explicit MSDFErrorCorrection(const BitmapRef<byte, 1> &stencil, const Projection &projection, double range); + /// Sets the minimum ratio between the actual and maximum expected distance delta to be considered an error. + void setMinDeviationRatio(double minDeviationRatio); + /// Sets the minimum ratio between the pre-correction distance error and the post-correction distance error. + void setMinImproveRatio(double minImproveRatio); + /// Flags all texels that are interpolated at corners as protected. + void protectCorners(const Shape &shape); + /// Flags all texels that contribute to edges as protected. + template <int N> + void protectEdges(const BitmapConstRef<float, N> &sdf); + /// Flags all texels as protected. + void protectAll(); + /// Flags texels that are expected to cause interpolation artifacts based on analysis of the SDF only. + template <int N> + void findErrors(const BitmapConstRef<float, N> &sdf); + /// Flags texels that are expected to cause interpolation artifacts based on analysis of the SDF and comparison with the exact shape distance. + template <template <typename> class ContourCombiner, int N> + void findErrors(const BitmapConstRef<float, N> &sdf, const Shape &shape); + /// Modifies the MSDF so that all texels with the error flag are converted to single-channel. + template <int N> + void apply(const BitmapRef<float, N> &sdf) const; + /// Returns the stencil in its current state (see Flags). + BitmapConstRef<byte, 1> getStencil() const; + +private: + BitmapRef<byte, 1> stencil; + Projection projection; + double invRange; + double minDeviationRatio; + double minImproveRatio; + +}; + +} diff --git a/thirdparty/msdfgen/core/Projection.cpp b/thirdparty/msdfgen/core/Projection.cpp new file mode 100644 index 0000000000..fa2f5e2592 --- /dev/null +++ b/thirdparty/msdfgen/core/Projection.cpp @@ -0,0 +1,42 @@ + +#include "Projection.h" + +namespace msdfgen { + +Projection::Projection() : scale(1), translate(0) { } + +Projection::Projection(const Vector2 &scale, const Vector2 &translate) : scale(scale), translate(translate) { } + +Point2 Projection::project(const Point2 &coord) const { + return scale*(coord+translate); +} + +Point2 Projection::unproject(const Point2 &coord) const { + return coord/scale-translate; +} + +Vector2 Projection::projectVector(const Vector2 &vector) const { + return scale*vector; +} + +Vector2 Projection::unprojectVector(const Vector2 &vector) const { + return vector/scale; +} + +double Projection::projectX(double x) const { + return scale.x*(x+translate.x); +} + +double Projection::projectY(double y) const { + return scale.y*(y+translate.y); +} + +double Projection::unprojectX(double x) const { + return x/scale.x-translate.x; +} + +double Projection::unprojectY(double y) const { + return y/scale.y-translate.y; +} + +} diff --git a/thirdparty/msdfgen/core/Projection.h b/thirdparty/msdfgen/core/Projection.h new file mode 100644 index 0000000000..7cdb1c307a --- /dev/null +++ b/thirdparty/msdfgen/core/Projection.h @@ -0,0 +1,37 @@ + +#pragma once + +#include "Vector2.h" + +namespace msdfgen { + +/// A transformation from shape coordinates to pixel coordinates. +class Projection { + +public: + Projection(); + Projection(const Vector2 &scale, const Vector2 &translate); + /// Converts the shape coordinate to pixel coordinate. + Point2 project(const Point2 &coord) const; + /// Converts the pixel coordinate to shape coordinate. + Point2 unproject(const Point2 &coord) const; + /// Converts the vector to pixel coordinate space. + Vector2 projectVector(const Vector2 &vector) const; + /// Converts the vector from pixel coordinate space. + Vector2 unprojectVector(const Vector2 &vector) const; + /// Converts the X-coordinate from shape to pixel coordinate space. + double projectX(double x) const; + /// Converts the Y-coordinate from shape to pixel coordinate space. + double projectY(double y) const; + /// Converts the X-coordinate from pixel to shape coordinate space. + double unprojectX(double x) const; + /// Converts the Y-coordinate from pixel to shape coordinate space. + double unprojectY(double y) const; + +private: + Vector2 scale; + Vector2 translate; + +}; + +} diff --git a/thirdparty/msdfgen/core/Scanline.cpp b/thirdparty/msdfgen/core/Scanline.cpp new file mode 100644 index 0000000000..8e5352dbf6 --- /dev/null +++ b/thirdparty/msdfgen/core/Scanline.cpp @@ -0,0 +1,125 @@ + +#include "Scanline.h" + +#include <algorithm> +#include "arithmetics.hpp" + +namespace msdfgen { + +static int compareIntersections(const void *a, const void *b) { + return sign(reinterpret_cast<const Scanline::Intersection *>(a)->x-reinterpret_cast<const Scanline::Intersection *>(b)->x); +} + +bool interpretFillRule(int intersections, FillRule fillRule) { + switch (fillRule) { + case FILL_NONZERO: + return intersections != 0; + case FILL_ODD: + return intersections&1; + case FILL_POSITIVE: + return intersections > 0; + case FILL_NEGATIVE: + return intersections < 0; + } + return false; +} + +double Scanline::overlap(const Scanline &a, const Scanline &b, double xFrom, double xTo, FillRule fillRule) { + double total = 0; + bool aInside = false, bInside = false; + int ai = 0, bi = 0; + double ax = !a.intersections.empty() ? a.intersections[ai].x : xTo; + double bx = !b.intersections.empty() ? b.intersections[bi].x : xTo; + while (ax < xFrom || bx < xFrom) { + double xNext = min(ax, bx); + if (ax == xNext && ai < (int) a.intersections.size()) { + aInside = interpretFillRule(a.intersections[ai].direction, fillRule); + ax = ++ai < (int) a.intersections.size() ? a.intersections[ai].x : xTo; + } + if (bx == xNext && bi < (int) b.intersections.size()) { + bInside = interpretFillRule(b.intersections[bi].direction, fillRule); + bx = ++bi < (int) b.intersections.size() ? b.intersections[bi].x : xTo; + } + } + double x = xFrom; + while (ax < xTo || bx < xTo) { + double xNext = min(ax, bx); + if (aInside == bInside) + total += xNext-x; + if (ax == xNext && ai < (int) a.intersections.size()) { + aInside = interpretFillRule(a.intersections[ai].direction, fillRule); + ax = ++ai < (int) a.intersections.size() ? a.intersections[ai].x : xTo; + } + if (bx == xNext && bi < (int) b.intersections.size()) { + bInside = interpretFillRule(b.intersections[bi].direction, fillRule); + bx = ++bi < (int) b.intersections.size() ? b.intersections[bi].x : xTo; + } + x = xNext; + } + if (aInside == bInside) + total += xTo-x; + return total; +} + +Scanline::Scanline() : lastIndex(0) { } + +void Scanline::preprocess() { + lastIndex = 0; + if (!intersections.empty()) { + qsort(&intersections[0], intersections.size(), sizeof(Intersection), compareIntersections); + int totalDirection = 0; + for (std::vector<Intersection>::iterator intersection = intersections.begin(); intersection != intersections.end(); ++intersection) { + totalDirection += intersection->direction; + intersection->direction = totalDirection; + } + } +} + +void Scanline::setIntersections(const std::vector<Intersection> &intersections) { + this->intersections = intersections; + preprocess(); +} + +#ifdef MSDFGEN_USE_CPP11 +void Scanline::setIntersections(std::vector<Intersection> &&intersections) { + this->intersections = (std::vector<Intersection> &&) intersections; + preprocess(); +} +#endif + +int Scanline::moveTo(double x) const { + if (intersections.empty()) + return -1; + int index = lastIndex; + if (x < intersections[index].x) { + do { + if (index == 0) { + lastIndex = 0; + return -1; + } + --index; + } while (x < intersections[index].x); + } else { + while (index < (int) intersections.size()-1 && x >= intersections[index+1].x) + ++index; + } + lastIndex = index; + return index; +} + +int Scanline::countIntersections(double x) const { + return moveTo(x)+1; +} + +int Scanline::sumIntersections(double x) const { + int index = moveTo(x); + if (index >= 0) + return intersections[index].direction; + return 0; +} + +bool Scanline::filled(double x, FillRule fillRule) const { + return interpretFillRule(sumIntersections(x), fillRule); +} + +} diff --git a/thirdparty/msdfgen/core/Scanline.h b/thirdparty/msdfgen/core/Scanline.h new file mode 100644 index 0000000000..9c8f34044b --- /dev/null +++ b/thirdparty/msdfgen/core/Scanline.h @@ -0,0 +1,55 @@ + +#pragma once + +#include <vector> + +namespace msdfgen { + +/// Fill rule dictates how intersection total is interpreted during rasterization. +enum FillRule { + FILL_NONZERO, + FILL_ODD, // "even-odd" + FILL_POSITIVE, + FILL_NEGATIVE +}; + +/// Resolves the number of intersection into a binary fill value based on fill rule. +bool interpretFillRule(int intersections, FillRule fillRule); + +/// Represents a horizontal scanline intersecting a shape. +class Scanline { + +public: + /// An intersection with the scanline. + struct Intersection { + /// X coordinate. + double x; + /// Normalized Y direction of the oriented edge at the point of intersection. + int direction; + }; + + static double overlap(const Scanline &a, const Scanline &b, double xFrom, double xTo, FillRule fillRule); + + Scanline(); + /// Populates the intersection list. + void setIntersections(const std::vector<Intersection> &intersections); +#ifdef MSDFGEN_USE_CPP11 + void setIntersections(std::vector<Intersection> &&intersections); +#endif + /// Returns the number of intersections left of x. + int countIntersections(double x) const; + /// Returns the total sign of intersections left of x. + int sumIntersections(double x) const; + /// Decides whether the scanline is filled at x based on fill rule. + bool filled(double x, FillRule fillRule) const; + +private: + std::vector<Intersection> intersections; + mutable int lastIndex; + + void preprocess(); + int moveTo(double x) const; + +}; + +} diff --git a/thirdparty/msdfgen/core/Shape.cpp b/thirdparty/msdfgen/core/Shape.cpp new file mode 100644 index 0000000000..8d6f47c807 --- /dev/null +++ b/thirdparty/msdfgen/core/Shape.cpp @@ -0,0 +1,183 @@ + +#include "Shape.h" + +#include <algorithm> +#include "arithmetics.hpp" + +namespace msdfgen { + +Shape::Shape() : inverseYAxis(false) { } + +void Shape::addContour(const Contour &contour) { + contours.push_back(contour); +} + +#ifdef MSDFGEN_USE_CPP11 +void Shape::addContour(Contour &&contour) { + contours.push_back((Contour &&) contour); +} +#endif + +Contour & Shape::addContour() { + contours.resize(contours.size()+1); + return contours.back(); +} + +bool Shape::validate() const { + for (std::vector<Contour>::const_iterator contour = contours.begin(); contour != contours.end(); ++contour) { + if (!contour->edges.empty()) { + Point2 corner = contour->edges.back()->point(1); + for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) { + if (!*edge) + return false; + if ((*edge)->point(0) != corner) + return false; + corner = (*edge)->point(1); + } + } + } + return true; +} + +static void deconvergeEdge(EdgeHolder &edgeHolder, int param) { + { + const QuadraticSegment *quadraticSegment = dynamic_cast<const QuadraticSegment *>(&*edgeHolder); + if (quadraticSegment) + edgeHolder = quadraticSegment->convertToCubic(); + } + { + CubicSegment *cubicSegment = dynamic_cast<CubicSegment *>(&*edgeHolder); + if (cubicSegment) + cubicSegment->deconverge(param, MSDFGEN_DECONVERGENCE_FACTOR); + } +} + +void Shape::normalize() { + for (std::vector<Contour>::iterator contour = contours.begin(); contour != contours.end(); ++contour) { + if (contour->edges.size() == 1) { + EdgeSegment *parts[3] = { }; + contour->edges[0]->splitInThirds(parts[0], parts[1], parts[2]); + contour->edges.clear(); + contour->edges.push_back(EdgeHolder(parts[0])); + contour->edges.push_back(EdgeHolder(parts[1])); + contour->edges.push_back(EdgeHolder(parts[2])); + } else { + EdgeHolder *prevEdge = &contour->edges.back(); + for (std::vector<EdgeHolder>::iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) { + Vector2 prevDir = (*prevEdge)->direction(1).normalize(); + Vector2 curDir = (*edge)->direction(0).normalize(); + if (dotProduct(prevDir, curDir) < MSDFGEN_CORNER_DOT_EPSILON-1) { + deconvergeEdge(*prevEdge, 1); + deconvergeEdge(*edge, 0); + } + prevEdge = &*edge; + } + } + } +} + +void Shape::bound(double &l, double &b, double &r, double &t) const { + for (std::vector<Contour>::const_iterator contour = contours.begin(); contour != contours.end(); ++contour) + contour->bound(l, b, r, t); +} + +void Shape::boundMiters(double &l, double &b, double &r, double &t, double border, double miterLimit, int polarity) const { + for (std::vector<Contour>::const_iterator contour = contours.begin(); contour != contours.end(); ++contour) + contour->boundMiters(l, b, r, t, border, miterLimit, polarity); +} + +Shape::Bounds Shape::getBounds(double border, double miterLimit, int polarity) const { + static const double LARGE_VALUE = 1e240; + Shape::Bounds bounds = { +LARGE_VALUE, +LARGE_VALUE, -LARGE_VALUE, -LARGE_VALUE }; + bound(bounds.l, bounds.b, bounds.r, bounds.t); + if (border > 0) { + bounds.l -= border, bounds.b -= border; + bounds.r += border, bounds.t += border; + if (miterLimit > 0) + boundMiters(bounds.l, bounds.b, bounds.r, bounds.t, border, miterLimit, polarity); + } + return bounds; +} + +void Shape::scanline(Scanline &line, double y) const { + std::vector<Scanline::Intersection> intersections; + double x[3]; + int dy[3]; + for (std::vector<Contour>::const_iterator contour = contours.begin(); contour != contours.end(); ++contour) { + for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) { + int n = (*edge)->scanlineIntersections(x, dy, y); + for (int i = 0; i < n; ++i) { + Scanline::Intersection intersection = { x[i], dy[i] }; + intersections.push_back(intersection); + } + } + } +#ifdef MSDFGEN_USE_CPP11 + line.setIntersections((std::vector<Scanline::Intersection> &&) intersections); +#else + line.setIntersections(intersections); +#endif +} + +int Shape::edgeCount() const { + int total = 0; + for (std::vector<Contour>::const_iterator contour = contours.begin(); contour != contours.end(); ++contour) + total += (int) contour->edges.size(); + return total; +} + +void Shape::orientContours() { + struct Intersection { + double x; + int direction; + int contourIndex; + + static int compare(const void *a, const void *b) { + return sign(reinterpret_cast<const Intersection *>(a)->x-reinterpret_cast<const Intersection *>(b)->x); + } + }; + + const double ratio = .5*(sqrt(5)-1); // an irrational number to minimize chance of intersecting a corner or other point of interest + std::vector<int> orientations(contours.size()); + std::vector<Intersection> intersections; + for (int i = 0; i < (int) contours.size(); ++i) { + if (!orientations[i] && !contours[i].edges.empty()) { + // Find an Y that crosses the contour + double y0 = contours[i].edges.front()->point(0).y; + double y1 = y0; + for (std::vector<EdgeHolder>::const_iterator edge = contours[i].edges.begin(); edge != contours[i].edges.end() && y0 == y1; ++edge) + y1 = (*edge)->point(1).y; + for (std::vector<EdgeHolder>::const_iterator edge = contours[i].edges.begin(); edge != contours[i].edges.end() && y0 == y1; ++edge) + y1 = (*edge)->point(ratio).y; // in case all endpoints are in a horizontal line + double y = mix(y0, y1, ratio); + // Scanline through whole shape at Y + double x[3]; + int dy[3]; + for (int j = 0; j < (int) contours.size(); ++j) { + for (std::vector<EdgeHolder>::const_iterator edge = contours[j].edges.begin(); edge != contours[j].edges.end(); ++edge) { + int n = (*edge)->scanlineIntersections(x, dy, y); + for (int k = 0; k < n; ++k) { + Intersection intersection = { x[k], dy[k], j }; + intersections.push_back(intersection); + } + } + } + qsort(&intersections[0], intersections.size(), sizeof(Intersection), &Intersection::compare); + // Disqualify multiple intersections + for (int j = 1; j < (int) intersections.size(); ++j) + if (intersections[j].x == intersections[j-1].x) + intersections[j].direction = intersections[j-1].direction = 0; + // Inspect scanline and deduce orientations of intersected contours + for (int j = 0; j < (int) intersections.size(); ++j) + if (intersections[j].direction) + orientations[intersections[j].contourIndex] += 2*((j&1)^(intersections[j].direction > 0))-1; + intersections.clear(); + } + } + // Reverse contours that have the opposite orientation + for (int i = 0; i < (int) contours.size(); ++i) + if (orientations[i] < 0) + contours[i].reverse(); +} + +} diff --git a/thirdparty/msdfgen/core/Shape.h b/thirdparty/msdfgen/core/Shape.h new file mode 100644 index 0000000000..7539921ce7 --- /dev/null +++ b/thirdparty/msdfgen/core/Shape.h @@ -0,0 +1,55 @@ + +#pragma once + +#include <vector> +#include "Contour.h" +#include "Scanline.h" + +namespace msdfgen { + +// Threshold of the dot product of adjacent edge directions to be considered convergent. +#define MSDFGEN_CORNER_DOT_EPSILON .000001 +// The proportional amount by which a curve's control point will be adjusted to eliminate convergent corners. +#define MSDFGEN_DECONVERGENCE_FACTOR .000001 + +/// Vector shape representation. +class Shape { + +public: + struct Bounds { + double l, b, r, t; + }; + + /// The list of contours the shape consists of. + std::vector<Contour> contours; + /// Specifies whether the shape uses bottom-to-top (false) or top-to-bottom (true) Y coordinates. + bool inverseYAxis; + + Shape(); + /// Adds a contour. + void addContour(const Contour &contour); +#ifdef MSDFGEN_USE_CPP11 + void addContour(Contour &&contour); +#endif + /// Adds a blank contour and returns its reference. + Contour & addContour(); + /// Normalizes the shape geometry for distance field generation. + void normalize(); + /// Performs basic checks to determine if the object represents a valid shape. + bool validate() const; + /// Adjusts the bounding box to fit the shape. + void bound(double &l, double &b, double &r, double &t) const; + /// Adjusts the bounding box to fit the shape border's mitered corners. + void boundMiters(double &l, double &b, double &r, double &t, double border, double miterLimit, int polarity) const; + /// Computes the minimum bounding box that fits the shape, optionally with a (mitered) border. + Bounds getBounds(double border = 0, double miterLimit = 0, int polarity = 0) const; + /// Outputs the scanline that intersects the shape at y. + void scanline(Scanline &line, double y) const; + /// Returns the total number of edge segments + int edgeCount() const; + /// Assumes its contours are unoriented (even-odd fill rule). Attempts to orient them to conform to the non-zero winding rule. + void orientContours(); + +}; + +} diff --git a/thirdparty/msdfgen/core/ShapeDistanceFinder.h b/thirdparty/msdfgen/core/ShapeDistanceFinder.h new file mode 100644 index 0000000000..57df8d8e72 --- /dev/null +++ b/thirdparty/msdfgen/core/ShapeDistanceFinder.h @@ -0,0 +1,37 @@ + +#pragma once + +#include <vector> +#include "Vector2.h" +#include "edge-selectors.h" +#include "contour-combiners.h" + +namespace msdfgen { + +/// Finds the distance between a point and a Shape. ContourCombiner dictates the distance metric and its data type. +template <class ContourCombiner> +class ShapeDistanceFinder { + +public: + typedef typename ContourCombiner::DistanceType DistanceType; + + // Passed shape object must persist until the distance finder is destroyed! + explicit ShapeDistanceFinder(const Shape &shape); + /// Finds the distance from origin. Not thread-safe! Is fastest when subsequent queries are close together. + DistanceType distance(const Point2 &origin); + + /// Finds the distance between shape and origin. Does not allocate result cache used to optimize performance of multiple queries. + static DistanceType oneShotDistance(const Shape &shape, const Point2 &origin); + +private: + const Shape &shape; + ContourCombiner contourCombiner; + std::vector<typename ContourCombiner::EdgeSelectorType::EdgeCache> shapeEdgeCache; + +}; + +typedef ShapeDistanceFinder<SimpleContourCombiner<TrueDistanceSelector> > SimpleTrueShapeDistanceFinder; + +} + +#include "ShapeDistanceFinder.hpp" diff --git a/thirdparty/msdfgen/core/ShapeDistanceFinder.hpp b/thirdparty/msdfgen/core/ShapeDistanceFinder.hpp new file mode 100644 index 0000000000..028738e5c3 --- /dev/null +++ b/thirdparty/msdfgen/core/ShapeDistanceFinder.hpp @@ -0,0 +1,56 @@ + +#include "ShapeDistanceFinder.h" + +namespace msdfgen { + +template <class ContourCombiner> +ShapeDistanceFinder<ContourCombiner>::ShapeDistanceFinder(const Shape &shape) : shape(shape), contourCombiner(shape), shapeEdgeCache(shape.edgeCount()) { } + +template <class ContourCombiner> +typename ShapeDistanceFinder<ContourCombiner>::DistanceType ShapeDistanceFinder<ContourCombiner>::distance(const Point2 &origin) { + contourCombiner.reset(origin); + typename ContourCombiner::EdgeSelectorType::EdgeCache *edgeCache = &shapeEdgeCache[0]; + + for (std::vector<Contour>::const_iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour) { + if (!contour->edges.empty()) { + typename ContourCombiner::EdgeSelectorType &edgeSelector = contourCombiner.edgeSelector(int(contour-shape.contours.begin())); + + const EdgeSegment *prevEdge = contour->edges.size() >= 2 ? *(contour->edges.end()-2) : *contour->edges.begin(); + const EdgeSegment *curEdge = contour->edges.back(); + for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) { + const EdgeSegment *nextEdge = *edge; + edgeSelector.addEdge(*edgeCache++, prevEdge, curEdge, nextEdge); + prevEdge = curEdge; + curEdge = nextEdge; + } + } + } + + return contourCombiner.distance(); +} + +template <class ContourCombiner> +typename ShapeDistanceFinder<ContourCombiner>::DistanceType ShapeDistanceFinder<ContourCombiner>::oneShotDistance(const Shape &shape, const Point2 &origin) { + ContourCombiner contourCombiner(shape); + contourCombiner.reset(origin); + + for (std::vector<Contour>::const_iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour) { + if (!contour->edges.empty()) { + typename ContourCombiner::EdgeSelectorType &edgeSelector = contourCombiner.edgeSelector(int(contour-shape.contours.begin())); + + const EdgeSegment *prevEdge = contour->edges.size() >= 2 ? *(contour->edges.end()-2) : *contour->edges.begin(); + const EdgeSegment *curEdge = contour->edges.back(); + for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) { + const EdgeSegment *nextEdge = *edge; + typename ContourCombiner::EdgeSelectorType::EdgeCache dummy; + edgeSelector.addEdge(dummy, prevEdge, curEdge, nextEdge); + prevEdge = curEdge; + curEdge = nextEdge; + } + } + } + + return contourCombiner.distance(); +} + +} diff --git a/thirdparty/msdfgen/core/SignedDistance.cpp b/thirdparty/msdfgen/core/SignedDistance.cpp new file mode 100644 index 0000000000..18c9d2c424 --- /dev/null +++ b/thirdparty/msdfgen/core/SignedDistance.cpp @@ -0,0 +1,30 @@ + +#include "SignedDistance.h" + +#include <cmath> + +namespace msdfgen { + +const SignedDistance SignedDistance::INFINITE(-1e240, 1); + +SignedDistance::SignedDistance() : distance(-1e240), dot(1) { } + +SignedDistance::SignedDistance(double dist, double d) : distance(dist), dot(d) { } + +bool operator<(SignedDistance a, SignedDistance b) { + return fabs(a.distance) < fabs(b.distance) || (fabs(a.distance) == fabs(b.distance) && a.dot < b.dot); +} + +bool operator>(SignedDistance a, SignedDistance b) { + return fabs(a.distance) > fabs(b.distance) || (fabs(a.distance) == fabs(b.distance) && a.dot > b.dot); +} + +bool operator<=(SignedDistance a, SignedDistance b) { + return fabs(a.distance) < fabs(b.distance) || (fabs(a.distance) == fabs(b.distance) && a.dot <= b.dot); +} + +bool operator>=(SignedDistance a, SignedDistance b) { + return fabs(a.distance) > fabs(b.distance) || (fabs(a.distance) == fabs(b.distance) && a.dot >= b.dot); +} + +} diff --git a/thirdparty/msdfgen/core/SignedDistance.h b/thirdparty/msdfgen/core/SignedDistance.h new file mode 100644 index 0000000000..034210f751 --- /dev/null +++ b/thirdparty/msdfgen/core/SignedDistance.h @@ -0,0 +1,25 @@ + +#pragma once + +namespace msdfgen { + +/// Represents a signed distance and alignment, which together can be compared to uniquely determine the closest edge segment. +class SignedDistance { + +public: + static const SignedDistance INFINITE; + + double distance; + double dot; + + SignedDistance(); + SignedDistance(double dist, double d); + + friend bool operator<(SignedDistance a, SignedDistance b); + friend bool operator>(SignedDistance a, SignedDistance b); + friend bool operator<=(SignedDistance a, SignedDistance b); + friend bool operator>=(SignedDistance a, SignedDistance b); + +}; + +} diff --git a/thirdparty/msdfgen/core/Vector2.cpp b/thirdparty/msdfgen/core/Vector2.cpp new file mode 100644 index 0000000000..896963ff2c --- /dev/null +++ b/thirdparty/msdfgen/core/Vector2.cpp @@ -0,0 +1,146 @@ + +#include "Vector2.h" + +namespace msdfgen { + +Vector2::Vector2(double val) : x(val), y(val) { } + +Vector2::Vector2(double x, double y) : x(x), y(y) { } + +void Vector2::reset() { + x = 0, y = 0; +} + +void Vector2::set(double x, double y) { + Vector2::x = x, Vector2::y = y; +} + +double Vector2::length() const { + return sqrt(x*x+y*y); +} + +double Vector2::direction() const { + return atan2(y, x); +} + +Vector2 Vector2::normalize(bool allowZero) const { + double len = length(); + if (len == 0) + return Vector2(0, !allowZero); + return Vector2(x/len, y/len); +} + +Vector2 Vector2::getOrthogonal(bool polarity) const { + return polarity ? Vector2(-y, x) : Vector2(y, -x); +} + +Vector2 Vector2::getOrthonormal(bool polarity, bool allowZero) const { + double len = length(); + if (len == 0) + return polarity ? Vector2(0, !allowZero) : Vector2(0, -!allowZero); + return polarity ? Vector2(-y/len, x/len) : Vector2(y/len, -x/len); +} + +Vector2 Vector2::project(const Vector2 &vector, bool positive) const { + Vector2 n = normalize(true); + double t = dotProduct(vector, n); + if (positive && t <= 0) + return Vector2(); + return t*n; +} + +Vector2::operator const void*() const { + return x || y ? this : NULL; +} + +bool Vector2::operator!() const { + return !x && !y; +} + +bool Vector2::operator==(const Vector2 &other) const { + return x == other.x && y == other.y; +} + +bool Vector2::operator!=(const Vector2 &other) const { + return x != other.x || y != other.y; +} + +Vector2 Vector2::operator+() const { + return *this; +} + +Vector2 Vector2::operator-() const { + return Vector2(-x, -y); +} + +Vector2 Vector2::operator+(const Vector2 &other) const { + return Vector2(x+other.x, y+other.y); +} + +Vector2 Vector2::operator-(const Vector2 &other) const { + return Vector2(x-other.x, y-other.y); +} + +Vector2 Vector2::operator*(const Vector2 &other) const { + return Vector2(x*other.x, y*other.y); +} + +Vector2 Vector2::operator/(const Vector2 &other) const { + return Vector2(x/other.x, y/other.y); +} + +Vector2 Vector2::operator*(double value) const { + return Vector2(x*value, y*value); +} + +Vector2 Vector2::operator/(double value) const { + return Vector2(x/value, y/value); +} + +Vector2 & Vector2::operator+=(const Vector2 &other) { + x += other.x, y += other.y; + return *this; +} + +Vector2 & Vector2::operator-=(const Vector2 &other) { + x -= other.x, y -= other.y; + return *this; +} + +Vector2 & Vector2::operator*=(const Vector2 &other) { + x *= other.x, y *= other.y; + return *this; +} + +Vector2 & Vector2::operator/=(const Vector2 &other) { + x /= other.x, y /= other.y; + return *this; +} + +Vector2 & Vector2::operator*=(double value) { + x *= value, y *= value; + return *this; +} + +Vector2 & Vector2::operator/=(double value) { + x /= value, y /= value; + return *this; +} + +double dotProduct(const Vector2 &a, const Vector2 &b) { + return a.x*b.x+a.y*b.y; +} + +double crossProduct(const Vector2 &a, const Vector2 &b) { + return a.x*b.y-a.y*b.x; +} + +Vector2 operator*(double value, const Vector2 &vector) { + return Vector2(value*vector.x, value*vector.y); +} + +Vector2 operator/(double value, const Vector2 &vector) { + return Vector2(value/vector.x, value/vector.y); +} + +} diff --git a/thirdparty/msdfgen/core/Vector2.h b/thirdparty/msdfgen/core/Vector2.h new file mode 100644 index 0000000000..47ca637c3d --- /dev/null +++ b/thirdparty/msdfgen/core/Vector2.h @@ -0,0 +1,66 @@ + +#pragma once + +#include <cstdlib> +#include <cmath> + +namespace msdfgen { + +/** +* A 2-dimensional euclidean vector with double precision. +* Implementation based on the Vector2 template from Artery Engine. +* @author Viktor Chlumsky +*/ +struct Vector2 { + + double x, y; + + Vector2(double val = 0); + Vector2(double x, double y); + /// Sets the vector to zero. + void reset(); + /// Sets individual elements of the vector. + void set(double x, double y); + /// Returns the vector's length. + double length() const; + /// Returns the angle of the vector in radians (atan2). + double direction() const; + /// Returns the normalized vector - one that has the same direction but unit length. + Vector2 normalize(bool allowZero = false) const; + /// Returns a vector with the same length that is orthogonal to this one. + Vector2 getOrthogonal(bool polarity = true) const; + /// Returns a vector with unit length that is orthogonal to this one. + Vector2 getOrthonormal(bool polarity = true, bool allowZero = false) const; + /// Returns a vector projected along this one. + Vector2 project(const Vector2 &vector, bool positive = false) const; + operator const void *() const; + bool operator!() const; + bool operator==(const Vector2 &other) const; + bool operator!=(const Vector2 &other) const; + Vector2 operator+() const; + Vector2 operator-() const; + Vector2 operator+(const Vector2 &other) const; + Vector2 operator-(const Vector2 &other) const; + Vector2 operator*(const Vector2 &other) const; + Vector2 operator/(const Vector2 &other) const; + Vector2 operator*(double value) const; + Vector2 operator/(double value) const; + Vector2 & operator+=(const Vector2 &other); + Vector2 & operator-=(const Vector2 &other); + Vector2 & operator*=(const Vector2 &other); + Vector2 & operator/=(const Vector2 &other); + Vector2 & operator*=(double value); + Vector2 & operator/=(double value); + /// Dot product of two vectors. + friend double dotProduct(const Vector2 &a, const Vector2 &b); + /// A special version of the cross product for 2D vectors (returns scalar value). + friend double crossProduct(const Vector2 &a, const Vector2 &b); + friend Vector2 operator*(double value, const Vector2 &vector); + friend Vector2 operator/(double value, const Vector2 &vector); + +}; + +/// A vector may also represent a point, which shall be differentiated semantically using the alias Point2. +typedef Vector2 Point2; + +} diff --git a/thirdparty/msdfgen/core/arithmetics.hpp b/thirdparty/msdfgen/core/arithmetics.hpp new file mode 100644 index 0000000000..78c21d658e --- /dev/null +++ b/thirdparty/msdfgen/core/arithmetics.hpp @@ -0,0 +1,63 @@ + +#pragma once + +#include <cstdlib> +#include <cmath> + +namespace msdfgen { + +/// Returns the smaller of the arguments. +template <typename T> +inline T min(T a, T b) { + return b < a ? b : a; +} + +/// Returns the larger of the arguments. +template <typename T> +inline T max(T a, T b) { + return a < b ? b : a; +} + +/// Returns the middle out of three values +template <typename T> +inline T median(T a, T b, T c) { + return max(min(a, b), min(max(a, b), c)); +} + +/// Returns the weighted average of a and b. +template <typename T, typename S> +inline T mix(T a, T b, S weight) { + return T((S(1)-weight)*a+weight*b); +} + +/// Clamps the number to the interval from 0 to 1. +template <typename T> +inline T clamp(T n) { + return n >= T(0) && n <= T(1) ? n : T(n > T(0)); +} + +/// Clamps the number to the interval from 0 to b. +template <typename T> +inline T clamp(T n, T b) { + return n >= T(0) && n <= b ? n : T(n > T(0))*b; +} + +/// Clamps the number to the interval from a to b. +template <typename T> +inline T clamp(T n, T a, T b) { + return n >= a && n <= b ? n : n < a ? a : b; +} + +/// Returns 1 for positive values, -1 for negative values, and 0 for zero. +template <typename T> +inline int sign(T n) { + return (T(0) < n)-(n < T(0)); +} + +/// Returns 1 for non-negative values and -1 for negative values. +template <typename T> +inline int nonZeroSign(T n) { + return 2*(n > T(0))-1; +} + +} diff --git a/thirdparty/msdfgen/core/bitmap-interpolation.hpp b/thirdparty/msdfgen/core/bitmap-interpolation.hpp new file mode 100644 index 0000000000..a14b0fb534 --- /dev/null +++ b/thirdparty/msdfgen/core/bitmap-interpolation.hpp @@ -0,0 +1,25 @@ + +#pragma once + +#include "arithmetics.hpp" +#include "Vector2.h" +#include "BitmapRef.hpp" + +namespace msdfgen { + +template <typename T, int N> +static void interpolate(T *output, const BitmapConstRef<T, N> &bitmap, Point2 pos) { + pos -= .5; + int l = (int) floor(pos.x); + int b = (int) floor(pos.y); + int r = l+1; + int t = b+1; + double lr = pos.x-l; + double bt = pos.y-b; + l = clamp(l, bitmap.width-1), r = clamp(r, bitmap.width-1); + b = clamp(b, bitmap.height-1), t = clamp(t, bitmap.height-1); + for (int i = 0; i < N; ++i) + output[i] = mix(mix(bitmap(l, b)[i], bitmap(r, b)[i], lr), mix(bitmap(l, t)[i], bitmap(r, t)[i], lr), bt); +} + +} diff --git a/thirdparty/msdfgen/core/contour-combiners.cpp b/thirdparty/msdfgen/core/contour-combiners.cpp new file mode 100644 index 0000000000..d0c5b46d74 --- /dev/null +++ b/thirdparty/msdfgen/core/contour-combiners.cpp @@ -0,0 +1,133 @@ + +#include "contour-combiners.h" + +#include "arithmetics.hpp" + +namespace msdfgen { + +static void initDistance(double &distance) { + distance = SignedDistance::INFINITE.distance; +} + +static void initDistance(MultiDistance &distance) { + distance.r = SignedDistance::INFINITE.distance; + distance.g = SignedDistance::INFINITE.distance; + distance.b = SignedDistance::INFINITE.distance; +} + +static double resolveDistance(double distance) { + return distance; +} + +static double resolveDistance(const MultiDistance &distance) { + return median(distance.r, distance.g, distance.b); +} + +template <class EdgeSelector> +SimpleContourCombiner<EdgeSelector>::SimpleContourCombiner(const Shape &shape) { } + +template <class EdgeSelector> +void SimpleContourCombiner<EdgeSelector>::reset(const Point2 &p) { + shapeEdgeSelector.reset(p); +} + +template <class EdgeSelector> +EdgeSelector & SimpleContourCombiner<EdgeSelector>::edgeSelector(int) { + return shapeEdgeSelector; +} + +template <class EdgeSelector> +typename SimpleContourCombiner<EdgeSelector>::DistanceType SimpleContourCombiner<EdgeSelector>::distance() const { + return shapeEdgeSelector.distance(); +} + +template class SimpleContourCombiner<TrueDistanceSelector>; +template class SimpleContourCombiner<PseudoDistanceSelector>; +template class SimpleContourCombiner<MultiDistanceSelector>; +template class SimpleContourCombiner<MultiAndTrueDistanceSelector>; + +template <class EdgeSelector> +OverlappingContourCombiner<EdgeSelector>::OverlappingContourCombiner(const Shape &shape) { + windings.reserve(shape.contours.size()); + for (std::vector<Contour>::const_iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour) + windings.push_back(contour->winding()); + edgeSelectors.resize(shape.contours.size()); +} + +template <class EdgeSelector> +void OverlappingContourCombiner<EdgeSelector>::reset(const Point2 &p) { + this->p = p; + for (typename std::vector<EdgeSelector>::iterator contourEdgeSelector = edgeSelectors.begin(); contourEdgeSelector != edgeSelectors.end(); ++contourEdgeSelector) + contourEdgeSelector->reset(p); +} + +template <class EdgeSelector> +EdgeSelector & OverlappingContourCombiner<EdgeSelector>::edgeSelector(int i) { + return edgeSelectors[i]; +} + +template <class EdgeSelector> +typename OverlappingContourCombiner<EdgeSelector>::DistanceType OverlappingContourCombiner<EdgeSelector>::distance() const { + int contourCount = (int) edgeSelectors.size(); + EdgeSelector shapeEdgeSelector; + EdgeSelector innerEdgeSelector; + EdgeSelector outerEdgeSelector; + shapeEdgeSelector.reset(p); + innerEdgeSelector.reset(p); + outerEdgeSelector.reset(p); + for (int i = 0; i < contourCount; ++i) { + DistanceType edgeDistance = edgeSelectors[i].distance(); + shapeEdgeSelector.merge(edgeSelectors[i]); + if (windings[i] > 0 && resolveDistance(edgeDistance) >= 0) + innerEdgeSelector.merge(edgeSelectors[i]); + if (windings[i] < 0 && resolveDistance(edgeDistance) <= 0) + outerEdgeSelector.merge(edgeSelectors[i]); + } + + DistanceType shapeDistance = shapeEdgeSelector.distance(); + DistanceType innerDistance = innerEdgeSelector.distance(); + DistanceType outerDistance = outerEdgeSelector.distance(); + double innerScalarDistance = resolveDistance(innerDistance); + double outerScalarDistance = resolveDistance(outerDistance); + DistanceType distance; + initDistance(distance); + + int winding = 0; + if (innerScalarDistance >= 0 && fabs(innerScalarDistance) <= fabs(outerScalarDistance)) { + distance = innerDistance; + winding = 1; + for (int i = 0; i < contourCount; ++i) + if (windings[i] > 0) { + DistanceType contourDistance = edgeSelectors[i].distance(); + if (fabs(resolveDistance(contourDistance)) < fabs(outerScalarDistance) && resolveDistance(contourDistance) > resolveDistance(distance)) + distance = contourDistance; + } + } else if (outerScalarDistance <= 0 && fabs(outerScalarDistance) < fabs(innerScalarDistance)) { + distance = outerDistance; + winding = -1; + for (int i = 0; i < contourCount; ++i) + if (windings[i] < 0) { + DistanceType contourDistance = edgeSelectors[i].distance(); + if (fabs(resolveDistance(contourDistance)) < fabs(innerScalarDistance) && resolveDistance(contourDistance) < resolveDistance(distance)) + distance = contourDistance; + } + } else + return shapeDistance; + + for (int i = 0; i < contourCount; ++i) + if (windings[i] != winding) { + DistanceType contourDistance = edgeSelectors[i].distance(); + if (resolveDistance(contourDistance)*resolveDistance(distance) >= 0 && fabs(resolveDistance(contourDistance)) < fabs(resolveDistance(distance))) + distance = contourDistance; + } + if (resolveDistance(distance) == resolveDistance(shapeDistance)) + distance = shapeDistance; + return distance; +} + +template class OverlappingContourCombiner<TrueDistanceSelector>; +template class OverlappingContourCombiner<PseudoDistanceSelector>; +template class OverlappingContourCombiner<MultiDistanceSelector>; +template class OverlappingContourCombiner<MultiAndTrueDistanceSelector>; + +} diff --git a/thirdparty/msdfgen/core/contour-combiners.h b/thirdparty/msdfgen/core/contour-combiners.h new file mode 100644 index 0000000000..944b119aba --- /dev/null +++ b/thirdparty/msdfgen/core/contour-combiners.h @@ -0,0 +1,47 @@ + +#pragma once + +#include "Shape.h" +#include "edge-selectors.h" + +namespace msdfgen { + +/// Simply selects the nearest contour. +template <class EdgeSelector> +class SimpleContourCombiner { + +public: + typedef EdgeSelector EdgeSelectorType; + typedef typename EdgeSelector::DistanceType DistanceType; + + explicit SimpleContourCombiner(const Shape &shape); + void reset(const Point2 &p); + EdgeSelector & edgeSelector(int i); + DistanceType distance() const; + +private: + EdgeSelector shapeEdgeSelector; + +}; + +/// Selects the nearest contour that actually forms a border between filled and unfilled area. +template <class EdgeSelector> +class OverlappingContourCombiner { + +public: + typedef EdgeSelector EdgeSelectorType; + typedef typename EdgeSelector::DistanceType DistanceType; + + explicit OverlappingContourCombiner(const Shape &shape); + void reset(const Point2 &p); + EdgeSelector & edgeSelector(int i); + DistanceType distance() const; + +private: + Point2 p; + std::vector<int> windings; + std::vector<EdgeSelector> edgeSelectors; + +}; + +} diff --git a/thirdparty/msdfgen/core/edge-coloring.cpp b/thirdparty/msdfgen/core/edge-coloring.cpp new file mode 100644 index 0000000000..370f9aa38d --- /dev/null +++ b/thirdparty/msdfgen/core/edge-coloring.cpp @@ -0,0 +1,499 @@ + +#include "edge-coloring.h" + +#include <cstdlib> +#include <cmath> +#include <cstring> +#include <queue> +#include "arithmetics.hpp" + +namespace msdfgen { + +static bool isCorner(const Vector2 &aDir, const Vector2 &bDir, double crossThreshold) { + return dotProduct(aDir, bDir) <= 0 || fabs(crossProduct(aDir, bDir)) > crossThreshold; +} + +static double estimateEdgeLength(const EdgeSegment *edge) { + double len = 0; + Point2 prev = edge->point(0); + for (int i = 1; i <= MSDFGEN_EDGE_LENGTH_PRECISION; ++i) { + Point2 cur = edge->point(1./MSDFGEN_EDGE_LENGTH_PRECISION*i); + len += (cur-prev).length(); + prev = cur; + } + return len; +} + +static void switchColor(EdgeColor &color, unsigned long long &seed, EdgeColor banned = BLACK) { + EdgeColor combined = EdgeColor(color&banned); + if (combined == RED || combined == GREEN || combined == BLUE) { + color = EdgeColor(combined^WHITE); + return; + } + if (color == BLACK || color == WHITE) { + static const EdgeColor start[3] = { CYAN, MAGENTA, YELLOW }; + color = start[seed%3]; + seed /= 3; + return; + } + int shifted = color<<(1+(seed&1)); + color = EdgeColor((shifted|shifted>>3)&WHITE); + seed >>= 1; +} + +void edgeColoringSimple(Shape &shape, double angleThreshold, unsigned long long seed) { + double crossThreshold = sin(angleThreshold); + std::vector<int> corners; + for (std::vector<Contour>::iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour) { + // Identify corners + corners.clear(); + if (!contour->edges.empty()) { + Vector2 prevDirection = contour->edges.back()->direction(1); + int index = 0; + for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge, ++index) { + if (isCorner(prevDirection.normalize(), (*edge)->direction(0).normalize(), crossThreshold)) + corners.push_back(index); + prevDirection = (*edge)->direction(1); + } + } + + // Smooth contour + if (corners.empty()) + for (std::vector<EdgeHolder>::iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) + (*edge)->color = WHITE; + // "Teardrop" case + else if (corners.size() == 1) { + EdgeColor colors[3] = { WHITE, WHITE }; + switchColor(colors[0], seed); + switchColor(colors[2] = colors[0], seed); + int corner = corners[0]; + if (contour->edges.size() >= 3) { + int m = (int) contour->edges.size(); + for (int i = 0; i < m; ++i) + contour->edges[(corner+i)%m]->color = (colors+1)[int(3+2.875*i/(m-1)-1.4375+.5)-3]; + } else if (contour->edges.size() >= 1) { + // Less than three edge segments for three colors => edges must be split + EdgeSegment *parts[7] = { }; + contour->edges[0]->splitInThirds(parts[0+3*corner], parts[1+3*corner], parts[2+3*corner]); + if (contour->edges.size() >= 2) { + contour->edges[1]->splitInThirds(parts[3-3*corner], parts[4-3*corner], parts[5-3*corner]); + parts[0]->color = parts[1]->color = colors[0]; + parts[2]->color = parts[3]->color = colors[1]; + parts[4]->color = parts[5]->color = colors[2]; + } else { + parts[0]->color = colors[0]; + parts[1]->color = colors[1]; + parts[2]->color = colors[2]; + } + contour->edges.clear(); + for (int i = 0; parts[i]; ++i) + contour->edges.push_back(EdgeHolder(parts[i])); + } + } + // Multiple corners + else { + int cornerCount = (int) corners.size(); + int spline = 0; + int start = corners[0]; + int m = (int) contour->edges.size(); + EdgeColor color = WHITE; + switchColor(color, seed); + EdgeColor initialColor = color; + for (int i = 0; i < m; ++i) { + int index = (start+i)%m; + if (spline+1 < cornerCount && corners[spline+1] == index) { + ++spline; + switchColor(color, seed, EdgeColor((spline == cornerCount-1)*initialColor)); + } + contour->edges[index]->color = color; + } + } + } +} + +struct EdgeColoringInkTrapCorner { + int index; + double prevEdgeLengthEstimate; + bool minor; + EdgeColor color; +}; + +void edgeColoringInkTrap(Shape &shape, double angleThreshold, unsigned long long seed) { + typedef EdgeColoringInkTrapCorner Corner; + double crossThreshold = sin(angleThreshold); + std::vector<Corner> corners; + for (std::vector<Contour>::iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour) { + // Identify corners + double splineLength = 0; + corners.clear(); + if (!contour->edges.empty()) { + Vector2 prevDirection = contour->edges.back()->direction(1); + int index = 0; + for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge, ++index) { + if (isCorner(prevDirection.normalize(), (*edge)->direction(0).normalize(), crossThreshold)) { + Corner corner = { index, splineLength }; + corners.push_back(corner); + splineLength = 0; + } + splineLength += estimateEdgeLength(*edge); + prevDirection = (*edge)->direction(1); + } + } + + // Smooth contour + if (corners.empty()) + for (std::vector<EdgeHolder>::iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) + (*edge)->color = WHITE; + // "Teardrop" case + else if (corners.size() == 1) { + EdgeColor colors[3] = { WHITE, WHITE }; + switchColor(colors[0], seed); + switchColor(colors[2] = colors[0], seed); + int corner = corners[0].index; + if (contour->edges.size() >= 3) { + int m = (int) contour->edges.size(); + for (int i = 0; i < m; ++i) + contour->edges[(corner+i)%m]->color = (colors+1)[int(3+2.875*i/(m-1)-1.4375+.5)-3]; + } else if (contour->edges.size() >= 1) { + // Less than three edge segments for three colors => edges must be split + EdgeSegment *parts[7] = { }; + contour->edges[0]->splitInThirds(parts[0+3*corner], parts[1+3*corner], parts[2+3*corner]); + if (contour->edges.size() >= 2) { + contour->edges[1]->splitInThirds(parts[3-3*corner], parts[4-3*corner], parts[5-3*corner]); + parts[0]->color = parts[1]->color = colors[0]; + parts[2]->color = parts[3]->color = colors[1]; + parts[4]->color = parts[5]->color = colors[2]; + } else { + parts[0]->color = colors[0]; + parts[1]->color = colors[1]; + parts[2]->color = colors[2]; + } + contour->edges.clear(); + for (int i = 0; parts[i]; ++i) + contour->edges.push_back(EdgeHolder(parts[i])); + } + } + // Multiple corners + else { + int cornerCount = (int) corners.size(); + int majorCornerCount = cornerCount; + if (cornerCount > 3) { + corners.begin()->prevEdgeLengthEstimate += splineLength; + for (int i = 0; i < cornerCount; ++i) { + if ( + corners[i].prevEdgeLengthEstimate > corners[(i+1)%cornerCount].prevEdgeLengthEstimate && + corners[(i+1)%cornerCount].prevEdgeLengthEstimate < corners[(i+2)%cornerCount].prevEdgeLengthEstimate + ) { + corners[i].minor = true; + --majorCornerCount; + } + } + } + EdgeColor color = WHITE; + EdgeColor initialColor = BLACK; + for (int i = 0; i < cornerCount; ++i) { + if (!corners[i].minor) { + --majorCornerCount; + switchColor(color, seed, EdgeColor(!majorCornerCount*initialColor)); + corners[i].color = color; + if (!initialColor) + initialColor = color; + } + } + for (int i = 0; i < cornerCount; ++i) { + if (corners[i].minor) { + EdgeColor nextColor = corners[(i+1)%cornerCount].color; + corners[i].color = EdgeColor((color&nextColor)^WHITE); + } else + color = corners[i].color; + } + int spline = 0; + int start = corners[0].index; + color = corners[0].color; + int m = (int) contour->edges.size(); + for (int i = 0; i < m; ++i) { + int index = (start+i)%m; + if (spline+1 < cornerCount && corners[spline+1].index == index) + color = corners[++spline].color; + contour->edges[index]->color = color; + } + } + } +} + +// EDGE COLORING BY DISTANCE - EXPERIMENTAL IMPLEMENTATION - WORK IN PROGRESS +#define MAX_RECOLOR_STEPS 16 +#define EDGE_DISTANCE_PRECISION 16 + +static double edgeToEdgeDistance(const EdgeSegment &a, const EdgeSegment &b, int precision) { + if (a.point(0) == b.point(0) || a.point(0) == b.point(1) || a.point(1) == b.point(0) || a.point(1) == b.point(1)) + return 0; + double iFac = 1./precision; + double minDistance = (b.point(0)-a.point(0)).length(); + for (int i = 0; i <= precision; ++i) { + double t = iFac*i; + double d = fabs(a.signedDistance(b.point(t), t).distance); + minDistance = min(minDistance, d); + } + for (int i = 0; i <= precision; ++i) { + double t = iFac*i; + double d = fabs(b.signedDistance(a.point(t), t).distance); + minDistance = min(minDistance, d); + } + return minDistance; +} + +static double splineToSplineDistance(EdgeSegment * const *edgeSegments, int aStart, int aEnd, int bStart, int bEnd, int precision) { + double minDistance = fabs(SignedDistance::INFINITE.distance); + for (int ai = aStart; ai < aEnd; ++ai) + for (int bi = bStart; bi < bEnd && minDistance; ++bi) { + double d = edgeToEdgeDistance(*edgeSegments[ai], *edgeSegments[bi], precision); + minDistance = min(minDistance, d); + } + return minDistance; +} + +static void colorSecondDegreeGraph(int *coloring, const int * const *edgeMatrix, int vertexCount, unsigned long long seed) { + for (int i = 0; i < vertexCount; ++i) { + int possibleColors = 7; + for (int j = 0; j < i; ++j) { + if (edgeMatrix[i][j]) + possibleColors &= ~(1<<coloring[j]); + } + int color = 0; + switch (possibleColors) { + case 1: + color = 0; + break; + case 2: + color = 1; + break; + case 3: + color = (int) seed&1; + seed >>= 1; + break; + case 4: + color = 2; + break; + case 5: + color = ((int) seed+1&1)<<1; + seed >>= 1; + break; + case 6: + color = ((int) seed&1)+1; + seed >>= 1; + break; + case 7: + color = int((seed+i)%3); + seed /= 3; + break; + } + coloring[i] = color; + } +} + +static int vertexPossibleColors(const int *coloring, const int *edgeVector, int vertexCount) { + int usedColors = 0; + for (int i = 0; i < vertexCount; ++i) + if (edgeVector[i]) + usedColors |= 1<<coloring[i]; + return 7&~usedColors; +} + +static void uncolorSameNeighbors(std::queue<int> &uncolored, int *coloring, const int * const *edgeMatrix, int vertex, int vertexCount) { + for (int i = vertex+1; i < vertexCount; ++i) { + if (edgeMatrix[vertex][i] && coloring[i] == coloring[vertex]) { + coloring[i] = -1; + uncolored.push(i); + } + } + for (int i = 0; i < vertex; ++i) { + if (edgeMatrix[vertex][i] && coloring[i] == coloring[vertex]) { + coloring[i] = -1; + uncolored.push(i); + } + } +} + +static bool tryAddEdge(int *coloring, int * const *edgeMatrix, int vertexCount, int vertexA, int vertexB, int *coloringBuffer) { + static const int FIRST_POSSIBLE_COLOR[8] = { -1, 0, 1, 0, 2, 2, 1, 0 }; + edgeMatrix[vertexA][vertexB] = 1; + edgeMatrix[vertexB][vertexA] = 1; + if (coloring[vertexA] != coloring[vertexB]) + return true; + int bPossibleColors = vertexPossibleColors(coloring, edgeMatrix[vertexB], vertexCount); + if (bPossibleColors) { + coloring[vertexB] = FIRST_POSSIBLE_COLOR[bPossibleColors]; + return true; + } + memcpy(coloringBuffer, coloring, sizeof(int)*vertexCount); + std::queue<int> uncolored; + { + int *coloring = coloringBuffer; + coloring[vertexB] = FIRST_POSSIBLE_COLOR[7&~(1<<coloring[vertexA])]; + uncolorSameNeighbors(uncolored, coloring, edgeMatrix, vertexB, vertexCount); + int step = 0; + while (!uncolored.empty() && step < MAX_RECOLOR_STEPS) { + int i = uncolored.front(); + uncolored.pop(); + int possibleColors = vertexPossibleColors(coloring, edgeMatrix[i], vertexCount); + if (possibleColors) { + coloring[i] = FIRST_POSSIBLE_COLOR[possibleColors]; + continue; + } + do { + coloring[i] = step++%3; + } while (edgeMatrix[i][vertexA] && coloring[i] == coloring[vertexA]); + uncolorSameNeighbors(uncolored, coloring, edgeMatrix, i, vertexCount); + } + } + if (!uncolored.empty()) { + edgeMatrix[vertexA][vertexB] = 0; + edgeMatrix[vertexB][vertexA] = 0; + return false; + } + memcpy(coloring, coloringBuffer, sizeof(int)*vertexCount); + return true; +} + +static int cmpDoublePtr(const void *a, const void *b) { + return sign(**reinterpret_cast<const double * const *>(a)-**reinterpret_cast<const double * const *>(b)); +} + +void edgeColoringByDistance(Shape &shape, double angleThreshold, unsigned long long seed) { + + std::vector<EdgeSegment *> edgeSegments; + std::vector<int> splineStarts; + + double crossThreshold = sin(angleThreshold); + std::vector<int> corners; + for (std::vector<Contour>::iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour) + if (!contour->edges.empty()) { + // Identify corners + corners.clear(); + Vector2 prevDirection = contour->edges.back()->direction(1); + int index = 0; + for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge, ++index) { + if (isCorner(prevDirection.normalize(), (*edge)->direction(0).normalize(), crossThreshold)) + corners.push_back(index); + prevDirection = (*edge)->direction(1); + } + + splineStarts.push_back((int) edgeSegments.size()); + // Smooth contour + if (corners.empty()) + for (std::vector<EdgeHolder>::iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) + edgeSegments.push_back(&**edge); + // "Teardrop" case + else if (corners.size() == 1) { + int corner = corners[0]; + if (contour->edges.size() >= 3) { + int m = (int) contour->edges.size(); + for (int i = 0; i < m; ++i) { + if (i == m/2) + splineStarts.push_back((int) edgeSegments.size()); + if (int(3+2.875*i/(m-1)-1.4375+.5)-3) + edgeSegments.push_back(&*contour->edges[(corner+i)%m]); + else + contour->edges[(corner+i)%m]->color = WHITE; + } + } else if (contour->edges.size() >= 1) { + // Less than three edge segments for three colors => edges must be split + EdgeSegment *parts[7] = { }; + contour->edges[0]->splitInThirds(parts[0+3*corner], parts[1+3*corner], parts[2+3*corner]); + if (contour->edges.size() >= 2) { + contour->edges[1]->splitInThirds(parts[3-3*corner], parts[4-3*corner], parts[5-3*corner]); + edgeSegments.push_back(parts[0]); + edgeSegments.push_back(parts[1]); + parts[2]->color = parts[3]->color = WHITE; + splineStarts.push_back((int) edgeSegments.size()); + edgeSegments.push_back(parts[4]); + edgeSegments.push_back(parts[5]); + } else { + edgeSegments.push_back(parts[0]); + parts[1]->color = WHITE; + splineStarts.push_back((int) edgeSegments.size()); + edgeSegments.push_back(parts[2]); + } + contour->edges.clear(); + for (int i = 0; parts[i]; ++i) + contour->edges.push_back(EdgeHolder(parts[i])); + } + } + // Multiple corners + else { + int cornerCount = (int) corners.size(); + int spline = 0; + int start = corners[0]; + int m = (int) contour->edges.size(); + for (int i = 0; i < m; ++i) { + int index = (start+i)%m; + if (spline+1 < cornerCount && corners[spline+1] == index) { + splineStarts.push_back((int) edgeSegments.size()); + ++spline; + } + edgeSegments.push_back(&*contour->edges[index]); + } + } + } + splineStarts.push_back((int) edgeSegments.size()); + + int segmentCount = (int) edgeSegments.size(); + int splineCount = (int) splineStarts.size()-1; + if (!splineCount) + return; + + std::vector<double> distanceMatrixStorage(splineCount*splineCount); + std::vector<double *> distanceMatrix(splineCount); + for (int i = 0; i < splineCount; ++i) + distanceMatrix[i] = &distanceMatrixStorage[i*splineCount]; + const double *distanceMatrixBase = &distanceMatrixStorage[0]; + + for (int i = 0; i < splineCount; ++i) { + distanceMatrix[i][i] = -1; + for (int j = i+1; j < splineCount; ++j) { + double dist = splineToSplineDistance(&edgeSegments[0], splineStarts[i], splineStarts[i+1], splineStarts[j], splineStarts[j+1], EDGE_DISTANCE_PRECISION); + distanceMatrix[i][j] = dist; + distanceMatrix[j][i] = dist; + } + } + + std::vector<const double *> graphEdgeDistances; + graphEdgeDistances.reserve(splineCount*(splineCount-1)/2); + for (int i = 0; i < splineCount; ++i) + for (int j = i+1; j < splineCount; ++j) + graphEdgeDistances.push_back(&distanceMatrix[i][j]); + int graphEdgeCount = (int) graphEdgeDistances.size(); + if (!graphEdgeDistances.empty()) + qsort(&graphEdgeDistances[0], graphEdgeDistances.size(), sizeof(const double *), &cmpDoublePtr); + + std::vector<int> edgeMatrixStorage(splineCount*splineCount); + std::vector<int *> edgeMatrix(splineCount); + for (int i = 0; i < splineCount; ++i) + edgeMatrix[i] = &edgeMatrixStorage[i*splineCount]; + int nextEdge = 0; + for (; nextEdge < graphEdgeCount && !*graphEdgeDistances[nextEdge]; ++nextEdge) { + int elem = graphEdgeDistances[nextEdge]-distanceMatrixBase; + int row = elem/splineCount; + int col = elem%splineCount; + edgeMatrix[row][col] = 1; + edgeMatrix[col][row] = 1; + } + + std::vector<int> coloring(2*splineCount); + colorSecondDegreeGraph(&coloring[0], &edgeMatrix[0], splineCount, seed); + for (; nextEdge < graphEdgeCount; ++nextEdge) { + int elem = graphEdgeDistances[nextEdge]-distanceMatrixBase; + tryAddEdge(&coloring[0], &edgeMatrix[0], splineCount, elem/splineCount, elem%splineCount, &coloring[splineCount]); + } + + const EdgeColor colors[3] = { YELLOW, CYAN, MAGENTA }; + int spline = -1; + for (int i = 0; i < segmentCount; ++i) { + if (splineStarts[spline+1] == i) + ++spline; + edgeSegments[i]->color = colors[coloring[spline]]; + } +} + +} diff --git a/thirdparty/msdfgen/core/edge-coloring.h b/thirdparty/msdfgen/core/edge-coloring.h new file mode 100644 index 0000000000..ffd5e6dce8 --- /dev/null +++ b/thirdparty/msdfgen/core/edge-coloring.h @@ -0,0 +1,29 @@ + +#pragma once + +#include "Shape.h" + +#define MSDFGEN_EDGE_LENGTH_PRECISION 4 + +namespace msdfgen { + +/** Assigns colors to edges of the shape in accordance to the multi-channel distance field technique. + * May split some edges if necessary. + * angleThreshold specifies the maximum angle (in radians) to be considered a corner, for example 3 (~172 degrees). + * Values below 1/2 PI will be treated as the external angle. + */ +void edgeColoringSimple(Shape &shape, double angleThreshold, unsigned long long seed = 0); + +/** The alternative "ink trap" coloring strategy is designed for better results with typefaces + * that use ink traps as a design feature. It guarantees that even if all edges that are shorter than + * both their neighboring edges are removed, the coloring remains consistent with the established rules. + */ +void edgeColoringInkTrap(Shape &shape, double angleThreshold, unsigned long long seed = 0); + +/** The alternative coloring by distance tries to use different colors for edges that are close together. + * This should theoretically be the best strategy on average. However, since it needs to compute the distance + * between all pairs of edges, and perform a graph optimization task, it is much slower than the rest. + */ +void edgeColoringByDistance(Shape &shape, double angleThreshold, unsigned long long seed = 0); + +} diff --git a/thirdparty/msdfgen/core/edge-segments.cpp b/thirdparty/msdfgen/core/edge-segments.cpp new file mode 100644 index 0000000000..5274a9a5a1 --- /dev/null +++ b/thirdparty/msdfgen/core/edge-segments.cpp @@ -0,0 +1,504 @@ + +#include "edge-segments.h" + +#include "arithmetics.hpp" +#include "equation-solver.h" + +namespace msdfgen { + +void EdgeSegment::distanceToPseudoDistance(SignedDistance &distance, Point2 origin, double param) const { + if (param < 0) { + Vector2 dir = direction(0).normalize(); + Vector2 aq = origin-point(0); + double ts = dotProduct(aq, dir); + if (ts < 0) { + double pseudoDistance = crossProduct(aq, dir); + if (fabs(pseudoDistance) <= fabs(distance.distance)) { + distance.distance = pseudoDistance; + distance.dot = 0; + } + } + } else if (param > 1) { + Vector2 dir = direction(1).normalize(); + Vector2 bq = origin-point(1); + double ts = dotProduct(bq, dir); + if (ts > 0) { + double pseudoDistance = crossProduct(bq, dir); + if (fabs(pseudoDistance) <= fabs(distance.distance)) { + distance.distance = pseudoDistance; + distance.dot = 0; + } + } + } +} + +LinearSegment::LinearSegment(Point2 p0, Point2 p1, EdgeColor edgeColor) : EdgeSegment(edgeColor) { + p[0] = p0; + p[1] = p1; +} + +QuadraticSegment::QuadraticSegment(Point2 p0, Point2 p1, Point2 p2, EdgeColor edgeColor) : EdgeSegment(edgeColor) { + if (p1 == p0 || p1 == p2) + p1 = 0.5*(p0+p2); + p[0] = p0; + p[1] = p1; + p[2] = p2; +} + +CubicSegment::CubicSegment(Point2 p0, Point2 p1, Point2 p2, Point2 p3, EdgeColor edgeColor) : EdgeSegment(edgeColor) { + if ((p1 == p0 || p1 == p3) && (p2 == p0 || p2 == p3)) { + p1 = mix(p0, p3, 1/3.); + p2 = mix(p0, p3, 2/3.); + } + p[0] = p0; + p[1] = p1; + p[2] = p2; + p[3] = p3; +} + +LinearSegment * LinearSegment::clone() const { + return new LinearSegment(p[0], p[1], color); +} + +QuadraticSegment * QuadraticSegment::clone() const { + return new QuadraticSegment(p[0], p[1], p[2], color); +} + +CubicSegment * CubicSegment::clone() const { + return new CubicSegment(p[0], p[1], p[2], p[3], color); +} + +Point2 LinearSegment::point(double param) const { + return mix(p[0], p[1], param); +} + +Point2 QuadraticSegment::point(double param) const { + return mix(mix(p[0], p[1], param), mix(p[1], p[2], param), param); +} + +Point2 CubicSegment::point(double param) const { + Vector2 p12 = mix(p[1], p[2], param); + return mix(mix(mix(p[0], p[1], param), p12, param), mix(p12, mix(p[2], p[3], param), param), param); +} + +Vector2 LinearSegment::direction(double param) const { + return p[1]-p[0]; +} + +Vector2 QuadraticSegment::direction(double param) const { + Vector2 tangent = mix(p[1]-p[0], p[2]-p[1], param); + if (!tangent) + return p[2]-p[0]; + return tangent; +} + +Vector2 CubicSegment::direction(double param) const { + Vector2 tangent = mix(mix(p[1]-p[0], p[2]-p[1], param), mix(p[2]-p[1], p[3]-p[2], param), param); + if (!tangent) { + if (param == 0) return p[2]-p[0]; + if (param == 1) return p[3]-p[1]; + } + return tangent; +} + +Vector2 LinearSegment::directionChange(double param) const { + return Vector2(); +} + +Vector2 QuadraticSegment::directionChange(double param) const { + return (p[2]-p[1])-(p[1]-p[0]); +} + +Vector2 CubicSegment::directionChange(double param) const { + return mix((p[2]-p[1])-(p[1]-p[0]), (p[3]-p[2])-(p[2]-p[1]), param); +} + +double LinearSegment::length() const { + return (p[1]-p[0]).length(); +} + +double QuadraticSegment::length() const { + Vector2 ab = p[1]-p[0]; + Vector2 br = p[2]-p[1]-ab; + double abab = dotProduct(ab, ab); + double abbr = dotProduct(ab, br); + double brbr = dotProduct(br, br); + double abLen = sqrt(abab); + double brLen = sqrt(brbr); + double crs = crossProduct(ab, br); + double h = sqrt(abab+abbr+abbr+brbr); + return ( + brLen*((abbr+brbr)*h-abbr*abLen)+ + crs*crs*log((brLen*h+abbr+brbr)/(brLen*abLen+abbr)) + )/(brbr*brLen); +} + +SignedDistance LinearSegment::signedDistance(Point2 origin, double ¶m) const { + Vector2 aq = origin-p[0]; + Vector2 ab = p[1]-p[0]; + param = dotProduct(aq, ab)/dotProduct(ab, ab); + Vector2 eq = p[param > .5]-origin; + double endpointDistance = eq.length(); + if (param > 0 && param < 1) { + double orthoDistance = dotProduct(ab.getOrthonormal(false), aq); + if (fabs(orthoDistance) < endpointDistance) + return SignedDistance(orthoDistance, 0); + } + return SignedDistance(nonZeroSign(crossProduct(aq, ab))*endpointDistance, fabs(dotProduct(ab.normalize(), eq.normalize()))); +} + +SignedDistance QuadraticSegment::signedDistance(Point2 origin, double ¶m) const { + Vector2 qa = p[0]-origin; + Vector2 ab = p[1]-p[0]; + Vector2 br = p[2]-p[1]-ab; + double a = dotProduct(br, br); + double b = 3*dotProduct(ab, br); + double c = 2*dotProduct(ab, ab)+dotProduct(qa, br); + double d = dotProduct(qa, ab); + double t[3]; + int solutions = solveCubic(t, a, b, c, d); + + Vector2 epDir = direction(0); + double minDistance = nonZeroSign(crossProduct(epDir, qa))*qa.length(); // distance from A + param = -dotProduct(qa, epDir)/dotProduct(epDir, epDir); + { + epDir = direction(1); + double distance = (p[2]-origin).length(); // distance from B + if (distance < fabs(minDistance)) { + minDistance = nonZeroSign(crossProduct(epDir, p[2]-origin))*distance; + param = dotProduct(origin-p[1], epDir)/dotProduct(epDir, epDir); + } + } + for (int i = 0; i < solutions; ++i) { + if (t[i] > 0 && t[i] < 1) { + Point2 qe = qa+2*t[i]*ab+t[i]*t[i]*br; + double distance = qe.length(); + if (distance <= fabs(minDistance)) { + minDistance = nonZeroSign(crossProduct(ab+t[i]*br, qe))*distance; + param = t[i]; + } + } + } + + if (param >= 0 && param <= 1) + return SignedDistance(minDistance, 0); + if (param < .5) + return SignedDistance(minDistance, fabs(dotProduct(direction(0).normalize(), qa.normalize()))); + else + return SignedDistance(minDistance, fabs(dotProduct(direction(1).normalize(), (p[2]-origin).normalize()))); +} + +SignedDistance CubicSegment::signedDistance(Point2 origin, double ¶m) const { + Vector2 qa = p[0]-origin; + Vector2 ab = p[1]-p[0]; + Vector2 br = p[2]-p[1]-ab; + Vector2 as = (p[3]-p[2])-(p[2]-p[1])-br; + + Vector2 epDir = direction(0); + double minDistance = nonZeroSign(crossProduct(epDir, qa))*qa.length(); // distance from A + param = -dotProduct(qa, epDir)/dotProduct(epDir, epDir); + { + epDir = direction(1); + double distance = (p[3]-origin).length(); // distance from B + if (distance < fabs(minDistance)) { + minDistance = nonZeroSign(crossProduct(epDir, p[3]-origin))*distance; + param = dotProduct(epDir-(p[3]-origin), epDir)/dotProduct(epDir, epDir); + } + } + // Iterative minimum distance search + for (int i = 0; i <= MSDFGEN_CUBIC_SEARCH_STARTS; ++i) { + double t = (double) i/MSDFGEN_CUBIC_SEARCH_STARTS; + Vector2 qe = qa+3*t*ab+3*t*t*br+t*t*t*as; + for (int step = 0; step < MSDFGEN_CUBIC_SEARCH_STEPS; ++step) { + // Improve t + Vector2 d1 = 3*ab+6*t*br+3*t*t*as; + Vector2 d2 = 6*br+6*t*as; + t -= dotProduct(qe, d1)/(dotProduct(d1, d1)+dotProduct(qe, d2)); + if (t <= 0 || t >= 1) + break; + qe = qa+3*t*ab+3*t*t*br+t*t*t*as; + double distance = qe.length(); + if (distance < fabs(minDistance)) { + minDistance = nonZeroSign(crossProduct(d1, qe))*distance; + param = t; + } + } + } + + if (param >= 0 && param <= 1) + return SignedDistance(minDistance, 0); + if (param < .5) + return SignedDistance(minDistance, fabs(dotProduct(direction(0).normalize(), qa.normalize()))); + else + return SignedDistance(minDistance, fabs(dotProduct(direction(1).normalize(), (p[3]-origin).normalize()))); +} + +int LinearSegment::scanlineIntersections(double x[3], int dy[3], double y) const { + if ((y >= p[0].y && y < p[1].y) || (y >= p[1].y && y < p[0].y)) { + double param = (y-p[0].y)/(p[1].y-p[0].y); + x[0] = mix(p[0].x, p[1].x, param); + dy[0] = sign(p[1].y-p[0].y); + return 1; + } + return 0; +} + +int QuadraticSegment::scanlineIntersections(double x[3], int dy[3], double y) const { + int total = 0; + int nextDY = y > p[0].y ? 1 : -1; + x[total] = p[0].x; + if (p[0].y == y) { + if (p[0].y < p[1].y || (p[0].y == p[1].y && p[0].y < p[2].y)) + dy[total++] = 1; + else + nextDY = 1; + } + { + Vector2 ab = p[1]-p[0]; + Vector2 br = p[2]-p[1]-ab; + double t[2]; + int solutions = solveQuadratic(t, br.y, 2*ab.y, p[0].y-y); + // Sort solutions + double tmp; + if (solutions >= 2 && t[0] > t[1]) + tmp = t[0], t[0] = t[1], t[1] = tmp; + for (int i = 0; i < solutions && total < 2; ++i) { + if (t[i] >= 0 && t[i] <= 1) { + x[total] = p[0].x+2*t[i]*ab.x+t[i]*t[i]*br.x; + if (nextDY*(ab.y+t[i]*br.y) >= 0) { + dy[total++] = nextDY; + nextDY = -nextDY; + } + } + } + } + if (p[2].y == y) { + if (nextDY > 0 && total > 0) { + --total; + nextDY = -1; + } + if ((p[2].y < p[1].y || (p[2].y == p[1].y && p[2].y < p[0].y)) && total < 2) { + x[total] = p[2].x; + if (nextDY < 0) { + dy[total++] = -1; + nextDY = 1; + } + } + } + if (nextDY != (y >= p[2].y ? 1 : -1)) { + if (total > 0) + --total; + else { + if (fabs(p[2].y-y) < fabs(p[0].y-y)) + x[total] = p[2].x; + dy[total++] = nextDY; + } + } + return total; +} + +int CubicSegment::scanlineIntersections(double x[3], int dy[3], double y) const { + int total = 0; + int nextDY = y > p[0].y ? 1 : -1; + x[total] = p[0].x; + if (p[0].y == y) { + if (p[0].y < p[1].y || (p[0].y == p[1].y && (p[0].y < p[2].y || (p[0].y == p[2].y && p[0].y < p[3].y)))) + dy[total++] = 1; + else + nextDY = 1; + } + { + Vector2 ab = p[1]-p[0]; + Vector2 br = p[2]-p[1]-ab; + Vector2 as = (p[3]-p[2])-(p[2]-p[1])-br; + double t[3]; + int solutions = solveCubic(t, as.y, 3*br.y, 3*ab.y, p[0].y-y); + // Sort solutions + double tmp; + if (solutions >= 2) { + if (t[0] > t[1]) + tmp = t[0], t[0] = t[1], t[1] = tmp; + if (solutions >= 3 && t[1] > t[2]) { + tmp = t[1], t[1] = t[2], t[2] = tmp; + if (t[0] > t[1]) + tmp = t[0], t[0] = t[1], t[1] = tmp; + } + } + for (int i = 0; i < solutions && total < 3; ++i) { + if (t[i] >= 0 && t[i] <= 1) { + x[total] = p[0].x+3*t[i]*ab.x+3*t[i]*t[i]*br.x+t[i]*t[i]*t[i]*as.x; + if (nextDY*(ab.y+2*t[i]*br.y+t[i]*t[i]*as.y) >= 0) { + dy[total++] = nextDY; + nextDY = -nextDY; + } + } + } + } + if (p[3].y == y) { + if (nextDY > 0 && total > 0) { + --total; + nextDY = -1; + } + if ((p[3].y < p[2].y || (p[3].y == p[2].y && (p[3].y < p[1].y || (p[3].y == p[1].y && p[3].y < p[0].y)))) && total < 3) { + x[total] = p[3].x; + if (nextDY < 0) { + dy[total++] = -1; + nextDY = 1; + } + } + } + if (nextDY != (y >= p[3].y ? 1 : -1)) { + if (total > 0) + --total; + else { + if (fabs(p[3].y-y) < fabs(p[0].y-y)) + x[total] = p[3].x; + dy[total++] = nextDY; + } + } + return total; +} + +static void pointBounds(Point2 p, double &l, double &b, double &r, double &t) { + if (p.x < l) l = p.x; + if (p.y < b) b = p.y; + if (p.x > r) r = p.x; + if (p.y > t) t = p.y; +} + +void LinearSegment::bound(double &l, double &b, double &r, double &t) const { + pointBounds(p[0], l, b, r, t); + pointBounds(p[1], l, b, r, t); +} + +void QuadraticSegment::bound(double &l, double &b, double &r, double &t) const { + pointBounds(p[0], l, b, r, t); + pointBounds(p[2], l, b, r, t); + Vector2 bot = (p[1]-p[0])-(p[2]-p[1]); + if (bot.x) { + double param = (p[1].x-p[0].x)/bot.x; + if (param > 0 && param < 1) + pointBounds(point(param), l, b, r, t); + } + if (bot.y) { + double param = (p[1].y-p[0].y)/bot.y; + if (param > 0 && param < 1) + pointBounds(point(param), l, b, r, t); + } +} + +void CubicSegment::bound(double &l, double &b, double &r, double &t) const { + pointBounds(p[0], l, b, r, t); + pointBounds(p[3], l, b, r, t); + Vector2 a0 = p[1]-p[0]; + Vector2 a1 = 2*(p[2]-p[1]-a0); + Vector2 a2 = p[3]-3*p[2]+3*p[1]-p[0]; + double params[2]; + int solutions; + solutions = solveQuadratic(params, a2.x, a1.x, a0.x); + for (int i = 0; i < solutions; ++i) + if (params[i] > 0 && params[i] < 1) + pointBounds(point(params[i]), l, b, r, t); + solutions = solveQuadratic(params, a2.y, a1.y, a0.y); + for (int i = 0; i < solutions; ++i) + if (params[i] > 0 && params[i] < 1) + pointBounds(point(params[i]), l, b, r, t); +} + +void LinearSegment::reverse() { + Point2 tmp = p[0]; + p[0] = p[1]; + p[1] = tmp; +} + +void QuadraticSegment::reverse() { + Point2 tmp = p[0]; + p[0] = p[2]; + p[2] = tmp; +} + +void CubicSegment::reverse() { + Point2 tmp = p[0]; + p[0] = p[3]; + p[3] = tmp; + tmp = p[1]; + p[1] = p[2]; + p[2] = tmp; +} + +void LinearSegment::moveStartPoint(Point2 to) { + p[0] = to; +} + +void QuadraticSegment::moveStartPoint(Point2 to) { + Vector2 origSDir = p[0]-p[1]; + Point2 origP1 = p[1]; + p[1] += crossProduct(p[0]-p[1], to-p[0])/crossProduct(p[0]-p[1], p[2]-p[1])*(p[2]-p[1]); + p[0] = to; + if (dotProduct(origSDir, p[0]-p[1]) < 0) + p[1] = origP1; +} + +void CubicSegment::moveStartPoint(Point2 to) { + p[1] += to-p[0]; + p[0] = to; +} + +void LinearSegment::moveEndPoint(Point2 to) { + p[1] = to; +} + +void QuadraticSegment::moveEndPoint(Point2 to) { + Vector2 origEDir = p[2]-p[1]; + Point2 origP1 = p[1]; + p[1] += crossProduct(p[2]-p[1], to-p[2])/crossProduct(p[2]-p[1], p[0]-p[1])*(p[0]-p[1]); + p[2] = to; + if (dotProduct(origEDir, p[2]-p[1]) < 0) + p[1] = origP1; +} + +void CubicSegment::moveEndPoint(Point2 to) { + p[2] += to-p[3]; + p[3] = to; +} + +void LinearSegment::splitInThirds(EdgeSegment *&part1, EdgeSegment *&part2, EdgeSegment *&part3) const { + part1 = new LinearSegment(p[0], point(1/3.), color); + part2 = new LinearSegment(point(1/3.), point(2/3.), color); + part3 = new LinearSegment(point(2/3.), p[1], color); +} + +void QuadraticSegment::splitInThirds(EdgeSegment *&part1, EdgeSegment *&part2, EdgeSegment *&part3) const { + part1 = new QuadraticSegment(p[0], mix(p[0], p[1], 1/3.), point(1/3.), color); + part2 = new QuadraticSegment(point(1/3.), mix(mix(p[0], p[1], 5/9.), mix(p[1], p[2], 4/9.), .5), point(2/3.), color); + part3 = new QuadraticSegment(point(2/3.), mix(p[1], p[2], 2/3.), p[2], color); +} + +void CubicSegment::splitInThirds(EdgeSegment *&part1, EdgeSegment *&part2, EdgeSegment *&part3) const { + part1 = new CubicSegment(p[0], p[0] == p[1] ? p[0] : mix(p[0], p[1], 1/3.), mix(mix(p[0], p[1], 1/3.), mix(p[1], p[2], 1/3.), 1/3.), point(1/3.), color); + part2 = new CubicSegment(point(1/3.), + mix(mix(mix(p[0], p[1], 1/3.), mix(p[1], p[2], 1/3.), 1/3.), mix(mix(p[1], p[2], 1/3.), mix(p[2], p[3], 1/3.), 1/3.), 2/3.), + mix(mix(mix(p[0], p[1], 2/3.), mix(p[1], p[2], 2/3.), 2/3.), mix(mix(p[1], p[2], 2/3.), mix(p[2], p[3], 2/3.), 2/3.), 1/3.), + point(2/3.), color); + part3 = new CubicSegment(point(2/3.), mix(mix(p[1], p[2], 2/3.), mix(p[2], p[3], 2/3.), 2/3.), p[2] == p[3] ? p[3] : mix(p[2], p[3], 2/3.), p[3], color); +} + +EdgeSegment * QuadraticSegment::convertToCubic() const { + return new CubicSegment(p[0], mix(p[0], p[1], 2/3.), mix(p[1], p[2], 1/3.), p[2], color); +} + +void CubicSegment::deconverge(int param, double amount) { + Vector2 dir = direction(param); + Vector2 normal = dir.getOrthonormal(); + double h = dotProduct(directionChange(param)-dir, normal); + switch (param) { + case 0: + p[1] += amount*(dir+sign(h)*sqrt(fabs(h))*normal); + break; + case 1: + p[2] -= amount*(dir-sign(h)*sqrt(fabs(h))*normal); + break; + } +} + +} diff --git a/thirdparty/msdfgen/core/edge-segments.h b/thirdparty/msdfgen/core/edge-segments.h new file mode 100644 index 0000000000..1c8fb599ff --- /dev/null +++ b/thirdparty/msdfgen/core/edge-segments.h @@ -0,0 +1,122 @@ + +#pragma once + +#include "Vector2.h" +#include "SignedDistance.h" +#include "EdgeColor.h" + +namespace msdfgen { + +// Parameters for iterative search of closest point on a cubic Bezier curve. Increase for higher precision. +#define MSDFGEN_CUBIC_SEARCH_STARTS 4 +#define MSDFGEN_CUBIC_SEARCH_STEPS 4 + +/// An abstract edge segment. +class EdgeSegment { + +public: + EdgeColor color; + + EdgeSegment(EdgeColor edgeColor = WHITE) : color(edgeColor) { } + virtual ~EdgeSegment() { } + /// Creates a copy of the edge segment. + virtual EdgeSegment * clone() const = 0; + /// Returns the point on the edge specified by the parameter (between 0 and 1). + virtual Point2 point(double param) const = 0; + /// Returns the direction the edge has at the point specified by the parameter. + virtual Vector2 direction(double param) const = 0; + /// Returns the change of direction (second derivative) at the point specified by the parameter. + virtual Vector2 directionChange(double param) const = 0; + /// Returns the minimum signed distance between origin and the edge. + virtual SignedDistance signedDistance(Point2 origin, double ¶m) const = 0; + /// Converts a previously retrieved signed distance from origin to pseudo-distance. + virtual void distanceToPseudoDistance(SignedDistance &distance, Point2 origin, double param) const; + /// Outputs a list of (at most three) intersections (their X coordinates) with an infinite horizontal scanline at y and returns how many there are. + virtual int scanlineIntersections(double x[3], int dy[3], double y) const = 0; + /// Adjusts the bounding box to fit the edge segment. + virtual void bound(double &l, double &b, double &r, double &t) const = 0; + + /// Reverses the edge (swaps its start point and end point). + virtual void reverse() = 0; + /// Moves the start point of the edge segment. + virtual void moveStartPoint(Point2 to) = 0; + /// Moves the end point of the edge segment. + virtual void moveEndPoint(Point2 to) = 0; + /// Splits the edge segments into thirds which together represent the original edge. + virtual void splitInThirds(EdgeSegment *&part1, EdgeSegment *&part2, EdgeSegment *&part3) const = 0; + +}; + +/// A line segment. +class LinearSegment : public EdgeSegment { + +public: + Point2 p[2]; + + LinearSegment(Point2 p0, Point2 p1, EdgeColor edgeColor = WHITE); + LinearSegment * clone() const; + Point2 point(double param) const; + Vector2 direction(double param) const; + Vector2 directionChange(double param) const; + double length() const; + SignedDistance signedDistance(Point2 origin, double ¶m) const; + int scanlineIntersections(double x[3], int dy[3], double y) const; + void bound(double &l, double &b, double &r, double &t) const; + + void reverse(); + void moveStartPoint(Point2 to); + void moveEndPoint(Point2 to); + void splitInThirds(EdgeSegment *&part1, EdgeSegment *&part2, EdgeSegment *&part3) const; + +}; + +/// A quadratic Bezier curve. +class QuadraticSegment : public EdgeSegment { + +public: + Point2 p[3]; + + QuadraticSegment(Point2 p0, Point2 p1, Point2 p2, EdgeColor edgeColor = WHITE); + QuadraticSegment * clone() const; + Point2 point(double param) const; + Vector2 direction(double param) const; + Vector2 directionChange(double param) const; + double length() const; + SignedDistance signedDistance(Point2 origin, double ¶m) const; + int scanlineIntersections(double x[3], int dy[3], double y) const; + void bound(double &l, double &b, double &r, double &t) const; + + void reverse(); + void moveStartPoint(Point2 to); + void moveEndPoint(Point2 to); + void splitInThirds(EdgeSegment *&part1, EdgeSegment *&part2, EdgeSegment *&part3) const; + + EdgeSegment * convertToCubic() const; + +}; + +/// A cubic Bezier curve. +class CubicSegment : public EdgeSegment { + +public: + Point2 p[4]; + + CubicSegment(Point2 p0, Point2 p1, Point2 p2, Point2 p3, EdgeColor edgeColor = WHITE); + CubicSegment * clone() const; + Point2 point(double param) const; + Vector2 direction(double param) const; + Vector2 directionChange(double param) const; + SignedDistance signedDistance(Point2 origin, double ¶m) const; + int scanlineIntersections(double x[3], int dy[3], double y) const; + void bound(double &l, double &b, double &r, double &t) const; + + void reverse(); + void moveStartPoint(Point2 to); + void moveEndPoint(Point2 to); + void splitInThirds(EdgeSegment *&part1, EdgeSegment *&part2, EdgeSegment *&part3) const; + + void deconverge(int param, double amount); + +}; + +} diff --git a/thirdparty/msdfgen/core/edge-selectors.cpp b/thirdparty/msdfgen/core/edge-selectors.cpp new file mode 100644 index 0000000000..aee78847fb --- /dev/null +++ b/thirdparty/msdfgen/core/edge-selectors.cpp @@ -0,0 +1,261 @@ + +#include "edge-selectors.h" + +#include "arithmetics.hpp" + +namespace msdfgen { + +#define DISTANCE_DELTA_FACTOR 1.001 + +TrueDistanceSelector::EdgeCache::EdgeCache() : absDistance(0) { } + +void TrueDistanceSelector::reset(const Point2 &p) { + double delta = DISTANCE_DELTA_FACTOR*(p-this->p).length(); + minDistance.distance += nonZeroSign(minDistance.distance)*delta; + this->p = p; +} + +void TrueDistanceSelector::addEdge(EdgeCache &cache, const EdgeSegment *prevEdge, const EdgeSegment *edge, const EdgeSegment *nextEdge) { + double delta = DISTANCE_DELTA_FACTOR*(p-cache.point).length(); + if (cache.absDistance-delta <= fabs(minDistance.distance)) { + double dummy; + SignedDistance distance = edge->signedDistance(p, dummy); + if (distance < minDistance) + minDistance = distance; + cache.point = p; + cache.absDistance = fabs(distance.distance); + } +} + +void TrueDistanceSelector::merge(const TrueDistanceSelector &other) { + if (other.minDistance < minDistance) + minDistance = other.minDistance; +} + +TrueDistanceSelector::DistanceType TrueDistanceSelector::distance() const { + return minDistance.distance; +} + +PseudoDistanceSelectorBase::EdgeCache::EdgeCache() : absDistance(0), aDomainDistance(0), bDomainDistance(0), aPseudoDistance(0), bPseudoDistance(0) { } + +bool PseudoDistanceSelectorBase::getPseudoDistance(double &distance, const Vector2 &ep, const Vector2 &edgeDir) { + double ts = dotProduct(ep, edgeDir); + if (ts > 0) { + double pseudoDistance = crossProduct(ep, edgeDir); + if (fabs(pseudoDistance) < fabs(distance)) { + distance = pseudoDistance; + return true; + } + } + return false; +} + +PseudoDistanceSelectorBase::PseudoDistanceSelectorBase() : minNegativePseudoDistance(-fabs(minTrueDistance.distance)), minPositivePseudoDistance(fabs(minTrueDistance.distance)), nearEdge(NULL), nearEdgeParam(0) { } + +void PseudoDistanceSelectorBase::reset(double delta) { + minTrueDistance.distance += nonZeroSign(minTrueDistance.distance)*delta; + minNegativePseudoDistance = -fabs(minTrueDistance.distance); + minPositivePseudoDistance = fabs(minTrueDistance.distance); + nearEdge = NULL; + nearEdgeParam = 0; +} + +bool PseudoDistanceSelectorBase::isEdgeRelevant(const EdgeCache &cache, const EdgeSegment *edge, const Point2 &p) const { + double delta = DISTANCE_DELTA_FACTOR*(p-cache.point).length(); + return ( + cache.absDistance-delta <= fabs(minTrueDistance.distance) || + fabs(cache.aDomainDistance) < delta || + fabs(cache.bDomainDistance) < delta || + (cache.aDomainDistance > 0 && (cache.aPseudoDistance < 0 ? + cache.aPseudoDistance+delta >= minNegativePseudoDistance : + cache.aPseudoDistance-delta <= minPositivePseudoDistance + )) || + (cache.bDomainDistance > 0 && (cache.bPseudoDistance < 0 ? + cache.bPseudoDistance+delta >= minNegativePseudoDistance : + cache.bPseudoDistance-delta <= minPositivePseudoDistance + )) + ); +} + +void PseudoDistanceSelectorBase::addEdgeTrueDistance(const EdgeSegment *edge, const SignedDistance &distance, double param) { + if (distance < minTrueDistance) { + minTrueDistance = distance; + nearEdge = edge; + nearEdgeParam = param; + } +} + +void PseudoDistanceSelectorBase::addEdgePseudoDistance(double distance) { + if (distance <= 0 && distance > minNegativePseudoDistance) + minNegativePseudoDistance = distance; + if (distance >= 0 && distance < minPositivePseudoDistance) + minPositivePseudoDistance = distance; +} + +void PseudoDistanceSelectorBase::merge(const PseudoDistanceSelectorBase &other) { + if (other.minTrueDistance < minTrueDistance) { + minTrueDistance = other.minTrueDistance; + nearEdge = other.nearEdge; + nearEdgeParam = other.nearEdgeParam; + } + if (other.minNegativePseudoDistance > minNegativePseudoDistance) + minNegativePseudoDistance = other.minNegativePseudoDistance; + if (other.minPositivePseudoDistance < minPositivePseudoDistance) + minPositivePseudoDistance = other.minPositivePseudoDistance; +} + +double PseudoDistanceSelectorBase::computeDistance(const Point2 &p) const { + double minDistance = minTrueDistance.distance < 0 ? minNegativePseudoDistance : minPositivePseudoDistance; + if (nearEdge) { + SignedDistance distance = minTrueDistance; + nearEdge->distanceToPseudoDistance(distance, p, nearEdgeParam); + if (fabs(distance.distance) < fabs(minDistance)) + minDistance = distance.distance; + } + return minDistance; +} + +SignedDistance PseudoDistanceSelectorBase::trueDistance() const { + return minTrueDistance; +} + +void PseudoDistanceSelector::reset(const Point2 &p) { + double delta = DISTANCE_DELTA_FACTOR*(p-this->p).length(); + PseudoDistanceSelectorBase::reset(delta); + this->p = p; +} + +void PseudoDistanceSelector::addEdge(EdgeCache &cache, const EdgeSegment *prevEdge, const EdgeSegment *edge, const EdgeSegment *nextEdge) { + if (isEdgeRelevant(cache, edge, p)) { + double param; + SignedDistance distance = edge->signedDistance(p, param); + addEdgeTrueDistance(edge, distance, param); + cache.point = p; + cache.absDistance = fabs(distance.distance); + + Vector2 ap = p-edge->point(0); + Vector2 bp = p-edge->point(1); + Vector2 aDir = edge->direction(0).normalize(true); + Vector2 bDir = edge->direction(1).normalize(true); + Vector2 prevDir = prevEdge->direction(1).normalize(true); + Vector2 nextDir = nextEdge->direction(0).normalize(true); + double add = dotProduct(ap, (prevDir+aDir).normalize(true)); + double bdd = -dotProduct(bp, (bDir+nextDir).normalize(true)); + if (add > 0) { + double pd = distance.distance; + if (getPseudoDistance(pd, ap, -aDir)) + addEdgePseudoDistance(pd = -pd); + cache.aPseudoDistance = pd; + } + if (bdd > 0) { + double pd = distance.distance; + if (getPseudoDistance(pd, bp, bDir)) + addEdgePseudoDistance(pd); + cache.bPseudoDistance = pd; + } + cache.aDomainDistance = add; + cache.bDomainDistance = bdd; + } +} + +PseudoDistanceSelector::DistanceType PseudoDistanceSelector::distance() const { + return computeDistance(p); +} + +void MultiDistanceSelector::reset(const Point2 &p) { + double delta = DISTANCE_DELTA_FACTOR*(p-this->p).length(); + r.reset(delta); + g.reset(delta); + b.reset(delta); + this->p = p; +} + +void MultiDistanceSelector::addEdge(EdgeCache &cache, const EdgeSegment *prevEdge, const EdgeSegment *edge, const EdgeSegment *nextEdge) { + if ( + (edge->color&RED && r.isEdgeRelevant(cache, edge, p)) || + (edge->color&GREEN && g.isEdgeRelevant(cache, edge, p)) || + (edge->color&BLUE && b.isEdgeRelevant(cache, edge, p)) + ) { + double param; + SignedDistance distance = edge->signedDistance(p, param); + if (edge->color&RED) + r.addEdgeTrueDistance(edge, distance, param); + if (edge->color&GREEN) + g.addEdgeTrueDistance(edge, distance, param); + if (edge->color&BLUE) + b.addEdgeTrueDistance(edge, distance, param); + cache.point = p; + cache.absDistance = fabs(distance.distance); + + Vector2 ap = p-edge->point(0); + Vector2 bp = p-edge->point(1); + Vector2 aDir = edge->direction(0).normalize(true); + Vector2 bDir = edge->direction(1).normalize(true); + Vector2 prevDir = prevEdge->direction(1).normalize(true); + Vector2 nextDir = nextEdge->direction(0).normalize(true); + double add = dotProduct(ap, (prevDir+aDir).normalize(true)); + double bdd = -dotProduct(bp, (bDir+nextDir).normalize(true)); + if (add > 0) { + double pd = distance.distance; + if (PseudoDistanceSelectorBase::getPseudoDistance(pd, ap, -aDir)) { + pd = -pd; + if (edge->color&RED) + r.addEdgePseudoDistance(pd); + if (edge->color&GREEN) + g.addEdgePseudoDistance(pd); + if (edge->color&BLUE) + b.addEdgePseudoDistance(pd); + } + cache.aPseudoDistance = pd; + } + if (bdd > 0) { + double pd = distance.distance; + if (PseudoDistanceSelectorBase::getPseudoDistance(pd, bp, bDir)) { + if (edge->color&RED) + r.addEdgePseudoDistance(pd); + if (edge->color&GREEN) + g.addEdgePseudoDistance(pd); + if (edge->color&BLUE) + b.addEdgePseudoDistance(pd); + } + cache.bPseudoDistance = pd; + } + cache.aDomainDistance = add; + cache.bDomainDistance = bdd; + } +} + +void MultiDistanceSelector::merge(const MultiDistanceSelector &other) { + r.merge(other.r); + g.merge(other.g); + b.merge(other.b); +} + +MultiDistanceSelector::DistanceType MultiDistanceSelector::distance() const { + MultiDistance multiDistance; + multiDistance.r = r.computeDistance(p); + multiDistance.g = g.computeDistance(p); + multiDistance.b = b.computeDistance(p); + return multiDistance; +} + +SignedDistance MultiDistanceSelector::trueDistance() const { + SignedDistance distance = r.trueDistance(); + if (g.trueDistance() < distance) + distance = g.trueDistance(); + if (b.trueDistance() < distance) + distance = b.trueDistance(); + return distance; +} + +MultiAndTrueDistanceSelector::DistanceType MultiAndTrueDistanceSelector::distance() const { + MultiDistance multiDistance = MultiDistanceSelector::distance(); + MultiAndTrueDistance mtd; + mtd.r = multiDistance.r; + mtd.g = multiDistance.g; + mtd.b = multiDistance.b; + mtd.a = trueDistance().distance; + return mtd; +} + +} diff --git a/thirdparty/msdfgen/core/edge-selectors.h b/thirdparty/msdfgen/core/edge-selectors.h new file mode 100644 index 0000000000..3620999f82 --- /dev/null +++ b/thirdparty/msdfgen/core/edge-selectors.h @@ -0,0 +1,117 @@ + +#pragma once + +#include "Vector2.h" +#include "SignedDistance.h" +#include "edge-segments.h" + +namespace msdfgen { + +struct MultiDistance { + double r, g, b; +}; +struct MultiAndTrueDistance : MultiDistance { + double a; +}; + +/// Selects the nearest edge by its true distance. +class TrueDistanceSelector { + +public: + typedef double DistanceType; + + struct EdgeCache { + Point2 point; + double absDistance; + + EdgeCache(); + }; + + void reset(const Point2 &p); + void addEdge(EdgeCache &cache, const EdgeSegment *prevEdge, const EdgeSegment *edge, const EdgeSegment *nextEdge); + void merge(const TrueDistanceSelector &other); + DistanceType distance() const; + +private: + Point2 p; + SignedDistance minDistance; + +}; + +class PseudoDistanceSelectorBase { + +public: + struct EdgeCache { + Point2 point; + double absDistance; + double aDomainDistance, bDomainDistance; + double aPseudoDistance, bPseudoDistance; + + EdgeCache(); + }; + + static bool getPseudoDistance(double &distance, const Vector2 &ep, const Vector2 &edgeDir); + + PseudoDistanceSelectorBase(); + void reset(double delta); + bool isEdgeRelevant(const EdgeCache &cache, const EdgeSegment *edge, const Point2 &p) const; + void addEdgeTrueDistance(const EdgeSegment *edge, const SignedDistance &distance, double param); + void addEdgePseudoDistance(double distance); + void merge(const PseudoDistanceSelectorBase &other); + double computeDistance(const Point2 &p) const; + SignedDistance trueDistance() const; + +private: + SignedDistance minTrueDistance; + double minNegativePseudoDistance; + double minPositivePseudoDistance; + const EdgeSegment *nearEdge; + double nearEdgeParam; + +}; + +/// Selects the nearest edge by its pseudo-distance. +class PseudoDistanceSelector : public PseudoDistanceSelectorBase { + +public: + typedef double DistanceType; + + void reset(const Point2 &p); + void addEdge(EdgeCache &cache, const EdgeSegment *prevEdge, const EdgeSegment *edge, const EdgeSegment *nextEdge); + DistanceType distance() const; + +private: + Point2 p; + +}; + +/// Selects the nearest edge for each of the three channels by its pseudo-distance. +class MultiDistanceSelector { + +public: + typedef MultiDistance DistanceType; + typedef PseudoDistanceSelectorBase::EdgeCache EdgeCache; + + void reset(const Point2 &p); + void addEdge(EdgeCache &cache, const EdgeSegment *prevEdge, const EdgeSegment *edge, const EdgeSegment *nextEdge); + void merge(const MultiDistanceSelector &other); + DistanceType distance() const; + SignedDistance trueDistance() const; + +private: + Point2 p; + PseudoDistanceSelectorBase r, g, b; + +}; + +/// Selects the nearest edge for each of the three color channels by its pseudo-distance and by true distance for the alpha channel. +class MultiAndTrueDistanceSelector : public MultiDistanceSelector { + +public: + typedef MultiAndTrueDistance DistanceType; + + DistanceType distance() const; + +}; + +} diff --git a/thirdparty/msdfgen/core/equation-solver.cpp b/thirdparty/msdfgen/core/equation-solver.cpp new file mode 100644 index 0000000000..fbe906428b --- /dev/null +++ b/thirdparty/msdfgen/core/equation-solver.cpp @@ -0,0 +1,77 @@ + +#include "equation-solver.h" + +#define _USE_MATH_DEFINES +#include <cmath> + +#define TOO_LARGE_RATIO 1e12 + +namespace msdfgen { + +int solveQuadratic(double x[2], double a, double b, double c) { + // a = 0 -> linear equation + if (a == 0 || fabs(b)+fabs(c) > TOO_LARGE_RATIO*fabs(a)) { + // a, b = 0 -> no solution + if (b == 0 || fabs(c) > TOO_LARGE_RATIO*fabs(b)) { + if (c == 0) + return -1; // 0 = 0 + return 0; + } + x[0] = -c/b; + return 1; + } + double dscr = b*b-4*a*c; + if (dscr > 0) { + dscr = sqrt(dscr); + x[0] = (-b+dscr)/(2*a); + x[1] = (-b-dscr)/(2*a); + return 2; + } else if (dscr == 0) { + x[0] = -b/(2*a); + return 1; + } else + return 0; +} + +static int solveCubicNormed(double x[3], double a, double b, double c) { + double a2 = a*a; + double q = (a2 - 3*b)/9; + double r = (a*(2*a2-9*b) + 27*c)/54; + double r2 = r*r; + double q3 = q*q*q; + double A, B; + if (r2 < q3) { + double t = r/sqrt(q3); + if (t < -1) t = -1; + if (t > 1) t = 1; + t = acos(t); + a /= 3; q = -2*sqrt(q); + x[0] = q*cos(t/3)-a; + x[1] = q*cos((t+2*M_PI)/3)-a; + x[2] = q*cos((t-2*M_PI)/3)-a; + return 3; + } else { + A = -pow(fabs(r)+sqrt(r2-q3), 1/3.); + if (r < 0) A = -A; + B = A == 0 ? 0 : q/A; + a /= 3; + x[0] = (A+B)-a; + x[1] = -0.5*(A+B)-a; + x[2] = 0.5*sqrt(3.)*(A-B); + if (fabs(x[2]) < 1e-14) + return 2; + return 1; + } +} + +int solveCubic(double x[3], double a, double b, double c, double d) { + if (a != 0) { + double bn = b/a, cn = c/a, dn = d/a; + // Check that a isn't "almost zero" + if (fabs(bn) < TOO_LARGE_RATIO && fabs(cn) < TOO_LARGE_RATIO && fabs(dn) < TOO_LARGE_RATIO) + return solveCubicNormed(x, bn, cn, dn); + } + return solveQuadratic(x, b, c, d); +} + +} diff --git a/thirdparty/msdfgen/core/equation-solver.h b/thirdparty/msdfgen/core/equation-solver.h new file mode 100644 index 0000000000..bae097b2b9 --- /dev/null +++ b/thirdparty/msdfgen/core/equation-solver.h @@ -0,0 +1,12 @@ + +#pragma once + +namespace msdfgen { + +// ax^2 + bx + c = 0 +int solveQuadratic(double x[2], double a, double b, double c); + +// ax^3 + bx^2 + cx + d = 0 +int solveCubic(double x[3], double a, double b, double c, double d); + +} diff --git a/thirdparty/msdfgen/core/generator-config.h b/thirdparty/msdfgen/core/generator-config.h new file mode 100644 index 0000000000..ddcad961f2 --- /dev/null +++ b/thirdparty/msdfgen/core/generator-config.h @@ -0,0 +1,63 @@ + +#pragma once + +#include <cstdlib> +#include "BitmapRef.hpp" + +namespace msdfgen { + +/// The configuration of the MSDF error correction pass. +struct ErrorCorrectionConfig { + /// The default value of minDeviationRatio. + static const double defaultMinDeviationRatio; + /// The default value of minImproveRatio. + static const double defaultMinImproveRatio; + + /// Mode of operation. + enum Mode { + /// Skips error correction pass. + DISABLED, + /// Corrects all discontinuities of the distance field regardless if edges are adversely affected. + INDISCRIMINATE, + /// Corrects artifacts at edges and other discontinuous distances only if it does not affect edges or corners. + EDGE_PRIORITY, + /// Only corrects artifacts at edges. + EDGE_ONLY + } mode; + /// Configuration of whether to use an algorithm that computes the exact shape distance at the positions of suspected artifacts. This algorithm can be much slower. + enum DistanceCheckMode { + /// Never computes exact shape distance. + DO_NOT_CHECK_DISTANCE, + /// Only computes exact shape distance at edges. Provides a good balance between speed and precision. + CHECK_DISTANCE_AT_EDGE, + /// Computes and compares the exact shape distance for each suspected artifact. + ALWAYS_CHECK_DISTANCE + } distanceCheckMode; + /// The minimum ratio between the actual and maximum expected distance delta to be considered an error. + double minDeviationRatio; + /// The minimum ratio between the pre-correction distance error and the post-correction distance error. Has no effect for DO_NOT_CHECK_DISTANCE. + double minImproveRatio; + /// An optional buffer to avoid dynamic allocation. Must have at least as many bytes as the MSDF has pixels. + byte *buffer; + + inline explicit ErrorCorrectionConfig(Mode mode = EDGE_PRIORITY, DistanceCheckMode distanceCheckMode = CHECK_DISTANCE_AT_EDGE, double minDeviationRatio = defaultMinDeviationRatio, double minImproveRatio = defaultMinImproveRatio, byte *buffer = NULL) : mode(mode), distanceCheckMode(distanceCheckMode), minDeviationRatio(minDeviationRatio), minImproveRatio(minImproveRatio), buffer(buffer) { } +}; + +/// The configuration of the distance field generator algorithm. +struct GeneratorConfig { + /// Specifies whether to use the version of the algorithm that supports overlapping contours with the same winding. May be set to false to improve performance when no such contours are present. + bool overlapSupport; + + inline explicit GeneratorConfig(bool overlapSupport = true) : overlapSupport(overlapSupport) { } +}; + +/// The configuration of the multi-channel distance field generator algorithm. +struct MSDFGeneratorConfig : GeneratorConfig { + /// Configuration of the error correction pass. + ErrorCorrectionConfig errorCorrection; + + inline MSDFGeneratorConfig() { } + inline explicit MSDFGeneratorConfig(bool overlapSupport, const ErrorCorrectionConfig &errorCorrection = ErrorCorrectionConfig()) : GeneratorConfig(overlapSupport), errorCorrection(errorCorrection) { } +}; + +} diff --git a/thirdparty/msdfgen/core/msdf-error-correction.cpp b/thirdparty/msdfgen/core/msdf-error-correction.cpp new file mode 100644 index 0000000000..21ddff8c85 --- /dev/null +++ b/thirdparty/msdfgen/core/msdf-error-correction.cpp @@ -0,0 +1,154 @@ + +#include "msdf-error-correction.h" + +#include <vector> +#include "arithmetics.hpp" +#include "Bitmap.h" +#include "contour-combiners.h" +#include "MSDFErrorCorrection.h" + +namespace msdfgen { + +template <int N> +static void msdfErrorCorrectionInner(const BitmapRef<float, N> &sdf, const Shape &shape, const Projection &projection, double range, const MSDFGeneratorConfig &config) { + if (config.errorCorrection.mode == ErrorCorrectionConfig::DISABLED) + return; + Bitmap<byte, 1> stencilBuffer; + if (!config.errorCorrection.buffer) + stencilBuffer = Bitmap<byte, 1>(sdf.width, sdf.height); + BitmapRef<byte, 1> stencil; + stencil.pixels = config.errorCorrection.buffer ? config.errorCorrection.buffer : (byte *) stencilBuffer; + stencil.width = sdf.width, stencil.height = sdf.height; + MSDFErrorCorrection ec(stencil, projection, range); + ec.setMinDeviationRatio(config.errorCorrection.minDeviationRatio); + ec.setMinImproveRatio(config.errorCorrection.minImproveRatio); + switch (config.errorCorrection.mode) { + case ErrorCorrectionConfig::DISABLED: + case ErrorCorrectionConfig::INDISCRIMINATE: + break; + case ErrorCorrectionConfig::EDGE_PRIORITY: + ec.protectCorners(shape); + ec.protectEdges<N>(sdf); + break; + case ErrorCorrectionConfig::EDGE_ONLY: + ec.protectAll(); + break; + } + if (config.errorCorrection.distanceCheckMode == ErrorCorrectionConfig::DO_NOT_CHECK_DISTANCE || (config.errorCorrection.distanceCheckMode == ErrorCorrectionConfig::CHECK_DISTANCE_AT_EDGE && config.errorCorrection.mode != ErrorCorrectionConfig::EDGE_ONLY)) { + ec.findErrors<N>(sdf); + if (config.errorCorrection.distanceCheckMode == ErrorCorrectionConfig::CHECK_DISTANCE_AT_EDGE) + ec.protectAll(); + } + if (config.errorCorrection.distanceCheckMode == ErrorCorrectionConfig::ALWAYS_CHECK_DISTANCE || config.errorCorrection.distanceCheckMode == ErrorCorrectionConfig::CHECK_DISTANCE_AT_EDGE) { + if (config.overlapSupport) + ec.findErrors<OverlappingContourCombiner, N>(sdf, shape); + else + ec.findErrors<SimpleContourCombiner, N>(sdf, shape); + } + ec.apply(sdf); +} + +template <int N> +static void msdfErrorCorrectionShapeless(const BitmapRef<float, N> &sdf, const Projection &projection, double range, double minDeviationRatio, bool protectAll) { + Bitmap<byte, 1> stencilBuffer(sdf.width, sdf.height); + MSDFErrorCorrection ec(stencilBuffer, projection, range); + ec.setMinDeviationRatio(minDeviationRatio); + if (protectAll) + ec.protectAll(); + ec.findErrors<N>(sdf); + ec.apply(sdf); +} + +void msdfErrorCorrection(const BitmapRef<float, 3> &sdf, const Shape &shape, const Projection &projection, double range, const MSDFGeneratorConfig &config) { + msdfErrorCorrectionInner(sdf, shape, projection, range, config); +} +void msdfErrorCorrection(const BitmapRef<float, 4> &sdf, const Shape &shape, const Projection &projection, double range, const MSDFGeneratorConfig &config) { + msdfErrorCorrectionInner(sdf, shape, projection, range, config); +} + +void msdfFastDistanceErrorCorrection(const BitmapRef<float, 3> &sdf, const Projection &projection, double range, double minDeviationRatio) { + msdfErrorCorrectionShapeless(sdf, projection, range, minDeviationRatio, false); +} +void msdfFastDistanceErrorCorrection(const BitmapRef<float, 4> &sdf, const Projection &projection, double range, double minDeviationRatio) { + msdfErrorCorrectionShapeless(sdf, projection, range, minDeviationRatio, false); +} + +void msdfFastEdgeErrorCorrection(const BitmapRef<float, 3> &sdf, const Projection &projection, double range, double minDeviationRatio) { + msdfErrorCorrectionShapeless(sdf, projection, range, minDeviationRatio, true); +} +void msdfFastEdgeErrorCorrection(const BitmapRef<float, 4> &sdf, const Projection &projection, double range, double minDeviationRatio) { + msdfErrorCorrectionShapeless(sdf, projection, range, minDeviationRatio, true); +} + + +// Legacy version + +inline static bool detectClash(const float *a, const float *b, double threshold) { + // Sort channels so that pairs (a0, b0), (a1, b1), (a2, b2) go from biggest to smallest absolute difference + float a0 = a[0], a1 = a[1], a2 = a[2]; + float b0 = b[0], b1 = b[1], b2 = b[2]; + float tmp; + if (fabsf(b0-a0) < fabsf(b1-a1)) { + tmp = a0, a0 = a1, a1 = tmp; + tmp = b0, b0 = b1, b1 = tmp; + } + if (fabsf(b1-a1) < fabsf(b2-a2)) { + tmp = a1, a1 = a2, a2 = tmp; + tmp = b1, b1 = b2, b2 = tmp; + if (fabsf(b0-a0) < fabsf(b1-a1)) { + tmp = a0, a0 = a1, a1 = tmp; + tmp = b0, b0 = b1, b1 = tmp; + } + } + return (fabsf(b1-a1) >= threshold) && + !(b0 == b1 && b0 == b2) && // Ignore if other pixel has been equalized + fabsf(a2-.5f) >= fabsf(b2-.5f); // Out of the pair, only flag the pixel farther from a shape edge +} + +template <int N> +static void msdfErrorCorrectionInner_legacy(const BitmapRef<float, N> &output, const Vector2 &threshold) { + std::vector<std::pair<int, int> > clashes; + int w = output.width, h = output.height; + for (int y = 0; y < h; ++y) + for (int x = 0; x < w; ++x) { + if ( + (x > 0 && detectClash(output(x, y), output(x-1, y), threshold.x)) || + (x < w-1 && detectClash(output(x, y), output(x+1, y), threshold.x)) || + (y > 0 && detectClash(output(x, y), output(x, y-1), threshold.y)) || + (y < h-1 && detectClash(output(x, y), output(x, y+1), threshold.y)) + ) + clashes.push_back(std::make_pair(x, y)); + } + for (std::vector<std::pair<int, int> >::const_iterator clash = clashes.begin(); clash != clashes.end(); ++clash) { + float *pixel = output(clash->first, clash->second); + float med = median(pixel[0], pixel[1], pixel[2]); + pixel[0] = med, pixel[1] = med, pixel[2] = med; + } +#ifndef MSDFGEN_NO_DIAGONAL_CLASH_DETECTION + clashes.clear(); + for (int y = 0; y < h; ++y) + for (int x = 0; x < w; ++x) { + if ( + (x > 0 && y > 0 && detectClash(output(x, y), output(x-1, y-1), threshold.x+threshold.y)) || + (x < w-1 && y > 0 && detectClash(output(x, y), output(x+1, y-1), threshold.x+threshold.y)) || + (x > 0 && y < h-1 && detectClash(output(x, y), output(x-1, y+1), threshold.x+threshold.y)) || + (x < w-1 && y < h-1 && detectClash(output(x, y), output(x+1, y+1), threshold.x+threshold.y)) + ) + clashes.push_back(std::make_pair(x, y)); + } + for (std::vector<std::pair<int, int> >::const_iterator clash = clashes.begin(); clash != clashes.end(); ++clash) { + float *pixel = output(clash->first, clash->second); + float med = median(pixel[0], pixel[1], pixel[2]); + pixel[0] = med, pixel[1] = med, pixel[2] = med; + } +#endif +} + +void msdfErrorCorrection_legacy(const BitmapRef<float, 3> &output, const Vector2 &threshold) { + msdfErrorCorrectionInner_legacy(output, threshold); +} +void msdfErrorCorrection_legacy(const BitmapRef<float, 4> &output, const Vector2 &threshold) { + msdfErrorCorrectionInner_legacy(output, threshold); +} + +} diff --git a/thirdparty/msdfgen/core/msdf-error-correction.h b/thirdparty/msdfgen/core/msdf-error-correction.h new file mode 100644 index 0000000000..d5384c9329 --- /dev/null +++ b/thirdparty/msdfgen/core/msdf-error-correction.h @@ -0,0 +1,28 @@ + +#pragma once + +#include "Vector2.h" +#include "Projection.h" +#include "Shape.h" +#include "BitmapRef.hpp" +#include "generator-config.h" + +namespace msdfgen { + +/// Predicts potential artifacts caused by the interpolation of the MSDF and corrects them by converting nearby texels to single-channel. +void msdfErrorCorrection(const BitmapRef<float, 3> &sdf, const Shape &shape, const Projection &projection, double range, const MSDFGeneratorConfig &config = MSDFGeneratorConfig()); +void msdfErrorCorrection(const BitmapRef<float, 4> &sdf, const Shape &shape, const Projection &projection, double range, const MSDFGeneratorConfig &config = MSDFGeneratorConfig()); + +/// Applies the simplified error correction to all discontiunous distances (INDISCRIMINATE mode). Does not need shape or translation. +void msdfFastDistanceErrorCorrection(const BitmapRef<float, 3> &sdf, const Projection &projection, double range, double minDeviationRatio = ErrorCorrectionConfig::defaultMinDeviationRatio); +void msdfFastDistanceErrorCorrection(const BitmapRef<float, 4> &sdf, const Projection &projection, double range, double minDeviationRatio = ErrorCorrectionConfig::defaultMinDeviationRatio); + +/// Applies the simplified error correction to edges only (EDGE_ONLY mode). Does not need shape or translation. +void msdfFastEdgeErrorCorrection(const BitmapRef<float, 3> &sdf, const Projection &projection, double range, double minDeviationRatio = ErrorCorrectionConfig::defaultMinDeviationRatio); +void msdfFastEdgeErrorCorrection(const BitmapRef<float, 4> &sdf, const Projection &projection, double range, double minDeviationRatio = ErrorCorrectionConfig::defaultMinDeviationRatio); + +/// The original version of the error correction algorithm. +void msdfErrorCorrection_legacy(const BitmapRef<float, 3> &output, const Vector2 &threshold); +void msdfErrorCorrection_legacy(const BitmapRef<float, 4> &output, const Vector2 &threshold); + +} diff --git a/thirdparty/msdfgen/core/msdfgen.cpp b/thirdparty/msdfgen/core/msdfgen.cpp new file mode 100644 index 0000000000..0289295f14 --- /dev/null +++ b/thirdparty/msdfgen/core/msdfgen.cpp @@ -0,0 +1,288 @@ + +#include "../msdfgen.h" + +#include <vector> +#include "edge-selectors.h" +#include "contour-combiners.h" +#include "ShapeDistanceFinder.h" + +namespace msdfgen { + +template <typename DistanceType> +class DistancePixelConversion; + +template <> +class DistancePixelConversion<double> { + double invRange; +public: + typedef BitmapRef<float, 1> BitmapRefType; + inline explicit DistancePixelConversion(double range) : invRange(1/range) { } + inline void operator()(float *pixels, double distance) const { + *pixels = float(invRange*distance+.5); + } +}; + +template <> +class DistancePixelConversion<MultiDistance> { + double invRange; +public: + typedef BitmapRef<float, 3> BitmapRefType; + inline explicit DistancePixelConversion(double range) : invRange(1/range) { } + inline void operator()(float *pixels, const MultiDistance &distance) const { + pixels[0] = float(invRange*distance.r+.5); + pixels[1] = float(invRange*distance.g+.5); + pixels[2] = float(invRange*distance.b+.5); + } +}; + +template <> +class DistancePixelConversion<MultiAndTrueDistance> { + double invRange; +public: + typedef BitmapRef<float, 4> BitmapRefType; + inline explicit DistancePixelConversion(double range) : invRange(1/range) { } + inline void operator()(float *pixels, const MultiAndTrueDistance &distance) const { + pixels[0] = float(invRange*distance.r+.5); + pixels[1] = float(invRange*distance.g+.5); + pixels[2] = float(invRange*distance.b+.5); + pixels[3] = float(invRange*distance.a+.5); + } +}; + +template <class ContourCombiner> +void generateDistanceField(const typename DistancePixelConversion<typename ContourCombiner::DistanceType>::BitmapRefType &output, const Shape &shape, const Projection &projection, double range) { + DistancePixelConversion<typename ContourCombiner::DistanceType> distancePixelConversion(range); +#ifdef MSDFGEN_USE_OPENMP + #pragma omp parallel +#endif + { + ShapeDistanceFinder<ContourCombiner> distanceFinder(shape); + bool rightToLeft = false; +#ifdef MSDFGEN_USE_OPENMP + #pragma omp for +#endif + for (int y = 0; y < output.height; ++y) { + int row = shape.inverseYAxis ? output.height-y-1 : y; + for (int col = 0; col < output.width; ++col) { + int x = rightToLeft ? output.width-col-1 : col; + Point2 p = projection.unproject(Point2(x+.5, y+.5)); + typename ContourCombiner::DistanceType distance = distanceFinder.distance(p); + distancePixelConversion(output(x, row), distance); + } + rightToLeft = !rightToLeft; + } + } +} + +void generateSDF(const BitmapRef<float, 1> &output, const Shape &shape, const Projection &projection, double range, const GeneratorConfig &config) { + if (config.overlapSupport) + generateDistanceField<OverlappingContourCombiner<TrueDistanceSelector> >(output, shape, projection, range); + else + generateDistanceField<SimpleContourCombiner<TrueDistanceSelector> >(output, shape, projection, range); +} + +void generatePseudoSDF(const BitmapRef<float, 1> &output, const Shape &shape, const Projection &projection, double range, const GeneratorConfig &config) { + if (config.overlapSupport) + generateDistanceField<OverlappingContourCombiner<PseudoDistanceSelector> >(output, shape, projection, range); + else + generateDistanceField<SimpleContourCombiner<PseudoDistanceSelector> >(output, shape, projection, range); +} + +void generateMSDF(const BitmapRef<float, 3> &output, const Shape &shape, const Projection &projection, double range, const MSDFGeneratorConfig &config) { + if (config.overlapSupport) + generateDistanceField<OverlappingContourCombiner<MultiDistanceSelector> >(output, shape, projection, range); + else + generateDistanceField<SimpleContourCombiner<MultiDistanceSelector> >(output, shape, projection, range); + msdfErrorCorrection(output, shape, projection, range, config); +} + +void generateMTSDF(const BitmapRef<float, 4> &output, const Shape &shape, const Projection &projection, double range, const MSDFGeneratorConfig &config) { + if (config.overlapSupport) + generateDistanceField<OverlappingContourCombiner<MultiAndTrueDistanceSelector> >(output, shape, projection, range); + else + generateDistanceField<SimpleContourCombiner<MultiAndTrueDistanceSelector> >(output, shape, projection, range); + msdfErrorCorrection(output, shape, projection, range, config); +} + +// Legacy API + +void generateSDF(const BitmapRef<float, 1> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate, bool overlapSupport) { + generateSDF(output, shape, Projection(scale, translate), range, GeneratorConfig(overlapSupport)); +} + +void generatePseudoSDF(const BitmapRef<float, 1> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate, bool overlapSupport) { + generatePseudoSDF(output, shape, Projection(scale, translate), range, GeneratorConfig(overlapSupport)); +} + +void generateMSDF(const BitmapRef<float, 3> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate, const ErrorCorrectionConfig &errorCorrectionConfig, bool overlapSupport) { + generateMSDF(output, shape, Projection(scale, translate), range, MSDFGeneratorConfig(overlapSupport, errorCorrectionConfig)); +} + +void generateMTSDF(const BitmapRef<float, 4> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate, const ErrorCorrectionConfig &errorCorrectionConfig, bool overlapSupport) { + generateMTSDF(output, shape, Projection(scale, translate), range, MSDFGeneratorConfig(overlapSupport, errorCorrectionConfig)); +} + +// Legacy version + +void generateSDF_legacy(const BitmapRef<float, 1> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate) { +#ifdef MSDFGEN_USE_OPENMP + #pragma omp parallel for +#endif + for (int y = 0; y < output.height; ++y) { + int row = shape.inverseYAxis ? output.height-y-1 : y; + for (int x = 0; x < output.width; ++x) { + double dummy; + Point2 p = Vector2(x+.5, y+.5)/scale-translate; + SignedDistance minDistance; + for (std::vector<Contour>::const_iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour) + for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) { + SignedDistance distance = (*edge)->signedDistance(p, dummy); + if (distance < minDistance) + minDistance = distance; + } + *output(x, row) = float(minDistance.distance/range+.5); + } + } +} + +void generatePseudoSDF_legacy(const BitmapRef<float, 1> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate) { +#ifdef MSDFGEN_USE_OPENMP + #pragma omp parallel for +#endif + for (int y = 0; y < output.height; ++y) { + int row = shape.inverseYAxis ? output.height-y-1 : y; + for (int x = 0; x < output.width; ++x) { + Point2 p = Vector2(x+.5, y+.5)/scale-translate; + SignedDistance minDistance; + const EdgeHolder *nearEdge = NULL; + double nearParam = 0; + for (std::vector<Contour>::const_iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour) + for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) { + double param; + SignedDistance distance = (*edge)->signedDistance(p, param); + if (distance < minDistance) { + minDistance = distance; + nearEdge = &*edge; + nearParam = param; + } + } + if (nearEdge) + (*nearEdge)->distanceToPseudoDistance(minDistance, p, nearParam); + *output(x, row) = float(minDistance.distance/range+.5); + } + } +} + +void generateMSDF_legacy(const BitmapRef<float, 3> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate, ErrorCorrectionConfig errorCorrectionConfig) { +#ifdef MSDFGEN_USE_OPENMP + #pragma omp parallel for +#endif + for (int y = 0; y < output.height; ++y) { + int row = shape.inverseYAxis ? output.height-y-1 : y; + for (int x = 0; x < output.width; ++x) { + Point2 p = Vector2(x+.5, y+.5)/scale-translate; + + struct { + SignedDistance minDistance; + const EdgeHolder *nearEdge; + double nearParam; + } r, g, b; + r.nearEdge = g.nearEdge = b.nearEdge = NULL; + r.nearParam = g.nearParam = b.nearParam = 0; + + for (std::vector<Contour>::const_iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour) + for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) { + double param; + SignedDistance distance = (*edge)->signedDistance(p, param); + if ((*edge)->color&RED && distance < r.minDistance) { + r.minDistance = distance; + r.nearEdge = &*edge; + r.nearParam = param; + } + if ((*edge)->color&GREEN && distance < g.minDistance) { + g.minDistance = distance; + g.nearEdge = &*edge; + g.nearParam = param; + } + if ((*edge)->color&BLUE && distance < b.minDistance) { + b.minDistance = distance; + b.nearEdge = &*edge; + b.nearParam = param; + } + } + + if (r.nearEdge) + (*r.nearEdge)->distanceToPseudoDistance(r.minDistance, p, r.nearParam); + if (g.nearEdge) + (*g.nearEdge)->distanceToPseudoDistance(g.minDistance, p, g.nearParam); + if (b.nearEdge) + (*b.nearEdge)->distanceToPseudoDistance(b.minDistance, p, b.nearParam); + output(x, row)[0] = float(r.minDistance.distance/range+.5); + output(x, row)[1] = float(g.minDistance.distance/range+.5); + output(x, row)[2] = float(b.minDistance.distance/range+.5); + } + } + + errorCorrectionConfig.distanceCheckMode = ErrorCorrectionConfig::DO_NOT_CHECK_DISTANCE; + msdfErrorCorrection(output, shape, Projection(scale, translate), range, MSDFGeneratorConfig(false, errorCorrectionConfig)); +} + +void generateMTSDF_legacy(const BitmapRef<float, 4> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate, ErrorCorrectionConfig errorCorrectionConfig) { +#ifdef MSDFGEN_USE_OPENMP + #pragma omp parallel for +#endif + for (int y = 0; y < output.height; ++y) { + int row = shape.inverseYAxis ? output.height-y-1 : y; + for (int x = 0; x < output.width; ++x) { + Point2 p = Vector2(x+.5, y+.5)/scale-translate; + + SignedDistance minDistance; + struct { + SignedDistance minDistance; + const EdgeHolder *nearEdge; + double nearParam; + } r, g, b; + r.nearEdge = g.nearEdge = b.nearEdge = NULL; + r.nearParam = g.nearParam = b.nearParam = 0; + + for (std::vector<Contour>::const_iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour) + for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) { + double param; + SignedDistance distance = (*edge)->signedDistance(p, param); + if (distance < minDistance) + minDistance = distance; + if ((*edge)->color&RED && distance < r.minDistance) { + r.minDistance = distance; + r.nearEdge = &*edge; + r.nearParam = param; + } + if ((*edge)->color&GREEN && distance < g.minDistance) { + g.minDistance = distance; + g.nearEdge = &*edge; + g.nearParam = param; + } + if ((*edge)->color&BLUE && distance < b.minDistance) { + b.minDistance = distance; + b.nearEdge = &*edge; + b.nearParam = param; + } + } + + if (r.nearEdge) + (*r.nearEdge)->distanceToPseudoDistance(r.minDistance, p, r.nearParam); + if (g.nearEdge) + (*g.nearEdge)->distanceToPseudoDistance(g.minDistance, p, g.nearParam); + if (b.nearEdge) + (*b.nearEdge)->distanceToPseudoDistance(b.minDistance, p, b.nearParam); + output(x, row)[0] = float(r.minDistance.distance/range+.5); + output(x, row)[1] = float(g.minDistance.distance/range+.5); + output(x, row)[2] = float(b.minDistance.distance/range+.5); + output(x, row)[3] = float(minDistance.distance/range+.5); + } + } + + errorCorrectionConfig.distanceCheckMode = ErrorCorrectionConfig::DO_NOT_CHECK_DISTANCE; + msdfErrorCorrection(output, shape, Projection(scale, translate), range, MSDFGeneratorConfig(false, errorCorrectionConfig)); +} + +} diff --git a/thirdparty/msdfgen/core/pixel-conversion.hpp b/thirdparty/msdfgen/core/pixel-conversion.hpp new file mode 100644 index 0000000000..7e9b6d08f0 --- /dev/null +++ b/thirdparty/msdfgen/core/pixel-conversion.hpp @@ -0,0 +1,18 @@ + +#pragma once + +#include "arithmetics.hpp" + +namespace msdfgen { + +typedef unsigned char byte; + +inline byte pixelFloatToByte(float x) { + return byte(clamp(256.f*x, 255.f)); +} + +inline float pixelByteToFloat(byte x) { + return 1.f/255.f*float(x); +} + +} diff --git a/thirdparty/msdfgen/core/rasterization.cpp b/thirdparty/msdfgen/core/rasterization.cpp new file mode 100644 index 0000000000..9aa695a8c1 --- /dev/null +++ b/thirdparty/msdfgen/core/rasterization.cpp @@ -0,0 +1,115 @@ + +#include "rasterization.h" + +#include <vector> +#include "arithmetics.hpp" + +namespace msdfgen { + +void rasterize(const BitmapRef<float, 1> &output, const Shape &shape, const Projection &projection, FillRule fillRule) { + Scanline scanline; + for (int y = 0; y < output.height; ++y) { + int row = shape.inverseYAxis ? output.height-y-1 : y; + shape.scanline(scanline, projection.unprojectY(y+.5)); + for (int x = 0; x < output.width; ++x) + *output(x, row) = (float) scanline.filled(projection.unprojectX(x+.5), fillRule); + } +} + +void distanceSignCorrection(const BitmapRef<float, 1> &sdf, const Shape &shape, const Projection &projection, FillRule fillRule) { + Scanline scanline; + for (int y = 0; y < sdf.height; ++y) { + int row = shape.inverseYAxis ? sdf.height-y-1 : y; + shape.scanline(scanline, projection.unprojectY(y+.5)); + for (int x = 0; x < sdf.width; ++x) { + bool fill = scanline.filled(projection.unprojectX(x+.5), fillRule); + float &sd = *sdf(x, row); + if ((sd > .5f) != fill) + sd = 1.f-sd; + } + } +} + +template <int N> +static void multiDistanceSignCorrection(const BitmapRef<float, N> &sdf, const Shape &shape, const Projection &projection, FillRule fillRule) { + int w = sdf.width, h = sdf.height; + if (!(w*h)) + return; + Scanline scanline; + bool ambiguous = false; + std::vector<char> matchMap; + matchMap.resize(w*h); + char *match = &matchMap[0]; + for (int y = 0; y < h; ++y) { + int row = shape.inverseYAxis ? h-y-1 : y; + shape.scanline(scanline, projection.unprojectY(y+.5)); + for (int x = 0; x < w; ++x) { + bool fill = scanline.filled(projection.unprojectX(x+.5), fillRule); + float *msd = sdf(x, row); + float sd = median(msd[0], msd[1], msd[2]); + if (sd == .5f) + ambiguous = true; + else if ((sd > .5f) != fill) { + msd[0] = 1.f-msd[0]; + msd[1] = 1.f-msd[1]; + msd[2] = 1.f-msd[2]; + *match = -1; + } else + *match = 1; + if (N >= 4 && (msd[3] > .5f) != fill) + msd[3] = 1.f-msd[3]; + ++match; + } + } + // This step is necessary to avoid artifacts when whole shape is inverted + if (ambiguous) { + match = &matchMap[0]; + for (int y = 0; y < h; ++y) { + int row = shape.inverseYAxis ? h-y-1 : y; + for (int x = 0; x < w; ++x) { + if (!*match) { + int neighborMatch = 0; + if (x > 0) neighborMatch += *(match-1); + if (x < w-1) neighborMatch += *(match+1); + if (y > 0) neighborMatch += *(match-w); + if (y < h-1) neighborMatch += *(match+w); + if (neighborMatch < 0) { + float *msd = sdf(x, row); + msd[0] = 1.f-msd[0]; + msd[1] = 1.f-msd[1]; + msd[2] = 1.f-msd[2]; + } + } + ++match; + } + } + } +} + +void distanceSignCorrection(const BitmapRef<float, 3> &sdf, const Shape &shape, const Projection &projection, FillRule fillRule) { + multiDistanceSignCorrection(sdf, shape, projection, fillRule); +} + +void distanceSignCorrection(const BitmapRef<float, 4> &sdf, const Shape &shape, const Projection &projection, FillRule fillRule) { + multiDistanceSignCorrection(sdf, shape, projection, fillRule); +} + +// Legacy API + +void rasterize(const BitmapRef<float, 1> &output, const Shape &shape, const Vector2 &scale, const Vector2 &translate, FillRule fillRule) { + rasterize(output, shape, Projection(scale, translate), fillRule); +} + +void distanceSignCorrection(const BitmapRef<float, 1> &sdf, const Shape &shape, const Vector2 &scale, const Vector2 &translate, FillRule fillRule) { + distanceSignCorrection(sdf, shape, Projection(scale, translate), fillRule); +} + +void distanceSignCorrection(const BitmapRef<float, 3> &sdf, const Shape &shape, const Vector2 &scale, const Vector2 &translate, FillRule fillRule) { + distanceSignCorrection(sdf, shape, Projection(scale, translate), fillRule); +} + +void distanceSignCorrection(const BitmapRef<float, 4> &sdf, const Shape &shape, const Vector2 &scale, const Vector2 &translate, FillRule fillRule) { + distanceSignCorrection(sdf, shape, Projection(scale, translate), fillRule); +} + +} diff --git a/thirdparty/msdfgen/core/rasterization.h b/thirdparty/msdfgen/core/rasterization.h new file mode 100644 index 0000000000..82d0c73d95 --- /dev/null +++ b/thirdparty/msdfgen/core/rasterization.h @@ -0,0 +1,25 @@ + +#pragma once + +#include "Vector2.h" +#include "Shape.h" +#include "Projection.h" +#include "Scanline.h" +#include "BitmapRef.hpp" + +namespace msdfgen { + +/// Rasterizes the shape into a monochrome bitmap. +void rasterize(const BitmapRef<float, 1> &output, const Shape &shape, const Projection &projection, FillRule fillRule = FILL_NONZERO); +/// Fixes the sign of the input signed distance field, so that it matches the shape's rasterized fill. +void distanceSignCorrection(const BitmapRef<float, 1> &sdf, const Shape &shape, const Projection &projection, FillRule fillRule = FILL_NONZERO); +void distanceSignCorrection(const BitmapRef<float, 3> &sdf, const Shape &shape, const Projection &projection, FillRule fillRule = FILL_NONZERO); +void distanceSignCorrection(const BitmapRef<float, 4> &sdf, const Shape &shape, const Projection &projection, FillRule fillRule = FILL_NONZERO); + +// Old version of the function API's kept for backwards compatibility +void rasterize(const BitmapRef<float, 1> &output, const Shape &shape, const Vector2 &scale, const Vector2 &translate, FillRule fillRule = FILL_NONZERO); +void distanceSignCorrection(const BitmapRef<float, 1> &sdf, const Shape &shape, const Vector2 &scale, const Vector2 &translate, FillRule fillRule = FILL_NONZERO); +void distanceSignCorrection(const BitmapRef<float, 3> &sdf, const Shape &shape, const Vector2 &scale, const Vector2 &translate, FillRule fillRule = FILL_NONZERO); +void distanceSignCorrection(const BitmapRef<float, 4> &sdf, const Shape &shape, const Vector2 &scale, const Vector2 &translate, FillRule fillRule = FILL_NONZERO); + +} diff --git a/thirdparty/msdfgen/core/render-sdf.cpp b/thirdparty/msdfgen/core/render-sdf.cpp new file mode 100644 index 0000000000..e282285e59 --- /dev/null +++ b/thirdparty/msdfgen/core/render-sdf.cpp @@ -0,0 +1,108 @@ + +#include "render-sdf.h" + +#include "arithmetics.hpp" +#include "pixel-conversion.hpp" +#include "bitmap-interpolation.hpp" + +namespace msdfgen { + +static float distVal(float dist, double pxRange, float midValue) { + if (!pxRange) + return (float) (dist > midValue); + return (float) clamp((dist-midValue)*pxRange+.5); +} + +void renderSDF(const BitmapRef<float, 1> &output, const BitmapConstRef<float, 1> &sdf, double pxRange, float midValue) { + Vector2 scale((double) sdf.width/output.width, (double) sdf.height/output.height); + pxRange *= (double) (output.width+output.height)/(sdf.width+sdf.height); + for (int y = 0; y < output.height; ++y) + for (int x = 0; x < output.width; ++x) { + float sd; + interpolate(&sd, sdf, scale*Point2(x+.5, y+.5)); + *output(x, y) = distVal(sd, pxRange, midValue); + } +} + +void renderSDF(const BitmapRef<float, 3> &output, const BitmapConstRef<float, 1> &sdf, double pxRange, float midValue) { + Vector2 scale((double) sdf.width/output.width, (double) sdf.height/output.height); + pxRange *= (double) (output.width+output.height)/(sdf.width+sdf.height); + for (int y = 0; y < output.height; ++y) + for (int x = 0; x < output.width; ++x) { + float sd; + interpolate(&sd, sdf, scale*Point2(x+.5, y+.5)); + float v = distVal(sd, pxRange, midValue); + output(x, y)[0] = v; + output(x, y)[1] = v; + output(x, y)[2] = v; + } +} + +void renderSDF(const BitmapRef<float, 1> &output, const BitmapConstRef<float, 3> &sdf, double pxRange, float midValue) { + Vector2 scale((double) sdf.width/output.width, (double) sdf.height/output.height); + pxRange *= (double) (output.width+output.height)/(sdf.width+sdf.height); + for (int y = 0; y < output.height; ++y) + for (int x = 0; x < output.width; ++x) { + float sd[3]; + interpolate(sd, sdf, scale*Point2(x+.5, y+.5)); + *output(x, y) = distVal(median(sd[0], sd[1], sd[2]), pxRange, midValue); + } +} + +void renderSDF(const BitmapRef<float, 3> &output, const BitmapConstRef<float, 3> &sdf, double pxRange, float midValue) { + Vector2 scale((double) sdf.width/output.width, (double) sdf.height/output.height); + pxRange *= (double) (output.width+output.height)/(sdf.width+sdf.height); + for (int y = 0; y < output.height; ++y) + for (int x = 0; x < output.width; ++x) { + float sd[3]; + interpolate(sd, sdf, scale*Point2(x+.5, y+.5)); + output(x, y)[0] = distVal(sd[0], pxRange, midValue); + output(x, y)[1] = distVal(sd[1], pxRange, midValue); + output(x, y)[2] = distVal(sd[2], pxRange, midValue); + } +} + +void renderSDF(const BitmapRef<float, 1> &output, const BitmapConstRef<float, 4> &sdf, double pxRange, float midValue) { + Vector2 scale((double) sdf.width/output.width, (double) sdf.height/output.height); + pxRange *= (double) (output.width+output.height)/(sdf.width+sdf.height); + for (int y = 0; y < output.height; ++y) + for (int x = 0; x < output.width; ++x) { + float sd[4]; + interpolate(sd, sdf, scale*Point2(x+.5, y+.5)); + *output(x, y) = distVal(median(sd[0], sd[1], sd[2]), pxRange, midValue); + } +} + +void renderSDF(const BitmapRef<float, 4> &output, const BitmapConstRef<float, 4> &sdf, double pxRange, float midValue) { + Vector2 scale((double) sdf.width/output.width, (double) sdf.height/output.height); + pxRange *= (double) (output.width+output.height)/(sdf.width+sdf.height); + for (int y = 0; y < output.height; ++y) + for (int x = 0; x < output.width; ++x) { + float sd[4]; + interpolate(sd, sdf, scale*Point2(x+.5, y+.5)); + output(x, y)[0] = distVal(sd[0], pxRange, midValue); + output(x, y)[1] = distVal(sd[1], pxRange, midValue); + output(x, y)[2] = distVal(sd[2], pxRange, midValue); + output(x, y)[3] = distVal(sd[3], pxRange, midValue); + } +} + +void simulate8bit(const BitmapRef<float, 1> &bitmap) { + const float *end = bitmap.pixels+1*bitmap.width*bitmap.height; + for (float *p = bitmap.pixels; p < end; ++p) + *p = pixelByteToFloat(pixelFloatToByte(*p)); +} + +void simulate8bit(const BitmapRef<float, 3> &bitmap) { + const float *end = bitmap.pixels+3*bitmap.width*bitmap.height; + for (float *p = bitmap.pixels; p < end; ++p) + *p = pixelByteToFloat(pixelFloatToByte(*p)); +} + +void simulate8bit(const BitmapRef<float, 4> &bitmap) { + const float *end = bitmap.pixels+4*bitmap.width*bitmap.height; + for (float *p = bitmap.pixels; p < end; ++p) + *p = pixelByteToFloat(pixelFloatToByte(*p)); +} + +} diff --git a/thirdparty/msdfgen/core/render-sdf.h b/thirdparty/msdfgen/core/render-sdf.h new file mode 100644 index 0000000000..7f2d270b67 --- /dev/null +++ b/thirdparty/msdfgen/core/render-sdf.h @@ -0,0 +1,22 @@ + +#pragma once + +#include "Vector2.h" +#include "BitmapRef.hpp" + +namespace msdfgen { + +/// Reconstructs the shape's appearance into output from the distance field sdf. +void renderSDF(const BitmapRef<float, 1> &output, const BitmapConstRef<float, 1> &sdf, double pxRange = 0, float midValue = .5f); +void renderSDF(const BitmapRef<float, 3> &output, const BitmapConstRef<float, 1> &sdf, double pxRange = 0, float midValue = .5f); +void renderSDF(const BitmapRef<float, 1> &output, const BitmapConstRef<float, 3> &sdf, double pxRange = 0, float midValue = .5f); +void renderSDF(const BitmapRef<float, 3> &output, const BitmapConstRef<float, 3> &sdf, double pxRange = 0, float midValue = .5f); +void renderSDF(const BitmapRef<float, 1> &output, const BitmapConstRef<float, 4> &sdf, double pxRange = 0, float midValue = .5f); +void renderSDF(const BitmapRef<float, 4> &output, const BitmapConstRef<float, 4> &sdf, double pxRange = 0, float midValue = .5f); + +/// Snaps the values of the floating-point bitmaps into one of the 256 values representable in a standard 8-bit bitmap. +void simulate8bit(const BitmapRef<float, 1> &bitmap); +void simulate8bit(const BitmapRef<float, 3> &bitmap); +void simulate8bit(const BitmapRef<float, 4> &bitmap); + +} diff --git a/thirdparty/msdfgen/core/save-bmp.cpp b/thirdparty/msdfgen/core/save-bmp.cpp new file mode 100644 index 0000000000..f761ee4f88 --- /dev/null +++ b/thirdparty/msdfgen/core/save-bmp.cpp @@ -0,0 +1,169 @@ + +#define _CRT_SECURE_NO_WARNINGS + +#include "save-bmp.h" + +#include <cstdio> + +#ifdef MSDFGEN_USE_CPP11 + #include <cstdint> +#else + typedef int int32_t; + typedef unsigned uint32_t; + typedef unsigned short uint16_t; + typedef unsigned char uint8_t; +#endif + +#include "pixel-conversion.hpp" + +namespace msdfgen { + +template <typename T> +static bool writeValue(FILE *file, T value) { + #ifdef __BIG_ENDIAN__ + T reverse = 0; + for (int i = 0; i < sizeof(T); ++i) { + reverse <<= 8; + reverse |= value&T(0xff); + value >>= 8; + } + return fwrite(&reverse, sizeof(T), 1, file) == 1; + #else + return fwrite(&value, sizeof(T), 1, file) == 1; + #endif +} + +static bool writeBmpHeader(FILE *file, int width, int height, int &paddedWidth) { + paddedWidth = (3*width+3)&~3; + const uint32_t bitmapStart = 54; + const uint32_t bitmapSize = paddedWidth*height; + const uint32_t fileSize = bitmapStart+bitmapSize; + + writeValue<uint16_t>(file, 0x4d42u); + writeValue<uint32_t>(file, fileSize); + writeValue<uint16_t>(file, 0); + writeValue<uint16_t>(file, 0); + writeValue<uint32_t>(file, bitmapStart); + + writeValue<uint32_t>(file, 40); + writeValue<int32_t>(file, width); + writeValue<int32_t>(file, height); + writeValue<uint16_t>(file, 1); + writeValue<uint16_t>(file, 24); + writeValue<uint32_t>(file, 0); + writeValue<uint32_t>(file, bitmapSize); + writeValue<uint32_t>(file, 2835); + writeValue<uint32_t>(file, 2835); + writeValue<uint32_t>(file, 0); + writeValue<uint32_t>(file, 0); + + return true; +} + +bool saveBmp(const BitmapConstRef<byte, 1> &bitmap, const char *filename) { + FILE *file = fopen(filename, "wb"); + if (!file) + return false; + + int paddedWidth; + writeBmpHeader(file, bitmap.width, bitmap.height, paddedWidth); + + const uint8_t padding[4] = { }; + int padLength = paddedWidth-3*bitmap.width; + for (int y = 0; y < bitmap.height; ++y) { + for (int x = 0; x < bitmap.width; ++x) { + uint8_t px = (uint8_t) *bitmap(x, y); + fwrite(&px, sizeof(uint8_t), 1, file); + fwrite(&px, sizeof(uint8_t), 1, file); + fwrite(&px, sizeof(uint8_t), 1, file); + } + fwrite(padding, 1, padLength, file); + } + + return !fclose(file); +} + +bool saveBmp(const BitmapConstRef<byte, 3> &bitmap, const char *filename) { + FILE *file = fopen(filename, "wb"); + if (!file) + return false; + + int paddedWidth; + writeBmpHeader(file, bitmap.width, bitmap.height, paddedWidth); + + const uint8_t padding[4] = { }; + int padLength = paddedWidth-3*bitmap.width; + for (int y = 0; y < bitmap.height; ++y) { + for (int x = 0; x < bitmap.width; ++x) { + uint8_t bgr[3] = { + (uint8_t) bitmap(x, y)[2], + (uint8_t) bitmap(x, y)[1], + (uint8_t) bitmap(x, y)[0] + }; + fwrite(bgr, sizeof(uint8_t), 3, file); + } + fwrite(padding, 1, padLength, file); + } + + return !fclose(file); +} + +bool saveBmp(const BitmapConstRef<byte, 4> &bitmap, const char *filename) { + // RGBA not supported by the BMP format + return false; +} + +bool saveBmp(const BitmapConstRef<float, 1> &bitmap, const char *filename) { + FILE *file = fopen(filename, "wb"); + if (!file) + return false; + + int paddedWidth; + writeBmpHeader(file, bitmap.width, bitmap.height, paddedWidth); + + const uint8_t padding[4] = { }; + int padLength = paddedWidth-3*bitmap.width; + for (int y = 0; y < bitmap.height; ++y) { + for (int x = 0; x < bitmap.width; ++x) { + uint8_t px = (uint8_t) pixelFloatToByte(*bitmap(x, y)); + fwrite(&px, sizeof(uint8_t), 1, file); + fwrite(&px, sizeof(uint8_t), 1, file); + fwrite(&px, sizeof(uint8_t), 1, file); + } + fwrite(padding, 1, padLength, file); + } + + return !fclose(file); +} + +bool saveBmp(const BitmapConstRef<float, 3> &bitmap, const char *filename) { + FILE *file = fopen(filename, "wb"); + if (!file) + return false; + + int paddedWidth; + writeBmpHeader(file, bitmap.width, bitmap.height, paddedWidth); + + const uint8_t padding[4] = { }; + int padLength = paddedWidth-3*bitmap.width; + for (int y = 0; y < bitmap.height; ++y) { + for (int x = 0; x < bitmap.width; ++x) { + uint8_t bgr[3] = { + (uint8_t) pixelFloatToByte(bitmap(x, y)[2]), + (uint8_t) pixelFloatToByte(bitmap(x, y)[1]), + (uint8_t) pixelFloatToByte(bitmap(x, y)[0]) + }; + fwrite(bgr, sizeof(uint8_t), 3, file); + } + fwrite(padding, 1, padLength, file); + } + + return !fclose(file); +} + +bool saveBmp(const BitmapConstRef<float, 4> &bitmap, const char *filename) { + // RGBA not supported by the BMP format + return false; +} + +} diff --git a/thirdparty/msdfgen/core/save-bmp.h b/thirdparty/msdfgen/core/save-bmp.h new file mode 100644 index 0000000000..98f852921f --- /dev/null +++ b/thirdparty/msdfgen/core/save-bmp.h @@ -0,0 +1,16 @@ + +#pragma once + +#include "BitmapRef.hpp" + +namespace msdfgen { + +/// Saves the bitmap as a BMP file. +bool saveBmp(const BitmapConstRef<byte, 1> &bitmap, const char *filename); +bool saveBmp(const BitmapConstRef<byte, 3> &bitmap, const char *filename); +bool saveBmp(const BitmapConstRef<byte, 4> &bitmap, const char *filename); +bool saveBmp(const BitmapConstRef<float, 1> &bitmap, const char *filename); +bool saveBmp(const BitmapConstRef<float, 3> &bitmap, const char *filename); +bool saveBmp(const BitmapConstRef<float, 4> &bitmap, const char *filename); + +} diff --git a/thirdparty/msdfgen/core/save-tiff.cpp b/thirdparty/msdfgen/core/save-tiff.cpp new file mode 100644 index 0000000000..71405e00e5 --- /dev/null +++ b/thirdparty/msdfgen/core/save-tiff.cpp @@ -0,0 +1,190 @@ + +#define _CRT_SECURE_NO_WARNINGS + +#include "save-tiff.h" + +#include <cstdio> + +#ifdef MSDFGEN_USE_CPP11 + #include <cstdint> +#else + typedef int int32_t; + typedef unsigned uint32_t; + typedef unsigned short uint16_t; + typedef unsigned char uint8_t; +#endif + +namespace msdfgen { + +template <typename T> +static bool writeValue(FILE *file, T value) { + return fwrite(&value, sizeof(T), 1, file) == 1; +} +template <typename T> +static void writeValueRepeated(FILE *file, T value, int times) { + for (int i = 0; i < times; ++i) + writeValue(file, value); +} + +static bool writeTiffHeader(FILE *file, int width, int height, int channels) { + #ifdef __BIG_ENDIAN__ + writeValue<uint16_t>(file, 0x4d4du); + #else + writeValue<uint16_t>(file, 0x4949u); + #endif + writeValue<uint16_t>(file, 42); + writeValue<uint32_t>(file, 0x0008u); // Offset of first IFD + // Offset = 0x0008 + + writeValue<uint16_t>(file, 15); // Number of IFD entries + + // ImageWidth + writeValue<uint16_t>(file, 0x0100u); + writeValue<uint16_t>(file, 0x0004u); + writeValue<uint32_t>(file, 1); + writeValue<int32_t>(file, width); + // ImageLength + writeValue<uint16_t>(file, 0x0101u); + writeValue<uint16_t>(file, 0x0004u); + writeValue<uint32_t>(file, 1); + writeValue<int32_t>(file, height); + // BitsPerSample + writeValue<uint16_t>(file, 0x0102u); + writeValue<uint16_t>(file, 0x0003u); + writeValue<uint32_t>(file, channels); + if (channels > 1) + writeValue<uint32_t>(file, 0x00c2u); // Offset of 32, 32, ... + else { + writeValue<uint16_t>(file, 32); + writeValue<uint16_t>(file, 0); + } + // Compression + writeValue<uint16_t>(file, 0x0103u); + writeValue<uint16_t>(file, 0x0003u); + writeValue<uint32_t>(file, 1); + writeValue<uint16_t>(file, 1); + writeValue<uint16_t>(file, 0); + // PhotometricInterpretation + writeValue<uint16_t>(file, 0x0106u); + writeValue<uint16_t>(file, 0x0003u); + writeValue<uint32_t>(file, 1); + writeValue<uint16_t>(file, channels >= 3 ? 2 : 1); + writeValue<uint16_t>(file, 0); + // StripOffsets + writeValue<uint16_t>(file, 0x0111u); + writeValue<uint16_t>(file, 0x0004u); + writeValue<uint32_t>(file, 1); + writeValue<uint32_t>(file, 0x00d2u+(channels > 1)*channels*12); // Offset of pixel data + // SamplesPerPixel + writeValue<uint16_t>(file, 0x0115u); + writeValue<uint16_t>(file, 0x0003u); + writeValue<uint32_t>(file, 1); + writeValue<uint16_t>(file, channels); + writeValue<uint16_t>(file, 0); + // RowsPerStrip + writeValue<uint16_t>(file, 0x0116u); + writeValue<uint16_t>(file, 0x0004u); + writeValue<uint32_t>(file, 1); + writeValue<int32_t>(file, height); + // StripByteCounts + writeValue<uint16_t>(file, 0x0117u); + writeValue<uint16_t>(file, 0x0004u); + writeValue<uint32_t>(file, 1); + writeValue<int32_t>(file, sizeof(float)*channels*width*height); + // XResolution + writeValue<uint16_t>(file, 0x011au); + writeValue<uint16_t>(file, 0x0005u); + writeValue<uint32_t>(file, 1); + writeValue<uint32_t>(file, 0x00c2u+(channels > 1)*channels*2); // Offset of 300, 1 + // YResolution + writeValue<uint16_t>(file, 0x011bu); + writeValue<uint16_t>(file, 0x0005u); + writeValue<uint32_t>(file, 1); + writeValue<uint32_t>(file, 0x00cau+(channels > 1)*channels*2); // Offset of 300, 1 + // ResolutionUnit + writeValue<uint16_t>(file, 0x0128u); + writeValue<uint16_t>(file, 0x0003u); + writeValue<uint32_t>(file, 1); + writeValue<uint16_t>(file, 2); + writeValue<uint16_t>(file, 0); + // SampleFormat + writeValue<uint16_t>(file, 0x0153u); + writeValue<uint16_t>(file, 0x0003u); + writeValue<uint32_t>(file, channels); + if (channels > 1) + writeValue<uint32_t>(file, 0x00d2u+channels*2); // Offset of 3, 3, ... + else { + writeValue<uint16_t>(file, 3); + writeValue<uint16_t>(file, 0); + } + // SMinSampleValue + writeValue<uint16_t>(file, 0x0154u); + writeValue<uint16_t>(file, 0x000bu); + writeValue<uint32_t>(file, channels); + if (channels > 1) + writeValue<uint32_t>(file, 0x00d2u+channels*4); // Offset of 0.f, 0.f, ... + else + writeValue<float>(file, 0.f); + // SMaxSampleValue + writeValue<uint16_t>(file, 0x0155u); + writeValue<uint16_t>(file, 0x000bu); + writeValue<uint32_t>(file, channels); + if (channels > 1) + writeValue<uint32_t>(file, 0x00d2u+channels*8); // Offset of 1.f, 1.f, ... + else + writeValue<float>(file, 1.f); + // Offset = 0x00be + + writeValue<uint32_t>(file, 0); + + if (channels > 1) { + // 0x00c2 BitsPerSample data + writeValueRepeated<uint16_t>(file, 32, channels); + // 0x00c2 + 2*N XResolution data + writeValue<uint32_t>(file, 300); + writeValue<uint32_t>(file, 1); + // 0x00ca + 2*N YResolution data + writeValue<uint32_t>(file, 300); + writeValue<uint32_t>(file, 1); + // 0x00d2 + 2*N SampleFormat data + writeValueRepeated<uint16_t>(file, 3, channels); + // 0x00d2 + 4*N SMinSampleValue data + writeValueRepeated<float>(file, 0.f, channels); + // 0x00d2 + 8*N SMaxSampleValue data + writeValueRepeated<float>(file, 1.f, channels); + // Offset = 0x00d2 + 12*N + } else { + // 0x00c2 XResolution data + writeValue<uint32_t>(file, 300); + writeValue<uint32_t>(file, 1); + // 0x00ca YResolution data + writeValue<uint32_t>(file, 300); + writeValue<uint32_t>(file, 1); + // Offset = 0x00d2 + } + + return true; +} + +template <int N> +bool saveTiffFloat(const BitmapConstRef<float, N> &bitmap, const char *filename) { + FILE *file = fopen(filename, "wb"); + if (!file) + return false; + writeTiffHeader(file, bitmap.width, bitmap.height, N); + for (int y = bitmap.height-1; y >= 0; --y) + fwrite(bitmap(0, y), sizeof(float), N*bitmap.width, file); + return !fclose(file); +} + +bool saveTiff(const BitmapConstRef<float, 1> &bitmap, const char *filename) { + return saveTiffFloat(bitmap, filename); +} +bool saveTiff(const BitmapConstRef<float, 3> &bitmap, const char *filename) { + return saveTiffFloat(bitmap, filename); +} +bool saveTiff(const BitmapConstRef<float, 4> &bitmap, const char *filename) { + return saveTiffFloat(bitmap, filename); +} + +} diff --git a/thirdparty/msdfgen/core/save-tiff.h b/thirdparty/msdfgen/core/save-tiff.h new file mode 100644 index 0000000000..072cd71d50 --- /dev/null +++ b/thirdparty/msdfgen/core/save-tiff.h @@ -0,0 +1,13 @@ + +#pragma once + +#include "BitmapRef.hpp" + +namespace msdfgen { + +/// Saves the bitmap as an uncompressed floating-point TIFF file. +bool saveTiff(const BitmapConstRef<float, 1> &bitmap, const char *filename); +bool saveTiff(const BitmapConstRef<float, 3> &bitmap, const char *filename); +bool saveTiff(const BitmapConstRef<float, 4> &bitmap, const char *filename); + +} diff --git a/thirdparty/msdfgen/core/sdf-error-estimation.cpp b/thirdparty/msdfgen/core/sdf-error-estimation.cpp new file mode 100644 index 0000000000..7c00c449a9 --- /dev/null +++ b/thirdparty/msdfgen/core/sdf-error-estimation.cpp @@ -0,0 +1,192 @@ + +#include "sdf-error-estimation.h" + +#include <cmath> +#include "arithmetics.hpp" + +namespace msdfgen { + +void scanlineSDF(Scanline &line, const BitmapConstRef<float, 1> &sdf, const Projection &projection, double y, bool inverseYAxis) { + if (!(sdf.width > 0 && sdf.height > 0)) + return line.setIntersections(std::vector<Scanline::Intersection>()); + double pixelY = clamp(projection.projectY(y)-.5, double(sdf.height-1)); + if (inverseYAxis) + pixelY = sdf.height-1-pixelY; + int b = (int) floor(pixelY); + int t = b+1; + double bt = pixelY-b; + if (t >= sdf.height) { + b = sdf.height-1; + t = sdf.height-1; + bt = 1; + } + bool inside = false; + std::vector<Scanline::Intersection> intersections; + float lv, rv = mix(*sdf(0, b), *sdf(0, t), bt); + if ((inside = rv > .5f)) { + Scanline::Intersection intersection = { -1e240, 1 }; + intersections.push_back(intersection); + } + for (int l = 0, r = 1; r < sdf.width; ++l, ++r) { + lv = rv; + rv = mix(*sdf(r, b), *sdf(r, t), bt); + if (lv != rv) { + double lr = double(.5f-lv)/double(rv-lv); + if (lr >= 0 && lr <= 1) { + Scanline::Intersection intersection = { projection.unprojectX(l+lr+.5), sign(rv-lv) }; + intersections.push_back(intersection); + } + } + } +#ifdef MSDFGEN_USE_CPP11 + line.setIntersections((std::vector<Scanline::Intersection> &&) intersections); +#else + line.setIntersections(intersections); +#endif +} + +template <int N> +void scanlineMSDF(Scanline &line, const BitmapConstRef<float, N> &sdf, const Projection &projection, double y, bool inverseYAxis) { + if (!(sdf.width > 0 && sdf.height > 0)) + return line.setIntersections(std::vector<Scanline::Intersection>()); + double pixelY = clamp(projection.projectY(y)-.5, double(sdf.height-1)); + if (inverseYAxis) + pixelY = sdf.height-1-pixelY; + int b = (int) floor(pixelY); + int t = b+1; + double bt = pixelY-b; + if (t >= sdf.height) { + b = sdf.height-1; + t = sdf.height-1; + bt = 1; + } + bool inside = false; + std::vector<Scanline::Intersection> intersections; + float lv[3], rv[3]; + rv[0] = mix(sdf(0, b)[0], sdf(0, t)[0], bt); + rv[1] = mix(sdf(0, b)[1], sdf(0, t)[1], bt); + rv[2] = mix(sdf(0, b)[2], sdf(0, t)[2], bt); + if ((inside = median(rv[0], rv[1], rv[2]) > .5f)) { + Scanline::Intersection intersection = { -1e240, 1 }; + intersections.push_back(intersection); + } + for (int l = 0, r = 1; r < sdf.width; ++l, ++r) { + lv[0] = rv[0], lv[1] = rv[1], lv[2] = rv[2]; + rv[0] = mix(sdf(r, b)[0], sdf(r, t)[0], bt); + rv[1] = mix(sdf(r, b)[1], sdf(r, t)[1], bt); + rv[2] = mix(sdf(r, b)[2], sdf(r, t)[2], bt); + Scanline::Intersection newIntersections[4]; + int newIntersectionCount = 0; + for (int i = 0; i < 3; ++i) { + if (lv[i] != rv[i]) { + double lr = double(.5f-lv[i])/double(rv[i]-lv[i]); + if (lr >= 0 && lr <= 1) { + float v[3] = { + mix(lv[0], rv[0], lr), + mix(lv[1], rv[1], lr), + mix(lv[2], rv[2], lr) + }; + if (median(v[0], v[1], v[2]) == v[i]) { + newIntersections[newIntersectionCount].x = projection.unprojectX(l+lr+.5); + newIntersections[newIntersectionCount].direction = sign(rv[i]-lv[i]); + ++newIntersectionCount; + } + } + } + } + // Sort new intersections + if (newIntersectionCount >= 2) { + if (newIntersections[0].x > newIntersections[1].x) + newIntersections[3] = newIntersections[0], newIntersections[0] = newIntersections[1], newIntersections[1] = newIntersections[3]; + if (newIntersectionCount >= 3 && newIntersections[1].x > newIntersections[2].x) { + newIntersections[3] = newIntersections[1], newIntersections[1] = newIntersections[2], newIntersections[2] = newIntersections[3]; + if (newIntersections[0].x > newIntersections[1].x) + newIntersections[3] = newIntersections[0], newIntersections[0] = newIntersections[1], newIntersections[1] = newIntersections[3]; + } + } + for (int i = 0; i < newIntersectionCount; ++i) { + if ((newIntersections[i].direction > 0) == !inside) { + intersections.push_back(newIntersections[i]); + inside = !inside; + } + } + // Consistency check + float rvScalar = median(rv[0], rv[1], rv[2]); + if ((rvScalar > .5f) != inside && rvScalar != .5f && !intersections.empty()) { + intersections.pop_back(); + inside = !inside; + } + } +#ifdef MSDFGEN_USE_CPP11 + line.setIntersections((std::vector<Scanline::Intersection> &&) intersections); +#else + line.setIntersections(intersections); +#endif +} + +void scanlineSDF(Scanline &line, const BitmapConstRef<float, 3> &sdf, const Projection &projection, double y, bool inverseYAxis) { + scanlineMSDF(line, sdf, projection, y, inverseYAxis); +} +void scanlineSDF(Scanline &line, const BitmapConstRef<float, 4> &sdf, const Projection &projection, double y, bool inverseYAxis) { + scanlineMSDF(line, sdf, projection, y, inverseYAxis); +} + +template <int N> +double estimateSDFErrorInner(const BitmapConstRef<float, N> &sdf, const Shape &shape, const Projection &projection, int scanlinesPerRow, FillRule fillRule) { + if (sdf.width <= 1 || sdf.height <= 1 || scanlinesPerRow < 1) + return 0; + double subRowSize = 1./scanlinesPerRow; + double xFrom = projection.unprojectX(.5); + double xTo = projection.unprojectX(sdf.width-.5); + double overlapFactor = 1/(xTo-xFrom); + double error = 0; + Scanline refScanline, sdfScanline; + for (int row = 0; row < sdf.height-1; ++row) { + for (int subRow = 0; subRow < scanlinesPerRow; ++subRow) { + double bt = (subRow+.5)*subRowSize; + double y = projection.unprojectY(row+bt+.5); + shape.scanline(refScanline, y); + scanlineSDF(sdfScanline, sdf, projection, y, shape.inverseYAxis); + error += 1-overlapFactor*Scanline::overlap(refScanline, sdfScanline, xFrom, xTo, fillRule); + } + } + return error/((sdf.height-1)*scanlinesPerRow); +} + +double estimateSDFError(const BitmapConstRef<float, 1> &sdf, const Shape &shape, const Projection &projection, int scanlinesPerRow, FillRule fillRule) { + return estimateSDFErrorInner(sdf, shape, projection, scanlinesPerRow, fillRule); +} +double estimateSDFError(const BitmapConstRef<float, 3> &sdf, const Shape &shape, const Projection &projection, int scanlinesPerRow, FillRule fillRule) { + return estimateSDFErrorInner(sdf, shape, projection, scanlinesPerRow, fillRule); +} +double estimateSDFError(const BitmapConstRef<float, 4> &sdf, const Shape &shape, const Projection &projection, int scanlinesPerRow, FillRule fillRule) { + return estimateSDFErrorInner(sdf, shape, projection, scanlinesPerRow, fillRule); +} + +// Legacy API + +void scanlineSDF(Scanline &line, const BitmapConstRef<float, 1> &sdf, const Vector2 &scale, const Vector2 &translate, bool inverseYAxis, double y) { + scanlineSDF(line, sdf, Projection(scale, translate), y, inverseYAxis); +} + +void scanlineSDF(Scanline &line, const BitmapConstRef<float, 3> &sdf, const Vector2 &scale, const Vector2 &translate, bool inverseYAxis, double y) { + scanlineSDF(line, sdf, Projection(scale, translate), y, inverseYAxis); +} + +void scanlineSDF(Scanline &line, const BitmapConstRef<float, 4> &sdf, const Vector2 &scale, const Vector2 &translate, bool inverseYAxis, double y) { + scanlineSDF(line, sdf, Projection(scale, translate), y, inverseYAxis); +} + +double estimateSDFError(const BitmapConstRef<float, 1> &sdf, const Shape &shape, const Vector2 &scale, const Vector2 &translate, int scanlinesPerRow, FillRule fillRule) { + return estimateSDFError(sdf, shape, Projection(scale, translate), scanlinesPerRow, fillRule); +} + +double estimateSDFError(const BitmapConstRef<float, 3> &sdf, const Shape &shape, const Vector2 &scale, const Vector2 &translate, int scanlinesPerRow, FillRule fillRule) { + return estimateSDFError(sdf, shape, Projection(scale, translate), scanlinesPerRow, fillRule); +} + +double estimateSDFError(const BitmapConstRef<float, 4> &sdf, const Shape &shape, const Vector2 &scale, const Vector2 &translate, int scanlinesPerRow, FillRule fillRule) { + return estimateSDFError(sdf, shape, Projection(scale, translate), scanlinesPerRow, fillRule); +} + +} diff --git a/thirdparty/msdfgen/core/sdf-error-estimation.h b/thirdparty/msdfgen/core/sdf-error-estimation.h new file mode 100644 index 0000000000..d2fd40d2b8 --- /dev/null +++ b/thirdparty/msdfgen/core/sdf-error-estimation.h @@ -0,0 +1,30 @@ + +#pragma once + +#include "Vector2.h" +#include "Shape.h" +#include "Projection.h" +#include "Scanline.h" +#include "BitmapRef.hpp" + +namespace msdfgen { + +/// Analytically constructs a scanline at y evaluating fill by linear interpolation of the SDF. +void scanlineSDF(Scanline &line, const BitmapConstRef<float, 1> &sdf, const Projection &projection, double y, bool inverseYAxis = false); +void scanlineSDF(Scanline &line, const BitmapConstRef<float, 3> &sdf, const Projection &projection, double y, bool inverseYAxis = false); +void scanlineSDF(Scanline &line, const BitmapConstRef<float, 4> &sdf, const Projection &projection, double y, bool inverseYAxis = false); + +/// Estimates the portion of the area that will be filled incorrectly when rendering using the SDF. +double estimateSDFError(const BitmapConstRef<float, 1> &sdf, const Shape &shape, const Projection &projection, int scanlinesPerRow, FillRule fillRule = FILL_NONZERO); +double estimateSDFError(const BitmapConstRef<float, 3> &sdf, const Shape &shape, const Projection &projection, int scanlinesPerRow, FillRule fillRule = FILL_NONZERO); +double estimateSDFError(const BitmapConstRef<float, 4> &sdf, const Shape &shape, const Projection &projection, int scanlinesPerRow, FillRule fillRule = FILL_NONZERO); + +// Old version of the function API's kept for backwards compatibility +void scanlineSDF(Scanline &line, const BitmapConstRef<float, 1> &sdf, const Vector2 &scale, const Vector2 &translate, bool inverseYAxis, double y); +void scanlineSDF(Scanline &line, const BitmapConstRef<float, 3> &sdf, const Vector2 &scale, const Vector2 &translate, bool inverseYAxis, double y); +void scanlineSDF(Scanline &line, const BitmapConstRef<float, 4> &sdf, const Vector2 &scale, const Vector2 &translate, bool inverseYAxis, double y); +double estimateSDFError(const BitmapConstRef<float, 1> &sdf, const Shape &shape, const Vector2 &scale, const Vector2 &translate, int scanlinesPerRow, FillRule fillRule = FILL_NONZERO); +double estimateSDFError(const BitmapConstRef<float, 3> &sdf, const Shape &shape, const Vector2 &scale, const Vector2 &translate, int scanlinesPerRow, FillRule fillRule = FILL_NONZERO); +double estimateSDFError(const BitmapConstRef<float, 4> &sdf, const Shape &shape, const Vector2 &scale, const Vector2 &translate, int scanlinesPerRow, FillRule fillRule = FILL_NONZERO); + +} diff --git a/thirdparty/msdfgen/core/shape-description.cpp b/thirdparty/msdfgen/core/shape-description.cpp new file mode 100644 index 0000000000..a096fa2541 --- /dev/null +++ b/thirdparty/msdfgen/core/shape-description.cpp @@ -0,0 +1,284 @@ + +#define _CRT_SECURE_NO_WARNINGS +#include "shape-description.h" + +namespace msdfgen { + +int readCharF(FILE *input) { + int c = '\0'; + do { + c = fgetc(input); + } while (c == ' ' || c == '\t' || c == '\r' || c == '\n'); + return c; +} + +int readCharS(const char **input) { + int c = '\0'; + do { + c = *(*input)++; + } while (c == ' ' || c == '\t' || c == '\r' || c == '\n'); + if (!c) { + --c; + return EOF; + } + return c; +} + +int readCoordF(FILE *input, Point2 &coord) { + return fscanf(input, "%lf,%lf", &coord.x, &coord.y); +} + +int readCoordS(const char **input, Point2 &coord) { + int read = 0; + int result = sscanf(*input, "%lf,%lf%n", &coord.x, &coord.y, &read); + *input += read; + return result; +} + +static bool writeCoord(FILE *output, Point2 coord) { + fprintf(output, "%.12g, %.12g", coord.x, coord.y); + return true; +} + +template <typename T, int (*readChar)(T *), int (*readCoord)(T *, Point2 &)> +static int readControlPoints(T *input, Point2 *output) { + int result = readCoord(input, output[0]); + if (result == 2) { + switch (readChar(input)) { + case ')': + return 1; + case ';': + break; + default: + return -1; + } + result = readCoord(input, output[1]); + if (result == 2 && readChar(input) == ')') + return 2; + } else if (result != 1 && readChar(input) == ')') + return 0; + return -1; +} + +template <typename T, int (*readChar)(T *), int (*readCoord)(T *, Point2 &)> +static bool readContour(T *input, Contour &output, const Point2 *first, int terminator, bool &colorsSpecified) { + Point2 p[4], start; + if (first) + p[0] = *first; + else { + int result = readCoord(input, p[0]); + if (result != 2) + return result != 1 && readChar(input) == terminator; + } + start = p[0]; + int c = '\0'; + while ((c = readChar(input)) != terminator) { + if (c != ';') + return false; + EdgeColor color = WHITE; + int result = readCoord(input, p[1]); + if (result == 2) { + output.addEdge(EdgeHolder(p[0], p[1], color)); + p[0] = p[1]; + continue; + } else if (result == 1) + return false; + else { + int controlPoints = 0; + switch ((c = readChar(input))) { + case '#': + output.addEdge(EdgeHolder(p[0], start, color)); + p[0] = start; + continue; + case ';': + goto FINISH_EDGE; + case '(': + goto READ_CONTROL_POINTS; + case 'C': case 'c': + color = CYAN; + colorsSpecified = true; + break; + case 'M': case 'm': + color = MAGENTA; + colorsSpecified = true; + break; + case 'Y': case 'y': + color = YELLOW; + colorsSpecified = true; + break; + case 'W': case 'w': + color = WHITE; + colorsSpecified = true; + break; + default: + return c == terminator; + } + switch (readChar(input)) { + case ';': + goto FINISH_EDGE; + case '(': + READ_CONTROL_POINTS: + if ((controlPoints = readControlPoints<T, readChar, readCoord>(input, p+1)) < 0) + return false; + break; + default: + return false; + } + if (readChar(input) != ';') + return false; + FINISH_EDGE: + result = readCoord(input, p[1+controlPoints]); + if (result != 2) { + if (result == 1) + return false; + else { + if (readChar(input) == '#') + p[1+controlPoints] = start; + else + return false; + } + } + switch (controlPoints) { + case 0: + output.addEdge(EdgeHolder(p[0], p[1], color)); + p[0] = p[1]; + continue; + case 1: + output.addEdge(EdgeHolder(p[0], p[1], p[2], color)); + p[0] = p[2]; + continue; + case 2: + output.addEdge(EdgeHolder(p[0], p[1], p[2], p[3], color)); + p[0] = p[3]; + continue; + } + } + } + return true; +} + +bool readShapeDescription(FILE *input, Shape &output, bool *colorsSpecified) { + bool locColorsSpec = false; + output.contours.clear(); + output.inverseYAxis = false; + Point2 p; + int result = readCoordF(input, p); + if (result == 2) { + return readContour<FILE, readCharF, readCoordF>(input, output.addContour(), &p, EOF, locColorsSpec); + } else if (result == 1) + return false; + else { + int c = readCharF(input); + if (c == '@') { + char after = '\0'; + if (fscanf(input, "invert-y%c", &after) != 1) + return feof(input) != 0; + output.inverseYAxis = true; + c = after; + if (c == ' ' || c == '\t' || c == '\r' || c == '\n') + c = readCharF(input); + } + for (; c == '{'; c = readCharF(input)) + if (!readContour<FILE, readCharF, readCoordF>(input, output.addContour(), NULL, '}', locColorsSpec)) + return false; + if (colorsSpecified) + *colorsSpecified = locColorsSpec; + return c == EOF && feof(input); + } +} + +bool readShapeDescription(const char *input, Shape &output, bool *colorsSpecified) { + bool locColorsSpec = false; + output.contours.clear(); + output.inverseYAxis = false; + Point2 p; + int result = readCoordS(&input, p); + if (result == 2) { + return readContour<const char *, readCharS, readCoordS>(&input, output.addContour(), &p, EOF, locColorsSpec); + } else if (result == 1) + return false; + else { + int c = readCharS(&input); + if (c == '@') { + for (int i = 0; i < (int) sizeof("invert-y")-1; ++i) + if (input[i] != "invert-y"[i]) + return false; + output.inverseYAxis = true; + input += sizeof("invert-y")-1; + c = readCharS(&input); + } + for (; c == '{'; c = readCharS(&input)) + if (!readContour<const char *, readCharS, readCoordS>(&input, output.addContour(), NULL, '}', locColorsSpec)) + return false; + if (colorsSpecified) + *colorsSpecified = locColorsSpec; + return c == EOF; + } +} + +static bool isColored(const Shape &shape) { + for (std::vector<Contour>::const_iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour) + for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) + if ((*edge)->color != WHITE) + return true; + return false; +} + +bool writeShapeDescription(FILE *output, const Shape &shape) { + if (!shape.validate()) + return false; + bool writeColors = isColored(shape); + if (shape.inverseYAxis) + fprintf(output, "@invert-y\n"); + for (std::vector<Contour>::const_iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour) { + fprintf(output, "{\n"); + if (!contour->edges.empty()) { + for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) { + char colorCode = '\0'; + if (writeColors) { + switch ((*edge)->color) { + case YELLOW: colorCode = 'y'; break; + case MAGENTA: colorCode = 'm'; break; + case CYAN: colorCode = 'c'; break; + case WHITE: colorCode = 'w'; break; + default:; + } + } + if (const LinearSegment *e = dynamic_cast<const LinearSegment *>(&**edge)) { + fprintf(output, "\t"); + writeCoord(output, e->p[0]); + fprintf(output, ";\n"); + if (colorCode) + fprintf(output, "\t\t%c;\n", colorCode); + } + if (const QuadraticSegment *e = dynamic_cast<const QuadraticSegment *>(&**edge)) { + fprintf(output, "\t"); + writeCoord(output, e->p[0]); + fprintf(output, ";\n\t\t"); + if (colorCode) + fprintf(output, "%c", colorCode); + fprintf(output, "("); + writeCoord(output, e->p[1]); + fprintf(output, ");\n"); + } + if (const CubicSegment *e = dynamic_cast<const CubicSegment *>(&**edge)) { + fprintf(output, "\t"); + writeCoord(output, e->p[0]); + fprintf(output, ";\n\t\t"); + if (colorCode) + fprintf(output, "%c", colorCode); + fprintf(output, "("); + writeCoord(output, e->p[1]); + fprintf(output, "; "); + writeCoord(output, e->p[2]); + fprintf(output, ");\n"); + } + } + fprintf(output, "\t#\n"); + } + fprintf(output, "}\n"); + } + return true; +} + +} diff --git a/thirdparty/msdfgen/core/shape-description.h b/thirdparty/msdfgen/core/shape-description.h new file mode 100644 index 0000000000..5df7c50a03 --- /dev/null +++ b/thirdparty/msdfgen/core/shape-description.h @@ -0,0 +1,16 @@ + +#pragma once + +#include <cstdlib> +#include <cstdio> +#include "Shape.h" + +namespace msdfgen { + +/// Deserializes a text description of a vector shape into output. +bool readShapeDescription(FILE *input, Shape &output, bool *colorsSpecified = NULL); +bool readShapeDescription(const char *input, Shape &output, bool *colorsSpecified = NULL); +/// Serializes a shape object into a text description. +bool writeShapeDescription(FILE *output, const Shape &shape); + +} diff --git a/thirdparty/msdfgen/msdfgen.h b/thirdparty/msdfgen/msdfgen.h new file mode 100644 index 0000000000..fb36bd7e1d --- /dev/null +++ b/thirdparty/msdfgen/msdfgen.h @@ -0,0 +1,65 @@ + +#pragma once + +/* + * MULTI-CHANNEL SIGNED DISTANCE FIELD GENERATOR v1.9 (2021-05-28) + * --------------------------------------------------------------- + * A utility by Viktor Chlumsky, (c) 2014 - 2021 + * + * The technique used to generate multi-channel distance fields in this code + * has been developed by Viktor Chlumsky in 2014 for his master's thesis, + * "Shape Decomposition for Multi-Channel Distance Fields". It provides improved + * quality of sharp corners in glyphs and other 2D shapes compared to monochrome + * distance fields. To reconstruct an image of the shape, apply the median of three + * operation on the triplet of sampled signed distance values. + * + */ + +#include "core/arithmetics.hpp" +#include "core/Vector2.h" +#include "core/Projection.h" +#include "core/Scanline.h" +#include "core/Shape.h" +#include "core/BitmapRef.hpp" +#include "core/Bitmap.h" +#include "core/bitmap-interpolation.hpp" +#include "core/pixel-conversion.hpp" +#include "core/edge-coloring.h" +#include "core/generator-config.h" +#include "core/msdf-error-correction.h" +#include "core/render-sdf.h" +#include "core/rasterization.h" +#include "core/sdf-error-estimation.h" +#include "core/save-bmp.h" +#include "core/save-tiff.h" +#include "core/shape-description.h" + +#define MSDFGEN_VERSION "1.9" + +namespace msdfgen { + +/// Generates a conventional single-channel signed distance field. +void generateSDF(const BitmapRef<float, 1> &output, const Shape &shape, const Projection &projection, double range, const GeneratorConfig &config = GeneratorConfig()); + +/// Generates a single-channel signed pseudo-distance field. +void generatePseudoSDF(const BitmapRef<float, 1> &output, const Shape &shape, const Projection &projection, double range, const GeneratorConfig &config = GeneratorConfig()); + +/// Generates a multi-channel signed distance field. Edge colors must be assigned first! (See edgeColoringSimple) +void generateMSDF(const BitmapRef<float, 3> &output, const Shape &shape, const Projection &projection, double range, const MSDFGeneratorConfig &config = MSDFGeneratorConfig()); + +/// Generates a multi-channel signed distance field with true distance in the alpha channel. Edge colors must be assigned first. +void generateMTSDF(const BitmapRef<float, 4> &output, const Shape &shape, const Projection &projection, double range, const MSDFGeneratorConfig &config = MSDFGeneratorConfig()); + +// Old version of the function API's kept for backwards compatibility +void generateSDF(const BitmapRef<float, 1> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate, bool overlapSupport = true); +void generatePseudoSDF(const BitmapRef<float, 1> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate, bool overlapSupport = true); +void generateMSDF(const BitmapRef<float, 3> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate, const ErrorCorrectionConfig &errorCorrectionConfig = ErrorCorrectionConfig(), bool overlapSupport = true); +void generateMTSDF(const BitmapRef<float, 4> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate, const ErrorCorrectionConfig &errorCorrectionConfig = ErrorCorrectionConfig(), bool overlapSupport = true); + +// Original simpler versions of the previous functions, which work well under normal circumstances, but cannot deal with overlapping contours. +void generateSDF_legacy(const BitmapRef<float, 1> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate); +void generatePseudoSDF_legacy(const BitmapRef<float, 1> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate); +void generateMSDF_legacy(const BitmapRef<float, 3> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate, ErrorCorrectionConfig errorCorrectionConfig = ErrorCorrectionConfig()); +void generateMTSDF_legacy(const BitmapRef<float, 4> &output, const Shape &shape, double range, const Vector2 &scale, const Vector2 &translate, ErrorCorrectionConfig errorCorrectionConfig = ErrorCorrectionConfig()); + +} |