[Bf-blender-cvs] [34664ee53f6] geometry-nodes-distribute-points: Add intial work on possion disk distribution

[Sebastian Parborg]

Commit: 34664ee53f6e69a9e94a0b12a1c880f416483a9e
Author: Sebastian Parborg
Date:   Mon Nov 23 20:56:57 2020 +0100
Branches: geometry-nodes-distribute-points
https://developer.blender.org/rB34664ee53f6e69a9e94a0b12a1c880f416483a9e

Add intial work on possion disk distribution

===================================================================

M	source/blender/blenlib/BLI_heap.h
M	source/blender/blenlib/intern/BLI_heap.c
A	source/blender/nodes/geometry/nodes/cyHeap.h
A	source/blender/nodes/geometry/nodes/cySampleElim.hh
M	source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc

===================================================================

diff --git a/source/blender/blenlib/BLI_heap.h b/source/blender/blenlib/BLI_heap.h
index 4cfb7945303..b0679f66c77 100644
--- a/source/blender/blenlib/BLI_heap.h
+++ b/source/blender/blenlib/BLI_heap.h
@@ -46,6 +46,7 @@ bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1);
 unsigned int BLI_heap_len(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1);
 HeapNode *BLI_heap_top(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1);
 float BLI_heap_top_value(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1);
+HeapNode *BLI_heap_idx(const Heap *heap, unsigned int idx) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1);
 void *BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1);
 void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value) ATTR_NONNULL(1, 2);
 void BLI_heap_node_value_update_ptr(Heap *heap, HeapNode *node, float value, void *ptr)
diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c
index a221820d4c4..70a5044e070 100644
--- a/source/blender/blenlib/intern/BLI_heap.c
+++ b/source/blender/blenlib/intern/BLI_heap.c
@@ -183,8 +183,8 @@ static struct HeapNode *heap_node_alloc(Heap *heap)
 
 static void heap_node_free(Heap *heap, HeapNode *node)
 {
-  node->ptr = heap->nodes.free;
-  heap->nodes.free = node;
+  // node->ptr = heap->nodes.free;
+  // heap->nodes.free = node;
 }
 
 /** \} */
@@ -332,6 +332,16 @@ float BLI_heap_top_value(const Heap *heap)
   return heap->tree[0]->value;
 }
 
+/**
+ * Return the heap node at idx.
+ */
+HeapNode *BLI_heap_idx(const Heap *heap, unsigned int idx)
+{
+  BLI_assert(idx < heap->size);
+
+  return heap->tree[idx];
+}
+
 /**
  * Pop the top node off the heap and return its pointer.
  */
diff --git a/source/blender/nodes/geometry/nodes/cyHeap.h b/source/blender/nodes/geometry/nodes/cyHeap.h
new file mode 100644
index 00000000000..cfc34e684a5
--- /dev/null
+++ b/source/blender/nodes/geometry/nodes/cyHeap.h
@@ -0,0 +1,279 @@
+// cyCodeBase by Cem Yuksel
+// [www.cemyuksel.com]
+//-------------------------------------------------------------------------------
+//! \file   cyHeap.h 
+//! \author Cem Yuksel
+//!
+//! \brief  A general-purpose heap class
+//! 
+//! This file includes a general-purpose heap class.
+//!
+//-------------------------------------------------------------------------------
+//
+// Copyright (c) 2016, Cem Yuksel <cem at cemyuksel.com>
+// All rights reserved.
+// 
+// Permission is hereby granted, free of charge, to any person obtaining a copy 
+// of this software and associated documentation files (the "Software"), to deal 
+// in the Software without restriction, including without limitation the rights 
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 
+// copies of the Software, and to permit persons to whom the Software is 
+// furnished to do so, subject to the following conditions:
+// 
+// The above copyright notice and this permission notice shall be included in all 
+// copies or substantial portions of the Software.
+// 
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 
+// SOFTWARE.
+// 
+//-------------------------------------------------------------------------------
+
+#ifndef _CY_HEAP_H_INCLUDED_
+#define _CY_HEAP_H_INCLUDED_
+
+//-------------------------------------------------------------------------------
+
+#include <assert.h>
+#include <stdint.h>
+
+//-------------------------------------------------------------------------------
+namespace cy {
+//-------------------------------------------------------------------------------
+
+//! A general-purpose max-heap structure that allows random access and updates.
+//!
+//! The main data can be kept in an external array or within the Heap class.
+
+template <typename DATA_TYPE, typename SIZE_TYPE=size_t> 
+class Heap
+{
+public:
+	//////////////////////////////////////////////////////////////////////////!//!//!
+	//!@name Constructor and Destructor
+
+	Heap() : size(0), heapItemCount(0), data(nullptr), heap(nullptr), heapPos(nullptr), deleteData(false) {}
+	~Heap() { Clear(); }
+
+	//////////////////////////////////////////////////////////////////////////!//!//!
+	//!@name Initialization methods
+
+	//! Deletes all data owned by the class.
+	void Clear() { ClearData(); ClearHeap(); }
+
+	//! Copies the main data items from an array into the internal storage of this class.
+	void CopyData( DATA_TYPE const *items, SIZE_TYPE itemCount )
+	{
+		ClearData();
+		size = itemCount;
+		data = new DATA_TYPE[size];
+		for ( SIZE_TYPE i=0; i<size; i++ ) data[i] = items[i];
+		deleteData = true;
+	}
+
+	//! Moves the main data items from an array to the internal storage of this class.
+	//! Modifying this array externally can invalidate the heap structure.
+	//! The given array must NOT be deleted externally.
+	//! The given items pointer still points to the same data, but the class claims
+	//! ownership of the data. Therefore, when the class object is deleted, the data
+	//! items are deleted as well. If this is not desirable, use SetDataPointer.
+	void MoveData( DATA_TYPE *items, SIZE_TYPE itemCount )
+	{
+		ClearData();
+		data = items;
+		size = itemCount;
+		deleteData = true;
+	}
+
+	//! Sets the data pointer of this class. This method is used for sharing the items
+	//! array with other structures. Unlike setting the main data using the MoveData
+	//! method, when SetDataPointer is used, the class does NOT claim ownership
+	//! of the data. Therefore, it does not deallocate memory used for the main data
+	//! when it is deleted, and the data items must be deleted externally.
+	//! However, the data items must NOT be deleted while an object of this class is used.
+	void SetDataPointer( DATA_TYPE *items, SIZE_TYPE itemCount )
+	{
+		ClearData();
+		data = items;
+		size = itemCount;
+		deleteData = false;
+	}
+
+	//! The Build method builds the heap structure using the main data. Therefore,
+	//! the main data must be set using either CopyData, MoveData, or SetDataPointer
+	//! before calling the Build method.
+	void Build()
+	{
+		ClearHeap();
+		heapItemCount = size;
+		heap    = new SIZE_TYPE[ size + 1 ];
+		heapPos = new SIZE_TYPE[ size ];
+		for ( SIZE_TYPE i=0; i< heapItemCount; i++ ) heapPos[i] = i+1;
+		for ( SIZE_TYPE i=1; i<=heapItemCount; i++ ) heap   [i] = i-1;
+		if ( heapItemCount <= 1 ) return;
+		for ( SIZE_TYPE ix = heapItemCount/2; ix>0; ix-- ) HeapMoveDown(ix);
+	}
+
+	//////////////////////////////////////////////////////////////////////////!//!//!
+	//!@name Access and manipulation methods
+
+	//! Returns the item from the main data with the given id.
+	DATA_TYPE const & GetItem( SIZE_TYPE id ) const { assert(id<size); return data[id]; }
+
+	//! Sets the item with the given id and updates the heap structure accordingly.
+	//! Returns false if the item is not in the heap anymore (removed by Pop) or if its heap position is not changed.
+	bool SetItem( SIZE_TYPE id, DATA_TYPE const &item ) { assert(id<size); data[id]=item; return MoveItem(id); }
+
+	//! Moves the item with the given id to the correct position in the heap.
+	//! This method is useful for fixing the heap position after an item is modified externally.
+	//! Returns false if the item is not in the heap anymore (removed by Pop) or if its heap position is not changed.
+	bool MoveItem( SIZE_TYPE id ) { return HeapOrder(heapPos[id]); }
+
+	//! Moves the item with the given id towards the top of the heap.
+	//! This method is useful for fixing the heap position after an item is modified externally to increase its priority.
+	//! Returns false if the item is not in the heap anymore (removed by Pop) or if its heap position is not changed.
+	bool MoveItemUp( SIZE_TYPE id ) { return HeapMoveUp(heapPos[id]); }
+
+	//! Moves the item with the given id towards the top of the heap.
+	//! This method is useful for fixing the heap position after an item is modified externally to decrease its priority.
+	//! Returns false if the item is not in the heap anymore (removed by Pop) or if its heap position is not changed.
+	bool MoveItemDown( SIZE_TYPE id ) { return HeapMoveDown(heapPos[id]); }
+
+	//! Returns if the item with the given id is in the heap or removed by Pop.
+	bool IsInHeap( SIZE_TYPE id ) const { assert(id<size); return heapPos[id]<=heapItemCount; }
+
+	//! Returns the number of items in the heap.
+	SIZE_TYPE NumItemsInHeap() const { return heapItemCount; }
+	
+	//! Returns the item from the heap with the given heap position.
+	//! Note that items that are removed from the heap appear in the inverse order 
+	//! with which they were removed after the last item in the heap.
+	DATA_TYPE const & GetFromHeap( SIZE_TYPE heapIndex ) const { assert(heapIndex<size); return data[heap[heapIndex+1]]; }
+
+	//! Returns the id of the item from the heap with the given heap position.
+	//! Note that items that are removed from the heap appear in the inverse order 
+	//! with which they were removed after the last item in the heap.
+	SIZE_TYPE GetIDFromHeap( SIZE_TYPE heapIndex ) const { assert(heapIndex<size); return heap[heapIndex+1]; }
+
+	//! Returns the item at the top of the heap.
+	DATA_TYPE const & GetTopItem() const { assert(size>=1); return data[heap[1]]; }
+
+	//! Returns the id of the item at the top of the heap.
+	SIZE_TYPE GetTopItemID() const { assert(size>=1); return heap[1]; }
+
+	//! Removes and returns the item at the top of the heap.
+	//! The removed item is not deleted, but it is removed from the heap
+	//! by placing it right after the last item in the heap.
+	void Pop( DATA_TYPE &item )
+	{
+		Pop();
+		item = data[ heap[heapItemCount] ];
+	}
+
+	//! Removes the item at the top of the heap.
+	//! The removed item is not deleted, but it is removed from the heap
+	//! by placing it right after the last item in the heap.
+	void Pop()
+	{
+

@@ Diff output truncated at 10240 characters. @@