Blender V5.3
lineart_cpu.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2019 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <algorithm>
10
11#include "MOD_lineart.hh"
12
13#include "BLI_bounds.hh"
14#include "BLI_listbase.hh"
15#include "BLI_math_geom_c.hh"
16#include "BLI_math_matrix.hh"
17#include "BLI_math_matrix_c.hh"
19#include "BLI_sort.hh"
20#include "BLI_task_c.hh"
21#include "BLI_time.hh"
22#include "BLI_utildefines.hh"
23#include "BLI_vector.hh"
24
25#include "BKE_attribute.hh"
26#include "BKE_camera.h"
27#include "BKE_collection.hh"
28#include "BKE_curves.hh"
29#include "BKE_customdata.hh"
30#include "BKE_deform.hh"
31#include "BKE_geometry_set.hh"
32#include "BKE_global.hh"
33#include "BKE_grease_pencil.hh"
35#include "BKE_lib_id.hh"
36#include "BKE_material.hh"
37#include "BKE_mesh.hh"
38#include "BKE_object.hh"
39#include "BKE_scene.hh"
40
42
43#include "DNA_camera_types.h"
45#include "DNA_light_types.h"
46#include "DNA_material_types.h"
47#include "DNA_meshdata_types.h"
48#include "DNA_modifier_types.h"
49#include "DNA_object_types.h"
50#include "DNA_scene_types.h"
51
52#include "MEM_guardedalloc.h"
53
54#include "RE_pipeline.h"
55#include "intern/render_types.h"
56
57#include "ED_grease_pencil.hh"
58
60
61#include "lineart_intern.hh"
62
63namespace blender {
64
65using namespace bke;
67
69 double v1[3], v2[3];
71};
72
75
76 /* Scheduled work range. */
81
82 /* Thread intersection result data. */
85 int max;
87
88 /* For individual thread reference. */
90};
91
97
99 LineartBoundingArea *root_ba,
100 LineartEdge *e);
101
103 LineartData *ld, LineartEdge *e, int *rowbegin, int *rowend, int *colbegin, int *colend);
104
106 const LineartEdge *e,
107 const double *override_camera_loc,
108 const bool override_cam_is_persp,
109 const bool allow_overlapping_edges,
110 const double m_view_projection[4][4],
111 const double camera_dir[3],
112 const float cam_shift_x,
113 const float cam_shift_y,
114 double *from,
115 double *to);
116
118 LineartBoundingArea *root_ba,
119 LineartTriangle *tri,
120 double l_r_u_b[4],
121 int recursive,
122 int recursive_level,
123 bool do_intersection,
125
126static void lineart_free_bounding_area_memory(LineartBoundingArea *ba, bool recursive);
127
129
131{
133
134 memset(es, 0, sizeof(LineartEdgeSegment));
135
136 /* Storing the node for potentially reuse the memory for new segment data.
137 * Line Art data is not freed after all calculations are done. */
138 BLI_addtail(&ld->wasted_cuts, es);
139
141}
142
144{
146
147 /* See if there is any already allocated memory we can reuse. */
148 if (ld->wasted_cuts.first_) {
151 memset(es, 0, sizeof(LineartEdgeSegment));
152 return es;
153 }
155
156 /* Otherwise allocate some new memory. */
157 return static_cast<LineartEdgeSegment *>(
159}
160
162 LineartEdge *e,
163 double start,
164 double end,
165 uchar material_mask_bits,
166 uchar mat_occlusion,
167 uint32_t shadow_bits)
168{
169 LineartEdgeSegment *i_seg, *prev_seg;
170 LineartEdgeSegment *cut_start_before = nullptr, *cut_end_before = nullptr;
171 LineartEdgeSegment *new_seg1 = nullptr, *new_seg2 = nullptr;
172 int untouched = 0;
173
174 /* If for some reason the occlusion function may give a result that has zero length, or reversed
175 * in direction, or NAN, we take care of them here. */
176 if (LRT_DOUBLE_CLOSE_ENOUGH(start, end)) {
177 return;
178 }
179 if (LRT_DOUBLE_CLOSE_ENOUGH(start, 1) || LRT_DOUBLE_CLOSE_ENOUGH(end, 0)) {
180 return;
181 }
182 if (start != start) [[unlikely]] {
183 start = 0.0;
184 }
185 if (end != end) [[unlikely]] {
186 end = 0.0;
187 }
188
189 if (start > end) {
190 double t = start;
191 start = end;
192 end = t;
193 }
194
195 /* Begin looking for starting position of the segment. */
196 /* Not using a list iteration macro because of it more clear when using for loops to iterate
197 * through the segments. */
198 for (LineartEdgeSegment &seg : e->segments) {
199 if (LRT_DOUBLE_CLOSE_ENOUGH(seg.ratio, start)) {
200 cut_start_before = &seg;
201 new_seg1 = cut_start_before;
202 break;
203 }
204 if (seg.next == nullptr) {
205 break;
206 }
207 i_seg = seg.next;
208 if (i_seg->ratio > start + 1e-09 && start > seg.ratio) {
209 cut_start_before = i_seg;
210 new_seg1 = lineart_give_segment(ld);
211 break;
212 }
213 }
214 if (!cut_start_before && LRT_DOUBLE_CLOSE_ENOUGH(1, end)) {
215 untouched = 1;
216 }
217 for (LineartEdgeSegment *seg = cut_start_before; seg; seg = seg->next) {
218 /* We tried to cut ratio existing cutting point (e.g. where the line's occluded by a triangle
219 * strip). */
220 if (LRT_DOUBLE_CLOSE_ENOUGH(seg->ratio, end)) {
221 cut_end_before = seg;
222 new_seg2 = cut_end_before;
223 break;
224 }
225 /* This check is to prevent `es->ratio == 1.0` (where we don't need to cut because we are ratio
226 * the end point). */
227 if (!seg->next && LRT_DOUBLE_CLOSE_ENOUGH(1, end)) {
228 cut_end_before = seg;
229 new_seg2 = cut_end_before;
230 untouched = 1;
231 break;
232 }
233 /* When an actual cut is needed in the line. */
234 if (seg->ratio > end) {
235 cut_end_before = seg;
236 new_seg2 = lineart_give_segment(ld);
237 break;
238 }
239 }
240
241 /* When we still can't find any existing cut in the line, we allocate new ones. */
242 if (new_seg1 == nullptr) {
243 new_seg1 = lineart_give_segment(ld);
244 }
245 if (new_seg2 == nullptr) {
246 if (untouched) {
247 new_seg2 = new_seg1;
248 cut_end_before = new_seg2;
249 }
250 else {
251 new_seg2 = lineart_give_segment(ld);
252 }
253 }
254
255 if (cut_start_before) {
256 if (cut_start_before != new_seg1) {
257 /* Insert cutting points for when a new cut is needed. */
258 i_seg = cut_start_before->prev ? cut_start_before->prev : nullptr;
259 if (i_seg) {
260 new_seg1->occlusion = i_seg->occlusion;
261 new_seg1->material_mask_bits = i_seg->material_mask_bits;
262 new_seg1->shadow_mask_bits = i_seg->shadow_mask_bits;
263 }
264 BLI_insertlinkbefore(&e->segments, cut_start_before, new_seg1);
265 }
266 /* Otherwise we already found a existing cutting point, no need to insert a new one. */
267 }
268 else {
269 /* We have yet to reach a existing cutting point even after we searched the whole line, so we
270 * append the new cut to the end. */
271 i_seg = e->segments.last();
272 new_seg1->occlusion = i_seg->occlusion;
273 new_seg1->material_mask_bits = i_seg->material_mask_bits;
274 new_seg1->shadow_mask_bits = i_seg->shadow_mask_bits;
275 BLI_addtail(&e->segments, new_seg1);
276 }
277 if (cut_end_before) {
278 /* The same manipulation as on "cut_start_before". */
279 if (cut_end_before != new_seg2) {
280 i_seg = cut_end_before->prev ? cut_end_before->prev : nullptr;
281 if (i_seg) {
282 new_seg2->occlusion = i_seg->occlusion;
283 new_seg2->material_mask_bits = i_seg->material_mask_bits;
284 new_seg2->shadow_mask_bits = i_seg->shadow_mask_bits;
285 }
286 BLI_insertlinkbefore(&e->segments, cut_end_before, new_seg2);
287 }
288 }
289 else {
290 i_seg = e->segments.last();
291 new_seg2->occlusion = i_seg->occlusion;
292 new_seg2->material_mask_bits = i_seg->material_mask_bits;
293 new_seg2->shadow_mask_bits = i_seg->shadow_mask_bits;
294 if (!untouched) {
295 BLI_addtail(&e->segments, new_seg2);
296 }
297 }
298
299 /* If we touched the cut list, we assign the new cut position based on new cut position,
300 * this way we accommodate precision lost due to multiple cut inserts. */
301 new_seg1->ratio = start;
302 if (!untouched) {
303 new_seg2->ratio = end;
304 }
305 else {
306 /* For the convenience of the loop below. */
307 new_seg2 = new_seg2->next;
308 }
309
310 /* Register 1 level of occlusion for all touched segments. */
311 for (LineartEdgeSegment *seg = new_seg1; seg && seg != new_seg2; seg = seg->next) {
312 seg->occlusion += mat_occlusion;
313 seg->material_mask_bits |= material_mask_bits;
314
315 /* The enclosed shape flag will override regular lit/shaded
316 * flags. See LineartEdgeSegment::shadow_mask_bits for details. */
317 if (shadow_bits == LRT_SHADOW_MASK_ENCLOSED_SHAPE) {
320 {
322 }
325 }
326 }
327 else {
328 seg->shadow_mask_bits |= shadow_bits;
329 }
330 }
331
332 /* Reduce adjacent cutting points of the same level, which saves memory. */
333 int8_t min_occ = 127;
334 prev_seg = nullptr;
335 for (LineartEdgeSegment &seg : e->segments.items_mutable()) {
336
337 if (prev_seg && prev_seg->occlusion == seg.occlusion &&
338 prev_seg->material_mask_bits == seg.material_mask_bits &&
339 prev_seg->shadow_mask_bits == seg.shadow_mask_bits)
340 {
341 BLI_remlink(&e->segments, &seg);
342 /* This puts the node back to the render buffer, if more cut happens, these unused nodes get
343 * picked first. */
344 lineart_discard_segment(ld, &seg);
345 continue;
346 }
347
348 min_occ = std::min<int8_t>(min_occ, seg.occlusion);
349
350 prev_seg = &seg;
351 }
352 e->min_occ = min_occ;
353}
354
359{
360 return (((e->target_reference & LRT_LIGHT_CONTOUR_TARGET) == tri->target_reference) ||
361 (((e->target_reference >> 32) & LRT_LIGHT_CONTOUR_TARGET) == tri->target_reference));
362}
363
370
372{
373 /* In case of too many lines concentrating in one point, do not add anymore, these lines will
374 * be either shorter than a single pixel, or will still be added into the list of other less
375 * dense areas. */
376 if (ba->line_count >= 65535) {
377 return;
378 }
379 if (ba->line_count >= ba->max_line_count) {
381 __func__);
382 memcpy(new_array, ba->linked_lines, sizeof(LineartEdge *) * ba->max_line_count);
383 ba->max_line_count *= 2;
384 MEM_delete(ba->linked_lines);
385 ba->linked_lines = new_array;
386 }
387 ba->linked_lines[ba->line_count] = e;
388 ba->line_count++;
389}
390
392{
394 double l, r;
395 LRT_EDGE_BA_MARCHING_BEGIN(e->v1->fbcoord, e->v2->fbcoord)
396 {
397 for (int i = 0; i < nba->triangle_count; i++) {
398 tri = reinterpret_cast<LineartTriangleThread *>(nba->linked_triangles[i]);
399 /* If we are already testing the line in this thread, then don't do it. */
400 if (tri->testing_e[thread_id] == e || (tri->base.flags & LRT_TRIANGLE_INTERSECTION_ONLY) ||
401 /* Ignore this triangle if an intersection line directly comes from it, */
403 reinterpret_cast<LineartTriangle *>(tri)) ||
404 /* Or if this triangle isn't effectively occluding anything nor it's providing a
405 * material flag. */
406 ((!tri->base.mat_occlusion) && (!tri->base.material_mask_bits)))
407 {
408 continue;
409 }
410 tri->testing_e[thread_id] = e;
412 reinterpret_cast<const LineartTriangle *>(tri),
413 e,
414 ld->conf.camera_pos,
415 ld->conf.cam_is_persp,
418 ld->conf.view_vector,
419 ld->conf.shift_x,
420 ld->conf.shift_y,
421 &l,
422 &r))
423 {
425 if (e->min_occ > ld->conf.max_occlusion_level) {
426 /* No need to calculate any longer on this line because no level more than set value is
427 * going to show up in the rendered result. */
428 return;
429 }
430 }
431 }
432 LRT_EDGE_BA_MARCHING_NEXT(e->v1->fbcoord, e->v2->fbcoord)
433 }
435}
436
438{
439 int res = 0;
440 int starting_index;
441
443
444 starting_index = ld->scheduled_count;
446
448
449 if (starting_index >= ld->pending_edges.next) {
450 res = 0;
451 }
452 else {
453 rti->pending_edges.array = &ld->pending_edges.array[starting_index];
454 int remaining = ld->pending_edges.next - starting_index;
455 rti->pending_edges.max = std::min(remaining, LRT_THREAD_EDGE_COUNT);
456 res = 1;
457 }
458
459 return res;
460}
461
462static void lineart_occlusion_worker(TaskPool *__restrict /*pool*/, LineartRenderTaskInfo *rti)
463{
464 LineartData *ld = rti->ld;
465 LineartEdge *eip;
466
467 while (lineart_occlusion_make_task_info(ld, rti)) {
468 for (int i = 0; i < rti->pending_edges.max; i++) {
469 eip = rti->pending_edges.array[i];
471 }
472 }
473}
474
476{
477 int thread_count = ld->thread_count;
479 int i;
480
482
483 for (i = 0; i < thread_count; i++) {
484 rti[i].thread_id = i;
485 rti[i].ld = ld;
487 tp, reinterpret_cast<TaskRunFunction>(lineart_occlusion_worker), &rti[i], false, nullptr);
488 }
491
492 MEM_delete(rti);
493}
494
502static bool lineart_point_inside_triangle(const double v[2],
503 const double v0[2],
504 const double v1[2],
505 const double v2[2])
506{
507 double cl, c, cl0;
508
509 cl = (v0[0] - v[0]) * (v1[1] - v[1]) - (v0[1] - v[1]) * (v1[0] - v[0]);
510 c = cl0 = cl;
511
512 cl = (v1[0] - v[0]) * (v2[1] - v[1]) - (v1[1] - v[1]) * (v2[0] - v[0]);
513 if (c * cl <= 0) {
514 return false;
515 }
516
517 c = cl;
518
519 cl = (v2[0] - v[0]) * (v0[1] - v[1]) - (v2[1] - v[1]) * (v0[0] - v[0]);
520 if (c * cl <= 0) {
521 return false;
522 }
523
524 c = cl;
525
526 if (c * cl0 <= 0) {
527 return false;
528 }
529
530 return true;
531}
532
533static int lineart_point_on_line_segment(double v[2], double v0[2], double v1[2])
534{
535 /* `c1 != c2` by default. */
536 double c1 = 1, c2 = 0;
537 double l0[2], l1[2];
538
539 sub_v2_v2v2_db(l0, v, v0);
540 sub_v2_v2v2_db(l1, v, v1);
541
542 if (v1[0] == v0[0] && v1[1] == v0[1]) {
543 return 0;
544 }
545
546 if (!LRT_DOUBLE_CLOSE_ENOUGH(v1[0], v0[0])) {
547 c1 = ratiod(v0[0], v1[0], v[0]);
548 }
549 else {
550 if (LRT_DOUBLE_CLOSE_ENOUGH(v[0], v1[0])) {
551 c2 = ratiod(v0[1], v1[1], v[1]);
552 return (c2 >= -DBL_TRIANGLE_LIM && c2 <= 1 + DBL_TRIANGLE_LIM);
553 }
554 return false;
555 }
556
557 if (!LRT_DOUBLE_CLOSE_ENOUGH(v1[1], v0[1])) {
558 c2 = ratiod(v0[1], v1[1], v[1]);
559 }
560 else {
561 if (LRT_DOUBLE_CLOSE_ENOUGH(v[1], v1[1])) {
562 c1 = ratiod(v0[0], v1[0], v[0]);
563 return (c1 >= -DBL_TRIANGLE_LIM && c1 <= 1 + DBL_TRIANGLE_LIM);
564 }
565 return false;
566 }
567
568 if (LRT_DOUBLE_CLOSE_ENOUGH(c1, c2) && c1 >= 0 && c1 <= 1) {
569 return 1;
570 }
571
572 return 0;
573}
574
580
586 double v0[2],
587 double v1[2],
588 double v2[2])
589{
590 double cl, c;
591 double r;
594 {
595 return LRT_ON_TRIANGLE;
596 }
597
598 cl = (v0[0] - v[0]) * (v1[1] - v[1]) - (v0[1] - v[1]) * (v1[0] - v[0]);
599 c = cl;
600
601 cl = (v1[0] - v[0]) * (v2[1] - v[1]) - (v1[1] - v[1]) * (v2[0] - v[0]);
602 if ((r = c * cl) < 0) {
604 }
605
606 c = cl;
607
608 cl = (v2[0] - v[0]) * (v0[1] - v[1]) - (v2[1] - v[1]) * (v0[0] - v[0]);
609 if ((r = c * cl) < 0) {
611 }
612
613 c = cl;
614
615 cl = (v0[0] - v[0]) * (v1[1] - v[1]) - (v0[1] - v[1]) * (v1[0] - v[0]);
616 if ((r = c * cl) < 0) {
618 }
619
620 if (r == 0) {
621 return LRT_ON_TRIANGLE;
622 }
623
624 return LRT_INSIDE_TRIANGLE;
625}
626
631static bool lineart_point_inside_triangle3d(double v[3], double v0[3], double v1[3], double v2[3])
632{
633 double l[3], r[3];
634 double N1[3], N2[3];
635 double d;
636
637 sub_v3_v3v3_db(l, v1, v0);
638 sub_v3_v3v3_db(r, v, v1);
639 cross_v3_v3v3_db(N1, l, r);
640
641 sub_v3_v3v3_db(l, v2, v1);
642 sub_v3_v3v3_db(r, v, v2);
643 cross_v3_v3v3_db(N2, l, r);
644
645 if ((d = dot_v3v3_db(N1, N2)) < 0) {
646 return false;
647 }
648
649 sub_v3_v3v3_db(l, v0, v2);
650 sub_v3_v3v3_db(r, v, v0);
651 cross_v3_v3v3_db(N1, l, r);
652
653 if ((d = dot_v3v3_db(N1, N2)) < 0) {
654 return false;
655 }
656
657 sub_v3_v3v3_db(l, v1, v0);
658 sub_v3_v3v3_db(r, v, v1);
659 cross_v3_v3v3_db(N2, l, r);
660
661 if ((d = dot_v3v3_db(N1, N2)) < 0) {
662 return false;
663 }
664
665 return true;
666}
667
673{
674 /* We don't need to allocate a whole bunch of triangles because the amount of clipped triangles
675 * are relatively small. */
676 LineartTriangle *render_triangles = static_cast<LineartTriangle *>(
678
681 &ld->render_data_pool,
682 render_triangles,
683 sizeof(LineartElementLinkNode)));
684 eln->element_count = 64;
686
687 return eln;
688}
689
691{
692 LineartVert *render_vertices = static_cast<LineartVert *>(
694
697 &ld->render_data_pool,
698 render_vertices,
699 sizeof(LineartElementLinkNode)));
700 eln->element_count = 64;
702
703 return eln;
704}
705
707{
708 LineartEdge *render_edges = static_cast<LineartEdge *>(
710
713 ld->edge_data_pool,
714 render_edges,
715 sizeof(LineartElementLinkNode)));
716 eln->element_count = 64;
719
720 return eln;
721}
722
724{
725 /* Just re-assign normal and set cull flag. */
726 copy_v3_v3_db(tri->gn, orig->gn);
730 tri->mat_occlusion = orig->mat_occlusion;
733}
734
736{
737 uchar intersection_only = (tri->flags & LRT_TRIANGLE_INTERSECTION_ONLY);
738 tri->flags = flag;
739 tri->flags |= intersection_only;
740}
741
742static bool lineart_edge_match(LineartTriangle *tri, LineartEdge *e, int v1, int v2)
743{
744 return ((tri->v[v1] == e->v1 && tri->v[v2] == e->v2) ||
745 (tri->v[v2] == e->v1 && tri->v[v1] == e->v2));
746}
747
749{
750 LineartEdge *e = old_e;
752 e++;
754 }
755}
756
762 LineartTriangle *tri,
763 int in0,
764 int in1,
765 int in2,
766 double cam_pos[3],
767 double view_dir[3],
768 bool allow_boundaries,
769 double m_view_projection[4][4],
770 Object *ob,
771 int *r_v_count,
772 int *r_e_count,
773 int *r_t_count,
777{
778 double span_v1[3], span_v2[3], dot_v1, dot_v2;
779 double a;
780 int v_count = *r_v_count;
781 int e_count = *r_e_count;
782 int t_count = *r_t_count;
783 uint16_t new_flag = 0;
784
785 LineartEdge *new_e, *e, *old_e;
787
789 return;
790 }
791
792 /* See definition of tri->intersecting_verts and the usage in
793 * lineart_geometry_object_load() for details. */
794 LineartTriangleAdjacent *tri_adj = reinterpret_cast<LineartTriangleAdjacent *>(
795 tri->intersecting_verts);
796
797 LineartVert *vt = &(static_cast<LineartVert *>(v_eln->pointer))[v_count];
798 LineartTriangle *tri1 = static_cast<LineartTriangle *>(static_cast<void *>(
799 (static_cast<uchar *>(t_eln->pointer)) + size_t(ld->sizeof_triangle) * t_count));
800 LineartTriangle *tri2 = static_cast<LineartTriangle *>(static_cast<void *>(
801 (static_cast<uchar *>(t_eln->pointer)) + size_t(ld->sizeof_triangle) * (t_count + 1)));
802
803 new_e = &(static_cast<LineartEdge *>(e_eln->pointer))[e_count];
804 /* Init `edge` to the last `edge` entry. */
805 e = new_e;
806
807#define INCREASE_EDGE \
808 new_e = &((LineartEdge *)e_eln->pointer)[e_count]; \
809 e_count++; \
810 e = new_e; \
811 es = static_cast<LineartEdgeSegment *>( \
812 lineart_mem_acquire(&ld->render_data_pool, sizeof(LineartEdgeSegment))); \
813 BLI_addtail(&e->segments, es);
814
815#define SELECT_EDGE(e_num, v1_link, v2_link, new_tri) \
816 if (tri_adj->e[e_num]) { \
817 old_e = tri_adj->e[e_num]; \
818 new_flag = old_e->flags; \
819 old_e->flags = MOD_LINEART_EDGE_FLAG_CHAIN_PICKED; \
820 lineart_discard_duplicated_edges(old_e); \
821 INCREASE_EDGE \
822 e->v1 = (v1_link); \
823 e->v2 = (v2_link); \
824 e->v1->index = (v1_link)->index; \
825 e->v2->index = (v1_link)->index; \
826 e->flags = new_flag; \
827 e->object_ref = ob; \
828 e->t1 = ((old_e->t1 == tri) ? (new_tri) : (old_e->t1)); \
829 e->t2 = ((old_e->t2 == tri) ? (new_tri) : (old_e->t2)); \
830 lineart_add_edge_to_array(&ld->pending_edges, e); \
831 }
832
833#define RELINK_EDGE(e_num, new_tri) \
834 if (tri_adj->e[e_num]) { \
835 old_e = tri_adj->e[e_num]; \
836 old_e->t1 = ((old_e->t1 == tri) ? (new_tri) : (old_e->t1)); \
837 old_e->t2 = ((old_e->t2 == tri) ? (new_tri) : (old_e->t2)); \
838 }
839
840#define REMOVE_TRIANGLE_EDGE \
841 if (tri_adj->e[0]) { \
842 tri_adj->e[0]->flags = MOD_LINEART_EDGE_FLAG_CHAIN_PICKED; \
843 lineart_discard_duplicated_edges(tri_adj->e[0]); \
844 } \
845 if (tri_adj->e[1]) { \
846 tri_adj->e[1]->flags = MOD_LINEART_EDGE_FLAG_CHAIN_PICKED; \
847 lineart_discard_duplicated_edges(tri_adj->e[1]); \
848 } \
849 if (tri_adj->e[2]) { \
850 tri_adj->e[2]->flags = MOD_LINEART_EDGE_FLAG_CHAIN_PICKED; \
851 lineart_discard_duplicated_edges(tri_adj->e[2]); \
852 }
853
854 switch (in0 + in1 + in2) {
855 case 0: /* Triangle is visible. Ignore this triangle. */
856 return;
857 case 3:
858 /* Triangle completely behind near plane, throw it away
859 * also remove render lines form being computed. */
862 return;
863 case 2:
864 /* Two points behind near plane, cut those and
865 * generate 2 new points, 3 lines and 1 triangle. */
867
888 if (!in0) {
889
890 /* Cut point for line 2---|-----0. */
891 sub_v3_v3v3_db(span_v1, tri->v[0]->gloc, cam_pos);
892 sub_v3_v3v3_db(span_v2, cam_pos, tri->v[2]->gloc);
893 dot_v1 = dot_v3v3_db(span_v1, view_dir);
894 dot_v2 = dot_v3v3_db(span_v2, view_dir);
895 a = dot_v1 / (dot_v1 + dot_v2);
896 /* Assign it to a new point. */
897 interp_v3_v3v3_db(vt[0].gloc, tri->v[0]->gloc, tri->v[2]->gloc, a);
898 mul_v4_m4v3_db(vt[0].fbcoord, m_view_projection, vt[0].gloc);
899 vt[0].index = tri->v[2]->index;
900
901 /* Cut point for line 1---|-----0. */
902 sub_v3_v3v3_db(span_v1, tri->v[0]->gloc, cam_pos);
903 sub_v3_v3v3_db(span_v2, cam_pos, tri->v[1]->gloc);
904 dot_v1 = dot_v3v3_db(span_v1, view_dir);
905 dot_v2 = dot_v3v3_db(span_v2, view_dir);
906 a = dot_v1 / (dot_v1 + dot_v2);
907 /* Assign it to another new point. */
908 interp_v3_v3v3_db(vt[1].gloc, tri->v[0]->gloc, tri->v[1]->gloc, a);
909 mul_v4_m4v3_db(vt[1].fbcoord, m_view_projection, vt[1].gloc);
910 vt[1].index = tri->v[1]->index;
911
912 /* New line connecting two new points. */
914 if (allow_boundaries) {
917 }
918 /* NOTE: inverting `e->v1/v2` (left/right point) doesn't matter as long as
919 * `tri->edge` and `tri->v` has the same sequence. and the winding direction
920 * can be either CW or CCW but needs to be consistent throughout the calculation. */
921 e->v1 = &vt[1];
922 e->v2 = &vt[0];
923 /* Only one adjacent triangle, because the other side is the near plane. */
924 /* Use `tl` or `tr` doesn't matter. */
925 e->t1 = tri1;
926 e->object_ref = ob;
927
928 /* New line connecting original point 0 and a new point, only when it's a selected line. */
929 SELECT_EDGE(2, tri->v[0], &vt[0], tri1)
930 /* New line connecting original point 0 and another new point. */
931 SELECT_EDGE(0, tri->v[0], &vt[1], tri1)
932
933 /* Re-assign triangle point array to two new points. */
934 tri1->v[0] = tri->v[0];
935 tri1->v[1] = &vt[1];
936 tri1->v[2] = &vt[0];
937
938 lineart_triangle_post(tri1, tri);
939
940 v_count += 2;
941 t_count += 1;
942 }
943 else if (!in2) {
944 sub_v3_v3v3_db(span_v1, tri->v[2]->gloc, cam_pos);
945 sub_v3_v3v3_db(span_v2, cam_pos, tri->v[0]->gloc);
946 dot_v1 = dot_v3v3_db(span_v1, view_dir);
947 dot_v2 = dot_v3v3_db(span_v2, view_dir);
948 a = dot_v1 / (dot_v1 + dot_v2);
949 interp_v3_v3v3_db(vt[0].gloc, tri->v[2]->gloc, tri->v[0]->gloc, a);
950 mul_v4_m4v3_db(vt[0].fbcoord, m_view_projection, vt[0].gloc);
951 vt[0].index = tri->v[0]->index;
952
953 sub_v3_v3v3_db(span_v1, tri->v[2]->gloc, cam_pos);
954 sub_v3_v3v3_db(span_v2, cam_pos, tri->v[1]->gloc);
955 dot_v1 = dot_v3v3_db(span_v1, view_dir);
956 dot_v2 = dot_v3v3_db(span_v2, view_dir);
957 a = dot_v1 / (dot_v1 + dot_v2);
958 interp_v3_v3v3_db(vt[1].gloc, tri->v[2]->gloc, tri->v[1]->gloc, a);
959 mul_v4_m4v3_db(vt[1].fbcoord, m_view_projection, vt[1].gloc);
960 vt[1].index = tri->v[1]->index;
961
963 if (allow_boundaries) {
966 }
967 e->v1 = &vt[0];
968 e->v2 = &vt[1];
969 e->t1 = tri1;
970 e->object_ref = ob;
971
972 SELECT_EDGE(2, tri->v[2], &vt[0], tri1)
973 SELECT_EDGE(1, tri->v[2], &vt[1], tri1)
974
975 tri1->v[0] = &vt[0];
976 tri1->v[1] = &vt[1];
977 tri1->v[2] = tri->v[2];
978
979 lineart_triangle_post(tri1, tri);
980
981 v_count += 2;
982 t_count += 1;
983 }
984 else if (!in1) {
985 sub_v3_v3v3_db(span_v1, tri->v[1]->gloc, cam_pos);
986 sub_v3_v3v3_db(span_v2, cam_pos, tri->v[2]->gloc);
987 dot_v1 = dot_v3v3_db(span_v1, view_dir);
988 dot_v2 = dot_v3v3_db(span_v2, view_dir);
989 a = dot_v1 / (dot_v1 + dot_v2);
990 interp_v3_v3v3_db(vt[0].gloc, tri->v[1]->gloc, tri->v[2]->gloc, a);
991 mul_v4_m4v3_db(vt[0].fbcoord, m_view_projection, vt[0].gloc);
992 vt[0].index = tri->v[2]->index;
993
994 sub_v3_v3v3_db(span_v1, tri->v[1]->gloc, cam_pos);
995 sub_v3_v3v3_db(span_v2, cam_pos, tri->v[0]->gloc);
996 dot_v1 = dot_v3v3_db(span_v1, view_dir);
997 dot_v2 = dot_v3v3_db(span_v2, view_dir);
998 a = dot_v1 / (dot_v1 + dot_v2);
999 interp_v3_v3v3_db(vt[1].gloc, tri->v[1]->gloc, tri->v[0]->gloc, a);
1000 mul_v4_m4v3_db(vt[1].fbcoord, m_view_projection, vt[1].gloc);
1001 vt[1].index = tri->v[0]->index;
1002
1004 if (allow_boundaries) {
1007 }
1008 e->v1 = &vt[1];
1009 e->v2 = &vt[0];
1010 e->t1 = tri1;
1011 e->object_ref = ob;
1012
1013 SELECT_EDGE(1, tri->v[1], &vt[0], tri1)
1014 SELECT_EDGE(0, tri->v[1], &vt[1], tri1)
1015
1016 tri1->v[0] = &vt[0];
1017 tri1->v[1] = tri->v[1];
1018 tri1->v[2] = &vt[1];
1019
1020 lineart_triangle_post(tri1, tri);
1021
1022 v_count += 2;
1023 t_count += 1;
1024 }
1025 break;
1026 case 1:
1027 /* One point behind near plane, cut those and
1028 * generate 2 new points, 4 lines and 2 triangles. */
1030
1054 if (in0) {
1055 /* Cut point for line 0---|------1. */
1056 sub_v3_v3v3_db(span_v1, tri->v[1]->gloc, cam_pos);
1057 sub_v3_v3v3_db(span_v2, cam_pos, tri->v[0]->gloc);
1058 dot_v1 = dot_v3v3_db(span_v1, view_dir);
1059 dot_v2 = dot_v3v3_db(span_v2, view_dir);
1060 a = dot_v2 / (dot_v1 + dot_v2);
1061 /* Assign to a new point. */
1062 interp_v3_v3v3_db(vt[0].gloc, tri->v[0]->gloc, tri->v[1]->gloc, a);
1063 mul_v4_m4v3_db(vt[0].fbcoord, m_view_projection, vt[0].gloc);
1064 vt[0].index = tri->v[0]->index;
1065
1066 /* Cut point for line 0---|------2. */
1067 sub_v3_v3v3_db(span_v1, tri->v[2]->gloc, cam_pos);
1068 sub_v3_v3v3_db(span_v2, cam_pos, tri->v[0]->gloc);
1069 dot_v1 = dot_v3v3_db(span_v1, view_dir);
1070 dot_v2 = dot_v3v3_db(span_v2, view_dir);
1071 a = dot_v2 / (dot_v1 + dot_v2);
1072 /* Assign to other new point. */
1073 interp_v3_v3v3_db(vt[1].gloc, tri->v[0]->gloc, tri->v[2]->gloc, a);
1074 mul_v4_m4v3_db(vt[1].fbcoord, m_view_projection, vt[1].gloc);
1075 vt[1].index = tri->v[0]->index;
1076
1077 /* New line connects two new points. */
1079 if (allow_boundaries) {
1082 }
1083 e->v1 = &vt[1];
1084 e->v2 = &vt[0];
1085 e->t1 = tri1;
1086 e->object_ref = ob;
1087
1088 /* New line connects new point 0 and old point 1,
1089 * this is a border line. */
1090
1091 SELECT_EDGE(0, tri->v[1], &vt[0], tri1)
1092 SELECT_EDGE(2, tri->v[2], &vt[1], tri2)
1093 RELINK_EDGE(1, tri2)
1094
1095 /* We now have one triangle closed. */
1096 tri1->v[0] = tri->v[1];
1097 tri1->v[1] = &vt[1];
1098 tri1->v[2] = &vt[0];
1099 /* Close the second triangle. */
1100 tri2->v[0] = &vt[1];
1101 tri2->v[1] = tri->v[1];
1102 tri2->v[2] = tri->v[2];
1103
1104 lineart_triangle_post(tri1, tri);
1105 lineart_triangle_post(tri2, tri);
1106
1107 v_count += 2;
1108 t_count += 2;
1109 }
1110 else if (in1) {
1111
1112 sub_v3_v3v3_db(span_v1, tri->v[1]->gloc, cam_pos);
1113 sub_v3_v3v3_db(span_v2, cam_pos, tri->v[2]->gloc);
1114 dot_v1 = dot_v3v3_db(span_v1, view_dir);
1115 dot_v2 = dot_v3v3_db(span_v2, view_dir);
1116 a = dot_v1 / (dot_v1 + dot_v2);
1117 interp_v3_v3v3_db(vt[0].gloc, tri->v[1]->gloc, tri->v[2]->gloc, a);
1118 mul_v4_m4v3_db(vt[0].fbcoord, m_view_projection, vt[0].gloc);
1119 vt[0].index = tri->v[1]->index;
1120
1121 sub_v3_v3v3_db(span_v1, tri->v[1]->gloc, cam_pos);
1122 sub_v3_v3v3_db(span_v2, cam_pos, tri->v[0]->gloc);
1123 dot_v1 = dot_v3v3_db(span_v1, view_dir);
1124 dot_v2 = dot_v3v3_db(span_v2, view_dir);
1125 a = dot_v1 / (dot_v1 + dot_v2);
1126 interp_v3_v3v3_db(vt[1].gloc, tri->v[1]->gloc, tri->v[0]->gloc, a);
1127 mul_v4_m4v3_db(vt[1].fbcoord, m_view_projection, vt[1].gloc);
1128 vt[1].index = tri->v[1]->index;
1129
1131 if (allow_boundaries) {
1134 }
1135 e->v1 = &vt[1];
1136 e->v2 = &vt[0];
1137
1138 e->t1 = tri1;
1139 e->object_ref = ob;
1140
1141 SELECT_EDGE(1, tri->v[2], &vt[0], tri1)
1142 SELECT_EDGE(0, tri->v[0], &vt[1], tri2)
1143 RELINK_EDGE(2, tri2)
1144
1145 tri1->v[0] = tri->v[2];
1146 tri1->v[1] = &vt[1];
1147 tri1->v[2] = &vt[0];
1148
1149 tri2->v[0] = &vt[1];
1150 tri2->v[1] = tri->v[2];
1151 tri2->v[2] = tri->v[0];
1152
1153 lineart_triangle_post(tri1, tri);
1154 lineart_triangle_post(tri2, tri);
1155
1156 v_count += 2;
1157 t_count += 2;
1158 }
1159 else if (in2) {
1160
1161 sub_v3_v3v3_db(span_v1, tri->v[2]->gloc, cam_pos);
1162 sub_v3_v3v3_db(span_v2, cam_pos, tri->v[0]->gloc);
1163 dot_v1 = dot_v3v3_db(span_v1, view_dir);
1164 dot_v2 = dot_v3v3_db(span_v2, view_dir);
1165 a = dot_v1 / (dot_v1 + dot_v2);
1166 interp_v3_v3v3_db(vt[0].gloc, tri->v[2]->gloc, tri->v[0]->gloc, a);
1167 mul_v4_m4v3_db(vt[0].fbcoord, m_view_projection, vt[0].gloc);
1168 vt[0].index = tri->v[2]->index;
1169
1170 sub_v3_v3v3_db(span_v1, tri->v[2]->gloc, cam_pos);
1171 sub_v3_v3v3_db(span_v2, cam_pos, tri->v[1]->gloc);
1172 dot_v1 = dot_v3v3_db(span_v1, view_dir);
1173 dot_v2 = dot_v3v3_db(span_v2, view_dir);
1174 a = dot_v1 / (dot_v1 + dot_v2);
1175 interp_v3_v3v3_db(vt[1].gloc, tri->v[2]->gloc, tri->v[1]->gloc, a);
1176 mul_v4_m4v3_db(vt[1].fbcoord, m_view_projection, vt[1].gloc);
1177 vt[1].index = tri->v[2]->index;
1178
1180 if (allow_boundaries) {
1183 }
1184 e->v1 = &vt[1];
1185 e->v2 = &vt[0];
1186
1187 e->t1 = tri1;
1188 e->object_ref = ob;
1189
1190 SELECT_EDGE(2, tri->v[0], &vt[0], tri1)
1191 SELECT_EDGE(1, tri->v[1], &vt[1], tri2)
1192 RELINK_EDGE(0, tri2)
1193
1194 tri1->v[0] = tri->v[0];
1195 tri1->v[1] = &vt[1];
1196 tri1->v[2] = &vt[0];
1197
1198 tri2->v[0] = &vt[1];
1199 tri2->v[1] = tri->v[0];
1200 tri2->v[2] = tri->v[1];
1201
1202 lineart_triangle_post(tri1, tri);
1203 lineart_triangle_post(tri2, tri);
1204
1205 v_count += 2;
1206 t_count += 2;
1207 }
1208 break;
1209 }
1210 *r_v_count = v_count;
1211 *r_e_count = e_count;
1212 *r_t_count = t_count;
1213
1214#undef INCREASE_EDGE
1215#undef SELECT_EDGE
1216#undef RELINK_EDGE
1217#undef REMOVE_TRIANGLE_EDGE
1218}
1219
1221{
1222 LineartTriangle *tri;
1223 LineartElementLinkNode *v_eln, *t_eln, *e_eln;
1224 double (*m_view_projection)[4] = ld->conf.view_projection;
1225 int i;
1226 int v_count = 0, t_count = 0, e_count = 0;
1227 Object *ob;
1228 bool allow_boundaries = ld->conf.allow_boundaries;
1229 double cam_pos[3];
1230 double clip_start = ld->conf.near_clip, clip_end = ld->conf.far_clip;
1231 double view_dir[3], clip_advance[3];
1232
1233 copy_v3_v3_db(view_dir, ld->conf.view_vector);
1234 copy_v3_v3_db(clip_advance, ld->conf.view_vector);
1235 copy_v3_v3_db(cam_pos, ld->conf.camera_pos);
1236
1237 if (clip_far) {
1238 /* Move starting point to end plane. */
1239 mul_v3db_db(clip_advance, -clip_end);
1240 add_v3_v3_db(cam_pos, clip_advance);
1241
1242 /* "reverse looking". */
1243 mul_v3db_db(view_dir, -1.0f);
1244 }
1245 else {
1246 /* Clip Near. */
1247 mul_v3db_db(clip_advance, -clip_start);
1248 add_v3_v3_db(cam_pos, clip_advance);
1249 }
1250
1254
1255 /* Additional memory space for storing generated points and triangles. */
1256#define LRT_CULL_ENSURE_MEMORY \
1257 if (v_count > 60) { \
1258 v_eln->element_count = v_count; \
1259 v_eln = lineart_memory_get_vert_space(ld); \
1260 v_count = 0; \
1261 } \
1262 if (t_count > 60) { \
1263 t_eln->element_count = t_count; \
1264 t_eln = lineart_memory_get_triangle_space(ld); \
1265 t_count = 0; \
1266 } \
1267 if (e_count > 60) { \
1268 e_eln->element_count = e_count; \
1269 e_eln = lineart_memory_get_edge_space(ld); \
1270 e_count = 0; \
1271 }
1272
1273#define LRT_CULL_DECIDE_INSIDE \
1274 /* These three represents points that are in the clipping range or not. */ \
1275 in0 = 0, in1 = 0, in2 = 0; \
1276 if (clip_far) { \
1277 /* Point outside far plane. */ \
1278 if (tri->v[0]->fbcoord[use_w] > clip_end) { \
1279 in0 = 1; \
1280 } \
1281 if (tri->v[1]->fbcoord[use_w] > clip_end) { \
1282 in1 = 1; \
1283 } \
1284 if (tri->v[2]->fbcoord[use_w] > clip_end) { \
1285 in2 = 1; \
1286 } \
1287 } \
1288 else { \
1289 /* Point inside near plane. */ \
1290 if (tri->v[0]->fbcoord[use_w] < clip_start) { \
1291 in0 = 1; \
1292 } \
1293 if (tri->v[1]->fbcoord[use_w] < clip_start) { \
1294 in1 = 1; \
1295 } \
1296 if (tri->v[2]->fbcoord[use_w] < clip_start) { \
1297 in2 = 1; \
1298 } \
1299 }
1300
1301 int use_w = 3;
1302 int in0 = 0, in1 = 0, in2 = 0;
1303
1304 if (!ld->conf.cam_is_persp) {
1305 clip_start = -1;
1306 clip_end = 1;
1307 use_w = 2;
1308 }
1309
1310 /* Then go through all the other triangles. */
1312 if (eln.flags & LRT_ELEMENT_IS_ADDITIONAL) {
1313 continue;
1314 }
1315 ob = static_cast<Object *>(eln.object_ref);
1316 for (i = 0; i < eln.element_count; i++) {
1317 /* Select the triangle in the array. */
1318 tri = static_cast<LineartTriangle *>(static_cast<void *>(
1319 (static_cast<uchar *>(eln.pointer)) + size_t(ld->sizeof_triangle) * i));
1320
1321 if (tri->flags & LRT_CULL_DISCARD) {
1322 continue;
1323 }
1324
1328 tri,
1329 in0,
1330 in1,
1331 in2,
1332 cam_pos,
1333 view_dir,
1334 allow_boundaries,
1335 m_view_projection,
1336 ob,
1337 &v_count,
1338 &e_count,
1339 &t_count,
1340 v_eln,
1341 e_eln,
1342 t_eln);
1343 }
1344 t_eln->element_count = t_count;
1345 v_eln->element_count = v_count;
1346 }
1347
1348#undef LRT_CULL_ENSURE_MEMORY
1349#undef LRT_CULL_DECIDE_INSIDE
1350}
1351
1353{
1354 while (
1355 LinkData *link = static_cast<LinkData *>(BLI_pophead(&ld->geom.triangle_adjacent_pointers)))
1356 {
1357 MEM_delete_void(link->data);
1358 }
1360 LineartTriangle *tri = static_cast<LineartTriangle *>(eln.pointer);
1361 int i;
1362 for (i = 0; i < eln.element_count; i++) {
1363 /* See definition of tri->intersecting_verts and the usage in
1364 * lineart_geometry_object_load() for detailed. */
1365 tri->intersecting_verts = nullptr;
1366 tri = reinterpret_cast<LineartTriangle *>((reinterpret_cast<uchar *>(tri)) +
1367 ld->sizeof_triangle);
1368 }
1369 }
1370}
1371
1373{
1375 LineartVert *vt = static_cast<LineartVert *>(eln.pointer);
1376 for (int i = 0; i < eln.element_count; i++) {
1377 if (ld->conf.cam_is_persp) {
1378 /* Do not divide Z, we use Z to back transform cut points in later chaining process. */
1379 vt[i].fbcoord[0] /= vt[i].fbcoord[3];
1380 vt[i].fbcoord[1] /= vt[i].fbcoord[3];
1381 /* Re-map z into (0-1) range, because we no longer need NDC (Normalized Device Coordinates)
1382 * at the moment.
1383 * The algorithm currently doesn't need Z for operation, we use W instead. If Z is needed
1384 * in the future, the line below correctly transforms it to view space coordinates. */
1385 // `vt[i].fbcoord[2] = -2 * vt[i].fbcoord[2] / (far - near) - (far + near) / (far - near);
1386 }
1387 /* Shifting is always needed. */
1388 vt[i].fbcoord[0] -= ld->conf.shift_x * 2;
1389 vt[i].fbcoord[1] -= ld->conf.shift_y * 2;
1390 }
1391 }
1392}
1393
1395{
1396 LineartEdge *e;
1397 const float bounds[4][2] = {{-1.0f, -1.0f}, {-1.0f, 1.0f}, {1.0f, -1.0f}, {1.0f, 1.0f}};
1398
1399#define LRT_VERT_OUT_OF_BOUND(v) \
1400 (v->fbcoord[0] < -1 || v->fbcoord[0] > 1 || v->fbcoord[1] < -1 || v->fbcoord[1] > 1)
1401
1403 e = static_cast<LineartEdge *>(eln.pointer);
1404 for (int i = 0; i < eln.element_count; i++) {
1405 if (!e[i].v1 || !e[i].v2) {
1407 continue;
1408 }
1409 const float2 vec1(e[i].v1->fbcoord), vec2(e[i].v2->fbcoord);
1410 if (LRT_VERT_OUT_OF_BOUND(e[i].v1) && LRT_VERT_OUT_OF_BOUND(e[i].v2)) {
1411 /* A line could still cross the image border even when both of the vertices are out of
1412 * bound. */
1413 if (isect_seg_seg_v2(bounds[0], bounds[1], vec1, vec2) == ISECT_LINE_LINE_NONE &&
1414 isect_seg_seg_v2(bounds[0], bounds[2], vec1, vec2) == ISECT_LINE_LINE_NONE &&
1415 isect_seg_seg_v2(bounds[1], bounds[3], vec1, vec2) == ISECT_LINE_LINE_NONE &&
1416 isect_seg_seg_v2(bounds[2], bounds[3], vec1, vec2) == ISECT_LINE_LINE_NONE)
1417 {
1419 }
1420 }
1421 }
1422 }
1423}
1424
1430
1437
1438static void lineart_mvert_transform_task(void *__restrict userdata,
1439 const int i,
1440 const TaskParallelTLS *__restrict /*tls*/)
1441{
1442 VertData *vert_task_data = static_cast<VertData *>(userdata);
1443 double co[4];
1444 LineartVert *v = &vert_task_data->v_arr[i];
1445 copy_v3db_v3fl(co, vert_task_data->positions[i]);
1446 mul_v3_m4v3_db(v->gloc, vert_task_data->model_view, co);
1447 mul_v4_m4v3_db(v->fbcoord, vert_task_data->model_view_proj, co);
1448 v->index = i;
1449}
1450
1459
1460#define LRT_MESH_EDGE_TYPES_COUNT 6
1461
1463{
1464 int count = 0;
1465 /* See eLineartEdgeFlag for details. */
1466 for (int i = 0; i < LRT_MESH_EDGE_TYPES_COUNT; i++) {
1467 if (eflag & LRT_MESH_EDGE_TYPES[i]) {
1468 count++;
1469 }
1470 }
1471 return count;
1472}
1473
1479 LineartTriangle *rt_array,
1480 int index)
1481{
1482 int8_t *b = reinterpret_cast<int8_t *>(rt_array);
1483 b += (size_t(index) * ld->sizeof_triangle);
1484 return reinterpret_cast<LineartTriangle *>(b);
1485}
1486
1509
1513
1514static void feat_data_sum_reduce(const void *__restrict /*userdata*/,
1515 void *__restrict chunk_join,
1516 void *__restrict chunk)
1517{
1518 EdgeFeatReduceData *feat_chunk_join = static_cast<EdgeFeatReduceData *>(chunk_join);
1519 EdgeFeatReduceData *feat_chunk = static_cast<EdgeFeatReduceData *>(chunk);
1520 feat_chunk_join->feat_edges += feat_chunk->feat_edges;
1521}
1522
1523static void lineart_identify_corner_tri_feature_edges(void *__restrict userdata,
1524 const int i,
1525 const TaskParallelTLS *__restrict tls)
1526{
1527 EdgeFeatData *e_feat_data = static_cast<EdgeFeatData *>(userdata);
1528 EdgeFeatReduceData *reduce_data = static_cast<EdgeFeatReduceData *>(tls->userdata_chunk);
1529 Object *ob_eval = e_feat_data->ob_eval;
1530 LineartEdgeNeighbor *edge_nabr = e_feat_data->edge_nabr;
1531 const Span<int3> corner_tris = e_feat_data->corner_tris;
1532 const Span<int> tri_faces = e_feat_data->tri_faces;
1533 const Span<int> material_indices = e_feat_data->material_indices;
1534
1535 uint16_t edge_flag_result = 0;
1536
1537 /* Because the edge neighbor array contains loop edge pairs, we only need to process the first
1538 * edge in the pair. Otherwise we would add the same edge that the loops represent twice. */
1539 if (i < edge_nabr[i].e) {
1540 return;
1541 }
1542
1543 bool face_mark_filtered = false;
1544 bool enable_face_mark = (e_feat_data->use_freestyle_face &&
1545 e_feat_data->ld->conf.filter_face_mark);
1546 bool only_contour = false;
1547 if (enable_face_mark) {
1548 bool ff1 = false;
1549 bool ff2 = false;
1550 if (const VArray<bool> &freestyle_face = e_feat_data->freestyle_face) {
1551 if (freestyle_face[tri_faces[i / 3]]) {
1552 ff1 = true;
1553 }
1554 }
1555 if (edge_nabr[i].e > -1 && e_feat_data->freestyle_face) {
1556 ff2 = e_feat_data->freestyle_face[tri_faces[edge_nabr[i].e / 3]];
1557 }
1558 else {
1559 /* Handle mesh boundary cases: We want mesh boundaries to respect
1560 * `filter_face_mark_boundaries` option the same way as face mark boundaries, and the code
1561 * path is simper when it's assuming both ff1 and ff2 not nullptr. */
1562 ff2 = ff1;
1563 }
1564 if (e_feat_data->ld->conf.filter_face_mark_boundaries ^
1565 e_feat_data->ld->conf.filter_face_mark_invert)
1566 {
1567 if (ff1 || ff2) {
1568 face_mark_filtered = true;
1569 }
1570 }
1571 else {
1572 if (ff1 && ff2 && (ff2 != ff1)) {
1573 face_mark_filtered = true;
1574 }
1575 }
1576 if (e_feat_data->ld->conf.filter_face_mark_invert) {
1577 face_mark_filtered = !face_mark_filtered;
1578 }
1579 if (!face_mark_filtered) {
1580 edge_nabr[i].flags = MOD_LINEART_EDGE_FLAG_INHIBIT;
1581 if (e_feat_data->ld->conf.filter_face_mark_keep_contour) {
1582 only_contour = true;
1583 }
1584 }
1585 }
1586
1587 if (enable_face_mark && !face_mark_filtered && !only_contour) {
1588 return;
1589 }
1590
1591 /* Mesh boundary */
1592 if (edge_nabr[i].e == -1) {
1593 edge_nabr[i].flags = MOD_LINEART_EDGE_FLAG_CONTOUR;
1594 reduce_data->feat_edges += 1;
1595 return;
1596 }
1597
1598 LineartTriangle *tri1, *tri2;
1599 LineartVert *vert;
1600 LineartData *ld = e_feat_data->ld;
1601
1602 int f1 = i / 3, f2 = edge_nabr[i].e / 3;
1603
1604 /* The mesh should already be triangulated now, so we can assume each face is a triangle. */
1605 tri1 = lineart_triangle_from_index(ld, e_feat_data->tri_array, f1);
1606 tri2 = lineart_triangle_from_index(ld, e_feat_data->tri_array, f2);
1607
1608 vert = &e_feat_data->v_array[edge_nabr[i].v1];
1609
1610 double view_vector_persp[3];
1611 double *view_vector = view_vector_persp;
1612 double dot_v1 = 0, dot_v2 = 0;
1613 double result;
1614 bool material_back_face = ((tri1->flags | tri2->flags) & LRT_TRIANGLE_MAT_BACK_FACE_CULLING);
1615
1616 if (ld->conf.use_contour || ld->conf.use_back_face_culling || material_back_face) {
1617 if (ld->conf.cam_is_persp) {
1618 sub_v3_v3v3_db(view_vector, ld->conf.camera_pos, vert->gloc);
1619 }
1620 else {
1621 view_vector = ld->conf.view_vector;
1622 }
1623
1624 dot_v1 = dot_v3v3_db(view_vector, tri1->gn);
1625 dot_v2 = dot_v3v3_db(view_vector, tri2->gn);
1626
1627 if ((result = dot_v1 * dot_v2) <= 0 && (dot_v1 + dot_v2)) {
1628 edge_flag_result |= MOD_LINEART_EDGE_FLAG_CONTOUR;
1629 }
1630
1631 if (ld->conf.use_back_face_culling) {
1632 if (dot_v1 < 0) {
1633 tri1->flags |= LRT_CULL_DISCARD;
1634 }
1635 if (dot_v2 < 0) {
1636 tri2->flags |= LRT_CULL_DISCARD;
1637 }
1638 }
1639 if (material_back_face) {
1640 if (tri1->flags & LRT_TRIANGLE_MAT_BACK_FACE_CULLING && dot_v1 < 0) {
1641 tri1->flags |= LRT_CULL_DISCARD;
1642 }
1643 if (tri2->flags & LRT_TRIANGLE_MAT_BACK_FACE_CULLING && dot_v2 < 0) {
1644 tri2->flags |= LRT_CULL_DISCARD;
1645 }
1646 }
1647 }
1648
1649 if (ld->conf.use_contour_secondary) {
1650 view_vector = view_vector_persp;
1651 if (ld->conf.cam_is_persp_secondary) {
1652 sub_v3_v3v3_db(view_vector, vert->gloc, ld->conf.camera_pos_secondary);
1653 }
1654 else {
1655 view_vector = ld->conf.view_vector_secondary;
1656 }
1657
1658 dot_v1 = dot_v3v3_db(view_vector, tri1->gn);
1659 dot_v2 = dot_v3v3_db(view_vector, tri2->gn);
1660
1661 if ((result = dot_v1 * dot_v2) <= 0 && (dot_v1 + dot_v2)) {
1662 edge_flag_result |= MOD_LINEART_EDGE_FLAG_CONTOUR_SECONDARY;
1663 }
1664 }
1665
1666 if (!only_contour) {
1667 if (ld->conf.use_crease) {
1668 bool do_crease = true;
1669 if (!ld->conf.force_crease && !e_feat_data->use_auto_smooth &&
1670 (!e_feat_data->sharp_faces[tri_faces[f1]]) && (!e_feat_data->sharp_faces[tri_faces[f2]]))
1671 {
1672 do_crease = false;
1673 }
1674 if (do_crease && (dot_v3v3_db(tri1->gn, tri2->gn) < e_feat_data->crease_threshold)) {
1675 edge_flag_result |= MOD_LINEART_EDGE_FLAG_CREASE;
1676 }
1677 }
1678
1679 int mat1 = material_indices.is_empty() ? 0 : material_indices[tri_faces[f1]];
1680 int mat2 = material_indices.is_empty() ? 0 : material_indices[tri_faces[f2]];
1681
1682 if (mat1 != mat2) {
1683 Material *m1 = BKE_object_material_get_eval(ob_eval, mat1 + 1);
1684 Material *m2 = BKE_object_material_get_eval(ob_eval, mat2 + 1);
1685 if (m1 && m2 &&
1686 ((m1->lineart.mat_occlusion == 0 && m2->lineart.mat_occlusion != 0) ||
1687 (m2->lineart.mat_occlusion == 0 && m1->lineart.mat_occlusion != 0)))
1688 {
1689 if (ld->conf.use_contour) {
1690 edge_flag_result |= MOD_LINEART_EDGE_FLAG_CONTOUR;
1691 }
1692 }
1693 if (ld->conf.use_material) {
1694 edge_flag_result |= MOD_LINEART_EDGE_FLAG_MATERIAL;
1695 }
1696 }
1697 }
1698 else { /* only_contour */
1699 if (!edge_flag_result) { /* Other edge types inhibited */
1700 return;
1701 }
1702 }
1703
1704 const int3 real_edges = corner_tri_get_real_edges(e_feat_data->edges,
1705 e_feat_data->corner_verts,
1706 e_feat_data->corner_edges,
1707 corner_tris[i / 3]);
1708
1709 if (real_edges[i % 3] >= 0) {
1710 if (ld->conf.use_crease && ld->conf.sharp_as_crease &&
1711 e_feat_data->sharp_edges[real_edges[i % 3]])
1712 {
1713 edge_flag_result |= MOD_LINEART_EDGE_FLAG_CREASE;
1714 }
1715
1716 if (ld->conf.use_edge_marks && e_feat_data->use_freestyle_edge) {
1717 if (e_feat_data->freestyle_edge[real_edges[i % 3]]) {
1718 edge_flag_result |= MOD_LINEART_EDGE_FLAG_EDGE_MARK;
1719 }
1720 }
1721 }
1722
1723 edge_nabr[i].flags = edge_flag_result;
1724
1725 if (edge_flag_result) {
1726 /* Only allocate for feature edge (instead of all edges) to save memory.
1727 * If allow duplicated edges, one edge gets added multiple times if it has multiple types.
1728 */
1729 reduce_data->feat_edges += e_feat_data->ld->conf.allow_duplicated_types ?
1730 lineart_edge_type_duplication_count(edge_flag_result) :
1731 1;
1732 }
1733}
1734
1739
1741{
1742 if (pe->next >= pe->max || !pe->max) {
1743 if (!pe->max) {
1744 pe->max = 1000;
1745 }
1746
1748 size_t(pe->max) * 2, "LineartPendingEdges array");
1749 if (pe->array) [[likely]] {
1750 memcpy(new_array, pe->array, sizeof(LineartEdge *) * pe->max);
1751 MEM_delete(pe->array);
1752 }
1753 pe->max *= 2;
1754 pe->array = new_array;
1755 }
1756 pe->array[pe->next] = e;
1757 pe->next++;
1758}
1763
1765{
1766 /* NOTE: For simplicity, this function doesn't actually do anything
1767 * if you already have data in #pe. */
1768
1769 if (pe->max || pe->array || count == 0) {
1770 return;
1771 }
1772
1773 pe->max = count;
1775 size_t(pe->max), "LineartPendingEdges array final");
1776 pe->array = new_array;
1777}
1778
1780{
1781 /* In case of line art "occlusion only" or contour not enabled, it's possible for an object to
1782 * not produce any feature lines. */
1783 if (!obi->pending_edges.array) {
1784 return;
1785 }
1786 memcpy(&pe->array[pe->next],
1787 obi->pending_edges.array,
1788 sizeof(LineartEdge *) * obi->pending_edges.next);
1789 MEM_delete(obi->pending_edges.array);
1790 pe->next += obi->pending_edges.next;
1791}
1792
1794 LineartTriangleAdjacent *tri_adj,
1795 LineartEdge *e)
1796{
1797 if (lineart_edge_match(tri, e, 0, 1)) {
1798 tri_adj->e[0] = e;
1799 }
1800 else if (lineart_edge_match(tri, e, 1, 2)) {
1801 tri_adj->e[1] = e;
1802 }
1803 else if (lineart_edge_match(tri, e, 2, 0)) {
1804 tri_adj->e[2] = e;
1805 }
1806}
1807
1822
1823static void lineart_load_tri_task(void *__restrict userdata,
1824 const int i,
1825 const TaskParallelTLS *__restrict /*tls*/)
1826{
1827 TriData *tri_task_data = static_cast<TriData *>(userdata);
1828 LineartObjectInfo *ob_info = tri_task_data->ob_info;
1829 const Span<float3> positions = tri_task_data->positions;
1830 const Span<int> corner_verts = tri_task_data->corner_verts;
1831 const int3 &corner_tri = tri_task_data->corner_tris[i];
1832 const int face_i = tri_task_data->tri_faces[i];
1833 const Span<int> material_indices = tri_task_data->material_indices;
1834
1835 LineartVert *vert_arr = tri_task_data->vert_arr;
1836 LineartTriangle *tri = tri_task_data->tri_arr;
1837
1838 tri = reinterpret_cast<LineartTriangle *>((reinterpret_cast<size_t>(tri)) +
1839 size_t(tri_task_data->lineart_triangle_size) * i);
1840
1841 int v1 = corner_verts[corner_tri[0]];
1842 int v2 = corner_verts[corner_tri[1]];
1843 int v3 = corner_verts[corner_tri[2]];
1844
1845 tri->v[0] = &vert_arr[v1];
1846 tri->v[1] = &vert_arr[v2];
1847 tri->v[2] = &vert_arr[v3];
1848
1849 /* Material mask bits and occlusion effectiveness assignment. */
1851 ob_info->original_ob_eval, material_indices.is_empty() ? 1 : material_indices[face_i] + 1);
1852 tri->material_mask_bits |= ((mat && (mat->lineart.flags & LRT_MATERIAL_MASK_ENABLED)) ?
1853 mat->lineart.material_mask_bits :
1854 0);
1855 tri->mat_occlusion |= (mat ? mat->lineart.mat_occlusion : 1);
1856 tri->intersection_priority = ((mat && (mat->lineart.flags &
1858 mat->lineart.intersection_priority :
1859 ob_info->intersection_priority);
1860 tri->flags |= (mat && (mat->blend_flag & MA_BL_CULL_BACKFACE)) ?
1862 0;
1863
1865
1866 tri->target_reference = (ob_info->obindex | (i & LRT_OBINDEX_LOWER));
1867
1868 double gn[3];
1869 float no[3];
1870 normal_tri_v3(no, positions[v1], positions[v2], positions[v3]);
1871 copy_v3db_v3fl(gn, no);
1872 mul_v3_mat3_m4v3_db(tri->gn, ob_info->normal, gn);
1873 normalize_v3_db(tri->gn);
1874
1875 if (ob_info->usage == OBJECT_LRT_INTERSECTION_ONLY) {
1877 }
1878 else if (ob_info->usage == OBJECT_LRT_FORCE_INTERSECTION) {
1880 }
1883 }
1884
1885 if (!tri_task_data->face_marks.is_empty()) {
1886 const bool has_mark = tri_task_data->face_marks[face_i];
1887 const bool filtered = tri_task_data->invert_face_marks ? has_mark : (!has_mark);
1888 if (filtered) {
1890 }
1891 }
1892
1893 /* Re-use this field to refer to adjacent info, will be cleared after culling stage. */
1894 tri->intersecting_verts = static_cast<LinkNode *>(
1895 static_cast<void *>(&tri_task_data->tri_adj[i]));
1896}
1904
1905static void lineart_edge_neighbor_init_task(void *__restrict userdata,
1906 const int i,
1907 const TaskParallelTLS *__restrict /*tls*/)
1908{
1909 EdgeNeighborData *en_data = static_cast<EdgeNeighborData *>(userdata);
1910 LineartAdjacentEdge *adj_e = &en_data->adj_e[i];
1911 const int3 &tri = en_data->corner_tris[i / 3];
1912 LineartEdgeNeighbor *edge_nabr = &en_data->edge_nabr[i];
1913 const Span<int> corner_verts = en_data->corner_verts;
1914
1915 adj_e->e = i;
1916 adj_e->v1 = corner_verts[tri[i % 3]];
1917 adj_e->v2 = corner_verts[tri[(i + 1) % 3]];
1918 if (adj_e->v1 > adj_e->v2) {
1919 std::swap(adj_e->v1, adj_e->v2);
1920 }
1921 edge_nabr->e = -1;
1922
1923 edge_nabr->v1 = adj_e->v1;
1924 edge_nabr->v2 = adj_e->v2;
1925 edge_nabr->flags = 0;
1926}
1927
1929{
1930 parallel_sort(ai, ai + length, [](const LineartAdjacentEdge &p1, const LineartAdjacentEdge &p2) {
1931 int a = p1.v1 - p2.v1;
1932 int b = p1.v2 - p2.v2;
1933 /* `parallel_sort()` requires `cmp()` to return true when the first element needs to appear
1934 * before the second element in the sorted array, false otherwise (strict weak ordering),
1935 * see https://en.cppreference.com/w/cpp/named_req/Compare. */
1936 if (a < 0) {
1937 return true;
1938 }
1939 if (a > 0) {
1940 return false;
1941 }
1942 return b < 0;
1943 });
1944}
1945
1947{
1948 /* Because the mesh is triangulated, so `mesh->edges_num` should be reliable? */
1950 size_t(total_edges), "LineartAdjacentEdge arr");
1952 size_t(total_edges), "LineartEdgeNeighbor arr");
1953
1954 TaskParallelSettings en_settings;
1956 /* Set the minimum amount of edges a thread has to process. */
1957 en_settings.min_iter_per_thread = 50000;
1958
1959 EdgeNeighborData en_data;
1960 en_data.adj_e = adj_e;
1961 en_data.edge_nabr = edge_nabr;
1962 en_data.corner_verts = mesh->corner_verts();
1963 en_data.corner_tris = mesh->corner_tris();
1964 en_data.tri_faces = mesh->corner_tri_faces();
1965
1966 BLI_task_parallel_range(0, total_edges, &en_data, lineart_edge_neighbor_init_task, &en_settings);
1967
1968 lineart_sort_adjacent_items(adj_e, total_edges);
1969
1970 for (int i = 0; i < total_edges - 1; i++) {
1971 if (adj_e[i].v1 == adj_e[i + 1].v1 && adj_e[i].v2 == adj_e[i + 1].v2) {
1972 edge_nabr[adj_e[i].e].e = adj_e[i + 1].e;
1973 edge_nabr[adj_e[i + 1].e].e = adj_e[i].e;
1974 }
1975 }
1976
1977 MEM_delete(adj_e);
1978
1979 return edge_nabr;
1980}
1981
1983 LineartData *la_data,
1984 ListBaseT<LineartElementLinkNode> *shadow_elns)
1985{
1986 Mesh *mesh = ob_info->original_me;
1987 if (!mesh->edges_num) {
1988 return;
1989 }
1990
1991 /* Triangulate. */
1992 const Span<int3> corner_tris = mesh->corner_tris();
1993 const AttributeAccessor attributes = mesh->attributes();
1994 const VArraySpan material_indices = *attributes.lookup<int>("material_index", AttrDomain::Face);
1995 const VArraySpan face_marks = *attributes.lookup<bool>("freestyle_face", AttrDomain::Face);
1996
1997 /* If we allow duplicated edges, one edge should get added multiple times if is has been
1998 * classified as more than one edge type. This is so we can create multiple different line type
1999 * chains containing the same edge. */
2000 LineartVert *la_v_arr = static_cast<LineartVert *>(lineart_mem_acquire_thread(
2001 &la_data->render_data_pool, sizeof(LineartVert) * mesh->verts_num));
2002 LineartTriangle *la_tri_arr = static_cast<LineartTriangle *>(lineart_mem_acquire_thread(
2003 &la_data->render_data_pool, corner_tris.size() * la_data->sizeof_triangle));
2004
2005 Object *orig_ob = ob_info->original_ob;
2006
2007 BLI_spin_lock(&la_data->lock_task);
2008 LineartElementLinkNode *elem_link_node = static_cast<LineartElementLinkNode *>(
2010 &la_data->render_data_pool,
2011 la_v_arr,
2012 sizeof(LineartElementLinkNode)));
2013 BLI_spin_unlock(&la_data->lock_task);
2014
2015 elem_link_node->obindex = ob_info->obindex;
2016 elem_link_node->element_count = mesh->verts_num;
2017 elem_link_node->object_ref = orig_ob;
2018 ob_info->v_eln = elem_link_node;
2019
2020 bool use_auto_smooth = false;
2021 float crease_angle = 0;
2022 if (orig_ob->lineart.flags & OBJECT_LRT_OWN_CREASE) {
2023 crease_angle = cosf(M_PI - orig_ob->lineart.crease_threshold);
2024 }
2025 else {
2026 crease_angle = la_data->conf.crease_threshold;
2027 }
2028
2029 /* FIXME(Yiming): Hack for getting clean 3D text, the seam that extruded text object creates
2030 * erroneous detection on creases. Future configuration should allow options. */
2031 if (orig_ob->type == OB_FONT) {
2032 elem_link_node->flags |= LRT_ELEMENT_BORDER_ONLY;
2033 }
2034
2035 BLI_spin_lock(&la_data->lock_task);
2036 elem_link_node = static_cast<LineartElementLinkNode *>(
2038 &la_data->render_data_pool,
2039 la_tri_arr,
2040 sizeof(LineartElementLinkNode)));
2041 BLI_spin_unlock(&la_data->lock_task);
2042
2043 int usage = ob_info->usage;
2044
2045 elem_link_node->element_count = corner_tris.size();
2046 elem_link_node->object_ref = orig_ob;
2047 elem_link_node->flags = eLineArtElementNodeFlag(
2048 elem_link_node->flags |
2050
2051 /* Note this memory is not from pool, will be deleted after culling. */
2053 size_t(corner_tris.size()), "LineartTriangleAdjacent");
2054 /* Link is minimal so we use pool anyway. */
2055 BLI_spin_lock(&la_data->lock_task);
2057 &la_data->geom.triangle_adjacent_pointers, &la_data->render_data_pool, tri_adj);
2058 BLI_spin_unlock(&la_data->lock_task);
2059
2060 /* Convert all vertices to lineart verts. */
2061 TaskParallelSettings vert_settings;
2063 /* Set the minimum amount of verts a thread has to process. */
2064 vert_settings.min_iter_per_thread = 4000;
2065
2066 VertData vert_data;
2067 vert_data.positions = mesh->vert_positions();
2068 vert_data.v_arr = la_v_arr;
2069 vert_data.model_view = ob_info->model_view;
2070 vert_data.model_view_proj = ob_info->model_view_proj;
2071
2073 0, mesh->verts_num, &vert_data, lineart_mvert_transform_task, &vert_settings);
2074
2075 /* Convert all mesh triangles into lineart triangles.
2076 * Also create an edge map to get connectivity between edges and triangles. */
2077 TaskParallelSettings tri_settings;
2079 /* Set the minimum amount of triangles a thread has to process. */
2080 tri_settings.min_iter_per_thread = 4000;
2081
2082 TriData tri_data;
2083 tri_data.ob_info = ob_info;
2084 tri_data.positions = mesh->vert_positions();
2085 tri_data.corner_tris = corner_tris;
2086 tri_data.tri_faces = mesh->corner_tri_faces();
2087 tri_data.corner_verts = mesh->corner_verts();
2088 tri_data.material_indices = material_indices;
2089 tri_data.vert_arr = la_v_arr;
2090 tri_data.tri_arr = la_tri_arr;
2091 tri_data.lineart_triangle_size = la_data->sizeof_triangle;
2092 tri_data.tri_adj = tri_adj;
2093 if (la_data->conf.filter_face_mark) {
2094 tri_data.face_marks = face_marks;
2096 }
2097
2098 uint32_t total_edges = corner_tris.size() * 3;
2099
2100 BLI_task_parallel_range(0, corner_tris.size(), &tri_data, lineart_load_tri_task, &tri_settings);
2101
2102 /* Check for contour lines in the mesh.
2103 * IE check if the triangle edges lies in area where the triangles go from front facing to back
2104 * facing.
2105 */
2106 EdgeFeatReduceData edge_reduce = {0};
2107 TaskParallelSettings edge_feat_settings;
2108 BLI_parallel_range_settings_defaults(&edge_feat_settings);
2109 /* Set the minimum amount of edges a thread has to process. */
2110 edge_feat_settings.min_iter_per_thread = 4000;
2111 edge_feat_settings.userdata_chunk = &edge_reduce;
2112 edge_feat_settings.userdata_chunk_size = sizeof(EdgeFeatReduceData);
2113 edge_feat_settings.func_reduce = feat_data_sum_reduce;
2114
2115 const VArray<bool> sharp_edges = *attributes.lookup_or_default<bool>(
2116 "sharp_edge", AttrDomain::Edge, false);
2117 const VArray<bool> sharp_faces = *attributes.lookup_or_default<bool>(
2118 "sharp_face", AttrDomain::Face, false);
2119
2120 EdgeFeatData edge_feat_data = {nullptr};
2121 edge_feat_data.ld = la_data;
2122 edge_feat_data.mesh = mesh;
2123 edge_feat_data.ob_eval = ob_info->original_ob_eval;
2124 edge_feat_data.material_indices = material_indices;
2125 edge_feat_data.edges = mesh->edges();
2126 edge_feat_data.corner_verts = mesh->corner_verts();
2127 edge_feat_data.corner_edges = mesh->corner_edges();
2128 edge_feat_data.corner_tris = corner_tris;
2129 edge_feat_data.tri_faces = mesh->corner_tri_faces();
2130 edge_feat_data.sharp_edges = sharp_edges;
2131 edge_feat_data.sharp_faces = sharp_faces;
2132 edge_feat_data.edge_nabr = lineart_build_edge_neighbor(mesh, total_edges);
2133 edge_feat_data.tri_array = la_tri_arr;
2134 edge_feat_data.v_array = la_v_arr;
2135 edge_feat_data.crease_threshold = crease_angle;
2136 edge_feat_data.use_auto_smooth = use_auto_smooth;
2137 edge_feat_data.freestyle_face = *attributes.lookup<bool>("freestyle_face", AttrDomain::Face);
2138 edge_feat_data.freestyle_edge = *attributes.lookup<bool>("freestyle_edge", AttrDomain::Edge);
2139 edge_feat_data.use_freestyle_face = bool(edge_feat_data.freestyle_face);
2140 edge_feat_data.use_freestyle_edge = bool(edge_feat_data.freestyle_edge);
2141
2143 total_edges,
2144 &edge_feat_data,
2146 &edge_feat_settings);
2147
2148 LooseEdgeData loose_data = {0};
2149
2150 if (la_data->conf.use_loose) {
2151 /* Only identifying floating edges at this point because other edges has been taken care of
2152 * inside #lineart_identify_corner_tri_feature_edges function. */
2153 const IndexMask &loose_edges = mesh->loose_edges();
2154 loose_data.loose_array = MEM_new_array_uninitialized<int>(loose_edges.size(), __func__);
2155 loose_data.loose_count = loose_edges.size();
2156 loose_edges.to_indices(MutableSpan(loose_data.loose_array, loose_data.loose_count));
2157 }
2158
2159 int allocate_la_e = edge_reduce.feat_edges + loose_data.loose_count;
2160
2161 LineartEdge *la_edge_arr = static_cast<LineartEdge *>(
2162 lineart_mem_acquire_thread(la_data->edge_data_pool, sizeof(LineartEdge) * allocate_la_e));
2164 la_data->edge_data_pool, sizeof(LineartEdgeSegment) * allocate_la_e));
2165 BLI_spin_lock(&la_data->lock_task);
2166 elem_link_node = static_cast<LineartElementLinkNode *>(
2168 la_data->edge_data_pool,
2169 la_edge_arr,
2170 sizeof(LineartElementLinkNode)));
2171 BLI_spin_unlock(&la_data->lock_task);
2172 elem_link_node->element_count = allocate_la_e;
2173 elem_link_node->object_ref = orig_ob;
2174 elem_link_node->obindex = ob_info->obindex;
2175
2176 LineartElementLinkNode *shadow_eln = nullptr;
2177 if (shadow_elns) {
2178 shadow_eln = lineart_find_matching_eln(shadow_elns, ob_info->obindex);
2179 }
2180
2181 /* Start of the edge/seg arr */
2182 LineartEdge *la_edge;
2183 LineartEdgeSegment *la_seg;
2184 la_edge = la_edge_arr;
2185 la_seg = la_seg_arr;
2186
2187 for (int i = 0; i < total_edges; i++) {
2188 LineartEdgeNeighbor *edge_nabr = &edge_feat_data.edge_nabr[i];
2189
2190 if (i < edge_nabr->e) {
2191 continue;
2192 }
2193
2194 /* Not a feature line, so we skip. */
2195 if (edge_nabr->flags == 0) {
2196 continue;
2197 }
2198
2199 LineartEdge *edge_added = nullptr;
2200
2201 /* See eLineartEdgeFlag for details. */
2202 for (int flag_bit = 0; flag_bit < LRT_MESH_EDGE_TYPES_COUNT; flag_bit++) {
2203 int use_type = LRT_MESH_EDGE_TYPES[flag_bit];
2204 if (!(use_type & edge_nabr->flags)) {
2205 continue;
2206 }
2207
2208 la_edge->v1 = &la_v_arr[edge_nabr->v1];
2209 la_edge->v2 = &la_v_arr[edge_nabr->v2];
2210 int findex = i / 3;
2211 la_edge->t1 = lineart_triangle_from_index(la_data, la_tri_arr, findex);
2212 if (!edge_added) {
2213 lineart_triangle_adjacent_assign(la_edge->t1, &tri_adj[findex], la_edge);
2214 }
2215 if (edge_nabr->e != -1) {
2216 findex = edge_nabr->e / 3;
2217 la_edge->t2 = lineart_triangle_from_index(la_data, la_tri_arr, findex);
2218 if (!edge_added) {
2219 lineart_triangle_adjacent_assign(la_edge->t2, &tri_adj[findex], la_edge);
2220 }
2221 }
2222 la_edge->flags = use_type;
2223 la_edge->object_ref = orig_ob;
2224 la_edge->edge_identifier = LRT_EDGE_IDENTIFIER(ob_info, la_edge);
2225 BLI_addtail(&la_edge->segments, la_seg);
2226
2227 if (shadow_eln) {
2228 /* TODO(Yiming): It's gonna be faster to do this operation after second stage occlusion if
2229 * we only need visible segments to have shadow info, however that way we lose information
2230 * on "shadow behind transparency window" type of region. */
2231 LineartEdge *shadow_e = lineart_find_matching_edge(shadow_eln, la_edge->edge_identifier);
2232 if (shadow_e) {
2233 lineart_register_shadow_cuts(la_data, la_edge, shadow_e);
2234 }
2235 }
2236
2237 if (ELEM(usage,
2242 {
2243 lineart_add_edge_to_array_thread(ob_info, la_edge);
2244 }
2245
2246 if (edge_added) {
2248 }
2249
2250 edge_added = la_edge;
2251
2252 la_edge++;
2253 la_seg++;
2254
2255 if (!la_data->conf.allow_duplicated_types) {
2256 break;
2257 }
2258 }
2259 }
2260
2261 if (loose_data.loose_array) {
2262 const Span<int2> edges = mesh->edges();
2263 for (int i = 0; i < loose_data.loose_count; i++) {
2264 const int2 &edge = edges[loose_data.loose_array[i]];
2265 la_edge->v1 = &la_v_arr[edge[0]];
2266 la_edge->v2 = &la_v_arr[edge[1]];
2268 la_edge->object_ref = orig_ob;
2269 la_edge->edge_identifier = LRT_EDGE_IDENTIFIER(ob_info, la_edge);
2270 BLI_addtail(&la_edge->segments, la_seg);
2271 if (ELEM(usage,
2276 {
2277 lineart_add_edge_to_array_thread(ob_info, la_edge);
2278 if (shadow_eln) {
2279 LineartEdge *shadow_e = lineart_find_matching_edge(shadow_eln, la_edge->edge_identifier);
2280 if (shadow_e) {
2281 lineart_register_shadow_cuts(la_data, la_edge, shadow_e);
2282 }
2283 }
2284 }
2285 la_edge++;
2286 la_seg++;
2287 }
2288 MEM_SAFE_DELETE(loose_data.loose_array);
2289 }
2290
2291 MEM_delete(edge_feat_data.edge_nabr);
2292
2293 if (ob_info->free_use_mesh) {
2294 BKE_id_free(nullptr, mesh);
2295 }
2296}
2297
2298static void lineart_object_load_worker(TaskPool *__restrict /*pool*/,
2300{
2301 for (LineartObjectInfo *obi = olti->pending; obi; obi = obi->next) {
2302 lineart_geometry_object_load(obi, olti->ld, olti->shadow_elns);
2303 }
2304}
2305
2307{
2308 for (CollectionChild &cc : c->children) {
2310 if (result) {
2311 return result;
2312 }
2313 }
2314
2315 /* We already did "depth-priority search" above, so if no child collection is overriding the
2316 * value, we use the parent's value. */
2317 if (BKE_collection_has_object_recursive_instanced(c, id_cast<Object *>(ob->id.orig_id))) {
2319 return c->lineart_intersection_mask;
2320 }
2321 }
2322
2323 return 0;
2324}
2325
2327{
2329 return ob->lineart.intersection_priority;
2330 }
2331
2332 for (CollectionChild &cc : c->children) {
2334 if (result) {
2335 return result;
2336 }
2337 }
2338
2339 /* We already did "depth-priority search" above, so if no child collection is overriding the
2340 * value, we use the parent's value. */
2341 if (BKE_collection_has_object_recursive_instanced(c, id_cast<Object *>(ob->id.orig_id))) {
2344 }
2345 }
2346 return 0;
2347}
2348
2353static int lineart_usage_check(Collection *c, Object *ob, bool is_render)
2354{
2355
2356 if (!c) {
2357 return OBJECT_LRT_INHERIT;
2358 }
2359
2360 int object_has_special_usage = (ob->lineart.usage != OBJECT_LRT_INHERIT);
2361
2362 if (object_has_special_usage) {
2363 return ob->lineart.usage;
2364 }
2365
2366 if (c->gobject.first_) {
2367 if (BKE_collection_has_object(c, id_cast<Object *>(ob->id.orig_id))) {
2368 if ((is_render && (c->flag & COLLECTION_HIDE_RENDER)) ||
2369 ((!is_render) && (c->flag & COLLECTION_HIDE_VIEWPORT)))
2370 {
2371 return OBJECT_LRT_EXCLUDE;
2372 }
2373 if (ob->lineart.usage == OBJECT_LRT_INHERIT) {
2374 switch (c->lineart_usage) {
2378 return OBJECT_LRT_EXCLUDE;
2386 break;
2387 }
2388 return OBJECT_LRT_INHERIT;
2389 }
2390 return ob->lineart.usage;
2391 }
2392 }
2393
2394 for (CollectionChild &cc : c->children) {
2395 int result = lineart_usage_check(cc.collection, ob, is_render);
2396 if (result > OBJECT_LRT_INHERIT) {
2397 return result;
2398 }
2399 }
2400
2401 return OBJECT_LRT_INHERIT;
2402}
2403
2405 LineartObjectInfo *obi,
2406 int thread_count,
2407 int this_face_count)
2408{
2409 LineartObjectLoadTaskInfo *use_olti = olti_list;
2410 uint64_t min_face = use_olti->total_faces;
2411 for (int i = 0; i < thread_count; i++) {
2412 if (olti_list[i].total_faces < min_face) {
2413 min_face = olti_list[i].total_faces;
2414 use_olti = &olti_list[i];
2415 }
2416 }
2417
2418 use_olti->total_faces += this_face_count;
2419 obi->next = use_olti->pending;
2420 use_olti->pending = obi;
2421}
2422
2423static bool lineart_geometry_check_visible(double model_view_proj[4][4],
2424 double shift_x,
2425 double shift_y,
2426 Mesh *use_mesh)
2427{
2428 if (!use_mesh) {
2429 return false;
2430 }
2431 const std::optional<Bounds<float3>> bounds = use_mesh->bounds_min_max();
2432 if (!bounds.has_value()) {
2433 return false;
2434 }
2435 const std::array<float3, 8> corners = bounds::corners(*bounds);
2436
2437 double co[8][4];
2438 double tmp[3];
2439 for (int i = 0; i < 8; i++) {
2440 copy_v3db_v3fl(co[i], corners[i]);
2441 copy_v3_v3_db(tmp, co[i]);
2442 mul_v4_m4v3_db(co[i], model_view_proj, tmp);
2443 co[i][0] -= shift_x * 2 * co[i][3];
2444 co[i][1] -= shift_y * 2 * co[i][3];
2445 }
2446
2447 bool cond[6] = {true, true, true, true, true, true};
2448 /* Because for a point to be inside clip space, it must satisfy `-Wc <= XYCc <= Wc`, here if
2449 * all verts falls to the same side of the clip space border, we know it's outside view. */
2450 for (int i = 0; i < 8; i++) {
2451 cond[0] &= (co[i][0] < -co[i][3]);
2452 cond[1] &= (co[i][0] > co[i][3]);
2453 cond[2] &= (co[i][1] < -co[i][3]);
2454 cond[3] &= (co[i][1] > co[i][3]);
2455 cond[4] &= (co[i][2] < -co[i][3]);
2456 cond[5] &= (co[i][2] > co[i][3]);
2457 }
2458 for (int i = 0; i < 6; i++) {
2459 if (cond[i]) {
2460 return false;
2461 }
2462 }
2463 return true;
2464}
2465
2467 Depsgraph *depsgraph,
2468 Scene *scene,
2469 Object *ob,
2470 Object *ref_ob,
2471 const float use_mat[4][4],
2472 bool is_render,
2474 int thread_count,
2475 int obindex)
2476{
2477 LineartObjectInfo *obi = static_cast<LineartObjectInfo *>(
2479 obi->usage = lineart_usage_check(scene->master_collection, ob, is_render);
2482 Mesh *use_mesh;
2483
2484 if (obi->usage == OBJECT_LRT_EXCLUDE) {
2485 return;
2486 }
2487
2488 obi->obindex = obindex << LRT_OBINDEX_SHIFT;
2489
2490 /* Prepare the matrix used for transforming this specific object (instance). This has to be
2491 * done before mesh bound-box check because the function needs that. */
2493 mul_m4db_m4db_m4fl(obi->model_view, ld->conf.view, use_mat);
2494
2496 return;
2497 }
2498 if (ob->type == OB_MESH) {
2499 use_mesh = BKE_object_get_evaluated_mesh(ob);
2500 if ((!use_mesh) || use_mesh->runtime->edit_mesh) {
2501 /* If the object is being edited, then the mesh is not evaluated fully into the final
2502 * result, do not load them. This could be caused by incorrect evaluation order due to
2503 * the way line art uses depsgraph.See #102612 for explanation of this workaround. */
2504 return;
2505 }
2506 }
2507 else {
2508 use_mesh = BKE_mesh_new_from_object(depsgraph, ob, true, true, true);
2509 }
2510
2511 /* In case we still can not get any mesh geometry data from the object, same as above. */
2512 if (!use_mesh) {
2513 return;
2514 }
2515
2517 obi->model_view_proj, ld->conf.shift_x, ld->conf.shift_y, use_mesh))
2518 {
2519 return;
2520 }
2521
2522 if (ob->type != OB_MESH) {
2523 obi->free_use_mesh = true;
2524 }
2525
2526 /* Make normal matrix. */
2527 float imat[4][4];
2528 invert_m4_m4(imat, use_mat);
2529 transpose_m4(imat);
2530 copy_m4d_m4(obi->normal, imat);
2531
2532 obi->original_me = use_mesh;
2533 obi->original_ob = (ref_ob->id.orig_id ? id_cast<Object *>(ref_ob->id.orig_id) : ref_ob);
2534 obi->original_ob_eval = DEG_get_evaluated(depsgraph, obi->original_ob);
2535 lineart_geometry_load_assign_thread(olti, obi, thread_count, use_mesh->faces_num);
2536}
2537
2538void lineart_main_load_geometries(Depsgraph *depsgraph,
2539 Scene *scene,
2540 Object *camera /* Still use camera arg for convenience. */,
2541 LineartData *ld,
2542 bool allow_duplicates,
2543 bool do_shadow_casting,
2544 ListBaseT<LineartElementLinkNode> *shadow_elns,
2545 Set<const Object *> *included_objects)
2546{
2547 double proj[4][4], view[4][4], result[4][4];
2548 float inv[4][4];
2549
2550 if (!do_shadow_casting) {
2551 Camera *cam = id_cast<Camera *>(camera->data);
2552 float sensor = BKE_camera_sensor_size(cam->sensor_fit, cam->sensor_x, cam->sensor_y);
2553 int fit = BKE_camera_sensor_fit(cam->sensor_fit, ld->w, ld->h);
2554 double asp = (double(ld->w) / double(ld->h));
2555 if (ELEM(cam->type, CAM_PERSP, CAM_PANO, CAM_CUSTOM)) {
2556 if (fit == CAMERA_SENSOR_FIT_VERT && asp > 1) {
2557 sensor *= asp;
2558 }
2559 if (fit == CAMERA_SENSOR_FIT_HOR && asp < 1) {
2560 sensor /= asp;
2561 }
2562 const double fov = focallength_to_fov(cam->lens / (1 + ld->conf.overscan), sensor);
2563 lineart_matrix_perspective_44d(proj, fov, asp, cam->clip_start, cam->clip_end);
2564 }
2565 else if (cam->type == CAM_ORTHO) {
2566 double horizontal = cam->ortho_scale / 2;
2567 double vertical = horizontal;
2568 if (fit == CAMERA_SENSOR_FIT_VERT) {
2569 horizontal *= asp;
2570 }
2571 else {
2572 vertical /= asp;
2573 }
2575 proj, -horizontal, horizontal, -vertical, vertical, cam->clip_start, cam->clip_end);
2576 }
2577 else {
2578 BLI_assert(!"Unsupported camera type in lineart_main_load_geometries");
2579 unit_m4_db(proj);
2580 }
2581
2582 invert_m4_m4(inv, ld->conf.cam_obmat);
2583 mul_m4db_m4db_m4fl(result, proj, inv);
2584 copy_m4_m4_db(proj, result);
2586
2587 unit_m4_db(view);
2588 copy_m4_m4_db(ld->conf.view, view);
2589 }
2590
2591 ld->geom.triangle_buffer_pointers.clear_no_delete();
2592 ld->geom.vertex_buffer_pointers.clear_no_delete();
2593
2594 double t_start;
2595 if (G.debug_value == 4000) {
2596 t_start = BLI_time_now_seconds();
2597 }
2598
2599 int thread_count = ld->thread_count;
2600 int bound_box_discard_count = 0;
2601 int obindex = 0;
2602
2603 /* This memory is in render buffer memory pool. So we don't need to free those after loading. */
2605 &ld->render_data_pool, sizeof(LineartObjectLoadTaskInfo) * thread_count));
2606
2607 eEvaluationMode eval_mode = DEG_get_mode(depsgraph);
2608 bool is_render = eval_mode == DAG_EVAL_RENDER;
2609
2612
2613 /* Instance duplicated & particles. */
2614 if (allow_duplicates) {
2616 }
2617
2618 DEGObjectIterSettings deg_iter_settings = {nullptr};
2619 deg_iter_settings.depsgraph = depsgraph;
2620 deg_iter_settings.flags = flags;
2621 deg_iter_settings.included_objects = included_objects;
2622
2623 DEG_OBJECT_ITER_BEGIN (&deg_iter_settings, ob) {
2624
2625 obindex++;
2626
2627 Object *eval_ob = DEG_get_evaluated(depsgraph, ob);
2628
2629 if (!eval_ob) {
2630 continue;
2631 }
2632
2633 /* DEG_OBJECT_ITER_BEGIN will include the instanced mesh of these curve object types, so don't
2634 * load them twice. */
2635 if (allow_duplicates && ELEM(ob->type, OB_CURVES_LEGACY, OB_FONT, OB_SURF, OB_CURVES)) {
2636 continue;
2637 }
2638
2639 if (BKE_object_visibility(eval_ob, eval_mode) & OB_VISIBLE_SELF) {
2641 depsgraph,
2642 scene,
2643 eval_ob,
2644 eval_ob,
2645 eval_ob->object_to_world().ptr(),
2646 is_render,
2647 olti,
2648 thread_count,
2649 obindex);
2650 }
2651 }
2653
2655
2656 if (G.debug_value == 4000) {
2657 printf("thread count: %d\n", thread_count);
2658 }
2659 for (int i = 0; i < thread_count; i++) {
2660 olti[i].ld = ld;
2661 olti[i].shadow_elns = shadow_elns;
2662 olti[i].thread_id = i;
2665 &olti[i],
2666 false,
2667 nullptr);
2668 }
2671
2672 /* The step below is to serialize vertex index in the whole scene, so
2673 * lineart_triangle_share_edge() can work properly from the lack of triangle adjacent info. */
2674 int global_i = 0;
2675
2676 int edge_count = 0;
2677 for (int i = 0; i < thread_count; i++) {
2678 for (LineartObjectInfo *obi = olti[i].pending; obi; obi = obi->next) {
2679 if (!obi->v_eln) {
2680 continue;
2681 }
2682 edge_count += obi->pending_edges.next;
2683 }
2684 }
2686
2687 for (int i = 0; i < thread_count; i++) {
2688 for (LineartObjectInfo *obi = olti[i].pending; obi; obi = obi->next) {
2689 if (!obi->v_eln) {
2690 continue;
2691 }
2692 LineartVert *v = static_cast<LineartVert *>(obi->v_eln->pointer);
2693 int v_count = obi->v_eln->element_count;
2694 obi->v_eln->global_index_offset = global_i;
2695 for (int vi = 0; vi < v_count; vi++) {
2696 v[vi].index += global_i;
2697 }
2698 /* Register a global index increment. See #lineart_triangle_share_edge() and
2699 * #lineart_main_load_geometries() for detailed. It's okay that global_vindex might
2700 * eventually overflow, in such large scene it's virtually impossible for two vertex of the
2701 * same numeric index to come close together. */
2702 obi->global_i_offset = global_i;
2703 global_i += v_count;
2705 }
2706 }
2707
2708 if (G.debug_value == 4000) {
2709 double t_elapsed = BLI_time_now_seconds() - t_start;
2710 printf("Line art loading time: %lf\n", t_elapsed);
2711 printf("Discarded %d object from bound box check\n", bound_box_discard_count);
2712 }
2713}
2714
2720 const LineartVert *vt,
2721 LineartVert **l,
2722 LineartVert **r)
2723{
2724 if (tri->v[0] == vt) {
2725 *l = tri->v[1];
2726 *r = tri->v[2];
2727 return true;
2728 }
2729 if (tri->v[1] == vt) {
2730 *l = tri->v[2];
2731 *r = tri->v[0];
2732 return true;
2733 }
2734 if (tri->v[2] == vt) {
2735 *l = tri->v[0];
2736 *r = tri->v[1];
2737 return true;
2738 }
2739 return false;
2740}
2741
2743 const LineartEdge *e,
2744 bool allow_overlapping_edges)
2745{
2746 const LineartEdge *use_e = e;
2748 if (((e->target_reference & LRT_LIGHT_CONTOUR_TARGET) == tri->target_reference) ||
2749 (((e->target_reference >> 32) & LRT_LIGHT_CONTOUR_TARGET) == tri->target_reference))
2750 {
2751 return true;
2752 }
2753 }
2754 else {
2755 /* Normally we just determine from identifiers of adjacent triangles. */
2756 if ((use_e->t1 && use_e->t1->target_reference == tri->target_reference) ||
2757 (use_e->t2 && use_e->t2->target_reference == tri->target_reference))
2758 {
2759 return true;
2760 }
2761 }
2762
2763 /* If allows overlapping, then we compare the vertex coordinates one by one to determine if one
2764 * edge is from specific triangle. This is slower but can handle edge split cases very well. */
2765 if (allow_overlapping_edges) {
2766#define LRT_TRI_SAME_POINT(tri, i, pt) \
2767 ((LRT_DOUBLE_CLOSE_ENOUGH(tri->v[i]->gloc[0], pt->gloc[0]) && \
2768 LRT_DOUBLE_CLOSE_ENOUGH(tri->v[i]->gloc[1], pt->gloc[1]) && \
2769 LRT_DOUBLE_CLOSE_ENOUGH(tri->v[i]->gloc[2], pt->gloc[2])) || \
2770 (LRT_DOUBLE_CLOSE_ENOUGH(tri->v[i]->gloc[0], pt->gloc[0]) && \
2771 LRT_DOUBLE_CLOSE_ENOUGH(tri->v[i]->gloc[1], pt->gloc[1]) && \
2772 LRT_DOUBLE_CLOSE_ENOUGH(tri->v[i]->gloc[2], pt->gloc[2])))
2773 if ((LRT_TRI_SAME_POINT(tri, 0, e->v1) || LRT_TRI_SAME_POINT(tri, 1, e->v1) ||
2774 LRT_TRI_SAME_POINT(tri, 2, e->v1)) &&
2775 (LRT_TRI_SAME_POINT(tri, 0, e->v2) || LRT_TRI_SAME_POINT(tri, 1, e->v2) ||
2776 LRT_TRI_SAME_POINT(tri, 2, e->v2)))
2777 {
2778 return true;
2779 }
2780#undef LRT_TRI_SAME_POINT
2781 }
2782 return false;
2783}
2784
2785/* Sorting three intersection points from min to max,
2786 * the order for each intersection is set in `lst[0]` to `lst[2]`. */
2787#define INTERSECT_SORT_MIN_TO_MAX_3(ia, ib, ic, lst) \
2788 { \
2789 lst[0] = LRT_MIN3_INDEX(ia, ib, ic); \
2790 lst[1] = (((ia <= ib && ib <= ic) || (ic <= ib && ib <= ia)) ? \
2791 1 : \
2792 (((ic <= ia && ia <= ib) || (ib < ia && ia <= ic)) ? 0 : 2)); \
2793 lst[2] = LRT_MAX3_INDEX(ia, ib, ic); \
2794 }
2795
2796/* `ia ib ic` are ordered. */
2797#define INTERSECT_JUST_GREATER(is, order, num, index) \
2798 { \
2799 index = (num < is[order[0]] ? \
2800 order[0] : \
2801 (num < is[order[1]] ? order[1] : (num < is[order[2]] ? order[2] : -1))); \
2802 }
2803
2804/* `ia ib ic` are ordered. */
2805#define INTERSECT_JUST_SMALLER(is, order, num, index) \
2806 { \
2807 index = (num > is[order[2]] ? \
2808 order[2] : \
2809 (num > is[order[1]] ? order[1] : (num > is[order[0]] ? order[0] : -1))); \
2810 }
2811
2812#define LRT_ISEC(index) (index == 0 ? isec_e1 : (index == 1 ? isec_e2 : isec_e3))
2813#define LRT_PARALLEL(index) (index == 0 ? para_e1 : (index == 1 ? para_e2 : para_e3))
2814
2838 const LineartEdge *e,
2839 const double *override_camera_loc,
2840 const bool override_cam_is_persp,
2841 const bool allow_overlapping_edges,
2842 const double m_view_projection[4][4],
2843 const double camera_dir[3],
2844 const float cam_shift_x,
2845 const float cam_shift_y,
2846 double *from,
2847 double *to)
2848{
2849 double cross_ratios[3] = {0};
2850 int cross_order[3];
2851 int cross_v1 = -1, cross_v2 = -1;
2852 /* If the edge intersects with the triangle edges (including extensions). */
2853 int isec_e1, isec_e2, isec_e3;
2854 /* If edge is parallel to one of the edges in the triangle. */
2855 bool para_e1, para_e2, para_e3;
2856 enum LineartPointTri state_v1 = LRT_OUTSIDE_TRIANGLE, state_v2 = LRT_OUTSIDE_TRIANGLE;
2857
2858 double dir_v1[3];
2859 double dir_v2[3];
2860 double view_vector[4];
2861 double dir_cam[3];
2862 double dot_v1, dot_v2, dot_v1a, dot_v2a;
2863 double dot_f;
2864 double gloc[4], trans[4];
2865 double cut = -1;
2866
2867 double *LFBC = e->v1->fbcoord, *RFBC = e->v2->fbcoord, *FBC0 = tri->v[0]->fbcoord,
2868 *FBC1 = tri->v[1]->fbcoord, *FBC2 = tri->v[2]->fbcoord;
2869
2870 /* Overlapping not possible, return early. */
2871 if ((std::max({FBC0[0], FBC1[0], FBC2[0]}) < std::min(LFBC[0], RFBC[0])) ||
2872 (std::min({FBC0[0], FBC1[0], FBC2[0]}) > std::max(LFBC[0], RFBC[0])) ||
2873 (std::max({FBC0[1], FBC1[1], FBC2[1]}) < std::min(LFBC[1], RFBC[1])) ||
2874 (std::min({FBC0[1], FBC1[1], FBC2[1]}) > std::max(LFBC[1], RFBC[1])) ||
2875 (std::min({FBC0[3], FBC1[3], FBC2[3]}) > std::max(LFBC[3], RFBC[3])))
2876 {
2877 return false;
2878 }
2879
2880 /* If the line is one of the edge in the triangle, then it's not occluded. */
2881 if (lineart_edge_from_triangle(tri, e, allow_overlapping_edges)) {
2882 return false;
2883 }
2884
2885 /* Check if the line visually crosses one of the edge in the triangle. */
2886 isec_e1 = lineart_intersect_seg_seg(LFBC, RFBC, FBC0, FBC1, &cross_ratios[0], &para_e1);
2887 isec_e2 = lineart_intersect_seg_seg(LFBC, RFBC, FBC1, FBC2, &cross_ratios[1], &para_e2);
2888 isec_e3 = lineart_intersect_seg_seg(LFBC, RFBC, FBC2, FBC0, &cross_ratios[2], &para_e3);
2889
2890 /* Sort the intersection distance. */
2891 INTERSECT_SORT_MIN_TO_MAX_3(cross_ratios[0], cross_ratios[1], cross_ratios[2], cross_order);
2892
2893 sub_v3_v3v3_db(dir_v1, e->v1->gloc, tri->v[0]->gloc);
2894 sub_v3_v3v3_db(dir_v2, e->v2->gloc, tri->v[0]->gloc);
2895
2896 copy_v3_v3_db(dir_cam, camera_dir);
2897 copy_v3_v3_db(view_vector, override_camera_loc);
2898 if (override_cam_is_persp) {
2899 sub_v3_v3v3_db(dir_cam, view_vector, tri->v[0]->gloc);
2900 }
2901
2902 dot_v1 = dot_v3v3_db(dir_v1, tri->gn);
2903 dot_v2 = dot_v3v3_db(dir_v2, tri->gn);
2904 dot_f = dot_v3v3_db(dir_cam, tri->gn);
2905
2907 (e->target_reference == tri->target_reference))
2908 {
2909 if (((dot_f > 0) && (e->flags & MOD_LINEART_EDGE_FLAG_SHADOW_FACING_LIGHT)) ||
2910 ((dot_f < 0) && !(e->flags & MOD_LINEART_EDGE_FLAG_SHADOW_FACING_LIGHT)))
2911 {
2912 *from = 0.0f;
2913 *to = 1.0f;
2914 return true;
2915 }
2916
2917 return false;
2918 }
2919
2920 /* NOTE(Yiming): When we don't use `dot_f==0` here, it's theoretically possible that _some_
2921 * faces in perspective mode would get erroneously caught in this condition where they really
2922 * are legit faces that would produce occlusion, but haven't encountered those yet in my test
2923 * files.
2924 */
2925 if (fabs(dot_f) < FLT_EPSILON) {
2926 return false;
2927 }
2928
2929 /* Whether two end points are inside/on_the_edge/outside of the triangle. */
2930 state_v1 = lineart_point_triangle_relation(LFBC, FBC0, FBC1, FBC2);
2931 state_v2 = lineart_point_triangle_relation(RFBC, FBC0, FBC1, FBC2);
2932
2933 /* If the edge doesn't visually cross any edge of the triangle... */
2934 if (!isec_e1 && !isec_e2 && !isec_e3) {
2935 /* And if both end point from the edge is outside of the triangle... */
2936 if ((!state_v1) && (!state_v2)) {
2937 return false; /* We don't have any occlusion. */
2938 }
2939 }
2940
2941 /* Determine the cut position. */
2942
2943 dot_v1a = fabs(dot_v1);
2944 if (dot_v1a < DBL_EPSILON) {
2945 dot_v1a = 0;
2946 dot_v1 = 0;
2947 }
2948 dot_v2a = fabs(dot_v2);
2949 if (dot_v2a < DBL_EPSILON) {
2950 dot_v2a = 0;
2951 dot_v2 = 0;
2952 }
2953 if (dot_v1 - dot_v2 == 0) {
2954 cut = 100000;
2955 }
2956 else if (dot_v1 * dot_v2 <= 0) {
2957 cut = dot_v1a / fabs(dot_v1 - dot_v2);
2958 }
2959 else {
2960 cut = fabs(dot_v2 + dot_v1) / fabs(dot_v1 - dot_v2);
2961 cut = dot_v2a > dot_v1a ? 1 - cut : cut;
2962 }
2963
2964 /* Transform the cut from geometry space to image space. */
2965 if (override_cam_is_persp) {
2966 interp_v3_v3v3_db(gloc, e->v1->gloc, e->v2->gloc, cut);
2967 mul_v4_m4v3_db(trans, m_view_projection, gloc);
2968 mul_v3db_db(trans, (1 / trans[3]));
2969 trans[0] -= cam_shift_x * 2;
2970 trans[1] -= cam_shift_y * 2;
2971 /* To accommodate `k=0` and `k=inf` (vertical) lines. here the cut is in image space. */
2972 if (fabs(e->v1->fbcoord[0] - e->v2->fbcoord[0]) > fabs(e->v1->fbcoord[1] - e->v2->fbcoord[1]))
2973 {
2974 cut = ratiod(e->v1->fbcoord[0], e->v2->fbcoord[0], trans[0]);
2975 }
2976 else {
2977 cut = ratiod(e->v1->fbcoord[1], e->v2->fbcoord[1], trans[1]);
2978 }
2979 }
2980
2981#define LRT_GUARD_NOT_FOUND \
2982 if (cross_v1 < 0 || cross_v2 < 0) { \
2983 return false; \
2984 }
2985
2986 /* Determine the pair of edges that the line has crossed. The "|" symbol in the comment
2987 * indicates triangle boundary. DBL_TRIANGLE_LIM is needed to for floating point precision
2988 * tolerance. */
2989
2990 if (state_v1 == LRT_INSIDE_TRIANGLE) {
2991 /* Left side is in the triangle. */
2992 if (state_v2 == LRT_INSIDE_TRIANGLE) {
2993 /* | l---r | */
2994 INTERSECT_JUST_SMALLER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v1);
2995 INTERSECT_JUST_GREATER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v2);
2996 }
2997 else if (state_v2 == LRT_ON_TRIANGLE) {
2998 /* | l------r| */
2999 INTERSECT_JUST_SMALLER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v1);
3000 INTERSECT_JUST_GREATER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v2);
3001 }
3002 else if (state_v2 == LRT_OUTSIDE_TRIANGLE) {
3003 /* | l-------|------r */
3004 INTERSECT_JUST_SMALLER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v1);
3005 INTERSECT_JUST_GREATER(cross_ratios, cross_order, 0, cross_v2);
3006 }
3007 }
3008 else if (state_v1 == LRT_ON_TRIANGLE) {
3009 /* Left side is on some edge of the triangle. */
3010 if (state_v2 == LRT_INSIDE_TRIANGLE) {
3011 /* |l------r | */
3012 INTERSECT_JUST_SMALLER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v1);
3013 INTERSECT_JUST_GREATER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v2);
3014 }
3015 else if (state_v2 == LRT_ON_TRIANGLE) {
3016 /* |l---------r| */
3017 INTERSECT_JUST_SMALLER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v1);
3018 INTERSECT_JUST_GREATER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v2);
3019 }
3020 else if (state_v2 == LRT_OUTSIDE_TRIANGLE) {
3021 /* |l----------|-------r (crossing the triangle) [OR]
3022 * r---------|l | (not crossing the triangle) */
3023 INTERSECT_JUST_GREATER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v2);
3024 if (cross_v2 >= 0 && LRT_ISEC(cross_v2) && cross_ratios[cross_v2] > (DBL_TRIANGLE_LIM)) {
3025 INTERSECT_JUST_SMALLER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v1);
3026 }
3027 else {
3028 INTERSECT_JUST_SMALLER(cross_ratios, cross_order, DBL_TRIANGLE_LIM, cross_v2);
3029 if (cross_v2 > 0) {
3030 INTERSECT_JUST_SMALLER(cross_ratios, cross_order, cross_ratios[cross_v2], cross_v1);
3031 }
3032 }
3034 /* We could have the edge being completely parallel to the triangle where there isn't a
3035 * viable occlusion result. */
3036 if ((LRT_PARALLEL(cross_v1) && !LRT_ISEC(cross_v1)) ||
3037 (LRT_PARALLEL(cross_v2) && !LRT_ISEC(cross_v2)))
3038 {
3039 return false;
3040 }
3041 }
3042 }
3043 else if (state_v1 == LRT_OUTSIDE_TRIANGLE) {
3044 /* Left side is outside of the triangle. */
3045 if (state_v2 == LRT_INSIDE_TRIANGLE) {
3046 /* l---|---r | */
3047 INTERSECT_JUST_SMALLER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v1);
3048 INTERSECT_JUST_GREATER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v2);
3049 }
3050 else if (state_v2 == LRT_ON_TRIANGLE) {
3051 /* |r----------|-------l (crossing the triangle) [OR]
3052 * l---------|r | (not crossing the triangle) */
3053 INTERSECT_JUST_SMALLER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v1);
3054 if (cross_v1 >= 0 && LRT_ISEC(cross_v1) && cross_ratios[cross_v1] < (1 - DBL_TRIANGLE_LIM)) {
3055 INTERSECT_JUST_GREATER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v2);
3056 }
3057 else {
3058 INTERSECT_JUST_GREATER(cross_ratios, cross_order, 1 - DBL_TRIANGLE_LIM, cross_v1);
3059 if (cross_v1 > 0) {
3060 INTERSECT_JUST_GREATER(cross_ratios, cross_order, cross_ratios[cross_v1], cross_v2);
3061 }
3062 }
3064 /* The same logic applies as above case. */
3065 if ((LRT_PARALLEL(cross_v1) && !LRT_ISEC(cross_v1)) ||
3066 (LRT_PARALLEL(cross_v2) && !LRT_ISEC(cross_v2)))
3067 {
3068 return false;
3069 }
3070 }
3071 else if (state_v2 == LRT_OUTSIDE_TRIANGLE) {
3072 /* l---|----|----r (crossing the triangle) [OR]
3073 * l----r | | (not crossing the triangle) */
3074 INTERSECT_JUST_GREATER(cross_ratios, cross_order, -DBL_TRIANGLE_LIM, cross_v1);
3075 if (cross_v1 >= 0 && LRT_ISEC(cross_v1)) {
3076 INTERSECT_JUST_GREATER(cross_ratios, cross_order, cross_ratios[cross_v1], cross_v2);
3077 }
3078 else {
3079 if (cross_v1 >= 0) {
3080 INTERSECT_JUST_GREATER(cross_ratios, cross_order, cross_ratios[cross_v1], cross_v1);
3081 if (cross_v1 >= 0) {
3082 INTERSECT_JUST_GREATER(cross_ratios, cross_order, cross_ratios[cross_v1], cross_v2);
3083 }
3084 }
3085 }
3086 }
3087 }
3088
3090
3091 double dot_1f = dot_v1 * dot_f, dot_2f = dot_v2 * dot_f;
3092
3093 /* Determine the start and end point of image space cut on a line. */
3094 if (dot_1f <= 0 && dot_2f <= 0 && (dot_v1 || dot_v2)) {
3095 *from = std::max(0.0, cross_ratios[cross_v1]);
3096 *to = std::min(1.0, cross_ratios[cross_v2]);
3097 if (*from >= *to) {
3098 return false;
3099 }
3100 return true;
3101 }
3102 if (dot_1f >= 0 && dot_2f <= 0 && (dot_v1 || dot_v2)) {
3103 *from = std::max(cut, cross_ratios[cross_v1]);
3104 *to = std::min(1.0, cross_ratios[cross_v2]);
3105 if (*from >= *to) {
3106 return false;
3107 }
3108 return true;
3109 }
3110 if (dot_1f <= 0 && dot_2f >= 0 && (dot_v1 || dot_v2)) {
3111 *from = std::max(0.0, cross_ratios[cross_v1]);
3112 *to = std::min(cut, cross_ratios[cross_v2]);
3113 if (*from >= *to) {
3114 return false;
3115 }
3116 return true;
3117 }
3118
3119 /* Unlikely, but here's the default failed value if anything fall through. */
3120 return false;
3121}
3122
3123#undef INTERSECT_SORT_MIN_TO_MAX_3
3124#undef INTERSECT_JUST_GREATER
3125#undef INTERSECT_JUST_SMALLER
3126#undef LRT_ISEC
3127#undef LRT_PARALLEL
3128
3134{
3135 if (l->v[0]->index == r->v[0]->index) {
3136 if (l->v[1]->index == r->v[1]->index || l->v[1]->index == r->v[2]->index ||
3137 l->v[2]->index == r->v[2]->index || l->v[2]->index == r->v[1]->index)
3138 {
3139 return true;
3140 }
3141 }
3142 if (l->v[0]->index == r->v[1]->index) {
3143 if (l->v[1]->index == r->v[0]->index || l->v[1]->index == r->v[2]->index ||
3144 l->v[2]->index == r->v[2]->index || l->v[2]->index == r->v[0]->index)
3145 {
3146 return true;
3147 }
3148 }
3149 if (l->v[0]->index == r->v[2]->index) {
3150 if (l->v[1]->index == r->v[1]->index || l->v[1]->index == r->v[0]->index ||
3151 l->v[2]->index == r->v[0]->index || l->v[2]->index == r->v[1]->index)
3152 {
3153 return true;
3154 }
3155 }
3156 if (l->v[1]->index == r->v[0]->index) {
3157 if (l->v[2]->index == r->v[1]->index || l->v[2]->index == r->v[2]->index ||
3158 l->v[0]->index == r->v[2]->index || l->v[0]->index == r->v[1]->index)
3159 {
3160 return true;
3161 }
3162 }
3163 if (l->v[1]->index == r->v[1]->index) {
3164 if (l->v[2]->index == r->v[0]->index || l->v[2]->index == r->v[2]->index ||
3165 l->v[0]->index == r->v[2]->index || l->v[0]->index == r->v[0]->index)
3166 {
3167 return true;
3168 }
3169 }
3170 if (l->v[1]->index == r->v[2]->index) {
3171 if (l->v[2]->index == r->v[1]->index || l->v[2]->index == r->v[0]->index ||
3172 l->v[0]->index == r->v[0]->index || l->v[0]->index == r->v[1]->index)
3173 {
3174 return true;
3175 }
3176 }
3177
3178 /* Otherwise not possible. */
3179 return false;
3180}
3181
3183 const LineartTriangle *r)
3184{
3185 if (l->v[0] == r->v[0]) {
3186 return r->v[0];
3187 }
3188 if (l->v[0] == r->v[1]) {
3189 return r->v[1];
3190 }
3191 if (l->v[0] == r->v[2]) {
3192 return r->v[2];
3193 }
3194 if (l->v[1] == r->v[0]) {
3195 return r->v[0];
3196 }
3197 if (l->v[1] == r->v[1]) {
3198 return r->v[1];
3199 }
3200 if (l->v[1] == r->v[2]) {
3201 return r->v[2];
3202 }
3203 if (l->v[2] == r->v[0]) {
3204 return r->v[0];
3205 }
3206 if (l->v[2] == r->v[1]) {
3207 return r->v[1];
3208 }
3209 if (l->v[2] == r->v[2]) {
3210 return r->v[2];
3211 }
3212 return nullptr;
3213}
3214
3216 LineartVert *v1, LineartVert *v2, LineartTriangle *tri, const double *last, double *rv)
3217{
3218 /* Direction vectors for the edge verts. We will check if the verts are on the same side of the
3219 * triangle or not. */
3220 double dir_v1[3], dir_v2[3];
3221 double dot_v1, dot_v2;
3222 double gloc[3];
3223
3224 sub_v3_v3v3_db(dir_v1, v1->gloc, tri->v[0]->gloc);
3225 sub_v3_v3v3_db(dir_v2, v2->gloc, tri->v[0]->gloc);
3226
3227 dot_v1 = dot_v3v3_db(dir_v1, tri->gn);
3228 dot_v2 = dot_v3v3_db(dir_v2, tri->gn);
3229
3230 if (dot_v1 * dot_v2 > 0 || (!dot_v1 && !dot_v2)) {
3231 return false;
3232 }
3233
3234 dot_v1 = fabs(dot_v1);
3235 dot_v2 = fabs(dot_v2);
3236
3237 interp_v3_v3v3_db(gloc, v1->gloc, v2->gloc, dot_v1 / (dot_v1 + dot_v2));
3238
3239 /* Due to precision issue, we might end up with the same point as the one we already detected. */
3240 if (last && LRT_DOUBLE_CLOSE_ENOUGH(last[0], gloc[0]) &&
3241 LRT_DOUBLE_CLOSE_ENOUGH(last[1], gloc[1]) && LRT_DOUBLE_CLOSE_ENOUGH(last[2], gloc[2]))
3242 {
3243 return false;
3244 }
3245
3246 if (!lineart_point_inside_triangle3d(gloc, tri->v[0]->gloc, tri->v[1]->gloc, tri->v[2]->gloc)) {
3247 return false;
3248 }
3249
3250 copy_v3_v3_db(rv, gloc);
3251
3252 return true;
3253}
3254
3256 LineartTriangle *t2,
3257 double *v1,
3258 double *v2)
3259{
3260 double *next = v1, *last = nullptr;
3261 LineartVert *sv1, *sv2;
3262
3263 LineartVert *share = lineart_triangle_share_point(t2, tri);
3264
3265 if (share) {
3266 /* If triangles have sharing points like `abc` and `acd`, then we only need to detect `bc`
3267 * against `acd` or `cd` against `abc`. */
3268
3269 lineart_triangle_get_other_verts(tri, share, &sv1, &sv2);
3270
3271 copy_v3_v3_db(v1, share->gloc);
3272
3273 if (!lineart_triangle_2v_intersection_math(sv1, sv2, t2, nullptr, v2)) {
3274 lineart_triangle_get_other_verts(t2, share, &sv1, &sv2);
3275 if (lineart_triangle_2v_intersection_math(sv1, sv2, tri, nullptr, v2)) {
3276 return true;
3277 }
3278 }
3279 }
3280 else {
3281 /* If not sharing any points, then we need to try all the possibilities. */
3282
3283 if (lineart_triangle_2v_intersection_math(tri->v[0], tri->v[1], t2, nullptr, v1)) {
3284 next = v2;
3285 last = v1;
3286 }
3287
3288 if (lineart_triangle_2v_intersection_math(tri->v[1], tri->v[2], t2, last, next)) {
3289 if (last) {
3290 return true;
3291 }
3292 next = v2;
3293 last = v1;
3294 }
3295 if (lineart_triangle_2v_intersection_math(tri->v[2], tri->v[0], t2, last, next)) {
3296 if (last) {
3297 return true;
3298 }
3299 next = v2;
3300 last = v1;
3301 }
3302
3303 if (lineart_triangle_2v_intersection_math(t2->v[0], t2->v[1], tri, last, next)) {
3304 if (last) {
3305 return true;
3306 }
3307 next = v2;
3308 last = v1;
3309 }
3310 if (lineart_triangle_2v_intersection_math(t2->v[1], t2->v[2], tri, last, next)) {
3311 if (last) {
3312 return true;
3313 }
3314 next = v2;
3315 last = v1;
3316 }
3317 if (lineart_triangle_2v_intersection_math(t2->v[2], t2->v[0], tri, last, next)) {
3318 if (last) {
3319 return true;
3320 }
3321 next = v2;
3322 last = v1;
3323 }
3324 }
3325 return false;
3326}
3327
3329 const double *v1,
3330 const double *v2,
3331 LineartTriangle *tri1,
3332 LineartTriangle *tri2)
3333{
3334 if (th->current == th->max) {
3335
3337 size_t(th->max) * 2, "LineartIsecSingle");
3338 memcpy(new_array, th->array, sizeof(LineartIsecSingle) * th->max);
3339 th->max *= 2;
3340 MEM_delete(th->array);
3341 th->array = new_array;
3342 }
3343 LineartIsecSingle *isec_single = &th->array[th->current];
3344 copy_v3_v3_db(isec_single->v1, v1);
3345 copy_v3_v3_db(isec_single->v2, v2);
3346 isec_single->tri1 = tri1;
3347 isec_single->tri2 = tri2;
3348 if (tri1->target_reference > tri2->target_reference) {
3349 std::swap(isec_single->tri1, isec_single->tri2);
3350 }
3351 th->current++;
3352}
3353
3354#define LRT_ISECT_TRIANGLE_PER_THREAD 4096
3355
3357{
3358 LineartData *ld = th->ld;
3359 int remaining = LRT_ISECT_TRIANGLE_PER_THREAD;
3360
3363
3364 if (!eln) {
3366 return false;
3367 }
3368
3369 th->pending_from = eln;
3371
3372 while (remaining > 0 && eln) {
3373 int remaining_this_eln = eln->element_count - ld->isect_scheduled_up_to_index;
3374 int added_count = std::min(remaining, remaining_this_eln);
3375 remaining -= added_count;
3376 if (remaining || added_count == remaining_this_eln) {
3377 eln = eln->next;
3378 ld->isect_scheduled_up_to = eln;
3380 }
3381 else {
3382 ld->isect_scheduled_up_to_index += added_count;
3383 }
3384 }
3385
3386 th->pending_to = eln ? eln :
3387
3388 ld->geom.triangle_buffer_pointers.last();
3390
3392
3393 return true;
3394}
3395
3396/* This function initializes two things:
3397 * 1) Triangle array scheduling info, for each worker thread to get its chunk from the scheduler.
3398 * 2) Per-thread intersection result array. Does not store actual #LineartEdge, these results will
3399 * be finalized by #lineart_create_edges_from_isec_data
3400 */
3401static void lineart_init_isec_thread(LineartIsecData *d, LineartData *ld, int thread_count)
3402{
3403 d->threads = MEM_new_array_zeroed<LineartIsecThread>(thread_count, "LineartIsecThread arr");
3404 d->ld = ld;
3405 d->thread_count = thread_count;
3406
3407 ld->isect_scheduled_up_to = static_cast<LineartElementLinkNode *>(
3408 ld->geom.triangle_buffer_pointers.first_);
3410
3411 for (int i = 0; i < thread_count; i++) {
3412 LineartIsecThread *it = &d->threads[i];
3413 it->array = MEM_new_array_uninitialized<LineartIsecSingle>(100, "LineartIsecSingle arr");
3414 it->max = 100;
3415 it->current = 0;
3416 it->thread_id = i;
3417 it->ld = ld;
3418 }
3419}
3420
3422{
3423 for (int i = 0; i < d->thread_count; i++) {
3424 LineartIsecThread *it = &d->threads[i];
3425 MEM_delete(it->array);
3426 }
3427 MEM_delete(d->threads);
3428}
3429
3433 int up_to)
3434{
3435 BLI_assert(th != nullptr);
3436
3437 if (!th) {
3438 return;
3439 }
3440
3441 double *G0 = tri->v[0]->gloc, *G1 = tri->v[1]->gloc, *G2 = tri->v[2]->gloc;
3442
3443 /* If this _is_ the smallest subdivision bounding area, then do the intersections there. */
3444 for (int i = 0; i < up_to; i++) {
3445 /* Testing_triangle->testing[0] is used to store pairing triangle reference.
3446 * See definition of LineartTriangleThread for more info. */
3447 LineartTriangle *testing_triangle = ba->linked_triangles[i];
3448 LineartTriangleThread *tt = reinterpret_cast<LineartTriangleThread *>(testing_triangle);
3449
3450 if (testing_triangle == tri ||
3451 tt->testing_e[th->thread_id] == reinterpret_cast<LineartEdge *>(tri))
3452 {
3453 continue;
3454 }
3455 tt->testing_e[th->thread_id] = reinterpret_cast<LineartEdge *>(tri);
3456
3457 if (!((testing_triangle->flags | tri->flags) & LRT_TRIANGLE_FORCE_INTERSECTION)) {
3458 if (((testing_triangle->flags | tri->flags) & LRT_TRIANGLE_NO_INTERSECTION) ||
3459 (testing_triangle->flags & tri->flags & LRT_TRIANGLE_INTERSECTION_ONLY))
3460 {
3461 continue;
3462 }
3463 }
3464
3465 double *RG0 = testing_triangle->v[0]->gloc, *RG1 = testing_triangle->v[1]->gloc,
3466 *RG2 = testing_triangle->v[2]->gloc;
3467
3468 /* Bounding box not overlapping or triangles share edges, not potential of intersecting. */
3469 if ((std::min({G0[2], G1[2], G2[2]}) > std::max({RG0[2], RG1[2], RG2[2]})) ||
3470 (std::max({G0[2], G1[2], G2[2]}) < std::min({RG0[2], RG1[2], RG2[2]})) ||
3471 (std::min({G0[0], G1[0], G2[0]}) > std::max({RG0[0], RG1[0], RG2[0]})) ||
3472 (std::max({G0[0], G1[0], G2[0]}) < std::min({RG0[0], RG1[0], RG2[0]})) ||
3473 (std::min({G0[1], G1[1], G2[1]}) > std::max({RG0[1], RG1[1], RG2[1]})) ||
3474 (std::max({G0[1], G1[1], G2[1]}) < std::min({RG0[1], RG1[1], RG2[1]})) ||
3475 lineart_triangle_share_edge(tri, testing_triangle))
3476 {
3477 continue;
3478 }
3479
3480 /* If we do need to compute intersection, then finally do it. */
3481
3482 double iv1[3], iv2[3];
3483 if (lineart_triangle_intersect_math(tri, testing_triangle, iv1, iv2)) {
3484 lineart_add_isec_thread(th, iv1, iv2, tri, testing_triangle);
3485 }
3486 }
3487}
3488
3490{
3491 float direction[3] = {0, 0, 1};
3492 float trans[3];
3493 float inv[4][4];
3494 float obmat_no_scale[4][4];
3495
3496 copy_m4_m4(obmat_no_scale, ld->conf.cam_obmat);
3497 normalize_v3(obmat_no_scale[0]);
3498 normalize_v3(obmat_no_scale[1]);
3499 normalize_v3(obmat_no_scale[2]);
3500 invert_m4_m4(inv, obmat_no_scale);
3501 transpose_m4(inv);
3502 mul_v3_mat3_m4v3(trans, inv, direction);
3503 copy_m4_m4(ld->conf.cam_obmat, obmat_no_scale);
3504 copy_v3db_v3fl(ld->conf.view_vector, trans);
3505
3507 copy_m4_m4(obmat_no_scale, ld->conf.cam_obmat_secondary);
3508 normalize_v3(obmat_no_scale[0]);
3509 normalize_v3(obmat_no_scale[1]);
3510 normalize_v3(obmat_no_scale[2]);
3511 invert_m4_m4(inv, obmat_no_scale);
3512 transpose_m4(inv);
3513 mul_v3_mat3_m4v3(trans, inv, direction);
3514 copy_m4_m4(ld->conf.cam_obmat_secondary, obmat_no_scale);
3516 }
3517}
3518
3520{
3521 BLI_spin_end(&ba->lock);
3522 if (ba->child) {
3523 for (int i = 0; i < 4; i++) {
3525 }
3526 }
3527}
3528
3530{
3531 if (ld == nullptr) {
3532 return;
3533 }
3534
3535 ld->chains.clear_no_delete();
3536 ld->wasted_cuts.clear_no_delete();
3537
3538 ld->geom.vertex_buffer_pointers.clear_no_delete();
3539 ld->geom.line_buffer_pointers.clear_no_delete();
3540 ld->geom.triangle_buffer_pointers.clear_no_delete();
3541
3542 if (ld->pending_edges.array) {
3543 MEM_delete(ld->pending_edges.array);
3544 }
3545
3546 for (int i = 0; i < ld->qtree.initial_tile_count; i++) {
3548 }
3550
3552}
3553
3555{
3556 if (ld == nullptr) {
3557 return;
3558 }
3559
3560 BLI_spin_end(&ld->lock_task);
3561 BLI_spin_end(&ld->lock_cuts);
3563
3565
3567}
3568
3570{
3571 LineartData *ld = lmd->la_data_ptr;
3572
3574
3575 if (ld) {
3576 MEM_delete(ld);
3577 lmd->la_data_ptr = nullptr;
3578 }
3579
3580 if (G.debug_value == 4000) {
3581 printf("LRT: Destroyed render data.\n");
3582 }
3583}
3584
3586{
3587 LineartCache *lc = MEM_new_zeroed<LineartCache>("Lineart Cache");
3588 return lc;
3589}
3590
3592{
3593 if (!(*lc)) {
3594 return;
3595 }
3596 lineart_mem_destroy(&((*lc)->chain_data_pool));
3597 MEM_delete(*lc);
3598 (*lc) = nullptr;
3599}
3600
3603 Object *camera,
3604 Object *active_camera,
3605 LineartCache *lc)
3606{
3607 LineartData *ld = MEM_new_zeroed<LineartData>("Line Art render buffer");
3608 lmd->cache = lc;
3609 lmd->la_data_ptr = ld;
3611
3612 if (!scene || !camera || !lc) {
3613 return nullptr;
3614 }
3615 const Camera *c = id_cast<Camera *>(camera->data);
3616 double clipping_offset = 0;
3617
3619 /* This way the clipped lines are "stably visible" by prevents depth buffer artifacts. */
3620 clipping_offset = 0.0001;
3621 }
3622
3623 copy_v3db_v3fl(ld->conf.camera_pos, camera->object_to_world().location());
3624 if (active_camera) {
3625 copy_v3db_v3fl(ld->conf.active_camera_pos, active_camera->object_to_world().location());
3626 }
3627 copy_m4_m4(ld->conf.cam_obmat, camera->object_to_world().ptr());
3628 /* Make sure none of the scaling factor makes in, line art expects no scaling on cameras and
3629 * lights. */
3630 normalize_v3(ld->conf.cam_obmat[0]);
3631 normalize_v3(ld->conf.cam_obmat[1]);
3632 normalize_v3(ld->conf.cam_obmat[2]);
3633
3634 ld->conf.cam_is_persp = (c->type == CAM_PERSP);
3635 ld->conf.near_clip = c->clip_start + clipping_offset;
3636 ld->conf.far_clip = c->clip_end - clipping_offset;
3637 ld->w = scene->r.xsch;
3638 ld->h = scene->r.ysch;
3639
3640 if (ld->conf.cam_is_persp) {
3642 }
3643 else {
3645 }
3646
3647 double asp = double(ld->w) / double(ld->h);
3648 int fit = BKE_camera_sensor_fit(c->sensor_fit, ld->w, ld->h);
3649 ld->conf.shift_x = fit == CAMERA_SENSOR_FIT_HOR ? c->shiftx : c->shiftx / asp;
3650 ld->conf.shift_y = fit == CAMERA_SENSOR_FIT_VERT ? c->shifty : c->shifty * asp;
3651
3652 ld->conf.overscan = lmd->overscan;
3653
3654 ld->conf.shift_x /= (1 + ld->conf.overscan);
3655 ld->conf.shift_y /= (1 + ld->conf.overscan);
3656
3657 if (lmd->light_contour_object) {
3658 Object *light_obj = lmd->light_contour_object;
3659 copy_v3db_v3fl(ld->conf.camera_pos_secondary, light_obj->object_to_world().location());
3660 copy_m4_m4(ld->conf.cam_obmat_secondary, light_obj->object_to_world().ptr());
3661 /* Make sure none of the scaling factor makes in, line art expects no scaling on cameras and
3662 * lights. */
3667 if (light_obj->type == OB_LAMP) {
3668 ld->conf.cam_is_persp_secondary = (id_cast<Light *>(light_obj->data))->type != LA_SUN;
3669 }
3670 }
3671
3676
3678 0;
3681 0;
3688
3689 /* See lineart_edge_from_triangle() for how this option may impact performance. */
3692
3695
3697 0;
3699
3702
3703 /* This is used to limit calculation to a certain level to save time, lines who have higher
3704 * occlusion levels will get ignored. */
3706
3707 int16_t edge_types = lmd->edge_types_override;
3708
3709 /* lmd->edge_types_override contains all used flags in the modifier stack. */
3710 ld->conf.use_contour = (edge_types & MOD_LINEART_EDGE_FLAG_CONTOUR) != 0;
3711 ld->conf.use_crease = (edge_types & MOD_LINEART_EDGE_FLAG_CREASE) != 0;
3712 ld->conf.use_material = (edge_types & MOD_LINEART_EDGE_FLAG_MATERIAL) != 0;
3713 ld->conf.use_edge_marks = (edge_types & MOD_LINEART_EDGE_FLAG_EDGE_MARK) != 0;
3715 ld->conf.use_loose = (edge_types & MOD_LINEART_EDGE_FLAG_LOOSE) != 0;
3716 ld->conf.use_light_contour = ((edge_types & MOD_LINEART_EDGE_FLAG_LIGHT_CONTOUR) != 0 &&
3717 (lmd->light_contour_object != nullptr));
3718 ld->conf.use_shadow = ((edge_types & MOD_LINEART_EDGE_FLAG_PROJECTED_SHADOW) != 0 &&
3719 (lmd->light_contour_object != nullptr));
3720
3725
3727 0;
3728
3736
3738
3739 /* See #LineartData::edge_data_pool for explanation. */
3741
3745
3746 ld->thread_count = BKE_render_num_threads(&scene->r);
3747
3748 return ld;
3749}
3750
3752{
3753 return sizeof(LineartTriangle) + (sizeof(LineartEdge *) * (ld->thread_count));
3754}
3755
3757{
3758 /* Initial tile split is defined as 4 (subdivided as 4*4), increasing the value allows the
3759 * algorithm to build the acceleration structure for bigger scenes a little faster but not as
3760 * efficient at handling medium to small scenes. */
3761 int sp_w = LRT_BA_ROWS;
3762 int sp_h = LRT_BA_ROWS;
3763 int row, col;
3765
3766 /* Always make sure the shortest side has at least LRT_BA_ROWS tiles. */
3767 if (ld->w > ld->h) {
3768 sp_w = sp_h * ld->w / ld->h;
3769 }
3770 else {
3771 sp_h = sp_w * ld->h / ld->w;
3772 }
3773
3774 /* Because NDC (Normalized Device Coordinates) range is (-1,1),
3775 * so the span for each initial tile is double of that in the (0,1) range. */
3776 double span_w = 1.0 / sp_w * 2.0;
3777 double span_h = 1.0 / sp_h * 2.0;
3778
3779 ld->qtree.count_x = sp_w;
3780 ld->qtree.count_y = sp_h;
3781 ld->qtree.tile_width = span_w;
3782 ld->qtree.tile_height = span_h;
3783
3784 ld->qtree.initial_tile_count = sp_w * sp_h;
3787 for (int i = 0; i < ld->qtree.initial_tile_count; i++) {
3789 }
3790
3791 /* Initialize tiles. */
3792 for (row = 0; row < sp_h; row++) {
3793 for (col = 0; col < sp_w; col++) {
3794 ba = &ld->qtree.initials[row * ld->qtree.count_x + col];
3795
3796 /* Set the four direction limits. */
3797 ba->l = span_w * col - 1.0;
3798 ba->r = (col == sp_w - 1) ? 1.0 : (span_w * (col + 1) - 1.0);
3799 ba->u = 1.0 - span_h * row;
3800 ba->b = (row == sp_h - 1) ? -1.0 : (1.0 - span_h * (row + 1));
3801
3802 ba->cx = (ba->l + ba->r) / 2;
3803 ba->cy = (ba->u + ba->b) / 2;
3804
3805 /* Init linked_triangles array. */
3809 "ba_linked_triangles");
3811 "ba_linked_lines");
3812
3813 BLI_spin_init(&ba->lock);
3814 }
3815 }
3816}
3817
3822{
3823 LineartBoundingArea *ba = root->child, *tba;
3824 LinkData *lip2, *next_lip;
3826
3827 /* Inter-connection with newly created 4 child bounding areas. */
3828 lineart_list_append_pointer_pool(&ba[1].rp, mph, &ba[0]);
3829 lineart_list_append_pointer_pool(&ba[0].lp, mph, &ba[1]);
3830 lineart_list_append_pointer_pool(&ba[1].bp, mph, &ba[2]);
3831 lineart_list_append_pointer_pool(&ba[2].up, mph, &ba[1]);
3832 lineart_list_append_pointer_pool(&ba[2].rp, mph, &ba[3]);
3833 lineart_list_append_pointer_pool(&ba[3].lp, mph, &ba[2]);
3834 lineart_list_append_pointer_pool(&ba[3].up, mph, &ba[0]);
3835 lineart_list_append_pointer_pool(&ba[0].bp, mph, &ba[3]);
3836
3837 /* Connect 4 child bounding areas to other areas that are
3838 * adjacent to their original parents. */
3839 for (LinkData &lip : root->lp) {
3840
3841 /* For example, we are dealing with parent's left side
3842 * "tba" represents each adjacent neighbor of the parent. */
3843 tba = static_cast<LineartBoundingArea *>(lip.data);
3844
3845 /* if this neighbor is adjacent to
3846 * the two new areas on the left side of the parent,
3847 * then add them to the adjacent list as well. */
3848 if (ba[1].u > tba->b && ba[1].b < tba->u) {
3849 lineart_list_append_pointer_pool(&ba[1].lp, mph, tba);
3850 lineart_list_append_pointer_pool(&tba->rp, mph, &ba[1]);
3851 }
3852 if (ba[2].u > tba->b && ba[2].b < tba->u) {
3853 lineart_list_append_pointer_pool(&ba[2].lp, mph, tba);
3854 lineart_list_append_pointer_pool(&tba->rp, mph, &ba[2]);
3855 }
3856 }
3857 for (LinkData &lip : root->rp) {
3858 tba = static_cast<LineartBoundingArea *>(lip.data);
3859 if (ba[0].u > tba->b && ba[0].b < tba->u) {
3860 lineart_list_append_pointer_pool(&ba[0].rp, mph, tba);
3861 lineart_list_append_pointer_pool(&tba->lp, mph, &ba[0]);
3862 }
3863 if (ba[3].u > tba->b && ba[3].b < tba->u) {
3864 lineart_list_append_pointer_pool(&ba[3].rp, mph, tba);
3865 lineart_list_append_pointer_pool(&tba->lp, mph, &ba[3]);
3866 }
3867 }
3868 for (LinkData &lip : root->up) {
3869 tba = static_cast<LineartBoundingArea *>(lip.data);
3870 if (ba[0].r > tba->l && ba[0].l < tba->r) {
3871 lineart_list_append_pointer_pool(&ba[0].up, mph, tba);
3872 lineart_list_append_pointer_pool(&tba->bp, mph, &ba[0]);
3873 }
3874 if (ba[1].r > tba->l && ba[1].l < tba->r) {
3875 lineart_list_append_pointer_pool(&ba[1].up, mph, tba);
3876 lineart_list_append_pointer_pool(&tba->bp, mph, &ba[1]);
3877 }
3878 }
3879 for (LinkData &lip : root->bp) {
3880 tba = static_cast<LineartBoundingArea *>(lip.data);
3881 if (ba[2].r > tba->l && ba[2].l < tba->r) {
3882 lineart_list_append_pointer_pool(&ba[2].bp, mph, tba);
3883 lineart_list_append_pointer_pool(&tba->up, mph, &ba[2]);
3884 }
3885 if (ba[3].r > tba->l && ba[3].l < tba->r) {
3886 lineart_list_append_pointer_pool(&ba[3].bp, mph, tba);
3887 lineart_list_append_pointer_pool(&tba->up, mph, &ba[3]);
3888 }
3889 }
3890
3891 /* Then remove the parent bounding areas from
3892 * their original adjacent areas. */
3893 for (LinkData &lip : root->lp) {
3894 for (lip2 = static_cast<LinkData *>((static_cast<LineartBoundingArea *>(lip.data))->rp.first_);
3895 lip2;
3896 lip2 = next_lip)
3897 {
3898 next_lip = lip2->next;
3899 tba = static_cast<LineartBoundingArea *>(lip2->data);
3900 if (tba == root) {
3902 &(static_cast<LineartBoundingArea *>(lip.data))->rp, lip2);
3903 if (ba[1].u > tba->b && ba[1].b < tba->u) {
3904 lineart_list_append_pointer_pool(&tba->rp, mph, &ba[1]);
3905 }
3906 if (ba[2].u > tba->b && ba[2].b < tba->u) {
3907 lineart_list_append_pointer_pool(&tba->rp, mph, &ba[2]);
3908 }
3909 }
3910 }
3911 }
3912 for (LinkData &lip : root->rp) {
3913 for (lip2 = static_cast<LinkData *>((static_cast<LineartBoundingArea *>(lip.data))->lp.first_);
3914 lip2;
3915 lip2 = next_lip)
3916 {
3917 next_lip = lip2->next;
3918 tba = static_cast<LineartBoundingArea *>(lip2->data);
3919 if (tba == root) {
3921 &(static_cast<LineartBoundingArea *>(lip.data))->lp, lip2);
3922 if (ba[0].u > tba->b && ba[0].b < tba->u) {
3923 lineart_list_append_pointer_pool(&tba->lp, mph, &ba[0]);
3924 }
3925 if (ba[3].u > tba->b && ba[3].b < tba->u) {
3926 lineart_list_append_pointer_pool(&tba->lp, mph, &ba[3]);
3927 }
3928 }
3929 }
3930 }
3931 for (LinkData &lip : root->up) {
3932 for (lip2 = static_cast<LinkData *>((static_cast<LineartBoundingArea *>(lip.data))->bp.first_);
3933 lip2;
3934 lip2 = next_lip)
3935 {
3936 next_lip = lip2->next;
3937 tba = static_cast<LineartBoundingArea *>(lip2->data);
3938 if (tba == root) {
3940 &(static_cast<LineartBoundingArea *>(lip.data))->bp, lip2);
3941 if (ba[0].r > tba->l && ba[0].l < tba->r) {
3942 lineart_list_append_pointer_pool(&tba->up, mph, &ba[0]);
3943 }
3944 if (ba[1].r > tba->l && ba[1].l < tba->r) {
3945 lineart_list_append_pointer_pool(&tba->up, mph, &ba[1]);
3946 }
3947 }
3948 }
3949 }
3950 for (LinkData &lip : root->bp) {
3951 for (lip2 = static_cast<LinkData *>((static_cast<LineartBoundingArea *>(lip.data))->up.first_);
3952 lip2;
3953 lip2 = next_lip)
3954 {
3955 next_lip = lip2->next;
3956 tba = static_cast<LineartBoundingArea *>(lip2->data);
3957 if (tba == root) {
3959 &(static_cast<LineartBoundingArea *>(lip.data))->up, lip2);
3960 if (ba[2].r > tba->l && ba[2].l < tba->r) {
3961 lineart_list_append_pointer_pool(&tba->bp, mph, &ba[2]);
3962 }
3963 if (ba[3].r > tba->l && ba[3].l < tba->r) {
3964 lineart_list_append_pointer_pool(&tba->bp, mph, &ba[3]);
3965 }
3966 }
3967 }
3968 }
3969
3970 /* Finally clear parent's adjacent list. */
3971 root->lp.clear_no_delete();
3972 root->rp.clear_no_delete();
3973 root->up.clear_no_delete();
3974 root->bp.clear_no_delete();
3975}
3976
3978{
3979 if (root->child) {
3981 for (int i = 0; i < 4; i++) {
3983 }
3984 }
3985}
3986
3988{
3989 int total_tile_initial = ld->qtree.count_x * ld->qtree.count_y;
3990 int tiles_per_row = ld->qtree.count_x;
3991
3992 for (int row = 0; row < ld->qtree.count_y; row++) {
3993 for (int col = 0; col < ld->qtree.count_x; col++) {
3994 LineartBoundingArea *ba = &ld->qtree.initials[row * tiles_per_row + col];
3995 /* Link adjacent ones. */
3996 if (row) {
3998 &ba->up, &ld->render_data_pool, &ld->qtree.initials[(row - 1) * tiles_per_row + col]);
3999 }
4000 if (col) {
4002 &ba->lp, &ld->render_data_pool, &ld->qtree.initials[row * tiles_per_row + col - 1]);
4003 }
4004 if (row != ld->qtree.count_y - 1) {
4006 &ba->bp, &ld->render_data_pool, &ld->qtree.initials[(row + 1) * tiles_per_row + col]);
4007 }
4008 if (col != ld->qtree.count_x - 1) {
4010 &ba->rp, &ld->render_data_pool, &ld->qtree.initials[row * tiles_per_row + col + 1]);
4011 }
4012 }
4013 }
4014 for (int i = 0; i < total_tile_initial; i++) {
4016 }
4017}
4018
4024 LineartBoundingArea *root,
4025 int recursive_level)
4026{
4027 LineartBoundingArea *ba = static_cast<LineartBoundingArea *>(
4029 ba[0].l = root->cx;
4030 ba[0].r = root->r;
4031 ba[0].u = root->u;
4032 ba[0].b = root->cy;
4033 ba[0].cx = (ba[0].l + ba[0].r) / 2;
4034 ba[0].cy = (ba[0].u + ba[0].b) / 2;
4035
4036 ba[1].l = root->l;
4037 ba[1].r = root->cx;
4038 ba[1].u = root->u;
4039 ba[1].b = root->cy;
4040 ba[1].cx = (ba[1].l + ba[1].r) / 2;
4041 ba[1].cy = (ba[1].u + ba[1].b) / 2;
4042
4043 ba[2].l = root->l;
4044 ba[2].r = root->cx;
4045 ba[2].u = root->cy;
4046 ba[2].b = root->b;
4047 ba[2].cx = (ba[2].l + ba[2].r) / 2;
4048 ba[2].cy = (ba[2].u + ba[2].b) / 2;
4049
4050 ba[3].l = root->cx;
4051 ba[3].r = root->r;
4052 ba[3].u = root->cy;
4053 ba[3].b = root->b;
4054 ba[3].cx = (ba[3].l + ba[3].r) / 2;
4055 ba[3].cy = (ba[3].u + ba[3].b) / 2;
4056
4057 /* Init linked_triangles array and locks. */
4058 for (int i = 0; i < 4; i++) {
4061 ba[i].linked_triangles = MEM_new_array_zeroed<LineartTriangle *>(ba[i].max_triangle_count,
4062 "ba_linked_triangles");
4063 ba[i].linked_lines = MEM_new_array_zeroed<LineartEdge *>(ba[i].max_line_count,
4064 "ba_linked_lines");
4065 BLI_spin_init(&ba[i].lock);
4066 }
4067
4068 for (uint32_t i = 0; i < root->triangle_count; i++) {
4069 LineartTriangle *tri = root->linked_triangles[i];
4070
4071 double b[4];
4072 b[0] = std::min({tri->v[0]->fbcoord[0], tri->v[1]->fbcoord[0], tri->v[2]->fbcoord[0]});
4073 b[1] = std::max({tri->v[0]->fbcoord[0], tri->v[1]->fbcoord[0], tri->v[2]->fbcoord[0]});
4074 b[2] = std::max({tri->v[0]->fbcoord[1], tri->v[1]->fbcoord[1], tri->v[2]->fbcoord[1]});
4075 b[3] = std::min({tri->v[0]->fbcoord[1], tri->v[1]->fbcoord[1], tri->v[2]->fbcoord[1]});
4076
4077 /* Re-link triangles into child tiles, not doing intersection lines during this because this
4078 * batch of triangles are all tested with each other for intersections. */
4079 if (LRT_BOUND_AREA_CROSSES(b, &ba[0].l)) {
4081 ld, &ba[0], tri, b, 0, recursive_level + 1, false, nullptr);
4082 }
4083 if (LRT_BOUND_AREA_CROSSES(b, &ba[1].l)) {
4085 ld, &ba[1], tri, b, 0, recursive_level + 1, false, nullptr);
4086 }
4087 if (LRT_BOUND_AREA_CROSSES(b, &ba[2].l)) {
4089 ld, &ba[2], tri, b, 0, recursive_level + 1, false, nullptr);
4090 }
4091 if (LRT_BOUND_AREA_CROSSES(b, &ba[3].l)) {
4093 ld, &ba[3], tri, b, 0, recursive_level + 1, false, nullptr);
4094 }
4095 }
4096
4097 /* At this point the child tiles are fully initialized and it's safe for new triangles to be
4098 * inserted, so assign root->child for #lineart_bounding_area_link_triangle to use. */
4099 root->child = ba;
4100}
4101
4103 const double l[2],
4104 const double r[2],
4106{
4107 double dx, dy;
4108 double converted[4];
4109 double c1, c;
4110
4111 if (((converted[0] = ba->l) > std::max(l[0], r[0])) ||
4112 ((converted[1] = ba->r) < std::min(l[0], r[0])) ||
4113 ((converted[2] = ba->b) > std::max(l[1], r[1])) ||
4114 ((converted[3] = ba->u) < std::min(l[1], r[1])))
4115 {
4116 return false;
4117 }
4118
4119 dx = l[0] - r[0];
4120 dy = l[1] - r[1];
4121
4122 c1 = dx * (converted[2] - l[1]) - dy * (converted[0] - l[0]);
4123 c = c1;
4124
4125 c1 = dx * (converted[2] - l[1]) - dy * (converted[1] - l[0]);
4126 if (c1 * c <= 0) {
4127 return true;
4128 }
4129 c = c1;
4130
4131 c1 = dx * (converted[3] - l[1]) - dy * (converted[0] - l[0]);
4132 if (c1 * c <= 0) {
4133 return true;
4134 }
4135 c = c1;
4136
4137 c1 = dx * (converted[3] - l[1]) - dy * (converted[1] - l[0]);
4138 if (c1 * c <= 0) {
4139 return true;
4140 }
4141 c = c1;
4142
4143 return false;
4144}
4145
4147 LineartTriangle *tri,
4149 bool *r_triangle_vert_inside)
4150{
4151 double p1[2], p2[2], p3[2], p4[2];
4152 double *FBC1 = tri->v[0]->fbcoord, *FBC2 = tri->v[1]->fbcoord, *FBC3 = tri->v[2]->fbcoord;
4153
4154 p3[0] = p1[0] = ba->l;
4155 p2[1] = p1[1] = ba->b;
4156 p2[0] = p4[0] = ba->r;
4157 p3[1] = p4[1] = ba->u;
4158
4159 if ((FBC1[0] >= p1[0] && FBC1[0] <= p2[0] && FBC1[1] >= p1[1] && FBC1[1] <= p3[1]) ||
4160 (FBC2[0] >= p1[0] && FBC2[0] <= p2[0] && FBC2[1] >= p1[1] && FBC2[1] <= p3[1]) ||
4161 (FBC3[0] >= p1[0] && FBC3[0] <= p2[0] && FBC3[1] >= p1[1] && FBC3[1] <= p3[1]))
4162 {
4163 *r_triangle_vert_inside = true;
4164 return true;
4165 }
4166
4167 *r_triangle_vert_inside = false;
4168
4169 if (lineart_point_inside_triangle(p1, FBC1, FBC2, FBC3) ||
4170 lineart_point_inside_triangle(p2, FBC1, FBC2, FBC3) ||
4171 lineart_point_inside_triangle(p3, FBC1, FBC2, FBC3) ||
4172 lineart_point_inside_triangle(p4, FBC1, FBC2, FBC3))
4173 {
4174 return true;
4175 }
4176
4177 if (lineart_bounding_area_edge_intersect(fb, FBC1, FBC2, ba) ||
4178 lineart_bounding_area_edge_intersect(fb, FBC2, FBC3, ba) ||
4180 {
4181 return true;
4182 }
4183
4184 return false;
4185}
4186
4200 LineartBoundingArea *root_ba,
4201 LineartTriangle *tri,
4202 double l_r_u_b[4],
4203 int recursive,
4204 int recursive_level,
4205 bool do_intersection,
4207{
4208 bool triangle_vert_inside;
4209 if (!lineart_bounding_area_triangle_intersect(ld, tri, root_ba, &triangle_vert_inside)) {
4210 return;
4211 }
4212
4213 LineartBoundingArea *old_ba = root_ba;
4214
4215 if (old_ba->child) {
4216 /* If old_ba->child is not nullptr, then tile splitting is fully finished, safe to directly
4217 * insert into child tiles. */
4218 double *B1 = l_r_u_b;
4219 double b[4];
4220 if (!l_r_u_b) {
4221 b[0] = std::min({tri->v[0]->fbcoord[0], tri->v[1]->fbcoord[0], tri->v[2]->fbcoord[0]});
4222 b[1] = std::max({tri->v[0]->fbcoord[0], tri->v[1]->fbcoord[0], tri->v[2]->fbcoord[0]});
4223 b[2] = std::max({tri->v[0]->fbcoord[1], tri->v[1]->fbcoord[1], tri->v[2]->fbcoord[1]});
4224 b[3] = std::min({tri->v[0]->fbcoord[1], tri->v[1]->fbcoord[1], tri->v[2]->fbcoord[1]});
4225 B1 = b;
4226 }
4227 for (int iba = 0; iba < 4; iba++) {
4228 if (LRT_BOUND_AREA_CROSSES(B1, &old_ba->child[iba].l)) {
4230 ld, &old_ba->child[iba], tri, B1, recursive, recursive_level + 1, do_intersection, th);
4231 }
4232 }
4233 return;
4234 }
4235
4236 /* When splitting tiles, triangles are relinked into new tiles by a single thread, #th is nullptr
4237 * in that situation. */
4238 if (th) {
4239 BLI_spin_lock(&old_ba->lock);
4240 }
4241
4242 /* If there are still space left in this tile for insertion. */
4243 if (old_ba->triangle_count < old_ba->max_triangle_count) {
4244 const uint32_t old_tri_count = old_ba->triangle_count;
4245
4246 old_ba->linked_triangles[old_tri_count] = tri;
4247
4248 if (triangle_vert_inside) {
4249 old_ba->insider_triangle_count++;
4250 }
4251 old_ba->triangle_count++;
4252
4253 /* Do intersections in place. */
4254 if (do_intersection && ld->conf.use_intersections) {
4255 lineart_triangle_intersect_in_bounding_area(tri, old_ba, th, old_tri_count);
4256 }
4257
4258 if (th) {
4259 BLI_spin_unlock(&old_ba->lock);
4260 }
4261 }
4262 else { /* We need to wait for either splitting or array extension to be done. */
4263
4264 if (recursive_level < ld->qtree.recursive_level &&
4266 {
4267 if (!old_ba->child) {
4268 /* old_ba->child==nullptr, means we are the thread that's doing the splitting. */
4269 lineart_bounding_area_split(ld, old_ba, recursive_level);
4270 } /* Otherwise other thread has completed the splitting process. */
4271 }
4272 else {
4273 if (old_ba->triangle_count == old_ba->max_triangle_count) {
4274 /* Means we are the thread that's doing the extension. */
4276 } /* Otherwise other thread has completed the extending the array. */
4277 }
4278
4279 /* Unlock before going into recursive call. */
4280 if (th) {
4281 BLI_spin_unlock(&old_ba->lock);
4282 }
4283
4284 /* Of course we still have our own triangle needs to be added. */
4286 ld, root_ba, tri, l_r_u_b, recursive, recursive_level, do_intersection, th);
4287 }
4288}
4289
4291{
4292 BLI_spin_end(&ba->lock);
4293 if (ba->linked_lines) {
4294 MEM_delete(ba->linked_lines);
4295 }
4296 if (ba->linked_triangles) {
4297 MEM_delete(ba->linked_triangles);
4298 }
4299 if (recursive && ba->child) {
4300 for (int i = 0; i < 4; i++) {
4301 lineart_free_bounding_area_memory(&ba->child[i], recursive);
4302 }
4303 }
4304}
4306{
4307 for (int i = 0; i < ld->qtree.count_y; i++) {
4308 for (int j = 0; j < ld->qtree.count_x; j++) {
4310 }
4311 }
4312}
4313
4315 LineartBoundingArea *root_ba,
4316 LineartEdge *e)
4317{
4318 if (root_ba->child == nullptr) {
4320 }
4321 else {
4323 ld, e->v1->fbcoord, e->v2->fbcoord, &root_ba->child[0]))
4324 {
4325 lineart_bounding_area_link_edge(ld, &root_ba->child[0], e);
4326 }
4328 ld, e->v1->fbcoord, e->v2->fbcoord, &root_ba->child[1]))
4329 {
4330 lineart_bounding_area_link_edge(ld, &root_ba->child[1], e);
4331 }
4333 ld, e->v1->fbcoord, e->v2->fbcoord, &root_ba->child[2]))
4334 {
4335 lineart_bounding_area_link_edge(ld, &root_ba->child[2], e);
4336 }
4338 ld, e->v1->fbcoord, e->v2->fbcoord, &root_ba->child[3]))
4339 {
4340 lineart_bounding_area_link_edge(ld, &root_ba->child[3], e);
4341 }
4342 }
4343}
4344
4346{
4347 if (root_ba->child) {
4348 for (int i = 0; i < 4; i++) {
4350 }
4351 }
4352 if (root_ba->linked_lines) {
4353 MEM_delete(root_ba->linked_lines);
4354 }
4355 root_ba->line_count = 0;
4356 root_ba->max_line_count = 128;
4358 "cleared lineart edges");
4359}
4361{
4363 for (int i = 0; i < ld->qtree.count_y; i++) {
4364 for (int j = 0; j < ld->qtree.count_x; j++) {
4366 }
4367 }
4368}
4369
4371{
4373 {
4374 int r1, r2, c1, c2, row, col;
4375 if (lineart_get_edge_bounding_areas(ld, e, &r1, &r2, &c1, &c2)) {
4376 for (row = r1; row != r2 + 1; row++) {
4377 for (col = c1; col != c2 + 1; col++) {
4379 ld, &ld->qtree.initials[row * ld->qtree.count_x + col], e);
4380 }
4381 }
4382 }
4383 }
4385}
4386
4388 uint8_t max_occlusion)
4389{
4390 if (ba->child) {
4391 for (int i = 0; i < 4; i++) {
4392 lineart_main_remove_unused_lines_recursive(&ba->child[i], max_occlusion);
4393 }
4394 return;
4395 }
4396
4397 if (!ba->line_count) {
4398 return;
4399 }
4400
4401 int usable_count = 0;
4402 for (int i = 0; i < ba->line_count; i++) {
4403 LineartEdge *e = ba->linked_lines[i];
4404 if (e->min_occ > max_occlusion) {
4405 continue;
4406 }
4407 usable_count++;
4408 }
4409
4410 if (!usable_count) {
4411 ba->line_count = 0;
4412 return;
4413 }
4414
4415 LineartEdge **new_array = MEM_new_array_zeroed<LineartEdge *>(usable_count,
4416 "cleaned lineart edge array");
4417
4418 int new_i = 0;
4419 for (int i = 0; i < ba->line_count; i++) {
4420 LineartEdge *e = ba->linked_lines[i];
4421 if (e->min_occ > max_occlusion) {
4422 continue;
4423 }
4424 new_array[new_i] = e;
4425 new_i++;
4426 }
4427
4428 MEM_delete(ba->linked_lines);
4429 ba->linked_lines = new_array;
4430 ba->max_line_count = ba->line_count = usable_count;
4431}
4432
4434{
4435 for (int row = 0; row < ld->qtree.count_y; row++) {
4436 for (int col = 0; col < ld->qtree.count_x; col++) {
4438 &ld->qtree.initials[row * ld->qtree.count_x + col], ld->conf.max_occlusion_level);
4439 }
4440 }
4441}
4442
4444 LineartData *ld, LineartTriangle *tri, int *rowbegin, int *rowend, int *colbegin, int *colend)
4445{
4446 double sp_w = ld->qtree.tile_width, sp_h = ld->qtree.tile_height;
4447 double b[4];
4448
4449 if (!tri->v[0] || !tri->v[1] || !tri->v[2]) {
4450 return false;
4451 }
4452
4453 b[0] = std::min({tri->v[0]->fbcoord[0], tri->v[1]->fbcoord[0], tri->v[2]->fbcoord[0]});
4454 b[1] = std::max({tri->v[0]->fbcoord[0], tri->v[1]->fbcoord[0], tri->v[2]->fbcoord[0]});
4455 b[2] = std::min({tri->v[0]->fbcoord[1], tri->v[1]->fbcoord[1], tri->v[2]->fbcoord[1]});
4456 b[3] = std::max({tri->v[0]->fbcoord[1], tri->v[1]->fbcoord[1], tri->v[2]->fbcoord[1]});
4457
4458 if (b[0] > 1 || b[1] < -1 || b[2] > 1 || b[3] < -1) {
4459 return false;
4460 }
4461
4462 (*colbegin) = int((b[0] + 1.0) / sp_w);
4463 (*colend) = int((b[1] + 1.0) / sp_w);
4464 (*rowend) = ld->qtree.count_y - int((b[2] + 1.0) / sp_h) - 1;
4465 (*rowbegin) = ld->qtree.count_y - int((b[3] + 1.0) / sp_h) - 1;
4466
4467 if ((*colend) >= ld->qtree.count_x) {
4468 (*colend) = ld->qtree.count_x - 1;
4469 }
4470 if ((*rowend) >= ld->qtree.count_y) {
4471 (*rowend) = ld->qtree.count_y - 1;
4472 }
4473 *colbegin = std::max(*colbegin, 0);
4474 *rowbegin = std::max(*rowbegin, 0);
4475
4476 return true;
4477}
4478
4480 LineartData *ld, LineartEdge *e, int *rowbegin, int *rowend, int *colbegin, int *colend)
4481{
4482 double sp_w = ld->qtree.tile_width, sp_h = ld->qtree.tile_height;
4483 double b[4];
4484
4485 if (!e->v1 || !e->v2) {
4486 return false;
4487 }
4488
4489 if (e->v1->fbcoord[0] != e->v1->fbcoord[0] || e->v2->fbcoord[0] != e->v2->fbcoord[0]) {
4490 return false;
4491 }
4492
4493 b[0] = std::min(e->v1->fbcoord[0], e->v2->fbcoord[0]);
4494 b[1] = std::max(e->v1->fbcoord[0], e->v2->fbcoord[0]);
4495 b[2] = std::min(e->v1->fbcoord[1], e->v2->fbcoord[1]);
4496 b[3] = std::max(e->v1->fbcoord[1], e->v2->fbcoord[1]);
4497
4498 if (b[0] > 1 || b[1] < -1 || b[2] > 1 || b[3] < -1) {
4499 return false;
4500 }
4501
4502 (*colbegin) = int((b[0] + 1.0) / sp_w);
4503 (*colend) = int((b[1] + 1.0) / sp_w);
4504 (*rowend) = ld->qtree.count_y - int((b[2] + 1.0) / sp_h) - 1;
4505 (*rowbegin) = ld->qtree.count_y - int((b[3] + 1.0) / sp_h) - 1;
4506
4507 /* It's possible that the line stretches too much out to the side, resulting negative value. */
4508 if ((*rowend) < (*rowbegin)) {
4509 (*rowend) = ld->qtree.count_y - 1;
4510 }
4511
4512 if ((*colend) < (*colbegin)) {
4513 (*colend) = ld->qtree.count_x - 1;
4514 }
4515
4516 CLAMP((*colbegin), 0, ld->qtree.count_x - 1);
4517 CLAMP((*rowbegin), 0, ld->qtree.count_y - 1);
4518 CLAMP((*colend), 0, ld->qtree.count_x - 1);
4519 CLAMP((*rowend), 0, ld->qtree.count_y - 1);
4520
4521 return true;
4522}
4523
4525{
4526 double sp_w = ld->qtree.tile_width, sp_h = ld->qtree.tile_height;
4527 int col, row;
4528
4529 if (x > 1 || x < -1 || y > 1 || y < -1) {
4530 return nullptr;
4531 }
4532
4533 col = int((x + 1.0) / sp_w);
4534 row = ld->qtree.count_y - int((y + 1.0) / sp_h) - 1;
4535
4536 if (col >= ld->qtree.count_x) {
4537 col = ld->qtree.count_x - 1;
4538 }
4539 if (row >= ld->qtree.count_y) {
4540 row = ld->qtree.count_y - 1;
4541 }
4542 col = std::max(col, 0);
4543 row = std::max(row, 0);
4544
4545 return &ld->qtree.initials[row * ld->qtree.count_x + col];
4546}
4547
4549{
4551 double sp_w = ld->qtree.tile_width, sp_h = ld->qtree.tile_height;
4552 int c = int((x + 1.0) / sp_w);
4553 int r = ld->qtree.count_y - int((y + 1.0) / sp_h) - 1;
4554 r = std::max(r, 0);
4555 c = std::max(c, 0);
4556 if (r >= ld->qtree.count_y) {
4557 r = ld->qtree.count_y - 1;
4558 }
4559 if (c >= ld->qtree.count_x) {
4560 c = ld->qtree.count_x - 1;
4561 }
4562
4563 iba = &ld->qtree.initials[r * ld->qtree.count_x + c];
4564 while (iba->child) {
4565 if (x > iba->cx) {
4566 if (y > iba->cy) {
4567 iba = &iba->child[0];
4568 }
4569 else {
4570 iba = &iba->child[3];
4571 }
4572 }
4573 else {
4574 if (y > iba->cy) {
4575 iba = &iba->child[1];
4576 }
4577 else {
4578 iba = &iba->child[2];
4579 }
4580 }
4581 }
4582 return iba;
4583}
4584
4586{
4588 if ((ba = MOD_lineart_get_parent_bounding_area(ld, x, y)) != nullptr) {
4589 return lineart_get_bounding_area(ld, x, y);
4590 }
4591 return nullptr;
4592}
4593
4594static void lineart_add_triangles_worker(TaskPool *__restrict /*pool*/, LineartIsecThread *th)
4595{
4596 LineartData *ld = th->ld;
4597 // int _dir_control = 0; /* UNUSED */
4599 for (LineartElementLinkNode *eln = th->pending_from; eln != th->pending_to->next;
4600 eln = eln->next)
4601 {
4602 int index_start = eln == th->pending_from ? th->index_from : 0;
4603 int index_end = eln == th->pending_to ? th->index_to : eln->element_count;
4604 LineartTriangle *tri = static_cast<LineartTriangle *>(static_cast<void *>(
4605 (static_cast<uchar *>(eln->pointer)) + size_t(ld->sizeof_triangle) * index_start));
4606 for (int ei = index_start; ei < index_end; ei++) {
4607 int x1, x2, y1, y2;
4608 int r, co;
4609 if ((tri->flags & LRT_CULL_USED) || (tri->flags & LRT_CULL_DISCARD)) {
4610 tri = static_cast<LineartTriangle *>(
4611 static_cast<void *>((reinterpret_cast<uchar *>(tri)) + ld->sizeof_triangle));
4612 continue;
4613 }
4614 if (lineart_get_triangle_bounding_areas(ld, tri, &y1, &y2, &x1, &x2)) {
4615 // _dir_control++;
4616 for (co = x1; co <= x2; co++) {
4617 for (r = y1; r <= y2; r++) {
4619 &ld->qtree.initials[r * ld->qtree.count_x + co],
4620 tri,
4621 nullptr,
4622 1,
4623 0,
4624 true,
4625 th);
4626 }
4627 }
4628 } /* Else throw away. */
4629 tri = static_cast<LineartTriangle *>(
4630 static_cast<void *>((reinterpret_cast<uchar *>(tri)) + ld->sizeof_triangle));
4631 }
4632 }
4633 }
4634}
4635
4637{
4638 LineartData *ld = d->ld;
4639 double ZMax = ld->conf.far_clip;
4640 double ZMin = ld->conf.near_clip;
4641 int total_lines = 0;
4642
4643 for (int i = 0; i < d->thread_count; i++) {
4644 LineartIsecThread *th = &d->threads[i];
4645 if (G.debug_value == 4000) {
4646 printf("Thread %d isec generated %d lines.\n", i, th->current);
4647 }
4648 if (!th->current) {
4649 continue;
4650 }
4651 total_lines += th->current;
4652 }
4653
4654 if (!total_lines) {
4655 return;
4656 }
4657
4658 /* We don't care about removing duplicated vert in this method, chaining can handle that,
4659 * and it saves us from using locks and look up tables. */
4660 LineartVert *v = static_cast<LineartVert *>(
4661 lineart_mem_acquire(ld->edge_data_pool, sizeof(LineartVert) * total_lines * 2));
4662 LineartEdge *e = static_cast<LineartEdge *>(
4663 lineart_mem_acquire(ld->edge_data_pool, sizeof(LineartEdge) * total_lines));
4664 LineartEdgeSegment *es = static_cast<LineartEdgeSegment *>(
4665 lineart_mem_acquire(ld->edge_data_pool, sizeof(LineartEdgeSegment) * total_lines));
4666
4667 LineartElementLinkNode *eln = static_cast<LineartElementLinkNode *>(
4669 eln->element_count = total_lines;
4670 eln->pointer = e;
4673
4674 for (int i = 0; i < d->thread_count; i++) {
4675 LineartIsecThread *th = &d->threads[i];
4676 if (!th->current) {
4677 continue;
4678 }
4679
4680 for (int j = 0; j < th->current; j++) {
4681 LineartIsecSingle *is = &th->array[j];
4682 LineartVert *v1 = v;
4683 LineartVert *v2 = v + 1;
4684 copy_v3_v3_db(v1->gloc, is->v1);
4685 copy_v3_v3_db(v2->gloc, is->v2);
4686 /* The intersection line has been generated only in geometry space, so we need to transform
4687 * them as well. */
4689 mul_v4_m4v3_db(v2->fbcoord, ld->conf.view_projection, v2->gloc);
4690 mul_v3db_db(v1->fbcoord, (1 / v1->fbcoord[3]));
4691 mul_v3db_db(v2->fbcoord, (1 / v2->fbcoord[3]));
4692
4693 v1->fbcoord[0] -= ld->conf.shift_x * 2;
4694 v1->fbcoord[1] -= ld->conf.shift_y * 2;
4695 v2->fbcoord[0] -= ld->conf.shift_x * 2;
4696 v2->fbcoord[1] -= ld->conf.shift_y * 2;
4697
4698 /* This z transformation is not the same as the rest of the part, because the data don't go
4699 * through normal perspective division calls in the pipeline, but this way the 3D result and
4700 * occlusion on the generated line is correct, and we don't really use 2D for viewport stroke
4701 * generation anyway. */
4702 v1->fbcoord[2] = ZMin * ZMax / (ZMax - fabs(v1->fbcoord[2]) * (ZMax - ZMin));
4703 v2->fbcoord[2] = ZMin * ZMax / (ZMax - fabs(v2->fbcoord[2]) * (ZMax - ZMin));
4704 e->v1 = v1;
4705 e->v2 = v2;
4706 e->t1 = is->tri1;
4707 e->t2 = is->tri2;
4708 /* This is so we can also match intersection edges from shadow to later viewing stage. */
4709 e->edge_identifier = (uint64_t(e->t1->target_reference) << 32) | e->t2->target_reference;
4711 e->intersection_mask = (is->tri1->intersection_mask | is->tri2->intersection_mask);
4712 BLI_addtail(&e->segments, es);
4713
4714 int obi1 = (e->t1->target_reference & LRT_OBINDEX_HIGHER);
4715 int obi2 = (e->t2->target_reference & LRT_OBINDEX_HIGHER);
4717 obi1);
4718 LineartElementLinkNode *eln2 = obi1 == obi2 ? eln1 :
4720 &ld->geom.line_buffer_pointers, obi2);
4721 Object *ob1 = eln1 ? static_cast<Object *>(eln1->object_ref) : nullptr;
4722 Object *ob2 = eln2 ? static_cast<Object *>(eln2->object_ref) : nullptr;
4723 if (e->t1->intersection_priority >= e->t2->intersection_priority) {
4724 /* `object_ref` should be ambiguous if intersection lines comes from different objects with
4725 * the same priority. */
4726 e->object_ref = ob1;
4727 }
4728 else if (e->t1->intersection_priority < e->t2->intersection_priority) {
4729 e->object_ref = ob2;
4730 }
4731
4733
4734 v += 2;
4735 e++;
4736 es++;
4737 }
4738 }
4739}
4740
4742{
4743 double t_start;
4744 if (G.debug_value == 4000) {
4745 t_start = BLI_time_now_seconds();
4746 }
4747
4748 /* Initialize per-thread data for thread task scheduling information and storing intersection
4749 * results. */
4750 LineartIsecData d = {nullptr};
4752
4754 for (int i = 0; i < ld->thread_count; i++) {
4757 &d.threads[i],
4758 false,
4759 nullptr);
4760 }
4763
4764 if (ld->conf.use_intersections) {
4766 }
4767
4769
4770 if (G.debug_value == 4000) {
4771 double t_elapsed = BLI_time_now_seconds() - t_start;
4772 printf("Line art intersection time: %f\n", t_elapsed);
4773 }
4774}
4775
4777 double *fbcoord1,
4778 double *fbcoord2)
4779{
4780 double data[2] = {fbcoord1[0], fbcoord1[1]};
4781 double LU[2] = {-1, 1}, RU[2] = {1, 1}, LB[2] = {-1, -1}, RB[2] = {1, -1};
4782 double r = 1, sr = 1;
4783 bool p_unused;
4784
4785 if (data[0] > -1 && data[0] < 1 && data[1] > -1 && data[1] < 1) {
4786 return lineart_get_bounding_area(ld, data[0], data[1]);
4787 }
4788
4789 if (lineart_intersect_seg_seg(fbcoord1, fbcoord2, LU, RU, &sr, &p_unused) && sr < r && sr > 0) {
4790 r = sr;
4791 }
4792 if (lineart_intersect_seg_seg(fbcoord1, fbcoord2, LB, RB, &sr, &p_unused) && sr < r && sr > 0) {
4793 r = sr;
4794 }
4795 if (lineart_intersect_seg_seg(fbcoord1, fbcoord2, LB, LU, &sr, &p_unused) && sr < r && sr > 0) {
4796 r = sr;
4797 }
4798 if (lineart_intersect_seg_seg(fbcoord1, fbcoord2, RB, RU, &sr, &p_unused) && sr < r && sr > 0) {
4799 r = sr;
4800 }
4801 interp_v2_v2v2_db(data, fbcoord1, fbcoord2, r);
4802
4803 return lineart_get_bounding_area(ld, data[0], data[1]);
4804}
4805
4807 double *fbcoord1,
4808 double *fbcoord2,
4809 double x,
4810 double y,
4811 double k,
4812 int positive_x,
4813 int positive_y,
4814 double *next_x,
4815 double *next_y)
4816{
4817 double rx, ry, ux, uy, lx, ly, bx, by;
4818 double r1, r2;
4820
4821 /* If we are marching towards the right. */
4822 if (positive_x > 0) {
4823 rx = self->r;
4824 ry = y + k * (rx - x);
4825
4826 /* If we are marching towards the top. */
4827 if (positive_y > 0) {
4828 uy = self->u;
4829 ux = x + (uy - y) / k;
4830 r1 = ratiod(fbcoord1[0], fbcoord2[0], rx);
4831 r2 = ratiod(fbcoord1[0], fbcoord2[0], ux);
4832 if (std::min(r1, r2) > 1) {
4833 return nullptr;
4834 }
4835
4836 /* We reached the right side before the top side. */
4837 if (r1 <= r2) {
4838 for (LinkData &lip : self->rp) {
4839 ba = static_cast<LineartBoundingArea *>(lip.data);
4840 if (ba->u >= ry && ba->b < ry) {
4841 *next_x = rx;
4842 *next_y = ry;
4843 return ba;
4844 }
4845 }
4846 }
4847 /* We reached the top side before the right side. */
4848 else {
4849 for (LinkData &lip : self->up) {
4850 ba = static_cast<LineartBoundingArea *>(lip.data);
4851 if (ba->r >= ux && ba->l < ux) {
4852 *next_x = ux;
4853 *next_y = uy;
4854 return ba;
4855 }
4856 }
4857 }
4858 }
4859 /* If we are marching towards the bottom. */
4860 else if (positive_y < 0) {
4861 by = self->b;
4862 bx = x + (by - y) / k;
4863 r1 = ratiod(fbcoord1[0], fbcoord2[0], rx);
4864 r2 = ratiod(fbcoord1[0], fbcoord2[0], bx);
4865 if (std::min(r1, r2) > 1) {
4866 return nullptr;
4867 }
4868 if (r1 <= r2) {
4869 for (LinkData &lip : self->rp) {
4870 ba = static_cast<LineartBoundingArea *>(lip.data);
4871 if (ba->u >= ry && ba->b < ry) {
4872 *next_x = rx;
4873 *next_y = ry;
4874 return ba;
4875 }
4876 }
4877 }
4878 else {
4879 for (LinkData &lip : self->bp) {
4880 ba = static_cast<LineartBoundingArea *>(lip.data);
4881 if (ba->r >= bx && ba->l < bx) {
4882 *next_x = bx;
4883 *next_y = by;
4884 return ba;
4885 }
4886 }
4887 }
4888 }
4889 /* If the line is completely horizontal, in which Y difference == 0. */
4890 else {
4891 r1 = ratiod(fbcoord1[0], fbcoord2[0], self->r);
4892 if (r1 > 1) {
4893 return nullptr;
4894 }
4895 for (LinkData &lip : self->rp) {
4896 ba = static_cast<LineartBoundingArea *>(lip.data);
4897 if (ba->u >= y && ba->b < y) {
4898 *next_x = self->r;
4899 *next_y = y;
4900 return ba;
4901 }
4902 }
4903 }
4904 }
4905
4906 /* If we are marching towards the left. */
4907 else if (positive_x < 0) {
4908 lx = self->l;
4909 ly = y + k * (lx - x);
4910
4911 /* If we are marching towards the top. */
4912 if (positive_y > 0) {
4913 uy = self->u;
4914 ux = x + (uy - y) / k;
4915 r1 = ratiod(fbcoord1[0], fbcoord2[0], lx);
4916 r2 = ratiod(fbcoord1[0], fbcoord2[0], ux);
4917 if (std::min(r1, r2) > 1) {
4918 return nullptr;
4919 }
4920 if (r1 <= r2) {
4921 for (LinkData &lip : self->lp) {
4922 ba = static_cast<LineartBoundingArea *>(lip.data);
4923 if (ba->u >= ly && ba->b < ly) {
4924 *next_x = lx;
4925 *next_y = ly;
4926 return ba;
4927 }
4928 }
4929 }
4930 else {
4931 for (LinkData &lip : self->up) {
4932 ba = static_cast<LineartBoundingArea *>(lip.data);
4933 if (ba->r >= ux && ba->l < ux) {
4934 *next_x = ux;
4935 *next_y = uy;
4936 return ba;
4937 }
4938 }
4939 }
4940 }
4941
4942 /* If we are marching towards the bottom. */
4943 else if (positive_y < 0) {
4944 by = self->b;
4945 bx = x + (by - y) / k;
4946 r1 = ratiod(fbcoord1[0], fbcoord2[0], lx);
4947 r2 = ratiod(fbcoord1[0], fbcoord2[0], bx);
4948 if (std::min(r1, r2) > 1) {
4949 return nullptr;
4950 }
4951 if (r1 <= r2) {
4952 for (LinkData &lip : self->lp) {
4953 ba = static_cast<LineartBoundingArea *>(lip.data);
4954 if (ba->u >= ly && ba->b < ly) {
4955 *next_x = lx;
4956 *next_y = ly;
4957 return ba;
4958 }
4959 }
4960 }
4961 else {
4962 for (LinkData &lip : self->bp) {
4963 ba = static_cast<LineartBoundingArea *>(lip.data);
4964 if (ba->r >= bx && ba->l < bx) {
4965 *next_x = bx;
4966 *next_y = by;
4967 return ba;
4968 }
4969 }
4970 }
4971 }
4972 /* Again, horizontal. */
4973 else {
4974 r1 = ratiod(fbcoord1[0], fbcoord2[0], self->l);
4975 if (r1 > 1) {
4976 return nullptr;
4977 }
4978 for (LinkData &lip : self->lp) {
4979 ba = static_cast<LineartBoundingArea *>(lip.data);
4980 if (ba->u >= y && ba->b < y) {
4981 *next_x = self->l;
4982 *next_y = y;
4983 return ba;
4984 }
4985 }
4986 }
4987 }
4988 /* If the line is completely vertical, hence X difference == 0. */
4989 else {
4990 if (positive_y > 0) {
4991 r1 = ratiod(fbcoord1[1], fbcoord2[1], self->u);
4992 if (r1 > 1) {
4993 return nullptr;
4994 }
4995 for (LinkData &lip : self->up) {
4996 ba = static_cast<LineartBoundingArea *>(lip.data);
4997 if (ba->r > x && ba->l <= x) {
4998 *next_x = x;
4999 *next_y = self->u;
5000 return ba;
5001 }
5002 }
5003 }
5004 else if (positive_y < 0) {
5005 r1 = ratiod(fbcoord1[1], fbcoord2[1], self->b);
5006 if (r1 > 1) {
5007 return nullptr;
5008 }
5009 for (LinkData &lip : self->bp) {
5010 ba = static_cast<LineartBoundingArea *>(lip.data);
5011 if (ba->r > x && ba->l <= x) {
5012 *next_x = x;
5013 *next_y = self->b;
5014 return ba;
5015 }
5016 }
5017 }
5018 else {
5019 /* Segment has no length. */
5020 return nullptr;
5021 }
5022 }
5023 return nullptr;
5024}
5025
5028 LineartCache **cached_result,
5029 bool enable_stroke_depth_offset)
5030{
5031 LineartData *ld;
5032 Scene *scene = DEG_get_evaluated_scene(depsgraph);
5033 int intersections_only = 0; /* Not used right now, but preserve for future. */
5034 Object *lineart_camera = nullptr;
5035
5036 double t_start;
5037 if (G.debug_value == 4000) {
5038 t_start = BLI_time_now_seconds();
5039 }
5040
5041 bool use_render_camera_override = false;
5043 if (!lmd.source_camera ||
5044 (lineart_camera = DEG_get_evaluated(depsgraph, lmd.source_camera))->type != OB_CAMERA)
5045 {
5046 return false;
5047 }
5048 }
5049 else {
5051 if (render && render->camera_override) {
5052 lineart_camera = DEG_get_evaluated(depsgraph, render->camera_override);
5053 use_render_camera_override = true;
5054 }
5055 if (!lineart_camera) {
5057 if (!scene->camera) {
5058 return false;
5059 }
5060 lineart_camera = scene->camera;
5061 }
5062 }
5063
5064 if (lineart_camera->type != OB_CAMERA) {
5065 return false;
5066 }
5067
5068 LineartCache *lc = *cached_result;
5069 if (!lc) {
5071 *cached_result = lc;
5072 }
5073
5075 &lmd,
5076 lineart_camera,
5077 use_render_camera_override ? lineart_camera : scene->camera,
5078 lc);
5079
5080 /* Triangle thread testing data size varies depending on the thread count.
5081 * See definition of LineartTriangleThread for details. */
5083
5084 LineartData *shadow_rb = nullptr;
5085 LineartElementLinkNode *shadow_veln, *shadow_eeln;
5086 ListBaseT<LineartElementLinkNode> *shadow_elns = ld->conf.shadow_selection ? &lc->shadow_elns :
5087 nullptr;
5088 bool shadow_generated = lineart_main_try_generate_shadow_v3(depsgraph,
5089 scene,
5090 ld,
5091 &lmd,
5092 &lc->shadow_data_pool,
5093 &shadow_veln,
5094 &shadow_eeln,
5095 shadow_elns,
5096 &shadow_rb);
5097
5098 /* Get view vector before loading geometries, because we detect feature lines there. */
5100
5101 LineartModifierRuntime *runtime = reinterpret_cast<LineartModifierRuntime *>(lmd.runtime);
5102 Set<const Object *> *included_objects = runtime ? &runtime->object_dependencies : nullptr;
5103
5105 scene,
5106 lineart_camera,
5107 ld,
5109 false,
5110 shadow_elns,
5111 included_objects);
5112
5113 if (shadow_generated) {
5114 lineart_main_transform_and_add_shadow(ld, shadow_veln, shadow_eeln);
5115 }
5116
5117 if (!ld->geom.vertex_buffer_pointers.first_) {
5118 /* No geometry loaded, return early. */
5119 return true;
5120 }
5121
5122 /* Initialize the bounding box acceleration structure, it's a lot like BVH in 3D. */
5124
5125 /* We need to get cut into triangles that are crossing near/far plans, only this way can we get
5126 * correct coordinates of those clipped lines. Done in two steps,
5127 * setting clip_far==false for near plane. */
5128 lineart_main_cull_triangles(ld, false);
5129 /* `clip_far == true` for far plane. */
5131
5132 /* At this point triangle adjacent info pointers is no longer needed, free them. */
5134
5135 /* Do the perspective division after clipping is done. */
5137
5139
5140 /* Triangle intersections are done here during sequential adding of them. Only after this,
5141 * triangles and lines are all linked with acceleration structure, and the 2D occlusion stage
5142 * can do its job. */
5144
5145 /* Add shadow cuts to intersection lines as well. */
5147
5148 /* Re-link bounding areas because they have been subdivided by worker threads and we need
5149 * adjacent info. */
5151
5152 /* Link lines to acceleration structure, this can only be done after perspective division, if
5153 * we do it after triangles being added, the acceleration structure has already been
5154 * subdivided, this way we do less list manipulations. */
5156
5157 /* "intersection_only" is preserved for being called in a standalone fashion.
5158 * If so the data will already be available at the stage. Otherwise we do the occlusion and
5159 * chaining etc. */
5160
5161 if (!intersections_only) {
5162
5163 /* Occlusion is work-and-wait. This call will not return before work is completed. */
5165
5166 lineart_main_make_enclosed_shapes(ld, shadow_rb);
5167
5169
5170 /* Chaining is all single threaded. See `lineart_chain.cc`.
5171 * In this particular call, only lines that are geometrically connected (share the _exact_
5172 * same end point) will be chained together. */
5174
5175 /* We are unable to take care of occlusion if we only connect end points, so here we do a
5176 * spit, where the splitting point could be any cut in e->segments. */
5178
5179 /* Then we connect chains based on the _proximity_ of their end points in image space, here's
5180 * the place threshold value gets involved. */
5182
5184 /* Keeping UI range of 0-1 for ease of read while scaling down the actual value for best
5185 * effective range in image-space (Coordinate only goes from -1 to 1). This value is
5186 * somewhat arbitrary, but works best for the moment. */
5188 }
5189
5192 }
5193
5196 }
5197
5198 if (enable_stroke_depth_offset && lmd.stroke_depth_offset > FLT_EPSILON) {
5201 }
5202
5203 if (ld->conf.shadow_use_silhouette) {
5205 }
5206
5207 /* Finally transfer the result list into cache. */
5208 memcpy(&lc->chains, &ld->chains, sizeof(ListBase));
5209
5210 /* At last, we need to clear flags so we don't confuse GPencil generation calls. */
5212
5214 }
5215
5217
5218 if (ld->conf.shadow_enclose_shapes && shadow_rb) {
5220 MEM_delete(shadow_rb);
5221 }
5222
5223 if (G.debug_value == 4000) {
5225
5226 double t_elapsed = BLI_time_now_seconds() - t_start;
5227 printf("Line art total time: %lf\n", t_elapsed);
5228 }
5229
5230 return true;
5231}
5232
5237
5239 const float4x4 &inverse_mat,
5240 Depsgraph *depsgraph,
5242 const int8_t source_type,
5243 Object *source_object,
5244 Collection *source_collection,
5245 const int level_start,
5246 const int level_end,
5247 const int mat_nr,
5248 const int16_t edge_types,
5249 const uchar mask_switches,
5250 const uchar material_mask_bits,
5251 const uchar intersection_mask,
5252 const float thickness,
5253 const float opacity,
5254 const bool fill_strokes,
5255 const uchar shadow_selection,
5256 const uchar silhouette_mode,
5257 const char *source_vgname,
5258 const char *vgname,
5259 const int modifier_flags,
5260 const int modifier_calculation_flags)
5261{
5262 if (G.debug_value == 4000) {
5263 printf("Line Art v3: Generating...\n");
5264 }
5265
5266 if (cache == nullptr) {
5267 if (G.debug_value == 4000) {
5268 printf("nullptr Lineart cache!\n");
5269 }
5270 return;
5271 }
5272
5273 Object *orig_ob = nullptr;
5274 Collection *orig_col = nullptr;
5275
5276 if (source_type == LINEART_SOURCE_OBJECT) {
5277 if (!source_object) {
5278 return;
5279 }
5280 orig_ob = source_object->id.orig_id ? id_cast<Object *>(source_object->id.orig_id) :
5281 source_object;
5282 orig_col = nullptr;
5283 }
5284 else if (source_type == LINEART_SOURCE_COLLECTION) {
5285 if (!source_collection) {
5286 return;
5287 }
5288 orig_col = source_collection->id.orig_id ?
5289 id_cast<Collection *>(source_collection->id.orig_id) :
5290 source_collection;
5291 orig_ob = nullptr;
5292 }
5293 /* Otherwise the whole scene is selected. */
5294
5295 int enabled_types = cache->all_enabled_edge_types;
5296
5297 bool invert_input = modifier_calculation_flags & MOD_LINEART_INVERT_SOURCE_VGROUP;
5298
5299 bool inverse_silhouette = modifier_flags & LINEART_GPENCIL_INVERT_SILHOUETTE_FILTER;
5300
5302 writer.reserve(128);
5303 int total_point_count = 0;
5304 int stroke_count = 0;
5305 for (LineartEdgeChain &ec : cache->chains) {
5306
5307 if (ec.picked) {
5308 continue;
5309 }
5310 if (!(ec.type & (edge_types & enabled_types))) {
5311 continue;
5312 }
5313 if (ec.level > level_end || ec.level < level_start) {
5314 continue;
5315 }
5316 if (orig_ob && orig_ob != ec.object_ref) {
5317 continue;
5318 }
5319 if (orig_col && ec.object_ref) {
5321 if (modifier_flags & LINEART_GPENCIL_INVERT_COLLECTION) {
5322 continue;
5323 }
5324 }
5325 else {
5326 if (!(modifier_flags & LINEART_GPENCIL_INVERT_COLLECTION)) {
5327 continue;
5328 }
5329 }
5330 }
5331 if (mask_switches & MOD_LINEART_MATERIAL_MASK_ENABLE) {
5332 if (mask_switches & MOD_LINEART_MATERIAL_MASK_MATCH) {
5333 if (ec.material_mask_bits != material_mask_bits) {
5334 continue;
5335 }
5336 }
5337 else {
5338 if (!(ec.material_mask_bits & material_mask_bits)) {
5339 continue;
5340 }
5341 }
5342 }
5344 if (mask_switches & MOD_LINEART_INTERSECTION_MATCH) {
5345 if (ec.intersection_mask != intersection_mask) {
5346 continue;
5347 }
5348 }
5349 else {
5350 if ((intersection_mask) && !(ec.intersection_mask & intersection_mask)) {
5351 continue;
5352 }
5353 }
5354 }
5355 if (shadow_selection) {
5357 /* TODO(@Yiming): Give a behavior option for how to display undefined shadow info. */
5358 if (shadow_selection == LINEART_SHADOW_FILTER_ILLUMINATED &&
5360 {
5361 continue;
5362 }
5363 if (shadow_selection == LINEART_SHADOW_FILTER_SHADED &&
5365 {
5366 continue;
5367 }
5368 if (shadow_selection == LINEART_SHADOW_FILTER_ILLUMINATED_ENCLOSED_SHAPES) {
5370 if ((test_bits != LRT_SHADOW_MASK_ILLUMINATED) &&
5372 {
5373 continue;
5374 }
5375 }
5376 }
5377 }
5378 if (silhouette_mode && (ec.type & (MOD_LINEART_EDGE_FLAG_CONTOUR))) {
5379 bool is_silhouette = false;
5380 if (orig_col) {
5381 if (!ec.silhouette_backdrop) {
5382 is_silhouette = true;
5383 }
5385 {
5386 is_silhouette = true;
5387 }
5388 }
5389 else {
5390 if ((!orig_ob) && (!ec.silhouette_backdrop)) {
5391 is_silhouette = true;
5392 }
5393 }
5394
5395 if ((silhouette_mode == LINEART_SILHOUETTE_FILTER_INDIVIDUAL || orig_ob) &&
5397 {
5398 is_silhouette = true;
5399 }
5400
5401 if (inverse_silhouette) {
5402 is_silhouette = !is_silhouette;
5403 }
5404 if (!is_silhouette) {
5405 continue;
5406 }
5407 }
5408
5409 /* Preserved: If we ever do asynchronous generation, this picked flag should be set here. */
5410 // ec->picked = 1;
5411
5412 const int count = MOD_lineart_chain_count(&ec);
5413 if (count < 2) {
5414 continue;
5415 }
5416
5417 total_point_count += count;
5418 writer.append({&ec, count});
5419
5420 stroke_count++;
5421 }
5422
5423 if (!total_point_count || !stroke_count) {
5424 return;
5425 }
5426
5427 bke::CurvesGeometry new_curves(total_point_count, stroke_count);
5429
5432
5433 MutableAttributeAccessor attributes = new_curves.attributes_for_write();
5434 MutableSpan<float3> point_positions = new_curves.positions_for_write();
5435
5436 SpanAttributeWriter<float> point_radii = attributes.lookup_or_add_for_write_only_span<float>(
5437 "radius", AttrDomain::Point);
5438
5439 SpanAttributeWriter<float> point_opacities = attributes.lookup_or_add_for_write_span<float>(
5440 "opacity", AttrDomain::Point);
5441
5442 SpanAttributeWriter<int> stroke_materials = attributes.lookup_or_add_for_write_span<int>(
5443 "material_index", AttrDomain::Curve);
5444
5445 MutableSpan<int> offsets = new_curves.offsets_for_write();
5446
5447 const bool weight_transfer_match_output = modifier_calculation_flags &
5449
5450 auto find_target_defgroup = [&](StringRef group_name) {
5451 if (group_name.is_empty()) {
5452 return -1;
5453 }
5454
5455 int group_index = 0;
5456 for (const bDeformGroup &group : new_curves.vertex_group_names) {
5457 if (group_name == StringRef(group.name)) {
5458 return group_index;
5459 }
5460 group_index++;
5461 }
5462 /* Do not create vertex group if the group of the same name doesn't exist in the target. */
5463 return -1;
5464 };
5465
5466 const bool skip_weight_transfer = drawing.strokes().vertex_group_names.is_empty();
5467
5468 int up_to_point = 0;
5469 for (int chain_i : writer.index_range()) {
5470 LineartChainWriteInfo &cwi = writer[chain_i];
5471
5472 Vector<int> src_to_dst_defgroup;
5473
5474 Span<MDeformVert> src_dvert;
5475 Mesh *src_mesh = nullptr;
5477 int target_defgroup = find_target_defgroup(vgname);
5478 if (source_vgname) {
5479 Object *eval_ob = DEG_get_evaluated(depsgraph, cwi.chain->object_ref);
5480 if (eval_ob && eval_ob->type == OB_MESH) {
5481 src_mesh = BKE_object_get_evaluated_mesh(eval_ob);
5482 src_dvert = src_mesh->deform_verts();
5483 }
5484 }
5485
5486 if ((!skip_weight_transfer) && (!src_dvert.is_empty())) {
5487 const ListBaseT<bDeformGroup> *deflist = &src_mesh->vertex_group_names;
5488
5489 for (const auto [group_index, defgroup] : (deflist)->enumerate()) {
5490 if (StringRef(defgroup.name).startswith(source_vgname)) {
5491 const int target_group_index = weight_transfer_match_output ?
5492 find_target_defgroup(defgroup.name) :
5493 target_defgroup;
5494 src_to_dst_defgroup.append(target_group_index);
5495 }
5496 else {
5497 src_to_dst_defgroup.append(-1);
5498 }
5499 }
5500 }
5501
5502 auto transfer_to_matching_groups = [&](const int64_t source_index, const int target_index) {
5503 for (const int from_group : src_to_dst_defgroup.index_range()) {
5504 if (from_group < 0 || src_to_dst_defgroup[from_group] < 0 ||
5505 UNLIKELY(source_index >= src_dvert.size()))
5506 {
5507 continue;
5508 }
5509 const MDeformWeight *mdw_from = BKE_defvert_find_index(&src_dvert[source_index],
5510 from_group);
5511 MDeformWeight *mdw_to = BKE_defvert_ensure_index(&dv[target_index],
5512 src_to_dst_defgroup[from_group]);
5513 const float source_weight = mdw_from ? mdw_from->weight : 0.0f;
5514 mdw_to->weight = invert_input ? (1 - source_weight) : source_weight;
5515 }
5516 };
5517
5518 auto transfer_to_singular_group = [&](const int64_t source_index, const int target_index) {
5519 if (target_defgroup < 0) {
5520 return;
5521 }
5522 float highest_weight = 0.0f;
5523 for (const int from_group : src_to_dst_defgroup.index_range()) {
5524 if (from_group < 0 || UNLIKELY(source_index >= src_dvert.size())) {
5525 continue;
5526 }
5527 const MDeformWeight *mdw_from = BKE_defvert_find_index(&src_dvert[source_index],
5528 from_group);
5529 const float source_weight = mdw_from ? mdw_from->weight : 0.0f;
5530 highest_weight = std::max(highest_weight, source_weight);
5531 }
5532 MDeformWeight *mdw_to = BKE_defvert_ensure_index(&dv[target_index], target_defgroup);
5533 mdw_to->weight = invert_input ? (1 - highest_weight) : highest_weight;
5534 };
5535
5536 for (const auto [i, eci] : cwi.chain->chain.enumerate()) {
5537 int point_i = i + up_to_point;
5538 point_positions[point_i] = math::transform_point(inverse_mat, float3(eci.gpos));
5539 point_radii.span[point_i] = thickness / 2.0f;
5540 if (point_opacities) {
5541 point_opacities.span[point_i] = opacity;
5542 }
5543
5544 const int64_t vindex = eci.index - cwi.chain->index_offset;
5545
5546 if (!src_to_dst_defgroup.is_empty()) {
5547 if (weight_transfer_match_output) {
5548 transfer_to_matching_groups(vindex, point_i);
5549 }
5550 else {
5551 transfer_to_singular_group(vindex, point_i);
5552 }
5553 }
5554 }
5555
5556 offsets[chain_i] = up_to_point;
5557 stroke_materials.span[chain_i] = max_ii(mat_nr, 0);
5558 up_to_point += cwi.point_count;
5559 }
5560
5561 offsets[writer.index_range().last() + 1] = up_to_point;
5562
5563 SpanAttributeWriter<bool> stroke_cyclic = attributes.lookup_or_add_for_write_span<bool>(
5564 "cyclic", AttrDomain::Curve);
5565 stroke_cyclic.span.fill(false);
5566 stroke_cyclic.finish();
5567
5568 point_radii.finish();
5569 point_opacities.finish();
5570 stroke_materials.finish();
5571
5572 if (fill_strokes) {
5573 SpanAttributeWriter<int> fill_ids = attributes.lookup_or_add_for_write_span<int>(
5574 "fill_id", AttrDomain::Curve);
5576 fill_ids.finish();
5577 }
5578
5579 Curves *original_curves = bke::curves_new_nomain(drawing.strokes());
5580 Curves *created_curves = bke::curves_new_nomain(std::move(new_curves));
5581 std::array<bke::GeometrySet, 2> geometry_sets{bke::GeometrySet::from_curves(original_curves),
5582 bke::GeometrySet::from_curves(created_curves)};
5583 bke::GeometrySet joined = geometry::join_geometries(geometry_sets, {});
5584
5585 drawing.strokes_for_write() = std::move(joined.get_curves_for_write()->geometry.wrap());
5586 drawing.tag_topology_changed();
5587
5588 if (G.debug_value == 4000) {
5589 printf("LRT: Generated %d strokes.\n", stroke_count);
5590 }
5591}
5592
5593} // namespace blender
Camera data-block and utility functions.
Low-level operations for curves.
CustomData interface, see also DNA_customdata_types.h.
support for deformation groups and hooks.
Low-level operations for grease pencil.
General operations, lookup, etc. for materials.
General operations, lookup, etc. for blender objects.
#define M_PI
#define ISECT_LINE_LINE_NONE
Platform independent time functions.
#define DEG_OBJECT_ITER_BEGIN(settings_, instance_)
#define DEG_OBJECT_ITER_END
Object groups, one object can be in many groups at once.
Object is a sort of wrapper for general info.
Read Blender memory allocation and freeing.
#define LRT_TILE_EDGE_COUNT_INITIAL
#define LRT_DOUBLE_CLOSE_ENOUGH(a, b)
#define LRT_SHADOW_MASK_INHIBITED
#define LRT_SHADOW_MASK_UNDEFINED
#define LRT_OBINDEX_LOWER
#define LRT_OBINDEX_SHIFT
#define LRT_SHADOW_MASK_ILLUMINATED_SHAPE
#define LRT_LIGHT_CONTOUR_TARGET
#define DBL_TRIANGLE_LIM
#define LRT_SHADOW_MASK_ENCLOSED_SHAPE
#define LRT_SHADOW_TEST_SHAPE_BITS
#define LRT_OBINDEX_HIGHER
#define LRT_SHADOW_MASK_ILLUMINATED
#define LRT_TILE_SPLITTING_TRIANGLE_LIMIT
#define LRT_THREAD_EDGE_COUNT
#define LRT_SHADOW_MASK_SHADED
#define LRT_EDGE_IDENTIFIER(obi, e)
volatile int lock
#define CLAMP(a, b, c)
#define BLI_INLINE
#define UNLIKELY(x)
#define ELEM(...)
#define MEM_realloc_zeroed(vmemh, len)
constexpr MutableSpan()=default
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr bool is_empty() const
Definition BLI_span.hh:264
constexpr StringRef()
void append(const T &value)
bool is_empty() const
IndexRange index_range() const
void reserve(const int64_t min_capacity)
GAttributeReader lookup_or_default(StringRef name, AttrDomain domain, AttrType data_type, const void *default_value=nullptr) const
GAttributeReader lookup(const StringRef name) const
MutableSpan< MDeformVert > deform_verts_for_write()
MutableSpan< float3 > positions_for_write()
MutableSpan< int > offsets_for_write()
void fill_curve_types(CurveType type)
MutableAttributeAccessor attributes_for_write()
GSpanAttributeWriter lookup_or_add_for_write_span(StringRef name, AttrDomain domain, AttrType data_type, const AttributeInit &initializer=AttributeInitDefaultValue())
GSpanAttributeWriter lookup_or_add_for_write_only_span(StringRef name, AttrDomain domain, AttrType data_type)
bke::CurvesGeometry & strokes_for_write()
const bke::CurvesGeometry & strokes() const
constexpr int64_t last(const int64_t n=0) const
constexpr bool is_empty() const
void to_indices(MutableSpan< T > r_indices) const
#define FLT_EPSILON
#define cos
float length(VecOp< float, D >) RET
void camera(KernelGlobals &kg, const ShadingData &sd, float3 &outview, float &outdepth, float &outdist)
#define INTERSECT_JUST_SMALLER(is, order, num, index)
#define LRT_MESH_EDGE_TYPES_COUNT
#define RELINK_EDGE(e_num, new_tri)
#define LRT_VERT_OUT_OF_BOUND(v)
#define LRT_CULL_DECIDE_INSIDE
#define INCREASE_EDGE
#define LRT_ISECT_TRIANGLE_PER_THREAD
#define REMOVE_TRIANGLE_EDGE
#define LRT_PARALLEL(index)
#define INTERSECT_JUST_GREATER(is, order, num, index)
#define LRT_TRI_SAME_POINT(tri, i, pt)
#define INTERSECT_SORT_MIN_TO_MAX_3(ia, ib, ic, lst)
#define SELECT_EDGE(e_num, v1_link, v2_link, new_tri)
#define LRT_CULL_ENSURE_MEMORY
#define LRT_ISEC(index)
#define LRT_GUARD_NOT_FOUND
#define LRT_BOUND_AREA_CROSSES(b1, b2)
#define LRT_EDGE_BA_MARCHING_BEGIN(fb1, fb2)
#define LRT_EDGE_BA_MARCHING_NEXT(fb1, fb2)
#define LRT_EDGE_BA_MARCHING_END
#define LRT_ITER_ALL_LINES_END
#define LRT_BA_ROWS
#define LRT_ITER_ALL_LINES_BEGIN
ccl_device_inline dual3 fabs(const ccl_private dual3 &a)
Definition math_dual.h:241
#define RB
#define LB
void gather_next_available_fill_ids(const VArray< int > &fill_ids, MutableSpan< int > r_new_fill_ids)
int3 corner_tri_get_real_edges(Span< int2 > edges, Span< int > corner_verts, Span< int > corner_edges, const int3 &corner_tri)
Curves * curves_new_nomain(int points_num, int curves_num)
std::array< VecBase< T, 3 >, 8 > corners(const Bounds< VecBase< T, 3 > > &bounds)
bke::GeometrySet join_geometries(Span< bke::GeometrySet > geometries, const bke::AttributeFilter &attribute_filter, const std::optional< Span< bke::GeometryComponent::Type > > &component_types_to_join=std::nullopt, bool allow_merging_instance_references=true)
VecBase< T, 3 > transform_point(const CartesianBasis &basis, const VecBase< T, 3 > &v)
BMesh Iterators.
void lineart_main_discard_out_of_frame_edges(LineartData *ld)
static void lineart_occlusion_single_line(LineartData *ld, LineartEdge *e, int thread_id)
bool lineart_edge_from_triangle(const LineartTriangle *tri, const LineartEdge *e, bool allow_overlapping_edges)
static LineartBoundingArea * lineart_get_bounding_area(LineartData *ld, double x, double y)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
static uchar lineart_intersection_mask_check(Collection *c, Object *ob)
static void lineart_object_load_worker(TaskPool *__restrict, LineartObjectLoadTaskInfo *olti)
void MOD_lineart_smooth_chains(LineartData *ld, float tolerance)
unsigned __int64 uint64_t
Definition BKE_text.h:91
LineartBoundingArea * MOD_lineart_get_parent_bounding_area(LineartData *ld, double x, double y)
@ COLLECTION_LRT_NO_INTERSECTION
@ COLLECTION_LRT_OCCLUSION_ONLY
@ COLLECTION_LRT_INTERSECTION_ONLY
@ COLLECTION_LRT_FORCE_INTERSECTION
__int64 int64_t
Definition BKE_text.h:90
static void lineart_bounding_areas_connect_new(LineartData *ld, LineartBoundingArea *root)
static LineartTriangle * lineart_triangle_from_index(LineartData *ld, LineartTriangle *rt_array, int index)
MINLINE void sub_v2_v2v2_db(double r[2], const double a[2], const double b[2])
static void lineart_discard_segment(LineartData *ld, LineartEdgeSegment *es)
void lineart_list_remove_pointer_item_no_free(ListBase *h, LinkData *lip)
LineartEdge * lineart_find_matching_edge(struct LineartElementLinkNode *shadow_eln, uint64_t edge_identifier)
bool BKE_collection_has_object_recursive_instanced(Collection *collection, Object *ob)
static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartData *la_data, ListBaseT< LineartElementLinkNode > *shadow_elns)
eLineArtElementNodeFlag
@ LRT_ELEMENT_BORDER_ONLY
@ LRT_ELEMENT_IS_ADDITIONAL
@ LRT_ELEMENT_INTERSECTION_DATA
@ LRT_ELEMENT_NO_INTERSECTION
MINLINE double dot_v3v3_db(const double a[3], const double b[3]) ATTR_WARN_UNUSED_RESULT
BLI_INLINE void BLI_parallel_range_settings_defaults(TaskParallelSettings *settings)
@ LRT_TRIANGLE_MAT_BACK_FACE_CULLING
@ LRT_CULL_GENERATED
@ LRT_TRIANGLE_FORCE_INTERSECTION
@ LRT_TRIANGLE_INTERSECTION_ONLY
@ LRT_CULL_DISCARD
@ LRT_TRIANGLE_NO_INTERSECTION
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void BLI_addhead(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:98
ATTR_WARN_UNUSED_RESULT const BMLoop * l
static void lineart_end_bounding_area_recursive(LineartBoundingArea *ba)
MINLINE void copy_v3db_v3fl(double r[3], const float a[3])
static void lineart_identify_corner_tri_feature_edges(void *__restrict userdata, const int i, const TaskParallelTLS *__restrict tls)
void lineart_main_bounding_areas_connect_post(LineartData *ld)
static void lineart_add_edge_to_array_thread(LineartObjectInfo *obi, LineartEdge *e)
@ LRT_TILE_RECURSIVE_PERSPECTIVE
@ LRT_TILE_RECURSIVE_ORTHO
void lineart_main_load_geometries(Depsgraph *depsgraph, Scene *scene, Object *camera, LineartData *ld, bool allow_duplicates, bool do_shadow_casting, ListBaseT< LineartElementLinkNode > *shadow_elns, Set< const Object * > *included_objects)
BLI_INLINE bool lineart_occlusion_is_adjacent_intersection(LineartEdge *e, LineartTriangle *tri)
static void lineart_init_isec_thread(LineartIsecData *d, LineartData *ld, int thread_count)
static int lineart_triangle_size_get(LineartData *ld)
BLI_INLINE float fb(float length, float L)
static int lineart_usage_check(Collection *c, Object *ob, bool is_render)
static void lineart_triangle_cull_single(LineartData *ld, LineartTriangle *tri, int in0, int in1, int in2, double cam_pos[3], double view_dir[3], bool allow_boundaries, double m_view_projection[4][4], Object *ob, int *r_v_count, int *r_e_count, int *r_t_count, LineartElementLinkNode *v_eln, LineartElementLinkNode *e_eln, LineartElementLinkNode *t_eln)
static bool lineart_bounding_area_triangle_intersect(LineartData *fb, LineartTriangle *tri, LineartBoundingArea *ba, bool *r_triangle_vert_inside)
static void lineart_destroy_isec_thread(LineartIsecData *d)
Material * BKE_object_material_get(Object *ob, short act)
@ TASK_PRIORITY_HIGH
Definition BLI_task_c.hh:61
void lineart_count_and_print_render_buffer_memory(struct LineartData *ld)
static bool lineart_get_edge_bounding_areas(LineartData *ld, LineartEdge *e, int *rowbegin, int *rowend, int *colbegin, int *colend)
@ COLLECTION_LRT_USE_INTERSECTION_PRIORITY
@ COLLECTION_LRT_USE_INTERSECTION_MASK
LineartBoundingArea * lineart_edge_first_bounding_area(LineartData *ld, double *fbcoord1, double *fbcoord2)
bool invert_m4_m4(float inverse[4][4], const float mat[4][4])
void MOD_lineart_clear_cache(LineartCache **lc)
void mul_v3_mat3_m4v3(float r[3], const float mat[4][4], const float vec[3])
void MOD_lineart_chain_feature_lines(LineartData *ld)
void * lineart_list_append_pointer_pool_sized(ListBase *h, struct LineartStaticMemPool *smp, void *data, int size)
static void lineart_edge_neighbor_init_task(void *__restrict userdata, const int i, const TaskParallelTLS *__restrict)
static bool lineart_schedule_new_triangle_task(LineartIsecThread *th)
void interp_v2_v2v2_db(double target[2], const double a[2], const double b[2], double t)
void lineart_matrix_perspective_44d(double(*mProjection)[4], double fFov_rad, double fAspect, double zMin, double zMax)
MINLINE int max_ii(int a, int b)
int isect_seg_seg_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2])
void BLI_task_parallel_range(int start, int stop, void *userdata, TaskParallelRangeFunc func, const TaskParallelSettings *settings)
@ OBJECT_LRT_OWN_INTERSECTION_PRIORITY
ATTR_WARN_UNUSED_RESULT const BMVert * v
@ CAMERA_SENSOR_FIT_VERT
@ CAMERA_SENSOR_FIT_HOR
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:45
void MOD_lineart_chain_offset_towards_camera(LineartData *ld, float dist, bool use_custom_camera)
static void lineart_mvert_transform_task(void *__restrict userdata, const int i, const TaskParallelTLS *__restrict)
static LineartVert * lineart_triangle_share_point(const LineartTriangle *l, const LineartTriangle *r)
MatBase< float, 4, 4 > float4x4
void lineart_destroy_render_data_keep_init(LineartData *ld)
MINLINE void copy_v3_v3_db(double r[3], const double a[3])
void MOD_lineart_finalize_chains(LineartData *ld)
static void lineart_destroy_render_data(LineartData *ld)
void MEM_delete_void(void *vmemh)
void * lineart_list_append_pointer_pool_sized_thread(ListBase *h, LineartStaticMemPool *smp, void *data, int size)
void MOD_lineart_chain_clip_at_border(LineartData *ld)
static void lineart_triangle_adjacent_assign(LineartTriangle *tri, LineartTriangleAdjacent *tri_adj, LineartEdge *e)
static void lineart_occlusion_worker(TaskPool *__restrict, LineartRenderTaskInfo *rti)
MINLINE double ratiod(double min, double max, double pos)
LineartBoundingArea * lineart_bounding_area_next(LineartBoundingArea *self, double *fbcoord1, double *fbcoord2, double x, double y, double k, int positive_x, int positive_y, double *next_x, double *next_y)
static LineartEdgeNeighbor * lineart_build_edge_neighbor(Mesh *mesh, int total_edges)
bool MOD_lineart_compute_feature_lines_v3(Depsgraph *depsgraph, GreasePencilLineartModifierData &lmd, LineartCache **cached_result, bool enable_stroke_depth_offset)
int MOD_lineart_chain_count(const LineartEdgeChain *ec)
bool BKE_collection_has_object(Collection *collection, const Object *ob)
void BLI_task_pool_work_and_wait(TaskPool *pool)
Definition task_pool.cc:455
static void lineart_add_isec_thread(LineartIsecThread *th, const double *v1, const double *v2, LineartTriangle *tri1, LineartTriangle *tri2)
void * BLI_pophead(ListBase *listbase) ATTR_NONNULL(1)
Definition listbase.cc:259
void MOD_lineart_chain_clear_picked_flag(LineartCache *lc)
@ LINEART_SILHOUETTE_FILTER_INDIVIDUAL
Global G
Definition blender.cc:57
unsigned short uint16_t
Definition BKE_text.h:80
void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end)
Definition BLI_sort.hh:37
static void lineart_main_remove_unused_lines_from_tiles(LineartData *ld)
@ OBJECT_LRT_OCCLUSION_ONLY
@ OBJECT_LRT_INTERSECTION_ONLY
@ OBJECT_LRT_FORCE_INTERSECTION
@ OBJECT_LRT_NO_INTERSECTION
float focallength_to_fov(float focal_length, float sensor)
unsigned int uint32_t
Definition BKE_text.h:81
int BKE_render_num_threads(const RenderData *r)
Definition scene.cc:3141
void BLI_spin_end(SpinLock *spin)
Definition threads.cc:448
Render * RE_GetSceneRender(const Scene *scene)
static void lineart_load_tri_task(void *__restrict userdata, const int i, const TaskParallelTLS *__restrict)
void lineart_add_edge_to_array(LineartPendingEdges *pe, LineartEdge *e)
static bool lineart_edge_match(LineartTriangle *tri, LineartEdge *e, int v1, int v2)
VecBase< int32_t, 2 > int2
VecBase< float, 2 > float2
VecBase< int32_t, 3 > int3
void lineart_main_clear_linked_edges(LineartData *ld)
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
void MOD_lineart_chain_split_for_fixed_occlusion(LineartData *ld)
unsigned char uchar
Definition BKE_text.h:58
void mul_v4_m4v3_db(double r[4], const double mat[4][4], const double vec[3])
void copy_m4_m4_db(double m1[4][4], const double m2[4][4])
void * lineart_list_append_pointer_pool_thread(ListBase *h, struct LineartStaticMemPool *smp, void *data)
static const int LRT_MESH_EDGE_TYPES[]
static uchar lineart_intersection_priority_check(Collection *c, Object *ob)
void lineart_register_intersection_shadow_cuts(struct LineartData *ld, ListBaseT< LineartElementLinkNode > *shadow_elns)
void lineart_main_add_triangles(LineartData *ld)
void BLI_remlink(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:138
static void lineart_finalize_object_edge_array(LineartPendingEdges *pe, LineartObjectInfo *obi)
static bool lineart_get_triangle_bounding_areas(LineartData *ld, LineartTriangle *tri, int *rowbegin, int *rowend, int *colbegin, int *colend)
void lineart_matrix_ortho_44d(double(*mProjection)[4], double xMin, double xMax, double yMin, double yMax, double zMin, double zMax)
BMesh const char void * data
T * DEG_get_evaluated(const Depsgraph *depsgraph, T *id)
void lineart_main_occlusion_begin(LineartData *ld)
static void lineart_clear_linked_edges_recursive(LineartData *ld, LineartBoundingArea *root_ba)
static int lineart_edge_type_duplication_count(int eflag)
void MOD_lineart_gpencil_generate_v3(const LineartCache *cache, const float4x4 &inverse_mat, Depsgraph *depsgraph, bke::greasepencil::Drawing &drawing, const int8_t source_type, Object *source_object, Collection *source_collection, const int level_start, const int level_end, const int mat_nr, const int16_t edge_types, const uchar mask_switches, const uchar material_mask_bits, const uchar intersection_mask, const float thickness, const float opacity, const bool fill_strokes, const uchar shadow_selection, const uchar silhouette_mode, const char *source_vgname, const char *vgname, const int modifier_flags, const int modifier_calculation_flags)
static int lineart_point_on_line_segment(double v[2], double v0[2], double v1[2])
int BKE_object_visibility(const Object *ob, int dag_eval_mode)
Definition object.cc:2063
static void lineart_bounding_area_split(LineartData *ld, LineartBoundingArea *root, int recursive_level)
static bool lineart_triangle_share_edge(const LineartTriangle *l, const LineartTriangle *r)
int3 corner_tri_get_real_edges(Span< int2 > edges, Span< int > corner_verts, Span< int > corner_edges, const int3 &corner_tri)
void MOD_lineart_chain_split_angle(LineartData *ld, float angle_threshold_rad)
unsigned char uint8_t
Definition BKE_text.h:79
static LineartElementLinkNode * lineart_memory_get_vert_space(LineartData *ld)
@ DEG_ITER_OBJECT_FLAG_LINKED_VIA_SET
@ DEG_ITER_OBJECT_FLAG_LINKED_DIRECTLY
MINLINE void cross_v3_v3v3_db(double r[3], const double a[3], const double b[3])
void MOD_lineart_chain_connect(LineartData *ld)
static void lineart_sort_adjacent_items(LineartAdjacentEdge *ai, int length)
MDeformWeight * BKE_defvert_ensure_index(MDeformVert *dv, int defgroup)
Definition deform.cc:830
void(*) TaskRunFunction(TaskPool *__restrict pool, void *taskdata)
Definition BLI_task_c.hh:65
void MOD_lineart_destroy_render_data_v3(GreasePencilLineartModifierData *lmd)
static bool lineart_geometry_check_visible(double model_view_proj[4][4], double shift_x, double shift_y, Mesh *use_mesh)
static bool lineart_triangle_2v_intersection_math(LineartVert *v1, LineartVert *v2, LineartTriangle *tri, const double *last, double *rv)
void mul_v3_m4v3_db(double r[3], const double mat[4][4], const double vec[3])
@ LINEART_SHADOW_FILTER_ILLUMINATED_ENCLOSED_SHAPES
@ LINEART_SHADOW_FILTER_ILLUMINATED
static void lineart_triangle_post(LineartTriangle *tri, LineartTriangle *orig)
void lineart_register_shadow_cuts(struct LineartData *ld, struct LineartEdge *e, struct LineartEdge *shadow_edge)
static void lineart_bounding_area_triangle_reallocate(LineartBoundingArea *ba)
void lineart_main_get_view_vector(LineartData *ld)
static bool lineart_triangle_get_other_verts(const LineartTriangle *tri, const LineartVert *vt, LineartVert **l, LineartVert **r)
void BKE_id_free(Main *bmain, void *idv)
eEvaluationMode DEG_get_mode(const Depsgraph *graph)
int BKE_camera_sensor_fit(int sensor_fit, float sizex, float sizey)
void BLI_insertlinkbefore(ListBase *listbase, void *vnextlink, void *vnewlink) ATTR_NONNULL(1)
Definition listbase.cc:378
void BLI_task_pool_free(TaskPool *pool)
Definition task_pool.cc:441
void unit_m4_db(double m[4][4])
LineartBoundingArea * MOD_lineart_get_bounding_area(LineartData *ld, double x, double y)
void copy_m4d_m4(double m1[4][4], const float m2[4][4])
TaskPool * BLI_task_pool_create(void *userdata, eTaskPriority priority)
Definition task_pool.cc:404
static void lineart_geometry_load_assign_thread(LineartObjectLoadTaskInfo *olti_list, LineartObjectInfo *obi, int thread_count, int this_face_count)
@ MOD_LINEART_EDGE_FLAG_PROJECTED_SHADOW
@ MOD_LINEART_EDGE_FLAG_NEXT_IS_DUPLICATION
@ MOD_LINEART_EDGE_FLAG_INHIBIT
@ MOD_LINEART_EDGE_FLAG_EDGE_MARK
@ MOD_LINEART_EDGE_FLAG_LOOSE
@ MOD_LINEART_EDGE_FLAG_CONTOUR_SECONDARY
@ MOD_LINEART_EDGE_FLAG_CREASE
@ MOD_LINEART_EDGE_FLAG_SHADOW_FACING_LIGHT
@ MOD_LINEART_EDGE_FLAG_CHAIN_PICKED
@ MOD_LINEART_EDGE_FLAG_INTERSECTION
@ MOD_LINEART_EDGE_FLAG_LIGHT_CONTOUR
@ MOD_LINEART_EDGE_FLAG_CONTOUR
@ MOD_LINEART_EDGE_FLAG_MATERIAL
void BLI_spin_unlock(SpinLock *spin)
Definition threads.cc:433
MINLINE float normalize_v3(float n[3])
void lineart_main_cull_triangles(LineartData *ld, bool clip_far)
MINLINE void mul_v3db_db(double r[3], double f)
float BKE_camera_sensor_size(int sensor_fit, float sensor_x, float sensor_y)
static void lineart_triangle_intersect_in_bounding_area(LineartTriangle *tri, LineartBoundingArea *ba, LineartIsecThread *th, int up_to)
void interp_v3_v3v3_db(double target[3], const double a[3], const double b[3], double t)
static void lineart_discard_duplicated_edges(LineartEdge *old_e)
void BLI_spin_init(SpinLock *spin)
Definition threads.cc:394
void * lineart_mem_acquire(struct LineartStaticMemPool *smp, size_t size)
void BLI_addtail(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:118
static LineartData * lineart_create_render_buffer_v3(Scene *scene, GreasePencilLineartModifierData *lmd, Object *camera, Object *active_camera, LineartCache *lc)
void transpose_m4(float R[4][4])
ATTR_WARN_UNUSED_RESULT const BMVert * v2
static bool lineart_bounding_area_edge_intersect(LineartData *, const double l[2], const double r[2], LineartBoundingArea *ba)
void lineart_mem_destroy(struct LineartStaticMemPool *smp)
bool BKE_scene_camera_switch_update(Scene *scene)
Definition scene.cc:2480
void lineart_main_link_lines(LineartData *ld)
static bool lineart_point_inside_triangle3d(double v[3], double v0[3], double v1[3], double v2[3])
static void lineart_bounding_area_line_add(LineartBoundingArea *ba, LineartEdge *e)
MINLINE void sub_v3_v3v3_db(double r[3], const double a[3], const double b[3])
void lineart_edge_cut(LineartData *ld, LineartEdge *e, double start, double end, uchar material_mask_bits, uchar mat_occlusion, uint32_t shadow_bits)
static void lineart_add_triangles_worker(TaskPool *__restrict, LineartIsecThread *th)
void lineart_main_transform_and_add_shadow(struct LineartData *ld, struct LineartElementLinkNode *veln, struct LineartElementLinkNode *eeln)
Material * BKE_object_material_get_eval(Object *ob, short act)
static void lineart_free_bounding_area_memory(LineartBoundingArea *ba, bool recursive)
void lineart_main_make_enclosed_shapes(struct LineartData *ld, struct LineartData *shadow_ld)
static void lineart_bounding_areas_connect_recursive(LineartData *ld, LineartBoundingArea *root)
static LineartPointTri lineart_point_triangle_relation(double v[2], double v0[2], double v1[2], double v2[2])
void lineart_finalize_object_edge_array_reserve(LineartPendingEdges *pe, int count)
static void lineart_triangle_set_cull_flag(LineartTriangle *tri, uchar flag)
void BKE_defgroup_copy_list(ListBaseT< bDeformGroup > *outbase, const ListBaseT< bDeformGroup > *inbase)
Definition deform.cc:75
static bool lineart_triangle_intersect_math(LineartTriangle *tri, LineartTriangle *t2, double *v1, double *v2)
static void lineart_main_remove_unused_lines_recursive(LineartBoundingArea *ba, uint8_t max_occlusion)
double BLI_time_now_seconds()
Definition time.cc:30
BLI_INLINE int lineart_intersect_seg_seg(const double a1[2], const double a2[2], const double b1[2], const double b2[2], double *r_ratio, bool *r_aligned)
@ LRT_OUTSIDE_TRIANGLE
@ LRT_INSIDE_TRIANGLE
@ LRT_ON_TRIANGLE
static int lineart_occlusion_make_task_info(LineartData *ld, LineartRenderTaskInfo *rti)
void MOD_lineart_chain_find_silhouette_backdrop_objects(LineartData *ld)
Mesh * BKE_mesh_new_from_object(Depsgraph *depsgraph, Object *object, bool preserve_all_data_layers, bool preserve_origindex, bool ensure_subdivision)
void * lineart_mem_acquire_thread(struct LineartStaticMemPool *smp, size_t size)
static void lineart_bounding_area_link_edge(LineartData *ld, LineartBoundingArea *root_ba, LineartEdge *e)
@ LINEART_GPENCIL_OFFSET_TOWARDS_CUSTOM_CAMERA
@ LINEART_GPENCIL_INVERT_COLLECTION
@ LINEART_GPENCIL_INVERT_SILHOUETTE_FILTER
static LineartElementLinkNode * lineart_memory_get_edge_space(LineartData *ld)
void mul_m4db_m4db_m4fl(double R[4][4], const double A[4][4], const float B[4][4])
MINLINE void add_v3_v3_db(double r[3], const double a[3])
static void lineart_create_edges_from_isec_data(LineartIsecData *d)
static void lineart_object_load_single_instance(LineartData *ld, Depsgraph *depsgraph, Scene *scene, Object *ob, Object *ref_ob, const float use_mat[4][4], bool is_render, LineartObjectLoadTaskInfo *olti, int thread_count, int obindex)
void copy_m4_m4(float m1[4][4], const float m2[4][4])
VecBase< float, 3 > float3
static void lineart_free_bounding_area_memories(LineartData *ld)
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 m_view_projection[4][4], const double camera_dir[3], const float cam_shift_x, const float cam_shift_y, double *from, double *to)
@ MOD_LINEART_USE_IMAGE_BOUNDARY_TRIMMING
@ MOD_LINEART_CHAIN_PRESERVE_DETAILS
@ MOD_LINEART_USE_BACK_FACE_CULLING
@ MOD_LINEART_FILTER_FACE_MARK
@ MOD_LINEART_ALLOW_CLIPPING_BOUNDARIES
@ MOD_LINEART_USE_CREASE_ON_SHARP_EDGES
@ MOD_LINEART_USE_CUSTOM_CAMERA
@ MOD_LINEART_ALLOW_DUPLI_OBJECTS
@ MOD_LINEART_CHAIN_GEOMETRY_SPACE
@ MOD_LINEART_FILTER_FACE_MARK_INVERT
@ MOD_LINEART_INVERT_SOURCE_VGROUP
@ MOD_LINEART_FILTER_FACE_MARK_BOUNDARIES
@ MOD_LINEART_MATCH_OUTPUT_VGROUP
@ MOD_LINEART_FILTER_FACE_MARK_KEEP_CONTOUR
@ MOD_LINEART_ALLOW_OVERLAP_EDGE_TYPES
@ MOD_LINEART_ALLOW_OVERLAPPING_EDGES
@ MOD_LINEART_CHAIN_LOOSE_EDGES
@ MOD_LINEART_INTERSECTION_AS_CONTOUR
@ MOD_LINEART_USE_CREASE_ON_SMOOTH_SURFACES
@ MOD_LINEART_LOOSE_AS_CONTOUR
@ MOD_LINEART_EVERYTHING_AS_CONTOUR
Scene * DEG_get_evaluated_scene(const Depsgraph *graph)
void * lineart_list_append_pointer_pool(ListBase *h, struct LineartStaticMemPool *smp, void *data)
MINLINE double normalize_v3_db(double n[3])
void BLI_spin_lock(SpinLock *spin)
Definition threads.cc:408
void BLI_task_pool_push(TaskPool *pool, TaskRunFunction run, void *taskdata, bool free_taskdata, TaskFreeFunction freedata)
Definition task_pool.cc:446
static LineartEdgeSegment * lineart_give_segment(LineartData *ld)
static bool lineart_point_inside_triangle(const double v[2], const double v0[2], const double v1[2], const double v2[2])
void mul_v3_mat3_m4v3_db(double r[3], const double mat[4][4], const double vec[3])
@ OB_VISIBLE_SELF
void lineart_main_perspective_division(LineartData *ld)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
signed char int8_t
Definition BKE_text.h:76
void lineart_main_free_adjacent_data(LineartData *ld)
static LineartElementLinkNode * lineart_memory_get_triangle_space(LineartData *ld)
static void feat_data_sum_reduce(const void *__restrict, void *__restrict chunk_join, void *__restrict chunk)
bool lineart_main_try_generate_shadow_v3(struct Depsgraph *depsgraph, struct Scene *scene, struct LineartData *original_ld, struct GreasePencilLineartModifierData *lmd, struct LineartStaticMemPool *shadow_data_pool, struct LineartElementLinkNode **r_veln, struct LineartElementLinkNode **r_eeln, ListBaseT< LineartElementLinkNode > *r_calculated_edges_eln_list, struct LineartData **r_shadow_ld_if_reproject)
MDeformWeight * BKE_defvert_find_index(const MDeformVert *dv, int defgroup)
Definition deform.cc:811
@ MOD_LINEART_MATERIAL_MASK_MATCH
@ MOD_LINEART_INTERSECTION_MATCH
@ MOD_LINEART_MATERIAL_MASK_ENABLE
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
Mesh * BKE_object_get_evaluated_mesh(const Object *object_eval)
Definition object.cc:4436
signed short int16_t
Definition BKE_text.h:77
@ LRT_MATERIAL_CUSTOM_INTERSECTION_PRIORITY
@ LRT_MATERIAL_MASK_ENABLED
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, LineartIsecThread *th)
void lineart_main_bounding_area_make_initial(LineartData *ld)
LineartElementLinkNode * lineart_find_matching_eln(ListBaseT< LineartElementLinkNode > *shadow_elns, int obindex)
LineartCache * MOD_lineart_init_cache()
#define cosf
eCollectionLineArt_Flags lineart_flags
eCollectionLineArt_Usage lineart_usage
ListBaseT< CollectionChild > children
ListBaseT< CollectionObject > gobject
ListBaseT< struct bDeformGroup > vertex_group_names
Set< const Object * > * included_objects
LineartTriangle * tri_array
VArray< bool > sharp_faces
VArray< bool > sharp_edges
LineartEdgeNeighbor * edge_nabr
VArray< bool > freestyle_edge
VArray< bool > freestyle_face
Span< int > material_indices
LineartEdgeNeighbor * edge_nabr
LineartAdjacentEdge * adj_e
struct LineartModifierRuntime * runtime
struct ID * orig_id
Definition DNA_ID.h:502
ListBaseT< LinkData > bp
LineartBoundingArea * child
LineartTriangle ** linked_triangles
ListBaseT< LinkData > lp
ListBaseT< LinkData > up
ListBaseT< LinkData > rp
LineartStaticMemPool chain_data_pool
ListBaseT< LineartElementLinkNode > shadow_elns
ListBaseT< LineartEdgeChain > chains
uint16_t all_enabled_edge_types
LineartStaticMemPool shadow_data_pool
ListBaseT< LineartElementLinkNode > vertex_buffer_pointers
ListBaseT< LineartElementLinkNode > triangle_adjacent_pointers
ListBaseT< LineartElementLinkNode > line_buffer_pointers
ListBaseT< LineartElementLinkNode > triangle_buffer_pointers
LineartBoundingArea * initials
LineartStaticMemPool * chain_data_pool
struct blender::LineartData::_geom geom
LineartStaticMemPool * edge_data_pool
struct blender::LineartData::_qtree qtree
struct blender::LineartData::_conf conf
ListBaseT< LineartEdgeChain > chains
struct LineartPendingEdges pending_edges
LineartStaticMemPool render_data_pool
ListBaseT< LineartEdgeSegment > wasted_cuts
LineartElementLinkNode * isect_scheduled_up_to
ListBaseT< LineartEdgeChainItem > chain
LineartEdgeSegment * next
LineartEdgeSegment * prev
ListBaseT< LineartEdgeSegment > segments
LineartTriangle * t1
LineartTriangle * t2
eLineArtElementNodeFlag flags
LineartElementLinkNode * next
LineartIsecThread * threads
LineartTriangle * tri2
LineartTriangle * tri1
LineartElementLinkNode * pending_from
LineartIsecSingle * array
LineartElementLinkNode * pending_to
Set< const Object * > object_dependencies
LineartObjectInfo * next
LineartPendingEdges pending_edges
LineartElementLinkNode * v_eln
ListBaseT< LineartElementLinkNode > * shadow_elns
struct LineartPendingEdges pending_edges
struct LinkData * next
ListBaseT< bDeformGroup > vertex_group_names
bke::MeshRuntime * runtime
eObjectLineArt_Usage usage
eObjectLineArt_Flags flags
unsigned char intersection_priority
ObjectLineArt lineart
struct Collection * master_collection
struct Object * camera
struct RenderData r
TaskParallelReduceFunc func_reduce
Span< float3 > positions
LineartTriangle * tri_arr
LineartObjectInfo * ob_info
Span< int > corner_verts
Span< int3 > corner_tris
LineartTriangleAdjacent * tri_adj
Span< bool > face_marks
Span< int > tri_faces
Span< int > material_indices
LineartVert * vert_arr
LineartVert * v_arr
Span< float3 > positions
double(* model_view_proj)[4]
double(* model_view)[4]
static GeometrySet from_curves(Curves *curves, GeometryOwnershipType ownership=GeometryOwnershipType::Owned)
std::shared_ptr< BMEditMesh > edit_mesh