diff options
author | YimingWu <xp8110@outlook.com> | 2021-05-27 15:33:02 +0300 |
---|---|---|
committer | YimingWu <xp8110@outlook.com> | 2021-05-27 15:33:02 +0300 |
commit | 6ad4b8b764a80b9deccd8e53b8c754829dda5e92 (patch) | |
tree | 9d80a25e583c9aa43a50b97d47b65e5e1edf7094 /source/blender/gpencil_modifiers | |
parent | f45270b4fb88c9d53b3b5abf0e3f2d6964623edf (diff) |
LineArt: List Optimization for tile linked data.
Use array instead of ListBase for line art
bounding area linked triangles and edges.
Reviewed By: Sebastian Parborg (zeddb)
Differential Revision: https://developer.blender.org/D11302
Diffstat (limited to 'source/blender/gpencil_modifiers')
3 files changed, 93 insertions, 17 deletions
diff --git a/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h b/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h index 4e0585c9f6d..712e92d017d 100644 --- a/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h +++ b/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h @@ -205,6 +205,17 @@ typedef struct LineartChainRegisterEntry { char is_left; } LineartChainRegisterEntry; +enum eLineArtTileRecursiveLimit { + /* If tile gets this small, it's already much smaller than a pixel. No need to continue + * splitting. */ + LRT_TILE_RECURSIVE_PERSPECTIVE = 30, + /* This is a tried-and-true safe value for high poly models that also needed ortho rendering. */ + LRT_TILE_RECURSIVE_ORTHO = 10, +}; + +#define LRT_TILE_SPLITTING_TRIANGLE_LIMIT 100 +#define LRT_TILE_EDGE_COUNT_INITIAL 32 + typedef struct LineartRenderBuffer { struct LineartRenderBuffer *prev, *next; @@ -219,6 +230,11 @@ typedef struct LineartRenderBuffer { struct LineartBoundingArea *initial_bounding_areas; unsigned int bounding_area_count; + /* When splitting bounding areas, if there's an ortho camera placed at a straight angle, there + * will be a lot of triangles aligned in line which can not be separated by continue subdividing + * the tile. So we set a strict limit when using ortho camera. See eLineArtTileRecursiveLimit. */ + int tile_recursive_level; + ListBase vertex_buffer_pointers; ListBase line_buffer_pointers; ListBase triangle_buffer_pointers; @@ -363,10 +379,14 @@ typedef struct LineartBoundingArea { ListBase up; ListBase bp; - short triangle_count; + int16_t triangle_count; + int16_t max_triangle_count; + int16_t line_count; + int16_t max_line_count; - ListBase linked_triangles; - ListBase linked_edges; + /* Use array for speeding up multiple accesses. */ + struct LineartTriangle **linked_triangles; + struct LineartEdge **linked_lines; /** Reserved for image space reduction && multi-thread chaining. */ ListBase linked_chains; diff --git a/source/blender/gpencil_modifiers/intern/lineart/lineart_chain.c b/source/blender/gpencil_modifiers/intern/lineart/lineart_chain.c index c8e4e93843a..23928b4ccda 100644 --- a/source/blender/gpencil_modifiers/intern/lineart/lineart_chain.c +++ b/source/blender/gpencil_modifiers/intern/lineart/lineart_chain.c @@ -40,8 +40,8 @@ static LineartEdge *lineart_line_get_connected(LineartBoundingArea *ba, LineartVert **new_vt, int match_flag) { - LISTBASE_FOREACH (LinkData *, lip, &ba->linked_edges) { - LineartEdge *n_e = lip->data; + for (int i = 0; i < ba->line_count; i++) { + LineartEdge *n_e = ba->linked_lines[i]; if ((!(n_e->flags & LRT_EDGE_FLAG_ALL_TYPE)) || (n_e->flags & LRT_EDGE_FLAG_CHAIN_PICKED)) { continue; diff --git a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c index 24c405f1d67..0b439c20d65 100644 --- a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c +++ b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c @@ -314,6 +314,36 @@ BLI_INLINE bool lineart_occlusion_is_adjacent_intersection(LineartEdge *e, Linea (v2->base.flag && v2->intersecting_with == tri)); } +static void lineart_bounding_area_triangle_add(LineartRenderBuffer *rb, + LineartBoundingArea *ba, + LineartTriangle *tri) +{ + if (ba->triangle_count >= ba->max_triangle_count) { + LineartTriangle **new_array = lineart_mem_acquire( + &rb->render_data_pool, sizeof(LineartTriangle *) * ba->max_triangle_count * 2); + memcpy(new_array, ba->linked_triangles, sizeof(LineartTriangle *) * ba->max_triangle_count); + ba->max_triangle_count *= 2; + ba->linked_triangles = new_array; + } + ba->linked_triangles[ba->triangle_count] = tri; + ba->triangle_count++; +} + +static void lineart_bounding_area_line_add(LineartRenderBuffer *rb, + LineartBoundingArea *ba, + LineartEdge *e) +{ + if (ba->line_count >= ba->max_line_count) { + LineartEdge **new_array = lineart_mem_acquire(&rb->render_data_pool, + sizeof(LineartEdge *) * ba->max_line_count * 2); + memcpy(new_array, ba->linked_lines, sizeof(LineartEdge *) * ba->max_line_count); + ba->max_line_count *= 2; + ba->linked_lines = new_array; + } + ba->linked_lines[ba->line_count] = e; + ba->line_count++; +} + static void lineart_occlusion_single_line(LineartRenderBuffer *rb, LineartEdge *e, int thread_id) { double x = e->v1->fbcoord[0], y = e->v1->fbcoord[1]; @@ -334,8 +364,8 @@ static void lineart_occlusion_single_line(LineartRenderBuffer *rb, LineartEdge * while (nba) { - LISTBASE_FOREACH (LinkData *, lip, &nba->linked_triangles) { - tri = lip->data; + for (int i = 0; i < nba->triangle_count; i++) { + tri = (LineartTriangleThread *)nba->linked_triangles[i]; /* If we are already testing the line in this thread, then don't do it. */ if (tri->testing_e[thread_id] == e || (tri->base.flags & LRT_TRIANGLE_INTERSECTION_ONLY) || lineart_occlusion_is_adjacent_intersection(e, (LineartTriangle *)tri)) { @@ -2499,6 +2529,7 @@ static LineartEdge *lineart_triangle_intersect(LineartRenderBuffer *rb, BLI_addtail(&result->segments, es); /* Don't need to OR flags right now, just a type mark. */ result->flags = LRT_EDGE_FLAG_INTERSECTION; + lineart_prepend_edge_direct(&rb->intersection.first, result); int r1, r2, c1, c2, row, col; if (lineart_get_edge_bounding_areas(rb, result, &r1, &r2, &c1, &c2)) { @@ -2521,7 +2552,6 @@ static void lineart_triangle_intersect_in_bounding_area(LineartRenderBuffer *rb, * See definition of LineartTriangleThread for more info. */ LineartTriangle *testing_triangle; LineartTriangleThread *tt; - LinkData *lip, *next_lip; double *G0 = tri->v[0]->gloc, *G1 = tri->v[1]->gloc, *G2 = tri->v[2]->gloc; @@ -2535,9 +2565,8 @@ static void lineart_triangle_intersect_in_bounding_area(LineartRenderBuffer *rb, } /* If this _is_ the smallest subdiv bounding area, then do the intersections there. */ - for (lip = ba->linked_triangles.first; lip; lip = next_lip) { - next_lip = lip->next; - testing_triangle = lip->data; + for (int i = 0; i < ba->triangle_count; i++) { + testing_triangle = ba->linked_triangles[i]; tt = (LineartTriangleThread *)testing_triangle; if (testing_triangle == tri || tt->testing_e[0] == (LineartEdge *)tri) { @@ -2660,6 +2689,13 @@ static LineartRenderBuffer *lineart_create_render_buffer(Scene *scene, rb->w = scene->r.xsch; rb->h = scene->r.ysch; + if (rb->cam_is_persp) { + rb->tile_recursive_level = LRT_TILE_RECURSIVE_PERSPECTIVE; + } + else { + rb->tile_recursive_level = LRT_TILE_RECURSIVE_ORTHO; + } + double asp = ((double)rb->w / (double)rb->h); rb->shift_x = (asp >= 1) ? c->shiftx : c->shiftx * asp; rb->shift_y = (asp <= 1) ? c->shifty : c->shifty * asp; @@ -2735,6 +2771,14 @@ static void lineart_main_bounding_area_make_initial(LineartRenderBuffer *rb) ba->cx = (ba->l + ba->r) / 2; ba->cy = (ba->u + ba->b) / 2; + /* Init linked_triangles array. */ + ba->max_triangle_count = LRT_TILE_SPLITTING_TRIANGLE_LIMIT; + ba->max_line_count = LRT_TILE_EDGE_COUNT_INITIAL; + ba->linked_triangles = lineart_mem_acquire( + &rb->render_data_pool, sizeof(LineartTriangle *) * ba->max_triangle_count); + ba->linked_lines = lineart_mem_acquire(&rb->render_data_pool, + sizeof(LineartEdge *) * ba->max_line_count); + /* Link adjacent ones. */ if (row) { lineart_list_append_pointer_pool( @@ -2949,7 +2993,18 @@ static void lineart_bounding_area_split(LineartRenderBuffer *rb, lineart_bounding_areas_connect_new(rb, root); - while ((tri = lineart_list_pop_pointer_no_free(&root->linked_triangles)) != NULL) { + /* Init linked_triangles array. */ + for (int i = 0; i < 4; i++) { + ba[i].max_triangle_count = LRT_TILE_SPLITTING_TRIANGLE_LIMIT; + ba[i].max_line_count = LRT_TILE_EDGE_COUNT_INITIAL; + ba[i].linked_triangles = lineart_mem_acquire( + &rb->render_data_pool, sizeof(LineartTriangle *) * LRT_TILE_SPLITTING_TRIANGLE_LIMIT); + ba[i].linked_lines = lineart_mem_acquire(&rb->render_data_pool, + sizeof(LineartEdge *) * LRT_TILE_EDGE_COUNT_INITIAL); + } + + for (int i = 0; i < root->triangle_count; i++) { + tri = root->linked_triangles[i]; LineartBoundingArea *cba = root->child; double b[4]; b[0] = MIN3(tri->v[0]->fbcoord[0], tri->v[1]->fbcoord[0], tri->v[2]->fbcoord[0]); @@ -2970,7 +3025,8 @@ static void lineart_bounding_area_split(LineartRenderBuffer *rb, } } - while ((e = lineart_list_pop_pointer_no_free(&root->linked_edges)) != NULL) { + for (int i = 0; i < root->line_count; i++) { + e = root->linked_lines[i]; lineart_bounding_area_link_edge(rb, root, e); } @@ -3070,13 +3126,13 @@ static void lineart_bounding_area_link_triangle(LineartRenderBuffer *rb, return; } if (root_ba->child == NULL) { - lineart_list_append_pointer_pool(&root_ba->linked_triangles, &rb->render_data_pool, tri); - root_ba->triangle_count++; + lineart_bounding_area_triangle_add(rb, root_ba, tri); /* If splitting doesn't improve triangle separation, then shouldn't allow splitting anymore. * Here we use recursive limit. This is especially useful in orthographic render, * where a lot of faces could easily line up perfectly in image space, * which can not be separated by simply slicing the image tile. */ - if (root_ba->triangle_count > 200 && recursive && recursive_level < 10) { + if (root_ba->triangle_count >= LRT_TILE_SPLITTING_TRIANGLE_LIMIT && recursive && + recursive_level < rb->tile_recursive_level) { lineart_bounding_area_split(rb, root_ba, recursive_level); } if (recursive && do_intersection && rb->use_intersections) { @@ -3118,7 +3174,7 @@ static void lineart_bounding_area_link_edge(LineartRenderBuffer *rb, LineartEdge *e) { if (root_ba->child == NULL) { - lineart_list_append_pointer_pool(&root_ba->linked_edges, &rb->render_data_pool, e); + lineart_bounding_area_line_add(rb, root_ba, e); } else { if (lineart_bounding_area_edge_intersect( |