Skip to content

Instantly share code, notes, and snippets.

@nickav

nickav/msdfgen.h

Created November 29, 2023 05:47
Show Gist options
  • Save nickav/78a949b835048060327ccc4e2bc6c32a to your computer and use it in GitHub Desktop.
Save nickav/78a949b835048060327ccc4e2bc6c32a to your computer and use it in GitHub Desktop.
Download ZIP
Single-file header library for MSDFgen
Raw
msdfgen.h
/*
* MULTI-CHANNEL SIGNED DISTANCE FIELD GENERATOR
* ---------------------------------------------
* A utility by Viktor Chlumsky, (c) 2014 - 2023
*
* 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/base.h"
//
#include <cstddef>
namespace msdfgen {
typedef unsigned char byte;
}
//
// #include "core/arithmetics.hpp"
//
#include <math.h>
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;
}
}
//
// #include "core/Vector2.hpp"
//
#include <math.h>
namespace msdfgen {
/**
* A 2-dimensional euclidean floating-point vector.
* @author Viktor Chlumsky
*/
struct Vector2 {
double x, y;
inline Vector2(double val = 0) : x(val), y(val) { }
inline Vector2(double x, double y) : x(x), y(y) { }
/// Sets the vector to zero.
inline void reset() {
x = 0, y = 0;
}
/// Sets individual elements of the vector.
inline void set(double x, double y) {
this->x = x, this->y = y;
}
/// Returns the vector's squared length.
inline double squaredLength() const {
return x*x+y*y;
}
/// Returns the vector's length.
inline double length() const {
return sqrt(x*x+y*y);
}
/// Returns the normalized vector - one that has the same direction but unit length.
inline Vector2 normalize(bool allowZero = false) const {
if (double len = length())
return Vector2(x/len, y/len);
return Vector2(0, !allowZero);
}
/// Returns a vector with the same length that is orthogonal to this one.
inline Vector2 getOrthogonal(bool polarity = true) const {
return polarity ? Vector2(-y, x) : Vector2(y, -x);
}
/// Returns a vector with unit length that is orthogonal to this one.
inline Vector2 getOrthonormal(bool polarity = true, bool allowZero = false) const {
if (double len = length())
return polarity ? Vector2(-y/len, x/len) : Vector2(y/len, -x/len);
return polarity ? Vector2(0, !allowZero) : Vector2(0, -!allowZero);
}
#ifdef MSDFGEN_USE_CPP11
inline explicit operator bool() const {
return x || y;
}
#else
inline operator const void *() const {
return x || y ? this : NULL;
}
#endif
inline Vector2 &operator+=(const Vector2 other) {
x += other.x, y += other.y;
return *this;
}
inline Vector2 &operator-=(const Vector2 other) {
x -= other.x, y -= other.y;
return *this;
}
inline Vector2 &operator*=(const Vector2 other) {
x *= other.x, y *= other.y;
return *this;
}
inline Vector2 &operator/=(const Vector2 other) {
x /= other.x, y /= other.y;
return *this;
}
inline Vector2 &operator*=(double value) {
x *= value, y *= value;
return *this;
}
inline Vector2 &operator/=(double value) {
x /= value, y /= value;
return *this;
}
};
/// A vector may also represent a point, which shall be differentiated semantically using the alias Point2.
typedef Vector2 Point2;
/// Dot product of two vectors.
inline double dotProduct(const Vector2 a, const Vector2 b) {
return a.x*b.x+a.y*b.y;
}
/// A special version of the cross product for 2D vectors (returns scalar value).
inline double crossProduct(const Vector2 a, const Vector2 b) {
return a.x*b.y-a.y*b.x;
}
inline bool operator==(const Vector2 a, const Vector2 b) {
return a.x == b.x && a.y == b.y;
}
inline bool operator!=(const Vector2 a, const Vector2 b) {
return a.x != b.x || a.y != b.y;
}
inline Vector2 operator+(const Vector2 v) {
return v;
}
inline Vector2 operator-(const Vector2 v) {
return Vector2(-v.x, -v.y);
}
inline bool operator!(const Vector2 v) {
return !v.x && !v.y;
}
inline Vector2 operator+(const Vector2 a, const Vector2 b) {
return Vector2(a.x+b.x, a.y+b.y);
}
inline Vector2 operator-(const Vector2 a, const Vector2 b) {
return Vector2(a.x-b.x, a.y-b.y);
}
inline Vector2 operator*(const Vector2 a, const Vector2 b) {
return Vector2(a.x*b.x, a.y*b.y);
}
inline Vector2 operator/(const Vector2 a, const Vector2 b) {
return Vector2(a.x/b.x, a.y/b.y);
}
inline Vector2 operator*(double a, const Vector2 b) {
return Vector2(a*b.x, a*b.y);
}
inline Vector2 operator/(double a, const Vector2 b) {
return Vector2(a/b.x, a/b.y);
}
inline Vector2 operator*(const Vector2 a, double b) {
return Vector2(a.x*b, a.y*b);
}
inline Vector2 operator/(const Vector2 a, double b) {
return Vector2(a.x/b, a.y/b);
}
}
//
// #include "core/Projection.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;
};
}
//
// #include "core/Scanline.h"
//
#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;
};
}
//
// #include "SignedDistance.hpp"
//
#include <math.h>
#include <float.h>
namespace msdfgen {
/// Represents a signed distance and alignment, which together can be compared to uniquely determine the closest edge segment.
class SignedDistance {
public:
double distance;
double dot;
inline SignedDistance() : distance(-DBL_MAX), dot(0) { }
inline SignedDistance(double dist, double d) : distance(dist), dot(d) { }
};
inline bool operator<(const SignedDistance a, const SignedDistance b) {
return fabs(a.distance) < fabs(b.distance) || (fabs(a.distance) == fabs(b.distance) && a.dot < b.dot);
}
inline bool operator>(const SignedDistance a, const SignedDistance b) {
return fabs(a.distance) > fabs(b.distance) || (fabs(a.distance) == fabs(b.distance) && a.dot > b.dot);
}
inline bool operator<=(const SignedDistance a, const SignedDistance b) {
return fabs(a.distance) < fabs(b.distance) || (fabs(a.distance) == fabs(b.distance) && a.dot <= b.dot);
}
inline bool operator>=(const SignedDistance a, const SignedDistance b) {
return fabs(a.distance) > fabs(b.distance) || (fabs(a.distance) == fabs(b.distance) && a.dot >= b.dot);
}
}
//
// #include "EdgeColor.h"
//
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
};
}
//
// #include "edge-segments.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 numeric code of the edge segment's type.
virtual int type() const = 0;
/// Returns the array of control points.
virtual const Point2 *controlPoints() 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 &param) 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:
enum EdgeType {
EDGE_TYPE = 1
};
Point2 p[2];
LinearSegment(Point2 p0, Point2 p1, EdgeColor edgeColor = WHITE);
LinearSegment *clone() const;
int type() const;
const Point2 *controlPoints() const;
Point2 point(double param) const;
Vector2 direction(double param) const;
Vector2 directionChange(double param) const;
double length() const;
SignedDistance signedDistance(Point2 origin, double &param) 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:
enum EdgeType {
EDGE_TYPE = 2
};
Point2 p[3];
QuadraticSegment(Point2 p0, Point2 p1, Point2 p2, EdgeColor edgeColor = WHITE);
QuadraticSegment *clone() const;
int type() const;
const Point2 *controlPoints() const;
Point2 point(double param) const;
Vector2 direction(double param) const;
Vector2 directionChange(double param) const;
double length() const;
SignedDistance signedDistance(Point2 origin, double &param) 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:
enum EdgeType {
EDGE_TYPE = 3
};
Point2 p[4];
CubicSegment(Point2 p0, Point2 p1, Point2 p2, Point2 p3, EdgeColor edgeColor = WHITE);
CubicSegment *clone() const;
int type() const;
const Point2 *controlPoints() const;
Point2 point(double param) const;
Vector2 direction(double param) const;
Vector2 directionChange(double param) const;
SignedDistance signedDistance(Point2 origin, double &param) 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);
};
}
//
// #include "EdgeHolder.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;
};
}
//
// #include "Contour.h"
//
#include <vector>
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();
};
}
//
// #include "core/Shape.h"
//
#include <vector>
// #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();
};
}
//
// #include "core/BitmapRef.hpp"
//
namespace msdfgen {
/// 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);
}
};
}
//
// #include "core/Bitmap.h"
//
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"
//
#include <stdlib.h>
#include <string.h>
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);
}
}
//
// #include "core/bitmap-interpolation.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);
}
}
//
// #include "core/pixel-conversion.hpp"
//
namespace msdfgen {
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);
}
}
//
// #include "core/edge-coloring.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);
}
//
// #include "core/generator-config.h"
//
#ifndef MSDFGEN_PUBLIC
#define MSDFGEN_PUBLIC // for DLL import/export
#endif
namespace msdfgen {
/// The configuration of the MSDF error correction pass.
struct ErrorCorrectionConfig {
/// The default value of minDeviationRatio.
static MSDFGEN_PUBLIC const double defaultMinDeviationRatio;
/// The default value of minImproveRatio.
static MSDFGEN_PUBLIC 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) { }
};
}
//
// #include "core/msdf-error-correction.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);
}
//
// #include "core/render-sdf.h"
//
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);
}
//
// #include "core/rasterization.h"
//
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);
}
//
// #include "core/sdf-error-estimation.h"
//
// #include "Vector2.hpp"
// #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);
}
//
// #include "core/save-bmp.h"
//
// #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);
}
//
// #include "core/save-tiff.h"
//
// #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);
}
//
// #include "core/shape-description.h"
//
#include <stdio.h>
// #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);
}
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());
}
//
// impl
//
#pragma once
//
// #include "core/Contour.cpp"
//
// #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();
}
}
//
// #include "edge-selectors.h"
//
// #include "SignedDistance.hpp"
// #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;
};
}
//
// #include "core/contour-combiners.cpp"
//
//
// #include "contour-combiners.h"
//
// #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;
};
}
#include <float.h>
// #include "arithmetics.hpp"
namespace msdfgen {
static void initDistance(double &distance) {
distance = -DBL_MAX;
}
static void initDistance(MultiDistance &distance) {
distance.r = -DBL_MAX;
distance.g = -DBL_MAX;
distance.b = -DBL_MAX;
}
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>;
}
//
// #include "core/edge-coloring.cpp"
//
// #include "edge-coloring.h"
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <float.h>
#include <vector>
#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 = DBL_MAX;
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 = (int) (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 = (int) (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]];
}
}
}
//
// #include "core/edge-segments.cpp"
//
// #include "edge-segments.h"
// #include "arithmetics.hpp"
//
// #include "equation-solver.h"
//
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);
}
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);
}
int LinearSegment::type() const {
return (int) EDGE_TYPE;
}
int QuadraticSegment::type() const {
return (int) EDGE_TYPE;
}
int CubicSegment::type() const {
return (int) EDGE_TYPE;
}
const Point2 *LinearSegment::controlPoints() const {
return p;
}
const Point2 *QuadraticSegment::controlPoints() const {
return p;
}
const Point2 *CubicSegment::controlPoints() const {
return p;
}
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 &param) 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 &param) 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 &param) 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;
}
}
}
//
// #include "core/edge-selectors.cpp"
//
// #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;
}
}
//
// #include "core/EdgeHolder.cpp"
//
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;
}
}
//
// #include "core/equation-solver.cpp"
//
// #include "equation-solver.h"
#define _USE_MATH_DEFINES
#include <math.h>
namespace msdfgen {
int solveQuadratic(double x[2], double a, double b, double c) {
// a == 0 -> linear equation
if (a == 0 || fabs(b) > 1e12*fabs(a)) {
// a == 0, b == 0 -> no solution
if (b == 0) {
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 = 1/9.*(a2-3*b);
double r = 1/54.*(a*(2*a2-9*b)+27*c);
double r2 = r*r;
double q3 = q*q*q;
a *= 1/3.;
if (r2 < q3) {
double t = r/sqrt(q3);
if (t < -1) t = -1;
if (t > 1) t = 1;
t = acos(t);
q = -2*sqrt(q);
x[0] = q*cos(1/3.*t)-a;
x[1] = q*cos(1/3.*(t+2*M_PI))-a;
x[2] = q*cos(1/3.*(t-2*M_PI))-a;
return 3;
} else {
double u = (r < 0 ? 1 : -1)*pow(fabs(r)+sqrt(r2-q3), 1/3.);
double v = u == 0 ? 0 : q/u;
x[0] = (u+v)-a;
if (u == v || fabs(u-v) < 1e-12*fabs(u+v)) {
x[1] = -.5*(u+v)-a;
return 2;
}
return 1;
}
}
int solveCubic(double x[3], double a, double b, double c, double d) {
if (a != 0) {
double bn = b/a;
if (fabs(bn) < 1e6) // Above this ratio, the numerical error gets larger than if we treated a as zero
return solveCubicNormed(x, bn, c/a, d/a);
}
return solveQuadratic(x, b, c, d);
}
}
//
// #include "core/msdf-error-correction.cpp"
//
#include <vector>
// #include "arithmetics.hpp"
// #include "Bitmap.h"
//
// #include "MSDFErrorCorrection.h"
//
// #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;
};
}
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);