[Bf-blender-cvs] [e79c6515e7f] temp-trimesh-sculpt: * more trimesh work
Joseph Eagar
noreply at git.blender.org
Wed Oct 14 04:05:42 CEST 2020
Commit: e79c6515e7f5f71a3beb8f6f821c6e7d2d92f064
Author: Joseph Eagar
Date: Fri Sep 25 02:01:29 2020 -0700
Branches: temp-trimesh-sculpt
https://developer.blender.org/rBe79c6515e7f5f71a3beb8f6f821c6e7d2d92f064
* more trimesh work
===================================================================
M source/blender/blenkernel/BKE_pbvh.h
M source/blender/blenkernel/CMakeLists.txt
M source/blender/blenkernel/intern/pbvh_intern.h
A source/blender/blenkernel/intern/pbvh_trimesh.c
M source/blender/blenlib/BLI_threadsafe_mempool.h
M source/blender/blenlib/BLI_trimesh.h
M source/blender/blenlib/intern/BLI_threadsafe_mempool.c
M source/blender/blenlib/intern/BLI_trimesh.c
===================================================================
diff --git a/source/blender/blenkernel/BKE_pbvh.h b/source/blender/blenkernel/BKE_pbvh.h
index 16a7e4d38d0..a9ff2a3b46a 100644
--- a/source/blender/blenkernel/BKE_pbvh.h
+++ b/source/blender/blenkernel/BKE_pbvh.h
@@ -203,6 +203,7 @@ typedef enum {
PBVH_FACES,
PBVH_GRIDS,
PBVH_BMESH,
+ PBVH_TRIMESH
} PBVHType;
PBVHType BKE_pbvh_type(const PBVH *bvh);
diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt
index 1e230e5af3a..6233de63d22 100644
--- a/source/blender/blenkernel/CMakeLists.txt
+++ b/source/blender/blenkernel/CMakeLists.txt
@@ -194,6 +194,7 @@ set(SRC
intern/particle_distribute.c
intern/particle_system.c
intern/pbvh.c
+ intern/pbvh_trimesh.c
intern/pbvh_bmesh.c
intern/pbvh_parallel.cc
intern/pointcache.c
diff --git a/source/blender/blenkernel/intern/pbvh_intern.h b/source/blender/blenkernel/intern/pbvh_intern.h
index af92f11e219..fa054efbecb 100644
--- a/source/blender/blenkernel/intern/pbvh_intern.h
+++ b/source/blender/blenkernel/intern/pbvh_intern.h
@@ -105,6 +105,14 @@ struct PBVHNode {
float (*bm_orco)[3];
int (*bm_ortri)[3];
int bm_tot_ortri;
+
+ /* trimesh */
+ GSet *tm_faces;
+ GSet *tm_unique_verts;
+ GSet *tm_other_verts;
+ float (*tm_orco)[3];
+ int (*tm_ortri)[3];
+ int tm_tot_ortri;
};
typedef enum {
@@ -168,6 +176,11 @@ struct PBVH {
int cd_face_node_offset;
struct BMLog *bm_log;
+
+ /* trimesh data */
+ struct TriMesh *tm;
+ float tm_max_edge_len;
+ float tm_min_edge_len;
};
/* pbvh.c */
diff --git a/source/blender/blenkernel/intern/pbvh_trimesh.c b/source/blender/blenkernel/intern/pbvh_trimesh.c
new file mode 100644
index 00000000000..71054592e18
--- /dev/null
+++ b/source/blender/blenkernel/intern/pbvh_trimesh.c
@@ -0,0 +1,2242 @@
+/*
+* 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.
+*/
+
+/** \file
+* \ingroup bli
+*/
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_buffer.h"
+#include "BLI_ghash.h"
+#include "BLI_heap_simple.h"
+#include "BLI_math.h"
+#include "BLI_memarena.h"
+#include "BLI_utildefines.h"
+
+#include "BLI_threadsafe_mempool.h"
+#include "BLI_trimesh.h"
+
+#include "BKE_DerivedMesh.h"
+#include "BKE_ccg.h"
+#include "BKE_pbvh.h"
+
+#include "GPU_buffers.h"
+
+#include "bmesh.h"
+#include "pbvh_intern.h"
+
+#include <assert.h>
+
+/* Avoid skinny faces */
+#define USE_EDGEQUEUE_EVEN_SUBDIV
+#ifdef USE_EDGEQUEUE_EVEN_SUBDIV
+# include "BKE_global.h"
+#endif
+
+/* Support for only operating on front-faces */
+#define USE_EDGEQUEUE_FRONTFACE
+
+/* don't add edges into the queue multiple times */
+#define USE_EDGEQUEUE_TAG
+/**
+* Ensure we don't have dirty tags for the edge queue, and that they are left cleared.
+* (slow, even for debug mode, so leave disabled for now).
+*/
+#if defined(USE_EDGEQUEUE_TAG) && 0
+# if !defined(NDEBUG)
+# define USE_EDGEQUEUE_TAG_VERIFY
+# endif
+#endif
+
+// #define USE_VERIFY
+
+#ifdef USE_VERIFY
+static void pbvh_trimesh_verify(PBVH *bvh);
+#endif
+
+/** \} */
+
+/****************************** Building ******************************/
+
+#define _TRITEST(a, b, c) tri->v1 == a && tri->v2 == b && tri->v3 == c
+
+OptTri *trimesh_tri_exists(OptTriEdge *e, OptTriVert *opposite) {
+ for (int i=0; i<e->tris.length; i++) {
+ OptTri *tri = e->tris.items[i];
+
+ if (_TRITEST(e->v1, e->v2, opposite))
+ return tri;
+ if (_TRITEST(e->v1, opposite, e->v2))
+ return tri;
+ if (_TRITEST(e->v2, e->v1, opposite))
+ return tri;
+ if (_TRITEST(e->v2, opposite, e->v1))
+ return tri;
+ if (_TRITEST(opposite, e->v1, e->v2))
+ return tri;
+ if (_TRITEST(opposite, e->v2, e->v1))
+ return tri;
+ }
+}
+#undef _TRITEST
+
+/* Update node data after splitting */
+static void pbvh_trimesh_node_finalize(PBVH *bvh,
+ const int node_index,
+ const int cd_vert_node_offset,
+ const int cd_face_node_offset)
+{
+ GSetIterator gs_iter;
+ PBVHNode *n = &bvh->nodes[node_index];
+ bool has_visible = false;
+
+ /* Create vert hash sets */
+ n->tm_unique_verts = BLI_gset_ptr_new("trimesh_unique_verts");
+ n->tm_other_verts = BLI_gset_ptr_new("trimesh_other_verts");
+
+ BB_reset(&n->vb);
+
+ GSET_ITER (gs_iter, n->tm_faces) {
+ OptTri *f = BLI_gsetIterator_getKey(&gs_iter);
+
+ /* Update ownership of faces */
+ TRIMESH_ELEM_CD_SET_INT(f, cd_face_node_offset, node_index);
+
+ /* Update vertices */
+ for (int i=0; i<3; i++) {
+ OptTriVert *v = TRIMESH_GET_TRI_VERT(f, i);
+ OptTriEdge *e = TRIMESH_GET_TRI_EDGE(f, i);
+ OptTriLoop *l = TRIMESH_GET_TRI_LOOP(f, i);
+
+ if (TRIMESH_ELEM_CD_GET_INT(v, cd_vert_node_offset) != DYNTOPO_NODE_NONE) {
+ BLI_gset_add(n->tm_other_verts, v);
+ }
+ else {
+ BLI_gset_insert(n->tm_unique_verts, v);
+ TRIMESH_ELEM_CD_SET_INT(v, cd_vert_node_offset, node_index);
+ }
+
+ /* Update node bounding box */
+ BB_expand(&n->vb, v->co);
+ }
+ }
+
+ BLI_assert(n->vb.bmin[0] <= n->vb.bmax[0] && n->vb.bmin[1] <= n->vb.bmax[1] &&
+ n->vb.bmin[2] <= n->vb.bmax[2]);
+ n->orig_vb = n->vb;
+
+ /* Build GPU buffers for new node and update vertex normals */
+ BKE_pbvh_node_mark_rebuild_draw(n);
+
+ BKE_pbvh_node_fully_hidden_set(n, !has_visible);
+ n->flag |= PBVH_UpdateNormals;
+}
+
+/* Recursively split the node if it exceeds the leaf_limit */
+static void pbvh_trimesh_node_split(PBVH *bvh, const BBC *bbc_array, int node_index) {
+ const int cd_vert_node_offset = bvh->cd_vert_node_offset;
+ const int cd_face_node_offset = bvh->cd_face_node_offset;
+ PBVHNode *n = &bvh->nodes[node_index];
+
+ if (BLI_gset_len(n->tm_faces) <= bvh->leaf_limit) {
+ /* Node limit not exceeded */
+ pbvh_trimesh_node_finalize(bvh, node_index, cd_vert_node_offset, cd_face_node_offset);
+ return;
+ }
+
+ /* Calculate bounding box around primitive centroids */
+ BB cb;
+ BB_reset(&cb);
+ GSetIterator gs_iter;
+ GSET_ITER (gs_iter, n->tm_faces) {
+ const OptTri *f = BLI_gsetIterator_getKey(&gs_iter);
+ const BBC *bbc = &bbc_array[f->index];
+
+ BB_expand(&cb, bbc->bcentroid);
+ }
+
+ /* Find widest axis and its midpoint */
+ const int axis = BB_widest_axis(&cb);
+ const float mid = (cb.bmax[axis] + cb.bmin[axis]) * 0.5f;
+
+ /* Add two new child nodes */
+ const int children = bvh->totnode;
+ n->children_offset = children;
+ pbvh_grow_nodes(bvh, bvh->totnode + 2);
+
+ /* Array reallocated, update current node pointer */
+ n = &bvh->nodes[node_index];
+
+ /* Initialize children */
+ PBVHNode *c1 = &bvh->nodes[children], *c2 = &bvh->nodes[children + 1];
+ c1->flag |= PBVH_Leaf;
+ c2->flag |= PBVH_Leaf;
+ c1->tm_faces = BLI_gset_ptr_new_ex("tm_faces", BLI_gset_len(n->tm_faces) / 2);
+ c2->tm_faces = BLI_gset_ptr_new_ex("tm_faces", BLI_gset_len(n->tm_faces) / 2);
+
+ /* Partition the parent node's faces between the two children */
+ GSET_ITER (gs_iter, n->tm_faces) {
+ OptTri *f = BLI_gsetIterator_getKey(&gs_iter);
+ const BBC *bbc = &bbc_array[f->index];
+
+ if (bbc->bcentroid[axis] < mid) {
+ BLI_gset_insert(c1->tm_faces, f);
+ }
+ else {
+ BLI_gset_insert(c2->tm_faces, f);
+ }
+ }
+
+ /* Enforce at least one primitive in each node */
+ GSet *empty = NULL, *other;
+ if (BLI_gset_len(c1->tm_faces) == 0) {
+ empty = c1->tm_faces;
+ other = c2->tm_faces;
+ }
+ else if (BLI_gset_len(c2->tm_faces) == 0) {
+ empty = c2->tm_faces;
+ other = c1->tm_faces;
+ }
+ if (empty) {
+ GSET_ITER (gs_iter, other) {
+ void *key = BLI_gsetIterator_getKey(&gs_iter);
+ BLI_gset_insert(empty, key);
+ BLI_gset_remove(other, key, NULL);
+ break;
+ }
+ }
+
+ /* Clear this node */
+
+ /* Mark this node's unique verts as unclaimed */
+ if (n->tm_unique_verts) {
+ GSET_ITER (gs_iter, n->tm_unique_verts) {
+ OptTriVert *v = BLI_gsetIterator_getKey(&gs_iter);
+ TRIMESH_ELEM_CD_SET_INT(v, cd_vert_node_offset, DYNTOPO_NODE_NONE);
+ }
+ BLI_gset_free(n->tm_unique_verts, NULL);
+ }
+
+ /* Unclaim faces */
+ GSET_ITER (gs_iter, n->tm_faces) {
+ OptTri *f = BLI_gsetIterator_getKey(&gs_iter);
+ TRIMESH_ELEM_CD_SET_INT(f, cd_face_node_offset, DYNTOPO_NODE_NONE);
+ }
+ BLI_gset_free(n->tm_faces, NULL);
+
+ if (n->tm_other_verts) {
+ BLI_gset_free(n->tm_other_verts, NULL);
+ }
+
+ if (n->layer_disp) {
+ MEM_freeN(n->layer_disp);
+ }
+
+ n->tm_faces = NULL;
+ n->tm_unique_verts = NULL;
+ n->tm_other_verts = NULL;
+ n->layer_disp = NULL;
+
+ if (n->draw_buffers) {
+ GPU_pbvh_buffers_free(n->draw_buffers);
+ n->draw_buffers = NULL;
+ }
+ n->flag &= ~PBVH_Leaf;
+
+ /* Recurse */
+ pbvh_trimesh_node_split(bvh, bbc_array, children);
+ pbvh_trimesh_node_split(bvh, bbc_array, children + 1);
+
+ /* Array maybe reallocated, update current node pointer */
+ n = &bvh->nodes[node_index];
+
+ /* Update bounding box */
+ BB_reset(&n->vb);
+ BB_expand_with_bb(&n->vb, &bvh->nodes[n->children_offset].vb);
+ BB_expand_with_bb(&n->vb, &bvh->nodes[n->children_offset + 1].vb);
+ n->orig_vb = n->vb;
+}
+
+/* Recursively split the node if it exceeds the leaf_limit */
+static bool pbvh_trimesh_node_limit_ensure(PBVH *bvh, int node_index)
+{
+ GSet *tm_faces = bvh->nodes[node_index].tm_faces;
+ const int tm_faces_size = BLI_gset_len(tm_faces);
+ if (tm_faces_size <= bvh->leaf_limit) {
+ /* Node limit not exceeded */
+ return false;
+ }
+
+ /* For each BMFace, store the AABB and AABB centroid */
+ BBC *bbc_array = MEM_mallocN(sizeof(BBC) * tm_faces_size, "BBC");
+
+ GSetIterator
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list