diff options
Diffstat (limited to 'source/blender/blenkernel/intern/curveprofile.c')
| -rw-r--r-- | source/blender/blenkernel/intern/curveprofile.c | 1011 |
1 files changed, 1011 insertions, 0 deletions
diff --git a/source/blender/blenkernel/intern/curveprofile.c b/source/blender/blenkernel/intern/curveprofile.c new file mode 100644 index 00000000000..6689eca132d --- /dev/null +++ b/source/blender/blenkernel/intern/curveprofile.c @@ -0,0 +1,1011 @@ +/* + * 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. + * + * Copyright (C) 2019 Blender Foundation. + * All rights reserved. + */ + +/** \file + * \ingroup bke + */ + +#include <string.h> +#include <math.h> +#include <stdlib.h> +#include <float.h> + +#include "MEM_guardedalloc.h" + +#include "DNA_curveprofile_types.h" +#include "DNA_curve_types.h" + +#include "BLI_blenlib.h" +#include "BLI_math.h" +#include "BLI_utildefines.h" +#include "BLI_task.h" +#include "BLI_threads.h" + +#include "BKE_curveprofile.h" +#include "BKE_curve.h" +#include "BKE_fcurve.h" + +void BKE_curveprofile_free_data(CurveProfile *profile) +{ + MEM_SAFE_FREE(profile->path); + MEM_SAFE_FREE(profile->table); + MEM_SAFE_FREE(profile->segments); +} + +void BKE_curveprofile_free(CurveProfile *profile) +{ + if (profile) { + BKE_curveprofile_free_data(profile); + MEM_freeN(profile); + } +} + +void BKE_curveprofile_copy_data(CurveProfile *target, const CurveProfile *profile) +{ + *target = *profile; + + target->path = MEM_dupallocN(profile->path); + target->table = MEM_dupallocN(profile->table); + target->segments = MEM_dupallocN(profile->segments); +} + +CurveProfile *BKE_curveprofile_copy(const CurveProfile *profile) +{ + if (profile) { + CurveProfile *new_prdgt = MEM_dupallocN(profile); + BKE_curveprofile_copy_data(new_prdgt, profile); + return new_prdgt; + } + return NULL; +} + +/** Removes a specific point from the path of control points. + * \note: Requires curveprofile_update call after. */ +bool BKE_curveprofile_remove_point(CurveProfile *profile, CurveProfilePoint *point) +{ + CurveProfilePoint *pts; + + /* Must have 2 points minimum. */ + if (profile->path_len <= 2) { + return false; + } + + /* Input point must be within the array. */ + if (!(point > profile->path && point < profile->path + profile->path_len)) { + return false; + } + + pts = MEM_mallocN(sizeof(CurveProfilePoint) * profile->path_len, "path points"); + + uint i_delete = (uint)(point - profile->path); + + /* Copy the before and after the deleted point. */ + memcpy(pts, profile->path, i_delete); + memcpy(pts + i_delete, profile->path + i_delete + 1, (size_t)profile->path_len - i_delete - 1); + + MEM_freeN(profile->path); + profile->path = pts; + profile->path_len -= 1; + return true; +} + +/** Removes every point in the widget with the supplied flag set, except for the first and last. + * \param flag: CurveProfilePoint->flag. + * \note: Requires curveprofile_update call after. */ +void BKE_curveprofile_remove_by_flag(CurveProfile *profile, const short flag) +{ + int i_old, i_new, n_removed = 0; + + /* Copy every point without the flag into the new path. */ + CurveProfilePoint *new_pts = MEM_mallocN(sizeof(CurveProfilePoint) * profile->path_len, + "profile path"); + + /* Build the new list without any of the points with the flag. Keep the first and last points. */ + new_pts[0] = profile->path[0]; + for (i_old = 1, i_new = 1; i_old < profile->path_len - 1; i_old++) { + if (!(profile->path[i_old].flag & flag)) { + new_pts[i_new] = profile->path[i_old]; + i_new++; + } + else { + n_removed++; + } + } + new_pts[i_new] = profile->path[i_old]; + + MEM_freeN(profile->path); + profile->path = new_pts; + profile->path_len -= n_removed; +} + +/** Adds a new point at the specified location. The choice for which points to place the new vertex + * between is made by checking which control point line segment is closest to the new point and + * placing the new vertex in between that segment's points. + * \note: Requires curveprofile_update call after. */ +CurveProfilePoint *BKE_curveprofile_insert(CurveProfile *profile, float x, float y) +{ + CurveProfilePoint *new_pt = NULL; + float new_loc[2] = {x, y}; + + /* Don't add more control points than the maximum size of the higher resolution table. */ + if (profile->path_len == PROF_TABLE_MAX - 1) { + return NULL; + } + + /* Find the index at the line segment that's closest to the new position. */ + float distance; + float min_distance = FLT_MAX; + int i_insert = 0; + for (int i = 0; i < profile->path_len - 1; i++) { + float loc1[2] = {profile->path[i].x, profile->path[i].y}; + float loc2[2] = {profile->path[i + 1].x, profile->path[i + 1].y}; + + distance = dist_squared_to_line_segment_v2(new_loc, loc1, loc2); + if (distance < min_distance) { + min_distance = distance; + i_insert = i + 1; + } + } + + /* Insert the new point at the location we found and copy all of the old points in as well. */ + profile->path_len++; + CurveProfilePoint *new_pts = MEM_mallocN(sizeof(CurveProfilePoint) * profile->path_len, + "profile path"); + for (int i_new = 0, i_old = 0; i_new < profile->path_len; i_new++) { + if (i_new != i_insert) { + /* Insert old points */ + new_pts[i_new].x = profile->path[i_old].x; + new_pts[i_new].y = profile->path[i_old].y; + new_pts[i_new].flag = profile->path[i_old].flag & ~PROF_SELECT; /* Deselect old points. */ + new_pts[i_new].h1 = profile->path[i_old].h1; + new_pts[i_new].h2 = profile->path[i_old].h2; + i_old++; + } + else { + /* Insert new point. */ + new_pts[i_new].x = x; + new_pts[i_new].y = y; + new_pts[i_new].flag = PROF_SELECT; + new_pt = &new_pts[i_new]; + /* Set handles of new point based on its neighbors. */ + if (new_pts[i_new - 1].h2 == HD_VECT && profile->path[i_insert].h1 == HD_VECT) { + new_pt->h1 = new_pt->h2 = HD_VECT; + } + else { + new_pt->h1 = new_pt->h2 = HD_AUTO; + } + } + } + + /* Free the old path and use the new one. */ + MEM_freeN(profile->path); + profile->path = new_pts; + return new_pt; +} + +/** Sets the handle type of the selected control points. + * \param type_*: Either HD_VECT or HD_AUTO. Handle types for the first and second handles. + * \note: Requires curveprofile_update call after. */ +void BKE_curveprofile_selected_handle_set(CurveProfile *profile, int type_1, int type_2) +{ + for (int i = 0; i < profile->path_len; i++) { + if (profile->path[i].flag & PROF_SELECT) { + switch (type_1) { + case HD_AUTO: + profile->path[i].h1 = HD_AUTO; + break; + case HD_VECT: + profile->path[i].h1 = HD_VECT; + break; + default: + profile->path[i].h1 = HD_AUTO; + break; + } + switch (type_2) { + case HD_AUTO: + profile->path[i].h2 = HD_AUTO; + break; + case HD_VECT: + profile->path[i].h2 = HD_VECT; + break; + default: + profile->path[i].h1 = HD_AUTO; + break; + } + } + } +} + +/** Flips the profile across the diagonal so that its orientation is reversed. + * \note: Requires curveprofile_update call after. */ +void BKE_curveprofile_reverse(CurveProfile *profile) +{ + /* When there are only two points, reversing shouldn't do anything. */ + if (profile->path_len == 2) { + return; + } + CurveProfilePoint *new_pts = MEM_mallocN(sizeof(CurveProfilePoint) * profile->path_len, + "profile path"); + /* Mirror the new points across the y = x line */ + for (int i = 0; i < profile->path_len; i++) { + new_pts[profile->path_len - i - 1].x = profile->path[i].y; + new_pts[profile->path_len - i - 1].y = profile->path[i].x; + new_pts[profile->path_len - i - 1].flag = profile->path[i].flag; + new_pts[profile->path_len - i - 1].h1 = profile->path[i].h1; + new_pts[profile->path_len - i - 1].h2 = profile->path[i].h2; + } + + /* Free the old points and use the new ones */ + MEM_freeN(profile->path); + profile->path = new_pts; +} + +/** Builds a quarter circle profile with space on each side for 'support loops.' */ +static void CurveProfile_build_supports(CurveProfile *profile) +{ + int n = profile->path_len; + + profile->path[0].x = 1.0; + profile->path[0].y = 0.0; + profile->path[0].flag = 0; + profile->path[0].h1 = HD_VECT; + profile->path[0].h2 = HD_VECT; + profile->path[1].x = 1.0; + profile->path[1].y = 0.5; + profile->path[1].flag = 0; + profile->path[1].h1 = HD_VECT; + profile->path[1].h2 = HD_VECT; + for (int i = 1; i < n - 2; i++) { + profile->path[i + 1].x = 1.0f - (0.5f * (1.0f - cosf((float)((i / (float)(n - 3))) * M_PI_2))); + profile->path[i + 1].y = 0.5f + 0.5f * sinf((float)((i / (float)(n - 3)) * M_PI_2)); + profile->path[i + 1].flag = 0; + profile->path[i + 1].h1 = HD_AUTO; + profile->path[i + 1].h2 = HD_AUTO; + } + profile->path[n - 2].x = 0.5; + profile->path[n - 2].y = 1.0; + profile->path[n - 2].flag = 0; + profile->path[n - 2].h1 = HD_VECT; + profile->path[n - 2].h2 = HD_VECT; + profile->path[n - 1].x = 0.0; + profile->path[n - 1].y = 1.0; + profile->path[n - 1].flag = 0; + profile->path[n - 1].h1 = HD_VECT; + profile->path[n - 1].h2 = HD_VECT; +} + +/** Puts the widget's control points in a step pattern. Uses vector handles for each point. */ +static void CurveProfile_build_steps(CurveProfile *profile) +{ + int n, step_x, step_y; + float n_steps_x, n_steps_y; + + n = profile->path_len; + + /* Special case for two points to avoid dividing by zero later. */ + if (n == 2) { + profile->path[0].x = 1.0f; + profile->path[0].y = 0.0f; + profile->path[0].flag = 0; + profile->path[0].h1 = HD_VECT; + profile->path[0].h2 = HD_VECT; + profile->path[1].x = 0.0f; + profile->path[1].y = 1.0f; + profile->path[1].flag = 0; + profile->path[1].h1 = HD_VECT; + profile->path[1].h2 = HD_VECT; + return; + } + + n_steps_x = (n % 2 == 0) ? n : (n - 1); + n_steps_y = (n % 2 == 0) ? (n - 2) : (n - 1); + + for (int i = 0; i < n; i++) { + step_x = (i + 1) / 2; + step_y = i / 2; + profile->path[i].x = 1.0f - ((float)(2 * step_x) / n_steps_x); + profile->path[i].y = (float)(2 * step_y) / n_steps_y; + profile->path[i].flag = 0; + profile->path[i].h1 = HD_VECT; + profile->path[i].h2 = HD_VECT; + } +} + +/** Shorthand helper function for setting location and interpolation of a point. */ +static void point_init(CurveProfilePoint *point, float x, float y, short flag, char h1, char h2) +{ + point->x = x; + point->y = y; + point->flag = flag; + point->h1 = h1; + point->h2 = h2; +} + +/** Resets the profile to the current preset. + * \note: Requires curveprofile_update call after. */ +void BKE_curveprofile_reset(CurveProfile *profile) +{ + if (profile->path) { + MEM_freeN(profile->path); + } + + int preset = profile->preset; + switch (preset) { + case PROF_PRESET_LINE: + profile->path_len = 2; + break; + case PROF_PRESET_SUPPORTS: + /* Use a dynamic number of control points for the widget's profile. */ + if (profile->segments_len < 4) { + /* But always use enough points to at least build the support points. */ + profile->path_len = 5; + } + else { + profile->path_len = profile->segments_len + 1; + } + break; + case PROF_PRESET_CORNICE: + profile->path_len = 13; + break; + case PROF_PRESET_CROWN: + profile->path_len = 11; + break; + case PROF_PRESET_STEPS: + /* Also use dynamic number of control points based on the set number of segments. */ + if (profile->segments_len == 0) { + /* totsegments hasn't been set-- use the number of control points for 8 steps. */ + profile->path_len = 17; + } + else { + profile->path_len = profile->segments_len + 1; + } + break; + } + + profile->path = MEM_callocN(sizeof(CurveProfilePoint) * profile->path_len, "profile path"); + + switch (preset) { + case PROF_PRESET_LINE: + point_init(&profile->path[0], 1.0f, 0.0f, 0, HD_AUTO, HD_AUTO); + point_init(&profile->path[1], 0.0f, 1.0f, 0, HD_AUTO, HD_AUTO); + break; + case PROF_PRESET_SUPPORTS: + CurveProfile_build_supports(profile); + break; + case PROF_PRESET_CORNICE: + point_init(&profile->path[0], 1.0f, 0.0f, 0, HD_VECT, HD_VECT); + point_init(&profile->path[1], 1.0f, 0.125f, 0, HD_VECT, HD_VECT); + point_init(&profile->path[2], 0.92f, 0.16f, 0, HD_AUTO, HD_AUTO); + point_init(&profile->path[3], 0.875f, 0.25f, 0, HD_VECT, HD_VECT); + point_init(&profile->path[4], 0.8f, 0.25f, 0, HD_VECT, HD_VECT); + point_init(&profile->path[5], 0.733f, 0.433f, 0, HD_AUTO, HD_AUTO); + point_init(&profile->path[6], 0.582f, 0.522f, 0, HD_AUTO, HD_AUTO); + point_init(&profile->path[7], 0.4f, 0.6f, 0, HD_AUTO, HD_AUTO); + point_init(&profile->path[8], 0.289f, 0.727f, 0, HD_AUTO, HD_AUTO); + point_init(&profile->path[9], 0.25f, 0.925f, 0, HD_VECT, HD_VECT); + point_init(&profile->path[10], 0.175f, 0.925f, 0, HD_VECT, HD_VECT); + point_init(&profile->path[11], 0.175f, 1.0f, 0, HD_VECT, HD_VECT); + point_init(&profile->path[12], 0.0f, 1.0f, 0, HD_VECT, HD_VECT); + break; + case PROF_PRESET_CROWN: + point_init(&profile->path[0], 1.0f, 0.0f, 0, HD_VECT, HD_VECT); + point_init(&profile->path[1], 1.0f, 0.25f, 0, HD_VECT, HD_VECT); + point_init(&profile->path[2], 0.75f, 0.25f, 0, HD_VECT, HD_VECT); + point_init(&profile->path[3], 0.75f, 0.325f, 0, HD_VECT, HD_VECT); + point_init(&profile->path[4], 0.925f, 0.4f, 0, HD_AUTO, HD_AUTO); + point_init(&profile->path[5], 0.975f, 0.5f, 0, HD_AUTO, HD_AUTO); + point_init(&profile->path[6], 0.94f, 0.65f, 0, HD_AUTO, HD_AUTO); + point_init(&profile->path[7], 0.85f, 0.75f, 0, HD_AUTO, HD_AUTO); + point_init(&profile->path[8], 0.75f, 0.875f, 0, HD_AUTO, HD_AUTO); + point_init(&profile->path[9], 0.7f, 1.0f, 0, HD_VECT, HD_VECT); + point_init(&profile->path[10], 0.0f, 1.0f, 0, HD_VECT, HD_VECT); + break; + case PROF_PRESET_STEPS: + CurveProfile_build_steps(profile); + break; + } + + if (profile->table) { + MEM_freeN(profile->table); + profile->table = NULL; + } +} + +/** Helper for 'curve_profile_create' samples. Returns whether both handles that make up the edge + * are vector handles. */ +static bool is_curved_edge(BezTriple *bezt, int i) +{ + return (bezt[i].h2 != HD_VECT || bezt[i + 1].h1 != HD_VECT); +} + +/** Used to set bezier handle locations in the sample creation process. Reduced copy of + * #calchandleNurb_intern code in curve.c. */ +static void calchandle_profile(BezTriple *bezt, const BezTriple *prev, const BezTriple *next) +{ +#define point_handle1 ((point_loc)-3) +#define point_handle2 ((point_loc) + 3) + + const float *prev_loc, *next_loc; + float *point_loc; + float pt[3]; + float len, len_a, len_b; + float dvec_a[2], dvec_b[2]; + + if (bezt->h1 == 0 && bezt->h2 == 0) { + return; + } + + point_loc = bezt->vec[1]; + + if (prev == NULL) { + next_loc = next->vec[1]; + pt[0] = 2.0f * point_loc[0] - next_loc[0]; + pt[1] = 2.0f * point_loc[1] - next_loc[1]; + prev_loc = pt; + } + else { + prev_loc = prev->vec[1]; + } + + if (next == NULL) { + prev_loc = prev->vec[1]; + pt[0] = 2.0f * point_loc[0] - prev_loc[0]; + pt[1] = 2.0f * point_loc[1] - prev_loc[1]; + next_loc = pt; + } + else { + next_loc = next->vec[1]; + } + + sub_v2_v2v2(dvec_a, point_loc, prev_loc); + sub_v2_v2v2(dvec_b, next_loc, point_loc); + + len_a = len_v2(dvec_a); + len_b = len_v2(dvec_b); + + if (len_a == 0.0f) { + len_a = 1.0f; + } + if (len_b == 0.0f) { + len_b = 1.0f; + } + + if (bezt->h1 == HD_AUTO || bezt->h2 == HD_AUTO) { /* auto */ + float tvec[2]; + tvec[0] = dvec_b[0] / len_b + dvec_a[0] / len_a; + tvec[1] = dvec_b[1] / len_b + dvec_a[1] / len_a; + + len = len_v2(tvec) * 2.5614f; + if (len != 0.0f) { + + if (bezt->h1 == HD_AUTO) { + len_a /= len; + madd_v2_v2v2fl(point_handle1, point_loc, tvec, -len_a); + } + if (bezt->h2 == HD_AUTO) { + len_b /= len; + madd_v2_v2v2fl(point_handle2, point_loc, tvec, len_b); + } + } + } + + if (bezt->h1 == HD_VECT) { /* vector */ + madd_v2_v2v2fl(point_handle1, point_loc, dvec_a, -1.0f / 3.0f); + } + if (bezt->h2 == HD_VECT) { + madd_v2_v2v2fl(point_handle2, point_loc, dvec_b, 1.0f / 3.0f); + } +#undef point_handle1 +#undef point_handle2 +} + +/** Helper function for 'BKE_CurveProfile_create_samples.' Calculates the angle between the + * handles on the inside of the edge starting at index i. A larger angle means the edge is + * more curved. + * \param i_edge: The start index of the edge to calculate the angle for. */ +static float bezt_edge_handle_angle(const BezTriple *bezt, int i_edge) +{ + /* Find the direction of the handles that define this edge along the direction of the path. */ + float start_handle_direction[2], end_handle_direction[2]; + /* Handle 2 - point location. */ + sub_v2_v2v2(start_handle_direction, bezt[i_edge].vec[2], bezt[i_edge].vec[1]); + /* Point location - handle 1. */ + sub_v2_v2v2(end_handle_direction, bezt[i_edge + 1].vec[1], bezt[i_edge + 1].vec[0]); + + float angle = angle_v2v2(start_handle_direction, end_handle_direction); + return angle; +} + +/** Struct to sort curvature of control point edges. */ +typedef struct { + /** The index of the corresponding bezier point. */ + int bezt_index; + /** The curvature of the edge with the above index. */ + float bezt_curvature; +} CurvatureSortPoint; + +/** Helper function for 'BKE_curveprofile_create_samples' for sorting edges based on curvature. */ +static int sort_points_curvature(const void *in_a, const void *in_b) +{ + const CurvatureSortPoint *a = (const CurvatureSortPoint *)in_a; + const CurvatureSortPoint *b = (const CurvatureSortPoint *)in_b; + + if (a->bezt_curvature > b->bezt_curvature) { + return 0; + } + else { + return 1; + } +} + +/** Used for sampling curves along the profile's path. Any points more than the number of user- + * defined points will be evenly distributed among the curved edges. Then the remainders will be + * distributed to the most curved edges. + * \param n_segments: The number of segments to sample along the path. It must be higher than the + * number of points used to define the profile (profile->path_len). + * \param sample_straight_edges: Whether to sample points between vector handle control points. If + * this is true and there are only vector edges the straight edges will still be sampled. + * \param r_samples: An array of points to put the sampled positions. Must have length n_segments. + * \return r_samples: Fill the array with the sampled locations and if the point corresponds + * to a control point, its handle type */ +void BKE_curveprofile_create_samples(CurveProfile *profile, + int n_segments, + bool sample_straight_edges, + CurveProfilePoint *r_samples) +{ + BezTriple *bezt; + int i, n_left, n_common, i_sample, n_curved_edges; + int *n_samples; + CurvatureSortPoint *curve_sorted; + int totpoints = profile->path_len; + int totedges = totpoints - 1; + + BLI_assert(n_segments > 0); + + /* Create Bezier points for calculating the higher resolution path. */ + bezt = MEM_callocN(sizeof(BezTriple) * totpoints, "beztarr"); + for (i = 0; i < totpoints; i++) { + bezt[i].vec[1][0] = profile->path[i].x; + bezt[i].vec[1][1] = profile->path[i].y; + bezt[i].h1 = (profile->path[i].h1 == HD_VECT) ? HD_VECT : HD_AUTO; + bezt[i].h2 = (profile->path[i].h2 == HD_VECT) ? HD_VECT : HD_AUTO; + } + /* Give the first and last bezier points the same handle type as their neighbors. */ + if (totpoints > 2) { + bezt[0].h1 = bezt[0].h2 = bezt[1].h1; + bezt[totpoints - 1].h1 = bezt[totpoints - 1].h2 = bezt[totpoints - 2].h2; + } + /* Get handle positions for the bezier points. */ + calchandle_profile(&bezt[0], NULL, &bezt[1]); + for (i = 1; i < totpoints - 1; i++) { + calchandle_profile(&bezt[i], &bezt[i - 1], &bezt[i + 1]); + } + calchandle_profile(&bezt[totpoints - 1], &bezt[totpoints - 2], NULL); + + /* Create a list of edge indices with the most curved at the start, least curved at the end. */ + curve_sorted = MEM_callocN(sizeof(CurvatureSortPoint) * totedges, "curve sorted"); + for (i = 0; i < totedges; i++) { + curve_sorted[i].bezt_index = i; + /* Calculate the curvature of each edge once for use when sorting for curvature. */ + curve_sorted[i].bezt_curvature = bezt_edge_handle_angle(bezt, i); + } + qsort(curve_sorted, (size_t)totedges, sizeof(CurvatureSortPoint), sort_points_curvature); + + /* Assign the number of sampled points for each edge. */ + n_samples = MEM_callocN(sizeof(int) * totedges, "create samples numbers"); + int n_added = 0; + if (n_segments >= totedges) { + if (sample_straight_edges) { + /* Assign an even number to each edge if it’s possible, then add the remainder of sampled + * points starting with the most curved edges. */ + n_common = n_segments / totedges; + n_left = n_segments % totedges; + + /* Assign the points that fill fit evenly to the edges. */ + if (n_common > 0) { + for (i = 0; i < totedges; i++) { + n_samples[i] = n_common; + n_added += n_common; + } + } + } + else { + /* Count the number of curved edges */ + n_curved_edges = 0; + for (i = 0; i < totedges; i++) { + if (is_curved_edge(bezt, i)) { + n_curved_edges++; + } + } + /* Just sample all of the edges if there are no curved edges. */ + n_curved_edges = (n_curved_edges == 0) ? totedges : n_curved_edges; + + /* Give all of the curved edges the same number of points and straight edges one point. */ + n_left = n_segments - (totedges - n_curved_edges); /* Left after 1 for each straight edge. */ + n_common = n_left / n_curved_edges; /* Number assigned to all curved edges */ + if (n_common > 0) { + for (i = 0; i < totedges; i++) { + /* Add the common number if it's a curved edge or if edges are curved. */ + if (is_curved_edge(bezt, i) || n_curved_edges == totedges) { + n_samples[i] += n_common; + n_added += n_common; + } + else { + n_samples[i] = 1; + n_added++; + } + } + } + n_left -= n_common * n_curved_edges; + } + } + else { + /* Not enough segments to give one to each edge, so just give them to the most curved edges. */ + n_left = n_segments; + } + /* Assign the remainder of the points that couldn't be spread out evenly. */ + BLI_assert(n_left < totedges); + for (i = 0; i < n_left; i++) { + n_samples[curve_sorted[i].bezt_index]++; + n_added++; + } + + BLI_assert(n_added == n_segments); /* n_added is just used for this assert, could remove it. */ + + /* Sample the points and add them to the locations table. */ + for (i_sample = 0, i = 0; i < totedges; i++) { + if (n_samples[i] > 0) { + /* Carry over the handle types from the control point to its first corresponding sample. */ + r_samples[i_sample].h1 = profile->path[i].h1; + r_samples[i_sample].h2 = profile->path[i].h2; + /* All extra sample points for this control point get "auto" handles. */ + for (int j = i_sample + 1; j < i_sample + n_samples[i]; j++) { + r_samples[j].flag = 0; + r_samples[j].h1 = HD_AUTO; + r_samples[j].h2 = HD_AUTO; + BLI_assert(j < n_segments); + } + + /* Do the sampling from bezier points, X values first, then Y values. */ + BKE_curve_forward_diff_bezier(bezt[i].vec[1][0], + bezt[i].vec[2][0], + bezt[i + 1].vec[0][0], + bezt[i + 1].vec[1][0], + &r_samples[i_sample].x, + n_samples[i], + sizeof(CurveProfilePoint)); + BKE_curve_forward_diff_bezier(bezt[i].vec[1][1], + bezt[i].vec[2][1], + bezt[i + 1].vec[0][1], + bezt[i + 1].vec[1][1], + &r_samples[i_sample].y, + n_samples[i], + sizeof(CurveProfilePoint)); + } + i_sample += n_samples[i]; /* Add the next set of points after the ones we just added. */ + BLI_assert(i_sample <= n_segments); + } + +#ifdef DEBUG_profile_TABLE + printf("CURVEPROFILE CREATE SAMPLES\n"); + printf("n_segments: %d\n", n_segments); + printf("totedges: %d\n", totedges); + printf("n_common: %d\n", n_common); + printf("n_left: %d\n", n_left); + printf("n_samples: "); + for (i = 0; i < totedges; i++) { + printf("%d, ", n_samples[i]); + } + printf("\n"); + printf("i_curved_sorted: "); + for (i = 0; i < totedges; i++) { + printf("(%d %.2f), ", curve_sorted[i].bezt_index, curve_sorted[i].bezt_curvature); + } + printf("\n"); +#endif + MEM_freeN(bezt); + MEM_freeN(curve_sorted); + MEM_freeN(n_samples); +} + +/** Creates a higher resolution table by sampling the curved points. This table is used for display + * and evenly spaced evaluation. */ +static void curveprofile_make_table(CurveProfile *profile) +{ + int n_samples = PROF_N_TABLE(profile->path_len); + CurveProfilePoint *new_table = MEM_callocN(sizeof(CurveProfilePoint) * (n_samples + 1), + "high-res table"); + + BKE_curveprofile_create_samples(profile, n_samples - 1, false, new_table); + /* Manually add last point at the end of the profile */ + new_table[n_samples - 1].x = 0.0f; + new_table[n_samples - 1].y = 1.0f; + + if (profile->table) { + MEM_freeN(profile->table); + } + profile->table = new_table; +} + +/** Creates the table of points used for displaying a preview of the sampled segment locations on + * the widget itself. */ +static void CurveProfile_make_segments_table(CurveProfile *profile) +{ + int n_samples = profile->segments_len; + if (n_samples <= 0) { + return; + } + CurveProfilePoint *new_table = MEM_callocN(sizeof(CurveProfilePoint) * (n_samples + 1), + "samples table"); + + if (profile->flag & PROF_SAMPLE_EVEN_LENGTHS) { + /* Even length sampling incompatible with only straight edge sampling for now. */ + BKE_curveprofile_create_samples_even_spacing(profile, n_samples, new_table); + } + else { + BKE_curveprofile_create_samples( + profile, n_samples, profile->flag & PROF_SAMPLE_STRAIGHT_EDGES, new_table); + } + + if (profile->segments) { + MEM_freeN(profile->segments); + } + profile->segments = new_table; +} + +/** Sets the default settings and clip range for the profile widget. Does not generate either + * table. */ +void BKE_curveprofile_set_defaults(CurveProfile *profile) +{ + profile->flag = PROF_USE_CLIP; + + BLI_rctf_init(&profile->view_rect, 0.0f, 1.0f, 0.0f, 1.0f); + profile->clip_rect = profile->view_rect; + + profile->path_len = 2; + profile->path = MEM_callocN(2 * sizeof(CurveProfilePoint), "path points"); + + profile->path[0].x = 1.0f; + profile->path[0].y = 0.0f; + profile->path[1].x = 1.0f; + profile->path[1].y = 1.0f; + + profile->changed_timestamp = 0; +} + +/** Returns a pointer to a newly allocated curve profile, using the given preset. + \param preset: Value in eCurveProfilePresets. */ +struct CurveProfile *BKE_curveprofile_add(int preset) +{ + CurveProfile *profile = MEM_callocN(sizeof(CurveProfile), "curve profile"); + + BKE_curveprofile_set_defaults(profile); + profile->preset = preset; + BKE_curveprofile_reset(profile); + curveprofile_make_table(profile); + + return profile; +} + +/** Should be called after the widget is changed. Does profile and remove double checks and more + * importantly, recreates the display / evaluation and segments tables. */ +void BKE_curveprofile_update(CurveProfile *profile, const bool remove_double) +{ + CurveProfilePoint *points = profile->path; + rctf *clipr = &profile->clip_rect; + float thresh; + float dx, dy; + int i; + + profile->changed_timestamp++; + + /* Clamp with the clipping rect in case something got past. */ + if (profile->flag & PROF_USE_CLIP) { + /* Move points inside the clip rectangle. */ + for (i = 0; i < profile->path_len; i++) { + points[i].x = max_ff(points[i].x, clipr->xmin); + points[i].x = min_ff(points[i].x, clipr->xmax); + points[i].y = max_ff(points[i].y, clipr->ymin); + points[i].y = min_ff(points[i].y, clipr->ymax); + } + /* Ensure zoom-level respects clipping. */ + if (BLI_rctf_size_x(&profile->view_rect) > BLI_rctf_size_x(&profile->clip_rect)) { + profile->view_rect.xmin = profile->clip_rect.xmin; + profile->view_rect.xmax = profile->clip_rect.xmax; + } + if (BLI_rctf_size_y(&profile->view_rect) > BLI_rctf_size_y(&profile->clip_rect)) { + profile->view_rect.ymin = profile->clip_rect.ymin; + profile->view_rect.ymax = profile->clip_rect.ymax; + } + } + + /* Remove doubles with a threshold set at 1% of default range. */ + thresh = 0.01f * BLI_rctf_size_x(clipr); + if (remove_double && profile->path_len > 2) { + for (i = 0; i < profile->path_len - 1; i++) { + dx = points[i].x - points[i + 1].x; + dy = points[i].y - points[i + 1].y; + if (sqrtf(dx * dx + dy * dy) < thresh) { + if (i == 0) { + points[i + 1].flag |= HD_VECT; + if (points[i + 1].flag & PROF_SELECT) { + points[i].flag |= PROF_SELECT; + } + } + else { + points[i].flag |= HD_VECT; + if (points[i].flag & PROF_SELECT) { + points[i + 1].flag |= PROF_SELECT; + } + } + break; /* Assumes 1 deletion per edit is ok. */ + } + } + if (i != profile->path_len - 1) { + BKE_curveprofile_remove_by_flag(profile, 2); + } + } + + /* Create the high resolution table for drawing and some evaluation functions. */ + curveprofile_make_table(profile); + + /* Store a table of samples for the segment locations for a preview and the table's user. */ + if (profile->segments_len > 0) { + CurveProfile_make_segments_table(profile); + } +} + +/** Refreshes the higher resolution table sampled from the input points. A call to this or + * curveprofile_update is needed before evaluation functions that use the table. Also sets the + * number of segments used for the display preview of the locations of the sampled points. */ +void BKE_curveprofile_initialize(CurveProfile *profile, short segments_len) +{ + profile->segments_len = segments_len; + + /* Calculate the higher resolution / segments tables for display and evaluation. */ + BKE_curveprofile_update(profile, false); +} + +/** Gives the distance to the next point in the widget's sampled table, in other words the length + * of the ith edge of the table. + * \note Requires curveprofile_initialize or curveprofile_update call before to fill table. */ +static float curveprofile_distance_to_next_table_point(const CurveProfile *profile, int i) +{ + BLI_assert(i < PROF_N_TABLE(profile->path_len)); + + return len_v2v2(&profile->table[i].x, &profile->table[i + 1].x); +} + +/** Calculates the total length of the profile from the curves sampled in the table. + * \note Requires curveprofile_initialize or curveprofile_update call before to fill table. */ +float BKE_curveprofile_total_length(const CurveProfile *profile) +{ + float total_length = 0; + for (int i = 0; i < PROF_N_TABLE(profile->path_len) - 1; i++) { + total_length += len_v2v2(&profile->table[i].x, &profile->table[i + 1].x); + } + return total_length; +} + +/** Samples evenly spaced positions along the curve profile's table (generated from path). Fills + * an entire table at once for a speedup if all of the results are going to be used anyway. + * \note Requires curveprofile_initialize or curveprofile_update call before to fill table. + * \note Working, but would conflict with "Sample Straight Edges" option, so this is unused for + * now. */ +void BKE_curveprofile_create_samples_even_spacing(CurveProfile *profile, + int n_segments, + CurveProfilePoint *r_samples) +{ + const float total_length = BKE_curveprofile_total_length(profile); + const float segment_length = total_length / n_segments; + float length_travelled = 0.0f; + float distance_to_next_table_point = curveprofile_distance_to_next_table_point(profile, 0); + float distance_to_previous_table_point = 0.0f; + float segment_left, factor; + int i_table = 0; + + /* Set the location for the first point. */ + r_samples[0].x = profile->table[0].x; + r_samples[0].y = profile->table[0].y; + + /* Travel along the path, recording the locations of segments as we pass them. */ + segment_left = segment_length; + for (int i = 1; i < n_segments; i++) { + /* Travel over all of the points that fit inside this segment. */ + while (distance_to_next_table_point < segment_left) { + length_travelled += distance_to_next_table_point; + segment_left -= distance_to_next_table_point; + i_table++; + distance_to_next_table_point = curveprofile_distance_to_next_table_point(profile, i_table); + distance_to_previous_table_point = 0.0f; + } + /* We're at the last table point that fits inside the current segment, use interpolation. */ + factor = (distance_to_previous_table_point + segment_left) / + (distance_to_previous_table_point + distance_to_next_table_point); + r_samples[i].x = interpf(profile->table[i_table + 1].x, profile->table[i_table].x, factor); + r_samples[i].y = interpf(profile->table[i_table + 1].y, profile->table[i_table].y, factor); +#ifdef DEBUG_CURVEPROFILE_EVALUATE + BLI_assert(factor <= 1.0f && factor >= 0.0f); + printf("segment_left: %.3f\n", segment_left); + printf("i_table: %d\n", i_table); + printf("distance_to_previous_table_point: %.3f\n", distance_to_previous_table_point); + printf("distance_to_next_table_point: %.3f\n", distance_to_next_table_point); + printf("Interpolating with factor %.3f from (%.3f, %.3f) to (%.3f, %.3f)\n\n", + factor, + profile->table[i_table].x, + profile->table[i_table].y, + profile->table[i_table + 1].x, + profile->table[i_table + 1].y); +#endif + + /* We sampled in between this table point and the next, so the next travel step is smaller. */ + distance_to_next_table_point -= segment_left; + distance_to_previous_table_point += segment_left; + length_travelled += segment_left; + segment_left = segment_length; + } +} + +/** Does a single evaluation along the profile's path. Travels down (length_portion * path) length + * and returns the position at that point. + * \param length_portion: The portion (0 to 1) of the path's full length to sample at. + * \note Requires curveprofile_initialize or curveprofile_update call before to fill table */ +void BKE_curveprofile_evaluate_length_portion(const CurveProfile *profile, + float length_portion, + float *x_out, + float *y_out) +{ + const float total_length = BKE_curveprofile_total_length(profile); + const float requested_length = length_portion * total_length; + + /* Find the last point along the path with a lower length portion than the input. */ + int i = 0; + float length_travelled = 0.0f; + while (length_travelled < requested_length) { + /* Check if we reached the last point before the final one. */ + if (i == PROF_N_TABLE(profile->path_len) - 2) { + break; + } + float new_length = curveprofile_distance_to_next_table_point(profile, i); + if (length_travelled + new_length >= requested_length) { + break; + } + length_travelled += new_length; + i++; + } + + /* Now travel the remaining distance of length portion down the path to the next point and + * find the location where we stop. */ + float distance_to_next_point = curveprofile_distance_to_next_table_point(profile, i); + float lerp_factor = (requested_length - length_travelled) / distance_to_next_point; + +#ifdef DEBUG_CURVEPROFILE_EVALUATE + printf("CURVEPROFILE EVALUATE\n"); + printf(" length portion input: %f\n", (double)length_portion); + printf(" requested path length: %f\n", (double)requested_length); + printf(" distance to next point: %f\n", (double)distance_to_next_point); + printf(" length travelled: %f\n", (double)length_travelled); + printf(" lerp-factor: %f\n", (double)lerp_factor); + printf(" ith point (%f, %f)\n", (double)profile->path[i].x, (double)profile->path[i].y); + printf(" next point(%f, %f)\n", (double)profile->path[i + 1].x, (double)profile->path[i + 1].y); +#endif + + *x_out = interpf(profile->table[i].x, profile->table[i + 1].x, lerp_factor); + *y_out = interpf(profile->table[i].y, profile->table[i + 1].y, lerp_factor); +} |