[Bf-blender-cvs] [6f5ced4] master: Math Lib: add dist_squared_to_line_v2, avoids sqrt in scanfill and 3d-text
Campbell Barton
noreply at git.blender.org
Sat Dec 28 07:25:30 CET 2013
Commit: 6f5ced4a3028875e1d90b6d2f93af557e4fa16fe
Author: Campbell Barton
Date: Sat Dec 28 17:17:55 2013 +1100
https://developer.blender.org/rB6f5ced4a3028875e1d90b6d2f93af557e4fa16fe
Math Lib: add dist_squared_to_line_v2, avoids sqrt in scanfill and 3d-text
===================================================================
M source/blender/blenlib/BLI_math_geom.h
M source/blender/blenlib/intern/freetypefont.c
M source/blender/blenlib/intern/math_geom.c
M source/blender/blenlib/intern/scanfill.c
===================================================================
diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h
index 4f41ac8..e99f890 100644
--- a/source/blender/blenlib/BLI_math_geom.h
+++ b/source/blender/blenlib/BLI_math_geom.h
@@ -80,7 +80,8 @@ int is_quad_convex_v2(const float v1[2], const float v2[2], const float v3[2], c
/********************************* Distance **********************************/
-float dist_to_line_v2(const float p[2], const float l1[2], const float l2[2]);
+float dist_squared_to_line_v2(const float p[2], const float l1[2], const float l2[2]);
+float dist_to_line_v2(const float p[2], const float l1[2], const float l2[2]);
float dist_squared_to_line_segment_v2(const float p[2], const float l1[2], const float l2[2]);
float dist_to_line_segment_v2(const float p[2], const float l1[2], const float l2[2]);
void closest_to_line_segment_v2(float closest[2], const float p[2], const float l1[2], const float l2[2]);
@@ -89,7 +90,8 @@ float dist_squared_to_plane_v3(const float p[3], const float plane[4]);
float dist_to_plane_v3(const float p[3], const float plane[4]);
float dist_squared_to_line_segment_v3(const float p[3], const float l1[3], const float l2[3]);
float dist_to_line_segment_v3(const float p[3], const float l1[3], const float l2[3]);
-float dist_to_line_v3(const float p[3], const float l1[3], const float l2[3]);
+float dist_squared_to_line_v3(const float p[3], const float l1[3], const float l2[3]);
+float dist_to_line_v3(const float p[3], const float l1[3], const float l2[3]);
float closest_to_line_v3(float r[3], const float p[3], const float l1[3], const float l2[3]);
float closest_to_line_v2(float r[2], const float p[2], const float l1[2], const float l2[2]);
void closest_to_line_segment_v3(float r[3], const float p[3], const float l1[3], const float l2[3]);
diff --git a/source/blender/blenlib/intern/freetypefont.c b/source/blender/blenlib/intern/freetypefont.c
index 10d574e..4f703d2 100644
--- a/source/blender/blenlib/intern/freetypefont.c
+++ b/source/blender/blenlib/intern/freetypefont.c
@@ -64,6 +64,8 @@ static FT_Error err;
static void freetypechar_to_vchar(FT_Face face, FT_ULong charcode, VFontData *vfd)
{
+ const float eps = 0.0001f;
+ const float eps_sq = eps * eps;
/* Blender */
struct Nurb *nu;
struct VChar *che;
@@ -260,18 +262,19 @@ static void freetypechar_to_vchar(FT_Face face, FT_ULong charcode, VFontData *vf
}
/* get the handles that are aligned, tricky...
- * dist_to_line_v2, check if the three beztriple points are on one line
- * len_squared_v2v2, see if there's a distance between the three points
- * len_squared_v2v2 again, to check the angle between the handles
- * finally, check if one of them is a vector handle */
+ * - check if one of them is a vector handle.
+ * - dist_squared_to_line_v2, check if the three beztriple points are on one line
+ * - len_squared_v2v2, see if there's a distance between the three points
+ * - len_squared_v2v2 again, to check the angle between the handles
+ */
if ((bezt->h1 != HD_VECT && bezt->h2 != HD_VECT) &&
- (dist_to_line_v2(bezt->vec[0], bezt->vec[1], bezt->vec[2]) < 0.001f) &&
- (len_squared_v2v2(bezt->vec[0], bezt->vec[1]) > 0.0001f * 0.0001f) &&
- (len_squared_v2v2(bezt->vec[1], bezt->vec[2]) > 0.0001f * 0.0001f) &&
- (len_squared_v2v2(bezt->vec[0], bezt->vec[2]) > 0.0002f * 0.0001f) &&
+ (dist_squared_to_line_v2(bezt->vec[0], bezt->vec[1], bezt->vec[2]) < (0.001f * 0.001f)) &&
+ (len_squared_v2v2(bezt->vec[0], bezt->vec[1]) > eps_sq) &&
+ (len_squared_v2v2(bezt->vec[1], bezt->vec[2]) > eps_sq) &&
+ (len_squared_v2v2(bezt->vec[0], bezt->vec[2]) > eps_sq) &&
(len_squared_v2v2(bezt->vec[0], bezt->vec[2]) >
max_ff(len_squared_v2v2(bezt->vec[0], bezt->vec[1]),
- len_squared_v2v2(bezt->vec[1], bezt->vec[2]))))
+ len_squared_v2v2(bezt->vec[1], bezt->vec[2]))))
{
bezt->h1 = bezt->h2 = HD_ALIGN;
}
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index 1d03bf4..833a08c 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -219,17 +219,41 @@ float volume_tetrahedron_v3(const float v1[3], const float v2[3], const float v3
/* distance p to line v1-v2
* using Hesse formula, NO LINE PIECE! */
+float dist_squared_to_line_v2(const float p[2], const float l1[2], const float l2[2])
+{
+ float a[2], deler;
+
+ a[0] = l1[1] - l2[1];
+ a[1] = l2[0] - l1[0];
+
+ deler = len_squared_v2(a);
+
+ if (deler != 0.0f) {
+ float f = ((p[0] - l1[0]) * a[0] +
+ (p[1] - l1[1]) * a[1]);
+ return (f * f) / deler;
+ }
+ else {
+ return 0.0f;
+ }
+}
float dist_to_line_v2(const float p[2], const float l1[2], const float l2[2])
{
float a[2], deler;
a[0] = l1[1] - l2[1];
a[1] = l2[0] - l1[0];
- deler = (float)sqrt(a[0] * a[0] + a[1] * a[1]);
- if (deler == 0.0f) return 0;
- return fabsf((p[0] - l1[0]) * a[0] + (p[1] - l1[1]) * a[1]) / deler;
+ deler = len_squared_v2(a);
+ if (deler != 0.0f) {
+ float f = ((p[0] - l1[0]) * a[0] +
+ (p[1] - l1[1]) * a[1]);
+ return fabsf(f) / sqrtf(deler);
+ }
+ else {
+ return 0.0f;
+ }
}
/* distance p to line-piece v1-v2 */
@@ -350,13 +374,17 @@ float dist_to_line_segment_v3(const float p[3], const float l1[3], const float l
return sqrtf(dist_squared_to_line_segment_v3(p, l1, l2));
}
-float dist_to_line_v3(const float v1[3], const float l1[3], const float l2[3])
+float dist_squared_to_line_v3(const float v1[3], const float l1[3], const float l2[3])
{
float closest[3];
closest_to_line_v3(closest, v1, l1, l2);
- return len_v3v3(closest, v1);
+ return len_squared_v3v3(closest, v1);
+}
+float dist_to_line_v3(const float v1[3], const float l1[3], const float l2[3])
+{
+ return sqrtf(dist_squared_to_line_v3(v1, l1, l2));
}
/* Adapted from "Real-Time Collision Detection" by Christer Ericson,
diff --git a/source/blender/blenlib/intern/scanfill.c b/source/blender/blenlib/intern/scanfill.c
index a292c22..c4cefad 100644
--- a/source/blender/blenlib/intern/scanfill.c
+++ b/source/blender/blenlib/intern/scanfill.c
@@ -62,6 +62,7 @@ typedef struct ScanFillVertLink {
/* local funcs */
#define SF_EPSILON 0.00003f
+#define SF_EPSILON_SQ (SF_EPSILON * SF_EPSILON)
#define SF_VERT_AVAILABLE 1 /* available - in an edge */
#define SF_VERT_ZERO_LEN 255
@@ -374,8 +375,8 @@ static void testvertexnearedge(ScanFillContext *sf_ctx)
}
else {
if (boundinsideEV(eed, eve)) {
- const float dist = dist_to_line_v2(eed->v1->xy, eed->v2->xy, eve->xy);
- if (dist < SF_EPSILON) {
+ const float dist = dist_squared_to_line_v2(eed->v1->xy, eed->v2->xy, eve->xy);
+ if (dist < SF_EPSILON_SQ) {
/* new edge */
ed1 = BLI_scanfill_edge_add(sf_ctx, eed->v1, eve);
More information about the Bf-blender-cvs
mailing list