diff options
author | Martin Poirier <theeth@yahoo.com> | 2009-07-29 08:53:10 +0400 |
---|---|---|
committer | Martin Poirier <theeth@yahoo.com> | 2009-07-29 08:53:10 +0400 |
commit | 208c535869de41c9036582e80528c4cacb132339 (patch) | |
tree | 2ece33f988cd20cc5c9ccdb2f490fbb0e93c791e | |
parent | cacc5f782a5d792225f3d4970857f9776488ef3d (diff) |
Use the Ramer-Douglas-Peucker algorithm instead of a reverse Chaikin filter to reduce stroke complexity.
Divergence limit is 4 pixels (could be tweakable but 4 is a nice number).
-rw-r--r-- | source/blender/editors/armature/editarmature_sketch.c | 105 |
1 files changed, 98 insertions, 7 deletions
diff --git a/source/blender/editors/armature/editarmature_sketch.c b/source/blender/editors/armature/editarmature_sketch.c index 974eeb91a68..16c5971a930 100644 --- a/source/blender/editors/armature/editarmature_sketch.c +++ b/source/blender/editors/armature/editarmature_sketch.c @@ -89,6 +89,7 @@ typedef enum SK_PMode typedef struct SK_Point { float p[3]; + short p2d[2]; float no[3]; float size; SK_PType type; @@ -591,12 +592,14 @@ SK_Sketch* sk_createSketch() return sketch; } -void sk_initPoint(bContext *C, SK_Point *pt) +void sk_initPoint(bContext *C, SK_Point *pt, SK_DrawData *dd) { ARegion *ar = CTX_wm_region(C); RegionView3D *rv3d = ar->regiondata; VECCOPY(pt->no, rv3d->viewinv[2]); + pt->p2d[0] = dd->mval[0]; + pt->p2d[1] = dd->mval[1]; Normalize(pt->no); /* more init code here */ } @@ -892,16 +895,14 @@ void sk_cancelStroke(SK_Sketch *sketch) } } -/* Apply reverse Chaikin filter to simplify the polyline - * */ void sk_filterStroke(SK_Stroke *stk, int start, int end) { SK_Point *old_points = stk->points; int nb_points = stk->nb_points; + char *marked = NULL; + char work; int i, j; - return; - if (start == -1) { start = 0; @@ -917,6 +918,10 @@ void sk_filterStroke(SK_Stroke *stk, int start, int end) sk_appendStrokePoint(stk, old_points + i); } +#if 0 + + /* Apply reverse Chaikin filter to simplify the polyline + * */ for (i = start, j = start; i <= end; i++) { if (i - j == 3) @@ -960,6 +965,91 @@ void sk_filterStroke(SK_Stroke *stk, int start, int end) j = i; } } +#else + /* Ramer-Douglas-Peucker */ + marked = MEM_callocN(nb_points, "marked array"); + marked[start] = 1; + marked[end] = 1; + + work = 1; + + /* while still reducing */ + while (work) + { + int ls, le; + work = 0; + + ls = start; + le = start+1; + + /* while not over interval */ + while (ls < end) + { + int i; + int max_i = 0; + short v1[2]; + float max_dist = 16; /* more than 4 pixels */ + + /* find the next marked point */ + while(marked[le] == 0) + { + le++; + } + + /* perpendicular vector to ls-le */ + v1[1] = old_points[le].p2d[0] - old_points[ls].p2d[0]; + v1[0] = old_points[ls].p2d[1] - old_points[le].p2d[1]; + + + for( i = ls + 1; i < le; i++ ) + { + float mul; + float dist; + short v2[2]; + + v2[0] = old_points[i].p2d[0] - old_points[ls].p2d[0]; + v2[1] = old_points[i].p2d[1] - old_points[ls].p2d[1]; + + if (v2[0] == 0 && v2[1] == 0) + { + continue; + } + + mul = (float)(v1[0]*v2[0] + v1[1]*v2[1]) / (float)(v2[0]*v2[0] + v2[1]*v2[1]); + + dist = mul * mul * (v2[0]*v2[0] + v2[1]*v2[1]); + + if (dist > max_dist) + { + max_dist = dist; + max_i = i; + } + } + + if (max_i != 0) + { + work = 1; + marked[max_i] = 1; + } + + ls = le; + le = ls + 1; + } + } + + + /* adding points after range */ + for (i = start; i <= end; i++) + { + if (marked[i]) + { + sk_appendStrokePoint(stk, old_points + i); + } + } + + MEM_freeN(marked); +#endif + /* adding points after range */ for (i = end + 1; i < nb_points; i++) @@ -1571,7 +1661,7 @@ int sk_addStrokeDrawPoint(bContext *C, SK_Sketch *sketch, SK_Stroke *stk, SK_Dra { SK_Point pt; - sk_initPoint(C, &pt); + sk_initPoint(C, &pt, dd); sk_getStrokeDrawPoint(C, &pt, sketch, stk, dd); @@ -1734,7 +1824,7 @@ int sk_addStrokeSnapPoint(bContext *C, SK_Sketch *sketch, SK_Stroke *stk, SK_Dra int point_added; SK_Point pt; - sk_initPoint(C, &pt); + sk_initPoint(C, &pt, dd); point_added = sk_getStrokeSnapPoint(C, &pt, sketch, stk, dd); @@ -2998,6 +3088,7 @@ int sk_draw_stroke(bContext *C, SK_Sketch *sketch, SK_Stroke *stk, SK_DrawData * sk_addStrokePoint(C, sketch, stk, dd, snap); sk_updateDrawData(dd); sk_updateNextPoint(sketch, stk); + return 1; } |