[Bf-blender-cvs] [432c4c74ebe] master: LineArt: Speedup construction of quad trees.
Yiming Wu
noreply at git.blender.org
Thu Jun 2 15:06:27 CEST 2022
Commit: 432c4c74ebe6f66b83e06ff7fca70c96d0526d6a
Author: Yiming Wu
Date: Thu Jun 2 20:32:31 2022 +0800
Branches: master
https://developer.blender.org/rB432c4c74ebe6f66b83e06ff7fca70c96d0526d6a
LineArt: Speedup construction of quad trees.
Using multithread for `add_triangles` to speed up quad tree building.
Each thread would lock its respective tile to work on triangle insertion,
intersection calculation, tile splitting and triangle array extension.
Reviewed By: Sebastian Parborg (zeddb), Sergey Sharybin (sergey)
Ref D14953
===================================================================
M source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
M source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
M source/blender/gpencil_modifiers/intern/lineart/lineart_intern.h
===================================================================
diff --git a/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h b/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
index ad3e1b5d7f2..16b9fcbbdd7 100644
--- a/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
+++ b/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
@@ -236,6 +236,9 @@ typedef struct LineartRenderBuffer {
ListBase line_buffer_pointers;
ListBase triangle_buffer_pointers;
+ LineartElementLinkNode *isect_scheduled_up_to;
+ int isect_scheduled_up_to_index;
+
/** This one's memory is not from main pool and is free()ed after culling stage. */
ListBase triangle_adjacent_pointers;
@@ -429,15 +432,18 @@ typedef struct LineartBoundingArea {
/** 1,2,3,4 quadrant */
struct LineartBoundingArea *child;
+ SpinLock lock;
+
ListBase lp;
ListBase rp;
ListBase up;
ListBase bp;
- uint16_t triangle_count;
- uint16_t max_triangle_count;
- uint16_t line_count;
- uint16_t max_line_count;
+ uint32_t triangle_count;
+ uint32_t max_triangle_count;
+ uint32_t line_count;
+ uint32_t max_line_count;
+ uint32_t user_count;
/* Use array for speeding up multiple accesses. */
struct LineartTriangle **linked_triangles;
diff --git a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
index aae439c62a2..da4d02f9ff2 100644
--- a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
+++ b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
@@ -52,6 +52,36 @@
#include "lineart_intern.h"
+typedef struct LineartIsecSingle {
+ float v1[3], v2[3];
+ LineartTriangle *tri1, *tri2;
+} LineartIsecSingle;
+
+typedef struct LineartIsecThread {
+ int thread_id;
+
+ /* Scheduled work range. */
+ LineartElementLinkNode *pending_from;
+ LineartElementLinkNode *pending_to;
+ int index_from;
+ int index_to;
+
+ /* Thread intersection result data. */
+ LineartIsecSingle *array;
+ int current;
+ int max;
+ int count_test;
+
+ /* For individual thread reference.*/
+ 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);
@@ -76,14 +106,6 @@ static bool lineart_get_edge_bounding_areas(LineartRenderBuffer *rb,
int *colbegin,
int *colend);
-static void lineart_bounding_area_link_triangle(LineartRenderBuffer *rb,
- LineartBoundingArea *root_ba,
- LineartTriangle *tri,
- double *LRUB,
- int recursive,
- int recursive_level,
- bool do_intersection);
-
static bool lineart_triangle_edge_image_space_occlusion(SpinLock *spl,
const LineartTriangle *tri,
const LineartEdge *e,
@@ -99,6 +121,19 @@ static bool lineart_triangle_edge_image_space_occlusion(SpinLock *spl,
static void lineart_add_edge_to_array(LineartPendingEdges *pe, LineartEdge *e);
+static void lineart_bounding_area_link_triangle(LineartRenderBuffer *rb,
+ LineartBoundingArea *root_ba,
+ LineartTriangle *tri,
+ double *LRUB,
+ int recursive,
+ int recursive_level,
+ bool do_intersection,
+ struct LineartIsecThread *th);
+
+static void lineart_free_bounding_area_memory(LineartBoundingArea *ba, bool recursive);
+
+static void lineart_free_bounding_area_memories(LineartRenderBuffer *rb);
+
static LineartCache *lineart_init_cache(void);
static void lineart_discard_segment(LineartRenderBuffer *rb, LineartEdgeSegment *es)
@@ -312,29 +347,14 @@ BLI_INLINE bool lineart_occlusion_is_adjacent_intersection(LineartEdge *e, Linea
(v2->base.flag && v2->intersecting_with == tri));
}
-static void lineart_bounding_area_triangle_add(LineartRenderBuffer *rb,
- LineartBoundingArea *ba,
- LineartTriangle *tri)
-{ /* In case of too many triangles concentrating in one point, do not add anymore, these triangles
- * will be either narrower than a single pixel, or will still be added into the list of other
- * less dense areas. */
- if (ba->triangle_count >= 65535) {
- return;
- }
- if (ba->triangle_count >= ba->max_triangle_count) {
- LineartTriangle **new_array = lineart_mem_acquire(
- &rb->render_data_pool, sizeof(LineartTriangle *) * ba->max_triangle_count * 2);
- memcpy(new_array, ba->linked_triangles, sizeof(LineartTriangle *) * ba->max_triangle_count);
- ba->max_triangle_count *= 2;
- ba->linked_triangles = new_array;
- }
- ba->linked_triangles[ba->triangle_count] = tri;
- ba->triangle_count++;
+static void lineart_bounding_area_triangle_reallocate(LineartBoundingArea *ba)
+{
+ ba->max_triangle_count *= 2;
+ ba->linked_triangles = MEM_recallocN(ba->linked_triangles,
+ sizeof(LineartTriangle *) * ba->max_triangle_count);
}
-static void lineart_bounding_area_line_add(LineartRenderBuffer *rb,
- LineartBoundingArea *ba,
- LineartEdge *e)
+static void lineart_bounding_area_line_add(LineartBoundingArea *ba, LineartEdge *e)
{
/* In case of too many lines concentrating in one point, do not add anymore, these lines will
* be either shorter than a single pixel, or will still be added into the list of other less
@@ -343,10 +363,11 @@ static void lineart_bounding_area_line_add(LineartRenderBuffer *rb,
return;
}
if (ba->line_count >= ba->max_line_count) {
- LineartEdge **new_array = lineart_mem_acquire(&rb->render_data_pool,
- sizeof(LineartEdge *) * ba->max_line_count * 2);
+ LineartEdge **new_array = MEM_mallocN(sizeof(LineartEdge *) * ba->max_line_count * 2,
+ "new ba_line_array");
memcpy(new_array, ba->linked_lines, sizeof(LineartEdge *) * ba->max_line_count);
ba->max_line_count *= 2;
+ MEM_freeN(ba->linked_lines);
ba->linked_lines = new_array;
}
ba->linked_lines[ba->line_count] = e;
@@ -1679,6 +1700,7 @@ static void lineart_join_loose_edge_arr(LooseEdgeData *loose_data, LooseEdgeData
sizeof(MEdge *) * to_be_joined->loose_count);
loose_data->loose_count += to_be_joined->loose_count;
MEM_freeN(to_be_joined->loose_array);
+ to_be_joined->loose_array = NULL;
}
static void lineart_add_loose_edge(LooseEdgeData *loose_data, MEdge *e)
@@ -2104,7 +2126,7 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend
elem_link_node->element_count = allocate_la_e;
elem_link_node->object_ref = orig_ob;
- // Start of the edge/seg arr
+ /* Start of the edge/seg arr */
LineartEdge *la_edge;
LineartEdgeSegment *la_seg;
la_edge = la_edge_arr;
@@ -3001,60 +3023,23 @@ static LineartVert *lineart_triangle_share_point(const LineartTriangle *l,
return NULL;
}
-/**
- * To save time and prevent overlapping lines when computing intersection lines.
- */
-static bool lineart_vert_already_intersected_2v(LineartVertIntersection *vt,
- LineartVertIntersection *v1,
- LineartVertIntersection *v2)
-{
- return ((vt->isec1 == v1->base.index && vt->isec2 == v2->base.index) ||
- (vt->isec2 == v2->base.index && vt->isec1 == v1->base.index));
-}
-
-static void lineart_vert_set_intersection_2v(LineartVert *vt, LineartVert *v1, LineartVert *v2)
-{
- LineartVertIntersection *irv = (LineartVertIntersection *)vt;
- irv->isec1 = v1->index;
- irv->isec2 = v2->index;
-}
-
-/**
- * This tests a triangle against a virtual line represented by `v1---v2`.
- * The vertices returned after repeated calls to this function
- * is then used to create a triangle/triangle intersection line.
- */
-static LineartVert *lineart_triangle_2v_intersection_test(LineartRenderBuffer *rb,
- LineartVert *v1,
- LineartVert *v2,
- LineartTriangle *tri,
- LineartTriangle *testing,
- LineartVert *last)
+static bool lineart_triangle_2v_intersection_math(
+ LineartVert *v1, LineartVert *v2, LineartTriangle *t2, double *last, double *rv)
{
double Lv[3];
double Rv[3];
double dot_l, dot_r;
- LineartVert *result;
double gloc[3];
LineartVert *l = v1, *r = v2;
- for (LinkNode *ln = (void *)testing->intersecting_verts; ln; ln = ln->next) {
- LineartVertIntersection *vt = ln->link;
- if (vt->intersecting_with == tri &&
- lineart_vert_already_intersected_2v(
- vt, (LineartVertIntersection *)l, (LineartVertIntersection *)r)) {
- return (LineartVert *)vt;
- }
- }
-
- sub_v3_v3v3_db(Lv, l->gloc, testing->v[0]->gloc);
- sub_v3_v3v3_db(Rv, r->gloc, testing->v[0]->gloc);
+ sub_v3_v3v3_db(Lv, l->gloc, t2->v[0]->gloc);
+ sub_v3_v3v3_db(Rv, r->gloc, t2->v[0]->gloc);
- dot_l = dot_v3v3_db(Lv, testing->gn);
- dot_r = dot_v3v3_db(Rv, testing->gn);
+ dot_l = dot_v3v3_db(Lv, t2->gn);
+ dot_r = dot_v3v3_db(Rv, t2->gn);
if (dot_l * d
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list