Commit: 8d6469adad6ccc1dbb65fc3a78247941b729921e
Author: Jonathan deWerd
Date: Mon Jul 7 23:05:48 2014 -0400
https://developer.blender.org/rB8d6469adad6ccc1dbb65fc3a78247941b729921e
BRep import base
===================================================================
M source/blender/blenkernel/intern/curve.c
M source/blender/blenlib/intern/polyfill2d.c
M source/blender/editors/curve/GridMesh.cpp
M source/blender/editors/curve/GridMesh.h
M source/blender/editors/curve/GridMesh_GLUT_debug_tool.cpp
M source/blender/editors/io/io_rhino_import.cpp
M source/blender/makesdna/DNA_curve_types.h
===================================================================
diff --git a/source/blender/blenkernel/intern/curve.c
b/source/blender/blenkernel/intern/curve.c
index 0abe956..83ea31c 100644
--- a/source/blender/blenkernel/intern/curve.c
+++ b/source/blender/blenkernel/intern/curve.c
@@ -992,6 +992,10 @@ void BKE_nurb_knot_calc_v(Nurb *nu)
makeknots(nu, 2);
}
+/* Fills <basis> with <pnts> weights corresponding to the curve evaluated
+ * at point t. <start> is the index of the first nz basis function at t, <end>
+ * is the index of the last nz basis function at t.
+ */
static void basisNurb(float t, short order, int pnts, float *knots, float
*basis, int *start, int *end)
{
float d, e;
diff --git a/source/blender/blenlib/intern/polyfill2d.c
b/source/blender/blenlib/intern/polyfill2d.c
index c718902..8c93b07 100644
--- a/source/blender/blenlib/intern/polyfill2d.c
+++ b/source/blender/blenlib/intern/polyfill2d.c
@@ -906,7 +906,7 @@ void BLI_polyfill_calc(
const int coords_sign,
unsigned int (*r_tris)[3])
{
- PolyFill pf;
+ PolyFill pf; printf(".");
PolyIndex *indices = BLI_array_alloca(indices, coords_tot);
#ifdef DEBUG_TIME
diff --git a/source/blender/editors/curve/GridMesh.cpp
b/source/blender/editors/curve/GridMesh.cpp
index 99f855a..8056c5e 100644
--- a/source/blender/editors/curve/GridMesh.cpp
+++ b/source/blender/editors/curve/GridMesh.cpp
@@ -14,7 +14,13 @@
#include <limits>
#include "GridMesh.h"
-static bool debug = 1;
+//#define NURBS_TESS_DEBUG
+#if defined(NURBS_TESS_DEBUG)
+#define NURBS_TESS_PRINTF(...) printf(__VA_ARGS__)
+#else
+#define NURBS_TESS_PRINTF(...)
+#endif
+
float GridMesh::tolerance = 1e-5;
@@ -36,13 +42,13 @@ inline static int xs_FloorToInt(double val) {
static void print_kc(known_corner_t kc) {
if (kc&KNOWN_CORNER_LL)
- printf("LL%c",(kc&KNOWN_CORNER_LL_EXTERIOR)?'e':'i');
+ NURBS_TESS_PRINTF("LL%c",(kc&KNOWN_CORNER_LL_EXTERIOR)?'e':'i');
if (kc&KNOWN_CORNER_UL)
- printf("UL%c",(kc&KNOWN_CORNER_UL_EXTERIOR)?'e':'i');
+ NURBS_TESS_PRINTF("UL%c",(kc&KNOWN_CORNER_UL_EXTERIOR)?'e':'i');
if (kc&KNOWN_CORNER_LR)
- printf("LR%c",(kc&KNOWN_CORNER_LR_EXTERIOR)?'e':'i');
+ NURBS_TESS_PRINTF("LR%c",(kc&KNOWN_CORNER_LR_EXTERIOR)?'e':'i');
if (kc&KNOWN_CORNER_UR)
- printf("UR%c",(kc&KNOWN_CORNER_UR_EXTERIOR)?'e':'i');
+ NURBS_TESS_PRINTF("UR%c",(kc&KNOWN_CORNER_UR_EXTERIOR)?'e':'i');
}
void GridMesh::set_ll_ur(double lowerleft_x, double lowerleft_y,
@@ -158,7 +164,7 @@ void GridMesh::poly_set_cyclic(int poly, bool cyc) {
int GridMesh::poly_for_cell(int x, int y) {
if (x<0||x>=nx) return 0;
- if (y<0||y>=nx) return 0;
+ if (y<0||y>=ny) return 0;
return 1+4*(y*nx+x);
}
@@ -166,7 +172,7 @@ int GridMesh::poly_for_cell(float fx, float fy) {
int x = floor((fx-llx)*inv_dx);
if (x<0||x>=nx) return 0;
int y = floor((fy-lly)*inv_dy);
- if (y<0||y>=nx) return 0;
+ if (y<0||y>=ny) return 0;
return 1+4*(y*nx+x);
}
@@ -302,7 +308,7 @@ void GridMesh::poly_draw(int poly, float shrinkby, int
maxedges) {
}
for (; poly; poly=v[poly].next_poly) {
if (v[poly].next==0) continue;
- printf("Poly %i: ",poly);
+ NURBS_TESS_PRINTF("Poly %i: ",poly);
// Find the center so that we can shrink towards it
float cx,cy;
poly_center(poly, &cx, &cy);
@@ -313,7 +319,7 @@ void GridMesh::poly_draw(int poly, float shrinkby, int
maxedges) {
int num_drawn_edges = 0;
do {
int v2 = v[v1].next;
- printf("%i-%i, ",v1,v2);
+ NURBS_TESS_PRINTF("%i-%i, ",v1,v2);
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);
++num_drawn_edges;
@@ -321,7 +327,7 @@ void GridMesh::poly_draw(int poly, float shrinkby, int
maxedges) {
break;
v1 = v2;
} while (v1!=poly && v1!=v[v1].first);
- puts("");
+ NURBS_TESS_PRINTF("\n");
glEnd();
// Draw the polygon verts
glPointSize(3);
@@ -479,22 +485,135 @@ int GridMesh::insert_vert(int poly1left,
void GridMesh::bool_AND(int poly2) {
int bb[4];
poly_grid_BB(poly2, bb);
- insert_vert_poly_gridmesh(poly2);
+ int num_v, num_e; insert_vert_poly_gridmesh(poly2, &num_v, &num_e);
+ bool add_poly_after_end = false;
+ if (num_v==0 && num_e==0) {
+ int p = poly_for_cell(v[poly2].x, v[poly2].y);
+ if (p) {
+ double p2x=v[poly2].x, p2y=v[poly2].y;
+ for (int subpoly=p; subpoly;
subpoly=v[subpoly].next_poly) {
+ if (point_in_polygon(p2x, p2y, subpoly)) {
+ add_poly_after_end = true;
+ break;
+ }
+ }
+ }
+ }
+ // If we found intersections, the chalk-cart algo suffices
label_interior_freepoly(poly2);
label_interior_AND(poly2,false,bb);
trim_to_odd();
+ if (add_poly_after_end) {
+ int p = poly_for_cell(v[poly2].x, v[poly2].y);
+ v[p].next_poly = poly2;
+ }
}
// gridmesh -> gridmesh (intersection) ~poly2
void GridMesh::bool_SUB(int poly2) {
int bb[4];
poly_grid_BB(poly2, bb);
- insert_vert_poly_gridmesh(poly2);
- label_interior_freepoly(poly2);
- label_interior_AND(poly2,true,bb);
- trim_to_odd(bb);
+ int num_v, num_e; insert_vert_poly_gridmesh(poly2, &num_v, &num_e);
+ if (num_v==0 && num_e==0) {
+ int p = poly_for_cell(v[poly2].x, v[poly2].y);
+ double p2x=v[poly2].x, p2y=v[poly2].y;
+ for (int containing_poly=p; containing_poly;
containing_poly=v[containing_poly].next_poly) {
+ if (point_in_polygon(p2x, p2y, containing_poly)) {
+ // We were in a polygon after all.
+ punch_hole(containing_poly, poly2);
+ break;
+ }
+ }
+ } else {
+ label_interior_freepoly(poly2);
+ label_interior_AND(poly2,true,bb);
+ trim_to_odd(bb);
+ }
}
+void GridMesh::poly_translate(int poly, double x, double y) {
+ int vert=poly; do {
+ v[vert].x += x;
+ v[vert].y += y;
+ vert = v[vert].next;
+ } while (vert!=poly);
+}
+
+double GridMesh::poly_signed_area(int poly) {
+ double a=0;
+ int v0=poly;
+ double v0x=v[v0].x, v0y=v[v0].y;
+ int v1=v[poly].next;
+ double v1x=v[v1].x, v1y=v[v1].y;
+ int v2=v[v1].next;
+ double v2x=v[v2].x, v2y=v[v2].y;
+ while (v2 && v2!=poly) {
+ double v01x=v1x-v0x, v01y=v1y-v0y;
+ double v02x=v2x-v0x, v02y=v2y-v0y;
+ a += v01x*v02y - v02x*v01y;
+ v1=v2; v1x=v2x; v1y=v2y;
+ v2=v[v2].next;
+ v2x=v[v2].x; v2y=v[v2].y;
+ }
+ return a*0.5;
+}
+
+void GridMesh::poly_flip_winding_direction(int poly) {
+ int vert=poly;
+ do {
+ int old_prev=v[vert].prev, old_next=v[vert].next;
+ v[vert].prev=old_next;
+ v[vert].next=old_prev;
+ vert = old_next;
+ } while (vert!=poly);
+}
+
+
+void GridMesh::punch_hole(int exterior, int hole) {
+ double a_ext=poly_signed_area(exterior), a_int=poly_signed_area(hole);
+ if ((a_ext>0&&a_int>0) || (a_ext<0&&a_int<0)) {
+ poly_flip_winding_direction(hole);
+ }
+ int v1=exterior, v2=hole;
+ bool v1v2_intersection_free;
+ while (!v1v2_intersection_free) {
+ double v1x=v[v1].x, v1y=v[v1].y;
+ double v2x=v[v2].x, v2y=v[v2].y;
+ v1v2_intersection_free = true;
+ std::vector<IntersectingEdge> isect_ext =
edge_poly_intersections(v1x,v1y,v2x,v2y, exterior);
+ for (IntersectingEdge& ie : isect_ext) {
+ if (ie.alpha1>tolerance && ie.alpha1<(1-tolerance)) {
+ v1v2_intersection_free = false;
+ v1 = ie.e2;
+ break;
+ }
+ }
+ if (!v1v2_intersection_free) continue;
+ std::vector<IntersectingEdge> isect_hole =
edge_poly_intersections(v1x,v1y,v2x,v2y, hole);
+ for (IntersectingEdge& ie : isect_hole) {
+ if (ie.alpha1>tolerance && ie.alpha1<(1-tolerance)) {
+ v1v2_intersection_free = false;
+ v2 = ie.e2;
+ break;
+ }
+ }
+ }
+ int int_l=v[v2].prev, int_c=v2, int_r=v[v2].next;
+ int ext_l=v[v1].prev, ext_c=v1, ext_r=v[v1].next;
+ int int_cc=vert_new(), ext_cc=vert_new();
+ v[int_cc]=v[int_c]; v[ext_cc]=v[ext_c];
+ v[int_c].next=ext_cc; v[ext_cc].prev=int_c;
+ v[ext_cc].next=ext_r; v[ext_r].prev=ext_cc;
+ v[ext_c].next=int_cc; v[int_cc].prev=ext_c;
+ v[int_cc].next=int_r; v[int_r].prev=int_cc;
+ int first = v[ext_c].first;
+ int vert = ext_c; do {
+ v[vert].first = first;
+ vert = v[vert].next;
+ } while (vert!=ext_c);
+}
+
+
static bool intersection_edge_order(const IntersectingEdge& e1, const
IntersectingEdge& e2) {
double diff = e1.alpha1-e2.alpha1;
if (abs(diff)<1e-5 && e1.cellidx!=e2.cellidx) {
@@ -502,19 +621,24 @@ static bool intersection_edge_order(const
IntersectingEdge& e1, const Intersecti
}
return diff<0;
}
-int GridMesh::insert_vert_poly_gridmesh(int mpoly) {
+void GridMesh::insert_vert_poly_gridmesh(int mpoly, int *verts_added, int
*edges_intersected) {
std::vector<std::pair<int,int>> bottom_edges, left_edges, integer_cells;
mpoly = poly_first_vert(mpoly);
int v1 = mpoly;
float v1x=v[v1].x, v1y=v[v1].y;
- int verts_added = 0;
+ int verts_added_local = 0;
+ int edges_intersected_local = 0;
while (v[v1].next) {
int v2 = v[v1].next;
// Step 1: find all intersections of the edge v1,v2
float v2x=v[v2].x, v2y=v[v2].y;
- //printf("(%f,%f)---line--(%f,%f)\n",v1x,v1y,v2x,v2y);
+
//NURBS_TESS_PRINTF("(%f,%f)---line--(%f,%f)\n",v1x,v1y,v2x,v2y);
integer_cells.clear();
-
find_cell_line_intersections(v1x,v1y,v2x,v2y,nullptr,nullptr,&integer_cells);
+ bottom_edges.clear();
+ left_edges.clear();
+ find_cell_line_intersections(v1x,v1y,v2x,v2y,
+
&bottom_edges,&left_edges,&integer_cells);
+ edges_intersected_local += int(bottom_edges.size() +
left_edges.size());
std::vector<IntersectingEdge> isect;
for (size_t i=0,l=integer_cells.size(); i<l; i++) {
std::pair<int,int> j = integer_cells[i];
@@ -523,10 +647,10 @@ int GridMesh::insert_vert_poly_gridmesh(int mpoly) {
if (!cell_poly || !v[cell_poly].next) continue;
std::vector<IntersectingEdge> isect_tmp =
edge_poly_intersections(v1, cell_poly);
for (IntersectingEdge& e : isect_tmp) {
- //printf("(%i,%i)",j.first,j.second);
+
//NURBS_TESS_PRINTF("(%i,%i)",j.first,j.second);
e.cellidx = int(i);
}
- //printf("\n");
+ //NURBS_TESS_PRINTF("\n");
isect.insert(isect.end(),isect_tmp.begin(),isect_tmp.end());
}
}
@@ -535,11 +659,12 @@ int GridMesh::insert_vert_poly_gridmesh(int mpoly) {
for (IntersectingEdge ie : isect) {
v1 = insert_vert(v1, v2, ie.e2, v[ie.e2].next, ie.x,
ie.y);
}
- verts_added += isect.size();
+ verts_added_local += isect.size();
v1=v2; v1x=v2x; v1y=v2y;
if (v1==mpoly) break;
}
-
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
