diff options
author | Sergey Sharybin <sergey.vfx@gmail.com> | 2012-07-16 21:54:28 +0400 |
---|---|---|
committer | Sergey Sharybin <sergey.vfx@gmail.com> | 2012-07-16 21:54:28 +0400 |
commit | 92205486e7d773928e1a09283f0e741fc2e9d24a (patch) | |
tree | 216ed57d98dd75f6b6517c4d4e5cade6b68e2260 /source/blender/blenkernel | |
parent | 3a039d0e101b2379a64d584bf3f77f2380fd0120 (diff) |
Masks: feather self-intersection collapse function
This implements simple function which collapses internal loops
caused by self-intersections into a singularity.
This loops can't be removed because rasterizer expects points
of feather be aligned with points from spline itself.
Diffstat (limited to 'source/blender/blenkernel')
-rw-r--r-- | source/blender/blenkernel/intern/mask.c | 136 |
1 files changed, 136 insertions, 0 deletions
diff --git a/source/blender/blenkernel/intern/mask.c b/source/blender/blenkernel/intern/mask.c index 9374b5dc1d9..d1610cda7d0 100644 --- a/source/blender/blenkernel/intern/mask.c +++ b/source/blender/blenkernel/intern/mask.c @@ -401,6 +401,140 @@ float (*BKE_mask_spline_differentiate(MaskSpline *spline, int *tot_diff_point))[ return BKE_mask_spline_differentiate_with_resolution(spline, 0, 0, tot_diff_point); } +/* ** feather points self-intersection collapse routine ** */ + +typedef struct FeatherEdgesBucket { + int tot_segment; + int (*segments)[2]; + int alloc_segment; +} FeatherEdgesBucket; + +static void feather_bucket_add_edge(FeatherEdgesBucket *bucket, int start, int end) +{ + const int alloc_delta = 20; + + if (bucket->tot_segment >= bucket->alloc_segment) { + if (!bucket->segments) { + bucket->segments = MEM_callocN(alloc_delta * sizeof(*bucket->segments), "feather bucket segments"); + } + else { + bucket->segments = MEM_reallocN(bucket->segments, + (alloc_delta + bucket->tot_segment) * sizeof(*bucket->segments)); + } + + bucket->alloc_segment += alloc_delta; + } + + bucket->segments[bucket->tot_segment][0] = start; + bucket->segments[bucket->tot_segment][1] = end; + + bucket->tot_segment++; +} + +static void feather_bucket_check_intersect(float (*feather_points)[2], FeatherEdgesBucket *bucket, int cur_a, int cur_b) +{ + int i; + + float *v1 = (float *) feather_points[cur_a]; + float *v2 = (float *) feather_points[cur_b]; + + for (i = 0; i< bucket->tot_segment; i++) { + int check_a = bucket->segments[i][0]; + int check_b = bucket->segments[i][1]; + + float *v3 = (float *) feather_points[check_a]; + float *v4 = (float *) feather_points[check_b]; + + if (check_a >= cur_a - 1 || cur_b == check_a) + continue; + + if (isect_seg_seg_v2(v1, v2, v3, v4)) { + int k; + float p[2]; + + isect_seg_seg_v2_point(v1, v2, v3, v4, p); + + for (k = check_b; k <= cur_a; k++) { + copy_v2_v2(feather_points[k], p); + } + + break; + } + } +} + +static void spline_feather_collapse_inner_loops(float (*feather_points)[2], int tot_feather_point) +{ +#define BUCKET_SIDE_INDEX(co, min, max) ((int) ((co - min) / (max - min + FLT_EPSILON) / bucket_size)) + +#define BUCKET_INDEX_DELTA(co, dx, dy) \ + BUCKET_SIDE_INDEX(co[1] + dy, min[1], max[1]) * buckets_per_side + \ + BUCKET_SIDE_INDEX(co[0] + dx, min[0], max[0]) + +#define BUCKET_INDEX(co) BUCKET_INDEX_DELTA(co, 0, 0) + + const int buckets_per_side = 10; + const int tot_bucket = buckets_per_side * buckets_per_side; + const float bucket_size = 1.0f / buckets_per_side; + + FeatherEdgesBucket *buckets; + + int i; + float min[2], max[2]; + + /* find min/max corners of mask to build buckets in that space */ + INIT_MINMAX2(min, max); + + for (i = 0; i < tot_feather_point; i++) { + DO_MINMAX2(feather_points[i], min, max); + } + + /* fill in buckets' edges */ + buckets = MEM_callocN(sizeof(FeatherEdgesBucket) * tot_bucket, "feather buckets"); + + for (i = 0; i < tot_feather_point; i++) { + int start = i; + int end = (i + 1) % tot_feather_point; + + int start_bucket_index = BUCKET_INDEX(feather_points[start]); + int end_bucket_index = BUCKET_INDEX(feather_points[end]); + + feather_bucket_add_edge(&buckets[start_bucket_index], start, end); + + if (start_bucket_index != end_bucket_index) { + feather_bucket_add_edge(&buckets[end_bucket_index], start, end); + } + } + + /* check all edges for intersection with edges from their buckets */ + for (i = 0; i < tot_feather_point; i++) { + int cur_a = i; + int cur_b = (i + 1) % tot_feather_point; + + int start_bucket_index = BUCKET_INDEX(feather_points[cur_a]); + int end_bucket_index = BUCKET_INDEX(feather_points[cur_b]); + + FeatherEdgesBucket *start_bucket = &buckets[start_bucket_index]; + FeatherEdgesBucket *end_bucket = &buckets[end_bucket_index]; + + feather_bucket_check_intersect(feather_points, start_bucket, cur_a, cur_b); + + if (start_bucket != end_bucket) + feather_bucket_check_intersect(feather_points, end_bucket, cur_a, cur_b); + } + + /* free buckets */ + for (i = 0; i < tot_bucket; i++) { + if (buckets[i].segments) + MEM_freeN(buckets[i].segments); + } + + MEM_freeN(buckets); + +#undef BUCKET_INDEX +#undef BUCKET_SIZE_INDEX +} + /** * values align with #BKE_mask_spline_differentiate_with_resolution_ex * when \a resol arguments match. @@ -467,6 +601,8 @@ float (*BKE_mask_spline_feather_differentiated_points_with_resolution_ex(MaskSpl *tot_feather_point = tot; + spline_feather_collapse_inner_loops(feather, tot); + return feather; } |