[Bf-blender-cvs] [bb7d07ea197] temp-lineart-contained: LineArt: Thread isec
YimingWu
noreply at git.blender.org
Sun Jul 4 11:34:38 CEST 2021
Commit: bb7d07ea197f8f248f8f750ba9b468f2f6499603
Author: YimingWu
Date: Sun Jul 4 17:31:41 2021 +0800
Branches: temp-lineart-contained
https://developer.blender.org/rBbb7d07ea197f8f248f8f750ba9b468f2f6499603
LineArt: Thread isec
===================================================================
M source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
M source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
===================================================================
diff --git a/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h b/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
index 5c84f7b11d7..8e241c500d0 100644
--- a/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
+++ b/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
@@ -233,6 +233,9 @@ typedef struct LineartRenderBuffer {
struct LineartBoundingArea *initial_bounding_areas;
unsigned int bounding_area_count;
+ /* Array of thread_count length for spatial locks. */
+ SpinLock *lock_bounding_areas;
+
/* When splitting bounding areas, if there's an ortho camera placed at a straight angle, there
* will be a lot of triangles aligned in line which can not be separated by continue subdividing
* the tile. So we set a strict limit when using ortho camera. See eLineArtTileRecursiveLimit. */
@@ -453,6 +456,8 @@ typedef struct LineartBoundingArea {
/** 1,2,3,4 quadrant */
struct LineartBoundingArea *child;
+ SpinLock *lock;
+
ListBase lp;
ListBase rp;
ListBase up;
diff --git a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
index 412f73abffa..bfc1b3de3e0 100644
--- a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
+++ b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
@@ -64,6 +64,35 @@
#include "lineart_intern.h"
+typedef struct LineartIsecSingle {
+ float v1[3], v2[3];
+ LineartTriangle *tri1, *tri2;
+} LineartIsecSingle;
+typedef struct LineartIsecThread {
+ /* Thread triangle data. */
+ /* Used to roughly spread the load. */
+ int count_pending;
+ /* An array of triangle element link nodes. */
+ LineartElementLinkNode **pending_triangle_nodes;
+ /* Count of above array. */
+ int current_pending;
+ int max_pending;
+
+ /* Thread intersection result data. */
+ LineartIsecSingle *array;
+ int current;
+ int max;
+ int count_test;
+
+ /* For individual thread reference.*/
+ LineartRenderBuffer *rb;
+} LineartIsecThread;
+typedef struct LineartIsecData {
+ LineartRenderBuffer *rb;
+ LineartIsecThread *threads;
+ int thread_count;
+} LineartIsecData;
+
static LineartBoundingArea *lineart_edge_first_bounding_area(LineartRenderBuffer *rb,
LineartEdge *e);
@@ -94,7 +123,9 @@ static void lineart_bounding_area_link_triangle(LineartRenderBuffer *rb,
double *LRUB,
int recursive,
int recursive_level,
- bool do_intersection);
+ bool do_intersection,
+ bool do_lock,
+ LineartIsecThread *th);
static bool lineart_triangle_edge_image_space_occlusion(SpinLock *spl,
const LineartTriangle *tri,
@@ -329,7 +360,7 @@ static void lineart_bounding_area_triangle_add(LineartRenderBuffer *rb,
LineartTriangle *tri)
{
if (ba->triangle_count >= ba->max_triangle_count) {
- LineartTriangle **new_array = lineart_mem_acquire(
+ LineartTriangle **new_array = lineart_mem_acquire_thread(
&rb->render_data_pool, sizeof(LineartTriangle *) * ba->max_triangle_count * 2);
memcpy(new_array, ba->linked_triangles, sizeof(LineartTriangle *) * ba->max_triangle_count);
ba->max_triangle_count *= 2;
@@ -2771,6 +2802,213 @@ static LineartVert *lineart_triangle_2v_intersection_test(LineartRenderBuffer *r
return result;
}
+static bool lineart_triangle_2v_intersection_math(LineartVert *v1,
+ LineartVert *v2,
+ LineartTriangle *tri,
+ LineartTriangle *t2,
+ float *last,
+ float *rv)
+{
+ double Lv[3];
+ double Rv[3];
+ double dot_l, dot_r;
+ LineartVert *result;
+ double gloc[3];
+ LineartVert *l = v1, *r = v2;
+
+ sub_v3_v3v3_db(Lv, l->gloc, t2->v[0]->gloc);
+ sub_v3_v3v3_db(Rv, r->gloc, t2->v[0]->gloc);
+
+ dot_l = dot_v3v3_db(Lv, t2->gn);
+ dot_r = dot_v3v3_db(Rv, t2->gn);
+
+ if (dot_l * dot_r > 0 || (!dot_l && !dot_r)) {
+ return false;
+ }
+
+ dot_l = fabs(dot_l);
+ dot_r = fabs(dot_r);
+
+ interp_v3_v3v3_db(gloc, l->gloc, r->gloc, dot_l / (dot_l + dot_r));
+
+ /* Due to precision issue, we might end up with the same point as the one we already detected.
+ */
+ if (last && LRT_DOUBLE_CLOSE_ENOUGH(last[0], gloc[0]) &&
+ LRT_DOUBLE_CLOSE_ENOUGH(last[1], gloc[1]) && LRT_DOUBLE_CLOSE_ENOUGH(last[2], gloc[2])) {
+ return false;
+ }
+
+ if (!(lineart_point_inside_triangle3d(gloc, t2->v[0]->gloc, t2->v[1]->gloc, t2->v[2]->gloc))) {
+ return false;
+ }
+
+ copy_v3fl_v3db(rv, gloc);
+
+ return true;
+}
+
+static bool lineart_triangle_intersect_math(LineartTriangle *tri,
+ LineartTriangle *t2,
+ float *v1,
+ float *v2)
+{
+ float *next = v1, *last = NULL;
+ LineartVert *sv1, *sv2;
+ double cl[3];
+
+ LineartVert *share = lineart_triangle_share_point(t2, tri);
+
+ if (share) {
+ /* If triangles have sharing points like `abc` and `acd`, then we only need to detect `bc`
+ * against `acd` or `cd` against `abc`. */
+
+ LineartVert *new_share;
+ lineart_triangle_get_other_verts(tri, share, &sv1, &sv2);
+
+ copy_v3fl_v3db(v1, share->gloc);
+
+ if (!lineart_triangle_2v_intersection_math(sv1, sv2, tri, t2, 0, v2)) {
+ lineart_triangle_get_other_verts(t2, share, &sv1, &sv2);
+ if (lineart_triangle_2v_intersection_math(sv1, sv2, t2, tri, 0, v2)) {
+ return true;
+ }
+ }
+ }
+ else {
+ /* If not sharing any points, then we need to try all the possibilities. */
+
+ if (lineart_triangle_2v_intersection_math(tri->v[0], tri->v[1], tri, t2, 0, v1)) {
+ next = v2;
+ last = v1;
+ }
+
+ if (lineart_triangle_2v_intersection_math(tri->v[1], tri->v[2], tri, t2, last, next)) {
+ if (last) {
+ return true;
+ }
+ next = v2;
+ last = v1;
+ }
+ if (lineart_triangle_2v_intersection_math(tri->v[2], tri->v[0], tri, t2, last, next)) {
+ if (last) {
+ return true;
+ }
+ next = v2;
+ last = v1;
+ }
+
+ if (lineart_triangle_2v_intersection_math(t2->v[0], t2->v[1], t2, tri, last, next)) {
+ if (last) {
+ return true;
+ }
+ next = v2;
+ last = v1;
+ }
+ if (lineart_triangle_2v_intersection_math(t2->v[1], t2->v[2], t2, tri, last, next)) {
+ if (last) {
+ return true;
+ }
+ next = v2;
+ last = v1;
+ }
+ if (lineart_triangle_2v_intersection_math(t2->v[2], t2->v[0], t2, tri, last, next)) {
+ if (last) {
+ return true;
+ }
+ next = v2;
+ last = v1;
+ }
+ }
+ return false;
+}
+
+static void lineart_add_isec_thread(LineartIsecThread *th,
+ const float *v1,
+ const float *v2,
+ LineartTriangle *tri1,
+ LineartTriangle *tri2)
+{
+ if (th->current == th->max) {
+
+ LineartIsecSingle *new_array = MEM_mallocN(sizeof(LineartIsecSingle) * th->max * 2,
+ "LineartIsecSingle");
+ memcpy(new_array, th->array, sizeof(LineartIsecSingle) * th->max);
+ th->max *= 2;
+ MEM_freeN(th->array);
+ th->array = new_array;
+ }
+ LineartIsecSingle *is = &th->array[th->current];
+ copy_v3_v3(is->v1, v1);
+ copy_v3_v3(is->v2, v2);
+ is->tri1 = tri1;
+ is->tri2 = tri2;
+ th->current++;
+}
+
+static void lineart_add_eln_thread(LineartIsecThread *th, LineartElementLinkNode *eln)
+{
+ if (th->current_pending == th->max_pending) {
+
+ LineartElementLinkNode *new_array = MEM_mallocN(
+ sizeof(LineartElementLinkNode *) * th->max_pending * 2, "LineartIsecSingle");
+ memcpy(
+ new_array, th->pending_triangle_nodes, sizeof(LineartElementLinkNode *) * th->max_pending);
+ th->max_pending *= 2;
+ MEM_freeN(th->pending_triangle_nodes);
+ th->pending_triangle_nodes = new_array;
+ }
+ th->pending_triangle_nodes[th->current_pending] = eln;
+ th->count_pending += eln->element_count;
+ th->current_pending++;
+}
+
+static void lineart_init_isec_thread(LineartIsecData *d, LineartRenderBuffer *rb, int thread_count)
+{
+ d->threads = MEM_callocN(sizeof(LineartIsecThread) * thread_count, "LineartIsecThread arr");
+ d->rb = rb;
+ d->thread_count = thread_count;
+ for (int i = 0; i < thread_count; i++) {
+ LineartIsecThread *it = &d->threads[i];
+ it->array = MEM_mallocN(sizeof(LineartIsecSingle) * 100, "LineartIsecSingle arr");
+ it->max = 100;
+ it->current = 0;
+ }
+
+#define OBJ_PER_ISEC_THREAD 8 /* Largely arbitrary, no need to be big. */
+ for (int i = 0; i < thread_count; i++) {
+ LineartIsecThread *it = &d->threads[i];
+ it->pending_triangle_nodes = MEM_mallocN(
+ sizeof(LineartElementLinkNode *) * OBJ_PER_ISEC_THREAD, "LineartIsec eln arr");
+ it->max_pending = OBJ_PER_ISEC_THREAD;
+ it->current_pending = 0;
+ it->rb = rb;
+ }
+#undef OBJ_PER_ISEC_THREAD
+
+ for (LineartElementLinkNode *eln = rb->triangle_buffer_pointers.first; eln; eln = eln->next) {
+ /* Find threads with least triangle count inside. */
+ LineartIsecThread *min_tri = &d->threads[0];
+ for (int i = 0; i < thread_count; i++) {
+ LineartIsecThread *it = &d->threads[i];
+ if (min_tri->count_pending > it->count_pending) {
+ min_tri = it;
+ }
+ }
+ /* Assign it. */
+ lineart_add_eln_thread(min_tri, eln);
+ }
+}
+
+static void lineart_destroy_isec_thread(LineartIsecData *d)
+{
+ for (int i = 0; i < d->thread_count; i++) {
+ LineartIsecThr
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list