From a6bee579e9c6e144f731072b93d004af7b2011c5 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sat, 15 Dec 2012 15:59:25 +0000 Subject: move pbvh into BKE, it used many BKE bad level includes. now blenlib/BLI doesn't depend on any blenkern/BKE functions, there are still some bad level includes but these are only to access G.background and the blender version define. --- source/blender/blenkernel/BKE_pbvh.h | 270 +++ source/blender/blenkernel/CMakeLists.txt | 5 +- source/blender/blenkernel/intern/DerivedMesh.c | 2 +- source/blender/blenkernel/intern/action.c | 1 - source/blender/blenkernel/intern/armature.c | 1 - source/blender/blenkernel/intern/blender.c | 2 +- source/blender/blenkernel/intern/bpath.c | 3 +- source/blender/blenkernel/intern/brush.c | 1 - source/blender/blenkernel/intern/cdderivedmesh.c | 2 +- source/blender/blenkernel/intern/curve.c | 1 - source/blender/blenkernel/intern/editderivedmesh.c | 2 +- source/blender/blenkernel/intern/image.c | 1 - source/blender/blenkernel/intern/lattice.c | 1 - source/blender/blenkernel/intern/material.c | 1 - source/blender/blenkernel/intern/mball.c | 2 - source/blender/blenkernel/intern/mesh.c | 1 - source/blender/blenkernel/intern/multires.c | 2 +- source/blender/blenkernel/intern/object.c | 3 +- source/blender/blenkernel/intern/particle.c | 1 - source/blender/blenkernel/intern/pbvh.c | 1909 +++++++++++++++++++ source/blender/blenkernel/intern/speaker.c | 1 - source/blender/blenkernel/intern/subsurf_ccg.c | 2 +- source/blender/blenkernel/intern/texture.c | 1 - source/blender/blenkernel/intern/world.c | 1 - source/blender/blenlib/BLI_pbvh.h | 270 --- source/blender/blenlib/CMakeLists.txt | 6 +- source/blender/blenlib/SConscript | 4 +- source/blender/blenlib/intern/BLI_ghash.c | 2 +- source/blender/blenlib/intern/endian_switch.c | 2 +- source/blender/blenlib/intern/fileops.c | 2 +- source/blender/blenlib/intern/freetypefont.c | 2 - source/blender/blenlib/intern/path_util.c | 2 +- source/blender/blenlib/intern/pbvh.c | 1911 -------------------- source/blender/blenlib/intern/winstuff.c | 2 +- source/blender/editors/sculpt_paint/paint_hide.c | 2 +- source/blender/editors/sculpt_paint/paint_mask.c | 3 +- source/blender/editors/sculpt_paint/sculpt.c | 2 +- .../blender/editors/sculpt_paint/sculpt_intern.h | 2 +- source/blender/makesrna/intern/rna_sculpt_paint.c | 3 +- 39 files changed, 2204 insertions(+), 2227 deletions(-) create mode 100644 source/blender/blenkernel/BKE_pbvh.h create mode 100644 source/blender/blenkernel/intern/pbvh.c delete mode 100644 source/blender/blenlib/BLI_pbvh.h delete mode 100644 source/blender/blenlib/intern/pbvh.c (limited to 'source') diff --git a/source/blender/blenkernel/BKE_pbvh.h b/source/blender/blenkernel/BKE_pbvh.h new file mode 100644 index 00000000000..59ecdb359c9 --- /dev/null +++ b/source/blender/blenkernel/BKE_pbvh.h @@ -0,0 +1,270 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * 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. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_PBVH_H__ +#define __BLI_PBVH_H__ + +/** \file BLI_pbvh.h + * \ingroup bli + * \brief A BVH for high poly meshes. + */ + +#include "BLI_bitmap.h" + +struct CCGElem; +struct CCGKey; +struct CustomData; +struct DMFlagMat; +struct DMGridAdjacency; +struct ListBase; +struct MFace; +struct MVert; +struct PBVH; +struct PBVHNode; + +typedef struct PBVH PBVH; +typedef struct PBVHNode PBVHNode; + +typedef struct { + float (*co)[3]; +} PBVHProxyNode; + +/* Callbacks */ + +/* returns 1 if the search should continue from this node, 0 otherwise */ +typedef int (*BLI_pbvh_SearchCallback)(PBVHNode *node, void *data); + +typedef void (*BLI_pbvh_HitCallback)(PBVHNode *node, void *data); +typedef void (*BLI_pbvh_HitOccludedCallback)(PBVHNode *node, void *data, float *tmin); + +/* Building */ + +PBVH *BLI_pbvh_new(void); +void BLI_pbvh_build_mesh(PBVH *bvh, struct MFace *faces, struct MVert *verts, + int totface, int totvert, struct CustomData *vdata); +void BLI_pbvh_build_grids(PBVH *bvh, struct CCGElem **grid_elems, + struct DMGridAdjacency *gridadj, int totgrid, + struct CCGKey *key, void **gridfaces, struct DMFlagMat *flagmats, + unsigned int **grid_hidden); +void BLI_pbvh_free(PBVH *bvh); + +/* Hierarchical Search in the BVH, two methods: + * - for each hit calling a callback + * - gather nodes in an array (easy to multithread) */ + +void BLI_pbvh_search_callback(PBVH *bvh, + BLI_pbvh_SearchCallback scb, void *search_data, + BLI_pbvh_HitCallback hcb, void *hit_data); + +void BLI_pbvh_search_gather(PBVH *bvh, + BLI_pbvh_SearchCallback scb, void *search_data, + PBVHNode ***array, int *tot); + +/* Raycast + * the hit callback is called for all leaf nodes intersecting the ray; + * it's up to the callback to find the primitive within the leaves that is + * hit first */ + +void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitOccludedCallback cb, void *data, + const float ray_start[3], const float ray_normal[3], + int original); + +int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3], + const float ray_start[3], const float ray_normal[3], + float *dist); + +/* Drawing */ + +void BLI_pbvh_node_draw(PBVHNode *node, void *data); +void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3], + int (*setMaterial)(int, void *attribs)); + +/* PBVH Access */ +typedef enum { + PBVH_FACES, + PBVH_GRIDS, +} PBVHType; + +PBVHType BLI_pbvh_type(const PBVH *bvh); + +/* multires hidden data, only valid for type == PBVH_GRIDS */ +unsigned int **BLI_pbvh_grid_hidden(const PBVH *bvh); + +/* multires level, only valid for type == PBVH_GRIDS */ +void BLI_pbvh_get_grid_key(const PBVH *pbvh, struct CCGKey *key); + +/* Node Access */ + +typedef enum { + PBVH_Leaf = 1, + + PBVH_UpdateNormals = 2, + PBVH_UpdateBB = 4, + PBVH_UpdateOriginalBB = 8, + PBVH_UpdateDrawBuffers = 16, + PBVH_UpdateRedraw = 32, + + PBVH_RebuildDrawBuffers = 64, + PBVH_FullyHidden = 128 +} PBVHNodeFlags; + +void BLI_pbvh_node_mark_update(PBVHNode *node); +void BLI_pbvh_node_mark_rebuild_draw(PBVHNode *node); +void BLI_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden); + +void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node, + int **grid_indices, int *totgrid, int *maxgrid, int *gridsize, + struct CCGElem ***grid_elems, struct DMGridAdjacency **gridadj); +void BLI_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node, + int *uniquevert, int *totvert); +void BLI_pbvh_node_get_verts(PBVH *bvh, PBVHNode *node, + int **vert_indices, struct MVert **verts); + +void BLI_pbvh_node_get_BB(PBVHNode * node, float bb_min[3], float bb_max[3]); +void BLI_pbvh_node_get_original_BB(PBVHNode * node, float bb_min[3], float bb_max[3]); + +float BLI_pbvh_node_get_tmin(PBVHNode *node); + +/* test if AABB is at least partially inside the planes' volume */ +int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data); +/* test if AABB is at least partially outside the planes' volume */ +int BLI_pbvh_node_planes_exclude_AABB(PBVHNode *node, void *data); + +/* Update Normals/Bounding Box/Draw Buffers/Redraw and clear flags */ + +void BLI_pbvh_update(PBVH *bvh, int flags, float (*face_nors)[3]); +void BLI_pbvh_redraw_BB(PBVH * bvh, float bb_min[3], float bb_max[3]); +void BLI_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***gridfaces, int *totface); +void BLI_pbvh_grids_update(PBVH *bvh, struct CCGElem **grid_elems, + struct DMGridAdjacency *gridadj, void **gridfaces, + struct DMFlagMat *flagmats, unsigned int **grid_hidden); + +/* vertex deformer */ +float (*BLI_pbvh_get_vertCos(struct PBVH *pbvh))[3]; +void BLI_pbvh_apply_vertCos(struct PBVH *pbvh, float (*vertCos)[3]); +int BLI_pbvh_isDeformed(struct PBVH *pbvh); + + +/* Vertex Iterator */ + +/* this iterator has quite a lot of code, but it's designed to: + * - allow the compiler to eliminate dead code and variables + * - spend most of the time in the relatively simple inner loop */ + +/* note: PBVH_ITER_ALL does not skip hidden vertices, + * PBVH_ITER_UNIQUE does */ +#define PBVH_ITER_ALL 0 +#define PBVH_ITER_UNIQUE 1 + +typedef struct PBVHVertexIter { + /* iteration */ + int g; + int width; + int height; + int gx; + int gy; + int i; + + /* grid */ + struct CCGElem **grids; + struct CCGElem *grid; + struct CCGKey *key; + BLI_bitmap *grid_hidden, gh; + int *grid_indices; + int totgrid; + int gridsize; + + /* mesh */ + struct MVert *mverts; + int totvert; + int *vert_indices; + float *vmask; + + /* result: these are all computed in the macro, but we assume + * that compiler optimization's will skip the ones we don't use */ + struct MVert *mvert; + float *co; + short *no; + float *fno; + float *mask; +} PBVHVertexIter; + +#ifdef _MSC_VER +#pragma warning (disable:4127) // conditional expression is constant +#endif + +void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node, + PBVHVertexIter *vi, int mode); + +#define BLI_pbvh_vertex_iter_begin(bvh, node, vi, mode) \ + pbvh_vertex_iter_init(bvh, node, &vi, mode); \ + \ + for (vi.i = 0, vi.g = 0; vi.g < vi.totgrid; vi.g++) { \ + if (vi.grids) { \ + vi.width = vi.gridsize; \ + vi.height = vi.gridsize; \ + vi.grid = vi.grids[vi.grid_indices[vi.g]]; \ + if (mode == PBVH_ITER_UNIQUE) \ + vi.gh = vi.grid_hidden[vi.grid_indices[vi.g]]; \ + } \ + else { \ + vi.width = vi.totvert; \ + vi.height = 1; \ + } \ + \ + for (vi.gy = 0; vi.gy < vi.height; vi.gy++) { \ + for (vi.gx = 0; vi.gx < vi.width; vi.gx++, vi.i++) { \ + if (vi.grid) { \ + vi.co = CCG_elem_co(vi.key, vi.grid); \ + vi.fno = CCG_elem_no(vi.key, vi.grid); \ + vi.mask = vi.key->has_mask ? CCG_elem_mask(vi.key, vi.grid) : NULL; \ + vi.grid = CCG_elem_next(vi.key, vi.grid); \ + if (vi.gh) { \ + if (BLI_BITMAP_GET(vi.gh, vi.gy * vi.gridsize + vi.gx)) \ + continue; \ + } \ + } \ + else { \ + vi.mvert = &vi.mverts[vi.vert_indices[vi.gx]]; \ + if (mode == PBVH_ITER_UNIQUE && vi.mvert->flag & ME_HIDE) \ + continue; \ + vi.co = vi.mvert->co; \ + vi.no = vi.mvert->no; \ + if (vi.vmask) \ + vi.mask = &vi.vmask[vi.vert_indices[vi.gx]]; \ + } \ + +#define BLI_pbvh_vertex_iter_end \ + } \ + } \ + } + +void BLI_pbvh_node_get_proxies(PBVHNode *node, PBVHProxyNode **proxies, int *proxy_count); +void BLI_pbvh_node_free_proxies(PBVHNode *node); +PBVHProxyNode *BLI_pbvh_node_add_proxy(PBVH *bvh, PBVHNode *node); +void BLI_pbvh_gather_proxies(PBVH *pbvh, PBVHNode ***nodes, int *totnode); + +//void BLI_pbvh_node_BB_reset(PBVHNode *node); +//void BLI_pbvh_node_BB_expand(PBVHNode *node, float co[3]); + +void pbvh_show_diffuse_color_set(PBVH *bvh, int show_diffuse_color); + +#endif /* __BLI_PBVH_H__ */ + diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt index 57996630c28..b350cb718c8 100644 --- a/source/blender/blenkernel/CMakeLists.txt +++ b/source/blender/blenkernel/CMakeLists.txt @@ -122,6 +122,7 @@ set(SRC intern/paint.c intern/particle.c intern/particle_system.c + intern/pbvh.c intern/pointcache.c intern/property.c intern/report.c @@ -149,7 +150,6 @@ set(SRC intern/writeavi.c intern/writeframeserver.c - BKE_DerivedMesh.h BKE_action.h BKE_anim.h @@ -161,6 +161,7 @@ set(SRC BKE_bmfont_types.h BKE_boids.h BKE_booleanops_mesh.h + BKE_bpath.h BKE_brush.h BKE_bullet.h BKE_bvhutils.h @@ -211,6 +212,7 @@ set(SRC BKE_packedFile.h BKE_paint.h BKE_particle.h + BKE_pbvh.h BKE_pointcache.h BKE_property.h BKE_report.h @@ -236,7 +238,6 @@ set(SRC BKE_world.h BKE_writeavi.h BKE_writeframeserver.h - BKE_bpath.h depsgraph_private.h nla_private.h diff --git a/source/blender/blenkernel/intern/DerivedMesh.c b/source/blender/blenkernel/intern/DerivedMesh.c index 1f4cc9bc5c2..6b8baf42318 100644 --- a/source/blender/blenkernel/intern/DerivedMesh.c +++ b/source/blender/blenkernel/intern/DerivedMesh.c @@ -47,10 +47,10 @@ #include "BLI_math.h" #include "BLI_memarena.h" #include "BLI_array.h" -#include "BLI_pbvh.h" #include "BLI_utildefines.h" #include "BLI_linklist.h" +#include "BKE_pbvh.h" #include "BKE_cdderivedmesh.h" #include "BKE_displist.h" #include "BKE_key.h" diff --git a/source/blender/blenkernel/intern/action.c b/source/blender/blenkernel/intern/action.c index 5da4f05321a..83d1538ecbe 100644 --- a/source/blender/blenkernel/intern/action.c +++ b/source/blender/blenkernel/intern/action.c @@ -43,7 +43,6 @@ #include "DNA_object_types.h" #include "BLI_blenlib.h" -#include "BKE_bpath.h" #include "BLI_math.h" #include "BLI_utildefines.h" #include "BLI_ghash.h" diff --git a/source/blender/blenkernel/intern/armature.c b/source/blender/blenkernel/intern/armature.c index e8dfe027bd7..9155d67dc36 100644 --- a/source/blender/blenkernel/intern/armature.c +++ b/source/blender/blenkernel/intern/armature.c @@ -37,7 +37,6 @@ #include "MEM_guardedalloc.h" -#include "BKE_bpath.h" #include "BLI_math.h" #include "BLI_blenlib.h" #include "BLI_utildefines.h" diff --git a/source/blender/blenkernel/intern/blender.c b/source/blender/blenkernel/intern/blender.c index a46a3879dc8..42634e6e700 100644 --- a/source/blender/blenkernel/intern/blender.c +++ b/source/blender/blenkernel/intern/blender.c @@ -56,7 +56,6 @@ #include "DNA_sound_types.h" #include "BLI_blenlib.h" -#include "BKE_bpath.h" #include "BLI_dynstr.h" #include "BLI_utildefines.h" #include "BLI_callbacks.h" @@ -65,6 +64,7 @@ #include "IMB_moviecache.h" #include "BKE_blender.h" +#include "BKE_bpath.h" #include "BKE_context.h" #include "BKE_depsgraph.h" #include "BKE_displist.h" diff --git a/source/blender/blenkernel/intern/bpath.c b/source/blender/blenkernel/intern/bpath.c index 9f51dddb4fc..24b13b062f3 100644 --- a/source/blender/blenkernel/intern/bpath.c +++ b/source/blender/blenkernel/intern/bpath.c @@ -72,7 +72,6 @@ #include "DNA_smoke_types.h" #include "BLI_blenlib.h" -#include "BKE_bpath.h" #include "BLI_utildefines.h" #include "BKE_font.h" @@ -83,6 +82,8 @@ #include "BKE_sequencer.h" #include "BKE_image.h" /* so we can check the image's type */ +#include "BKE_bpath.h" /* own include */ + static int checkMissingFiles_visit_cb(void *userdata, char *UNUSED(path_dst), const char *path_src) { ReportList *reports = (ReportList *)userdata; diff --git a/source/blender/blenkernel/intern/brush.c b/source/blender/blenkernel/intern/brush.c index 7bcb9b45b23..405b1efb25d 100644 --- a/source/blender/blenkernel/intern/brush.c +++ b/source/blender/blenkernel/intern/brush.c @@ -46,7 +46,6 @@ #include "RNA_access.h" -#include "BKE_bpath.h" #include "BLI_math.h" #include "BLI_blenlib.h" #include "BLI_rand.h" diff --git a/source/blender/blenkernel/intern/cdderivedmesh.c b/source/blender/blenkernel/intern/cdderivedmesh.c index 54bbe4bf495..34adeb4fefb 100644 --- a/source/blender/blenkernel/intern/cdderivedmesh.c +++ b/source/blender/blenkernel/intern/cdderivedmesh.c @@ -40,12 +40,12 @@ #include "BLI_blenlib.h" #include "BLI_edgehash.h" #include "BLI_math.h" -#include "BLI_pbvh.h" #include "BLI_array.h" #include "BLI_smallhash.h" #include "BLI_utildefines.h" #include "BLI_scanfill.h" +#include "BKE_pbvh.h" #include "BKE_cdderivedmesh.h" #include "BKE_global.h" #include "BKE_mesh.h" diff --git a/source/blender/blenkernel/intern/curve.c b/source/blender/blenkernel/intern/curve.c index c9f084a9297..1d199cdf1e2 100644 --- a/source/blender/blenkernel/intern/curve.c +++ b/source/blender/blenkernel/intern/curve.c @@ -36,7 +36,6 @@ #include "MEM_guardedalloc.h" -#include "BKE_bpath.h" #include "BLI_blenlib.h" #include "BLI_math.h" #include "BLI_utildefines.h" diff --git a/source/blender/blenkernel/intern/editderivedmesh.c b/source/blender/blenkernel/intern/editderivedmesh.c index 73320c96315..bb8df834d0f 100644 --- a/source/blender/blenkernel/intern/editderivedmesh.c +++ b/source/blender/blenkernel/intern/editderivedmesh.c @@ -39,8 +39,8 @@ #include "BLI_blenlib.h" #include "BLI_edgehash.h" #include "BLI_math.h" -#include "BLI_pbvh.h" +#include "BKE_pbvh.h" #include "BKE_cdderivedmesh.h" #include "BKE_global.h" #include "BKE_mesh.h" diff --git a/source/blender/blenkernel/intern/image.c b/source/blender/blenkernel/intern/image.c index f1f9667c3d0..7f0475cf155 100644 --- a/source/blender/blenkernel/intern/image.c +++ b/source/blender/blenkernel/intern/image.c @@ -68,7 +68,6 @@ #include "BLI_blenlib.h" #include "BLI_threads.h" #include "BLI_utildefines.h" -#include "BKE_bpath.h" #include "BKE_bmfont.h" #include "BKE_colortools.h" diff --git a/source/blender/blenkernel/intern/lattice.c b/source/blender/blenkernel/intern/lattice.c index 7f3e43c40ff..d98188d8a6f 100644 --- a/source/blender/blenkernel/intern/lattice.c +++ b/source/blender/blenkernel/intern/lattice.c @@ -37,7 +37,6 @@ #include "MEM_guardedalloc.h" #include "BLI_blenlib.h" -#include "BKE_bpath.h" #include "BLI_math.h" #include "BLI_utildefines.h" diff --git a/source/blender/blenkernel/intern/material.c b/source/blender/blenkernel/intern/material.c index e4a938e7152..a3dcda7069a 100644 --- a/source/blender/blenkernel/intern/material.c +++ b/source/blender/blenkernel/intern/material.c @@ -52,7 +52,6 @@ #include "BLI_math.h" #include "BLI_listbase.h" #include "BLI_utildefines.h" -#include "BKE_bpath.h" #include "BLI_string.h" #include "BKE_animsys.h" diff --git a/source/blender/blenkernel/intern/mball.c b/source/blender/blenkernel/intern/mball.c index fdd0c504dac..5c882fd97d6 100644 --- a/source/blender/blenkernel/intern/mball.c +++ b/source/blender/blenkernel/intern/mball.c @@ -50,8 +50,6 @@ #include "BLI_blenlib.h" #include "BLI_math.h" #include "BLI_utildefines.h" -#include "BKE_bpath.h" - #include "BKE_global.h" #include "BKE_main.h" diff --git a/source/blender/blenkernel/intern/mesh.c b/source/blender/blenkernel/intern/mesh.c index e12c3bc2260..55cf2743bfa 100644 --- a/source/blender/blenkernel/intern/mesh.c +++ b/source/blender/blenkernel/intern/mesh.c @@ -46,7 +46,6 @@ #include "BLI_utildefines.h" #include "BLI_blenlib.h" -#include "BKE_bpath.h" #include "BLI_math.h" #include "BLI_edgehash.h" #include "BLI_scanfill.h" diff --git a/source/blender/blenkernel/intern/multires.c b/source/blender/blenkernel/intern/multires.c index c737dccc5d2..06d7cf55d49 100644 --- a/source/blender/blenkernel/intern/multires.c +++ b/source/blender/blenkernel/intern/multires.c @@ -43,9 +43,9 @@ #include "BLI_bitmap.h" #include "BLI_blenlib.h" #include "BLI_math.h" -#include "BLI_pbvh.h" #include "BLI_utildefines.h" +#include "BKE_pbvh.h" #include "BKE_ccg.h" #include "BKE_cdderivedmesh.h" #include "BKE_mesh.h" diff --git a/source/blender/blenkernel/intern/object.c b/source/blender/blenkernel/intern/object.c index 85ad7186132..c705e226f45 100644 --- a/source/blender/blenkernel/intern/object.c +++ b/source/blender/blenkernel/intern/object.c @@ -59,12 +59,11 @@ #include "DNA_object_types.h" #include "BLI_blenlib.h" -#include "BKE_bpath.h" #include "BLI_math.h" -#include "BLI_pbvh.h" #include "BLI_utildefines.h" #include "BLI_linklist.h" +#include "BKE_pbvh.h" #include "BKE_main.h" #include "BKE_global.h" #include "BKE_idprop.h" diff --git a/source/blender/blenkernel/intern/particle.c b/source/blender/blenkernel/intern/particle.c index 000545d936f..b2851962b49 100644 --- a/source/blender/blenkernel/intern/particle.c +++ b/source/blender/blenkernel/intern/particle.c @@ -55,7 +55,6 @@ #include "BLI_rand.h" #include "BLI_threads.h" #include "BLI_linklist.h" -#include "BKE_bpath.h" #include "BKE_anim.h" #include "BKE_animsys.h" diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c new file mode 100644 index 00000000000..3a4e8afca76 --- /dev/null +++ b/source/blender/blenkernel/intern/pbvh.c @@ -0,0 +1,1909 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * 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. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenlib/intern/pbvh.c + * \ingroup bli + */ + +#include "DNA_meshdata_types.h" + +#include "MEM_guardedalloc.h" + +#include "BLI_bitmap.h" +#include "BLI_math.h" +#include "BLI_utildefines.h" +#include "BLI_ghash.h" + +#include "BKE_pbvh.h" +#include "BKE_ccg.h" +#include "BKE_DerivedMesh.h" +#include "BKE_mesh.h" /* for BKE_mesh_calc_normals */ +#include "BKE_global.h" /* for BKE_mesh_calc_normals */ +#include "BKE_paint.h" +#include "BKE_subsurf.h" + +#include "GPU_buffers.h" + +#define LEAF_LIMIT 10000 + +//#define PERFCNTRS + +/* Axis-aligned bounding box */ +typedef struct { + float bmin[3], bmax[3]; +} BB; + +/* Axis-aligned bounding box with centroid */ +typedef struct { + float bmin[3], bmax[3], bcentroid[3]; +} BBC; + +struct PBVHNode { + /* Opaque handle for drawing code */ + GPU_Buffers *draw_buffers; + + /* Voxel bounds */ + BB vb; + BB orig_vb; + + /* For internal nodes, the offset of the children in the PBVH + * 'nodes' array. */ + int children_offset; + + /* Pointer into the PBVH prim_indices array and the number of + * primitives used by this leaf node. + * + * Used for leaf nodes in both mesh- and multires-based PBVHs. + */ + int *prim_indices; + unsigned int totprim; + + /* Array of indices into the mesh's MVert array. Contains the + * indices of all vertices used by faces that are within this + * node's bounding box. + * + * Note that a vertex might be used by a multiple faces, and + * these faces might be in different leaf nodes. Such a vertex + * will appear in the vert_indices array of each of those leaf + * nodes. + * + * In order to support cases where you want access to multiple + * nodes' vertices without duplication, the vert_indices array + * is ordered such that the first part of the array, up to + * index 'uniq_verts', contains "unique" vertex indices. These + * vertices might not be truly unique to this node, but if + * they appear in another node's vert_indices array, they will + * be above that node's 'uniq_verts' value. + * + * Used for leaf nodes in a mesh-based PBVH (not multires.) + */ + int *vert_indices; + unsigned int uniq_verts, face_verts; + + /* An array mapping face corners into the vert_indices + * array. The array is sized to match 'totprim', and each of + * the face's corners gets an index into the vert_indices + * array, in the same order as the corners in the original + * MFace. The fourth value should not be used if the original + * face is a triangle. + * + * Used for leaf nodes in a mesh-based PBVH (not multires.) + */ + int (*face_vert_indices)[4]; + + /* Indicates whether this node is a leaf or not; also used for + * marking various updates that need to be applied. */ + PBVHNodeFlags flag : 8; + + /* Used for raycasting: how close bb is to the ray point. */ + float tmin; + + int proxy_count; + PBVHProxyNode *proxies; +}; + +struct PBVH { + PBVHType type; + + PBVHNode *nodes; + int node_mem_count, totnode; + + int *prim_indices; + int totprim; + int totvert; + + int leaf_limit; + + /* Mesh data */ + MVert *verts; + MFace *faces; + CustomData *vdata; + + /* Grid Data */ + CCGKey gridkey; + CCGElem **grids; + DMGridAdjacency *gridadj; + void **gridfaces; + const DMFlagMat *grid_flag_mats; + int totgrid; + BLI_bitmap *grid_hidden; + + /* Only used during BVH build and update, + * don't need to remain valid after */ + BLI_bitmap vert_bitmap; + +#ifdef PERFCNTRS + int perf_modified; +#endif + + /* flag are verts/faces deformed */ + int deformed; + + int show_diffuse_color; +}; + +#define STACK_FIXED_DEPTH 100 + +typedef struct PBVHStack { + PBVHNode *node; + int revisiting; +} PBVHStack; + +typedef struct PBVHIter { + PBVH *bvh; + BLI_pbvh_SearchCallback scb; + void *search_data; + + PBVHStack *stack; + int stacksize; + + PBVHStack stackfixed[STACK_FIXED_DEPTH]; + int stackspace; +} PBVHIter; + +static void BB_reset(BB *bb) +{ + bb->bmin[0] = bb->bmin[1] = bb->bmin[2] = FLT_MAX; + bb->bmax[0] = bb->bmax[1] = bb->bmax[2] = -FLT_MAX; +} + +/* Expand the bounding box to include a new coordinate */ +static void BB_expand(BB *bb, float co[3]) +{ + int i; + for (i = 0; i < 3; ++i) { + bb->bmin[i] = min_ff(bb->bmin[i], co[i]); + bb->bmax[i] = max_ff(bb->bmax[i], co[i]); + } +} + +/* Expand the bounding box to include another bounding box */ +static void BB_expand_with_bb(BB *bb, BB *bb2) +{ + int i; + for (i = 0; i < 3; ++i) { + bb->bmin[i] = min_ff(bb->bmin[i], bb2->bmin[i]); + bb->bmax[i] = max_ff(bb->bmax[i], bb2->bmax[i]); + } +} + +/* Return 0, 1, or 2 to indicate the widest axis of the bounding box */ +static int BB_widest_axis(BB *bb) +{ + float dim[3]; + int i; + + for (i = 0; i < 3; ++i) + dim[i] = bb->bmax[i] - bb->bmin[i]; + + if (dim[0] > dim[1]) { + if (dim[0] > dim[2]) + return 0; + else + return 2; + } + else { + if (dim[1] > dim[2]) + return 1; + else + return 2; + } +} + +static void BBC_update_centroid(BBC *bbc) +{ + int i; + for (i = 0; i < 3; ++i) + bbc->bcentroid[i] = (bbc->bmin[i] + bbc->bmax[i]) * 0.5f; +} + +/* Not recursive */ +static void update_node_vb(PBVH *bvh, PBVHNode *node) +{ + BB vb; + + BB_reset(&vb); + + if (node->flag & PBVH_Leaf) { + PBVHVertexIter vd; + + BLI_pbvh_vertex_iter_begin(bvh, node, vd, PBVH_ITER_ALL) + { + BB_expand(&vb, vd.co); + } + BLI_pbvh_vertex_iter_end; + } + else { + BB_expand_with_bb(&vb, + &bvh->nodes[node->children_offset].vb); + BB_expand_with_bb(&vb, + &bvh->nodes[node->children_offset + 1].vb); + } + + node->vb = vb; +} + +//void BLI_pbvh_node_BB_reset(PBVHNode *node) +//{ +// BB_reset(&node->vb); +//} +// +//void BLI_pbvh_node_BB_expand(PBVHNode *node, float co[3]) +//{ +// BB_expand(&node->vb, co); +//} + +static int face_materials_match(const MFace *f1, const MFace *f2) +{ + return ((f1->flag & ME_SMOOTH) == (f2->flag & ME_SMOOTH) && + (f1->mat_nr == f2->mat_nr)); +} + +static int grid_materials_match(const DMFlagMat *f1, const DMFlagMat *f2) +{ + return ((f1->flag & ME_SMOOTH) == (f2->flag & ME_SMOOTH) && + (f1->mat_nr == f2->mat_nr)); +} + +/* Adapted from BLI_kdopbvh.c */ +/* Returns the index of the first element on the right of the partition */ +static int partition_indices(int *prim_indices, int lo, int hi, int axis, + float mid, BBC *prim_bbc) +{ + int i = lo, j = hi; + for (;; ) { + for (; prim_bbc[prim_indices[i]].bcentroid[axis] < mid; i++) ; + for (; mid < prim_bbc[prim_indices[j]].bcentroid[axis]; j--) ; + + if (!(i < j)) + return i; + + SWAP(int, prim_indices[i], prim_indices[j]); + i++; + } +} + +/* Returns the index of the first element on the right of the partition */ +static int partition_indices_material(PBVH *bvh, int lo, int hi) +{ + const MFace *faces = bvh->faces; + const DMFlagMat *flagmats = bvh->grid_flag_mats; + const int *indices = bvh->prim_indices; + const void *first; + int i = lo, j = hi; + + if (bvh->faces) + first = &faces[bvh->prim_indices[lo]]; + else + first = &flagmats[bvh->prim_indices[lo]]; + + for (;; ) { + if (bvh->faces) { + for (; face_materials_match(first, &faces[indices[i]]); i++) ; + for (; !face_materials_match(first, &faces[indices[j]]); j--) ; + } + else { + for (; grid_materials_match(first, &flagmats[indices[i]]); i++) ; + for (; !grid_materials_match(first, &flagmats[indices[j]]); j--) ; + } + + if (!(i < j)) + return i; + + SWAP(int, bvh->prim_indices[i], bvh->prim_indices[j]); + i++; + } +} + +static void grow_nodes(PBVH *bvh, int totnode) +{ + if (totnode > bvh->node_mem_count) { + PBVHNode *prev = bvh->nodes; + bvh->node_mem_count *= 1.33; + if (bvh->node_mem_count < totnode) + bvh->node_mem_count = totnode; + bvh->nodes = MEM_callocN(sizeof(PBVHNode) * bvh->node_mem_count, + "bvh nodes"); + memcpy(bvh->nodes, prev, bvh->totnode * sizeof(PBVHNode)); + MEM_freeN(prev); + } + + bvh->totnode = totnode; +} + +/* Add a vertex to the map, with a positive value for unique vertices and + * a negative value for additional vertices */ +static int map_insert_vert(PBVH *bvh, GHash *map, + unsigned int *face_verts, + unsigned int *uniq_verts, int vertex) +{ + void *value, *key = SET_INT_IN_POINTER(vertex); + + if (!BLI_ghash_haskey(map, key)) { + if (BLI_BITMAP_GET(bvh->vert_bitmap, vertex)) { + value = SET_INT_IN_POINTER(~(*face_verts)); + ++(*face_verts); + } + else { + BLI_BITMAP_SET(bvh->vert_bitmap, vertex); + value = SET_INT_IN_POINTER(*uniq_verts); + ++(*uniq_verts); + } + + BLI_ghash_insert(map, key, value); + return GET_INT_FROM_POINTER(value); + } + else + return GET_INT_FROM_POINTER(BLI_ghash_lookup(map, key)); +} + +/* Find vertices used by the faces in this node and update the draw buffers */ +static void build_mesh_leaf_node(PBVH *bvh, PBVHNode *node) +{ + GHashIterator *iter; + GHash *map; + int i, j, totface; + + map = BLI_ghash_int_new("build_mesh_leaf_node gh"); + + node->uniq_verts = node->face_verts = 0; + totface = node->totprim; + + node->face_vert_indices = MEM_callocN(sizeof(int) * 4 * totface, + "bvh node face vert indices"); + + for (i = 0; i < totface; ++i) { + MFace *f = bvh->faces + node->prim_indices[i]; + int sides = f->v4 ? 4 : 3; + + for (j = 0; j < sides; ++j) { + node->face_vert_indices[i][j] = + map_insert_vert(bvh, map, &node->face_verts, + &node->uniq_verts, (&f->v1)[j]); + } + } + + node->vert_indices = MEM_callocN(sizeof(int) * + (node->uniq_verts + node->face_verts), + "bvh node vert indices"); + + /* Build the vertex list, unique verts first */ + for (iter = BLI_ghashIterator_new(map), i = 0; + BLI_ghashIterator_isDone(iter) == FALSE; + BLI_ghashIterator_step(iter), ++i) + { + void *value = BLI_ghashIterator_getValue(iter); + int ndx = GET_INT_FROM_POINTER(value); + + if (ndx < 0) + ndx = -ndx + node->uniq_verts - 1; + + node->vert_indices[ndx] = + GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(iter)); + } + + BLI_ghashIterator_free(iter); + + for (i = 0; i < totface; ++i) { + MFace *f = bvh->faces + node->prim_indices[i]; + int sides = f->v4 ? 4 : 3; + + for (j = 0; j < sides; ++j) { + if (node->face_vert_indices[i][j] < 0) + node->face_vert_indices[i][j] = + -node->face_vert_indices[i][j] + + node->uniq_verts - 1; + } + } + + if (!G.background) { + node->draw_buffers = + GPU_build_mesh_buffers(node->face_vert_indices, + bvh->faces, bvh->verts, + node->prim_indices, + node->totprim); + } + + node->flag |= PBVH_UpdateDrawBuffers; + + BLI_ghash_free(map, NULL, NULL); +} + +static void build_grids_leaf_node(PBVH *bvh, PBVHNode *node) +{ + if (!G.background) { + node->draw_buffers = + GPU_build_grid_buffers(node->prim_indices, + node->totprim, bvh->grid_hidden, bvh->gridkey.grid_size); + } + node->flag |= PBVH_UpdateDrawBuffers; +} + +static void update_vb(PBVH *bvh, PBVHNode *node, BBC *prim_bbc, + int offset, int count) +{ + int i; + + BB_reset(&node->vb); + for (i = offset + count - 1; i >= offset; --i) { + BB_expand_with_bb(&node->vb, (BB *)(&prim_bbc[bvh->prim_indices[i]])); + } + node->orig_vb = node->vb; +} + +static void build_leaf(PBVH *bvh, int node_index, BBC *prim_bbc, + int offset, int count) +{ + bvh->nodes[node_index].flag |= PBVH_Leaf; + + bvh->nodes[node_index].prim_indices = bvh->prim_indices + offset; + bvh->nodes[node_index].totprim = count; + + /* Still need vb for searches */ + update_vb(bvh, &bvh->nodes[node_index], prim_bbc, offset, count); + + if (bvh->faces) + build_mesh_leaf_node(bvh, bvh->nodes + node_index); + else + build_grids_leaf_node(bvh, bvh->nodes + node_index); +} + +/* Return zero if all primitives in the node can be drawn with the + * same material (including flat/smooth shading), non-zerootherwise */ +static int leaf_needs_material_split(PBVH *bvh, int offset, int count) +{ + int i, prim; + + if (count <= 1) + return 0; + + if (bvh->faces) { + const MFace *first = &bvh->faces[bvh->prim_indices[offset]]; + + for (i = offset + count - 1; i > offset; --i) { + prim = bvh->prim_indices[i]; + if (!face_materials_match(first, &bvh->faces[prim])) + return 1; + } + } + else { + const DMFlagMat *first = &bvh->grid_flag_mats[bvh->prim_indices[offset]]; + + for (i = offset + count - 1; i > offset; --i) { + prim = bvh->prim_indices[i]; + if (!grid_materials_match(first, &bvh->grid_flag_mats[prim])) + return 1; + } + } + + return 0; +} + + +/* Recursively build a node in the tree + * + * vb is the voxel box around all of the primitives contained in + * this node. + * + * cb is the bounding box around all the centroids of the primitives + * contained in this node + * + * offset and start indicate a range in the array of primitive indices + */ + +static void build_sub(PBVH *bvh, int node_index, BB *cb, BBC *prim_bbc, + int offset, int count) +{ + int i, axis, end, below_leaf_limit; + BB cb_backing; + + /* Decide whether this is a leaf or not */ + below_leaf_limit = count <= bvh->leaf_limit; + if (below_leaf_limit) { + if (!leaf_needs_material_split(bvh, offset, count)) { + build_leaf(bvh, node_index, prim_bbc, offset, count); + return; + } + } + + /* Add two child nodes */ + bvh->nodes[node_index].children_offset = bvh->totnode; + grow_nodes(bvh, bvh->totnode + 2); + + /* Update parent node bounding box */ + update_vb(bvh, &bvh->nodes[node_index], prim_bbc, offset, count); + + if (!below_leaf_limit) { + /* Find axis with widest range of primitive centroids */ + if (!cb) { + cb = &cb_backing; + BB_reset(cb); + for (i = offset + count - 1; i >= offset; --i) + BB_expand(cb, prim_bbc[bvh->prim_indices[i]].bcentroid); + } + axis = BB_widest_axis(cb); + + /* Partition primitives along that axis */ + end = partition_indices(bvh->prim_indices, + offset, offset + count - 1, + axis, + (cb->bmax[axis] + cb->bmin[axis]) * 0.5f, + prim_bbc); + } + else { + /* Partition primitives by material */ + end = partition_indices_material(bvh, offset, offset + count - 1); + } + + /* Build children */ + build_sub(bvh, bvh->nodes[node_index].children_offset, NULL, + prim_bbc, offset, end - offset); + build_sub(bvh, bvh->nodes[node_index].children_offset + 1, NULL, + prim_bbc, end, offset + count - end); +} + +static void pbvh_build(PBVH *bvh, BB *cb, BBC *prim_bbc, int totprim) +{ + int i; + + if (totprim != bvh->totprim) { + bvh->totprim = totprim; + if (bvh->nodes) MEM_freeN(bvh->nodes); + if (bvh->prim_indices) MEM_freeN(bvh->prim_indices); + bvh->prim_indices = MEM_callocN(sizeof(int) * totprim, + "bvh prim indices"); + for (i = 0; i < totprim; ++i) + bvh->prim_indices[i] = i; + bvh->totnode = 0; + if (bvh->node_mem_count < 100) { + bvh->node_mem_count = 100; + bvh->nodes = MEM_callocN(sizeof(PBVHNode) * + bvh->node_mem_count, + "bvh initial nodes"); + } + } + + bvh->totnode = 1; + build_sub(bvh, 0, cb, prim_bbc, 0, totprim); +} + +/* Do a full rebuild with on Mesh data structure */ +void BLI_pbvh_build_mesh(PBVH *bvh, MFace *faces, MVert *verts, int totface, int totvert, struct CustomData *vdata) +{ + BBC *prim_bbc = NULL; + BB cb; + int i, j; + + bvh->type = PBVH_FACES; + bvh->faces = faces; + bvh->verts = verts; + bvh->vert_bitmap = BLI_BITMAP_NEW(totvert, "bvh->vert_bitmap"); + bvh->totvert = totvert; + bvh->leaf_limit = LEAF_LIMIT; + bvh->vdata = vdata; + + BB_reset(&cb); + + /* For each face, store the AABB and the AABB centroid */ + prim_bbc = MEM_mallocN(sizeof(BBC) * totface, "prim_bbc"); + + for (i = 0; i < totface; ++i) { + MFace *f = faces + i; + const int sides = f->v4 ? 4 : 3; + BBC *bbc = prim_bbc + i; + + BB_reset((BB *)bbc); + + for (j = 0; j < sides; ++j) + BB_expand((BB *)bbc, verts[(&f->v1)[j]].co); + + BBC_update_centroid(bbc); + + BB_expand(&cb, bbc->bcentroid); + } + + if (totface) + pbvh_build(bvh, &cb, prim_bbc, totface); + + MEM_freeN(prim_bbc); + MEM_freeN(bvh->vert_bitmap); +} + +/* Do a full rebuild with on Grids data structure */ +void BLI_pbvh_build_grids(PBVH *bvh, CCGElem **grids, DMGridAdjacency *gridadj, + int totgrid, CCGKey *key, void **gridfaces, DMFlagMat *flagmats, BLI_bitmap *grid_hidden) +{ + BBC *prim_bbc = NULL; + BB cb; + int gridsize = key->grid_size; + int i, j; + + bvh->type = PBVH_GRIDS; + bvh->grids = grids; + bvh->gridadj = gridadj; + bvh->gridfaces = gridfaces; + bvh->grid_flag_mats = flagmats; + bvh->totgrid = totgrid; + bvh->gridkey = *key; + bvh->grid_hidden = grid_hidden; + bvh->leaf_limit = max_ii(LEAF_LIMIT / ((gridsize - 1) * (gridsize - 1)), 1); + + BB_reset(&cb); + + /* For each grid, store the AABB and the AABB centroid */ + prim_bbc = MEM_mallocN(sizeof(BBC) * totgrid, "prim_bbc"); + + for (i = 0; i < totgrid; ++i) { + CCGElem *grid = grids[i]; + BBC *bbc = prim_bbc + i; + + BB_reset((BB *)bbc); + + for (j = 0; j < gridsize * gridsize; ++j) + BB_expand((BB *)bbc, CCG_elem_offset_co(key, grid, j)); + + BBC_update_centroid(bbc); + + BB_expand(&cb, bbc->bcentroid); + } + + if (totgrid) + pbvh_build(bvh, &cb, prim_bbc, totgrid); + + MEM_freeN(prim_bbc); +} + +PBVH *BLI_pbvh_new(void) +{ + PBVH *bvh = MEM_callocN(sizeof(PBVH), "pbvh"); + + return bvh; +} + +void BLI_pbvh_free(PBVH *bvh) +{ + PBVHNode *node; + int i; + + for (i = 0; i < bvh->totnode; ++i) { + node = &bvh->nodes[i]; + + if (node->flag & PBVH_Leaf) { + if (node->draw_buffers) + GPU_free_buffers(node->draw_buffers); + if (node->vert_indices) + MEM_freeN(node->vert_indices); + if (node->face_vert_indices) + MEM_freeN(node->face_vert_indices); + } + } + + if (bvh->deformed) { + if (bvh->verts) { + /* if pbvh was deformed, new memory was allocated for verts/faces -- free it */ + + MEM_freeN(bvh->verts); + if (bvh->faces) + MEM_freeN(bvh->faces); + } + } + + if (bvh->nodes) + MEM_freeN(bvh->nodes); + + if (bvh->prim_indices) + MEM_freeN(bvh->prim_indices); + + MEM_freeN(bvh); +} + +static void pbvh_iter_begin(PBVHIter *iter, PBVH *bvh, BLI_pbvh_SearchCallback scb, void *search_data) +{ + iter->bvh = bvh; + iter->scb = scb; + iter->search_data = search_data; + + iter->stack = iter->stackfixed; + iter->stackspace = STACK_FIXED_DEPTH; + + iter->stack[0].node = bvh->nodes; + iter->stack[0].revisiting = 0; + iter->stacksize = 1; +} + +static void pbvh_iter_end(PBVHIter *iter) +{ + if (iter->stackspace > STACK_FIXED_DEPTH) + MEM_freeN(iter->stack); +} + +static void pbvh_stack_push(PBVHIter *iter, PBVHNode *node, int revisiting) +{ + if (iter->stacksize == iter->stackspace) { + PBVHStack *newstack; + + iter->stackspace *= 2; + newstack = MEM_callocN(sizeof(PBVHStack) * iter->stackspace, "PBVHStack"); + memcpy(newstack, iter->stack, sizeof(PBVHStack) * iter->stacksize); + + if (iter->stackspace > STACK_FIXED_DEPTH) + MEM_freeN(iter->stack); + iter->stack = newstack; + } + + iter->stack[iter->stacksize].node = node; + iter->stack[iter->stacksize].revisiting = revisiting; + iter->stacksize++; +} + +static PBVHNode *pbvh_iter_next(PBVHIter *iter) +{ + PBVHNode *node; + int revisiting; + + /* purpose here is to traverse tree, visiting child nodes before their + * parents, this order is necessary for e.g. computing bounding boxes */ + + while (iter->stacksize) { + /* pop node */ + iter->stacksize--; + node = iter->stack[iter->stacksize].node; + + /* on a mesh with no faces this can happen + * can remove this check if we know meshes have at least 1 face */ + if (node == NULL) + return NULL; + + revisiting = iter->stack[iter->stacksize].revisiting; + + /* revisiting node already checked */ + if (revisiting) + return node; + + if (iter->scb && !iter->scb(node, iter->search_data)) + continue; /* don't traverse, outside of search zone */ + + if (node->flag & PBVH_Leaf) { + /* immediately hit leaf node */ + return node; + } + else { + /* come back later when children are done */ + pbvh_stack_push(iter, node, 1); + + /* push two child nodes on the stack */ + pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset + 1, 0); + pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset, 0); + } + } + + return NULL; +} + +static PBVHNode *pbvh_iter_next_occluded(PBVHIter *iter) +{ + PBVHNode *node; + + while (iter->stacksize) { + /* pop node */ + iter->stacksize--; + node = iter->stack[iter->stacksize].node; + + /* on a mesh with no faces this can happen + * can remove this check if we know meshes have at least 1 face */ + if (node == NULL) return NULL; + + if (iter->scb && !iter->scb(node, iter->search_data)) continue; /* don't traverse, outside of search zone */ + + if (node->flag & PBVH_Leaf) { + /* immediately hit leaf node */ + return node; + } + else { + pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset + 1, 0); + pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset, 0); + } + } + + return NULL; +} + +void BLI_pbvh_search_gather(PBVH *bvh, + BLI_pbvh_SearchCallback scb, void *search_data, + PBVHNode ***r_array, int *r_tot) +{ + PBVHIter iter; + PBVHNode **array = NULL, **newarray, *node; + int tot = 0, space = 0; + + pbvh_iter_begin(&iter, bvh, scb, search_data); + + while ((node = pbvh_iter_next(&iter))) { + if (node->flag & PBVH_Leaf) { + if (tot == space) { + /* resize array if needed */ + space = (tot == 0) ? 32 : space * 2; + newarray = MEM_callocN(sizeof(PBVHNode) * space, "PBVHNodeSearch"); + + if (array) { + memcpy(newarray, array, sizeof(PBVHNode) * tot); + MEM_freeN(array); + } + + array = newarray; + } + + array[tot] = node; + tot++; + } + } + + pbvh_iter_end(&iter); + + if (tot == 0 && array) { + MEM_freeN(array); + array = NULL; + } + + *r_array = array; + *r_tot = tot; +} + +void BLI_pbvh_search_callback(PBVH *bvh, + BLI_pbvh_SearchCallback scb, void *search_data, + BLI_pbvh_HitCallback hcb, void *hit_data) +{ + PBVHIter iter; + PBVHNode *node; + + pbvh_iter_begin(&iter, bvh, scb, search_data); + + while ((node = pbvh_iter_next(&iter))) + if (node->flag & PBVH_Leaf) + hcb(node, hit_data); + + pbvh_iter_end(&iter); +} + +typedef struct node_tree { + PBVHNode *data; + + struct node_tree *left; + struct node_tree *right; +} node_tree; + +static void node_tree_insert(node_tree *tree, node_tree *new_node) +{ + if (new_node->data->tmin < tree->data->tmin) { + if (tree->left) { + node_tree_insert(tree->left, new_node); + } + else { + tree->left = new_node; + } + } + else { + if (tree->right) { + node_tree_insert(tree->right, new_node); + } + else { + tree->right = new_node; + } + } +} + +static void traverse_tree(node_tree *tree, BLI_pbvh_HitOccludedCallback hcb, void *hit_data, float *tmin) +{ + if (tree->left) traverse_tree(tree->left, hcb, hit_data, tmin); + + hcb(tree->data, hit_data, tmin); + + if (tree->right) traverse_tree(tree->right, hcb, hit_data, tmin); +} + +static void free_tree(node_tree *tree) +{ + if (tree->left) { + free_tree(tree->left); + tree->left = 0; + } + + if (tree->right) { + free_tree(tree->right); + tree->right = 0; + } + + free(tree); +} + +float BLI_pbvh_node_get_tmin(PBVHNode *node) +{ + return node->tmin; +} + +static void BLI_pbvh_search_callback_occluded(PBVH *bvh, + BLI_pbvh_SearchCallback scb, void *search_data, + BLI_pbvh_HitOccludedCallback hcb, void *hit_data) +{ + PBVHIter iter; + PBVHNode *node; + node_tree *tree = 0; + + pbvh_iter_begin(&iter, bvh, scb, search_data); + + while ((node = pbvh_iter_next_occluded(&iter))) { + if (node->flag & PBVH_Leaf) { + node_tree *new_node = malloc(sizeof(node_tree)); + + new_node->data = node; + + new_node->left = NULL; + new_node->right = NULL; + + if (tree) { + node_tree_insert(tree, new_node); + } + else { + tree = new_node; + } + } + } + + pbvh_iter_end(&iter); + + if (tree) { + float tmin = FLT_MAX; + traverse_tree(tree, hcb, hit_data, &tmin); + free_tree(tree); + } +} + +static int update_search_cb(PBVHNode *node, void *data_v) +{ + int flag = GET_INT_FROM_POINTER(data_v); + + if (node->flag & PBVH_Leaf) + return (node->flag & flag); + + return 1; +} + +static void pbvh_update_normals(PBVH *bvh, PBVHNode **nodes, + int totnode, float (*face_nors)[3]) +{ + float (*vnor)[3]; + int n; + + if (bvh->type != PBVH_FACES) + return; + + /* could be per node to save some memory, but also means + * we have to store for each vertex which node it is in */ + vnor = MEM_callocN(sizeof(float) * 3 * bvh->totvert, "bvh temp vnors"); + + /* subtle assumptions: + * - We know that for all edited vertices, the nodes with faces + * adjacent to these vertices have been marked with PBVH_UpdateNormals. + * This is true because if the vertex is inside the brush radius, the + * bounding box of it's adjacent faces will be as well. + * - However this is only true for the vertices that have actually been + * edited, not for all vertices in the nodes marked for update, so we + * can only update vertices marked with ME_VERT_PBVH_UPDATE. + */ + + #pragma omp parallel for private(n) schedule(static) + for (n = 0; n < totnode; n++) { + PBVHNode *node = nodes[n]; + + if ((node->flag & PBVH_UpdateNormals)) { + int i, j, totface, *faces; + + faces = node->prim_indices; + totface = node->totprim; + + for (i = 0; i < totface; ++i) { + MFace *f = bvh->faces + faces[i]; + float fn[3]; + unsigned int *fv = &f->v1; + int sides = (f->v4) ? 4 : 3; + + if (f->v4) + normal_quad_v3(fn, bvh->verts[f->v1].co, bvh->verts[f->v2].co, + bvh->verts[f->v3].co, bvh->verts[f->v4].co); + else + normal_tri_v3(fn, bvh->verts[f->v1].co, bvh->verts[f->v2].co, + bvh->verts[f->v3].co); + + for (j = 0; j < sides; ++j) { + int v = fv[j]; + + if (bvh->verts[v].flag & ME_VERT_PBVH_UPDATE) { + /* this seems like it could be very slow but profile + * does not show this, so just leave it for now? */ + #pragma omp atomic + vnor[v][0] += fn[0]; + #pragma omp atomic + vnor[v][1] += fn[1]; + #pragma omp atomic + vnor[v][2] += fn[2]; + } + } + + if (face_nors) + copy_v3_v3(face_nors[faces[i]], fn); + } + } + } + + #pragma omp parallel for private(n) schedule(static) + for (n = 0; n < totnode; n++) { + PBVHNode *node = nodes[n]; + + if (node->flag & PBVH_UpdateNormals) { + int i, *verts, totvert; + + verts = node->vert_indices; + totvert = node->uniq_verts; + + for (i = 0; i < totvert; ++i) { + const int v = verts[i]; + MVert *mvert = &bvh->verts[v]; + + if (mvert->flag & ME_VERT_PBVH_UPDATE) { + float no[3]; + + copy_v3_v3(no, vnor[v]); + normalize_v3(no); + normal_float_to_short_v3(mvert->no, no); + + mvert->flag &= ~ME_VERT_PBVH_UPDATE; + } + } + + node->flag &= ~PBVH_UpdateNormals; + } + } + + MEM_freeN(vnor); +} + +static void pbvh_update_BB_redraw(PBVH *bvh, PBVHNode **nodes, + int totnode, int flag) +{ + int n; + + /* update BB, redraw flag */ + #pragma omp parallel for private(n) schedule(static) + for (n = 0; n < totnode; n++) { + PBVHNode *node = nodes[n]; + + if ((flag & PBVH_UpdateBB) && (node->flag & PBVH_UpdateBB)) + /* don't clear flag yet, leave it for flushing later */ + update_node_vb(bvh, node); + + if ((flag & PBVH_UpdateOriginalBB) && (node->flag & PBVH_UpdateOriginalBB)) + node->orig_vb = node->vb; + + if ((flag & PBVH_UpdateRedraw) && (node->flag & PBVH_UpdateRedraw)) + node->flag &= ~PBVH_UpdateRedraw; + } +} + +static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode) +{ + PBVHNode *node; + int n; + + /* can't be done in parallel with OpenGL */ + for (n = 0; n < totnode; n++) { + node = nodes[n]; + + if (node->flag & PBVH_RebuildDrawBuffers) { + GPU_free_buffers(node->draw_buffers); + switch (bvh->type) { + case PBVH_GRIDS: + node->draw_buffers = + GPU_build_grid_buffers(node->prim_indices, + node->totprim, + bvh->grid_hidden, + bvh->gridkey.grid_size); + break; + case PBVH_FACES: + node->draw_buffers = + GPU_build_mesh_buffers(node->face_vert_indices, + bvh->faces, bvh->verts, + node->prim_indices, + node->totprim); + break; + } + + node->flag &= ~PBVH_RebuildDrawBuffers; + } + + if (node->flag & PBVH_UpdateDrawBuffers) { + switch (bvh->type) { + case PBVH_GRIDS: + GPU_update_grid_buffers(node->draw_buffers, + bvh->grids, + bvh->grid_flag_mats, + node->prim_indices, + node->totprim, + &bvh->gridkey, + bvh->show_diffuse_color); + break; + case PBVH_FACES: + GPU_update_mesh_buffers(node->draw_buffers, + bvh->verts, + node->vert_indices, + node->uniq_verts + + node->face_verts, + CustomData_get_layer(bvh->vdata, + CD_PAINT_MASK), + node->face_vert_indices, + bvh->show_diffuse_color); + break; + } + + node->flag &= ~PBVH_UpdateDrawBuffers; + } + } +} + +static int pbvh_flush_bb(PBVH *bvh, PBVHNode *node, int flag) +{ + int update = 0; + + /* difficult to multithread well, we just do single threaded recursive */ + if (node->flag & PBVH_Leaf) { + if (flag & PBVH_UpdateBB) { + update |= (node->flag & PBVH_UpdateBB); + node->flag &= ~PBVH_UpdateBB; + } + + if (flag & PBVH_UpdateOriginalBB) { + update |= (node->flag & PBVH_UpdateOriginalBB); + node->flag &= ~PBVH_UpdateOriginalBB; + } + + return update; + } + else { + update |= pbvh_flush_bb(bvh, bvh->nodes + node->children_offset, flag); + update |= pbvh_flush_bb(bvh, bvh->nodes + node->children_offset + 1, flag); + + if (update & PBVH_UpdateBB) + update_node_vb(bvh, node); + if (update & PBVH_UpdateOriginalBB) + node->orig_vb = node->vb; + } + + return update; +} + +void BLI_pbvh_update(PBVH *bvh, int flag, float (*face_nors)[3]) +{ + PBVHNode **nodes; + int totnode; + + if (!bvh->nodes) + return; + + BLI_pbvh_search_gather(bvh, update_search_cb, SET_INT_IN_POINTER(flag), + &nodes, &totnode); + + if (flag & PBVH_UpdateNormals) + pbvh_update_normals(bvh, nodes, totnode, face_nors); + + if (flag & (PBVH_UpdateBB | PBVH_UpdateOriginalBB | PBVH_UpdateRedraw)) + pbvh_update_BB_redraw(bvh, nodes, totnode, flag); + + if (flag & (PBVH_UpdateBB | PBVH_UpdateOriginalBB)) + pbvh_flush_bb(bvh, bvh->nodes, flag); + + if (nodes) MEM_freeN(nodes); +} + +void BLI_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3]) +{ + PBVHIter iter; + PBVHNode *node; + BB bb; + + BB_reset(&bb); + + pbvh_iter_begin(&iter, bvh, NULL, NULL); + + while ((node = pbvh_iter_next(&iter))) + if (node->flag & PBVH_UpdateRedraw) + BB_expand_with_bb(&bb, &node->vb); + + pbvh_iter_end(&iter); + + copy_v3_v3(bb_min, bb.bmin); + copy_v3_v3(bb_max, bb.bmax); +} + +void BLI_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***gridfaces, int *totface) +{ + PBVHIter iter; + PBVHNode *node; + GHashIterator *hiter; + GHash *map; + void *face, **faces; + unsigned i; + int tot; + + map = BLI_ghash_ptr_new("pbvh_get_grid_updates gh"); + + pbvh_iter_begin(&iter, bvh, NULL, NULL); + + while ((node = pbvh_iter_next(&iter))) { + if (node->flag & PBVH_UpdateNormals) { + for (i = 0; i < node->totprim; ++i) { + face = bvh->gridfaces[node->prim_indices[i]]; + if (!BLI_ghash_lookup(map, face)) + BLI_ghash_insert(map, face, face); + } + + if (clear) + node->flag &= ~PBVH_UpdateNormals; + } + } + + pbvh_iter_end(&iter); + + tot = BLI_ghash_size(map); + if (tot == 0) { + *totface = 0; + *gridfaces = NULL; + BLI_ghash_free(map, NULL, NULL); + return; + } + + faces = MEM_callocN(sizeof(void *) * tot, "PBVH Grid Faces"); + + for (hiter = BLI_ghashIterator_new(map), i = 0; + !BLI_ghashIterator_isDone(hiter); + BLI_ghashIterator_step(hiter), ++i) + { + faces[i] = BLI_ghashIterator_getKey(hiter); + } + + BLI_ghashIterator_free(hiter); + + BLI_ghash_free(map, NULL, NULL); + + *totface = tot; + *gridfaces = faces; +} + +/***************************** PBVH Access ***********************************/ + +PBVHType BLI_pbvh_type(const PBVH *bvh) +{ + return bvh->type; +} + +BLI_bitmap *BLI_pbvh_grid_hidden(const PBVH *bvh) +{ + BLI_assert(bvh->type == PBVH_GRIDS); + return bvh->grid_hidden; +} + +void BLI_pbvh_get_grid_key(const PBVH *bvh, CCGKey *key) +{ + BLI_assert(bvh->type == PBVH_GRIDS); + *key = bvh->gridkey; +} + +/***************************** Node Access ***********************************/ + +void BLI_pbvh_node_mark_update(PBVHNode *node) +{ + node->flag |= PBVH_UpdateNormals | PBVH_UpdateBB | PBVH_UpdateOriginalBB | PBVH_UpdateDrawBuffers | PBVH_UpdateRedraw; +} + +void BLI_pbvh_node_mark_rebuild_draw(PBVHNode *node) +{ + node->flag |= PBVH_RebuildDrawBuffers | PBVH_UpdateDrawBuffers | PBVH_UpdateRedraw; +} + +void BLI_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden) +{ + BLI_assert(node->flag & PBVH_Leaf); + + if (fully_hidden) + node->flag |= PBVH_FullyHidden; + else + node->flag &= ~PBVH_FullyHidden; +} + +void BLI_pbvh_node_get_verts(PBVH *bvh, PBVHNode *node, int **vert_indices, MVert **verts) +{ + if (vert_indices) *vert_indices = node->vert_indices; + if (verts) *verts = bvh->verts; +} + +void BLI_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node, int *uniquevert, int *totvert) +{ + int tot; + + switch (bvh->type) { + case PBVH_GRIDS: + tot = node->totprim * bvh->gridkey.grid_area; + if (totvert) *totvert = tot; + if (uniquevert) *uniquevert = tot; + break; + case PBVH_FACES: + if (totvert) *totvert = node->uniq_verts + node->face_verts; + if (uniquevert) *uniquevert = node->uniq_verts; + break; + } +} + +void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node, int **grid_indices, int *totgrid, int *maxgrid, int *gridsize, CCGElem ***griddata, DMGridAdjacency **gridadj) +{ + switch (bvh->type) { + case PBVH_GRIDS: + if (grid_indices) *grid_indices = node->prim_indices; + if (totgrid) *totgrid = node->totprim; + if (maxgrid) *maxgrid = bvh->totgrid; + if (gridsize) *gridsize = bvh->gridkey.grid_size; + if (griddata) *griddata = bvh->grids; + if (gridadj) *gridadj = bvh->gridadj; + break; + case PBVH_FACES: + if (grid_indices) *grid_indices = NULL; + if (totgrid) *totgrid = 0; + if (maxgrid) *maxgrid = 0; + if (gridsize) *gridsize = 0; + if (griddata) *griddata = NULL; + if (gridadj) *gridadj = NULL; + break; + } +} + +void BLI_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3]) +{ + copy_v3_v3(bb_min, node->vb.bmin); + copy_v3_v3(bb_max, node->vb.bmax); +} + +void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3]) +{ + copy_v3_v3(bb_min, node->orig_vb.bmin); + copy_v3_v3(bb_max, node->orig_vb.bmax); +} + +void BLI_pbvh_node_get_proxies(PBVHNode *node, PBVHProxyNode **proxies, int *proxy_count) +{ + if (node->proxy_count > 0) { + if (proxies) *proxies = node->proxies; + if (proxy_count) *proxy_count = node->proxy_count; + } + else { + if (proxies) *proxies = 0; + if (proxy_count) *proxy_count = 0; + } +} + +/********************************* Raycast ***********************************/ + +typedef struct { + IsectRayAABBData ray; + int original; +} RaycastData; + +static int ray_aabb_intersect(PBVHNode *node, void *data_v) +{ + RaycastData *rcd = data_v; + float bb_min[3], bb_max[3]; + + if (rcd->original) + BLI_pbvh_node_get_original_BB(node, bb_min, bb_max); + else + BLI_pbvh_node_get_BB(node, bb_min, bb_max); + + return isect_ray_aabb(&rcd->ray, bb_min, bb_max, &node->tmin); +} + +void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitOccludedCallback cb, void *data, + const float ray_start[3], const float ray_normal[3], + int original) +{ + RaycastData rcd; + + isect_ray_aabb_initialize(&rcd.ray, ray_start, ray_normal); + rcd.original = original; + + BLI_pbvh_search_callback_occluded(bvh, ray_aabb_intersect, &rcd, cb, data); +} + +static int ray_face_intersection(const float ray_start[3], + const float ray_normal[3], + const float *t0, const float *t1, + const float *t2, const float *t3, + float *fdist) +{ + float dist; + + if ((isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t1, t2, &dist, NULL, 0.1f) && dist < *fdist) || + (t3 && isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t2, t3, &dist, NULL, 0.1f) && dist < *fdist)) + { + *fdist = dist; + return 1; + } + else { + return 0; + } +} + +static int pbvh_faces_node_raycast(PBVH *bvh, const PBVHNode *node, + float (*origco)[3], + const float ray_start[3], + const float ray_normal[3], float *dist) +{ + const MVert *vert = bvh->verts; + const int *faces = node->prim_indices; + int i, hit = 0, totface = node->totprim; + + for (i = 0; i < totface; ++i) { + const MFace *f = bvh->faces + faces[i]; + const int *face_verts = node->face_vert_indices[i]; + + if (paint_is_face_hidden(f, vert)) + continue; + + if (origco) { + /* intersect with backuped original coordinates */ + hit |= ray_face_intersection(ray_start, ray_normal, + origco[face_verts[0]], + origco[face_verts[1]], + origco[face_verts[2]], + f->v4 ? origco[face_verts[3]] : NULL, + dist); + } + else { + /* intersect with current coordinates */ + hit |= ray_face_intersection(ray_start, ray_normal, + vert[f->v1].co, + vert[f->v2].co, + vert[f->v3].co, + f->v4 ? vert[f->v4].co : NULL, + dist); + } + } + + return hit; +} + +static int pbvh_grids_node_raycast(PBVH *bvh, PBVHNode *node, + float (*origco)[3], + const float ray_start[3], + const float ray_normal[3], float *dist) +{ + int totgrid = node->totprim; + int gridsize = bvh->gridkey.grid_size; + int i, x, y, hit = 0; + + for (i = 0; i < totgrid; ++i) { + CCGElem *grid = bvh->grids[node->prim_indices[i]]; + BLI_bitmap gh; + + if (!grid) + continue; + + gh = bvh->grid_hidden[node->prim_indices[i]]; + + for (y = 0; y < gridsize - 1; ++y) { + for (x = 0; x < gridsize - 1; ++x) { + /* check if grid face is hidden */ + if (gh) { + if (paint_is_grid_face_hidden(gh, gridsize, x, y)) + continue; + } + + if (origco) { + hit |= ray_face_intersection(ray_start, ray_normal, + origco[y * gridsize + x], + origco[y * gridsize + x + 1], + origco[(y + 1) * gridsize + x + 1], + origco[(y + 1) * gridsize + x], + dist); + } + else { + hit |= ray_face_intersection(ray_start, ray_normal, + CCG_grid_elem_co(&bvh->gridkey, grid, x, y), + CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y), + CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y + 1), + CCG_grid_elem_co(&bvh->gridkey, grid, x, y + 1), + dist); + } + } + } + + if (origco) + origco += gridsize * gridsize; + } + + return hit; +} + +int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3], + const float ray_start[3], const float ray_normal[3], + float *dist) +{ + int hit = 0; + + if (node->flag & PBVH_FullyHidden) + return 0; + + switch (bvh->type) { + case PBVH_FACES: + hit |= pbvh_faces_node_raycast(bvh, node, origco, + ray_start, ray_normal, dist); + break; + case PBVH_GRIDS: + hit |= pbvh_grids_node_raycast(bvh, node, origco, + ray_start, ray_normal, dist); + break; + } + + return hit; +} + +//#include + +void BLI_pbvh_node_draw(PBVHNode *node, void *setMaterial) +{ +#if 0 + /* XXX: Just some quick code to show leaf nodes in different colors */ + float col[3]; int i; + + if (0) { //is_partial) { + col[0] = (rand() / (float)RAND_MAX); col[1] = col[2] = 0.6; + } + else { + srand((long long)node); + for (i = 0; i < 3; ++i) + col[i] = (rand() / (float)RAND_MAX) * 0.3 + 0.7; + } + glMaterialfv(GL_FRONT_AND_BACK, GL_DIFFUSE, col); + + glColor3f(1, 0, 0); +#endif + + if (!(node->flag & PBVH_FullyHidden)) + GPU_draw_buffers(node->draw_buffers, setMaterial); +} + +typedef enum { + ISECT_INSIDE, + ISECT_OUTSIDE, + ISECT_INTERSECT +} PlaneAABBIsect; + +/* Adapted from: + * http://www.gamedev.net/community/forums/topic.asp?topic_id=512123 + * Returns true if the AABB is at least partially within the frustum + * (ok, not a real frustum), false otherwise. + */ +static PlaneAABBIsect test_planes_aabb(const float bb_min[3], + const float bb_max[3], + const float (*planes)[4]) +{ + float vmin[3], vmax[3]; + PlaneAABBIsect ret = ISECT_INSIDE; + int i, axis; + + for (i = 0; i < 4; ++i) { + for (axis = 0; axis < 3; ++axis) { + if (planes[i][axis] > 0) { + vmin[axis] = bb_min[axis]; + vmax[axis] = bb_max[axis]; + } + else { + vmin[axis] = bb_max[axis]; + vmax[axis] = bb_min[axis]; + } + } + + if (dot_v3v3(planes[i], vmin) + planes[i][3] > 0) + return ISECT_OUTSIDE; + else if (dot_v3v3(planes[i], vmax) + planes[i][3] >= 0) + ret = ISECT_INTERSECT; + } + + return ret; +} + +int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data) +{ + float bb_min[3], bb_max[3]; + + BLI_pbvh_node_get_BB(node, bb_min, bb_max); + return test_planes_aabb(bb_min, bb_max, data) != ISECT_OUTSIDE; +} + +int BLI_pbvh_node_planes_exclude_AABB(PBVHNode *node, void *data) +{ + float bb_min[3], bb_max[3]; + + BLI_pbvh_node_get_BB(node, bb_min, bb_max); + return test_planes_aabb(bb_min, bb_max, data) != ISECT_INSIDE; +} + +static void pbvh_node_check_diffuse_changed(PBVH *bvh, PBVHNode *node) +{ + if (!node->draw_buffers) + return; + + if (GPU_buffers_diffuse_changed(node->draw_buffers, bvh->show_diffuse_color)) + node->flag |= PBVH_UpdateDrawBuffers; +} + +void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3], + DMSetMaterial setMaterial) +{ + PBVHNode **nodes; + int a, totnode; + + for (a = 0; a < bvh->totnode; a++) + pbvh_node_check_diffuse_changed(bvh, &bvh->nodes[a]); + + BLI_pbvh_search_gather(bvh, update_search_cb, SET_INT_IN_POINTER(PBVH_UpdateNormals | PBVH_UpdateDrawBuffers), + &nodes, &totnode); + + pbvh_update_normals(bvh, nodes, totnode, face_nors); + pbvh_update_draw_buffers(bvh, nodes, totnode); + + if (nodes) MEM_freeN(nodes); + + if (planes) { + BLI_pbvh_search_callback(bvh, BLI_pbvh_node_planes_contain_AABB, + planes, BLI_pbvh_node_draw, setMaterial); + } + else { + BLI_pbvh_search_callback(bvh, NULL, NULL, BLI_pbvh_node_draw, setMaterial); + } +} + +void BLI_pbvh_grids_update(PBVH *bvh, CCGElem **grids, DMGridAdjacency *gridadj, void **gridfaces, + DMFlagMat *flagmats, BLI_bitmap *grid_hidden) +{ + int a; + + bvh->grids = grids; + bvh->gridadj = gridadj; + bvh->gridfaces = gridfaces; + + if (flagmats != bvh->grid_flag_mats || bvh->grid_hidden != grid_hidden) { + bvh->grid_flag_mats = flagmats; + bvh->grid_hidden = grid_hidden; + + for (a = 0; a < bvh->totnode; ++a) + BLI_pbvh_node_mark_rebuild_draw(&bvh->nodes[a]); + } +} + +float (*BLI_pbvh_get_vertCos(PBVH * pbvh))[3] +{ + int a; + float (*vertCos)[3] = NULL; + + if (pbvh->verts) { + float *co; + MVert *mvert = pbvh->verts; + + vertCos = MEM_callocN(3 * pbvh->totvert * sizeof(float), "BLI_pbvh_get_vertCoords"); + co = (float *)vertCos; + + for (a = 0; a < pbvh->totvert; a++, mvert++, co += 3) { + copy_v3_v3(co, mvert->co); + } + } + + return vertCos; +} + +void BLI_pbvh_apply_vertCos(PBVH *pbvh, float (*vertCos)[3]) +{ + int a; + + if (!pbvh->deformed) { + if (pbvh->verts) { + /* if pbvh is not already deformed, verts/faces points to the */ + /* original data and applying new coords to this arrays would lead to */ + /* unneeded deformation -- duplicate verts/faces to avoid this */ + + pbvh->verts = MEM_dupallocN(pbvh->verts); + pbvh->faces = MEM_dupallocN(pbvh->faces); + + pbvh->deformed = 1; + } + } + + if (pbvh->verts) { + MVert *mvert = pbvh->verts; + /* copy new verts coords */ + for (a = 0; a < pbvh->totvert; ++a, ++mvert) { + copy_v3_v3(mvert->co, vertCos[a]); + mvert->flag |= ME_VERT_PBVH_UPDATE; + } + + /* coordinates are new -- normals should also be updated */ + BKE_mesh_calc_normals_tessface(pbvh->verts, pbvh->totvert, pbvh->faces, pbvh->totprim, NULL); + + for (a = 0; a < pbvh->totnode; ++a) + BLI_pbvh_node_mark_update(&pbvh->nodes[a]); + + BLI_pbvh_update(pbvh, PBVH_UpdateBB, NULL); + BLI_pbvh_update(pbvh, PBVH_UpdateOriginalBB, NULL); + + } +} + +int BLI_pbvh_isDeformed(PBVH *pbvh) +{ + return pbvh->deformed; +} +/* Proxies */ + +PBVHProxyNode *BLI_pbvh_node_add_proxy(PBVH *bvh, PBVHNode *node) +{ + int index, totverts; + + #pragma omp critical + { + + index = node->proxy_count; + + node->proxy_count++; + + if (node->proxies) + node->proxies = MEM_reallocN(node->proxies, node->proxy_count * sizeof(PBVHProxyNode)); + else + node->proxies = MEM_mallocN(sizeof(PBVHProxyNode), "PBVHNodeProxy"); + + BLI_pbvh_node_num_verts(bvh, node, &totverts, NULL); + node->proxies[index].co = MEM_callocN(sizeof(float[3]) * totverts, "PBVHNodeProxy.co"); + } + + return node->proxies + index; +} + +void BLI_pbvh_node_free_proxies(PBVHNode *node) +{ + #pragma omp critical + { + int p; + + for (p = 0; p < node->proxy_count; p++) { + MEM_freeN(node->proxies[p].co); + node->proxies[p].co = 0; + } + + MEM_freeN(node->proxies); + node->proxies = 0; + + node->proxy_count = 0; + } +} + +void BLI_pbvh_gather_proxies(PBVH *pbvh, PBVHNode ***r_array, int *r_tot) +{ + PBVHNode **array = NULL, **newarray, *node; + int tot = 0, space = 0; + int n; + + for (n = 0; n < pbvh->totnode; n++) { + node = pbvh->nodes + n; + + if (node->proxy_count > 0) { + if (tot == space) { + /* resize array if needed */ + space = (tot == 0) ? 32 : space * 2; + newarray = MEM_callocN(sizeof(PBVHNode) * space, "BLI_pbvh_gather_proxies"); + + if (array) { + memcpy(newarray, array, sizeof(PBVHNode) * tot); + MEM_freeN(array); + } + + array = newarray; + } + + array[tot] = node; + tot++; + } + } + + if (tot == 0 && array) { + MEM_freeN(array); + array = NULL; + } + + *r_array = array; + *r_tot = tot; +} + +void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node, + PBVHVertexIter *vi, int mode) +{ + struct CCGElem **grids; + struct MVert *verts; + int *grid_indices, *vert_indices; + int totgrid, gridsize, uniq_verts, totvert; + + vi->grid = 0; + vi->no = 0; + vi->fno = 0; + vi->mvert = 0; + + BLI_pbvh_node_get_grids(bvh, node, &grid_indices, &totgrid, NULL, &gridsize, &grids, NULL); + BLI_pbvh_node_num_verts(bvh, node, &uniq_verts, &totvert); + BLI_pbvh_node_get_verts(bvh, node, &vert_indices, &verts); + vi->key = &bvh->gridkey; + + vi->grids = grids; + vi->grid_indices = grid_indices; + vi->totgrid = (grids) ? totgrid : 1; + vi->gridsize = gridsize; + + if (mode == PBVH_ITER_ALL) + vi->totvert = totvert; + else + vi->totvert = uniq_verts; + vi->vert_indices = vert_indices; + vi->mverts = verts; + + vi->gh = NULL; + if (vi->grids && mode == PBVH_ITER_UNIQUE) + vi->grid_hidden = bvh->grid_hidden; + + vi->mask = NULL; + if (!vi->grids) + vi->vmask = CustomData_get_layer(bvh->vdata, CD_PAINT_MASK); +} + +void pbvh_show_diffuse_color_set(PBVH *bvh, int show_diffuse_color) +{ + bvh->show_diffuse_color = show_diffuse_color; +} diff --git a/source/blender/blenkernel/intern/speaker.c b/source/blender/blenkernel/intern/speaker.c index 4594445dec0..f6599cc9648 100644 --- a/source/blender/blenkernel/intern/speaker.c +++ b/source/blender/blenkernel/intern/speaker.c @@ -35,7 +35,6 @@ #include "BLI_math.h" #include "BLI_utildefines.h" -#include "BKE_bpath.h" #include "BKE_animsys.h" #include "BKE_global.h" diff --git a/source/blender/blenkernel/intern/subsurf_ccg.c b/source/blender/blenkernel/intern/subsurf_ccg.c index be8b572417e..fdd115617de 100644 --- a/source/blender/blenkernel/intern/subsurf_ccg.c +++ b/source/blender/blenkernel/intern/subsurf_ccg.c @@ -50,8 +50,8 @@ #include "BLI_edgehash.h" #include "BLI_math.h" #include "BLI_memarena.h" -#include "BLI_pbvh.h" +#include "BKE_pbvh.h" #include "BKE_ccg.h" #include "BKE_cdderivedmesh.h" #include "BKE_global.h" diff --git a/source/blender/blenkernel/intern/texture.c b/source/blender/blenkernel/intern/texture.c index b78d23c5437..149842bc038 100644 --- a/source/blender/blenkernel/intern/texture.c +++ b/source/blender/blenkernel/intern/texture.c @@ -42,7 +42,6 @@ #include "BLI_math.h" #include "BLI_kdopbvh.h" #include "BLI_utildefines.h" -#include "BKE_bpath.h" #include "DNA_key_types.h" #include "DNA_object_types.h" diff --git a/source/blender/blenkernel/intern/world.c b/source/blender/blenkernel/intern/world.c index ef5ad435037..ad101c41dc5 100644 --- a/source/blender/blenkernel/intern/world.c +++ b/source/blender/blenkernel/intern/world.c @@ -40,7 +40,6 @@ #include "BLI_listbase.h" #include "BLI_utildefines.h" -#include "BKE_bpath.h" #include "BKE_animsys.h" #include "BKE_global.h" diff --git a/source/blender/blenlib/BLI_pbvh.h b/source/blender/blenlib/BLI_pbvh.h deleted file mode 100644 index 59ecdb359c9..00000000000 --- a/source/blender/blenlib/BLI_pbvh.h +++ /dev/null @@ -1,270 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * 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. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -#ifndef __BLI_PBVH_H__ -#define __BLI_PBVH_H__ - -/** \file BLI_pbvh.h - * \ingroup bli - * \brief A BVH for high poly meshes. - */ - -#include "BLI_bitmap.h" - -struct CCGElem; -struct CCGKey; -struct CustomData; -struct DMFlagMat; -struct DMGridAdjacency; -struct ListBase; -struct MFace; -struct MVert; -struct PBVH; -struct PBVHNode; - -typedef struct PBVH PBVH; -typedef struct PBVHNode PBVHNode; - -typedef struct { - float (*co)[3]; -} PBVHProxyNode; - -/* Callbacks */ - -/* returns 1 if the search should continue from this node, 0 otherwise */ -typedef int (*BLI_pbvh_SearchCallback)(PBVHNode *node, void *data); - -typedef void (*BLI_pbvh_HitCallback)(PBVHNode *node, void *data); -typedef void (*BLI_pbvh_HitOccludedCallback)(PBVHNode *node, void *data, float *tmin); - -/* Building */ - -PBVH *BLI_pbvh_new(void); -void BLI_pbvh_build_mesh(PBVH *bvh, struct MFace *faces, struct MVert *verts, - int totface, int totvert, struct CustomData *vdata); -void BLI_pbvh_build_grids(PBVH *bvh, struct CCGElem **grid_elems, - struct DMGridAdjacency *gridadj, int totgrid, - struct CCGKey *key, void **gridfaces, struct DMFlagMat *flagmats, - unsigned int **grid_hidden); -void BLI_pbvh_free(PBVH *bvh); - -/* Hierarchical Search in the BVH, two methods: - * - for each hit calling a callback - * - gather nodes in an array (easy to multithread) */ - -void BLI_pbvh_search_callback(PBVH *bvh, - BLI_pbvh_SearchCallback scb, void *search_data, - BLI_pbvh_HitCallback hcb, void *hit_data); - -void BLI_pbvh_search_gather(PBVH *bvh, - BLI_pbvh_SearchCallback scb, void *search_data, - PBVHNode ***array, int *tot); - -/* Raycast - * the hit callback is called for all leaf nodes intersecting the ray; - * it's up to the callback to find the primitive within the leaves that is - * hit first */ - -void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitOccludedCallback cb, void *data, - const float ray_start[3], const float ray_normal[3], - int original); - -int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3], - const float ray_start[3], const float ray_normal[3], - float *dist); - -/* Drawing */ - -void BLI_pbvh_node_draw(PBVHNode *node, void *data); -void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3], - int (*setMaterial)(int, void *attribs)); - -/* PBVH Access */ -typedef enum { - PBVH_FACES, - PBVH_GRIDS, -} PBVHType; - -PBVHType BLI_pbvh_type(const PBVH *bvh); - -/* multires hidden data, only valid for type == PBVH_GRIDS */ -unsigned int **BLI_pbvh_grid_hidden(const PBVH *bvh); - -/* multires level, only valid for type == PBVH_GRIDS */ -void BLI_pbvh_get_grid_key(const PBVH *pbvh, struct CCGKey *key); - -/* Node Access */ - -typedef enum { - PBVH_Leaf = 1, - - PBVH_UpdateNormals = 2, - PBVH_UpdateBB = 4, - PBVH_UpdateOriginalBB = 8, - PBVH_UpdateDrawBuffers = 16, - PBVH_UpdateRedraw = 32, - - PBVH_RebuildDrawBuffers = 64, - PBVH_FullyHidden = 128 -} PBVHNodeFlags; - -void BLI_pbvh_node_mark_update(PBVHNode *node); -void BLI_pbvh_node_mark_rebuild_draw(PBVHNode *node); -void BLI_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden); - -void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node, - int **grid_indices, int *totgrid, int *maxgrid, int *gridsize, - struct CCGElem ***grid_elems, struct DMGridAdjacency **gridadj); -void BLI_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node, - int *uniquevert, int *totvert); -void BLI_pbvh_node_get_verts(PBVH *bvh, PBVHNode *node, - int **vert_indices, struct MVert **verts); - -void BLI_pbvh_node_get_BB(PBVHNode * node, float bb_min[3], float bb_max[3]); -void BLI_pbvh_node_get_original_BB(PBVHNode * node, float bb_min[3], float bb_max[3]); - -float BLI_pbvh_node_get_tmin(PBVHNode *node); - -/* test if AABB is at least partially inside the planes' volume */ -int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data); -/* test if AABB is at least partially outside the planes' volume */ -int BLI_pbvh_node_planes_exclude_AABB(PBVHNode *node, void *data); - -/* Update Normals/Bounding Box/Draw Buffers/Redraw and clear flags */ - -void BLI_pbvh_update(PBVH *bvh, int flags, float (*face_nors)[3]); -void BLI_pbvh_redraw_BB(PBVH * bvh, float bb_min[3], float bb_max[3]); -void BLI_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***gridfaces, int *totface); -void BLI_pbvh_grids_update(PBVH *bvh, struct CCGElem **grid_elems, - struct DMGridAdjacency *gridadj, void **gridfaces, - struct DMFlagMat *flagmats, unsigned int **grid_hidden); - -/* vertex deformer */ -float (*BLI_pbvh_get_vertCos(struct PBVH *pbvh))[3]; -void BLI_pbvh_apply_vertCos(struct PBVH *pbvh, float (*vertCos)[3]); -int BLI_pbvh_isDeformed(struct PBVH *pbvh); - - -/* Vertex Iterator */ - -/* this iterator has quite a lot of code, but it's designed to: - * - allow the compiler to eliminate dead code and variables - * - spend most of the time in the relatively simple inner loop */ - -/* note: PBVH_ITER_ALL does not skip hidden vertices, - * PBVH_ITER_UNIQUE does */ -#define PBVH_ITER_ALL 0 -#define PBVH_ITER_UNIQUE 1 - -typedef struct PBVHVertexIter { - /* iteration */ - int g; - int width; - int height; - int gx; - int gy; - int i; - - /* grid */ - struct CCGElem **grids; - struct CCGElem *grid; - struct CCGKey *key; - BLI_bitmap *grid_hidden, gh; - int *grid_indices; - int totgrid; - int gridsize; - - /* mesh */ - struct MVert *mverts; - int totvert; - int *vert_indices; - float *vmask; - - /* result: these are all computed in the macro, but we assume - * that compiler optimization's will skip the ones we don't use */ - struct MVert *mvert; - float *co; - short *no; - float *fno; - float *mask; -} PBVHVertexIter; - -#ifdef _MSC_VER -#pragma warning (disable:4127) // conditional expression is constant -#endif - -void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node, - PBVHVertexIter *vi, int mode); - -#define BLI_pbvh_vertex_iter_begin(bvh, node, vi, mode) \ - pbvh_vertex_iter_init(bvh, node, &vi, mode); \ - \ - for (vi.i = 0, vi.g = 0; vi.g < vi.totgrid; vi.g++) { \ - if (vi.grids) { \ - vi.width = vi.gridsize; \ - vi.height = vi.gridsize; \ - vi.grid = vi.grids[vi.grid_indices[vi.g]]; \ - if (mode == PBVH_ITER_UNIQUE) \ - vi.gh = vi.grid_hidden[vi.grid_indices[vi.g]]; \ - } \ - else { \ - vi.width = vi.totvert; \ - vi.height = 1; \ - } \ - \ - for (vi.gy = 0; vi.gy < vi.height; vi.gy++) { \ - for (vi.gx = 0; vi.gx < vi.width; vi.gx++, vi.i++) { \ - if (vi.grid) { \ - vi.co = CCG_elem_co(vi.key, vi.grid); \ - vi.fno = CCG_elem_no(vi.key, vi.grid); \ - vi.mask = vi.key->has_mask ? CCG_elem_mask(vi.key, vi.grid) : NULL; \ - vi.grid = CCG_elem_next(vi.key, vi.grid); \ - if (vi.gh) { \ - if (BLI_BITMAP_GET(vi.gh, vi.gy * vi.gridsize + vi.gx)) \ - continue; \ - } \ - } \ - else { \ - vi.mvert = &vi.mverts[vi.vert_indices[vi.gx]]; \ - if (mode == PBVH_ITER_UNIQUE && vi.mvert->flag & ME_HIDE) \ - continue; \ - vi.co = vi.mvert->co; \ - vi.no = vi.mvert->no; \ - if (vi.vmask) \ - vi.mask = &vi.vmask[vi.vert_indices[vi.gx]]; \ - } \ - -#define BLI_pbvh_vertex_iter_end \ - } \ - } \ - } - -void BLI_pbvh_node_get_proxies(PBVHNode *node, PBVHProxyNode **proxies, int *proxy_count); -void BLI_pbvh_node_free_proxies(PBVHNode *node); -PBVHProxyNode *BLI_pbvh_node_add_proxy(PBVH *bvh, PBVHNode *node); -void BLI_pbvh_gather_proxies(PBVH *pbvh, PBVHNode ***nodes, int *totnode); - -//void BLI_pbvh_node_BB_reset(PBVHNode *node); -//void BLI_pbvh_node_BB_expand(PBVHNode *node, float co[3]); - -void pbvh_show_diffuse_color_set(PBVH *bvh, int show_diffuse_color); - -#endif /* __BLI_PBVH_H__ */ - diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index f1f70a79202..6644c58611f 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -25,9 +25,7 @@ set(INC . - ../blenkernel - ../blenloader - ../gpu + # ../blenkernel # dont add this back! ../makesdna ../../../intern/ghost ../../../intern/guardedalloc @@ -77,7 +75,6 @@ set(SRC intern/md5.c intern/noise.c intern/path_util.c - intern/pbvh.c intern/quadric.c intern/rand.c intern/rct.c @@ -135,7 +132,6 @@ set(SRC BLI_mempool.h BLI_noise.h BLI_path_util.h - BLI_pbvh.h BLI_quadric.h BLI_rand.h BLI_rect.h diff --git a/source/blender/blenlib/SConscript b/source/blender/blenlib/SConscript index e53f622a5c4..e42c43566fc 100644 --- a/source/blender/blenlib/SConscript +++ b/source/blender/blenlib/SConscript @@ -4,8 +4,8 @@ Import ('env') sources = env.Glob('intern/*.c') cflags='' -incs = '. ../makesdna ../blenkernel #/intern/guardedalloc #/intern/ghost ../editors/include ../gpu ../blenloader' -incs += ' ../windowmanager ../bmesh #/extern/glew/include' +# don't add ../blenkernel back! +incs = '. ../makesdna #/intern/guardedalloc #/intern/ghost' incs += ' ' + env['BF_FREETYPE_INC'] incs += ' ' + env['BF_ZLIB_INC'] diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index 8767a9ac14c..7d2fc38272d 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -39,7 +39,7 @@ #include "BLI_mempool.h" #include "BLI_ghash.h" -#include "BLO_sys_types.h" // for intptr_t support +#include "MEM_sys_types.h" /* for intptr_t support */ /***/ unsigned int hashsizes[] = { diff --git a/source/blender/blenlib/intern/endian_switch.c b/source/blender/blenlib/intern/endian_switch.c index b9b18136863..e3ed88b6f8d 100644 --- a/source/blender/blenlib/intern/endian_switch.c +++ b/source/blender/blenlib/intern/endian_switch.c @@ -24,7 +24,7 @@ * \ingroup bli */ -#include "BLO_sys_types.h" +#include "MEM_sys_types.h" #include "BLI_utildefines.h" #include "BLI_endian_switch.h" diff --git a/source/blender/blenlib/intern/fileops.c b/source/blender/blenlib/intern/fileops.c index 883cdfde426..0f42fca9f12 100644 --- a/source/blender/blenlib/intern/fileops.c +++ b/source/blender/blenlib/intern/fileops.c @@ -63,7 +63,7 @@ #include "BLI_blenlib.h" #include "BLI_utildefines.h" -#include "BLO_sys_types.h" // for intptr_t support +#include "MEM_sys_types.h" // for intptr_t support /* gzip the file in from and write it to "to". diff --git a/source/blender/blenlib/intern/freetypefont.c b/source/blender/blenlib/intern/freetypefont.c index 0a87316aa81..353b73a6403 100644 --- a/source/blender/blenlib/intern/freetypefont.c +++ b/source/blender/blenlib/intern/freetypefont.c @@ -52,8 +52,6 @@ #include "BLI_math.h" #include "BLI_utildefines.h" -#include "BKE_font.h" - #include "DNA_vfont_types.h" #include "DNA_packedFile_types.h" #include "DNA_curve_types.h" diff --git a/source/blender/blenlib/intern/path_util.c b/source/blender/blenlib/intern/path_util.c index 444daf8817c..7c1842b10f2 100644 --- a/source/blender/blenlib/intern/path_util.c +++ b/source/blender/blenlib/intern/path_util.c @@ -47,7 +47,7 @@ #include "BLI_string_utf8.h" #include "BLI_utildefines.h" -#include "BKE_blender.h" /* BLENDER_VERSION */ +#include "../blenkernel/BKE_blender.h" /* BLENDER_VERSION, bad level include (no function call) */ #include "GHOST_Path-api.h" diff --git a/source/blender/blenlib/intern/pbvh.c b/source/blender/blenlib/intern/pbvh.c deleted file mode 100644 index 6fa6d86589f..00000000000 --- a/source/blender/blenlib/intern/pbvh.c +++ /dev/null @@ -1,1911 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * 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. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file blender/blenlib/intern/pbvh.c - * \ingroup bli - */ - - - -#include "DNA_meshdata_types.h" - -#include "MEM_guardedalloc.h" - -#include "BLI_bitmap.h" -#include "BLI_math.h" -#include "BLI_utildefines.h" -#include "BLI_ghash.h" -#include "BLI_pbvh.h" - -#include "BKE_ccg.h" -#include "BKE_DerivedMesh.h" -#include "BKE_mesh.h" /* for BKE_mesh_calc_normals */ -#include "BKE_global.h" /* for BKE_mesh_calc_normals */ -#include "BKE_paint.h" -#include "BKE_subsurf.h" - -#include "GPU_buffers.h" - -#define LEAF_LIMIT 10000 - -//#define PERFCNTRS - -/* Axis-aligned bounding box */ -typedef struct { - float bmin[3], bmax[3]; -} BB; - -/* Axis-aligned bounding box with centroid */ -typedef struct { - float bmin[3], bmax[3], bcentroid[3]; -} BBC; - -struct PBVHNode { - /* Opaque handle for drawing code */ - GPU_Buffers *draw_buffers; - - /* Voxel bounds */ - BB vb; - BB orig_vb; - - /* For internal nodes, the offset of the children in the PBVH - * 'nodes' array. */ - int children_offset; - - /* Pointer into the PBVH prim_indices array and the number of - * primitives used by this leaf node. - * - * Used for leaf nodes in both mesh- and multires-based PBVHs. - */ - int *prim_indices; - unsigned int totprim; - - /* Array of indices into the mesh's MVert array. Contains the - * indices of all vertices used by faces that are within this - * node's bounding box. - * - * Note that a vertex might be used by a multiple faces, and - * these faces might be in different leaf nodes. Such a vertex - * will appear in the vert_indices array of each of those leaf - * nodes. - * - * In order to support cases where you want access to multiple - * nodes' vertices without duplication, the vert_indices array - * is ordered such that the first part of the array, up to - * index 'uniq_verts', contains "unique" vertex indices. These - * vertices might not be truly unique to this node, but if - * they appear in another node's vert_indices array, they will - * be above that node's 'uniq_verts' value. - * - * Used for leaf nodes in a mesh-based PBVH (not multires.) - */ - int *vert_indices; - unsigned int uniq_verts, face_verts; - - /* An array mapping face corners into the vert_indices - * array. The array is sized to match 'totprim', and each of - * the face's corners gets an index into the vert_indices - * array, in the same order as the corners in the original - * MFace. The fourth value should not be used if the original - * face is a triangle. - * - * Used for leaf nodes in a mesh-based PBVH (not multires.) - */ - int (*face_vert_indices)[4]; - - /* Indicates whether this node is a leaf or not; also used for - * marking various updates that need to be applied. */ - PBVHNodeFlags flag : 8; - - /* Used for raycasting: how close bb is to the ray point. */ - float tmin; - - int proxy_count; - PBVHProxyNode *proxies; -}; - -struct PBVH { - PBVHType type; - - PBVHNode *nodes; - int node_mem_count, totnode; - - int *prim_indices; - int totprim; - int totvert; - - int leaf_limit; - - /* Mesh data */ - MVert *verts; - MFace *faces; - CustomData *vdata; - - /* Grid Data */ - CCGKey gridkey; - CCGElem **grids; - DMGridAdjacency *gridadj; - void **gridfaces; - const DMFlagMat *grid_flag_mats; - int totgrid; - BLI_bitmap *grid_hidden; - - /* Only used during BVH build and update, - * don't need to remain valid after */ - BLI_bitmap vert_bitmap; - -#ifdef PERFCNTRS - int perf_modified; -#endif - - /* flag are verts/faces deformed */ - int deformed; - - int show_diffuse_color; -}; - -#define STACK_FIXED_DEPTH 100 - -typedef struct PBVHStack { - PBVHNode *node; - int revisiting; -} PBVHStack; - -typedef struct PBVHIter { - PBVH *bvh; - BLI_pbvh_SearchCallback scb; - void *search_data; - - PBVHStack *stack; - int stacksize; - - PBVHStack stackfixed[STACK_FIXED_DEPTH]; - int stackspace; -} PBVHIter; - -static void BB_reset(BB *bb) -{ - bb->bmin[0] = bb->bmin[1] = bb->bmin[2] = FLT_MAX; - bb->bmax[0] = bb->bmax[1] = bb->bmax[2] = -FLT_MAX; -} - -/* Expand the bounding box to include a new coordinate */ -static void BB_expand(BB *bb, float co[3]) -{ - int i; - for (i = 0; i < 3; ++i) { - bb->bmin[i] = min_ff(bb->bmin[i], co[i]); - bb->bmax[i] = max_ff(bb->bmax[i], co[i]); - } -} - -/* Expand the bounding box to include another bounding box */ -static void BB_expand_with_bb(BB *bb, BB *bb2) -{ - int i; - for (i = 0; i < 3; ++i) { - bb->bmin[i] = min_ff(bb->bmin[i], bb2->bmin[i]); - bb->bmax[i] = max_ff(bb->bmax[i], bb2->bmax[i]); - } -} - -/* Return 0, 1, or 2 to indicate the widest axis of the bounding box */ -static int BB_widest_axis(BB *bb) -{ - float dim[3]; - int i; - - for (i = 0; i < 3; ++i) - dim[i] = bb->bmax[i] - bb->bmin[i]; - - if (dim[0] > dim[1]) { - if (dim[0] > dim[2]) - return 0; - else - return 2; - } - else { - if (dim[1] > dim[2]) - return 1; - else - return 2; - } -} - -static void BBC_update_centroid(BBC *bbc) -{ - int i; - for (i = 0; i < 3; ++i) - bbc->bcentroid[i] = (bbc->bmin[i] + bbc->bmax[i]) * 0.5f; -} - -/* Not recursive */ -static void update_node_vb(PBVH *bvh, PBVHNode *node) -{ - BB vb; - - BB_reset(&vb); - - if (node->flag & PBVH_Leaf) { - PBVHVertexIter vd; - - BLI_pbvh_vertex_iter_begin(bvh, node, vd, PBVH_ITER_ALL) - { - BB_expand(&vb, vd.co); - } - BLI_pbvh_vertex_iter_end; - } - else { - BB_expand_with_bb(&vb, - &bvh->nodes[node->children_offset].vb); - BB_expand_with_bb(&vb, - &bvh->nodes[node->children_offset + 1].vb); - } - - node->vb = vb; -} - -//void BLI_pbvh_node_BB_reset(PBVHNode *node) -//{ -// BB_reset(&node->vb); -//} -// -//void BLI_pbvh_node_BB_expand(PBVHNode *node, float co[3]) -//{ -// BB_expand(&node->vb, co); -//} - -static int face_materials_match(const MFace *f1, const MFace *f2) -{ - return ((f1->flag & ME_SMOOTH) == (f2->flag & ME_SMOOTH) && - (f1->mat_nr == f2->mat_nr)); -} - -static int grid_materials_match(const DMFlagMat *f1, const DMFlagMat *f2) -{ - return ((f1->flag & ME_SMOOTH) == (f2->flag & ME_SMOOTH) && - (f1->mat_nr == f2->mat_nr)); -} - -/* Adapted from BLI_kdopbvh.c */ -/* Returns the index of the first element on the right of the partition */ -static int partition_indices(int *prim_indices, int lo, int hi, int axis, - float mid, BBC *prim_bbc) -{ - int i = lo, j = hi; - for (;; ) { - for (; prim_bbc[prim_indices[i]].bcentroid[axis] < mid; i++) ; - for (; mid < prim_bbc[prim_indices[j]].bcentroid[axis]; j--) ; - - if (!(i < j)) - return i; - - SWAP(int, prim_indices[i], prim_indices[j]); - i++; - } -} - -/* Returns the index of the first element on the right of the partition */ -static int partition_indices_material(PBVH *bvh, int lo, int hi) -{ - const MFace *faces = bvh->faces; - const DMFlagMat *flagmats = bvh->grid_flag_mats; - const int *indices = bvh->prim_indices; - const void *first; - int i = lo, j = hi; - - if (bvh->faces) - first = &faces[bvh->prim_indices[lo]]; - else - first = &flagmats[bvh->prim_indices[lo]]; - - for (;; ) { - if (bvh->faces) { - for (; face_materials_match(first, &faces[indices[i]]); i++) ; - for (; !face_materials_match(first, &faces[indices[j]]); j--) ; - } - else { - for (; grid_materials_match(first, &flagmats[indices[i]]); i++) ; - for (; !grid_materials_match(first, &flagmats[indices[j]]); j--) ; - } - - if (!(i < j)) - return i; - - SWAP(int, bvh->prim_indices[i], bvh->prim_indices[j]); - i++; - } -} - -static void grow_nodes(PBVH *bvh, int totnode) -{ - if (totnode > bvh->node_mem_count) { - PBVHNode *prev = bvh->nodes; - bvh->node_mem_count *= 1.33; - if (bvh->node_mem_count < totnode) - bvh->node_mem_count = totnode; - bvh->nodes = MEM_callocN(sizeof(PBVHNode) * bvh->node_mem_count, - "bvh nodes"); - memcpy(bvh->nodes, prev, bvh->totnode * sizeof(PBVHNode)); - MEM_freeN(prev); - } - - bvh->totnode = totnode; -} - -/* Add a vertex to the map, with a positive value for unique vertices and - * a negative value for additional vertices */ -static int map_insert_vert(PBVH *bvh, GHash *map, - unsigned int *face_verts, - unsigned int *uniq_verts, int vertex) -{ - void *value, *key = SET_INT_IN_POINTER(vertex); - - if (!BLI_ghash_haskey(map, key)) { - if (BLI_BITMAP_GET(bvh->vert_bitmap, vertex)) { - value = SET_INT_IN_POINTER(~(*face_verts)); - ++(*face_verts); - } - else { - BLI_BITMAP_SET(bvh->vert_bitmap, vertex); - value = SET_INT_IN_POINTER(*uniq_verts); - ++(*uniq_verts); - } - - BLI_ghash_insert(map, key, value); - return GET_INT_FROM_POINTER(value); - } - else - return GET_INT_FROM_POINTER(BLI_ghash_lookup(map, key)); -} - -/* Find vertices used by the faces in this node and update the draw buffers */ -static void build_mesh_leaf_node(PBVH *bvh, PBVHNode *node) -{ - GHashIterator *iter; - GHash *map; - int i, j, totface; - - map = BLI_ghash_int_new("build_mesh_leaf_node gh"); - - node->uniq_verts = node->face_verts = 0; - totface = node->totprim; - - node->face_vert_indices = MEM_callocN(sizeof(int) * 4 * totface, - "bvh node face vert indices"); - - for (i = 0; i < totface; ++i) { - MFace *f = bvh->faces + node->prim_indices[i]; - int sides = f->v4 ? 4 : 3; - - for (j = 0; j < sides; ++j) { - node->face_vert_indices[i][j] = - map_insert_vert(bvh, map, &node->face_verts, - &node->uniq_verts, (&f->v1)[j]); - } - } - - node->vert_indices = MEM_callocN(sizeof(int) * - (node->uniq_verts + node->face_verts), - "bvh node vert indices"); - - /* Build the vertex list, unique verts first */ - for (iter = BLI_ghashIterator_new(map), i = 0; - BLI_ghashIterator_isDone(iter) == FALSE; - BLI_ghashIterator_step(iter), ++i) - { - void *value = BLI_ghashIterator_getValue(iter); - int ndx = GET_INT_FROM_POINTER(value); - - if (ndx < 0) - ndx = -ndx + node->uniq_verts - 1; - - node->vert_indices[ndx] = - GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(iter)); - } - - BLI_ghashIterator_free(iter); - - for (i = 0; i < totface; ++i) { - MFace *f = bvh->faces + node->prim_indices[i]; - int sides = f->v4 ? 4 : 3; - - for (j = 0; j < sides; ++j) { - if (node->face_vert_indices[i][j] < 0) - node->face_vert_indices[i][j] = - -node->face_vert_indices[i][j] + - node->uniq_verts - 1; - } - } - - if (!G.background) { - node->draw_buffers = - GPU_build_mesh_buffers(node->face_vert_indices, - bvh->faces, bvh->verts, - node->prim_indices, - node->totprim); - } - - node->flag |= PBVH_UpdateDrawBuffers; - - BLI_ghash_free(map, NULL, NULL); -} - -static void build_grids_leaf_node(PBVH *bvh, PBVHNode *node) -{ - if (!G.background) { - node->draw_buffers = - GPU_build_grid_buffers(node->prim_indices, - node->totprim, bvh->grid_hidden, bvh->gridkey.grid_size); - } - node->flag |= PBVH_UpdateDrawBuffers; -} - -static void update_vb(PBVH *bvh, PBVHNode *node, BBC *prim_bbc, - int offset, int count) -{ - int i; - - BB_reset(&node->vb); - for (i = offset + count - 1; i >= offset; --i) { - BB_expand_with_bb(&node->vb, (BB *)(&prim_bbc[bvh->prim_indices[i]])); - } - node->orig_vb = node->vb; -} - -static void build_leaf(PBVH *bvh, int node_index, BBC *prim_bbc, - int offset, int count) -{ - bvh->nodes[node_index].flag |= PBVH_Leaf; - - bvh->nodes[node_index].prim_indices = bvh->prim_indices + offset; - bvh->nodes[node_index].totprim = count; - - /* Still need vb for searches */ - update_vb(bvh, &bvh->nodes[node_index], prim_bbc, offset, count); - - if (bvh->faces) - build_mesh_leaf_node(bvh, bvh->nodes + node_index); - else - build_grids_leaf_node(bvh, bvh->nodes + node_index); -} - -/* Return zero if all primitives in the node can be drawn with the - * same material (including flat/smooth shading), non-zerootherwise */ -static int leaf_needs_material_split(PBVH *bvh, int offset, int count) -{ - int i, prim; - - if (count <= 1) - return 0; - - if (bvh->faces) { - const MFace *first = &bvh->faces[bvh->prim_indices[offset]]; - - for (i = offset + count - 1; i > offset; --i) { - prim = bvh->prim_indices[i]; - if (!face_materials_match(first, &bvh->faces[prim])) - return 1; - } - } - else { - const DMFlagMat *first = &bvh->grid_flag_mats[bvh->prim_indices[offset]]; - - for (i = offset + count - 1; i > offset; --i) { - prim = bvh->prim_indices[i]; - if (!grid_materials_match(first, &bvh->grid_flag_mats[prim])) - return 1; - } - } - - return 0; -} - - -/* Recursively build a node in the tree - * - * vb is the voxel box around all of the primitives contained in - * this node. - * - * cb is the bounding box around all the centroids of the primitives - * contained in this node - * - * offset and start indicate a range in the array of primitive indices - */ - -static void build_sub(PBVH *bvh, int node_index, BB *cb, BBC *prim_bbc, - int offset, int count) -{ - int i, axis, end, below_leaf_limit; - BB cb_backing; - - /* Decide whether this is a leaf or not */ - below_leaf_limit = count <= bvh->leaf_limit; - if (below_leaf_limit) { - if (!leaf_needs_material_split(bvh, offset, count)) { - build_leaf(bvh, node_index, prim_bbc, offset, count); - return; - } - } - - /* Add two child nodes */ - bvh->nodes[node_index].children_offset = bvh->totnode; - grow_nodes(bvh, bvh->totnode + 2); - - /* Update parent node bounding box */ - update_vb(bvh, &bvh->nodes[node_index], prim_bbc, offset, count); - - if (!below_leaf_limit) { - /* Find axis with widest range of primitive centroids */ - if (!cb) { - cb = &cb_backing; - BB_reset(cb); - for (i = offset + count - 1; i >= offset; --i) - BB_expand(cb, prim_bbc[bvh->prim_indices[i]].bcentroid); - } - axis = BB_widest_axis(cb); - - /* Partition primitives along that axis */ - end = partition_indices(bvh->prim_indices, - offset, offset + count - 1, - axis, - (cb->bmax[axis] + cb->bmin[axis]) * 0.5f, - prim_bbc); - } - else { - /* Partition primitives by material */ - end = partition_indices_material(bvh, offset, offset + count - 1); - } - - /* Build children */ - build_sub(bvh, bvh->nodes[node_index].children_offset, NULL, - prim_bbc, offset, end - offset); - build_sub(bvh, bvh->nodes[node_index].children_offset + 1, NULL, - prim_bbc, end, offset + count - end); -} - -static void pbvh_build(PBVH *bvh, BB *cb, BBC *prim_bbc, int totprim) -{ - int i; - - if (totprim != bvh->totprim) { - bvh->totprim = totprim; - if (bvh->nodes) MEM_freeN(bvh->nodes); - if (bvh->prim_indices) MEM_freeN(bvh->prim_indices); - bvh->prim_indices = MEM_callocN(sizeof(int) * totprim, - "bvh prim indices"); - for (i = 0; i < totprim; ++i) - bvh->prim_indices[i] = i; - bvh->totnode = 0; - if (bvh->node_mem_count < 100) { - bvh->node_mem_count = 100; - bvh->nodes = MEM_callocN(sizeof(PBVHNode) * - bvh->node_mem_count, - "bvh initial nodes"); - } - } - - bvh->totnode = 1; - build_sub(bvh, 0, cb, prim_bbc, 0, totprim); -} - -/* Do a full rebuild with on Mesh data structure */ -void BLI_pbvh_build_mesh(PBVH *bvh, MFace *faces, MVert *verts, int totface, int totvert, struct CustomData *vdata) -{ - BBC *prim_bbc = NULL; - BB cb; - int i, j; - - bvh->type = PBVH_FACES; - bvh->faces = faces; - bvh->verts = verts; - bvh->vert_bitmap = BLI_BITMAP_NEW(totvert, "bvh->vert_bitmap"); - bvh->totvert = totvert; - bvh->leaf_limit = LEAF_LIMIT; - bvh->vdata = vdata; - - BB_reset(&cb); - - /* For each face, store the AABB and the AABB centroid */ - prim_bbc = MEM_mallocN(sizeof(BBC) * totface, "prim_bbc"); - - for (i = 0; i < totface; ++i) { - MFace *f = faces + i; - const int sides = f->v4 ? 4 : 3; - BBC *bbc = prim_bbc + i; - - BB_reset((BB *)bbc); - - for (j = 0; j < sides; ++j) - BB_expand((BB *)bbc, verts[(&f->v1)[j]].co); - - BBC_update_centroid(bbc); - - BB_expand(&cb, bbc->bcentroid); - } - - if (totface) - pbvh_build(bvh, &cb, prim_bbc, totface); - - MEM_freeN(prim_bbc); - MEM_freeN(bvh->vert_bitmap); -} - -/* Do a full rebuild with on Grids data structure */ -void BLI_pbvh_build_grids(PBVH *bvh, CCGElem **grids, DMGridAdjacency *gridadj, - int totgrid, CCGKey *key, void **gridfaces, DMFlagMat *flagmats, BLI_bitmap *grid_hidden) -{ - BBC *prim_bbc = NULL; - BB cb; - int gridsize = key->grid_size; - int i, j; - - bvh->type = PBVH_GRIDS; - bvh->grids = grids; - bvh->gridadj = gridadj; - bvh->gridfaces = gridfaces; - bvh->grid_flag_mats = flagmats; - bvh->totgrid = totgrid; - bvh->gridkey = *key; - bvh->grid_hidden = grid_hidden; - bvh->leaf_limit = max_ii(LEAF_LIMIT / ((gridsize - 1) * (gridsize - 1)), 1); - - BB_reset(&cb); - - /* For each grid, store the AABB and the AABB centroid */ - prim_bbc = MEM_mallocN(sizeof(BBC) * totgrid, "prim_bbc"); - - for (i = 0; i < totgrid; ++i) { - CCGElem *grid = grids[i]; - BBC *bbc = prim_bbc + i; - - BB_reset((BB *)bbc); - - for (j = 0; j < gridsize * gridsize; ++j) - BB_expand((BB *)bbc, CCG_elem_offset_co(key, grid, j)); - - BBC_update_centroid(bbc); - - BB_expand(&cb, bbc->bcentroid); - } - - if (totgrid) - pbvh_build(bvh, &cb, prim_bbc, totgrid); - - MEM_freeN(prim_bbc); -} - -PBVH *BLI_pbvh_new(void) -{ - PBVH *bvh = MEM_callocN(sizeof(PBVH), "pbvh"); - - return bvh; -} - -void BLI_pbvh_free(PBVH *bvh) -{ - PBVHNode *node; - int i; - - for (i = 0; i < bvh->totnode; ++i) { - node = &bvh->nodes[i]; - - if (node->flag & PBVH_Leaf) { - if (node->draw_buffers) - GPU_free_buffers(node->draw_buffers); - if (node->vert_indices) - MEM_freeN(node->vert_indices); - if (node->face_vert_indices) - MEM_freeN(node->face_vert_indices); - } - } - - if (bvh->deformed) { - if (bvh->verts) { - /* if pbvh was deformed, new memory was allocated for verts/faces -- free it */ - - MEM_freeN(bvh->verts); - if (bvh->faces) - MEM_freeN(bvh->faces); - } - } - - if (bvh->nodes) - MEM_freeN(bvh->nodes); - - if (bvh->prim_indices) - MEM_freeN(bvh->prim_indices); - - MEM_freeN(bvh); -} - -static void pbvh_iter_begin(PBVHIter *iter, PBVH *bvh, BLI_pbvh_SearchCallback scb, void *search_data) -{ - iter->bvh = bvh; - iter->scb = scb; - iter->search_data = search_data; - - iter->stack = iter->stackfixed; - iter->stackspace = STACK_FIXED_DEPTH; - - iter->stack[0].node = bvh->nodes; - iter->stack[0].revisiting = 0; - iter->stacksize = 1; -} - -static void pbvh_iter_end(PBVHIter *iter) -{ - if (iter->stackspace > STACK_FIXED_DEPTH) - MEM_freeN(iter->stack); -} - -static void pbvh_stack_push(PBVHIter *iter, PBVHNode *node, int revisiting) -{ - if (iter->stacksize == iter->stackspace) { - PBVHStack *newstack; - - iter->stackspace *= 2; - newstack = MEM_callocN(sizeof(PBVHStack) * iter->stackspace, "PBVHStack"); - memcpy(newstack, iter->stack, sizeof(PBVHStack) * iter->stacksize); - - if (iter->stackspace > STACK_FIXED_DEPTH) - MEM_freeN(iter->stack); - iter->stack = newstack; - } - - iter->stack[iter->stacksize].node = node; - iter->stack[iter->stacksize].revisiting = revisiting; - iter->stacksize++; -} - -static PBVHNode *pbvh_iter_next(PBVHIter *iter) -{ - PBVHNode *node; - int revisiting; - - /* purpose here is to traverse tree, visiting child nodes before their - * parents, this order is necessary for e.g. computing bounding boxes */ - - while (iter->stacksize) { - /* pop node */ - iter->stacksize--; - node = iter->stack[iter->stacksize].node; - - /* on a mesh with no faces this can happen - * can remove this check if we know meshes have at least 1 face */ - if (node == NULL) - return NULL; - - revisiting = iter->stack[iter->stacksize].revisiting; - - /* revisiting node already checked */ - if (revisiting) - return node; - - if (iter->scb && !iter->scb(node, iter->search_data)) - continue; /* don't traverse, outside of search zone */ - - if (node->flag & PBVH_Leaf) { - /* immediately hit leaf node */ - return node; - } - else { - /* come back later when children are done */ - pbvh_stack_push(iter, node, 1); - - /* push two child nodes on the stack */ - pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset + 1, 0); - pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset, 0); - } - } - - return NULL; -} - -static PBVHNode *pbvh_iter_next_occluded(PBVHIter *iter) -{ - PBVHNode *node; - - while (iter->stacksize) { - /* pop node */ - iter->stacksize--; - node = iter->stack[iter->stacksize].node; - - /* on a mesh with no faces this can happen - * can remove this check if we know meshes have at least 1 face */ - if (node == NULL) return NULL; - - if (iter->scb && !iter->scb(node, iter->search_data)) continue; /* don't traverse, outside of search zone */ - - if (node->flag & PBVH_Leaf) { - /* immediately hit leaf node */ - return node; - } - else { - pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset + 1, 0); - pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset, 0); - } - } - - return NULL; -} - -void BLI_pbvh_search_gather(PBVH *bvh, - BLI_pbvh_SearchCallback scb, void *search_data, - PBVHNode ***r_array, int *r_tot) -{ - PBVHIter iter; - PBVHNode **array = NULL, **newarray, *node; - int tot = 0, space = 0; - - pbvh_iter_begin(&iter, bvh, scb, search_data); - - while ((node = pbvh_iter_next(&iter))) { - if (node->flag & PBVH_Leaf) { - if (tot == space) { - /* resize array if needed */ - space = (tot == 0) ? 32 : space * 2; - newarray = MEM_callocN(sizeof(PBVHNode) * space, "PBVHNodeSearch"); - - if (array) { - memcpy(newarray, array, sizeof(PBVHNode) * tot); - MEM_freeN(array); - } - - array = newarray; - } - - array[tot] = node; - tot++; - } - } - - pbvh_iter_end(&iter); - - if (tot == 0 && array) { - MEM_freeN(array); - array = NULL; - } - - *r_array = array; - *r_tot = tot; -} - -void BLI_pbvh_search_callback(PBVH *bvh, - BLI_pbvh_SearchCallback scb, void *search_data, - BLI_pbvh_HitCallback hcb, void *hit_data) -{ - PBVHIter iter; - PBVHNode *node; - - pbvh_iter_begin(&iter, bvh, scb, search_data); - - while ((node = pbvh_iter_next(&iter))) - if (node->flag & PBVH_Leaf) - hcb(node, hit_data); - - pbvh_iter_end(&iter); -} - -typedef struct node_tree { - PBVHNode *data; - - struct node_tree *left; - struct node_tree *right; -} node_tree; - -static void node_tree_insert(node_tree *tree, node_tree *new_node) -{ - if (new_node->data->tmin < tree->data->tmin) { - if (tree->left) { - node_tree_insert(tree->left, new_node); - } - else { - tree->left = new_node; - } - } - else { - if (tree->right) { - node_tree_insert(tree->right, new_node); - } - else { - tree->right = new_node; - } - } -} - -static void traverse_tree(node_tree *tree, BLI_pbvh_HitOccludedCallback hcb, void *hit_data, float *tmin) -{ - if (tree->left) traverse_tree(tree->left, hcb, hit_data, tmin); - - hcb(tree->data, hit_data, tmin); - - if (tree->right) traverse_tree(tree->right, hcb, hit_data, tmin); -} - -static void free_tree(node_tree *tree) -{ - if (tree->left) { - free_tree(tree->left); - tree->left = 0; - } - - if (tree->right) { - free_tree(tree->right); - tree->right = 0; - } - - free(tree); -} - -float BLI_pbvh_node_get_tmin(PBVHNode *node) -{ - return node->tmin; -} - -static void BLI_pbvh_search_callback_occluded(PBVH *bvh, - BLI_pbvh_SearchCallback scb, void *search_data, - BLI_pbvh_HitOccludedCallback hcb, void *hit_data) -{ - PBVHIter iter; - PBVHNode *node; - node_tree *tree = 0; - - pbvh_iter_begin(&iter, bvh, scb, search_data); - - while ((node = pbvh_iter_next_occluded(&iter))) { - if (node->flag & PBVH_Leaf) { - node_tree *new_node = malloc(sizeof(node_tree)); - - new_node->data = node; - - new_node->left = NULL; - new_node->right = NULL; - - if (tree) { - node_tree_insert(tree, new_node); - } - else { - tree = new_node; - } - } - } - - pbvh_iter_end(&iter); - - if (tree) { - float tmin = FLT_MAX; - traverse_tree(tree, hcb, hit_data, &tmin); - free_tree(tree); - } -} - -static int update_search_cb(PBVHNode *node, void *data_v) -{ - int flag = GET_INT_FROM_POINTER(data_v); - - if (node->flag & PBVH_Leaf) - return (node->flag & flag); - - return 1; -} - -static void pbvh_update_normals(PBVH *bvh, PBVHNode **nodes, - int totnode, float (*face_nors)[3]) -{ - float (*vnor)[3]; - int n; - - if (bvh->type != PBVH_FACES) - return; - - /* could be per node to save some memory, but also means - * we have to store for each vertex which node it is in */ - vnor = MEM_callocN(sizeof(float) * 3 * bvh->totvert, "bvh temp vnors"); - - /* subtle assumptions: - * - We know that for all edited vertices, the nodes with faces - * adjacent to these vertices have been marked with PBVH_UpdateNormals. - * This is true because if the vertex is inside the brush radius, the - * bounding box of it's adjacent faces will be as well. - * - However this is only true for the vertices that have actually been - * edited, not for all vertices in the nodes marked for update, so we - * can only update vertices marked with ME_VERT_PBVH_UPDATE. - */ - - #pragma omp parallel for private(n) schedule(static) - for (n = 0; n < totnode; n++) { - PBVHNode *node = nodes[n]; - - if ((node->flag & PBVH_UpdateNormals)) { - int i, j, totface, *faces; - - faces = node->prim_indices; - totface = node->totprim; - - for (i = 0; i < totface; ++i) { - MFace *f = bvh->faces + faces[i]; - float fn[3]; - unsigned int *fv = &f->v1; - int sides = (f->v4) ? 4 : 3; - - if (f->v4) - normal_quad_v3(fn, bvh->verts[f->v1].co, bvh->verts[f->v2].co, - bvh->verts[f->v3].co, bvh->verts[f->v4].co); - else - normal_tri_v3(fn, bvh->verts[f->v1].co, bvh->verts[f->v2].co, - bvh->verts[f->v3].co); - - for (j = 0; j < sides; ++j) { - int v = fv[j]; - - if (bvh->verts[v].flag & ME_VERT_PBVH_UPDATE) { - /* this seems like it could be very slow but profile - * does not show this, so just leave it for now? */ - #pragma omp atomic - vnor[v][0] += fn[0]; - #pragma omp atomic - vnor[v][1] += fn[1]; - #pragma omp atomic - vnor[v][2] += fn[2]; - } - } - - if (face_nors) - copy_v3_v3(face_nors[faces[i]], fn); - } - } - } - - #pragma omp parallel for private(n) schedule(static) - for (n = 0; n < totnode; n++) { - PBVHNode *node = nodes[n]; - - if (node->flag & PBVH_UpdateNormals) { - int i, *verts, totvert; - - verts = node->vert_indices; - totvert = node->uniq_verts; - - for (i = 0; i < totvert; ++i) { - const int v = verts[i]; - MVert *mvert = &bvh->verts[v]; - - if (mvert->flag & ME_VERT_PBVH_UPDATE) { - float no[3]; - - copy_v3_v3(no, vnor[v]); - normalize_v3(no); - normal_float_to_short_v3(mvert->no, no); - - mvert->flag &= ~ME_VERT_PBVH_UPDATE; - } - } - - node->flag &= ~PBVH_UpdateNormals; - } - } - - MEM_freeN(vnor); -} - -static void pbvh_update_BB_redraw(PBVH *bvh, PBVHNode **nodes, - int totnode, int flag) -{ - int n; - - /* update BB, redraw flag */ - #pragma omp parallel for private(n) schedule(static) - for (n = 0; n < totnode; n++) { - PBVHNode *node = nodes[n]; - - if ((flag & PBVH_UpdateBB) && (node->flag & PBVH_UpdateBB)) - /* don't clear flag yet, leave it for flushing later */ - update_node_vb(bvh, node); - - if ((flag & PBVH_UpdateOriginalBB) && (node->flag & PBVH_UpdateOriginalBB)) - node->orig_vb = node->vb; - - if ((flag & PBVH_UpdateRedraw) && (node->flag & PBVH_UpdateRedraw)) - node->flag &= ~PBVH_UpdateRedraw; - } -} - -static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode) -{ - PBVHNode *node; - int n; - - /* can't be done in parallel with OpenGL */ - for (n = 0; n < totnode; n++) { - node = nodes[n]; - - if (node->flag & PBVH_RebuildDrawBuffers) { - GPU_free_buffers(node->draw_buffers); - switch (bvh->type) { - case PBVH_GRIDS: - node->draw_buffers = - GPU_build_grid_buffers(node->prim_indices, - node->totprim, - bvh->grid_hidden, - bvh->gridkey.grid_size); - break; - case PBVH_FACES: - node->draw_buffers = - GPU_build_mesh_buffers(node->face_vert_indices, - bvh->faces, bvh->verts, - node->prim_indices, - node->totprim); - break; - } - - node->flag &= ~PBVH_RebuildDrawBuffers; - } - - if (node->flag & PBVH_UpdateDrawBuffers) { - switch (bvh->type) { - case PBVH_GRIDS: - GPU_update_grid_buffers(node->draw_buffers, - bvh->grids, - bvh->grid_flag_mats, - node->prim_indices, - node->totprim, - &bvh->gridkey, - bvh->show_diffuse_color); - break; - case PBVH_FACES: - GPU_update_mesh_buffers(node->draw_buffers, - bvh->verts, - node->vert_indices, - node->uniq_verts + - node->face_verts, - CustomData_get_layer(bvh->vdata, - CD_PAINT_MASK), - node->face_vert_indices, - bvh->show_diffuse_color); - break; - } - - node->flag &= ~PBVH_UpdateDrawBuffers; - } - } -} - -static int pbvh_flush_bb(PBVH *bvh, PBVHNode *node, int flag) -{ - int update = 0; - - /* difficult to multithread well, we just do single threaded recursive */ - if (node->flag & PBVH_Leaf) { - if (flag & PBVH_UpdateBB) { - update |= (node->flag & PBVH_UpdateBB); - node->flag &= ~PBVH_UpdateBB; - } - - if (flag & PBVH_UpdateOriginalBB) { - update |= (node->flag & PBVH_UpdateOriginalBB); - node->flag &= ~PBVH_UpdateOriginalBB; - } - - return update; - } - else { - update |= pbvh_flush_bb(bvh, bvh->nodes + node->children_offset, flag); - update |= pbvh_flush_bb(bvh, bvh->nodes + node->children_offset + 1, flag); - - if (update & PBVH_UpdateBB) - update_node_vb(bvh, node); - if (update & PBVH_UpdateOriginalBB) - node->orig_vb = node->vb; - } - - return update; -} - -void BLI_pbvh_update(PBVH *bvh, int flag, float (*face_nors)[3]) -{ - PBVHNode **nodes; - int totnode; - - if (!bvh->nodes) - return; - - BLI_pbvh_search_gather(bvh, update_search_cb, SET_INT_IN_POINTER(flag), - &nodes, &totnode); - - if (flag & PBVH_UpdateNormals) - pbvh_update_normals(bvh, nodes, totnode, face_nors); - - if (flag & (PBVH_UpdateBB | PBVH_UpdateOriginalBB | PBVH_UpdateRedraw)) - pbvh_update_BB_redraw(bvh, nodes, totnode, flag); - - if (flag & (PBVH_UpdateBB | PBVH_UpdateOriginalBB)) - pbvh_flush_bb(bvh, bvh->nodes, flag); - - if (nodes) MEM_freeN(nodes); -} - -void BLI_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3]) -{ - PBVHIter iter; - PBVHNode *node; - BB bb; - - BB_reset(&bb); - - pbvh_iter_begin(&iter, bvh, NULL, NULL); - - while ((node = pbvh_iter_next(&iter))) - if (node->flag & PBVH_UpdateRedraw) - BB_expand_with_bb(&bb, &node->vb); - - pbvh_iter_end(&iter); - - copy_v3_v3(bb_min, bb.bmin); - copy_v3_v3(bb_max, bb.bmax); -} - -void BLI_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***gridfaces, int *totface) -{ - PBVHIter iter; - PBVHNode *node; - GHashIterator *hiter; - GHash *map; - void *face, **faces; - unsigned i; - int tot; - - map = BLI_ghash_ptr_new("pbvh_get_grid_updates gh"); - - pbvh_iter_begin(&iter, bvh, NULL, NULL); - - while ((node = pbvh_iter_next(&iter))) { - if (node->flag & PBVH_UpdateNormals) { - for (i = 0; i < node->totprim; ++i) { - face = bvh->gridfaces[node->prim_indices[i]]; - if (!BLI_ghash_lookup(map, face)) - BLI_ghash_insert(map, face, face); - } - - if (clear) - node->flag &= ~PBVH_UpdateNormals; - } - } - - pbvh_iter_end(&iter); - - tot = BLI_ghash_size(map); - if (tot == 0) { - *totface = 0; - *gridfaces = NULL; - BLI_ghash_free(map, NULL, NULL); - return; - } - - faces = MEM_callocN(sizeof(void *) * tot, "PBVH Grid Faces"); - - for (hiter = BLI_ghashIterator_new(map), i = 0; - !BLI_ghashIterator_isDone(hiter); - BLI_ghashIterator_step(hiter), ++i) - { - faces[i] = BLI_ghashIterator_getKey(hiter); - } - - BLI_ghashIterator_free(hiter); - - BLI_ghash_free(map, NULL, NULL); - - *totface = tot; - *gridfaces = faces; -} - -/***************************** PBVH Access ***********************************/ - -PBVHType BLI_pbvh_type(const PBVH *bvh) -{ - return bvh->type; -} - -BLI_bitmap *BLI_pbvh_grid_hidden(const PBVH *bvh) -{ - BLI_assert(bvh->type == PBVH_GRIDS); - return bvh->grid_hidden; -} - -void BLI_pbvh_get_grid_key(const PBVH *bvh, CCGKey *key) -{ - BLI_assert(bvh->type == PBVH_GRIDS); - *key = bvh->gridkey; -} - -/***************************** Node Access ***********************************/ - -void BLI_pbvh_node_mark_update(PBVHNode *node) -{ - node->flag |= PBVH_UpdateNormals | PBVH_UpdateBB | PBVH_UpdateOriginalBB | PBVH_UpdateDrawBuffers | PBVH_UpdateRedraw; -} - -void BLI_pbvh_node_mark_rebuild_draw(PBVHNode *node) -{ - node->flag |= PBVH_RebuildDrawBuffers | PBVH_UpdateDrawBuffers | PBVH_UpdateRedraw; -} - -void BLI_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden) -{ - BLI_assert(node->flag & PBVH_Leaf); - - if (fully_hidden) - node->flag |= PBVH_FullyHidden; - else - node->flag &= ~PBVH_FullyHidden; -} - -void BLI_pbvh_node_get_verts(PBVH *bvh, PBVHNode *node, int **vert_indices, MVert **verts) -{ - if (vert_indices) *vert_indices = node->vert_indices; - if (verts) *verts = bvh->verts; -} - -void BLI_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node, int *uniquevert, int *totvert) -{ - int tot; - - switch (bvh->type) { - case PBVH_GRIDS: - tot = node->totprim * bvh->gridkey.grid_area; - if (totvert) *totvert = tot; - if (uniquevert) *uniquevert = tot; - break; - case PBVH_FACES: - if (totvert) *totvert = node->uniq_verts + node->face_verts; - if (uniquevert) *uniquevert = node->uniq_verts; - break; - } -} - -void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node, int **grid_indices, int *totgrid, int *maxgrid, int *gridsize, CCGElem ***griddata, DMGridAdjacency **gridadj) -{ - switch (bvh->type) { - case PBVH_GRIDS: - if (grid_indices) *grid_indices = node->prim_indices; - if (totgrid) *totgrid = node->totprim; - if (maxgrid) *maxgrid = bvh->totgrid; - if (gridsize) *gridsize = bvh->gridkey.grid_size; - if (griddata) *griddata = bvh->grids; - if (gridadj) *gridadj = bvh->gridadj; - break; - case PBVH_FACES: - if (grid_indices) *grid_indices = NULL; - if (totgrid) *totgrid = 0; - if (maxgrid) *maxgrid = 0; - if (gridsize) *gridsize = 0; - if (griddata) *griddata = NULL; - if (gridadj) *gridadj = NULL; - break; - } -} - -void BLI_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3]) -{ - copy_v3_v3(bb_min, node->vb.bmin); - copy_v3_v3(bb_max, node->vb.bmax); -} - -void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3]) -{ - copy_v3_v3(bb_min, node->orig_vb.bmin); - copy_v3_v3(bb_max, node->orig_vb.bmax); -} - -void BLI_pbvh_node_get_proxies(PBVHNode *node, PBVHProxyNode **proxies, int *proxy_count) -{ - if (node->proxy_count > 0) { - if (proxies) *proxies = node->proxies; - if (proxy_count) *proxy_count = node->proxy_count; - } - else { - if (proxies) *proxies = 0; - if (proxy_count) *proxy_count = 0; - } -} - -/********************************* Raycast ***********************************/ - -typedef struct { - IsectRayAABBData ray; - int original; -} RaycastData; - -static int ray_aabb_intersect(PBVHNode *node, void *data_v) -{ - RaycastData *rcd = data_v; - float bb_min[3], bb_max[3]; - - if (rcd->original) - BLI_pbvh_node_get_original_BB(node, bb_min, bb_max); - else - BLI_pbvh_node_get_BB(node, bb_min, bb_max); - - return isect_ray_aabb(&rcd->ray, bb_min, bb_max, &node->tmin); -} - -void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitOccludedCallback cb, void *data, - const float ray_start[3], const float ray_normal[3], - int original) -{ - RaycastData rcd; - - isect_ray_aabb_initialize(&rcd.ray, ray_start, ray_normal); - rcd.original = original; - - BLI_pbvh_search_callback_occluded(bvh, ray_aabb_intersect, &rcd, cb, data); -} - -static int ray_face_intersection(const float ray_start[3], - const float ray_normal[3], - const float *t0, const float *t1, - const float *t2, const float *t3, - float *fdist) -{ - float dist; - - if ((isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t1, t2, &dist, NULL, 0.1f) && dist < *fdist) || - (t3 && isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t2, t3, &dist, NULL, 0.1f) && dist < *fdist)) - { - *fdist = dist; - return 1; - } - else { - return 0; - } -} - -static int pbvh_faces_node_raycast(PBVH *bvh, const PBVHNode *node, - float (*origco)[3], - const float ray_start[3], - const float ray_normal[3], float *dist) -{ - const MVert *vert = bvh->verts; - const int *faces = node->prim_indices; - int i, hit = 0, totface = node->totprim; - - for (i = 0; i < totface; ++i) { - const MFace *f = bvh->faces + faces[i]; - const int *face_verts = node->face_vert_indices[i]; - - if (paint_is_face_hidden(f, vert)) - continue; - - if (origco) { - /* intersect with backuped original coordinates */ - hit |= ray_face_intersection(ray_start, ray_normal, - origco[face_verts[0]], - origco[face_verts[1]], - origco[face_verts[2]], - f->v4 ? origco[face_verts[3]] : NULL, - dist); - } - else { - /* intersect with current coordinates */ - hit |= ray_face_intersection(ray_start, ray_normal, - vert[f->v1].co, - vert[f->v2].co, - vert[f->v3].co, - f->v4 ? vert[f->v4].co : NULL, - dist); - } - } - - return hit; -} - -static int pbvh_grids_node_raycast(PBVH *bvh, PBVHNode *node, - float (*origco)[3], - const float ray_start[3], - const float ray_normal[3], float *dist) -{ - int totgrid = node->totprim; - int gridsize = bvh->gridkey.grid_size; - int i, x, y, hit = 0; - - for (i = 0; i < totgrid; ++i) { - CCGElem *grid = bvh->grids[node->prim_indices[i]]; - BLI_bitmap gh; - - if (!grid) - continue; - - gh = bvh->grid_hidden[node->prim_indices[i]]; - - for (y = 0; y < gridsize - 1; ++y) { - for (x = 0; x < gridsize - 1; ++x) { - /* check if grid face is hidden */ - if (gh) { - if (paint_is_grid_face_hidden(gh, gridsize, x, y)) - continue; - } - - if (origco) { - hit |= ray_face_intersection(ray_start, ray_normal, - origco[y * gridsize + x], - origco[y * gridsize + x + 1], - origco[(y + 1) * gridsize + x + 1], - origco[(y + 1) * gridsize + x], - dist); - } - else { - hit |= ray_face_intersection(ray_start, ray_normal, - CCG_grid_elem_co(&bvh->gridkey, grid, x, y), - CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y), - CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y + 1), - CCG_grid_elem_co(&bvh->gridkey, grid, x, y + 1), - dist); - } - } - } - - if (origco) - origco += gridsize * gridsize; - } - - return hit; -} - -int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3], - const float ray_start[3], const float ray_normal[3], - float *dist) -{ - int hit = 0; - - if (node->flag & PBVH_FullyHidden) - return 0; - - switch (bvh->type) { - case PBVH_FACES: - hit |= pbvh_faces_node_raycast(bvh, node, origco, - ray_start, ray_normal, dist); - break; - case PBVH_GRIDS: - hit |= pbvh_grids_node_raycast(bvh, node, origco, - ray_start, ray_normal, dist); - break; - } - - return hit; -} - -//#include - -void BLI_pbvh_node_draw(PBVHNode *node, void *setMaterial) -{ -#if 0 - /* XXX: Just some quick code to show leaf nodes in different colors */ - float col[3]; int i; - - if (0) { //is_partial) { - col[0] = (rand() / (float)RAND_MAX); col[1] = col[2] = 0.6; - } - else { - srand((long long)node); - for (i = 0; i < 3; ++i) - col[i] = (rand() / (float)RAND_MAX) * 0.3 + 0.7; - } - glMaterialfv(GL_FRONT_AND_BACK, GL_DIFFUSE, col); - - glColor3f(1, 0, 0); -#endif - - if (!(node->flag & PBVH_FullyHidden)) - GPU_draw_buffers(node->draw_buffers, setMaterial); -} - -typedef enum { - ISECT_INSIDE, - ISECT_OUTSIDE, - ISECT_INTERSECT -} PlaneAABBIsect; - -/* Adapted from: - * http://www.gamedev.net/community/forums/topic.asp?topic_id=512123 - * Returns true if the AABB is at least partially within the frustum - * (ok, not a real frustum), false otherwise. - */ -static PlaneAABBIsect test_planes_aabb(const float bb_min[3], - const float bb_max[3], - const float (*planes)[4]) -{ - float vmin[3], vmax[3]; - PlaneAABBIsect ret = ISECT_INSIDE; - int i, axis; - - for (i = 0; i < 4; ++i) { - for (axis = 0; axis < 3; ++axis) { - if (planes[i][axis] > 0) { - vmin[axis] = bb_min[axis]; - vmax[axis] = bb_max[axis]; - } - else { - vmin[axis] = bb_max[axis]; - vmax[axis] = bb_min[axis]; - } - } - - if (dot_v3v3(planes[i], vmin) + planes[i][3] > 0) - return ISECT_OUTSIDE; - else if (dot_v3v3(planes[i], vmax) + planes[i][3] >= 0) - ret = ISECT_INTERSECT; - } - - return ret; -} - -int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data) -{ - float bb_min[3], bb_max[3]; - - BLI_pbvh_node_get_BB(node, bb_min, bb_max); - return test_planes_aabb(bb_min, bb_max, data) != ISECT_OUTSIDE; -} - -int BLI_pbvh_node_planes_exclude_AABB(PBVHNode *node, void *data) -{ - float bb_min[3], bb_max[3]; - - BLI_pbvh_node_get_BB(node, bb_min, bb_max); - return test_planes_aabb(bb_min, bb_max, data) != ISECT_INSIDE; -} - -static void pbvh_node_check_diffuse_changed(PBVH *bvh, PBVHNode *node) -{ - if (!node->draw_buffers) - return; - - if (GPU_buffers_diffuse_changed(node->draw_buffers, bvh->show_diffuse_color)) - node->flag |= PBVH_UpdateDrawBuffers; -} - -void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3], - DMSetMaterial setMaterial) -{ - PBVHNode **nodes; - int a, totnode; - - for (a = 0; a < bvh->totnode; a++) - pbvh_node_check_diffuse_changed(bvh, &bvh->nodes[a]); - - BLI_pbvh_search_gather(bvh, update_search_cb, SET_INT_IN_POINTER(PBVH_UpdateNormals | PBVH_UpdateDrawBuffers), - &nodes, &totnode); - - pbvh_update_normals(bvh, nodes, totnode, face_nors); - pbvh_update_draw_buffers(bvh, nodes, totnode); - - if (nodes) MEM_freeN(nodes); - - if (planes) { - BLI_pbvh_search_callback(bvh, BLI_pbvh_node_planes_contain_AABB, - planes, BLI_pbvh_node_draw, setMaterial); - } - else { - BLI_pbvh_search_callback(bvh, NULL, NULL, BLI_pbvh_node_draw, setMaterial); - } -} - -void BLI_pbvh_grids_update(PBVH *bvh, CCGElem **grids, DMGridAdjacency *gridadj, void **gridfaces, - DMFlagMat *flagmats, BLI_bitmap *grid_hidden) -{ - int a; - - bvh->grids = grids; - bvh->gridadj = gridadj; - bvh->gridfaces = gridfaces; - - if (flagmats != bvh->grid_flag_mats || bvh->grid_hidden != grid_hidden) { - bvh->grid_flag_mats = flagmats; - bvh->grid_hidden = grid_hidden; - - for (a = 0; a < bvh->totnode; ++a) - BLI_pbvh_node_mark_rebuild_draw(&bvh->nodes[a]); - } -} - -float (*BLI_pbvh_get_vertCos(PBVH * pbvh))[3] -{ - int a; - float (*vertCos)[3] = NULL; - - if (pbvh->verts) { - float *co; - MVert *mvert = pbvh->verts; - - vertCos = MEM_callocN(3 * pbvh->totvert * sizeof(float), "BLI_pbvh_get_vertCoords"); - co = (float *)vertCos; - - for (a = 0; a < pbvh->totvert; a++, mvert++, co += 3) { - copy_v3_v3(co, mvert->co); - } - } - - return vertCos; -} - -void BLI_pbvh_apply_vertCos(PBVH *pbvh, float (*vertCos)[3]) -{ - int a; - - if (!pbvh->deformed) { - if (pbvh->verts) { - /* if pbvh is not already deformed, verts/faces points to the */ - /* original data and applying new coords to this arrays would lead to */ - /* unneeded deformation -- duplicate verts/faces to avoid this */ - - pbvh->verts = MEM_dupallocN(pbvh->verts); - pbvh->faces = MEM_dupallocN(pbvh->faces); - - pbvh->deformed = 1; - } - } - - if (pbvh->verts) { - MVert *mvert = pbvh->verts; - /* copy new verts coords */ - for (a = 0; a < pbvh->totvert; ++a, ++mvert) { - copy_v3_v3(mvert->co, vertCos[a]); - mvert->flag |= ME_VERT_PBVH_UPDATE; - } - - /* coordinates are new -- normals should also be updated */ - BKE_mesh_calc_normals_tessface(pbvh->verts, pbvh->totvert, pbvh->faces, pbvh->totprim, NULL); - - for (a = 0; a < pbvh->totnode; ++a) - BLI_pbvh_node_mark_update(&pbvh->nodes[a]); - - BLI_pbvh_update(pbvh, PBVH_UpdateBB, NULL); - BLI_pbvh_update(pbvh, PBVH_UpdateOriginalBB, NULL); - - } -} - -int BLI_pbvh_isDeformed(PBVH *pbvh) -{ - return pbvh->deformed; -} -/* Proxies */ - -PBVHProxyNode *BLI_pbvh_node_add_proxy(PBVH *bvh, PBVHNode *node) -{ - int index, totverts; - - #pragma omp critical - { - - index = node->proxy_count; - - node->proxy_count++; - - if (node->proxies) - node->proxies = MEM_reallocN(node->proxies, node->proxy_count * sizeof(PBVHProxyNode)); - else - node->proxies = MEM_mallocN(sizeof(PBVHProxyNode), "PBVHNodeProxy"); - - BLI_pbvh_node_num_verts(bvh, node, &totverts, NULL); - node->proxies[index].co = MEM_callocN(sizeof(float[3]) * totverts, "PBVHNodeProxy.co"); - } - - return node->proxies + index; -} - -void BLI_pbvh_node_free_proxies(PBVHNode *node) -{ - #pragma omp critical - { - int p; - - for (p = 0; p < node->proxy_count; p++) { - MEM_freeN(node->proxies[p].co); - node->proxies[p].co = 0; - } - - MEM_freeN(node->proxies); - node->proxies = 0; - - node->proxy_count = 0; - } -} - -void BLI_pbvh_gather_proxies(PBVH *pbvh, PBVHNode ***r_array, int *r_tot) -{ - PBVHNode **array = NULL, **newarray, *node; - int tot = 0, space = 0; - int n; - - for (n = 0; n < pbvh->totnode; n++) { - node = pbvh->nodes + n; - - if (node->proxy_count > 0) { - if (tot == space) { - /* resize array if needed */ - space = (tot == 0) ? 32 : space * 2; - newarray = MEM_callocN(sizeof(PBVHNode) * space, "BLI_pbvh_gather_proxies"); - - if (array) { - memcpy(newarray, array, sizeof(PBVHNode) * tot); - MEM_freeN(array); - } - - array = newarray; - } - - array[tot] = node; - tot++; - } - } - - if (tot == 0 && array) { - MEM_freeN(array); - array = NULL; - } - - *r_array = array; - *r_tot = tot; -} - -void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node, - PBVHVertexIter *vi, int mode) -{ - struct CCGElem **grids; - struct MVert *verts; - int *grid_indices, *vert_indices; - int totgrid, gridsize, uniq_verts, totvert; - - vi->grid = 0; - vi->no = 0; - vi->fno = 0; - vi->mvert = 0; - - BLI_pbvh_node_get_grids(bvh, node, &grid_indices, &totgrid, NULL, &gridsize, &grids, NULL); - BLI_pbvh_node_num_verts(bvh, node, &uniq_verts, &totvert); - BLI_pbvh_node_get_verts(bvh, node, &vert_indices, &verts); - vi->key = &bvh->gridkey; - - vi->grids = grids; - vi->grid_indices = grid_indices; - vi->totgrid = (grids) ? totgrid : 1; - vi->gridsize = gridsize; - - if (mode == PBVH_ITER_ALL) - vi->totvert = totvert; - else - vi->totvert = uniq_verts; - vi->vert_indices = vert_indices; - vi->mverts = verts; - - vi->gh = NULL; - if (vi->grids && mode == PBVH_ITER_UNIQUE) - vi->grid_hidden = bvh->grid_hidden; - - vi->mask = NULL; - if (!vi->grids) - vi->vmask = CustomData_get_layer(bvh->vdata, CD_PAINT_MASK); -} - -void pbvh_show_diffuse_color_set(PBVH *bvh, int show_diffuse_color) -{ - bvh->show_diffuse_color = show_diffuse_color; -} diff --git a/source/blender/blenlib/intern/winstuff.c b/source/blender/blenlib/intern/winstuff.c index 68d9d74cca4..65fb490b218 100644 --- a/source/blender/blenlib/intern/winstuff.c +++ b/source/blender/blenlib/intern/winstuff.c @@ -41,7 +41,7 @@ #include "BLI_path_util.h" #include "BLI_string.h" -#include "BKE_global.h" +#include "../blenkernel/BKE_global.h" /* G.background, bad level include (no function calls) */ #define WIN32_SKIP_HKEY_PROTECTION // need to use HKEY #include "BLI_winstuff.h" diff --git a/source/blender/editors/sculpt_paint/paint_hide.c b/source/blender/editors/sculpt_paint/paint_hide.c index bdd73cd6db3..36fe4715fc0 100644 --- a/source/blender/editors/sculpt_paint/paint_hide.c +++ b/source/blender/editors/sculpt_paint/paint_hide.c @@ -37,7 +37,6 @@ #include "BLI_bitmap.h" #include "BLI_listbase.h" #include "BLI_math_vector.h" -#include "BLI_pbvh.h" #include "BLI_utildefines.h" #include "DNA_mesh_types.h" @@ -45,6 +44,7 @@ #include "DNA_object_types.h" #include "DNA_scene_types.h" +#include "BKE_pbvh.h" #include "BKE_ccg.h" #include "BKE_context.h" #include "BKE_DerivedMesh.h" diff --git a/source/blender/editors/sculpt_paint/paint_mask.c b/source/blender/editors/sculpt_paint/paint_mask.c index 697d7c63d1f..9fe7fc1d3ac 100644 --- a/source/blender/editors/sculpt_paint/paint_mask.c +++ b/source/blender/editors/sculpt_paint/paint_mask.c @@ -38,8 +38,7 @@ #include "DNA_meshdata_types.h" #include "DNA_object_types.h" -#include "BLI_pbvh.h" - +#include "BKE_pbvh.h" #include "BKE_ccg.h" #include "BKE_context.h" #include "BKE_DerivedMesh.h" diff --git a/source/blender/editors/sculpt_paint/sculpt.c b/source/blender/editors/sculpt_paint/sculpt.c index e2ed7776b7e..8325b47beab 100644 --- a/source/blender/editors/sculpt_paint/sculpt.c +++ b/source/blender/editors/sculpt_paint/sculpt.c @@ -40,7 +40,6 @@ #include "BLI_utildefines.h" #include "BLI_dynstr.h" #include "BLI_ghash.h" -#include "BLI_pbvh.h" #include "BLI_threads.h" #include "BLI_rand.h" @@ -51,6 +50,7 @@ #include "DNA_scene_types.h" #include "DNA_brush_types.h" +#include "BKE_pbvh.h" #include "BKE_brush.h" #include "BKE_ccg.h" #include "BKE_cdderivedmesh.h" diff --git a/source/blender/editors/sculpt_paint/sculpt_intern.h b/source/blender/editors/sculpt_paint/sculpt_intern.h index acb906e4a91..44068122b89 100644 --- a/source/blender/editors/sculpt_paint/sculpt_intern.h +++ b/source/blender/editors/sculpt_paint/sculpt_intern.h @@ -38,7 +38,7 @@ #include "DNA_key_types.h" #include "BLI_bitmap.h" -#include "BLI_pbvh.h" +#include "BKE_pbvh.h" struct bContext; struct Brush; diff --git a/source/blender/makesrna/intern/rna_sculpt_paint.c b/source/blender/makesrna/intern/rna_sculpt_paint.c index 84e76fae896..f717c83075a 100644 --- a/source/blender/makesrna/intern/rna_sculpt_paint.c +++ b/source/blender/makesrna/intern/rna_sculpt_paint.c @@ -59,8 +59,7 @@ static EnumPropertyItem particle_edit_hair_brush_items[] = { #include "BKE_pointcache.h" #include "BKE_particle.h" #include "BKE_depsgraph.h" - -#include "BLI_pbvh.h" +#include "BKE_pbvh.h" #include "ED_particle.h" -- cgit v1.2.3