Blender V5.3
convexhull_2d.cc File Reference
#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)

Macro Definition Documentation

◆ USE_ANGLE_ITER_ORDER_ASSERT

#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.

Note
This may fail when USE_CONVEX_CROSS_PRODUCT_ENSURE isn't defined.

Definition at line 56 of file convexhull_2d.cc.

◆ USE_CONVEX_CROSS_PRODUCT_ENSURE

#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.