#include <cmath>
#include <cstdlib>
#include "MEM_guardedalloc.h"
#include "BLI_boxpack_2d.h"
#include "BLI_listbase.h"
#include "BLI_math_base.h"
#include "BLI_utildefines.h"
#include "BLI_sort.h"
#include "BLI_strict_flags.h"

Classes
struct	BoxVert
struct	VertSortContext

Macros
#define	qsort_r BLI_qsort_r
#define	USE_MERGE
#define	USE_FREE_STRIP
#define	USE_PACK_BIAS
#define	EPSILON 0.0000001f
#define	EPSILON_MERGE 0.00001f
#define	EPSILON_BIAS 0.000001f
#define	BLF 1
#define	TRF 2
#define	TLF 4
#define	BRF 8
#define	CORNERFLAGS (BLF \| TRF \| TLF \| BRF)
#define	BL 0
#define	TR 1
#define	TL 2
#define	BR 3
#define	A (vert->trb->v[TL])
#define	B (vert->tlb->v[TR])
#define	MASK (BLF \| BRF)
#define	A (vert->blb->v[BR])
#define	B (vert->brb->v[BL])
#define	MASK (TRF \| TLF)
#define	A (vert->blb->v[TL])
#define	B (vert->tlb->v[BL])
#define	MASK (TRF \| BRF)
#define	A (vert->brb->v[TR])
#define	B (vert->trb->v[BR])
#define	MASK (TLF \| BLF)

Functions
BLI_INLINE int	quad_flag (uint q)
static void	vert_bias_update (BoxVert *v)
void	BLI_box_pack_2d (BoxPack boxarray, const uint len, const bool sort_boxes, float r_tot_x, float *r_tot_y)
void	BLI_box_pack_2d_fixedarea (ListBase boxes, int width, int height, ListBase packed)
Box Accessor Functions
static float	box_xmin_get (const BoxPack *box)
static float	box_xmax_get (const BoxPack *box)
static float	box_ymin_get (const BoxPack *box)
static float	box_ymax_get (const BoxPack *box)
Box Placement
BLI_INLINE void	box_v34x_update (BoxPack *box)
BLI_INLINE void	box_v34y_update (BoxPack *box)
static void	box_xmin_set (BoxPack *box, const float f)
static void	box_xmax_set (BoxPack *box, const float f)
static void	box_ymin_set (BoxPack *box, const float f)
static void	box_ymax_set (BoxPack *box, const float f)
Box Utils
static float	box_area (const BoxPack *box)
static bool	box_isect (const BoxPack box_a, const BoxPack box_b)
Box/Vert Sorting
static int	box_areasort (const void p1, const void p2)
static int	vertex_sort (const void p1, const void p2, void *vs_ctx_p)

Macro Definition Documentation

◆ A [1/4]

#define A (vert->brb->v[TR])

◆ A [2/4]

#define A (vert->blb->v[TL])

◆ A [3/4]

#define A (vert->blb->v[BR])

◆ A [4/4]

#define A (vert->trb->v[TL])

Referenced by add_m3_m3m3(), add_m4_m4m4(), bake_differentials(), BKE_ocean_is_valid(), BLI_box_pack_2d(), BLI_ewa_filter(), BLI_ewa_imp2radangle(), BLI_ghashutil_paircmp(), bsdf_hair_huang_albedo(), bsdf_hair_huang_eval_trrt(), bssrdf_burley_fitting(), bssrdf_burley_setup(), btDoSimplex2(), btDoSimplex3(), btDoSimplex4(), btFactorLDLT(), btLCP::btLCP(), btLDLTRemove(), btRemoveRowCol(), btSolveDantzigLCP(), btSwapProblem(), btSwapRowsAndCols(), slim::build_linear_system(), slim::buildA(), Freestyle::ViewEdgeXBuilder::BuildSmoothFEdge(), blender::eevee::burley_setup(), Freestyle::GridHelpers::closestPointToSegment(), GivensRotation::columnRotation(), GivensRotation::columnRotation(), Freestyle::ViewMapBuilder::computeCusps(), Freestyle::ViewMapBuilder::ComputeRayCastingVisibility(), libmv::ComputeTrackingEquation(), Eigen::ConstrainedConjugateGradient< _MatrixType, _UpLo, _Filter, _Preconditioner >::ConstrainedConjugateGradient(), Freestyle::crossesProscenium(), cullPoints2(), CurvePoint_fedge_get(), CurvePoint_first_svertex_get(), dBoxBox2(), Freestyle::GeomUtils::distPointSegment(), btDeformableNeoHookeanForce::DotProduct(), libmv::EightPointSolver(), libmv::euclidean_resection::EuclideanResectionPPnP(), libmv::ExtractColumns(), extractRotation(), FEdge_first_svertex_get(), GivensRotation::fill(), GivensRotation::fill(), film_adaptive_sampling_convergence_check(), btLemkeAlgorithm::findLexicographicMinimum(), Freestyle::ViewMapBuilder::FindOccludee(), Freestyle::ViewMapBuilder::FindOccludee(), Freestyle::findOccludee(), Freestyle::findOccludee(), blender::ed::object::followpath_path_animate_exec(), fresnel_dielectric_cos(), fresnel_dielectric_cos(), libmv::FrobeniusDistance(), libmv::FrobeniusNorm(), libmv::FundamentalFrom7CorrespondencesLinear(), btLemkeAlgorithm::GaussJordanEliminationStep(), Freestyle::GenerateBezier(), blender::ed::greasepencil::get_reordered_indices(), Freestyle::ViewMap::getClosestFEdge(), Freestyle::ViewMap::getClosestViewEdge(), libmv::euclidean_resection::IJToIndex(), Freestyle::GeomUtils::include2dSeg2dArea(), Freestyle::GeomUtils::includePointTriangle(), interp_m3_m3m3(), interp_m4_m4m4(), blender::math::interpolate(), blender::math::interpolate(), Freestyle::GeomUtils::intersect2dSeg2dArea(), madd_m3_m3m3fl(), madd_m4_m4m4fl(), libmv::MatrixColumn(), libmv::MatrixColumn(), libmv::MatrixColumn(), libmv::euclidean_resection::MatrixToConstraint(), md5_process_block(), libmv::MeanAndVarianceAlongRows(), libmv::Dogleg< Function, Jacobian, Solver >::minimize(), libmv::LevenbergMarquardt< Function, Jacobian, Solver >::minimize(), mnee_solve_matrix_h_to_x(), mul_m3_m3_pre(), mul_m3_m3m3(), mul_m3_m3m4(), mul_m3_m4m3(), mul_m3_m4m4(), mul_m4_m3m4(), mul_m4_m4_pre(), mul_m4_m4m3(), mul_m4_m4m4(), mul_m4_m4m4_aligned_scale(), mul_m4_m4m4_split_channels(), mul_m4db_m4db_m4fl(), newPerlin(), nlaevalchan_keycmp(), libmv::Nullspace(), libmv::Nullspace2(), operator!=(), Freestyle::Functions0D::Curvature2DAngleF0D::operator()(), Freestyle::Functions0D::VertexOrientation2DF0D::operator()(), Freestyle::Functions0D::VertexOrientation3DF0D::operator()(), Freestyle::less_SVertex2D::operator()(), GivensRotation::operator*(), GivensRotation::operator*=(), operator<(), operator==(), operator==(), Freestyle::ImagePyramid::pixel(), slim::polar_svd(), polarDecomposition(), polarDecomposition(), blender::ed::greasepencil::primitive_calulate_curve_positions(), pseudoinverse_m4_m4(), radangle2imp(), GivensRotation::rowRotation(), GivensRotation::rowRotation(), libmv::SelectKeyframesBasedOnGRICAndVariance(), SIM_hair_volume_solve_divergence(), singularValueDecomposition(), singularValueDecomposition(), singularValueDecomposition(), btConjugateGradient< MatrixX >::solve(), btConjugateResidual< MatrixX >::solve(), btKrylovSolver< MatrixX >::solve(), btLemkeAlgorithm::solve(), iTaSC::Solver::solve(), iTaSC::WDLSSolver::solve(), iTaSC::WSDLSSolver::solve(), solve_least_squares(), libmv::SolveCubicPolynomial(), btDantzigSolver::solveMLCP(), btLemkeSolver::solveMLCP(), btMLCPSolverInterface::solveMLCP(), btSolveProjectedGaussSeidel::solveMLCP(), SolveP3(), Freestyle::SShape::SplitEdge(), sub_m3_m3m3(), KDL::svd_eigen_HH(), svd_m4(), swapCol(), Freestyle::StrokeTesselator::Tesselate(), transform_equal_threshold(), libmv::TransposeInPlace(), triangle_light_pdf(), triangle_light_sample(), libmv::Dogleg< Function, Jacobian, Solver >::Update(), libmv::LevenbergMarquardt< Function, Jacobian, Solver >::Update(), and IK_QElbowSegment::UpdateAngleApply().

◆ B [1/4]

#define B (vert->trb->v[BR])

◆ B [2/4]

#define B (vert->tlb->v[BL])

◆ B [3/4]

#define B (vert->brb->v[BL])

◆ B [4/4]

#define B (vert->tlb->v[TR])

◆ BL

#define BL 0

Definition at line 74 of file boxpack_2d.cc.

Referenced by BLI_box_pack_2d(), box_v34x_update(), box_v34y_update(), box_xmax_set(), box_xmin_get(), box_xmin_set(), box_ymax_set(), box_ymin_get(), and box_ymin_set().

◆ BLF

#define BLF 1

Definition at line 62 of file boxpack_2d.cc.

Referenced by BLI_box_pack_2d().

◆ BR

#define BR 3

Definition at line 77 of file boxpack_2d.cc.

Referenced by BKE_idtype_idcode_to_index(), BKE_idtype_idfilter_to_index(), BLI_box_pack_2d(), box_v34x_update(), and box_v34y_update().

◆ BRF

#define BRF 8

Definition at line 65 of file boxpack_2d.cc.

Referenced by BLI_box_pack_2d().

◆ CORNERFLAGS

#define CORNERFLAGS (BLF | TRF | TLF | BRF)

Definition at line 66 of file boxpack_2d.cc.

Referenced by BLI_box_pack_2d().

◆ EPSILON

#define EPSILON 0.0000001f

Definition at line 57 of file boxpack_2d.cc.

Referenced by box_isect(), and btMultiBodySliderConstraint::createConstraintRows().

◆ EPSILON_BIAS

#define EPSILON_BIAS 0.000001f

Definition at line 60 of file boxpack_2d.cc.

Referenced by vert_bias_update().

◆ EPSILON_MERGE

#define EPSILON_MERGE 0.00001f

Definition at line 58 of file boxpack_2d.cc.

Referenced by BLI_box_pack_2d().

◆ MASK [1/4]

#define MASK (TLF | BLF)

◆ MASK [2/4]

#define MASK (TRF | BRF)

◆ MASK [3/4]

#define MASK (TRF | TLF)

◆ MASK [4/4]

#define MASK (BLF | BRF)

Referenced by BLI_box_pack_2d(), and nanovdb::CachedReadAccessor< BuildT >::insert().

◆ qsort_r

#define qsort_r BLI_qsort_r

Definition at line 20 of file boxpack_2d.cc.

Referenced by BLI_box_pack_2d().

◆ TL

#define TL 2

Definition at line 76 of file boxpack_2d.cc.

Referenced by BLI_box_pack_2d(), box_v34x_update(), and box_v34y_update().

◆ TLF

#define TLF 4

Definition at line 64 of file boxpack_2d.cc.

Referenced by BLI_box_pack_2d().

◆ TR

#define TR 1

Definition at line 75 of file boxpack_2d.cc.

Referenced by BLI_box_pack_2d(), box_v34x_update(), box_v34y_update(), box_xmax_get(), box_xmax_set(), box_xmin_set(), box_ymax_get(), box_ymax_set(), box_ymin_set(), and bsdf_hair_huang_sample().

◆ TRF

#define TRF 2

Definition at line 63 of file boxpack_2d.cc.

Referenced by BLI_box_pack_2d().

◆ USE_FREE_STRIP

#define USE_FREE_STRIP

Definition at line 27 of file boxpack_2d.cc.

◆ USE_MERGE

#define USE_MERGE

Definition at line 25 of file boxpack_2d.cc.

◆ USE_PACK_BIAS

#define USE_PACK_BIAS

Definition at line 29 of file boxpack_2d.cc.

Function Documentation

◆ BLI_box_pack_2d()

void BLI_box_pack_2d	(	BoxPack *	boxarray,
		unsigned int	len,
		bool	sort_boxes,
		float *	r_tot_x,
		float *	r_tot_y )

Main box-packing function accessed from other functions This sets boxes x,y to positive values, sorting from 0,0 outwards. There is no limit to the space boxes may take, only that they will be packed tightly into the lower left hand corner (0,0)

Parameters

box_array	a pre-allocated array of boxes. only the 'box->x' and 'box->y' are set, 'box->w' and 'box->h' are used, 'box->index' is not used at all, the only reason its there is that the box array is sorted by area and programs need to be able to have some way of writing the boxes back to the original data.
len	the number of boxes in the array.
sort_boxes	Sort box_array before packing.
r_tot_x,r_tot_y	set so you can normalize the data.

Definition at line 257 of file boxpack_2d.cc.

References A, B, BL, BoxVert::blb, BLF, BLI_assert, box_areasort(), VertSortContext::box_height, box_isect(), VertSortContext::box_width, box_xmax_get(), box_xmax_set(), box_xmin_get(), box_xmin_set(), box_ymax_get(), box_ymax_set(), box_ymin_get(), box_ymin_set(), BR, BoxVert::brb, BRF, CORNERFLAGS, ELEM, EPSILON_MERGE, fabsf, BoxVert::free, BoxPack::h, i, BoxVert::index, BoxVert::isect_cache, len, MASK, max_ff(), MEM_freeN(), MEM_malloc_arrayN(), qsort_r, quad_flag(), TL, BoxVert::tlb, TLF, TR, BoxVert::trb, TRF, UNLIKELY, BoxVert::used, BoxPack::v, vert_bias_update(), VertSortContext::vertarray, vertex_sort(), BoxPack::w, BoxPack::x, BoxVert::x, BoxPack::y, and BoxVert::y.

Referenced by M_Geometry_box_pack_2d(), and blender::geometry::pack_island_box_pack_2d().

◆ BLI_box_pack_2d_fixedarea()

void BLI_box_pack_2d_fixedarea	(	struct ListBase *	boxes,
		int	width,
		int	height,
		struct ListBase *	packed )

Packs boxes into a fixed area.

Boxes and packed are linked lists containing structs that can be cast to FixedSizeBoxPack (i.e. contains a FixedSizeBoxPack as its first element). Boxes that were packed successfully are placed into *packed and removed from *boxes.

The algorithm is a simplified version of https://github.com/TeamHypersomnia/rectpack2D. Better ones could be used, but for the current use case (packing Image tiles into GPU textures) this is fine.

Note that packing efficiency depends on the order of the input boxes. Generally speaking, larger boxes should come first, though how exactly size is best defined (e.g. area, perimeter) depends on the particular application.

Definition at line 649 of file boxpack_2d.cc.

References BLI_addhead(), BLI_addtail(), BLI_freelistN(), BLI_remlink(), FixedSizeBoxPack::h, LISTBASE_FOREACH, LISTBASE_FOREACH_MUTABLE, MEM_callocN(), MEM_freeN(), packed, FixedSizeBoxPack::w, FixedSizeBoxPack::x, and FixedSizeBoxPack::y.