Geometry Nodes: initial scattering and geometry nodes

This is the initial merge from the geometry-nodes branch.
Nodes:
* Attribute Math
* Boolean
* Edge Split
* Float Compare
* Object Info
* Point Distribute
* Point Instance
* Random Attribute
* Random Float
* Subdivision Surface
* Transform
* Triangulate

It includes the initial evaluation of geometry node groups in the Geometry Nodes modifier.

Notes on the Generic attribute access API

The API adds an indirection for attribute access. That has the following benefits:
* Most code does not have to care about how an attribute is stored internally.
  This is mainly necessary, because we have to deal with "legacy" attributes
  such as vertex weights and attributes that are embedded into other structs
  such as vertex positions.
* When reading from an attribute, we generally don't care what domain the
  attribute is stored on. So we want to abstract away the interpolation that
  that adapts attributes from one domain to another domain (this is not
  actually implemented yet).

Other possible improvements for later iterations include:
* Actually implement interpolation between domains.
* Don't use inheritance for the different attribute types. A single class for read
  access and one for write access might be enough, because we know all the ways
  in which attributes are stored internally. We don't want more different internal
  structures in the future. On the contrary, ideally we can consolidate the different
  storage formats in the future to reduce the need for this indirection.
* Remove the need for heap allocations when creating attribute accessors.

It includes commits from:
* Dalai Felinto
* Hans Goudey
* Jacques Lucke
* Léo Depoix

3 files changed, 137 insertions, 0 deletions

diff --git a/source/blender/functions/CMakeLists.txt b/source/blender/functions/CMakeLists.txt
index e005753e228..429959f9c33 100644
--- a/source/blender/functions/CMakeLists.txt
+++ b/source/blender/functions/CMakeLists.txt
@@ -39,6 +39,7 @@ set(SRC
   FN_attributes_ref.hh
   FN_cpp_type.hh
   FN_generic_pointer.hh
+  FN_generic_value_map.hh
   FN_generic_vector_array.hh
   FN_multi_function.hh
   FN_multi_function_builder.hh
diff --git a/source/blender/functions/FN_generic_value_map.hh b/source/blender/functions/FN_generic_value_map.hh
new file mode 100644
index 00000000000..2c1b37c0461
--- /dev/null
+++ b/source/blender/functions/FN_generic_value_map.hh
@@ -0,0 +1,123 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#pragma once
+
+#include "BLI_linear_allocator.hh"
+#include "BLI_map.hh"
+
+#include "FN_generic_pointer.hh"
+
+namespace blender::fn {
+
+/**
+ * This is a map that stores key-value-pairs. What makes it special is that the type of values does
+ * not have to be known at compile time. There just has to be a corresponding CPPType.
+ */
+template<typename Key> class GValueMap {
+ private:
+  /* Used to allocate values owned by this container. */
+  LinearAllocator<> &allocator_;
+  Map<Key, GMutablePointer> values_;
+
+ public:
+  GValueMap(LinearAllocator<> &allocator) : allocator_(allocator)
+  {
+  }
+
+  ~GValueMap()
+  {
+    /* Destruct all values that are still in the map. */
+    for (GMutablePointer value : values_.values()) {
+      value.destruct();
+    }
+  }
+
+  /* Add a value to the container. The container becomes responsible for destructing the value that
+   * is passed in. The caller remains responsible for freeing the value after it has been
+   * destructed. */
+  template<typename ForwardKey> void add_new_direct(ForwardKey &&key, GMutablePointer value)
+  {
+    values_.add_new_as(std::forward<ForwardKey>(key), value);
+  }
+
+  /* Add a value to the container that is move constructed from the given value. The caller remains
+   * responsible for destructing and freeing the given value. */
+  template<typename ForwardKey> void add_new_by_move(ForwardKey &&key, GMutablePointer value)
+  {
+    const CPPType &type = *value.type();
+    void *buffer = allocator_.allocate(type.size(), type.alignment());
+    type.move_to_uninitialized(value.get(), buffer);
+    values_.add_new_as(std::forward<ForwardKey>(key), GMutablePointer{type, buffer});
+  }
+
+  /* Add a value to the container that is copy constructed from the given value. The caller remains
+   * responsible for destructing and freeing the given value. */
+  template<typename ForwardKey> void add_new_by_copy(ForwardKey &&key, GMutablePointer value)
+  {
+    const CPPType &type = *value.type();
+    void *buffer = allocator_.allocate(type.size(), type.alignment());
+    type.copy_to_uninitialized(value.get(), buffer);
+    values_.add_new_as(std::forward<ForwardKey>(key), GMutablePointer{type, buffer});
+  }
+
+  /* Add a value to the container. */
+  template<typename ForwardKey, typename T> void add_new(ForwardKey &&key, T &&value)
+  {
+    if constexpr (std::is_rvalue_reference_v<T>) {
+      this->add_new_by_move(std::forward<ForwardKey>(key), &value);
+    }
+    else {
+      this->add_new_by_copy(std::forward<ForwardKey>(key), &value);
+    }
+  }
+
+  /* Remove the value for the given name from the container and remove it. The caller is
+   * responsible for freeing it. The lifetime of the referenced memory might be bound to lifetime
+   * of the container. */
+  template<typename ForwardKey> GMutablePointer extract(const ForwardKey &key)
+  {
+    return values_.pop_as(key);
+  }
+
+  /* Remove the value for the given name from the container and remove it. */
+  template<typename T, typename ForwardKey> T extract(const ForwardKey &key)
+  {
+    GMutablePointer value = values_.pop_as(key);
+    const CPPType &type = *value.type();
+    BLI_assert(type.is<T>());
+    T return_value;
+    type.relocate_to_initialized(value.get(), &return_value);
+    return return_value;
+  }
+
+  template<typename T, typename ForwardKey> T lookup(const ForwardKey &key) const
+  {
+    GMutablePointer value = values_.lookup_as(key);
+    const CPPType &type = *value.type();
+    BLI_assert(type.is<T>());
+    T return_value;
+    type.copy_to_initialized(value.get(), &return_value);
+    return return_value;
+  }
+
+  template<typename ForwardKey> bool contains(const ForwardKey &key) const
+  {
+    return values_.contains_as(key);
+  }
+};
+
+}  // namespace blender::fn
diff --git a/source/blender/functions/FN_multi_function.hh b/source/blender/functions/FN_multi_function.hh
index bf431984946..d8924b3cf23 100644
--- a/source/blender/functions/FN_multi_function.hh
+++ b/source/blender/functions/FN_multi_function.hh
@@ -122,4 +122,17 @@ inline MFParamsBuilder::MFParamsBuilder(const class MultiFunction &fn, int64_t m
 
 extern const MultiFunction &dummy_multi_function;
 
+namespace multi_function_types {
+using fn::CPPType;
+using fn::GMutableSpan;
+using fn::GSpan;
+using fn::MFContext;
+using fn::MFContextBuilder;
+using fn::MFDataType;
+using fn::MFParams;
+using fn::MFParamsBuilder;
+using fn::MFParamType;
+using fn::MultiFunction;
+}  // namespace multi_function_types
+
 }  // namespace blender::fn