/* * 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 #include #include #include #include "MEM_guardedalloc.h" #include "DNA_curve_types.h" #include "DNA_curveprofile_types.h" #include "BLI_blenlib.h" #include "BLI_math.h" #include "BLI_task.h" #include "BLI_threads.h" #include "BLI_utildefines.h" #include "BKE_curve.h" #include "BKE_curveprofile.h" #include "BKE_fcurve.h" #include "BLO_read_write.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); /* Update the reference the points have to the profile. */ for (int i = 0; i < target->path_len; i++) { target->path[i].profile = target; } } 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; } /** * Move a point's handle, accounting for the alignment of handles with the #HD_ALIGN type. * * \param handle_1: Whether to move the 1st or 2nd control point. * \param delta: The *relative* change in the handle's position. * \note Requires #BKE_curveprofile_update call after. * \return Whether the handle moved from its start position. */ bool BKE_curveprofile_move_handle(struct CurveProfilePoint *point, const bool handle_1, const bool snap, const float delta[2]) { short handle_type = (handle_1) ? point->h1 : point->h2; float *handle_location = (handle_1) ? &point->h1_loc[0] : &point->h2_loc[0]; float start_position[2]; copy_v2_v2(start_position, handle_location); /* Don't move the handle if it's not a free handle type. */ if (!ELEM(handle_type, HD_FREE, HD_ALIGN)) { return false; } /* Move the handle. */ handle_location[0] += delta ? delta[0] : 0.0f; handle_location[1] += delta ? delta[1] : 0.0f; if (snap) { handle_location[0] = 0.125f * roundf(8.0f * handle_location[0]); handle_location[1] = 0.125f * roundf(8.0f * handle_location[1]); } /* Move the other handle if they are aligned. */ if (handle_type == HD_ALIGN) { short other_handle_type = (handle_1) ? point->h2 : point->h1; if (other_handle_type == HD_ALIGN) { float *other_handle_location = (handle_1) ? &point->h2_loc[0] : &point->h1_loc[0]; other_handle_location[0] = 2.0f * point->x - handle_location[0]; other_handle_location[1] = 2.0f * point->y - handle_location[1]; } } if (!equals_v2v2(handle_location, start_position)) { return true; } return false; } /** * Moves a control point, accounting for clipping and snapping, and moving free handles. * * \param snap: Whether to snap the point to the grid * \param delta: The *relative* change of the point's location. * \return Whether the point moved from its start position. * \note Requires #BKE_curveprofile_update call after. */ bool BKE_curveprofile_move_point(struct CurveProfile *profile, struct CurveProfilePoint *point, const bool snap, const float delta[2]) { float origx = point->x; float origy = point->y; point->x += delta[0]; point->y += delta[1]; if (snap) { point->x = 0.125f * roundf(8.0f * point->x); point->y = 0.125f * roundf(8.0f * point->y); } /* Clip here instead to test clipping here to stop handles from moving too. */ if (profile->flag & PROF_USE_CLIP) { point->x = max_ff(point->x, profile->clip_rect.xmin); point->x = min_ff(point->x, profile->clip_rect.xmax); point->y = max_ff(point->y, profile->clip_rect.ymin); point->y = min_ff(point->y, profile->clip_rect.ymax); } /* Also move free handles even when they aren't selected. */ if (ELEM(point->h1, HD_FREE, HD_ALIGN)) { point->h1_loc[0] += point->x - origx; point->h1_loc[1] += point->y - origy; } if (ELEM(point->h2, HD_FREE, HD_ALIGN)) { point->h2_loc[0] += point->x - origx; point->h2_loc[1] += point->y - origy; } if (point->x != origx || point->y != origy) { return true; } return false; } /** * Removes a specific point from the path of control points. * \note Requires #BKE_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, sizeof(CurveProfilePoint) * i_delete); memcpy(pts + i_delete, profile->path + i_delete + 1, sizeof(CurveProfilePoint) * (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 #BKE_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 #BKE_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. */ memcpy(&new_pts[i_new], &profile->path[i_old], sizeof(CurveProfilePoint)); new_pts[i_new].flag &= ~PROF_SELECT; /* Deselect old points. */ 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; } /* Give new point a reference to the profile. */ new_pt->profile = profile; } } /* 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_1, type_2: Handle type for the first handle. HD_VECT, HD_AUTO, HD_FREE, or HD_ALIGN. * \note Requires #BKE_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 (ELEM(profile->path[i].flag, PROF_SELECT, PROF_H1_SELECT, PROF_H2_SELECT)) { profile->path[i].h1 = type_1; profile->path[i].h2 = type_2; if (type_1 == HD_ALIGN && type_2 == HD_ALIGN) { /* Align the handles. */ BKE_curveprofile_move_handle(&profile->path[i], true, false, NULL); } } } } /** * Flips the profile across the diagonal so that its orientation is reversed. * * \note Requires #BKE_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++) { int i_reversed = profile->path_len - i - 1; BLI_assert(i_reversed >= 0); new_pts[i_reversed].x = profile->path[i].y; new_pts[i_reversed].y = profile->path[i].x; new_pts[i_reversed].flag = profile->path[i].flag; new_pts[i_reversed].h1 = profile->path[i].h2; new_pts[i_reversed].h2 = profile->path[i].h1; new_pts[i_reversed].profile = profile; /* Mirror free handles, they can't be recalculated. */ if (ELEM(profile->path[i].h1, HD_FREE, HD_ALIGN)) { new_pts[i_reversed].h1_loc[0] = profile->path[i].h2_loc[1]; new_pts[i_reversed].h1_loc[1] = profile->path[i].h2_loc[0]; } if (ELEM(profile->path[i].h2, HD_FREE, HD_ALIGN)) { new_pts[i_reversed].h2_loc[0] = profile->path[i].h1_loc[1]; new_pts[i_reversed].h2_loc[1] = profile->path[i].h1_loc[0]; } } /* 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 widgets 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 #BKE_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; } profile->flag &= ~PROF_DIRTY_PRESET; /* Ensure each point has a reference to the profile. */ for (int i = 0; i < profile->path_len; i++) { profile->path[i].profile = profile; } 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, mostly changed by removing the third dimension. */ 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; } 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; bezt[i].h2 = profile->path[i].h2; /* Copy handle locations if the handle type is free. */ if (ELEM(profile->path[i].h1, HD_FREE, HD_ALIGN)) { bezt[i].vec[0][0] = profile->path[i].h1_loc[0]; bezt[i].vec[0][1] = profile->path[i].h1_loc[1]; } if (ELEM(profile->path[i].h1, HD_FREE, HD_ALIGN)) { bezt[i].vec[2][0] = profile->path[i].h2_loc[0]; bezt[i].vec[2][1] = profile->path[i].h2_loc[1]; } } /* Get handle positions for the non-free 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); /* Copy the handle locations back to the control points. */ for (i = 0; i < totpoints; i++) { profile->path[i].h1_loc[0] = bezt[i].vec[0][0]; profile->path[i].h1_loc[1] = bezt[i].vec[0][1]; profile->path[i].h2_loc[0] = bezt[i].vec[2][0]; profile->path[i].h2_loc[1] = bezt[i].vec[2][1]; } /* 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); } /* Sample from the bezier points. X 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_TABLE_LEN(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[0].profile = profile; profile->path[1].x = 1.0f; profile->path[1].y = 1.0f; profile->path[1].profile = profile; 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. * \param update_flags: Bitfield with fields defined in header file. Controls removing doubles and * clipping. */ void BKE_curveprofile_update(CurveProfile *profile, const int update_flags) { CurveProfilePoint *points = profile->path; rctf *clipr = &profile->clip_rect; float thresh; 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. */ if (update_flags & PROF_UPDATE_CLIP) { 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); /* Extra sanity assert to make sure the points have the right profile pointer. */ BLI_assert(points[i].profile == profile); } } /* 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 = pow2f(0.01f * BLI_rctf_size_x(clipr)); if (update_flags & PROF_UPDATE_REMOVE_DOUBLES && profile->path_len > 2) { for (i = 0; i < profile->path_len - 1; i++) { if (len_squared_v2v2(&points[i].x, &points[i + 1].x) < thresh) { if (i == 0) { BKE_curveprofile_remove_point(profile, &points[1]); } else { BKE_curveprofile_remove_point(profile, &points[i]); } break; /* Assumes 1 deletion per update call is ok. */ } } } /* 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 * #BKE_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_init(CurveProfile *profile, short segments_len) { if (segments_len != profile->segments_len) { profile->flag |= PROF_DIRTY_PRESET; } profile->segments_len = segments_len; /* Calculate the higher resolution / segments tables for display and evaluation. */ BKE_curveprofile_update(profile, PROF_UPDATE_NONE); } /** * Gives the distance to the next point in the widgets sampled table, in other words the length * of the \a 'i' edge of the table. * * \note Requires #BKE_curveprofile_init or #BKE_curveprofile_update call before to fill table. */ static float curveprofile_distance_to_next_table_point(const CurveProfile *profile, int i) { BLI_assert(i < PROF_TABLE_LEN(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 #BKE_curveprofile_init or #BKE_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_TABLE_LEN(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 #BKE_curveprofile_init or #BKE_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 #BKE_curveprofile_init or #BKE_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_TABLE_LEN(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); } void BKE_curveprofile_blend_write(struct BlendWriter *writer, const struct CurveProfile *profile) { BLO_write_struct(writer, CurveProfile, profile); BLO_write_struct_array(writer, CurveProfilePoint, profile->path_len, profile->path); } /* Expects that the curve profile itself has been read already. */ void BKE_curveprofile_blend_read(struct BlendDataReader *reader, struct CurveProfile *profile) { BLO_read_data_address(reader, &profile->path); profile->table = NULL; profile->segments = NULL; /* Reset the points' pointers to the profile. */ for (int i = 0; i < profile->path_len; i++) { profile->path[i].profile = profile; } }