From 540c2eee566318a40fef26cd60f182020d2cb7ff Mon Sep 17 00:00:00 2001
From: Campbell Barton <ideasman42@gmail.com>
Date: Sun, 26 Jun 2011 07:21:19 +0000
Subject: 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)
---
 source/blender/blenlib/BLI_math_geom.h    |  1 +
 source/blender/blenlib/intern/math_geom.c | 73 +++++++++++++++++++++++++++++++
 2 files changed, 74 insertions(+)

(limited to 'source/blender/blenlib')

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
-- 
cgit v1.2.3