Fix T57284: poor result UV unwrapping concave n-gon.
[blender.git] / source / blender / editors / uvedit / uvedit_parametrizer.c
index 79e804725e5b6195e1f959fc76cb3dcb8eeada69..352bfbf9a9e12d0dbbfc842c1785908af659d1c0 100644 (file)
@@ -34,6 +34,8 @@
 #include "BLI_heap.h"
 #include "BLI_boxpack_2d.h"
 #include "BLI_convexhull_2d.h"
+#include "BLI_polyfill_2d.h"
+#include "BLI_polyfill_2d_beautify.h"
 
 #include "uvedit_parametrizer.h"
 
@@ -219,6 +221,8 @@ enum PHandleState {
 typedef struct PHandle {
        enum PHandleState state;
        MemArena *arena;
+       MemArena *polyfill_arena;
+       Heap *polyfill_heap;
 
        PChart *construction_chart;
        PHash *hash_verts;
@@ -4119,6 +4123,8 @@ ParamHandle *param_construct_begin(void)
        handle->construction_chart = p_chart_new(handle);
        handle->state = PHANDLE_STATE_ALLOCATED;
        handle->arena = BLI_memarena_new(MEM_SIZE_OPTIMAL(1 << 16), "param construct arena");
+       handle->polyfill_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "param polyfill arena");
+       handle->polyfill_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE);
        handle->aspx = 1.0f;
        handle->aspy = 1.0f;
        handle->do_aspect = false;
@@ -4162,82 +4168,71 @@ void param_delete(ParamHandle *handle)
        }
 
        BLI_memarena_free(phandle->arena);
+       BLI_memarena_free(phandle->polyfill_arena);
+       BLI_heap_free(phandle->polyfill_heap, NULL);
        MEM_freeN(phandle);
 }
 
 static void p_add_ngon(ParamHandle *handle, ParamKey key, int nverts,
                        ParamKey *vkeys, float **co, float **uv,
-                       ParamBool *pin, ParamBool *select, const float normal[3])
+                       ParamBool *pin, ParamBool *select)
 {
-       int *boundary = BLI_array_alloca(boundary, nverts);
-
-       /* boundary vertex indexes */
-       for (int i = 0; i < nverts; i++) {
-               boundary[i] = i;
-       }
-
-       while (nverts > 2) {
-               float minangle = FLT_MAX;
-               float minshape = FLT_MAX;
-               int i, mini = 0;
-
-               /* find corner with smallest angle */
-               for (i = 0; i < nverts; i++) {
-                       int v0 = boundary[(i + nverts - 1) % nverts];
-                       int v1 = boundary[i];
-                       int v2 = boundary[(i + 1) % nverts];
-                       float angle = p_vec_angle(co[v0], co[v1], co[v2]);
-                       float n[3];
-
-                       normal_tri_v3(n, co[v0], co[v1], co[v2]);
+       /* Allocate memory for polyfill. */
+       PHandle *phandle = (PHandle *)handle;
+       MemArena *arena = phandle->polyfill_arena;
+       Heap *heap = phandle->polyfill_heap;
+       unsigned int nfilltri = nverts - 2;
+       unsigned int (*tris)[3] = BLI_memarena_alloc(arena, sizeof(*tris) * (size_t)nfilltri);
+       float (*projverts)[2] = BLI_memarena_alloc(arena, sizeof(*projverts) * (size_t)nverts);
 
-                       if (normal && (dot_v3v3(n, normal) < 0.0f))
-                               angle = (float)(2.0 * M_PI) - angle;
+       /* Calc normal, flipped: to get a positive 2d cross product. */
+       float normal[3];
+       zero_v3(normal);
 
-                       float other_angle = p_vec_angle(co[v2], co[v0], co[v1]);
-                       float shape = fabsf((float)M_PI - angle - 2.0f * other_angle);
+       const float *co_curr, *co_prev = co[nverts-1];
+       for (int j = 0; j < nverts; j++) {
+               co_curr = co[j];
+               add_newell_cross_v3_v3v3(normal, co_prev, co_curr);
+               co_prev = co_curr;
+       }
+       if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
+               normal[2] = 1.0f;
+       }
 
-                       if (fabsf(angle - minangle) < 0.01f) {
-                               /* for nearly equal angles, try to get well shaped triangles */
-                               if (shape < minshape) {
-                                       minangle = angle;
-                                       minshape = shape;
-                                       mini = i;
-                               }
-                       }
-                       else if (angle < minangle) {
-                               minangle = angle;
-                               minshape = shape;
-                               mini = i;
-                       }
-               }
+       /* Project verts to 2d. */
+       float axis_mat[3][3];
+       axis_dominant_v3_to_m3_negate(axis_mat, normal);
+       for (int j = 0; j < nverts; j++) {
+               mul_v2_m3v3(projverts[j], axis_mat, co[j]);
+       }
 
-               /* add triangle in corner */
-               {
-                       int v0 = boundary[(mini + nverts - 1) % nverts];
-                       int v1 = boundary[mini];
-                       int v2 = boundary[(mini + 1) % nverts];
+       BLI_polyfill_calc_arena(projverts, nverts, 1, tris, arena);
 
-                       ParamKey tri_vkeys[3] = {vkeys[v0], vkeys[v1], vkeys[v2]};
-                       float *tri_co[3] = {co[v0], co[v1], co[v2]};
-                       float *tri_uv[3] = {uv[v0], uv[v1], uv[v2]};
-                       ParamBool tri_pin[3] = {pin[v0], pin[v1], pin[v2]};
-                       ParamBool tri_select[3] = {select[v0], select[v1], select[v2]};
+       /* Beautify helps avoid thin triangles that give numerical problems. */
+       BLI_polyfill_beautify(projverts, nverts, tris, arena, heap);
 
-                       param_face_add(handle, key, 3, tri_vkeys, tri_co, tri_uv, tri_pin, tri_select, NULL);
-               }
+       /* Add triangles. */
+       for (int j = 0; j < nfilltri; j++) {
+               unsigned int *tri = tris[j];
+               unsigned int v0 = tri[0];
+               unsigned int v1 = tri[1];
+               unsigned int v2 = tri[2];
 
-               /* remove corner */
-               if (mini + 1 < nverts)
-                       memmove(boundary + mini, boundary + mini + 1, (nverts - mini - 1) * sizeof(int));
+               ParamKey tri_vkeys[3] = {vkeys[v0], vkeys[v1], vkeys[v2]};
+               float *tri_co[3] = {co[v0], co[v1], co[v2]};
+               float *tri_uv[3] = {uv[v0], uv[v1], uv[v2]};
+               ParamBool tri_pin[3] = {pin[v0], pin[v1], pin[v2]};
+               ParamBool tri_select[3] = {select[v0], select[v1], select[v2]};
 
-               nverts--;
+               param_face_add(handle, key, 3, tri_vkeys, tri_co, tri_uv, tri_pin, tri_select);
        }
+
+       BLI_memarena_clear(arena);
 }
 
 void param_face_add(ParamHandle *handle, ParamKey key, int nverts,
                     ParamKey *vkeys, float *co[4], float *uv[4],
-                    ParamBool *pin, ParamBool *select, float normal[3])
+                    ParamBool *pin, ParamBool *select)
 {
        PHandle *phandle = (PHandle *)handle;
 
@@ -4247,7 +4242,7 @@ void param_face_add(ParamHandle *handle, ParamKey key, int nverts,
 
        if (nverts > 4) {
                /* ngon */
-               p_add_ngon(handle, key, nverts, vkeys, co, uv, pin, select, normal);
+               p_add_ngon(handle, key, nverts, vkeys, co, uv, pin, select);
        }
        else if (nverts == 4) {
                /* quad */