diff options
author | Campbell Barton <ideasman42@gmail.com> | 2011-06-26 11:21:19 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2011-06-26 11:21:19 +0400 |
commit | 540c2eee566318a40fef26cd60f182020d2cb7ff (patch) | |
tree | 29b87644ee8f0b69e2193956376acebaa942b104 /source | |
parent | 83000d8504269b61eb8645fc92979603521a1ae6 (diff) |
math func to find the intersection(s) between a segment and a sphere for C/python.
from python:
i1, i2 = mathutils.geometry.intersect_line_sphere(l1, l2, sphere, radius)
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenlib/BLI_math_geom.h | 1 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_geom.c | 73 | ||||
-rw-r--r-- | source/blender/python/generic/mathutils_geometry.c | 68 |
3 files changed, 142 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index b34b9c4b70f..26cf315fc36 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -79,6 +79,7 @@ void closest_to_line_segment_v3(float r[3], const float p[3], const float l1[3], int isect_line_line_v2(const float a1[2], const float a2[2], const float b1[2], const float b2[2]); int isect_line_line_v2_int(const int a1[2], const int a2[2], const int b1[2], const int b2[2]); int isect_seg_seg_v2_point(const float v1[2], const float v2[2], const float v3[2], const float v4[2], float vi[2]); +int isect_seg_sphere_v3(const float l1[3], const float l2[3], const float sp[3], const float r, float r_p1[3], float r_p2[3]); /* Returns the number of point of interests * 0 - lines are colinear diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index 96ed788a49f..ce03143dcaf 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -349,6 +349,79 @@ int isect_seg_seg_v2_point(const float v1[2], const float v2[2], const float v3[ return -1; } +int isect_seg_sphere_v3(const float l1[3], const float l2[3], + const float sp[3], const float r, + float r_p1[3], float r_p2[3]) +{ + /* l1: coordinates (point of line) + * l2: coordinates (point of line) + * sp, r: coordinates and radius (sphere) + * r_p1, r_p2: return intersection coordinates + */ + + + /* adapted for use in blender by Campbell Barton - 2011 + * + * atelier iebele abel - 2001 + * atelier@iebele.nl + * http://www.iebele.nl + * + * sphere_line_intersection function adapted from: + * http://astronomy.swin.edu.au/pbourke/geometry/sphereline + * Paul Bourke pbourke@swin.edu.au + */ + + const float ldir[3]= { + l2[0] - l1[0], + l2[1] - l1[1], + l2[2] - l1[2] + }; + + const float a= dot_v3v3(ldir, ldir); + + const float b= 2.0f * + (ldir[0] * (l1[0] - sp[0]) + + ldir[1] * (l1[1] - sp[1]) + + ldir[2] * (l1[2] - sp[2])); + + const float c= + dot_v3v3(sp, sp) + + dot_v3v3(l1, l1) - + (2.0f * dot_v3v3(sp, l1)) - + (r * r); + + const float i = b * b - 4.0f * a * c; + + float mu; + + if (i < 0.0f) { + /* no intersections */ + return 0; + } + else if (i == 0.0f) { + /* one intersection */ + mu = -b / (2.0f * a); + madd_v3_v3v3fl(r_p1, l1, ldir, mu); + return 1; + } + else if (i > 0.0) { + const float i_sqrt= sqrt(i); /* avoid calc twice */ + + /* first intersection */ + mu = (-b + i_sqrt) / (2.0f * a); + madd_v3_v3v3fl(r_p1, l1, ldir, mu); + + /* second intersection */ + mu = (-b - i_sqrt) / (2.0f * a); + madd_v3_v3v3fl(r_p2, l1, ldir, mu); + return 2; + } + else { + /* math domain error - nan */ + return -1; + } +} + /* -1: colliniar 1: intersection diff --git a/source/blender/python/generic/mathutils_geometry.c b/source/blender/python/generic/mathutils_geometry.c index 53c066d1a85..0b98867dcee 100644 --- a/source/blender/python/generic/mathutils_geometry.c +++ b/source/blender/python/generic/mathutils_geometry.c @@ -553,6 +553,73 @@ static PyObject *M_Geometry_intersect_line_plane(PyObject *UNUSED(self), PyObjec } } + +PyDoc_STRVAR(M_Geometry_intersect_line_sphere_doc, +".. function:: intersect_line_sphere(line_a, line_b, sphere_co, sphere_radius)\n" +"\n" +" Takes a lines (as 2 vectors), a sphere as a point and a radius and\n" +" returns the intersection\n" +"\n" +" :arg line_a: First point of the first line\n" +" :type line_a: :class:`mathutils.Vector`\n" +" :arg line_b: Second point of the first line\n" +" :type line_b: :class:`mathutils.Vector`\n" +" :arg sphere_co: The center of the sphere\n" +" :type sphere_co: :class:`mathutils.Vector`\n" +" :arg sphere_radius: Radius of the sphere\n" +" :type sphere_radius: sphere_radius\n" +" :return: The intersection points as a pair of vectors or None when there is no intersection\n" +" :rtype: A tuple pair containing :class:`mathutils.Vector` or None\n" +); +static PyObject *M_Geometry_intersect_line_sphere(PyObject *UNUSED(self), PyObject* args) +{ + PyObject *ret; + VectorObject *line_a, *line_b, *sphere_co; + float sphere_radius; + + float isect_a[3]; + float isect_b[3]; + + if(!PyArg_ParseTuple(args, "O!O!O!f:intersect_line_sphere", + &vector_Type, &line_a, + &vector_Type, &line_b, + &vector_Type, &sphere_co, + &sphere_radius) + ) { + return NULL; + } + + if( BaseMath_ReadCallback(line_a) == -1 || + BaseMath_ReadCallback(line_b) == -1 || + BaseMath_ReadCallback(sphere_co) == -1 + ) { + return NULL; + } + + if(ELEM3(2, line_a->size, line_b->size, sphere_co->size)) { + PyErr_SetString(PyExc_RuntimeError, "geometry.intersect_line_sphere(...) can't use 2D Vectors"); + return NULL; + } + + ret= PyTuple_New(2); + + switch(isect_seg_sphere_v3(line_a->vec, line_b->vec, sphere_co->vec, sphere_radius, isect_a, isect_b)) { + case 1: + PyTuple_SET_ITEM(ret, 0, newVectorObject(isect_a, 3, Py_NEW, NULL)); + PyTuple_SET_ITEM(ret, 1, Py_None); Py_INCREF(Py_None); + break; + case 2: + PyTuple_SET_ITEM(ret, 0, newVectorObject(isect_a, 3, Py_NEW, NULL)); + PyTuple_SET_ITEM(ret, 1, newVectorObject(isect_b, 3, Py_NEW, NULL)); + break; + default: + PyTuple_SET_ITEM(ret, 0, Py_None); Py_INCREF(Py_None); + PyTuple_SET_ITEM(ret, 1, Py_None); Py_INCREF(Py_None); + } + + return ret; +} + PyDoc_STRVAR(M_Geometry_intersect_point_line_doc, ".. function:: intersect_point_line(pt, line_p1, line_p2)\n" "\n" @@ -917,6 +984,7 @@ static PyMethodDef M_Geometry_methods[]= { {"intersect_line_line", (PyCFunction) M_Geometry_intersect_line_line, METH_VARARGS, M_Geometry_intersect_line_line_doc}, {"intersect_line_line_2d", (PyCFunction) M_Geometry_intersect_line_line_2d, METH_VARARGS, M_Geometry_intersect_line_line_2d_doc}, {"intersect_line_plane", (PyCFunction) M_Geometry_intersect_line_plane, METH_VARARGS, M_Geometry_intersect_line_plane_doc}, + {"intersect_line_sphere", (PyCFunction) M_Geometry_intersect_line_sphere, METH_VARARGS, M_Geometry_intersect_line_sphere_doc}, {"interpolate_bezier", (PyCFunction) M_Geometry_interpolate_bezier, METH_VARARGS, M_Geometry_interpolate_bezier_doc}, {"area_tri", (PyCFunction) M_Geometry_area_tri, METH_VARARGS, M_Geometry_area_tri_doc}, {"normal", (PyCFunction) M_Geometry_normal, METH_VARARGS, M_Geometry_normal_doc}, |