[Bf-blender-cvs] [8d6469a] soc-2014-nurbs: BRep import base

Jonathan deWerd noreply at git.blender.org
Sat Jul 12 09:24:35 CEST 2014


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. @@




More information about the Bf-blender-cvs mailing list