diff options
author | Campbell Barton <ideasman42@gmail.com> | 2012-07-14 22:42:59 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2012-07-14 22:42:59 +0400 |
commit | a52153a618688bcabb9812959e7b1de7c4b92f71 (patch) | |
tree | 0fe9ae36544550f7072aa570f2e9bcba77a2e213 /source/blender/blenkernel | |
parent | 6946294ab95c3a32ca3d6c39daff6b5d24f4c724 (diff) |
mask rasterization: use a simpler method to check if a bucket intersects with a triangle.
Diffstat (limited to 'source/blender/blenkernel')
-rw-r--r-- | source/blender/blenkernel/intern/mask_rasterize.c | 162 |
1 files changed, 53 insertions, 109 deletions
diff --git a/source/blender/blenkernel/intern/mask_rasterize.c b/source/blender/blenkernel/intern/mask_rasterize.c index ecceb282392..9041e304444 100644 --- a/source/blender/blenkernel/intern/mask_rasterize.c +++ b/source/blender/blenkernel/intern/mask_rasterize.c @@ -217,73 +217,52 @@ void maskrasterize_spline_differentiate_point_outset(float (*diff_feather_points } } +/* this function is not exact, sometimes it retuns false positives, + * the main point of it is to clear out _almost_ all bucket/face non-intersections, + * returning TRUE in corner cases is ok but missing an intersection is NOT. + * + * method used + * - check if the center of the buckets bounding box is intersecting the face + * - if not get the max radius to a corner of the bucket and see how close we + * are to any of the triangle edges. + */ static int layer_bucket_isect_test(MaskRasterLayer *layer, unsigned int face_index, const unsigned int bucket_x, const unsigned int bucket_y, - const float bucket_x_size, const float bucket_y_size) + const float bucket_size_x, const float bucket_size_y, + const float bucket_max_rad_squared) { - const float xmin = layer->bounds.xmin + (bucket_x_size * bucket_x); - const float ymin = layer->bounds.ymin + (bucket_y_size * bucket_y); - const float xmax = xmin + bucket_x_size; - const float ymax = ymin + bucket_y_size; - - const float bucket_quad[4][2] = {{xmin, ymin}, - {xmin, ymax}, - {xmax, ymax}, - {xmax, ymin}}; - unsigned int *face = layer->face_array[face_index]; float (*cos)[3] = layer->face_coords; -// float dummy_lambda; + const float xmin = layer->bounds.xmin + (bucket_size_x * bucket_x); + const float ymin = layer->bounds.ymin + (bucket_size_y * bucket_y); + const float xmax = xmin + bucket_size_x; + const float ymax = ymin + bucket_size_y; + + float cent[2] = {(xmin + xmax) * 0.5f, + (ymin + ymax) * 0.5f}; if (face[3] == TRI_VERT) { const float *v1 = cos[face[0]]; const float *v2 = cos[face[1]]; const float *v3 = cos[face[2]]; - /* bucket corner in tri? */ - if (isect_point_tri_v2(bucket_quad[0], v1, v2, v3) || - isect_point_tri_v2(bucket_quad[1], v1, v2, v3) || - isect_point_tri_v2(bucket_quad[2], v1, v2, v3) || - isect_point_tri_v2(bucket_quad[3], v1, v2, v3)) - { - return TRUE; - } - - /* line intersect */ -#if 1 - if (isect_line_line_v2(bucket_quad[0], bucket_quad[1], v1, v2) || - isect_line_line_v2(bucket_quad[0], bucket_quad[1], v2, v3) || - isect_line_line_v2(bucket_quad[0], bucket_quad[1], v3, v1) || - - isect_line_line_v2(bucket_quad[1], bucket_quad[2], v1, v2) || - isect_line_line_v2(bucket_quad[1], bucket_quad[2], v2, v3) || - isect_line_line_v2(bucket_quad[1], bucket_quad[2], v3, v1) || - - isect_line_line_v2(bucket_quad[2], bucket_quad[3], v1, v2) || - isect_line_line_v2(bucket_quad[2], bucket_quad[3], v2, v3) || - isect_line_line_v2(bucket_quad[2], bucket_quad[3], v3, v1) || - - isect_line_line_v2(bucket_quad[3], bucket_quad[0], v1, v2) || - isect_line_line_v2(bucket_quad[3], bucket_quad[0], v2, v3) || - isect_line_line_v2(bucket_quad[3], bucket_quad[0], v3, v1) - - ) - { + if (isect_point_tri_v2(cent, v1, v2, v3)) { return TRUE; } -#else - /* line intersect */ - if (isect_line_tri_v3(bucket_quad[0], bucket_quad[1], v1, v2, v3, &dummy_lambda, NULL) || - isect_line_tri_v3(bucket_quad[1], bucket_quad[2], v1, v2, v3, &dummy_lambda, NULL) || - isect_line_tri_v3(bucket_quad[2], bucket_quad[3], v1, v2, v3, &dummy_lambda, NULL) || - isect_line_tri_v3(bucket_quad[3], bucket_quad[0], v1, v2, v3, &dummy_lambda, NULL)) - { - return TRUE; + else { + if ((dist_squared_to_line_segment_v2(cent, v1, v2) < bucket_max_rad_squared) || + (dist_squared_to_line_segment_v2(cent, v2, v3) < bucket_max_rad_squared) || + (dist_squared_to_line_segment_v2(cent, v3, v1) < bucket_max_rad_squared)) + { + return TRUE; + } + else { + // printf("skip tri\n"); + return FALSE; + } } -#endif - return FALSE; } else { const float *v1 = cos[face[0]]; @@ -291,66 +270,25 @@ static int layer_bucket_isect_test(MaskRasterLayer *layer, unsigned int face_ind const float *v3 = cos[face[2]]; const float *v4 = cos[face[3]]; - /* bucket corner in tri? */ - if (isect_point_tri_v2(bucket_quad[0], v1, v2, v3) || - isect_point_tri_v2(bucket_quad[1], v1, v2, v3) || - isect_point_tri_v2(bucket_quad[2], v1, v2, v3) || - isect_point_tri_v2(bucket_quad[3], v1, v2, v3)) - { - return TRUE; - } - else if (isect_point_tri_v2(bucket_quad[0], v1, v3, v4) || - isect_point_tri_v2(bucket_quad[1], v1, v3, v4) || - isect_point_tri_v2(bucket_quad[2], v1, v3, v4) || - isect_point_tri_v2(bucket_quad[3], v1, v3, v4)) - { - return TRUE; - } - - /* line intersect */ -#if 1 - if (isect_line_line_v2(bucket_quad[0], bucket_quad[1], v1, v2) || - isect_line_line_v2(bucket_quad[0], bucket_quad[1], v2, v3) || - isect_line_line_v2(bucket_quad[0], bucket_quad[1], v3, v4) || - isect_line_line_v2(bucket_quad[0], bucket_quad[1], v4, v1) || - - isect_line_line_v2(bucket_quad[1], bucket_quad[2], v1, v2) || - isect_line_line_v2(bucket_quad[1], bucket_quad[2], v2, v3) || - isect_line_line_v2(bucket_quad[1], bucket_quad[2], v3, v4) || - isect_line_line_v2(bucket_quad[1], bucket_quad[2], v4, v1) || - - isect_line_line_v2(bucket_quad[2], bucket_quad[3], v1, v2) || - isect_line_line_v2(bucket_quad[2], bucket_quad[3], v2, v3) || - isect_line_line_v2(bucket_quad[2], bucket_quad[3], v3, v4) || - isect_line_line_v2(bucket_quad[2], bucket_quad[3], v4, v1) || - - isect_line_line_v2(bucket_quad[3], bucket_quad[0], v1, v2) || - isect_line_line_v2(bucket_quad[3], bucket_quad[0], v2, v3) || - isect_line_line_v2(bucket_quad[3], bucket_quad[0], v3, v4) || - isect_line_line_v2(bucket_quad[3], bucket_quad[0], v4, v1) - - ) - { + if (isect_point_tri_v2(cent, v1, v2, v3)) { return TRUE; } -#else - if (isect_line_tri_v3(bucket_quad[0], bucket_quad[1], v1, v2, v3, &dummy_lambda, NULL) || - isect_line_tri_v3(bucket_quad[1], bucket_quad[2], v1, v2, v3, &dummy_lambda, NULL) || - isect_line_tri_v3(bucket_quad[2], bucket_quad[3], v1, v2, v3, &dummy_lambda, NULL) || - isect_line_tri_v3(bucket_quad[3], bucket_quad[0], v1, v2, v3, &dummy_lambda, NULL)) - { + else if (isect_point_tri_v2(cent, v1, v3, v4)) { return TRUE; } - else if (isect_line_tri_v3(bucket_quad[0], bucket_quad[1], v1, v3, v4, &dummy_lambda, NULL) || - isect_line_tri_v3(bucket_quad[1], bucket_quad[2], v1, v3, v4, &dummy_lambda, NULL) || - isect_line_tri_v3(bucket_quad[2], bucket_quad[3], v1, v3, v4, &dummy_lambda, NULL) || - isect_line_tri_v3(bucket_quad[3], bucket_quad[0], v1, v3, v4, &dummy_lambda, NULL)) - { - return TRUE; + else { + if ((dist_squared_to_line_segment_v2(cent, v1, v2) < bucket_max_rad_squared) || + (dist_squared_to_line_segment_v2(cent, v2, v3) < bucket_max_rad_squared) || + (dist_squared_to_line_segment_v2(cent, v3, v4) < bucket_max_rad_squared) || + (dist_squared_to_line_segment_v2(cent, v4, v1) < bucket_max_rad_squared)) + { + return TRUE; + } + else { + // printf("skip quad\n"); + return FALSE; + } } -#endif - - return FALSE; } } @@ -374,8 +312,10 @@ static void layer_bucket_init(MaskRasterLayer *layer, const float pixel_size) { /* width and height of each bucket */ - const float bucket_size_x = bucket_dim_x / layer->buckets_x; - const float bucket_size_y = bucket_dim_y / layer->buckets_y; + const float bucket_size_x = (bucket_dim_x + FLT_EPSILON) / layer->buckets_x; + const float bucket_size_y = (bucket_dim_y + FLT_EPSILON) / layer->buckets_y; + const float bucket_max_rad = (maxf(bucket_size_x, bucket_size_y) * M_SQRT2) + FLT_EPSILON; + const float bucket_max_rad_squared = bucket_max_rad * bucket_max_rad; unsigned int *face = &layer->face_array[0][0]; float (*cos)[3] = layer->face_coords; @@ -438,7 +378,11 @@ static void layer_bucket_init(MaskRasterLayer *layer, const float pixel_size) /* note: there is a tradeoff here since checking box/tri intersections isn't * as optimal as it could be, but checking pixels against faces they will never intersect * with is likely the greater slowdown here - so check if the cell intersects the face */ - if (layer_bucket_isect_test(layer, face_index, xi, yi, bucket_size_x, bucket_size_y)) { + if (layer_bucket_isect_test(layer, face_index, + xi, yi, + bucket_size_x, bucket_size_y, + bucket_max_rad_squared)) + { BLI_linklist_prepend_arena(&bucketstore[bucket_index], face_index_void, arena); bucketstore_tot[bucket_index]++; } |