[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [33605] trunk/blender/source/blender: New math util funcitons:
Sergey Sharybin
g.ulairi at gmail.com
Sat Dec 11 22:27:39 CET 2010
Revision: 33605
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=33605
Author: nazgul
Date: 2010-12-11 22:27:39 +0100 (Sat, 11 Dec 2010)
Log Message:
-----------
New math util funcitons:
- equals_v2v2
- project_v2_v2v2
- isect_seg_seg_v2_point
which would be necessery for my further multires interpolation commit
M_Geometry_LineIntersect2D now uses isect_seg_seg_v2_point(). Behaviour of this
function was changed a bit -- it haven't returned intersection point in several
cases when two segments are making angle.
Modified Paths:
--------------
trunk/blender/source/blender/blenlib/BLI_math_geom.h
trunk/blender/source/blender/blenlib/BLI_math_vector.h
trunk/blender/source/blender/blenlib/intern/math_geom.c
trunk/blender/source/blender/blenlib/intern/math_vector.c
trunk/blender/source/blender/blenlib/intern/math_vector_inline.c
trunk/blender/source/blender/python/generic/mathutils_geometry.c
Modified: trunk/blender/source/blender/blenlib/BLI_math_geom.h
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_math_geom.h 2010-12-11 20:01:34 UTC (rev 33604)
+++ trunk/blender/source/blender/blenlib/BLI_math_geom.h 2010-12-11 21:27:39 UTC (rev 33605)
@@ -73,6 +73,7 @@
int isect_line_line_v2(float a1[2], float a2[2], float b1[2], float b2[2]);
int isect_line_line_v2_short(short a1[2], short a2[2], short b1[2], short b2[2]);
+int isect_seg_seg_v2_point(float v1[2], float v2[2], float v3[2], float v4[2], float vi[2]);
/* Returns the number of point of interests
* 0 - lines are colinear
Modified: trunk/blender/source/blender/blenlib/BLI_math_vector.h
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_math_vector.h 2010-12-11 20:01:34 UTC (rev 33604)
+++ trunk/blender/source/blender/blenlib/BLI_math_vector.h 2010-12-11 21:27:39 UTC (rev 33605)
@@ -124,6 +124,7 @@
MINLINE int is_zero_v3(const float a[3]);
MINLINE int is_one_v3(const float a[3]);
+MINLINE int equals_v2v2(const float *v1, const float *v2);
MINLINE int equals_v3v3(const float a[3], const float b[3]);
MINLINE int compare_v3v3(const float a[3], const float b[3], const float limit);
MINLINE int compare_len_v3v3(const float a[3], const float b[3], const float limit);
@@ -149,6 +150,7 @@
/********************************* Geometry **********************************/
+void project_v2_v2v2(float c[2], const float v1[2], const float v2[2]);
void project_v3_v3v3(float r[3], const float p[3], const float n[3]);
void reflect_v3_v3v3(float r[3], const float v[3], const float n[3]);
void ortho_basis_v3v3_v3(float r1[3], float r2[3], const float a[3]);
Modified: trunk/blender/source/blender/blenlib/intern/math_geom.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/math_geom.c 2010-12-11 20:01:34 UTC (rev 33604)
+++ trunk/blender/source/blender/blenlib/intern/math_geom.c 2010-12-11 21:27:39 UTC (rev 33605)
@@ -282,6 +282,81 @@
return 0;
}
+/* get intersection point of two 2D segments and return intersection type:
+ -1: colliniar
+ 1: intersection */
+int isect_seg_seg_v2_point(float v1[2], float v2[2], float v3[2], float v4[2], float vi[2])
+{
+ float a1, a2, b1, b2, c1, c2, d;
+ float u, v;
+ const float eps= 0.000001f;
+
+ a1= v2[0]-v1[0];
+ b1= v4[0]-v3[0];
+ c1= v1[0]-v4[0];
+
+ a2= v2[1]-v1[1];
+ b2= v4[1]-v3[1];
+ c2= v1[1]-v4[1];
+
+ d= a1*b2-a2*b1;
+
+ if(d==0) {
+ if(a1*c2-a2*c1==0.0f && b1*c2-b2*c1==0.0f) { /* equal lines */
+ float a[2], b[2], c[2];
+ float u2;
+
+ if(len_v2v2(v1, v2)==0.0f) {
+ if(len_v2v2(v3, v4)>eps) {
+ /* use non-point segment as basis */
+ SWAP(float, v1[0], v3[0]);
+ SWAP(float, v1[1], v3[1]);
+ SWAP(float, v2[0], v4[0]);
+ SWAP(float, v2[1], v4[1]);
+ } else { /* both of segments are points */
+ if(equals_v2v2(v1, v3)) { /* points are equal */
+ copy_v2_v2(vi, v1);
+ return 1;
+ }
+
+ /* two different points */
+ return -1;
+ }
+ }
+
+ sub_v2_v2v2(a, v3, v1);
+ sub_v2_v2v2(b, v2, v1);
+ sub_v2_v2v2(c, v2, v1);
+ u= dot_v2v2(a, b) / dot_v2v2(c, c);
+
+ sub_v2_v2v2(a, v4, v1);
+ u2= dot_v2v2(a, b) / dot_v2v2(c, c);
+
+ if(u>u2) SWAP(float, u, u2);
+
+ if(u>1.0f+eps || u2<-eps) return -1; /* non-ovlerlapping segments */
+ else if(maxf(0.0f, u) == minf(1.0f, u2)){ /* one common point: can return result */
+ interp_v2_v2v2(vi, v1, v2, maxf(0, u));
+ return 1;
+ }
+ }
+
+ /* lines are colliniar */
+ return -1;
+ }
+
+ u= (c2*b1-b2*c1)/d;
+ v= (c1*a2-a1*c2)/d;
+
+ if(u>=-eps && u<=1.0f+eps && v>=-eps && v<=1.0f+eps) { /* intersection */
+ interp_v2_v2v2(vi, v1, v2, u);
+ return 1;
+ }
+
+ /* out of segment intersection */
+ return -1;
+}
+
/*
-1: colliniar
1: intersection
Modified: trunk/blender/source/blender/blenlib/intern/math_vector.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/math_vector.c 2010-12-11 20:01:34 UTC (rev 33604)
+++ trunk/blender/source/blender/blenlib/intern/math_vector.c 2010-12-11 21:27:39 UTC (rev 33605)
@@ -231,6 +231,16 @@
/********************************* Geometry **********************************/
/* Project v1 on v2 */
+void project_v2_v2v2(float c[2], const float v1[2], const float v2[2])
+{
+ float mul;
+ mul = dot_v2v2(v1, v2) / dot_v2v2(v2, v2);
+
+ c[0] = mul * v2[0];
+ c[1] = mul * v2[1];
+}
+
+/* Project v1 on v2 */
void project_v3_v3v3(float c[3], const float v1[3], const float v2[3])
{
float mul;
Modified: trunk/blender/source/blender/blenlib/intern/math_vector_inline.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/math_vector_inline.c 2010-12-11 20:01:34 UTC (rev 33604)
+++ trunk/blender/source/blender/blenlib/intern/math_vector_inline.c 2010-12-11 21:27:39 UTC (rev 33605)
@@ -429,6 +429,11 @@
return (v[0] == 1 && v[1] == 1 && v[2] == 1);
}
+MINLINE int equals_v2v2(const float *v1, const float *v2)
+{
+ return ((v1[0]==v2[0]) && (v1[1]==v2[1]));
+}
+
MINLINE int equals_v3v3(const float *v1, const float *v2)
{
return ((v1[0]==v2[0]) && (v1[1]==v2[1]) && (v1[2]==v2[2]));
Modified: trunk/blender/source/blender/python/generic/mathutils_geometry.c
===================================================================
--- trunk/blender/source/blender/python/generic/mathutils_geometry.c 2010-12-11 20:01:34 UTC (rev 33604)
+++ trunk/blender/source/blender/python/generic/mathutils_geometry.c 2010-12-11 21:27:39 UTC (rev 33605)
@@ -587,7 +587,7 @@
static PyObject *M_Geometry_LineIntersect2D(PyObject *UNUSED(self), PyObject* args)
{
VectorObject *line_a1, *line_a2, *line_b1, *line_b2;
- float a1x, a1y, a2x, a2y, b1x, b1y, b2x, b2y, xi, yi, a1,a2,b1,b2, newvec[2];
+ float vi[2];
if( !PyArg_ParseTuple ( args, "O!O!O!O!",
&vector_Type, &line_a1,
&vector_Type, &line_a2,
@@ -600,86 +600,12 @@
if(!BaseMath_ReadCallback(line_a1) || !BaseMath_ReadCallback(line_a2) || !BaseMath_ReadCallback(line_b1) || !BaseMath_ReadCallback(line_b2))
return NULL;
-
- a1x= line_a1->vec[0];
- a1y= line_a1->vec[1];
- a2x= line_a2->vec[0];
- a2y= line_a2->vec[1];
- b1x= line_b1->vec[0];
- b1y= line_b1->vec[1];
- b2x= line_b2->vec[0];
- b2y= line_b2->vec[1];
-
- if((MIN2(a1x, a2x) > MAX2(b1x, b2x)) ||
- (MAX2(a1x, a2x) < MIN2(b1x, b2x)) ||
- (MIN2(a1y, a2y) > MAX2(b1y, b2y)) ||
- (MAX2(a1y, a2y) < MIN2(b1y, b2y)) ) {
+ if(isect_seg_seg_v2_point(line_a1->vec, line_a2->vec, line_b1->vec, line_b2->vec, vi) == 1) {
+ return newVectorObject(vi, 2, Py_NEW, NULL);
+ } else {
Py_RETURN_NONE;
}
- /* Make sure the hoz/vert line comes first. */
- if (fabs(b1x - b2x) < eps || fabs(b1y - b2y) < eps) {
- SWAP_FLOAT(a1x, b1x, xi); /*abuse xi*/
- SWAP_FLOAT(a1y, b1y, xi);
- SWAP_FLOAT(a2x, b2x, xi);
- SWAP_FLOAT(a2y, b2y, xi);
- }
-
- if (fabs(a1x-a2x) < eps) { /* verticle line */
- if (fabs(b1x-b2x) < eps){ /*verticle second line */
- Py_RETURN_NONE; /* 2 verticle lines dont intersect. */
- }
- else if (fabs(b1y-b2y) < eps) {
- /*X of vert, Y of hoz. no calculation needed */
- newvec[0]= a1x;
- newvec[1]= b1y;
- return newVectorObject(newvec, 2, Py_NEW, NULL);
- }
-
- yi = (float)(((b1y / fabs(b1x - b2x)) * fabs(b2x - a1x)) + ((b2y / fabs(b1x - b2x)) * fabs(b1x - a1x)));
-
- if (yi > MAX2(a1y, a2y)) {/* New point above seg1's vert line */
- Py_RETURN_NONE;
- } else if (yi < MIN2(a1y, a2y)) { /* New point below seg1's vert line */
- Py_RETURN_NONE;
- }
- newvec[0]= a1x;
- newvec[1]= yi;
- return newVectorObject(newvec, 2, Py_NEW, NULL);
- } else if (fabs(a2y-a1y) < eps) { /* hoz line1 */
- if (fabs(b2y-b1y) < eps) { /*hoz line2*/
- Py_RETURN_NONE; /*2 hoz lines dont intersect*/
- }
-
- /* Can skip vert line check for seg 2 since its covered above. */
- xi = (float)(((b1x / fabs(b1y - b2y)) * fabs(b2y - a1y)) + ((b2x / fabs(b1y - b2y)) * fabs(b1y - a1y)));
- if (xi > MAX2(a1x, a2x)) { /* New point right of hoz line1's */
- Py_RETURN_NONE;
- } else if (xi < MIN2(a1x, a2x)) { /*New point left of seg1's hoz line */
- Py_RETURN_NONE;
- }
- newvec[0]= xi;
- newvec[1]= a1y;
- return newVectorObject(newvec, 2, Py_NEW, NULL);
- }
-
- b1 = (a2y-a1y)/(a2x-a1x);
- b2 = (b2y-b1y)/(b2x-b1x);
- a1 = a1y-b1*a1x;
- a2 = b1y-b2*b1x;
-
- if (b1 - b2 == 0.0) {
- Py_RETURN_NONE;
- }
-
- xi = - (a1-a2)/(b1-b2);
- yi = a1+b1*xi;
- if ((a1x-xi)*(xi-a2x) >= 0 && (b1x-xi)*(xi-b2x) >= 0 && (a1y-yi)*(yi-a2y) >= 0 && (b1y-yi)*(yi-b2y)>=0) {
- newvec[0]= xi;
- newvec[1]= yi;
- return newVectorObject(newvec, 2, Py_NEW, NULL);
- }
- Py_RETURN_NONE;
}
static PyObject *M_Geometry_ClosestPointOnLine(PyObject *UNUSED(self), PyObject* args)
More information about the Bf-blender-cvs
mailing list