From 82ae614496237dff952c44c1847c0a96f83953ee Mon Sep 17 00:00:00 2001 From: Jonathan deWerd Date: Fri, 27 Jun 2014 11:36:59 -0400 Subject: Added infrastructure to visualize inclusion-exclusion, moved trim code into GLUT demo. --- source/blender/editors/curve/GridMesh.cpp | 251 +++++++++-- source/blender/editors/curve/GridMesh.h | 25 +- .../editors/curve/GridMesh_GLUT_debug_tool.cpp | 474 +++++++++++++++++++++ source/blender/editors/curve/GridMesh_demo.cpp | 468 -------------------- 4 files changed, 702 insertions(+), 516 deletions(-) create mode 100644 source/blender/editors/curve/GridMesh_GLUT_debug_tool.cpp delete mode 100644 source/blender/editors/curve/GridMesh_demo.cpp diff --git a/source/blender/editors/curve/GridMesh.cpp b/source/blender/editors/curve/GridMesh.cpp index 808cc58643e..f9bec1052fc 100644 --- a/source/blender/editors/curve/GridMesh.cpp +++ b/source/blender/editors/curve/GridMesh.cpp @@ -9,6 +9,7 @@ #include #include #include +#include #include #include "GridMesh.h" @@ -200,6 +201,14 @@ void GridMesh::vert_add_neighbor(int v1, int v2) { } } +std::pair GridMesh::vert_grid_cell(int vert) { + // vert = 1+4*(y*nx+x) + int ynx_plus_x = (vert-1)/4; + int y = ynx_plus_x/nx; + int x = ynx_plus_x%nx; + return std::make_pair(x,y); +} + #if defined(ENABLE_GLUT_DEMO) void GridMesh::poly_center(int poly, float *cx, float *cy) { int vert = poly; @@ -210,7 +219,7 @@ void GridMesh::poly_center(int poly, float *cx, float *cy) { sum_y += v[vert].y; n += 1; vert = v[vert].next; - } while (vert && vert!=poly); + } while (vert && vert!=poly && vert!=v[poly].first); *cx = sum_x/n; *cy = sum_y/n; } @@ -229,39 +238,42 @@ void GridMesh::poly_draw(int poly, float shrinkby) { } else { color = it->second; } - // Find the center so that we can shrink towards it - float cx,cy; - poly_center(poly, &cx, &cy); - // Draw the polygon - glBegin(GL_LINES); - glColor3ub(color.r, color.g, color.b); - int v1 = poly; - do { - int v2 = v[v1].next; - glVertex2f((1-shrinkby)*v[v1].x+shrinkby*cx, (1-shrinkby)*v[v1].y+shrinkby*cy); - glVertex2f((1-shrinkby)*v[v2].x+shrinkby*cx, (1-shrinkby)*v[v2].y+shrinkby*cy); - v1 = v2; - } while (v1 != poly); - glEnd(); - // Draw the polygon verts - glPointSize(3); - glBegin(GL_POINTS); - glColor3ub(color.r, color.g, color.b); - v1 = poly; - do { - if (v[v1].is_interior) { - glColor3ub(255,255,0); - } else { - glColor3ub(0,0,255); - } - float x=v[v1].x, y=v[v1].y; - float cx, cy; poly_center(v[v1].first, &cx, &cy); - x = (1.0-shrinkby)*x + shrinkby*cx; - y = (1.0-shrinkby)*y + shrinkby*cy; - glVertex2f(x,y); - v1 = v[v1].next; - } while (v1 != poly); - glEnd(); + for (; poly; poly=v[poly].next_poly) { + if (v[poly].next==0) continue; + // Find the center so that we can shrink towards it + float cx,cy; + poly_center(poly, &cx, &cy); + // Draw the polygon + glBegin(GL_LINES); + glColor3ub(color.r, color.g, color.b); + int v1 = poly; + do { + int v2 = v[v1].next; + glVertex2f((1-shrinkby)*v[v1].x+shrinkby*cx, (1-shrinkby)*v[v1].y+shrinkby*cy); + glVertex2f((1-shrinkby)*v[v2].x+shrinkby*cx, (1-shrinkby)*v[v2].y+shrinkby*cy); + v1 = v2; + } while (v1!=poly && v1!=v[v1].first); + glEnd(); + // Draw the polygon verts + glPointSize(3); + glBegin(GL_POINTS); + glColor3ub(color.r, color.g, color.b); + v1 = poly; + do { + if (v[v1].is_interior) { + glColor3ub(255,255,0); + } else { + glColor3ub(0,0,255); + } + float x=v[v1].x, y=v[v1].y; + float cx, cy; poly_center(v[v1].first, &cx, &cy); + x = (1.0-shrinkby)*x + shrinkby*cx; + y = (1.0-shrinkby)*y + shrinkby*cy; + glVertex2f(x,y); + v1 = v[v1].next; + } while (v1!=poly && v1!=v[v1].first); + glEnd(); + } } #endif @@ -470,7 +482,7 @@ int GridMesh::insert_vert_poly_gridmesh(int mpoly) { return verts_added; } -void GridMesh::label_interior_cell(int x, int y, int poly, bool ll, bool *lr, bool*ul) { +void GridMesh::label_interior_cell(int x, int y, bool ll, bool *lr, bool*ul) { int cell = poly_for_cell(x,y); bool interior = ll; bool first_is_interior = interior; @@ -479,7 +491,10 @@ void GridMesh::label_interior_cell(int x, int y, int poly, bool ll, bool *lr, bo v[vert].is_interior = interior; if (v[vert].corner==2&&lr) *lr = interior; if (v[vert].corner==4&&ul) *ul = interior; - if (v[vert].is_intersection) interior = !interior; + if (v[vert].is_intersection) { + interior = !interior; + v[vert].is_entry = interior; // If we were in the interior, this isn't an entry point + } vert = v[vert].next; } while (vert!=cell); if (!interior==first_is_interior&&debug) { @@ -487,15 +502,171 @@ void GridMesh::label_interior_cell(int x, int y, int poly, bool ll, bool *lr, bo } } -void GridMesh::label_interior(int poly) { - bool ll_next_row = point_in_polygon(0, 0, poly); +void GridMesh::trim_to_odd() { + for (int i=0; i trace_origins; + trace_origins.push_back(poly); + while (trace_origins.size()) { + int vert = *trace_origins.rbegin(); trace_origins.pop_back(); + GreinerV2f *vvert = &v[vert]; + // Move until vert = valid starting vertex + bool bail=false; + while (!( (vvert->is_intersection && !vvert->is_entry) + || (!vvert->is_intersection && vvert->is_interior))) { + vvert->is_used = true; + vert = vvert->next; + vvert->next = 0; + vvert->prev = 0; + vvert = &v[vert]; + if (vvert->is_used) { + bail = true; + break; + } + } + if (bail) continue; // No valid starting vertex? Bail! + // Hook up the polygon backbone + if (latest_trace_poly) v[latest_trace_poly].next_poly = vert; + latest_trace_poly = vert; + if (!first_trace_poly) { + first_trace_poly = vert; + if (poly!=vert) { + v[poly].next_poly = vert; + v[poly].next = poly; + v[poly].prev = poly; + } + } + // Now trace out the active boundary, leaving behind + // .is_used=1 + // .first = latest_trace_poly + // .prev/.next connecting the boundary + // and spinning out trace_origins every time we exit poly + while (vert != latest_trace_poly) { + vvert->is_used = 1; + vvert->first = latest_trace_poly; + if (vvert->is_intersection) { + int last = vert; + int escape_island=v[vert].neighbor, reentry_island=0; + trace_origins.push_back(vvert->next); + if (v[escape_island].is_entry) { // next next next along foreign edge + int fvert = v[escape_island].next; + v[last].next = fvert; + v[fvert].prev = last; + while (true) { + v[fvert].is_used = true; + v[fvert].first = latest_trace_poly; + reentry_island = v[fvert].neighbor; + if (reentry_island) { + if (v[reentry_island].first==poly) break; + } + last = fvert; + fvert = v[fvert].next; + // v[last].next = fvert; + // v[fvert].prev = last; + } + vert = v[reentry_island].next; + vvert = &v[vert]; + vvert->prev = fvert; + v[fvert].next = vert; + } else { // prev prev prev along foreign edge + int fvert = v[escape_island].prev; + v[last].next = fvert; + v[fvert].prev = last; + while (true) { + v[fvert].is_used = true; + v[fvert].first = latest_trace_poly; + reentry_island = v[fvert].neighbor; + if (reentry_island) { + if (v[reentry_island].first==poly) break; + } + int next_fvert = v[fvert].prev; + v[last].next = fvert; + v[fvert].prev = last; + last = fvert; + fvert = next_fvert; + } + vert = v[reentry_island].next; + vvert = &v[vert]; + vvert->prev = fvert; + v[fvert].next = vert; + } + } else { // !vvert->is_intersection + vert = vvert->next; + vvert = &v[vert]; + } + } // end while (vert != latest_trace_poly) + } +} + + +void GridMesh::label_interior_freepoly(int poly) { + float x=v[poly].x, y=v[poly].y; + int over_poly = poly_for_cell(x,y); + std::set inside; // The set of polygons we are currently inside + for (int p=over_poly; p; p=v[p].next_poly) { + if (inside.count(p)) { + inside.erase(p); + } else { + inside.insert(p); + } + } + for (int vert=poly; vert; vert=v[vert].next) { + if (v[vert].is_intersection) { + int neighbor = v[vert].neighbor; + if (inside.count(neighbor)) { + v[vert].is_entry = false; + inside.erase(neighbor); + } else { + v[vert].is_entry = true; + inside.insert(neighbor); + } + } + if (v[vert].next==poly) break; + } +} + +// Adds is_interior and is_entry labels as appropriate to all grid +// vertices with odd winding number between all polygons +// {poly1, poly1.next, poly1.next.next, ..., poly2, poly2.next, poly2.next.next, ...} +// and all vertices of said polygons with the same labels with respect to +// each vertex's neighbor. E.G. if grid vert 09 and poly2's vert 27 are neighbors, +// then labeling vert 27 is_entry unambiguously declares that poly2 enters the +// grid square of vert 09 at that point. +void GridMesh::label_interior(int poly1, int poly2) { + // Winding number changes by +-1 on every polygon entry/exit + // BUT that leaves the problem of finding the initial winding number! + // We do it the slow way for the vert at (llx,lly) + int wind=0; + for (int poly=poly1; poly; poly=v[poly].next_poly) { + wind += int(point_in_polygon(llx, lly, poly)); + } + for (int poly=poly2; poly; poly=v[poly].next_poly) { + wind += int(point_in_polygon(llx, lly, poly)); + } + // Now we use the +-1 rule to propagate the inside/outside info everywhere else + bool ll_next_row = wind%2; for (int j=0; j GridMesh::edge_poly_intersections(int e1, int p) { diff --git a/source/blender/editors/curve/GridMesh.h b/source/blender/editors/curve/GridMesh.h index ca7ea3d0c89..25e61e625a1 100644 --- a/source/blender/editors/curve/GridMesh.h +++ b/source/blender/editors/curve/GridMesh.h @@ -22,15 +22,17 @@ struct GreinerV2f { int first, prev, next; // First,prev,next verts in the *same* polygon int next_poly; // First vertex of the *next* polygon float alpha; // If this vertex came from an affine comb, this is the mixing factor - bool is_intersection; // True if this vertex was added at an intersection - bool is_interior; - bool is_trivial; // True if this polygon has four vertices corresponding precisely to its cell bounds + bool is_intersection:1; // True if this vertex was added at an intersection + bool is_interior:1; + bool is_entry:1; + bool is_used:1; char corner; // 1=ll, 2=lr, 3=ur, 4=ul, 0 = none int neighbor; // Corresp. vertex at same {x,y} in different polygon GreinerV2f() : next(0), prev(0), next_poly(0), neighbor(0), first(0), - is_intersection(false), corner(0) {}; + is_intersection(false), is_interior(false), is_entry(false), + is_used(false), corner(0) {}; }; struct IntersectingEdge { @@ -64,6 +66,7 @@ struct GridMesh { int vert_id(GreinerV2f *vert) {return vert?int(vert-v):0;} int vert_neighbor_on_poly(int vert, int poly); void vert_add_neighbor(int vert, int new_neighbor); + std::pair vert_grid_cell(int vert); int poly_for_cell(int x, int y); int poly_for_cell(float x, float y); int poly_first_vert(int anyvert); @@ -74,11 +77,8 @@ struct GridMesh { bool poly_is_cyclic(int poly); void poly_set_cyclic(int poly, bool cyclic); - // Intersection + // Trimming bool point_in_polygon(double x, double y, int poly); - int insert_vert_poly_gridmesh(int poly); // Returns # of vertices inserted. - void label_interior(int poly); - void label_interior_cell(int x, int y, int poly, bool ll, bool *lr, bool*ul); std::vector edge_poly_intersections(int e1, int p); int insert_vert(int poly1left, int poly1right, @@ -90,6 +90,15 @@ struct GridMesh { std::vector> *bottom_edges, std::vector> *left_edges, std::vector> *integer_cells); + // Step 1: insert verts at intersections + int insert_vert_poly_gridmesh(int poly); // Returns # of vertices inserted. + // Step 2: find mutual entry/exit points + void label_interior(int poly1, int poly2); // is_interior for pts with odd winding num + void label_interior_cell(int x, int y, bool ll, bool *lr, bool*ul); + void label_interior_freepoly(int poly); + // Step 3: perform the actual trim + void trim_to_odd(); + void trim_to_odd(int poly); // Trim one grid poly, leaving behind parts w/odd winding# in .next_poly linked list #if defined(ENABLE_GLUT_DEMO) // Draw void poly_center(int poly, float *cx, float *cy); diff --git a/source/blender/editors/curve/GridMesh_GLUT_debug_tool.cpp b/source/blender/editors/curve/GridMesh_GLUT_debug_tool.cpp new file mode 100644 index 00000000000..ae937f382b0 --- /dev/null +++ b/source/blender/editors/curve/GridMesh_GLUT_debug_tool.cpp @@ -0,0 +1,474 @@ +#include +#include +#include +#include +#include + +bool debug = true; +float intersect_check_tol = .001; //Maximum Euclidean dist between intersect pts + +// GLUT coords. Format: (x,y) +// (1,1)(w,1) |-----> +// | +// (1,h)(w,h) v + +// GL coords. Format: (x,y) Specified via gluOrtho2D +// (-1,1) (1,1) ^ +// | +// (-1,-1) (1,-1) |------> + + +/***************************** MATH *****************************/ +#include "GridMesh.h" + +/***************************** DEFAULT SCENE *****************************/ +GridMesh *gm; +bool clip_cyclic = true; // Required for initialization +bool subj_cyclic = true; +std::vector clip_verts = {2.360000,8.648000, 3.176000,5.888000, 0.200000,5.000000, 1.304000,0.416000, 4.208000,2.096000, 8.600000,0.536000, 9.632000,4.736000, 5.960000,5.936000, 6.896000,8.696000}; +std::vector subj0 = {2.816000,4.784000, 5.024000,5.000000, 5.672000,4.808001, 5.720000,4.160000, 5.384000,3.248000, 4.496000,2.840000, 4.832000,2.456000, 5.696000,3.056000, 6.104000,3.896000, 6.104000,5.024000, 5.072000,5.672000}; +std::vector subj1 = {3.992000,3.344000, 5.048000,3.320000, 5.264000,3.896000, 5.120000,4.160000, 4.832000,4.232000, 4.472000,4.256001, 4.160000,4.256001, 3.896000,4.160000}; +std::vector> subj_polys = {subj0,subj1}; +std::vector inout_pts = {}; + +int clip = 0; // Vertex index of the first vertex of the clip polygon +int subj = 0; + +int win_width = 500; +int win_height = 500; + +void glut_coords_2_scene(float gx, float gy, float* sx, float* sy) { + gx /= win_width; + gy /= win_height; + *sx =-1.0*(1-gx) + 11.0*gx; + *sy =11.0*(1-gy) + -1.0*gy; +} + +void init_default_scene() { + // Create the gridmesh + gm = new GridMesh(0,0,10,10,11,11); + // Import the clip polygon into the linked-list datastructure + int last = 0; + size_t clip_n = clip_verts.size()/2; + for (int i=0; ivert_new(last,0); + if (!clip) clip = v; + gm->v[v].first = clip; + gm->v[v].x = clip_verts[2*i+0]; + gm->v[v].y = clip_verts[2*i+1]; + last = v; + } + if (clip_cyclic) { + gm->v[clip].prev = last; + gm->v[last].next = clip; + } + // Import the subject polygons into the linked list datastructure + GreinerV2f *v = gm->v; + last = 0; + for (std::vector poly_verts : subj_polys) { + // Different subject polygons are stored in + // subj, subj->nextPoly, subj->nextPoly->nextPoly etc + int newpoly_first_vert = gm->vert_new(); + v[newpoly_first_vert].first = newpoly_first_vert; + if (!subj) { + subj = newpoly_first_vert; + } else { + v[last].next_poly = newpoly_first_vert; + } + last = newpoly_first_vert; + // Fill in the vertices of the polygon we just finished hooking up + // to the polygon list + int last_inner = 0; + for (size_t i=0,l=poly_verts.size()/2; ivert_new(); + } + v[vert].x = poly_verts[2*i+0]; + v[vert].y = poly_verts[2*i+1]; + v[vert].prev = last_inner; + v[vert].first = last; + if (last_inner) v[last_inner].next = vert; + last_inner = vert; + } + gm->poly_set_cyclic(newpoly_first_vert, subj_cyclic); + } +} + +void GLUT_init(){ + glClearColor(0,0,0,0); + glMatrixMode(GL_PROJECTION); + // Defines the view box + // left,right,bottom,top + gluOrtho2D(-1,11,-1,11); + init_default_scene(); +} + + +/***************************** DRAW *****************************/ +void GLUT_display(){ + float contraction = .04; // Move polygon edges and verts closer to their center + GreinerV2f *v = gm->v; + glClear(GL_COLOR_BUFFER_BIT); + // Draw Clip polygon lines + glLineWidth(1); + glBegin(GL_LINES); + glColor3f(.8,0,0); + float last_x=v[clip].x, last_y=v[clip].y; + for (int vert=v[clip].next; vert; vert=v[vert].next) { + float x=v[vert].x, y=v[vert].y; + if (v[vert].is_intersection) { + float cx, cy; + gm->poly_center(v[v[vert].neighbor].first, &cx, &cy); + x = (1.0-contraction)*x + contraction*cx; + y = (1.0-contraction)*y + contraction*cy; + } + glVertex2f(last_x,last_y); + glVertex2f(x,y); + last_x=x; last_y=y; + if (vert==clip) break; + } + glEnd(); + + //Draw Clip polygon verts + glPointSize(5); + glBegin(GL_POINTS); + glColor3f(1,0,0); + bool first_iter = true; + for (int vert=clip; vert; vert=v[vert].next) { + float x=v[vert].x, y=v[vert].y; + if (v[vert].is_intersection) { + float cx, cy; + gm->poly_center(v[v[vert].neighbor].first, &cx, &cy); + x = (1.0-contraction)*x + contraction*cx; + y = (1.0-contraction)*y + contraction*cy; + } + glVertex2f(x,y); + if (!first_iter && vert==clip) break; + first_iter = false; + } + glEnd(); + + // Draw Subject polygon lines + glBegin(GL_LINES); + for (int curpoly=subj; curpoly; curpoly=v[curpoly].next_poly) { + last_x=v[curpoly].x, last_y=v[curpoly].y; + for (int vert=v[curpoly].next; vert; vert=v[vert].next) { + float x=v[vert].x, y=v[vert].y; + glColor3f(0,.8,0); + glVertex2f(last_x,last_y); + glVertex2f(x,y); + last_x=x; last_y=y; + if (vert==curpoly) break; + } + } + glEnd(); + + // Draw Subject polygon verts + glPointSize(3); + glBegin(GL_POINTS); + glColor3f(0,1,0); + for (int curpoly=subj; curpoly; curpoly=v[curpoly].next_poly) { + last_x=v[curpoly].x, last_y=v[curpoly].y; + for (int vert=v[curpoly].next; vert; vert=v[vert].next) { + float x=v[vert].x, y=v[vert].y; + glColor3f(0,.8,0); + glVertex2f(x,y); + last_x=x; last_y=y; + if (vert==curpoly) break; + } + } + glEnd(); + + // Draw Grid polygon lines & verts + for (int i=0; inx; i++) { + for (int j=0; jny; j++) { + gm->poly_draw(gm->poly_for_cell(i,j), contraction); + } + } + + // Draw inclusion/exclusion test points + if (clip_cyclic) { + glPointSize(5); + glBegin(GL_POINTS); + for (size_t i=0,l=inout_pts.size()/2; ipoint_in_polygon(x,y,clip); + if (pip) glColor3f(1,1,0); + else glColor3f(0, 0, 1); + glVertex2f(x,y); + } + glEnd(); + } + + // Vestigal grid variables + float xo = 1*(12.0/win_width); + float yo = 1*(12.0/win_height); + xo=0; yo=0; + + //Draw purple grid boxes on cells intersected by subj's first line segment + glColor3f(.5, 0, .5); + std::vector> bottom_edges, left_edges, integer_cells; + gm->find_cell_line_intersections(v[clip].x, v[clip].y, + v[v[clip].next].x, v[v[clip].next].y, + &bottom_edges, &left_edges, &integer_cells); + glPointSize(10); + glBegin(GL_POINTS); + for (std::pair xy : integer_cells) { + float x=gm->llx + xy.first*gm->dx; + float y=gm->lly + xy.second*gm->dy; + glVertex2f(x+0.5*gm->dx, y+0.5*gm->dy); + } + glEnd(); + + //Draw magenta lines on cell edges intersected by subj's first line segment + glLineWidth(2); + glBegin(GL_LINES); + glColor3f(1, 0, 0); + xo=0; yo=0; + for (std::pair xy : bottom_edges) { + float x=gm->llx + xy.first*gm->dx; + float y=gm->lly + xy.second*gm->dy; + glVertex2f(x+xo,y+yo); glVertex2f(x+gm->dx-xo,y+yo); + } + for (std::pair xy : left_edges) { + float x=gm->llx + xy.first*gm->dx; + float y=gm->lly + xy.second*gm->dy; + glVertex2f(x+xo,y+gm->dy-yo); glVertex2f(x+xo,y+yo); + } + glEnd(); + + + glFlush(); +} + +/***************************** INTERACTION *****************************/ +int grabbed_vert = 0; + +void GLUT_reshape(int w, int h){ + glViewport(0,0,w,h); + win_width = w; + win_height = h; + if (debug){ + printf("GLUT_reshape w:%d h:%d\n",w,h); + } +} +void dump_polys_to_stdout() { + GreinerV2f *v = gm->v; + printf("bool clip_cyclic = %s; // Required for initialization\n",clip_cyclic?"true":"false"); + printf("bool subj_cyclic = %s;\n",subj_cyclic?"true":"false"); + printf("std::vector clip_verts = {"); + for (int vert=clip; vert; vert=v[vert].next) { + printf((v[vert].next&&v[vert].next!=clip)?"%f,%f, ":"%f,%f};\n",v[vert].x,v[vert].y); + if (v[vert].next==clip) break; + } + int subj_poly_num = 0; + for (int subj_poly=subj; subj_poly; subj_poly=v[subj_poly].next_poly) { + printf("std::vector subj%i = {", subj_poly_num); + for (int vert=subj_poly; vert; vert=v[vert].next) { + bool is_last_vert = !v[vert].next || v[vert].next==subj_poly; + printf((!is_last_vert)?"%f,%f, ":"%f,%f};\n",v[vert].x,v[vert].y); + if (is_last_vert) break; + } + subj_poly_num++; + } + printf("std::vector> subj_polys = {"); + for (int i=0; i inout_pts = {"); + for (size_t i=0,l=inout_pts.size()/2; ipoly_is_cyclic(curve); + gm->poly_set_cyclic(curve, !iscyc); + glutPostRedisplay(); +} +void delete_last_selected_vert() { + // Don't allow #subj verts or #clip verts -> 0 + if (!grabbed_vert || grabbed_vert==clip) return; + int next = gm->v[grabbed_vert].next; + int prev = gm->v[grabbed_vert].next; + gm->v[prev].next = next; + gm->v[next].prev = prev; + glutPostRedisplay(); +} +#define GLUT_KEY_ESC 27 +#define GLUT_KEY_RETURN 13 +#define GLUT_KEY_DELETE 127 +void GLUT_keyboard(unsigned char ch, int x, int y ) { + int m = glutGetModifiers(); + if (debug) { + char m_str[128]; m_str[0]=0; + if (m&GLUT_ACTIVE_ALT) strcpy(m_str+strlen(m_str),"ALT,"); + if (m&GLUT_ACTIVE_SHIFT) strcpy(m_str+strlen(m_str),"SHIFT,"); + if (m&GLUT_ACTIVE_CTRL) strcpy(m_str+strlen(m_str),"CTRL,"); + printf("GLUT_keyboard x:%d y:%d ch:%i mod:%x(%s)\n",x,y,(int)ch,m,m_str); + } + if (ch==GLUT_KEY_ESC) { + init_default_scene(); + glutPostRedisplay(); + } + if (ch==GLUT_KEY_RETURN) { + dump_polys_to_stdout(); + } + if (ch=='i') { + gm->insert_vert_poly_gridmesh(clip); + for (int poly=subj; poly; poly=gm->v[poly].next_poly) { + gm->insert_vert_poly_gridmesh(poly); + } + glutPostRedisplay(); + } + if (ch=='l') { + gm->label_interior(clip,subj); + glutPostRedisplay(); + } + if (ch=='t') { + gm->trim_to_odd(); + subj = 0; // Subject and clip were destroyed in trimming process + clip = 0; + glutPostRedisplay(); + } + if (ch=='1') toggle_cyclic(clip); + if (ch==GLUT_KEY_DELETE) delete_last_selected_vert(); +} +void GLUT_specialkey(int ch, int x, int y) { + // CTRL, SHIFT, arrows actually work + // alt/option, command do not + if (debug) { + const char* ch_str = "???"; + if (ch==GLUT_KEY_LEFT) ch_str = "GLUT_KEY_LEFT"; + if (ch==GLUT_KEY_RIGHT) ch_str = "GLUT_KEY_RIGHT"; + if (ch==GLUT_KEY_UP) ch_str = "GLUT_KEY_UP"; + if (ch==GLUT_KEY_DOWN) ch_str = "GLUT_KEY_DOWN"; + printf("GLUT_specialkey x:%d y:%d ch:%x(%s)\n",x,y,ch,ch_str); + } +} +void create_new_poly(float sx, float sy) { + GreinerV2f *v = gm->v; + int last_backbone = subj; + while (v[last_backbone].next_poly) last_backbone = v[last_backbone].next_poly; + int newpoly = gm->vert_new(); + v[newpoly].x = sx; v[newpoly].y = sy; + v[last_backbone].next_poly = newpoly; + glutPostRedisplay(); +} +void create_pt(float sx, float sy) { + if (!grabbed_vert) return; + int last_vert = gm->poly_last_vert(grabbed_vert); + int v = gm->vert_new(last_vert, gm->v[last_vert].next); + gm->v[v].x = sx; + gm->v[v].y = sy; + grabbed_vert = v; // Let's drag the new vert we just made + glutPostRedisplay(); +} +void initiate_pt_drag_if_near_pt(float sx, float sy) { + GreinerV2f *v = gm->v; // Vertex info array + float closest_dist = 1e50; + int closest_vert = 0; + for (int vert=clip; vert; vert=v[vert].next) { + float dx = v[vert].x - sx; + float dy = v[vert].y - sy; + float dist = sqrt(dx*dx + dy*dy); + if (distv[grabbed_vert].x = sx; + gm->v[grabbed_vert].y = sy; + glutPostRedisplay(); + } +} + + +/***************************** MAIN *****************************/ +int main(int argc, char **argv){ + glutInit(& argc, argv); + glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB); + glutInitWindowSize(win_width,win_height); + glutInitWindowPosition(200,200); + glutCreateWindow("Polygon Split Viz"); + glutDisplayFunc(GLUT_display); + glutReshapeFunc(GLUT_reshape); + glutMouseFunc(GLUT_mouse); + glutMotionFunc(GLUT_motion); // Mouse is dragged. Callback args: (int x, int y) + glutPassiveMotionFunc(NULL); // Mouse is moved. Callback args: (int x, int y) + glutKeyboardFunc(GLUT_keyboard); + glutSpecialFunc(GLUT_specialkey); + GLUT_init(); + puts("Welcome to the polygon demo! This was designed to be a convenient "); + puts("sandbox for testing polygon trim code designed as a part of blender's "); + puts(" new NURBS functionality."); + puts("------ Instructions: ------"); + puts(": move polyline/polygon vertices around"); + puts("+: new vertex on last touched polyline"); + puts(": dump vertices in format suitable for copypaste into code"); + puts(": reset to default 'scene'"); + puts("i: insert vertices at points of intersection between the two polylines/gons"); + puts("1: toggle clip (red) polyline<->polygon"); + puts("2: toggle subj (green) polyline<->polygon"); + puts("---------------------------"); + glutMainLoop(); + return 0; +} \ No newline at end of file diff --git a/source/blender/editors/curve/GridMesh_demo.cpp b/source/blender/editors/curve/GridMesh_demo.cpp deleted file mode 100644 index 27501393ec0..00000000000 --- a/source/blender/editors/curve/GridMesh_demo.cpp +++ /dev/null @@ -1,468 +0,0 @@ -#include -#include -#include -#include -#include - -bool debug = true; -float intersect_check_tol = .001; //Maximum Euclidean dist between intersect pts - -// GLUT coords. Format: (x,y) -// (1,1)(w,1) |-----> -// | -// (1,h)(w,h) v - -// GL coords. Format: (x,y) Specified via gluOrtho2D -// (-1,1) (1,1) ^ -// | -// (-1,-1) (1,-1) |------> - - -/***************************** MATH *****************************/ -#include "GridMesh.h" - -/***************************** DEFAULT SCENE *****************************/ -GridMesh *gm; -bool clip_cyclic = true; // Required for initialization -bool subj_cyclic = true; -std::vector clip_verts = {2.360000,8.648000, 3.176000,5.888000, 0.200000,5.000000, 1.304000,0.416000, 4.208000,2.096000, 8.600000,0.536000, 9.632000,4.736000, 5.960000,5.936000, 6.896000,8.696000}; -std::vector subj0 = {2.816000,4.784000, 5.024000,5.000000, 5.672000,4.808001, 5.720000,4.160000, 5.384000,3.248000, 4.496000,2.840000, 4.832000,2.456000, 5.696000,3.056000, 6.104000,3.896000, 6.104000,5.024000, 5.072000,5.672000}; -std::vector subj1 = {3.992000,3.344000, 5.048000,3.320000, 5.264000,3.896000, 5.120000,4.160000, 4.832000,4.232000, 4.472000,4.256001, 4.160000,4.256001, 3.896000,4.160000}; -std::vector> subj_polys = {subj0,subj1}; -std::vector inout_pts = {}; - -int clip = 0; // Vertex index of the first vertex of the clip polygon -int subj = 0; - -int win_width = 500; -int win_height = 500; - -void glut_coords_2_scene(float gx, float gy, float* sx, float* sy) { - gx /= win_width; - gy /= win_height; - *sx =-1.0*(1-gx) + 11.0*gx; - *sy =11.0*(1-gy) + -1.0*gy; -} - -void init_default_scene() { - // Create the gridmesh - gm = new GridMesh(0,0,10,10,11,11); - // Import the clip polygon into the linked-list datastructure - int last = 0; - size_t clip_n = clip_verts.size()/2; - for (int i=0; ivert_new(last,0); - if (!clip) clip = v; - gm->v[v].first = clip; - gm->v[v].x = clip_verts[2*i+0]; - gm->v[v].y = clip_verts[2*i+1]; - last = v; - } - if (clip_cyclic) { - gm->v[clip].prev = last; - gm->v[last].next = clip; - } - // Import the subject polygons into the linked list datastructure - GreinerV2f *v = gm->v; - last = 0; - for (std::vector poly_verts : subj_polys) { - // Different subject polygons are stored in - // subj, subj->nextPoly, subj->nextPoly->nextPoly etc - int newpoly_first_vert = gm->vert_new(); - v[newpoly_first_vert].first = newpoly_first_vert; - if (!subj) { - subj = newpoly_first_vert; - } else { - v[last].next_poly = newpoly_first_vert; - } - last = newpoly_first_vert; - // Fill in the vertices of the polygon we just finished hooking up - // to the polygon list - int last_inner = 0; - for (size_t i=0,l=poly_verts.size()/2; ivert_new(); - } - v[vert].x = poly_verts[2*i+0]; - v[vert].y = poly_verts[2*i+1]; - v[vert].prev = last_inner; - v[vert].first = last; - if (last_inner) v[last_inner].next = vert; - last_inner = vert; - } - gm->poly_set_cyclic(newpoly_first_vert, subj_cyclic); - } -} - -void GLUT_init(){ - glClearColor(0,0,0,0); - glMatrixMode(GL_PROJECTION); - // Defines the view box - // left,right,bottom,top - gluOrtho2D(-1,11,-1,11); - init_default_scene(); -} - - -/***************************** DRAW *****************************/ -void GLUT_display(){ - float contraction = .04; // Move polygon edges and verts closer to their center - GreinerV2f *v = gm->v; - glClear(GL_COLOR_BUFFER_BIT); - // Draw Clip polygon lines - glLineWidth(1); - glBegin(GL_LINES); - glColor3f(.8,0,0); - float last_x=v[clip].x, last_y=v[clip].y; - for (int vert=v[clip].next; vert; vert=v[vert].next) { - float x=v[vert].x, y=v[vert].y; - if (v[vert].is_intersection) { - float cx, cy; - gm->poly_center(v[v[vert].neighbor].first, &cx, &cy); - x = (1.0-contraction)*x + contraction*cx; - y = (1.0-contraction)*y + contraction*cy; - } - glVertex2f(last_x,last_y); - glVertex2f(x,y); - last_x=x; last_y=y; - if (vert==clip) break; - } - glEnd(); - - //Draw Clip polygon verts - glPointSize(5); - glBegin(GL_POINTS); - glColor3f(1,0,0); - bool first_iter = true; - for (int vert=clip; vert; vert=v[vert].next) { - float x=v[vert].x, y=v[vert].y; - if (v[vert].is_intersection) { - float cx, cy; - gm->poly_center(v[v[vert].neighbor].first, &cx, &cy); - x = (1.0-contraction)*x + contraction*cx; - y = (1.0-contraction)*y + contraction*cy; - } - glVertex2f(x,y); - if (!first_iter && vert==clip) break; - first_iter = false; - } - glEnd(); - - // Draw Subject polygon lines - glBegin(GL_LINES); - for (int curpoly=subj; curpoly; curpoly=v[curpoly].next_poly) { - last_x=v[curpoly].x, last_y=v[curpoly].y; - for (int vert=v[curpoly].next; vert; vert=v[vert].next) { - float x=v[vert].x, y=v[vert].y; - glColor3f(0,.8,0); - glVertex2f(last_x,last_y); - glVertex2f(x,y); - last_x=x; last_y=y; - if (vert==curpoly) break; - } - } - glEnd(); - - // Draw Subject polygon verts - glPointSize(3); - glBegin(GL_POINTS); - glColor3f(0,1,0); - for (int curpoly=subj; curpoly; curpoly=v[curpoly].next_poly) { - last_x=v[curpoly].x, last_y=v[curpoly].y; - for (int vert=v[curpoly].next; vert; vert=v[vert].next) { - float x=v[vert].x, y=v[vert].y; - glColor3f(0,.8,0); - glVertex2f(x,y); - last_x=x; last_y=y; - if (vert==curpoly) break; - } - } - glEnd(); - - // Draw Grid polygon lines & verts - for (int i=0; inx; i++) { - for (int j=0; jny; j++) { - gm->poly_draw(gm->poly_for_cell(i,j), contraction); - } - } - - // Draw inclusion/exclusion test points - if (clip_cyclic) { - glPointSize(5); - glBegin(GL_POINTS); - for (size_t i=0,l=inout_pts.size()/2; ipoint_in_polygon(x,y,clip); - if (pip) glColor3f(1,1,0); - else glColor3f(0, 0, 1); - glVertex2f(x,y); - } - glEnd(); - } - - // Vestigal grid variables - float xo = 1*(12.0/win_width); - float yo = 1*(12.0/win_height); - xo=0; yo=0; - - //Draw purple grid boxes on cells intersected by subj's first line segment - glColor3f(.5, 0, .5); - std::vector> bottom_edges, left_edges, integer_cells; - gm->find_cell_line_intersections(v[clip].x, v[clip].y, - v[v[clip].next].x, v[v[clip].next].y, - &bottom_edges, &left_edges, &integer_cells); - glPointSize(10); - glBegin(GL_POINTS); - for (std::pair xy : integer_cells) { - float x=gm->llx + xy.first*gm->dx; - float y=gm->lly + xy.second*gm->dy; - glVertex2f(x+0.5*gm->dx, y+0.5*gm->dy); - } - glEnd(); - - //Draw magenta lines on cell edges intersected by subj's first line segment - glLineWidth(2); - glBegin(GL_LINES); - glColor3f(1, 0, 0); - xo=0; yo=0; - for (std::pair xy : bottom_edges) { - float x=gm->llx + xy.first*gm->dx; - float y=gm->lly + xy.second*gm->dy; - glVertex2f(x+xo,y+yo); glVertex2f(x+gm->dx-xo,y+yo); - } - for (std::pair xy : left_edges) { - float x=gm->llx + xy.first*gm->dx; - float y=gm->lly + xy.second*gm->dy; - glVertex2f(x+xo,y+gm->dy-yo); glVertex2f(x+xo,y+yo); - } - glEnd(); - - - glFlush(); -} - -/***************************** INTERACTION *****************************/ -int grabbed_vert = 0; - -void GLUT_reshape(int w, int h){ - glViewport(0,0,w,h); - win_width = w; - win_height = h; - if (debug){ - printf("GLUT_reshape w:%d h:%d\n",w,h); - } -} -void dump_polys_to_stdout() { - GreinerV2f *v = gm->v; - printf("bool clip_cyclic = %s; // Required for initialization\n",clip_cyclic?"true":"false"); - printf("bool subj_cyclic = %s;\n",subj_cyclic?"true":"false"); - printf("std::vector clip_verts = {"); - for (int vert=clip; vert; vert=v[vert].next) { - printf((v[vert].next&&v[vert].next!=clip)?"%f,%f, ":"%f,%f};\n",v[vert].x,v[vert].y); - if (v[vert].next==clip) break; - } - int subj_poly_num = 0; - for (int subj_poly=subj; subj_poly; subj_poly=v[subj_poly].next_poly) { - printf("std::vector subj%i = {", subj_poly_num); - for (int vert=subj_poly; vert; vert=v[vert].next) { - bool is_last_vert = !v[vert].next || v[vert].next==subj_poly; - printf((!is_last_vert)?"%f,%f, ":"%f,%f};\n",v[vert].x,v[vert].y); - if (is_last_vert) break; - } - subj_poly_num++; - } - printf("std::vector> subj_polys = {"); - for (int i=0; i inout_pts = {"); - for (size_t i=0,l=inout_pts.size()/2; ipoly_is_cyclic(curve); - gm->poly_set_cyclic(curve, !iscyc); - glutPostRedisplay(); -} -void delete_last_selected_vert() { - // Don't allow #subj verts or #clip verts -> 0 - if (!grabbed_vert || grabbed_vert==clip) return; - int next = gm->v[grabbed_vert].next; - int prev = gm->v[grabbed_vert].next; - gm->v[prev].next = next; - gm->v[next].prev = prev; - glutPostRedisplay(); -} -#define GLUT_KEY_ESC 27 -#define GLUT_KEY_RETURN 13 -#define GLUT_KEY_DELETE 127 -void GLUT_keyboard(unsigned char ch, int x, int y ) { - int m = glutGetModifiers(); - if (debug) { - char m_str[128]; m_str[0]=0; - if (m&GLUT_ACTIVE_ALT) strcpy(m_str+strlen(m_str),"ALT,"); - if (m&GLUT_ACTIVE_SHIFT) strcpy(m_str+strlen(m_str),"SHIFT,"); - if (m&GLUT_ACTIVE_CTRL) strcpy(m_str+strlen(m_str),"CTRL,"); - printf("GLUT_keyboard x:%d y:%d ch:%i mod:%x(%s)\n",x,y,(int)ch,m,m_str); - } - if (ch==GLUT_KEY_ESC) { - init_default_scene(); - glutPostRedisplay(); - } - if (ch==GLUT_KEY_RETURN) { - dump_polys_to_stdout(); - } - if (ch=='i') { - gm->insert_vert_poly_gridmesh(clip); - for (int poly=subj; poly; poly=gm->v[poly].next_poly) { - gm->insert_vert_poly_gridmesh(poly); - } - glutPostRedisplay(); - } - if (ch=='t') { - gm->label_interior(clip); - glutPostRedisplay(); - } - if (ch=='1') toggle_cyclic(clip); - if (ch==GLUT_KEY_DELETE) delete_last_selected_vert(); -} -void GLUT_specialkey(int ch, int x, int y) { - // CTRL, SHIFT, arrows actually work - // alt/option, command do not - if (debug) { - const char* ch_str = "???"; - if (ch==GLUT_KEY_LEFT) ch_str = "GLUT_KEY_LEFT"; - if (ch==GLUT_KEY_RIGHT) ch_str = "GLUT_KEY_RIGHT"; - if (ch==GLUT_KEY_UP) ch_str = "GLUT_KEY_UP"; - if (ch==GLUT_KEY_DOWN) ch_str = "GLUT_KEY_DOWN"; - printf("GLUT_specialkey x:%d y:%d ch:%x(%s)\n",x,y,ch,ch_str); - } -} -void create_new_poly(float sx, float sy) { - GreinerV2f *v = gm->v; - int last_backbone = subj; - while (v[last_backbone].next_poly) last_backbone = v[last_backbone].next_poly; - int newpoly = gm->vert_new(); - v[newpoly].x = sx; v[newpoly].y = sy; - v[last_backbone].next_poly = newpoly; - glutPostRedisplay(); -} -void create_pt(float sx, float sy) { - if (!grabbed_vert) return; - int last_vert = gm->poly_last_vert(grabbed_vert); - int v = gm->vert_new(last_vert, gm->v[last_vert].next); - gm->v[v].x = sx; - gm->v[v].y = sy; - grabbed_vert = v; // Let's drag the new vert we just made - glutPostRedisplay(); -} -void initiate_pt_drag_if_near_pt(float sx, float sy) { - GreinerV2f *v = gm->v; // Vertex info array - float closest_dist = 1e50; - int closest_vert = 0; - for (int vert=clip; vert; vert=v[vert].next) { - float dx = v[vert].x - sx; - float dy = v[vert].y - sy; - float dist = sqrt(dx*dx + dy*dy); - if (distv[grabbed_vert].x = sx; - gm->v[grabbed_vert].y = sy; - glutPostRedisplay(); - } -} - - -/***************************** MAIN *****************************/ -int main(int argc, char **argv){ - glutInit(& argc, argv); - glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB); - glutInitWindowSize(win_width,win_height); - glutInitWindowPosition(200,200); - glutCreateWindow("Polygon Split Viz"); - glutDisplayFunc(GLUT_display); - glutReshapeFunc(GLUT_reshape); - glutMouseFunc(GLUT_mouse); - glutMotionFunc(GLUT_motion); // Mouse is dragged. Callback args: (int x, int y) - glutPassiveMotionFunc(NULL); // Mouse is moved. Callback args: (int x, int y) - glutKeyboardFunc(GLUT_keyboard); - glutSpecialFunc(GLUT_specialkey); - GLUT_init(); - puts("Welcome to the polygon demo! This was designed to be a convenient "); - puts("sandbox for testing polygon trim code designed as a part of blender's "); - puts(" new NURBS functionality."); - puts("------ Instructions: ------"); - puts(": move polyline/polygon vertices around"); - puts("+: new vertex on last touched polyline"); - puts(": dump vertices in format suitable for copypaste into code"); - puts(": reset to default 'scene'"); - puts("i: insert vertices at points of intersection between the two polylines/gons"); - puts("1: toggle clip (red) polyline<->polygon"); - puts("2: toggle subj (green) polyline<->polygon"); - puts("---------------------------"); - glutMainLoop(); - return 0; -} \ No newline at end of file -- cgit v1.2.3