[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [35886] branches/bmesh/blender/source/ blender: =bmesh=
Joseph Eagar
joeedh at gmail.com
Wed Mar 30 03:36:43 CEST 2011
Revision: 35886
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=35886
Author: joeedh
Date: 2011-03-30 01:36:42 +0000 (Wed, 30 Mar 2011)
Log Message:
-----------
=bmesh=
Multires interpolation is now nearly perfect, but has some
issues on faces whose angle to each other isn't relatively
shallow (probably need to use some sort of fast spatial structure
to more accurately project multires points).
It also doesn't work super well with bevel (mostly due to a
flipped normals bug in bevel I need to get around to fixing).
And, for some reason extrude tends to explode the multires
geometry (it should just be copying it).
Since edge cut doesn't do anything yet with face interpolation,
cuts that arn't exactly centered will move the underlying multires
geometry around a bit..
Modified Paths:
--------------
branches/bmesh/blender/source/blender/blenkernel/intern/multires.c
branches/bmesh/blender/source/blender/bmesh/intern/bmesh_interp.c
Modified: branches/bmesh/blender/source/blender/blenkernel/intern/multires.c
===================================================================
--- branches/bmesh/blender/source/blender/blenkernel/intern/multires.c 2011-03-29 21:00:42 UTC (rev 35885)
+++ branches/bmesh/blender/source/blender/blenkernel/intern/multires.c 2011-03-30 01:36:42 UTC (rev 35886)
@@ -1116,7 +1116,7 @@
float urat, vrat, uopp;
float d[4][3], d2[2][3];
- if (!disps)
+ if (!disps || isnan(u) || isnan(v))
return;
if(u < 0)
Modified: branches/bmesh/blender/source/blender/bmesh/intern/bmesh_interp.c
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/intern/bmesh_interp.c 2011-03-29 21:00:42 UTC (rev 35885)
+++ branches/bmesh/blender/source/blender/bmesh/intern/bmesh_interp.c 2011-03-30 01:36:42 UTC (rev 35886)
@@ -221,120 +221,13 @@
BLI_array_free(blocks);
}
-/***** multires interpolation*****
+/****some math stuff for dealing with doubles, put here to
+ avoid merge errors - joeedh ****/
-mdisps is a grid of displacements, ordered thus:
+#define VECMUL(a, b) (((a)[0] = (a)[0] * (b)), ((a)[1] = (a)[1] * (b)), ((a)[2] = (a)[2] * (b)))
+#define VECADD2(a, b) (((a)[0] = (a)[0] + (b)[0]), ((a)[1] = (a)[1] + (b)[1]), ((a)[2] = (a)[2] + (b)[2]))
+#define VECSUB2(a, b) (((a)[0] = (a)[0] - (b)[0]), ((a)[1] = (a)[1] - (b)[1]), ((a)[2] = (a)[2] - (b)[2]))
-v1/center -- v4/next -> x
-| |
-| |
-v2/prev ---- v3/cur
-|
-V
-
-y
-*/
-static int compute_mdisp_quad(BMLoop *l, float v1[3], float v2[3], float v3[3], float v4[3], float e1[3], float e2[3])
-{
- float cent[3] = {0.0f, 0.0f, 0.0f}, n[3], p[3];
- BMLoop *l2;
-
- /*computer center*/
- l2 = bm_firstfaceloop(l->f);
- do {
- add_v3_v3(cent, l2->v->co);
- l2 = l2->next;
- } while (l2 != bm_firstfaceloop(l->f));
-
- mul_v3_fl(cent, 1.0/(float)l->f->len);
-
- add_v3_v3v3(p, l->prev->v->co, l->v->co);
- mul_v3_fl(p, 0.5);
- add_v3_v3v3(n, l->next->v->co, l->v->co);
- mul_v3_fl(n, 0.5);
-
- copy_v3_v3(v1, cent);
- copy_v3_v3(v2, p);
- copy_v3_v3(v3, l->v->co);
- copy_v3_v3(v4, n);
-
- sub_v3_v3v3(e1, v2, v1);
- sub_v3_v3v3(e2, v3, v4);
-
- return 1;
-}
-
-
-int isect_ray_tri_threshold_v3_uvw(float p1[3], float d[3], float _v0[3], float _v1[3], float _v2[3], float *lambda, float uv[3], float threshold)
-{
- float p[3], s[3], e1[3], e2[3], q[3];
- float a, f, u, v;
- float du = 0, dv = 0;
- float v0[3], v1[3], v2[3], c[3];
-
- /*expand triangle a bit*/
-#if 1
- cent_tri_v3(c, _v0, _v1, _v2);
- sub_v3_v3v3(v0, _v0, c);
- sub_v3_v3v3(v1, _v1, c);
- sub_v3_v3v3(v2, _v2, c);
- mul_v3_fl(v0, 1.0+threshold);
- mul_v3_fl(v1, 1.0+threshold);
- mul_v3_fl(v2, 1.0+threshold);
- add_v3_v3(v0, c);
- add_v3_v3(v1, c);
- add_v3_v3(v2, c);
-#else
- copy_v3_v3(v0, _v0);
- copy_v3_v3(v1, _v1);
- copy_v3_v3(v2, _v2);
-#endif
-
- sub_v3_v3v3(e1, v1, v0);
- sub_v3_v3v3(e2, v2, v0);
-
- cross_v3_v3v3(p, d, e2);
- a = dot_v3v3(e1, p);
- if ((a > -0.000001) && (a < 0.000001)) return 0;
- f = 1.0f/a;
-
- sub_v3_v3v3(s, p1, v0);
-
- cross_v3_v3v3(q, s, e1);
- *lambda = f * dot_v3v3(e2, q);
- if ((*lambda < 0.0+FLT_EPSILON)) return 0;
-
- u = f * dot_v3v3(s, p);
- v = f * dot_v3v3(d, q);
-
- if (u < 0) du = u;
- if (u > 1) du = u - 1;
- if (v < 0) dv = v;
- if (v > 1) dv = v - 1;
- if (u > 0 && v > 0 && u + v > 1)
- {
- float t = u + v - 1;
- du = u - t/2;
- dv = v - t/2;
- }
-
- mul_v3_fl(e1, du);
- mul_v3_fl(e2, dv);
-
- if (dot_v3v3(e1, e1) + dot_v3v3(e2, e2) > threshold * threshold)
- {
- return 0;
- }
-
- if(uv) {
- uv[0]= u;
- uv[1]= v;
- uv[2]= fabs(1.0-u-v);
- }
-
- return 1;
-}
-
/* find closest point to p on line through l1,l2 and return lambda,
* where (0 <= lambda <= 1) when cp is in the line segement l1,l2
*/
@@ -366,6 +259,11 @@
}
}
+static double len_v3_d(const double a[3])
+{
+ return sqrt(INPR(a, a));
+}
+
static double len_v3v3_d(const double a[3], const double b[3])
{
double d[3];
@@ -374,61 +272,181 @@
return sqrt(INPR(d, d));
}
+static void cent_quad_v3_d(double *cent, double *v1, double *v2, double *v3, double *v4)
+{
+ cent[0]= 0.25*(v1[0]+v2[0]+v3[0]+v4[0]);
+ cent[1]= 0.25*(v1[1]+v2[1]+v3[1]+v4[1]);
+ cent[2]= 0.25*(v1[2]+v2[2]+v3[2]+v4[2]);
+}
+
+static void cent_tri_v3_d(double *cent, double *v1, double *v2, double *v3)
+{
+ cent[0]= 0.33333*(v1[0]+v2[0]+v3[0]);
+ cent[1]= 0.33333*(v1[1]+v2[1]+v3[1]);
+ cent[2]= 0.33333*(v1[2]+v2[2]+v3[2]);
+}
+
+static void cross_v3_v3v3_d(double r[3], const double a[3], const double b[3])
+{
+ r[0]= a[1]*b[2] - a[2]*b[1];
+ r[1]= a[2]*b[0] - a[0]*b[2];
+ r[2]= a[0]*b[1] - a[1]*b[0];
+}
+
+/* distance v1 to line-piece v2-v3 */
+double dist_to_line_segment_v2_d(double v1[3], double v2[3], double v3[3])
+{
+ double labda, rc[2], pt[2], len;
+
+ rc[0]= v3[0]-v2[0];
+ rc[1]= v3[1]-v2[1];
+ len= rc[0]*rc[0]+ rc[1]*rc[1];
+ if(len==0.0) {
+ rc[0]= v1[0]-v2[0];
+ rc[1]= v1[1]-v2[1];
+ return sqrt(rc[0]*rc[0]+ rc[1]*rc[1]);
+ }
+
+ labda= (rc[0]*(v1[0]-v2[0]) + rc[1]*(v1[1]-v2[1]))/len;
+ if(labda<=0.0) {
+ pt[0]= v2[0];
+ pt[1]= v2[1];
+ }
+ else if(labda>=1.0) {
+ pt[0]= v3[0];
+ pt[1]= v3[1];
+ }
+ else {
+ pt[0]= labda*rc[0]+v2[0];
+ pt[1]= labda*rc[1]+v2[1];
+ }
+
+ rc[0]= pt[0]-v1[0];
+ rc[1]= pt[1]-v1[1];
+ return sqrt(rc[0]*rc[0]+ rc[1]*rc[1]);
+}
+
+
+MINLINE double line_point_side_v2_d(const double *l1, const double *l2, const double *pt)
+{
+ return ((l1[0]-pt[0]) * (l2[1]-pt[1])) -
+ ((l2[0]-pt[0]) * (l1[1]-pt[1]));
+}
+
+/* point in quad - only convex quads */
+int isect_point_quad_v2_d(double pt[2], double v1[2], double v2[2], double v3[2], double v4[2])
+{
+ if (line_point_side_v2_d(v1,v2,pt)>=0.0) {
+ if (line_point_side_v2_d(v2,v3,pt)>=0.0) {
+ if (line_point_side_v2_d(v3,v4,pt)>=0.0) {
+ if (line_point_side_v2_d(v4,v1,pt)>=0.0) {
+ return 1;
+ }
+ }
+ }
+ } else {
+ if (! (line_point_side_v2_d(v2,v3,pt)>=0.0)) {
+ if (! (line_point_side_v2_d(v3,v4,pt)>=0.0)) {
+ if (! (line_point_side_v2_d(v4,v1,pt)>=0.0)) {
+ return -1;
+ }
+ }
+ }
+ }
+
+ return 0;
+}
+
+/***** multires interpolation*****
+
+mdisps is a grid of displacements, ordered thus:
+
+v1/center -- v4/next -> x
+| |
+| |
+v2/prev ---- v3/cur
+|
+V
+
+y
+*/
+
+static int compute_mdisp_quad(BMLoop *l, double v1[3], double v2[3], double v3[3], double v4[3], double e1[3], double e2[3])
+{
+ double cent[3] = {0.0, 0.0, 0.0}, n[3], p[3];
+ BMLoop *l2;
+
+ /*computer center*/
+ l2 = bm_firstfaceloop(l->f);
+ do {
+ VECADD2(cent, l2->v->co);
+ l2 = l2->next;
+ } while (l2 != bm_firstfaceloop(l->f));
+
+ VECMUL(cent, (1.0/(double)l->f->len));
+
+ VECADD(p, l->prev->v->co, l->v->co);
+ VECMUL(p, 0.5);
+ VECADD(n, l->next->v->co, l->v->co);
+ VECMUL(n, 0.5);
+
+ VECCOPY(v1, cent);
+ VECCOPY(v2, p);
+ VECCOPY(v3, l->v->co);
+ VECCOPY(v4, n);
+
+ VECSUB(e1, v2, v1);
+ VECSUB(e2, v3, v4);
+
+ return 1;
+}
+
/*funnily enough, I think this is identical to face_to_crn_interp, heh*/
double quad_coord(double aa[3], double bb[3], double cc[3], double dd[3], int a1, int a2)
{
- double x, y, z, f1, f2;
+ double x, y, z, c, f1, f2;
x = aa[a1]*cc[a2]-cc[a1]*aa[a2];
y = aa[a1]*dd[a2]+bb[a1]*cc[a2]-cc[a1]*bb[a2]-dd[a1]*aa[a2];
z = bb[a1]*dd[a2]-dd[a1]*bb[a2];
-
- if (fabs(2*(x-y+z)) > DBL_EPSILON*1000.0) {
+ if (fabs(2*(x-y+z)) > DBL_EPSILON*10.0) {
f1 = (sqrt(y*y-4.0*x*z) - y + 2.0*z) / (2.0*(x-y+z));
f2 = (-sqrt(y*y-4.0*x*z) - y + 2.0*z) / (2.0*(x-y+z));
} else f1 = -1;
- if (isnan(f1) || f1 == -1.0) {
- int i, tot=200;
+ if (isnan(f1) || f1 == -1.0 || f1 < 0.0 || f1 > 1.0+DBL_EPSILON*50) {
+ int i, tot=55;
double d, lastd=-1.0;
- //return -1.0f;
-#if 0
- double co[3], p[3] = {0.0, 0.0, 0.0};
- closest_to_line_segment_v3_d(co, p, aa, bb);
-
- return len_v3v3_d(bb, co) / len_v3v3_d(aa, bb);
-#endif
-#if 1
- f1 = 1.0;
- f2 = 0.0;
+ /*this is a bisecting root solver that's fudged to avoid false
+ roots*/
+ f1 = 0.0;
+ f2 = 0.5;
for (i=0; i<tot; i++) {
- double f3, v1[3], v2[3], co[3], p[3] = {0.0, 0.0, 0.0};
+ double f3, v1[3], v2[3], origin[3] = {0.0, 0.0, 0.0};
VECINTERP(v1, aa, bb, f1);
VECINTERP(v2, cc, dd, f1);
- closest_to_line_segment_v3_d(co, p, v1, v2);
- d = len_v3v3_d(co, p);
+ d = dist_to_line_segment_v2_d(origin, v1, v2);
f3 = f1;
- if (d < lastd) {
- f1 += (f1-f2)*0.5;
+ if (d < lastd && i != 0) {
+ f1 += (f1 - f2)*0.75;
} else {
- f1 -= (f1-f2)*0.5;
+ f1 -= (f1 - f2)*0.5;
}
-
+
f2 = f3;
lastd = d;
}
- if (d > 0.0000001 || f1 < -FLT_EPSILON*1000 || f1 >= 1.0+FLT_EPSILON*100)
+ if (d > 0.0001 || f1 < 0.0 || f1 >= 1.0+DBL_EPSILON*10)
return -1.0;
CLAMP(f1, 0.0, 1.0+DBL_EPSILON);
return 1.0 - f1;
-#endif
}
f1 = MIN2(fabs(f1), fabs(f2));
@@ -437,107 +455,75 @@
return f1;
}
-void quad_co(float *x, float *y, float v1[3], float v2[3], float v3[3], float v4[3], float p[3], float n[3])
+int quad_co(double *x, double *y, double v1[3], double v2[3], double v3[3], double v4[3], double p[3], float n[3])
{
- float projverts[4][3];
- double dverts[4][3];
- int i;
+ float projverts[5][3];
+ double xn, yn, zn, dprojverts[4][3], origin[3]={0.0f, 0.0f, 0.0f};
+ int i, ax, ay;
+
+ /*project points into 2d along normal*/
+ VECCOPY(projverts[0], v1);
+ VECCOPY(projverts[1], v2);
+ VECCOPY(projverts[2], v3);
+ VECCOPY(projverts[3], v4);
+ VECCOPY(projverts[4], p);
- sub_v3_v3v3(projverts[0], v1, p);
- sub_v3_v3v3(projverts[1], v2, p);
- sub_v3_v3v3(projverts[2], v3, p);
- sub_v3_v3v3(projverts[3], v4, p);
-
/*rotate*/
- poly_rotate_plane(n, projverts, 4);
+ poly_rotate_plane(n, projverts, 5);
/*flatten*/
- for (i=0; i<4; i++) projverts[i][2] = 0.0f;
+ for (i=0; i<5; i++) projverts[i][2] = 0.0f;
- VECCOPY(dverts[0], projverts[0]);
- VECCOPY(dverts[1], projverts[1]);
- VECCOPY(dverts[2], projverts[2]);
- VECCOPY(dverts[3], projverts[3]);
+ /*subtract origin*/
+ for (i=0; i<4; i++) {
+ VECSUB2(projverts[i], projverts[4]);
+ }
- *y = quad_coord(dverts[1], dverts[0], dverts[2], dverts[3], 0, 1);
- *x = quad_coord(dverts[2], dverts[1], dverts[3], dverts[0], 0, 1);
+ VECCOPY(dprojverts[0], projverts[0]);
+ VECCOPY(dprojverts[1], projverts[1]);
+ VECCOPY(dprojverts[2], projverts[2]);
+ VECCOPY(dprojverts[3], projverts[3]);
+
+ if (!isect_point_quad_v2_d(origin, dprojverts[0], dprojverts[1], dprojverts[2], dprojverts[3]))
+ return 0;
+
+ *y = quad_coord(dprojverts[1], dprojverts[0], dprojverts[2], dprojverts[3], 0, 1);
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list