blender
/
blender
136
406
Fork 590
Code Issues 6.2k Pull Requests 764 Projects 19 Wiki Activity

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
This commit is contained in:
YimingWu 2022-05-18 15:33:35 +08:00
parent 9f8254fd34
commit 6f00b1500c
Notes: blender-bot 2023-02-14 04:39:18 +01:00 
Referenced by issue #87739, Line Art further improvement list
3 changed files with 97 additions and 202 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

39
source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
View File

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

214
source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
View File

@ -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(&rb->floating.first, e);
break;
if (pe->next >= pe->max || !pe->max) {
if (!pe->max) {
pe->max = 1000;
}
LineartEdge **new_array = MEM_mallocN(sizeof(LineartEdge *) * pe->max * 2,
"LineartPendingEdges array");
if (LIKELY(pe->array)) {
memcpy(new_array, pe->array, sizeof(LineartEdge *) * pe->max);
MEM_freeN(pe->array);
}
pe->max *= 2;
pe->array = new_array;
}
pe->array[pe->next] = e;
pe->next++;
}
static void lineart_add_edge_to_list_thread(LineartObjectInfo *obi, LineartEdge *e)
static void lineart_add_edge_to_array_thread(LineartObjectInfo *obi, LineartEdge *e)
{
#define LRT_ASSIGN_EDGE(name) \
lineart_prepend_edge_direct(&obi->name.first, e); \
if (!obi->name.last) { \
obi->name.last = e; \
}
switch (e->flags) {
case LRT_EDGE_FLAG_CONTOUR:
LRT_ASSIGN_EDGE(contour);
break;
case LRT_EDGE_FLAG_CREASE:
LRT_ASSIGN_EDGE(crease);
break;
case LRT_EDGE_FLAG_MATERIAL:
LRT_ASSIGN_EDGE(material);
break;
case LRT_EDGE_FLAG_EDGE_MARK:
LRT_ASSIGN_EDGE(edge_mark);
break;
case LRT_EDGE_FLAG_INTERSECTION:
LRT_ASSIGN_EDGE(intersection);
break;
case LRT_EDGE_FLAG_LOOSE:
LRT_ASSIGN_EDGE(floating);
break;
}
#undef LRT_ASSIGN_EDGE
lineart_add_edge_to_array(&obi->pending_edges, e);
}
static void lineart_finalize_object_edge_list(LineartRenderBuffer *rb, LineartObjectInfo *obi)
/* Note: For simplicity, this function doesn't actually do anything if you already have data in
* #pe. */
static void lineart_finalize_object_edge_array_reserve(LineartPendingEdges *pe, int count)
{
#define LRT_OBI_TO_RB(name) \
if (obi->name.last) { \
((LineartEdge *)obi->name.last)->next = rb->name.first; \
rb->name.first = obi->name.first; \
if (pe->max || pe->array) {
return;
}
LRT_OBI_TO_RB(contour);
LRT_OBI_TO_RB(crease);
LRT_OBI_TO_RB(material);
LRT_OBI_TO_RB(edge_mark);
LRT_OBI_TO_RB(intersection);
LRT_OBI_TO_RB(floating);
#undef LRT_OBI_TO_RB
pe->max = count;
LineartEdge **new_array = MEM_mallocN(sizeof(LineartEdge *) * pe->max,
"LineartPendingEdges array final");
pe->array = new_array;
}
static void lineart_finalize_object_edge_array(LineartPendingEdges *pe, LineartObjectInfo *obi)
{
memcpy(&pe->array[pe->next],
obi->pending_edges.array,
sizeof(LineartEdge *) * obi->pending_edges.next);
MEM_freeN(obi->pending_edges.array);
pe->next += obi->pending_edges.next;
}
static void lineart_triangle_adjacent_assign(LineartTriangle *tri,
@ -2209,7 +2145,7 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend
BLI_addtail(&la_edge->segments, la_seg);
if (usage == OBJECT_LRT_INHERIT || usage == OBJECT_LRT_INCLUDE ||
usage == OBJECT_LRT_NO_INTERSECTION) {
lineart_add_edge_to_list_thread(ob_info, la_edge);
lineart_add_edge_to_array_thread(ob_info, la_edge);
}
if (edge_added) {
@ -2236,7 +2172,7 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend
BLI_addtail(&la_edge->segments, la_seg);
if (usage == OBJECT_LRT_INHERIT || usage == OBJECT_LRT_INCLUDE ||
usage == OBJECT_LRT_NO_INTERSECTION) {
lineart_add_edge_to_list_thread(ob_info, la_edge);
lineart_add_edge_to_array_thread(ob_info, la_edge);
}
la_edge++;
la_seg++;
@ -2551,6 +2487,17 @@ static void lineart_main_load_geometries(
* lineart_triangle_share_edge() can work properly from the lack of triangle adjacent info. */
int global_i = 0;
int edge_count = 0;
for (int i = 0; i < thread_count; i++) {
for (LineartObjectInfo *obi = olti[i].pending; obi; obi = obi->next) {
if (!obi->v_eln) {
continue;
}
edge_count += obi->pending_edges.next;
}
}
lineart_finalize_object_edge_array_reserve(&rb->pending_edges, edge_count);
for (int i = 0; i < thread_count; i++) {
for (LineartObjectInfo *obi = olti[i].pending; obi; obi = obi->next) {
if (!obi->v_eln) {
@ -2567,7 +2514,7 @@ static void lineart_main_load_geometries(
* same numeric index to come close together. */
obi->global_i_offset = global_i;
global_i += v_count;
lineart_finalize_object_edge_list(rb, obi);
lineart_finalize_object_edge_array(&rb->pending_edges, obi);
}
}
@ -3272,7 +3219,7 @@ static LineartEdge *lineart_triangle_intersect(LineartRenderBuffer *rb,
result->flags = LRT_EDGE_FLAG_INTERSECTION;
result->intersection_mask = (tri->intersection_mask | testing->intersection_mask);
lineart_prepend_edge_direct(&rb->intersection.first, result);
lineart_add_edge_to_array(&rb->pending_edges, result);
return result;
}
@ -3360,13 +3307,6 @@ static void lineart_destroy_render_data(LineartRenderBuffer *rb)
return;
}
memset(&rb->contour, 0, sizeof(ListBase));
memset(&rb->crease, 0, sizeof(ListBase));
memset(&rb->intersection, 0, sizeof(ListBase));
memset(&rb->edge_mark, 0, sizeof(ListBase));
memset(&rb->material, 0, sizeof(ListBase));
memset(&rb->floating, 0, sizeof(ListBase));
BLI_listbase_clear(&rb->chains);
BLI_listbase_clear(&rb->wasted_cuts);
@ -3378,6 +3318,10 @@ static void lineart_destroy_render_data(LineartRenderBuffer *rb)
BLI_spin_end(&rb->lock_cuts);
BLI_spin_end(&rb->render_data_pool.lock_mem);
if (rb->pending_edges.array) {
MEM_freeN(rb->pending_edges.array);
}
lineart_mem_destroy(&rb->render_data_pool);
}

46
source/blender/gpencil_modifiers/intern/lineart/lineart_intern.h
View File

@ -67,49 +67,11 @@ int lineart_count_intersection_segment_count(struct LineartRenderBuffer *rb);
void lineart_count_and_print_render_buffer_memory(struct LineartRenderBuffer *rb);
#define LRT_ITER_ALL_LINES_BEGIN \
LineartEdge *e, *next_e; \
void **current_head; \
e = rb->contour.first; \
if (!e) { \
e = rb->crease.first; \
} \
if (!e) { \
e = rb->material.first; \
} \
if (!e) { \
e = rb->edge_mark.first; \
} \
if (!e) { \
e = rb->intersection.first; \
} \
if (!e) { \
e = rb->floating.first; \
} \
for (current_head = &rb->contour.first; e; e = next_e) { \
next_e = e->next;
LineartEdge *e; \
for (int i = 0; i < rb->pending_edges.next; i++) { \
e = rb->pending_edges.array[i];
#define LRT_ITER_ALL_LINES_NEXT \
while (!next_e) { \
if (current_head == &rb->contour.first) { \
current_head = &rb->crease.first; \
} \
else if (current_head == &rb->crease.first) { \
current_head = &rb->material.first; \
} \
else if (current_head == &rb->material.first) { \
current_head = &rb->edge_mark.first; \
} \
else if (current_head == &rb->edge_mark.first) { \
current_head = &rb->intersection.first; \
} \
else if (current_head == &rb->intersection.first) { \
current_head = &rb->floating.first; \
} \
else { \
break; \
} \
next_e = *current_head; \
}
#define LRT_ITER_ALL_LINES_NEXT ; /* Doesn't do anything now with new array setup. */
#define LRT_ITER_ALL_LINES_END \
LRT_ITER_ALL_LINES_NEXT \