3D View: new nethod of opengl selection
authorCampbell Barton <ideasman42@gmail.com>
Wed, 8 Mar 2017 18:17:55 +0000 (05:17 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Wed, 8 Mar 2017 19:22:02 +0000 (06:22 +1100)
Intended to replace legacy GL_SELECT, without the limitations of
sample queries which can't access depth information.

This commit adds VIEW3D_SELECT_PICK_NEAREST and VIEW3D_SELECT_PICK_ALL
which access the depth buffers to detect whats under the pointer,
so initial selection is always the closest item.

The performance of this method depends a lot on the OpenGL
implementations glReadPixels.

Since reading depth can be slow, buffers are cached for object picking
so selecting re-uses depth data, performing 1 draw instead of 3
(for 24, 18, 10 px regions, picking with many items under the pointer).

Occlusion queries draw twice when picking nearest,
so worst case 6x draw calls per selection.

Even with these improvements occlusion queries is faster on AMD hardware.

Depth selection is disabled by default, toggle option under select method.
May enable by default if this works well on different hardware.

Reviewed as D2543

15 files changed:
release/scripts/startup/bl_ui/space_userpref.py
source/blender/editors/armature/armature_select.c
source/blender/editors/armature/editarmature_sketch.c
source/blender/editors/include/ED_view3d.h
source/blender/editors/metaball/mball_edit.c
source/blender/editors/space_view3d/view3d_select.c
source/blender/editors/space_view3d/view3d_view.c
source/blender/gpu/CMakeLists.txt
source/blender/gpu/GPU_select.h
source/blender/gpu/intern/gpu_select.c
source/blender/gpu/intern/gpu_select_pick.c [new file with mode: 0644]
source/blender/gpu/intern/gpu_select_private.h [new file with mode: 0644]
source/blender/gpu/intern/gpu_select_sample_query.c [new file with mode: 0644]
source/blender/makesdna/DNA_userdef_types.h
source/blender/makesrna/intern/rna_userdef.c

index d7f5723539d3c6daa261bacdb86a68abbba154de..cd12255c24c72b1caec67de11b3fcb425fda109f 100644 (file)
@@ -453,6 +453,7 @@ class USERPREF_PT_system(Panel):
         col.separator()
         col.label(text="Selection")
         col.prop(system, "select_method", text="")
+        col.prop(system, "use_select_pick_depth")
 
         col.separator()
 
index ec0f193e7808591184a385b6a1bcaa48ebf6c528..3a0d07c02eec003e0735812cc50c02b3ca18a50d 100644 (file)
@@ -177,7 +177,7 @@ void *get_nearest_bone(bContext *C, const int xy[2], bool findunsel)
        rect.xmin = rect.xmax = xy[0];
        rect.ymin = rect.ymax = xy[1];
        
-       hits = view3d_opengl_select(&vc, buffer, MAXPICKBUF, &rect, true);
+       hits = view3d_opengl_select(&vc, buffer, MAXPICKBUF, &rect, VIEW3D_SELECT_PICK_NEAREST);
 
        if (hits > 0)
                return get_bone_from_selectbuffer(vc.scene, vc.scene->basact, buffer, hits, findunsel, true);
@@ -279,7 +279,7 @@ void ARMATURE_OT_select_linked(wmOperatorType *ot)
 /* note that BONE ROOT only gets drawn for root bones (or without IK) */
 static EditBone *get_nearest_editbonepoint(
         ViewContext *vc, const int mval[2],
-        ListBase *edbo, bool findunsel, int *r_selmask)
+        ListBase *edbo, bool findunsel, bool use_cycle, int *r_selmask)
 {
        bArmature *arm = (bArmature *)vc->obedit->data;
        EditBone *ebone_next_act = arm->act_edbone;
@@ -290,6 +290,7 @@ static EditBone *get_nearest_editbonepoint(
        unsigned int hitresult, besthitresult = BONESEL_NOSEL;
        int i, mindep = 5;
        short hits;
+       static int last_mval[2] = {-100, -100};
 
        /* find the bone after the current active bone, so as to bump up its chances in selection.
         * this way overlapping bones will cycle selection state as with objects. */
@@ -303,12 +304,33 @@ static EditBone *get_nearest_editbonepoint(
                ebone_next_act = NULL;
        }
 
+       bool do_nearest = false;
+
+       /* define if we use solid nearest select or not */
+       if (use_cycle) {
+               if (vc->v3d->drawtype > OB_WIRE) {
+                       do_nearest = true;
+                       if (len_manhattan_v2v2_int(mval, last_mval) < 3) {
+                               do_nearest = false;
+                       }
+               }
+               copy_v2_v2_int(last_mval, mval);
+       }
+       else {
+               if (vc->v3d->drawtype > OB_WIRE) {
+                       do_nearest = true;
+               }
+       }
+
+       const int select_mode = (do_nearest ? VIEW3D_SELECT_PICK_NEAREST : VIEW3D_SELECT_PICK_ALL);
+
+       /* TODO: select larger region first (so we can use GPU_select_cache) */
        BLI_rcti_init_pt_radius(&rect, mval, 5);
+       hits = view3d_opengl_select(vc, buffer, MAXPICKBUF, &rect, select_mode);
 
-       hits = view3d_opengl_select(vc, buffer, MAXPICKBUF, &rect, true);
        if (hits == 0) {
                BLI_rcti_init_pt_radius(&rect, mval, 12);
-               hits = view3d_opengl_select(vc, buffer, MAXPICKBUF, &rect, true);
+               hits = view3d_opengl_select(vc, buffer, MAXPICKBUF, &rect, select_mode);
        }
        /* See if there are any selected bones in this group */
        if (hits > 0) {
@@ -434,7 +456,7 @@ bool ED_armature_select_pick(bContext *C, const int mval[2], bool extend, bool d
                return true;
        }
 
-       nearBone = get_nearest_editbonepoint(&vc, mval, arm->edbo, true, &selmask);
+       nearBone = get_nearest_editbonepoint(&vc, mval, arm->edbo, true, true, &selmask);
        if (nearBone) {
 
                if (!extend && !deselect && !toggle) {
index 8690072ca85abef5f0292ba792809efccf0bafc1..bba486bc65c04d9994acc934261773e788b4e627 100644 (file)
@@ -1909,7 +1909,7 @@ static bool sk_selectStroke(bContext *C, SK_Sketch *sketch, const int mval[2], c
 
        BLI_rcti_init_pt_radius(&rect, mval, 5);
 
-       hits = view3d_opengl_select(&vc, buffer, MAXPICKBUF, &rect, true);
+       hits = view3d_opengl_select(&vc, buffer, MAXPICKBUF, &rect, VIEW3D_SELECT_PICK_NEAREST);
 
        if (hits > 0) {
                int besthitresult = -1;
index 5514dc0d3dfcff561715eb25569736a0b9dcaad4..af6f37d937c3d064bae9ed797e5364e5c60ac539 100644 (file)
@@ -302,7 +302,19 @@ bool ED_view3d_autodist_depth_seg(struct ARegion *ar, const int mval_sta[2], con
 /* select */
 #define MAXPICKELEMS    2500
 #define MAXPICKBUF      (4 * MAXPICKELEMS)
-short view3d_opengl_select(struct ViewContext *vc, unsigned int *buffer, unsigned int bufsize, const struct rcti *input, bool do_nearest);
+
+enum {
+       /* all elements in the region, ignore depth */
+       VIEW3D_SELECT_ALL = 0,
+       /* pick also depth sorts (only for small regions!) */
+       VIEW3D_SELECT_PICK_ALL = 1,
+       /* sorts and only returns visible objects (only for small regions!) */
+       VIEW3D_SELECT_PICK_NEAREST = 2,
+};
+
+int view3d_opengl_select(
+        struct ViewContext *vc, unsigned int *buffer, unsigned int bufsize, const struct rcti *input,
+        int select_mode);
 
 /* view3d_select.c */
 float ED_view3d_select_dist_px(void);
index fff53d6885e0d06346f2b326a9508a5a62a3cee4..bc42717b69fb3b557659e05d34a0e40960b2115d 100644 (file)
@@ -594,7 +594,7 @@ bool ED_mball_select_pick(bContext *C, const int mval[2], bool extend, bool dese
 
        BLI_rcti_init_pt_radius(&rect, mval, 12);
 
-       hits = view3d_opengl_select(&vc, buffer, MAXPICKBUF, &rect, true);
+       hits = view3d_opengl_select(&vc, buffer, MAXPICKBUF, &rect, VIEW3D_SELECT_PICK_NEAREST);
 
        /* does startelem exist? */
        ml = mb->editelems->first;
index 49f24ef634f24aeb73fa413623990d2eea2b28d7..0b3468f2c234c396c9b826dc031e104e4e8a1e06 100644 (file)
 
 #include "GPU_draw.h"
 
+#include "GPU_select.h"
+
 #include "view3d_intern.h"  /* own include */
 
+// #include "PIL_time_utildefines.h"
+
 float ED_view3d_select_dist_px(void)
 {
        return 75.0f * U.pixelsize;
@@ -1091,7 +1095,7 @@ static Base *object_mouse_select_menu(
         bContext *C, ViewContext *vc, unsigned int *buffer, int hits,
         const int mval[2], bool toggle)
 {
-       int baseCount = 0;
+       short baseCount = 0;
        bool ok;
        LinkNode *linklist = NULL;
        
@@ -1236,44 +1240,56 @@ static int mixed_bones_object_selectbuffer(
 
        do_nearest = do_nearest && !enumerate;
 
+       const int select_mode = (do_nearest ? VIEW3D_SELECT_PICK_NEAREST : VIEW3D_SELECT_PICK_ALL);
+       int hits = 0;
+
+       /* we _must_ end cache before return, use 'goto finally' */
+       GPU_select_cache_begin();
+
        BLI_rcti_init_pt_radius(&rect, mval, 14);
-       hits15 = view3d_opengl_select(vc, buffer, MAXPICKBUF, &rect, do_nearest);
+       hits15 = view3d_opengl_select(vc, buffer, MAXPICKBUF, &rect, select_mode);
        if (hits15 == 1) {
-               return selectbuffer_ret_hits_15(buffer, hits15);
+               hits = selectbuffer_ret_hits_15(buffer, hits15);
+               goto finally;
        }
        else if (hits15 > 0) {
                has_bones15 = selectbuffer_has_bones(buffer, hits15);
 
                offs = 4 * hits15;
                BLI_rcti_init_pt_radius(&rect, mval, 9);
-               hits9 = view3d_opengl_select(vc, buffer + offs, MAXPICKBUF - offs, &rect, do_nearest);
+               hits9 = view3d_opengl_select(vc, buffer + offs, MAXPICKBUF - offs, &rect, select_mode);
                if (hits9 == 1) {
-                       return selectbuffer_ret_hits_9(buffer, hits15, hits9);
+                       hits = selectbuffer_ret_hits_9(buffer, hits15, hits9);
+                       goto finally;
                }
                else if (hits9 > 0) {
                        has_bones9 = selectbuffer_has_bones(buffer + offs, hits9);
 
                        offs += 4 * hits9;
                        BLI_rcti_init_pt_radius(&rect, mval, 5);
-                       hits5 = view3d_opengl_select(vc, buffer + offs, MAXPICKBUF - offs, &rect, do_nearest);
+                       hits5 = view3d_opengl_select(vc, buffer + offs, MAXPICKBUF - offs, &rect, select_mode);
                        if (hits5 == 1) {
-                               return selectbuffer_ret_hits_5(buffer, hits15, hits9, hits5);
+                               hits = selectbuffer_ret_hits_5(buffer, hits15, hits9, hits5);
+                               goto finally;
                        }
                        else if (hits5 > 0) {
                                has_bones5 = selectbuffer_has_bones(buffer + offs, hits5);
                        }
                }
 
-               if      (has_bones5)  return selectbuffer_ret_hits_5(buffer,  hits15, hits9, hits5);
-               else if (has_bones9)  return selectbuffer_ret_hits_9(buffer,  hits15, hits9);
-               else if (has_bones15) return selectbuffer_ret_hits_15(buffer, hits15);
-               
-               if      (hits5 > 0) return selectbuffer_ret_hits_5(buffer,  hits15, hits9, hits5);
-               else if (hits9 > 0) return selectbuffer_ret_hits_9(buffer,  hits15, hits9);
-               else                return selectbuffer_ret_hits_15(buffer, hits15);
+               if      (has_bones5)  { hits = selectbuffer_ret_hits_5(buffer,  hits15, hits9, hits5); goto finally; }
+               else if (has_bones9)  { hits = selectbuffer_ret_hits_9(buffer,  hits15, hits9); goto finally; }
+               else if (has_bones15) { hits = selectbuffer_ret_hits_15(buffer, hits15); goto finally; }
+
+               if      (hits5 > 0) { hits = selectbuffer_ret_hits_5(buffer,  hits15, hits9, hits5); goto finally; }
+               else if (hits9 > 0) { hits = selectbuffer_ret_hits_9(buffer,  hits15, hits9); goto finally; }
+               else                { hits = selectbuffer_ret_hits_15(buffer, hits15); goto finally; }
        }
-       
-       return 0;
+
+finally:
+       GPU_select_cache_end();
+
+       return hits;
 }
 
 /* returns basact */
@@ -1466,10 +1482,13 @@ static bool ed_object_select_pick(
                unsigned int buffer[MAXPICKBUF];
                bool do_nearest;
 
+               // TIMEIT_START(select_time);
+
                /* if objects have posemode set, the bones are in the same selection buffer */
-               
                hits = mixed_bones_object_selectbuffer(&vc, buffer, mval, true, enumerate, &do_nearest);
-               
+
+               // TIMEIT_END(select_time);
+
                if (hits > 0) {
                        /* note: bundles are handling in the same way as bones */
                        const bool has_bones = selectbuffer_has_bones(buffer, hits);
@@ -1908,7 +1927,7 @@ static int do_meta_box_select(ViewContext *vc, rcti *rect, bool select, bool ext
        unsigned int buffer[MAXPICKBUF];
        int hits;
 
-       hits = view3d_opengl_select(vc, buffer, MAXPICKBUF, rect, false);
+       hits = view3d_opengl_select(vc, buffer, MAXPICKBUF, rect, VIEW3D_SELECT_ALL);
 
        if (extend == false && select)
                BKE_mball_deselect_all(mb);
@@ -1942,7 +1961,7 @@ static int do_armature_box_select(ViewContext *vc, rcti *rect, bool select, bool
        unsigned int buffer[MAXPICKBUF];
        int hits;
 
-       hits = view3d_opengl_select(vc, buffer, MAXPICKBUF, rect, false);
+       hits = view3d_opengl_select(vc, buffer, MAXPICKBUF, rect, VIEW3D_SELECT_ALL);
        
        /* clear flag we use to detect point was affected */
        for (ebone = arm->edbo->first; ebone; ebone = ebone->next)
@@ -2039,7 +2058,7 @@ static int do_object_pose_box_select(bContext *C, ViewContext *vc, rcti *rect, b
 
        /* selection buffer now has bones potentially too, so we add MAXPICKBUF */
        vbuffer = MEM_mallocN(4 * (totobj + MAXPICKELEMS) * sizeof(unsigned int), "selection buffer");
-       hits = view3d_opengl_select(vc, vbuffer, 4 * (totobj + MAXPICKELEMS), rect, false);
+       hits = view3d_opengl_select(vc, vbuffer, 4 * (totobj + MAXPICKELEMS), rect, VIEW3D_SELECT_ALL);
        /*
         * LOGIC NOTES (theeth):
         * The buffer and ListBase have the same relative order, which makes the selection
index 20361b73e78cdff639a23fd6ba75b90da43aab03..9d1a3633786c935ea6b4ee9aa58dd312c365d3eb 100644 (file)
@@ -1170,18 +1170,24 @@ static void view3d_select_loop(ViewContext *vc, Scene *scene, View3D *v3d, ARegi
  *
  * \note (vc->obedit == NULL) can be set to explicitly skip edit-object selection.
  */
-short view3d_opengl_select(ViewContext *vc, unsigned int *buffer, unsigned int bufsize, const rcti *input, bool do_nearest)
+int view3d_opengl_select(
+        ViewContext *vc, unsigned int *buffer, unsigned int bufsize, const rcti *input,
+        int select_mode)
 {
        Scene *scene = vc->scene;
        View3D *v3d = vc->v3d;
        ARegion *ar = vc->ar;
        rcti rect;
-       short hits;
+       int hits;
        const bool use_obedit_skip = (scene->obedit != NULL) && (vc->obedit == NULL);
-       const bool do_passes = do_nearest && GPU_select_query_check_active();
+       const bool is_pick_select = (U.gpu_select_pick_deph != 0);
+       const bool do_passes = (
+               (is_pick_select == false) &&
+               (select_mode == VIEW3D_SELECT_PICK_NEAREST) &&
+               GPU_select_query_check_active());
+
+       char gpu_select_mode;
 
-       G.f |= G_PICKSEL;
-       
        /* case not a border select */
        if (input->xmin == input->xmax) {
                /* seems to be default value for bones only now */
@@ -1190,7 +1196,38 @@ short view3d_opengl_select(ViewContext *vc, unsigned int *buffer, unsigned int b
        else {
                rect = *input;
        }
-       
+
+       if (is_pick_select) {
+               if (is_pick_select && select_mode == VIEW3D_SELECT_PICK_NEAREST) {
+                       gpu_select_mode = GPU_SELECT_PICK_NEAREST;
+               }
+               else if (is_pick_select && select_mode == VIEW3D_SELECT_PICK_ALL) {
+                       gpu_select_mode = GPU_SELECT_PICK_ALL;
+               }
+               else {
+                       gpu_select_mode = GPU_SELECT_ALL;
+               }
+       }
+       else {
+               if (do_passes) {
+                       gpu_select_mode = GPU_SELECT_NEAREST_FIRST_PASS;
+               }
+               else {
+                       gpu_select_mode = GPU_SELECT_ALL;
+               }
+       }
+
+       /* Re-use cache (rect must be smaller then the cached)
+        * other context is assumed to be unchanged */
+       if (GPU_select_is_cached()) {
+               GPU_select_begin(buffer, bufsize, &rect, gpu_select_mode, 0);
+               GPU_select_cache_load_id();
+               hits = GPU_select_end();
+               goto finally;
+       }
+
+       G.f |= G_PICKSEL;
+
        view3d_winmatrix_set(ar, v3d, &rect);
        mul_m4_m4m4(vc->rv3d->persmat, vc->rv3d->winmat, vc->rv3d->viewmat);
        
@@ -1202,10 +1239,7 @@ short view3d_opengl_select(ViewContext *vc, unsigned int *buffer, unsigned int b
        if (vc->rv3d->rflag & RV3D_CLIPPING)
                ED_view3d_clipping_set(vc->rv3d);
        
-       if (do_passes)
-               GPU_select_begin(buffer, bufsize, &rect, GPU_SELECT_NEAREST_FIRST_PASS, 0);
-       else
-               GPU_select_begin(buffer, bufsize, &rect, GPU_SELECT_ALL, 0);
+       GPU_select_begin(buffer, bufsize, &rect, gpu_select_mode, 0);
 
        view3d_select_loop(vc, scene, v3d, ar, use_obedit_skip);
 
@@ -1231,7 +1265,8 @@ short view3d_opengl_select(ViewContext *vc, unsigned int *buffer, unsigned int b
        
        if (vc->rv3d->rflag & RV3D_CLIPPING)
                ED_view3d_clipping_disable();
-       
+
+finally:
        if (hits < 0) printf("Too many objects in select buffer\n");  /* XXX make error message */
 
        return hits;
index 8885209ce01cce48ebeb21292ae8d34ca932bb55..885ff2ff159c4c70d3e62ffea9eb0ca5df28a2e6 100644 (file)
@@ -57,6 +57,8 @@ set(SRC
        intern/gpu_init_exit.c
        intern/gpu_material.c
        intern/gpu_select.c
+       intern/gpu_select_pick.c
+       intern/gpu_select_sample_query.c
        intern/gpu_shader.c
        intern/gpu_texture.c
 
@@ -97,6 +99,7 @@ set(SRC
        GPU_texture.h
        intern/gpu_codegen.h
        intern/gpu_private.h
+       intern/gpu_select_private.h
 )
 
 data_to_c_simple(shaders/gpu_shader_geometry.glsl SRC)
index 93f5ce13bbdd339b939b972b9ad828ce583cfdad..cf5b8bf7d8f07e44f437cb4e7cbc81ea5d4b4e5c 100644 (file)
@@ -37,8 +37,12 @@ struct rcti;
 /* flags for mode of operation */
 enum {
        GPU_SELECT_ALL                      = 1,
+       /* gpu_select_query */
        GPU_SELECT_NEAREST_FIRST_PASS       = 2,
        GPU_SELECT_NEAREST_SECOND_PASS      = 3,
+       /* gpu_select_pick */
+       GPU_SELECT_PICK_ALL           = 4,
+       GPU_SELECT_PICK_NEAREST       = 5,
 };
 
 void GPU_select_begin(unsigned int *buffer, unsigned int bufsize, const struct rcti *input, char mode, int oldhits);
@@ -46,4 +50,10 @@ bool GPU_select_load_id(unsigned int id);
 unsigned int GPU_select_end(void);
 bool GPU_select_query_check_active(void);
 
+/* cache selection region */
+bool GPU_select_is_cached(void);
+void GPU_select_cache_begin(void);
+void GPU_select_cache_load_id(void);
+void GPU_select_cache_end(void);
+
 #endif
index 35944c455a519097f78298d1eba38e9d04f2e8d9..9496ff137dcffdacf7ac726c54153b96c1aabcb7 100644 (file)
  * Interface for accessing gpu-related methods for selection. The semantics will be
  * similar to glRenderMode(GL_SELECT) since the goal is to maintain compatibility.
  */
+#include <stdlib.h>
+
 #include "GPU_select.h"
 #include "GPU_extensions.h"
 #include "GPU_glew.h"
+
 #include "MEM_guardedalloc.h"
 
 #include "DNA_userdef_types.h"
 
-#include "BLI_rect.h"
-
 #include "BLI_utildefines.h"
 
-/* Ad hoc number of queries to allocate to skip doing many glGenQueries */
-#define ALLOC_QUERIES 200
-
-typedef struct GPUQueryState {
+#include "gpu_select_private.h"
+
+/* Internal algorithm used */
+enum {
+       /** GL_SELECT, legacy OpenGL selection */
+       ALGO_GL_LEGACY = 1,
+       /** glBegin/EndQuery(GL_SAMPLES_PASSED... ), `gpu_select_query.c`
+        * Only sets 4th component (ID) correctly. */
+       ALGO_GL_QUERY = 2,
+       /** Read depth buffer for every drawing pass and extract depths, `gpu_select_pick.c`
+        * Only sets 4th component (ID) correctly. */
+       ALGO_GL_PICK = 3,
+};
+
+typedef struct GPUSelectState {
        /* To ignore selection id calls when not initialized */
        bool select_is_active;
-       /* Tracks whether a query has been issued so that gpu_load_id can end the previous one */
-       bool query_issued;
-       /* array holding the OpenGL query identifiers */
-       unsigned int *queries;
-       /* array holding the id corresponding to each query */
-       unsigned int *id;
-       /* number of queries in *queries and *id */
-       unsigned int num_of_queries;
-       /* index to the next query to start */
-       unsigned int active_query;
        /* flag to cache user preference for occlusion based selection */
        bool use_gpu_select;
-       /* cache on initialization */
-       unsigned int *buffer;
-       /* buffer size (stores number of integers, for actual size multiply by sizeof integer)*/
-       unsigned int bufsize;
        /* mode of operation */
        char mode;
-       unsigned int index;
-       int oldhits;
-} GPUQueryState;
+       /* internal algorithm for selection */
+       char algorithm;
+       /* allow GPU_select_begin/end without drawing */
+       bool use_cache;
+} GPUSelectState;
 
-static GPUQueryState g_query_state = {0};
+static GPUSelectState g_select_state = {0};
 
 /**
  * initialize and provide buffer for results
  */
 void GPU_select_begin(unsigned int *buffer, unsigned int bufsize, const rcti *input, char mode, int oldhits)
 {
-       g_query_state.select_is_active = true;
-       g_query_state.query_issued = false;
-       g_query_state.active_query = 0;
-       g_query_state.use_gpu_select = GPU_select_query_check_active();
-       g_query_state.num_of_queries = 0;
-       g_query_state.bufsize = bufsize;
-       g_query_state.buffer = buffer;
-       g_query_state.mode = mode;
-       g_query_state.index = 0;
-       g_query_state.oldhits = oldhits;
+       g_select_state.select_is_active = true;
+       g_select_state.use_gpu_select = GPU_select_query_check_active();
+       g_select_state.mode = mode;
 
-       if (!g_query_state.use_gpu_select) {
-               glSelectBuffer(bufsize, (GLuint *)buffer);
-               glRenderMode(GL_SELECT);
-               glInitNames();
-               glPushName(-1);
+       if (ELEM(g_select_state.mode, GPU_SELECT_PICK_ALL, GPU_SELECT_PICK_NEAREST)) {
+               g_select_state.algorithm = ALGO_GL_PICK;
+       }
+       else if (!g_select_state.use_gpu_select) {
+               g_select_state.algorithm = ALGO_GL_LEGACY;
        }
        else {
-               float viewport[4];
-
-               g_query_state.num_of_queries = ALLOC_QUERIES;
-
-               g_query_state.queries = MEM_mallocN(g_query_state.num_of_queries * sizeof(*g_query_state.queries), "gpu selection queries");
-               g_query_state.id = MEM_mallocN(g_query_state.num_of_queries * sizeof(*g_query_state.id), "gpu selection ids");
-               glGenQueries(g_query_state.num_of_queries, g_query_state.queries);
-
-               glPushAttrib(GL_DEPTH_BUFFER_BIT | GL_VIEWPORT_BIT);
-               /* disable writing to the framebuffer */
-               glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE);
-
-               /* In order to save some fill rate we minimize the viewport using rect.
-                * We need to get the region of the scissor so that our geometry doesn't
-                * get rejected before the depth test. Should probably cull rect against
-                * scissor for viewport but this is a rare case I think */
-               glGetFloatv(GL_SCISSOR_BOX, viewport);
-               glViewport(viewport[0], viewport[1], BLI_rcti_size_x(input), BLI_rcti_size_y(input));
+               g_select_state.algorithm = ALGO_GL_QUERY;
+       }
 
-               /* occlusion queries operates on fragments that pass tests and since we are interested on all
-                * objects in the view frustum independently of their order, we need to disable the depth test */
-               if (mode == GPU_SELECT_ALL) {
-                       glDisable(GL_DEPTH_TEST);
-                       glDepthMask(GL_FALSE);
+       switch (g_select_state.algorithm) {
+               case ALGO_GL_LEGACY:
+               {
+                       g_select_state.use_cache = false;
+                       glSelectBuffer(bufsize, (GLuint *)buffer);
+                       glRenderMode(GL_SELECT);
+                       glInitNames();
+                       glPushName(-1);
+                       break;
                }
-               else if (mode == GPU_SELECT_NEAREST_FIRST_PASS) {
-                       glClear(GL_DEPTH_BUFFER_BIT);
-                       glEnable(GL_DEPTH_TEST);
-                       glDepthMask(GL_TRUE);
-                       glDepthFunc(GL_LEQUAL);
+               case ALGO_GL_QUERY:
+               {
+                       g_select_state.use_cache = false;
+                       gpu_select_query_begin((unsigned int (*)[4])buffer, bufsize / 4, input, mode, oldhits);
+                       break;
                }
-               else if (mode == GPU_SELECT_NEAREST_SECOND_PASS) {
-                       glEnable(GL_DEPTH_TEST);
-                       glDepthMask(GL_FALSE);
-                       glDepthFunc(GL_EQUAL);
+               default:  /* ALGO_GL_PICK */
+               {
+                       gpu_select_pick_begin((unsigned int (*)[4])buffer, bufsize / 4, input, mode);
+                       break;
                }
        }
 }
@@ -143,41 +123,24 @@ void GPU_select_begin(unsigned int *buffer, unsigned int bufsize, const rcti *in
 bool GPU_select_load_id(unsigned int id)
 {
        /* if no selection mode active, ignore */
-       if (!g_query_state.select_is_active)
+       if (!g_select_state.select_is_active)
                return true;
 
-       if (!g_query_state.use_gpu_select) {
-               glLoadName(id);
-       }
-       else {
-               if (g_query_state.query_issued) {
-                       glEndQuery(GL_SAMPLES_PASSED);
+       switch (g_select_state.algorithm) {
+               case ALGO_GL_LEGACY:
+               {
+                       glLoadName(id);
+                       return true;
                }
-               /* if required, allocate extra queries */
-               if (g_query_state.active_query == g_query_state.num_of_queries) {
-                       g_query_state.num_of_queries += ALLOC_QUERIES;
-                       g_query_state.queries = MEM_reallocN(g_query_state.queries, g_query_state.num_of_queries * sizeof(*g_query_state.queries));
-                       g_query_state.id = MEM_reallocN(g_query_state.id, g_query_state.num_of_queries * sizeof(*g_query_state.id));
-                       glGenQueries(ALLOC_QUERIES, &g_query_state.queries[g_query_state.active_query]);
+               case ALGO_GL_QUERY:
+               {
+                       return gpu_select_query_load_id(id);
                }
-
-               glBeginQuery(GL_SAMPLES_PASSED, g_query_state.queries[g_query_state.active_query]);
-               g_query_state.id[g_query_state.active_query] = id;
-               g_query_state.active_query++;
-               g_query_state.query_issued = true;
-
-               if (g_query_state.mode == GPU_SELECT_NEAREST_SECOND_PASS && g_query_state.index < g_query_state.oldhits) {
-                       if (g_query_state.buffer[g_query_state.index * 4 + 3] == id) {
-                               g_query_state.index++;
-                               return true;
-                       }
-                       else {
-                               return false;
-                       }
+               default:  /* ALGO_GL_PICK */
+               {
+                       return gpu_select_pick_load_id(id);
                }
        }
-
-       return true;
 }
 
 /**
@@ -188,59 +151,27 @@ bool GPU_select_load_id(unsigned int id)
 unsigned int GPU_select_end(void)
 {
        unsigned int hits = 0;
-       if (!g_query_state.use_gpu_select) {
-               glPopName();
-               hits = glRenderMode(GL_RENDER);
-       }
-       else {
-               int i;
 
-               if (g_query_state.query_issued) {
-                       glEndQuery(GL_SAMPLES_PASSED);
+       switch (g_select_state.algorithm) {
+               case ALGO_GL_LEGACY:
+               {
+                       glPopName();
+                       hits = glRenderMode(GL_RENDER);
+                       break;
                }
-
-               for (i = 0; i < g_query_state.active_query; i++) {
-                       unsigned int result;
-                       glGetQueryObjectuiv(g_query_state.queries[i], GL_QUERY_RESULT, &result);
-                       if (result > 0) {
-                               if (g_query_state.mode != GPU_SELECT_NEAREST_SECOND_PASS) {
-                                       int maxhits = g_query_state.bufsize / 4;
-
-                                       if (hits < maxhits) {
-                                               g_query_state.buffer[hits * 4] = 1;
-                                               g_query_state.buffer[hits * 4 + 1] = 0xFFFF;
-                                               g_query_state.buffer[hits * 4 + 2] = 0xFFFF;
-                                               g_query_state.buffer[hits * 4 + 3] = g_query_state.id[i];
-
-                                               hits++;
-                                       }
-                                       else {
-                                               hits = -1;
-                                               break;
-                                       }
-                               }
-                               else {
-                                       int j;
-                                       /* search in buffer and make selected object first */
-                                       for (j = 0; j < g_query_state.oldhits; j++) {
-                                               if (g_query_state.buffer[j * 4 + 3] == g_query_state.id[i]) {
-                                                       g_query_state.buffer[j * 4 + 1] = 0;
-                                                       g_query_state.buffer[j * 4 + 2] = 0;
-                                               }
-                                       }
-                                       break;
-                               }
-                       }
+               case ALGO_GL_QUERY:
+               {
+                       hits = gpu_select_query_end();
+                       break;
+               }
+               default:  /* ALGO_GL_PICK */
+               {
+                       hits = gpu_select_pick_end();
+                       break;
                }
-
-               glDeleteQueries(g_query_state.num_of_queries, g_query_state.queries);
-               MEM_freeN(g_query_state.queries);
-               MEM_freeN(g_query_state.id);
-               glPopAttrib();
-               glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE);
        }
 
-       g_query_state.select_is_active = false;
+       g_select_state.select_is_active = false;
 
        return hits;
 }
@@ -257,3 +188,41 @@ bool GPU_select_query_check_active(void)
                  GPU_type_matches(GPU_DEVICE_NVIDIA, GPU_OS_UNIX, GPU_DRIVER_OPENSOURCE))));
 
 }
+
+/* ----------------------------------------------------------------------------
+ * Caching
+ *
+ * Support multiple begin/end's as long as they are within the initial region.
+ * Currently only used by ALGO_GL_PICK.
+ */
+
+void GPU_select_cache_begin(void)
+{
+       /* validate on GPU_select_begin, clear if not supported */
+       BLI_assert(g_select_state.use_cache == false);
+       g_select_state.use_cache = true;
+       if (g_select_state.algorithm == ALGO_GL_PICK) {
+               gpu_select_pick_cache_begin();
+       }
+}
+
+void GPU_select_cache_load_id(void)
+{
+       BLI_assert(g_select_state.use_cache == true);
+       if (g_select_state.algorithm == ALGO_GL_PICK) {
+               gpu_select_pick_cache_load_id();
+       }
+}
+
+void GPU_select_cache_end(void)
+{
+       if (g_select_state.algorithm == ALGO_GL_PICK) {
+               gpu_select_pick_cache_end();
+       }
+       g_select_state.use_cache = false;
+}
+
+bool GPU_select_is_cached(void)
+{
+       return g_select_state.use_cache && gpu_select_pick_is_cached();
+}
diff --git a/source/blender/gpu/intern/gpu_select_pick.c b/source/blender/gpu/intern/gpu_select_pick.c
new file mode 100644 (file)
index 0000000..31f82fd
--- /dev/null
@@ -0,0 +1,718 @@
+/*
+ * ***** 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) 2017 Blender Foundation.
+ * All rights reserved.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/gpu/intern/gpu_select_pick.c
+ *  \ingroup gpu
+ *
+ * Custom select code for picking small regions (not efficient for large regions).
+ * `gpu_select_pick_*` API.
+ */
+#include <string.h>
+#include <stdlib.h>
+#include <float.h>
+
+#include "GPU_select.h"
+#include "GPU_extensions.h"
+#include "GPU_glew.h"
+#include "MEM_guardedalloc.h"
+
+#include "BLI_rect.h"
+#include "BLI_listbase.h"
+#include "BLI_math_vector.h"
+#include "BLI_utildefines.h"
+
+#include "gpu_select_private.h"
+
+/* #define DEBUG_PRINT */
+
+/* Alloc number for depths */
+#define ALLOC_DEPTHS 200
+
+/* Z-depth of cleared depth buffer */
+#define DEPTH_MAX 0xffffffff
+
+/* ----------------------------------------------------------------------------
+ * SubRectStride
+ */
+
+/* For looping over a sub-region of a rect, could be moved into 'rct.c'*/
+typedef struct SubRectStride {
+       unsigned int start;     /* start here */
+       unsigned int span;      /* read these */
+       unsigned int span_len;  /* len times (read span 'len' times). */
+       unsigned int skip;      /* skip those */
+} SubRectStride;
+
+/* we may want to change back to float if uint isn't well supported */
+typedef unsigned int depth_t;
+
+/**
+ * Calculate values needed for looping over a sub-region (smaller buffer within a larger buffer).
+ *
+ * 'src' must be bigger than 'dst'.
+ */
+static void rect_subregion_stride_calc(const rcti *src, const rcti *dst, SubRectStride *r_sub)
+{
+       const int src_x = BLI_rcti_size_x(src);
+       // const int src_y = BLI_rcti_size_y(src);
+       const int dst_x = BLI_rcti_size_x(dst);
+       const int dst_y = BLI_rcti_size_y(dst);
+       const int x = dst->xmin - src->xmin;
+       const int y = dst->ymin - src->ymin;
+
+       BLI_assert(src->xmin <= dst->xmin && src->ymin <= dst->ymin &&
+                  src->ymax >= dst->ymax && src->ymax >= dst->ymax);
+       BLI_assert(x >= 0 && y >= 0);
+
+       r_sub->start = (src_x * y) + x;
+       r_sub->span = dst_x;
+       r_sub->span_len = dst_y;
+       r_sub->skip = src_x - dst_x;
+}
+
+/* ----------------------------------------------------------------------------
+ * DepthBufCache
+ *
+ * Result of reading glReadPixels,
+ * use for both cache and non-cached storage.
+ */
+
+/* store result of glReadPixels */
+typedef struct DepthBufCache {
+       struct DepthBufCache *next, *prev;
+       unsigned int id;
+       depth_t buf[0];
+} DepthBufCache;
+
+static DepthBufCache *depth_buf_malloc(unsigned int rect_len)
+{
+       DepthBufCache *rect = MEM_mallocN(sizeof(DepthBufCache) + sizeof(depth_t) * rect_len, __func__);
+       rect->id = SELECT_ID_NONE;
+       return rect;
+}
+
+static bool depth_buf_rect_depth_any(
+        const DepthBufCache *rect_depth,
+        unsigned int rect_len)
+{
+       const depth_t *curr = rect_depth->buf;
+       for (unsigned int i = 0; i < rect_len; i++, curr++) {
+               if (*curr != DEPTH_MAX) {
+                       return true;
+               }
+       }
+       return false;
+}
+
+static bool depth_buf_subrect_depth_any(
+        const DepthBufCache *rect_depth,
+        const SubRectStride *sub_rect)
+{
+       const depth_t *curr = rect_depth->buf + sub_rect->start;
+       for (unsigned int i = 0; i < sub_rect->span_len; i++) {
+               const depth_t *curr_end = curr + sub_rect->span;
+               for (; curr < curr_end; curr++, curr++) {
+                       if (*curr != DEPTH_MAX) {
+                               return true;
+                       }
+               }
+               curr += sub_rect->skip;
+       }
+       return false;
+}
+
+static bool depth_buf_rect_not_equal(
+        const DepthBufCache *rect_depth_a, const DepthBufCache *rect_depth_b,
+        unsigned int rect_len)
+{
+       return memcmp(rect_depth_a->buf, rect_depth_b->buf, rect_len * sizeof(depth_t)) != 0;
+}
+
+/**
+ * Both buffers are the same size, just check if the sub-rect contains any differences.
+ */
+static bool depth_buf_subrect_not_equal(
+        const DepthBufCache *rect_src, const DepthBufCache *rect_dst,
+        const SubRectStride *sub_rect)
+{
+       /* same as above but different rect sizes */
+       const depth_t *prev = rect_src->buf + sub_rect->start;
+       const depth_t *curr = rect_dst->buf + sub_rect->start;
+       for (unsigned int i = 0; i < sub_rect->span_len; i++) {
+               const depth_t *curr_end = curr + sub_rect->span;
+               for (; curr < curr_end; prev++, curr++) {
+                       if (*prev != *curr) {
+                               return true;
+                       }
+               }
+               prev += sub_rect->skip;
+               curr += sub_rect->skip;
+       }
+       return false;
+}
+
+/* ----------------------------------------------------------------------------
+ * DepthID
+ *
+ * Internal structure for storing hits.
+ */
+
+typedef struct DepthID {
+       unsigned int id;
+       depth_t depth;
+} DepthID;
+
+static int depth_id_cmp(const void *v1, const void *v2)
+{
+       const DepthID *d1 = v1, *d2 = v2;
+       if (d1->id < d2->id) {
+               return -1;
+       }
+       else if (d1->id > d2->id) {
+               return 1;
+       }
+       else {
+               return 0;
+       }
+}
+
+static int depth_cmp(const void *v1, const void *v2)
+{
+       const DepthID *d1 = v1, *d2 = v2;
+       if (d1->depth < d2->depth) {
+               return -1;
+       }
+       else if (d1->depth > d2->depth) {
+               return 1;
+       }
+       else {
+               return 0;
+       }
+}
+
+/* depth sorting */
+typedef struct GPUPickState {
+       /* cache on initialization */
+       unsigned int (*buffer)[4];
+
+       /* buffer size (stores number of integers, for actual size multiply by sizeof integer)*/
+       unsigned int bufsize;
+       /* mode of operation */
+       char mode;
+
+       /* OpenGL drawing, never use when (is_cached == true). */
+       struct {
+               /* The current depth, accumulated as we draw */
+               DepthBufCache *rect_depth;
+               /* Scratch buffer, avoid allocs every time (when not caching) */
+               DepthBufCache *rect_depth_test;
+
+               /* Pass to glReadPixels (x, y, w, h) */
+               int clip_readpixels[4];
+
+               /* Set after first draw */
+               bool is_init;
+               unsigned int prev_id;
+       } gl;
+
+       /* src: data stored in 'cache' and 'gl',
+        * dst: use when cached region is smaller (where src -> dst isn't 1:1) */
+       struct {
+               rcti clip_rect;
+               unsigned int rect_len;
+       } src, dst;
+
+       /* Store cache between `GPU_select_cache_begin/end` */
+       bool use_cache;
+       bool is_cached;
+       struct {
+               /* Cleanup used for iterating over both source and destination buffers:
+                * src.clip_rect -> dst.clip_rect */
+               SubRectStride sub_rect;
+
+               /* List of DepthBufCache, sized of 'src.clip_rect' */
+               ListBase bufs;
+       } cache;
+
+       /* Pickign methods */
+       union {
+               /* GPU_SELECT_PICK_ALL */
+               struct {
+                       DepthID *hits;
+                       unsigned int hits_len;
+                       unsigned int hits_len_alloc;
+               } all;
+
+               /* GPU_SELECT_PICK_NEAREST */
+               struct {
+                       unsigned int *rect_id;
+               } nearest;
+       };
+} GPUPickState;
+
+
+static GPUPickState g_pick_state = {0};
+
+void gpu_select_pick_begin(
+        unsigned int (*buffer)[4], unsigned int bufsize,
+        const rcti *input, char mode)
+{
+       GPUPickState *ps = &g_pick_state;
+
+#ifdef DEBUG_PRINT
+       printf("%s: mode=%d, use_cache=%d, is_cache=%d\n", __func__, mode, ps->use_cache, ps->is_cached);
+#endif
+
+       ps->bufsize = bufsize;
+       ps->buffer = buffer;
+       ps->mode = mode;
+
+       const unsigned int rect_len = BLI_rcti_size_x(input) * BLI_rcti_size_y(input);
+       ps->dst.clip_rect = *input;
+       ps->dst.rect_len = rect_len;
+
+       /* Restrict OpenGL operations for when we don't have cache */
+       if (ps->is_cached == false) {
+
+               glPushAttrib(GL_DEPTH_BUFFER_BIT | GL_VIEWPORT_BIT);
+               /* disable writing to the framebuffer */
+               glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE);
+
+               glEnable(GL_DEPTH_TEST);
+               glDepthMask(GL_TRUE);
+
+               if (mode == GPU_SELECT_PICK_ALL) {
+                       glDepthFunc(GL_ALWAYS);
+               }
+               else {
+                       glDepthFunc(GL_LEQUAL);
+               }
+
+               glPixelTransferi(GL_DEPTH_BIAS, 0.0);
+               glPixelTransferi(GL_DEPTH_SCALE, 1.0);
+
+
+               float viewport[4];
+               glGetFloatv(GL_SCISSOR_BOX, viewport);
+
+               ps->src.clip_rect = *input;
+               ps->src.rect_len = rect_len;
+
+               ps->gl.clip_readpixels[0] = viewport[0];
+               ps->gl.clip_readpixels[1] = viewport[1];
+               ps->gl.clip_readpixels[2] = BLI_rcti_size_x(&ps->src.clip_rect);
+               ps->gl.clip_readpixels[3] = BLI_rcti_size_y(&ps->src.clip_rect);
+
+               glViewport(UNPACK4(ps->gl.clip_readpixels));
+
+               /* It's possible we don't want to clear depth buffer,
+                * so existing elements are masked by current z-buffer. */
+               glClear(GL_DEPTH_BUFFER_BIT);
+
+               /* scratch buffer (read new values here) */
+               ps->gl.rect_depth_test = depth_buf_malloc(rect_len);
+               ps->gl.rect_depth = depth_buf_malloc(rect_len);
+
+               /* set initial 'far' value */
+#if 0
+               glReadPixels(UNPACK4(ps->gl.clip_readpixels), GL_DEPTH_COMPONENT, GL_UNSIGNED_INT, ps->gl.rect_depth->buf);
+#else
+               for (unsigned int i = 0; i < rect_len; i++) {
+                       ps->gl.rect_depth->buf[i] = DEPTH_MAX;
+               }
+#endif
+
+               ps->gl.is_init = false;
+               ps->gl.prev_id = 0;
+       }
+       else {
+               /* Using cache (ps->is_cached == true) */
+               /* src.clip_rect -> dst.clip_rect */
+               rect_subregion_stride_calc(&ps->src.clip_rect, &ps->dst.clip_rect, &ps->cache.sub_rect);
+               BLI_assert(ps->gl.rect_depth == NULL);
+               BLI_assert(ps->gl.rect_depth_test == NULL);
+       }
+
+       if (mode == GPU_SELECT_PICK_ALL) {
+               ps->all.hits = MEM_mallocN(sizeof(*ps->all.hits) * ALLOC_DEPTHS, __func__);
+               ps->all.hits_len = 0;
+               ps->all.hits_len_alloc = ALLOC_DEPTHS;
+       }
+       else {
+               /* Set to 0xff for SELECT_ID_NONE */
+               ps->nearest.rect_id = MEM_mallocN(sizeof(unsigned int) * ps->dst.rect_len, __func__);
+               memset(ps->nearest.rect_id, 0xff, sizeof(unsigned int) * ps->dst.rect_len);
+       }
+}
+
+/**
+ * Given 2x depths, we know are different - update the depth information
+ * use for both cached/uncached depth buffers.
+ */
+static void gpu_select_load_id_pass_all(const DepthBufCache *rect_curr)
+{
+       GPUPickState *ps = &g_pick_state;
+       const unsigned int id = rect_curr->id;
+       /* find the best depth for this pass and store in 'all.hits' */
+       depth_t depth_best = DEPTH_MAX;
+
+#define EVAL_TEST() \
+       if (depth_best > *curr) { \
+               depth_best = *curr; \
+       } ((void)0)
+
+       if (ps->is_cached == false) {
+               const depth_t *curr = rect_curr->buf;
+               BLI_assert(ps->src.rect_len == ps->dst.rect_len);
+               const unsigned int rect_len = ps->src.rect_len;
+               for (unsigned int i = 0; i < rect_len; i++, curr++) {
+                       EVAL_TEST();
+               }
+       }
+       else {
+               /* same as above but different rect sizes */
+               const depth_t *curr = rect_curr->buf + ps->cache.sub_rect.start;
+               for (unsigned int i = 0; i < ps->cache.sub_rect.span_len; i++) {
+                       const depth_t *curr_end = curr + ps->cache.sub_rect.span;
+                       for (; curr < curr_end; curr++) {
+                               EVAL_TEST();
+                       }
+                       curr += ps->cache.sub_rect.skip;
+               }
+       }
+
+#undef EVAL_TEST
+
+       /* ensure enough space */
+       if (UNLIKELY(ps->all.hits_len == ps->all.hits_len_alloc)) {
+               ps->all.hits_len_alloc += ALLOC_DEPTHS;
+               ps->all.hits = MEM_reallocN(ps->all.hits, ps->all.hits_len_alloc * sizeof(*ps->all.hits));
+       }
+       DepthID *d = &ps->all.hits[ps->all.hits_len++];
+       d->id = id;
+       d->depth = depth_best;
+}
+
+static void gpu_select_load_id_pass_nearest(const DepthBufCache *rect_prev, const DepthBufCache *rect_curr)
+{
+       GPUPickState *ps = &g_pick_state;
+       const unsigned int id = rect_curr->id;
+       /* keep track each pixels ID in 'nearest.rect_id' */
+       if (id != SELECT_ID_NONE) {
+               unsigned int *id_ptr = ps->nearest.rect_id;
+
+#define EVAL_TEST() \
+               if (*curr != *prev) { \
+                       *id_ptr = id; \
+               } ((void)0)
+
+               if (ps->is_cached == false) {
+                       const depth_t *prev = rect_prev->buf;
+                       const depth_t *curr = rect_curr->buf;
+                       BLI_assert(ps->src.rect_len == ps->dst.rect_len);
+                       const unsigned int rect_len = ps->src.rect_len;
+                       for (unsigned int i = 0; i < rect_len; i++, curr++, prev++, id_ptr++) {
+                               EVAL_TEST();
+                       }
+               }
+               else {
+                       /* same as above but different rect sizes */
+                       const depth_t *prev = rect_prev->buf + ps->cache.sub_rect.start;
+                       const depth_t *curr = rect_curr->buf + ps->cache.sub_rect.start;
+                       for (unsigned int i = 0; i < ps->cache.sub_rect.span_len; i++) {
+                               const depth_t *curr_end = curr + ps->cache.sub_rect.span;
+                               for (; curr < curr_end; prev++, curr++, id_ptr++) {
+                                       EVAL_TEST();
+                               }
+                               prev += ps->cache.sub_rect.skip;
+                               curr += ps->cache.sub_rect.skip;
+                       }
+               }
+
+#undef EVAL_TEST
+       }
+}
+
+
+bool gpu_select_pick_load_id(unsigned int id)
+{
+       GPUPickState *ps = &g_pick_state;
+       if (ps->gl.is_init) {
+               const unsigned int rect_len = ps->src.rect_len;
+               glReadPixels(UNPACK4(ps->gl.clip_readpixels), GL_DEPTH_COMPONENT, GL_UNSIGNED_INT, ps->gl.rect_depth_test->buf);
+               /* perform initial check since most cases the array remains unchanged  */
+
+               bool do_pass = false;
+               if (g_pick_state.mode == GPU_SELECT_PICK_ALL) {
+                       if (depth_buf_rect_depth_any(ps->gl.rect_depth_test, rect_len)) {
+                               ps->gl.rect_depth_test->id = ps->gl.prev_id;
+                               gpu_select_load_id_pass_all(ps->gl.rect_depth_test);
+                               do_pass = true;
+                       }
+               }
+               else {
+                       if (depth_buf_rect_not_equal(ps->gl.rect_depth, ps->gl.rect_depth_test, rect_len)) {
+                               ps->gl.rect_depth_test->id = ps->gl.prev_id;
+                               gpu_select_load_id_pass_nearest(ps->gl.rect_depth, ps->gl.rect_depth_test);
+                               do_pass = true;
+                       }
+               }
+
+               if (do_pass) {
+                       /* Store depth in cache */
+                       if (ps->use_cache) {
+                               BLI_addtail(&ps->cache.bufs, ps->gl.rect_depth);
+                               ps->gl.rect_depth = depth_buf_malloc(ps->src.rect_len);
+                       }
+
+                       SWAP(DepthBufCache *, ps->gl.rect_depth, ps->gl.rect_depth_test);
+
+                       if (g_pick_state.mode == GPU_SELECT_PICK_ALL) {
+                               /* we want new depths every time */
+                               glClear(GL_DEPTH_BUFFER_BIT);
+                       }
+               }
+       }
+
+       ps->gl.is_init = true;
+       ps->gl.prev_id = id;
+
+       return true;
+}
+
+unsigned int gpu_select_pick_end(void)
+{
+       GPUPickState *ps = &g_pick_state;
+
+#ifdef DEBUG_PRINT
+       printf("%s\n", __func__);
+#endif
+
+       if (ps->is_cached == false) {
+               if (ps->gl.is_init) {
+                       /* force finishing last pass */
+                       gpu_select_pick_load_id(ps->gl.prev_id);
+               }
+
+               glPopAttrib();
+               glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE);
+       }
+
+       /* assign but never free directly since it may be in cache */
+       DepthBufCache *rect_depth_final;
+
+       /* Store depth in cache */
+       if (ps->use_cache && !ps->is_cached) {
+               BLI_addtail(&ps->cache.bufs, ps->gl.rect_depth);
+               ps->gl.rect_depth = NULL;
+               rect_depth_final = ps->cache.bufs.last;
+       }
+       else if (ps->is_cached) {
+               rect_depth_final = ps->cache.bufs.last;
+       }
+       else {
+               /* common case, no cache */
+               rect_depth_final = ps->gl.rect_depth;
+       }
+
+       unsigned int maxhits = g_pick_state.bufsize;
+       DepthID *depth_data;
+       unsigned int depth_data_len = 0;
+
+       if (g_pick_state.mode == GPU_SELECT_PICK_ALL) {
+               depth_data = ps->all.hits;
+               depth_data_len = ps->all.hits_len;
+               /* move ownership */
+               ps->all.hits = NULL;
+               ps->all.hits_len = 0;
+               ps->all.hits_len_alloc = 0;
+       }
+       else {
+               /* GPU_SELECT_PICK_NEAREST */
+
+               /* Over alloc (unlikely we have as many depths as pixels) */
+               unsigned int depth_data_len_first_pass = 0;
+               depth_data = MEM_mallocN(ps->dst.rect_len * sizeof(*depth_data), __func__);
+
+               /* Partially de-duplicating copy,
+                * when contiguous ID's are found - update their closest depth.
+                * This isn't essential but means there is less data to sort. */
+
+#define EVAL_TEST(i_src, i_dst) \
+               { \
+                       const unsigned int id = ps->nearest.rect_id[i_dst]; \
+                       if (id != SELECT_ID_NONE) { \
+                               const depth_t depth = rect_depth_final->buf[i_src]; \
+                               if (depth_last == NULL || depth_last->id != id) { \
+                                       DepthID *d = &depth_data[depth_data_len_first_pass++]; \
+                                       d->id = id; \
+                                       d->depth = depth; \
+                               } \
+                               else if (depth_last->depth > depth) { \
+                                       depth_last->depth = depth; \
+                               } \
+                       } \
+               } ((void)0)
+
+               {
+                       DepthID *depth_last = NULL;
+                       if (ps->is_cached == false) {
+                               for (unsigned int i = 0; i < ps->src.rect_len; i++) {
+                                       EVAL_TEST(i, i);
+                               }
+                       }
+                       else {
+                               /* same as above but different rect sizes */
+                               unsigned int i_src = ps->cache.sub_rect.start, i_dst = 0;
+                               for (unsigned int j = 0; j < ps->cache.sub_rect.span_len; j++) {
+                                       const unsigned int i_src_end = i_src + ps->cache.sub_rect.span;
+                                       for (; i_src < i_src_end; i_src++, i_dst++) {
+                                               EVAL_TEST(i_src, i_dst);
+                                       }
+                                       i_src += ps->cache.sub_rect.skip;
+                               }
+                       }
+               }
+
+#undef EVAL_TEST
+
+               qsort(depth_data, depth_data_len_first_pass, sizeof(DepthID), depth_id_cmp);
+
+               /* Sort by ID's then keep the best depth for each ID */
+               depth_data_len = 0;
+               {
+                       DepthID *depth_last = NULL;
+                       for (unsigned int i = 0; i < depth_data_len_first_pass; i++) {
+                               if (depth_last == NULL || depth_last->id != depth_data[i].id) {
+                                       depth_last = &depth_data[depth_data_len++];
+                                       *depth_last = depth_data[i];
+                               }
+                               else if (depth_last->depth > depth_data[i].depth) {
+                                       depth_last->depth = depth_data[i].depth;
+                               }
+                       }
+               }
+       }
+
+       /* Finally sort each unique (id, depth) pair by depth
+        * so the final hit-list is sorted by depth (nearest first) */
+       unsigned int hits = 0;
+
+       if (depth_data_len > maxhits) {
+               hits = -1;
+       }
+       else {
+               qsort(depth_data, depth_data_len, sizeof(DepthID), depth_cmp);
+
+               for (unsigned int i = 0; i < depth_data_len; i++) {
+#ifdef DEBUG_PRINT
+                       printf("  hit: %d: depth %u\n", depth_data[i].id,  depth_data[i].depth);
+#endif
+                       /* first 3 are dummy values */
+                       g_pick_state.buffer[hits][0] = 1;
+                       g_pick_state.buffer[hits][1] = 0x0;
+                       g_pick_state.buffer[hits][2] = 0x0;
+                       g_pick_state.buffer[hits][3] = depth_data[i].id;
+                       hits++;
+               }
+               BLI_assert(hits < maxhits);
+       }
+
+       MEM_freeN(depth_data);
+
+       MEM_SAFE_FREE(ps->gl.rect_depth);
+       MEM_SAFE_FREE(ps->gl.rect_depth_test);
+
+       if (g_pick_state.mode == GPU_SELECT_PICK_ALL) {
+               /* 'hits' already freed as 'depth_data' */
+       }
+       else {
+               MEM_freeN(ps->nearest.rect_id);
+               ps->nearest.rect_id = NULL;
+       }
+
+       if (ps->use_cache) {
+               ps->is_cached = true;
+       }
+
+       return hits;
+}
+
+/* ----------------------------------------------------------------------------
+ * Caching
+ *
+ * Support multiple begin/end's reusing depth buffers.
+ */
+
+void gpu_select_pick_cache_begin(void)
+{
+       BLI_assert(g_pick_state.use_cache == false);
+#ifdef DEBUG_PRINT
+       printf("%s\n", __func__);
+#endif
+       g_pick_state.use_cache = true;
+       g_pick_state.is_cached = false;
+}
+
+void gpu_select_pick_cache_end(void)
+{
+#ifdef DEBUG_PRINT
+       printf("%s: with %d buffers\n", __func__, BLI_listbase_count(&g_pick_state.cache.bufs));
+#endif
+       g_pick_state.use_cache = false;
+       g_pick_state.is_cached = false;
+
+       BLI_freelistN(&g_pick_state.cache.bufs);
+}
+
+/* is drawing needed? */
+bool gpu_select_pick_is_cached(void)
+{
+       return g_pick_state.is_cached;
+}
+
+void gpu_select_pick_cache_load_id(void)
+{
+       BLI_assert(g_pick_state.is_cached == true);
+       GPUPickState *ps = &g_pick_state;
+#ifdef DEBUG_PRINT
+       printf("%s (building depth from cache)\n", __func__);
+#endif
+       for (DepthBufCache *rect_depth = ps->cache.bufs.first; rect_depth; rect_depth = rect_depth->next) {
+               if (rect_depth->next != NULL) {
+                       /* we know the buffers differ, but this sub-region may not.
+                        * double check before adding an id-pass */
+                       if (g_pick_state.mode == GPU_SELECT_PICK_ALL) {
+                               if (depth_buf_subrect_depth_any(rect_depth->next, &ps->cache.sub_rect)) {
+                                       gpu_select_load_id_pass_all(rect_depth->next);
+                               }
+                       }
+                       else {
+                               if (depth_buf_subrect_not_equal(rect_depth, rect_depth->next, &ps->cache.sub_rect)) {
+                                       gpu_select_load_id_pass_nearest(rect_depth, rect_depth->next);
+                               }
+                       }
+               }
+       }
+}
diff --git a/source/blender/gpu/intern/gpu_select_private.h b/source/blender/gpu/intern/gpu_select_private.h
new file mode 100644 (file)
index 0000000..631b880
--- /dev/null
@@ -0,0 +1,48 @@
+/*
+ * ***** 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) 2014 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): Antony Riakiotakis.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/gpu/intern/gpu_select_private.h
+ *  \ingroup gpu
+ *
+ * Selection implementations.
+ */
+
+/* gpu_select_pick */
+void gpu_select_pick_begin(unsigned int (*buffer)[4], unsigned int bufsize, const rcti *input, char mode);
+bool gpu_select_pick_load_id(unsigned int id);
+unsigned int gpu_select_pick_end(void);
+
+void gpu_select_pick_cache_begin(void);
+void gpu_select_pick_cache_end(void);
+bool gpu_select_pick_is_cached(void);
+void gpu_select_pick_cache_load_id(void);
+
+/* gpu_select_sample_query */
+void gpu_select_query_begin(unsigned int (*buffer)[4], unsigned int bufsize, const rcti *input, char mode, int oldhits);
+bool gpu_select_query_load_id(unsigned int id);
+unsigned int gpu_select_query_end(void);
+
+
+#define SELECT_ID_NONE ((unsigned int)0xffffffff)
diff --git a/source/blender/gpu/intern/gpu_select_sample_query.c b/source/blender/gpu/intern/gpu_select_sample_query.c
new file mode 100644 (file)
index 0000000..5576367
--- /dev/null
@@ -0,0 +1,209 @@
+/*
+ * ***** 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) 2014 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): Antony Riakiotakis.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/gpu/intern/gpu_select.c
+ *  \ingroup gpu
+ *
+ * Interface for accessing gpu-related methods for selection. The semantics will be
+ * similar to glRenderMode(GL_SELECT) since the goal is to maintain compatibility.
+ */
+
+#include <stdlib.h>
+
+#include "GPU_select.h"
+#include "GPU_extensions.h"
+#include "GPU_glew.h"
+#include "MEM_guardedalloc.h"
+
+#include "BLI_rect.h"
+
+#include "BLI_utildefines.h"
+
+#include "gpu_select_private.h"
+
+
+/* Ad hoc number of queries to allocate to skip doing many glGenQueries */
+#define ALLOC_QUERIES 200
+
+typedef struct GPUQueryState {
+       /* Tracks whether a query has been issued so that gpu_load_id can end the previous one */
+       bool query_issued;
+       /* array holding the OpenGL query identifiers */
+       unsigned int *queries;
+       /* array holding the id corresponding to each query */
+       unsigned int *id;
+       /* number of queries in *queries and *id */
+       unsigned int num_of_queries;
+       /* index to the next query to start */
+       unsigned int active_query;
+       /* cache on initialization */
+       unsigned int (*buffer)[4];
+       /* buffer size (stores number of integers, for actual size multiply by sizeof integer)*/
+       unsigned int bufsize;
+       /* mode of operation */
+       char mode;
+       unsigned int index;
+       int oldhits;
+} GPUQueryState;
+
+static GPUQueryState g_query_state = {0};
+
+
+void gpu_select_query_begin(
+        unsigned int (*buffer)[4], unsigned int bufsize,
+        const rcti *input, char mode,
+        int oldhits)
+{
+       float viewport[4];
+
+       g_query_state.query_issued = false;
+       g_query_state.active_query = 0;
+       g_query_state.num_of_queries = 0;
+       g_query_state.bufsize = bufsize;
+       g_query_state.buffer = buffer;
+       g_query_state.mode = mode;
+       g_query_state.index = 0;
+       g_query_state.oldhits = oldhits;
+
+       g_query_state.num_of_queries = ALLOC_QUERIES;
+
+       g_query_state.queries = MEM_mallocN(g_query_state.num_of_queries * sizeof(*g_query_state.queries), "gpu selection queries");
+       g_query_state.id = MEM_mallocN(g_query_state.num_of_queries * sizeof(*g_query_state.id), "gpu selection ids");
+       glGenQueries(g_query_state.num_of_queries, g_query_state.queries);
+
+       glPushAttrib(GL_DEPTH_BUFFER_BIT | GL_VIEWPORT_BIT);
+       /* disable writing to the framebuffer */
+       glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE);
+
+       /* In order to save some fill rate we minimize the viewport using rect.
+        * We need to get the region of the scissor so that our geometry doesn't
+        * get rejected before the depth test. Should probably cull rect against
+        * scissor for viewport but this is a rare case I think */
+       glGetFloatv(GL_SCISSOR_BOX, viewport);
+       glViewport(viewport[0], viewport[1], BLI_rcti_size_x(input), BLI_rcti_size_y(input));
+
+       /* occlusion queries operates on fragments that pass tests and since we are interested on all
+        * objects in the view frustum independently of their order, we need to disable the depth test */
+       if (mode == GPU_SELECT_ALL) {
+               glDisable(GL_DEPTH_TEST);
+               glDepthMask(GL_FALSE);
+       }
+       else if (mode == GPU_SELECT_NEAREST_FIRST_PASS) {
+               glClear(GL_DEPTH_BUFFER_BIT);
+               glEnable(GL_DEPTH_TEST);
+               glDepthMask(GL_TRUE);
+               glDepthFunc(GL_LEQUAL);
+       }
+       else if (mode == GPU_SELECT_NEAREST_SECOND_PASS) {
+               glEnable(GL_DEPTH_TEST);
+               glDepthMask(GL_FALSE);
+               glDepthFunc(GL_EQUAL);
+       }
+}
+
+bool gpu_select_query_load_id(unsigned int id)
+{
+       if (g_query_state.query_issued) {
+               glEndQuery(GL_SAMPLES_PASSED);
+       }
+       /* if required, allocate extra queries */
+       if (g_query_state.active_query == g_query_state.num_of_queries) {
+               g_query_state.num_of_queries += ALLOC_QUERIES;
+               g_query_state.queries = MEM_reallocN(g_query_state.queries, g_query_state.num_of_queries * sizeof(*g_query_state.queries));
+               g_query_state.id = MEM_reallocN(g_query_state.id, g_query_state.num_of_queries * sizeof(*g_query_state.id));
+               glGenQueries(ALLOC_QUERIES, &g_query_state.queries[g_query_state.active_query]);
+       }
+
+       glBeginQuery(GL_SAMPLES_PASSED, g_query_state.queries[g_query_state.active_query]);
+       g_query_state.id[g_query_state.active_query] = id;
+       g_query_state.active_query++;
+       g_query_state.query_issued = true;
+
+       if (g_query_state.mode == GPU_SELECT_NEAREST_SECOND_PASS && g_query_state.index < g_query_state.oldhits) {
+               if (g_query_state.buffer[g_query_state.index][3] == id) {
+                       g_query_state.index++;
+                       return true;
+               }
+               else {
+                       return false;
+               }
+       }
+
+       return true;
+}
+
+unsigned int gpu_select_query_end(void)
+{
+       int i;
+
+       unsigned int hits = 0;
+       const unsigned int maxhits = g_query_state.bufsize;
+
+       if (g_query_state.query_issued) {
+               glEndQuery(GL_SAMPLES_PASSED);
+       }
+
+       for (i = 0; i < g_query_state.active_query; i++) {
+               unsigned int result;
+               glGetQueryObjectuiv(g_query_state.queries[i], GL_QUERY_RESULT, &result);
+               if (result > 0) {
+                       if (g_query_state.mode != GPU_SELECT_NEAREST_SECOND_PASS) {
+
+                               if (hits < maxhits) {
+                                       g_query_state.buffer[hits][0] = 1;
+                                       g_query_state.buffer[hits][1] = 0xFFFF;
+                                       g_query_state.buffer[hits][2] = 0xFFFF;
+                                       g_query_state.buffer[hits][3] = g_query_state.id[i];
+
+                                       hits++;
+                               }
+                               else {
+                                       hits = -1;
+                                       break;
+                               }
+                       }
+                       else {
+                               int j;
+                               /* search in buffer and make selected object first */
+                               for (j = 0; j < g_query_state.oldhits; j++) {
+                                       if (g_query_state.buffer[j][3] == g_query_state.id[i]) {
+                                               g_query_state.buffer[j][1] = 0;
+                                               g_query_state.buffer[j][2] = 0;
+                                       }
+                               }
+                               break;
+                       }
+               }
+       }
+
+       glDeleteQueries(g_query_state.num_of_queries, g_query_state.queries);
+       MEM_freeN(g_query_state.queries);
+       MEM_freeN(g_query_state.id);
+       glPopAttrib();
+       glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE);
+
+       return hits;
+}
index 0ad4482708f51d9ec0324e932bfe4590402bbf22..73c341e35baa97e5b52f367d3ca3890f2bb5684b 100644 (file)
@@ -497,7 +497,6 @@ typedef struct UserDef {
        int prefetchframes;
        float pad_rot_angle; /* control the rotation step of the view when PAD2, PAD4, PAD6&PAD8 is use */
        short frameserverport;
-       short pad4;
        short obcenter_dia;
        short rvisize;                  /* rotating view icon size */
        short rvibright;                /* rotating view icon brightness */
@@ -509,6 +508,8 @@ typedef struct UserDef {
        char  ipo_new;                  /* interpolation mode for newly added F-Curves */
        char  keyhandles_new;   /* handle types for newly added keyframes */
        char  gpu_select_method;
+       char  gpu_select_pick_deph;
+       char  pad4;
        char  view_frame_type;
 
        int view_frame_keyframes; /* number of keyframes to zoom around current frame */
index e68e67586e9f7547715d1afed69efa48e498ec49..74888bf4f00ddb9a32264c640af78332405d4cdb 100644 (file)
@@ -4180,6 +4180,10 @@ static void rna_def_userdef_system(BlenderRNA *brna)
        RNA_def_property_ui_text(prop, "Selection Method",
                                 "Use OpenGL occlusion queries or selection render mode to accelerate selection");
 
+       prop = RNA_def_property(srna, "use_select_pick_depth", PROP_BOOLEAN, PROP_NONE);
+       RNA_def_property_boolean_sdna(prop, NULL, "gpu_select_pick_deph", 1);
+       RNA_def_property_ui_text(prop, "OpenGL Depth Picking", "Use the depth buffer for picking 3D View selection");
+
        /* Full scene anti-aliasing */
        prop = RNA_def_property(srna, "multi_sample", PROP_ENUM, PROP_NONE);
        RNA_def_property_enum_bitflag_sdna(prop, NULL, "ogl_multisamples");