Commit: b96ab7a6b587e7c96f2205129f7ca4b5a3ca80c0
Author: Campbell Barton
Date: Sat Mar 4 12:51:17 2017 +1100
Branches: temp-select-pick
https://developer.blender.org/rBb96ab7a6b587e7c96f2205129f7ca4b5a3ca80c0
More efficient depth sorting
===================================================================
M source/blender/gpu/intern/gpu_select.c
===================================================================
diff --git a/source/blender/gpu/intern/gpu_select.c
b/source/blender/gpu/intern/gpu_select.c
index 8e822504bb..a1f60ce181 100644
--- a/source/blender/gpu/intern/gpu_select.c
+++ b/source/blender/gpu/intern/gpu_select.c
@@ -53,7 +53,7 @@ typedef struct DepthID {
float depth;
} DepthID;
-static int id_depth_cmp(const void *v1, const void *v2)
+static int depth_id_cmp(const void *v1, const void *v2)
{
const DepthID *d1 = v1, *d2 = v2;
if (d1->id < d2->id) {
@@ -63,15 +63,7 @@ static int id_depth_cmp(const void *v1, const void *v2)
return 1;
}
else {
- if (d1->depth < d2->depth) {
- return -1;
- }
- else if (d1->depth > d2->depth) {
- return 1;
- }
- else {
- return 0;
- }
+ return 0;
}
}
@@ -330,32 +322,55 @@ unsigned int GPU_select_end(void)
unsigned int maxhits = g_query_state.bufsize / 4;
- DepthID *depth = MEM_mallocN(qsd->rect_len * sizeof(*depth),
__func__);
- /* unsigned int depth_last = 0; */
+ /* Over alloc (unlikely we have as many depths as pixels) */
+ DepthID *depth_data = MEM_mallocN(qsd->rect_len *
sizeof(*depth_data), __func__);
unsigned int depth_len = 0;
- for (unsigned int i = 0; i < qsd->rect_len; i++) {
- if (qsd->rect_id[i] != 0xffffffff) {
- DepthID *d = &depth[depth_len++];
- d->id = qsd->rect_id[i];
- d->depth = *((float *)&qsd->rect_depth[i]);
+
+ /* Partially de-duplicating copy,
+ * when contiguous ID's are found - update their closest depth.
+ * This isn't essential but means there is lest data to sort. */
+ {
+ DepthID *depth_last = NULL;
+ for (unsigned int i = 0; i < qsd->rect_len; i++) {
+ const unsigned int id = qsd->rect_id[i];
+ if (qsd->rect_id[i] != 0xffffffff) {
+ const float depth = *((float
*)&qsd->rect_depth[i]);
+ if (depth_last == NULL ||
depth_last->id != id) {
+ DepthID *d =
&depth_data[depth_len++];
+ d->id = id;
+ d->depth = depth;
+ } else if (depth_last->depth > depth) {
+ depth_last->depth = depth;
+ }
+ }
}
}
- qsort(depth, depth_len, sizeof(DepthID), id_depth_cmp);
- unsigned int id_last = 0xffffffff;
+
+ /* Sort by ID's then keep the best depth for each ID */
unsigned int depth_compact_len = 0;
- for (unsigned int i = 0; i < depth_len; i++) {
- if (depth[i].id != id_last) {
- id_last = depth[i].id;
- depth[depth_compact_len++] = depth[i];
+ {
+ qsort(depth_data, depth_len, sizeof(DepthID),
depth_id_cmp);
+ DepthID *depth_last = NULL;
+ for (unsigned int i = 0; i < depth_len; i++) {
+ if (depth_last == NULL || depth_last->id !=
depth_data[i].id) {
+ depth_last =
&depth_data[depth_compact_len++];
+ *depth_last = depth_data[i];
+ }
+ else if (depth_last->depth >
depth_data[i].depth) {
+ depth_last->depth = depth_data[i].depth;
+ }
}
}
- qsort(depth, depth_compact_len, sizeof(DepthID), depth_cmp);
+
+ /* Finally sort each unique (id, depth) pair by depth
+ * so the final hit-list is sorted by depth (nearest first) */
+ qsort(depth_data, depth_compact_len, sizeof(DepthID),
depth_cmp);
for (unsigned int i = 0; i < depth_compact_len; i++) {
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] =
depth[i].id;
+ g_query_state.buffer[hits * 4 + 3] =
depth_data[i].id;
hits++;
}
@@ -365,7 +380,7 @@ unsigned int GPU_select_end(void)
}
}
- MEM_freeN(depth);
+ MEM_freeN(depth_data);
MEM_freeN(qsd->rect_id);
MEM_freeN(qsd->rect_depth);
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
https://lists.blender.org/mailman/listinfo/bf-blender-cvs
