diff --git a/c++/contourgl/geometry.h b/c++/contourgl/geometry.h index b2e018a..825b1c5 100644 --- a/c++/contourgl/geometry.h +++ b/c++/contourgl/geometry.h @@ -86,6 +86,9 @@ public: vec2 operator/(type a) const { return vec2(x/a, y/a); } + type dot(const vec2 &a) const + { return x*a.x + y*a.y; } + static vec2 zero() { return vec2(); } }; diff --git a/c++/contourgl/test.cpp b/c++/contourgl/test.cpp index 54969d9..3ac52f9 100644 --- a/c++/contourgl/test.cpp +++ b/c++/contourgl/test.cpp @@ -31,6 +31,7 @@ #include "rendersw.h" #include "contourbuilder.h" #include "shaders.h" +#include "triangulator.h" using namespace std; @@ -621,6 +622,8 @@ void Test::test4() { commands_count += i->contour.get_chunks().size(); } + // gl_stencil + GLuint buffer_id = 0; GLuint array_id = 0; vector< vec2 > vertices; @@ -653,7 +656,7 @@ void Test::test4() { } { - Wrapper t("test_4_gl_prepare_data"); + Wrapper t("test_4_gl_stencil_prepare_data"); vertices.push_back(vec2(bounds_gl.p0.x, bounds_gl.p0.y)); vertices.push_back(vec2(bounds_gl.p0.x, bounds_gl.p1.y)); vertices.push_back(vec2(bounds_gl.p1.x, bounds_gl.p0.y)); @@ -681,7 +684,7 @@ void Test::test4() { } { - Wrapper t("test_4_gl_send_data"); + Wrapper t("test_4_gl_stencil_send_data"); glBufferSubData( GL_ARRAY_BUFFER, 0, vertices.size()*sizeof(vertices.front()), @@ -689,7 +692,12 @@ void Test::test4() { } { - Wrapper t("test_4_gl_render.tga"); + Wrapper t("test_4_gl_stencil_points.tga"); + glDrawArrays(GL_POINTS, 0, vertices.size()); + } + + { + Wrapper t("test_4_gl_stencil_render.tga"); for(int i = 0; i < (int)contours_gl.size(); ++i) { Helper::draw_contour( starts[i], @@ -700,6 +708,70 @@ void Test::test4() { } // glDrawArrays(GL_POINTS, 0, vertices.size()); } + + // gl_triangles + + GLuint index_buffer_id = 0; + vector triangle_starts(contours_gl.size()); + vector triangle_counts(contours_gl.size()); + vector triangles; + vertices.clear(); + vertices.reserve(commands_count); + + { + Wrapper t("test_4_gl_init_index_buffer"); + triangles.resize(3*commands_count); + glGenBuffers(1, &index_buffer_id); + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, index_buffer_id); + glBufferData( GL_ELEMENT_ARRAY_BUFFER, + triangles.size()*sizeof(triangles.front()), + &triangles.front(), + GL_DYNAMIC_DRAW ); + triangles.clear(); + triangles.reserve(3*commands_count); + } + + { + Wrapper t("test_4_gl_triangulate"); + int index_offset = 4; + for(int i = 0; i < (int)contours_gl.size(); ++i) { + triangle_starts[i] = (int)triangles.size(); + Triangulator::triangulate(contours_gl[i].contour, triangles, index_offset); + triangle_counts[i] = (int)triangles.size() - triangle_starts[i]; + index_offset += (int)contours_gl[i].contour.get_chunks().size(); + } + } + + cout << triangles.size() << " triangles" << endl; + + { + Wrapper t("test_4_gl_triangles_prepare_vertices"); + for(int i = 0; i < (int)contours_gl.size(); ++i) { + const Contour::ChunkList &chunks = contours_gl[i].contour.get_chunks(); + for(Contour::ChunkList::const_iterator j = chunks.begin(); j != chunks.end(); ++j) + vertices.push_back(vec2(j->p1)); + } + } + + { + Wrapper t("test_4_gl_triangles_send_data"); + glBufferSubData( GL_ARRAY_BUFFER, + 4*sizeof(vertices.front()), + vertices.size()*sizeof(vertices.front()), + &vertices.front() ); + glBufferSubData( GL_ELEMENT_ARRAY_BUFFER, + 0, + triangles.size()*sizeof(triangles.front()), + &triangles.front() ); + } + + { + Wrapper t("test_4_gl_triangles_render.tga"); + for(int i = 0; i < (int)contours_gl.size(); ++i) { + Shaders::color(contours_gl[i].color); + glDrawElements(GL_TRIANGLES, triangle_counts[i], GL_UNSIGNED_INT, (char*)NULL + triangle_starts[i]*sizeof(int)); + } + } } { diff --git a/c++/contourgl/triangulator.cpp b/c++/contourgl/triangulator.cpp new file mode 100644 index 0000000..7216451 --- /dev/null +++ b/c++/contourgl/triangulator.cpp @@ -0,0 +1,124 @@ +/* + ......... 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 "triangulator.h" + + +using namespace std; + + +bool Triangulator::intersect_lines(Vector a0, Vector a1, Vector b0, Vector b1) { + static const Real precision = 1e-6; + + Vector da(a1 - a0); + Vector pa(-da.y, da.x); + + Real d0, d1; + + d0 = pa.dot(b0 - a0); + if (fabs(d0) < precision) return false; + d1 = pa.dot(b1 - a0); + if (fabs(d1) < precision) return false; + if ((d0 > 0.0) == (d1 > 0.0)) return false; + + Vector db(b1 - b0); + Vector pb(-db.y, db.x); + + d0 = pa.dot(a0 - b0); + if (fabs(d0) < precision) return false; + d1 = pa.dot(a1 - b0); + if (fabs(d1) < precision) return false; + if ((d0 > 0.0) == (d1 > 0.0)) return false; + + return true; +} + +void Triangulator::build_path(const Contour &contour, Path &path, int index_offset) { + // TODO: connect multiple contours + path.clear(); + path.resize(contour.get_chunks().size()); + for(int i = 0; i < (int)contour.get_chunks().size(); ++i) { + const Contour::Chunk &c = contour.get_chunks()[i]; + Vertex &v = path[i]; + v.index = i + index_offset; + v.p = c.p1; + v.next = &v + 1; + } + path.back().next = &path.front(); +} + +bool Triangulator::check_triangle(Vertex *first, TriangleList &triangles) { + // path is a dot + if (first->next == first) + return true; + + // path is a two lines + if (first->next->next == first) + return true; + + // path is triangle + if (first->next->next->next == first) { + triangles.push_back(first->index); + triangles.push_back(first->next->index); + triangles.push_back(first->next->next->index); + return true; + } + + return false; +} + +void Triangulator::split_path(Vertex *first, TriangleList &triangles) { + if (check_triangle(first, triangles)) + return; + + // split path + Vertex *va0 = first; + for(Vertex *va1 = va0->next; va1 != first; va1 = va1->next) { + if (va0 != va1 && va0->next != va1 && va1->next != va0) { + bool intersects = false; + for(Vertex *vb0 = first->next; vb0->next != first; vb0 = vb0->next) { + Vertex *vb1 = vb0->next; + if ( va0 != vb0 && va0 != vb1 && va1 != vb0 && va1 != vb1 + && intersect_lines(va0->p, va1->p, vb0->p, vb1->p) ) + { intersects = true; break; } + } + if (!intersects) { + Vertex *next = va1->next; + va1->next = va0; + if (!check_triangle(va0, triangles)) + split_path(va0, triangles); + va1->next = next; + va0->next = va1; + if (check_triangle(va0, triangles)) + return; + va1 = va0; + } + } + } + + cout << "bug - path not fully triangulated" << endl; +} + +void Triangulator::triangulate(const Contour &contour, TriangleList &triangles, int index_offset) { + Path path; + build_path(contour, path, index_offset); + triangles.reserve(triangles.size() + 3*(path.size() - 2)); + split_path(&path.front(), triangles); +} + diff --git a/c++/contourgl/triangulator.h b/c++/contourgl/triangulator.h new file mode 100644 index 0000000..94f5283 --- /dev/null +++ b/c++/contourgl/triangulator.h @@ -0,0 +1,46 @@ +/* + ......... 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 _TRIANGULATOR_H_ +#define _TRIANGULATOR_H_ + +#include + +#include "geometry.h" +#include "contour.h" + +class Triangulator { +public: + class Vertex { + public: + int index; + Vector p; + Vertex *next; + Vertex(): index(), next() { } + }; + + typedef std::vector Path; + typedef std::vector TriangleList; + + static bool intersect_lines(Vector a0, Vector a1, Vector b0, Vector b1); + static void build_path(const Contour &contour, Path &path, int index_offset); + static bool check_triangle(Vertex *first, TriangleList &triangles); + static void split_path(Vertex *first, TriangleList &triangles); + static void triangulate(const Contour &contour, TriangleList &triangles, int index_offset); +}; + +#endif