blender
/
blender
136
406
Fork 588
Code Issues 6.2k Pull Requests 754 Projects 19 Wiki Activity

LineArt: Improve certain edge cases in occlusion 

This patch includes:
View vector fix for ortho back face.
Point on segment logic correction.
Better handling of boundary cases.

See review page for detailed description.

Reviewed By: Sebastian Parborg (zeddb)

Differential Revision: https://developer.blender.org/D13143
This commit is contained in:
YimingWu 2021-11-17 14:30:08 +08:00
parent 6e6123b40f
commit 51b8e34fb7
3 changed files with 181 additions and 47 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

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

@ -476,11 +476,32 @@ typedef struct LineartBoundingArea {
#define LRT_MIN3_INDEX_ABC(x, y, z) (x < y ? (x < z ? a : (y < z ? b : c)) : (y < z ? b : c))
#define LRT_ABC(index) (index == 0 ? a : (index == 1 ? b : c))
#define LRT_PABC(index) (index == 0 ? pa : (index == 1 ? pb : pc))
#define DBL_LOOSER 1e-5
#define LRT_DOUBLE_CLOSE_LOOSER(a, b) (((a) + DBL_LOOSER) >= (b) && ((a)-DBL_LOOSER) <= (b))
#define LRT_DOUBLE_CLOSE_ENOUGH(a, b) (((a) + DBL_EDGE_LIM) >= (b) && ((a)-DBL_EDGE_LIM) <= (b))
#define LRT_DOUBLE_CLOSE_ENOUGH_TRI(a, b) \
(((a) + DBL_TRIANGLE_LIM) >= (b) && ((a)-DBL_TRIANGLE_LIM) <= (b))
BLI_INLINE int lineart_LineIntersectTest2d(
const double *a1, const double *a2, const double *b1, const double *b2, double *aRatio)
/* Notes on this function:
* r_ratio: The ratio on segment a1-a2. When r_ratio is very close to zero or one, it
* fixes the value to zero or one, this makes it easier to identify "on the tip" situations.
*
* r_aligned: True when 1) a and b is exactly on the same straight line and 2) a and b share a
* common end-point.
*
* Important: if r_aligned is true, r_ratio will be either 0 or 1 depending on which point from
* segment a is shared with segment b. If it's a1 then r_ratio is 0, else then r_ratio is 1. This
* extra information is needed for line art occlusion stage to work correctly in such cases.
*/
BLI_INLINE int lineart_intersect_seg_seg(const double *a1,
const double *a2,
const double *b1,
const double *b2,
double *r_ratio,
bool *r_aligned)
{
/* Legacy intersection math aligns better with occlusion function quirks. */
/* #define USE_VECTOR_LINE_INTERSECTION */
@ -504,27 +525,27 @@ BLI_INLINE int lineart_LineIntersectTest2d(
double rr;
if (fabs(a2[0] - a1[0]) > fabs(a2[1] - a1[1])) {
*aRatio = ratiod(a1[0], a2[0], rx);
*r_ratio = ratiod(a1[0], a2[0], rx);
if (fabs(b2[0] - b1[0]) > fabs(b2[1] - b1[1])) {
rr = ratiod(b1[0], b2[0], rx);
}
else {
rr = ratiod(b1[1], b2[1], ry);
}
if ((*aRatio) > 0 && (*aRatio) < 1 && rr > 0 && rr < 1) {
if ((*r_ratio) > 0 && (*r_ratio) < 1 && rr > 0 && rr < 1) {
return 1;
}
return 0;
}
*aRatio = ratiod(a1[1], a2[1], ry);
*r_ratio = ratiod(a1[1], a2[1], ry);
if (fabs(b2[0] - b1[0]) > fabs(b2[1] - b1[1])) {
rr = ratiod(b1[0], b2[0], rx);
}
else {
rr = ratiod(b1[1], b2[1], ry);
}
if ((*aRatio) > 0 && (*aRatio) < 1 && rr > 0 && rr < 1) {
if ((*r_ratio) > 0 && (*r_ratio) < 1 && rr > 0 && rr < 1) {
return 1;
}
return 0;
@ -539,34 +560,62 @@ BLI_INLINE int lineart_LineIntersectTest2d(
double x_diff = (a2[0] - a1[0]);
double x_diff2 = (b2[0] - b1[0]);
*r_aligned = false;
if (LRT_DOUBLE_CLOSE_ENOUGH(x_diff, 0)) {
if (LRT_DOUBLE_CLOSE_ENOUGH(x_diff2, 0)) {
*aRatio = 0;
/* This means two segments are both vertical. */
if ((LRT_DOUBLE_CLOSE_ENOUGH(a2[0], b1[0]) && LRT_DOUBLE_CLOSE_ENOUGH(a2[1], b1[1])) ||
(LRT_DOUBLE_CLOSE_ENOUGH(a2[0], b2[0]) && LRT_DOUBLE_CLOSE_ENOUGH(a2[1], b2[1]))) {
*r_aligned = true;
*r_ratio = 1;
}
else if ((LRT_DOUBLE_CLOSE_ENOUGH(a1[0], b1[0]) && LRT_DOUBLE_CLOSE_ENOUGH(a1[1], b1[1])) ||
(LRT_DOUBLE_CLOSE_ENOUGH(a1[0], b2[0]) && LRT_DOUBLE_CLOSE_ENOUGH(a1[1], b2[1]))) {
*r_aligned = true;
*r_ratio = 0;
}
return 0;
}
double r2 = ratiod(b1[0], b2[0], a1[0]);
x = interpd(b2[0], b1[0], r2);
y = interpd(b2[1], b1[1], r2);
*aRatio = ratio = ratiod(a1[1], a2[1], y);
*r_ratio = ratio = ratiod(a1[1], a2[1], y);
}
else {
if (LRT_DOUBLE_CLOSE_ENOUGH(x_diff2, 0)) {
ratio = ratiod(a1[0], a2[0], b1[0]);
x = interpd(a2[0], a1[0], ratio);
*aRatio = ratio;
*r_ratio = ratio;
}
else {
k1 = (a2[1] - a1[1]) / x_diff;
k2 = (b2[1] - b1[1]) / x_diff2;
double y_diff = a2[1] - a1[1], y_diff2 = b2[1] - b1[1];
k1 = y_diff / x_diff;
k2 = y_diff2 / x_diff2;
if (k1 == k2)
if (LRT_DOUBLE_CLOSE_ENOUGH_TRI(k2, k1)) {
/* This means two segments are parallel. This also handles k==0 (both completely
* horizontal) cases. */
if ((LRT_DOUBLE_CLOSE_ENOUGH(a2[0], b1[0]) && LRT_DOUBLE_CLOSE_ENOUGH(a2[1], b1[1])) ||
(LRT_DOUBLE_CLOSE_ENOUGH(a2[0], b2[0]) && LRT_DOUBLE_CLOSE_ENOUGH(a2[1], b2[1]))) {
*r_aligned = true;
*r_ratio = 1;
}
else if ((LRT_DOUBLE_CLOSE_ENOUGH(a1[0], b1[0]) &&
LRT_DOUBLE_CLOSE_ENOUGH(a1[1], b1[1])) ||
(LRT_DOUBLE_CLOSE_ENOUGH(a1[0], b2[0]) &&
LRT_DOUBLE_CLOSE_ENOUGH(a1[1], b2[1]))) {
*r_aligned = true;
*r_ratio = 0;
}
return 0;
}
x = (a1[1] - b1[1] - k1 * a1[0] + k2 * b1[0]) / (k2 - k1);
ratio = (x - a1[0]) / x_diff;
*aRatio = ratio;
*r_ratio = ratio;
}
}
@ -580,6 +629,13 @@ BLI_INLINE int lineart_LineIntersectTest2d(
(b2[0] < b1[0] && x < b2[0]))
return 0;
if (LRT_DOUBLE_CLOSE_ENOUGH_TRI(*r_ratio, 1)) {
*r_ratio = 1;
}
else if (LRT_DOUBLE_CLOSE_ENOUGH_TRI(*r_ratio, 0)) {
*r_ratio = 0;
}
return 1;
#endif
}

5
source/blender/gpencil_modifiers/intern/lineart/lineart_chain.c
View File

@ -634,6 +634,8 @@ void MOD_lineart_chain_split_for_fixed_occlusion(LineartRenderBuffer *rb)
}
}
}
/* Get rid of those very short "zig-zag" lines that jumps around visibility. */
MOD_lineart_chain_discard_short(rb, DBL_EDGE_LIM);
LISTBASE_FOREACH (LineartEdgeChain *, iec, &rb->chains) {
lineart_bounding_area_link_chain(rb, iec);
}
@ -890,6 +892,9 @@ float MOD_lineart_chain_compute_length(LineartEdgeChain *ec)
float last_point[2];
eci = ec->chain.first;
if (!eci) {
return 0;
}
copy_v2_v2(last_point, eci->pos);
for (eci = ec->chain.first; eci; eci = eci->next) {
dist = len_v2v2(eci->pos, last_point);

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

@ -502,6 +502,10 @@ static void lineart_main_occlusion_begin(LineartRenderBuffer *rb)
rb->edge_mark.last = rb->edge_mark.first;
rb->floating.last = rb->floating.first;
/* This is needed because the occlusion function expects the camera vector to point towards the
* camera. */
negate_v3_db(rb->view_vector);
TaskPool *tp = BLI_task_pool_create(NULL, TASK_PRIORITY_HIGH);
for (i = 0; i < thread_count; i++) {
@ -567,20 +571,30 @@ static int lineart_point_on_line_segment(double v[2], double v0[2], double v1[2]
return 0;
}
if (v1[0] - v0[0]) {
if (!LRT_DOUBLE_CLOSE_ENOUGH(v1[0], v0[0])) {
c1 = ratiod(v0[0], v1[0], v[0]);
}
else if (v[0] == v1[0]) {
c2 = ratiod(v0[1], v1[1], v[1]);
return (c2 >= 0 && c2 <= 1);
else {
if (LRT_DOUBLE_CLOSE_ENOUGH(v[0], v1[0])) {
c2 = ratiod(v0[1], v1[1], v[1]);
return (c2 >= -DBL_TRIANGLE_LIM && c2 <= 1 + DBL_TRIANGLE_LIM);
}
else {
return false;
}
}
if (v1[1] - v0[1]) {
if (!LRT_DOUBLE_CLOSE_ENOUGH(v1[1], v0[1])) {
c2 = ratiod(v0[1], v1[1], v[1]);
}
else if (v[1] == v1[1]) {
c1 = ratiod(v0[0], v1[0], v[0]);
return (c1 >= 0 && c1 <= 1);
else {
if (LRT_DOUBLE_CLOSE_ENOUGH(v[1], v1[1])) {
c1 = ratiod(v0[0], v1[0], v[0]);
return (c1 >= -DBL_TRIANGLE_LIM && c1 <= 1 + DBL_TRIANGLE_LIM);
}
else {
return false;
}
}
if (LRT_DOUBLE_CLOSE_ENOUGH(c1, c2) && c1 >= 0 && c1 <= 1) {
@ -1529,7 +1543,7 @@ static uint16_t lineart_identify_feature_line(LineartRenderBuffer *rb,
dot_1 = dot_v3v3_db(view_vector, tri1->gn);
dot_2 = dot_v3v3_db(view_vector, tri2->gn);
if ((result = dot_1 * dot_2) <= 0 && (dot_1 + dot_2)) {
if ((result = dot_1 * dot_2) <= 0 && (fabs(dot_1) + fabs(dot_2))) {
edge_flag_result |= LRT_EDGE_FLAG_CONTOUR;
}
@ -2305,7 +2319,7 @@ static bool lineart_edge_from_triangle(const LineartTriangle *tri,
{ \
index = (num < is[order[0]] ? \
order[0] : \
(num < is[order[1]] ? order[1] : (num < is[order[2]] ? order[2] : order[2]))); \
(num < is[order[1]] ? order[1] : (num < is[order[2]] ? order[2] : -1))); \
}
/* `ia ib ic` are ordered. */
@ -2313,7 +2327,7 @@ static bool lineart_edge_from_triangle(const LineartTriangle *tri,
{ \
index = (num > is[order[2]] ? \
order[2] : \
(num > is[order[1]] ? order[1] : (num > is[order[0]] ? order[0] : order[0]))); \
(num > is[order[1]] ? order[1] : (num > is[order[0]] ? order[0] : -1))); \
}
/**
@ -2321,6 +2335,22 @@ static bool lineart_edge_from_triangle(const LineartTriangle *tri,
* the occlusion status between 1(one) triangle and 1(one) line.
* if returns true, then from/to will carry the occluded segments
* in ratio from `e->v1` to `e->v2`. The line is later cut with these two values.
*
* TODO: (Yiming) This function uses a convoluted method that needs to be redesigned.
*
* 1) The lineart_intersect_seg_seg() and lineart_point_triangle_relation() are separate calls,
* which would potentially return results that doesn't agree, especially when it's an edge
* extruding from one of the triangle's point. To get the information using one math process can
* solve this problem.
*
* 2) Currently using discrete a/b/c/pa/pb/pc/is[3] values for storing
* intersection/edge_aligned/intersection_order info, which isn't optimal, needs a better
* representation (likely a struct) for readability and clarity of code path.
*
* I keep this function as-is because it's still fast, and more importantly the output value
* threshold is already in tune with the cutting function in the next stage.
* While current "edge aligned" fix isn't ideal, it does solve most of the precision issue
* especially in ortho camera mode.
*/
static bool lineart_triangle_edge_image_space_occlusion(SpinLock *UNUSED(spl),
const LineartTriangle *tri,
@ -2338,7 +2368,8 @@ static bool lineart_triangle_edge_image_space_occlusion(SpinLock *UNUSED(spl),
double is[3] = {0};
int order[3];
int LCross = -1, RCross = -1;
int a, b, c;
int a, b, c; /* Crossing info. */
bool pa, pb, pc; /* Parallel info. */
int st_l = 0, st_r = 0;
double Lv[3];
@ -2368,9 +2399,9 @@ static bool lineart_triangle_edge_image_space_occlusion(SpinLock *UNUSED(spl),
}
/* Check if the line visually crosses one of the edge in the triangle. */
a = lineart_LineIntersectTest2d(LFBC, RFBC, FBC0, FBC1, &is[0]);
b = lineart_LineIntersectTest2d(LFBC, RFBC, FBC1, FBC2, &is[1]);
c = lineart_LineIntersectTest2d(LFBC, RFBC, FBC2, FBC0, &is[2]);
a = lineart_intersect_seg_seg(LFBC, RFBC, FBC0, FBC1, &is[0], &pa);
b = lineart_intersect_seg_seg(LFBC, RFBC, FBC1, FBC2, &is[1], &pb);
c = lineart_intersect_seg_seg(LFBC, RFBC, FBC2, FBC0, &is[2], &pc);
/* Sort the intersection distance. */
INTERSECT_SORT_MIN_TO_MAX_3(is[0], is[1], is[2], order);
@ -2402,13 +2433,16 @@ static bool lineart_triangle_edge_image_space_occlusion(SpinLock *UNUSED(spl),
return false;
}
/* If the edge doesn't visually cross any edge of the triangle... */
if (!a && !b && !c) {
/* And if both end point from the edge is outside of the triangle... */
if (!(st_l = lineart_point_triangle_relation(LFBC, FBC0, FBC1, FBC2)) &&
!(st_r = lineart_point_triangle_relation(RFBC, FBC0, FBC1, FBC2))) {
return 0; /* Intersection point is not inside triangle. */
return 0; /* We don't have any occlusion. */
}
}
/* Whether two end points are inside/on_the_edge/outside of the triangle. */
st_l = lineart_point_triangle_relation(LFBC, FBC0, FBC1, FBC2);
st_r = lineart_point_triangle_relation(RFBC, FBC0, FBC1, FBC2);
@ -2455,60 +2489,96 @@ static bool lineart_triangle_edge_image_space_occlusion(SpinLock *UNUSED(spl),
cut = ratiod(e->v1->fbcoord[1], e->v2->fbcoord[1], trans[1]);
}
/* Determine the pair of edges that the line has crossed. */
#define LRT_GUARD_NOT_FOUND \
if (LCross < 0 || RCross < 0) { \
return false; \
}
/* Determine the pair of edges that the line has crossed. The "|" symbol in the comment indicates
* triangle boundary. DBL_TRIANGLE_LIM is needed to for floating point precision tolerance. */
if (st_l == 2) {
/* Left side is in the triangle. */
if (st_r == 2) {
/* | l---r | */
INTERSECT_JUST_SMALLER(is, order, DBL_TRIANGLE_LIM, LCross);
INTERSECT_JUST_GREATER(is, order, 1 - DBL_TRIANGLE_LIM, RCross);
}
else if (st_r == 1) {
/* | l------r| */
INTERSECT_JUST_SMALLER(is, order, DBL_TRIANGLE_LIM, LCross);
INTERSECT_JUST_GREATER(is, order, 1 - DBL_TRIANGLE_LIM, RCross);
}
else if (st_r == 0) {
/* | l-------|------r */
INTERSECT_JUST_SMALLER(is, order, DBL_TRIANGLE_LIM, LCross);
INTERSECT_JUST_GREATER(is, order, 0, RCross);
}
}
else if (st_l == 1) {
/* Left side is on some edge of the triangle. */
if (st_r == 2) {
/* |l------r | */
INTERSECT_JUST_SMALLER(is, order, DBL_TRIANGLE_LIM, LCross);
INTERSECT_JUST_GREATER(is, order, 1 - DBL_TRIANGLE_LIM, RCross);
}
else if (st_r == 1) {
/* |l---------r| */
INTERSECT_JUST_SMALLER(is, order, DBL_TRIANGLE_LIM, LCross);
INTERSECT_JUST_GREATER(is, order, 1 - DBL_TRIANGLE_LIM, RCross);
}
else if (st_r == 0) {
/* |l----------|-------r (crossing the triangle) [OR]
* r---------|l | (not crossing the triangle) */
INTERSECT_JUST_GREATER(is, order, DBL_TRIANGLE_LIM, RCross);
if (LRT_ABC(RCross) && is[RCross] > (DBL_TRIANGLE_LIM)) {
if (RCross >= 0 && LRT_ABC(RCross) && is[RCross] > (DBL_TRIANGLE_LIM)) {
INTERSECT_JUST_SMALLER(is, order, DBL_TRIANGLE_LIM, LCross);
}
else {
INTERSECT_JUST_SMALLER(is, order, -DBL_TRIANGLE_LIM, LCross);
INTERSECT_JUST_GREATER(is, order, -DBL_TRIANGLE_LIM, RCross);
INTERSECT_JUST_SMALLER(is, order, DBL_TRIANGLE_LIM, RCross);
if (RCross > 0) {
INTERSECT_JUST_SMALLER(is, order, is[RCross], LCross);
}
}
LRT_GUARD_NOT_FOUND
/* We could have the edge being completely parallel to the triangle where there isn't a
* viable occlusion result. */
if ((LRT_PABC(LCross) && !LRT_ABC(LCross)) || (LRT_PABC(RCross) && !LRT_ABC(RCross))) {
return false;
}
}
}
else if (st_l == 0) {
/* Left side is outside of the triangle. */
if (st_r == 2) {
/* l---|---r | */
INTERSECT_JUST_SMALLER(is, order, 1 - DBL_TRIANGLE_LIM, LCross);
INTERSECT_JUST_GREATER(is, order, 1 - DBL_TRIANGLE_LIM, RCross);
}
else if (st_r == 1) {
/* |r----------|-------l (crossing the triangle) [OR]
* l---------|r | (not crossing the triangle) */
INTERSECT_JUST_SMALLER(is, order, 1 - DBL_TRIANGLE_LIM, LCross);
if (LRT_ABC(LCross) && is[LCross] < (1 - DBL_TRIANGLE_LIM)) {
if (LCross >= 0 && LRT_ABC(LCross) && is[LCross] < (1 - DBL_TRIANGLE_LIM)) {
INTERSECT_JUST_GREATER(is, order, 1 - DBL_TRIANGLE_LIM, RCross);
}
else {
INTERSECT_JUST_SMALLER(is, order, 1 + DBL_TRIANGLE_LIM, LCross);
INTERSECT_JUST_GREATER(is, order, 1 + DBL_TRIANGLE_LIM, RCross);
INTERSECT_JUST_GREATER(is, order, 1 - DBL_TRIANGLE_LIM, LCross);
if (LCross > 0) {
INTERSECT_JUST_GREATER(is, order, is[LCross], RCross);
}
}
LRT_GUARD_NOT_FOUND
/* The same logic applies as above case. */
if ((LRT_PABC(LCross) && !LRT_ABC(LCross)) || (LRT_PABC(RCross) && !LRT_ABC(RCross))) {
return false;
}
}
else if (st_r == 0) {
INTERSECT_JUST_GREATER(is, order, DBL_TRIANGLE_LIM, LCross);
if (LRT_ABC(LCross) && is[LCross] > DBL_TRIANGLE_LIM) {
/* l---|----|----r (crossing the triangle) [OR]
* l----r | | (not crossing the triangle) */
INTERSECT_JUST_GREATER(is, order, -DBL_TRIANGLE_LIM, LCross);
if (LCross >= 0 && LRT_ABC(LCross)) {
INTERSECT_JUST_GREATER(is, order, is[LCross], RCross);
}
else {
@ -2518,6 +2588,8 @@ static bool lineart_triangle_edge_image_space_occlusion(SpinLock *UNUSED(spl),
}
}
LRT_GUARD_NOT_FOUND
double LF = dot_l * dot_f, RF = dot_r * dot_f;
/* Determine the start and end point of image space cut on a line. */
@ -2938,7 +3010,7 @@ static void lineart_triangle_intersect_in_bounding_area(LineartRenderBuffer *rb,
*/
static void lineart_main_get_view_vector(LineartRenderBuffer *rb)
{
float direction[3] = {0, 0, 1};
float direction[3] = {0, 0, -1};
float trans[3];
float inv[4][4];
float obmat_no_scale[4][4];
@ -3827,25 +3899,26 @@ static LineartBoundingArea *lineart_edge_first_bounding_area(LineartRenderBuffer
double data[2] = {e->v1->fbcoord[0], e->v1->fbcoord[1]};
double LU[2] = {-1, 1}, RU[2] = {1, 1}, LB[2] = {-1, -1}, RB[2] = {1, -1};
double r = 1, sr = 1;
bool p_unused;
if (data[0] > -1 && data[0] < 1 && data[1] > -1 && data[1] < 1) {
return lineart_get_bounding_area(rb, data[0], data[1]);
}
if (lineart_LineIntersectTest2d(e->v1->fbcoord, e->v2->fbcoord, LU, RU, &sr) && sr < r &&
sr > 0) {
if (lineart_intersect_seg_seg(e->v1->fbcoord, e->v2->fbcoord, LU, RU, &sr, &p_unused) &&
sr < r && sr > 0) {
r = sr;
}
if (lineart_LineIntersectTest2d(e->v1->fbcoord, e->v2->fbcoord, LB, RB, &sr) && sr < r &&
sr > 0) {
if (lineart_intersect_seg_seg(e->v1->fbcoord, e->v2->fbcoord, LB, RB, &sr, &p_unused) &&
sr < r && sr > 0) {
r = sr;
}
if (lineart_LineIntersectTest2d(e->v1->fbcoord, e->v2->fbcoord, LB, LU, &sr) && sr < r &&
sr > 0) {
if (lineart_intersect_seg_seg(e->v1->fbcoord, e->v2->fbcoord, LB, LU, &sr, &p_unused) &&
sr < r && sr > 0) {
r = sr;
}
if (lineart_LineIntersectTest2d(e->v1->fbcoord, e->v2->fbcoord, RB, RU, &sr) && sr < r &&
sr > 0) {
if (lineart_intersect_seg_seg(e->v1->fbcoord, e->v2->fbcoord, RB, RU, &sr, &p_unused) &&
sr < r && sr > 0) {
r = sr;
}
interp_v2_v2v2_db(data, e->v1->fbcoord, e->v2->fbcoord, r);