1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
|
/*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*
* The Original Code is Copyright (C) 2008 Blender Foundation.
* All rights reserved.
*/
/** \file
* \ingroup editors
*/
#pragma once
#include "BLI_linklist.h"
#include "BLI_listbase.h"
#include "BLI_math.h"
#include "BLI_threads.h"
#include "DNA_lineart_types.h"
#include <math.h>
#include <string.h>
typedef struct LineartStaticMemPoolNode {
Link item;
size_t size;
size_t used_byte;
/* User memory starts here */
} LineartStaticMemPoolNode;
typedef struct LineartStaticMemPool {
ListBase pools;
SpinLock lock_mem;
} LineartStaticMemPool;
typedef struct LineartTriangleAdjacent {
struct LineartEdge *e[3];
} LineartTriangleAdjacent;
typedef struct LineartTriangle {
struct LineartVert *v[3];
/* first culled in line list to use adjacent triangle info, then go through triangle list. */
double gn[3];
/* Material flag is removed to save space. */
unsigned char transparency_mask;
unsigned char flags; /* eLineartTriangleFlags */
/* Only use single link list, because we don't need to go back in order.
* This variable is also reused to store the pointer to adjacent lines of this triangle before
* intersection statge */
struct LinkNode *intersecting_verts;
} LineartTriangle;
typedef struct LineartTriangleThread {
struct LineartTriangle base;
/* This variable is used to store per-thread triangle-line testing pair,
* also re-used to store triangle-triangle pair for intersection testing stage.
* Do not directly use LineartTriangleThread.
* The size of LineartTriangle is dynamically allocated to contain set thread number of
* "testing_e" field. Worker threads will test lines against the "base" triangle.
* At least one thread is present, thus we always have at least testing_e[0]. */
struct LineartEdge *testing_e[1];
} LineartTriangleThread;
typedef enum eLineArtElementNodeFlag {
LRT_ELEMENT_IS_ADDITIONAL = (1 << 0),
LRT_ELEMENT_BORDER_ONLY = (1 << 1),
LRT_ELEMENT_NO_INTERSECTION = (1 << 2),
} eLineArtElementNodeFlag;
typedef struct LineartElementLinkNode {
struct LineartElementLinkNode *next, *prev;
void *pointer;
int element_count;
void *object_ref;
eLineArtElementNodeFlag flags;
/* Per object value, always set, if not enabled by ObjectLineArt, then it's set to global. */
float crease_threshold;
} LineartElementLinkNode;
typedef struct LineartLineSegment {
struct LineartLineSegment *next, *prev;
/** at==0: left at==1: right (this is in 2D projected space) */
double at;
/** Occlusion level after "at" point */
unsigned char occlusion;
/** For determining lines beind a glass window material.
* the size of this variable should also be dynamically decided, 1 byte to 8 byte,
* allows 8 to 64 materials for "transparent mask". 1 byte (8 materials) should be
* enought for most cases.
*/
unsigned char transparency_mask;
} LineartLineSegment;
typedef struct LineartVert {
double gloc[3];
double fbcoord[4];
/* Scene global index. */
int index;
/** Intersection data flag is here, when LRT_VERT_HAS_INTERSECTION_DATA is set,
* size of the struct is extended to include intersection data.
* See eLineArtVertFlags.
*/
char flag;
} LineartVert;
typedef struct LineartVertIntersection {
struct LineartVert base;
/* Use vert index because we only use this to check vertex equal. This way we save 8 Bytes. */
int isec1, isec2;
struct LineartTriangle *intersecting_with;
} LineartVertIntersection;
typedef enum eLineArtVertFlags {
LRT_VERT_HAS_INTERSECTION_DATA = (1 << 0),
LRT_VERT_EDGE_USED = (1 << 1),
} eLineArtVertFlags;
typedef struct LineartEdge {
/* We only need link node kind of list here. */
struct LineartEdge *next;
struct LineartVert *v1, *v2;
/* Local vertex index for two ends, not puting in RenderVert because all verts are loaded, so as
* long as fewer than half of the mesh edges are becoming a feature line, we save more memory. */
int v1_obindex, v2_obindex;
struct LineartTriangle *t1, *t2;
ListBase segments;
char min_occ;
/** Also for line type determination on chainning */
unsigned char flags;
/** Still need this entry because culled lines will not add to object reln node,
* TODO: If really need more savings, we can allocate this in a "extended" way too, but we need
* another bit in flags to be able to show the difference.
*/
struct Object *object_ref;
} LineartEdge;
typedef struct LineartLineChain {
struct LineartLineChain *next, *prev;
ListBase chain;
/** Calculated before draw cmd. */
float length;
/** Used when re-connecting and gp stroke generation */
char picked;
char level;
/** Chain now only contains one type of segments */
int type;
unsigned char transparency_mask;
struct Object *object_ref;
} LineartLineChain;
typedef struct LineartLineChainItem {
struct LineartLineChainItem *next, *prev;
/** Need z value for fading */
float pos[3];
/** For restoring position to 3d space */
float gpos[3];
float normal[3];
char line_type;
char occlusion;
unsigned char transparency_mask;
size_t index;
} LineartLineChainItem;
typedef struct LineartChainRegisterEntry {
struct LineartChainRegisterEntry *next, *prev;
LineartLineChain *rlc;
LineartLineChainItem *rlci;
char picked;
/* left/right mark.
* Because we revert list in chaining so we need the flag. */
char is_left;
} LineartChainRegisterEntry;
typedef struct LineartRenderBuffer {
struct LineartRenderBuffer *prev, *next;
int thread_count;
int w, h;
int tile_size_w, tile_size_h;
int tile_count_x, tile_count_y;
double width_per_tile, height_per_tile;
double view_projection[4][4];
struct LineartBoundingArea *initial_bounding_areas;
unsigned int bounding_area_count;
ListBase vertex_buffer_pointers;
ListBase line_buffer_pointers;
ListBase triangle_buffer_pointers;
/* This one's memory is not from main pool and is free()ed after culling stage. */
ListBase triangle_adjacent_pointers;
ListBase intersecting_vertex_buffer;
/* Use the one comes with Line Art. */
LineartStaticMemPool render_data_pool;
ListBase wasted_cuts;
SpinLock lock_cuts;
/* Render status */
double view_vector[3];
int triangle_size;
unsigned int contour_count;
unsigned int contour_processed;
LineartEdge *contour_managed;
/* Now changed to linknodes. */
LineartEdge *contours;
unsigned int intersection_count;
unsigned int intersection_processed;
LineartEdge *intersection_managed;
LineartEdge *intersection_lines;
unsigned int crease_count;
unsigned int crease_processed;
LineartEdge *crease_managed;
LineartEdge *crease_lines;
unsigned int material_line_count;
unsigned int material_processed;
LineartEdge *material_managed;
LineartEdge *material_lines;
unsigned int edge_mark_count;
unsigned int edge_mark_processed;
LineartEdge *edge_mark_managed;
LineartEdge *edge_marks;
ListBase chains;
/* For managing calculation tasks for multiple threads. */
SpinLock lock_task;
/* settings */
int max_occlusion_level;
double crease_angle;
double crease_cos;
int draw_material_preview;
double material_transparency;
bool use_contour;
bool use_crease;
bool use_material;
bool use_edge_marks;
bool use_intersections;
bool fuzzy_intersections;
bool fuzzy_everything;
bool allow_boundaries;
bool allow_overlapping_edges;
bool remove_doubles;
/* Keep an copy of these data so when line art is running it's self-contained. */
bool cam_is_persp;
float cam_obmat[4][4];
double camera_pos[3];
double near_clip, far_clip;
float shift_x, shift_y;
float crease_threshold;
float chaining_image_threshold;
float chaining_geometry_threshold;
float angle_splitting_threshold;
/* FIXME: (Yiming) Temporary solution for speeding up calculation by not including lines that
* are not in the selected source. This will not be needed after we have a proper scene-wise
* cache running because multiple modifiers can then select results from that without further
* calculation. */
int _source_type;
struct Collection *_source_collection;
struct Object *_source_object;
} LineartRenderBuffer;
#define DBL_TRIANGLE_LIM 1e-8
#define DBL_EDGE_LIM 1e-9
#define LRT_MEMORY_POOL_64MB (1 << 26)
typedef enum eLineartTriangleFlags {
LRT_CULL_DONT_CARE = 0,
LRT_CULL_USED = (1 << 0),
LRT_CULL_DISCARD = (1 << 1),
LRT_CULL_GENERATED = (1 << 2),
LRT_TRIANGLE_INTERSECTION_ONLY = (1 << 3),
LRT_TRIANGLE_NO_INTERSECTION = (1 << 4),
} eLineartTriangleFlags;
/** Controls how many edges a worker thread is processing at one request.
* There's no significant performance impact on choosing different values.
* Don't make it too small so that the worker thread won't request too many times. */
#define LRT_THREAD_EDGE_COUNT 1000
typedef struct LineartRenderTaskInfo {
struct LineartRenderBuffer *rb;
int thread_id;
LineartEdge *contour;
LineartEdge *contour_end;
LineartEdge *intersection;
LineartEdge *intersection_end;
LineartEdge *crease;
LineartEdge *crease_end;
LineartEdge *material;
LineartEdge *material_end;
LineartEdge *edge_mark;
LineartEdge *edge_mark_end;
} LineartRenderTaskInfo;
/** Bounding area diagram:
*
* +----+ <----U (Upper edge Y value)
* | |
* +----+ <----B (Bottom edge Y value)
* ^ ^
* L R (Left/Right edge X value)
*
* Example structure when subdividing 1 bounding areas:
* 1 area can be divided into 4 smaller children to
* accomodate image areas with denser triangle distribution.
* +--+--+-----+
* +--+--+ |
* +--+--+-----+
* | | |
* +-----+-----+
* lp/rp/up/bp is the list for
* storing pointers to adjacent bounding areas.
*/
typedef struct LineartBoundingArea {
double l, r, u, b;
double cx, cy;
/** 1,2,3,4 quadrant */
struct LineartBoundingArea *child;
ListBase lp;
ListBase rp;
ListBase up;
ListBase bp;
short triangle_count;
ListBase linked_triangles;
ListBase linked_lines;
/** Reserved for image space reduction && multithread chainning */
ListBase linked_chains;
} LineartBoundingArea;
#define LRT_TILE(tile, r, c, CCount) tile[r * CCount + c]
#define LRT_CLAMP(a, Min, Max) a = a < Min ? Min : (a > Max ? Max : a)
#define LRT_MAX3_INDEX(a, b, c) (a > b ? (a > c ? 0 : (b > c ? 1 : 2)) : (b > c ? 1 : 2))
#define LRT_MIN3_INDEX(a, b, c) (a < b ? (a < c ? 0 : (b < c ? 1 : 2)) : (b < c ? 1 : 2))
#define LRT_MAX3_INDEX_ABC(x, y, z) (x > y ? (x > z ? a : (y > z ? b : c)) : (y > z ? b : c))
#define LRT_MIN3_INDEX_ABC(x, y, z) (x < y ? (x < z ? a : (y < z ? b : c)) : (y < z ? b : c))
#define LRT_ABC(index) (index == 0 ? a : (index == 1 ? b : c))
#define LRT_DOUBLE_CLOSE_ENOUGH(a, b) (((a) + DBL_EDGE_LIM) >= (b) && ((a)-DBL_EDGE_LIM) <= (b))
BLI_INLINE int lineart_LineIntersectTest2d(
const double *a1, const double *a2, const double *b1, const double *b2, double *aRatio)
{
#define USE_VECTOR_LINE_INTERSECTION
#ifdef USE_VECTOR_LINE_INTERSECTION
/* from isect_line_line_v2_point() */
double s10[2], s32[2];
double div;
sub_v2_v2v2_db(s10, a2, a1);
sub_v2_v2v2_db(s32, b2, b1);
div = cross_v2v2_db(s10, s32);
if (div != 0.0f) {
const double u = cross_v2v2_db(a2, a1);
const double v = cross_v2v2_db(b2, b1);
const double rx = ((s32[0] * u) - (s10[0] * v)) / div;
const double ry = ((s32[1] * u) - (s10[1] * v)) / div;
double rr;
if (fabs(a2[0] - a1[0]) > fabs(a2[1] - a1[1])) {
*aRatio = ratiod(a1[0], a2[0], rx);
if (fabs(b2[0] - b1[0]) > fabs(b2[1] - b1[1])) {
rr = ratiod(b1[0], b2[0], rx);
}
else {
rr = ratiod(b1[1], b2[1], ry);
}
if ((*aRatio) > 0 && (*aRatio) < 1 && rr > 0 && rr < 1) {
return 1;
}
return 0;
}
*aRatio = ratiod(a1[1], a2[1], ry);
if (fabs(b2[0] - b1[0]) > fabs(b2[1] - b1[1])) {
rr = ratiod(b1[0], b2[0], rx);
}
else {
rr = ratiod(b1[1], b2[1], ry);
}
if ((*aRatio) > 0 && (*aRatio) < 1 && rr > 0 && rr < 1) {
return 1;
}
return 0;
}
return 0;
#else
double k1, k2;
double x;
double y;
double ratio;
double x_diff = (a2[0] - a1[0]);
double x_diff2 = (b2[0] - b1[0]);
if (LRT_DOUBLE_CLOSE_ENOUGH(x_diff, 0)) {
if (LRT_DOUBLE_CLOSE_ENOUGH(x_diff2, 0)) {
*aRatio = 0;
return 0;
}
double r2 = ratiod(b1[0], b2[0], a1[0]);
x = interpd(b2[0], b1[0], r2);
y = interpd(b2[1], b1[1], r2);
*aRatio = ratio = ratiod(a1[1], a2[1], y);
}
else {
if (LRT_DOUBLE_CLOSE_ENOUGH(x_diff2, 0)) {
ratio = ratiod(a1[0], a2[0], b1[0]);
x = interpd(a2[0], a1[0], ratio);
*aRatio = ratio;
}
else {
k1 = (a2[1] - a1[1]) / x_diff;
k2 = (b2[1] - b1[1]) / x_diff2;
if ((k1 == k2))
return 0;
x = (a1[1] - b1[1] - k1 * a1[0] + k2 * b1[0]) / (k2 - k1);
ratio = (x - a1[0]) / x_diff;
*aRatio = ratio;
}
}
if (LRT_DOUBLE_CLOSE_ENOUGH(b1[0], b2[0])) {
y = interpd(a2[1], a1[1], ratio);
if (y > MAX2(b1[1], b2[1]) || y < MIN2(b1[1], b2[1]))
return 0;
}
else if (ratio <= 0 || ratio > 1 || (b1[0] > b2[0] && x > b1[0]) ||
(b1[0] < b2[0] && x < b1[0]) || (b2[0] > b1[0] && x > b2[0]) ||
(b2[0] < b1[0] && x < b2[0]))
return 0;
return 1;
#endif
}
struct Depsgraph;
struct Scene;
struct LineartRenderBuffer;
struct LineartGpencilModifierData;
void MOD_lineart_destroy_render_data(struct LineartGpencilModifierData *lmd);
void MOD_lineart_chain_feature_lines(LineartRenderBuffer *rb);
void MOD_lineart_chain_split_for_fixed_occlusion(LineartRenderBuffer *rb);
void MOD_lineart_chain_connect(LineartRenderBuffer *rb, const bool do_geometry_space);
void MOD_lineart_chain_discard_short(LineartRenderBuffer *rb, const float threshold);
void MOD_lineart_chain_split_angle(LineartRenderBuffer *rb, float angle_threshold_rad);
int MOD_lineart_chain_count(const LineartLineChain *rlc);
void MOD_lineart_chain_clear_picked_flag(struct LineartRenderBuffer *rb);
int MOD_lineart_compute_feature_lines(struct Depsgraph *depsgraph,
struct LineartGpencilModifierData *lmd);
struct Scene;
LineartBoundingArea *MOD_lineart_get_parent_bounding_area(LineartRenderBuffer *rb,
double x,
double y);
LineartBoundingArea *MOD_lineart_get_bounding_area(LineartRenderBuffer *rb, double x, double y);
struct bGPDlayer;
struct bGPDframe;
struct GpencilModifierData;
void MOD_lineart_gpencil_generate(LineartRenderBuffer *rb,
struct Depsgraph *depsgraph,
struct Object *ob,
struct bGPDlayer *gpl,
struct bGPDframe *gpf,
char source_type,
void *source_reference,
int level_start,
int level_end,
int mat_nr,
short edge_types,
unsigned char transparency_flags,
unsigned char transparency_mask,
short thickness,
float opacity,
float pre_sample_length,
const char *source_vgname,
const char *vgname,
int modifier_flags);
float MOD_lineart_chain_compute_length(LineartLineChain *rlc);
struct wmOperatorType;
void ED_operatortypes_lineart(void);
|