[Bf-blender-cvs] [3eb66494539] master: GPencil: Add uniform subdivide BKE to improve interpolation
Falk David
noreply at git.blender.org
Sat Dec 12 16:50:50 CET 2020
Commit: 3eb66494539b58d67b1605e76a070a97e910f124
Author: Falk David
Date: Sat Dec 12 16:34:38 2020 +0100
Branches: master
https://developer.blender.org/rB3eb66494539b58d67b1605e76a070a97e910f124
GPencil: Add uniform subdivide BKE to improve interpolation
This patch introduces a new BKE function that performs a uniform subdivide.
The goal of this function is to subdivide the stroke to reach a target number of points while maintaining its shape, color, and weights.
This is done by repeatedly subdividing the longest edge in the stroke. Every subdivision adds a new point at the exact middle point of an edge.
The function is intended to be used in the interpolation operators to give better results when interpolating between different sized strokes.
Reviewed By: antoniov
Differential Revision: https://developer.blender.org/D9835
===================================================================
M source/blender/blenkernel/BKE_gpencil_geom.h
M source/blender/blenkernel/intern/gpencil_geom.c
===================================================================
diff --git a/source/blender/blenkernel/BKE_gpencil_geom.h b/source/blender/blenkernel/BKE_gpencil_geom.h
index b107a6e72af..111f9030463 100644
--- a/source/blender/blenkernel/BKE_gpencil_geom.h
+++ b/source/blender/blenkernel/BKE_gpencil_geom.h
@@ -164,6 +164,11 @@ bool BKE_gpencil_convert_mesh(struct Main *bmain,
const bool use_seams,
const bool use_faces);
+void BKE_gpencil_stroke_uniform_subdivide(struct bGPdata *gpd,
+ struct bGPDstroke *gps,
+ const uint32_t target_number,
+ const bool select);
+
#ifdef __cplusplus
}
#endif
diff --git a/source/blender/blenkernel/intern/gpencil_geom.c b/source/blender/blenkernel/intern/gpencil_geom.c
index fc74439fd76..85b02d2ba3b 100644
--- a/source/blender/blenkernel/intern/gpencil_geom.c
+++ b/source/blender/blenkernel/intern/gpencil_geom.c
@@ -34,6 +34,7 @@
#include "BLI_blenlib.h"
#include "BLI_ghash.h"
#include "BLI_hash.h"
+#include "BLI_heap.h"
#include "BLI_math_vector.h"
#include "BLI_polyfill_2d.h"
@@ -3224,4 +3225,197 @@ void BKE_gpencil_stroke_join(bGPDstroke *gps_a,
gps_a, dvert, pt, delta, pt->pressure * ratio, pt->strength, deltatime);
}
}
+
+/* Stroke Uniform Subdivide ------------------------------------- */
+
+typedef struct tSamplePoint {
+ struct tSamplePoint *next, *prev;
+ float x, y, z;
+ float pressure, strength, time;
+ float vertex_color[4];
+ struct MDeformWeight *dw;
+ int totweight;
+} tSamplePoint;
+
+typedef struct tSampleEdge {
+ float length_sq;
+ tSamplePoint *from;
+ tSamplePoint *to;
+} tSampleEdge;
+
+/* Helper: creates a tSamplePoint from a bGPDspoint and (optionally) a MDeformVert. */
+static tSamplePoint *new_sample_point_from_gp_point(const bGPDspoint *pt, const MDeformVert *dvert)
+{
+ tSamplePoint *new_pt = MEM_callocN(sizeof(tSamplePoint), __func__);
+ copy_v3_v3(&new_pt->x, &pt->x);
+ new_pt->pressure = pt->pressure;
+ new_pt->strength = pt->strength;
+ new_pt->time = pt->time;
+ copy_v4_v4((float *)&new_pt->vertex_color, (float *)&pt->vert_color);
+ if (dvert != NULL) {
+ new_pt->totweight = dvert->totweight;
+ new_pt->dw = MEM_callocN(sizeof(MDeformWeight) * new_pt->totweight, __func__);
+ for (uint i = 0; i < new_pt->totweight; ++i) {
+ MDeformWeight *dw = &new_pt->dw[i];
+ MDeformWeight *dw_from = &dvert->dw[i];
+ dw->def_nr = dw_from->def_nr;
+ dw->weight = dw_from->weight;
+ }
+ }
+ return new_pt;
+}
+
+/* Helper: creates a tSampleEdge from two tSamplePoints. Also calculates the length (squared) of
+ * the edge. */
+static tSampleEdge *new_sample_edge_from_sample_points(tSamplePoint *from, tSamplePoint *to)
+{
+ tSampleEdge *new_edge = MEM_callocN(sizeof(tSampleEdge), __func__);
+ new_edge->from = from;
+ new_edge->to = to;
+ new_edge->length_sq = len_squared_v3v3(&from->x, &to->x);
+ return new_edge;
+}
+
+/**
+ * Subdivide the grease pencil stroke so the number of points is target_number.
+ * Does not change the shape of the stroke. The new points will be distributed as
+ * uniformly as possible by repeatedly subdividing the current longest edge.
+ *
+ * \param gps: The stroke to be upsampled.
+ * \param target_number: The number of points the upsampled stroke should have.
+ * \param select: Select/Deselect the stroke.
+ */
+void BKE_gpencil_stroke_uniform_subdivide(bGPdata *gpd,
+ bGPDstroke *gps,
+ const uint32_t target_number,
+ const bool select)
+{
+ /* Stroke needs at least two points and strictly less points than the target number. */
+ if (gps == NULL || gps->totpoints < 2 || gps->totpoints >= target_number) {
+ return;
+ }
+
+ const int totpoints = gps->totpoints;
+ const bool has_dverts = (gps->dvert != NULL);
+ const bool is_cyclic = (gps->flag & GP_STROKE_CYCLIC);
+
+ ListBase points = {NULL, NULL};
+ Heap *edges = BLI_heap_new();
+
+ /* Add all points into list. */
+ for (uint32_t i = 0; i < totpoints; ++i) {
+ bGPDspoint *pt = &gps->points[i];
+ MDeformVert *dvert = has_dverts ? &gps->dvert[i] : NULL;
+ tSamplePoint *sp = new_sample_point_from_gp_point(pt, dvert);
+ BLI_addtail(&points, sp);
+ }
+
+ /* Iterate over edges and insert them into the heap. */
+ for (tSamplePoint *pt = ((tSamplePoint *)points.first)->next; pt != NULL; pt = pt->next) {
+ tSampleEdge *se = new_sample_edge_from_sample_points(pt->prev, pt);
+ /* BLI_heap is a min-heap, but we need the largest key to be at the top, so we take the
+ * negative of the squared length. */
+ BLI_heap_insert(edges, -(se->length_sq), se);
+ }
+
+ if (is_cyclic) {
+ tSamplePoint *sp_first = points.first;
+ tSamplePoint *sp_last = points.last;
+ tSampleEdge *se = new_sample_edge_from_sample_points(sp_last, sp_first);
+ BLI_heap_insert(edges, -(se->length_sq), se);
+ }
+
+ int num_points_needed = target_number - totpoints;
+ BLI_assert(num_points_needed > 0);
+
+ while (num_points_needed > 0) {
+ tSampleEdge *se = BLI_heap_pop_min(edges);
+ tSamplePoint *sp = se->from;
+ tSamplePoint *sp_next = se->to;
+
+ /* Subdivide the edge. */
+ tSamplePoint *new_sp = MEM_callocN(sizeof(tSamplePoint), __func__);
+ interp_v3_v3v3(&new_sp->x, &sp->x, &sp_next->x, 0.5f);
+ new_sp->pressure = interpf(sp->pressure, sp_next->pressure, 0.5f);
+ new_sp->strength = interpf(sp->strength, sp_next->strength, 0.5f);
+ new_sp->time = interpf(sp->time, sp_next->time, 0.5f);
+ interp_v4_v4v4((float *)&new_sp->vertex_color,
+ (float *)&sp->vertex_color,
+ (float *)&sp_next->vertex_color,
+ 0.5f);
+ if (sp->dw && sp_next->dw) {
+ new_sp->totweight = MIN2(sp->totweight, sp_next->totweight);
+ new_sp->dw = MEM_callocN(sizeof(MDeformWeight) * new_sp->totweight, __func__);
+ for (uint32_t i = 0; i < new_sp->totweight; ++i) {
+ MDeformWeight *dw = &new_sp->dw[i];
+ MDeformWeight *dw_from = &sp->dw[i];
+ MDeformWeight *dw_to = &sp_next->dw[i];
+ dw->def_nr = dw_from->def_nr;
+ dw->weight = interpf(dw_from->weight, dw_to->weight, 0.5f);
+ }
+ }
+ BLI_insertlinkafter(&points, sp, new_sp);
+
+ tSampleEdge *se_prev = new_sample_edge_from_sample_points(sp, new_sp);
+ tSampleEdge *se_next = new_sample_edge_from_sample_points(new_sp, sp_next);
+ BLI_heap_insert(edges, -(se_prev->length_sq), se_prev);
+ BLI_heap_insert(edges, -(se_next->length_sq), se_next);
+
+ MEM_freeN(se);
+ num_points_needed--;
+ }
+
+ /* Edges are no longer needed. Heap is freed. */
+ BLI_heap_free(edges, (HeapFreeFP)MEM_freeN);
+
+ gps->totpoints = target_number;
+ gps->points = MEM_recallocN(gps->points, sizeof(bGPDspoint) * gps->totpoints);
+ if (has_dverts) {
+ gps->dvert = MEM_recallocN(gps->dvert, sizeof(MDeformVert) * gps->totpoints);
+ }
+
+ /* Convert list back to stroke point array. */
+ tSamplePoint *sp = points.first;
+ for (uint32_t i = 0; i < gps->totpoints && sp; ++i, sp = sp->next) {
+ bGPDspoint *pt = &gps->points[i];
+ MDeformVert *dvert = &gps->dvert[i];
+
+ copy_v3_v3(&pt->x, &sp->x);
+ pt->pressure = sp->pressure;
+ pt->strength = sp->strength;
+ pt->time = sp->time;
+ copy_v4_v4((float *)&pt->vert_color, (float *)&sp->vertex_color);
+
+ if (sp->dw) {
+ dvert->totweight = sp->totweight;
+ dvert->dw = MEM_callocN(sizeof(MDeformWeight) * dvert->totweight, __func__);
+ for (uint32_t j = 0; j < dvert->totweight; ++j) {
+ MDeformWeight *dw = &dvert->dw[j];
+ MDeformWeight *dw_from = &sp->dw[j];
+ dw->def_nr = dw_from->def_nr;
+ dw->weight = dw_from->weight;
+ }
+ }
+ if (select) {
+ pt->flag |= GP_SPOINT_SELECT;
+ }
+ }
+
+ if (select) {
+ gps->flag |= GP_STROKE_SELECT;
+ }
+
+ /* Free the sample points. Important to use the mutable loop here because we are erasing the list
+ * elements. */
+ LISTBASE_FOREACH_MUTABLE (tSamplePoint *, temp, &points) {
+ if (temp->dw != NULL) {
+ MEM_freeN(temp->dw);
+ }
+ MEM_SAFE_FREE(temp);
+ }
+
+ /* Update the geometry of the stroke. */
+ BKE_gpencil_stroke_geometry_update(gpd, gps);
+}
+
/** \} */
More information about the Bf-blender-cvs
mailing list