[Bf-blender-cvs] [dc02d5439bd] temp-trimesh-sculpt: add trimesh and thread safe mempool code
Joseph Eagar
noreply at git.blender.org
Wed Oct 14 04:05:42 CEST 2020
Commit: dc02d5439bdb32fffce519030f34816938320252
Author: Joseph Eagar
Date: Thu Sep 24 22:06:43 2020 -0700
Branches: temp-trimesh-sculpt
https://developer.blender.org/rBdc02d5439bdb32fffce519030f34816938320252
add trimesh and thread safe mempool code
===================================================================
A source/blender/blenlib/BLI_threadsafe_mempool.h
A source/blender/blenlib/BLI_trimesh.h
M source/blender/blenlib/CMakeLists.txt
A source/blender/blenlib/intern/BLI_threadsafe_mempool.c
A source/blender/blenlib/intern/BLI_trimesh.c
===================================================================
diff --git a/source/blender/blenlib/BLI_threadsafe_mempool.h b/source/blender/blenlib/BLI_threadsafe_mempool.h
new file mode 100644
index 00000000000..e900651856b
--- /dev/null
+++ b/source/blender/blenlib/BLI_threadsafe_mempool.h
@@ -0,0 +1,47 @@
+/*
+ * 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.
+ *
+ * The Original Code is Copyright (C) 2008 Blender Foundation.
+ * All rights reserved.
+ */
+#ifndef _BLI_THREADSAFE_MEMPOOL_H
+#define _BLI_THREADSAFE_MEMPOOL_H
+
+struct BLI_ThreadSafePool;
+typedef struct BLI_ThreadSafePool BLI_ThreadSafePool;
+
+struct BLI_ThreadSafePool* BLI_safepool_create(int elemsize, int chunksize, int maxthread);
+void* BLI_safepool_alloc(struct BLI_ThreadSafePool *pool, int threadnr);
+
+void BLI_safepool_free(struct BLI_ThreadSafePool*pool, void *elem);
+bool BLI_safepool_is_dead(struct BLI_ThreadSafePool *pool, void *elem);
+
+void BLI_safepool_threaded_free(struct BLI_ThreadSafePool*pool, void *elem, int threadnr);
+int BLI_safepool_length(struct BLI_ThreadSafePool*pool);
+void BLI_safepool_destroy(struct BLI_ThreadSafePool* pool);
+
+typedef struct ThreadSafePoolIter {
+ struct BLI_ThreadSafePool* pool;
+ int thread;
+ void *chunk;
+ int i;
+} ThreadSafePoolIter;
+
+void BLI_safepool_iternew(struct BLI_ThreadSafePool* pool, ThreadSafePoolIter* iter);
+void BLI_safepool_iterfree(ThreadSafePoolIter* iter);
+void* BLI_safepool_iterstep(ThreadSafePoolIter* iter);
+void BLI_safepool_threaded_free(struct BLI_ThreadSafePool* pool, void* elem, int thread);
+
+#endif /* _BLI_THREADSAFE_MEMPOOL_H */
diff --git a/source/blender/blenlib/BLI_trimesh.h b/source/blender/blenlib/BLI_trimesh.h
new file mode 100644
index 00000000000..9c84155e8a7
--- /dev/null
+++ b/source/blender/blenlib/BLI_trimesh.h
@@ -0,0 +1,107 @@
+//optimized thread-safe triangle mesh library with topological info
+
+#include "BLI_threads.h"
+#include "BLI_threadsafe_mempool.h"
+
+
+struct OptTriVert;
+struct OptTriEdge;
+struct OptTri;
+
+#define OPTELEM_HEAD(type) struct type *next, *prev; int threadtag;
+
+typedef struct OptElem {
+ OPTELEM_HEAD(OptElem)
+} OptElem;
+
+typedef struct optmesh_simplelist {
+ void **items;
+ int _size, length;
+ bool is_pool_allocd;
+} optmesh_simplelist;
+
+typedef struct OptTriVert {
+ OPTELEM_HEAD(OptTriVert)
+ float co[3];
+ float no[3];
+
+ optmesh_simplelist edges;
+} OptTriVert;
+
+typedef struct OptTriEdge {
+ OPTELEM_HEAD(OptTriEdge)
+ OptTriVert *v1, *v2;
+ optmesh_simplelist tris;
+} OptTriEdge;
+
+typedef struct OptTri {
+ OPTELEM_HEAD(OptTri)
+
+ OptTriVert *v1, *v2, *v3;
+ OptTriEdge *e1, *e2, *e3;
+
+ float no[3];
+} OptTri;
+
+typedef struct OptTriIsland {
+ OptTri **tris;
+ int tottri;
+ OptTriVert **verts;
+ int totvert;
+ int tag;
+} OptTriIsland;
+
+struct BLI_ThreadSafePool;
+
+#define MAX_TRIMESH_POOLS 5
+
+typedef struct OptTriMesh {
+ struct BLI_ThreadSafePool* pools[MAX_TRIMESH_POOLS];
+
+ int totvert, tottri, totedge;
+ int maxthread;
+ SpinLock global_lock;
+} OptTriMesh;
+
+typedef struct OptTriMeshIter {
+ int pool;
+ ThreadSafePoolIter iter;
+} OptTriMeshIter;
+
+#define TRIMESH_NEED_TAG -1
+#define TRIMESH_BOUNDARY -2
+#define TRIMESH_BOUNDARY_TEMP -3
+#define TRIMESH_TAG_CLEAR -4
+
+#define TRIMESH_VERT 1
+#define TRIMESH_EDGE 2
+#define TRIMESH_TRI 4
+
+OptTriMesh* BLI_trimesh_new(int maxthread);
+void BLI_trimesh_free(OptTriMesh *tm);
+void BLI_trimesh_vert_iternew(OptTriMesh *tm, OptTriMeshIter* iter);
+void BLI_trimesh_edge_iternew(OptTriMesh *tm, OptTriMeshIter* iter);
+void BLI_trimesh_tri_iternew(OptTriMesh *tm, OptTriMeshIter* iter);
+void BLI_trimesh_iterstep(OptTriMeshIter* iter);
+void BLI_trimesh_add(OptTriMesh *tm, float* vertCos, float* vertNos, int totvert, int* triIndices, int tottri, int threadnr);
+
+void BLI_trimesh_kill_edge(OptTriMesh *tm, OptTriEdge *e, int threadnr, bool kill_verts);
+void BLI_trimesh_kill_vert(OptTriMesh *tm, OptTriVert *v, int threadnr);
+void BLI_trimesh_kill_tri(OptTriMesh *tm, OptTri *tri, int threadnr, bool kill_edges, bool kill_verts);
+
+//primary interface to run threaded jobs
+typedef void (*OptTriMeshJob)(OptTriMesh *tm, void **elements, int totelem, int threadnr, void *userdata);
+void BLI_trimesh_foreach_tris(OptTriMesh *tm, OptTri **tris, int tottri, OptTriMeshJob job, int maxthread, void *userdata);
+
+//yes, the input is an array of triangles, even though the jobs are fed vertices.
+void BLI_trimesh_foreach_verts(OptTriMesh *tm, OptTri **tris, int tottri, OptTriMeshJob job, int maxthread, void *userdata);
+
+//low-level api functions used by BLI_trimesh_foreach_XXX
+//if tottris is -1 then all triangles will be tagged
+void BLI_trimesh_thread_tag(OptTriMesh *tm, OptTri** tris, int tottri);
+void BLI_trimesh_clear_threadtags(OptTriMesh *tm);
+void BLI_trimesh_tag_thread_boundaries(OptTriMesh *tm, OptTri **tris, int tottri);
+
+//called after BLI_trimesh_thread_tag
+//last island is always boundary triangles
+void BLI_trimesh_build_islands(OptTriMesh *tm, OptTri **tris, int tottri, OptTriIsland** r_islands, int *r_totisland);
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 5f5145cab70..61cfd78f966 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -40,6 +40,7 @@ set(SRC
intern/BLI_dial_2d.c
intern/BLI_dynstr.c
intern/BLI_filelist.c
+ intern/BLI_trimesh.c
intern/BLI_ghash.c
intern/BLI_ghash_utils.c
intern/BLI_heap.c
@@ -50,6 +51,7 @@ set(SRC
intern/BLI_linklist_lockfree.c
intern/BLI_memarena.c
intern/BLI_memblock.c
+ intern/BLI_threadsafe_mempool.c
intern/BLI_memiter.c
intern/BLI_mempool.c
intern/BLI_timer.c
diff --git a/source/blender/blenlib/intern/BLI_threadsafe_mempool.c b/source/blender/blenlib/intern/BLI_threadsafe_mempool.c
new file mode 100644
index 00000000000..88787cf12d8
--- /dev/null
+++ b/source/blender/blenlib/intern/BLI_threadsafe_mempool.c
@@ -0,0 +1,313 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdint.h>
+
+#include "BLI_threadsafe_mempool.h"
+#include "BLI_threads.h"
+#include "BLI_utildefines.h"
+#include "MEM_guardedalloc.h"
+#include "atomic_ops.h"
+#include "BLI_listbase.h"
+
+#define POOL_CHUNK_MAGIC ('p' | ('o' << 8) | ('o' << 16) | ('l' || 24))
+#define DEAD_MAGIC ('d' | ('e' << 8) | ('a' << 16) | ('d' || 24))
+
+//#define BLI_SAFEPOOL_HAVE_LENGTH
+
+//keep eight-byte aligned!
+typedef struct poolchunk {
+ struct poolchunk* next, * prev;
+ unsigned int threadnr, magic;
+} poolchunk;
+
+typedef struct deadelem {
+ struct deadelem *next;
+ int dead_magic;
+} deadelem;
+
+typedef struct pool_thread_data {
+ ListBase chunks;
+ void* freehead;
+ SpinLock lock;
+ unsigned int used;
+} pool_thread_data;
+
+typedef struct BLI_ThreadSafePool {
+ pool_thread_data* threadchunks;
+ int maxthread;
+ SpinLock global_lock;
+
+#ifdef BLI_SAFEPOOL_HAVE_LENGTH
+ unsigned int length;
+#endif
+ size_t esize, csize;
+} BLI_ThreadSafePool;
+
+static int getalign(int size) {
+ if (size & 15) {
+ return size + (16 - (size & 15));
+ }
+
+ return size;
+}
+
+static size_t get_chunk_size(BLI_ThreadSafePool* pool) {
+ return getalign(sizeof(pool_thread_data) + pool->esize*pool->csize);
+}
+
+static poolchunk* get_chunk_from_elem(BLI_ThreadSafePool *pool, void* elem) {
+ uintptr_t addr = (uintptr_t) elem;
+ uintptr_t size = get_chunk_size(pool);
+
+ if (!elem) {
+ return NULL;
+ }
+
+ addr = addr - (addr % size);
+
+ poolchunk *chunk = (poolchunk*)addr;
+
+ if (chunk->magic != POOL_CHUNK_MAGIC) {
+ return NULL;
+ }
+
+ return chunk;
+}
+
+static poolchunk *new_chunk(BLI_ThreadSafePool *pool, pool_thread_data* thread_data) {
+ size_t size = get_chunk_size(pool);
+ size_t esize = pool->esize;
+
+ //align size?
+ /*
+ if (size & 7) {
+ size += 8 - (size & 7);
+ };*/
+
+ poolchunk* chunk = MEM_mallocN_aligned(size, getalign(size), "safepool chunk");
+
+ chunk->magic = POOL_CHUNK_MAGIC;
+ chunk->threadnr = thread_data - pool->threadchunks;
+
+ BLI_addtail(&thread_data->chunks, chunk);
+ deadelem *first = NULL;
+
+ for (size_t i = 0; i < pool->csize-1; i++) {
+ deadelem *de = (deadelem*)(((char*)chunk) + sizeof(poolchunk) + esize*i);
+
+ if (i == 0) {
+ first = de;
+ }
+
+ de->next = de + 1;
+ de->dead_magic = DEAD_MAGIC;
+ }
+
+ deadelem *de = (deadelem*)(((char*)chunk) + sizeof(poolchunk) + esize*(pool->csize-1));
+ de->next = thread_data->freehead;
+ de->dead_magic = DEAD_MAGIC;
+
+ thread_data->freehead = first;
+
+ return chunk;
+}
+
+BLI_ThreadSafePool* BLI_safepool_create(int elemsize, int chunksize, int maxthread) {
+ BLI_ThreadSafePool* pool = MEM_callocN(sizeof(*pool), "BLI_ThreadSafePool");
+
+ elemsize = MAX2(elemsize, sizeof(void*)*2);
+
+ pool->maxthread = maxthread;
+ pool->threadchunks = MEM_callocN(sizeof(pool_thread_data) * maxthread, "pool->threadchunks");
+ pool->esize = elemsize;
+ pool->csize = chunksize;
+
+ BLI_spin_init(&pool->global_lock);
+
+ for (int i = 0; i < maxthread; i++) {
+ BLI_spin_init(&pool->threadchunks[i].lock);
+ new_chunk(pool, pool->threadchunks);
+ }
+
+ return pool;
+}
+
+bool BLI_safepool_elem_is_dead(BLI_ThreadSafePool *pool, void *elem) {
+ deadelem *de = (deadelem*)elem;
+
+ return de->dead_magic == DEAD_MAGIC;
+}
+
+void BLI_safepool_destroy(BLI_ThreadSafePool* pool) {
+ poolchunk* chunk;
+ int i;
+
+ //wait for all threads to end?
+ //BLI_spin_lock(&pool->global_lock);
+ //BLI_spin_unlock(&pool->global_lock);
+
+ for (i = 0; i < pool->maxthread; i++) {
+ B
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list