blender
/
blender
137
415
Fork 598
Code Issues 6.3k Pull Requests 766 Projects 19 Wiki Activity

Math Lib: replace point in polygon function with one thats ~23x faster. 

rather then using angle summing, use line intersection checks.
This commit is contained in:
Campbell Barton 2013-12-29 14:46:56 +11:00
parent 28f5573197
commit 07851dd8df
Notes: blender-bot 2023-11-06 19:56:33 +01:00 
Referenced by commit 6e4adbe694, Cleanup: use_holes arg to isect_point_poly_v2 has been ignored since 2013
1 changed files with 34 additions and 0 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

34
source/blender/blenlib/intern/math_geom.c
View File

@ -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 */