diff --git a/c++/contourgl/Makefile b/c++/contourgl/Makefile index afc16e4..fdd894d 100644 --- a/c++/contourgl/Makefile +++ b/c++/contourgl/Makefile @@ -1,8 +1,9 @@ DEPLIBS = gl x11 CXXFLAGS = -O3 -Wall -fmessage-length=0 `pkg-config --libs $(DEPLIBS)` -DGL_GLEXT_PROTOTYPES -DEPS = contour.h contourbuilder.h -OBJS = contour.o contourgl.o contourbuilder.o +DEPS = contour.h contourbuilder.h geometry.h polyspan.h rendersw.h test.h \ + contour.cpp contourbuilder.cpp polyspan.cpp rendersw.cpp test.cpp +OBJS = contour.o contourgl.o contourbuilder.o polyspan.o rendersw.o test.o LIBS = `pkg-config --libs $(DEPLIBS)` TARGET = contourgl diff --git a/c++/contourgl/contour.cpp b/c++/contourgl/contour.cpp index 93748a7..8a5bacf 100644 --- a/c++/contourgl/contour.cpp +++ b/c++/contourgl/contour.cpp @@ -15,7 +15,7 @@ along with this program. If not, see . */ -#include +#include #include "contour.h" @@ -78,11 +78,6 @@ void Contour::close() { } } -void Contour::assign(const Contour &other) { - chunks = other.chunks; - first = other.first; -} - void Contour::line_split( Rect &ref_line_bounds, const Rect &bounds, @@ -118,9 +113,9 @@ void Contour::conic_split( const Vector &min_size, const Vector &p1, const Vector ¢er, - double radius, - double radians0, - double radians1, + Real radius, + Real radians0, + Real radians1, int level ) { assert(level > 0); @@ -131,7 +126,7 @@ void Contour::conic_split( { Rect b = conic_bounds(p0, p1, center, radius, radians0, radians1); if (bounds.intersects(b)) { - double radians = 0.5*(radians0 + radians1); + Real radians = 0.5*(radians0 + radians1); Vector p( radius*cos(radians) + center.x, radius*sin(radians) + center.y ); conic_split(ref_line_bounds, bounds, min_size, p, center, radius, radians0, radians, level - 1); @@ -196,9 +191,9 @@ void Contour::split(Contour &c, const Rect &bounds, const Vector &min_size) cons { const Vector &p0 = c.current(); Vector center; - double radius = 0.0; - double radians0 = 0.0; - double radians1 = 0.0; + Real radius = 0.0; + Real radians0 = 0.0; + Real radians1 = 0.0; if (conic_convert(p0, i->p1, i->t0, center, radius, radians0, radians1)) c.conic_split(line_bounds, bounds, min_size, i->p1, center, radius, radians0, radians1); else @@ -222,11 +217,11 @@ bool Contour::conic_convert( const Vector &p1, const Vector &t, Vector &out_center, - double &out_radius, - double &out_radians0, - double &out_radians1 ) + Real &out_radius, + Real &out_radians0, + Real &out_radians1 ) { - double tl = sqrt(t.x*t.x + t.y*t.y); + Real tl = sqrt(t.x*t.x + t.y*t.y); if (fabs(tl) < 1e-6) { out_center = Vector(); out_radius = 0.0; @@ -238,7 +233,7 @@ bool Contour::conic_convert( Vector d = p1 - p0; Vector n(-t.y/tl, t.x/tl); - double r = 0.5*(d.x*d.x + d.y*d.y)/(d.x*n.x + d.y*n.y); + Real r = 0.5*(d.x*d.x + d.y*d.y)/(d.x*n.x + d.y*n.y); out_center = p0 + n*r; out_radius = fabs(r); out_radians0 = atan2(p0.y - out_center.y, p0.x - out_center.x); @@ -257,9 +252,9 @@ Rect Contour::conic_bounds( const Vector &p0, const Vector &p1, const Vector ¢er, - double radius, - double radians0, - double radians1 ) + Real radius, + Real radians0, + Real radians1 ) { radius = fabs(radius); @@ -304,3 +299,57 @@ Rect Contour::cubic_bounds( r.p1.y = max(max(p0.y, bezier_pp0.y), max(p1.y, bezier_pp1.y)); return r; } + +void Contour::transform(const Rect &from, const Rect &to) { + Vector s( (to.p1.x - to.p0.x)/(from.p1.x - from.p0.x), + (to.p1.y - to.p0.y)/(from.p1.y - from.p0.y) ); + Vector o( to.p0.x - from.p0.x*s.x, + to.p0.y - from.p0.y*s.y ); + for(Contour::ChunkList::iterator i = chunks.begin(); i != chunks.end(); ++i) { + i->p1 = i->p1*s + o; + i->t0 = i->t0*s; + i->t1 = i->t1*s; + } +} + +void Contour::to_polyspan(Polyspan &polyspan) const { + polyspan.move_to(0.0, 0.0); + Vector p0; + for(Contour::ChunkList::const_iterator i = chunks.begin(); i != chunks.end(); ++i) { + switch(i->type) { + case Contour::CLOSE: + polyspan.close(); + break; + case Contour::MOVE: + polyspan.move_to(i->p1.x, i->p1.y); + break; + case Contour::LINE: + polyspan.line_to(i->p1.x, i->p1.y); + break; + case Contour::CONIC: { + Vector center; + Real radius = 0.0; + Real radians0 = 0.0; + Real radians1 = 0.0; + if (conic_convert(p0, i->p1, i->t0, center, radius, radians0, radians1)) { + // TODO: fix bugs + Vector pp0( center.x + 2.0*radius*cos(0.5*(radians0 + radians1)), + center.y + 2.0*radius*sin(0.5*(radians0 + radians1)) ); + polyspan.conic_to(pp0.x, pp0.y, i->p1.x, i->p1.y); + } else { + polyspan.line_to(i->p1.x, i->p1.y); + } + } + break; + case Contour::CUBIC: { + Vector pp0, pp1; + cubic_convert(p0, i->p1, i->t0, i->t1, pp0, pp1); + polyspan.cubic_to(pp0.x, pp0.y, pp1.x, pp1.y, i->p1.x, i->p1.y); + } + break; + default: + break; + } + p0 = i->p1; + } +} diff --git a/c++/contourgl/contour.h b/c++/contourgl/contour.h index 643586e..71f9adb 100644 --- a/c++/contourgl/contour.h +++ b/c++/contourgl/contour.h @@ -18,84 +18,10 @@ #ifndef _CONTOUR_H_ #define _CONTOUR_H_ -#include -#include - -#include #include -template -bool intersects(const T &a0, const T &a1, const T &b0, const T &b1) { - return !(std::max(b0, b1) < std::min(a0, a1)) - && !(std::max(a0, a1) < std::min(b0, b1)); -} - -inline double wrap_angle(double a, double round) { - double rounds = a/round + 0.5; - return (rounds - floor(rounds) - 0.5)*round; -} - -inline bool angle_between(double a0, double a1, double a, double round) { - if (a1 < a0) std::swap(a0, a1); - a0 = wrap_angle(a0, round); - a1 = wrap_angle(a1, round); - a = wrap_angle(a, round); - if (a < a0) a += round; - if (a1 < a0) a1 += round; - return a0 < a && a < a1; -} - -class Vector { -public: - union { - struct { double x, y; }; - struct { double coords[]; }; - }; - - Vector(): - x(), y() { } - Vector(double x, double y): - x(x), y(y) { } - - double& operator[] (int index) - { return coords[index]; } - const double& operator[] (int index) const - { return coords[index]; } - bool is_equal_to(const Vector &other) const - { return fabs(x - other.x) < 1e-6 && fabs(y - other.y) < 1e-6; } - - Vector operator+(const Vector &a) const - { return Vector(x + a.x, y + a.y); } - Vector operator-(const Vector &a) const - { return Vector(x - a.x, y - a.y); } - Vector operator*(double a) const - { return Vector(x*a, y*a); } - Vector operator/(double a) const - { return Vector(x/a, y/a); } - - static Vector zero() { return Vector(); } -}; - -class Rect { -public: - Vector p0, p1; - - bool intersects(const Rect &other) const - { return ::intersects(p0.x, p1.x, other.p0.x, other.p1.x) - && ::intersects(p0.y, p1.y, other.p0.y, other.p1.y); } - - Rect expand(const Vector &p) const { - Rect r; - r.p0.x = std::min(std::min(p0.x, p1.x), p.x); - r.p0.y = std::min(std::min(p0.y, p1.y), p.y); - r.p1.x = std::max(std::max(p0.x, p1.x), p.x); - r.p1.y = std::max(std::max(p0.y, p1.y), p.y); - return r; - } -}; - -inline bool intersects(const Rect &a, const Rect &b) - { return a.intersects(b); } +#include "geometry.h" +#include "polyspan.h" class Contour { @@ -133,8 +59,6 @@ public: void conic_to(const Vector &v, const Vector &t); void close(); - void assign(const Contour &other); - const ChunkList& get_chunks() const { return chunks; } const Vector& current() const @@ -142,6 +66,10 @@ public: void split(Contour &c, const Rect &bounds, const Vector &min_size) const; + void transform(const Rect &from, const Rect &to); + + void to_polyspan(Polyspan &polyspan) const; + private: void line_split( Rect &ref_line_bounds, @@ -155,9 +83,9 @@ private: const Vector &min_size, const Vector &p1, const Vector ¢er, - double radius, - double radians0, - double radians1, + Real radius, + Real radians0, + Real radians1, int level = 64 ); void cubic_split( @@ -174,17 +102,17 @@ private: const Vector &p1, const Vector &t, Vector &out_center, - double &out_radius, - double &out_radians0, - double &out_radians1 ); + Real &out_radius, + Real &out_radians0, + Real &out_radians1 ); static Rect conic_bounds( const Vector &p0, const Vector &p1, const Vector ¢er, - double radius, - double radians0, - double radians1 ); + Real radius, + Real radians0, + Real radians1 ); static void cubic_convert( const Vector &p0, diff --git a/c++/contourgl/contourbuilder.cpp b/c++/contourgl/contourbuilder.cpp index 92162f3..4084c14 100644 --- a/c++/contourgl/contourbuilder.cpp +++ b/c++/contourgl/contourbuilder.cpp @@ -82,7 +82,7 @@ void ContourBuilder::build_simple(vector &c) { c.push_back(c.front()); } -void ContourBuilder::build_car(Contour &c, const Vector &o, double s) { +void ContourBuilder::build_car(Contour &c, const Vector &o, Real s) { c.move_to( Vector( 5, -1)*s + o); c.line_to( Vector( 4, -1)*s + o); c.conic_to( Vector( 2, -1)*s + o, Vector( 0, -1)*s); @@ -98,22 +98,22 @@ void ContourBuilder::build_car(Contour &c, const Vector &o, double s) { } void ContourBuilder::build(Contour &c) { - double scale = 0.8/5.0; + Real scale = 0.8/5.0; int count = 100; - double size = (double)(count + 2)/(double)(count); - double step = 2.0*size/(double)(count + 1); - double origin = step - size; - double s = 2*size*scale/(double)(count); + Real size = (Real)(count + 2)/(Real)(count); + Real step = 2.0*size/(Real)(count + 1); + Real origin = step - size; + Real s = 2*size*scale/(Real)(count); for(int i = 0; i < count; ++i) for(int j = 0; j < count; ++j) build_car(c, Vector(origin + i*step, origin + j*step), s); count = 100; - size = (double)(count + 2)/(double)(count); - step = 2.0*size/(double)(count + 1); + size = (Real)(count + 2)/(Real)(count); + step = 2.0*size/(Real)(count + 1); origin = step - size; - s = size*scale/(double)(count); + s = size*scale/(Real)(count); for(int i = 0; i < count; ++i) for(int j = 0; j < count; ++j) build_car(c, Vector(origin + i*step, origin + j*step), s); diff --git a/c++/contourgl/contourbuilder.h b/c++/contourgl/contourbuilder.h index 17c4e67..1395c25 100644 --- a/c++/contourgl/contourbuilder.h +++ b/c++/contourgl/contourbuilder.h @@ -20,6 +20,6 @@ class ContourBuilder { public: static void build_simple(std::vector &c); - static void build_car(Contour &c, const Vector &o, double s); + static void build_car(Contour &c, const Vector &o, Real s); static void build(Contour &c); }; diff --git a/c++/contourgl/contourgl.cpp b/c++/contourgl/contourgl.cpp index 2c7b10f..14d1b0a 100644 --- a/c++/contourgl/contourgl.cpp +++ b/c++/contourgl/contourgl.cpp @@ -16,19 +16,19 @@ */ #include +#include #include #include #include #include -#include - #include #include #include -#include "contourbuilder.h" +#include "test.h" + #define GLX_CONTEXT_MAJOR_VERSION_ARB 0x2091 #define GLX_CONTEXT_MINOR_VERSION_ARB 0x2092 @@ -38,227 +38,6 @@ typedef GLXContext (*GLXCREATECONTEXTATTRIBSARBPROC)(Display*, GLXFBConfig, GLXC using namespace std; -void save_rgba(const void *buffer, int width, int height, const string &filename) { - // create file - ofstream f(filename.c_str(), ofstream::out | ofstream::trunc | ofstream::binary); - - // write header - unsigned char targa_header[] = { - 0, // Length of the image ID field (0 - no ID field) - 0, // Whether a color map is included (0 - no colormap) - 2, // Compression and color types (2 - uncompressed true-color image) - 0, 0, 0, 0, 0, // Color map specification (not need for us) - 0, 0, // X-origin - 0, 0, // Y-origin - (unsigned char)(width & 0xff), // Image width - (unsigned char)(width >> 8), - (unsigned char)(height & 0xff), // Image height - (unsigned char)(height >> 8), - 32, // Bits per pixel - 0 // Image descriptor (keep zero for capability) - }; - f.write((char*)targa_header, sizeof(targa_header)); - - // write data - int line_size = 4*width; - const char *end = (char*)buffer; - const char *current = end + height*line_size; - while(current > end) { - current -= line_size; - f.write(current, line_size); - } -} - -void save_viewport(const string &filename) { - glFinish(); - int vp[4] = {}; - glGetIntegerv(GL_VIEWPORT, vp); - char *buffer = new char[vp[2]*vp[3]*4]; - glReadPixels(vp[0], vp[1], vp[2], vp[3], GL_BGRA, GL_UNSIGNED_BYTE, buffer); - save_rgba(buffer, vp[2], vp[3], filename); -} - -void draw_contour_strip(const vector &c) { - glBegin(GL_TRIANGLE_STRIP); - for(vector::const_iterator i = c.begin(); i != c.end(); ++i) { - glVertex2d(i->x, i->y); - glVertex2d(-1.0, i->y); - } - glEnd(); -} - -void draw_contour_strip(const Contour &c) { - glBegin(GL_TRIANGLE_STRIP); - const Contour::ChunkList &chunks = c.get_chunks(); - Vector prev; - for(Contour::ChunkList::const_iterator i = chunks.begin(); i != chunks.end(); ++i) { - if ( i->type == Contour::LINE - || i->type == Contour::CLOSE) - { - glVertex2d(i->p1.x, i->p1.y); - glVertex2d(-1.0, i->p1.y); - prev.x = -1.0; - prev.y = i->p1.y; - } else { - glVertex2d(prev.x, prev.y); - glVertex2d(prev.x, prev.y); - glVertex2d(i->p1.x, i->p1.y); - glVertex2d(i->p1.x, i->p1.y); - prev = i->p1; - } - } - glEnd(); -} - -template -void draw_contour(const T &c, bool even_odd, bool invert) { - glPushAttrib(GL_ALL_ATTRIB_BITS); - glEnable(GL_STENCIL_TEST); - - // render mask - glClear(GL_STENCIL_BUFFER_BIT); - glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE); - glStencilFunc(GL_ALWAYS, 0, 0); - if (even_odd) { - glStencilOp(GL_KEEP, GL_KEEP, GL_INCR_WRAP); - } else { - glStencilOpSeparate(GL_FRONT, GL_INCR_WRAP, GL_INCR_WRAP, GL_INCR_WRAP); - glStencilOpSeparate(GL_BACK, GL_DECR_WRAP, GL_DECR_WRAP, GL_DECR_WRAP); - } - draw_contour_strip(c); - - // fill mask - glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE); - glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP); - if (!even_odd && !invert) - glStencilFunc(GL_NOTEQUAL, 0, -1); - if (!even_odd && invert) - glStencilFunc(GL_EQUAL, 0, -1); - if ( even_odd && !invert) - glStencilFunc(GL_EQUAL, 1, 1); - if ( even_odd && invert) - glStencilFunc(GL_EQUAL, 0, 1); - - glBegin(GL_TRIANGLE_STRIP); - glVertex2d(-1.0, -1.0); - glVertex2d( 1.0, -1.0); - glVertex2d(-1.0, 1.0); - glVertex2d( 1.0, 1.0); - glEnd(); - - glPopAttrib(); -} - -class test_wrapper { -private: - string filename; - clock_t t; - test_wrapper(const test_wrapper&): t() { } - test_wrapper& operator= (const test_wrapper&) { return *this; } -public: - test_wrapper(const string &filename): filename(filename), t(clock()) { } - ~test_wrapper() { - glFinish(); - double ms = 1000.0*(double)(clock() - t)/(double)(CLOCKS_PER_SEC); - cout << ms << " ms - " << filename << endl; - if (filename.size() > 4 && filename.substr(filename.size()-4, 4) == ".tga") - save_viewport(filename); - glClear(GL_COLOR_BUFFER_BIT); - glFinish(); - } -}; - -void test1() { - vector c; - ContourBuilder::build_simple(c); - cout << c.size() << " vertices" << endl; - - glPushAttrib(GL_ALL_ATTRIB_BITS); - glColor4d(0.0, 0.0, 1.0, 1.0); - - { - test_wrapper t("test_1_contour.tga"); - glBegin(GL_LINE_STRIP); - for(vector::const_iterator i = c.begin(); i != c.end(); ++i) - glVertex2d(i->x, i->y); - glEnd(); - } - - { - test_wrapper t("test_1_contour_fill.tga"); - draw_contour(c, false, false); - } - - { - test_wrapper t("test_1_contour_fill_invert.tga"); - draw_contour(c, false, true); - } - - { - test_wrapper t("test_1_contour_evenodd.tga"); - draw_contour(c, true, false); - } - - { - test_wrapper t("test_1_contour_evenodd_invert.tga"); - draw_contour(c, true, true); - } - - glPopAttrib(); -} - -void test2() { - Contour c, cc; - ContourBuilder::build(cc); - cout << cc.get_chunks().size() << " commands" << endl; - - Rect bounds; - bounds.p0 = Vector(-1.0, -1.0); - bounds.p1 = Vector( 1.0, 1.0); - Vector min_size(1.0/1024.0, 1.0/1024.0); - - { - test_wrapper("test_2_split"); - cc.split(c, bounds, min_size); - } - - const Contour::ChunkList &chunks = c.get_chunks(); - cout << chunks.size() << " vertices" << endl; - - glPushAttrib(GL_ALL_ATTRIB_BITS); - glColor4d(0.0, 0.0, 1.0, 1.0); - - { - test_wrapper t("test_2_contour.tga"); - glBegin(GL_LINE_STRIP); - for(Contour::ChunkList::const_iterator i = chunks.begin(); i != chunks.end(); ++i) - glVertex2d(i->p1.x, i->p1.y); - glEnd(); - } - - { - test_wrapper t("test_2_contour_fill.tga"); - draw_contour(c, false, false); - } - - { - test_wrapper t("test_2_contour_fill_invert.tga"); - draw_contour(c, false, true); - } - - { - test_wrapper t("test_2_contour_evenodd.tga"); - draw_contour(c, true, false); - } - - { - test_wrapper t("test_2_contour_evenodd_invert.tga"); - draw_contour(c, true, true); - } - - glPopAttrib(); -} - int main() { // open display (we will use default display and screen 0) Display *display = XOpenDisplay(NULL); @@ -311,8 +90,9 @@ int main() { glViewport(0, 0, pbuffer_width, pbuffer_height); // do something - test1(); - test2(); + Test::test1(); + Test::test2(); + Test::test3(); // deinitialization glXMakeContextCurrent(display, None, None, NULL); diff --git a/c++/contourgl/geometry.h b/c++/contourgl/geometry.h new file mode 100644 index 0000000..10f6ad8 --- /dev/null +++ b/c++/contourgl/geometry.h @@ -0,0 +1,112 @@ +/* + ......... 2015 Ivan Mahonin + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + +#ifndef _GEOMETRY_H_ +#define _GEOMETRY_H_ + +#include + +#include + + +typedef double Real; + +template +bool intersects(const T &a0, const T &a1, const T &b0, const T &b1) { + return !(std::max(b0, b1) < std::min(a0, a1)) + && !(std::max(a0, a1) < std::min(b0, b1)); +} + +inline Real wrap_angle(Real a, Real round) { + Real rounds = a/round + 0.5; + return (rounds - floor(rounds) - 0.5)*round; +} + +inline bool angle_between(Real a0, Real a1, Real a, Real round) { + if (a1 < a0) std::swap(a0, a1); + a0 = wrap_angle(a0, round); + a1 = wrap_angle(a1, round); + a = wrap_angle(a, round); + if (a < a0) a += round; + if (a1 < a0) a1 += round; + return a0 < a && a < a1; +} + +class Vector { +public: + union { + struct { Real x, y; }; + struct { Real coords[]; }; + }; + + Vector(): + x(), y() { } + Vector(Real x, Real y): + x(x), y(y) { } + + Real& operator[] (int index) + { return coords[index]; } + const Real& operator[] (int index) const + { return coords[index]; } + bool is_equal_to(const Vector &other) const + { return fabs(x - other.x) < 1e-6 && fabs(y - other.y) < 1e-6; } + + Vector operator+(const Vector &a) const + { return Vector(x + a.x, y + a.y); } + Vector operator-(const Vector &a) const + { return Vector(x - a.x, y - a.y); } + Vector operator*(const Vector &a) const + { return Vector(x*a.x, y*a.y); } + Vector operator/(const Vector &a) const + { return Vector(x/a.x, y/a.y); } + + Vector operator*(Real a) const + { return Vector(x*a, y*a); } + Vector operator/(Real a) const + { return Vector(x/a, y/a); } + + static Vector zero() { return Vector(); } +}; + +class Rect { +public: + Vector p0, p1; + + bool intersects(const Rect &other) const + { return ::intersects(p0.x, p1.x, other.p0.x, other.p1.x) + && ::intersects(p0.y, p1.y, other.p0.y, other.p1.y); } + + Rect expand(const Vector &p) const { + Rect r; + r.p0.x = std::min(std::min(p0.x, p1.x), p.x); + r.p0.y = std::min(std::min(p0.y, p1.y), p.y); + r.p1.x = std::max(std::max(p0.x, p1.x), p.x); + r.p1.y = std::max(std::max(p0.y, p1.y), p.y); + return r; + } +}; + +class ContextRect { +public: + int minx, miny, maxx, maxy; + ContextRect(): minx(), miny(), maxx(), maxy() { } +}; + +inline bool intersects(const Rect &a, const Rect &b) + { return a.intersects(b); } + +#endif diff --git a/c++/contourgl/polyspan.cpp b/c++/contourgl/polyspan.cpp new file mode 100644 index 0000000..fe6747f --- /dev/null +++ b/c++/contourgl/polyspan.cpp @@ -0,0 +1,775 @@ +/* + polyspan.cpp + Polyspan + + Copyright (c) 2002-2005 Robert B. Quattlebaum Jr., Adrian Bentley + Copyright (c) 2007, 2008 Chris Moore + Copyright (c) 2012-2013 Carlos López + ......... ... 2015 Ivan Mahonin + + This package is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of + the License, or (at your option) any later version. + + This package is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. +*/ + +#include + +#include "polyspan.h" + + +Polyspan::Polyspan(): + open_index(0), + cur_x(0.0), + cur_y(0.0), + close_x(0.0), + close_y(0.0), + flags(NotSorted) +{ } + +void Polyspan::clear() { + covers.clear(); + cur_x = cur_y = close_x = close_y = 0; + open_index = 0; + current.set(0, 0, 0, 0); + flags = NotSorted; +} + +// add the current cell, but only if there is information to add +void Polyspan::addcurrent() { + if (current.cover || current.area) { + if (covers.size() == covers.capacity()) + covers.reserve(covers.size() + 1024*1024); + covers.push_back(current); + } +} + +// move to the next cell (cover values 0 initially), keeping the current if necessary +void Polyspan::move_pen(int x, int y) { + if (y != current.y || x != current.x) { + addcurrent(); + current.set(x, y, 0, 0); + } +} + +// close the primitives with a line (or rendering will not work as expected) +void Polyspan::close() { + if (flags & NotClosed) { + if (cur_x != close_x || cur_y != close_y) { + line_to(close_x, close_y); + addcurrent(); + current.setcover(0,0); + } + flags &= ~NotClosed; + } +} + +// Not recommended - destroys any separation of spans currently held +void Polyspan::merge_all() { + sort(covers.begin(), covers.end()); + open_index = 0; +} + +// will sort the marks if they are not sorted +void Polyspan::sort_marks() { + if (flags & NotSorted) { + //only sort the open index + addcurrent(); + current.setcover(0, 0); + + sort(covers.begin() + open_index, covers.end()); + flags &= ~NotSorted; + } +} + +// encapsulate the current sublist of marks (used for drawing) +void Polyspan::encapsulate_current() { + // sort the current list then reposition the open list section + sort_marks(); + open_index = covers.size(); +} + +// move to start a new primitive list (enclose the last primitive if need be) +void Polyspan::move_to(Real x, Real y) { + close(); + if (isnan(x)) x=0; + if (isnan(y)) y=0; + move_pen((int)floor(x), (int)floor(y)); + close_y = cur_y = y; + close_x = cur_x = x; +} + +// primitive_to functions +void Polyspan::line_to(Real x, Real y) { + Real n[4] = {0, 0, 0, 0}; + bool afterx = false; + + const Real xin(x), yin(y); + + Real dx = x - cur_x; + Real dy = y - cur_y; + + // CLIP IT!!!! + // outside y - ignore entirely + if ( (cur_y >= window.maxy && y >= window.maxy) + || (cur_y < window.miny && y < window.miny) ) + { + cur_x = x; + cur_y = y; + } else { // not degenerate - more complicated + if (dy > 0) { //be sure it's not tooooo small + // cur_y ... window.miny ... window.maxy ... y + + // initial degenerate - initial clip + if (cur_y < window.miny) { + // new clipped start point (must also move pen) + n[2] = cur_x + (window.miny - cur_y)*dx/dy; + + cur_x = n[2]; + cur_y = window.miny; + move_pen((int)floor(cur_x), window.miny); + } + + // generate data for the ending clipped info + if (y > window.maxy) { + // initial line to intersection (and degenerate) + n[2] = x + (window.maxy - y)*dx/dy; + + //intersect coords + x = n[2]; + y = window.maxy; + } + } else { + // initial degenerate - initial clip + if (cur_y > window.maxy) { + // new clipped start point (must also move pen) + n[2] = cur_x + (window.maxy - cur_y)*dx/dy; + + cur_x = n[2]; + cur_y = window.maxy; + move_pen((int)floor(cur_x), window.maxy); + } + + // generate data for the ending clipped info + if (y < window.miny) { + // initial line to intersection (and degenerate) + n[2] = x + (window.miny - y)*dx/dy; + + // intersect coords + x = n[2]; + y = window.miny; + } + } + + // all degenerate - but require bounded clipped values + if ( (cur_x >= window.maxx && x >= window.maxx) + || (cur_x < window.minx && x < window.minx) ) + { + //clip both vertices - but only needed in the x direction + cur_x = std::max(cur_x, (Real)window.minx); + cur_x = std::min(cur_x, (Real)window.maxx); + + //clip the dest values - y is already clipped + x = std::max(x, (Real)window.minx); + x = std::min(x, (Real)window.maxx); + + //must start at new point... + move_pen((int)floor(cur_x), (int)floor(cur_y)); + + draw_line(cur_x,cur_y,x,y); + + cur_x = xin; + cur_y = yin; + } else { + // clip x + if (dx > 0) { + // initial degenerate - initial clip + if (cur_x < window.minx) { + // need to draw an initial segment from clippedx,cur_y to clippedx,intersecty + n[2] = cur_y + (window.minx - cur_x)*dy/dx; + + move_pen(window.minx, (int)floor(cur_y)); + draw_line(window.minx, cur_y, window.minx, n[2]); + + cur_x = window.minx; + cur_y = n[2]; + } + + // generate data for the ending clipped info + if (x > window.maxx) { + // initial line to intersection (and degenerate) + n[2] = y + (window.maxx - x)*dy/dx; + + n[0] = window.maxx; + n[1] = y; + + // intersect coords + x = window.maxx; + y = n[2]; + afterx = true; + } + } else { + // initial degenerate - initial clip + if (cur_x > window.maxx) { + // need to draw an initial segment from clippedx,cur_y to clippedx,intersecty + n[2] = cur_y + (window.maxx - cur_x)*dy/dx; + + move_pen(window.maxx, (int)floor(cur_y)); + draw_line(window.maxx, cur_y, window.maxx, n[2]); + + cur_x = window.maxx; + cur_y = n[2]; + } + + // generate data for the ending clipped info + if (x < window.minx) { + //initial line to intersection (and degenerate) + n[2] = y + (window.minx - x)*dy/dx; + + n[0] = window.minx; + n[1] = y; + + //intersect coords + x = window.minx; + y = n[2]; + afterx = true; + } + } + + move_pen((int)floor(cur_x), (int)floor(cur_y)); + // draw the relevant line (clipped) + draw_line(cur_x, cur_y, x, y); + + if (afterx) + draw_line(x, y, n[0], n[1]); + + cur_x = xin; + cur_y = yin; + } + } + + flags |= NotClosed | NotSorted; +} + +bool Polyspan::clip_conic(const Vector * const p, const ContextRect &r) { + const Real minx = std::min(std::min(p[0][0], p[1][0]), p[2][0]); + const Real miny = std::min(std::min(p[0][1], p[1][1]), p[2][1]); + const Real maxx = std::max(std::max(p[0][0], p[1][0]), p[2][0]); + const Real maxy = std::max(std::max(p[0][1], p[1][1]), p[2][1]); + + return (minx > r.maxx) || + (maxx < r.minx) || + (miny > r.maxy) || + (maxy < r.miny); +} + +Real Polyspan::max_edges_conic(const Vector *const p) { + const Real x1 = p[1][0] - p[0][0]; + const Real y1 = p[1][1] - p[0][1]; + + const Real x2 = p[2][0] - p[1][0]; + const Real y2 = p[2][1] - p[1][1]; + + const Real d1 = x1*x1 + y1*y1; + const Real d2 = x2*x2 + y2*y2; + + return std::max(d1,d2); +} + +void Polyspan::subd_conic_stack(Vector *arc) { + /* + + b0 + * 0+1 a + b1 b * 1+2*1+2 a + * 1+2 b * + b2 * + * + + 0.1.2 -> 0.1 2 3.4 + + */ + + Real a, b; + + + arc[4][0] = arc[2][0]; + b = arc[1][0]; + + a = arc[1][0] = (arc[0][0] + b)/2; + b = arc[3][0] = (arc[4][0] + b)/2; + arc[2][0] = (a + b)/2; + + + arc[4][1] = arc[2][1]; + b = arc[1][1]; + + a = arc[1][1] = (arc[0][1] + b)/2; + + b = arc[3][1] = (arc[4][1] + b)/2; + arc[2][1] = (a + b)/2; + + /* //USING SIMD + + arc[4] = arc[2]; + + arc[3] = (arc[2] + arc[1])/2; + arc[1] = (arc[0] + arc[1])/2; + + arc[2] = (arc[1] + arc[3])/2; + + */ +} + +void Polyspan::conic_to(Real x1, Real y1, Real x, Real y) { + Vector *current = arc; + int level = 0; + int num = 0; + bool onsecond = false; + + arc[0] = Vector(x, y); + arc[1] = Vector(x1, y1); + arc[2] = Vector(cur_x, cur_y); + + // just draw the line if it's outside + if (clip_conic(arc, window)) + { + line_to(x,y); + return; + } + + // Ok so it's not super degenerate, subdivide and draw (run through minimum subdivision levels first) + while(current >= arc) { + assert(num < MAX_SUBDIVISION_SIZE); + + // if the curve is clipping then draw degenerate + if (clip_conic(current, window)) { + line_to(current[0][0],current[0][1]); //backwards so front is destination + current -= 2; + if (onsecond) level--; + onsecond = true; + num--; + continue; + } else + // if we are not at the level minimum + if (level < MIN_SUBDIVISION_DRAW_LEVELS) { + subd_conic_stack(current); + current += 2; // cursor on second curve + level ++; + num ++; + onsecond = false; + continue; + } else + // split it again, if it's too big + if (max_edges_conic(current) > 0.25) { // distance of .5 (cover no more than half the pixel) + subd_conic_stack(current); + current += 2; // cursor on second curve + level ++; + num ++; + onsecond = false; + } else { // NOT TOO BIG? RENDER!!! + // cur_x, cur_y = current[2], so we need to go 1,0 + line_to(current[1][0], current[1][1]); + line_to(current[0][0], current[0][1]); + + current -= 2; + if (onsecond) level--; + num--; + onsecond = true; + } + } +} + +bool Polyspan::clip_cubic(const Vector *const p, const ContextRect &r) { + return ((p[0][0] > r.maxx) && (p[1][0] > r.maxx) && (p[2][0] > r.maxx) && (p[3][0] > r.maxx)) || + ((p[0][0] < r.minx) && (p[1][0] < r.minx) && (p[2][0] < r.minx) && (p[3][0] < r.minx)) || + ((p[0][1] > r.maxy) && (p[1][1] > r.maxy) && (p[2][1] > r.maxy) && (p[3][1] > r.maxy)) || + ((p[0][1] < r.miny) && (p[1][1] < r.miny) && (p[2][1] < r.miny) && (p[3][1] < r.miny)); +} + +Real Polyspan::max_edges_cubic(const Vector *const p) { + const Real x1 = p[1][0] - p[0][0]; + const Real y1 = p[1][1] - p[0][1]; + + const Real x2 = p[2][0] - p[1][0]; + const Real y2 = p[2][1] - p[1][1]; + + const Real x3 = p[3][0] - p[2][0]; + const Real y3 = p[3][1] - p[2][1]; + + const Real d1 = x1*x1 + y1*y1; + const Real d2 = x2*x2 + y2*y2; + const Real d3 = x3*x3 + y3*y3; + + return std::max(std::max(d1, d2), d3); +} + +void Polyspan::subd_cubic_stack(Vector *arc) { + Real a, b, c; + + /* + + b0 + * 0+1 a + b1 b * 1+2*1+2 a + * 1+2 b * 0+3*1+3*2+3 + b2 c * 1+2*2+2 b * + * 2+3 c * + b3 * + * + + 0.1 2.3 -> 0.1 2 3 4 5.6 + + */ + + arc[6][0] = arc[3][0]; + + b = arc[1][0]; + c = arc[2][0]; + + a = arc[1][0] = (arc[0][0] + b)/2; + b = (b + c)/2; + c = arc[5][0] = (arc[6][0] + c)/2; + + a = arc[2][0] = (a + b)/2; + b = arc[4][0] = (b + c)/2; + + arc[3][0] = (a + b)/2; + + + arc[6][1] = arc[3][1]; + + b = arc[1][1]; + c = arc[2][1]; + + a = arc[1][1] = (arc[0][1] + b)/2; + b = (b + c)/2; + c = arc[5][1] = (arc[6][1] + c)/2; + + a = arc[2][1] = (a + b)/2; + b = arc[4][1] = (b + c)/2; + + arc[3][1] = (a + b)/2; +} + +void Polyspan::cubic_to(Real x1, Real y1, Real x2, Real y2, Real x, Real y) { + Vector *current = arc; + int num = 0; + int level = 0; + bool onsecond = false; + + arc[0] = Vector(x, y); + arc[1] = Vector(x2, y2); + arc[2] = Vector(x1, y1); + arc[3] = Vector(cur_x, cur_y); + + // just draw the line if it's outside + if (clip_cubic(arc, window)) { + line_to(x,y); + return; + } + + // Ok so it's not super degenerate, subdivide and draw (run through minimum subdivision levels first) + while(current >= arc) { // once current goes below arc, there are no more curves left + assert(num < MAX_SUBDIVISION_SIZE); + + // if we are not at the level minimum + if (level < MIN_SUBDIVISION_DRAW_LEVELS) { + subd_cubic_stack(current); + current += 3; // cursor on second curve + level ++; + num ++; + onsecond = false; + continue; + } else + // if the curve is clipping then draw degenerate + if (clip_cubic(current, window)) { + line_to(current[0][0], current[0][1]); // backwards so front is destination + current -= 3; + if (onsecond) level--; + onsecond = true; + num --; + continue; + } else + // split it again, if it's too big + if (max_edges_cubic(current) > 0.25) { //could use max_edges<3> + subd_cubic_stack(current); + current += 3; // cursor on second curve + level ++; + num ++; + onsecond = false; + } else { // NOT TOO BIG? RENDER!!! + // cur_x, cur_y = current[3], so we need to go 2,1,0 + line_to(current[2][0], current[2][1]); + line_to(current[1][0], current[1][1]); + line_to(current[0][0], current[0][1]); + + current -= 3; + if (onsecond) level--; + num --; + onsecond = true; + } + } +} + +void Polyspan::draw_scanline(int y, Real x1, Real y1, Real x2, Real y2) { + int ix1 = (int)floor(x1); + int ix2 = (int)floor(x2); + Real fx1 = x1 - ix1; + Real fx2 = x2 - ix2; + + Real dx,dy,dydx,mult; + + dx = x2 - x1; + dy = y2 - y1; + + // case horizontal line + if (y1 == y2) { + move_pen(ix2, y); // pen needs to be at the last coord + return; + } + + // case all in same pixel + if (ix1 == ix2) { // impossible for degenerate case (covered by the previous cases) + current.addcover(dy, (fx1 + fx2)*dy/2); // horizontal trapezoid area + return; + } + + if (dx > 0) { + // ----> fx1...1 0...1 ... 0...1 0...fx2 + dydx = dy/dx; + + // set initial values + // Iterate through the covered pixels + mult = (1 - fx1)*dydx; // next y intersection diff value (at 1) + + // first pixel + current.addcover(mult, (1 + fx1)*mult/2); // fx1, fy1, 1, fy@1 - starting trapezoidal area + + // move to the next pixel + y1 += mult; + ix1++; + + move_pen(ix1, y); + + // set up for whole ones + while(ix1 != ix2) { + // trapezoid(0, y1, 1, y1 + dydx); + current.addcover(dydx,dydx/2); // accumulated area 1/2 the cover + + // move to next pixel (+1) + ix1++; + y1 += dydx; + move_pen(ix1, y); + } + + // last pixel + // final y-pos - last intersect pos + mult = fx2 * dydx; + current.addcover(mult, (0 + fx2)*mult/2); + } else { + // fx2...1 0...1 ... 0...1 0...fx1 <---- + // mult = (0 - fx1) * dy / dx; + // neg sign sucked into dydx + dydx = -dy/dx; + + // set initial values + // Iterate through the covered pixels + mult = fx1*dydx; // next y intersection diff value + + // first pixel + current.addcover(mult, fx1*mult/2); // fx1, fy1, 0, fy@0 - starting trapezoidal area + + // move to next pixel + y1 += mult; + ix1--; + + move_pen(ix1, y); + + // set up for whole ones + while(ix1 != ix2) { + // trapezoid(0, y1, 1, y1+dydx); + current.addcover(dydx, dydx/2); // accumulated area 1/2 the cover + + // move to next pixel (-1) + y1 += dydx; + ix1--; + move_pen(ix1, y); + } + + // last pixel + mult = y2 - y1; // final y-pos - last intersect pos + + current.addcover(mult, (fx2+1)*mult/2); + } +} + +void Polyspan::draw_line(Real x1, Real y1, Real x2, Real y2) { + int iy1 = (int)floor(y1); + int iy2 = (int)floor(y2); + Real fy1 = y1 - iy1; + Real fy2 = y2 - iy2; + + assert(!isnan(fy1)); + assert(!isnan(fy2)); + + Real dx,dy,dxdy,mult,x_from,x_to; + + const Real SLOPE_EPSILON = 1e-10; + + // case all one scanline + if (iy1 == iy2) { + draw_scanline(iy1, x1, y1, x2, y2); + return; + } + + // difference values + dy = y2 - y1; + dx = x2 - x1; + + // case vertical line + if (dx < SLOPE_EPSILON && dx > -SLOPE_EPSILON) { + // calc area and cover on vertical line + if (dy > 0) { + // ----> fx1...1 0...1 ... 0...1 0...fx2 + Real sub; + + int ix1 = (int)floor(x1); + Real fx1 = x1 - ix1; + + // current pixel + sub = 1 - fy1; + + current.addcover(sub, fx1*sub); + + // next pixel + iy1++; + + // move pen to next pixel + move_pen(ix1, iy1); + + while(iy1 != iy2) { + // accumulate cover + current.addcover(1,fx1); + + // next pixel + iy1++; + move_pen(ix1, iy1); + } + + // last pixel + current.addcover(fy2, fy2*fx1); + } else { + Real sub; + + int ix1 = (int)floor(x1); + Real fx1 = x1 - ix1; + + // current pixel + sub = 0 - fy1; + + current.addcover(sub, fx1*sub); + + // next pixel + iy1--; + + move_pen(ix1, iy1); + + while(iy1 != iy2) { + // accumulate in current pixel + current.addcover(-1,-fx1); + + // move to next + iy1--; + move_pen(ix1,iy1); + } + + current.addcover(fy2-1,(fy2-1)*fx1); + } + return; + } + + // case normal line - guaranteed dx != 0 && dy != 0 + + // calculate the initial intersection with "next" scanline + if (dy > 0) { + dxdy = dx/dy; + + mult = (1 - fy1)*dxdy; + + // x intersect scanline + x_from = x1 + mult; + draw_scanline(iy1, x1, fy1, x_from, 1); + + // move to next line + iy1++; + + move_pen((int)floor(x_from), iy1); + + while(iy1 != iy2) { + // keep up on the x axis, and render the current scanline + x_to = x_from + dxdy; + draw_scanline(iy1, x_from, 0, x_to, 1); + x_from = x_to; + + // move to next pixel + iy1++; + move_pen((int)floor(x_from), iy1); + } + + //draw the last one, fractional + draw_scanline(iy2, x_from, 0, x2, fy2); + } else { + dxdy = -dx/dy; + + mult = fy1*dxdy; + + // x intersect scanline + x_from = x1 + mult; + draw_scanline(iy1,x1,fy1,x_from,0); + + // each line after + iy1--; + + move_pen((int)floor(x_from), iy1); + + while(iy1 != iy2) { + x_to = x_from + dxdy; + draw_scanline(iy1, x_from, 1, x_to, 0); + x_from = x_to; + + iy1--; + move_pen((int)floor(x_from), iy1); + } + // draw the last one, fractional + draw_scanline(iy2, x_from, 1, x2, fy2); + } +} + +Real Polyspan::extract_alpha(Real area, bool evenodd) const { + if (area < 0) + area = -area; + + if (evenodd) { + // even-odd winding style + while (area > 1) + area -= 2; + + // want pyramid like thing + if (area < 0) + area = -area; + } else { + // non-zero winding style + if (area > 1) + return 1; + } + + return area; +} + +/* === E N T R Y P O I N T ================================================= */ diff --git a/c++/contourgl/polyspan.h b/c++/contourgl/polyspan.h new file mode 100644 index 0000000..c0267fc --- /dev/null +++ b/c++/contourgl/polyspan.h @@ -0,0 +1,146 @@ +/* + polyspan.h + Polyspan Header + + Copyright (c) 2002-2005 Robert B. Quattlebaum Jr., Adrian Bentley + Copyright (c) 2007, 2008 Chris Moore + Copyright (c) 2012-2013 Carlos López + ......... ... 2015 Ivan Mahonin + + This package is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of + the License, or (at your option) any later version. + + This package is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. +*/ + +#ifndef _POLYSPAN_H_ +#define _POLYSPAN_H_ + +#include + +#include "geometry.h" + +class Polyspan { +public: + struct PenMark { + int y, x; + Real cover, area; + + PenMark(): y(), x(), cover(), area() { } + PenMark(int xin, int yin, Real c, Real a): + y(yin), x(xin), cover(c), area(a) { } + void set(int xin, int yin, Real c, Real a) + { y = yin; x = xin; cover = c; area = a; } + void setcoord(int xin, int yin) + { y = yin; x = xin; } + void setcover(Real c, Real a) + { cover = c; area = a; } + void addcover(Real c, Real a) + { cover += c; area += a; } + bool operator < (const PenMark &rhs) const + { return y == rhs.y ? x < rhs.x : y < rhs.y; } + }; + + typedef std::vector cover_array; + + //for assignment to flags value + enum PolySpanFlags { + NotSorted = 0x8000, + NotClosed = 0x4000 + }; + + enum { + MAX_SUBDIVISION_SIZE = 64, + MIN_SUBDIVISION_DRAW_LEVELS = 4 + }; + +private: + Vector arc[3*MAX_SUBDIVISION_SIZE + 1]; + + cover_array covers; + PenMark current; + + int open_index; + + //ending position of last primitive + Real cur_x; + Real cur_y; + + //starting position of current primitive list + Real close_x; + Real close_y; + + //flags for the current segment + int flags; + + //the window that will be drawn (used for clipping) + ContextRect window; + + //add the current cell, but only if there is information to add + void addcurrent(); + + //move to the next cell (cover values 0 initially), keeping the current if necessary + void move_pen(int x, int y); + + static bool clip_conic(const Vector *const p, const ContextRect &r); + static Real max_edges_conic(const Vector *const p); + static void subd_conic_stack(Vector *arc); + + static bool clip_cubic(const Vector *const p, const ContextRect &r); + static Real max_edges_cubic(const Vector *const p); + static void subd_cubic_stack(Vector *arc); + +public: + Polyspan(); + + const ContextRect& get_window() const { return window; } + const cover_array& get_covers() const { return covers; } + + bool notclosed() const + { return (flags & NotClosed) || (cur_x != close_x) || (cur_y != close_y); } + + //0 out all the variables involved in processing + void clear(); + void init(const ContextRect &window) + { clear(); this->window = window; } + void init(int minx, int miny, int maxx, int maxy) + { + clear(); + window.minx = minx; + window.miny = miny; + window.maxx = maxx; + window.maxy = maxy; + } + + //close the primitives with a line (or rendering will not work as expected) + void close(); + + // Not recommended - destroys any separation of spans currently held + void merge_all(); + + //will sort the marks if they are not sorted + void sort_marks(); + + //encapsulate the current sublist of marks (used for drawing) + void encapsulate_current(); + + //move to start a new primitive list (enclose the last primitive if need be) + void move_to(Real x, Real y); + + //primitive_to functions + void line_to(Real x, Real y); + void conic_to(Real x1, Real y1, Real x, Real y); + void cubic_to(Real x1, Real y1, Real x2, Real y2, Real x, Real y); + + void draw_scanline(int y, Real x1, Real y1, Real x2, Real y2); + void draw_line(Real x1, Real y1, Real x2, Real y2); + + Real extract_alpha(Real area, bool evenodd) const; +}; + +#endif diff --git a/c++/contourgl/rendersw.cpp b/c++/contourgl/rendersw.cpp new file mode 100644 index 0000000..b6970d0 --- /dev/null +++ b/c++/contourgl/rendersw.cpp @@ -0,0 +1,180 @@ +/* + ......... 2015 Ivan Mahonin + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + +#include "rendersw.h" + + +using namespace std; + + +void RenderSW::fill( + Surface &target, + const Color &color ) +{ + for(Color *i = target.data, *end = i + target.count(); i != end; ++i) + *i = color; +} + +void RenderSW::fill( + Surface &target, + const Color &color, + int left, + int top, + int width, + int height ) +{ + int step = target.width - width; + for(Color *i = &target[top][left], *end = i + height*target.width; i < end; i += step) + for(Color *rowend = i + width; i < rowend; ++i) + *i = color; +} + +void RenderSW::row( + Surface &target, + const Color &color, + int left, + int top, + int length ) +{ + for(Color *i = &target[top][left], *end = i + length; i < end; ++i) + *i = color; +} + +void RenderSW::row_alpha( + Surface &target, + const Color &color, + Color::type alpha, + int left, + int top, + int length ) +{ + for(Color *i = &target[top][left], *end = i + length; i < end; ++i) { + i->r = color.r; + i->g = color.g; + i->b = color.b; + i->a = min(1.f, i->a + alpha); + } +} + +void RenderSW::polyspan( + Surface &target, + const Polyspan &polyspan, + const Color &color, + bool evenodd, + bool invert ) +{ + const ContextRect &window = polyspan.get_window(); + const Polyspan::cover_array &covers = polyspan.get_covers(); + + Polyspan::cover_array::const_iterator cur_mark = covers.begin(); + Polyspan::cover_array::const_iterator end_mark = covers.end(); + + Real cover = 0, area = 0, alpha = 0; + int y = 0, x = 0; + + if (cur_mark == end_mark) { + // no marks at all + if (invert) + fill( target, color, + window.minx, window.miny, + window.maxx - window.minx, window.maxy - window.miny ); + return; + } + + // fill initial rect / line + if (invert) { + // fill all the area above the first vertex + y = window.miny; + int l = window.maxx - window.minx; + + fill( target, color, + window.minx, window.miny, + l, cur_mark->y - window.miny ); + + // fill the area to the left of the first vertex on that line + l = cur_mark->x - window.minx; + if (l) + row(target, color, window.minx, cur_mark->y, l); + } + + while(true) { + y = cur_mark->y; + x = cur_mark->x; + + area = cur_mark->area; + cover += cur_mark->cover; + + // accumulate for the current pixel + while(++cur_mark != covers.end()) { + if (y != cur_mark->y || x != cur_mark->x) + break; + area += cur_mark->area; + cover += cur_mark->cover; + } + + // draw pixel - based on covered area + if (area) { // if we're ok, draw the current pixel + alpha = polyspan.extract_alpha(cover - area, evenodd); + if (invert) alpha = 1 - alpha; + if (alpha) { + Color &c = target[y][x]; + c.r = color.r; + c.g = color.g; + c.b = color.b; + c.a = min(1.f, c.a + (Color::type)alpha); + } + ++x; + } + + // if we're done, don't use iterator and exit + if (cur_mark == end_mark) + break; + + // if there is no more live pixels on this line, goto next + if (y != cur_mark->y) { + if (invert) { + // fill the area at the end of the line + row(target, color, x, y, window.maxx - x); + + // fill area at the beginning of the next line + row(target, color, window.minx, cur_mark->y, cur_mark->x - window.minx); + } + + cover = 0; + continue; + } + + // draw span to next pixel - based on total amount of pixel cover + if (x < cur_mark->x) { + alpha = polyspan.extract_alpha(cover, evenodd); + if (invert) alpha = 1.0 - alpha; + if (alpha) + row_alpha(target, color, alpha, x, y, cur_mark->x - x); + } + } + + // fill the after stuff + if (invert) { + // fill the area at the end of the line + row(target, color, x, y, window.maxx - x); + + // fill area at the beginning of the next line + fill( target, color, + window.minx, y+1, + window.maxx - window.minx, window.maxy - y - 1 ); + } +} diff --git a/c++/contourgl/rendersw.h b/c++/contourgl/rendersw.h new file mode 100644 index 0000000..2da0811 --- /dev/null +++ b/c++/contourgl/rendersw.h @@ -0,0 +1,89 @@ +/* + ......... 2015 Ivan Mahonin + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + +#ifndef _RENDERSW_H_ +#define _RENDERSW_H_ + +#include + +#include "polyspan.h" + +class Color { +public: + typedef float type; + type r, g, b, a; + Color(): r(), g(), b(), a() { } + Color(type r, type g, type b, type a): r(r), g(g), b(b), a(a) { } + Color(const Color &color, type a): r(color.r), g(color.g), b(color.b), a(color.a*a) { } +}; + +class Surface { +public: + const int width, height; + Color * const data; + + Surface(int width, int height): + width(width), height(height), data(new Color[width*height]) + { clear(); } + + ~Surface() + { delete data; } + + void clear() { memset(data, 0, count()*sizeof(Color)); } + int count() const { return width*height; } + Color* operator[] (int row) { return data + row*width; } + const Color* operator[] (int row) const { return data + row*width; } +}; + +class RenderSW { +public: + static void fill( + Surface &target, + const Color &color ); + + static void fill( + Surface &target, + const Color &color, + int left, + int top, + int width, + int height ); + + static void row( + Surface &target, + const Color &color, + int left, + int top, + int length ); + + static void row_alpha( + Surface &target, + const Color &color, + Color::type alpha, + int left, + int top, + int length ); + + static void polyspan( + Surface &target, + const Polyspan &polyspan, + const Color &color, + bool evenodd, + bool invert ); +}; + +#endif diff --git a/c++/contourgl/test.cpp b/c++/contourgl/test.cpp new file mode 100644 index 0000000..00d8b90 --- /dev/null +++ b/c++/contourgl/test.cpp @@ -0,0 +1,348 @@ +/* + ......... 2015 Ivan Mahonin + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + +#include +#include + +#include +#include +#include + +#include "test.h" + +#include "contour.h" +#include "rendersw.h" +#include "contourbuilder.h" + + +using namespace std; + + +class Test::Helper { +public: + static void save_rgba( + const void *buffer, + int width, + int height, + bool flip, + const string &filename ) + { + // create file + ofstream f(filename.c_str(), ofstream::out | ofstream::trunc | ofstream::binary); + + // write header + unsigned char targa_header[] = { + 0, // Length of the image ID field (0 - no ID field) + 0, // Whether a color map is included (0 - no colormap) + 2, // Compression and color types (2 - uncompressed true-color image) + 0, 0, 0, 0, 0, // Color map specification (not need for us) + 0, 0, // X-origin + 0, 0, // Y-origin + (unsigned char)(width & 0xff), // Image width + (unsigned char)(width >> 8), + (unsigned char)(height & 0xff), // Image height + (unsigned char)(height >> 8), + 32, // Bits per pixel + 0 // Image descriptor (keep zero for capability) + }; + f.write((char*)targa_header, sizeof(targa_header)); + + // write data + if (flip) { + int line_size = 4*width; + const char *end = (char*)buffer; + const char *current = end + height*line_size; + while(current > end) { + current -= line_size; + f.write(current, line_size); + } + } else { + f.write((const char*)buffer, 4*width*height); + } + } + + static void save_viewport(const string &filename) { + glFinish(); + int vp[4] = {}; + glGetIntegerv(GL_VIEWPORT, vp); + char *buffer = new char[vp[2]*vp[3]*4]; + glReadPixels(vp[0], vp[1], vp[2], vp[3], GL_BGRA, GL_UNSIGNED_BYTE, buffer); + save_rgba(buffer, vp[2], vp[3], false, filename); + delete buffer; + } + + static void save_surface(const Surface &surface, const string &filename) { + unsigned char *buffer = new unsigned char[4*surface.count()]; + unsigned char *j = buffer; + for(Color *i = surface.data, *end = i + surface.count(); i != end; ++i, j += 4) { + j[0] = (unsigned char)roundf(max(0.f, min(1.f, i->b))*255.f); + j[1] = (unsigned char)roundf(max(0.f, min(1.f, i->g))*255.f); + j[2] = (unsigned char)roundf(max(0.f, min(1.f, i->r))*255.f); + j[3] = (unsigned char)roundf(max(0.f, min(1.f, i->a))*255.f); + } + save_rgba(buffer, surface.width, surface.height, false, filename); + delete buffer; + } + + static void draw_contour_strip(const vector &c) { + glBegin(GL_TRIANGLE_STRIP); + for(vector::const_iterator i = c.begin(); i != c.end(); ++i) { + glVertex2d(i->x, i->y); + glVertex2d(-1.0, i->y); + } + glEnd(); + } + + static void draw_contour_strip(const Contour &c) { + glBegin(GL_TRIANGLE_STRIP); + const Contour::ChunkList &chunks = c.get_chunks(); + Vector prev; + for(Contour::ChunkList::const_iterator i = chunks.begin(); i != chunks.end(); ++i) { + if ( i->type == Contour::LINE + || i->type == Contour::CLOSE) + { + glVertex2d(i->p1.x, i->p1.y); + glVertex2d(-1.0, i->p1.y); + prev.x = -1.0; + prev.y = i->p1.y; + } else { + glVertex2d(prev.x, prev.y); + glVertex2d(prev.x, prev.y); + glVertex2d(i->p1.x, i->p1.y); + glVertex2d(i->p1.x, i->p1.y); + prev = i->p1; + } + } + glEnd(); + } + + template + static void draw_contour(const T &c, bool even_odd, bool invert) { + glPushAttrib(GL_ALL_ATTRIB_BITS); + glEnable(GL_STENCIL_TEST); + + // render mask + glClear(GL_STENCIL_BUFFER_BIT); + glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE); + glStencilFunc(GL_ALWAYS, 0, 0); + if (even_odd) { + glStencilOp(GL_KEEP, GL_KEEP, GL_INCR_WRAP); + } else { + glStencilOpSeparate(GL_FRONT, GL_INCR_WRAP, GL_INCR_WRAP, GL_INCR_WRAP); + glStencilOpSeparate(GL_BACK, GL_DECR_WRAP, GL_DECR_WRAP, GL_DECR_WRAP); + } + draw_contour_strip(c); + + // fill mask + glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE); + glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP); + if (!even_odd && !invert) + glStencilFunc(GL_NOTEQUAL, 0, -1); + if (!even_odd && invert) + glStencilFunc(GL_EQUAL, 0, -1); + if ( even_odd && !invert) + glStencilFunc(GL_EQUAL, 1, 1); + if ( even_odd && invert) + glStencilFunc(GL_EQUAL, 0, 1); + + glBegin(GL_TRIANGLE_STRIP); + glVertex2d(-1.0, -1.0); + glVertex2d( 1.0, -1.0); + glVertex2d(-1.0, 1.0); + glVertex2d( 1.0, 1.0); + glEnd(); + + glPopAttrib(); + } +}; + +Test::Wrapper::~Wrapper() { + if (!surface) glFinish(); + Real ms = 1000.0*(Real)(clock() - t)/(Real)(CLOCKS_PER_SEC); + cout << ms << " ms - " << filename << endl; + + if (filename.size() > 4 && filename.substr(filename.size()-4, 4) == ".tga") { + if (surface) + Helper::save_surface(*surface, filename); + else + Helper::save_viewport(filename); + } + + if (surface) { + surface->clear(); + } else { + glClear(GL_COLOR_BUFFER_BIT); + glFinish(); + } +} + +void Test::test1() { + vector c; + ContourBuilder::build_simple(c); + cout << c.size() << " vertices" << endl; + + glPushAttrib(GL_ALL_ATTRIB_BITS); + glColor4d(0.0, 0.0, 1.0, 1.0); + + { + Wrapper t("test_1_contour.tga"); + glBegin(GL_LINE_STRIP); + for(vector::const_iterator i = c.begin(); i != c.end(); ++i) + glVertex2d(i->x, i->y); + glEnd(); + } + + { + Wrapper t("test_1_contour_fill.tga"); + Helper::draw_contour(c, false, false); + } + + { + Wrapper t("test_1_contour_fill_invert.tga"); + Helper::draw_contour(c, false, true); + } + + { + Wrapper t("test_1_contour_evenodd.tga"); + Helper::draw_contour(c, true, false); + } + + { + Wrapper t("test_1_contour_evenodd_invert.tga"); + Helper::draw_contour(c, true, true); + } + + glPopAttrib(); +} + +void Test::test2() { + Contour c, cc; + ContourBuilder::build(cc); + cout << cc.get_chunks().size() << " commands" << endl; + + Rect bounds; + bounds.p0 = Vector(-1.0, -1.0); + bounds.p1 = Vector( 1.0, 1.0); + Vector min_size(1.0/1024.0, 1.0/1024.0); + + { + Wrapper("test_2_split"); + cc.split(c, bounds, min_size); + } + + const Contour::ChunkList &chunks = c.get_chunks(); + cout << chunks.size() << " vertices" << endl; + + glPushAttrib(GL_ALL_ATTRIB_BITS); + glColor4d(0.0, 0.0, 1.0, 1.0); + + { + Wrapper t("test_2_contour.tga"); + glBegin(GL_LINE_STRIP); + for(Contour::ChunkList::const_iterator i = chunks.begin(); i != chunks.end(); ++i) + glVertex2d(i->p1.x, i->p1.y); + glEnd(); + } + + { + Wrapper t("test_2_contour_fill.tga"); + Helper::draw_contour(c, false, false); + } + + { + Wrapper t("test_2_contour_fill_invert.tga"); + Helper::draw_contour(c, false, true); + } + + { + Wrapper t("test_2_contour_evenodd.tga"); + Helper::draw_contour(c, true, false); + } + + { + Wrapper t("test_2_contour_evenodd_invert.tga"); + Helper::draw_contour(c, true, true); + } + + glPopAttrib(); +} + +void Test::test3() { + Contour c; + ContourBuilder::build(c); + cout << c.get_chunks().size() << " commands" << endl; + + Rect bounds; + bounds.p0 = Vector(-1.0, -1.0); + bounds.p1 = Vector( 1.0, 1.0); + Rect pixel_bounds; + pixel_bounds.p0 = Vector( 0.0, 0.0); + pixel_bounds.p1 = Vector(1024.0, 1024.0); + + c.transform(bounds, pixel_bounds); + + Polyspan polyspan; + polyspan.init(0, 0, 1024, 1024); + + Surface surface(1024, 1024); + Color color(0.f, 0.f, 1.f, 1.f); + + { + Wrapper("test_3_build_polyspan"); + c.to_polyspan(polyspan); + } + + cout << polyspan.get_covers().size() << " covers" << endl; + + glPushAttrib(GL_ALL_ATTRIB_BITS); + glColor4d(0.0, 0.0, 1.0, 1.0); + { + Wrapper t("test_3_polyspan_gl_lines.tga"); + glBegin(GL_LINE_STRIP); + for(Polyspan::cover_array::const_iterator i = polyspan.get_covers().begin(); i != polyspan.get_covers().end(); ++i) + glVertex2d((double)i->x/1024.0*2.0 - 1.0, (double)i->y/1024.0*2.0 - 1.0); + glEnd(); + } + glPopAttrib(); + + + { + Wrapper("test_3_polyspan_sort"); + polyspan.sort_marks(); + } + + { + Wrapper t("test_3_polyspan_fill.tga", surface); + RenderSW::polyspan(surface, polyspan, color, false, false); + } + + { + Wrapper t("test_3_polyspan_fill_invert.tga", surface); + RenderSW::polyspan(surface, polyspan, color, false, true); + } + + { + Wrapper t("test_3_polyspan_evenodd.tga", surface); + RenderSW::polyspan(surface, polyspan, color, true, false); + } + + { + Wrapper t("test_3_polyspan_evenodd_invert.tga", surface); + RenderSW::polyspan(surface, polyspan, color, true, true); + } +} + diff --git a/c++/contourgl/test.h b/c++/contourgl/test.h new file mode 100644 index 0000000..dd0066a --- /dev/null +++ b/c++/contourgl/test.h @@ -0,0 +1,51 @@ +/* + ......... 2015 Ivan Mahonin + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + +#ifndef _TEST_H_ +#define _TEST_H_ + +#include +#include + +class Surface; + +class Test { +public: + class Wrapper { + private: + std::string filename; + Surface *surface; + clock_t t; + + Wrapper(const Wrapper&): surface(), t() { } + Wrapper& operator= (const Wrapper&) { return *this; } + public: + Wrapper(const std::string &filename): filename(filename), surface(), t(clock()) { } + Wrapper(const std::string &filename, Surface &surface): filename(filename), surface(&surface), t(clock()) { } + ~Wrapper(); + }; + +private: + class Helper; + +public: + static void test1(); + static void test2(); + static void test3(); +}; + +#endif diff --git a/c++/contourgl/vector.h b/c++/contourgl/vector.h deleted file mode 100644 index ce674a4..0000000 --- a/c++/contourgl/vector.h +++ /dev/null @@ -1,258 +0,0 @@ -/* - ......... 2015 Ivan Mahonin - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program. If not, see . -*/ - -#ifndef _VECTOR_H_ -#define _VECTOR_H_ - -#include - -class Vector { -public: - typedef float float; - -private: - float _x, _y; - -public: - Vector(): _x(0.0), _y(0.0) { }; - Vector(const float &x, const float &y):_x(x),_y(y) { }; - Vector(const float &radius, const Angle &angle): - _x(radius*Angle::cos(angle).get()), - _y(radius*Angle::sin(angle).get()) - { }; - - bool is_valid()const { return !(isnan(_x) || isnan(_y)); } - bool is_nan_or_inf()const { return isnan(_x) || isnan(_y) || isinf(_x) || isinf(_y); } - - float & - operator[](const int& i) - { return i?_y:_x; } - - const float & - operator[](const int& i) const - { return i?_y:_x; } - - const Vector & - operator+=(const Vector &rhs) - { - _x+=rhs._x; - _y+=rhs._y; - return *this; - } - - const Vector & - operator-=(const Vector &rhs) - { - _x-=rhs._x; - _y-=rhs._y; - return *this; - } - - const Vector & - operator*=(const float &rhs) - { - _x*=rhs; - _y*=rhs; - return *this; - } - - const Vector & - operator/=(const float &rhs) - { - float tmp=1.0/rhs; - _x*=tmp; - _y*=tmp; - return *this; - } - - Vector - operator+(const Vector &rhs)const - { return Vector(*this)+=rhs; } - - Vector - operator-(const Vector &rhs)const - { return Vector(*this)-=rhs; } - - Vector - operator*(const float &rhs)const - { return Vector(*this)*=rhs; } - - Vector - operator/(const float &rhs)const - { return Vector(*this)/=rhs; } - - Vector - operator-()const - { return Vector(-_x,-_y); } - - float - operator*(const Vector &rhs)const - { return _x*rhs._x+_y*rhs._y; } - - bool - operator==(const Vector &rhs)const - { return _x==rhs._x && _y==rhs._y; } - - bool - operator!=(const Vector &rhs)const - { return _y!=rhs._y || _x!=rhs._x; } - - //! Returns the squared magnitude of the vector - float mag_squared()const - { return _x*_x+_y*_y; } - - //! Returns the magnitude of the vector - float mag()const - { return sqrt(mag_squared()); } - - //! Returns the reciprocal of the magnitude of the vector - float inv_mag()const - { return 1.0/sqrt(mag_squared()); } - - //! Returns a normalized version of the vector - Vector norm()const - { return (*this)*inv_mag(); } - - //! Returns a perpendicular version of the vector - Vector perp()const - { return Vector(_y,-_x); } - - Angle angle()const - { return Angle::rad(atan2(_y, _x)); } - - bool is_equal_to(const Vector& rhs)const - { - static const float epsilon(0.0000000000001); -// return (_x>rhs._x)?_x-rhs._x<=epsilon:rhs._x-_x<=epsilon && (_y>rhs._y)?_y-rhs._y<=epsilon:rhs._y-_y<=epsilon; - return (*this-rhs).mag_squared()<=epsilon; - } - - static const Vector zero() { return Vector(0,0); } - - Vector multiply_coords(const Vector &rhs) const - { return Vector(_x*rhs._x, _y*rhs._y); } - Vector divide_coords(const Vector &rhs) const - { return Vector(_x/rhs._x, _y/rhs._y); } - Vector one_divide_coords() const - { return Vector(1.0/_x, 1.0/_y); } - Vector rotate(const Angle &rhs) const - { - float s = Angle::sin(rhs).get(); - float c = Angle::cos(rhs).get(); - return Vector(c*_x - s*_y, s*_x + c*_y); - } -}; - -/*! \typedef Point -** \todo writeme -*/ -typedef Vector Point; - - - -}; // END of namespace synfig - -namespace std { - -inline synfig::Vector::float -abs(const synfig::Vector &rhs) - { return rhs.mag(); } - -}; // END of namespace std - -#include - -_ETL_BEGIN_NAMESPACE - -template <> -class bezier_base : public std::unary_function -{ -public: - typedef synfig::Vector float; - typedef float time_type; -private: - - bezier_base bezier_x,bezier_y; - - float a,b,c,d; - -protected: - affine_combo affine_func; - -public: - bezier_base() { } - bezier_base( - const float &a, const float &b, const float &c, const float &d, - const time_type &r=0.0, const time_type &s=1.0): - a(a),b(b),c(c),d(d) { set_rs(r,s); sync(); } - - void sync() - { - bezier_x[0]=a[0],bezier_y[0]=a[1]; - bezier_x[1]=b[0],bezier_y[1]=b[1]; - bezier_x[2]=c[0],bezier_y[2]=c[1]; - bezier_x[3]=d[0],bezier_y[3]=d[1]; - bezier_x.sync(); - bezier_y.sync(); - } - - float - operator()(time_type t)const - { - return synfig::Vector(bezier_x(t),bezier_y(t)); - } - - void evaluate(time_type t, float &f, float &df) const - { - t=(t-get_r())/get_dt(); - - const float p1 = affine_func( - affine_func(a,b,t), - affine_func(b,c,t) - ,t); - const float p2 = affine_func( - affine_func(b,c,t), - affine_func(c,d,t) - ,t); - - f = affine_func(p1,p2,t); - df = (p2-p1)*3; - } - - void set_rs(time_type new_r, time_type new_s) { bezier_x.set_rs(new_r,new_s); bezier_y.set_rs(new_r,new_s); } - void set_r(time_type new_r) { bezier_x.set_r(new_r); bezier_y.set_r(new_r); } - void set_s(time_type new_s) { bezier_x.set_s(new_s); bezier_y.set_s(new_s); } - const time_type &get_r()const { return bezier_x.get_r(); } - const time_type &get_s()const { return bezier_x.get_s(); } - time_type get_dt()const { return bezier_x.get_dt(); } - - float & - operator[](int i) - { return (&a)[i]; } - - const float & - operator[](int i) const - { return (&a)[i]; } - - //! Bezier curve intersection function - time_type intersect(const bezier_base &/*x*/, time_type /*near*/=0.0)const - { - return 0; - } -}; - -#endif