[Bf-blender-cvs] [dc9a5e7] soc-2014-nurbs: Updates to GridMesh (int indexes, now verts keep backpointers to first vert
Jonathan deWerd
noreply at git.blender.org
Fri Jun 27 08:14:42 CEST 2014
Commit: dc9a5e71ebce63dc78032ec06ffcfeac93096d6d
Author: Jonathan deWerd
Date: Mon Jun 23 22:54:39 2014 -0400
https://developer.blender.org/rBdc9a5e71ebce63dc78032ec06ffcfeac93096d6d
Updates to GridMesh (int indexes, now verts keep backpointers to first vert
===================================================================
M PolyTest/GridMesh.cpp
M PolyTest/GridMesh.h
===================================================================
diff --git a/PolyTest/GridMesh.cpp b/PolyTest/GridMesh.cpp
index bd0010a..ade9cef 100644
--- a/PolyTest/GridMesh.cpp
+++ b/PolyTest/GridMesh.cpp
@@ -6,54 +6,419 @@
// Copyright (c) 2014 a.b.c. All rights reserved.
//
+#include <cmath>
#include "GridMesh.h"
-GreinerV2f *GreinerV2f::firstVert() {
- if (!prev || isBackbone) return this;
- GreinerV2f *v = this;
- while (v->prev) {
- v = v->prev;
- if (v->isBackbone) return v;
+static bool debug = 1;
+float GridMesh::tolerance = 1e-5;
+
+
+/*struct GridMesh {
+ // Vertex storage. Example: "int prev" in a GreinerV2f refers to v[prev].
+ // v[0] is defined to be invalid and filled with the telltale location (-42,-42)
+ GreinerV2f *v;
+ float llx, lly, urx, ury; // Coordinates of lower left and upper right grid corners
+ float 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(float lowerleft_x, float lowerleft_y,
+ float upperright_x, float upperright_y,
+ int num_x_cells, int num_y_cells);
+
+ void merge_poly(GreinerV2f *mpoly);
+
+ GreinerV2f *vert_new();
+ int vert_id(GreinerV2f *vert) {return int(vert-v);}
+ GreinerV2f *poly_for_cell(int x, int y, bool *isTrivial);
+ GreinerV2f *poly_for_cell(float x, float y, bool *isTrivial);
+ GreinerV2f *poly_first_vert(GreinerV2f *anyvert);
+ GreinerV2f *poly_last_vert(GreinerV2f *anyvert);
+ bool poly_is_cyclic(GreinerV2f *poly);
+ bool poly_set_cyclic(GreinerV2f *poly);
+};*/
+
+
+
+GridMesh::GridMesh(float lowerleft_x, float lowerleft_y,
+ float upperright_x, float upperright_y,
+ int num_x_cells, int num_y_cells) {
+ llx = lowerleft_x; lly = lowerleft_y;
+ urx = upperright_x; ury = upperright_y;
+ nx = num_x_cells; ny = num_y_cells;
+ double Dx = urx-llx;
+ double Dy = ury-lly;
+ dx = Dx/nx;
+ dy = Dy/ny;
+ inv_dx = 1.0/dx;
+ inv_dy = 1.0/dy;
+ v_capacity = nx*ny*4 + 256;
+ v_count = nx*ny*4;
+ v = (GreinerV2f*)malloc(sizeof(GreinerV2f)*v_capacity);
+ new (v) GreinerV2f();
+ v->x = v->y = -1234;
+ for (int j=0; j<ny; j++) {
+ double b = lly + j*dy;
+ double t = (j==ny-1)? ury : lly + (j+1)*dy;
+ for (int i=0; i<nx; i++) {
+ double l = llx + i*dx;
+ double r = (i==nx-1)? urx : llx + (i+1)*dx;
+ GreinerV2f *v1 = poly_for_cell(i, j);
+ GreinerV2f *v2 = v1+1;
+ GreinerV2f *v3 = v1+2;
+ GreinerV2f *v4 = v1+3;
+ new (v1) GreinerV2f(); v1->x=l; v1->y=b;
+ new (v2) GreinerV2f(); v1->x=r; v1->y=b;
+ new (v3) GreinerV2f(); v1->x=r; v1->y=t;
+ new (v4) GreinerV2f(); v1->x=l; v1->y=t;
+ int iv1 = vert_id(v1);
+ int iv2 = iv1+1;
+ int iv3 = iv1+2;
+ int iv4 = iv1+3;
+ v1->next = iv2; v2->prev = iv1; v1->first = iv1;
+ v2->next = iv3; v3->prev = iv2; v2->first = iv1;
+ v3->next = iv4; v4->prev = iv3; v3->first = iv1;
+ v4->next = iv1; v1->prev = iv4; v4->first = iv1;
+ }
+ }
+}
+
+GreinerV2f *GridMesh::vert_new() {
+ if (v_count>=v_capacity) {
+ long newcap = v_capacity*2;
+ v = (GreinerV2f*)realloc(v, newcap);
+ v_capacity = newcap;
}
- return v;
+ GreinerV2f *newvert = new (v+v_count) GreinerV2f();
+ v_count++;
+ return newvert;
}
-GreinerV2f *GreinerV2f::lastVert() {
- if (!next) return this;
- if (next->isBackbone) return this;
- GreinerV2f *v = this;
- while (v->next) {
- v = v->next;
- if (v->isBackbone) return v;
+GreinerV2f *GridMesh::vert_new(GreinerV2f *prev, GreinerV2f *next) {
+ GreinerV2f *ret = vert_new();
+ if (prev) {
+ ret->first = prev->first;
+ ret->prev = vert_id(prev);
+ prev->next = vert_id(ret);
+ }
+ if (next) {
+ ret->first = next->first;
+ ret->next = vert_id(next);
+ next->prev = vert_id(ret);
}
- return v;
+ return ret;
}
-GreinerV2f *GreinerV2f::nextPolygon() {
- return firstVert()->nextPoly;
+
+GreinerV2f *GridMesh::poly_first_vert(GreinerV2f *vert) {
+ GreinerV2f *v2 = vert;
+ while (v2->prev) {
+ if (v2->first==vert_id(v2)) return v;
+ v2 = &v[v2->prev];
+ }
+ return v2;
}
-GreinerV2f *GreinerV2f::vertAt(float x, float y) {
- for(GreinerV2f *v = firstVert(); v; v=v->next) {
- if (fabs(x-v->x)+fabs(y-v->y)<tolerance) return v;
+GreinerV2f *GridMesh::poly_last_vert(GreinerV2f *vert) {
+ GreinerV2f *v2 = vert;
+ while (v2->next) {
+ GreinerV2f *next = &v[v2->next];
+ if (v2->first==vert_id(v2)) return v2;
+ v2 = next;
}
- return nullptr;
+ return v2;
}
-bool GreinerV2f::isCyclic() {
- if (!prev || !next) return false;
- return bool(firstVert()->prev);
+GreinerV2f *GridMesh::poly_next(GreinerV2f *anyvert) {
+ return &v[poly_first_vert(anyvert)->next_poly];
}
-void GreinerV2f::setCyclic(bool cyc) {
- if (cyc==isCyclic()) return;
- GreinerV2f *first = firstVert();
- GreinerV2f *last = lastVert();
+bool GridMesh::poly_is_cyclic(GreinerV2f *poly) {
+ if (!poly->next) return false;
+ return bool(poly_first_vert(poly)->prev);
+}
+
+void GridMesh::poly_set_cyclic(GreinerV2f *poly, bool cyc) {
+ if (cyc==poly_is_cyclic(poly)) return;
+ GreinerV2f *first = poly_first_vert(poly);
+ GreinerV2f *last = poly_last_vert(poly);
if (cyc) {
- first->prev = last;
- last->next = first;
+ first->prev = vert_id(last);
+ last->next = vert_id(first);
} else {
- first->prev = nullptr;
- last->next = nullptr;
+ first->prev = 0;
+ last->next = 0;
+ }
+}
+
+GreinerV2f *GridMesh::poly_for_cell(int x, int y) {
+ return &v[1+4*(y*nx+x)];
+}
+
+GreinerV2f *GridMesh::poly_for_cell(float fx, float fy) {
+ int x = (fx-llx)*inv_dx;
+ int y = (fy-lly)*inv_dy;
+ return &v[1+4*(y*nx+x)];
+}
+
+int GridMesh::poly_num_edges(GreinerV2f *poly) {
+ poly = poly_first_vert(poly);
+ int ret = 0;
+ while (poly->next) {
+ ret++;
+ GreinerV2f *next = &v[poly->next];
+ if (next->first==vert_id(next)) break;
+ poly = next;
+ }
+ return ret;
+}
+
+GreinerV2f *GridMesh::poly_vert_at(GreinerV2f *anyvert, float x, float y) {
+ bool first_iter = true;
+ for(GreinerV2f *vert = poly_first_vert(anyvert); vert; vert=&v[vert->next]) {
+ if (fabs(x-vert->x)+fabs(y-vert->y)<tolerance) return vert;
+ if (first_iter) {
+ first_iter = false;
+ } else {
+ if (vert->is_backbone) break;
+ }
}
-}
\ No newline at end of file
+ return nullptr;
+}
+
+void GridMesh::add_verts_at_intersections(GreinerV2f *mpoly) {
+ std::vector<std::pair<int,int>> bottom_edges, left_edges, integer_cells;
+ mpoly = poly_first_vert(mpoly);
+ GreinerV2f *v1 = mpoly;
+ float v1x=v1->x, v1y=v1->y;
+ while (v1->next) {
+ GreinerV2f *v2 = &v[mpoly->next];
+ float v2x=v2->x, v2y=v2->y;
+ bottom_edges.clear();
+ left_edges.clear();
+ integer_cells.clear();
+ find_integer_cell_line_intersections(v1x,v1y,v2x,v2y,&bottom_edges,&left_edges,&integer_cells);
+ bool intersects_grid_edges = bottom_edges.size()+left_edges.size()>0;
+ bool trivial = true;
+ for (std::pair<int,int> i : integer_cells) {
+ trivial = poly_for_cell(i.first, i.second)->is_trivial;
+ if (!trivial) break;
+ }
+ if (trivial) {
+ if (intersects_grid_edges) {
+ //Loop through left edges, insert
+ //Loop through bottom edges, insert
+ }
+ } else {
+ //All pairs, baby!
+ }
+ v1=v2; v1x=v2x; v1y=v2y;
+ if (v1->is_backbone) break;
+ }
+}
+
+
+// Fast float->int, courtesy of http://stereopsis.com/sree/fpu2006.html
+// 5x faster on x86. It's not in the hot loop anymore so it probably
+// doesn't really matter. Todo: test and see.
+const double _xs_doublemagic = 6755399441055744.0; //2^52 * 1.5, uses limited precisicion to floor
+const double _xs_doublemagicdelta = (1.5e-8); //almost .5f = .5f + 1e^(number of exp bit)
+const double _xs_doublemagicroundeps = (.5f-_xs_doublemagicdelta); //almost .5f = .5f - 1e^(number of exp bit)
+inline static int xs_CRoundToInt(double val) {
+ val = val + _xs_doublemagic;
+ return ((int*)&val)[0]; // 0 for little endian (ok), 1 for big endian (?)
+ // return int32(floor(val+.5)); //Alternative implementation if the trick is buggy
+}
+inline static int xs_FloorToInt(double val) {
+ //return xs_CRoundToInt(val-_xs_doublemagicroundeps);
+ return floor(val); //Alternative implementation if the trick is buggy
+}
+
+void find_integer_cell_line_intersections(float x0, float y0, float x1, float y1,
+ std::vector<std::pair<int,int>> *bottom_edges,
+ std::vector<std::pair<int,int>> *left_edges,
+ std::vector<std::pair<int,int>> *integer_cells) {
+ if (x0>x1) { // Ensure order is left to right
+ std::swap(x0,x1);
+ std::swap(y0,y1);
+ }
+ int cx0=xs_FloorToInt(x0), cy0=xs_FloorToInt(y0), cx1=xs_FloorToInt(x1), cy1=xs_FloorToInt(y1);
+ // Line segments smaller than a cell's minimum dimension should always hit these trivial cases
+ if (cy0==cy1) { //Horizontal or single-cell
+ if (integer_cells) {
+ for (int i=cx0; i<=cx1; i++)
+ integer_cells->push_back(std::make_pair(i,cy0));
+ }
+ if (left_edges) {
+ for (int i=cx0+1; i<=cx1; i++)
+ left_edges->push_back(std::make_pair(i,cy0));
+ }
+ return;
+ } else if (cx0==cx1) { // Vertical
+ if (integer_cells) {
+ if (cy0<cy1) {
+ for (int i=cy0; i<=cy1; i++)
+ integer_cells->push_back(std::make_pair(cx0,i));
+ } else {
+ for (int i=cy1; i<=cy0; i++)
+ integer_cells->push_back(std::make_pair(cx1,i));
+ }
+ }
+ if (bottom_edges) {
+ if (cy0<cy1) {
+ for (int i=cy0+1; i<=cy1; i++)
+ bottom_edges->push_back(std::make_pair(cx0,i));
+ }
+ else {
+ for (int i=cy1+1; i<=cy0; i++)
+ bottom_edges->push_back(std::make_pair(cx1,i));
+ }
+ }
+ return;
+ }
+ // Line segments that make us think :)
+ double m = (y1-y0)/(x1-x0);
+ double residue_x=(cx0+1)-x0;
+ double rhy = y0+residue_x*m; // y coord at the right edge of the cell
+ if (cy1>cy0) { //Upwards and to the right
+ int j; float jf;
+ j=cy0; jf=cy0;
+ for (int i=cx0; i<=cx1; i++) {
+ if (i==cx1) rhy = y1;
+ if (integer_cells) integer_cells->push_back(std::make_pair(i,j));
+ while (jf+1<rhy) {
+ j+=1; jf+=1.0;
+ if (integer_cells) integer_cells->push_back(std::make_pair(i,j));
+ if (bottom_edges) bottom_edges->push_back(std::make_pair(i,j));
+ }
+ if (i!=cx1 && left_edges) left_edges->push_back(std::make_pair(i+1, j));
+ rhy += m;
+ }
+ } else { //Downwards and to the right
+ int j; float jf;
+ j=cy0; jf=cy0;
+ for (int i=cx0; i<=c
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list