[Bf-blender-cvs] [6f00b1500cb] master: LineArt: Use array instead of lists for edges pending occusion query
YimingWu
noreply at git.blender.org
Wed May 18 09:35:26 CEST 2022
Commit: 6f00b1500cbd162dfe2fa7f8de2c46f156f75da4
Author: YimingWu
Date: Wed May 18 15:33:35 2022 +0800
Branches: master
https://developer.blender.org/rB6f00b1500cbd162dfe2fa7f8de2c46f156f75da4
LineArt: Use array instead of lists for edges pending occusion query
It turns out there's no practical use for separating different edge types
before final occlusion stage, also using an array should be faster overall.
So changed those lists into one pending array, it also made the
iteration and occlusion task scheduling simpler.
Reviewed By: Sebastian Parborg (zeddb)
Differential Revision: https://developer.blender.org/D14951
===================================================================
M source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
M source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
M source/blender/gpencil_modifiers/intern/lineart/lineart_intern.h
===================================================================
diff --git a/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h b/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
index 12c1e9cf563..06738ef6a12 100644
--- a/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
+++ b/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
@@ -204,6 +204,12 @@ enum eLineArtTileRecursiveLimit {
#define LRT_TILE_SPLITTING_TRIANGLE_LIMIT 100
#define LRT_TILE_EDGE_COUNT_INITIAL 32
+typedef struct LineartPendingEdges {
+ LineartEdge **array;
+ int max;
+ int next;
+} LineartPendingEdges;
+
typedef struct LineartRenderBuffer {
struct LineartRenderBuffer *prev, *next;
@@ -248,15 +254,9 @@ typedef struct LineartRenderBuffer {
int triangle_size;
- /* Although using ListBase here, LineartEdge is single linked list.
- * list.last is used to store worker progress along the list.
- * See lineart_main_occlusion_begin() for more info. */
- ListBase contour;
- ListBase intersection;
- ListBase crease;
- ListBase material;
- ListBase edge_mark;
- ListBase floating;
+ /* Note: Data inside #pending_edges are allocated with MEM_xxx call instead of in pool. */
+ struct LineartPendingEdges pending_edges;
+ int scheduled_count;
ListBase chains;
@@ -362,14 +362,9 @@ typedef struct LineartRenderTaskInfo {
int thread_id;
- /* These lists only denote the part of the main edge list that the thread should iterate over.
- * Be careful to not iterate outside of these bounds as it is not thread safe to do so. */
- ListBase contour;
- ListBase intersection;
- ListBase crease;
- ListBase material;
- ListBase edge_mark;
- ListBase floating;
+ /* #pending_edges here only stores a refernce to a portion in LineartRenderbuffer::pending_edges,
+ * assigned by the occlusion scheduler. */
+ struct LineartPendingEdges pending_edges;
} LineartRenderTaskInfo;
@@ -387,14 +382,8 @@ typedef struct LineartObjectInfo {
bool free_use_mesh;
- /* Threads will add lines inside here, when all threads are done, we combine those into the
- * ones in LineartRenderBuffer. */
- ListBase contour;
- ListBase intersection;
- ListBase crease;
- ListBase material;
- ListBase edge_mark;
- ListBase floating;
+ /* Note: Data inside #pending_edges are allocated with MEM_xxx call instead of in pool. */
+ struct LineartPendingEdges pending_edges;
} LineartObjectInfo;
diff --git a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
index 08a8aed41c0..fe1bbc3fc23 100644
--- a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
+++ b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
@@ -97,7 +97,7 @@ static bool lineart_triangle_edge_image_space_occlusion(SpinLock *spl,
double *from,
double *to);
-static void lineart_add_edge_to_list(LineartRenderBuffer *rb, LineartEdge *e);
+static void lineart_add_edge_to_array(LineartPendingEdges *pe, LineartEdge *e);
static LineartCache *lineart_init_cache(void);
@@ -412,38 +412,26 @@ static void lineart_occlusion_single_line(LineartRenderBuffer *rb, LineartEdge *
static int lineart_occlusion_make_task_info(LineartRenderBuffer *rb, LineartRenderTaskInfo *rti)
{
- LineartEdge *data;
- int i;
int res = 0;
+ int starting_index;
BLI_spin_lock(&rb->lock_task);
-#define LRT_ASSIGN_OCCLUSION_TASK(name) \
- if (rb->name.last) { \
- data = rb->name.last; \
- rti->name.first = (void *)data; \
- for (i = 0; i < LRT_THREAD_EDGE_COUNT && data; i++) { \
- data = data->next; \
- } \
- rti->name.last = data; \
- rb->name.last = data; \
- res = 1; \
- } \
- else { \
- rti->name.first = rti->name.last = NULL; \
- }
-
- LRT_ASSIGN_OCCLUSION_TASK(contour);
- LRT_ASSIGN_OCCLUSION_TASK(intersection);
- LRT_ASSIGN_OCCLUSION_TASK(crease);
- LRT_ASSIGN_OCCLUSION_TASK(material);
- LRT_ASSIGN_OCCLUSION_TASK(edge_mark);
- LRT_ASSIGN_OCCLUSION_TASK(floating);
-
-#undef LRT_ASSIGN_OCCLUSION_TASK
+ starting_index = rb->scheduled_count;
+ rb->scheduled_count += LRT_THREAD_EDGE_COUNT;
BLI_spin_unlock(&rb->lock_task);
+ if (starting_index >= rb->pending_edges.next) {
+ res = 0;
+ }
+ else {
+ rti->pending_edges.array = &rb->pending_edges.array[starting_index];
+ int remaining = rb->pending_edges.next - starting_index;
+ rti->pending_edges.max = MIN2(remaining, LRT_THREAD_EDGE_COUNT);
+ res = 1;
+ }
+
return res;
}
@@ -453,28 +441,8 @@ static void lineart_occlusion_worker(TaskPool *__restrict UNUSED(pool), LineartR
LineartEdge *eip;
while (lineart_occlusion_make_task_info(rb, rti)) {
-
- for (eip = rti->contour.first; eip && eip != rti->contour.last; eip = eip->next) {
- lineart_occlusion_single_line(rb, eip, rti->thread_id);
- }
-
- for (eip = rti->crease.first; eip && eip != rti->crease.last; eip = eip->next) {
- lineart_occlusion_single_line(rb, eip, rti->thread_id);
- }
-
- for (eip = rti->intersection.first; eip && eip != rti->intersection.last; eip = eip->next) {
- lineart_occlusion_single_line(rb, eip, rti->thread_id);
- }
-
- for (eip = rti->material.first; eip && eip != rti->material.last; eip = eip->next) {
- lineart_occlusion_single_line(rb, eip, rti->thread_id);
- }
-
- for (eip = rti->edge_mark.first; eip && eip != rti->edge_mark.last; eip = eip->next) {
- lineart_occlusion_single_line(rb, eip, rti->thread_id);
- }
-
- for (eip = rti->floating.first; eip && eip != rti->floating.last; eip = eip->next) {
+ for (int i = 0; i < rti->pending_edges.max; i++) {
+ eip = rti->pending_edges.array[i];
lineart_occlusion_single_line(rb, eip, rti->thread_id);
}
}
@@ -492,15 +460,6 @@ static void lineart_main_occlusion_begin(LineartRenderBuffer *rb)
"Task Pool");
int i;
- /* The "last" entry is used to store worker progress in the whole list.
- * These list themselves are single-direction linked, with list.first being the head. */
- rb->contour.last = rb->contour.first;
- rb->crease.last = rb->crease.first;
- rb->intersection.last = rb->intersection.first;
- rb->material.last = rb->material.first;
- rb->edge_mark.last = rb->edge_mark.first;
- rb->floating.last = rb->floating.first;
-
TaskPool *tp = BLI_task_pool_create(NULL, TASK_PRIORITY_HIGH);
for (i = 0; i < thread_count; i++) {
@@ -836,7 +795,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb,
e->object_ref = ob; \
e->t1 = ((old_e->t1 == tri) ? (new_tri) : (old_e->t1)); \
e->t2 = ((old_e->t2 == tri) ? (new_tri) : (old_e->t2)); \
- lineart_add_edge_to_list(rb, e); \
+ lineart_add_edge_to_array(&rb->pending_edges, e); \
}
#define RELINK_EDGE(e_num, new_tri) \
@@ -922,7 +881,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb,
INCREASE_EDGE
if (allow_boundaries) {
e->flags = LRT_EDGE_FLAG_CONTOUR;
- lineart_prepend_edge_direct(&rb->contour.first, e);
+ lineart_add_edge_to_array(&rb->pending_edges, e);
}
/* NOTE: inverting `e->v1/v2` (left/right point) doesn't matter as long as
* `tri->edge` and `tri->v` has the same sequence. and the winding direction
@@ -971,7 +930,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb,
INCREASE_EDGE
if (allow_boundaries) {
e->flags = LRT_EDGE_FLAG_CONTOUR;
- lineart_prepend_edge_direct(&rb->contour.first, e);
+ lineart_add_edge_to_array(&rb->pending_edges, e);
}
e->v1 = &vt[0];
e->v2 = &vt[1];
@@ -1012,7 +971,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb,
INCREASE_EDGE
if (allow_boundaries) {
e->flags = LRT_EDGE_FLAG_CONTOUR;
- lineart_prepend_edge_direct(&rb->contour.first, e);
+ lineart_add_edge_to_array(&rb->pending_edges, e);
}
e->v1 = &vt[1];
e->v2 = &vt[0];
@@ -1087,7 +1046,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb,
INCREASE_EDGE
if (allow_boundaries) {
e->flags = LRT_EDGE_FLAG_CONTOUR;
- lineart_prepend_edge_direct(&rb->contour.first, e);
+ lineart_add_edge_to_array(&rb->pending_edges, e);
}
e->v1 = &vt[1];
e->v2 = &vt[0];
@@ -1139,7 +1098,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb,
INCREASE_EDGE
if (allow_boundaries) {
e->flags = LRT_EDGE_FLAG_CONTOUR;
- lineart_prepend_edge_direct(&rb->contour.first, e);
+ lineart_add_edge_to_array(&rb->pending_edges, e);
}
e->v1 = &vt[1];
e->v2 = &vt[0];
@@ -1188,7 +1147,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb,
INCREASE_EDGE
if (allow_boundaries) {
e->flags = LRT_EDGE_FLAG_CONTOUR;
- lineart_prepend_edge_direct(&rb->contour.first, e);
+ lineart_add_edge_to_array(&rb->pending_edges, e);
}
e->v1 = &vt[1];
e->v2 = &vt[0];
@@ -1753,75 +1712,52 @@ static void loose_data_sum_reduce(const void *__restrict UNUSED(userdata),
lineart_join_loose_edge_arr(final, loose_chunk);
}
-static void lineart_add_edge_to_list(LineartRenderBuffer *rb, LineartEdge *e)
+static void lineart_add_edge_to_array(LineartPendingEdges *pe, LineartEdge *e)
{
- switch (e->flags) {
- case LRT_EDGE_FLAG_CONTOUR:
- lineart_prepend_edge_direct(&rb->contour.first, e);
- break;
- case LRT_EDGE_FLAG_CREASE:
- lineart_prepend_edge_direct(&rb->crease.first, e);
- break;
- case LRT_EDGE_FLAG_MATERIAL:
- lineart_prepend_edge_direct(&rb->material.first, e);
- break;
- case LRT_EDGE_FLAG_EDGE_MARK:
- lineart_prepend_edge_direct(&rb->edge_mark.first, e);
- break;
- case LRT_EDGE_FLAG_INTERSECTION:
- lineart_prepend_edge_direct(&rb->intersection.first, e);
- break;
- case LRT_EDGE_FLAG_LOOSE:
- lineart_prepend_edge_direct(&r
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list