1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 *
16 * Copyright (C) 2019 Blender Foundation.
17 * All rights reserved.
18 */
19
20 /** \file
21 * \ingroup bke
22 */
23
24 #include <float.h>
25 #include <math.h>
26 #include <stdlib.h>
27 #include <string.h>
28
29 #include "MEM_guardedalloc.h"
30
31 #include "DNA_curve_types.h"
32 #include "DNA_curveprofile_types.h"
33
34 #include "BLI_blenlib.h"
35 #include "BLI_math.h"
36 #include "BLI_task.h"
37 #include "BLI_threads.h"
38 #include "BLI_utildefines.h"
39
40 #include "BKE_curve.h"
41 #include "BKE_curveprofile.h"
42 #include "BKE_fcurve.h"
43
44 #include "BLO_read_write.h"
45
BKE_curveprofile_free_data(CurveProfile * profile)46 void BKE_curveprofile_free_data(CurveProfile *profile)
47 {
48 MEM_SAFE_FREE(profile->path);
49 MEM_SAFE_FREE(profile->table);
50 MEM_SAFE_FREE(profile->segments);
51 }
52
BKE_curveprofile_free(CurveProfile * profile)53 void BKE_curveprofile_free(CurveProfile *profile)
54 {
55 if (profile) {
56 BKE_curveprofile_free_data(profile);
57 MEM_freeN(profile);
58 }
59 }
60
BKE_curveprofile_copy_data(CurveProfile * target,const CurveProfile * profile)61 void BKE_curveprofile_copy_data(CurveProfile *target, const CurveProfile *profile)
62 {
63 *target = *profile;
64
65 target->path = MEM_dupallocN(profile->path);
66 target->table = MEM_dupallocN(profile->table);
67 target->segments = MEM_dupallocN(profile->segments);
68
69 /* Update the reference the points have to the profile. */
70 for (int i = 0; i < target->path_len; i++) {
71 target->path[i].profile = target;
72 }
73 }
74
BKE_curveprofile_copy(const CurveProfile * profile)75 CurveProfile *BKE_curveprofile_copy(const CurveProfile *profile)
76 {
77 if (profile) {
78 CurveProfile *new_prdgt = MEM_dupallocN(profile);
79 BKE_curveprofile_copy_data(new_prdgt, profile);
80 return new_prdgt;
81 }
82 return NULL;
83 }
84
85 /**
86 * Move a point's handle, accounting for the alignment of handles with the #HD_ALIGN type.
87 *
88 * \param handle_1: Whether to move the 1st or 2nd control point.
89 * \param delta: The *relative* change in the handle's position.
90 * \note Requires #BKE_curveprofile_update call after.
91 * \return Whether the handle moved from its start position.
92 */
BKE_curveprofile_move_handle(struct CurveProfilePoint * point,const bool handle_1,const bool snap,const float delta[2])93 bool BKE_curveprofile_move_handle(struct CurveProfilePoint *point,
94 const bool handle_1,
95 const bool snap,
96 const float delta[2])
97 {
98 short handle_type = (handle_1) ? point->h1 : point->h2;
99 float *handle_location = (handle_1) ? &point->h1_loc[0] : &point->h2_loc[0];
100
101 float start_position[2];
102 copy_v2_v2(start_position, handle_location);
103
104 /* Don't move the handle if it's not a free handle type. */
105 if (!ELEM(handle_type, HD_FREE, HD_ALIGN)) {
106 return false;
107 }
108
109 /* Move the handle. */
110 handle_location[0] += delta ? delta[0] : 0.0f;
111 handle_location[1] += delta ? delta[1] : 0.0f;
112 if (snap) {
113 handle_location[0] = 0.125f * roundf(8.0f * handle_location[0]);
114 handle_location[1] = 0.125f * roundf(8.0f * handle_location[1]);
115 }
116
117 /* Move the other handle if they are aligned. */
118 if (handle_type == HD_ALIGN) {
119 short other_handle_type = (handle_1) ? point->h2 : point->h1;
120 if (other_handle_type == HD_ALIGN) {
121 float *other_handle_location = (handle_1) ? &point->h2_loc[0] : &point->h1_loc[0];
122 other_handle_location[0] = 2.0f * point->x - handle_location[0];
123 other_handle_location[1] = 2.0f * point->y - handle_location[1];
124 }
125 }
126
127 if (!equals_v2v2(handle_location, start_position)) {
128 return true;
129 }
130 return false;
131 }
132
133 /**
134 * Moves a control point, accounting for clipping and snapping, and moving free handles.
135 *
136 * \param snap: Whether to snap the point to the grid
137 * \param delta: The *relative* change of the point's location.
138 * \return Whether the point moved from its start position.
139 * \note Requires #BKE_curveprofile_update call after.
140 */
BKE_curveprofile_move_point(struct CurveProfile * profile,struct CurveProfilePoint * point,const bool snap,const float delta[2])141 bool BKE_curveprofile_move_point(struct CurveProfile *profile,
142 struct CurveProfilePoint *point,
143 const bool snap,
144 const float delta[2])
145 {
146 /* Don't move the final point. */
147 if (point == &profile->path[profile->path_len - 1]) {
148 return false;
149 }
150 /* Don't move the first point. */
151 if (point == profile->path) {
152 return false;
153 }
154 float origx = point->x;
155 float origy = point->y;
156
157 point->x += delta[0];
158 point->y += delta[1];
159 if (snap) {
160 point->x = 0.125f * roundf(8.0f * point->x);
161 point->y = 0.125f * roundf(8.0f * point->y);
162 }
163
164 /* Clip here instead to test clipping here to stop handles from moving too. */
165 if (profile->flag & PROF_USE_CLIP) {
166 point->x = max_ff(point->x, profile->clip_rect.xmin);
167 point->x = min_ff(point->x, profile->clip_rect.xmax);
168 point->y = max_ff(point->y, profile->clip_rect.ymin);
169 point->y = min_ff(point->y, profile->clip_rect.ymax);
170 }
171
172 /* Also move free handles even when they aren't selected. */
173 if (ELEM(point->h1, HD_FREE, HD_ALIGN)) {
174 point->h1_loc[0] += point->x - origx;
175 point->h1_loc[1] += point->y - origy;
176 }
177 if (ELEM(point->h2, HD_FREE, HD_ALIGN)) {
178 point->h2_loc[0] += point->x - origx;
179 point->h2_loc[1] += point->y - origy;
180 }
181
182 if (point->x != origx || point->y != origy) {
183 return true;
184 }
185 return false;
186 }
187
188 /**
189 * Removes a specific point from the path of control points.
190 * \note Requires #BKE_curveprofile_update call after.
191 */
BKE_curveprofile_remove_point(CurveProfile * profile,CurveProfilePoint * point)192 bool BKE_curveprofile_remove_point(CurveProfile *profile, CurveProfilePoint *point)
193 {
194 /* Must have 2 points minimum. */
195 if (profile->path_len <= 2) {
196 return false;
197 }
198
199 /* Input point must be within the array. */
200 if (!(point > profile->path && point < profile->path + profile->path_len)) {
201 return false;
202 }
203
204 CurveProfilePoint *new_path = MEM_mallocN(sizeof(CurveProfilePoint) * profile->path_len,
205 "profile path");
206
207 int i_delete = (int)(point - profile->path);
208 BLI_assert(i_delete > 0);
209
210 /* Copy the before and after the deleted point. */
211 memcpy(new_path, profile->path, sizeof(CurveProfilePoint) * i_delete);
212 memcpy(new_path + i_delete,
213 profile->path + i_delete + 1,
214 sizeof(CurveProfilePoint) * (profile->path_len - i_delete - 1));
215
216 MEM_freeN(profile->path);
217 profile->path = new_path;
218 profile->path_len -= 1;
219 return true;
220 }
221
222 /**
223 * Removes every point in the widget with the supplied flag set, except for the first and last.
224 *
225 * \param flag: #CurveProfilePoint.flag.
226 *
227 * \note Requires #BKE_curveprofile_update call after.
228 */
BKE_curveprofile_remove_by_flag(CurveProfile * profile,const short flag)229 void BKE_curveprofile_remove_by_flag(CurveProfile *profile, const short flag)
230 {
231 /* Copy every point without the flag into the new path. */
232 CurveProfilePoint *new_path = MEM_mallocN(sizeof(CurveProfilePoint) * profile->path_len,
233 "profile path");
234
235 /* Build the new list without any of the points with the flag. Keep the first and last points. */
236 int i_new = 1;
237 int i_old = 1;
238 int n_removed = 0;
239 new_path[0] = profile->path[0];
240 for (; i_old < profile->path_len - 1; i_old++) {
241 if (!(profile->path[i_old].flag & flag)) {
242 new_path[i_new] = profile->path[i_old];
243 i_new++;
244 }
245 else {
246 n_removed++;
247 }
248 }
249 new_path[i_new] = profile->path[i_old];
250
251 MEM_freeN(profile->path);
252 profile->path = new_path;
253 profile->path_len -= n_removed;
254 }
255
256 /**
257 * Shorthand helper function for setting location and interpolation of a point.
258 */
point_init(CurveProfilePoint * point,float x,float y,short flag,char h1,char h2)259 static void point_init(CurveProfilePoint *point, float x, float y, short flag, char h1, char h2)
260 {
261 point->x = x;
262 point->y = y;
263 point->flag = flag;
264 point->h1 = h1;
265 point->h2 = h2;
266 }
267
268 /**
269 * Adds a new point at the specified location. The choice for which points to place the new vertex
270 * between is made by checking which control point line segment is closest to the new point and
271 * placing the new vertex in between that segment's points.
272 *
273 * \note Requires #BKE_curveprofile_update call after.
274 */
BKE_curveprofile_insert(CurveProfile * profile,float x,float y)275 CurveProfilePoint *BKE_curveprofile_insert(CurveProfile *profile, float x, float y)
276 {
277 const float new_loc[2] = {x, y};
278
279 /* Don't add more control points than the maximum size of the higher resolution table. */
280 if (profile->path_len == PROF_TABLE_MAX - 1) {
281 return NULL;
282 }
283
284 /* Find the index at the line segment that's closest to the new position. */
285 float min_distance = FLT_MAX;
286 int i_insert = 0;
287 for (int i = 0; i < profile->path_len - 1; i++) {
288 const float loc1[2] = {profile->path[i].x, profile->path[i].y};
289 const float loc2[2] = {profile->path[i + 1].x, profile->path[i + 1].y};
290
291 float distance = dist_squared_to_line_segment_v2(new_loc, loc1, loc2);
292 if (distance < min_distance) {
293 min_distance = distance;
294 i_insert = i + 1;
295 }
296 }
297
298 /* Insert the new point at the location we found and copy all of the old points in as well. */
299 profile->path_len++;
300 CurveProfilePoint *new_path = MEM_mallocN(sizeof(CurveProfilePoint) * profile->path_len,
301 "profile path");
302 CurveProfilePoint *new_pt = NULL;
303 for (int i_new = 0, i_old = 0; i_new < profile->path_len; i_new++) {
304 if (i_new != i_insert) {
305 /* Insert old points. */
306 new_path[i_new] = profile->path[i_old];
307 new_path[i_new].flag &= ~PROF_SELECT; /* Deselect old points. */
308 i_old++;
309 }
310 else {
311 /* Insert new point. */
312 /* Set handles of new point based on its neighbors. */
313 char new_handle_type = (new_path[i_new - 1].h2 == HD_VECT &&
314 profile->path[i_insert].h1 == HD_VECT) ?
315 HD_VECT :
316 HD_AUTO;
317 point_init(&new_path[i_new], x, y, PROF_SELECT, new_handle_type, new_handle_type);
318 new_pt = &new_path[i_new];
319 /* Give new point a reference to the profile. */
320 new_pt->profile = profile;
321 }
322 }
323
324 /* Free the old path and use the new one. */
325 MEM_freeN(profile->path);
326 profile->path = new_path;
327 return new_pt;
328 }
329
330 /**
331 * Sets the handle type of the selected control points.
332 * \param type_1, type_2: Handle type for the first handle. HD_VECT, HD_AUTO, HD_FREE, or HD_ALIGN.
333 * \note Requires #BKE_curveprofile_update call after.
334 */
BKE_curveprofile_selected_handle_set(CurveProfile * profile,int type_1,int type_2)335 void BKE_curveprofile_selected_handle_set(CurveProfile *profile, int type_1, int type_2)
336 {
337 for (int i = 0; i < profile->path_len; i++) {
338 if (ELEM(profile->path[i].flag, PROF_SELECT, PROF_H1_SELECT, PROF_H2_SELECT)) {
339 profile->path[i].h1 = type_1;
340 profile->path[i].h2 = type_2;
341
342 if (type_1 == HD_ALIGN && type_2 == HD_ALIGN) {
343 /* Align the handles. */
344 BKE_curveprofile_move_handle(&profile->path[i], true, false, NULL);
345 }
346 }
347 }
348 }
349
mirror_point(const CurveProfilePoint * point)350 static CurveProfilePoint mirror_point(const CurveProfilePoint *point)
351 {
352 CurveProfilePoint new_point = *point;
353 point_init(&new_point, point->y, point->x, point->flag, point->h2, point->h1);
354 return new_point;
355 }
356
357 /**
358 * Flips the profile across the diagonal so that its orientation is reversed.
359 *
360 * \note Requires #BKE_curveprofile_update call after.
361 */
BKE_curveprofile_reverse(CurveProfile * profile)362 void BKE_curveprofile_reverse(CurveProfile *profile)
363 {
364 /* When there are only two points, reversing shouldn't do anything. */
365 if (profile->path_len == 2) {
366 return;
367 }
368 CurveProfilePoint *new_path = MEM_mallocN(sizeof(CurveProfilePoint) * profile->path_len,
369 "profile path");
370 /* Mirror the new points across the y = x line */
371 for (int i = 0; i < profile->path_len; i++) {
372 int i_reversed = profile->path_len - i - 1;
373 BLI_assert(i_reversed >= 0);
374 new_path[i_reversed] = mirror_point(&profile->path[i]);
375 new_path[i_reversed].profile = profile;
376
377 /* Mirror free handles, they can't be recalculated. */
378 if (ELEM(profile->path[i].h1, HD_FREE, HD_ALIGN)) {
379 new_path[i_reversed].h1_loc[0] = profile->path[i].h2_loc[1];
380 new_path[i_reversed].h1_loc[1] = profile->path[i].h2_loc[0];
381 }
382 if (ELEM(profile->path[i].h2, HD_FREE, HD_ALIGN)) {
383 new_path[i_reversed].h2_loc[0] = profile->path[i].h1_loc[1];
384 new_path[i_reversed].h2_loc[1] = profile->path[i].h1_loc[0];
385 }
386 }
387
388 /* Free the old points and use the new ones */
389 MEM_freeN(profile->path);
390 profile->path = new_path;
391 }
392
393 /**
394 * Builds a quarter circle profile with space on each side for 'support loops.'
395 */
curveprofile_build_supports(CurveProfile * profile)396 static void curveprofile_build_supports(CurveProfile *profile)
397 {
398 int n = profile->path_len;
399
400 point_init(&profile->path[0], 1.0f, 0.0f, 0, HD_VECT, HD_VECT);
401 point_init(&profile->path[1], 1.0f, 0.5f, 0, HD_VECT, HD_VECT);
402 for (int i = 1; i < n - 2; i++) {
403 const float x = 1.0f - (0.5f * (1.0f - cosf((float)((i / (float)(n - 3))) * M_PI_2)));
404 const float y = 0.5f + 0.5f * sinf((float)((i / (float)(n - 3)) * M_PI_2));
405 point_init(&profile->path[i], x, y, 0, HD_AUTO, HD_AUTO);
406 }
407 point_init(&profile->path[n - 2], 0.5f, 1.0f, 0, HD_VECT, HD_VECT);
408 point_init(&profile->path[n - 1], 0.0f, 1.0f, 0, HD_VECT, HD_VECT);
409 }
410
411 /**
412 * Puts the widgets control points in a step pattern.
413 * Uses vector handles for each point.
414 */
curveprofile_build_steps(CurveProfile * profile)415 static void curveprofile_build_steps(CurveProfile *profile)
416 {
417 int n = profile->path_len;
418
419 /* Special case for two points to avoid dividing by zero later. */
420 if (n == 2) {
421 point_init(&profile->path[0], 1.0f, 0.0f, 0, HD_VECT, HD_VECT);
422 point_init(&profile->path[0], 0.0f, 1.0f, 0, HD_VECT, HD_VECT);
423 return;
424 }
425
426 float n_steps_x = (n % 2 == 0) ? n : (n - 1);
427 float n_steps_y = (n % 2 == 0) ? (n - 2) : (n - 1);
428
429 for (int i = 0; i < n; i++) {
430 int step_x = (i + 1) / 2;
431 int step_y = i / 2;
432 const float x = 1.0f - ((float)(2 * step_x) / n_steps_x);
433 const float y = (float)(2 * step_y) / n_steps_y;
434 point_init(&profile->path[i], x, y, 0, HD_VECT, HD_VECT);
435 }
436 }
437
438 /**
439 * Resets the profile to the current preset.
440 *
441 * \note Requires #BKE_curveprofile_update call after.
442 */
BKE_curveprofile_reset(CurveProfile * profile)443 void BKE_curveprofile_reset(CurveProfile *profile)
444 {
445 MEM_SAFE_FREE(profile->path);
446
447 eCurveProfilePresets preset = profile->preset;
448 switch (preset) {
449 case PROF_PRESET_LINE:
450 profile->path_len = 2;
451 break;
452 case PROF_PRESET_SUPPORTS:
453 /* Use a dynamic number of control points for the widget's profile. */
454 if (profile->segments_len < 4) {
455 /* But always use enough points to at least build the support points. */
456 profile->path_len = 5;
457 }
458 else {
459 profile->path_len = profile->segments_len + 1;
460 }
461 break;
462 case PROF_PRESET_CORNICE:
463 profile->path_len = 13;
464 break;
465 case PROF_PRESET_CROWN:
466 profile->path_len = 11;
467 break;
468 case PROF_PRESET_STEPS:
469 /* Also use dynamic number of control points based on the set number of segments. */
470 if (profile->segments_len == 0) {
471 /* totsegments hasn't been set-- use the number of control points for 8 steps. */
472 profile->path_len = 17;
473 }
474 else {
475 profile->path_len = profile->segments_len + 1;
476 }
477 break;
478 }
479
480 profile->path = MEM_callocN(sizeof(CurveProfilePoint) * profile->path_len, "profile path");
481
482 switch (preset) {
483 case PROF_PRESET_LINE:
484 point_init(&profile->path[0], 1.0f, 0.0f, 0, HD_AUTO, HD_AUTO);
485 point_init(&profile->path[1], 0.0f, 1.0f, 0, HD_AUTO, HD_AUTO);
486 break;
487 case PROF_PRESET_SUPPORTS:
488 curveprofile_build_supports(profile);
489 break;
490 case PROF_PRESET_CORNICE:
491 point_init(&profile->path[0], 1.0f, 0.0f, 0, HD_VECT, HD_VECT);
492 point_init(&profile->path[1], 1.0f, 0.125f, 0, HD_VECT, HD_VECT);
493 point_init(&profile->path[2], 0.92f, 0.16f, 0, HD_AUTO, HD_AUTO);
494 point_init(&profile->path[3], 0.875f, 0.25f, 0, HD_VECT, HD_VECT);
495 point_init(&profile->path[4], 0.8f, 0.25f, 0, HD_VECT, HD_VECT);
496 point_init(&profile->path[5], 0.733f, 0.433f, 0, HD_AUTO, HD_AUTO);
497 point_init(&profile->path[6], 0.582f, 0.522f, 0, HD_AUTO, HD_AUTO);
498 point_init(&profile->path[7], 0.4f, 0.6f, 0, HD_AUTO, HD_AUTO);
499 point_init(&profile->path[8], 0.289f, 0.727f, 0, HD_AUTO, HD_AUTO);
500 point_init(&profile->path[9], 0.25f, 0.925f, 0, HD_VECT, HD_VECT);
501 point_init(&profile->path[10], 0.175f, 0.925f, 0, HD_VECT, HD_VECT);
502 point_init(&profile->path[11], 0.175f, 1.0f, 0, HD_VECT, HD_VECT);
503 point_init(&profile->path[12], 0.0f, 1.0f, 0, HD_VECT, HD_VECT);
504 break;
505 case PROF_PRESET_CROWN:
506 point_init(&profile->path[0], 1.0f, 0.0f, 0, HD_VECT, HD_VECT);
507 point_init(&profile->path[1], 1.0f, 0.25f, 0, HD_VECT, HD_VECT);
508 point_init(&profile->path[2], 0.75f, 0.25f, 0, HD_VECT, HD_VECT);
509 point_init(&profile->path[3], 0.75f, 0.325f, 0, HD_VECT, HD_VECT);
510 point_init(&profile->path[4], 0.925f, 0.4f, 0, HD_AUTO, HD_AUTO);
511 point_init(&profile->path[5], 0.975f, 0.5f, 0, HD_AUTO, HD_AUTO);
512 point_init(&profile->path[6], 0.94f, 0.65f, 0, HD_AUTO, HD_AUTO);
513 point_init(&profile->path[7], 0.85f, 0.75f, 0, HD_AUTO, HD_AUTO);
514 point_init(&profile->path[8], 0.75f, 0.875f, 0, HD_AUTO, HD_AUTO);
515 point_init(&profile->path[9], 0.7f, 1.0f, 0, HD_VECT, HD_VECT);
516 point_init(&profile->path[10], 0.0f, 1.0f, 0, HD_VECT, HD_VECT);
517 break;
518 case PROF_PRESET_STEPS:
519 curveprofile_build_steps(profile);
520 break;
521 }
522
523 profile->flag &= ~PROF_DIRTY_PRESET;
524
525 /* Ensure each point has a reference to the profile. */
526 for (int i = 0; i < profile->path_len; i++) {
527 profile->path[i].profile = profile;
528 }
529
530 MEM_SAFE_FREE(profile->table);
531 profile->table = NULL;
532 }
533
534 /**
535 * Helper for 'curve_profile_create' samples.
536 * Returns whether both handles that make up the edge are vector handles.
537 */
is_curved_edge(CurveProfilePoint * path,int i)538 static bool is_curved_edge(CurveProfilePoint *path, int i)
539 {
540 return (path[i].h2 != HD_VECT || path[i + 1].h1 != HD_VECT);
541 }
542
543 /**
544 * Used to set bezier handle locations in the sample creation process. Reduced copy of
545 * #calchandleNurb_intern code in curve.c, mostly changed by removing the third dimension.
546 */
point_calculate_handle(CurveProfilePoint * point,const CurveProfilePoint * prev,const CurveProfilePoint * next)547 static void point_calculate_handle(CurveProfilePoint *point,
548 const CurveProfilePoint *prev,
549 const CurveProfilePoint *next)
550 {
551 if (point->h1 == HD_FREE && point->h2 == HD_FREE) {
552 return;
553 }
554
555 float *point_loc = &point->x;
556
557 float pt[2];
558 const float *prev_loc, *next_loc;
559 if (prev == NULL) {
560 next_loc = &next->x;
561 pt[0] = 2.0f * point_loc[0] - next_loc[0];
562 pt[1] = 2.0f * point_loc[1] - next_loc[1];
563 prev_loc = pt;
564 }
565 else {
566 prev_loc = &prev->x;
567 }
568
569 if (next == NULL) {
570 prev_loc = &prev->x;
571 pt[0] = 2.0f * point_loc[0] - prev_loc[0];
572 pt[1] = 2.0f * point_loc[1] - prev_loc[1];
573 next_loc = pt;
574 }
575 else {
576 next_loc = &next->x;
577 }
578
579 float dvec_a[2], dvec_b[2];
580 sub_v2_v2v2(dvec_a, point_loc, prev_loc);
581 sub_v2_v2v2(dvec_b, next_loc, point_loc);
582
583 float len_a = len_v2(dvec_a);
584 float len_b = len_v2(dvec_b);
585 if (len_a == 0.0f) {
586 len_a = 1.0f;
587 }
588 if (len_b == 0.0f) {
589 len_b = 1.0f;
590 }
591
592 if (point->h1 == HD_AUTO || point->h2 == HD_AUTO) {
593 float tvec[2];
594 tvec[0] = dvec_b[0] / len_b + dvec_a[0] / len_a;
595 tvec[1] = dvec_b[1] / len_b + dvec_a[1] / len_a;
596
597 float len = len_v2(tvec) * 2.5614f;
598 if (len != 0.0f) {
599 if (point->h1 == HD_AUTO) {
600 len_a /= len;
601 madd_v2_v2v2fl(point->h1_loc, point_loc, tvec, -len_a);
602 }
603 if (point->h2 == HD_AUTO) {
604 len_b /= len;
605 madd_v2_v2v2fl(point->h2_loc, point_loc, tvec, len_b);
606 }
607 }
608 }
609
610 if (point->h1 == HD_VECT) {
611 madd_v2_v2v2fl(point->h1_loc, point_loc, dvec_a, -1.0f / 3.0f);
612 }
613 if (point->h2 == HD_VECT) {
614 madd_v2_v2v2fl(point->h2_loc, point_loc, dvec_b, 1.0f / 3.0f);
615 }
616 }
617
calculate_path_handles(CurveProfilePoint * path,int path_len)618 static void calculate_path_handles(CurveProfilePoint *path, int path_len)
619 {
620 point_calculate_handle(&path[0], NULL, &path[1]);
621 for (int i = 1; i < path_len - 1; i++) {
622 point_calculate_handle(&path[i], &path[i - 1], &path[i + 1]);
623 }
624 point_calculate_handle(&path[path_len - 1], &path[path_len - 2], NULL);
625 }
626
627 /**
628 * Helper function for 'BKE_curveprofile_create_samples.' Calculates the angle between the
629 * handles on the inside of the edge starting at index i. A larger angle means the edge is
630 * more curved.
631 * \param i_edge: The start index of the edge to calculate the angle for.
632 */
bezt_edge_handle_angle(const CurveProfilePoint * path,int i_edge)633 static float bezt_edge_handle_angle(const CurveProfilePoint *path, int i_edge)
634 {
635 /* Find the direction of the handles that define this edge along the direction of the path. */
636 float start_handle_direction[2], end_handle_direction[2];
637 /* Handle 2 - point location. */
638 sub_v2_v2v2(start_handle_direction, path[i_edge].h2_loc, &path[i_edge].x);
639 /* Point location - handle 1. */
640 sub_v2_v2v2(end_handle_direction, &path[i_edge + 1].x, path[i_edge + 1].h1_loc);
641
642 return angle_v2v2(start_handle_direction, end_handle_direction);
643 }
644
645 /** Struct to sort curvature of control point edges. */
646 typedef struct {
647 /** The index of the corresponding profile point. */
648 int point_index;
649 /** The curvature of the edge with the above index. */
650 float point_curvature;
651 } CurvatureSortPoint;
652
653 /**
654 * Helper function for 'BKE_curveprofile_create_samples' for sorting edges based on curvature.
655 */
sort_points_curvature(const void * in_a,const void * in_b)656 static int sort_points_curvature(const void *in_a, const void *in_b)
657 {
658 const CurvatureSortPoint *a = (const CurvatureSortPoint *)in_a;
659 const CurvatureSortPoint *b = (const CurvatureSortPoint *)in_b;
660
661 if (a->point_curvature > b->point_curvature) {
662 return 0;
663 }
664
665 return 1;
666 }
667
668 /**
669 * Used for sampling curves along the profile's path. Any points more than the number of
670 * user-defined points will be evenly distributed among the curved edges.
671 * Then the remainders will be distributed to the most curved edges.
672 *
673 * \param n_segments: The number of segments to sample along the path. Ideally it is higher than
674 * the number of points used to define the profile (profile->path_len).
675 * \param sample_straight_edges: Whether to sample points between vector handle control points.
676 * If this is true and there are only vector edges the straight edges will still be sampled.
677 * \param r_samples: Return array of points to put the sampled positions. Must have length
678 * n_segments. Fill the array with the sampled locations and if the point corresponds to a
679 * control point, its handle type.
680 */
BKE_curveprofile_create_samples(CurveProfile * profile,int n_segments,bool sample_straight_edges,CurveProfilePoint * r_samples)681 void BKE_curveprofile_create_samples(CurveProfile *profile,
682 int n_segments,
683 bool sample_straight_edges,
684 CurveProfilePoint *r_samples)
685 {
686 CurveProfilePoint *path = profile->path;
687 int totpoints = profile->path_len;
688 BLI_assert(n_segments > 0);
689
690 int totedges = totpoints - 1;
691
692 calculate_path_handles(path, totpoints);
693
694 /* Create a list of edge indices with the most curved at the start, least curved at the end. */
695 CurvatureSortPoint *curve_sorted = MEM_callocN(sizeof(CurvatureSortPoint) * totedges,
696 "curve sorted");
697 for (int i = 0; i < totedges; i++) {
698 curve_sorted[i].point_index = i;
699 /* Calculate the curvature of each edge once for use when sorting for curvature. */
700 curve_sorted[i].point_curvature = bezt_edge_handle_angle(path, i);
701 }
702 qsort(curve_sorted, totedges, sizeof(CurvatureSortPoint), sort_points_curvature);
703
704 /* Assign the number of sampled points for each edge. */
705 int16_t *n_samples = MEM_callocN(sizeof(int16_t) * totedges, "samples numbers");
706 int n_added = 0;
707 int n_left;
708 if (n_segments >= totedges) {
709 if (sample_straight_edges) {
710 /* Assign an even number to each edge if it’s possible, then add the remainder of sampled
711 * points starting with the most curved edges. */
712 int n_common = n_segments / totedges;
713 n_left = n_segments % totedges;
714
715 /* Assign the points that fill fit evenly to the edges. */
716 if (n_common > 0) {
717 BLI_assert(n_common < INT16_MAX);
718 for (int i = 0; i < totedges; i++) {
719 n_samples[i] = n_common;
720 n_added += n_common;
721 }
722 }
723 }
724 else {
725 /* Count the number of curved edges */
726 int n_curved_edges = 0;
727 for (int i = 0; i < totedges; i++) {
728 if (is_curved_edge(path, i)) {
729 n_curved_edges++;
730 }
731 }
732 /* Just sample all of the edges if there are no curved edges. */
733 n_curved_edges = (n_curved_edges == 0) ? totedges : n_curved_edges;
734
735 /* Give all of the curved edges the same number of points and straight edges one point. */
736 n_left = n_segments - (totedges - n_curved_edges); /* Left after 1 for each straight edge. */
737 int n_common = n_left / n_curved_edges; /* Number assigned to all curved edges */
738 if (n_common > 0) {
739 for (int i = 0; i < totedges; i++) {
740 /* Add the common number if it's a curved edge or if edges are curved. */
741 if (is_curved_edge(path, i) || n_curved_edges == totedges) {
742 BLI_assert(n_common + n_samples[i] < INT16_MAX);
743 n_samples[i] += n_common;
744 n_added += n_common;
745 }
746 else {
747 n_samples[i] = 1;
748 n_added++;
749 }
750 }
751 }
752 n_left -= n_common * n_curved_edges;
753 }
754 }
755 else {
756 /* Not enough segments to give one to each edge, so just give them to the most curved edges. */
757 n_left = n_segments;
758 }
759 /* Assign the remainder of the points that couldn't be spread out evenly. */
760 BLI_assert(n_left < totedges);
761 for (int i = 0; i < n_left; i++) {
762 BLI_assert(n_samples[curve_sorted[i].point_index] < INT16_MAX);
763 n_samples[curve_sorted[i].point_index]++;
764 n_added++;
765 }
766
767 BLI_assert(n_added == n_segments); /* n_added is just used for this assert, could remove it. */
768
769 /* Sample the points and add them to the locations table. */
770 for (int i_sample = 0, i = 0; i < totedges; i++) {
771 if (n_samples[i] > 0) {
772 /* Carry over the handle types from the control point to its first corresponding sample. */
773 r_samples[i_sample].h1 = path[i].h1;
774 r_samples[i_sample].h2 = path[i].h2;
775 /* All extra sample points for this control point get "auto" handles. */
776 for (int j = i_sample + 1; j < i_sample + n_samples[i]; j++) {
777 r_samples[j].flag = 0;
778 r_samples[j].h1 = HD_AUTO;
779 r_samples[j].h2 = HD_AUTO;
780 BLI_assert(j < n_segments);
781 }
782
783 /* Sample from the bezier points. X then Y values. */
784 BKE_curve_forward_diff_bezier(path[i].x,
785 path[i].h2_loc[0],
786 path[i + 1].h1_loc[0],
787 path[i + 1].x,
788 &r_samples[i_sample].x,
789 n_samples[i],
790 sizeof(CurveProfilePoint));
791 BKE_curve_forward_diff_bezier(path[i].y,
792 path[i].h2_loc[1],
793 path[i + 1].h1_loc[1],
794 path[i + 1].y,
795 &r_samples[i_sample].y,
796 n_samples[i],
797 sizeof(CurveProfilePoint));
798 }
799 i_sample += n_samples[i]; /* Add the next set of points after the ones we just added. */
800 BLI_assert(i_sample <= n_segments);
801 }
802
803 MEM_freeN(curve_sorted);
804 MEM_freeN(n_samples);
805 }
806
807 /**
808 * Creates a higher resolution table by sampling the curved points.
809 * This table is used for display and evenly spaced evaluation.
810 */
curveprofile_make_table(CurveProfile * profile)811 static void curveprofile_make_table(CurveProfile *profile)
812 {
813 int n_samples = PROF_TABLE_LEN(profile->path_len);
814 CurveProfilePoint *new_table = MEM_callocN(sizeof(CurveProfilePoint) * (n_samples + 1),
815 __func__);
816
817 BKE_curveprofile_create_samples(profile, n_samples - 1, false, new_table);
818 /* Manually add last point at the end of the profile */
819 new_table[n_samples - 1].x = 0.0f;
820 new_table[n_samples - 1].y = 1.0f;
821
822 MEM_SAFE_FREE(profile->table);
823 profile->table = new_table;
824 }
825
826 /**
827 * Creates the table of points used for displaying a preview of the sampled segment locations on
828 * the widget itself.
829 */
curveprofile_make_segments_table(CurveProfile * profile)830 static void curveprofile_make_segments_table(CurveProfile *profile)
831 {
832 int n_samples = profile->segments_len;
833 if (n_samples <= 0) {
834 return;
835 }
836 CurveProfilePoint *new_table = MEM_callocN(sizeof(CurveProfilePoint) * (n_samples + 1),
837 __func__);
838
839 if (profile->flag & PROF_SAMPLE_EVEN_LENGTHS) {
840 /* Even length sampling incompatible with only straight edge sampling for now. */
841 BKE_curveprofile_create_samples_even_spacing(profile, n_samples, new_table);
842 }
843 else {
844 BKE_curveprofile_create_samples(
845 profile, n_samples, profile->flag & PROF_SAMPLE_STRAIGHT_EDGES, new_table);
846 }
847
848 MEM_SAFE_FREE(profile->segments);
849 profile->segments = new_table;
850 }
851
852 /**
853 * Sets the default settings and clip range for the profile widget.
854 * Does not generate either table.
855 */
BKE_curveprofile_set_defaults(CurveProfile * profile)856 void BKE_curveprofile_set_defaults(CurveProfile *profile)
857 {
858 profile->flag = PROF_USE_CLIP;
859
860 BLI_rctf_init(&profile->view_rect, 0.0f, 1.0f, 0.0f, 1.0f);
861 profile->clip_rect = profile->view_rect;
862
863 profile->path_len = 2;
864 profile->path = MEM_callocN(2 * sizeof(CurveProfilePoint), "path points");
865
866 profile->path[0].x = 1.0f;
867 profile->path[0].y = 0.0f;
868 profile->path[0].profile = profile;
869 profile->path[1].x = 1.0f;
870 profile->path[1].y = 1.0f;
871 profile->path[1].profile = profile;
872
873 profile->changed_timestamp = 0;
874 }
875
876 /**
877 * Returns a pointer to a newly allocated curve profile, using the given preset.
878 */
BKE_curveprofile_add(eCurveProfilePresets preset)879 struct CurveProfile *BKE_curveprofile_add(eCurveProfilePresets preset)
880 {
881 CurveProfile *profile = MEM_callocN(sizeof(CurveProfile), "curve profile");
882
883 BKE_curveprofile_set_defaults(profile);
884 profile->preset = preset;
885 BKE_curveprofile_reset(profile);
886 curveprofile_make_table(profile);
887
888 return profile;
889 }
890
891 /**
892 * Should be called after the widget is changed. Does profile and remove double checks and more
893 * importantly, recreates the display / evaluation and segments tables.
894 * \param update_flags: Bitfield with fields defined in header file. Controls removing doubles and
895 * clipping.
896 */
BKE_curveprofile_update(CurveProfile * profile,const int update_flags)897 void BKE_curveprofile_update(CurveProfile *profile, const int update_flags)
898 {
899 CurveProfilePoint *points = profile->path;
900 rctf *clipr = &profile->clip_rect;
901
902 profile->changed_timestamp++;
903
904 /* Clamp with the clipping rect in case something got past. */
905 if (profile->flag & PROF_USE_CLIP) {
906 /* Move points inside the clip rectangle. */
907 if (update_flags & PROF_UPDATE_CLIP) {
908 for (int i = 0; i < profile->path_len; i++) {
909 points[i].x = clamp_f(points[i].x, clipr->xmin, clipr->xmax);
910 points[i].y = clamp_f(points[i].y, clipr->ymin, clipr->ymax);
911
912 /* Extra sanity assert to make sure the points have the right profile pointer. */
913 BLI_assert(points[i].profile == profile);
914 }
915 }
916 /* Ensure zoom-level respects clipping. */
917 if (BLI_rctf_size_x(&profile->view_rect) > BLI_rctf_size_x(&profile->clip_rect)) {
918 profile->view_rect.xmin = profile->clip_rect.xmin;
919 profile->view_rect.xmax = profile->clip_rect.xmax;
920 }
921 if (BLI_rctf_size_y(&profile->view_rect) > BLI_rctf_size_y(&profile->clip_rect)) {
922 profile->view_rect.ymin = profile->clip_rect.ymin;
923 profile->view_rect.ymax = profile->clip_rect.ymax;
924 }
925 }
926
927 /* Remove doubles with a threshold set at 1% of default range. */
928 float thresh = pow2f(0.01f * BLI_rctf_size_x(clipr));
929 if (update_flags & PROF_UPDATE_REMOVE_DOUBLES && profile->path_len > 2) {
930 for (int i = 0; i < profile->path_len - 1; i++) {
931 if (len_squared_v2v2(&points[i].x, &points[i + 1].x) < thresh) {
932 if (i == 0) {
933 BKE_curveprofile_remove_point(profile, &points[1]);
934 }
935 else {
936 BKE_curveprofile_remove_point(profile, &points[i]);
937 }
938 break; /* Assumes 1 deletion per update call is ok. */
939 }
940 }
941 }
942
943 /* Create the high resolution table for drawing and some evaluation functions. */
944 curveprofile_make_table(profile);
945
946 /* Store a table of samples for the segment locations for a preview and the table's user. */
947 if (profile->segments_len > 0) {
948 curveprofile_make_segments_table(profile);
949 }
950 }
951
952 /**
953 * Refreshes the higher resolution table sampled from the input points. A call to this or
954 * #BKE_curveprofile_update is needed before evaluation functions that use the table.
955 * Also sets the number of segments used for the display preview of the locations
956 * of the sampled points.
957 */
BKE_curveprofile_init(CurveProfile * profile,short segments_len)958 void BKE_curveprofile_init(CurveProfile *profile, short segments_len)
959 {
960 if (segments_len != profile->segments_len) {
961 profile->flag |= PROF_DIRTY_PRESET;
962 }
963 profile->segments_len = segments_len;
964
965 /* Calculate the higher resolution / segments tables for display and evaluation. */
966 BKE_curveprofile_update(profile, PROF_UPDATE_NONE);
967 }
968
969 /**
970 * Gives the distance to the next point in the widgets sampled table, in other words the length
971 * of the \a 'i' edge of the table.
972 *
973 * \note Requires #BKE_curveprofile_init or #BKE_curveprofile_update call before to fill table.
974 */
curveprofile_distance_to_next_table_point(const CurveProfile * profile,int i)975 static float curveprofile_distance_to_next_table_point(const CurveProfile *profile, int i)
976 {
977 BLI_assert(i < PROF_TABLE_LEN(profile->path_len));
978
979 return len_v2v2(&profile->table[i].x, &profile->table[i + 1].x);
980 }
981
982 /**
983 * Calculates the total length of the profile from the curves sampled in the table.
984 *
985 * \note Requires #BKE_curveprofile_init or #BKE_curveprofile_update call before to fill table.
986 */
BKE_curveprofile_total_length(const CurveProfile * profile)987 float BKE_curveprofile_total_length(const CurveProfile *profile)
988 {
989 float total_length = 0;
990 for (int i = 0; i < PROF_TABLE_LEN(profile->path_len) - 1; i++) {
991 total_length += len_v2v2(&profile->table[i].x, &profile->table[i + 1].x);
992 }
993 return total_length;
994 }
995
996 /**
997 * Samples evenly spaced positions along the curve profile's table (generated from path). Fills
998 * an entire table at once for a speedup if all of the results are going to be used anyway.
999 *
1000 * \note Requires #BKE_curveprofile_init or #BKE_curveprofile_update call before to fill table.
1001 * \note Working, but would conflict with "Sample Straight Edges" option, so this is unused for
1002 * now.
1003 */
BKE_curveprofile_create_samples_even_spacing(CurveProfile * profile,int n_segments,CurveProfilePoint * r_samples)1004 void BKE_curveprofile_create_samples_even_spacing(CurveProfile *profile,
1005 int n_segments,
1006 CurveProfilePoint *r_samples)
1007 {
1008 const float total_length = BKE_curveprofile_total_length(profile);
1009 const float segment_length = total_length / n_segments;
1010 float length_travelled = 0.0f;
1011 float distance_to_next_table_point = curveprofile_distance_to_next_table_point(profile, 0);
1012 float distance_to_previous_table_point = 0.0f;
1013 int i_table = 0;
1014
1015 /* Set the location for the first point. */
1016 r_samples[0].x = profile->table[0].x;
1017 r_samples[0].y = profile->table[0].y;
1018
1019 /* Travel along the path, recording the locations of segments as we pass them. */
1020 float segment_left = segment_length;
1021 for (int i = 1; i < n_segments; i++) {
1022 /* Travel over all of the points that fit inside this segment. */
1023 while (distance_to_next_table_point < segment_left) {
1024 length_travelled += distance_to_next_table_point;
1025 segment_left -= distance_to_next_table_point;
1026 i_table++;
1027 distance_to_next_table_point = curveprofile_distance_to_next_table_point(profile, i_table);
1028 distance_to_previous_table_point = 0.0f;
1029 }
1030 /* We're at the last table point that fits inside the current segment, use interpolation. */
1031 float factor = (distance_to_previous_table_point + segment_left) /
1032 (distance_to_previous_table_point + distance_to_next_table_point);
1033 r_samples[i].x = interpf(profile->table[i_table + 1].x, profile->table[i_table].x, factor);
1034 r_samples[i].y = interpf(profile->table[i_table + 1].y, profile->table[i_table].y, factor);
1035 BLI_assert(factor <= 1.0f && factor >= 0.0f);
1036 #ifdef DEBUG_CURVEPROFILE_EVALUATE
1037 printf("segment_left: %.3f\n", segment_left);
1038 printf("i_table: %d\n", i_table);
1039 printf("distance_to_previous_table_point: %.3f\n", distance_to_previous_table_point);
1040 printf("distance_to_next_table_point: %.3f\n", distance_to_next_table_point);
1041 printf("Interpolating with factor %.3f from (%.3f, %.3f) to (%.3f, %.3f)\n\n",
1042 factor,
1043 profile->table[i_table].x,
1044 profile->table[i_table].y,
1045 profile->table[i_table + 1].x,
1046 profile->table[i_table + 1].y);
1047 #endif
1048
1049 /* We sampled in between this table point and the next, so the next travel step is smaller. */
1050 distance_to_next_table_point -= segment_left;
1051 distance_to_previous_table_point += segment_left;
1052 length_travelled += segment_left;
1053 segment_left = segment_length;
1054 }
1055 }
1056
1057 /**
1058 * Does a single evaluation along the profile's path.
1059 * Travels down (length_portion * path) length and returns the position at that point.
1060 *
1061 * \param length_portion: The portion (0 to 1) of the path's full length to sample at.
1062 * \note Requires #BKE_curveprofile_init or #BKE_curveprofile_update call before to fill table.
1063 */
BKE_curveprofile_evaluate_length_portion(const CurveProfile * profile,float length_portion,float * x_out,float * y_out)1064 void BKE_curveprofile_evaluate_length_portion(const CurveProfile *profile,
1065 float length_portion,
1066 float *x_out,
1067 float *y_out)
1068 {
1069 const float total_length = BKE_curveprofile_total_length(profile);
1070 const float requested_length = length_portion * total_length;
1071
1072 /* Find the last point along the path with a lower length portion than the input. */
1073 int i = 0;
1074 float length_travelled = 0.0f;
1075 while (length_travelled < requested_length) {
1076 /* Check if we reached the last point before the final one. */
1077 if (i == PROF_TABLE_LEN(profile->path_len) - 2) {
1078 break;
1079 }
1080 float new_length = curveprofile_distance_to_next_table_point(profile, i);
1081 if (length_travelled + new_length >= requested_length) {
1082 break;
1083 }
1084 length_travelled += new_length;
1085 i++;
1086 }
1087
1088 /* Now travel the remaining distance of length portion down the path to the next point and
1089 * find the location where we stop. */
1090 float distance_to_next_point = curveprofile_distance_to_next_table_point(profile, i);
1091 float lerp_factor = (requested_length - length_travelled) / distance_to_next_point;
1092
1093 #ifdef DEBUG_CURVEPROFILE_EVALUATE
1094 printf("CURVEPROFILE EVALUATE\n");
1095 printf(" length portion input: %f\n", (double)length_portion);
1096 printf(" requested path length: %f\n", (double)requested_length);
1097 printf(" distance to next point: %f\n", (double)distance_to_next_point);
1098 printf(" length travelled: %f\n", (double)length_travelled);
1099 printf(" lerp-factor: %f\n", (double)lerp_factor);
1100 printf(" ith point (%f, %f)\n", (double)profile->path[i].x, (double)profile->path[i].y);
1101 printf(" next point(%f, %f)\n", (double)profile->path[i + 1].x, (double)profile->path[i + 1].y);
1102 #endif
1103
1104 *x_out = interpf(profile->table[i].x, profile->table[i + 1].x, lerp_factor);
1105 *y_out = interpf(profile->table[i].y, profile->table[i + 1].y, lerp_factor);
1106 }
1107
BKE_curveprofile_blend_write(struct BlendWriter * writer,const struct CurveProfile * profile)1108 void BKE_curveprofile_blend_write(struct BlendWriter *writer, const struct CurveProfile *profile)
1109 {
1110 BLO_write_struct(writer, CurveProfile, profile);
1111 BLO_write_struct_array(writer, CurveProfilePoint, profile->path_len, profile->path);
1112 }
1113
1114 /* Expects that the curve profile itself has been read already. */
BKE_curveprofile_blend_read(struct BlendDataReader * reader,struct CurveProfile * profile)1115 void BKE_curveprofile_blend_read(struct BlendDataReader *reader, struct CurveProfile *profile)
1116 {
1117 BLO_read_data_address(reader, &profile->path);
1118 profile->table = NULL;
1119 profile->segments = NULL;
1120
1121 /* Reset the points' pointers to the profile. */
1122 for (int i = 0; i < profile->path_len; i++) {
1123 profile->path[i].profile = profile;
1124 }
1125
1126 BKE_curveprofile_init(profile, profile->segments_len);
1127 }
1128