Displist construction -- better commit it before I tear it up again

5 files changed, 136 insertions, 22 deletions

diff --git a/source/blender/blenkernel/BKE_curve.h b/source/blender/blenkernel/BKE_curve.h
index 6dd124157be..d51505931ef 100644
--- a/source/blender/blenkernel/BKE_curve.h
+++ b/source/blender/blenkernel/BKE_curve.h
@@ -180,6 +180,6 @@ void BKE_nurb_handles_test(struct Nurb *nu, const bool use_handles);
 /* Does not traverse nu's linked list. Fills dl with a mesh corresponding to
  * the single surface nu, performing trim if necessary.
  */
-void BKE_nurb_make_displist(struct Nurb *nu, struct DispList *dl);
+void BKE_nurb_make_displist(struct Nurb *nurb, struct DispList *dl, int nu, int nv);
 
 #endif  /* __BKE_CURVE_H__ */
diff --git a/source/blender/blenkernel/intern/curve.cpp b/source/blender/blenkernel/intern/curve.cpp
index 041f5714206..a85d9c4f982 100644
--- a/source/blender/blenkernel/intern/curve.cpp
+++ b/source/blender/blenkernel/intern/curve.cpp
@@ -40,6 +40,7 @@ extern "C" {
 #include "BLI_math.h"
 #include "BLI_utildefines.h"
 #include "BLI_ghash.h"
+#include "BLI_polyfill2d.h"
 
 #include "DNA_curve_types.h"
 #include "DNA_material_types.h"
@@ -65,6 +66,7 @@ extern "C" {
 #include <CoreServices/CoreServices.h>
 #include <mach/mach.h>
 #include <mach/mach_time.h>
+#include "surf_gridmesh.h"
 
 /* globals */
 
@@ -4250,6 +4252,79 @@ void BKE_curve_rect_from_textbox(const struct Curve *cu, const struct TextBox *t
 	r_rect->ymin = r_rect->ymax - tb->h;
 }
 
-void BKE_nurb_make_displist(struct Nurb *nu, struct DispList *dl) {
+void BKE_nurb_make_displist(struct Nurb *nu, struct DispList *dl, int totu, int totv) {
+	dl->col = nu->mat_nr;
+	dl->charidx = nu->charidx;
+	dl->rt = nu->flag & ~CU_2D;
+
+	// Figure out the domain
+	float ustart = nu->knotsu[nu->orderu - 1];
+	float uend;
+	if (nu->flagu & CU_NURB_CYCLIC)
+		uend = nu->knotsu[nu->pntsu + nu->orderu - 1];
+	else
+		uend = nu->knotsu[nu->pntsu];
+	float vstart = nu->knotsv[nu->orderv - 1];
+	float vend;
+	if (nu->flagv & CU_NURB_CYCLIC)
+		vend = nu->knotsv[nu->pntsv + nu->orderv - 1];
+	else
+		vend = nu->knotsv[nu->pntsv];
+	
+	// Trim the uniform grid in 2D UV space
+	GridMesh *gm = new GridMesh();
+	int coords_len = (totu+1)*(totv+1)*2;
+	float *coords = (float*)MEM_mallocN(coords_len * sizeof(float[3]), "dlcoords");
+	gm->coords_import((GridMeshCoord*)coords, coords_len);
+	gm->set_ll_ur(ustart,vstart,uend,vend);
+	gm->init_grid(totu,totv);
+	
+	// Extract the results
+	dl->verts = coords = (float*)gm->coords_export(NULL);
+	int idxs_len = 2 * 6*sizeof(int)*totu*totv;
+	int *idxs = (int*)MEM_mallocN(idxs_len, "index array nurbs");
+	int ii=0; // Index index
+#define TESS_MAX_POLY_VERTS 32
+	float *coords_tmp[TESS_MAX_POLY_VERTS];
+	int *idx_tmp[TESS_MAX_POLY_VERTS];
+	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].is_pristine) {
+					int ll_gp = gm->gridpt_for_cell(i, j);
+					idxs[ii++] = ll_gp;
+					idxs[ii++] = ll_gp+1;
+					idxs[ii++] = ll_gp+(totu+1)+1;
+					idxs[ii++] = ll_gp+(totu+1)+1;
+					idxs[ii++] = ll_gp+(totu+1);
+					idxs[ii++] = ll_gp;
+				} else {
+					int coords_tot=0;
+					for (int vert=poly; vert!=poly; vert=v[poly].next) {
+						coords_tmp[coords_tot] = &coords[v[poly].coord_idx];
+						idx_tmp[coords_tot] = &idxs[ii];
+						ii += 3;
+						coords_tot++;
+					}
+					ii-=6; // n vert polygon has n-2 tris in triangulation
+					BLI_polyfill_calc((float(*)[2])coords_tmp,
+									  coords_tot,
+									  0, // tell polyfill to do concave check
+									  (unsigned int(*)[3])idx_tmp);
+				}
+			}
+		}
+	}
+	dl->verts = coords;
+	dl->index = idxs;
+	dl->type = DL_INDEX3;
+	dl->parts = ii/3;
+	
+	// Pushforward through the NURBS map
+	//gm->pushforward(nu);
 	
+	delete gm;
 }
diff --git a/source/blender/blenkernel/intern/displist.c b/source/blender/blenkernel/intern/displist.c
index 55b8ae57c61..137709d1363 100644
--- a/source/blender/blenkernel/intern/displist.c
+++ b/source/blender/blenkernel/intern/displist.c
@@ -1249,7 +1249,8 @@ void BKE_displist_make_surf(Scene *scene, Object *ob, ListBase *dispbase,
 			else {
 				dl = MEM_callocN(sizeof(DispList), "makeDispListsurf");
 				BLI_addtail(dispbase, dl);
-				BKE_nurb_make_displist(nu, dl);
+				int totu = nu->pntsu * resolu, totv = nu->pntsv * resolv;
+				BKE_nurb_make_displist(nu, dl, totu, totv);
 			}
 		}
 	}
diff --git a/source/blender/blenkernel/intern/surf_gridmesh.cpp b/source/blender/blenkernel/intern/surf_gridmesh.cpp
index d8f5bb433ef..b280e552784 100644
--- a/source/blender/blenkernel/intern/surf_gridmesh.cpp
+++ b/source/blender/blenkernel/intern/surf_gridmesh.cpp
@@ -51,6 +51,45 @@ static void print_kc(known_corner_t kc) {
 		NURBS_TESS_PRINTF("UR%c",(kc&KNOWN_CORNER_UR_EXTERIOR)?'e':'i');
 }
 
+GridMeshVert::GridMeshVert() :	next(0), prev(0),
+								next_poly(0), neighbor(0), first(0),
+								is_intersection(false), is_interior(true), is_entry(false),
+								is_used(false), corner(0), tmp(0), is_pristine(0),
+								owns_coords(0), coord_idx(0)
+{}
+
+GridMesh::GridMesh() {
+	coords = NULL;
+	coords_len = coords_reserved_len = 0;
+}
+
+GridMesh::~GridMesh() {
+	if (coords) free(coords);
+}
+
+void GridMesh::coords_reserve(int new_reserved_len) {
+	if (coords_reserved_len>=new_reserved_len) return;
+	if (!coords) {
+		coords = (GridMeshCoord*)malloc(sizeof(*coords)*new_reserved_len);
+		coords_reserved_len = new_reserved_len;
+	} else if (coords_reserved_len<new_reserved_len){
+		coords = (GridMeshCoord*)realloc(coords, sizeof(*coords)*new_reserved_len);
+	}
+}
+
+void GridMesh::coords_import(GridMeshCoord *c, int len) {
+	if (coords) printf("WARNING: coords should be imported *before* init\n");
+	coords = c;
+	coords_len = len;
+}
+
+GridMeshCoord *GridMesh::coords_export(int *len) {
+	GridMeshCoord *ret = coords;
+	if (len) *len = coords_len;
+	coords = NULL;
+	return ret;
+}
+
 void GridMesh::set_ll_ur(double lowerleft_x, double lowerleft_y,
 						 double upperright_x, double upperright_y) {
 	llx = lowerleft_x; lly = lowerleft_y;
@@ -63,19 +102,10 @@ void GridMesh::set_ll_ur(double lowerleft_x, double lowerleft_y,
 	inv_dy = 1.0/dy;
 }
 
-GridMeshVert::GridMeshVert() :	next(0), prev(0),
-								next_poly(0), neighbor(0), first(0),
-								is_intersection(false), is_interior(true), is_entry(false),
-								is_used(false), corner(0), tmp(0), is_pristine(0),
-								owns_coords(0), coord_idx(0)
-{}
-
-GridMesh::GridMesh(double lowerleft_x, double lowerleft_y,
-				   double upperright_x, double upperright_y,
-				   int num_x_cells, int num_y_cells) {
+void GridMesh::init_grid(int num_x_cells, int num_y_cells) {
 	nx = num_x_cells; ny = num_y_cells;
-	set_ll_ur(lowerleft_x, lowerleft_y, upperright_x, upperright_y);
-	coords.resize((nx+1)*(ny+1)*2);
+	int num_coords = (nx+1)*(ny+1)*2+1;
+	coords_reserve(num_coords);
 	for (int j=0; j<ny+1; j++) {
 		for (int i=0; i<nx+1; i++) {
 			GridMeshCoord& c = coords[gridpt_for_cell(i,j)];
@@ -144,8 +174,11 @@ void GridMesh::vert_set_coord(int vert, double x, double y, double z) {
 		xyz.x=x; xyz.y=y; xyz.z=z;
 		return;
 	}
-	coords.push_back(GridMeshCoord(x,y,z));
-	v[vert].coord_idx = int(coords.size()-1);
+	int idx = coords_len;
+	coords_reserve(coords_len++);
+	GridMeshCoord& xyz = coords[idx];
+	xyz.x=x; xyz.y=y; xyz.z=z;
+	v[vert].coord_idx = idx;
 	v[vert].owns_coords = 1;
 }
 
diff --git a/source/blender/blenkernel/intern/surf_gridmesh.h b/source/blender/blenkernel/intern/surf_gridmesh.h
index 5c415832311..42b29b377c5 100644
--- a/source/blender/blenkernel/intern/surf_gridmesh.h
+++ b/source/blender/blenkernel/intern/surf_gridmesh.h
@@ -69,8 +69,13 @@ struct GridMesh {
 	static float tolerance;
 	
 	// 3D coordinate storage (all trimming functions ignore the 3rd coord)
-	// coords[0] is defined to be invalid
-	std::vector<GridMeshCoord> coords;
+	// coords[0] is defined to be invalid.
+	// manually managed memory to avoid copy during handoff to C code
+	GridMeshCoord *coords;
+	int coords_len, coords_reserved_len;
+	void coords_reserve(int new_reserved_len);
+	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)
@@ -91,11 +96,11 @@ struct GridMesh {
 	double inv_dx, inv_dy; // 1/(width of a cell), 1/(height of a cell)
 	int nx, ny; // Number of cells in the x and y directions
 	
-	GridMesh(double lowerleft_x, double lowerleft_y,
-			 double upperright_x, double upperright_y,
-			 int num_x_cells, int num_y_cells);
+	GridMesh();
 	void set_ll_ur(double lowerleft_x, double lowerleft_y,
 				   double upperright_x, double upperright_y);
+	void init_grid(int num_x_cells, int num_y_cells);
+	~GridMesh();
 	
 	// Vert manipulation
 	int vert_new();