diff options
Diffstat (limited to 'source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c')
| -rw-r--r-- | source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c | 3027 |
1 files changed, 1805 insertions, 1222 deletions
diff --git a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c index 016b70cedb0..874da3b88c9 100644 --- a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c +++ b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c @@ -39,6 +39,7 @@ #include "DNA_camera_types.h" #include "DNA_collection_types.h" #include "DNA_gpencil_types.h" +#include "DNA_light_types.h" #include "DNA_material_types.h" #include "DNA_mesh_types.h" #include "DNA_meshdata_types.h" @@ -46,105 +47,117 @@ #include "DNA_scene_types.h" #include "MEM_guardedalloc.h" -#include "bmesh.h" -#include "bmesh_class.h" -#include "bmesh_tools.h" - #include "lineart_intern.h" -static LineartBoundingArea *lineart_edge_first_bounding_area(LineartRenderBuffer *rb, - LineartEdge *e); - -static void lineart_bounding_area_link_edge(LineartRenderBuffer *rb, +typedef struct LineartIsecSingle { + float v1[3], v2[3]; + LineartTriangle *tri1, *tri2; +} LineartIsecSingle; + +typedef struct LineartIsecThread { + int thread_id; + + /* Scheduled work range. */ + LineartElementLinkNode *pending_from; + LineartElementLinkNode *pending_to; + int index_from; + int index_to; + + /* Thread intersection result data. */ + LineartIsecSingle *array; + int current; + int max; + int count_test; + + /* For individual thread reference.*/ + LineartData *ld; +} LineartIsecThread; + +typedef struct LineartIsecData { + LineartData *ld; + LineartIsecThread *threads; + int thread_count; +} LineartIsecData; + +static void lineart_bounding_area_link_edge(LineartData *ld, LineartBoundingArea *root_ba, LineartEdge *e); -static LineartBoundingArea *lineart_bounding_area_next(LineartBoundingArea *this, - LineartEdge *e, - double x, - double y, - double k, - int positive_x, - int positive_y, - double *next_x, - double *next_y); - -static bool lineart_get_edge_bounding_areas(LineartRenderBuffer *rb, - LineartEdge *e, - int *rowbegin, - int *rowend, - int *colbegin, - int *colend); - -static void lineart_bounding_area_link_triangle(LineartRenderBuffer *rb, - LineartBoundingArea *root_ba, - LineartTriangle *tri, - double *LRUB, - int recursive, - int recursive_level, - bool do_intersection); +static bool lineart_get_edge_bounding_areas( + LineartData *ld, LineartEdge *e, int *rowbegin, int *rowend, int *colbegin, int *colend); -static bool lineart_triangle_edge_image_space_occlusion(SpinLock *spl, - const LineartTriangle *tri, +static bool lineart_triangle_edge_image_space_occlusion(const LineartTriangle *tri, const LineartEdge *e, const double *override_camera_loc, const bool override_cam_is_persp, const bool allow_overlapping_edges, - const double vp[4][4], - const double *camera_dir, + const double m_view_projection[4][4], + const double camera_dir[3], const float cam_shift_x, const float cam_shift_y, double *from, double *to); -static void lineart_add_edge_to_array(LineartPendingEdges *pe, LineartEdge *e); +static void lineart_bounding_area_link_triangle(LineartData *ld, + LineartBoundingArea *root_ba, + LineartTriangle *tri, + double l_r_u_b[4], + int recursive, + int recursive_level, + bool do_intersection, + struct LineartIsecThread *th); + +static void lineart_free_bounding_area_memory(LineartBoundingArea *ba, bool recursive); + +static void lineart_free_bounding_area_memories(LineartData *ld); static LineartCache *lineart_init_cache(void); -static void lineart_discard_segment(LineartRenderBuffer *rb, LineartEdgeSegment *es) +static void lineart_discard_segment(LineartData *ld, LineartEdgeSegment *es) { - BLI_spin_lock(&rb->lock_cuts); + BLI_spin_lock(&ld->lock_cuts); memset(es, 0, sizeof(LineartEdgeSegment)); /* Storing the node for potentially reuse the memory for new segment data. * Line Art data is not freed after all calculations are done. */ - BLI_addtail(&rb->wasted_cuts, es); + BLI_addtail(&ld->wasted_cuts, es); - BLI_spin_unlock(&rb->lock_cuts); + BLI_spin_unlock(&ld->lock_cuts); } -static LineartEdgeSegment *lineart_give_segment(LineartRenderBuffer *rb) +static LineartEdgeSegment *lineart_give_segment(LineartData *ld) { - BLI_spin_lock(&rb->lock_cuts); + BLI_spin_lock(&ld->lock_cuts); /* See if there is any already allocated memory we can reuse. */ - if (rb->wasted_cuts.first) { - LineartEdgeSegment *es = (LineartEdgeSegment *)BLI_pophead(&rb->wasted_cuts); - BLI_spin_unlock(&rb->lock_cuts); + if (ld->wasted_cuts.first) { + LineartEdgeSegment *es = (LineartEdgeSegment *)BLI_pophead(&ld->wasted_cuts); + BLI_spin_unlock(&ld->lock_cuts); memset(es, 0, sizeof(LineartEdgeSegment)); return es; } - BLI_spin_unlock(&rb->lock_cuts); + BLI_spin_unlock(&ld->lock_cuts); /* Otherwise allocate some new memory. */ - return (LineartEdgeSegment *)lineart_mem_acquire_thread(&rb->render_data_pool, + return (LineartEdgeSegment *)lineart_mem_acquire_thread(ld->edge_data_pool, sizeof(LineartEdgeSegment)); } /** * Cuts the edge in image space and mark occlusion level for each segment. */ -static void lineart_edge_cut(LineartRenderBuffer *rb, - LineartEdge *e, - double start, - double end, - uchar material_mask_bits, - uchar mat_occlusion) +void lineart_edge_cut(LineartData *ld, + LineartEdge *e, + double start, + double end, + uchar material_mask_bits, + uchar mat_occlusion, + uint32_t shadow_bits) { - LineartEdgeSegment *es, *ies, *next_es, *prev_es; + LineartEdgeSegment *seg, *i_seg, *next_seg, *prev_seg; LineartEdgeSegment *cut_start_before = 0, *cut_end_before = 0; - LineartEdgeSegment *ns = 0, *ns2 = 0; + LineartEdgeSegment *new_seg1 = 0, *new_seg2 = 0; int untouched = 0; /* If for some reason the occlusion function may give a result that has zero length, or reversed @@ -171,132 +184,159 @@ static void lineart_edge_cut(LineartRenderBuffer *rb, /* Begin looking for starting position of the segment. */ /* Not using a list iteration macro because of it more clear when using for loops to iterate * through the segments. */ - for (es = e->segments.first; es; es = es->next) { - if (LRT_DOUBLE_CLOSE_ENOUGH(es->at, start)) { - cut_start_before = es; - ns = cut_start_before; + for (seg = e->segments.first; seg; seg = seg->next) { + if (LRT_DOUBLE_CLOSE_ENOUGH(seg->ratio, start)) { + cut_start_before = seg; + new_seg1 = cut_start_before; break; } - if (es->next == NULL) { + if (seg->next == NULL) { break; } - ies = es->next; - if (ies->at > start + 1e-09 && start > es->at) { - cut_start_before = ies; - ns = lineart_give_segment(rb); + i_seg = seg->next; + if (i_seg->ratio > start + 1e-09 && start > seg->ratio) { + cut_start_before = i_seg; + new_seg1 = lineart_give_segment(ld); break; } } if (!cut_start_before && LRT_DOUBLE_CLOSE_ENOUGH(1, end)) { untouched = 1; } - for (es = cut_start_before; es; es = es->next) { - /* We tried to cut at existing cutting point (e.g. where the line's occluded by a triangle + for (seg = cut_start_before; seg; seg = seg->next) { + /* We tried to cut ratio existing cutting point (e.g. where the line's occluded by a triangle * strip). */ - if (LRT_DOUBLE_CLOSE_ENOUGH(es->at, end)) { - cut_end_before = es; - ns2 = cut_end_before; + if (LRT_DOUBLE_CLOSE_ENOUGH(seg->ratio, end)) { + cut_end_before = seg; + new_seg2 = cut_end_before; break; } - /* This check is to prevent `es->at == 1.0` (where we don't need to cut because we are at the - * end point). */ - if (!es->next && LRT_DOUBLE_CLOSE_ENOUGH(1, end)) { - cut_end_before = es; - ns2 = cut_end_before; + /* This check is to prevent `es->ratio == 1.0` (where we don't need to cut because we are ratio + * the end point). */ + if (!seg->next && LRT_DOUBLE_CLOSE_ENOUGH(1, end)) { + cut_end_before = seg; + new_seg2 = cut_end_before; untouched = 1; break; } /* When an actual cut is needed in the line. */ - if (es->at > end) { - cut_end_before = es; - ns2 = lineart_give_segment(rb); + if (seg->ratio > end) { + cut_end_before = seg; + new_seg2 = lineart_give_segment(ld); break; } } /* When we still can't find any existing cut in the line, we allocate new ones. */ - if (ns == NULL) { - ns = lineart_give_segment(rb); + if (new_seg1 == NULL) { + new_seg1 = lineart_give_segment(ld); } - if (ns2 == NULL) { + if (new_seg2 == NULL) { if (untouched) { - ns2 = ns; - cut_end_before = ns2; + new_seg2 = new_seg1; + cut_end_before = new_seg2; } else { - ns2 = lineart_give_segment(rb); + new_seg2 = lineart_give_segment(ld); } } if (cut_start_before) { - if (cut_start_before != ns) { + if (cut_start_before != new_seg1) { /* Insert cutting points for when a new cut is needed. */ - ies = cut_start_before->prev ? cut_start_before->prev : NULL; - ns->occlusion = ies ? ies->occlusion : 0; - ns->material_mask_bits = ies->material_mask_bits; - BLI_insertlinkbefore(&e->segments, cut_start_before, ns); + i_seg = cut_start_before->prev ? cut_start_before->prev : NULL; + if (i_seg) { + new_seg1->occlusion = i_seg->occlusion; + new_seg1->material_mask_bits = i_seg->material_mask_bits; + new_seg1->shadow_mask_bits = i_seg->shadow_mask_bits; + } + BLI_insertlinkbefore(&e->segments, cut_start_before, new_seg1); } /* Otherwise we already found a existing cutting point, no need to insert a new one. */ } else { /* We have yet to reach a existing cutting point even after we searched the whole line, so we * append the new cut to the end. */ - ies = e->segments.last; - ns->occlusion = ies->occlusion; - ns->material_mask_bits = ies->material_mask_bits; - BLI_addtail(&e->segments, ns); + i_seg = e->segments.last; + new_seg1->occlusion = i_seg->occlusion; + new_seg1->material_mask_bits = i_seg->material_mask_bits; + new_seg1->shadow_mask_bits = i_seg->shadow_mask_bits; + BLI_addtail(&e->segments, new_seg1); } if (cut_end_before) { /* The same manipulation as on "cut_start_before". */ - if (cut_end_before != ns2) { - ies = cut_end_before->prev ? cut_end_before->prev : NULL; - ns2->occlusion = ies ? ies->occlusion : 0; - ns2->material_mask_bits = ies ? ies->material_mask_bits : 0; - BLI_insertlinkbefore(&e->segments, cut_end_before, ns2); + if (cut_end_before != new_seg2) { + i_seg = cut_end_before->prev ? cut_end_before->prev : NULL; + if (i_seg) { + new_seg2->occlusion = i_seg->occlusion; + new_seg2->material_mask_bits = i_seg->material_mask_bits; + new_seg2->shadow_mask_bits = i_seg->shadow_mask_bits; + } + BLI_insertlinkbefore(&e->segments, cut_end_before, new_seg2); } } else { - ies = e->segments.last; - ns2->occlusion = ies->occlusion; - ns2->material_mask_bits = ies->material_mask_bits; - BLI_addtail(&e->segments, ns2); + i_seg = e->segments.last; + new_seg2->occlusion = i_seg->occlusion; + new_seg2->material_mask_bits = i_seg->material_mask_bits; + new_seg2->shadow_mask_bits = i_seg->shadow_mask_bits; + if (!untouched) { + BLI_addtail(&e->segments, new_seg2); + } } /* If we touched the cut list, we assign the new cut position based on new cut position, * this way we accommodate precision lost due to multiple cut inserts. */ - ns->at = start; + new_seg1->ratio = start; if (!untouched) { - ns2->at = end; + new_seg2->ratio = end; } else { /* For the convenience of the loop below. */ - ns2 = ns2->next; + new_seg2 = new_seg2->next; } /* Register 1 level of occlusion for all touched segments. */ - for (es = ns; es && es != ns2; es = es->next) { - es->occlusion += mat_occlusion; - es->material_mask_bits |= material_mask_bits; + for (seg = new_seg1; seg && seg != new_seg2; seg = seg->next) { + seg->occlusion += mat_occlusion; + seg->material_mask_bits |= material_mask_bits; + + /* The enclosed shape flag will override regular lit/shaded + * flags. See LineartEdgeSegment::shadow_mask_bits for details. */ + if (shadow_bits == LRT_SHADOW_MASK_ENCLOSED_SHAPE) { + if (seg->shadow_mask_bits & LRT_SHADOW_MASK_LIT || e->flags & LRT_EDGE_FLAG_LIGHT_CONTOUR) { + seg->shadow_mask_bits &= ~LRT_SHADOW_MASK_LIT; + seg->shadow_mask_bits |= LRT_SHADOW_MASK_INHIBITED; + } + else if (seg->shadow_mask_bits & LRT_SHADOW_MASK_SHADED) { + seg->shadow_mask_bits &= ~LRT_SHADOW_MASK_SHADED; + seg->shadow_mask_bits |= LRT_SHADOW_MASK_LIT; + } + } + else { + seg->shadow_mask_bits |= shadow_bits; + } } /* Reduce adjacent cutting points of the same level, which saves memory. */ - char min_occ = 127; - prev_es = NULL; - for (es = e->segments.first; es; es = next_es) { - next_es = es->next; - - if (prev_es && prev_es->occlusion == es->occlusion && - prev_es->material_mask_bits == es->material_mask_bits) { - BLI_remlink(&e->segments, es); + int8_t min_occ = 127; + prev_seg = NULL; + for (seg = e->segments.first; seg; seg = next_seg) { + next_seg = seg->next; + + if (prev_seg && prev_seg->occlusion == seg->occlusion && + prev_seg->material_mask_bits == seg->material_mask_bits && + prev_seg->shadow_mask_bits == seg->shadow_mask_bits) { + BLI_remlink(&e->segments, seg); /* This puts the node back to the render buffer, if more cut happens, these unused nodes get * picked first. */ - lineart_discard_segment(rb, es); + lineart_discard_segment(ld, seg); continue; } - min_occ = MIN2(min_occ, es->occlusion); + min_occ = MIN2(min_occ, seg->occlusion); - prev_es = es; + prev_seg = seg; } e->min_occ = min_occ; } @@ -306,35 +346,18 @@ static void lineart_edge_cut(LineartRenderBuffer *rb, */ BLI_INLINE bool lineart_occlusion_is_adjacent_intersection(LineartEdge *e, LineartTriangle *tri) { - LineartVertIntersection *v1 = (void *)e->v1; - LineartVertIntersection *v2 = (void *)e->v2; - return ((v1->base.flag && v1->intersecting_with == tri) || - (v2->base.flag && v2->intersecting_with == tri)); + return (((e->target_reference & LRT_LIGHT_CONTOUR_TARGET) == tri->target_reference) || + (((e->target_reference >> 32) & LRT_LIGHT_CONTOUR_TARGET) == tri->target_reference)); } -static void lineart_bounding_area_triangle_add(LineartRenderBuffer *rb, - LineartBoundingArea *ba, - LineartTriangle *tri) -{ /* In case of too many triangles concentrating in one point, do not add anymore, these triangles - * will be either narrower than a single pixel, or will still be added into the list of other - * less dense areas. */ - if (ba->triangle_count >= 65535) { - return; - } - 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_triangle_reallocate(LineartBoundingArea *ba) +{ + ba->max_triangle_count *= 2; + ba->linked_triangles = MEM_recallocN(ba->linked_triangles, + sizeof(LineartTriangle *) * ba->max_triangle_count); } -static void lineart_bounding_area_line_add(LineartRenderBuffer *rb, - LineartBoundingArea *ba, - LineartEdge *e) +static void lineart_bounding_area_line_add(LineartBoundingArea *ba, LineartEdge *e) { /* In case of too many lines concentrating in one point, do not add anymore, these lines will * be either shorter than a single pixel, or will still be added into the list of other less @@ -343,36 +366,23 @@ static void lineart_bounding_area_line_add(LineartRenderBuffer *rb, return; } 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); + LineartEdge **new_array = MEM_mallocN(sizeof(LineartEdge *) * ba->max_line_count * 2, + "new ba_line_array"); memcpy(new_array, ba->linked_lines, sizeof(LineartEdge *) * ba->max_line_count); ba->max_line_count *= 2; + MEM_freeN(ba->linked_lines); 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) +static void lineart_occlusion_single_line(LineartData *ld, LineartEdge *e, int thread_id) { - double x = e->v1->fbcoord[0], y = e->v1->fbcoord[1]; - LineartBoundingArea *ba = lineart_edge_first_bounding_area(rb, e); - LineartBoundingArea *nba = ba; LineartTriangleThread *tri; - - /* These values are used for marching along the line. */ double l, r; - double k = (e->v2->fbcoord[1] - e->v1->fbcoord[1]) / - (e->v2->fbcoord[0] - e->v1->fbcoord[0] + 1e-30); - int positive_x = (e->v2->fbcoord[0] - e->v1->fbcoord[0]) > 0 ? - 1 : - (e->v2->fbcoord[0] == e->v1->fbcoord[0] ? 0 : -1); - int positive_y = (e->v2->fbcoord[1] - e->v1->fbcoord[1]) > 0 ? - 1 : - (e->v2->fbcoord[1] == e->v1->fbcoord[1] ? 0 : -1); - - while (nba) { - + LRT_EDGE_BA_MARCHING_BEGIN(e->v1->fbcoord, e->v2->fbcoord) + { 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. */ @@ -385,49 +395,48 @@ static void lineart_occlusion_single_line(LineartRenderBuffer *rb, LineartEdge * continue; } tri->testing_e[thread_id] = e; - if (lineart_triangle_edge_image_space_occlusion(&rb->lock_task, - (const LineartTriangle *)tri, + if (lineart_triangle_edge_image_space_occlusion((const LineartTriangle *)tri, e, - rb->camera_pos, - rb->cam_is_persp, - rb->allow_overlapping_edges, - rb->view_projection, - rb->view_vector, - rb->shift_x, - rb->shift_y, + ld->conf.camera_pos, + ld->conf.cam_is_persp, + ld->conf.allow_overlapping_edges, + ld->conf.view_projection, + ld->conf.view_vector, + ld->conf.shift_x, + ld->conf.shift_y, &l, &r)) { - lineart_edge_cut(rb, e, l, r, tri->base.material_mask_bits, tri->base.mat_occlusion); - if (e->min_occ > rb->max_occlusion_level) { + lineart_edge_cut(ld, e, l, r, tri->base.material_mask_bits, tri->base.mat_occlusion, 0); + if (e->min_occ > ld->conf.max_occlusion_level) { /* No need to calculate any longer on this line because no level more than set value is * going to show up in the rendered result. */ return; } } } - /* Marching along `e->v1` to `e->v2`, searching each possible bounding areas it may touch. */ - nba = lineart_bounding_area_next(nba, e, x, y, k, positive_x, positive_y, &x, &y); + LRT_EDGE_BA_MARCHING_NEXT(e->v1->fbcoord, e->v2->fbcoord) } + LRT_EDGE_BA_MARCHING_END } -static int lineart_occlusion_make_task_info(LineartRenderBuffer *rb, LineartRenderTaskInfo *rti) +static int lineart_occlusion_make_task_info(LineartData *ld, LineartRenderTaskInfo *rti) { int res = 0; int starting_index; - BLI_spin_lock(&rb->lock_task); + BLI_spin_lock(&ld->lock_task); - starting_index = rb->scheduled_count; - rb->scheduled_count += LRT_THREAD_EDGE_COUNT; + starting_index = ld->scheduled_count; + ld->scheduled_count += LRT_THREAD_EDGE_COUNT; - BLI_spin_unlock(&rb->lock_task); + BLI_spin_unlock(&ld->lock_task); - if (starting_index >= rb->pending_edges.next) { + if (starting_index >= ld->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.array = &ld->pending_edges.array[starting_index]; + int remaining = ld->pending_edges.next - starting_index; rti->pending_edges.max = MIN2(remaining, LRT_THREAD_EDGE_COUNT); res = 1; } @@ -437,13 +446,13 @@ static int lineart_occlusion_make_task_info(LineartRenderBuffer *rb, LineartRend static void lineart_occlusion_worker(TaskPool *__restrict UNUSED(pool), LineartRenderTaskInfo *rti) { - LineartRenderBuffer *rb = rti->rb; + LineartData *ld = rti->ld; LineartEdge *eip; - while (lineart_occlusion_make_task_info(rb, rti)) { + while (lineart_occlusion_make_task_info(ld, rti)) { 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); + lineart_occlusion_single_line(ld, eip, rti->thread_id); } } } @@ -453,9 +462,9 @@ static void lineart_occlusion_worker(TaskPool *__restrict UNUSED(pool), LineartR * #MOD_lineart_compute_feature_lines function. * This function handles all occlusion calculation. */ -static void lineart_main_occlusion_begin(LineartRenderBuffer *rb) +void lineart_main_occlusion_begin(LineartData *ld) { - int thread_count = rb->thread_count; + int thread_count = ld->thread_count; LineartRenderTaskInfo *rti = MEM_callocN(sizeof(LineartRenderTaskInfo) * thread_count, "Task Pool"); int i; @@ -464,7 +473,7 @@ static void lineart_main_occlusion_begin(LineartRenderBuffer *rb) for (i = 0; i < thread_count; i++) { rti[i].thread_id = i; - rti[i].rb = rb; + rti[i].ld = ld; BLI_task_pool_push(tp, (TaskRunFunction)lineart_occlusion_worker, &rti[i], 0, NULL); } BLI_task_pool_work_and_wait(tp); @@ -485,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) { @@ -504,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; } @@ -554,6 +562,12 @@ static int lineart_point_on_line_segment(double v[2], double v0[2], double v1[2] return 0; } +enum LineartPointTri { + LRT_OUTSIDE_TRIANGLE = 0, + LRT_ON_TRIANGLE = 1, + LRT_INSIDE_TRIANGLE = 2, +}; + /** * Same algorithm as lineart_point_inside_triangle(), but returns differently: * 0-outside 1-on the edge 2-inside. @@ -564,7 +578,7 @@ static int lineart_point_triangle_relation(double v[2], double v0[2], double v1[ double r; if (lineart_point_on_line_segment(v, v0, v1) || lineart_point_on_line_segment(v, v1, v2) || lineart_point_on_line_segment(v, v2, v0)) { - return 1; + return LRT_ON_TRIANGLE; } cl = (v0[0] - v[0]) * (v1[1] - v[1]) - (v0[1] - v[1]) * (v1[0] - v[0]); @@ -572,28 +586,28 @@ static int lineart_point_triangle_relation(double v[2], double v0[2], double v1[ cl = (v1[0] - v[0]) * (v2[1] - v[1]) - (v1[1] - v[1]) * (v2[0] - v[0]); if ((r = c * cl) < 0) { - return 0; + return LRT_OUTSIDE_TRIANGLE; } c = cl; cl = (v2[0] - v[0]) * (v0[1] - v[1]) - (v2[1] - v[1]) * (v0[0] - v[0]); if ((r = c * cl) < 0) { - return 0; + return LRT_OUTSIDE_TRIANGLE; } c = cl; cl = (v0[0] - v[0]) * (v1[1] - v[1]) - (v0[1] - v[1]) * (v1[0] - v[0]); if ((r = c * cl) < 0) { - return 0; + return LRT_OUTSIDE_TRIANGLE; } if (r == 0) { - return 1; + return LRT_ON_TRIANGLE; } - return 2; + return LRT_INSIDE_TRIANGLE; } /** @@ -641,17 +655,17 @@ static bool lineart_point_inside_triangle3d(double v[3], double v0[3], double v1 * The following `lineart_memory_get_XXX_space` functions are for allocating new memory for some * modified geometries in the culling stage. */ -static LineartElementLinkNode *lineart_memory_get_triangle_space(LineartRenderBuffer *rb) +static LineartElementLinkNode *lineart_memory_get_triangle_space(LineartData *ld) { LineartElementLinkNode *eln; /* We don't need to allocate a whole bunch of triangles because the amount of clipped triangles * are relatively small. */ - LineartTriangle *render_triangles = lineart_mem_acquire(&rb->render_data_pool, - 64 * rb->triangle_size); + LineartTriangle *render_triangles = lineart_mem_acquire(&ld->render_data_pool, + 64 * ld->sizeof_triangle); - eln = lineart_list_append_pointer_pool_sized(&rb->triangle_buffer_pointers, - &rb->render_data_pool, + eln = lineart_list_append_pointer_pool_sized(&ld->geom.triangle_buffer_pointers, + &ld->render_data_pool, render_triangles, sizeof(LineartElementLinkNode)); eln->element_count = 64; @@ -660,15 +674,15 @@ static LineartElementLinkNode *lineart_memory_get_triangle_space(LineartRenderBu return eln; } -static LineartElementLinkNode *lineart_memory_get_vert_space(LineartRenderBuffer *rb) +static LineartElementLinkNode *lineart_memory_get_vert_space(LineartData *ld) { LineartElementLinkNode *eln; - LineartVert *render_vertices = lineart_mem_acquire(&rb->render_data_pool, + LineartVert *render_vertices = lineart_mem_acquire(&ld->render_data_pool, sizeof(LineartVert) * 64); - eln = lineart_list_append_pointer_pool_sized(&rb->vertex_buffer_pointers, - &rb->render_data_pool, + eln = lineart_list_append_pointer_pool_sized(&ld->geom.vertex_buffer_pointers, + &ld->render_data_pool, render_vertices, sizeof(LineartElementLinkNode)); eln->element_count = 64; @@ -677,18 +691,18 @@ static LineartElementLinkNode *lineart_memory_get_vert_space(LineartRenderBuffer return eln; } -static LineartElementLinkNode *lineart_memory_get_edge_space(LineartRenderBuffer *rb) +static LineartElementLinkNode *lineart_memory_get_edge_space(LineartData *ld) { LineartElementLinkNode *eln; - LineartEdge *render_edges = lineart_mem_acquire(&rb->render_data_pool, sizeof(LineartEdge) * 64); + LineartEdge *render_edges = lineart_mem_acquire(ld->edge_data_pool, sizeof(LineartEdge) * 64); - eln = lineart_list_append_pointer_pool_sized(&rb->line_buffer_pointers, - &rb->render_data_pool, + eln = lineart_list_append_pointer_pool_sized(&ld->geom.line_buffer_pointers, + ld->edge_data_pool, render_edges, sizeof(LineartElementLinkNode)); eln->element_count = 64; - eln->crease_threshold = rb->crease_threshold; + eln->crease_threshold = ld->conf.crease_threshold; eln->flags |= LRT_ELEMENT_IS_ADDITIONAL; return eln; @@ -699,8 +713,11 @@ static void lineart_triangle_post(LineartTriangle *tri, LineartTriangle *orig) /* Just re-assign normal and set cull flag. */ copy_v3_v3_db(tri->gn, orig->gn); tri->flags = LRT_CULL_GENERATED; + tri->intersection_mask = orig->intersection_mask; tri->material_mask_bits = orig->material_mask_bits; tri->mat_occlusion = orig->mat_occlusion; + tri->intersection_priority = orig->intersection_priority; + tri->target_reference = orig->target_reference; } static void lineart_triangle_set_cull_flag(LineartTriangle *tri, uchar flag) @@ -729,15 +746,15 @@ static void lineart_discard_duplicated_edges(LineartEdge *old_e) * Does near-plane cut on 1 triangle only. When cutting with far-plane, the camera vectors gets * reversed by the caller so don't need to implement one in a different direction. */ -static void lineart_triangle_cull_single(LineartRenderBuffer *rb, +static void lineart_triangle_cull_single(LineartData *ld, LineartTriangle *tri, int in0, int in1, int in2, - double *cam_pos, - double *view_dir, + double cam_pos[3], + double view_dir[3], bool allow_boundaries, - double (*vp)[4], + double m_view_projection[4][4], Object *ob, int *r_v_count, int *r_e_count, @@ -746,7 +763,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb, LineartElementLinkNode *e_eln, LineartElementLinkNode *t_eln) { - double vv1[3], vv2[3], dot1, dot2; + double span_v1[3], span_v2[3], dot_v1, dot_v2; double a; int v_count = *r_v_count; int e_count = *r_e_count; @@ -755,7 +772,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb, LineartEdge *new_e, *e, *old_e; LineartEdgeSegment *es; - LineartTriangleAdjacent *ta; + LineartTriangleAdjacent *tri_adj; if (tri->flags & (LRT_CULL_USED | LRT_CULL_GENERATED | LRT_CULL_DISCARD)) { return; @@ -763,11 +780,12 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb, /* See definition of tri->intersecting_verts and the usage in * lineart_geometry_object_load() for details. */ - ta = (void *)tri->intersecting_verts; + tri_adj = (void *)tri->intersecting_verts; LineartVert *vt = &((LineartVert *)v_eln->pointer)[v_count]; - LineartTriangle *tri1 = (void *)(((uchar *)t_eln->pointer) + rb->triangle_size * t_count); - LineartTriangle *tri2 = (void *)(((uchar *)t_eln->pointer) + rb->triangle_size * (t_count + 1)); + LineartTriangle *tri1 = (void *)(((uchar *)t_eln->pointer) + ld->sizeof_triangle * t_count); + LineartTriangle *tri2 = (void *)(((uchar *)t_eln->pointer) + + ld->sizeof_triangle * (t_count + 1)); new_e = &((LineartEdge *)e_eln->pointer)[e_count]; /* Init `edge` to the last `edge` entry. */ @@ -777,12 +795,12 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb, new_e = &((LineartEdge *)e_eln->pointer)[e_count]; \ e_count++; \ e = new_e; \ - es = lineart_mem_acquire(&rb->render_data_pool, sizeof(LineartEdgeSegment)); \ + es = lineart_mem_acquire(&ld->render_data_pool, sizeof(LineartEdgeSegment)); \ BLI_addtail(&e->segments, es); #define SELECT_EDGE(e_num, v1_link, v2_link, new_tri) \ - if (ta->e[e_num]) { \ - old_e = ta->e[e_num]; \ + if (tri_adj->e[e_num]) { \ + old_e = tri_adj->e[e_num]; \ new_flag = old_e->flags; \ old_e->flags = LRT_EDGE_FLAG_CHAIN_PICKED; \ lineart_discard_duplicated_edges(old_e); \ @@ -795,28 +813,28 @@ 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_array(&rb->pending_edges, e); \ + lineart_add_edge_to_array(&ld->pending_edges, e); \ } #define RELINK_EDGE(e_num, new_tri) \ - if (ta->e[e_num]) { \ - old_e = ta->e[e_num]; \ + if (tri_adj->e[e_num]) { \ + old_e = tri_adj->e[e_num]; \ old_e->t1 = ((old_e->t1 == tri) ? (new_tri) : (old_e->t1)); \ old_e->t2 = ((old_e->t2 == tri) ? (new_tri) : (old_e->t2)); \ } #define REMOVE_TRIANGLE_EDGE \ - if (ta->e[0]) { \ - ta->e[0]->flags = LRT_EDGE_FLAG_CHAIN_PICKED; \ - lineart_discard_duplicated_edges(ta->e[0]); \ + if (tri_adj->e[0]) { \ + tri_adj->e[0]->flags = LRT_EDGE_FLAG_CHAIN_PICKED; \ + lineart_discard_duplicated_edges(tri_adj->e[0]); \ } \ - if (ta->e[1]) { \ - ta->e[1]->flags = LRT_EDGE_FLAG_CHAIN_PICKED; \ - lineart_discard_duplicated_edges(ta->e[1]); \ + if (tri_adj->e[1]) { \ + tri_adj->e[1]->flags = LRT_EDGE_FLAG_CHAIN_PICKED; \ + lineart_discard_duplicated_edges(tri_adj->e[1]); \ } \ - if (ta->e[2]) { \ - ta->e[2]->flags = LRT_EDGE_FLAG_CHAIN_PICKED; \ - lineart_discard_duplicated_edges(ta->e[2]); \ + if (tri_adj->e[2]) { \ + tri_adj->e[2]->flags = LRT_EDGE_FLAG_CHAIN_PICKED; \ + lineart_discard_duplicated_edges(tri_adj->e[2]); \ } switch (in0 + in1 + in2) { @@ -856,32 +874,32 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb, if (!in0) { /* Cut point for line 2---|-----0. */ - sub_v3_v3v3_db(vv1, tri->v[0]->gloc, cam_pos); - sub_v3_v3v3_db(vv2, cam_pos, tri->v[2]->gloc); - dot1 = dot_v3v3_db(vv1, view_dir); - dot2 = dot_v3v3_db(vv2, view_dir); - a = dot1 / (dot1 + dot2); + sub_v3_v3v3_db(span_v1, tri->v[0]->gloc, cam_pos); + sub_v3_v3v3_db(span_v2, cam_pos, tri->v[2]->gloc); + dot_v1 = dot_v3v3_db(span_v1, view_dir); + dot_v2 = dot_v3v3_db(span_v2, view_dir); + a = dot_v1 / (dot_v1 + dot_v2); /* Assign it to a new point. */ interp_v3_v3v3_db(vt[0].gloc, tri->v[0]->gloc, tri->v[2]->gloc, a); - mul_v4_m4v3_db(vt[0].fbcoord, vp, vt[0].gloc); + mul_v4_m4v3_db(vt[0].fbcoord, m_view_projection, vt[0].gloc); vt[0].index = tri->v[2]->index; /* Cut point for line 1---|-----0. */ - sub_v3_v3v3_db(vv1, tri->v[0]->gloc, cam_pos); - sub_v3_v3v3_db(vv2, cam_pos, tri->v[1]->gloc); - dot1 = dot_v3v3_db(vv1, view_dir); - dot2 = dot_v3v3_db(vv2, view_dir); - a = dot1 / (dot1 + dot2); + sub_v3_v3v3_db(span_v1, tri->v[0]->gloc, cam_pos); + sub_v3_v3v3_db(span_v2, cam_pos, tri->v[1]->gloc); + dot_v1 = dot_v3v3_db(span_v1, view_dir); + dot_v2 = dot_v3v3_db(span_v2, view_dir); + a = dot_v1 / (dot_v1 + dot_v2); /* Assign it to another new point. */ interp_v3_v3v3_db(vt[1].gloc, tri->v[0]->gloc, tri->v[1]->gloc, a); - mul_v4_m4v3_db(vt[1].fbcoord, vp, vt[1].gloc); + mul_v4_m4v3_db(vt[1].fbcoord, m_view_projection, vt[1].gloc); vt[1].index = tri->v[1]->index; /* New line connecting two new points. */ INCREASE_EDGE if (allow_boundaries) { e->flags = LRT_EDGE_FLAG_CONTOUR; - lineart_add_edge_to_array(&rb->pending_edges, e); + lineart_add_edge_to_array(&ld->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 @@ -909,28 +927,28 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb, t_count += 1; } else if (!in2) { - sub_v3_v3v3_db(vv1, tri->v[2]->gloc, cam_pos); - sub_v3_v3v3_db(vv2, cam_pos, tri->v[0]->gloc); - dot1 = dot_v3v3_db(vv1, view_dir); - dot2 = dot_v3v3_db(vv2, view_dir); - a = dot1 / (dot1 + dot2); + sub_v3_v3v3_db(span_v1, tri->v[2]->gloc, cam_pos); + sub_v3_v3v3_db(span_v2, cam_pos, tri->v[0]->gloc); + dot_v1 = dot_v3v3_db(span_v1, view_dir); + dot_v2 = dot_v3v3_db(span_v2, view_dir); + a = dot_v1 / (dot_v1 + dot_v2); interp_v3_v3v3_db(vt[0].gloc, tri->v[2]->gloc, tri->v[0]->gloc, a); - mul_v4_m4v3_db(vt[0].fbcoord, vp, vt[0].gloc); + mul_v4_m4v3_db(vt[0].fbcoord, m_view_projection, vt[0].gloc); vt[0].index = tri->v[0]->index; - sub_v3_v3v3_db(vv1, tri->v[2]->gloc, cam_pos); - sub_v3_v3v3_db(vv2, cam_pos, tri->v[1]->gloc); - dot1 = dot_v3v3_db(vv1, view_dir); - dot2 = dot_v3v3_db(vv2, view_dir); - a = dot1 / (dot1 + dot2); + sub_v3_v3v3_db(span_v1, tri->v[2]->gloc, cam_pos); + sub_v3_v3v3_db(span_v2, cam_pos, tri->v[1]->gloc); + dot_v1 = dot_v3v3_db(span_v1, view_dir); + dot_v2 = dot_v3v3_db(span_v2, view_dir); + a = dot_v1 / (dot_v1 + dot_v2); interp_v3_v3v3_db(vt[1].gloc, tri->v[2]->gloc, tri->v[1]->gloc, a); - mul_v4_m4v3_db(vt[1].fbcoord, vp, vt[1].gloc); + mul_v4_m4v3_db(vt[1].fbcoord, m_view_projection, vt[1].gloc); vt[1].index = tri->v[1]->index; INCREASE_EDGE if (allow_boundaries) { e->flags = LRT_EDGE_FLAG_CONTOUR; - lineart_add_edge_to_array(&rb->pending_edges, e); + lineart_add_edge_to_array(&ld->pending_edges, e); } e->v1 = &vt[0]; e->v2 = &vt[1]; @@ -950,28 +968,28 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb, t_count += 1; } else if (!in1) { - sub_v3_v3v3_db(vv1, tri->v[1]->gloc, cam_pos); - sub_v3_v3v3_db(vv2, cam_pos, tri->v[2]->gloc); - dot1 = dot_v3v3_db(vv1, view_dir); - dot2 = dot_v3v3_db(vv2, view_dir); - a = dot1 / (dot1 + dot2); + sub_v3_v3v3_db(span_v1, tri->v[1]->gloc, cam_pos); + sub_v3_v3v3_db(span_v2, cam_pos, tri->v[2]->gloc); + dot_v1 = dot_v3v3_db(span_v1, view_dir); + dot_v2 = dot_v3v3_db(span_v2, view_dir); + a = dot_v1 / (dot_v1 + dot_v2); interp_v3_v3v3_db(vt[0].gloc, tri->v[1]->gloc, tri->v[2]->gloc, a); - mul_v4_m4v3_db(vt[0].fbcoord, vp, vt[0].gloc); + mul_v4_m4v3_db(vt[0].fbcoord, m_view_projection, vt[0].gloc); vt[0].index = tri->v[2]->index; - sub_v3_v3v3_db(vv1, tri->v[1]->gloc, cam_pos); - sub_v3_v3v3_db(vv2, cam_pos, tri->v[0]->gloc); - dot1 = dot_v3v3_db(vv1, view_dir); - dot2 = dot_v3v3_db(vv2, view_dir); - a = dot1 / (dot1 + dot2); + sub_v3_v3v3_db(span_v1, tri->v[1]->gloc, cam_pos); + sub_v3_v3v3_db(span_v2, cam_pos, tri->v[0]->gloc); + dot_v1 = dot_v3v3_db(span_v1, view_dir); + dot_v2 = dot_v3v3_db(span_v2, view_dir); + a = dot_v1 / (dot_v1 + dot_v2); interp_v3_v3v3_db(vt[1].gloc, tri->v[1]->gloc, tri->v[0]->gloc, a); - mul_v4_m4v3_db(vt[1].fbcoord, vp, vt[1].gloc); + mul_v4_m4v3_db(vt[1].fbcoord, m_view_projection, vt[1].gloc); vt[1].index = tri->v[0]->index; INCREASE_EDGE if (allow_boundaries) { e->flags = LRT_EDGE_FLAG_CONTOUR; - lineart_add_edge_to_array(&rb->pending_edges, e); + lineart_add_edge_to_array(&ld->pending_edges, e); } e->v1 = &vt[1]; e->v2 = &vt[0]; @@ -1021,32 +1039,32 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb, */ if (in0) { /* Cut point for line 0---|------1. */ - sub_v3_v3v3_db(vv1, tri->v[1]->gloc, cam_pos); - sub_v3_v3v3_db(vv2, cam_pos, tri->v[0]->gloc); - dot1 = dot_v3v3_db(vv1, view_dir); - dot2 = dot_v3v3_db(vv2, view_dir); - a = dot2 / (dot1 + dot2); + sub_v3_v3v3_db(span_v1, tri->v[1]->gloc, cam_pos); + sub_v3_v3v3_db(span_v2, cam_pos, tri->v[0]->gloc); + dot_v1 = dot_v3v3_db(span_v1, view_dir); + dot_v2 = dot_v3v3_db(span_v2, view_dir); + a = dot_v2 / (dot_v1 + dot_v2); /* Assign to a new point. */ interp_v3_v3v3_db(vt[0].gloc, tri->v[0]->gloc, tri->v[1]->gloc, a); - mul_v4_m4v3_db(vt[0].fbcoord, vp, vt[0].gloc); + mul_v4_m4v3_db(vt[0].fbcoord, m_view_projection, vt[0].gloc); vt[0].index = tri->v[0]->index; /* Cut point for line 0---|------2. */ - sub_v3_v3v3_db(vv1, tri->v[2]->gloc, cam_pos); - sub_v3_v3v3_db(vv2, cam_pos, tri->v[0]->gloc); - dot1 = dot_v3v3_db(vv1, view_dir); - dot2 = dot_v3v3_db(vv2, view_dir); - a = dot2 / (dot1 + dot2); + sub_v3_v3v3_db(span_v1, tri->v[2]->gloc, cam_pos); + sub_v3_v3v3_db(span_v2, cam_pos, tri->v[0]->gloc); + dot_v1 = dot_v3v3_db(span_v1, view_dir); + dot_v2 = dot_v3v3_db(span_v2, view_dir); + a = dot_v2 / (dot_v1 + dot_v2); /* Assign to other new point. */ interp_v3_v3v3_db(vt[1].gloc, tri->v[0]->gloc, tri->v[2]->gloc, a); - mul_v4_m4v3_db(vt[1].fbcoord, vp, vt[1].gloc); + mul_v4_m4v3_db(vt[1].fbcoord, m_view_projection, vt[1].gloc); vt[1].index = tri->v[0]->index; /* New line connects two new points. */ INCREASE_EDGE if (allow_boundaries) { e->flags = LRT_EDGE_FLAG_CONTOUR; - lineart_add_edge_to_array(&rb->pending_edges, e); + lineart_add_edge_to_array(&ld->pending_edges, e); } e->v1 = &vt[1]; e->v2 = &vt[0]; @@ -1077,28 +1095,28 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb, } else if (in1) { - sub_v3_v3v3_db(vv1, tri->v[1]->gloc, cam_pos); - sub_v3_v3v3_db(vv2, cam_pos, tri->v[2]->gloc); - dot1 = dot_v3v3_db(vv1, view_dir); - dot2 = dot_v3v3_db(vv2, view_dir); - a = dot1 / (dot1 + dot2); + sub_v3_v3v3_db(span_v1, tri->v[1]->gloc, cam_pos); + sub_v3_v3v3_db(span_v2, cam_pos, tri->v[2]->gloc); + dot_v1 = dot_v3v3_db(span_v1, view_dir); + dot_v2 = dot_v3v3_db(span_v2, view_dir); + a = dot_v1 / (dot_v1 + dot_v2); interp_v3_v3v3_db(vt[0].gloc, tri->v[1]->gloc, tri->v[2]->gloc, a); - mul_v4_m4v3_db(vt[0].fbcoord, vp, vt[0].gloc); + mul_v4_m4v3_db(vt[0].fbcoord, m_view_projection, vt[0].gloc); vt[0].index = tri->v[1]->index; - sub_v3_v3v3_db(vv1, tri->v[1]->gloc, cam_pos); - sub_v3_v3v3_db(vv2, cam_pos, tri->v[0]->gloc); - dot1 = dot_v3v3_db(vv1, view_dir); - dot2 = dot_v3v3_db(vv2, view_dir); - a = dot1 / (dot1 + dot2); + sub_v3_v3v3_db(span_v1, tri->v[1]->gloc, cam_pos); + sub_v3_v3v3_db(span_v2, cam_pos, tri->v[0]->gloc); + dot_v1 = dot_v3v3_db(span_v1, view_dir); + dot_v2 = dot_v3v3_db(span_v2, view_dir); + a = dot_v1 / (dot_v1 + dot_v2); interp_v3_v3v3_db(vt[1].gloc, tri->v[1]->gloc, tri->v[0]->gloc, a); - mul_v4_m4v3_db(vt[1].fbcoord, vp, vt[1].gloc); + mul_v4_m4v3_db(vt[1].fbcoord, m_view_projection, vt[1].gloc); vt[1].index = tri->v[1]->index; INCREASE_EDGE if (allow_boundaries) { e->flags = LRT_EDGE_FLAG_CONTOUR; - lineart_add_edge_to_array(&rb->pending_edges, e); + lineart_add_edge_to_array(&ld->pending_edges, e); } e->v1 = &vt[1]; e->v2 = &vt[0]; @@ -1126,28 +1144,28 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb, } else if (in2) { - sub_v3_v3v3_db(vv1, tri->v[2]->gloc, cam_pos); - sub_v3_v3v3_db(vv2, cam_pos, tri->v[0]->gloc); - dot1 = dot_v3v3_db(vv1, view_dir); - dot2 = dot_v3v3_db(vv2, view_dir); - a = dot1 / (dot1 + dot2); + sub_v3_v3v3_db(span_v1, tri->v[2]->gloc, cam_pos); + sub_v3_v3v3_db(span_v2, cam_pos, tri->v[0]->gloc); + dot_v1 = dot_v3v3_db(span_v1, view_dir); + dot_v2 = dot_v3v3_db(span_v2, view_dir); + a = dot_v1 / (dot_v1 + dot_v2); interp_v3_v3v3_db(vt[0].gloc, tri->v[2]->gloc, tri->v[0]->gloc, a); - mul_v4_m4v3_db(vt[0].fbcoord, vp, vt[0].gloc); + mul_v4_m4v3_db(vt[0].fbcoord, m_view_projection, vt[0].gloc); vt[0].index = tri->v[2]->index; - sub_v3_v3v3_db(vv1, tri->v[2]->gloc, cam_pos); - sub_v3_v3v3_db(vv2, cam_pos, tri->v[1]->gloc); - dot1 = dot_v3v3_db(vv1, view_dir); - dot2 = dot_v3v3_db(vv2, view_dir); - a = dot1 / (dot1 + dot2); + sub_v3_v3v3_db(span_v1, tri->v[2]->gloc, cam_pos); + sub_v3_v3v3_db(span_v2, cam_pos, tri->v[1]->gloc); + dot_v1 = dot_v3v3_db(span_v1, view_dir); + dot_v2 = dot_v3v3_db(span_v2, view_dir); + a = dot_v1 / (dot_v1 + dot_v2); interp_v3_v3v3_db(vt[1].gloc, tri->v[2]->gloc, tri->v[1]->gloc, a); - mul_v4_m4v3_db(vt[1].fbcoord, vp, vt[1].gloc); + mul_v4_m4v3_db(vt[1].fbcoord, m_view_projection, vt[1].gloc); vt[1].index = tri->v[2]->index; INCREASE_EDGE if (allow_boundaries) { e->flags = LRT_EDGE_FLAG_CONTOUR; - lineart_add_edge_to_array(&rb->pending_edges, e); + lineart_add_edge_to_array(&ld->pending_edges, e); } e->v1 = &vt[1]; e->v2 = &vt[0]; @@ -1191,22 +1209,22 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb, * new topology that represents the trimmed triangle. (which then became a triangle or a square * formed by two triangles) */ -static void lineart_main_cull_triangles(LineartRenderBuffer *rb, bool clip_far) +void lineart_main_cull_triangles(LineartData *ld, bool clip_far) { LineartTriangle *tri; LineartElementLinkNode *v_eln, *t_eln, *e_eln; - double(*vp)[4] = rb->view_projection; + double(*m_view_projection)[4] = ld->conf.view_projection; int i; int v_count = 0, t_count = 0, e_count = 0; Object *ob; - bool allow_boundaries = rb->allow_boundaries; + bool allow_boundaries = ld->conf.allow_boundaries; double cam_pos[3]; - double clip_start = rb->near_clip, clip_end = rb->far_clip; + double clip_start = ld->conf.near_clip, clip_end = ld->conf.far_clip; double view_dir[3], clip_advance[3]; - copy_v3_v3_db(view_dir, rb->view_vector); - copy_v3_v3_db(clip_advance, rb->view_vector); - copy_v3_v3_db(cam_pos, rb->camera_pos); + copy_v3_v3_db(view_dir, ld->conf.view_vector); + copy_v3_v3_db(clip_advance, ld->conf.view_vector); + copy_v3_v3_db(cam_pos, ld->conf.camera_pos); if (clip_far) { /* Move starting point to end plane. */ @@ -1222,25 +1240,25 @@ static void lineart_main_cull_triangles(LineartRenderBuffer *rb, bool clip_far) add_v3_v3_db(cam_pos, clip_advance); } - v_eln = lineart_memory_get_vert_space(rb); - t_eln = lineart_memory_get_triangle_space(rb); - e_eln = lineart_memory_get_edge_space(rb); + v_eln = lineart_memory_get_vert_space(ld); + t_eln = lineart_memory_get_triangle_space(ld); + e_eln = lineart_memory_get_edge_space(ld); /* Additional memory space for storing generated points and triangles. */ #define LRT_CULL_ENSURE_MEMORY \ if (v_count > 60) { \ v_eln->element_count = v_count; \ - v_eln = lineart_memory_get_vert_space(rb); \ + v_eln = lineart_memory_get_vert_space(ld); \ v_count = 0; \ } \ if (t_count > 60) { \ t_eln->element_count = t_count; \ - t_eln = lineart_memory_get_triangle_space(rb); \ + t_eln = lineart_memory_get_triangle_space(ld); \ t_count = 0; \ } \ if (e_count > 60) { \ e_eln->element_count = e_count; \ - e_eln = lineart_memory_get_edge_space(rb); \ + e_eln = lineart_memory_get_edge_space(ld); \ e_count = 0; \ } @@ -1275,21 +1293,21 @@ static void lineart_main_cull_triangles(LineartRenderBuffer *rb, bool clip_far) int use_w = 3; int in0 = 0, in1 = 0, in2 = 0; - if (!rb->cam_is_persp) { + if (!ld->conf.cam_is_persp) { clip_start = -1; clip_end = 1; use_w = 2; } /* Then go through all the other triangles. */ - LISTBASE_FOREACH (LineartElementLinkNode *, eln, &rb->triangle_buffer_pointers) { + LISTBASE_FOREACH (LineartElementLinkNode *, eln, &ld->geom.triangle_buffer_pointers) { if (eln->flags & LRT_ELEMENT_IS_ADDITIONAL) { continue; } ob = eln->object_ref; for (i = 0; i < eln->element_count; i++) { /* Select the triangle in the array. */ - tri = (void *)(((uchar *)eln->pointer) + rb->triangle_size * i); + tri = (void *)(((uchar *)eln->pointer) + ld->sizeof_triangle * i); if (tri->flags & LRT_CULL_DISCARD) { continue; @@ -1297,7 +1315,7 @@ static void lineart_main_cull_triangles(LineartRenderBuffer *rb, bool clip_far) LRT_CULL_DECIDE_INSIDE LRT_CULL_ENSURE_MEMORY - lineart_triangle_cull_single(rb, + lineart_triangle_cull_single(ld, tri, in0, in1, @@ -1305,7 +1323,7 @@ static void lineart_main_cull_triangles(LineartRenderBuffer *rb, bool clip_far) cam_pos, view_dir, allow_boundaries, - vp, + m_view_projection, ob, &v_count, &e_count, @@ -1326,33 +1344,33 @@ static void lineart_main_cull_triangles(LineartRenderBuffer *rb, bool clip_far) * Adjacent data is only used during the initial stages of computing. * So we can free it using this function when it is not needed anymore. */ -static void lineart_main_free_adjacent_data(LineartRenderBuffer *rb) +void lineart_main_free_adjacent_data(LineartData *ld) { - LinkData *ld; - while ((ld = BLI_pophead(&rb->triangle_adjacent_pointers)) != NULL) { - MEM_freeN(ld->data); + LinkData *link; + while ((link = BLI_pophead(&ld->geom.triangle_adjacent_pointers)) != NULL) { + MEM_freeN(link->data); } - LISTBASE_FOREACH (LineartElementLinkNode *, eln, &rb->triangle_buffer_pointers) { + LISTBASE_FOREACH (LineartElementLinkNode *, eln, &ld->geom.triangle_buffer_pointers) { LineartTriangle *tri = eln->pointer; int i; for (i = 0; i < eln->element_count; i++) { /* See definition of tri->intersecting_verts and the usage in * lineart_geometry_object_load() for detailed. */ tri->intersecting_verts = NULL; - tri = (LineartTriangle *)(((uchar *)tri) + rb->triangle_size); + tri = (LineartTriangle *)(((uchar *)tri) + ld->sizeof_triangle); } } } -static void lineart_main_perspective_division(LineartRenderBuffer *rb) +void lineart_main_perspective_division(LineartData *ld) { LineartVert *vt; int i; - LISTBASE_FOREACH (LineartElementLinkNode *, eln, &rb->vertex_buffer_pointers) { + LISTBASE_FOREACH (LineartElementLinkNode *, eln, &ld->geom.vertex_buffer_pointers) { vt = eln->pointer; for (i = 0; i < eln->element_count; i++) { - if (rb->cam_is_persp) { + if (ld->conf.cam_is_persp) { /* Do not divide Z, we use Z to back transform cut points in later chaining process. */ vt[i].fbcoord[0] /= vt[i].fbcoord[3]; vt[i].fbcoord[1] /= vt[i].fbcoord[3]; @@ -1363,13 +1381,13 @@ static void lineart_main_perspective_division(LineartRenderBuffer *rb) // `vt[i].fbcoord[2] = -2 * vt[i].fbcoord[2] / (far - near) - (far + near) / (far - near); } /* Shifting is always needed. */ - vt[i].fbcoord[0] -= rb->shift_x * 2; - vt[i].fbcoord[1] -= rb->shift_y * 2; + vt[i].fbcoord[0] -= ld->conf.shift_x * 2; + vt[i].fbcoord[1] -= ld->conf.shift_y * 2; } } } -static void lineart_main_discard_out_of_frame_edges(LineartRenderBuffer *rb) +void lineart_main_discard_out_of_frame_edges(LineartData *ld) { LineartEdge *e; int i; @@ -1377,7 +1395,7 @@ static void lineart_main_discard_out_of_frame_edges(LineartRenderBuffer *rb) #define LRT_VERT_OUT_OF_BOUND(v) \ (v && (v->fbcoord[0] < -1 || v->fbcoord[0] > 1 || v->fbcoord[1] < -1 || v->fbcoord[1] > 1)) - LISTBASE_FOREACH (LineartElementLinkNode *, eln, &rb->line_buffer_pointers) { + LISTBASE_FOREACH (LineartElementLinkNode *, eln, &ld->geom.line_buffer_pointers) { e = (LineartEdge *)eln->pointer; for (i = 0; i < eln->element_count; i++) { if ((LRT_VERT_OUT_OF_BOUND(e[i].v1) && LRT_VERT_OUT_OF_BOUND(e[i].v2))) { @@ -1414,14 +1432,23 @@ static void lineart_mvert_transform_task(void *__restrict userdata, v->index = i; } -#define LRT_EDGE_FLAG_TYPE_MAX_BITS 6 +static const int LRT_MESH_EDGE_TYPES[] = { + LRT_EDGE_FLAG_EDGE_MARK, + LRT_EDGE_FLAG_CONTOUR, + LRT_EDGE_FLAG_CREASE, + LRT_EDGE_FLAG_MATERIAL, + LRT_EDGE_FLAG_LOOSE, + LRT_EDGE_FLAG_CONTOUR_SECONDARY, +}; -static int lineart_edge_type_duplication_count(char eflag) +#define LRT_MESH_EDGE_TYPES_COUNT 6 + +static int lineart_edge_type_duplication_count(int eflag) { int count = 0; /* See eLineartEdgeFlag for details. */ - for (int i = 0; i < LRT_EDGE_FLAG_TYPE_MAX_BITS; i++) { - if (eflag & (1 << i)) { + for (int i = 0; i < LRT_MESH_EDGE_TYPES_COUNT; i++) { + if (eflag & LRT_MESH_EDGE_TYPES[i]) { count++; } } @@ -1432,18 +1459,19 @@ static int lineart_edge_type_duplication_count(char eflag) * Because we have a variable size for #LineartTriangle, we need an access helper. * See #LineartTriangleThread for more info. */ -static LineartTriangle *lineart_triangle_from_index(LineartRenderBuffer *rb, +static LineartTriangle *lineart_triangle_from_index(LineartData *ld, LineartTriangle *rt_array, int index) { - char *b = (char *)rt_array; - b += (index * rb->triangle_size); + int8_t *b = (int8_t *)rt_array; + b += (index * ld->sizeof_triangle); return (LineartTriangle *)b; } typedef struct EdgeFeatData { - LineartRenderBuffer *rb; + LineartData *ld; Mesh *me; + Object *ob; const MLoopTri *mlooptri; LineartTriangle *tri_array; LineartVert *v_array; @@ -1476,6 +1504,7 @@ static void lineart_identify_mlooptri_feature_edges(void *__restrict userdata, EdgeFeatData *e_feat_data = (EdgeFeatData *)userdata; EdgeFeatReduceData *reduce_data = (EdgeFeatReduceData *)tls->userdata_chunk; Mesh *me = e_feat_data->me; + Object *ob = e_feat_data->ob; LineartEdgeNeighbor *edge_nabr = e_feat_data->edge_nabr; const MLoopTri *mlooptri = e_feat_data->mlooptri; @@ -1488,7 +1517,8 @@ static void lineart_identify_mlooptri_feature_edges(void *__restrict userdata, } bool face_mark_filtered = false; - bool enable_face_mark = (e_feat_data->use_freestyle_face && e_feat_data->rb->filter_face_mark); + bool enable_face_mark = (e_feat_data->use_freestyle_face && + e_feat_data->ld->conf.filter_face_mark); bool only_contour = false; if (enable_face_mark) { FreestyleFace *ff1, *ff2; @@ -1505,7 +1535,8 @@ static void lineart_identify_mlooptri_feature_edges(void *__restrict userdata, * path is simper when it's assuming both ff1 and ff2 not NULL. */ ff2 = ff1; } - if (e_feat_data->rb->filter_face_mark_boundaries ^ e_feat_data->rb->filter_face_mark_invert) { + if (e_feat_data->ld->conf.filter_face_mark_boundaries ^ + e_feat_data->ld->conf.filter_face_mark_invert) { if ((ff1->flag & FREESTYLE_FACE_MARK) || (ff2->flag & FREESTYLE_FACE_MARK)) { face_mark_filtered = true; } @@ -1515,12 +1546,12 @@ static void lineart_identify_mlooptri_feature_edges(void *__restrict userdata, face_mark_filtered = true; } } - if (e_feat_data->rb->filter_face_mark_invert) { + if (e_feat_data->ld->conf.filter_face_mark_invert) { face_mark_filtered = !face_mark_filtered; } if (!face_mark_filtered) { edge_nabr[i].flags = LRT_EDGE_FLAG_INHIBIT; - if (e_feat_data->rb->filter_face_mark_keep_contour) { + if (e_feat_data->ld->conf.filter_face_mark_keep_contour) { only_contour = true; } } @@ -1539,60 +1570,77 @@ static void lineart_identify_mlooptri_feature_edges(void *__restrict userdata, LineartTriangle *tri1, *tri2; LineartVert *vert; - LineartRenderBuffer *rb = e_feat_data->rb; + LineartData *ld = e_feat_data->ld; int f1 = i / 3, f2 = edge_nabr[i].e / 3; /* The mesh should already be triangulated now, so we can assume each face is a triangle. */ - tri1 = lineart_triangle_from_index(rb, e_feat_data->tri_array, f1); - tri2 = lineart_triangle_from_index(rb, e_feat_data->tri_array, f2); + tri1 = lineart_triangle_from_index(ld, e_feat_data->tri_array, f1); + tri2 = lineart_triangle_from_index(ld, e_feat_data->tri_array, f2); vert = &e_feat_data->v_array[edge_nabr[i].v1]; double view_vector_persp[3]; double *view_vector = view_vector_persp; - double dot_1 = 0, dot_2 = 0; + double dot_v1 = 0, dot_v2 = 0; double result; bool material_back_face = ((tri1->flags | tri2->flags) & LRT_TRIANGLE_MAT_BACK_FACE_CULLING); - if (rb->use_contour || rb->use_back_face_culling || material_back_face) { - if (rb->cam_is_persp) { - sub_v3_v3v3_db(view_vector, rb->camera_pos, vert->gloc); + if (ld->conf.use_contour || ld->conf.use_back_face_culling || material_back_face) { + if (ld->conf.cam_is_persp) { + sub_v3_v3v3_db(view_vector, ld->conf.camera_pos, vert->gloc); } else { - view_vector = rb->view_vector; + view_vector = ld->conf.view_vector; } - dot_1 = dot_v3v3_db(view_vector, tri1->gn); - dot_2 = dot_v3v3_db(view_vector, tri2->gn); + dot_v1 = dot_v3v3_db(view_vector, tri1->gn); + dot_v2 = dot_v3v3_db(view_vector, tri2->gn); - if ((result = dot_1 * dot_2) <= 0 && (dot_1 + dot_2)) { + if ((result = dot_v1 * dot_v2) <= 0 && (dot_v1 + dot_v2)) { edge_flag_result |= LRT_EDGE_FLAG_CONTOUR; } - if (rb->use_back_face_culling) { - if (dot_1 < 0) { + if (ld->conf.use_back_face_culling) { + if (dot_v1 < 0) { tri1->flags |= LRT_CULL_DISCARD; } - if (dot_2 < 0) { + if (dot_v2 < 0) { tri2->flags |= LRT_CULL_DISCARD; } } if (material_back_face) { - if (tri1->flags & LRT_TRIANGLE_MAT_BACK_FACE_CULLING && dot_1 < 0) { + if (tri1->flags & LRT_TRIANGLE_MAT_BACK_FACE_CULLING && dot_v1 < 0) { tri1->flags |= LRT_CULL_DISCARD; } - if (tri2->flags & LRT_TRIANGLE_MAT_BACK_FACE_CULLING && dot_2 < 0) { + if (tri2->flags & LRT_TRIANGLE_MAT_BACK_FACE_CULLING && dot_v2 < 0) { tri2->flags |= LRT_CULL_DISCARD; } } } + if (ld->conf.use_contour_secondary) { + view_vector = view_vector_persp; + if (ld->conf.cam_is_persp_secondary) { + sub_v3_v3v3_db(view_vector, vert->gloc, ld->conf.camera_pos_secondary); + } + else { + view_vector = ld->conf.view_vector_secondary; + } + + dot_v1 = dot_v3v3_db(view_vector, tri1->gn); + dot_v2 = dot_v3v3_db(view_vector, tri2->gn); + + if ((result = dot_v1 * dot_v2) <= 0 && (dot_v1 + dot_v2)) { + edge_flag_result |= LRT_EDGE_FLAG_CONTOUR_SECONDARY; + } + } + if (!only_contour) { - if (rb->use_crease) { + if (ld->conf.use_crease) { bool do_crease = true; - if (!rb->force_crease && !e_feat_data->use_auto_smooth && + if (!ld->conf.force_crease && !e_feat_data->use_auto_smooth && (me->mpoly[mlooptri[f1].poly].flag & ME_SMOOTH) && (me->mpoly[mlooptri[f2].poly].flag & ME_SMOOTH)) { do_crease = false; @@ -1605,8 +1653,19 @@ static void lineart_identify_mlooptri_feature_edges(void *__restrict userdata, int mat1 = me->mpoly[mlooptri[f1].poly].mat_nr; int mat2 = me->mpoly[mlooptri[f2].poly].mat_nr; - if (rb->use_material && mat1 != mat2) { - edge_flag_result |= LRT_EDGE_FLAG_MATERIAL; + if (mat1 != mat2) { + Material *m1 = BKE_object_material_get(ob, mat1 + 1); + Material *m2 = BKE_object_material_get(ob, mat2 + 1); + if (m1 && m2 && + ((m1->lineart.mat_occlusion == 0 && m2->lineart.mat_occlusion != 0) || + (m2->lineart.mat_occlusion == 0 && m1->lineart.mat_occlusion != 0))) { + if (ld->conf.use_contour) { + edge_flag_result |= LRT_EDGE_FLAG_CONTOUR; + } + } + if (ld->conf.use_material) { + edge_flag_result |= LRT_EDGE_FLAG_MATERIAL; + } } } else { /* only_contour */ @@ -1621,11 +1680,11 @@ static void lineart_identify_mlooptri_feature_edges(void *__restrict userdata, if (real_edges[i % 3] >= 0) { MEdge *medge = &me->medge[real_edges[i % 3]]; - if (rb->use_crease && rb->sharp_as_crease && (medge->flag & ME_SHARP)) { + if (ld->conf.use_crease && ld->conf.sharp_as_crease && (medge->flag & ME_SHARP)) { edge_flag_result |= LRT_EDGE_FLAG_CREASE; } - if (rb->use_edge_marks && e_feat_data->use_freestyle_edge) { + if (ld->conf.use_edge_marks && e_feat_data->use_freestyle_edge) { FreestyleEdge *fe; int index = e_feat_data->freestyle_edge_index; fe = &((FreestyleEdge *)me->edata.layers[index].data)[real_edges[i % 3]]; @@ -1641,7 +1700,7 @@ static void lineart_identify_mlooptri_feature_edges(void *__restrict userdata, /* Only allocate for feature edge (instead of all edges) to save memory. * If allow duplicated edges, one edge gets added multiple times if it has multiple types. */ - reduce_data->feat_edges += e_feat_data->rb->allow_duplicated_types ? + reduce_data->feat_edges += e_feat_data->ld->conf.allow_duplicated_types ? lineart_edge_type_duplication_count(edge_flag_result) : 1; } @@ -1679,6 +1738,7 @@ static void lineart_join_loose_edge_arr(LooseEdgeData *loose_data, LooseEdgeData sizeof(MEdge *) * to_be_joined->loose_count); loose_data->loose_count += to_be_joined->loose_count; MEM_freeN(to_be_joined->loose_array); + to_be_joined->loose_array = NULL; } static void lineart_add_loose_edge(LooseEdgeData *loose_data, MEdge *e) @@ -1712,7 +1772,7 @@ 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_array(LineartPendingEdges *pe, LineartEdge *e) +void lineart_add_edge_to_array(LineartPendingEdges *pe, LineartEdge *e) { if (pe->next >= pe->max || !pe->max) { if (!pe->max) { @@ -1731,15 +1791,14 @@ static void lineart_add_edge_to_array(LineartPendingEdges *pe, LineartEdge *e) pe->array[pe->next] = e; pe->next++; } - static void lineart_add_edge_to_array_thread(LineartObjectInfo *obi, LineartEdge *e) { lineart_add_edge_to_array(&obi->pending_edges, e); } -/* Note: For simplicity, this function doesn't actually do anything if you already have data in +/* 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) +void lineart_finalize_object_edge_array_reserve(LineartPendingEdges *pe, int count) { if (pe->max || pe->array) { return; @@ -1766,17 +1825,17 @@ static void lineart_finalize_object_edge_array(LineartPendingEdges *pe, LineartO } static void lineart_triangle_adjacent_assign(LineartTriangle *tri, - LineartTriangleAdjacent *ta, + LineartTriangleAdjacent *tri_adj, LineartEdge *e) { if (lineart_edge_match(tri, e, 0, 1)) { - ta->e[0] = e; + tri_adj->e[0] = e; } else if (lineart_edge_match(tri, e, 1, 2)) { - ta->e[1] = e; + tri_adj->e[1] = e; } else if (lineart_edge_match(tri, e, 2, 0)) { - ta->e[2] = e; + tri_adj->e[2] = e; } } @@ -1817,12 +1876,18 @@ static void lineart_load_tri_task(void *__restrict userdata, mat->lineart.material_mask_bits : 0); tri->mat_occlusion |= (mat ? mat->lineart.mat_occlusion : 1); + tri->intersection_priority = ((mat && (mat->lineart.flags & + LRT_MATERIAL_CUSTOM_INTERSECTION_PRIORITY)) ? + mat->lineart.intersection_priority : + ob_info->intersection_priority); tri->flags |= (mat && (mat->blend_flag & MA_BL_CULL_BACKFACE)) ? LRT_TRIANGLE_MAT_BACK_FACE_CULLING : 0; tri->intersection_mask = ob_info->override_intersection_mask; + tri->target_reference = (ob_info->obindex | (i & LRT_OBINDEX_LOWER)); + double gn[3]; float no[3]; normal_tri_v3(no, me->mvert[v1].co, me->mvert[v2].co, me->mvert[v3].co); @@ -1862,7 +1927,7 @@ static void lineart_edge_neighbor_init_task(void *__restrict userdata, adj_e->v1 = mloop[looptri->tri[i % 3]].v; adj_e->v2 = mloop[looptri->tri[(i + 1) % 3]].v; if (adj_e->v1 > adj_e->v2) { - SWAP(unsigned int, adj_e->v1, adj_e->v2); + SWAP(uint32_t, adj_e->v1, adj_e->v2); } edge_nabr->e = -1; @@ -1908,7 +1973,9 @@ static LineartEdgeNeighbor *lineart_build_edge_neighbor(Mesh *me, int total_edge return edge_nabr; } -static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRenderBuffer *re_buf) +static void lineart_geometry_object_load(LineartObjectInfo *ob_info, + LineartData *la_data, + ListBase *shadow_elns) { LineartElementLinkNode *elem_link_node; LineartVert *la_v_arr; @@ -1942,20 +2009,22 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend /* If we allow duplicated edges, one edge should get added multiple times if is has been * classified as more than one edge type. This is so we can create multiple different line type * chains containing the same edge. */ - la_v_arr = lineart_mem_acquire_thread(&re_buf->render_data_pool, + la_v_arr = lineart_mem_acquire_thread(&la_data->render_data_pool, sizeof(LineartVert) * me->totvert); - la_tri_arr = lineart_mem_acquire_thread(&re_buf->render_data_pool, - tot_tri * re_buf->triangle_size); + la_tri_arr = lineart_mem_acquire_thread(&la_data->render_data_pool, + tot_tri * la_data->sizeof_triangle); Object *orig_ob = ob_info->original_ob; - BLI_spin_lock(&re_buf->lock_task); - elem_link_node = lineart_list_append_pointer_pool_sized_thread(&re_buf->vertex_buffer_pointers, - &re_buf->render_data_pool, - la_v_arr, - sizeof(LineartElementLinkNode)); - BLI_spin_unlock(&re_buf->lock_task); + BLI_spin_lock(&la_data->lock_task); + elem_link_node = lineart_list_append_pointer_pool_sized_thread( + &la_data->geom.vertex_buffer_pointers, + &la_data->render_data_pool, + la_v_arr, + sizeof(LineartElementLinkNode)); + BLI_spin_unlock(&la_data->lock_task); + elem_link_node->obindex = ob_info->obindex; elem_link_node->element_count = me->totvert; elem_link_node->object_ref = orig_ob; ob_info->v_eln = elem_link_node; @@ -1970,7 +2039,7 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend use_auto_smooth = true; } else { - crease_angle = re_buf->crease_threshold; + crease_angle = la_data->conf.crease_threshold; } /* FIXME(Yiming): Hack for getting clean 3D text, the seam that extruded text object creates @@ -1979,12 +2048,13 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend elem_link_node->flags |= LRT_ELEMENT_BORDER_ONLY; } - BLI_spin_lock(&re_buf->lock_task); - elem_link_node = lineart_list_append_pointer_pool_sized_thread(&re_buf->triangle_buffer_pointers, - &re_buf->render_data_pool, - la_tri_arr, - sizeof(LineartElementLinkNode)); - BLI_spin_unlock(&re_buf->lock_task); + BLI_spin_lock(&la_data->lock_task); + elem_link_node = lineart_list_append_pointer_pool_sized_thread( + &la_data->geom.triangle_buffer_pointers, + &la_data->render_data_pool, + la_tri_arr, + sizeof(LineartElementLinkNode)); + BLI_spin_unlock(&la_data->lock_task); int usage = ob_info->usage; @@ -1996,10 +2066,10 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend LineartTriangleAdjacent *tri_adj = MEM_callocN(sizeof(LineartTriangleAdjacent) * tot_tri, "LineartTriangleAdjacent"); /* Link is minimal so we use pool anyway. */ - BLI_spin_lock(&re_buf->lock_task); + BLI_spin_lock(&la_data->lock_task); lineart_list_append_pointer_pool_thread( - &re_buf->triangle_adjacent_pointers, &re_buf->render_data_pool, tri_adj); - BLI_spin_unlock(&re_buf->lock_task); + &la_data->geom.triangle_adjacent_pointers, &la_data->render_data_pool, tri_adj); + BLI_spin_unlock(&la_data->lock_task); /* Convert all vertices to lineart verts. */ TaskParallelSettings vert_settings; @@ -2028,10 +2098,10 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend tri_data.mlooptri = mlooptri; tri_data.vert_arr = la_v_arr; tri_data.tri_arr = la_tri_arr; - tri_data.lineart_triangle_size = re_buf->triangle_size; + tri_data.lineart_triangle_size = la_data->sizeof_triangle; tri_data.tri_adj = tri_adj; - unsigned int total_edges = tot_tri * 3; + uint32_t total_edges = tot_tri * 3; BLI_task_parallel_range(0, tot_tri, &tri_data, lineart_load_tri_task, &tri_settings); @@ -2049,8 +2119,9 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend edge_feat_settings.func_reduce = feat_data_sum_reduce; EdgeFeatData edge_feat_data = {0}; - edge_feat_data.rb = re_buf; + edge_feat_data.ld = la_data; edge_feat_data.me = me; + edge_feat_data.ob = orig_ob; edge_feat_data.mlooptri = mlooptri; edge_feat_data.edge_nabr = lineart_build_edge_neighbor(me, total_edges); edge_feat_data.tri_array = la_tri_arr; @@ -2075,7 +2146,7 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend &edge_feat_settings); LooseEdgeData loose_data = {0}; - if (re_buf->use_loose) { + if (la_data->conf.use_loose) { /* Only identifying floating edges at this point because other edges has been taken care of * inside #lineart_identify_mlooptri_feature_edges function. */ TaskParallelSettings edge_loose_settings; @@ -2091,20 +2162,27 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend int allocate_la_e = edge_reduce.feat_edges + loose_data.loose_count; - la_edge_arr = lineart_mem_acquire_thread(&re_buf->render_data_pool, + la_edge_arr = lineart_mem_acquire_thread(la_data->edge_data_pool, sizeof(LineartEdge) * allocate_la_e); - la_seg_arr = lineart_mem_acquire_thread(&re_buf->render_data_pool, + la_seg_arr = lineart_mem_acquire_thread(la_data->edge_data_pool, sizeof(LineartEdgeSegment) * allocate_la_e); - BLI_spin_lock(&re_buf->lock_task); - elem_link_node = lineart_list_append_pointer_pool_sized_thread(&re_buf->line_buffer_pointers, - &re_buf->render_data_pool, - la_edge_arr, - sizeof(LineartElementLinkNode)); - BLI_spin_unlock(&re_buf->lock_task); + BLI_spin_lock(&la_data->lock_task); + elem_link_node = lineart_list_append_pointer_pool_sized_thread( + &la_data->geom.line_buffer_pointers, + la_data->edge_data_pool, + la_edge_arr, + sizeof(LineartElementLinkNode)); + BLI_spin_unlock(&la_data->lock_task); elem_link_node->element_count = allocate_la_e; elem_link_node->object_ref = orig_ob; + elem_link_node->obindex = ob_info->obindex; + + LineartElementLinkNode *shadow_eln = NULL; + if (shadow_elns) { + shadow_eln = lineart_find_matching_eln(shadow_elns, ob_info->obindex); + } - // Start of the edge/seg arr + /* Start of the edge/seg arr */ LineartEdge *la_edge; LineartEdgeSegment *la_seg; la_edge = la_edge_arr; @@ -2125,8 +2203,8 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend LineartEdge *edge_added = NULL; /* See eLineartEdgeFlag for details. */ - for (int flag_bit = 0; flag_bit < LRT_EDGE_FLAG_TYPE_MAX_BITS; flag_bit++) { - char use_type = 1 << flag_bit; + for (int flag_bit = 0; flag_bit < LRT_MESH_EDGE_TYPES_COUNT; flag_bit++) { + int use_type = LRT_MESH_EDGE_TYPES[flag_bit]; if (!(use_type & edge_nabr->flags)) { continue; } @@ -2134,20 +2212,32 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend la_edge->v1 = &la_v_arr[edge_nabr->v1]; la_edge->v2 = &la_v_arr[edge_nabr->v2]; int findex = i / 3; - la_edge->t1 = lineart_triangle_from_index(re_buf, la_tri_arr, findex); + la_edge->t1 = lineart_triangle_from_index(la_data, la_tri_arr, findex); if (!edge_added) { lineart_triangle_adjacent_assign(la_edge->t1, &tri_adj[findex], la_edge); } if (edge_nabr->e != -1) { findex = edge_nabr->e / 3; - la_edge->t2 = lineart_triangle_from_index(re_buf, la_tri_arr, findex); + la_edge->t2 = lineart_triangle_from_index(la_data, la_tri_arr, findex); if (!edge_added) { lineart_triangle_adjacent_assign(la_edge->t2, &tri_adj[findex], la_edge); } } la_edge->flags = use_type; la_edge->object_ref = orig_ob; + la_edge->edge_identifier = LRT_EDGE_IDENTIFIER(ob_info, la_edge); BLI_addtail(&la_edge->segments, la_seg); + + if (shadow_eln) { + /* TODO(Yiming): It's gonna be faster to do this operation after second stage occlusion if + * we only need visible segments to have shadow info, however that way we lose information + * on "shadow behind transparency window" type of region. */ + LineartEdge *shadow_e = lineart_find_matching_edge(shadow_eln, la_edge->edge_identifier); + if (shadow_e) { + lineart_register_shadow_cuts(la_data, la_edge, shadow_e); + } + } + if (usage == OBJECT_LRT_INHERIT || usage == OBJECT_LRT_INCLUDE || usage == OBJECT_LRT_NO_INTERSECTION) { lineart_add_edge_to_array_thread(ob_info, la_edge); @@ -2162,7 +2252,7 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend la_edge++; la_seg++; - if (!re_buf->allow_duplicated_types) { + if (!la_data->conf.allow_duplicated_types) { break; } } @@ -2174,10 +2264,17 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend la_edge->v2 = &la_v_arr[loose_data.loose_array[i]->v2]; la_edge->flags = LRT_EDGE_FLAG_LOOSE; la_edge->object_ref = orig_ob; + la_edge->edge_identifier = LRT_EDGE_IDENTIFIER(ob_info, la_edge); 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_array_thread(ob_info, la_edge); + if (shadow_eln) { + LineartEdge *shadow_e = lineart_find_matching_edge(shadow_eln, la_edge->edge_identifier); + if (shadow_e) { + lineart_register_shadow_cuts(la_data, la_edge, shadow_e); + } + } } la_edge++; la_seg++; @@ -2196,10 +2293,7 @@ static void lineart_object_load_worker(TaskPool *__restrict UNUSED(pool), LineartObjectLoadTaskInfo *olti) { for (LineartObjectInfo *obi = olti->pending; obi; obi = obi->next) { - lineart_geometry_object_load(obi, olti->rb); - if (G.debug_value == 4000) { - printf("thread id: %d processed: %d\n", olti->thread_id, obi->original_me->totpoly); - } + lineart_geometry_object_load(obi, olti->ld, olti->shadow_elns); } } @@ -2221,6 +2315,26 @@ static uchar lineart_intersection_mask_check(Collection *c, Object *ob) return 0; } +static uchar lineart_intersection_priority_check(Collection *c, Object *ob) +{ + if (ob->lineart.flags & OBJECT_LRT_OWN_INTERSECTION_PRIORITY) { + return ob->lineart.intersection_priority; + } + + LISTBASE_FOREACH (CollectionChild *, cc, &c->children) { + uchar result = lineart_intersection_priority_check(cc->collection, ob); + if (result) { + return result; + } + } + if (BKE_collection_has_object(c, (Object *)(ob->id.orig_id))) { + if (c->lineart_flags & COLLECTION_LRT_USE_INTERSECTION_PRIORITY) { + return c->lineart_intersection_priority; + } + } + return 0; +} + /** * See if this object in such collection is used for generating line art, * Disabling a collection for line art will doable all objects inside. @@ -2277,7 +2391,7 @@ static void lineart_geometry_load_assign_thread(LineartObjectLoadTaskInfo *olti_ int this_face_count) { LineartObjectLoadTaskInfo *use_olti = olti_list; - long unsigned int min_face = use_olti->total_faces; + uint64_t min_face = use_olti->total_faces; for (int i = 0; i < thread_count; i++) { if (olti_list[i].total_faces < min_face) { min_face = olti_list[i].total_faces; @@ -2290,7 +2404,7 @@ static void lineart_geometry_load_assign_thread(LineartObjectLoadTaskInfo *olti_ use_olti->pending = obi; } -static bool lineart_geometry_check_visible(double (*model_view_proj)[4], +static bool lineart_geometry_check_visible(double model_view_proj[4][4], double shift_x, double shift_y, Mesh *use_mesh) @@ -2333,7 +2447,7 @@ static bool lineart_geometry_check_visible(double (*model_view_proj)[4], return true; } -static void lineart_object_load_single_instance(LineartRenderBuffer *rb, +static void lineart_object_load_single_instance(LineartData *ld, Depsgraph *depsgraph, Scene *scene, Object *ob, @@ -2341,21 +2455,25 @@ static void lineart_object_load_single_instance(LineartRenderBuffer *rb, float use_mat[4][4], bool is_render, LineartObjectLoadTaskInfo *olti, - int thread_count) + int thread_count, + int obindex) { - LineartObjectInfo *obi = lineart_mem_acquire(&rb->render_data_pool, sizeof(LineartObjectInfo)); + LineartObjectInfo *obi = lineart_mem_acquire(&ld->render_data_pool, sizeof(LineartObjectInfo)); obi->usage = lineart_usage_check(scene->master_collection, ob, is_render); obi->override_intersection_mask = lineart_intersection_mask_check(scene->master_collection, ob); + obi->intersection_priority = lineart_intersection_priority_check(scene->master_collection, ob); Mesh *use_mesh; if (obi->usage == OBJECT_LRT_EXCLUDE) { return; } + obi->obindex = obindex << LRT_OBINDEX_SHIFT; + /* Prepare the matrix used for transforming this specific object (instance). This has to be * done before mesh boundbox check because the function needs that. */ - mul_m4db_m4db_m4fl_uniq(obi->model_view_proj, rb->view_projection, use_mat); - mul_m4db_m4db_m4fl_uniq(obi->model_view, rb->view, use_mat); + mul_m4db_m4db_m4fl_uniq(obi->model_view_proj, ld->conf.view_projection, use_mat); + mul_m4db_m4db_m4fl_uniq(obi->model_view, ld->conf.view, use_mat); if (!ELEM(ob->type, OB_MESH, OB_MBALL, OB_CURVES_LEGACY, OB_SURF, OB_FONT)) { return; @@ -2377,7 +2495,8 @@ static void lineart_object_load_single_instance(LineartRenderBuffer *rb, return; } - if (!lineart_geometry_check_visible(obi->model_view_proj, rb->shift_x, rb->shift_y, use_mesh)) { + if (!lineart_geometry_check_visible( + obi->model_view_proj, ld->conf.shift_x, ld->conf.shift_y, use_mesh)) { return; } @@ -2396,89 +2515,105 @@ static void lineart_object_load_single_instance(LineartRenderBuffer *rb, lineart_geometry_load_assign_thread(olti, obi, thread_count, use_mesh->totpoly); } -static void lineart_main_load_geometries( - Depsgraph *depsgraph, - Scene *scene, - Object *camera /* Still use camera arg for convenience. */, - LineartRenderBuffer *rb, - bool allow_duplicates) +void lineart_main_load_geometries(Depsgraph *depsgraph, + Scene *scene, + Object *camera /* Still use camera arg for convenience. */, + LineartData *ld, + bool allow_duplicates, + bool do_shadow_casting, + ListBase *shadow_elns) { double proj[4][4], view[4][4], result[4][4]; float inv[4][4]; - Camera *cam = camera->data; - float sensor = BKE_camera_sensor_size(cam->sensor_fit, cam->sensor_x, cam->sensor_y); - int fit = BKE_camera_sensor_fit(cam->sensor_fit, rb->w, rb->h); - double asp = ((double)rb->w / (double)rb->h); - - int bound_box_discard_count = 0; - if (cam->type == CAM_PERSP) { - if (fit == CAMERA_SENSOR_FIT_VERT && asp > 1) { - sensor *= asp; + if (!do_shadow_casting) { + Camera *cam = camera->data; + float sensor = BKE_camera_sensor_size(cam->sensor_fit, cam->sensor_x, cam->sensor_y); + int fit = BKE_camera_sensor_fit(cam->sensor_fit, ld->w, ld->h); + double asp = ((double)ld->w / (double)ld->h); + if (cam->type == CAM_PERSP) { + if (fit == CAMERA_SENSOR_FIT_VERT && asp > 1) { + sensor *= asp; + } + if (fit == CAMERA_SENSOR_FIT_HOR && asp < 1) { + sensor /= asp; + } + const double fov = focallength_to_fov(cam->lens / (1 + ld->conf.overscan), sensor); + lineart_matrix_perspective_44d(proj, fov, asp, cam->clip_start, cam->clip_end); } - if (fit == CAMERA_SENSOR_FIT_HOR && asp < 1) { - sensor /= asp; + else if (cam->type == CAM_ORTHO) { + const double w = cam->ortho_scale / 2; + lineart_matrix_ortho_44d(proj, -w, w, -w / asp, w / asp, cam->clip_start, cam->clip_end); } - const double fov = focallength_to_fov(cam->lens / (1 + rb->overscan), sensor); - lineart_matrix_perspective_44d(proj, fov, asp, cam->clip_start, cam->clip_end); - } - else if (cam->type == CAM_ORTHO) { - const double w = cam->ortho_scale / 2; - lineart_matrix_ortho_44d(proj, -w, w, -w / asp, w / asp, cam->clip_start, cam->clip_end); + + invert_m4_m4(inv, ld->conf.cam_obmat); + mul_m4db_m4db_m4fl_uniq(result, proj, inv); + copy_m4_m4_db(proj, result); + copy_m4_m4_db(ld->conf.view_projection, proj); + + unit_m4_db(view); + copy_m4_m4_db(ld->conf.view, view); } - double t_start; + BLI_listbase_clear(&ld->geom.triangle_buffer_pointers); + BLI_listbase_clear(&ld->geom.vertex_buffer_pointers); + double t_start; if (G.debug_value == 4000) { t_start = PIL_check_seconds_timer(); } - invert_m4_m4(inv, rb->cam_obmat); - mul_m4db_m4db_m4fl_uniq(result, proj, inv); - copy_m4_m4_db(proj, result); - copy_m4_m4_db(rb->view_projection, proj); - - unit_m4_db(view); - copy_m4_m4_db(rb->view, view); - - BLI_listbase_clear(&rb->triangle_buffer_pointers); - BLI_listbase_clear(&rb->vertex_buffer_pointers); - - int thread_count = rb->thread_count; + int thread_count = ld->thread_count; + int bound_box_discard_count = 0; + int obindex = 0; - /* This memory is in render buffer memory pool. so we don't need to free those after loading. - */ + /* This memory is in render buffer memory pool. So we don't need to free those after loading. */ LineartObjectLoadTaskInfo *olti = lineart_mem_acquire( - &rb->render_data_pool, sizeof(LineartObjectLoadTaskInfo) * thread_count); + &ld->render_data_pool, sizeof(LineartObjectLoadTaskInfo) * thread_count); eEvaluationMode eval_mode = DEG_get_mode(depsgraph); bool is_render = eval_mode == DAG_EVAL_RENDER; - FOREACH_SCENE_OBJECT_BEGIN (scene, ob) { + int flags = DEG_ITER_OBJECT_FLAG_LINKED_DIRECTLY | DEG_ITER_OBJECT_FLAG_LINKED_VIA_SET | + DEG_ITER_OBJECT_FLAG_VISIBLE; + + /* Instance duplicated & particles. */ + if (allow_duplicates) { + flags |= DEG_ITER_OBJECT_FLAG_DUPLI; + } + + /* XXX(@Yiming): Temporary solution, this iterator is technically unsafe to use *during* + * depsgraph evaluation, see D14997 for detailed explanations. */ + DEG_OBJECT_ITER_BEGIN (depsgraph, ob, flags) { + + obindex++; + Object *eval_ob = DEG_get_evaluated_object(depsgraph, ob); if (!eval_ob) { continue; } + /* DEG_OBJECT_ITER_BEGIN will include the instanced mesh of these curve object types, so don't + * load them twice. */ + if (allow_duplicates && ELEM(ob->type, OB_CURVES_LEGACY, OB_FONT, OB_SURF)) { + continue; + } + if (BKE_object_visibility(eval_ob, eval_mode) & OB_VISIBLE_SELF) { - lineart_object_load_single_instance( - rb, depsgraph, scene, eval_ob, eval_ob, eval_ob->obmat, is_render, olti, thread_count); - } - if (allow_duplicates) { - ListBase *dupli = object_duplilist(depsgraph, scene, eval_ob); - LISTBASE_FOREACH (DupliObject *, dob, dupli) { - if (BKE_object_visibility(eval_ob, eval_mode) & - (OB_VISIBLE_PARTICLES | OB_VISIBLE_INSTANCES)) { - Object *ob_ref = (dob->type & OB_DUPLIPARTS) ? eval_ob : dob->ob; - lineart_object_load_single_instance( - rb, depsgraph, scene, dob->ob, ob_ref, dob->mat, is_render, olti, thread_count); - } - } - free_object_duplilist(dupli); + lineart_object_load_single_instance(ld, + depsgraph, + scene, + eval_ob, + eval_ob, + eval_ob->obmat, + is_render, + olti, + thread_count, + obindex); } } - FOREACH_SCENE_OBJECT_END; + DEG_OBJECT_ITER_END; TaskPool *tp = BLI_task_pool_create(NULL, TASK_PRIORITY_HIGH); @@ -2486,7 +2621,8 @@ static void lineart_main_load_geometries( printf("thread count: %d\n", thread_count); } for (int i = 0; i < thread_count; i++) { - olti[i].rb = rb; + olti[i].ld = ld; + olti[i].shadow_elns = shadow_elns; olti[i].thread_id = i; BLI_task_pool_push(tp, (TaskRunFunction)lineart_object_load_worker, &olti[i], 0, NULL); } @@ -2506,7 +2642,7 @@ static void lineart_main_load_geometries( edge_count += obi->pending_edges.next; } } - lineart_finalize_object_edge_array_reserve(&rb->pending_edges, edge_count); + lineart_finalize_object_edge_array_reserve(&ld->pending_edges, edge_count); for (int i = 0; i < thread_count; i++) { for (LineartObjectInfo *obi = olti[i].pending; obi; obi = obi->next) { @@ -2524,7 +2660,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_array(&rb->pending_edges, obi); + lineart_finalize_object_edge_array(&ld->pending_edges, obi); } } @@ -2562,14 +2698,25 @@ static bool lineart_triangle_get_other_verts(const LineartTriangle *tri, return false; } -static bool lineart_edge_from_triangle(const LineartTriangle *tri, - const LineartEdge *e, - bool allow_overlapping_edges) +bool lineart_edge_from_triangle(const LineartTriangle *tri, + const LineartEdge *e, + bool allow_overlapping_edges) { - /* Normally we just determine from the pointer address. */ - if (e->t1 == tri || e->t2 == tri) { - return true; + const LineartEdge *use_e = e; + if (e->flags & LRT_EDGE_FLAG_LIGHT_CONTOUR) { + if (((e->target_reference & LRT_LIGHT_CONTOUR_TARGET) == tri->target_reference) || + (((e->target_reference >> 32) & LRT_LIGHT_CONTOUR_TARGET) == tri->target_reference)) { + return true; + } } + else { + /* Normally we just determine from identifiers of adjacent triangles. */ + if ((use_e->t1 && use_e->t1->target_reference == tri->target_reference) || + (use_e->t2 && use_e->t2->target_reference == tri->target_reference)) { + return true; + } + } + /* If allows overlapping, then we compare the vertex coordinates one by one to determine if one * edge is from specific triangle. This is slower but can handle edge split cases very well. */ if (allow_overlapping_edges) { @@ -2618,6 +2765,9 @@ static bool lineart_edge_from_triangle(const LineartTriangle *tri, (num > is[order[1]] ? order[1] : (num > is[order[0]] ? order[0] : -1))); \ } +#define LRT_ISEC(index) (index == 0 ? isec_e1 : (index == 1 ? isec_e2 : isec_e3)) +#define LRT_PARALLEL(index) (index == 0 ? para_e1 : (index == 1 ? para_e2 : para_e3)) + /** * This is the main function to calculate * the occlusion status between 1(one) triangle and 1(one) line. @@ -2631,7 +2781,7 @@ static bool lineart_edge_from_triangle(const LineartTriangle *tri, * 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 + * 2) Currently using discrete a/b/c/para_e1/para_e2/para_e3/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. * @@ -2640,31 +2790,32 @@ static bool lineart_edge_from_triangle(const LineartTriangle *tri, * While current "edge aligned" fix isn't ideal, it does solve most of the precision issue * especially in orthographic camera mode. */ -static bool lineart_triangle_edge_image_space_occlusion(SpinLock *UNUSED(spl), - const LineartTriangle *tri, +static bool lineart_triangle_edge_image_space_occlusion(const LineartTriangle *tri, const LineartEdge *e, const double *override_camera_loc, const bool override_cam_is_persp, const bool allow_overlapping_edges, - const double vp[4][4], - const double *camera_dir, + const double m_view_projection[4][4], + const double camera_dir[3], const float cam_shift_x, const float cam_shift_y, double *from, double *to) { - double is[3] = {0}; - int order[3]; - int LCross = -1, RCross = -1; - int a, b, c; /* Crossing info. */ - bool pa, pb, pc; /* Parallel info. */ - int st_l = 0, st_r = 0; - - double Lv[3]; - double Rv[3]; - double vd4[4]; - double Cv[3]; - double dot_l, dot_r, dot_la, dot_ra; + double cross_ratios[3] = {0}; + int cross_order[3]; + int cross_v1 = -1, cross_v2 = -1; + /* If the edge intersects with the triangle edges (including extensions). */ + int isec_e1, isec_e2, isec_e3; + /* If edge is parallel to one of the edges in the triangle. */ + bool para_e1, para_e2, para_e3; + enum LineartPointTri state_v1 = LRT_OUTSIDE_TRIANGLE, state_v2 = LRT_OUTSIDE_TRIANGLE; + + double dir_v1[3]; + double dir_v2[3]; + double view_vector[4]; + double dir_cam[3]; + double dot_v1, dot_v2, dot_v1a, dot_v2a; double dot_f; double gloc[4], trans[4]; double cut = -1; @@ -2687,31 +2838,37 @@ 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_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); + isec_e1 = lineart_intersect_seg_seg(LFBC, RFBC, FBC0, FBC1, &cross_ratios[0], ¶_e1); + isec_e2 = lineart_intersect_seg_seg(LFBC, RFBC, FBC1, FBC2, &cross_ratios[1], ¶_e2); + isec_e3 = lineart_intersect_seg_seg(LFBC, RFBC, FBC2, FBC0, &cross_ratios[2], ¶_e3); /* Sort the intersection distance. */ - INTERSECT_SORT_MIN_TO_MAX_3(is[0], is[1], is[2], order); + INTERSECT_SORT_MIN_TO_MAX_3(cross_ratios[0], cross_ratios[1], cross_ratios[2], cross_order); - sub_v3_v3v3_db(Lv, e->v1->gloc, tri->v[0]->gloc); - sub_v3_v3v3_db(Rv, e->v2->gloc, tri->v[0]->gloc); + sub_v3_v3v3_db(dir_v1, e->v1->gloc, tri->v[0]->gloc); + sub_v3_v3v3_db(dir_v2, e->v2->gloc, tri->v[0]->gloc); - copy_v3_v3_db(Cv, camera_dir); - - if (override_cam_is_persp) { - copy_v3_v3_db(vd4, override_camera_loc); - } - else { - copy_v4_v4_db(vd4, override_camera_loc); - } + copy_v3_v3_db(dir_cam, camera_dir); + copy_v3_v3_db(view_vector, override_camera_loc); if (override_cam_is_persp) { - sub_v3_v3v3_db(Cv, vd4, tri->v[0]->gloc); + sub_v3_v3v3_db(dir_cam, view_vector, tri->v[0]->gloc); } - dot_l = dot_v3v3_db(Lv, tri->gn); - dot_r = dot_v3v3_db(Rv, tri->gn); - dot_f = dot_v3v3_db(Cv, tri->gn); + dot_v1 = dot_v3v3_db(dir_v1, tri->gn); + dot_v2 = dot_v3v3_db(dir_v2, tri->gn); + dot_f = dot_v3v3_db(dir_cam, tri->gn); + + if ((e->flags & LRT_EDGE_FLAG_PROJECTED_SHADOW) && + (e->target_reference == tri->target_reference)) { + if (((dot_f > 0) && (e->flags & LRT_EDGE_FLAG_SHADOW_FACING_LIGHT)) || + ((dot_f < 0) && (!(e->flags & LRT_EDGE_FLAG_SHADOW_FACING_LIGHT)))) { + *from = 0.0f; + *to = 1.0f; + return true; + } + + return false; + } /* NOTE(Yiming): When we don't use `dot_f==0` here, it's theoretically possible that _some_ * faces in perspective mode would get erroneously caught in this condition where they really @@ -2722,46 +2879,45 @@ static bool lineart_triangle_edge_image_space_occlusion(SpinLock *UNUSED(spl), return false; } + /* Whether two end points are inside/on_the_edge/outside of the triangle. */ + state_v1 = lineart_point_triangle_relation(LFBC, FBC0, FBC1, FBC2); + state_v2 = lineart_point_triangle_relation(RFBC, FBC0, FBC1, FBC2); + /* If the edge doesn't visually cross any edge of the triangle... */ - if (!a && !b && !c) { + if (!isec_e1 && !isec_e2 && !isec_e3) { /* 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))) { + if ((!state_v1) && (!state_v2)) { 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); - /* Determine the cut position. */ - dot_la = fabs(dot_l); - if (dot_la < DBL_EPSILON) { - dot_la = 0; - dot_l = 0; + dot_v1a = fabs(dot_v1); + if (dot_v1a < DBL_EPSILON) { + dot_v1a = 0; + dot_v1 = 0; } - dot_ra = fabs(dot_r); - if (dot_ra < DBL_EPSILON) { - dot_ra = 0; - dot_r = 0; + dot_v2a = fabs(dot_v2); + if (dot_v2a < DBL_EPSILON) { + dot_v2a = 0; + dot_v2 = 0; } - if (dot_l - dot_r == 0) { + if (dot_v1 - dot_v2 == 0) { cut = 100000; } - else if (dot_l * dot_r <= 0) { - cut = dot_la / fabs(dot_l - dot_r); + else if (dot_v1 * dot_v2 <= 0) { + cut = dot_v1a / fabs(dot_v1 - dot_v2); } else { - cut = fabs(dot_r + dot_l) / fabs(dot_l - dot_r); - cut = dot_ra > dot_la ? 1 - cut : cut; + cut = fabs(dot_v2 + dot_v1) / fabs(dot_v1 - dot_v2); + cut = dot_v2a > dot_v1a ? 1 - cut : cut; } /* Transform the cut from geometry space to image space. */ if (override_cam_is_persp) { interp_v3_v3v3_db(gloc, e->v1->gloc, e->v2->gloc, cut); - mul_v4_m4v3_db(trans, vp, gloc); + mul_v4_m4v3_db(trans, m_view_projection, gloc); mul_v3db_db(trans, (1 / trans[3])); trans[0] -= cam_shift_x * 2; trans[1] -= cam_shift_y * 2; @@ -2776,7 +2932,7 @@ static bool lineart_triangle_edge_image_space_occlusion(SpinLock *UNUSED(spl), } #define LRT_GUARD_NOT_FOUND \ - if (LCross < 0 || RCross < 0) { \ + if (cross_v1 < 0 || cross_v2 < 0) { \ return false; \ } @@ -2784,95 +2940,97 @@ static bool lineart_triangle_edge_image_space_occlusion(SpinLock *UNUSED(spl), * indicates triangle boundary. DBL_TRIANGLE_LIM is needed to for floating point precision * tolerance. */ - if (st_l == 2) { + if (state_v1 == LRT_INSIDE_TRIANGLE) { /* Left side is in the triangle. */ - if (st_r == 2) { + if (state_v2 == LRT_INSIDE_TRIANGLE) { /* | l---r | */ - INTERSECT_JUST_SMALLER(is, order, DBL_TRIANGLE_LIM, LCross); - INTERSECT_JUST_GREATER(is, order, 1 - DBL_TRIANGLE_LIM, RCross); + INTERSECT_JUST_SMALLER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v1); + INTERSECT_JUST_GREATER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v2); } - else if (st_r == 1) { + else if (state_v2 == LRT_ON_TRIANGLE) { /* | l------r| */ - INTERSECT_JUST_SMALLER(is, order, DBL_TRIANGLE_LIM, LCross); - INTERSECT_JUST_GREATER(is, order, 1 - DBL_TRIANGLE_LIM, RCross); + INTERSECT_JUST_SMALLER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v1); + INTERSECT_JUST_GREATER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v2); } - else if (st_r == 0) { + else if (state_v2 == LRT_OUTSIDE_TRIANGLE) { /* | l-------|------r */ - INTERSECT_JUST_SMALLER(is, order, DBL_TRIANGLE_LIM, LCross); - INTERSECT_JUST_GREATER(is, order, 0, RCross); + INTERSECT_JUST_SMALLER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v1); + INTERSECT_JUST_GREATER(cross_ratios, cross_order, 0, cross_v2); } } - else if (st_l == 1) { + else if (state_v1 == LRT_ON_TRIANGLE) { /* Left side is on some edge of the triangle. */ - if (st_r == 2) { + if (state_v2 == LRT_INSIDE_TRIANGLE) { /* |l------r | */ - INTERSECT_JUST_SMALLER(is, order, DBL_TRIANGLE_LIM, LCross); - INTERSECT_JUST_GREATER(is, order, 1 - DBL_TRIANGLE_LIM, RCross); + INTERSECT_JUST_SMALLER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v1); + INTERSECT_JUST_GREATER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v2); } - else if (st_r == 1) { + else if (state_v2 == LRT_ON_TRIANGLE) { /* |l---------r| */ - INTERSECT_JUST_SMALLER(is, order, DBL_TRIANGLE_LIM, LCross); - INTERSECT_JUST_GREATER(is, order, 1 - DBL_TRIANGLE_LIM, RCross); + INTERSECT_JUST_SMALLER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v1); + INTERSECT_JUST_GREATER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v2); } - else if (st_r == 0) { + else if (state_v2 == LRT_OUTSIDE_TRIANGLE) { /* |l----------|-------r (crossing the triangle) [OR] * r---------|l | (not crossing the triangle) */ - INTERSECT_JUST_GREATER(is, order, DBL_TRIANGLE_LIM, RCross); - if (RCross >= 0 && LRT_ABC(RCross) && is[RCross] > (DBL_TRIANGLE_LIM)) { - INTERSECT_JUST_SMALLER(is, order, DBL_TRIANGLE_LIM, LCross); + INTERSECT_JUST_GREATER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v2); + if (cross_v2 >= 0 && LRT_ISEC(cross_v2) && cross_ratios[cross_v2] > (DBL_TRIANGLE_LIM)) { + INTERSECT_JUST_SMALLER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v1); } else { - INTERSECT_JUST_SMALLER(is, order, DBL_TRIANGLE_LIM, RCross); - if (RCross > 0) { - INTERSECT_JUST_SMALLER(is, order, is[RCross], LCross); + INTERSECT_JUST_SMALLER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v2); + if (cross_v2 > 0) { + INTERSECT_JUST_SMALLER(cross_ratios, cross_order, cross_ratios[cross_v2], cross_v1); } } 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))) { + if ((LRT_PARALLEL(cross_v1) && !LRT_ISEC(cross_v1)) || + (LRT_PARALLEL(cross_v2) && !LRT_ISEC(cross_v2))) { return false; } } } - else if (st_l == 0) { + else if (state_v1 == LRT_OUTSIDE_TRIANGLE) { /* Left side is outside of the triangle. */ - if (st_r == 2) { + if (state_v2 == LRT_INSIDE_TRIANGLE) { /* l---|---r | */ - INTERSECT_JUST_SMALLER(is, order, 1 - DBL_TRIANGLE_LIM, LCross); - INTERSECT_JUST_GREATER(is, order, 1 - DBL_TRIANGLE_LIM, RCross); + INTERSECT_JUST_SMALLER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v1); + INTERSECT_JUST_GREATER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v2); } - else if (st_r == 1) { + else if (state_v2 == LRT_ON_TRIANGLE) { /* |r----------|-------l (crossing the triangle) [OR] * l---------|r | (not crossing the triangle) */ - INTERSECT_JUST_SMALLER(is, order, 1 - DBL_TRIANGLE_LIM, LCross); - if (LCross >= 0 && LRT_ABC(LCross) && is[LCross] < (1 - DBL_TRIANGLE_LIM)) { - INTERSECT_JUST_GREATER(is, order, 1 - DBL_TRIANGLE_LIM, RCross); + INTERSECT_JUST_SMALLER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v1); + if (cross_v1 >= 0 && LRT_ISEC(cross_v1) && cross_ratios[cross_v1] < (1 - DBL_TRIANGLE_LIM)) { + INTERSECT_JUST_GREATER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v2); } else { - INTERSECT_JUST_GREATER(is, order, 1 - DBL_TRIANGLE_LIM, LCross); - if (LCross > 0) { - INTERSECT_JUST_GREATER(is, order, is[LCross], RCross); + INTERSECT_JUST_GREATER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v1); + if (cross_v1 > 0) { + INTERSECT_JUST_GREATER(cross_ratios, cross_order, cross_ratios[cross_v1], cross_v2); } } LRT_GUARD_NOT_FOUND /* The same logic applies as above case. */ - if ((LRT_PABC(LCross) && !LRT_ABC(LCross)) || (LRT_PABC(RCross) && !LRT_ABC(RCross))) { + if ((LRT_PARALLEL(cross_v1) && !LRT_ISEC(cross_v1)) || + (LRT_PARALLEL(cross_v2) && !LRT_ISEC(cross_v2))) { return false; } } - else if (st_r == 0) { + else if (state_v2 == LRT_OUTSIDE_TRIANGLE) { /* 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); + INTERSECT_JUST_GREATER(cross_ratios, cross_order, -DBL_TRIANGLE_LIM, cross_v1); + if (cross_v1 >= 0 && LRT_ISEC(cross_v1)) { + INTERSECT_JUST_GREATER(cross_ratios, cross_order, cross_ratios[cross_v1], cross_v2); } else { - if (LCross >= 0) { - INTERSECT_JUST_GREATER(is, order, is[LCross], LCross); - if (LCross >= 0) { - INTERSECT_JUST_GREATER(is, order, is[LCross], RCross); + if (cross_v1 >= 0) { + INTERSECT_JUST_GREATER(cross_ratios, cross_order, cross_ratios[cross_v1], cross_v1); + if (cross_v1 >= 0) { + INTERSECT_JUST_GREATER(cross_ratios, cross_order, cross_ratios[cross_v1], cross_v2); } } } @@ -2881,28 +3039,28 @@ 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; + double dot_1f = dot_v1 * dot_f, dot_2f = dot_v2 * dot_f; /* Determine the start and end point of image space cut on a line. */ - if (LF <= 0 && RF <= 0 && (dot_l || dot_r)) { - *from = MAX2(0, is[LCross]); - *to = MIN2(1, is[RCross]); + if (dot_1f <= 0 && dot_2f <= 0 && (dot_v1 || dot_v2)) { + *from = MAX2(0, cross_ratios[cross_v1]); + *to = MIN2(1, cross_ratios[cross_v2]); if (*from >= *to) { return false; } return true; } - if (LF >= 0 && RF <= 0 && (dot_l || dot_r)) { - *from = MAX2(cut, is[LCross]); - *to = MIN2(1, is[RCross]); + if (dot_1f >= 0 && dot_2f <= 0 && (dot_v1 || dot_v2)) { + *from = MAX2(cut, cross_ratios[cross_v1]); + *to = MIN2(1, cross_ratios[cross_v2]); if (*from >= *to) { return false; } return true; } - if (LF <= 0 && RF >= 0 && (dot_l || dot_r)) { - *from = MAX2(0, is[LCross]); - *to = MIN2(cut, is[RCross]); + if (dot_1f <= 0 && dot_2f >= 0 && (dot_v1 || dot_v2)) { + *from = MAX2(0, cross_ratios[cross_v1]); + *to = MIN2(cut, cross_ratios[cross_v2]); if (*from >= *to) { return false; } @@ -2916,6 +3074,8 @@ static bool lineart_triangle_edge_image_space_occlusion(SpinLock *UNUSED(spl), #undef INTERSECT_SORT_MIN_TO_MAX_3 #undef INTERSECT_JUST_GREATER #undef INTERSECT_JUST_SMALLER +#undef LRT_ISEC +#undef LRT_PARALLEL /** * At this stage of the computation we don't have triangle adjacent info anymore, @@ -2997,272 +3157,242 @@ static LineartVert *lineart_triangle_share_point(const LineartTriangle *l, return NULL; } -/** - * To save time and prevent overlapping lines when computing intersection lines. - */ -static bool lineart_vert_already_intersected_2v(LineartVertIntersection *vt, - LineartVertIntersection *v1, - LineartVertIntersection *v2) -{ - return ((vt->isec1 == v1->base.index && vt->isec2 == v2->base.index) || - (vt->isec2 == v2->base.index && vt->isec1 == v1->base.index)); -} - -static void lineart_vert_set_intersection_2v(LineartVert *vt, LineartVert *v1, LineartVert *v2) -{ - LineartVertIntersection *irv = (LineartVertIntersection *)vt; - irv->isec1 = v1->index; - irv->isec2 = v2->index; -} - -/** - * This tests a triangle against a virtual line represented by `v1---v2`. - * The vertices returned after repeated calls to this function - * is then used to create a triangle/triangle intersection line. - */ -static LineartVert *lineart_triangle_2v_intersection_test(LineartRenderBuffer *rb, - LineartVert *v1, - LineartVert *v2, - LineartTriangle *tri, - LineartTriangle *testing, - LineartVert *last) +static bool lineart_triangle_2v_intersection_math( + LineartVert *v1, LineartVert *v2, LineartTriangle *tri, const double *last, double *rv) { - double Lv[3]; - double Rv[3]; - double dot_l, dot_r; - LineartVert *result; + /* Direction vectors for the edge verts. We will check if the verts are on the same side of the + * triangle or not. */ + double dir_v1[3], dir_v2[3]; + double dot_v1, dot_v2; double gloc[3]; - LineartVert *l = v1, *r = v2; - for (LinkNode *ln = (void *)testing->intersecting_verts; ln; ln = ln->next) { - LineartVertIntersection *vt = ln->link; - if (vt->intersecting_with == tri && - lineart_vert_already_intersected_2v( - vt, (LineartVertIntersection *)l, (LineartVertIntersection *)r)) { - return (LineartVert *)vt; - } - } - - sub_v3_v3v3_db(Lv, l->gloc, testing->v[0]->gloc); - sub_v3_v3v3_db(Rv, r->gloc, testing->v[0]->gloc); + sub_v3_v3v3_db(dir_v1, v1->gloc, tri->v[0]->gloc); + sub_v3_v3v3_db(dir_v2, v2->gloc, tri->v[0]->gloc); - dot_l = dot_v3v3_db(Lv, testing->gn); - dot_r = dot_v3v3_db(Rv, testing->gn); + dot_v1 = dot_v3v3_db(dir_v1, tri->gn); + dot_v2 = dot_v3v3_db(dir_v2, tri->gn); - if (dot_l * dot_r > 0 || (!dot_l && !dot_r)) { - return 0; + if (dot_v1 * dot_v2 > 0 || (!dot_v1 && !dot_v2)) { + return false; } - dot_l = fabs(dot_l); - dot_r = fabs(dot_r); + dot_v1 = fabs(dot_v1); + dot_v2 = fabs(dot_v2); - interp_v3_v3v3_db(gloc, l->gloc, r->gloc, dot_l / (dot_l + dot_r)); + interp_v3_v3v3_db(gloc, v1->gloc, v2->gloc, dot_v1 / (dot_v1 + dot_v2)); - /* Due to precision issue, we might end up with the same point as the one we already detected. - */ - if (last && LRT_DOUBLE_CLOSE_ENOUGH(last->gloc[0], gloc[0]) && - LRT_DOUBLE_CLOSE_ENOUGH(last->gloc[1], gloc[1]) && - LRT_DOUBLE_CLOSE_ENOUGH(last->gloc[2], gloc[2])) { - return NULL; + /* Due to precision issue, we might end up with the same point as the one we already detected. */ + if (last && LRT_DOUBLE_CLOSE_ENOUGH(last[0], gloc[0]) && + LRT_DOUBLE_CLOSE_ENOUGH(last[1], gloc[1]) && LRT_DOUBLE_CLOSE_ENOUGH(last[2], gloc[2])) { + return false; } if (!(lineart_point_inside_triangle3d( - gloc, testing->v[0]->gloc, testing->v[1]->gloc, testing->v[2]->gloc))) { - return NULL; + gloc, tri->v[0]->gloc, tri->v[1]->gloc, tri->v[2]->gloc))) { + return false; } - /* This is an intersection vert, the size is bigger than LineartVert, - * allocated separately. */ - result = lineart_mem_acquire(&rb->render_data_pool, sizeof(LineartVertIntersection)); - - /* Indicate the data structure difference. */ - result->flag = LRT_VERT_HAS_INTERSECTION_DATA; + copy_v3_v3_db(rv, gloc); - copy_v3_v3_db(result->gloc, gloc); - - lineart_prepend_pool(&testing->intersecting_verts, &rb->render_data_pool, result); - - return result; + return true; } -/** - * Test if two triangles intersect. Generates one intersection line if the check succeeds. - */ -static LineartEdge *lineart_triangle_intersect(LineartRenderBuffer *rb, - LineartTriangle *tri, - LineartTriangle *testing) +static bool lineart_triangle_intersect_math(LineartTriangle *tri, + LineartTriangle *t2, + double *v1, + double *v2) { - LineartVert *v1 = 0, *v2 = 0; - LineartVert **next = &v1; - LineartEdge *result; - LineartVert *E0T = 0; - LineartVert *E1T = 0; - LineartVert *E2T = 0; - LineartVert *TE0 = 0; - LineartVert *TE1 = 0; - LineartVert *TE2 = 0; + double *next = v1, *last = NULL; LineartVert *sv1, *sv2; - double cl[3]; - double ZMin, ZMax; - ZMax = rb->far_clip; - ZMin = rb->near_clip; - copy_v3_v3_db(cl, rb->camera_pos); - LineartVert *share = lineart_triangle_share_point(testing, tri); + LineartVert *share = lineart_triangle_share_point(t2, tri); if (share) { /* If triangles have sharing points like `abc` and `acd`, then we only need to detect `bc` * against `acd` or `cd` against `abc`. */ - LineartVert *new_share; lineart_triangle_get_other_verts(tri, share, &sv1, &sv2); - v1 = new_share = lineart_mem_acquire(&rb->render_data_pool, (sizeof(LineartVertIntersection))); - - new_share->flag = LRT_VERT_HAS_INTERSECTION_DATA; - - copy_v3_v3_db(new_share->gloc, share->gloc); + copy_v3_v3_db(v1, share->gloc); - v2 = lineart_triangle_2v_intersection_test(rb, sv1, sv2, tri, testing, 0); - - if (v2 == NULL) { - lineart_triangle_get_other_verts(testing, share, &sv1, &sv2); - v2 = lineart_triangle_2v_intersection_test(rb, sv1, sv2, testing, tri, 0); - if (v2 == NULL) { - return 0; + if (!lineart_triangle_2v_intersection_math(sv1, sv2, t2, 0, v2)) { + lineart_triangle_get_other_verts(t2, share, &sv1, &sv2); + if (lineart_triangle_2v_intersection_math(sv1, sv2, tri, 0, v2)) { + return true; } - lineart_prepend_pool(&testing->intersecting_verts, &rb->render_data_pool, new_share); - } - else { - lineart_prepend_pool(&tri->intersecting_verts, &rb->render_data_pool, new_share); } } else { /* If not sharing any points, then we need to try all the possibilities. */ - E0T = lineart_triangle_2v_intersection_test(rb, tri->v[0], tri->v[1], tri, testing, 0); - if (E0T && (!(*next))) { - (*next) = E0T; - lineart_vert_set_intersection_2v((*next), tri->v[0], tri->v[1]); - next = &v2; - } - E1T = lineart_triangle_2v_intersection_test(rb, tri->v[1], tri->v[2], tri, testing, v1); - if (E1T && (!(*next))) { - (*next) = E1T; - lineart_vert_set_intersection_2v((*next), tri->v[1], tri->v[2]); - next = &v2; - } - if (!(*next)) { - E2T = lineart_triangle_2v_intersection_test(rb, tri->v[2], tri->v[0], tri, testing, v1); - } - if (E2T && (!(*next))) { - (*next) = E2T; - lineart_vert_set_intersection_2v((*next), tri->v[2], tri->v[0]); - next = &v2; + if (lineart_triangle_2v_intersection_math(tri->v[0], tri->v[1], t2, 0, v1)) { + next = v2; + last = v1; } - if (!(*next)) { - TE0 = lineart_triangle_2v_intersection_test( - rb, testing->v[0], testing->v[1], testing, tri, v1); - } - if (TE0 && (!(*next))) { - (*next) = TE0; - lineart_vert_set_intersection_2v((*next), testing->v[0], testing->v[1]); - next = &v2; + if (lineart_triangle_2v_intersection_math(tri->v[1], tri->v[2], t2, last, next)) { + if (last) { + return true; + } + next = v2; + last = v1; } - if (!(*next)) { - TE1 = lineart_triangle_2v_intersection_test( - rb, testing->v[1], testing->v[2], testing, tri, v1); + if (lineart_triangle_2v_intersection_math(tri->v[2], tri->v[0], t2, last, next)) { + if (last) { + return true; + } + next = v2; + last = v1; } - if (TE1 && (!(*next))) { - (*next) = TE1; - lineart_vert_set_intersection_2v((*next), testing->v[1], testing->v[2]); - next = &v2; + + if (lineart_triangle_2v_intersection_math(t2->v[0], t2->v[1], tri, last, next)) { + if (last) { + return true; + } + next = v2; + last = v1; } - if (!(*next)) { - TE2 = lineart_triangle_2v_intersection_test( - rb, testing->v[2], testing->v[0], testing, tri, v1); + if (lineart_triangle_2v_intersection_math(t2->v[1], t2->v[2], tri, last, next)) { + if (last) { + return true; + } + next = v2; + last = v1; } - if (TE2 && (!(*next))) { - (*next) = TE2; - lineart_vert_set_intersection_2v((*next), testing->v[2], testing->v[0]); - next = &v2; + if (lineart_triangle_2v_intersection_math(t2->v[2], t2->v[0], tri, last, next)) { + if (last) { + return true; + } + next = v2; + last = v1; } + } + return false; +} - if (!(*next)) { - return 0; - } +static void lineart_add_isec_thread(LineartIsecThread *th, + const double *v1, + const double *v2, + LineartTriangle *tri1, + LineartTriangle *tri2) +{ + if (th->current == th->max) { + + LineartIsecSingle *new_array = MEM_mallocN(sizeof(LineartIsecSingle) * th->max * 2, + "LineartIsecSingle"); + memcpy(new_array, th->array, sizeof(LineartIsecSingle) * th->max); + th->max *= 2; + MEM_freeN(th->array); + th->array = new_array; + } + LineartIsecSingle *isec_single = &th->array[th->current]; + copy_v3fl_v3db(isec_single->v1, v1); + copy_v3fl_v3db(isec_single->v2, v2); + isec_single->tri1 = tri1; + isec_single->tri2 = tri2; + if (tri1->target_reference > tri2->target_reference) { + SWAP(LineartTriangle *, isec_single->tri1, isec_single->tri2); + } + th->current++; +} + +#define LRT_ISECT_TRIANGLE_PER_THREAD 4096 + +static bool lineart_schedule_new_triangle_task(LineartIsecThread *th) +{ + LineartData *ld = th->ld; + int remaining = LRT_ISECT_TRIANGLE_PER_THREAD; + + BLI_spin_lock(&ld->lock_task); + LineartElementLinkNode *eln = ld->isect_scheduled_up_to; + + if (!eln) { + BLI_spin_unlock(&ld->lock_task); + return false; } - /* The intersection line has been generated only in geometry space, so we need to transform - * them as well. */ - mul_v4_m4v3_db(v1->fbcoord, rb->view_projection, v1->gloc); - mul_v4_m4v3_db(v2->fbcoord, rb->view_projection, v2->gloc); - if (rb->cam_is_persp) { - mul_v3db_db(v1->fbcoord, (1 / v1->fbcoord[3])); - mul_v3db_db(v2->fbcoord, (1 / v2->fbcoord[3])); + th->pending_from = eln; + th->index_from = ld->isect_scheduled_up_to_index; + + while (remaining > 0 && eln) { + int remaining_this_eln = eln->element_count - ld->isect_scheduled_up_to_index; + int added_count = MIN2(remaining, remaining_this_eln); + remaining -= added_count; + if (remaining || added_count == remaining_this_eln) { + eln = eln->next; + ld->isect_scheduled_up_to = eln; + ld->isect_scheduled_up_to_index = 0; + } + else { + ld->isect_scheduled_up_to_index += added_count; + } } - v1->fbcoord[0] -= rb->shift_x * 2; - v1->fbcoord[1] -= rb->shift_y * 2; - v2->fbcoord[0] -= rb->shift_x * 2; - v2->fbcoord[1] -= rb->shift_y * 2; - /* This z transformation is not the same as the rest of the part, because the data don't go - * through normal perspective division calls in the pipeline, but this way the 3D result and - * occlusion on the generated line is correct, and we don't really use 2D for viewport stroke - * generation anyway. */ - v1->fbcoord[2] = ZMin * ZMax / (ZMax - fabs(v1->fbcoord[2]) * (ZMax - ZMin)); - v2->fbcoord[2] = ZMin * ZMax / (ZMax - fabs(v2->fbcoord[2]) * (ZMax - ZMin)); + th->pending_to = eln ? eln : ld->geom.triangle_buffer_pointers.last; + th->index_to = ld->isect_scheduled_up_to_index; - ((LineartVertIntersection *)v1)->intersecting_with = tri; - ((LineartVertIntersection *)v2)->intersecting_with = testing; + BLI_spin_unlock(&ld->lock_task); - result = lineart_mem_acquire(&rb->render_data_pool, sizeof(LineartEdge)); - result->v1 = v1; - result->v2 = v2; - result->t1 = tri; - result->t2 = testing; + return true; +} - LineartEdgeSegment *es = lineart_mem_acquire(&rb->render_data_pool, sizeof(LineartEdgeSegment)); - BLI_addtail(&result->segments, es); - /* Don't need to OR flags right now, just a type mark. */ - result->flags = LRT_EDGE_FLAG_INTERSECTION; - result->intersection_mask = (tri->intersection_mask | testing->intersection_mask); +/* This function initializes two things: + * 1) Triangle array scheduling info, for each worker thread to get its chunk from the scheduler. + * 2) Per-thread intersection result array. Does not store actual #LineartEdge, these results will + * be finalized by #lineart_create_edges_from_isec_data + */ +static void lineart_init_isec_thread(LineartIsecData *d, LineartData *ld, int thread_count) +{ + d->threads = MEM_callocN(sizeof(LineartIsecThread) * thread_count, "LineartIsecThread arr"); + d->ld = ld; + d->thread_count = thread_count; - lineart_add_edge_to_array(&rb->pending_edges, result); + ld->isect_scheduled_up_to = ld->geom.triangle_buffer_pointers.first; + ld->isect_scheduled_up_to_index = 0; - return result; + for (int i = 0; i < thread_count; i++) { + LineartIsecThread *it = &d->threads[i]; + it->array = MEM_mallocN(sizeof(LineartIsecSingle) * 100, "LineartIsecSingle arr"); + it->max = 100; + it->current = 0; + it->thread_id = i; + it->ld = ld; + } } -static void lineart_triangle_intersect_in_bounding_area(LineartRenderBuffer *rb, - LineartTriangle *tri, - LineartBoundingArea *ba) +static void lineart_destroy_isec_thread(LineartIsecData *d) { - /* Testing_triangle->testing[0] is used to store pairing triangle reference. - * See definition of LineartTriangleThread for more info. */ - LineartTriangle *testing_triangle; - LineartTriangleThread *tt; + for (int i = 0; i < d->thread_count; i++) { + LineartIsecThread *it = &d->threads[i]; + MEM_freeN(it->array); + } + MEM_freeN(d->threads); +} - double *G0 = tri->v[0]->gloc, *G1 = tri->v[1]->gloc, *G2 = tri->v[2]->gloc; +static void lineart_triangle_intersect_in_bounding_area(LineartTriangle *tri, + LineartBoundingArea *ba, + LineartIsecThread *th, + int up_to) +{ + BLI_assert(th != NULL); - /* If this is not the smallest subdiv bounding area. */ - if (ba->child) { - lineart_triangle_intersect_in_bounding_area(rb, tri, &ba->child[0]); - lineart_triangle_intersect_in_bounding_area(rb, tri, &ba->child[1]); - lineart_triangle_intersect_in_bounding_area(rb, tri, &ba->child[2]); - lineart_triangle_intersect_in_bounding_area(rb, tri, &ba->child[3]); + if (!th) { return; } - /* If this _is_ the smallest subdiv bounding area, then do the intersections there. */ - for (int i = 0; i < ba->triangle_count; i++) { - testing_triangle = ba->linked_triangles[i]; - tt = (LineartTriangleThread *)testing_triangle; + double *G0 = tri->v[0]->gloc, *G1 = tri->v[1]->gloc, *G2 = tri->v[2]->gloc; - if (testing_triangle == tri || tt->testing_e[0] == (LineartEdge *)tri) { + /* If this _is_ the smallest subdivision bounding area, then do the intersections there. */ + for (int i = 0; i < up_to; i++) { + /* Testing_triangle->testing[0] is used to store pairing triangle reference. + * See definition of LineartTriangleThread for more info. */ + LineartTriangle *testing_triangle = ba->linked_triangles[i]; + LineartTriangleThread *tt = (LineartTriangleThread *)testing_triangle; + + if (testing_triangle == tri || tt->testing_e[th->thread_id] == (LineartEdge *)tri) { continue; } - tt->testing_e[0] = (LineartEdge *)tri; + tt->testing_e[th->thread_id] = (LineartEdge *)tri; if ((testing_triangle->flags & LRT_TRIANGLE_NO_INTERSECTION) || ((testing_triangle->flags & LRT_TRIANGLE_INTERSECTION_ONLY) && @@ -3285,65 +3415,106 @@ static void lineart_triangle_intersect_in_bounding_area(LineartRenderBuffer *rb, } /* If we do need to compute intersection, then finally do it. */ - lineart_triangle_intersect(rb, tri, testing_triangle); + + double iv1[3], iv2[3]; + if (lineart_triangle_intersect_math(tri, testing_triangle, iv1, iv2)) { + lineart_add_isec_thread(th, iv1, iv2, tri, testing_triangle); + } } } /** * The calculated view vector will point towards the far-plane from the camera position. */ -static void lineart_main_get_view_vector(LineartRenderBuffer *rb) +void lineart_main_get_view_vector(LineartData *ld) { float direction[3] = {0, 0, 1}; float trans[3]; float inv[4][4]; float obmat_no_scale[4][4]; - copy_m4_m4(obmat_no_scale, rb->cam_obmat); - + copy_m4_m4(obmat_no_scale, ld->conf.cam_obmat); normalize_v3(obmat_no_scale[0]); normalize_v3(obmat_no_scale[1]); normalize_v3(obmat_no_scale[2]); invert_m4_m4(inv, obmat_no_scale); transpose_m4(inv); mul_v3_mat3_m4v3(trans, inv, direction); - copy_m4_m4(rb->cam_obmat, obmat_no_scale); - copy_v3db_v3fl(rb->view_vector, trans); + copy_m4_m4(ld->conf.cam_obmat, obmat_no_scale); + copy_v3db_v3fl(ld->conf.view_vector, trans); + + if (ld->conf.light_reference_available) { + copy_m4_m4(obmat_no_scale, ld->conf.cam_obmat_secondary); + normalize_v3(obmat_no_scale[0]); + normalize_v3(obmat_no_scale[1]); + normalize_v3(obmat_no_scale[2]); + invert_m4_m4(inv, obmat_no_scale); + transpose_m4(inv); + mul_v3_mat3_m4v3(trans, inv, direction); + copy_m4_m4(ld->conf.cam_obmat_secondary, obmat_no_scale); + copy_v3db_v3fl(ld->conf.view_vector_secondary, trans); + } +} + +static void lineart_end_bounding_area_recursive(LineartBoundingArea *ba) +{ + BLI_spin_end(&ba->lock); + if (ba->child) { + for (int i = 0; i < 4; i++) { + lineart_end_bounding_area_recursive(&ba->child[i]); + } + } } -static void lineart_destroy_render_data(LineartRenderBuffer *rb) +void lineart_destroy_render_data_keep_init(LineartData *ld) { - if (rb == NULL) { + if (ld == NULL) { return; } - BLI_listbase_clear(&rb->chains); - BLI_listbase_clear(&rb->wasted_cuts); + BLI_listbase_clear(&ld->chains); + BLI_listbase_clear(&ld->wasted_cuts); + + BLI_listbase_clear(&ld->geom.vertex_buffer_pointers); + BLI_listbase_clear(&ld->geom.line_buffer_pointers); + BLI_listbase_clear(&ld->geom.triangle_buffer_pointers); + + if (ld->pending_edges.array) { + MEM_freeN(ld->pending_edges.array); + } - BLI_listbase_clear(&rb->vertex_buffer_pointers); - BLI_listbase_clear(&rb->line_buffer_pointers); - BLI_listbase_clear(&rb->triangle_buffer_pointers); + for (int i = 0; i < ld->qtree.initial_tile_count; i++) { + lineart_end_bounding_area_recursive(&ld->qtree.initials[i]); + } + lineart_free_bounding_area_memories(ld); - BLI_spin_end(&rb->lock_task); - BLI_spin_end(&rb->lock_cuts); - BLI_spin_end(&rb->render_data_pool.lock_mem); + lineart_mem_destroy(&ld->render_data_pool); +} - if (rb->pending_edges.array) { - MEM_freeN(rb->pending_edges.array); +static void lineart_destroy_render_data(LineartData *ld) +{ + if (ld == NULL) { + return; } - lineart_mem_destroy(&rb->render_data_pool); + BLI_spin_end(&ld->lock_task); + BLI_spin_end(&ld->lock_cuts); + BLI_spin_end(&ld->render_data_pool.lock_mem); + + lineart_destroy_render_data_keep_init(ld); + + lineart_mem_destroy(&ld->render_data_pool); } void MOD_lineart_destroy_render_data(LineartGpencilModifierData *lmd) { - LineartRenderBuffer *rb = lmd->render_buffer_ptr; + LineartData *ld = lmd->la_data_ptr; - lineart_destroy_render_data(rb); + lineart_destroy_render_data(ld); - if (rb) { - MEM_freeN(rb); - lmd->render_buffer_ptr = NULL; + if (ld) { + MEM_freeN(ld); + lmd->la_data_ptr = NULL; } if (G.debug_value == 4000) { @@ -3367,17 +3538,17 @@ void MOD_lineart_clear_cache(struct LineartCache **lc) (*lc) = NULL; } -static LineartRenderBuffer *lineart_create_render_buffer(Scene *scene, - LineartGpencilModifierData *lmd, - Object *camera, - Object *active_camera, - LineartCache *lc) +static LineartData *lineart_create_render_buffer(Scene *scene, + LineartGpencilModifierData *lmd, + Object *camera, + Object *active_camera, + LineartCache *lc) { - LineartRenderBuffer *rb = MEM_callocN(sizeof(LineartRenderBuffer), "Line Art render buffer"); + LineartData *ld = MEM_callocN(sizeof(LineartData), "Line Art render buffer"); lmd->cache = lc; - lmd->render_buffer_ptr = rb; - lc->rb_edge_types = lmd->edge_types_override; + lmd->la_data_ptr = ld; + lc->all_enabled_edge_types = lmd->edge_types_override; if (!scene || !camera || !lc) { return NULL; @@ -3390,98 +3561,120 @@ static LineartRenderBuffer *lineart_create_render_buffer(Scene *scene, clipping_offset = 0.0001; } - copy_v3db_v3fl(rb->camera_pos, camera->obmat[3]); + copy_v3db_v3fl(ld->conf.camera_pos, camera->obmat[3]); if (active_camera) { - copy_v3db_v3fl(rb->active_camera_pos, active_camera->obmat[3]); + copy_v3db_v3fl(ld->conf.active_camera_pos, active_camera->obmat[3]); } - copy_m4_m4(rb->cam_obmat, camera->obmat); - rb->cam_is_persp = (c->type == CAM_PERSP); - rb->near_clip = c->clip_start + clipping_offset; - rb->far_clip = c->clip_end - clipping_offset; - rb->w = scene->r.xsch; - rb->h = scene->r.ysch; + copy_m4_m4(ld->conf.cam_obmat, camera->obmat); + + ld->conf.cam_is_persp = (c->type == CAM_PERSP); + ld->conf.near_clip = c->clip_start + clipping_offset; + ld->conf.far_clip = c->clip_end - clipping_offset; + ld->w = scene->r.xsch; + ld->h = scene->r.ysch; - if (rb->cam_is_persp) { - rb->tile_recursive_level = LRT_TILE_RECURSIVE_PERSPECTIVE; + if (ld->conf.cam_is_persp) { + ld->qtree.recursive_level = LRT_TILE_RECURSIVE_PERSPECTIVE; } else { - rb->tile_recursive_level = LRT_TILE_RECURSIVE_ORTHO; + ld->qtree.recursive_level = LRT_TILE_RECURSIVE_ORTHO; } - double asp = ((double)rb->w / (double)rb->h); - int fit = BKE_camera_sensor_fit(c->sensor_fit, rb->w, rb->h); - rb->shift_x = fit == CAMERA_SENSOR_FIT_HOR ? c->shiftx : c->shiftx / asp; - rb->shift_y = fit == CAMERA_SENSOR_FIT_VERT ? c->shifty : c->shifty * asp; + double asp = ((double)ld->w / (double)ld->h); + int fit = BKE_camera_sensor_fit(c->sensor_fit, ld->w, ld->h); + ld->conf.shift_x = fit == CAMERA_SENSOR_FIT_HOR ? c->shiftx : c->shiftx / asp; + ld->conf.shift_y = fit == CAMERA_SENSOR_FIT_VERT ? c->shifty : c->shifty * asp; - rb->overscan = lmd->overscan; + ld->conf.overscan = lmd->overscan; - rb->shift_x /= (1 + rb->overscan); - rb->shift_y /= (1 + rb->overscan); + ld->conf.shift_x /= (1 + ld->conf.overscan); + ld->conf.shift_y /= (1 + ld->conf.overscan); - rb->crease_threshold = cos(M_PI - lmd->crease_threshold); - rb->chaining_image_threshold = lmd->chaining_image_threshold; - rb->angle_splitting_threshold = lmd->angle_splitting_threshold; - rb->chain_smooth_tolerance = lmd->chain_smooth_tolerance; + if (lmd->light_contour_object) { + Object *light_obj = lmd->light_contour_object; + copy_v3db_v3fl(ld->conf.camera_pos_secondary, light_obj->obmat[3]); + copy_m4_m4(ld->conf.cam_obmat_secondary, light_obj->obmat); + ld->conf.light_reference_available = true; + if (light_obj->type == OB_LAMP) { + ld->conf.cam_is_persp_secondary = ((Light *)light_obj->data)->type != LA_SUN; + } + } - rb->fuzzy_intersections = (lmd->calculation_flags & LRT_INTERSECTION_AS_CONTOUR) != 0; - rb->fuzzy_everything = (lmd->calculation_flags & LRT_EVERYTHING_AS_CONTOUR) != 0; - rb->allow_boundaries = (lmd->calculation_flags & LRT_ALLOW_CLIPPING_BOUNDARIES) != 0; - rb->use_loose_as_contour = (lmd->calculation_flags & LRT_LOOSE_AS_CONTOUR) != 0; - rb->use_loose_edge_chain = (lmd->calculation_flags & LRT_CHAIN_LOOSE_EDGES) != 0; - rb->use_geometry_space_chain = (lmd->calculation_flags & LRT_CHAIN_GEOMETRY_SPACE) != 0; - rb->use_image_boundary_trimming = (lmd->calculation_flags & LRT_USE_IMAGE_BOUNDARY_TRIMMING) != - 0; + ld->conf.crease_threshold = cos(M_PI - lmd->crease_threshold); + ld->conf.chaining_image_threshold = lmd->chaining_image_threshold; + ld->conf.angle_splitting_threshold = lmd->angle_splitting_threshold; + ld->conf.chain_smooth_tolerance = lmd->chain_smooth_tolerance; + + ld->conf.fuzzy_intersections = (lmd->calculation_flags & LRT_INTERSECTION_AS_CONTOUR) != 0; + ld->conf.fuzzy_everything = (lmd->calculation_flags & LRT_EVERYTHING_AS_CONTOUR) != 0; + ld->conf.allow_boundaries = (lmd->calculation_flags & LRT_ALLOW_CLIPPING_BOUNDARIES) != 0; + ld->conf.use_loose_as_contour = (lmd->calculation_flags & LRT_LOOSE_AS_CONTOUR) != 0; + ld->conf.use_loose_edge_chain = (lmd->calculation_flags & LRT_CHAIN_LOOSE_EDGES) != 0; + ld->conf.use_geometry_space_chain = (lmd->calculation_flags & LRT_CHAIN_GEOMETRY_SPACE) != 0; + ld->conf.use_image_boundary_trimming = (lmd->calculation_flags & + LRT_USE_IMAGE_BOUNDARY_TRIMMING) != 0; /* See lineart_edge_from_triangle() for how this option may impact performance. */ - rb->allow_overlapping_edges = (lmd->calculation_flags & LRT_ALLOW_OVERLAPPING_EDGES) != 0; + ld->conf.allow_overlapping_edges = (lmd->calculation_flags & LRT_ALLOW_OVERLAPPING_EDGES) != 0; - rb->allow_duplicated_types = (lmd->calculation_flags & LRT_ALLOW_OVERLAP_EDGE_TYPES) != 0; + ld->conf.allow_duplicated_types = (lmd->calculation_flags & LRT_ALLOW_OVERLAP_EDGE_TYPES) != 0; - rb->force_crease = (lmd->calculation_flags & LRT_USE_CREASE_ON_SMOOTH_SURFACES) != 0; - rb->sharp_as_crease = (lmd->calculation_flags & LRT_USE_CREASE_ON_SHARP_EDGES) != 0; + ld->conf.force_crease = (lmd->calculation_flags & LRT_USE_CREASE_ON_SMOOTH_SURFACES) != 0; + ld->conf.sharp_as_crease = (lmd->calculation_flags & LRT_USE_CREASE_ON_SHARP_EDGES) != 0; - rb->chain_preserve_details = (lmd->calculation_flags & LRT_CHAIN_PRESERVE_DETAILS) != 0; + ld->conf.chain_preserve_details = (lmd->calculation_flags & LRT_CHAIN_PRESERVE_DETAILS) != 0; /* This is used to limit calculation to a certain level to save time, lines who have higher * occlusion levels will get ignored. */ - rb->max_occlusion_level = lmd->level_end_override; - - rb->use_back_face_culling = (lmd->calculation_flags & LRT_USE_BACK_FACE_CULLING) != 0; + ld->conf.max_occlusion_level = lmd->level_end_override; int16_t edge_types = lmd->edge_types_override; - rb->use_contour = (edge_types & LRT_EDGE_FLAG_CONTOUR) != 0; - rb->use_crease = (edge_types & LRT_EDGE_FLAG_CREASE) != 0; - rb->use_material = (edge_types & LRT_EDGE_FLAG_MATERIAL) != 0; - rb->use_edge_marks = (edge_types & LRT_EDGE_FLAG_EDGE_MARK) != 0; - rb->use_intersections = (edge_types & LRT_EDGE_FLAG_INTERSECTION) != 0; - rb->use_loose = (edge_types & LRT_EDGE_FLAG_LOOSE) != 0; + /* lmd->edge_types_override contains all used flags in the modifier stack. */ + ld->conf.use_contour = (edge_types & LRT_EDGE_FLAG_CONTOUR) != 0; + ld->conf.use_crease = (edge_types & LRT_EDGE_FLAG_CREASE) != 0; + ld->conf.use_material = (edge_types & LRT_EDGE_FLAG_MATERIAL) != 0; + ld->conf.use_edge_marks = (edge_types & LRT_EDGE_FLAG_EDGE_MARK) != 0; + ld->conf.use_intersections = (edge_types & LRT_EDGE_FLAG_INTERSECTION) != 0; + ld->conf.use_loose = (edge_types & LRT_EDGE_FLAG_LOOSE) != 0; + ld->conf.use_light_contour = ((edge_types & LRT_EDGE_FLAG_LIGHT_CONTOUR) != 0 && + (lmd->light_contour_object != NULL)); + ld->conf.use_shadow = ((edge_types & LRT_EDGE_FLAG_PROJECTED_SHADOW) != 0 && + (lmd->light_contour_object != NULL)); + + ld->conf.shadow_selection = lmd->shadow_selection_override; + ld->conf.shadow_enclose_shapes = (lmd->calculation_flags & LRT_SHADOW_ENCLOSED_SHAPES) != 0; + ld->conf.shadow_use_silhouette = lmd->shadow_use_silhouette_override != 0; + + ld->conf.use_back_face_culling = (lmd->calculation_flags & LRT_USE_BACK_FACE_CULLING) != 0; + + ld->conf.filter_face_mark_invert = (lmd->calculation_flags & LRT_FILTER_FACE_MARK_INVERT) != 0; + ld->conf.filter_face_mark = (lmd->calculation_flags & LRT_FILTER_FACE_MARK) != 0; + ld->conf.filter_face_mark_boundaries = (lmd->calculation_flags & + LRT_FILTER_FACE_MARK_BOUNDARIES) != 0; + ld->conf.filter_face_mark_keep_contour = (lmd->calculation_flags & + LRT_FILTER_FACE_MARK_KEEP_CONTOUR) != 0; - rb->filter_face_mark_invert = (lmd->calculation_flags & LRT_FILTER_FACE_MARK_INVERT) != 0; - rb->filter_face_mark = (lmd->calculation_flags & LRT_FILTER_FACE_MARK) != 0; - rb->filter_face_mark_boundaries = (lmd->calculation_flags & LRT_FILTER_FACE_MARK_BOUNDARIES) != - 0; - rb->filter_face_mark_keep_contour = (lmd->calculation_flags & - LRT_FILTER_FACE_MARK_KEEP_CONTOUR) != 0; + ld->chain_data_pool = &lc->chain_data_pool; - rb->chain_data_pool = &lc->chain_data_pool; + /* See #LineartData::edge_data_pool for explanation. */ + ld->edge_data_pool = &ld->render_data_pool; - BLI_spin_init(&rb->lock_task); - BLI_spin_init(&rb->lock_cuts); - BLI_spin_init(&rb->render_data_pool.lock_mem); + BLI_spin_init(&ld->lock_task); + BLI_spin_init(&ld->lock_cuts); + BLI_spin_init(&ld->render_data_pool.lock_mem); - return rb; + ld->thread_count = BKE_render_num_threads(&scene->r); + + return ld; } -static int lineart_triangle_size_get(const Scene *scene, LineartRenderBuffer *rb) +static int lineart_triangle_size_get(LineartData *ld) { - if (rb->thread_count == 0) { - rb->thread_count = BKE_render_num_threads(&scene->r); - } - return sizeof(LineartTriangle) + (sizeof(LineartEdge *) * (rb->thread_count)); + return sizeof(LineartTriangle) + (sizeof(LineartEdge *) * (ld->thread_count)); } -static void lineart_main_bounding_area_make_initial(LineartRenderBuffer *rb) +void lineart_main_bounding_area_make_initial(LineartData *ld) { /* Initial tile split is defined as 4 (subdivided as 4*4), increasing the value allows the * algorithm to build the acceleration structure for bigger scenes a little faster but not as @@ -3491,24 +3684,35 @@ static void lineart_main_bounding_area_make_initial(LineartRenderBuffer *rb) int row, col; LineartBoundingArea *ba; + /* Always make sure the shortest side has at least LRT_BA_ROWS tiles. */ + if (ld->w > ld->h) { + sp_w = sp_h * ld->w / ld->h; + } + else { + sp_h = sp_w * ld->h / ld->w; + } + /* Because NDC (Normalized Device Coordinates) range is (-1,1), * so the span for each initial tile is double of that in the (0,1) range. */ double span_w = (double)1 / sp_w * 2.0; double span_h = (double)1 / sp_h * 2.0; - rb->tile_count_x = sp_w; - rb->tile_count_y = sp_h; - rb->width_per_tile = span_w; - rb->height_per_tile = span_h; + ld->qtree.count_x = sp_w; + ld->qtree.count_y = sp_h; + ld->qtree.tile_width = span_w; + ld->qtree.tile_height = span_h; - rb->bounding_area_count = sp_w * sp_h; - rb->initial_bounding_areas = lineart_mem_acquire( - &rb->render_data_pool, sizeof(LineartBoundingArea) * rb->bounding_area_count); + ld->qtree.initial_tile_count = sp_w * sp_h; + ld->qtree.initials = lineart_mem_acquire( + &ld->render_data_pool, sizeof(LineartBoundingArea) * ld->qtree.initial_tile_count); + for (int i = 0; i < ld->qtree.initial_tile_count; i++) { + BLI_spin_init(&ld->qtree.initials[i].lock); + } /* Initialize tiles. */ for (row = 0; row < sp_h; row++) { for (col = 0; col < sp_w; col++) { - ba = &rb->initial_bounding_areas[row * LRT_BA_ROWS + col]; + ba = &ld->qtree.initials[row * ld->qtree.count_x + col]; /* Set the four direction limits. */ ba->l = span_w * col - 1.0; @@ -3522,34 +3726,12 @@ static void lineart_main_bounding_area_make_initial(LineartRenderBuffer *rb) /* 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); + ba->linked_triangles = MEM_callocN(sizeof(LineartTriangle *) * ba->max_triangle_count, + "ba_linked_triangles"); + ba->linked_lines = MEM_callocN(sizeof(LineartEdge *) * ba->max_line_count, + "ba_linked_lines"); - /* Link adjacent ones. */ - if (row) { - lineart_list_append_pointer_pool( - &ba->up, - &rb->render_data_pool, - &rb->initial_bounding_areas[(row - 1) * LRT_BA_ROWS + col]); - } - if (col) { - lineart_list_append_pointer_pool(&ba->lp, - &rb->render_data_pool, - &rb->initial_bounding_areas[row * LRT_BA_ROWS + col - 1]); - } - if (row != sp_h - 1) { - lineart_list_append_pointer_pool( - &ba->bp, - &rb->render_data_pool, - &rb->initial_bounding_areas[(row + 1) * LRT_BA_ROWS + col]); - } - if (col != sp_w - 1) { - lineart_list_append_pointer_pool(&ba->rp, - &rb->render_data_pool, - &rb->initial_bounding_areas[row * LRT_BA_ROWS + col + 1]); - } + BLI_spin_init(&ba->lock); } } } @@ -3557,11 +3739,11 @@ static void lineart_main_bounding_area_make_initial(LineartRenderBuffer *rb) /** * Re-link adjacent tiles after one gets subdivided. */ -static void lineart_bounding_areas_connect_new(LineartRenderBuffer *rb, LineartBoundingArea *root) +static void lineart_bounding_areas_connect_new(LineartData *ld, LineartBoundingArea *root) { LineartBoundingArea *ba = root->child, *tba; LinkData *lip2, *next_lip; - LineartStaticMemPool *mph = &rb->render_data_pool; + LineartStaticMemPool *mph = &ld->render_data_pool; /* Inter-connection with newly created 4 child bounding areas. */ lineart_list_append_pointer_pool(&ba[1].rp, mph, &ba[0]); @@ -3697,17 +3879,59 @@ static void lineart_bounding_areas_connect_new(LineartRenderBuffer *rb, LineartB BLI_listbase_clear(&root->bp); } +static void lineart_bounding_areas_connect_recursive(LineartData *ld, LineartBoundingArea *root) +{ + if (root->child) { + lineart_bounding_areas_connect_new(ld, root); + for (int i = 0; i < 4; i++) { + lineart_bounding_areas_connect_recursive(ld, &root->child[i]); + } + } +} + +void lineart_main_bounding_areas_connect_post(LineartData *ld) +{ + int total_tile_initial = ld->qtree.count_x * ld->qtree.count_y; + int tiles_per_row = ld->qtree.count_x; + + for (int row = 0; row < ld->qtree.count_y; row++) { + for (int col = 0; col < ld->qtree.count_x; col++) { + LineartBoundingArea *ba = &ld->qtree.initials[row * tiles_per_row + col]; + /* Link adjacent ones. */ + if (row) { + lineart_list_append_pointer_pool( + &ba->up, &ld->render_data_pool, &ld->qtree.initials[(row - 1) * tiles_per_row + col]); + } + if (col) { + lineart_list_append_pointer_pool( + &ba->lp, &ld->render_data_pool, &ld->qtree.initials[row * tiles_per_row + col - 1]); + } + if (row != ld->qtree.count_y - 1) { + lineart_list_append_pointer_pool( + &ba->bp, &ld->render_data_pool, &ld->qtree.initials[(row + 1) * tiles_per_row + col]); + } + if (col != ld->qtree.count_x - 1) { + lineart_list_append_pointer_pool( + &ba->rp, &ld->render_data_pool, &ld->qtree.initials[row * tiles_per_row + col + 1]); + } + } + } + for (int i = 0; i < total_tile_initial; i++) { + lineart_bounding_areas_connect_recursive(ld, &ld->qtree.initials[i]); + } +} + /** - * Subdivide a tile after one tile contains too many triangles. + * Subdivide a tile after one tile contains too many triangles, then re-link triangles into all the + * child tiles. */ -static void lineart_bounding_area_split(LineartRenderBuffer *rb, +static void lineart_bounding_area_split(LineartData *ld, LineartBoundingArea *root, int recursive_level) { - LineartBoundingArea *ba = lineart_mem_acquire(&rb->render_data_pool, - sizeof(LineartBoundingArea) * 4); - LineartTriangle *tri; + LineartBoundingArea *ba = lineart_mem_acquire_thread(&ld->render_data_pool, + sizeof(LineartBoundingArea) * 4); ba[0].l = root->cx; ba[0].r = root->r; ba[0].u = root->u; @@ -3736,80 +3960,80 @@ static void lineart_bounding_area_split(LineartRenderBuffer *rb, ba[3].cx = (ba[3].l + ba[3].r) / 2; ba[3].cy = (ba[3].u + ba[3].b) / 2; - root->child = ba; - - lineart_bounding_areas_connect_new(rb, root); - - /* Init linked_triangles array. */ + /* Init linked_triangles array and locks. */ 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); + ba[i].linked_triangles = MEM_callocN(sizeof(LineartTriangle *) * ba[i].max_triangle_count, + "ba_linked_triangles"); + ba[i].linked_lines = MEM_callocN(sizeof(LineartEdge *) * ba[i].max_line_count, + "ba_linked_lines"); + BLI_spin_init(&ba[i].lock); } - for (int i = 0; i < root->triangle_count; i++) { - tri = root->linked_triangles[i]; - LineartBoundingArea *cba = root->child; + for (uint32_t i = 0; i < root->triangle_count; i++) { + LineartTriangle *tri = root->linked_triangles[i]; + double b[4]; b[0] = MIN3(tri->v[0]->fbcoord[0], tri->v[1]->fbcoord[0], tri->v[2]->fbcoord[0]); b[1] = MAX3(tri->v[0]->fbcoord[0], tri->v[1]->fbcoord[0], tri->v[2]->fbcoord[0]); b[2] = MAX3(tri->v[0]->fbcoord[1], tri->v[1]->fbcoord[1], tri->v[2]->fbcoord[1]); b[3] = MIN3(tri->v[0]->fbcoord[1], tri->v[1]->fbcoord[1], tri->v[2]->fbcoord[1]); - if (LRT_BOUND_AREA_CROSSES(b, &cba[0].l)) { - lineart_bounding_area_link_triangle(rb, &cba[0], tri, b, 0, recursive_level + 1, false); + + /* Re-link triangles into child tiles, not doing intersection lines during this because this + * batch of triangles are all tested with each other for intersections. */ + if (LRT_BOUND_AREA_CROSSES(b, &ba[0].l)) { + lineart_bounding_area_link_triangle(ld, &ba[0], tri, b, 0, recursive_level + 1, false, NULL); } - if (LRT_BOUND_AREA_CROSSES(b, &cba[1].l)) { - lineart_bounding_area_link_triangle(rb, &cba[1], tri, b, 0, recursive_level + 1, false); + if (LRT_BOUND_AREA_CROSSES(b, &ba[1].l)) { + lineart_bounding_area_link_triangle(ld, &ba[1], tri, b, 0, recursive_level + 1, false, NULL); } - if (LRT_BOUND_AREA_CROSSES(b, &cba[2].l)) { - lineart_bounding_area_link_triangle(rb, &cba[2], tri, b, 0, recursive_level + 1, false); + if (LRT_BOUND_AREA_CROSSES(b, &ba[2].l)) { + lineart_bounding_area_link_triangle(ld, &ba[2], tri, b, 0, recursive_level + 1, false, NULL); } - if (LRT_BOUND_AREA_CROSSES(b, &cba[3].l)) { - lineart_bounding_area_link_triangle(rb, &cba[3], tri, b, 0, recursive_level + 1, false); + if (LRT_BOUND_AREA_CROSSES(b, &ba[3].l)) { + lineart_bounding_area_link_triangle(ld, &ba[3], tri, b, 0, recursive_level + 1, false, NULL); } } - rb->bounding_area_count += 3; + /* At this point the child tiles are fully initialized and it's safe for new triangles to be + * inserted, so assign root->child for #lineart_bounding_area_link_triangle to use. */ + root->child = ba; } -static bool lineart_bounding_area_edge_intersect(LineartRenderBuffer *UNUSED(fb), +static bool lineart_bounding_area_edge_intersect(LineartData *UNUSED(fb), const double l[2], const double r[2], LineartBoundingArea *ba) { - double vx, vy; + double dx, dy; 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; } - vx = l[0] - r[0]; - vy = l[1] - r[1]; + dx = l[0] - r[0]; + dy = l[1] - r[1]; - c1 = vx * (converted[2] - l[1]) - vy * (converted[0] - l[0]); + c1 = dx * (converted[2] - l[1]) - dy * (converted[0] - l[0]); c = c1; - c1 = vx * (converted[2] - l[1]) - vy * (converted[1] - l[0]); + c1 = dx * (converted[2] - l[1]) - dy * (converted[1] - l[0]); if (c1 * c <= 0) { return true; } c = c1; - c1 = vx * (converted[3] - l[1]) - vy * (converted[0] - l[0]); + c1 = dx * (converted[3] - l[1]) - dy * (converted[0] - l[0]); if (c1 * c <= 0) { return true; } c = c1; - c1 = vx * (converted[3] - l[1]) - vy * (converted[1] - l[0]); + c1 = dx * (converted[3] - l[1]) - dy * (converted[1] - l[0]); if (c1 * c <= 0) { return true; } @@ -3818,24 +4042,28 @@ static bool lineart_bounding_area_edge_intersect(LineartRenderBuffer *UNUSED(fb) return false; } -static bool lineart_bounding_area_triangle_intersect(LineartRenderBuffer *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) || @@ -3853,87 +4081,180 @@ static bool lineart_bounding_area_triangle_intersect(LineartRenderBuffer *fb, } /** - * 1) Link triangles with bounding areas for later occlusion test. - * 2) Test triangles with existing(added previously) triangles for intersection lines. + * This function does two things: + * + * 1) Builds a quad-tree under ld->InitialBoundingAreas to achieve good geometry separation for + * fast overlapping test between triangles and lines. This acceleration structure makes the + * occlusion stage much faster. + * + * 2) Test triangles with other triangles that are previously linked into each tile + * (#LineartBoundingArea) for intersection lines. When splitting the tile into 4 children and + * re-linking triangles into the child tiles, intersections are inhibited so we don't get + * duplicated intersection lines. + * */ -static void lineart_bounding_area_link_triangle(LineartRenderBuffer *rb, +static void lineart_bounding_area_link_triangle(LineartData *ld, LineartBoundingArea *root_ba, LineartTriangle *tri, - double *LRUB, + double l_r_u_b[4], int recursive, int recursive_level, - bool do_intersection) + bool do_intersection, + struct LineartIsecThread *th) { - if (!lineart_bounding_area_triangle_intersect(rb, tri, root_ba)) { + bool triangle_vert_inside; + if (!lineart_bounding_area_triangle_intersect(ld, tri, root_ba, &triangle_vert_inside)) { return; } - if (root_ba->child == NULL) { - 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 >= 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) { - lineart_triangle_intersect_in_bounding_area(rb, tri, root_ba); - } - } - else { - LineartBoundingArea *ba = root_ba->child; - double *B1 = LRUB; + + LineartBoundingArea *old_ba = root_ba; + + if (old_ba->child) { + /* If old_ba->child is not NULL, then tile splitting is fully finished, safe to directly insert + * into child tiles. */ + double *B1 = l_r_u_b; double b[4]; - if (!LRUB) { + if (!l_r_u_b) { b[0] = MIN3(tri->v[0]->fbcoord[0], tri->v[1]->fbcoord[0], tri->v[2]->fbcoord[0]); b[1] = MAX3(tri->v[0]->fbcoord[0], tri->v[1]->fbcoord[0], tri->v[2]->fbcoord[0]); b[2] = MAX3(tri->v[0]->fbcoord[1], tri->v[1]->fbcoord[1], tri->v[2]->fbcoord[1]); b[3] = MIN3(tri->v[0]->fbcoord[1], tri->v[1]->fbcoord[1], tri->v[2]->fbcoord[1]); B1 = b; } - if (LRT_BOUND_AREA_CROSSES(B1, &ba[0].l)) { - lineart_bounding_area_link_triangle( - rb, &ba[0], tri, B1, recursive, recursive_level + 1, do_intersection); + for (int iba = 0; iba < 4; iba++) { + if (LRT_BOUND_AREA_CROSSES(B1, &old_ba->child[iba].l)) { + lineart_bounding_area_link_triangle( + ld, &old_ba->child[iba], tri, B1, recursive, recursive_level + 1, do_intersection, th); + } } - if (LRT_BOUND_AREA_CROSSES(B1, &ba[1].l)) { - lineart_bounding_area_link_triangle( - rb, &ba[1], tri, B1, recursive, recursive_level + 1, do_intersection); + return; + } + + /* When splitting tiles, triangles are relinked into new tiles by a single thread, #th is NULL + * in that situation. */ + if (th) { + BLI_spin_lock(&old_ba->lock); + } + + /* If there are still space left in this tile for insertion. */ + 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_tri_count] = tri; + + if (triangle_vert_inside) { + old_ba->insider_triangle_count++; } - if (LRT_BOUND_AREA_CROSSES(B1, &ba[2].l)) { - lineart_bounding_area_link_triangle( - rb, &ba[2], tri, B1, recursive, recursive_level + 1, do_intersection); + old_ba->triangle_count++; + + /* Do intersections in place. */ + if (do_intersection && ld->conf.use_intersections) { + lineart_triangle_intersect_in_bounding_area(tri, old_ba, th, old_tri_count); + } + + if (th) { + BLI_spin_unlock(&old_ba->lock); } - if (LRT_BOUND_AREA_CROSSES(B1, &ba[3].l)) { - lineart_bounding_area_link_triangle( - rb, &ba[3], tri, B1, recursive, recursive_level + 1, do_intersection); + } + else { /* We need to wait for either splitting or array extension to be done. */ + + 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); + } /* Otherwise other thread has completed the splitting process. */ + } + else { + if (old_ba->triangle_count == old_ba->max_triangle_count) { + /* Means we are the thread that's doing the extension. */ + lineart_bounding_area_triangle_reallocate(old_ba); + } /* Otherwise other thread has completed the extending the array. */ + } + + /* Unlock before going into recursive call. */ + if (th) { + BLI_spin_unlock(&old_ba->lock); + } + + /* Of course we still have our own triangle needs to be added. */ + lineart_bounding_area_link_triangle( + ld, root_ba, tri, l_r_u_b, recursive, recursive_level, do_intersection, th); + } +} + +static void lineart_free_bounding_area_memory(LineartBoundingArea *ba, bool recursive) +{ + BLI_spin_end(&ba->lock); + if (ba->linked_lines) { + MEM_freeN(ba->linked_lines); + } + if (ba->linked_triangles) { + MEM_freeN(ba->linked_triangles); + } + if (recursive && ba->child) { + for (int i = 0; i < 4; i++) { + lineart_free_bounding_area_memory(&ba->child[i], recursive); + } + } +} +static void lineart_free_bounding_area_memories(LineartData *ld) +{ + for (int i = 0; i < ld->qtree.count_y; i++) { + for (int j = 0; j < ld->qtree.count_x; j++) { + lineart_free_bounding_area_memory(&ld->qtree.initials[i * ld->qtree.count_x + j], true); } } } -static void lineart_bounding_area_link_edge(LineartRenderBuffer *rb, +static void lineart_bounding_area_link_edge(LineartData *ld, LineartBoundingArea *root_ba, LineartEdge *e) { if (root_ba->child == NULL) { - lineart_bounding_area_line_add(rb, root_ba, e); + lineart_bounding_area_line_add(root_ba, e); } else { if (lineart_bounding_area_edge_intersect( - rb, e->v1->fbcoord, e->v2->fbcoord, &root_ba->child[0])) { - lineart_bounding_area_link_edge(rb, &root_ba->child[0], e); + ld, e->v1->fbcoord, e->v2->fbcoord, &root_ba->child[0])) { + lineart_bounding_area_link_edge(ld, &root_ba->child[0], e); } if (lineart_bounding_area_edge_intersect( - rb, e->v1->fbcoord, e->v2->fbcoord, &root_ba->child[1])) { - lineart_bounding_area_link_edge(rb, &root_ba->child[1], e); + ld, e->v1->fbcoord, e->v2->fbcoord, &root_ba->child[1])) { + lineart_bounding_area_link_edge(ld, &root_ba->child[1], e); } if (lineart_bounding_area_edge_intersect( - rb, e->v1->fbcoord, e->v2->fbcoord, &root_ba->child[2])) { - lineart_bounding_area_link_edge(rb, &root_ba->child[2], e); + ld, e->v1->fbcoord, e->v2->fbcoord, &root_ba->child[2])) { + lineart_bounding_area_link_edge(ld, &root_ba->child[2], e); } if (lineart_bounding_area_edge_intersect( - rb, e->v1->fbcoord, e->v2->fbcoord, &root_ba->child[3])) { - lineart_bounding_area_link_edge(rb, &root_ba->child[3], e); + ld, e->v1->fbcoord, e->v2->fbcoord, &root_ba->child[3])) { + lineart_bounding_area_link_edge(ld, &root_ba->child[3], e); + } + } +} + +static void lineart_clear_linked_edges_recursive(LineartData *ld, LineartBoundingArea *root_ba) +{ + if (root_ba->child) { + for (int i = 0; i < 4; i++) { + lineart_clear_linked_edges_recursive(ld, &root_ba->child[i]); + } + } + if (root_ba->linked_lines) { + MEM_freeN(root_ba->linked_lines); + } + root_ba->line_count = 0; + root_ba->max_line_count = 128; + root_ba->linked_lines = MEM_callocN(sizeof(LineartEdge *) * root_ba->max_line_count, + "cleared lineart edges"); +} +void lineart_main_clear_linked_edges(LineartData *ld) +{ + LineartBoundingArea *ba = ld->qtree.initials; + for (int i = 0; i < ld->qtree.count_y; i++) { + for (int j = 0; j < ld->qtree.count_x; j++) { + lineart_clear_linked_edges_recursive(ld, &ba[i * ld->qtree.count_x + j]); } } } @@ -3941,16 +4262,16 @@ static void lineart_bounding_area_link_edge(LineartRenderBuffer *rb, /** * Link lines to their respective bounding areas. */ -static void lineart_main_link_lines(LineartRenderBuffer *rb) +void lineart_main_link_lines(LineartData *ld) { LRT_ITER_ALL_LINES_BEGIN { int r1, r2, c1, c2, row, col; - if (lineart_get_edge_bounding_areas(rb, e, &r1, &r2, &c1, &c2)) { + if (lineart_get_edge_bounding_areas(ld, e, &r1, &r2, &c1, &c2)) { for (row = r1; row != r2 + 1; row++) { for (col = c1; col != c2 + 1; col++) { lineart_bounding_area_link_edge( - rb, &rb->initial_bounding_areas[row * LRT_BA_ROWS + col], e); + ld, &ld->qtree.initials[row * ld->qtree.count_x + col], e); } } } @@ -3958,14 +4279,66 @@ static void lineart_main_link_lines(LineartRenderBuffer *rb) LRT_ITER_ALL_LINES_END } -static bool lineart_get_triangle_bounding_areas(LineartRenderBuffer *rb, - LineartTriangle *tri, - int *rowbegin, - int *rowend, - int *colbegin, - int *colend) +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) { - double sp_w = rb->width_per_tile, sp_h = rb->height_per_tile; + 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) +{ + double sp_w = ld->qtree.tile_width, sp_h = ld->qtree.tile_height; double b[4]; if (!tri->v[0] || !tri->v[1] || !tri->v[2]) { @@ -3983,14 +4356,14 @@ static bool lineart_get_triangle_bounding_areas(LineartRenderBuffer *rb, (*colbegin) = (int)((b[0] + 1.0) / sp_w); (*colend) = (int)((b[1] + 1.0) / sp_w); - (*rowend) = rb->tile_count_y - (int)((b[2] + 1.0) / sp_h) - 1; - (*rowbegin) = rb->tile_count_y - (int)((b[3] + 1.0) / sp_h) - 1; + (*rowend) = ld->qtree.count_y - (int)((b[2] + 1.0) / sp_h) - 1; + (*rowbegin) = ld->qtree.count_y - (int)((b[3] + 1.0) / sp_h) - 1; - if ((*colend) >= rb->tile_count_x) { - (*colend) = rb->tile_count_x - 1; + if ((*colend) >= ld->qtree.count_x) { + (*colend) = ld->qtree.count_x - 1; } - if ((*rowend) >= rb->tile_count_y) { - (*rowend) = rb->tile_count_y - 1; + if ((*rowend) >= ld->qtree.count_y) { + (*rowend) = ld->qtree.count_y - 1; } if ((*colbegin) < 0) { (*colbegin) = 0; @@ -4002,14 +4375,10 @@ static bool lineart_get_triangle_bounding_areas(LineartRenderBuffer *rb, return true; } -static bool lineart_get_edge_bounding_areas(LineartRenderBuffer *rb, - LineartEdge *e, - int *rowbegin, - int *rowend, - int *colbegin, - int *colend) +static bool lineart_get_edge_bounding_areas( + LineartData *ld, LineartEdge *e, int *rowbegin, int *rowend, int *colbegin, int *colend) { - double sp_w = rb->width_per_tile, sp_h = rb->height_per_tile; + double sp_w = ld->qtree.tile_width, sp_h = ld->qtree.tile_height; double b[4]; if (!e->v1 || !e->v2) { @@ -4031,31 +4400,29 @@ static bool lineart_get_edge_bounding_areas(LineartRenderBuffer *rb, (*colbegin) = (int)((b[0] + 1.0) / sp_w); (*colend) = (int)((b[1] + 1.0) / sp_w); - (*rowend) = rb->tile_count_y - (int)((b[2] + 1.0) / sp_h) - 1; - (*rowbegin) = rb->tile_count_y - (int)((b[3] + 1.0) / sp_h) - 1; + (*rowend) = ld->qtree.count_y - (int)((b[2] + 1.0) / sp_h) - 1; + (*rowbegin) = ld->qtree.count_y - (int)((b[3] + 1.0) / sp_h) - 1; /* It's possible that the line stretches too much out to the side, resulting negative value. */ if ((*rowend) < (*rowbegin)) { - (*rowend) = rb->tile_count_y - 1; + (*rowend) = ld->qtree.count_y - 1; } if ((*colend) < (*colbegin)) { - (*colend) = rb->tile_count_x - 1; + (*colend) = ld->qtree.count_x - 1; } - CLAMP((*colbegin), 0, rb->tile_count_x - 1); - CLAMP((*rowbegin), 0, rb->tile_count_y - 1); - CLAMP((*colend), 0, rb->tile_count_x - 1); - CLAMP((*rowend), 0, rb->tile_count_y - 1); + CLAMP((*colbegin), 0, ld->qtree.count_x - 1); + CLAMP((*rowbegin), 0, ld->qtree.count_y - 1); + CLAMP((*colend), 0, ld->qtree.count_x - 1); + CLAMP((*rowend), 0, ld->qtree.count_y - 1); return true; } -LineartBoundingArea *MOD_lineart_get_parent_bounding_area(LineartRenderBuffer *rb, - double x, - double y) +LineartBoundingArea *MOD_lineart_get_parent_bounding_area(LineartData *ld, double x, double y) { - double sp_w = rb->width_per_tile, sp_h = rb->height_per_tile; + double sp_w = ld->qtree.tile_width, sp_h = ld->qtree.tile_height; int col, row; if (x > 1 || x < -1 || y > 1 || y < -1) { @@ -4063,13 +4430,13 @@ LineartBoundingArea *MOD_lineart_get_parent_bounding_area(LineartRenderBuffer *r } col = (int)((x + 1.0) / sp_w); - row = rb->tile_count_y - (int)((y + 1.0) / sp_h) - 1; + row = ld->qtree.count_y - (int)((y + 1.0) / sp_h) - 1; - if (col >= rb->tile_count_x) { - col = rb->tile_count_x - 1; + if (col >= ld->qtree.count_x) { + col = ld->qtree.count_x - 1; } - if (row >= rb->tile_count_y) { - row = rb->tile_count_y - 1; + if (row >= ld->qtree.count_y) { + row = ld->qtree.count_y - 1; } if (col < 0) { col = 0; @@ -4078,29 +4445,29 @@ LineartBoundingArea *MOD_lineart_get_parent_bounding_area(LineartRenderBuffer *r row = 0; } - return &rb->initial_bounding_areas[row * LRT_BA_ROWS + col]; + return &ld->qtree.initials[row * ld->qtree.count_x + col]; } -static LineartBoundingArea *lineart_get_bounding_area(LineartRenderBuffer *rb, double x, double y) +static LineartBoundingArea *lineart_get_bounding_area(LineartData *ld, double x, double y) { LineartBoundingArea *iba; - double sp_w = rb->width_per_tile, sp_h = rb->height_per_tile; + double sp_w = ld->qtree.tile_width, sp_h = ld->qtree.tile_height; int c = (int)((x + 1.0) / sp_w); - int r = rb->tile_count_y - (int)((y + 1.0) / sp_h) - 1; + int r = ld->qtree.count_y - (int)((y + 1.0) / sp_h) - 1; if (r < 0) { r = 0; } if (c < 0) { c = 0; } - if (r >= rb->tile_count_y) { - r = rb->tile_count_y - 1; + if (r >= ld->qtree.count_y) { + r = ld->qtree.count_y - 1; } - if (c >= rb->tile_count_x) { - c = rb->tile_count_x - 1; + if (c >= ld->qtree.count_x) { + c = ld->qtree.count_x - 1; } - iba = &rb->initial_bounding_areas[r * LRT_BA_ROWS + c]; + iba = &ld->qtree.initials[r * ld->qtree.count_x + c]; while (iba->child) { if (x > iba->cx) { if (y > iba->cy) { @@ -4122,101 +4489,243 @@ static LineartBoundingArea *lineart_get_bounding_area(LineartRenderBuffer *rb, d return iba; } -LineartBoundingArea *MOD_lineart_get_bounding_area(LineartRenderBuffer *rb, double x, double y) +LineartBoundingArea *MOD_lineart_get_bounding_area(LineartData *ld, double x, double y) { LineartBoundingArea *ba; - if ((ba = MOD_lineart_get_parent_bounding_area(rb, x, y)) != NULL) { - return lineart_get_bounding_area(rb, x, y); + if ((ba = MOD_lineart_get_parent_bounding_area(ld, x, y)) != NULL) { + return lineart_get_bounding_area(ld, x, y); } return NULL; } -/** - * Sequentially add triangles into render buffer. This also does intersection along the way. - */ -static void lineart_main_add_triangles(LineartRenderBuffer *rb) +static void lineart_add_triangles_worker(TaskPool *__restrict UNUSED(pool), LineartIsecThread *th) { - LineartTriangle *tri; - int i, lim; - int x1, x2, y1, y2; - int r, co; - - LISTBASE_FOREACH (LineartElementLinkNode *, eln, &rb->triangle_buffer_pointers) { - tri = eln->pointer; - lim = eln->element_count; - for (i = 0; i < lim; i++) { - if ((tri->flags & LRT_CULL_USED) || (tri->flags & LRT_CULL_DISCARD)) { - tri = (void *)(((uchar *)tri) + rb->triangle_size); - continue; - } - if (lineart_get_triangle_bounding_areas(rb, tri, &y1, &y2, &x1, &x2)) { - for (co = x1; co <= x2; co++) { - for (r = y1; r <= y2; r++) { - lineart_bounding_area_link_triangle(rb, - &rb->initial_bounding_areas[r * LRT_BA_ROWS + co], - tri, - 0, - 1, - 0, - (!(tri->flags & LRT_TRIANGLE_NO_INTERSECTION))); + LineartData *ld = th->ld; + int _dir_control = 0; + while (lineart_schedule_new_triangle_task(th)) { + for (LineartElementLinkNode *eln = th->pending_from; eln != th->pending_to->next; + eln = eln->next) { + int index_start = eln == th->pending_from ? th->index_from : 0; + int index_end = eln == th->pending_to ? th->index_to : eln->element_count; + LineartTriangle *tri = (void *)(((uchar *)eln->pointer) + ld->sizeof_triangle * index_start); + for (int ei = index_start; ei < index_end; ei++) { + int x1, x2, y1, y2; + int r, co; + if ((tri->flags & LRT_CULL_USED) || (tri->flags & LRT_CULL_DISCARD)) { + tri = (void *)(((uchar *)tri) + ld->sizeof_triangle); + continue; + } + if (lineart_get_triangle_bounding_areas(ld, tri, &y1, &y2, &x1, &x2)) { + _dir_control++; + for (co = x1; co <= x2; co++) { + for (r = y1; r <= y2; r++) { + lineart_bounding_area_link_triangle(ld, + &ld->qtree.initials[r * ld->qtree.count_x + co], + tri, + 0, + 1, + 0, + (!(tri->flags & LRT_TRIANGLE_NO_INTERSECTION)), + th); + } } + } /* Else throw away. */ + tri = (void *)(((uchar *)tri) + ld->sizeof_triangle); + } + } + } +} + +static void lineart_create_edges_from_isec_data(LineartIsecData *d) +{ + LineartData *ld = d->ld; + double ZMax = ld->conf.far_clip; + double ZMin = ld->conf.near_clip; + int total_lines = 0; + + for (int i = 0; i < d->thread_count; i++) { + LineartIsecThread *th = &d->threads[i]; + if (G.debug_value == 4000) { + printf("Thread %d isec generated %d lines.\n", i, th->current); + } + if (!th->current) { + continue; + } + total_lines += th->current; + } + + if (!total_lines) { + return; + } + + /* We don't care about removing duplicated vert in this method, chaining can handle that, + * and it saves us from using locks and look up tables. */ + LineartVert *v = lineart_mem_acquire(ld->edge_data_pool, sizeof(LineartVert) * total_lines * 2); + LineartEdge *e = lineart_mem_acquire(ld->edge_data_pool, sizeof(LineartEdge) * total_lines); + LineartEdgeSegment *es = lineart_mem_acquire(ld->edge_data_pool, + sizeof(LineartEdgeSegment) * total_lines); + + LineartElementLinkNode *eln = lineart_mem_acquire(ld->edge_data_pool, + sizeof(LineartElementLinkNode)); + eln->element_count = total_lines; + eln->pointer = e; + eln->flags |= LRT_ELEMENT_INTERSECTION_DATA; + BLI_addhead(&ld->geom.line_buffer_pointers, eln); + + for (int i = 0; i < d->thread_count; i++) { + LineartIsecThread *th = &d->threads[i]; + if (!th->current) { + continue; + } + + for (int j = 0; j < th->current; j++) { + LineartIsecSingle *is = &th->array[j]; + LineartVert *v1 = v; + LineartVert *v2 = v + 1; + copy_v3db_v3fl(v1->gloc, is->v1); + copy_v3db_v3fl(v2->gloc, is->v2); + /* The intersection line has been generated only in geometry space, so we need to transform + * them as well. */ + mul_v4_m4v3_db(v1->fbcoord, ld->conf.view_projection, v1->gloc); + mul_v4_m4v3_db(v2->fbcoord, ld->conf.view_projection, v2->gloc); + mul_v3db_db(v1->fbcoord, (1 / v1->fbcoord[3])); + mul_v3db_db(v2->fbcoord, (1 / v2->fbcoord[3])); + + v1->fbcoord[0] -= ld->conf.shift_x * 2; + v1->fbcoord[1] -= ld->conf.shift_y * 2; + v2->fbcoord[0] -= ld->conf.shift_x * 2; + v2->fbcoord[1] -= ld->conf.shift_y * 2; + + /* This z transformation is not the same as the rest of the part, because the data don't go + * through normal perspective division calls in the pipeline, but this way the 3D result and + * occlusion on the generated line is correct, and we don't really use 2D for viewport stroke + * generation anyway. */ + v1->fbcoord[2] = ZMin * ZMax / (ZMax - fabs(v1->fbcoord[2]) * (ZMax - ZMin)); + v2->fbcoord[2] = ZMin * ZMax / (ZMax - fabs(v2->fbcoord[2]) * (ZMax - ZMin)); + e->v1 = v1; + e->v2 = v2; + e->t1 = is->tri1; + e->t2 = is->tri2; + /* This is so we can also match intersection edges from shadow to later viewing stage. */ + e->edge_identifier = (((uint64_t)e->t1->target_reference) << 32) | e->t2->target_reference; + e->flags = LRT_EDGE_FLAG_INTERSECTION; + e->intersection_mask = (is->tri1->intersection_mask | is->tri2->intersection_mask); + BLI_addtail(&e->segments, es); + + int obi1 = (e->t1->target_reference & LRT_OBINDEX_HIGHER); + int obi2 = (e->t2->target_reference & LRT_OBINDEX_HIGHER); + LineartElementLinkNode *eln1 = lineart_find_matching_eln(&ld->geom.line_buffer_pointers, + obi1); + LineartElementLinkNode *eln2 = obi1 == obi2 ? eln1 : + lineart_find_matching_eln( + &ld->geom.line_buffer_pointers, obi2); + Object *ob1 = eln1 ? eln1->object_ref : NULL; + Object *ob2 = eln2 ? eln2->object_ref : NULL; + if (e->t1->intersection_priority > e->t2->intersection_priority) { + e->object_ref = ob1; + } + else if (e->t1->intersection_priority < e->t2->intersection_priority) { + e->object_ref = ob2; + } + else { /* equal priority */ + if (ob1 == ob2) { + /* object_ref should be ambiguous if intersection lines comes from different objects. */ + e->object_ref = ob1; } - } /* Else throw away. */ - tri = (void *)(((uchar *)tri) + rb->triangle_size); + } + + lineart_add_edge_to_array(&ld->pending_edges, e); + + v += 2; + e++; + es++; } } } /** + * Sequentially add triangles into render buffer, intersection lines between those triangles will + * also be computed at the same time. + */ +void lineart_main_add_triangles(LineartData *ld) +{ + double t_start; + if (G.debug_value == 4000) { + t_start = PIL_check_seconds_timer(); + } + + /* Initialize per-thread data for thread task scheduling information and storing intersection + * results. */ + LineartIsecData d = {0}; + lineart_init_isec_thread(&d, ld, ld->thread_count); + + TaskPool *tp = BLI_task_pool_create(NULL, TASK_PRIORITY_HIGH); + for (int i = 0; i < ld->thread_count; i++) { + BLI_task_pool_push(tp, (TaskRunFunction)lineart_add_triangles_worker, &d.threads[i], 0, NULL); + } + BLI_task_pool_work_and_wait(tp); + BLI_task_pool_free(tp); + + if (ld->conf.use_intersections) { + lineart_create_edges_from_isec_data(&d); + } + + lineart_destroy_isec_thread(&d); + + if (G.debug_value == 4000) { + double t_elapsed = PIL_check_seconds_timer() - t_start; + printf("Line art intersection time: %f\n", t_elapsed); + } +} + +/** * This function gets the tile for the point `e->v1`, and later use #lineart_bounding_area_next() * to get next along the way. */ -static LineartBoundingArea *lineart_edge_first_bounding_area(LineartRenderBuffer *rb, - LineartEdge *e) +LineartBoundingArea *lineart_edge_first_bounding_area(LineartData *ld, + double *fbcoord1, + double *fbcoord2) { - double data[2] = {e->v1->fbcoord[0], e->v1->fbcoord[1]}; + double data[2] = {fbcoord1[0], fbcoord1[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]); + return lineart_get_bounding_area(ld, data[0], data[1]); } - if (lineart_intersect_seg_seg(e->v1->fbcoord, e->v2->fbcoord, LU, RU, &sr, &p_unused) && - sr < r && sr > 0) { + if (lineart_intersect_seg_seg(fbcoord1, fbcoord2, LU, RU, &sr, &p_unused) && sr < r && sr > 0) { r = sr; } - if (lineart_intersect_seg_seg(e->v1->fbcoord, e->v2->fbcoord, LB, RB, &sr, &p_unused) && - sr < r && sr > 0) { + if (lineart_intersect_seg_seg(fbcoord1, fbcoord2, LB, RB, &sr, &p_unused) && sr < r && sr > 0) { r = sr; } - if (lineart_intersect_seg_seg(e->v1->fbcoord, e->v2->fbcoord, LB, LU, &sr, &p_unused) && - sr < r && sr > 0) { + if (lineart_intersect_seg_seg(fbcoord1, fbcoord2, LB, LU, &sr, &p_unused) && sr < r && sr > 0) { r = sr; } - if (lineart_intersect_seg_seg(e->v1->fbcoord, e->v2->fbcoord, RB, RU, &sr, &p_unused) && - sr < r && sr > 0) { + if (lineart_intersect_seg_seg(fbcoord1, fbcoord2, RB, RU, &sr, &p_unused) && sr < r && sr > 0) { r = sr; } - interp_v2_v2v2_db(data, e->v1->fbcoord, e->v2->fbcoord, r); + interp_v2_v2v2_db(data, fbcoord1, fbcoord2, r); - return lineart_get_bounding_area(rb, data[0], data[1]); + return lineart_get_bounding_area(ld, data[0], data[1]); } /** * This march along one render line in image space and * get the next bounding area the line is crossing. */ -static LineartBoundingArea *lineart_bounding_area_next(LineartBoundingArea *this, - LineartEdge *e, - double x, - double y, - double k, - int positive_x, - int positive_y, - double *next_x, - double *next_y) +LineartBoundingArea *lineart_bounding_area_next(LineartBoundingArea *this, + double *fbcoord1, + double *fbcoord2, + double x, + double y, + double k, + int positive_x, + int positive_y, + double *next_x, + double *next_y) { double rx, ry, ux, uy, lx, ly, bx, by; double r1, r2; @@ -4231,8 +4740,8 @@ static LineartBoundingArea *lineart_bounding_area_next(LineartBoundingArea *this if (positive_y > 0) { uy = this->u; ux = x + (uy - y) / k; - r1 = ratiod(e->v1->fbcoord[0], e->v2->fbcoord[0], rx); - r2 = ratiod(e->v1->fbcoord[0], e->v2->fbcoord[0], ux); + r1 = ratiod(fbcoord1[0], fbcoord2[0], rx); + r2 = ratiod(fbcoord1[0], fbcoord2[0], ux); if (MIN2(r1, r2) > 1) { return 0; } @@ -4264,8 +4773,8 @@ static LineartBoundingArea *lineart_bounding_area_next(LineartBoundingArea *this else if (positive_y < 0) { by = this->b; bx = x + (by - y) / k; - r1 = ratiod(e->v1->fbcoord[0], e->v2->fbcoord[0], rx); - r2 = ratiod(e->v1->fbcoord[0], e->v2->fbcoord[0], bx); + r1 = ratiod(fbcoord1[0], fbcoord2[0], rx); + r2 = ratiod(fbcoord1[0], fbcoord2[0], bx); if (MIN2(r1, r2) > 1) { return 0; } @@ -4292,7 +4801,7 @@ static LineartBoundingArea *lineart_bounding_area_next(LineartBoundingArea *this } /* If the line is completely horizontal, in which Y difference == 0. */ else { - r1 = ratiod(e->v1->fbcoord[0], e->v2->fbcoord[0], this->r); + r1 = ratiod(fbcoord1[0], fbcoord2[0], this->r); if (r1 > 1) { return 0; } @@ -4316,8 +4825,8 @@ static LineartBoundingArea *lineart_bounding_area_next(LineartBoundingArea *this if (positive_y > 0) { uy = this->u; ux = x + (uy - y) / k; - r1 = ratiod(e->v1->fbcoord[0], e->v2->fbcoord[0], lx); - r2 = ratiod(e->v1->fbcoord[0], e->v2->fbcoord[0], ux); + r1 = ratiod(fbcoord1[0], fbcoord2[0], lx); + r2 = ratiod(fbcoord1[0], fbcoord2[0], ux); if (MIN2(r1, r2) > 1) { return 0; } @@ -4347,8 +4856,8 @@ static LineartBoundingArea *lineart_bounding_area_next(LineartBoundingArea *this else if (positive_y < 0) { by = this->b; bx = x + (by - y) / k; - r1 = ratiod(e->v1->fbcoord[0], e->v2->fbcoord[0], lx); - r2 = ratiod(e->v1->fbcoord[0], e->v2->fbcoord[0], bx); + r1 = ratiod(fbcoord1[0], fbcoord2[0], lx); + r2 = ratiod(fbcoord1[0], fbcoord2[0], bx); if (MIN2(r1, r2) > 1) { return 0; } @@ -4375,7 +4884,7 @@ static LineartBoundingArea *lineart_bounding_area_next(LineartBoundingArea *this } /* Again, horizontal. */ else { - r1 = ratiod(e->v1->fbcoord[0], e->v2->fbcoord[0], this->l); + r1 = ratiod(fbcoord1[0], fbcoord2[0], this->l); if (r1 > 1) { return 0; } @@ -4392,7 +4901,7 @@ static LineartBoundingArea *lineart_bounding_area_next(LineartBoundingArea *this /* If the line is completely vertical, hence X difference == 0. */ else { if (positive_y > 0) { - r1 = ratiod(e->v1->fbcoord[1], e->v2->fbcoord[1], this->u); + r1 = ratiod(fbcoord1[1], fbcoord2[1], this->u); if (r1 > 1) { return 0; } @@ -4406,7 +4915,7 @@ static LineartBoundingArea *lineart_bounding_area_next(LineartBoundingArea *this } } else if (positive_y < 0) { - r1 = ratiod(e->v1->fbcoord[1], e->v2->fbcoord[1], this->b); + r1 = ratiod(fbcoord1[1], fbcoord2[1], this->b); if (r1 > 1) { return 0; } @@ -4427,24 +4936,26 @@ static LineartBoundingArea *lineart_bounding_area_next(LineartBoundingArea *this return 0; } +/** + * This is the entry point of all line art calculations. + * + * \return True when a change is made. + */ bool MOD_lineart_compute_feature_lines(Depsgraph *depsgraph, LineartGpencilModifierData *lmd, LineartCache **cached_result, bool enable_stroke_depth_offset) { - LineartRenderBuffer *rb; + LineartData *ld; Scene *scene = DEG_get_evaluated_scene(depsgraph); int intersections_only = 0; /* Not used right now, but preserve for future. */ Object *use_camera; double t_start; - if (G.debug_value == 4000) { t_start = PIL_check_seconds_timer(); } - BKE_scene_camera_switch_update(scene); - if (lmd->calculation_flags & LRT_USE_CUSTOM_CAMERA) { if (!lmd->source_camera || (use_camera = DEG_get_evaluated_object(depsgraph, lmd->source_camera))->type != @@ -4453,6 +4964,9 @@ bool MOD_lineart_compute_feature_lines(Depsgraph *depsgraph, } } else { + + BKE_scene_camera_switch_update(scene); + if (!scene->camera) { return false; } @@ -4462,54 +4976,79 @@ bool MOD_lineart_compute_feature_lines(Depsgraph *depsgraph, LineartCache *lc = lineart_init_cache(); *cached_result = lc; - rb = lineart_create_render_buffer(scene, lmd, use_camera, scene->camera, lc); + ld = lineart_create_render_buffer(scene, lmd, use_camera, scene->camera, lc); /* Triangle thread testing data size varies depending on the thread count. * See definition of LineartTriangleThread for details. */ - rb->triangle_size = lineart_triangle_size_get(scene, rb); - - /* FIXME(Yiming): See definition of int #LineartRenderBuffer::_source_type for detailed. */ - rb->_source_type = lmd->source_type; - rb->_source_collection = lmd->source_collection; - rb->_source_object = lmd->source_object; + ld->sizeof_triangle = lineart_triangle_size_get(ld); + + LineartData *shadow_rb = NULL; + LineartElementLinkNode *shadow_veln, *shadow_eeln; + ListBase *shadow_elns = ld->conf.shadow_selection ? &lc->shadow_elns : NULL; + bool shadow_generated = lineart_main_try_generate_shadow(depsgraph, + scene, + ld, + lmd, + &lc->shadow_data_pool, + &shadow_veln, + &shadow_eeln, + shadow_elns, + &shadow_rb); /* Get view vector before loading geometries, because we detect feature lines there. */ - lineart_main_get_view_vector(rb); - lineart_main_load_geometries( - depsgraph, scene, use_camera, rb, lmd->calculation_flags & LRT_ALLOW_DUPLI_OBJECTS); + lineart_main_get_view_vector(ld); + + lineart_main_load_geometries(depsgraph, + scene, + use_camera, + ld, + lmd->calculation_flags & LRT_ALLOW_DUPLI_OBJECTS, + false, + shadow_elns); - if (!rb->vertex_buffer_pointers.first) { + if (shadow_generated) { + lineart_main_transform_and_add_shadow(ld, shadow_veln, shadow_eeln); + } + + if (!ld->geom.vertex_buffer_pointers.first) { /* No geometry loaded, return early. */ return true; } /* Initialize the bounding box acceleration structure, it's a lot like BVH in 3D. */ - lineart_main_bounding_area_make_initial(rb); + lineart_main_bounding_area_make_initial(ld); /* We need to get cut into triangles that are crossing near/far plans, only this way can we get * correct coordinates of those clipped lines. Done in two steps, * setting clip_far==false for near plane. */ - lineart_main_cull_triangles(rb, false); + lineart_main_cull_triangles(ld, false); /* `clip_far == true` for far plane. */ - lineart_main_cull_triangles(rb, true); + lineart_main_cull_triangles(ld, true); /* At this point triangle adjacent info pointers is no longer needed, free them. */ - lineart_main_free_adjacent_data(rb); + lineart_main_free_adjacent_data(ld); /* Do the perspective division after clipping is done. */ - lineart_main_perspective_division(rb); + lineart_main_perspective_division(ld); - lineart_main_discard_out_of_frame_edges(rb); + lineart_main_discard_out_of_frame_edges(ld); /* Triangle intersections are done here during sequential adding of them. Only after this, * triangles and lines are all linked with acceleration structure, and the 2D occlusion stage * can do its job. */ - lineart_main_add_triangles(rb); + lineart_main_add_triangles(ld); + + /* Add shadow cuts to intersection lines as well. */ + lineart_register_intersection_shadow_cuts(ld, shadow_elns); + + /* Re-link bounding areas because they have been subdivided by worker threads and we need + * adjacent info. */ + lineart_main_bounding_areas_connect_post(ld); /* Link lines to acceleration structure, this can only be done after perspective division, if * we do it after triangles being added, the acceleration structure has already been * subdivided, this way we do less list manipulations. */ - lineart_main_link_lines(rb); + lineart_main_link_lines(ld); /* "intersection_only" is preserved for being called in a standalone fashion. * If so the data will already be available at the stage. Otherwise we do the occlusion and @@ -4518,54 +5057,65 @@ bool MOD_lineart_compute_feature_lines(Depsgraph *depsgraph, if (!intersections_only) { /* Occlusion is work-and-wait. This call will not return before work is completed. */ - lineart_main_occlusion_begin(rb); + lineart_main_occlusion_begin(ld); + + 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. */ - MOD_lineart_chain_feature_lines(rb); + MOD_lineart_chain_feature_lines(ld); /* We are unable to take care of occlusion if we only connect end points, so here we do a * spit, where the splitting point could be any cut in e->segments. */ - MOD_lineart_chain_split_for_fixed_occlusion(rb); + MOD_lineart_chain_split_for_fixed_occlusion(ld); /* Then we connect chains based on the _proximity_ of their end points in image space, here's * the place threshold value gets involved. */ - MOD_lineart_chain_connect(rb); - - 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(rb, MIN2(*t_image, 0.001f) - FLT_EPSILON); + MOD_lineart_chain_connect(ld); - if (rb->chain_smooth_tolerance > 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 * somewhat arbitrary, but works best for the moment. */ - MOD_lineart_smooth_chains(rb, rb->chain_smooth_tolerance / 50); + MOD_lineart_smooth_chains(ld, ld->conf.chain_smooth_tolerance / 50); } - if (rb->use_image_boundary_trimming) { - MOD_lineart_chain_clip_at_border(rb); + if (ld->conf.use_image_boundary_trimming) { + MOD_lineart_chain_clip_at_border(ld); } - if (rb->angle_splitting_threshold > FLT_EPSILON) { - MOD_lineart_chain_split_angle(rb, rb->angle_splitting_threshold); + if (ld->conf.angle_splitting_threshold > FLT_EPSILON) { + MOD_lineart_chain_split_angle(ld, ld->conf.angle_splitting_threshold); } if (enable_stroke_depth_offset && lmd->stroke_depth_offset > FLT_EPSILON) { MOD_lineart_chain_offset_towards_camera( - rb, lmd->stroke_depth_offset, lmd->flags & LRT_GPENCIL_OFFSET_TOWARDS_CUSTOM_CAMERA); + ld, lmd->stroke_depth_offset, lmd->flags & LRT_GPENCIL_OFFSET_TOWARDS_CUSTOM_CAMERA); + } + + if (ld->conf.shadow_use_silhouette) { + MOD_lineart_chain_find_silhouette_backdrop_objects(ld); } /* Finally transfer the result list into cache. */ - memcpy(&lc->chains, &rb->chains, sizeof(ListBase)); + memcpy(&lc->chains, &ld->chains, sizeof(ListBase)); /* At last, we need to clear flags so we don't confuse GPencil generation calls. */ MOD_lineart_chain_clear_picked_flag(lc); } + lineart_mem_destroy(&lc->shadow_data_pool); + + if (ld->conf.shadow_enclose_shapes && shadow_rb) { + lineart_destroy_render_data_keep_init(shadow_rb); + MEM_freeN(shadow_rb); + } + if (G.debug_value == 4000) { - lineart_count_and_print_render_buffer_memory(rb); + lineart_count_and_print_render_buffer_memory(ld); double t_elapsed = PIL_check_seconds_timer() - t_start; printf("Line art total time: %lf\n", t_elapsed); @@ -4574,18 +5124,6 @@ bool MOD_lineart_compute_feature_lines(Depsgraph *depsgraph, return true; } -static int UNUSED_FUNCTION(lineart_rb_edge_types)(LineartRenderBuffer *rb) -{ - int types = 0; - types |= rb->use_contour ? LRT_EDGE_FLAG_CONTOUR : 0; - types |= rb->use_crease ? LRT_EDGE_FLAG_CREASE : 0; - types |= rb->use_material ? LRT_EDGE_FLAG_MATERIAL : 0; - types |= rb->use_edge_marks ? LRT_EDGE_FLAG_EDGE_MARK : 0; - types |= rb->use_intersections ? LRT_EDGE_FLAG_INTERSECTION : 0; - types |= rb->use_loose ? LRT_EDGE_FLAG_LOOSE : 0; - return types; -} - static void lineart_gpencil_generate(LineartCache *cache, Depsgraph *depsgraph, Object *gpencil_object, @@ -4601,8 +5139,10 @@ static void lineart_gpencil_generate(LineartCache *cache, uchar mask_switches, uchar material_mask_bits, uchar intersection_mask, - short thickness, + int16_t thickness, float opacity, + uchar shaodow_selection, + uchar silhouette_mode, const char *source_vgname, const char *vgname, int modifier_flags) @@ -4630,9 +5170,10 @@ static void lineart_gpencil_generate(LineartCache *cache, /* (!orig_col && !orig_ob) means the whole scene is selected. */ - int enabled_types = cache->rb_edge_types; + int enabled_types = cache->all_enabled_edge_types; bool invert_input = modifier_flags & LRT_GPENCIL_INVERT_SOURCE_VGROUP; bool match_output = modifier_flags & LRT_GPENCIL_MATCH_OUTPUT_VGROUP; + bool inverse_silhouette = modifier_flags & LRT_GPENCIL_INVERT_SILHOUETTE_FILTER; LISTBASE_FOREACH (LineartEdgeChain *, ec, &cache->chains) { @@ -4684,11 +5225,55 @@ static void lineart_gpencil_generate(LineartCache *cache, } } } + if (shaodow_selection) { + if (ec->shadow_mask_bits != LRT_SHADOW_MASK_UNDEFINED) { + /* TODO(@Yiming): Give a behavior option for how to display undefined shadow info. */ + if ((shaodow_selection == LRT_SHADOW_FILTER_LIT && + (!(ec->shadow_mask_bits & LRT_SHADOW_MASK_LIT))) || + (shaodow_selection == LRT_SHADOW_FILTER_SHADED && + (!(ec->shadow_mask_bits & LRT_SHADOW_MASK_SHADED)))) { + continue; + } + } + } + if (silhouette_mode && (ec->type & (LRT_EDGE_FLAG_CONTOUR))) { + bool is_silhouette = false; + if (orig_col) { + if (!ec->silhouette_backdrop) { + is_silhouette = true; + } + else if (!BKE_collection_has_object_recursive_instanced(orig_col, + ec->silhouette_backdrop)) { + is_silhouette = true; + } + } + else { + if ((!orig_ob) && (!ec->silhouette_backdrop)) { + is_silhouette = true; + } + } + + if ((silhouette_mode == LRT_SILHOUETTE_FILTER_INDIVIDUAL || orig_ob) && + ec->silhouette_backdrop != ec->object_ref) { + is_silhouette = true; + } + + if (inverse_silhouette) { + is_silhouette = !is_silhouette; + } + if (!is_silhouette) { + continue; + } + } /* Preserved: If we ever do asynchronous generation, this picked flag should be set here. */ // ec->picked = 1; const int count = MOD_lineart_chain_count(ec); + if (count < 2) { + continue; + } + bGPDstroke *gps = BKE_gpencil_stroke_add(gpf, color_idx, count, thickness, false); int i; @@ -4760,17 +5345,19 @@ void MOD_lineart_gpencil_generate(LineartCache *cache, Object *ob, bGPDlayer *gpl, bGPDframe *gpf, - char source_type, + int8_t source_type, void *source_reference, int level_start, int level_end, int mat_nr, - short edge_types, + int16_t edge_types, uchar mask_switches, uchar material_mask_bits, uchar intersection_mask, - short thickness, + int16_t thickness, float opacity, + uchar shadow_selection, + uchar silhouette_mode, const char *source_vgname, const char *vgname, int modifier_flags) @@ -4782,26 +5369,20 @@ void MOD_lineart_gpencil_generate(LineartCache *cache, Object *source_object = NULL; Collection *source_collection = NULL; - short use_types = 0; + int16_t use_types = edge_types; if (source_type == LRT_SOURCE_OBJECT) { if (!source_reference) { return; } source_object = (Object *)source_reference; - /* Note that intersection lines will only be in collection. */ - use_types = edge_types & (~LRT_EDGE_FLAG_INTERSECTION); } else if (source_type == LRT_SOURCE_COLLECTION) { if (!source_reference) { return; } source_collection = (Collection *)source_reference; - use_types = edge_types; - } - else { - /* Whole scene. */ - use_types = edge_types; } + float gp_obmat_inverse[4][4]; invert_m4_m4(gp_obmat_inverse, ob->obmat); lineart_gpencil_generate(cache, @@ -4821,6 +5402,8 @@ void MOD_lineart_gpencil_generate(LineartCache *cache, intersection_mask, thickness, opacity, + shadow_selection, + silhouette_mode, source_vgname, vgname, modifier_flags); |