Revision: 49005
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=49005
Author: nazgul
Date: 2012-07-17 16:26:38 +0000 (Tue, 17 Jul 2012)
Log Message:
-----------
Merging r49003 through r49004 from trunk into soc-2011-tomato
Revision Links:
--------------
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=49003
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=49004
Modified Paths:
--------------
branches/soc-2011-tomato/source/blender/blenkernel/intern/mask.c
Property Changed:
----------------
branches/soc-2011-tomato/
branches/soc-2011-tomato/source/blender/editors/interface/interface.c
branches/soc-2011-tomato/source/blender/editors/space_outliner/
Property changes on: branches/soc-2011-tomato
___________________________________________________________________
Modified: svn:mergeinfo
-
/branches/ge_harmony:42255,42279-42282,42286,42302,42338,42349,42616,42620,42698-42699,42739,42753,42773-42774,42832,44568,44597-44598,44793-44794
/branches/soc-2011-cucumber:37517,38166-38167,38177,38179-38180,38187,38242,38384,38387,38403-38404,38407,38968,38970,38973,39045,40845,42997-42998,43439
/branches/vgroup_modifiers:38694-39989
/trunk/blender:36831-49002
+
/branches/ge_harmony:42255,42279-42282,42286,42302,42338,42349,42616,42620,42698-42699,42739,42753,42773-42774,42832,44568,44597-44598,44793-44794
/branches/soc-2011-cucumber:37517,38166-38167,38177,38179-38180,38187,38242,38384,38387,38403-38404,38407,38968,38970,38973,39045,40845,42997-42998,43439
/branches/vgroup_modifiers:38694-39989
/trunk/blender:36831-49004
Modified: branches/soc-2011-tomato/source/blender/blenkernel/intern/mask.c
===================================================================
--- branches/soc-2011-tomato/source/blender/blenkernel/intern/mask.c
2012-07-17 16:22:18 UTC (rev 49004)
+++ branches/soc-2011-tomato/source/blender/blenkernel/intern/mask.c
2012-07-17 16:26:38 UTC (rev 49005)
@@ -429,7 +429,7 @@
static void feather_bucket_add_edge(FeatherEdgesBucket *bucket, int start, int
end)
{
- const int alloc_delta = 32;
+ const int alloc_delta = 256;
if (bucket->tot_segment >= bucket->alloc_segment) {
if (!bucket->segments) {
@@ -457,7 +457,7 @@
float *v1 = (float *) feather_points[cur_a];
float *v2 = (float *) feather_points[cur_b];
- for (i = 0; i< bucket->tot_segment; i++) {
+ for (i = 0; i < bucket->tot_segment; i++) {
int check_a = bucket->segments[i][0];
int check_b = bucket->segments[i][1];
@@ -495,34 +495,51 @@
}
}
-static int feather_bucket_index_from_coord(float co[2], float min[2], float
max[2],
- const int buckets_per_side, const
float bucket_size)
+static int feather_bucket_index_from_coord(float co[2], const float min[2],
const float bucket_scale[2],
+ const int buckets_per_side)
{
-#define BUCKET_SIDE_INDEX(co, min, max) ((int) ((co - min) / (max - min) /
bucket_size))
+ int x = (int) ((co[0] - min[0]) * bucket_scale[0]);
+ int y = (int) ((co[1] - min[1]) * bucket_scale[1]);
- int x = BUCKET_SIDE_INDEX(co[0], min[0], max[0]);
- int y = BUCKET_SIDE_INDEX(co[1], min[1], max[1]);
+ if (x == buckets_per_side)
+ x--;
- x = MIN2(x, buckets_per_side - 1);
- y = MIN2(y, buckets_per_side - 1);
+ if (y == buckets_per_side)
+ y--;
return y * buckets_per_side + x;
-#undef BUCKET_SIDE_INDEX
}
+static void feather_bucket_get_diagonal(FeatherEdgesBucket *buckets, int
start_bucket_index, int end_bucket_index,
+ int buckets_per_side,
FeatherEdgesBucket **diagonal_bucket_a_r,
+ FeatherEdgesBucket
**diagonal_bucket_b_r)
+{
+ int start_bucket_x = start_bucket_index % buckets_per_side;
+ int start_bucket_y = start_bucket_index / buckets_per_side;
+
+ int end_bucket_x = end_bucket_index % buckets_per_side;
+ int end_bucket_y = end_bucket_index / buckets_per_side;
+
+ int diagonal_bucket_a_index = start_bucket_y * buckets_per_side +
end_bucket_x;
+ int diagonal_bucket_b_index = end_bucket_y * buckets_per_side +
start_bucket_x;
+
+ *diagonal_bucket_a_r = &buckets[diagonal_bucket_a_index];
+ *diagonal_bucket_b_r = &buckets[diagonal_bucket_b_index];
+}
+
static void spline_feather_collapse_inner_loops(float (*feather_points)[2],
int tot_feather_point)
{
#define BUCKET_INDEX(co) \
- feather_bucket_index_from_coord(co, min, max, buckets_per_side,
bucket_size)
+ feather_bucket_index_from_coord(co, min, bucket_scale, buckets_per_side)
- 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;
+ int buckets_per_side, tot_bucket;
+ float bucket_size, bucket_scale[2];
FeatherEdgesBucket *buckets;
int i;
float min[2], max[2];
+ float max_delta_x = -1.0f, max_delta_y = -1.0f, max_delta;
if (tot_feather_point < 4) {
/* self-intersection works only for quads at least,
@@ -536,41 +553,95 @@
INIT_MINMAX2(min, max);
for (i = 0; i < tot_feather_point; i++) {
+ int next = i + 1;
+ float delta;
+
+ if (next == tot_feather_point)
+ next = 0;
+
+ delta = fabsf(feather_points[i][0] - feather_points[next][0]);
+ if (delta > max_delta_x)
+ max_delta_x = delta;
+
+ delta = fabsf(feather_points[i][1] - feather_points[next][1]);
+ if (delta > max_delta_y)
+ max_delta_y = delta;
+
DO_MINMAX2(feather_points[i], min, max);
}
+ /* use dynamically calculated buckets per side, so we likely wouldn't
+ * run into a situation when segment doesn't fit two buckets which is
+ * pain collecting candidates for intersection
+ */
+ max_delta_x /= max[0] - min[0];
+ max_delta_y /= max[1] - min[1];
+ max_delta = MAX2(max_delta_x, max_delta_y);
+
+ buckets_per_side = MIN2(512, 0.9f / max_delta);
+ tot_bucket = buckets_per_side * buckets_per_side;
+ bucket_size = 1.0f / buckets_per_side;
+
+ /* pre-compute multipliers, to save mathematical operations in loops */
+ bucket_scale[0] = 1.0f / ((max[0] - min[0]) * bucket_size);
+ bucket_scale[1] = 1.0f / ((max[1] - min[1]) * bucket_size);
+
/* 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 = i, end = i + 1;
+ int start_bucket_index, end_bucket_index;
- int start_bucket_index = BUCKET_INDEX(feather_points[start]);
- int end_bucket_index = BUCKET_INDEX(feather_points[end]);
+ if (end == tot_feather_point)
+ end = 0;
+ start_bucket_index = BUCKET_INDEX(feather_points[start]);
+ 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);
+ FeatherEdgesBucket *end_bucket =
&buckets[end_bucket_index];
+ FeatherEdgesBucket *diagonal_bucket_a,
*diagonal_bucket_b;
+
+ feather_bucket_get_diagonal(buckets,
start_bucket_index, end_bucket_index, buckets_per_side,
+ &diagonal_bucket_a,
&diagonal_bucket_b);
+
+ feather_bucket_add_edge(end_bucket, start, end);
+ feather_bucket_add_edge(diagonal_bucket_a, start, end);
+ feather_bucket_add_edge(diagonal_bucket_a, 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 cur_a = i, cur_b = i + 1;
+ int start_bucket_index, end_bucket_index;
- int start_bucket_index = BUCKET_INDEX(feather_points[cur_a]);
- int end_bucket_index = BUCKET_INDEX(feather_points[cur_b]);
+ FeatherEdgesBucket *start_bucket;
- FeatherEdgesBucket *start_bucket = &buckets[start_bucket_index];
- FeatherEdgesBucket *end_bucket = &buckets[end_bucket_index];
+ if (cur_b == tot_feather_point)
+ cur_b = 0;
+ start_bucket_index = BUCKET_INDEX(feather_points[cur_a]);
+ end_bucket_index = BUCKET_INDEX(feather_points[cur_b]);
+
+ start_bucket = &buckets[start_bucket_index];
+
feather_bucket_check_intersect(feather_points,
tot_feather_point, start_bucket, cur_a, cur_b);
- if (start_bucket != end_bucket)
+ if (start_bucket_index != end_bucket_index) {
+ FeatherEdgesBucket *end_bucket =
&buckets[end_bucket_index];
+ FeatherEdgesBucket *diagonal_bucket_a,
*diagonal_bucket_b;
+
+ feather_bucket_get_diagonal(buckets,
start_bucket_index, end_bucket_index, buckets_per_side,
+ &diagonal_bucket_a,
&diagonal_bucket_b);
+
feather_bucket_check_intersect(feather_points,
tot_feather_point, end_bucket, cur_a, cur_b);
+ feather_bucket_check_intersect(feather_points,
tot_feather_point, diagonal_bucket_a, cur_a, cur_b);
+ feather_bucket_check_intersect(feather_points,
tot_feather_point, diagonal_bucket_b, cur_a, cur_b);
+ }
}
/* free buckets */
Property changes on:
branches/soc-2011-tomato/source/blender/editors/interface/interface.c
___________________________________________________________________
Modified: svn:mergeinfo
- /branches/ge_candy/source/blender/editors/interface/interface.c:45070-46163
/branches/ge_harmony/source/blender/editors/interface/interface.c:42255,42279-42282,42286,42302,42338,42349,42616,42620,42698-42699,42739,42753,42773-42774,42832,44568,44597-44598,44793-44794
/branches/soc-2011-cucumber/source/blender/editors/interface/interface.c:37517,38166-38167,38177,38179-38180,38187,38242,38384,38387,38403-38404,38407,38968,38970,38973,39045,40845,42997-42998,43439
/branches/vgroup_modifiers/source/blender/editors/interface/interface.c:38694-39989
/trunk/blender/source/blender/editors/interface/interface.c:36831-49002
+ /branches/ge_candy/source/blender/editors/interface/interface.c:45070-46163
/branches/ge_harmony/source/blender/editors/interface/interface.c:42255,42279-42282,42286,42302,42338,42349,42616,42620,42698-42699,42739,42753,42773-42774,42832,44568,44597-44598,44793-44794
/branches/soc-2011-cucumber/source/blender/editors/interface/interface.c:37517,38166-38167,38177,38179-38180,38187,38242,38384,38387,38403-38404,38407,38968,38970,38973,39045,40845,42997-42998,43439
/branches/vgroup_modifiers/source/blender/editors/interface/interface.c:38694-39989
/trunk/blender/source/blender/editors/interface/interface.c:36831-49004
Property changes on:
branches/soc-2011-tomato/source/blender/editors/space_outliner
___________________________________________________________________
Modified: svn:mergeinfo
-
/branches/soc-2011-cucumber/source/blender/editors/space_outliner:38968,38970,38973,39045,40845
/branches/soc-2011-pepper/source/blender/editors/space_outliner:36831-38987
/trunk/blender/source/blender/editors/space_outliner:36831-49002
+
/branches/soc-2011-cucumber/source/blender/editors/space_outliner:38968,38970,38973,39045,40845
/branches/soc-2011-pepper/source/blender/editors/space_outliner:36831-38987
/trunk/blender/source/blender/editors/space_outliner:36831-49004
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
