Commit: 99c45cd6d858d7e9475e2564ec8b3f8f1435bda8 Author: Jonathan deWerd Date: Tue Jul 1 23:53:38 2014 -0400 https://developer.blender.org/rB99c45cd6d858d7e9475e2564ec8b3f8f1435bda8
GridMesh can now handle being ANDed with multiple *successive* polygons rather than all-at-once-so-long-as-they-dont-intersect. Also, slow PIP test is avoided when possible by a more general mechanism that can propagate interior/exterior info via any grid vertex. =================================================================== M source/blender/editors/curve/GridMesh.cpp M source/blender/editors/curve/GridMesh.h M source/blender/editors/curve/GridMesh_GLUT_debug_tool.cpp =================================================================== diff --git a/source/blender/editors/curve/GridMesh.cpp b/source/blender/editors/curve/GridMesh.cpp index d200a67..6050b00 100644 --- a/source/blender/editors/curve/GridMesh.cpp +++ b/source/blender/editors/curve/GridMesh.cpp @@ -11,11 +11,30 @@ #include <map> #include <set> #include <algorithm> +#include <limits> #include "GridMesh.h" static bool debug = 1; float GridMesh::tolerance = 1e-5; + +// Fast float->int, courtesy of http://stereopsis.com/sree/fpu2006.html +// 5x faster on x86. It's not in the hot loop anymore so it probably +// doesn't really matter. Todo: test and see. +const double _xs_doublemagic = 6755399441055744.0; //2^52 * 1.5, uses limited precisicion to floor +const double _xs_doublemagicdelta = (1.5e-8); //almost .5f = .5f + 1e^(number of exp bit) +const double _xs_doublemagicroundeps = (.5f-_xs_doublemagicdelta); //almost .5f = .5f - 1e^(number of exp bit) +inline static int xs_CRoundToInt(double val) { + val = val + _xs_doublemagic; + return ((int*)&val)[0]; // 0 for little endian (ok), 1 for big endian (?) + // return int32(floor(val+.5)); //Alternative implementation if the trick is buggy +} +inline static int xs_FloorToInt(double val) { + return xs_CRoundToInt(val-_xs_doublemagicroundeps); + //return floor(val); //Alternative implementation if the trick is buggy +} + + void GridMesh::set_ll_ur(double lowerleft_x, double lowerleft_y, double upperright_x, double upperright_y) { llx = lowerleft_x; lly = lowerleft_y; @@ -54,12 +73,12 @@ GridMesh::GridMesh(double lowerleft_x, double lowerleft_y, new (v4) GreinerV2f(); v4->x=l; v4->y=t; int iv1 = vert_id(v1); int iv2 = iv1+1; - int iv3 = iv1+2; - int iv4 = iv1+3; + int iv3 = iv1+2; // 13 + 1 + int iv4 = iv1+3; // 02 v1->next = iv2; v2->prev = iv1; v1->first = iv1; v1->corner = 1; - v2->next = iv3; v3->prev = iv2; v2->first = iv1; v2->corner = 2; - v3->next = iv4; v4->prev = iv3; v3->first = iv1; v3->corner = 3; - v4->next = iv1; v1->prev = iv4; v4->first = iv1; v4->corner = 4; + v2->next = iv3; v3->prev = iv2; v2->first = iv1; v2->corner = 3; + v3->next = iv4; v4->prev = iv3; v3->first = iv1; v3->corner = 4; + v4->next = iv1; v1->prev = iv4; v4->first = iv1; v4->corner = 2; } } } @@ -209,6 +228,39 @@ std::pair<int,int> GridMesh::vert_grid_cell(int vert) { return std::make_pair(x,y); } +void GridMesh::poly_grid_BB(int poly, int *bb) { //int bb[4] = {minx,maxx,miny,maxy} + int first = poly_first_vert(poly); + int vert = first; + float minx=std::numeric_limits<float>::max(), maxx=std::numeric_limits<float>::min(); + float miny=std::numeric_limits<float>::max(), maxy=std::numeric_limits<float>::min(); + do { + GreinerV2f& g = v[vert]; + minx = fmin(g.x,minx); + maxx = fmax(g.x,maxx); + miny = fmin(g.y,miny); + maxy = fmax(g.y,maxy); + vert = g.next; + } while (vert && vert!=first); + bb[0] = xs_FloorToInt(minx); + bb[1] = xs_FloorToInt(maxx); + bb[2] = xs_FloorToInt(miny); + bb[3] = xs_FloorToInt(maxy); +} + +// Sets is_interior flag of all vertices of poly and all vertices +// of polygons connected to poly's next_poly linked list +void GridMesh::poly_set_interior(int poly, bool interior) { + poly = poly_first_vert(poly); + for (; poly; poly=v[poly].next_poly) { + int first = poly_first_vert(poly); + int vert=first; + do { + v[vert].is_interior = interior; + vert = v[vert].next; + } while (vert&&vert!=first); + } +} + #if defined(ENABLE_GLUT_DEMO) void GridMesh::poly_center(int poly, float *cx, float *cy) { int vert = poly; @@ -285,23 +337,6 @@ void GridMesh::poly_draw(int poly, float shrinkby, int maxedges) { #endif - -// Fast float->int, courtesy of http://stereopsis.com/sree/fpu2006.html -// 5x faster on x86. It's not in the hot loop anymore so it probably -// doesn't really matter. Todo: test and see. -const double _xs_doublemagic = 6755399441055744.0; //2^52 * 1.5, uses limited precisicion to floor -const double _xs_doublemagicdelta = (1.5e-8); //almost .5f = .5f + 1e^(number of exp bit) -const double _xs_doublemagicroundeps = (.5f-_xs_doublemagicdelta); //almost .5f = .5f - 1e^(number of exp bit) -inline static int xs_CRoundToInt(double val) { - val = val + _xs_doublemagic; - return ((int*)&val)[0]; // 0 for little endian (ok), 1 for big endian (?) - // return int32(floor(val+.5)); //Alternative implementation if the trick is buggy -} -inline static int xs_FloorToInt(double val) { - return xs_CRoundToInt(val-_xs_doublemagicroundeps); - //return floor(val); //Alternative implementation if the trick is buggy -} - void GridMesh::find_cell_line_intersections(double x0, double y0, double x1, double y1, std::vector<std::pair<int,int>> *bottom_edges, std::vector<std::pair<int,int>> *left_edges, @@ -475,26 +510,112 @@ int GridMesh::insert_vert_poly_gridmesh(int mpoly) { return verts_added; } -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; - int vert = cell; - do { - 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; - v[vert].is_entry = interior; // If we were in the interior, this isn't an entry point +void GridMesh::label_interior_AND(int poly2, bool invert_poly2) { + int bb[4]; + poly_grid_BB(poly2, bb); + int minx=bb[0], maxx=bb[1], miny=bb[2], maxy=bb[3]; + if (!invert_poly2) + label_exterior_cells(poly2, false, bb); + known_corner_t known_verts_x0=0, known_verts_xsweep; + for (int y=miny; y<=maxy; y++) { + known_verts_x0 = KNOWN_CORNER_NEXTY(known_verts_x0); + known_verts_x0 = label_interior_cell(poly_for_cell(minx, y), + poly2, + invert_poly2, + known_verts_x0); + known_verts_xsweep = known_verts_x0; + for (int x=minx+1; x<=maxx; x++) { + known_verts_xsweep = KNOWN_CORNER_NEXTX(known_verts_xsweep); + known_verts_xsweep = label_interior_cell(poly_for_cell(x, y), + poly2, + invert_poly2, + known_verts_xsweep); } - vert = v[vert].next; - } while (vert!=cell); - if (!interior==first_is_interior&&debug) { - printf("inconsistent interior call!\n"); } } +void GridMesh::label_interior_SUB(int poly2) { + label_interior_AND(poly2, true); +} + +void GridMesh::label_exterior_cells(int poly, bool interior_lbl, int* bb) { + int bb_local[4]; //int bb[4] = {minx,maxx,miny,maxy} + if (!bb) { + bb = bb_local; + poly_grid_BB(poly, bb); + } + int minx=bb[0], maxx=bb[1], miny=bb[2], maxy=bb[3]; + for (int y=0; y<ny; y++) { // Left of poly + for (int x=0,xlim=std::min(nx,minx); x<xlim; x++) { + poly_set_interior(poly_for_cell(x, y), interior_lbl); + } + } + for (int y=0; y<ny; y++) { // Right of poly + for (int x=maxx+1; x<nx; x++) { + poly_set_interior(poly_for_cell(x, y), interior_lbl); + } + } + for (int y=0; y<miny; y++) { // Bottom of poly + for (int x=minx; x<=maxx; x++) { + poly_set_interior(poly_for_cell(x, y), interior_lbl); + } + } + for (int y=maxy+1; y<ny; y++) { // Top of poly + for (int x=minx; x<=maxx; x++) { + poly_set_interior(poly_for_cell(x, y), interior_lbl); + } + } + +} + +// lr,ul = {0=unknown, 1=known_exterior, 2=known_interior} +known_corner_t GridMesh::label_interior_cell(int cell, int poly2, bool bool_SUB, known_corner_t kin) { + //printf("%i kin:%i\n",cell,int(kin)); + bool interior = false; + known_corner_t ret=0; + for (int poly=cell; poly; poly=v[poly].next_poly) { + if (v[poly].next==0) continue; // Skip degenerate polys + // First, try to find a known corner + bool found_known_corner = false; + if (kin) { + int vert = cell; + do { + char k = v[vert].corner; + if (k && kin|KNOWN_CORNER(k-1)) { + found_known_corner = true; + interior = !(kin&KNOWN_CORNER_EXTERIOR(k-1)); + break; + } + vert = v[vert].next; + } while (vert && vert!=cell); + } + // If using a known corner didn't work, use the slow PIP test + if (!found_known_corner) { + interior = point_in_polygon(v[poly].x, v[poly].y, poly2); + //printf(" pip:%i\n",int(interior)); + if (bool_SUB) interior = !interior; + } + // One way or another, (bool)interior is good now. + int vert = cell; + do { + if (v[vert].is_intersection) { + v[vert].is_interior = true; + interior = !interior; + v[vert].is_entry = interior; // If we were in the interior, this isn't an entry point + } else { + v[vert].is_interior = interior; + char k = v[vert].corner; + if (k) { + ret |= KNOWN_CORNER(k-1); + if (!interior) ret |= KNOWN_CORNER_EXTERIOR(k-1); + } + } + vert = v[vert].next; + } while (vert && vert!=cell); + } + return ret; +} + void GridMesh::trim_to_odd() { for (int i=0; i<nx; i++) { for (int j=0; j<ny; j++) { @@ -503,105 +624,107 @@ void GridMesh::trim_to_odd() { } } -void GridMesh::trim_to_odd(int poly) { +void GridMesh::trim_to_odd(int poly0) { int previous_trace_poly = 0; int this_trace_poly = 0; std::vector<int> trace_origins; std::vector<int> trace; // Holds verts of the polygon being traced trace.reserve(256); - trace_origins.push_back(poly); - while (trace_origins.size()) { - trace.clear(); - 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_intersection && vvert->is_interior))) { - if (vvert->is_used) { - bail = true; - break; - } - vvert->is_used = true; - vert = vvert->next; - vvert->next = 0; // Trail of destruction: no polygons should be - vvert->prev = 0; // generated in the excluded region - vvert = &v[vert]; - } - if (bail) continue; // No valid starting vertex? Bail! - - // We're still sitting at the first valid vertex. - // Overview: follow its edge, record points into trace, - // record branches into trace_or @@ Diff output truncated at 10240 characters. @@ _______________________________________________ Bf-blender-cvs mailing list [email protected] http://lists.blender.org/mailman/listinfo/bf-blender-cvs
