#include <algorithm>
#include <cstdlib>
#include <cstring>
#include "MEM_guardedalloc.h"
#include "BLI_bounds_types.hh"
#include "BLI_convexhull_2d.hh"
#include "BLI_math_vector.h"
#include "BLI_math_vector.hh"
#include "BLI_math_vector_types.hh"
#include "BLI_utildefines.h"
#include "BLI_strict_flags.h"

Classes
struct	AngleCanonical
struct	HullAngleStep
struct	HullAngleIter

Macros
#define	USE_CONVEX_CROSS_PRODUCT_ENSURE
#define	USE_ANGLE_ITER_ORDER_ASSERT

Typedefs
using	float2

Functions
Internal Math Functions
static float	sincos_rotate_cw_x (const float2 &sincos, const float2 &p)
static float	sincos_rotate_cw_y (const float2 &sincos, const float2 &p)
Main Convex-Hull Calculation
static float	is_left (const float2 &p0, const float2 &p1, const float2 &p2)
static void	convexhull_2d_stack_finalize (const float2 *points, const int r_points[], blender::int2 &r_points_range)
static void	convexhull_2d_stack_push (const float2 *points, int r_points[], int &top, int index)
static int	convexhull_2d_sorted_impl (const float2 *points, const int points_num, int r_points[])
static blender::int2	convexhull_2d_sorted (const float2 *points, const int points_num, int r_points[])
int	BLI_convexhull_2d (blender::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	sincos_canonical (const float2 &sincos)
static int	hull_angle_canonical_cmp (const AngleCanonical &a, const AngleCanonical &b)
static void	hull_angle_insert_ordered (HullAngleIter &hiter, HullAngleStep *insert)
static bool	convexhull_2d_angle_iter_step_on_axis (const HullAngleIter &hiter, HullAngleStep &hstep)
static HullAngleIter	convexhull_2d_angle_iter_init (const float(*points_hull)[2], const int points_hull_num)
static void	convexhull_2d_angle_iter_step (HullAngleIter &hiter)
Compute AABB Fitting Angle (Optimized)
template<int Axis, int AxisSign>
static float	convexhull_2d_compute_extent_on_axis (const float(points_hull)[2], const int points_hull_num, const float2 &sincos, int index_p)
static float	convexhull_aabb_fit_hull_2d (const float(*points_hull)[2], int points_hull_num)
float	BLI_convexhull_aabb_fit_points_2d (blender::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 54 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 41 of file convexhull_2d.cc.

Typedef Documentation

◆ float2

using blender::float2

Definition at line 618 of file BLI_math_vector_types.hh.

Function Documentation

◆ BLI_convexhull_2d()

int BLI_convexhull_2d	(	blender::Span< float2 >	points,
		int	r_points[] )

Definition at line 309 of file convexhull_2d.cc.

References b, BLI_assert, convexhull_2d_sorted(), copy_v2_v2(), i, MEM_freeN(), MEM_malloc_arrayN(), and blender::Span< T >::size().

Referenced by BLI_convexhull_aabb_fit_points_2d().

◆ BLI_convexhull_aabb_fit_points_2d()

float BLI_convexhull_aabb_fit_points_2d ( blender::Span< float2 > points )

Definition at line 788 of file convexhull_2d.cc.

References angle(), BLI_assert, BLI_convexhull_2d(), convexhull_aabb_fit_hull_2d(), copy_v2_v2(), float, MEM_freeN(), MEM_malloc_arrayN(), and blender::Span< T >::size().

◆ convexhull_2d_angle_iter_init()

HullAngleIter convexhull_2d_angle_iter_init	(	const float(*)	points_hull[2],
		const int	points_hull_num )

static

Definition at line 577 of file convexhull_2d.cc.

References blender::math::abs(), HullAngleStep::angle, HullAngleIter::axis, convexhull_2d_angle_iter_step_on_axis(), hull_angle_insert_ordered(), i, AngleCanonical::index, HullAngleStep::index, HullAngleStep::index_max, LIKELY, blender::math::normalize_and_get_length(), HullAngleIter::points_hull, HullAngleIter::points_hull_num, and sincos_canonical().

Referenced by convexhull_aabb_fit_hull_2d().

◆ convexhull_2d_angle_iter_step()

void convexhull_2d_angle_iter_step ( HullAngleIter & hiter )

static

Definition at line 660 of file convexhull_2d.cc.

References HullAngleStep::angle, HullAngleIter::axis_ordered, BLI_assert, convexhull_2d_angle_iter_step_on_axis(), hull_angle_canonical_cmp(), hull_angle_insert_ordered(), HullAngleStep::next, and UNUSED_VARS_NDEBUG.

Referenced by convexhull_aabb_fit_hull_2d().

◆ convexhull_2d_angle_iter_step_on_axis()

bool convexhull_2d_angle_iter_step_on_axis	(	const HullAngleIter &	hiter,
		HullAngleStep &	hstep )

static

Definition at line 554 of file convexhull_2d.cc.

References HullAngleStep::angle, BLI_assert, AngleCanonical::index, HullAngleStep::index, HullAngleStep::index_max, LIKELY, blender::math::normalize_and_get_length(), HullAngleIter::points_hull, HullAngleIter::points_hull_num, AngleCanonical::sincos, AngleCanonical::sincos_canonical, and sincos_canonical().

Referenced by convexhull_2d_angle_iter_init(), and convexhull_2d_angle_iter_step().

◆ convexhull_2d_compute_extent_on_axis()

template<int Axis, int AxisSign>

float convexhull_2d_compute_extent_on_axis	(	const float(*)	points_hull[2],
		const int	points_hull_num,
		const float2 &	sincos,
		int *	index_p )

static

When using the rotating calipers, step one half of the caliper to a new index.

Note that this relies on points_hull being ordered CCW which BLI_convexhull_2d ensures.

Definition at line 693 of file convexhull_2d.cc.

References BLI_assert, count, sincos_rotate_cw_x(), and sincos_rotate_cw_y().

Referenced by convexhull_aabb_fit_hull_2d().

◆ convexhull_2d_sorted()

blender::int2 convexhull_2d_sorted	(	const float2 *	points,
		const int	points_num,
		int	r_points[] )

static

The range of r_points to use (inclusive).

Note: A range is used since points may be removed from the beginning of r_points, this avoids removing elements from the beginning of the array in favor of skipping them to keep the order of points predictable.

Definition at line 299 of file convexhull_2d.cc.

References convexhull_2d_sorted_impl(), convexhull_2d_stack_finalize(), and top.

Referenced by BLI_convexhull_2d().

◆ convexhull_2d_sorted_impl()

int convexhull_2d_sorted_impl	(	const float2 *	points,
		const int	points_num,
		int	r_points[] )

static

Returns: the number of points in r_points minus 1.

Definition at line 188 of file convexhull_2d.cc.

References BLI_assert, convexhull_2d_stack_push(), i, is_left(), and top.

Referenced by convexhull_2d_sorted().

◆ convexhull_2d_stack_finalize()

void convexhull_2d_stack_finalize	(	const float2 *	points,
		const int	r_points[],
		blender::int2 &	r_points_range )

static

Final pass on r_points & r_points_range,

Definition at line 114 of file convexhull_2d.cc.

References is_left(), top, UNLIKELY, and UNUSED_VARS.

Referenced by convexhull_2d_sorted().

◆ convexhull_2d_stack_push()

void convexhull_2d_stack_push	(	const float2 *	points,
		int	r_points[],
		int &	top,
		int	index )

inlinestatic

This practically always results in r_points[++top] = index. In rare cases extra checks are needed.

Definition at line 165 of file convexhull_2d.cc.

References is_left(), top, UNLIKELY, and UNUSED_VARS.

Referenced by convexhull_2d_sorted_impl().

◆ convexhull_aabb_fit_hull_2d()

float convexhull_aabb_fit_hull_2d	(	const float(*)	points_hull[2],
		int	points_hull_num )

static

Definition at line 725 of file convexhull_2d.cc.

References angle(), HullAngleStep::angle, atan2(), HullAngleIter::axis, HullAngleIter::axis_ordered, BLI_assert, convexhull_2d_angle_iter_init(), convexhull_2d_angle_iter_step(), convexhull_2d_compute_extent_on_axis(), AngleCanonical::index, blender::Bounds< T >::max, max, blender::Bounds< T >::min, and min.

Referenced by BLI_convexhull_aabb_fit_points_2d().

◆ hull_angle_canonical_cmp()

int hull_angle_canonical_cmp	(	const AngleCanonical &	a,
		const AngleCanonical &	b )

static

Definition at line 487 of file convexhull_2d.cc.

References b, AngleCanonical::index, and AngleCanonical::sincos_canonical.

Referenced by convexhull_2d_angle_iter_step(), and hull_angle_insert_ordered().

◆ hull_angle_insert_ordered()

void hull_angle_insert_ordered	(	HullAngleIter &	hiter,
		HullAngleStep *	insert )

static

Definition at line 542 of file convexhull_2d.cc.

References HullAngleStep::angle, HullAngleIter::axis_ordered, hull_angle_canonical_cmp(), insert(), and HullAngleStep::next.

Referenced by convexhull_2d_angle_iter_init(), and convexhull_2d_angle_iter_step().

◆ is_left()

float is_left	(	const float2 &	p0,
		const float2 &	p1,
		const float2 &	p2 )

static

Tests if a point is [left / on / right] of an infinite line.

Parameters

p0	Point (start of the line).
p1	Point (end of the line).
p2	Point (point to compare).

Returns

value > 0.0 for p2 left of the line through p0 and p1.
value = 0.0 for p2 on the line.
value < 0.0 for p2 right of the line.

Note: When using to check the hull is convex: arguments 1 & 2 are set to the larger span across the hull (lowest-to-highest index) with the mid-point being the last argument. This is a convention that should be followed to prevent mismatching results depending on argument order.

Definition at line 106 of file convexhull_2d.cc.

Referenced by area_actionzone_get_rect(), area_split_invoke(), BKE_camera_multiview_model_matrix_scaled(), BKE_camera_multiview_view_matrix(), BKE_camera_multiview_view_matrix(), camera_stereo3d_model_matrix(), camera_stereo3d_shift_x(), convexhull_2d_sorted_impl(), convexhull_2d_stack_finalize(), convexhull_2d_stack_push(), blender::ed::curves::pen_tool::move_handles_in_curve(), UI_panel_category_draw_all(), view3d_stereo3d_setup(), and view3d_stereo3d_setup_offscreen().

◆ sincos_canonical()

float2 sincos_canonical ( const float2 & sincos )

static

Return a canonical version of sincos for the purpose of bounding box fitting, this maps any sincos to 0-1 range for both sin & cos.

Definition at line 434 of file convexhull_2d.cc.

References BLI_assert, and result.

Referenced by convexhull_2d_angle_iter_init(), and convexhull_2d_angle_iter_step_on_axis().

◆ sincos_rotate_cw_x()

float sincos_rotate_cw_x	(	const float2 &	sincos,
		const float2 &	p )

static

Definition at line 62 of file convexhull_2d.cc.

Referenced by convexhull_2d_compute_extent_on_axis().

◆ sincos_rotate_cw_y()

float sincos_rotate_cw_y	(	const float2 &	sincos,
		const float2 &	p )

static

Definition at line 67 of file convexhull_2d.cc.

Referenced by convexhull_2d_compute_extent_on_axis().

Classes

Macros

Typedefs

Functions

Macro Definition Documentation

◆ USE_ANGLE_ITER_ORDER_ASSERT

◆ USE_CONVEX_CROSS_PRODUCT_ENSURE

Typedef Documentation

◆ float2

Function Documentation

◆ BLI_convexhull_2d()

◆ BLI_convexhull_aabb_fit_points_2d()

◆ convexhull_2d_angle_iter_init()

◆ convexhull_2d_angle_iter_step()

◆ convexhull_2d_angle_iter_step_on_axis()

◆ convexhull_2d_compute_extent_on_axis()

◆ convexhull_2d_sorted()

◆ convexhull_2d_sorted_impl()

◆ convexhull_2d_stack_finalize()

◆ convexhull_2d_stack_push()

◆ convexhull_aabb_fit_hull_2d()

◆ hull_angle_canonical_cmp()

◆ hull_angle_insert_ordered()

◆ is_left()

◆ sincos_canonical()

◆ sincos_rotate_cw_x()

◆ sincos_rotate_cw_y()