diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-12-29 07:46:56 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-12-29 07:50:15 +0400 |
commit | 07851dd8df23f716b60aa215c8cd9f7c591b0fde (patch) | |
tree | 47821d231f39b29ff3231f63e6a26944c0a1d716 /source | |
parent | 28f55731976caeee154be39f994c50cae954003b (diff) |
Math Lib: replace point in polygon function with one thats ~23x faster.
rather then using angle summing, use line intersection checks.
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenlib/intern/math_geom.c | 34 |
1 files changed, 34 insertions, 0 deletions
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index bf5ae8fab4f..cfbf814a5f2 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -735,6 +735,7 @@ int isect_line_sphere_v2(const float l1[2], const float l2[2], } /* point in polygon (keep float and int versions in sync) */ +#if 0 bool isect_point_poly_v2(const float pt[2], const float verts[][2], const unsigned int nr, const bool use_holes) { @@ -816,6 +817,39 @@ bool isect_point_poly_v2_int(const int pt[2], const int verts[][2], const unsign } } +#else + +bool isect_point_poly_v2(const float pt[2], const float verts[][2], const unsigned int nr, + const bool UNUSED(use_holes)) +{ + unsigned int i, j; + bool isect = false; + for (i = 0, j = nr - 1; i < nr; j = i++) { + if (((verts[i][1] > pt[1]) != (verts[j][1] > pt[1])) && + (pt[0] < (verts[j][0] - verts[i][0]) * (pt[1] - verts[i][1]) / (verts[j][1] - verts[i][1]) + verts[i][0])) + { + isect = !isect; + } + } + return isect; +} +bool isect_point_poly_v2_int(const int pt[2], const int verts[][2], const unsigned int nr, + const bool UNUSED(use_holes)) +{ + unsigned int i, j; + bool isect = false; + for (i = 0, j = nr - 1; i < nr; j = i++) { + if (((verts[i][1] > pt[1]) != (verts[j][1] > pt[1])) && + (pt[0] < (verts[j][0] - verts[i][0]) * (pt[1] - verts[i][1]) / (verts[j][1] - verts[i][1]) + verts[i][0])) + { + isect = !isect; + } + } + return isect; +} + +#endif + /* point in tri */ /* only single direction */ |