diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-12-28 10:17:55 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-12-28 10:23:59 +0400 |
commit | 6f5ced4a3028875e1d90b6d2f93af557e4fa16fe (patch) | |
tree | 6438830cfbdf59bb5829337744a7a2a10e1d4e2f /source | |
parent | 114284b1fbec7c01092ade3ade2bae5464c7f7ac (diff) |
Math Lib: add dist_squared_to_line_v2, avoids sqrt in scanfill and 3d-text
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenlib/BLI_math_geom.h | 6 | ||||
-rw-r--r-- | source/blender/blenlib/intern/freetypefont.c | 21 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_geom.c | 38 | ||||
-rw-r--r-- | source/blender/blenlib/intern/scanfill.c | 5 |
4 files changed, 52 insertions, 18 deletions
diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index 4f41ac86a0e..e99f89036b3 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 10d574e56b4..4f703d2d148 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 1d03bf42f83..833a08cec60 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 a292c2275c9..c4cefadb815 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); |