Fix delaunay triangulation, bad indices for output faces.

If there were merged vertices, sometimes the output faces
had wrong vertex indices. Added a test for this, and fixed.

1 files changed, 15 insertions, 2 deletions

diff --git a/source/blender/blenlib/intern/delaunay_2d.c b/source/blender/blenlib/intern/delaunay_2d.c
index ca9c0389c07..c3df51be0e4 100644
--- a/source/blender/blenlib/intern/delaunay_2d.c
+++ b/source/blender/blenlib/intern/delaunay_2d.c
@@ -2965,6 +2965,13 @@ static CDT_result *cdt_get_output(CDT_state *cdt,
   SymEdge *se, *se_start;
   CDTEdge *e;
   CDTFace *f;
+#ifdef DEBUG_CDT
+  int dbg_level = 0;
+
+  if (dbg_level > 0) {
+    fprintf(stderr, "\nCDT_GET_OUTPUT\n\n");
+  }
+#endif
 
   prepare_cdt_for_output(cdt, output_type);
 
@@ -2973,6 +2980,12 @@ static CDT_result *cdt_get_output(CDT_state *cdt,
     return result;
   }
 
+#ifdef DEBUG_CDT
+  if (dbg_level > 1) {
+    dump_cdt(cdt, "cdt to output");
+  }
+#endif
+
   /* All verts without a merge_to_index will be output.
    * vert_to_output_map[i] will hold the output vertex index
    * corresponding to the vert in position i in cdt->vert_array.
@@ -3112,7 +3125,7 @@ static CDT_result *cdt_get_output(CDT_state *cdt,
         result->faces_start_table[i] = j;
         se = se_start = f->symedge;
         do {
-          result->faces[j++] = se->vert->index;
+          result->faces[j++] = vert_to_output_map[se->vert->index];
           se = se->next;
         } while (se != se_start);
         result->faces_len_table[i] = j - result->faces_start_table[i];
@@ -3216,7 +3229,7 @@ CDT_result *BLI_delaunay_2d_cdt_calc(const CDT_input *input, const CDT_output_ty
     ne = input->edges_len;
     nf = input->faces_len;
 #ifdef DEBUG_CDT
-    if (dbg_level > 4) {
+    if (dbg_level > 0) {
       fprintf(stderr, "input modified for near ends; now ne=%d\n", ne);
     }
 #endif