diff options
author | Campbell Barton <ideasman42@gmail.com> | 2017-02-15 06:10:42 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2017-02-15 06:17:06 +0300 |
commit | 402b0aa59b2402a0fb72e5c64949a5480913a492 (patch) | |
tree | d3cbf4ad9783104654a01c135f6ef369b4422d1d /source/blender/blenlib | |
parent | af1e48e8ab7a25269ba5a44158bd16c564ed3535 (diff) |
Comments: notes on polyfill2d, minor corrections
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r-- | source/blender/blenlib/intern/polyfill2d.c | 17 |
1 files changed, 15 insertions, 2 deletions
diff --git a/source/blender/blenlib/intern/polyfill2d.c b/source/blender/blenlib/intern/polyfill2d.c index 8d9881e4539..2969b0eccf4 100644 --- a/source/blender/blenlib/intern/polyfill2d.c +++ b/source/blender/blenlib/intern/polyfill2d.c @@ -21,8 +21,15 @@ /** \file blender/blenlib/intern/polyfill2d.c * \ingroup bli * - * A simple implementation of the ear cutting algorithm - * to triangulate simple polygons without holes. + * An ear clipping algorithm to triangulate single boundary polygons. + * + * Details: + * + * - The algorithm guarantees all triangles are assigned (number of coords - 2) + * and that triangles will have non-overlapping indices (even for degenerate geometry). + * - Self-intersections are considered degenerate (resulting triangles will overlap). + * - While multiple polygons aren't supported, holes can still be defined using *key-holes* + * (where the polygon doubles back on its self with *exactly* matching coordinates). * * \note * @@ -74,6 +81,12 @@ typedef signed char eSign; #ifdef USE_KDTREE /** + * Spatial optimization for point-in-triangle intersection checks. + * The simple version of this algorithm is ``O(n^2)`` complexity + * (every point needing to check the triangle defined by every other point), + * Using a binary-tree reduces the complexity to ``O(n log n)`` + * plus some overhead of creating the tree. + * * This is a single purpose KDTree based on BLI_kdtree with some modifications * to better suit polyfill2d. * |