[Bf-blender-cvs] [695da4f] viewport_bvh_select: Initial BVH based object mode selection

Julian Eisel noreply at git.blender.org
Thu Aug 25 17:32:01 CEST 2016


Commit: 695da4fd62a4ade9c47005ca032930ff3dabb28c
Author: Julian Eisel
Date:   Thu Aug 25 15:56:53 2016 +0200
Branches: viewport_bvh_select
https://developer.blender.org/rB695da4fd62a4ade9c47005ca032930ff3dabb28c

Initial BVH based object mode selection

As part of the viewport project, we wanted to switch from OpenGL based to BVH based selection (see https://wiki.blender.org/index.php/Dev:2.8/Viewport#Discussion_Items). This should increase performance and make selection drawing and hence driver independent. (OpenGL selection was always an issue with buggy drivers.)

This commit adds initial functions for building and visualizing an object BVH (AABB) using the multi-threaded BLI_bvhtree and uses it for object mode selecting. Only basic selection works now, not taking care for movie clip editor selection syncing or so. One idea was to keep the actual BVH part a bit separate from selection, so that it can be reused e.g. for culling out objects out of view frustum before drawing.
Quite some speedup is already visible, but it's not fair to compare to previous selection, since we're only doing bounding box intesection checks currently. Detailed geometry intersection checks are not done yet, neither are overlapping objects handled.

One issue I faced was that some object types (cameras, lamps, speakers) are basically infinite small points with no visible bounding box. I added some functions to get the visual bounding box for those, but only implemented it for cameras so far.

Main TODOs I can see (random order):
* Selection should behave just like current OpenGL based selection.
* Lasso, Circle & Box select.
* The BVH tree is currently recreated on every redraw, more reasonable updating needs to be checked on. It's unsure if it's better to commonly recreate the entire tree or if we can use some more advanced caching and updating. The BLI_bvhtree isn't really flexible when it comes to updating (e.g. you can't insert objects after initial creating), so maybe adding a different BVH type will be needed.
* Do more detailed geometry intersection checks. OpenSubdiv needs some special attention here, since its geometry only lives on the GPU (AFAIK). It should be possible to send geometry patches from GPU to CPU so we can create AABBs for BVH ray casting.
* Better handling for overlapping geometry.
* BVH based selection for other modes (edit mode, pose mode, etc). I'd like to make the edit mode BVH lookups efficient enough to allow performant pre-selection highlighting.
* Allow selecting lamps and speakers (not possible currently).

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

M	source/blender/blenkernel/BKE_camera.h
M	source/blender/blenkernel/BKE_object.h
M	source/blender/blenkernel/intern/camera.c
M	source/blender/blenkernel/intern/object.c
M	source/blender/blenkernel/intern/pbvh.c
M	source/blender/editors/space_view3d/CMakeLists.txt
M	source/blender/editors/space_view3d/space_view3d.c
A	source/blender/editors/space_view3d/view3d_bvh.c
M	source/blender/editors/space_view3d/view3d_draw.c
M	source/blender/editors/space_view3d/view3d_intern.h
M	source/blender/editors/space_view3d/view3d_select.c
M	source/blender/gpu/GPU_buffers.h
M	source/blender/gpu/intern/gpu_buffers.c
M	source/blender/makesdna/DNA_view3d_types.h

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

diff --git a/source/blender/blenkernel/BKE_camera.h b/source/blender/blenkernel/BKE_camera.h
index 31a732c..f509f24 100644
--- a/source/blender/blenkernel/BKE_camera.h
+++ b/source/blender/blenkernel/BKE_camera.h
@@ -64,6 +64,8 @@ void BKE_camera_object_mode(struct RenderData *rd, struct Object *ob);
 int BKE_camera_sensor_fit(int sensor_fit, float sizex, float sizey);
 float BKE_camera_sensor_size(int sensor_fit, float sensor_x, float sensor_y);
 
+struct BoundBox *BKE_camera_drawboundbox_get(const struct Scene *scene, const struct Object *ob);
+
 /* Camera Parameters:
  *
  * Intermediate struct for storing camera parameters from various sources,
diff --git a/source/blender/blenkernel/BKE_object.h b/source/blender/blenkernel/BKE_object.h
index 1b3e05d..3da0560 100644
--- a/source/blender/blenkernel/BKE_object.h
+++ b/source/blender/blenkernel/BKE_object.h
@@ -147,6 +147,9 @@ struct BoundBox *BKE_boundbox_ensure_minimum_dimensions(
         struct BoundBox *bb, struct BoundBox *bb_temp, const float epsilon);
 
 struct BoundBox *BKE_object_boundbox_get(struct Object *ob);
+struct BoundBox *BKE_object_drawboundbox_get(
+        const struct Scene *scene, const struct Object *ob,
+        bool *r_needs_freeing);
 void BKE_object_dimensions_get(struct Object *ob, float vec[3]);
 void BKE_object_dimensions_set(struct Object *ob, const float value[3]);
 void BKE_object_empty_draw_type_set(struct Object *ob, const int value);
diff --git a/source/blender/blenkernel/intern/camera.c b/source/blender/blenkernel/intern/camera.c
index 85ce399..158d1df 100644
--- a/source/blender/blenkernel/intern/camera.c
+++ b/source/blender/blenkernel/intern/camera.c
@@ -57,6 +57,9 @@
 
 #include "GPU_compositing.h"
 
+#include "MEM_guardedalloc.h"
+
+
 /****************************** Camera Datablock *****************************/
 
 void BKE_camera_init(Camera *cam)
@@ -169,6 +172,41 @@ int BKE_camera_sensor_fit(int sensor_fit, float sizex, float sizey)
 	return sensor_fit;
 }
 
+/**
+ * Even though our virtual cameras are infinite small points with some attributes,
+ * sometimes we need the bounding box that matches what the user sees.
+ *
+ * \return Allocated BoundBox in local space (needs freeing).
+ */
+BoundBox *BKE_camera_drawboundbox_get(const Scene *scene, const Object *ob)
+{
+	Camera *cam = ob->data;
+	BoundBox *bb = MEM_callocN(sizeof(*bb), "Camera boundbox");
+	float viewframe[4][3];
+	float min[3], max[3];
+
+	float dummy_asp[2];
+	float dummy_shift[2];
+	float dummy_drawsize;
+	float scale[3] = {1.0f, 1.0f, 1.0f};
+
+	BKE_camera_view_frame_ex(
+	            scene, cam, cam->drawsize, false,
+	            scale, dummy_asp, dummy_shift, &dummy_drawsize,
+	            viewframe);
+
+	INIT_MINMAX(min, max);
+	for (int i = 0; i < 4; i++) {
+		minmax_v3v3_v3(min, max, viewframe[i]);
+	}
+	const float origin[3] = {0.0f};
+	minmax_v3v3_v3(min, max, origin);
+
+	BKE_boundbox_init_from_minmax(bb, min, max);
+
+	return bb;
+}
+
 /******************************** Camera Params *******************************/
 
 void BKE_camera_params_init(CameraParams *params)
diff --git a/source/blender/blenkernel/intern/object.c b/source/blender/blenkernel/intern/object.c
index d736a45..e582284 100644
--- a/source/blender/blenkernel/intern/object.c
+++ b/source/blender/blenkernel/intern/object.c
@@ -2310,6 +2310,38 @@ BoundBox *BKE_object_boundbox_get(Object *ob)
 	return bb;
 }
 
+/**
+ * For some cases we need the visual bounding box of objects that don't
+ * have real geometry, that are just infinite small points in space.
+ *
+ * \param r_needs_freeing: The bounding box may have been allocated and needs to be freed manually.
+ * \return The visual bounding box in local space.
+ */
+BoundBox *BKE_object_drawboundbox_get(
+        const Scene *scene, const Object *ob,
+        bool *r_needs_freeing)
+{
+	BoundBox *bb = BKE_object_boundbox_get((Object *)ob);
+
+	*r_needs_freeing = false;
+	if (!bb) {
+		switch (ob->type) {
+			case OB_CAMERA:
+				bb = BKE_camera_drawboundbox_get(scene, ob);
+				*r_needs_freeing = true;
+				break;
+			case OB_EMPTY:
+			case OB_LAMP:
+			case OB_SPEAKER:
+				/* TODO */
+			default:
+				break;
+		}
+	}
+
+	return bb;
+}
+
 /* used to temporally disable/enable boundbox */
 void BKE_object_boundbox_flag(Object *ob, int flag, const bool set)
 {
diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c
index ff69f38..7e00029 100644
--- a/source/blender/blenkernel/intern/pbvh.c
+++ b/source/blender/blenkernel/intern/pbvh.c
@@ -1156,15 +1156,15 @@ static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode)
 
 static void pbvh_draw_BB(PBVH *bvh)
 {
-	GPU_init_draw_pbvh_BB();
+	GPU_init_draw_boundbox();
 
 	for (int a = 0; a < bvh->totnode; a++) {
 		PBVHNode *node = &bvh->nodes[a];
 
-		GPU_draw_pbvh_BB(node->vb.bmin, node->vb.bmax, ((node->flag & PBVH_Leaf) != 0));
+		GPU_draw_boundbox(node->vb.bmin, node->vb.bmax, ((node->flag & PBVH_Leaf) != 0));
 	}
 
-	GPU_end_draw_pbvh_BB();
+	GPU_end_draw_boundbox();
 }
 
 static int pbvh_flush_bb(PBVH *bvh, PBVHNode *node, int flag)
diff --git a/source/blender/editors/space_view3d/CMakeLists.txt b/source/blender/editors/space_view3d/CMakeLists.txt
index 059b384..417610d 100644
--- a/source/blender/editors/space_view3d/CMakeLists.txt
+++ b/source/blender/editors/space_view3d/CMakeLists.txt
@@ -50,6 +50,7 @@ set(SRC
 	drawvolume.c
 	space_view3d.c
 	view3d_buttons.c
+	view3d_bvh.c
 	view3d_camera_control.c
 	view3d_draw.c
 	view3d_edit.c
diff --git a/source/blender/editors/space_view3d/space_view3d.c b/source/blender/editors/space_view3d/space_view3d.c
index 075b1fa..0ace734 100644
--- a/source/blender/editors/space_view3d/space_view3d.c
+++ b/source/blender/editors/space_view3d/space_view3d.c
@@ -432,6 +432,10 @@ static void view3d_free(SpaceLink *sl)
 		MEM_freeN(vd->fx_settings.ssao);
 	if (vd->fx_settings.dof)
 		MEM_freeN(vd->fx_settings.dof);
+
+	if (vd->bvhtree) {
+		view3d_objectbvh_free(vd);
+	}
 }
 
 
diff --git a/source/blender/editors/space_view3d/view3d_bvh.c b/source/blender/editors/space_view3d/view3d_bvh.c
new file mode 100644
index 0000000..5bf9048
--- /dev/null
+++ b/source/blender/editors/space_view3d/view3d_bvh.c
@@ -0,0 +1,165 @@
+/*
+ * ***** 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.
+ *
+ * The Original Code is Copyright (C) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ *
+ * Contributor(s): Blender Foundation
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/editors/space_view3d/view3d_bvh.c
+ *  \ingroup spview3d
+ */
+
+#include "BKE_DerivedMesh.h"
+#include "BKE_object.h"
+
+#include "BLI_kdopbvh.h"
+#include "BLI_listbase.h"
+#include "BLI_math.h"
+
+#include "DNA_object_types.h"
+#include "DNA_scene_types.h"
+#include "DNA_screen_types.h"
+#include "DNA_view3d_types.h"
+
+#include "GPU_buffers.h"
+
+#include "MEM_guardedalloc.h"
+
+#include "view3d_intern.h" /* own include */
+
+
+static void bvh_objects_insert(View3D *v3d, const Scene *scene)
+{
+	int i = 0;
+	for (Base *base = scene->base.first; base; base = base->next) {
+		if (BASE_SELECTABLE(v3d, base)) {
+			bool needs_freeing;
+			BoundBox *bb = BKE_object_drawboundbox_get(scene, base->object, &needs_freeing);
+			if (bb) {
+				BoundBox bb_local = *bb;
+				if (needs_freeing) {
+					MEM_freeN(bb);
+				}
+
+				for (int j = 0; j < 8; j++) {
+					mul_v3_m4v3(bb_local.vec[j], base->object->obmat, bb_local.vec[j]);
+				}
+
+				BLI_bvhtree_insert(v3d->bvhtree, i++, &bb_local.vec[0][0], 8);
+			}
+			else {
+//				printf("No BB: %s\n", base->object->id.name + 2);
+			}
+		}
+		else {
+//			printf("Not selectable: %s\n", base->object->id.name + 2);
+		}
+	}
+}
+
+void view3d_objectbvh_rebuild(View3D *v3d, const Scene *scene)
+{
+	BVHTree *bvhtree = v3d->bvhtree;
+	if (bvhtree) {
+		view3d_objectbvh_free(v3d);
+	}
+	v3d->bvhtree = bvhtree = BLI_bvhtree_new(BLI_listbase_count(&scene->base), FLT_EPSILON, 2, 8);
+	bvh_objects_insert(v3d, scene);
+	BLI_bvhtree_balance(bvhtree);
+}
+
+void view3d_objectbvh_free(View3D *v3d)
+{
+	BLI_bvhtree_free(v3d->bvhtree);
+}
+
+Base *view3d_objectbvh_raycast(Scene *scene, View3D *v3d, ARegion *ar, const int mval[2])
+{
+	RegionView3D *rv3d = ar->regiondata;
+	BVHTreeNearest nearest = {.index = -1, .dist_sq = FLT_MAX};
+	const float mval_fl[2] = {mval[0], mval[1]};
+	float ray_start[3] = {0}, ray_normal[3] = {0};
+
+	ED_view3d_win_to_ray(ar, v3d, mval_fl, ray_start, ray_normal, true);
+
+	BLI_bvhtree_find_nearest_to_ray(v3d->bvhtree, ray_start, ray_normal, true, NULL, &nearest, NULL, NULL);
+	/* TODO more refined geometry check */
+
+	/* distance threshold */
+	const float dist_px = sqrtf(nearest.dist_sq) / ED_view3d_pixel_size(rv3d, nearest.co);
+	if (dist_px > SELECT_DIST_THRESHOLD) {
+		return NULL;
+	}
+
+	int i = 0;
+	Base *base;
+	for (base = scene->base.first; base; base = base->next) {
+		if (BASE_SELECTABLE(v3d, base)) {
+			bool needs_freeing;
+			BoundBox *bb = BKE_object_drawboundbox_get(scene, base->object, &needs_freeing);
+			if (bb) {
+				if (needs_freeing) {
+					MEM_freeN(bb);
+				}
+				if (i == nearest.index) {
+					break;
+				}
+				i++;
+			}
+		}
+	}
+	if (base) {
+//		printf("Select: %s\n", base->object->id.name + 2);
+	}
+	return base;
+}
+
+static void bvh_draw_boundbox(const BVHTreeAxisRange *bounds, const bool is_leaf)
+{
+	float min[3] = {bounds[0].min, bounds[1].min, bounds[2].min};
+	float max[3] = {bounds[0].max, bounds[1].max, bounds[2].max};
+	GPU_draw_boundbox(min

@@ Diff output truncated at 10240 characters. @@




More information about the Bf-blender-cvs mailing list