[Bf-blender-cvs] [6ad4b8b764a] master: LineArt: List Optimization for tile linked data.
YimingWu
noreply at git.blender.org
Thu May 27 14:36:54 CEST 2021
Commit: 6ad4b8b764a80b9deccd8e53b8c754829dda5e92
Author: YimingWu
Date: Thu May 27 20:33:02 2021 +0800
Branches: master
https://developer.blender.org/rB6ad4b8b764a80b9deccd8e53b8c754829dda5e92
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
===================================================================
M source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
M source/blender/gpencil_modifiers/intern/lineart/lineart_chain.c
M source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
===================================================================
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
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list