|
Blender V5.3
|
#include <algorithm>#include <cstdlib>#include <cstring>#include "MEM_guardedalloc.h"#include "BLI_bounds_types.hh"#include "BLI_convexhull_2d.hh"#include "BLI_math_vector.hh"#include "BLI_math_vector_c.hh"#include "BLI_math_vector_types.hh"#include "BLI_utildefines.hh"#include "BLI_strict_flags.hh"Go to the source code of this file.
Classes | |
| struct | blender::AngleCanonical |
| struct | blender::HullAngleStep |
| struct | blender::HullAngleIter |
Namespaces | |
| namespace | blender |
| BMesh Iterators. | |
Macros | |
| #define | USE_CONVEX_CROSS_PRODUCT_ENSURE |
| #define | USE_ANGLE_ITER_ORDER_ASSERT |
Functions | |
Internal Math Functions | |
| static float | blender::sincos_rotate_cw_x (const float2 &sincos, const float2 &p) |
| static float | blender::sincos_rotate_cw_y (const float2 &sincos, const float2 &p) |
Main Convex-Hull Calculation | |
An implementation of: "Andrew's monotone chain 2D convex hull algorithm". | |
| static float | blender::is_left (const float2 &p0, const float2 &p1, const float2 &p2) |
| static void | blender::convexhull_2d_stack_finalize (const float2 *points, const int r_points[], int2 &r_points_range) |
| static void | blender::convexhull_2d_stack_push (const float2 *points, int r_points[], int &top, int index) |
| static int | blender::convexhull_2d_sorted_impl (const float2 *points, const int points_num, int r_points[]) |
| static int2 | blender::convexhull_2d_sorted (const float2 *points, const int points_num, int r_points[]) |
| int | blender::BLI_convexhull_2d (Span< float2 > points, int r_points[]) |
Hull Angle Iteration | |
Step over all angles defined by a convex hull in order from 0-90 degrees, when angles are converted into their canonical form (see sincos_canonical). | |
| static float2 | blender::sincos_canonical (const float2 &sincos) |
| static int | blender::hull_angle_canonical_cmp (const AngleCanonical &a, const AngleCanonical &b) |
| static void | blender::hull_angle_insert_ordered (HullAngleIter &hiter, HullAngleStep *insert) |
| static bool | blender::convexhull_2d_angle_iter_step_on_axis (const HullAngleIter &hiter, HullAngleStep &hstep) |
| static HullAngleIter | blender::convexhull_2d_angle_iter_init (const float(*points_hull)[2], const int points_hull_num) |
| static float | blender::convexhull_2d_angle_iter_cross_for_assert (const HullAngleIter &hiter, const AngleCanonical &angle_prev) |
| static void | blender::convexhull_2d_angle_iter_step (HullAngleIter &hiter) |
Compute AABB Fitting Angle (Optimized) | |
| template<int Axis, int AxisSign> | |
| static float | blender::convexhull_2d_compute_extent_on_axis (const float(*points_hull)[2], const int points_hull_num, const float2 &sincos, int *index_p) |
| static float2 | blender::convexhull_aabb_fit_hull_2d (const float(*points_hull)[2], int points_hull_num) |
| float2 | blender::BLI_convexhull_aabb_fit_points_2d_as_sincos (Span< float2 > points) |
| float | blender::BLI_convexhull_aabb_fit_points_2d (Span< float2 > points) |
| #define USE_ANGLE_ITER_ORDER_ASSERT |
Assert the optimized bounds match a brute force check, disable by default is this is slow for dense hulls, using O(n^2) complexity. Assert that the angles the iterator is looping over are in order.
Definition at line 56 of file convexhull_2d.cc.
| #define USE_CONVEX_CROSS_PRODUCT_ENSURE |
The algorithm used to create the convex hull is susceptible to errors when the shape contains nearly overlapping vertices on polygons using large values. Unlike most floating point precision errors this happens when the numbers are not that big. Errors may occur in the range of 100-500 for polygons that are (near) degenerate. See the test: convexhull_2d.OctagonNearDuplicates which fails without this define.
To ensure the resulting hull is convex, perform additional convex cross-product checks when adding indices to the hull as well as running a final check on the start & end points. In the common case these checks aren't needed.
Note that it's especially important for the cross-product of each "ear" to be convex for AABB fitting since the method used relies on each edge "turning" in the same direction. When stepping over the hull: points that turn in a non-convex direction may break angle-stepping, causing the final rotation angle calculation to be incorrect, see: #143390.
Definition at line 43 of file convexhull_2d.cc.