Make it optional to track input->output mapping in delaunay_2d_calc.

Some uses of delaunay_2d_calc don't need to know the original verts,
edges, and faces that correspond to output elements.
This change adds a "need_ids" value to the CDT input spec, default true,
which tracks the input ids only when true.
The python api mathutils.geometry.delaunay_2d_cdt gets an optional
final bool argument that is the value of need_ids. If the argument
is not supplied, it is true by default, so this won't break old uses
of the API.

On a sample text test, not tracking ids save about 30% of the runtime.
For most inputs the difference will not be so dramatic: it only really
kicks in if there are a lot of holes.

1 files changed, 8 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_delaunay_2d.h b/source/blender/blenlib/BLI_delaunay_2d.h
index d42bd6af637..5a8ddfb5a92 100644
--- a/source/blender/blenlib/BLI_delaunay_2d.h
+++ b/source/blender/blenlib/BLI_delaunay_2d.h
@@ -110,6 +110,10 @@ extern "C" {
  * If zero is supplied for epsilon, an internal value of 1e-8 used
  * instead, since this code will not work correctly if it is not allowed
  * to merge "too near" vertices.
+ * 
+ * Normally the output will contain mappings from outputs to inputs.
+ * If this is not needed, set need_ids to false and the execution may be much
+ * faster in some circumstances.
  */
 typedef struct CDT_input {
   int verts_len;
@@ -121,6 +125,7 @@ typedef struct CDT_input {
   int *faces_start_table;
   int *faces_len_table;
   float epsilon;
+  bool need_ids;
 } CDT_input;
 
 /**
@@ -140,6 +145,7 @@ typedef struct CDT_input {
  * a run-together array and a "start" and "len" extra array,
  * similar triples are used to represent the output to input
  * mapping of vertices, edges, and faces.
+ * These are only set if need_ids is true in the input.
  *
  * Those triples are:
  * - verts_orig, verts_orig_start_table, verts_orig_len_table
@@ -236,6 +242,7 @@ template<typename Arith_t> class CDT_input {
   Array<std::pair<int, int>> edge;
   Array<Vector<int>> face;
   Arith_t epsilon{0};
+  bool need_ids{true};
 };
 
 template<typename Arith_t> class CDT_result {
@@ -243,6 +250,7 @@ template<typename Arith_t> class CDT_result {
   Array<vec2<Arith_t>> vert;
   Array<std::pair<int, int>> edge;
   Array<Vector<int>> face;
+  /* The orig vectors are only popluated if the need_ids input field is true. */
   /** For each output vert, which input verts correspond to it? */
   Array<Vector<int>> vert_orig;
   /**