[Bf-blender-cvs] [b2ddd70] soc-2014-nurbs: Added dumber+faster grid propagator, fixed displist crash bug for >~10x10 tessellation grids.
Jonathan deWerd
noreply at git.blender.org
Wed Jul 16 06:35:04 CEST 2014
Commit: b2ddd70949e6681e5244b0fc0414560f47a8c6ce
Author: Jonathan deWerd
Date: Mon Jul 14 21:46:58 2014 -0400
https://developer.blender.org/rBb2ddd70949e6681e5244b0fc0414560f47a8c6ce
Added dumber+faster grid propagator, fixed displist crash bug for >~10x10 tessellation grids.
===================================================================
M source/blender/blenkernel/intern/curve.cpp
M source/blender/blenkernel/intern/surf_gridmesh.cpp
M source/blender/blenkernel/intern/surf_gridmesh.h
M tests/interactive/nurbs_trimtess.cpp
===================================================================
diff --git a/source/blender/blenkernel/intern/curve.cpp b/source/blender/blenkernel/intern/curve.cpp
index 065fc1d..3ddbe01 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 cfd7cae..ec2fbec 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 2f5636b..50ff336 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 usag
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list