Added dumber+faster grid propagator, fixed displist crash bug for >~10x10 tessellation grids.

4 files changed, 114 insertions, 38 deletions

diff --git a/source/blender/blenkernel/intern/curve.cpp b/source/blender/blenkernel/intern/curve.cpp
index 065fc1defad..3ddbe0118fc 100644
--- a/source/blender/blenkernel/intern/curve.cpp
+++ b/source/blender/blenkernel/intern/curve.cpp
@@ -67,6 +67,7 @@ extern "C" {
 #include <mach/mach.h>
 #include <mach/mach_time.h>
 #include "surf_gridmesh.h"
+#include <set>
 
 /* globals */
 
@@ -4294,12 +4295,16 @@ void BKE_nurb_make_displist(struct Nurb *nu, struct DispList *dl) {
 	float (*coords_tmp)[2] = (float(*)[2])MEM_mallocN(sizeof(*coords_tmp)*TESS_MAX_POLY_VERTS,"NURBS_tess_3");
 	int reindex_tmp[TESS_MAX_POLY_VERTS];
 	unsigned (*idx_tmp)[3] = (unsigned(*)[3])MEM_mallocN(sizeof(*idx_tmp)*TESS_MAX_POLY_VERTS,"NURBS_tess_4");
+	std::vector<int> degenerate_polys;
 	for (int j=0; j<totv; j++) {
 		for (int i=0; i<totu; i++) {
 			int cell = gm->poly_for_cell(i, j);
 			GridMeshVert *v = &gm->v[0];
 			for (int poly=cell; poly; poly=v[poly].next_poly) {
-				if (!v[poly].next) continue;
+				if (!v[poly].next) {
+					printf("Degenerate: %i\n",poly);
+					continue;
+				}
 				if (v[poly].is_pristine) {
 					int ll_gp = gm->gridpt_for_cell(i, j);
 					if (ii+6>=idxs_len) {
diff --git a/source/blender/blenkernel/intern/surf_gridmesh.cpp b/source/blender/blenkernel/intern/surf_gridmesh.cpp
index cfd7caefa19..ec2fbec8db3 100644
--- a/source/blender/blenkernel/intern/surf_gridmesh.cpp
+++ b/source/blender/blenkernel/intern/surf_gridmesh.cpp
@@ -126,9 +126,9 @@ void GridMesh::init_grid(int num_x_cells, int num_y_cells) {
 	}
 	coords_len = (1+nx)*(1+ny)+1;
 	v.resize(nx*ny*4*2);
-	ie_grid.resize(nx*ny+1,false);
-	ie_isect_right.resize(nx*ny+1,false);
-	ie_isect_up.resize(nx*ny+1,false);
+	ie_grid.assign(nx*ny+1,true);
+	ie_isect_right.assign(nx*ny+1,false);
+	ie_isect_up.assign(nx*ny+1,false);
 	vert_set_coord(0, -1234, -1234, -1234);
 	for (int j=0; j<ny; j++) {
 		for (int i=0; i<nx; i++) {
@@ -153,6 +153,27 @@ void GridMesh::init_grid(int num_x_cells, int num_y_cells) {
 	}
 }
 
+void GridMesh::ie_print_grid(int num) {
+	std::vector<bool> *grid = NULL;
+	if (num==0) {
+		puts("ie_grid:");
+		grid = &ie_grid;
+	} else if (num==1) {
+		puts("ie_isect_right:");
+		grid = &ie_isect_right;
+	} else {
+		puts("ie_isect_up:");
+		grid = &ie_isect_up;
+	}
+	for (int y=ny; y>=0; y--) {
+		for (int x=0; x<=nx; x++) {
+			bool val = grid->operator[](gridpt_for_cell(x, y));
+			printf((val)?"1":"0");
+		}
+		puts("");
+	}
+}
+
 int GridMesh::vert_new() {
 	v.push_back(GridMeshVert());
 	return int(v.size()-1);
@@ -260,18 +281,6 @@ void GridMesh::poly_set_cyclic(int poly, bool cyc) {
 	}
 }
 
-int GridMesh::gridpt_for_cell(int x, int y) {
-	if (x<0||x>=nx+1) return 0;
-	if (y<0||y>=ny+1) return 0;
-	return 1+(y*(nx+1)+x);
-}
-
-int GridMesh::poly_for_cell(int x, int y) {
-	if (x<0||x>=nx) return 0;
-	if (y<0||y>=ny) return 0;
-	return 1+4*(y*nx+x);
-}
-
 int GridMesh::poly_for_cell(float fx, float fy) {
 	int x = floor((fx-llx)*inv_dx);
 	if (x<0||x>=nx) return 0;
@@ -341,7 +350,7 @@ void GridMesh::vert_add_neighbor(int v1, int v2) {
 	}
 }
 
-std::pair<int,int> GridMesh::vert_grid_cell(int vert) {
+std::pair<int,int> GridMesh::cell_for_vert(int vert) {
 	// vert = 1+4*(y*nx+x)
 	int ynx_plus_x = (vert-1)/4;
 	int y = ynx_plus_x/nx;
@@ -682,7 +691,7 @@ void GridMesh::punch_hole(int exterior, int hole) {
 		poly_flip_winding_direction(hole);
 	}
 	int v1=exterior, v2=hole;
-	bool v1v2_intersection_free;
+	bool v1v2_intersection_free = false;
 	while (!v1v2_intersection_free) {
 		double v1xyz[3]; vert_get_coord(v1, v1xyz);
 		double v2xyz[3]; vert_get_coord(v2, v1xyz);
@@ -736,15 +745,34 @@ void GridMesh::insert_vert_poly_gridmesh(int mpoly, int *verts_added, int *edges
 	int edges_intersected_local = 0;
 	while (v[v1].next) {
 		int v2 = v[v1].next;
-		// Step 1: find all intersections of the edge v1,v2
+		/**** Step 1: find all intersections of the edge v1,v2 vs the grid ****/
 		double v2xyz[3]; vert_get_coord(v2, v2xyz);
-		//NURBS_TESS_PRINTF("(%f,%f)---line--(%f,%f)\n",v1x,v1y,v2x,v2y);
 		integer_cells.clear();
 		bottom_edges.clear();
 		left_edges.clear();
 		find_cell_line_intersections(v1xyz[0],v1xyz[1],v2xyz[0],v2xyz[1],
 									 &bottom_edges,&left_edges,&integer_cells);
-		edges_intersected_local += int(bottom_edges.size() + left_edges.size());
+		// Step 2: flip the even/odd#intersections indicators on the respective edges
+		int num_bottom_edge_isects = int(bottom_edges.size());
+		for (int ei_num=0; ei_num<num_bottom_edge_isects; ei_num++) {
+			std::pair<int,int> xy = bottom_edges[ei_num];
+			int ie_isect_idx = gridpt_for_cell(xy.first, xy.second);
+			bool even_odd = ie_isect_right[ie_isect_idx];
+			ie_isect_right[ie_isect_idx] = !even_odd;
+		}
+		int num_left_edge_isects = int(left_edges.size());
+		for (int ei_num=0; ei_num<num_left_edge_isects; ei_num++) {
+			std::pair<int,int> xy = left_edges[ei_num];
+			int ie_isect_idx = gridpt_for_cell(xy.first, xy.second);
+			bool even_odd = ie_isect_up[ie_isect_idx];
+			ie_isect_up[ie_isect_idx] = !even_odd;
+		}
+		edges_intersected_local += num_bottom_edge_isects + num_left_edge_isects;
+		
+		// Step 3: turn "line passed through cell" events from raster algo
+		// into actual intersections by intersecting againt every edge in the cell,
+		// sorting so that even in the case of coincident edges we leave one
+		// polygon before entering the other.
 		std::vector<IntersectingEdge> isect;
 		for (size_t i=0,l=integer_cells.size(); i<l; i++) {
 			std::pair<int,int> j = integer_cells[i];
@@ -762,7 +790,8 @@ void GridMesh::insert_vert_poly_gridmesh(int mpoly, int *verts_added, int *edges
 			}
 		}
 		std::stable_sort(isect.begin(),isect.end(),intersection_edge_order);
-		// Step 2: insert them
+		
+		/**** Step 4: insert verts at the intersections we discovered ****/
 		for (IntersectingEdge ie : isect) {
 			v1 = insert_vert(v1, v2, ie.e2, v[ie.e2].next, ie.x, ie.y);
 		}
@@ -775,6 +804,7 @@ void GridMesh::insert_vert_poly_gridmesh(int mpoly, int *verts_added, int *edges
 }
 
 void GridMesh::label_interior_AND(int poly2, bool invert_poly2, int *bb) {
+	// Step 1: Label cells that are definitely in the exterior of the boolean result.
 	int bb_local[4];
 	if (!bb) {
 		bb = bb_local;
@@ -783,6 +813,38 @@ void GridMesh::label_interior_AND(int poly2, bool invert_poly2, int *bb) {
 	int minx=bb[0], maxx=bb[1], miny=bb[2], maxy=bb[3];
 	if (!invert_poly2)
 		label_exterior_cells(poly2, false, bb);
+	// Step 2: Ensure that the lower left corner is labeled correctly
+	int ll_gridpt = gridpt_for_cell(0, 0);
+	if (ie_grid[ll_gridpt]) { // false => not in interior. true => anything's possible
+		std::pair<float,float> llxy = cell_ll_corner(0,0);
+		ie_grid[1] = point_in_polygon(llxy.first, llxy.second, poly2) ^ invert_poly2;
+	}
+	/* Step 3: propagate the label to all other gridpoints
+	for (int y=0; y<=ny; y++) {
+		bool cur_ie = false;
+		int below_idx=gridpt_for_cell(0, y-1), cur_idx=gridpt_for_cell(0, y);
+		if (y!=0) {
+			cur_ie = ie_grid[cur_idx] = ie_grid[below_idx] ^ ie_isect_up[below_idx];
+		} else {
+			cur_ie = ie_grid[cur_idx];
+		}
+		for (int x=0; x<nx; x++) {
+			cur_ie = cur_ie ^ ie_isect_right[cur_idx];
+			ie_grid[++cur_idx] = cur_ie;
+		}
+	}
+	// Step 4: Use interior/exterior calls on gridpt verts to label all verts
+	for (int y=miny; y<=maxy; y++) {
+		for (int x=minx; x<=maxx; x++) {
+			known_corner_t known_verts = KNOWN_CORNER_ALL;
+			if (!ie_grid[gridpt_for_cell(x,y)])     known_verts += KNOWN_CORNER_LL_EXTERIOR;
+			if (!ie_grid[gridpt_for_cell(x+1,y)])   known_verts += KNOWN_CORNER_LR_EXTERIOR;
+			if (!ie_grid[gridpt_for_cell(x+1,y+1)]) known_verts += KNOWN_CORNER_UR_EXTERIOR;
+			if (!ie_grid[gridpt_for_cell(x,y+1)])   known_verts += KNOWN_CORNER_UL_EXTERIOR;
+			label_interior_cell(poly_for_cell(x, y), poly2, invert_poly2, known_verts);
+		}
+	}*/
+	// Alternative Step 3+4
 	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);
diff --git a/source/blender/blenkernel/intern/surf_gridmesh.h b/source/blender/blenkernel/intern/surf_gridmesh.h
index 2f5636bc2af..50ff336d2a0 100644
--- a/source/blender/blenkernel/intern/surf_gridmesh.h
+++ b/source/blender/blenkernel/intern/surf_gridmesh.h
@@ -56,11 +56,12 @@ struct IntersectingEdge {
 #define KNOWN_CORNER_LL (1<<0)
 #define KNOWN_CORNER_LL_EXTERIOR (1<<1)
 #define KNOWN_CORNER_UL (1<<2)
-#define KNOWN_CORNER_ULe_EXTERIOR (1<<3)
+#define KNOWN_CORNER_UL_EXTERIOR (1<<3)
 #define KNOWN_CORNER_LR (1<<4)
 #define KNOWN_CORNER_LR_EXTERIOR (1<<5)
 #define KNOWN_CORNER_UR (1<<6)
 #define KNOWN_CORNER_UR_EXTERIOR (1<<7)
+#define KNOWN_CORNER_ALL (KNOWN_CORNER_LL+KNOWN_CORNER_LR+KNOWN_CORNER_UL+KNOWN_CORNER_UR)
 #define KNOWN_CORNER_NEXTX(kc) ((kc)>>4)
 #define KNOWN_CORNER_NEXTY(kc) ((kc)>>2)&0x33
 typedef unsigned char known_corner_t;
@@ -68,7 +69,7 @@ typedef unsigned char known_corner_t;
 struct GridMesh {
 	static float tolerance;
 	
-	// 3D coordinate storage (all trimming functions ignore the 3rd coord)
+	// 3D coordinate storage (all trimming functions ignore the z coord)
 	// coords[0] is defined to be invalid.
 	// manually managed memory to avoid copy during handoff to C code
 	GridMeshCoord *coords;
@@ -77,8 +78,13 @@ struct GridMesh {
 	void coords_import(GridMeshCoord *c, int len); // Transfers ownership to this
 	GridMeshCoord *coords_export(int *len); // Transfers ownership to the caller
 	
-	// Vertex storage. Example: "int prev" in a GridMeshVert refers to v[prev].
-	// v[0] is defined to be invalid and filled with the telltale location (-1234,-1234)
+	// Permit usage of blender's memory management system
+	void* (*mallocN)(size_t sz, const char *name);
+	void* (*reallocN)(void *old, size_t sz, const char *name);
+
+	// Vertex storage. Example: "int prev" in a GridMeshVert refers to
+	// (GridMeshVert*)v[prev]. v[0] is defined to be invalid and filled with
+	// the telltale location (-1234,-1234)
 	std::vector<GridMeshVert> v;
 	
 	// Interior/Exterior calls are cheap at grid points due to information
@@ -90,11 +96,8 @@ struct GridMesh {
 	std::vector<bool> ie_grid;
 	std::vector<bool> ie_isect_right;
 	std::vector<bool> ie_isect_up;
-	
-	// Permit usage of blender's memory management system
-	void* (*mallocN)(size_t sz, const char *name);
-	void* (*reallocN)(void *old, size_t sz, const char *name);
-	
+	void ie_print_grid(int num);
+		
 	double llx, lly, urx, ury; // Coordinates of lower left and upper right grid corners
 	double dx, dy; // Width of a cell in the x, y directions
 	double inv_dx, inv_dy; // 1/(width of a cell), 1/(height of a cell)
@@ -106,6 +109,11 @@ struct GridMesh {
 	void init_grid(int num_x_cells, int num_y_cells);
 	~GridMesh();
 	
+	// Coordinate utilities
+	int gridpt_for_cell(int x, int y) {return (0<=x&&x<=nx&&0<=y&y<=ny)? 1+(y*(nx+1)+x) : 0;}
+	std::pair<int,int> cell_for_vert(int vert);
+	std::pair<float,float> cell_ll_corner(int x, int y) {return std::make_pair(llx+x*dx,lly+y*dy);}
+
 	// Vert manipulation
 	int vert_new();
 	int vert_new(int prev, int next); // Make a new vert in the middle of an existing poly
@@ -115,12 +123,10 @@ struct GridMesh {
 	int vert_id(GridMeshVert *vert) {return vert?int(vert-&v[0]):0;}
 	int vert_neighbor_on_poly(int vert, int poly);
 	void vert_add_neighbor(int vert, int new_neighbor);
-	std::pair<int,int> vert_grid_cell(int vert);
-	int gridpt_for_cell(int x, int y);
 	
 	// Poly manipulation
 	int poly_new(const float* packed_coords, int len);
-	int poly_for_cell(int x, int y);
+	int poly_for_cell(int x, int y) {return (0<=x&&x<nx&&0<=y&y<ny)? 1+4*(y*nx+x) : 0;}
 	int poly_for_cell(float x, float y);
 	int poly_first_vert(int anyvert);
 	int poly_last_vert(int anyvert);
@@ -135,7 +141,6 @@ struct GridMesh {
 	void poly_translate(int poly, double x, double y);
 	double poly_signed_area(int poly); // ccw is positive
 	void poly_flip_winding_direction(int poly);
-	void punch_hole(int exterior, int hole);
 	
 	// Trimming
 	bool point_in_polygon(double x, double y, int poly);
@@ -151,7 +156,10 @@ struct GridMesh {
 									  std::vector<std::pair<int,int> > *bottom_edges,
 									  std::vector<std::pair<int,int> > *left_edges,
 									  std::vector<std::pair<int,int> > *integer_cells);
-	// High level booleans
+	void punch_hole(int exterior, int hole);
+
+	/********************  Booleans ********************/
+	// High level
 	void bool_AND(int poly2); // gridmesh -> gridmesh (intersection) poly2
 	void bool_SUB(int poly2); // gridmesh -> gridmesh (intersection) ~poly2
 	// Low level boolean support algorithms
@@ -168,6 +176,7 @@ struct GridMesh {
 	// Step 3: perform the actual trim
 	void trim_to_odd(int *bb=NULL);
 	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/tests/interactive/nurbs_trimtess.cpp b/tests/interactive/nurbs_trimtess.cpp
index 50b0ee7894e..5f54640a022 100644
--- a/tests/interactive/nurbs_trimtess.cpp
+++ b/tests/interactive/nurbs_trimtess.cpp
@@ -25,7 +25,7 @@ float intersect_check_tol = .001; //Maximum Euclidean dist between intersect pts
 /***************************** DEFAULT SCENE *****************************/
 GridMesh *gm;
 int max_drawn_edges=0; // Number of edges to draw per poly (for figuring out order). 0 disables.
-#define GRIDMESH_GEOM_TEST_5
+#define GRIDMESH_GEOM_TEST_4
 //#define RASTER_VIZ
 
 #if defined(GRIDMESH_GEOM_TEST_1)
@@ -127,7 +127,7 @@ void init_default_scene() {
 	// Import the subject polygons into the linked list datastructure
 	int last = 0;
 	for (std::vector<float> poly_verts : subj_polys) {
-		int np = gm->poly_new(&subj0[0], int(subj0.size()));
+		int np = gm->poly_new(&poly_verts[0], int(poly_verts.size()));
 		if (last)
 			gm->v[last].next_poly = np;
 		else