diff options
author | Campbell Barton <ideasman42@gmail.com> | 2012-07-14 21:58:42 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2012-07-14 21:58:42 +0400 |
commit | 83d1fac2e471ae3278e1e6b12041de71b0038b87 (patch) | |
tree | 383f0c704704757eb6f07fdb7d28ad5b9044b98c /source/blender/blenkernel | |
parent | 8a9d1c0a795aad31c19cc3f0c70e2f53578f49dd (diff) |
mask rasterizer - test if buckets overlap the face before adding the face into the bucket.
Diffstat (limited to 'source/blender/blenkernel')
-rw-r--r-- | source/blender/blenkernel/intern/mask_rasterize.c | 182 |
1 files changed, 162 insertions, 20 deletions
diff --git a/source/blender/blenkernel/intern/mask_rasterize.c b/source/blender/blenkernel/intern/mask_rasterize.c index c4690f1d7c1..ecceb282392 100644 --- a/source/blender/blenkernel/intern/mask_rasterize.c +++ b/source/blender/blenkernel/intern/mask_rasterize.c @@ -217,28 +217,166 @@ void maskrasterize_spline_differentiate_point_outset(float (*diff_feather_points } } +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 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; + + 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) + + ) + { + 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; + } + +#endif + return FALSE; + } + else { + const float *v1 = cos[face[0]]; + const float *v2 = cos[face[1]]; + 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) + + ) + { + 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)) + { + 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; + } +#endif + + return FALSE; + } +} static void layer_bucket_init(MaskRasterLayer *layer, const float pixel_size) { MemArena *arena = BLI_memarena_new(1 << 16, __func__); - { - const float dims[2] = {layer->bounds.xmax - layer->bounds.xmin, - layer->bounds.ymax - layer->bounds.ymin}; + const float bucket_dim_x = layer->bounds.xmax - layer->bounds.xmin; + const float bucket_dim_y = layer->bounds.ymax - layer->bounds.ymin; - layer->buckets_x = (dims[0] / pixel_size) / (float)BUCKET_PIXELS_PER_CELL; - layer->buckets_y = (dims[1] / pixel_size) / (float)BUCKET_PIXELS_PER_CELL; + layer->buckets_x = (bucket_dim_x / pixel_size) / (float)BUCKET_PIXELS_PER_CELL; + layer->buckets_y = (bucket_dim_y / pixel_size) / (float)BUCKET_PIXELS_PER_CELL; // printf("bucket size %ux%u\n", layer->buckets_x, layer->buckets_y); - CLAMP(layer->buckets_x, 8, 512); - CLAMP(layer->buckets_y, 8, 512); + CLAMP(layer->buckets_x, 8, 512); + CLAMP(layer->buckets_y, 8, 512); - layer->buckets_xy_scalar[0] = (1.0f / (dims[0] + FLT_EPSILON)) * layer->buckets_x; - layer->buckets_xy_scalar[1] = (1.0f / (dims[1] + FLT_EPSILON)) * layer->buckets_y; - } + layer->buckets_xy_scalar[0] = (1.0f / (bucket_dim_x + FLT_EPSILON)) * layer->buckets_x; + layer->buckets_xy_scalar[1] = (1.0f / (bucket_dim_y + FLT_EPSILON)) * layer->buckets_y; { + /* 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; + unsigned int *face = &layer->face_array[0][0]; float (*cos)[3] = layer->face_coords; @@ -283,22 +421,27 @@ static void layer_bucket_init(MaskRasterLayer *layer, const float pixel_size) const unsigned int xi_max = (unsigned int) ((xmax - layer->bounds.xmin) * layer->buckets_xy_scalar[0]); const unsigned int yi_min = (unsigned int) ((ymin - layer->bounds.ymin) * layer->buckets_xy_scalar[1]); const unsigned int yi_max = (unsigned int) ((ymax - layer->bounds.ymin) * layer->buckets_xy_scalar[1]); + void *face_index_void = SET_UINT_IN_POINTER(face_index); unsigned int xi, yi; - for (xi = xi_min; xi <= xi_max; xi++) { - for (yi = yi_min; yi <= yi_max; yi++) { - unsigned int bucket_index = (layer->buckets_x * yi) + xi; + for (yi = yi_min; yi <= yi_max; yi++) { + unsigned int bucket_index = (layer->buckets_x * yi) + xi_min; + for (xi = xi_min; xi <= xi_max; xi++, bucket_index++) { + // unsigned int bucket_index = (layer->buckets_x * yi) + xi; /* correct but do in outer loop */ BLI_assert(xi < layer->buckets_x); BLI_assert(yi < layer->buckets_y); BLI_assert(bucket_index < bucket_tot); - BLI_linklist_prepend_arena(&bucketstore[bucket_index], - SET_UINT_IN_POINTER(face_index), - arena); - - bucketstore_tot[bucket_index]++; + /* check if the bucket intersects with the face */ + /* 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)) { + BLI_linklist_prepend_arena(&bucketstore[bucket_index], face_index_void, arena); + bucketstore_tot[bucket_index]++; + } } } } @@ -343,8 +486,7 @@ void BLI_maskrasterize_handle_init(MaskRasterHandle *mr_handle, struct Mask *mas const short do_aspect_correct, const short do_mask_aa, const short do_feather) { - /* TODO: real size */ - const int resol = SPLINE_RESOL; + const int resol = SPLINE_RESOL; /* TODO: real size */ const float pixel_size = 1.0f / MIN2(width, height); const float zvec[3] = {0.0f, 0.0f, 1.0f}; |