From 3debcc8b517ece352aa325cfd61adc0b16cf91da Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Tue, 13 Jan 2015 19:01:40 +1100 Subject: Math Lib: improve area calculation - area_quad_v3 now works correctly with concave quads. - add area_squared_*** functions, to use when comparing to avoid a sqrt(). --- source/blender/blenkernel/intern/mesh_evaluate.c | 7 -- source/blender/blenlib/BLI_math_geom.h | 7 ++ source/blender/blenlib/intern/math_geom.c | 93 +++++++++++++++--------- source/blender/blenlib/intern/math_geom_inline.c | 6 ++ source/blender/bmesh/intern/bmesh_polygon.c | 3 - 5 files changed, 70 insertions(+), 46 deletions(-) (limited to 'source/blender') diff --git a/source/blender/blenkernel/intern/mesh_evaluate.c b/source/blender/blenkernel/intern/mesh_evaluate.c index 4c9e44682c3..915abdb6766 100644 --- a/source/blender/blenkernel/intern/mesh_evaluate.c +++ b/source/blender/blenkernel/intern/mesh_evaluate.c @@ -896,13 +896,6 @@ float BKE_mesh_calc_poly_area(MPoly *mpoly, MLoop *loopstart, mvarray[loopstart[2].v].co ); } - else if (mpoly->totloop == 4) { - return area_quad_v3(mvarray[loopstart[0].v].co, - mvarray[loopstart[1].v].co, - mvarray[loopstart[2].v].co, - mvarray[loopstart[3].v].co - ); - } else { int i; MLoop *l_iter = loopstart; diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index ee99f860a97..495aa6b2465 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -52,16 +52,23 @@ float normal_quad_v3(float r[3], const float a[3], const float b[3], const float float normal_poly_v3(float r[3], const float verts[][3], unsigned int nr); MINLINE float area_tri_v2(const float a[2], const float b[2], const float c[2]); +MINLINE float area_squared_tri_v2(const float a[2], const float b[2], const float c[2]); MINLINE float area_tri_signed_v2(const float v1[2], const float v2[2], const float v3[2]); float area_tri_v3(const float a[3], const float b[3], const float c[3]); +float area_squared_tri_v3(const float a[3], const float b[3], const float c[3]); float area_tri_signed_v3(const float v1[3], const float v2[3], const float v3[3], const float normal[3]); float area_quad_v3(const float a[3], const float b[3], const float c[3], const float d[3]); +float area_squared_quad_v3(const float a[3], const float b[3], const float c[3], const float d[3]); float area_poly_v3(const float verts[][3], unsigned int nr); float area_poly_v2(const float verts[][2], unsigned int nr); +float area_squared_poly_v3(const float verts[][3], unsigned int nr); +float area_squared_poly_v2(const float verts[][2], unsigned int nr); +float area_poly_signed_v2(const float verts[][2], unsigned int nr); float cotangent_tri_weight_v3(const float v1[3], const float v2[3], const float v3[3]); void cross_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3]); MINLINE float cross_tri_v2(const float v1[2], const float v2[2], const float v3[2]); +void cross_poly_v3(float n[3], const float verts[][3], unsigned int nr); float cross_poly_v2(const float verts[][2], unsigned int nr); /********************************* Planes **********************************/ diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index 59d9cf85dec..05a527c4f7a 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -109,58 +109,44 @@ float normal_quad_v3(float n[3], const float v1[3], const float v2[3], const flo */ float normal_poly_v3(float n[3], const float verts[][3], unsigned int nr) { - const float *v_prev = verts[nr - 1]; - const float *v_curr = verts[0]; - unsigned int i; - - zero_v3(n); - - /* Newell's Method */ - for (i = 0; i < nr; v_prev = v_curr, v_curr = verts[++i]) { - add_newell_cross_v3_v3v3(n, v_prev, v_curr); - } - + cross_poly_v3(n, verts, nr); return normalize_v3(n); } -/* only convex Quadrilaterals */ float area_quad_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3]) { - float len, vec1[3], vec2[3], n[3]; - - sub_v3_v3v3(vec1, v2, v1); - sub_v3_v3v3(vec2, v4, v1); - cross_v3_v3v3(n, vec1, vec2); - len = len_v3(n); - - sub_v3_v3v3(vec1, v4, v3); - sub_v3_v3v3(vec2, v2, v3); - cross_v3_v3v3(n, vec1, vec2); - len += len_v3(n); + const float verts[4][3] = {{UNPACK3(v1)}, {UNPACK3(v2)}, {UNPACK3(v3)}, {UNPACK3(v4)}}; + return area_poly_v3(verts, 4); +} - return (len / 2.0f); +float area_squared_quad_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3]) +{ + const float verts[4][3] = {{UNPACK3(v1)}, {UNPACK3(v2)}, {UNPACK3(v3)}, {UNPACK3(v4)}}; + return area_squared_poly_v3(verts, 4); } /* Triangles */ float area_tri_v3(const float v1[3], const float v2[3], const float v3[3]) { - float vec1[3], vec2[3], n[3]; - - sub_v3_v3v3(vec1, v3, v2); - sub_v3_v3v3(vec2, v1, v2); - cross_v3_v3v3(n, vec1, vec2); + float n[3]; + cross_tri_v3(n, v1, v2, v3); + return len_v3(n) * 0.5f; +} - return len_v3(n) / 2.0f; +float area_squared_tri_v3(const float v1[3], const float v2[3], const float v3[3]) +{ + float n[3]; + cross_tri_v3(n, v1, v2, v3); + mul_v3_fl(n, 0.5f); + return len_squared_v3(n); } float area_tri_signed_v3(const float v1[3], const float v2[3], const float v3[3], const float normal[3]) { - float area, vec1[3], vec2[3], n[3]; + float area, n[3]; - sub_v3_v3v3(vec1, v3, v2); - sub_v3_v3v3(vec2, v1, v2); - cross_v3_v3v3(n, vec1, vec2); - area = len_v3(n) / 2.0f; + cross_tri_v3(n, v1, v2, v3); + area = len_v3(n) * 0.5f; /* negate area for flipped triangles */ if (dot_v3v3(n, normal) < 0.0f) @@ -172,7 +158,17 @@ float area_tri_signed_v3(const float v1[3], const float v2[3], const float v3[3] float area_poly_v3(const float verts[][3], unsigned int nr) { float n[3]; - return normal_poly_v3(n, verts, nr) * 0.5f; + cross_poly_v3(n, verts, nr); + return len_v3(n) * 0.5f; +} + +float area_squared_poly_v3(const float verts[][3], unsigned int nr) +{ + float n[3]; + + cross_poly_v3(n, verts, nr); + mul_v3_fl(n, 0.5f); + return len_squared_v3(n); } /** @@ -200,11 +196,36 @@ float cross_poly_v2(const float verts[][2], unsigned int nr) return cross; } +void cross_poly_v3(float n[3], const float verts[][3], unsigned int nr) +{ + const float *v_prev = verts[nr - 1]; + const float *v_curr = verts[0]; + unsigned int i; + + zero_v3(n); + + /* Newell's Method */ + for (i = 0; i < nr; v_prev = v_curr, v_curr = verts[++i]) { + add_newell_cross_v3_v3v3(n, v_prev, v_curr); + } +} + float area_poly_v2(const float verts[][2], unsigned int nr) { return fabsf(0.5f * cross_poly_v2(verts, nr)); } +float area_poly_signed_v2(const float verts[][2], unsigned int nr) +{ + return (0.5f * cross_poly_v2(verts, nr)); +} + +float area_squared_poly_v2(const float verts[][2], unsigned int nr) +{ + float area = area_poly_signed_v2(verts, nr); + return area * area; +} + float cotangent_tri_weight_v3(const float v1[3], const float v2[3], const float v3[3]) { float a[3], b[3], c[3], c_len; diff --git a/source/blender/blenlib/intern/math_geom_inline.c b/source/blender/blenlib/intern/math_geom_inline.c index 5a64ed63ecf..44b17681540 100644 --- a/source/blender/blenlib/intern/math_geom_inline.c +++ b/source/blender/blenlib/intern/math_geom_inline.c @@ -54,6 +54,12 @@ MINLINE float area_tri_v2(const float v1[2], const float v2[2], const float v3[2 return fabsf(area_tri_signed_v2(v1, v2, v3)); } +MINLINE float area_squared_tri_v2(const float v1[2], const float v2[2], const float v3[2]) +{ + float area = area_tri_signed_v2(v1, v2, v3); + return area * area; +} + /****************************** Spherical Harmonics **************************/ MINLINE void zero_sh(float r[9]) diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index f2c426133c2..e4aa4bb0c0e 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -214,9 +214,6 @@ float BM_face_calc_area(BMFace *f) if (f->len == 3) { area = area_tri_v3(verts[0], verts[1], verts[2]); } - else if (f->len == 4) { - area = area_quad_v3(verts[0], verts[1], verts[2], verts[3]); - } else { area = area_poly_v3((const float (*)[3])verts, f->len); } -- cgit v1.2.3