[Bf-blender-cvs] [56b218296c2] master: Fix T99268: LineArt better handling for dense overlappings.
Yiming Wu
noreply at git.blender.org
Fri Jul 1 14:47:32 CEST 2022
Commit: 56b218296c228acbe00940d50336a3b6f0df2915
Author: Yiming Wu
Date: Fri Jul 1 16:55:15 2022 +0800
Branches: master
https://developer.blender.org/rB56b218296c228acbe00940d50336a3b6f0df2915
Fix T99268: LineArt better handling for dense overlappings.
Two main fixes:
- Split tiles only when we are more sure that it will improve distribution.
- Discard edges and chains that are not gonna be used afterwards before chaining.
This speeds up the whole process and also eliminates unnecessary tile splitting.
Reviewed By: Sebastian Parborg (zeddb)
Differential Revision: https://developer.blender.org/D15335
===================================================================
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 d7005a4bc61..5dd833fb12b 100644
--- a/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
+++ b/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
@@ -549,7 +549,7 @@ typedef struct LineartBoundingArea {
uint32_t max_triangle_count;
uint32_t line_count;
uint32_t max_line_count;
- uint32_t user_count;
+ uint32_t insider_triangle_count;
/* Use array for speeding up multiple accesses. */
struct LineartTriangle **linked_triangles;
@@ -845,7 +845,7 @@ void MOD_lineart_chain_split_for_fixed_occlusion(LineartData *ld);
* implemented yet.
*/
void MOD_lineart_chain_connect(LineartData *ld);
-void MOD_lineart_chain_discard_short(LineartData *ld, float threshold);
+void MOD_lineart_chain_discard_unused(LineartData *ld, float threshold, uint8_t max_occlusion);
void MOD_lineart_chain_clip_at_border(LineartData *ld);
/**
* This should always be the last stage!, see the end of
diff --git a/source/blender/gpencil_modifiers/intern/lineart/lineart_chain.c b/source/blender/gpencil_modifiers/intern/lineart/lineart_chain.c
index 988698771bf..7c8e0c5a6f5 100644
--- a/source/blender/gpencil_modifiers/intern/lineart/lineart_chain.c
+++ b/source/blender/gpencil_modifiers/intern/lineart/lineart_chain.c
@@ -725,8 +725,9 @@ void MOD_lineart_chain_split_for_fixed_occlusion(LineartData *ld)
}
}
}
- /* Get rid of those very short "zig-zag" lines that jumps around visibility. */
- MOD_lineart_chain_discard_short(ld, DBL_EDGE_LIM);
+
+ MOD_lineart_chain_discard_unused(ld, DBL_EDGE_LIM, ld->conf.max_occlusion_level);
+
LISTBASE_FOREACH (LineartEdgeChain *, iec, &ld->chains) {
lineart_bounding_area_link_chain(ld, iec);
}
@@ -1018,12 +1019,14 @@ float MOD_lineart_chain_compute_length(LineartEdgeChain *ec)
return offset_accum;
}
-void MOD_lineart_chain_discard_short(LineartData *ld, const float threshold)
+void MOD_lineart_chain_discard_unused(LineartData *ld,
+ const float threshold,
+ uint8_t max_occlusion)
{
LineartEdgeChain *ec, *next_ec;
for (ec = ld->chains.first; ec; ec = next_ec) {
next_ec = ec->next;
- if (MOD_lineart_chain_compute_length(ec) < threshold) {
+ if (ec->level > max_occlusion || MOD_lineart_chain_compute_length(ec) < threshold) {
BLI_remlink(&ld->chains, ec);
}
}
diff --git a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
index 236e2df1537..874da3b88c9 100644
--- a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
+++ b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
@@ -494,10 +494,10 @@ static bool lineart_point_inside_triangle(const double v[2],
const double v1[2],
const double v2[2])
{
- double cl, c;
+ double cl, c, cl0;
cl = (v0[0] - v[0]) * (v1[1] - v[1]) - (v0[1] - v[1]) * (v1[0] - v[0]);
- c = cl;
+ c = cl0 = cl;
cl = (v1[0] - v[0]) * (v2[1] - v[1]) - (v1[1] - v[1]) * (v2[0] - v[0]);
if (c * cl <= 0) {
@@ -513,8 +513,7 @@ static bool lineart_point_inside_triangle(const double v[2],
c = cl;
- cl = (v0[0] - v[0]) * (v1[1] - v[1]) - (v0[1] - v[1]) * (v1[0] - v[0]);
- if (c * cl <= 0) {
+ if (c * cl0 <= 0) {
return false;
}
@@ -3972,7 +3971,7 @@ static void lineart_bounding_area_split(LineartData *ld,
BLI_spin_init(&ba[i].lock);
}
- for (int i = 0; i < root->triangle_count; i++) {
+ for (uint32_t i = 0; i < root->triangle_count; i++) {
LineartTriangle *tri = root->linked_triangles[i];
double b[4];
@@ -4011,10 +4010,8 @@ static bool lineart_bounding_area_edge_intersect(LineartData *UNUSED(fb),
double converted[4];
double c1, c;
- if (((converted[0] = (double)ba->l) > MAX2(l[0], r[0])) ||
- ((converted[1] = (double)ba->r) < MIN2(l[0], r[0])) ||
- ((converted[2] = (double)ba->b) > MAX2(l[1], r[1])) ||
- ((converted[3] = (double)ba->u) < MIN2(l[1], r[1]))) {
+ if (((converted[0] = ba->l) > MAX2(l[0], r[0])) || ((converted[1] = ba->r) < MIN2(l[0], r[0])) ||
+ ((converted[2] = ba->b) > MAX2(l[1], r[1])) || ((converted[3] = ba->u) < MIN2(l[1], r[1]))) {
return false;
}
@@ -4047,22 +4044,26 @@ static bool lineart_bounding_area_edge_intersect(LineartData *UNUSED(fb),
static bool lineart_bounding_area_triangle_intersect(LineartData *fb,
LineartTriangle *tri,
- LineartBoundingArea *ba)
+ LineartBoundingArea *ba,
+ bool *r_triangle_vert_inside)
{
double p1[2], p2[2], p3[2], p4[2];
double *FBC1 = tri->v[0]->fbcoord, *FBC2 = tri->v[1]->fbcoord, *FBC3 = tri->v[2]->fbcoord;
- p3[0] = p1[0] = (double)ba->l;
- p2[1] = p1[1] = (double)ba->b;
- p2[0] = p4[0] = (double)ba->r;
- p3[1] = p4[1] = (double)ba->u;
+ p3[0] = p1[0] = ba->l;
+ p2[1] = p1[1] = ba->b;
+ p2[0] = p4[0] = ba->r;
+ p3[1] = p4[1] = ba->u;
if ((FBC1[0] >= p1[0] && FBC1[0] <= p2[0] && FBC1[1] >= p1[1] && FBC1[1] <= p3[1]) ||
(FBC2[0] >= p1[0] && FBC2[0] <= p2[0] && FBC2[1] >= p1[1] && FBC2[1] <= p3[1]) ||
(FBC3[0] >= p1[0] && FBC3[0] <= p2[0] && FBC3[1] >= p1[1] && FBC3[1] <= p3[1])) {
+ *r_triangle_vert_inside = true;
return true;
}
+ *r_triangle_vert_inside = false;
+
if (lineart_point_inside_triangle(p1, FBC1, FBC2, FBC3) ||
lineart_point_inside_triangle(p2, FBC1, FBC2, FBC3) ||
lineart_point_inside_triangle(p3, FBC1, FBC2, FBC3) ||
@@ -4101,7 +4102,8 @@ static void lineart_bounding_area_link_triangle(LineartData *ld,
bool do_intersection,
struct LineartIsecThread *th)
{
- if (!lineart_bounding_area_triangle_intersect(ld, tri, root_ba)) {
+ bool triangle_vert_inside;
+ if (!lineart_bounding_area_triangle_intersect(ld, tri, root_ba, &triangle_vert_inside)) {
return;
}
@@ -4138,7 +4140,12 @@ static void lineart_bounding_area_link_triangle(LineartData *ld,
if (old_ba->triangle_count < old_ba->max_triangle_count) {
const uint32_t old_tri_count = old_ba->triangle_count;
- old_ba->linked_triangles[old_ba->triangle_count++] = tri;
+ old_ba->linked_triangles[old_tri_count] = tri;
+
+ if (triangle_vert_inside) {
+ old_ba->insider_triangle_count++;
+ }
+ old_ba->triangle_count++;
/* Do intersections in place. */
if (do_intersection && ld->conf.use_intersections) {
@@ -4151,7 +4158,8 @@ static void lineart_bounding_area_link_triangle(LineartData *ld,
}
else { /* We need to wait for either splitting or array extension to be done. */
- if (recursive_level < ld->qtree.recursive_level) {
+ if (recursive_level < ld->qtree.recursive_level &&
+ old_ba->insider_triangle_count >= LRT_TILE_SPLITTING_TRIANGLE_LIMIT) {
if (!old_ba->child) {
/* old_ba->child==NULL, means we are the thread that's doing the splitting. */
lineart_bounding_area_split(ld, old_ba, recursive_level);
@@ -4271,6 +4279,62 @@ void lineart_main_link_lines(LineartData *ld)
LRT_ITER_ALL_LINES_END
}
+static void lineart_main_remove_unused_lines_recursive(LineartBoundingArea *ba,
+ uint8_t max_occlusion)
+{
+ if (ba->child) {
+ for (int i = 0; i < 4; i++) {
+ lineart_main_remove_unused_lines_recursive(&ba->child[i], max_occlusion);
+ }
+ return;
+ }
+
+ if (!ba->line_count) {
+ return;
+ }
+
+ int usable_count = 0;
+ for (int i = 0; i < ba->line_count; i++) {
+ LineartEdge *e = ba->linked_lines[i];
+ if (e->min_occ > max_occlusion) {
+ continue;
+ }
+ usable_count++;
+ }
+
+ if (!usable_count) {
+ ba->line_count = 0;
+ return;
+ }
+
+ LineartEdge **new_array = MEM_callocN(sizeof(LineartEdge *) * usable_count,
+ "cleaned lineart edge array");
+
+ int new_i = 0;
+ for (int i = 0; i < ba->line_count; i++) {
+ LineartEdge *e = ba->linked_lines[i];
+ if (e->min_occ > max_occlusion) {
+ continue;
+ }
+ new_array[new_i] = e;
+ new_i++;
+ }
+
+ MEM_freeN(ba->linked_lines);
+ ba->linked_lines = new_array;
+ ba->max_line_count = ba->line_count = usable_count;
+}
+
+static void lineart_main_remove_unused_lines_from_tiles(LineartData *ld)
+{
+ for (int row = 0; row < ld->qtree.count_y; row++) {
+ for (int col = 0; col < ld->qtree.count_x; col++) {
+ lineart_main_remove_unused_lines_recursive(
+ &ld->qtree.initials[row * ld->qtree.count_x + col], ld->conf.max_occlusion_level);
+ }
+ }
+}
+
static bool lineart_get_triangle_bounding_areas(
LineartData *ld, LineartTriangle *tri, int *rowbegin, int *rowend, int *colbegin, int *colend)
{
@@ -4997,6 +5061,8 @@ bool MOD_lineart_compute_feature_lines(Depsgraph *depsgraph,
lineart_main_make_enclosed_shapes(ld, shadow_rb);
+ lineart_main_remove_unused_lines_from_tiles(ld);
+
/* Chaining is all single threaded. See lineart_chain.c
* In this particular call, only lines that are geometrically connected (share the _exact_
* same end point) will be chained together. */
@@ -5010,10 +5076,6 @@ bool MOD_lineart_compute_feature_lines(Depsgraph *depsgraph,
* the place threshold value gets involved. */
MOD_lineart_chain_connect(ld);
- float *t_image = &lmd->chaining_image_threshold;
- /* This configuration ensures there won't be accidental lost of short unchained segments. */
- MOD_lineart_chain_discard_short(ld, MIN2(*t_image, 0.001f) - FLT_EPSILON);
-
if (ld->conf.chain_smooth_tolerance > FLT_EPSILON) {
/* Keeping UI range of 0-1 for ease of read while scaling down the actual value for best
* effective range in image-space (Coordinate only goes from -1 to 1). This value is
More information about the Bf-blender-cvs
mailing list