[Bf-blender-cvs] [b96ab7a6b5] temp-select-pick: More efficient depth sorting

Campbell Barton noreply at git.blender.org
Mon Mar 6 08:41:44 CET 2017


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);




More information about the Bf-blender-cvs mailing list