From deacb3d6b816afe9f86f51b00043821829fb550e Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sun, 18 Feb 2018 21:27:33 +1100 Subject: Cleanup: add 2d suffix to BLI files Some of these API's can have 3D versions, explicitly name them 2D. --- source/blender/blenkernel/intern/editderivedmesh.c | 2 +- source/blender/blenkernel/intern/mesh_evaluate.c | 2 +- source/blender/blenkernel/intern/mesh_remap.c | 2 +- .../blenkernel/intern/particle_distribute.c | 2 +- source/blender/blenkernel/intern/particle_system.c | 2 +- source/blender/blenlib/BLI_boxpack2d.h | 53 -- source/blender/blenlib/BLI_boxpack_2d.h | 53 ++ source/blender/blenlib/BLI_convexhull2d.h | 34 - source/blender/blenlib/BLI_convexhull_2d.h | 34 + source/blender/blenlib/BLI_dial.h | 59 -- source/blender/blenlib/BLI_dial_2d.h | 59 ++ source/blender/blenlib/BLI_jitter.h | 40 - source/blender/blenlib/BLI_jitter_2d.h | 40 + source/blender/blenlib/BLI_lasso.h | 41 - source/blender/blenlib/BLI_lasso_2d.h | 41 + source/blender/blenlib/BLI_polyfill2d.h | 43 - source/blender/blenlib/BLI_polyfill2d_beautify.h | 45 - source/blender/blenlib/BLI_polyfill_2d.h | 43 + source/blender/blenlib/BLI_polyfill_2d_beautify.h | 45 + source/blender/blenlib/BLI_voronoi.h | 70 -- source/blender/blenlib/BLI_voronoi_2d.h | 70 ++ source/blender/blenlib/CMakeLists.txt | 32 +- source/blender/blenlib/intern/BLI_dial.c | 100 --- source/blender/blenlib/intern/BLI_dial_2d.c | 104 +++ source/blender/blenlib/intern/boxpack2d.c | 674 -------------- source/blender/blenlib/intern/boxpack_2d.c | 674 ++++++++++++++ source/blender/blenlib/intern/convexhull2d.c | 331 ------- source/blender/blenlib/intern/convexhull_2d.c | 331 +++++++ source/blender/blenlib/intern/jitter.c | 186 ---- source/blender/blenlib/intern/jitter_2d.c | 186 ++++ source/blender/blenlib/intern/lasso.c | 93 -- source/blender/blenlib/intern/lasso_2d.c | 93 ++ source/blender/blenlib/intern/polyfill2d.c | 969 --------------------- .../blender/blenlib/intern/polyfill2d_beautify.c | 439 ---------- source/blender/blenlib/intern/polyfill_2d.c | 969 +++++++++++++++++++++ .../blender/blenlib/intern/polyfill_2d_beautify.c | 439 ++++++++++ source/blender/blenlib/intern/voronoi.c | 832 ------------------ source/blender/blenlib/intern/voronoi_2d.c | 830 ++++++++++++++++++ source/blender/bmesh/intern/bmesh_polygon.c | 4 +- .../blender/bmesh/operators/bmo_connect_concave.c | 4 +- source/blender/bmesh/tools/bmesh_beautify.c | 2 +- .../blender/bmesh/tools/bmesh_decimate_collapse.c | 4 +- source/blender/bmesh/tools/bmesh_triangulate.c | 4 +- .../operations/COM_KeyingScreenOperation.h | 2 +- .../operations/COM_PlaneDistortCommonOperation.cpp | 2 +- source/blender/editors/animation/keyframes_edit.c | 2 +- source/blender/editors/gpencil/drawgpencil.c | 2 +- source/blender/editors/gpencil/gpencil_select.c | 2 +- source/blender/editors/mask/mask_select.c | 2 +- source/blender/editors/physics/particle_edit.c | 2 +- source/blender/editors/sculpt_paint/paint_mask.c | 2 +- source/blender/editors/sculpt_paint/sculpt.c | 2 +- .../blender/editors/space_action/action_select.c | 2 +- .../blender/editors/space_clip/tracking_select.c | 2 +- source/blender/editors/space_graph/graph_select.c | 2 +- source/blender/editors/space_node/node_select.c | 2 +- source/blender/editors/space_view3d/view3d_draw.c | 2 +- .../blender/editors/space_view3d/view3d_select.c | 2 +- source/blender/editors/uvedit/uvedit_ops.c | 2 +- .../blender/editors/uvedit/uvedit_parametrizer.c | 4 +- .../blender/python/mathutils/mathutils_bvhtree.c | 2 +- .../blender/python/mathutils/mathutils_geometry.c | 4 +- source/blender/render/intern/source/initrender.c | 2 +- source/blender/render/intern/source/shadbuf.c | 2 +- source/blender/render/intern/source/zbuf.c | 2 +- source/blender/windowmanager/intern/wm_gesture.c | 2 +- source/blender/windowmanager/intern/wm_operators.c | 2 +- 67 files changed, 4067 insertions(+), 4065 deletions(-) delete mode 100644 source/blender/blenlib/BLI_boxpack2d.h create mode 100644 source/blender/blenlib/BLI_boxpack_2d.h delete mode 100644 source/blender/blenlib/BLI_convexhull2d.h create mode 100644 source/blender/blenlib/BLI_convexhull_2d.h delete mode 100644 source/blender/blenlib/BLI_dial.h create mode 100644 source/blender/blenlib/BLI_dial_2d.h delete mode 100644 source/blender/blenlib/BLI_jitter.h create mode 100644 source/blender/blenlib/BLI_jitter_2d.h delete mode 100644 source/blender/blenlib/BLI_lasso.h create mode 100644 source/blender/blenlib/BLI_lasso_2d.h delete mode 100644 source/blender/blenlib/BLI_polyfill2d.h delete mode 100644 source/blender/blenlib/BLI_polyfill2d_beautify.h create mode 100644 source/blender/blenlib/BLI_polyfill_2d.h create mode 100644 source/blender/blenlib/BLI_polyfill_2d_beautify.h delete mode 100644 source/blender/blenlib/BLI_voronoi.h create mode 100644 source/blender/blenlib/BLI_voronoi_2d.h delete mode 100644 source/blender/blenlib/intern/BLI_dial.c create mode 100644 source/blender/blenlib/intern/BLI_dial_2d.c delete mode 100644 source/blender/blenlib/intern/boxpack2d.c create mode 100644 source/blender/blenlib/intern/boxpack_2d.c delete mode 100644 source/blender/blenlib/intern/convexhull2d.c create mode 100644 source/blender/blenlib/intern/convexhull_2d.c delete mode 100644 source/blender/blenlib/intern/jitter.c create mode 100644 source/blender/blenlib/intern/jitter_2d.c delete mode 100644 source/blender/blenlib/intern/lasso.c create mode 100644 source/blender/blenlib/intern/lasso_2d.c delete mode 100644 source/blender/blenlib/intern/polyfill2d.c delete mode 100644 source/blender/blenlib/intern/polyfill2d_beautify.c create mode 100644 source/blender/blenlib/intern/polyfill_2d.c create mode 100644 source/blender/blenlib/intern/polyfill_2d_beautify.c delete mode 100644 source/blender/blenlib/intern/voronoi.c create mode 100644 source/blender/blenlib/intern/voronoi_2d.c (limited to 'source/blender') diff --git a/source/blender/blenkernel/intern/editderivedmesh.c b/source/blender/blenkernel/intern/editderivedmesh.c index be8fcaa6863..ffa7fdc3ec9 100644 --- a/source/blender/blenkernel/intern/editderivedmesh.c +++ b/source/blender/blenkernel/intern/editderivedmesh.c @@ -44,7 +44,7 @@ #include "atomic_ops.h" #include "BLI_math.h" -#include "BLI_jitter.h" +#include "BLI_jitter_2d.h" #include "BLI_bitmap.h" #include "BLI_task.h" diff --git a/source/blender/blenkernel/intern/mesh_evaluate.c b/source/blender/blenkernel/intern/mesh_evaluate.c index b0c09979de9..91331043be4 100644 --- a/source/blender/blenkernel/intern/mesh_evaluate.c +++ b/source/blender/blenkernel/intern/mesh_evaluate.c @@ -43,7 +43,7 @@ #include "BLI_math.h" #include "BLI_edgehash.h" #include "BLI_bitmap.h" -#include "BLI_polyfill2d.h" +#include "BLI_polyfill_2d.h" #include "BLI_linklist.h" #include "BLI_linklist_stack.h" #include "BLI_alloca.h" diff --git a/source/blender/blenkernel/intern/mesh_remap.c b/source/blender/blenkernel/intern/mesh_remap.c index f321c94bf00..0af4dae4506 100644 --- a/source/blender/blenkernel/intern/mesh_remap.c +++ b/source/blender/blenkernel/intern/mesh_remap.c @@ -36,7 +36,7 @@ #include "BLI_bitmap.h" #include "BLI_math.h" #include "BLI_memarena.h" -#include "BLI_polyfill2d.h" +#include "BLI_polyfill_2d.h" #include "BLI_rand.h" #include "BKE_bvhutils.h" diff --git a/source/blender/blenkernel/intern/particle_distribute.c b/source/blender/blenkernel/intern/particle_distribute.c index 9a7980827ad..81a5874ef4c 100644 --- a/source/blender/blenkernel/intern/particle_distribute.c +++ b/source/blender/blenkernel/intern/particle_distribute.c @@ -36,7 +36,7 @@ #include "MEM_guardedalloc.h" #include "BLI_utildefines.h" -#include "BLI_jitter.h" +#include "BLI_jitter_2d.h" #include "BLI_kdtree.h" #include "BLI_math.h" #include "BLI_math_geom.h" diff --git a/source/blender/blenkernel/intern/particle_system.c b/source/blender/blenkernel/intern/particle_system.c index 7851cd5e801..e4dcf6618fa 100644 --- a/source/blender/blenkernel/intern/particle_system.c +++ b/source/blender/blenkernel/intern/particle_system.c @@ -58,7 +58,7 @@ #include "BLI_utildefines.h" #include "BLI_edgehash.h" #include "BLI_rand.h" -#include "BLI_jitter.h" +#include "BLI_jitter_2d.h" #include "BLI_math.h" #include "BLI_blenlib.h" #include "BLI_kdtree.h" diff --git a/source/blender/blenlib/BLI_boxpack2d.h b/source/blender/blenlib/BLI_boxpack2d.h deleted file mode 100644 index b02e3423f88..00000000000 --- a/source/blender/blenlib/BLI_boxpack2d.h +++ /dev/null @@ -1,53 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): Campbell Barton - * - * ***** END GPL LICENSE BLOCK ***** - */ - -#ifndef __BLI_BOXPACK2D_H__ -#define __BLI_BOXPACK2D_H__ - -/** \file BLI_boxpack2d.h - * \ingroup bli - */ - -/* Box Packer */ - -typedef struct BoxPack { - float x; - float y; - float w; - float h; - - /* Verts this box uses - * (BL,TR,TL,BR) / 0,1,2,3 */ - struct BoxVert *v[4]; - - int index; -} BoxPack; - -void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width, float *tot_height); - -#endif - diff --git a/source/blender/blenlib/BLI_boxpack_2d.h b/source/blender/blenlib/BLI_boxpack_2d.h new file mode 100644 index 00000000000..80e89bdb04f --- /dev/null +++ b/source/blender/blenlib/BLI_boxpack_2d.h @@ -0,0 +1,53 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): Campbell Barton + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_BOXPACK_2D_H__ +#define __BLI_BOXPACK_2D_H__ + +/** \file BLI_boxpack_2d.h + * \ingroup bli + */ + +/* Box Packer */ + +typedef struct BoxPack { + float x; + float y; + float w; + float h; + + /* Verts this box uses + * (BL,TR,TL,BR) / 0,1,2,3 */ + struct BoxVert *v[4]; + + int index; +} BoxPack; + +void BLI_box_pack_2d(BoxPack *boxarray, const unsigned int len, float *tot_width, float *tot_height); + +#endif /* __BLI_BOXPACK_2D_H__ */ + diff --git a/source/blender/blenlib/BLI_convexhull2d.h b/source/blender/blenlib/BLI_convexhull2d.h deleted file mode 100644 index 4b82071ede8..00000000000 --- a/source/blender/blenlib/BLI_convexhull2d.h +++ /dev/null @@ -1,34 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -#ifndef __BLI_CONVEXHULL2D_H__ -#define __BLI_CONVEXHULL2D_H__ - -/** \file BLI_convexhull2d.h - * \ingroup bli - */ - -int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points[]); -int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[]); - -float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], unsigned int n); -float BLI_convexhull_aabb_fit_points_2d(const float (*points)[2], unsigned int n); - -#endif /* __BLI_CONVEXHULL2D_H__ */ diff --git a/source/blender/blenlib/BLI_convexhull_2d.h b/source/blender/blenlib/BLI_convexhull_2d.h new file mode 100644 index 00000000000..000d28acdde --- /dev/null +++ b/source/blender/blenlib/BLI_convexhull_2d.h @@ -0,0 +1,34 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_CONVEXHULL_2D_H__ +#define __BLI_CONVEXHULL_2D_H__ + +/** \file BLI_convexhull_2d.h + * \ingroup bli + */ + +int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points[]); +int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[]); + +float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], unsigned int n); +float BLI_convexhull_aabb_fit_points_2d(const float (*points)[2], unsigned int n); + +#endif /* __BLI_CONVEXHULL_2D_H__ */ diff --git a/source/blender/blenlib/BLI_dial.h b/source/blender/blenlib/BLI_dial.h deleted file mode 100644 index 71ab57bb61a..00000000000 --- a/source/blender/blenlib/BLI_dial.h +++ /dev/null @@ -1,59 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -#ifndef __BLI_DIAL_H__ -#define __BLI_DIAL_H__ - -/** \file BLI_dial.h - * \ingroup bli - * - * \note dials act similar to old rotation based phones and output an angle. - * - * They just are initialized with the center of the dial and a threshold value as input. - * - * When the distance of the current position of the dial from the center - * exceeds the threshold, this position is used to calculate the initial direction. - * After that, the angle from the initial direction is calculated based on - * current and previous directions of the digit, and returned to the user. - * - * Usage examples: - * - * \code{.c} - * float start_position[2] = {0.0f, 0.0f}; - * float current_position[2]; - * float threshold = 0.5f; - * float angle; - * Dial *dial; - * - * dial = BLI_dial_initialize(start_position, threshold); - * - * angle = BLI_dial_angle(dial, curent_position); - * - * MEM_freeN(dial); - * \endcode - */ - -typedef struct Dial Dial; - -Dial *BLI_dial_initialize(const float start_position[2], float threshold); - -float BLI_dial_angle(Dial *dial, const float current_position[2]); - -#endif /* __BLI_DIAL_H__ */ diff --git a/source/blender/blenlib/BLI_dial_2d.h b/source/blender/blenlib/BLI_dial_2d.h new file mode 100644 index 00000000000..dbd71a8ad3f --- /dev/null +++ b/source/blender/blenlib/BLI_dial_2d.h @@ -0,0 +1,59 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_DIAL_2D_H__ +#define __BLI_DIAL_2D_H__ + +/** \file BLI_dial_2d.h + * \ingroup bli + * + * \note dials act similar to old rotation based phones and output an angle. + * + * They just are initialized with the center of the dial and a threshold value as input. + * + * When the distance of the current position of the dial from the center + * exceeds the threshold, this position is used to calculate the initial direction. + * After that, the angle from the initial direction is calculated based on + * current and previous directions of the digit, and returned to the user. + * + * Usage examples: + * + * \code{.c} + * float start_position[2] = {0.0f, 0.0f}; + * float current_position[2]; + * float threshold = 0.5f; + * float angle; + * Dial *dial; + * + * dial = BLI_dial_initialize(start_position, threshold); + * + * angle = BLI_dial_angle(dial, curent_position); + * + * MEM_freeN(dial); + * \endcode + */ + +typedef struct Dial Dial; + +Dial *BLI_dial_initialize(const float start_position[2], float threshold); + +float BLI_dial_angle(Dial *dial, const float current_position[2]); + +#endif /* __BLI_DIAL_2D_H__ */ diff --git a/source/blender/blenlib/BLI_jitter.h b/source/blender/blenlib/BLI_jitter.h deleted file mode 100644 index 769fb445678..00000000000 --- a/source/blender/blenlib/BLI_jitter.h +++ /dev/null @@ -1,40 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -#ifndef __BLI_JITTER_H__ -#define __BLI_JITTER_H__ - -/** \file BLI_jitter.h - * \ingroup bli - */ - -void BLI_jitter_init(float (*jitarr)[2], int num); -void BLI_jitterate1(float (*jit1)[2], float (*jit2)[2], int num, float radius1); -void BLI_jitterate2(float (*jit1)[2], float (*jit2)[2], int num, float radius2); - -#endif - diff --git a/source/blender/blenlib/BLI_jitter_2d.h b/source/blender/blenlib/BLI_jitter_2d.h new file mode 100644 index 00000000000..e2b1f21800c --- /dev/null +++ b/source/blender/blenlib/BLI_jitter_2d.h @@ -0,0 +1,40 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): none yet. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_JITTER_2D_H__ +#define __BLI_JITTER_2D_H__ + +/** \file BLI_jitter_2d.h + * \ingroup bli + */ + +void BLI_jitter_init(float (*jitarr)[2], int num); +void BLI_jitterate1(float (*jit1)[2], float (*jit2)[2], int num, float radius1); +void BLI_jitterate2(float (*jit1)[2], float (*jit2)[2], int num, float radius2); + +#endif /* __BLI_JITTER_2D_H__ */ + diff --git a/source/blender/blenlib/BLI_lasso.h b/source/blender/blenlib/BLI_lasso.h deleted file mode 100644 index 28f21e5bd85..00000000000 --- a/source/blender/blenlib/BLI_lasso.h +++ /dev/null @@ -1,41 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -#ifndef __BLI_LASSO_H__ -#define __BLI_LASSO_H__ - -/** \file BLI_lasso.h - * \ingroup bli - */ - -struct rcti; - -void BLI_lasso_boundbox(struct rcti *rect, const int mcords[][2], const unsigned int moves); -bool BLI_lasso_is_point_inside(const int mcords[][2], const unsigned int moves, const int sx, const int sy, const int error_value); -bool BLI_lasso_is_edge_inside(const int mcords[][2], const unsigned int moves, int x0, int y0, int x1, int y1, const int error_value); - -#endif diff --git a/source/blender/blenlib/BLI_lasso_2d.h b/source/blender/blenlib/BLI_lasso_2d.h new file mode 100644 index 00000000000..3644224f1d7 --- /dev/null +++ b/source/blender/blenlib/BLI_lasso_2d.h @@ -0,0 +1,41 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): none yet. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_LASSO_2D_H__ +#define __BLI_LASSO_2D_H__ + +/** \file BLI_lasso_2d.h + * \ingroup bli + */ + +struct rcti; + +void BLI_lasso_boundbox(struct rcti *rect, const int mcords[][2], const unsigned int moves); +bool BLI_lasso_is_point_inside(const int mcords[][2], const unsigned int moves, const int sx, const int sy, const int error_value); +bool BLI_lasso_is_edge_inside(const int mcords[][2], const unsigned int moves, int x0, int y0, int x1, int y1, const int error_value); + +#endif /* __BLI_LASSO_2D_H__ */ diff --git a/source/blender/blenlib/BLI_polyfill2d.h b/source/blender/blenlib/BLI_polyfill2d.h deleted file mode 100644 index 798055f9240..00000000000 --- a/source/blender/blenlib/BLI_polyfill2d.h +++ /dev/null @@ -1,43 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -#ifndef __BLI_POLYFILL2D_H__ -#define __BLI_POLYFILL2D_H__ - -struct MemArena; - -void BLI_polyfill_calc_arena( - const float (*coords)[2], - const unsigned int coords_tot, - const int coords_sign, - unsigned int (*r_tris)[3], - - struct MemArena *arena); - -void BLI_polyfill_calc( - const float (*coords)[2], - const unsigned int coords_tot, - const int coords_sign, - unsigned int (*r_tris)[3]); - -/* default size of polyfill arena */ -#define BLI_POLYFILL_ARENA_SIZE MEM_SIZE_OPTIMAL(1 << 14) - -#endif /* __BLI_POLYFILL2D_H__ */ diff --git a/source/blender/blenlib/BLI_polyfill2d_beautify.h b/source/blender/blenlib/BLI_polyfill2d_beautify.h deleted file mode 100644 index 278771e9611..00000000000 --- a/source/blender/blenlib/BLI_polyfill2d_beautify.h +++ /dev/null @@ -1,45 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -#ifndef __BLI_POLYFILL2D_BEAUTIFY_H__ -#define __BLI_POLYFILL2D_BEAUTIFY_H__ - -struct Heap; -struct MemArena; - -void BLI_polyfill_beautify( - const float (*coords)[2], - const unsigned int coords_tot, - unsigned int (*tris)[3], - - /* structs for reuse */ - struct MemArena *arena, struct Heap *eheap); - -float BLI_polyfill_beautify_quad_rotate_calc_ex( - const float v1[2], const float v2[2], const float v3[2], const float v4[2], - const bool lock_degenerate); -#define BLI_polyfill_beautify_quad_rotate_calc(v1, v2, v3, v4) \ - BLI_polyfill_beautify_quad_rotate_calc_ex(v1, v2, v3, v4, false) - - -/* avoid realloc's when creating new structures for polyfill ngons */ -#define BLI_POLYFILL_ALLOC_NGON_RESERVE 64 - -#endif /* __BLI_POLYFILL2D_BEAUTIFY_H__ */ diff --git a/source/blender/blenlib/BLI_polyfill_2d.h b/source/blender/blenlib/BLI_polyfill_2d.h new file mode 100644 index 00000000000..099f08d4663 --- /dev/null +++ b/source/blender/blenlib/BLI_polyfill_2d.h @@ -0,0 +1,43 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_POLYFILL_2D_H__ +#define __BLI_POLYFILL_2D_H__ + +struct MemArena; + +void BLI_polyfill_calc_arena( + const float (*coords)[2], + const unsigned int coords_tot, + const int coords_sign, + unsigned int (*r_tris)[3], + + struct MemArena *arena); + +void BLI_polyfill_calc( + const float (*coords)[2], + const unsigned int coords_tot, + const int coords_sign, + unsigned int (*r_tris)[3]); + +/* default size of polyfill arena */ +#define BLI_POLYFILL_ARENA_SIZE MEM_SIZE_OPTIMAL(1 << 14) + +#endif /* __BLI_POLYFILL_2D_H__ */ diff --git a/source/blender/blenlib/BLI_polyfill_2d_beautify.h b/source/blender/blenlib/BLI_polyfill_2d_beautify.h new file mode 100644 index 00000000000..278771e9611 --- /dev/null +++ b/source/blender/blenlib/BLI_polyfill_2d_beautify.h @@ -0,0 +1,45 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_POLYFILL2D_BEAUTIFY_H__ +#define __BLI_POLYFILL2D_BEAUTIFY_H__ + +struct Heap; +struct MemArena; + +void BLI_polyfill_beautify( + const float (*coords)[2], + const unsigned int coords_tot, + unsigned int (*tris)[3], + + /* structs for reuse */ + struct MemArena *arena, struct Heap *eheap); + +float BLI_polyfill_beautify_quad_rotate_calc_ex( + const float v1[2], const float v2[2], const float v3[2], const float v4[2], + const bool lock_degenerate); +#define BLI_polyfill_beautify_quad_rotate_calc(v1, v2, v3, v4) \ + BLI_polyfill_beautify_quad_rotate_calc_ex(v1, v2, v3, v4, false) + + +/* avoid realloc's when creating new structures for polyfill ngons */ +#define BLI_POLYFILL_ALLOC_NGON_RESERVE 64 + +#endif /* __BLI_POLYFILL2D_BEAUTIFY_H__ */ diff --git a/source/blender/blenlib/BLI_voronoi.h b/source/blender/blenlib/BLI_voronoi.h deleted file mode 100644 index 9d32061bf97..00000000000 --- a/source/blender/blenlib/BLI_voronoi.h +++ /dev/null @@ -1,70 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2012 Blender Foundation. - * All rights reserved. - * - * Contributor(s): Sergey Sharybin - * - * ***** END GPL LICENSE BLOCK ***** - */ - -#ifndef __BLI_VORONOI_H__ -#define __BLI_VORONOI_H__ - -struct ListBase; - -/** \file BLI_voronoi.h - * \ingroup bli - */ - -typedef struct VoronoiSite { - float co[2]; - float color[3]; -} VoronoiSite; - -typedef struct VoronoiEdge { - struct VoronoiEdge *next, *prev; - - float start[2], end[2]; /* start and end points */ - - /* this fields are used during diagram computation only */ - - float direction[2]; /* directional vector, from "start", points to "end", normal of |left, right| */ - - float left[2]; /* point on Voronoi place on the left side of edge */ - float right[2]; /* point on Voronoi place on the right side of edge */ - - float f, g; /* directional coeffitients satisfying equation y = f * x + g (edge lies on this line) */ - - /* some edges consist of two parts, so we add the pointer to another part to connect them at the end of an algorithm */ - struct VoronoiEdge *neighbor; -} VoronoiEdge; - -typedef struct VoronoiTriangulationPoint { - float co[2]; - float color[3]; - int power; -} VoronoiTriangulationPoint; - -void BLI_voronoi_compute(const VoronoiSite *sites, int sites_total, int width, int height, struct ListBase *edges); - -void BLI_voronoi_triangulate(const VoronoiSite *sites, int sites_total, struct ListBase *edges, int width, int height, - VoronoiTriangulationPoint **triangulated_points_r, int *triangulated_points_total_r, - int (**triangles_r)[3], int *triangles_total_r); - -#endif /* __BLI_VORONOI_H__ */ diff --git a/source/blender/blenlib/BLI_voronoi_2d.h b/source/blender/blenlib/BLI_voronoi_2d.h new file mode 100644 index 00000000000..51d1d5aa88e --- /dev/null +++ b/source/blender/blenlib/BLI_voronoi_2d.h @@ -0,0 +1,70 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2012 Blender Foundation. + * All rights reserved. + * + * Contributor(s): Sergey Sharybin + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_VORONOI_H__ +#define __BLI_VORONOI_H__ + +struct ListBase; + +/** \file BLI_voronoi_2d.h + * \ingroup bli + */ + +typedef struct VoronoiSite { + float co[2]; + float color[3]; +} VoronoiSite; + +typedef struct VoronoiEdge { + struct VoronoiEdge *next, *prev; + + float start[2], end[2]; /* start and end points */ + + /* this fields are used during diagram computation only */ + + float direction[2]; /* directional vector, from "start", points to "end", normal of |left, right| */ + + float left[2]; /* point on Voronoi place on the left side of edge */ + float right[2]; /* point on Voronoi place on the right side of edge */ + + float f, g; /* directional coeffitients satisfying equation y = f * x + g (edge lies on this line) */ + + /* some edges consist of two parts, so we add the pointer to another part to connect them at the end of an algorithm */ + struct VoronoiEdge *neighbor; +} VoronoiEdge; + +typedef struct VoronoiTriangulationPoint { + float co[2]; + float color[3]; + int power; +} VoronoiTriangulationPoint; + +void BLI_voronoi_compute(const VoronoiSite *sites, int sites_total, int width, int height, struct ListBase *edges); + +void BLI_voronoi_triangulate(const VoronoiSite *sites, int sites_total, struct ListBase *edges, int width, int height, + VoronoiTriangulationPoint **triangulated_points_r, int *triangulated_points_total_r, + int (**triangles_r)[3], int *triangles_total_r); + +#endif /* __BLI_VORONOI_H__ */ diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 61a1241cd8f..edfa2239d0a 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -41,7 +41,7 @@ set(INC_SYS set(SRC intern/BLI_args.c intern/BLI_array.c - intern/BLI_dial.c + intern/BLI_dial_2d.c intern/BLI_dynstr.c intern/BLI_filelist.c intern/BLI_ghash.c @@ -57,10 +57,10 @@ set(SRC intern/array_utils.c intern/astar.c intern/bitmap_draw_2d.c - intern/boxpack2d.c + intern/boxpack_2d.c intern/buffer.c intern/callbacks.c - intern/convexhull2d.c + intern/convexhull_2d.c intern/dynlib.c intern/easing.c intern/edgehash.c @@ -72,8 +72,8 @@ set(SRC intern/gsqueue.c intern/hash_md5.c intern/hash_mm2a.c - intern/jitter.c - intern/lasso.c + intern/jitter_2d.c + intern/lasso_2d.c intern/list_sort_impl.h intern/listbase.c intern/math_base.c @@ -94,8 +94,8 @@ set(SRC intern/memory_utils.c intern/noise.c intern/path_util.c - intern/polyfill2d.c - intern/polyfill2d_beautify.c + intern/polyfill_2d.c + intern/polyfill_2d_beautify.c intern/quadric.c intern/rand.c intern/rct.c @@ -116,7 +116,7 @@ set(SRC intern/time.c intern/timecode.c intern/uvproject.c - intern/voronoi.c + intern/voronoi_2d.c intern/voxel.c intern/winstuff.c intern/winstuff_dir.c @@ -131,14 +131,14 @@ set(SRC BLI_bitmap.h BLI_bitmap_draw_2d.h BLI_blenlib.h - BLI_boxpack2d.h + BLI_boxpack_2d.h BLI_buffer.h BLI_callbacks.h BLI_compiler_attrs.h BLI_compiler_compat.h BLI_compiler_typecheck.h - BLI_convexhull2d.h - BLI_dial.h + BLI_convexhull_2d.h + BLI_dial_2d.h BLI_dlrbTree.h BLI_dynlib.h BLI_dynstr.h @@ -156,10 +156,10 @@ set(SRC BLI_hash_md5.h BLI_hash_mm2a.h BLI_heap.h - BLI_jitter.h + BLI_jitter_2d.h BLI_kdopbvh.h BLI_kdtree.h - BLI_lasso.h + BLI_lasso_2d.h BLI_link_utils.h BLI_linklist.h BLI_linklist_stack.h @@ -182,8 +182,8 @@ set(SRC BLI_mempool.h BLI_noise.h BLI_path_util.h - BLI_polyfill2d.h - BLI_polyfill2d_beautify.h + BLI_polyfill_2d.h + BLI_polyfill_2d_beautify.h BLI_quadric.h BLI_rand.h BLI_rect.h @@ -208,7 +208,7 @@ set(SRC BLI_utildefines_variadic.h BLI_uvproject.h BLI_vfontdata.h - BLI_voronoi.h + BLI_voronoi_2d.h BLI_voxel.h BLI_winstuff.h PIL_time.h diff --git a/source/blender/blenlib/intern/BLI_dial.c b/source/blender/blenlib/intern/BLI_dial.c deleted file mode 100644 index 89f18fa10b4..00000000000 --- a/source/blender/blenlib/intern/BLI_dial.c +++ /dev/null @@ -1,100 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -#include "BLI_dial.h" -#include "BLI_math.h" - -#include "MEM_guardedalloc.h" - -struct Dial { - /* center of the dial */ - float center[2]; - - /* threshold of the dial. Distance of current position has to be greater - * than the threshold to be used in any calculations */ - float threshold_squared; - - /* the direction of the first dial position exceeding the threshold. This - * is later used as the basis against which rotation angle is calculated */ - float initial_direction[2]; - - /* cache the last angle to detect rotations bigger than -/+ PI */ - float last_angle; - - /* number of full rotations */ - int rotations; - - /* has initial_direction been initialized */ - bool initialized; -}; - - -Dial *BLI_dial_initialize(const float start_position[2], float threshold) -{ - Dial *dial = MEM_callocN(sizeof(Dial), "dial"); - - copy_v2_v2(dial->center, start_position); - dial->threshold_squared = threshold * threshold; - - return dial; -} - -float BLI_dial_angle(Dial *dial, const float current_position[2]) -{ - float current_direction[2]; - - sub_v2_v2v2(current_direction, current_position, dial->center); - - /* only update when we have enough precision, by having the mouse adequately away from center */ - if (len_squared_v2(current_direction) > dial->threshold_squared) { - float angle; - float cosval, sinval; - - normalize_v2(current_direction); - - if (!dial->initialized) { - copy_v2_v2(dial->initial_direction, current_direction); - dial->initialized = true; - } - - /* calculate mouse angle between initial and final mouse position */ - cosval = dot_v2v2(current_direction, dial->initial_direction); - sinval = cross_v2v2(current_direction, dial->initial_direction); - - /* clamp to avoid nans in acos */ - angle = atan2f(sinval, cosval); - - /* change of sign, we passed the 180 degree threshold. This means we need to add a turn. - * to distinguish between transition from 0 to -1 and -PI to +PI, use comparison with PI/2 */ - if ((angle * dial->last_angle < 0.0f) && - (fabsf(dial->last_angle) > (float)M_PI_2)) - { - if (dial->last_angle < 0.0f) - dial->rotations--; - else - dial->rotations++; - } - dial->last_angle = angle; - - return angle + 2.0f * (float)M_PI * dial->rotations; - } - - return dial->last_angle; -} diff --git a/source/blender/blenlib/intern/BLI_dial_2d.c b/source/blender/blenlib/intern/BLI_dial_2d.c new file mode 100644 index 00000000000..d31367c5e87 --- /dev/null +++ b/source/blender/blenlib/intern/BLI_dial_2d.c @@ -0,0 +1,104 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenlib/intern/BLI_dial_2d.c + * \ingroup bli + */ + +#include "BLI_dial_2d.h" +#include "BLI_math.h" + +#include "MEM_guardedalloc.h" + +struct Dial { + /* center of the dial */ + float center[2]; + + /* threshold of the dial. Distance of current position has to be greater + * than the threshold to be used in any calculations */ + float threshold_squared; + + /* the direction of the first dial position exceeding the threshold. This + * is later used as the basis against which rotation angle is calculated */ + float initial_direction[2]; + + /* cache the last angle to detect rotations bigger than -/+ PI */ + float last_angle; + + /* number of full rotations */ + int rotations; + + /* has initial_direction been initialized */ + bool initialized; +}; + + +Dial *BLI_dial_initialize(const float start_position[2], float threshold) +{ + Dial *dial = MEM_callocN(sizeof(Dial), "dial"); + + copy_v2_v2(dial->center, start_position); + dial->threshold_squared = threshold * threshold; + + return dial; +} + +float BLI_dial_angle(Dial *dial, const float current_position[2]) +{ + float current_direction[2]; + + sub_v2_v2v2(current_direction, current_position, dial->center); + + /* only update when we have enough precision, by having the mouse adequately away from center */ + if (len_squared_v2(current_direction) > dial->threshold_squared) { + float angle; + float cosval, sinval; + + normalize_v2(current_direction); + + if (!dial->initialized) { + copy_v2_v2(dial->initial_direction, current_direction); + dial->initialized = true; + } + + /* calculate mouse angle between initial and final mouse position */ + cosval = dot_v2v2(current_direction, dial->initial_direction); + sinval = cross_v2v2(current_direction, dial->initial_direction); + + /* clamp to avoid nans in acos */ + angle = atan2f(sinval, cosval); + + /* change of sign, we passed the 180 degree threshold. This means we need to add a turn. + * to distinguish between transition from 0 to -1 and -PI to +PI, use comparison with PI/2 */ + if ((angle * dial->last_angle < 0.0f) && + (fabsf(dial->last_angle) > (float)M_PI_2)) + { + if (dial->last_angle < 0.0f) + dial->rotations--; + else + dial->rotations++; + } + dial->last_angle = angle; + + return angle + 2.0f * (float)M_PI * dial->rotations; + } + + return dial->last_angle; +} diff --git a/source/blender/blenlib/intern/boxpack2d.c b/source/blender/blenlib/intern/boxpack2d.c deleted file mode 100644 index ff17d2ac28b..00000000000 --- a/source/blender/blenlib/intern/boxpack2d.c +++ /dev/null @@ -1,674 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * Contributor(s): Campbell Barton - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file blender/blenlib/intern/boxpack2d.c - * \ingroup bli - */ - -#include /* for qsort */ -#include /* for fabsf */ - -#include "MEM_guardedalloc.h" - -#include "BLI_utildefines.h" -#include "BLI_boxpack2d.h" /* own include */ - -#include "BLI_sort.h" /* qsort_r */ -#define qsort_r BLI_qsort_r - -#include "BLI_strict_flags.h" - -#ifdef __GNUC__ -# pragma GCC diagnostic error "-Wpadded" -#endif - -/* de-duplicate as we pack */ -#define USE_MERGE -/* use strip-free */ -#define USE_FREE_STRIP -/* slight bias, needed when packing many boxes the _exact_ same size */ -#define USE_PACK_BIAS - - -/* BoxPacker for backing 2D rectangles into a square - * - * The defined Below are for internal use only */ -typedef struct BoxVert { - float x; - float y; - - int free : 8; /* vert status */ - uint used : 1; - uint _pad : 23; - uint index; - - struct BoxPack *trb; /* top right box */ - struct BoxPack *blb; /* bottom left box */ - struct BoxPack *brb; /* bottom right box */ - struct BoxPack *tlb; /* top left box */ - - /* Store last intersecting boxes here - * speedup intersection testing */ - struct BoxPack *isect_cache[4]; - -#ifdef USE_PACK_BIAS - float bias; - int _pad2; -#endif -} BoxVert; - -#ifdef __GNUC__ -# pragma GCC diagnostic ignored "-Wpadded" -#endif - -/* free vert flags */ -#define EPSILON 0.0000001f -#define EPSILON_MERGE 0.00001f -#ifdef USE_PACK_BIAS -# define EPSILON_BIAS 0.000001f -#endif -#define BLF 1 -#define TRF 2 -#define TLF 4 -#define BRF 8 -#define CORNERFLAGS (BLF | TRF | TLF | BRF) - -BLI_INLINE int quad_flag(uint q) -{ - BLI_assert(q < 4); - return (1 << q); -} - -#define BL 0 -#define TR 1 -#define TL 2 -#define BR 3 - -/** \name Box Accessor Functions - * \{ */ - -static float box_xmin_get(const BoxPack *box) -{ - return box->v[BL]->x; -} - -static float box_xmax_get(const BoxPack *box) -{ - return box->v[TR]->x; -} - -static float box_ymin_get(const BoxPack *box) -{ - return box->v[BL]->y; -} - -static float box_ymax_get(const BoxPack *box) -{ - return box->v[TR]->y; -} -/** \} */ - - -/** \name Box Placement - * \{ */ - -BLI_INLINE void box_v34x_update(BoxPack *box) -{ - box->v[TL]->x = box->v[BL]->x; - box->v[BR]->x = box->v[TR]->x; -} - -BLI_INLINE void box_v34y_update(BoxPack *box) -{ - box->v[TL]->y = box->v[TR]->y; - box->v[BR]->y = box->v[BL]->y; -} - -static void box_xmin_set(BoxPack *box, const float f) -{ - box->v[TR]->x = f + box->w; - box->v[BL]->x = f; - box_v34x_update(box); -} - -static void box_xmax_set(BoxPack *box, const float f) -{ - box->v[BL]->x = f - box->w; - box->v[TR]->x = f; - box_v34x_update(box); -} - -static void box_ymin_set(BoxPack *box, const float f) -{ - box->v[TR]->y = f + box->h; - box->v[BL]->y = f; - box_v34y_update(box); -} - -static void box_ymax_set(BoxPack *box, const float f) -{ - box->v[BL]->y = f - box->h; - box->v[TR]->y = f; - box_v34y_update(box); -} -/** \} */ - - -/** \name Box Utils - * \{ */ - -static float box_area(const BoxPack *box) -{ - return box->w * box->h; -} - -static bool box_isect(const BoxPack *box_a, const BoxPack *box_b) -{ - return !(box_xmin_get(box_a) + EPSILON >= box_xmax_get(box_b) || - box_ymin_get(box_a) + EPSILON >= box_ymax_get(box_b) || - box_xmax_get(box_a) - EPSILON <= box_xmin_get(box_b) || - box_ymax_get(box_a) - EPSILON <= box_ymin_get(box_b)); -} - -/** \} */ - - -/* compiler should inline */ -static float max_ff(const float a, const float b) { return b > a ? b : a; } - -#ifdef USE_PACK_BIAS -/* set when used is enabled */ -static void vert_bias_update(BoxVert *v) -{ - BLI_assert(v->used); - v->bias = (v->x * v->y) * EPSILON_BIAS; -} -#endif - -#if 0 -#define BOXDEBUG(b) \ - printf("\tBox Debug i %i, w:%.3f h:%.3f x:%.3f y:%.3f\n", \ - b->index, b->w, b->h, b->x, b->y) -#endif - -/** \name Box/Vert Sorting - * \{ */ - -/* qsort function - sort largest to smallest */ -static int box_areasort(const void *p1, const void *p2) -{ - const BoxPack *b1 = p1, *b2 = p2; - const float a1 = box_area(b1); - const float a2 = box_area(b2); - - if (a1 < a2) return 1; - else if (a1 > a2) return -1; - return 0; -} - -/* qsort vertex sorting function - * sorts from lower left to top right It uses the current box's width and height - * as offsets when sorting, this has the result of not placing boxes outside - * the bounds of the existing backed area where possible - */ -struct VertSortContext { - BoxVert *vertarray; - float box_width, box_height; -}; - -static int vertex_sort(const void *p1, const void *p2, void *vs_ctx_p) -{ - const struct VertSortContext *vs_ctx = vs_ctx_p; - const BoxVert *v1, *v2; - float a1, a2; - - v1 = &vs_ctx->vertarray[*((const uint *)p1)]; - v2 = &vs_ctx->vertarray[*((const uint *)p2)]; - -#ifdef USE_FREE_STRIP - /* push free verts to the end so we can strip */ - if (UNLIKELY(v1->free == 0 && v2->free == 0)) return 0; - else if (UNLIKELY(v1->free == 0)) return 1; - else if (UNLIKELY(v2->free == 0)) return -1; -#endif - - a1 = max_ff(v1->x + vs_ctx->box_width, v1->y + vs_ctx->box_height); - a2 = max_ff(v2->x + vs_ctx->box_width, v2->y + vs_ctx->box_height); - -#ifdef USE_PACK_BIAS - a1 += v1->bias; - a2 += v2->bias; -#endif - - /* sort largest to smallest */ - if (a1 > a2) return 1; - else if (a1 < a2) return -1; - return 0; -} -/** \} */ - -/** - * Main boxpacking 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) - * - * \param boxarray: 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. - * \param len: the number of boxes in the array. - * \param r_tot_x, r_tot_y: set so you can normalize the data. - * */ -void BLI_box_pack_2d(BoxPack *boxarray, const uint len, float *r_tot_x, float *r_tot_y) -{ - uint box_index, verts_pack_len, i, j, k; - uint *vertex_pack_indices; /* an array of indices used for sorting verts */ - bool isect; - float tot_x = 0.0f, tot_y = 0.0f; - - BoxPack *box, *box_test; /*current box and another for intersection tests*/ - BoxVert *vert; /* the current vert */ - - struct VertSortContext vs_ctx; - - if (!len) { - *r_tot_x = tot_x; - *r_tot_y = tot_y; - return; - } - - /* Sort boxes, biggest first */ - qsort(boxarray, (size_t)len, sizeof(BoxPack), box_areasort); - - /* add verts to the boxes, these are only used internally */ - vert = MEM_mallocN((size_t)len * 4 * sizeof(BoxVert), "BoxPack Verts"); - vertex_pack_indices = MEM_mallocN((size_t)len * 3 * sizeof(int), "BoxPack Indices"); - - vs_ctx.vertarray = vert; - - for (box = boxarray, box_index = 0, i = 0; box_index < len; box_index++, box++) { - - vert->blb = vert->brb = vert->tlb = - vert->isect_cache[0] = vert->isect_cache[1] = - vert->isect_cache[2] = vert->isect_cache[3] = NULL; - vert->free = CORNERFLAGS & ~TRF; - vert->trb = box; - vert->used = false; - vert->index = i++; - box->v[BL] = vert++; - - vert->trb = vert->brb = vert->tlb = - vert->isect_cache[0] = vert->isect_cache[1] = - vert->isect_cache[2] = vert->isect_cache[3] = NULL; - vert->free = CORNERFLAGS & ~BLF; - vert->blb = box; - vert->used = false; - vert->index = i++; - box->v[TR] = vert++; - - vert->trb = vert->blb = vert->tlb = - vert->isect_cache[0] = vert->isect_cache[1] = - vert->isect_cache[2] = vert->isect_cache[3] = NULL; - vert->free = CORNERFLAGS & ~BRF; - vert->brb = box; - vert->used = false; - vert->index = i++; - box->v[TL] = vert++; - - vert->trb = vert->blb = vert->brb = - vert->isect_cache[0] = vert->isect_cache[1] = - vert->isect_cache[2] = vert->isect_cache[3] = NULL; - vert->free = CORNERFLAGS & ~TLF; - vert->tlb = box; - vert->used = false; - vert->index = i++; - box->v[BR] = vert++; - } - vert = NULL; - - /* Pack the First box! - * then enter the main box-packing loop */ - - box = boxarray; /* get the first box */ - /* First time, no boxes packed */ - box->v[BL]->free = 0; /* Can't use any if these */ - box->v[BR]->free &= ~(BLF | BRF); - box->v[TL]->free &= ~(BLF | TLF); - - tot_x = box->w; - tot_y = box->h; - - /* This sets all the vertex locations */ - box_xmin_set(box, 0.0f); - box_ymin_set(box, 0.0f); - box->x = box->y = 0.0f; - - for (i = 0; i < 4; i++) { - box->v[i]->used = true; -#ifdef USE_PACK_BIAS - vert_bias_update(box->v[i]); -#endif - } - - for (i = 0; i < 3; i++) - vertex_pack_indices[i] = box->v[i + 1]->index; - verts_pack_len = 3; - box++; /* next box, needed for the loop below */ - /* ...done packing the first box */ - - /* Main boxpacking loop */ - for (box_index = 1; box_index < len; box_index++, box++) { - - /* These floats are used for sorting re-sorting */ - vs_ctx.box_width = box->w; - vs_ctx.box_height = box->h; - - qsort_r(vertex_pack_indices, (size_t)verts_pack_len, sizeof(int), vertex_sort, &vs_ctx); - -#ifdef USE_FREE_STRIP - /* strip free vertices */ - i = verts_pack_len - 1; - while ((i != 0) && vs_ctx.vertarray[vertex_pack_indices[i]].free == 0) { - i--; - } - verts_pack_len = i + 1; -#endif - - /* Pack the box in with the others */ - /* sort the verts */ - isect = true; - - for (i = 0; i < verts_pack_len && isect; i++) { - vert = &vs_ctx.vertarray[vertex_pack_indices[i]]; - /* printf("\ttesting vert %i %i %i %f %f\n", i, - * vert->free, verts_pack_len, vert->x, vert->y); */ - - /* This vert has a free quadrant - * Test if we can place the box here - * vert->free & quad_flags[j] - Checks - * */ - - for (j = 0; (j < 4) && isect; j++) { - if (vert->free & quad_flag(j)) { - switch (j) { - case BL: - box_xmax_set(box, vert->x); - box_ymax_set(box, vert->y); - break; - case TR: - box_xmin_set(box, vert->x); - box_ymin_set(box, vert->y); - break; - case TL: - box_xmax_set(box, vert->x); - box_ymin_set(box, vert->y); - break; - case BR: - box_xmin_set(box, vert->x); - box_ymax_set(box, vert->y); - break; - } - - /* Now we need to check that the box intersects - * with any other boxes - * Assume no intersection... */ - isect = false; - - if ( /* Constrain boxes to positive X/Y values */ - box_xmin_get(box) < 0.0f || box_ymin_get(box) < 0.0f || - /* check for last intersected */ - (vert->isect_cache[j] && - box_isect(box, vert->isect_cache[j]))) - { - /* Here we check that the last intersected - * box will intersect with this one using - * isect_cache that can store a pointer to a - * box for each quadrant - * big speedup */ - isect = true; - } - else { - /* do a full search for colliding box - * this is really slow, some spatially divided - * data-structure would be better */ - for (box_test = boxarray; box_test != box; box_test++) { - if (box_isect(box, box_test)) { - /* Store the last intersecting here as cache - * for faster checking next time around */ - vert->isect_cache[j] = box_test; - isect = true; - break; - } - } - } - - if (!isect) { - - /* maintain the total width and height */ - tot_x = max_ff(box_xmax_get(box), tot_x); - tot_y = max_ff(box_ymax_get(box), tot_y); - - /* Place the box */ - vert->free &= (signed char)(~quad_flag(j)); - - switch (j) { - case TR: - box->v[BL] = vert; - vert->trb = box; - break; - case TL: - box->v[BR] = vert; - vert->tlb = box; - break; - case BR: - box->v[TL] = vert; - vert->brb = box; - break; - case BL: - box->v[TR] = vert; - vert->blb = box; - break; - } - - /* Mask free flags for verts that are - * on the bottom or side so we don't get - * boxes outside the given rectangle ares - * - * We can do an else/if here because only the first - * box can be at the very bottom left corner */ - if (box_xmin_get(box) <= 0) { - box->v[TL]->free &= ~(TLF | BLF); - box->v[BL]->free &= ~(TLF | BLF); - } - else if (box_ymin_get(box) <= 0) { - box->v[BL]->free &= ~(BRF | BLF); - box->v[BR]->free &= ~(BRF | BLF); - } - - /* The following block of code does a logical - * check with 2 adjacent boxes, its possible to - * flag verts on one or both of the boxes - * as being used by checking the width or - * height of both boxes */ - if (vert->tlb && vert->trb && (box == vert->tlb || box == vert->trb)) { - if (UNLIKELY(fabsf(vert->tlb->h - vert->trb->h) < EPSILON_MERGE)) { -#ifdef USE_MERGE -# define A (vert->trb->v[TL]) -# define B (vert->tlb->v[TR]) -# define MASK (BLF | BRF) - BLI_assert(A->used != B->used); - if (A->used) { - A->free &= B->free & ~MASK; - B = A; - } - else { - B->free &= A->free & ~MASK; - A = B; - } - BLI_assert((A->free & MASK) == 0); -# undef A -# undef B -# undef MASK -#else - vert->tlb->v[TR]->free &= ~BLF; - vert->trb->v[TL]->free &= ~BRF; -#endif - } - else if (vert->tlb->h > vert->trb->h) { - vert->trb->v[TL]->free &= ~(TLF | BLF); - } - else /* if (vert->tlb->h < vert->trb->h) */ { - vert->tlb->v[TR]->free &= ~(TRF | BRF); - } - } - else if (vert->blb && vert->brb && (box == vert->blb || box == vert->brb)) { - if (UNLIKELY(fabsf(vert->blb->h - vert->brb->h) < EPSILON_MERGE)) { -#ifdef USE_MERGE -# define A (vert->blb->v[BR]) -# define B (vert->brb->v[BL]) -# define MASK (TRF | TLF) - BLI_assert(A->used != B->used); - if (A->used) { - A->free &= B->free & ~MASK; - B = A; - } - else { - B->free &= A->free & ~MASK; - A = B; - } - BLI_assert((A->free & MASK) == 0); -# undef A -# undef B -# undef MASK -#else - vert->blb->v[BR]->free &= ~TRF; - vert->brb->v[BL]->free &= ~TLF; -#endif - } - else if (vert->blb->h > vert->brb->h) { - vert->brb->v[BL]->free &= ~(TLF | BLF); - } - else /* if (vert->blb->h < vert->brb->h) */ { - vert->blb->v[BR]->free &= ~(TRF | BRF); - } - } - /* Horizontal */ - if (vert->tlb && vert->blb && (box == vert->tlb || box == vert->blb)) { - if (UNLIKELY(fabsf(vert->tlb->w - vert->blb->w) < EPSILON_MERGE)) { -#ifdef USE_MERGE -# define A (vert->blb->v[TL]) -# define B (vert->tlb->v[BL]) -# define MASK (TRF | BRF) - BLI_assert(A->used != B->used); - if (A->used) { - A->free &= B->free & ~MASK; - B = A; - } - else { - B->free &= A->free & ~MASK; - A = B; - } - BLI_assert((A->free & MASK) == 0); -# undef A -# undef B -# undef MASK -#else - vert->blb->v[TL]->free &= ~TRF; - vert->tlb->v[BL]->free &= ~BRF; -#endif - } - else if (vert->tlb->w > vert->blb->w) { - vert->blb->v[TL]->free &= ~(TLF | TRF); - } - else /* if (vert->tlb->w < vert->blb->w) */ { - vert->tlb->v[BL]->free &= ~(BLF | BRF); - } - } - else if (vert->trb && vert->brb && (box == vert->trb || box == vert->brb)) { - if (UNLIKELY(fabsf(vert->trb->w - vert->brb->w) < EPSILON_MERGE)) { - -#ifdef USE_MERGE -# define A (vert->brb->v[TR]) -# define B (vert->trb->v[BR]) -# define MASK (TLF | BLF) - BLI_assert(A->used != B->used); - if (A->used) { - A->free &= B->free & ~MASK; - B = A; - } - else { - B->free &= A->free & ~MASK; - A = B; - } - BLI_assert((A->free & MASK) == 0); -# undef A -# undef B -# undef MASK -#else - vert->brb->v[TR]->free &= ~TLF; - vert->trb->v[BR]->free &= ~BLF; -#endif - } - else if (vert->trb->w > vert->brb->w) { - vert->brb->v[TR]->free &= ~(TLF | TRF); - } - else /* if (vert->trb->w < vert->brb->w) */ { - vert->trb->v[BR]->free &= ~(BLF | BRF); - } - } - /* End logical check */ - - for (k = 0; k < 4; k++) { - if (box->v[k]->used == false) { - box->v[k]->used = true; -#ifdef USE_PACK_BIAS - vert_bias_update(box->v[k]); -#endif - vertex_pack_indices[verts_pack_len] = box->v[k]->index; - verts_pack_len++; - } - } - /* The Box verts are only used internally - * Update the box x and y since thats what external - * functions will see */ - box->x = box_xmin_get(box); - box->y = box_ymin_get(box); - } - } - } - } - } - - *r_tot_x = tot_x; - *r_tot_y = tot_y; - - /* free all the verts, not really needed because they shouldn't be - * touched anymore but accessing the pointers would crash blender */ - for (box_index = 0; box_index < len; box_index++) { - box = boxarray + box_index; - box->v[0] = box->v[1] = box->v[2] = box->v[3] = NULL; - } - MEM_freeN(vertex_pack_indices); - MEM_freeN(vs_ctx.vertarray); -} diff --git a/source/blender/blenlib/intern/boxpack_2d.c b/source/blender/blenlib/intern/boxpack_2d.c new file mode 100644 index 00000000000..b3beff0b78b --- /dev/null +++ b/source/blender/blenlib/intern/boxpack_2d.c @@ -0,0 +1,674 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * Contributor(s): Campbell Barton + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenlib/intern/boxpack2d.c + * \ingroup bli + */ + +#include /* for qsort */ +#include /* for fabsf */ + +#include "MEM_guardedalloc.h" + +#include "BLI_utildefines.h" +#include "BLI_boxpack_2d.h" /* own include */ + +#include "BLI_sort.h" /* qsort_r */ +#define qsort_r BLI_qsort_r + +#include "BLI_strict_flags.h" + +#ifdef __GNUC__ +# pragma GCC diagnostic error "-Wpadded" +#endif + +/* de-duplicate as we pack */ +#define USE_MERGE +/* use strip-free */ +#define USE_FREE_STRIP +/* slight bias, needed when packing many boxes the _exact_ same size */ +#define USE_PACK_BIAS + + +/* BoxPacker for backing 2D rectangles into a square + * + * The defined Below are for internal use only */ +typedef struct BoxVert { + float x; + float y; + + int free : 8; /* vert status */ + uint used : 1; + uint _pad : 23; + uint index; + + struct BoxPack *trb; /* top right box */ + struct BoxPack *blb; /* bottom left box */ + struct BoxPack *brb; /* bottom right box */ + struct BoxPack *tlb; /* top left box */ + + /* Store last intersecting boxes here + * speedup intersection testing */ + struct BoxPack *isect_cache[4]; + +#ifdef USE_PACK_BIAS + float bias; + int _pad2; +#endif +} BoxVert; + +#ifdef __GNUC__ +# pragma GCC diagnostic ignored "-Wpadded" +#endif + +/* free vert flags */ +#define EPSILON 0.0000001f +#define EPSILON_MERGE 0.00001f +#ifdef USE_PACK_BIAS +# define EPSILON_BIAS 0.000001f +#endif +#define BLF 1 +#define TRF 2 +#define TLF 4 +#define BRF 8 +#define CORNERFLAGS (BLF | TRF | TLF | BRF) + +BLI_INLINE int quad_flag(uint q) +{ + BLI_assert(q < 4); + return (1 << q); +} + +#define BL 0 +#define TR 1 +#define TL 2 +#define BR 3 + +/** \name Box Accessor Functions + * \{ */ + +static float box_xmin_get(const BoxPack *box) +{ + return box->v[BL]->x; +} + +static float box_xmax_get(const BoxPack *box) +{ + return box->v[TR]->x; +} + +static float box_ymin_get(const BoxPack *box) +{ + return box->v[BL]->y; +} + +static float box_ymax_get(const BoxPack *box) +{ + return box->v[TR]->y; +} +/** \} */ + + +/** \name Box Placement + * \{ */ + +BLI_INLINE void box_v34x_update(BoxPack *box) +{ + box->v[TL]->x = box->v[BL]->x; + box->v[BR]->x = box->v[TR]->x; +} + +BLI_INLINE void box_v34y_update(BoxPack *box) +{ + box->v[TL]->y = box->v[TR]->y; + box->v[BR]->y = box->v[BL]->y; +} + +static void box_xmin_set(BoxPack *box, const float f) +{ + box->v[TR]->x = f + box->w; + box->v[BL]->x = f; + box_v34x_update(box); +} + +static void box_xmax_set(BoxPack *box, const float f) +{ + box->v[BL]->x = f - box->w; + box->v[TR]->x = f; + box_v34x_update(box); +} + +static void box_ymin_set(BoxPack *box, const float f) +{ + box->v[TR]->y = f + box->h; + box->v[BL]->y = f; + box_v34y_update(box); +} + +static void box_ymax_set(BoxPack *box, const float f) +{ + box->v[BL]->y = f - box->h; + box->v[TR]->y = f; + box_v34y_update(box); +} +/** \} */ + + +/** \name Box Utils + * \{ */ + +static float box_area(const BoxPack *box) +{ + return box->w * box->h; +} + +static bool box_isect(const BoxPack *box_a, const BoxPack *box_b) +{ + return !(box_xmin_get(box_a) + EPSILON >= box_xmax_get(box_b) || + box_ymin_get(box_a) + EPSILON >= box_ymax_get(box_b) || + box_xmax_get(box_a) - EPSILON <= box_xmin_get(box_b) || + box_ymax_get(box_a) - EPSILON <= box_ymin_get(box_b)); +} + +/** \} */ + + +/* compiler should inline */ +static float max_ff(const float a, const float b) { return b > a ? b : a; } + +#ifdef USE_PACK_BIAS +/* set when used is enabled */ +static void vert_bias_update(BoxVert *v) +{ + BLI_assert(v->used); + v->bias = (v->x * v->y) * EPSILON_BIAS; +} +#endif + +#if 0 +#define BOXDEBUG(b) \ + printf("\tBox Debug i %i, w:%.3f h:%.3f x:%.3f y:%.3f\n", \ + b->index, b->w, b->h, b->x, b->y) +#endif + +/** \name Box/Vert Sorting + * \{ */ + +/* qsort function - sort largest to smallest */ +static int box_areasort(const void *p1, const void *p2) +{ + const BoxPack *b1 = p1, *b2 = p2; + const float a1 = box_area(b1); + const float a2 = box_area(b2); + + if (a1 < a2) return 1; + else if (a1 > a2) return -1; + return 0; +} + +/* qsort vertex sorting function + * sorts from lower left to top right It uses the current box's width and height + * as offsets when sorting, this has the result of not placing boxes outside + * the bounds of the existing backed area where possible + */ +struct VertSortContext { + BoxVert *vertarray; + float box_width, box_height; +}; + +static int vertex_sort(const void *p1, const void *p2, void *vs_ctx_p) +{ + const struct VertSortContext *vs_ctx = vs_ctx_p; + const BoxVert *v1, *v2; + float a1, a2; + + v1 = &vs_ctx->vertarray[*((const uint *)p1)]; + v2 = &vs_ctx->vertarray[*((const uint *)p2)]; + +#ifdef USE_FREE_STRIP + /* push free verts to the end so we can strip */ + if (UNLIKELY(v1->free == 0 && v2->free == 0)) return 0; + else if (UNLIKELY(v1->free == 0)) return 1; + else if (UNLIKELY(v2->free == 0)) return -1; +#endif + + a1 = max_ff(v1->x + vs_ctx->box_width, v1->y + vs_ctx->box_height); + a2 = max_ff(v2->x + vs_ctx->box_width, v2->y + vs_ctx->box_height); + +#ifdef USE_PACK_BIAS + a1 += v1->bias; + a2 += v2->bias; +#endif + + /* sort largest to smallest */ + if (a1 > a2) return 1; + else if (a1 < a2) return -1; + return 0; +} +/** \} */ + +/** + * Main boxpacking 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) + * + * \param boxarray: 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. + * \param len: the number of boxes in the array. + * \param r_tot_x, r_tot_y: set so you can normalize the data. + * */ +void BLI_box_pack_2d(BoxPack *boxarray, const uint len, float *r_tot_x, float *r_tot_y) +{ + uint box_index, verts_pack_len, i, j, k; + uint *vertex_pack_indices; /* an array of indices used for sorting verts */ + bool isect; + float tot_x = 0.0f, tot_y = 0.0f; + + BoxPack *box, *box_test; /*current box and another for intersection tests*/ + BoxVert *vert; /* the current vert */ + + struct VertSortContext vs_ctx; + + if (!len) { + *r_tot_x = tot_x; + *r_tot_y = tot_y; + return; + } + + /* Sort boxes, biggest first */ + qsort(boxarray, (size_t)len, sizeof(BoxPack), box_areasort); + + /* add verts to the boxes, these are only used internally */ + vert = MEM_mallocN((size_t)len * 4 * sizeof(BoxVert), "BoxPack Verts"); + vertex_pack_indices = MEM_mallocN((size_t)len * 3 * sizeof(int), "BoxPack Indices"); + + vs_ctx.vertarray = vert; + + for (box = boxarray, box_index = 0, i = 0; box_index < len; box_index++, box++) { + + vert->blb = vert->brb = vert->tlb = + vert->isect_cache[0] = vert->isect_cache[1] = + vert->isect_cache[2] = vert->isect_cache[3] = NULL; + vert->free = CORNERFLAGS & ~TRF; + vert->trb = box; + vert->used = false; + vert->index = i++; + box->v[BL] = vert++; + + vert->trb = vert->brb = vert->tlb = + vert->isect_cache[0] = vert->isect_cache[1] = + vert->isect_cache[2] = vert->isect_cache[3] = NULL; + vert->free = CORNERFLAGS & ~BLF; + vert->blb = box; + vert->used = false; + vert->index = i++; + box->v[TR] = vert++; + + vert->trb = vert->blb = vert->tlb = + vert->isect_cache[0] = vert->isect_cache[1] = + vert->isect_cache[2] = vert->isect_cache[3] = NULL; + vert->free = CORNERFLAGS & ~BRF; + vert->brb = box; + vert->used = false; + vert->index = i++; + box->v[TL] = vert++; + + vert->trb = vert->blb = vert->brb = + vert->isect_cache[0] = vert->isect_cache[1] = + vert->isect_cache[2] = vert->isect_cache[3] = NULL; + vert->free = CORNERFLAGS & ~TLF; + vert->tlb = box; + vert->used = false; + vert->index = i++; + box->v[BR] = vert++; + } + vert = NULL; + + /* Pack the First box! + * then enter the main box-packing loop */ + + box = boxarray; /* get the first box */ + /* First time, no boxes packed */ + box->v[BL]->free = 0; /* Can't use any if these */ + box->v[BR]->free &= ~(BLF | BRF); + box->v[TL]->free &= ~(BLF | TLF); + + tot_x = box->w; + tot_y = box->h; + + /* This sets all the vertex locations */ + box_xmin_set(box, 0.0f); + box_ymin_set(box, 0.0f); + box->x = box->y = 0.0f; + + for (i = 0; i < 4; i++) { + box->v[i]->used = true; +#ifdef USE_PACK_BIAS + vert_bias_update(box->v[i]); +#endif + } + + for (i = 0; i < 3; i++) + vertex_pack_indices[i] = box->v[i + 1]->index; + verts_pack_len = 3; + box++; /* next box, needed for the loop below */ + /* ...done packing the first box */ + + /* Main boxpacking loop */ + for (box_index = 1; box_index < len; box_index++, box++) { + + /* These floats are used for sorting re-sorting */ + vs_ctx.box_width = box->w; + vs_ctx.box_height = box->h; + + qsort_r(vertex_pack_indices, (size_t)verts_pack_len, sizeof(int), vertex_sort, &vs_ctx); + +#ifdef USE_FREE_STRIP + /* strip free vertices */ + i = verts_pack_len - 1; + while ((i != 0) && vs_ctx.vertarray[vertex_pack_indices[i]].free == 0) { + i--; + } + verts_pack_len = i + 1; +#endif + + /* Pack the box in with the others */ + /* sort the verts */ + isect = true; + + for (i = 0; i < verts_pack_len && isect; i++) { + vert = &vs_ctx.vertarray[vertex_pack_indices[i]]; + /* printf("\ttesting vert %i %i %i %f %f\n", i, + * vert->free, verts_pack_len, vert->x, vert->y); */ + + /* This vert has a free quadrant + * Test if we can place the box here + * vert->free & quad_flags[j] - Checks + * */ + + for (j = 0; (j < 4) && isect; j++) { + if (vert->free & quad_flag(j)) { + switch (j) { + case BL: + box_xmax_set(box, vert->x); + box_ymax_set(box, vert->y); + break; + case TR: + box_xmin_set(box, vert->x); + box_ymin_set(box, vert->y); + break; + case TL: + box_xmax_set(box, vert->x); + box_ymin_set(box, vert->y); + break; + case BR: + box_xmin_set(box, vert->x); + box_ymax_set(box, vert->y); + break; + } + + /* Now we need to check that the box intersects + * with any other boxes + * Assume no intersection... */ + isect = false; + + if ( /* Constrain boxes to positive X/Y values */ + box_xmin_get(box) < 0.0f || box_ymin_get(box) < 0.0f || + /* check for last intersected */ + (vert->isect_cache[j] && + box_isect(box, vert->isect_cache[j]))) + { + /* Here we check that the last intersected + * box will intersect with this one using + * isect_cache that can store a pointer to a + * box for each quadrant + * big speedup */ + isect = true; + } + else { + /* do a full search for colliding box + * this is really slow, some spatially divided + * data-structure would be better */ + for (box_test = boxarray; box_test != box; box_test++) { + if (box_isect(box, box_test)) { + /* Store the last intersecting here as cache + * for faster checking next time around */ + vert->isect_cache[j] = box_test; + isect = true; + break; + } + } + } + + if (!isect) { + + /* maintain the total width and height */ + tot_x = max_ff(box_xmax_get(box), tot_x); + tot_y = max_ff(box_ymax_get(box), tot_y); + + /* Place the box */ + vert->free &= (signed char)(~quad_flag(j)); + + switch (j) { + case TR: + box->v[BL] = vert; + vert->trb = box; + break; + case TL: + box->v[BR] = vert; + vert->tlb = box; + break; + case BR: + box->v[TL] = vert; + vert->brb = box; + break; + case BL: + box->v[TR] = vert; + vert->blb = box; + break; + } + + /* Mask free flags for verts that are + * on the bottom or side so we don't get + * boxes outside the given rectangle ares + * + * We can do an else/if here because only the first + * box can be at the very bottom left corner */ + if (box_xmin_get(box) <= 0) { + box->v[TL]->free &= ~(TLF | BLF); + box->v[BL]->free &= ~(TLF | BLF); + } + else if (box_ymin_get(box) <= 0) { + box->v[BL]->free &= ~(BRF | BLF); + box->v[BR]->free &= ~(BRF | BLF); + } + + /* The following block of code does a logical + * check with 2 adjacent boxes, its possible to + * flag verts on one or both of the boxes + * as being used by checking the width or + * height of both boxes */ + if (vert->tlb && vert->trb && (box == vert->tlb || box == vert->trb)) { + if (UNLIKELY(fabsf(vert->tlb->h - vert->trb->h) < EPSILON_MERGE)) { +#ifdef USE_MERGE +# define A (vert->trb->v[TL]) +# define B (vert->tlb->v[TR]) +# define MASK (BLF | BRF) + BLI_assert(A->used != B->used); + if (A->used) { + A->free &= B->free & ~MASK; + B = A; + } + else { + B->free &= A->free & ~MASK; + A = B; + } + BLI_assert((A->free & MASK) == 0); +# undef A +# undef B +# undef MASK +#else + vert->tlb->v[TR]->free &= ~BLF; + vert->trb->v[TL]->free &= ~BRF; +#endif + } + else if (vert->tlb->h > vert->trb->h) { + vert->trb->v[TL]->free &= ~(TLF | BLF); + } + else /* if (vert->tlb->h < vert->trb->h) */ { + vert->tlb->v[TR]->free &= ~(TRF | BRF); + } + } + else if (vert->blb && vert->brb && (box == vert->blb || box == vert->brb)) { + if (UNLIKELY(fabsf(vert->blb->h - vert->brb->h) < EPSILON_MERGE)) { +#ifdef USE_MERGE +# define A (vert->blb->v[BR]) +# define B (vert->brb->v[BL]) +# define MASK (TRF | TLF) + BLI_assert(A->used != B->used); + if (A->used) { + A->free &= B->free & ~MASK; + B = A; + } + else { + B->free &= A->free & ~MASK; + A = B; + } + BLI_assert((A->free & MASK) == 0); +# undef A +# undef B +# undef MASK +#else + vert->blb->v[BR]->free &= ~TRF; + vert->brb->v[BL]->free &= ~TLF; +#endif + } + else if (vert->blb->h > vert->brb->h) { + vert->brb->v[BL]->free &= ~(TLF | BLF); + } + else /* if (vert->blb->h < vert->brb->h) */ { + vert->blb->v[BR]->free &= ~(TRF | BRF); + } + } + /* Horizontal */ + if (vert->tlb && vert->blb && (box == vert->tlb || box == vert->blb)) { + if (UNLIKELY(fabsf(vert->tlb->w - vert->blb->w) < EPSILON_MERGE)) { +#ifdef USE_MERGE +# define A (vert->blb->v[TL]) +# define B (vert->tlb->v[BL]) +# define MASK (TRF | BRF) + BLI_assert(A->used != B->used); + if (A->used) { + A->free &= B->free & ~MASK; + B = A; + } + else { + B->free &= A->free & ~MASK; + A = B; + } + BLI_assert((A->free & MASK) == 0); +# undef A +# undef B +# undef MASK +#else + vert->blb->v[TL]->free &= ~TRF; + vert->tlb->v[BL]->free &= ~BRF; +#endif + } + else if (vert->tlb->w > vert->blb->w) { + vert->blb->v[TL]->free &= ~(TLF | TRF); + } + else /* if (vert->tlb->w < vert->blb->w) */ { + vert->tlb->v[BL]->free &= ~(BLF | BRF); + } + } + else if (vert->trb && vert->brb && (box == vert->trb || box == vert->brb)) { + if (UNLIKELY(fabsf(vert->trb->w - vert->brb->w) < EPSILON_MERGE)) { + +#ifdef USE_MERGE +# define A (vert->brb->v[TR]) +# define B (vert->trb->v[BR]) +# define MASK (TLF | BLF) + BLI_assert(A->used != B->used); + if (A->used) { + A->free &= B->free & ~MASK; + B = A; + } + else { + B->free &= A->free & ~MASK; + A = B; + } + BLI_assert((A->free & MASK) == 0); +# undef A +# undef B +# undef MASK +#else + vert->brb->v[TR]->free &= ~TLF; + vert->trb->v[BR]->free &= ~BLF; +#endif + } + else if (vert->trb->w > vert->brb->w) { + vert->brb->v[TR]->free &= ~(TLF | TRF); + } + else /* if (vert->trb->w < vert->brb->w) */ { + vert->trb->v[BR]->free &= ~(BLF | BRF); + } + } + /* End logical check */ + + for (k = 0; k < 4; k++) { + if (box->v[k]->used == false) { + box->v[k]->used = true; +#ifdef USE_PACK_BIAS + vert_bias_update(box->v[k]); +#endif + vertex_pack_indices[verts_pack_len] = box->v[k]->index; + verts_pack_len++; + } + } + /* The Box verts are only used internally + * Update the box x and y since thats what external + * functions will see */ + box->x = box_xmin_get(box); + box->y = box_ymin_get(box); + } + } + } + } + } + + *r_tot_x = tot_x; + *r_tot_y = tot_y; + + /* free all the verts, not really needed because they shouldn't be + * touched anymore but accessing the pointers would crash blender */ + for (box_index = 0; box_index < len; box_index++) { + box = boxarray + box_index; + box->v[0] = box->v[1] = box->v[2] = box->v[3] = NULL; + } + MEM_freeN(vertex_pack_indices); + MEM_freeN(vs_ctx.vertarray); +} diff --git a/source/blender/blenlib/intern/convexhull2d.c b/source/blender/blenlib/intern/convexhull2d.c deleted file mode 100644 index 1f1f214ce32..00000000000 --- a/source/blender/blenlib/intern/convexhull2d.c +++ /dev/null @@ -1,331 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file blender/blenlib/intern/convexhull2d.c - * \ingroup bli - */ - - -#include -#include - -#include "MEM_guardedalloc.h" - -#include "BLI_convexhull2d.h" -#include "BLI_math.h" -#include "BLI_strict_flags.h" -#include "BLI_utildefines.h" - -/* Copyright 2001, softSurfer (www.softsurfer.com) - * This code may be freely used and modified for any purpose - * providing that this copyright notice is included with it. - * SoftSurfer makes no warranty for this code, and cannot be held - * liable for any real or imagined damage resulting from its use. - * Users of this code must verify correctness for their application. - * http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm - */ - -/** \name Main Convex-Hull Calculation - * \{ */ - -/** - * tests if a point is Left|On|Right of an infinite line. - * Input: three points P0, P1, and P2 - * \returns > 0.0 for P2 left of the line through P0 and P1. - * = 0.0 for P2 on the line. - * < 0.0 for P2 right of the line. - */ -static float is_left(const float p0[2], const float p1[2], const float p2[2]) -{ - return (p1[0] - p0[0]) * (p2[1] - p0[1]) - (p2[0] - p0[0]) * (p1[1] - p0[1]); -} - -/** - * A.M. Andrew's monotone chain 2D convex hull algorithm - * - * \param points An array of 2D points presorted by increasing x and y-coords. - * \param n The number of points in points. - * \param r_points An array of the convex hull vertex indices (max is n). - * \returns the number of points in r_points. - */ -int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points[]) -{ - /* the output array r_points[] will be used as the stack */ - int bot = 0; - int top = -1; /* indices for bottom and top of the stack */ - int i; /* array scan index */ - int minmin, minmax; - int maxmin, maxmax; - float xmax; - - /* Get the indices of points with min x-coord and min|max y-coord */ - float xmin = points[0][0]; - for (i = 1; i < n; i++) { - if (points[i][0] != xmin) { - break; - } - } - - minmin = 0; - minmax = i - 1; - if (minmax == n - 1) { /* degenerate case: all x-coords == xmin */ - r_points[++top] = minmin; - if (points[minmax][1] != points[minmin][1]) /* a nontrivial segment */ - r_points[++top] = minmax; - r_points[++top] = minmin; /* add polygon endpoint */ - return top + 1; - } - - /* Get the indices of points with max x-coord and min|max y-coord */ - - maxmax = n - 1; - xmax = points[n - 1][0]; - for (i = n - 2; i >= 0; i--) { - if (points[i][0] != xmax) { - break; - } - } - maxmin = i + 1; - - /* Compute the lower hull on the stack r_points */ - r_points[++top] = minmin; /* push minmin point onto stack */ - i = minmax; - while (++i <= maxmin) { - /* the lower line joins points[minmin] with points[maxmin] */ - if (is_left(points[minmin], points[maxmin], points[i]) >= 0 && i < maxmin) { - continue; /* ignore points[i] above or on the lower line */ - } - - while (top > 0) { /* there are at least 2 points on the stack */ - /* test if points[i] is left of the line at the stack top */ - if (is_left(points[r_points[top - 1]], points[r_points[top]], points[i]) > 0.0f) { - break; /* points[i] is a new hull vertex */ - } - else { - top--; /* pop top point off stack */ - } - } - - r_points[++top] = i; /* push points[i] onto stack */ - } - - /* Next, compute the upper hull on the stack r_points above the bottom hull */ - if (maxmax != maxmin) { /* if distinct xmax points */ - r_points[++top] = maxmax; /* push maxmax point onto stack */ - } - - bot = top; /* the bottom point of the upper hull stack */ - i = maxmin; - while (--i >= minmax) { - /* the upper line joins points[maxmax] with points[minmax] */ - if (is_left(points[maxmax], points[minmax], points[i]) >= 0 && i > minmax) { - continue; /* ignore points[i] below or on the upper line */ - } - - while (top > bot) { /* at least 2 points on the upper stack */ - /* test if points[i] is left of the line at the stack top */ - if (is_left(points[r_points[top - 1]], points[r_points[top]], points[i]) > 0.0f) { - break; /* points[i] is a new hull vertex */ - } - else { - top--; /* pop top point off stack */ - } - } - - if (points[i][0] == points[r_points[0]][0] && points[i][1] == points[r_points[0]][1]) { - return top + 1; /* special case (mgomes) */ - } - - r_points[++top] = i; /* push points[i] onto stack */ - } - - if (minmax != minmin) { - r_points[++top] = minmin; /* push joining endpoint onto stack */ - } - - return top + 1; -} - -struct PointRef { - const float *pt; /* 2d vector */ -}; - -static int pointref_cmp_yx(const void *a_, const void *b_) -{ - const struct PointRef *a = a_; - const struct PointRef *b = b_; - - if (a->pt[1] > b->pt[1]) return 1; - else if (a->pt[1] < b->pt[1]) return -1; - - if (a->pt[0] > b->pt[0]) return 1; - else if (a->pt[0] < b->pt[0]) return -1; - - else return 0; -} - -/** - * A.M. Andrew's monotone chain 2D convex hull algorithm - * - * \param points An array of 2D points. - * \param n The number of points in points. - * \param r_points An array of the convex hull vertex indices (max is n). - * _must_ be allocated as ``n * 2`` because of how its used internally, - * even though the final result will be no more than \a n in size. - * \returns the number of points in r_points. - */ -int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[]) -{ - struct PointRef *points_ref = MEM_mallocN(sizeof(*points_ref) * (size_t)n, __func__); - float (*points_sort)[2] = MEM_mallocN(sizeof(*points_sort) * (size_t)n, __func__); - int *points_map; - int tot, i; - - for (i = 0; i < n; i++) { - points_ref[i].pt = points[i]; - } - - /* Sort the points by X, then by Y (required by the algorithm) */ - qsort(points_ref, (size_t)n, sizeof(struct PointRef), pointref_cmp_yx); - - for (i = 0; i < n; i++) { - memcpy(points_sort[i], points_ref[i].pt, sizeof(float[2])); - } - - tot = BLI_convexhull_2d_sorted(points_sort, n, r_points); - - /* map back to the original index values */ - points_map = (int *)points_sort; /* abuse float array for temp storage */ - for (i = 0; i < tot; i++) { - points_map[i] = (int)((const float(*)[2])points_ref[r_points[i]].pt - points); - } - - memcpy(r_points, points_map, (size_t)tot * sizeof(*points_map)); - - MEM_freeN(points_ref); - MEM_freeN(points_sort); - - return tot; -} - -/** \} */ - - -/* -------------------------------------------------------------------- */ -/* Helper functions */ - -/** \name Utility Convex-Hull Functions - * \{ */ - -/** - * \return The best angle for fitting the convex hull to an axis aligned bounding box. - * - * Intended to be used with #BLI_convexhull_2d - * - * \param points_hull Ordered hull points - * (result of #BLI_convexhull_2d mapped to a contiguous array). - * - * \note we could return the index of the best edge too if its needed. - */ -float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], unsigned int n) -{ - unsigned int i, i_prev; - float area_best = FLT_MAX; - float dvec_best[2]; /* best angle, delay atan2 */ - - i_prev = n - 1; - for (i = 0; i < n; i++) { - const float *ev_a = points_hull[i]; - const float *ev_b = points_hull[i_prev]; - float dvec[2]; /* 2d rotation matrix */ - - sub_v2_v2v2(dvec, ev_a, ev_b); - if (normalize_v2(dvec) != 0.0f) { - /* rotation matrix */ - float min[2] = {FLT_MAX, FLT_MAX}, max[2] = {-FLT_MAX, -FLT_MAX}; - unsigned int j; - float area; - - for (j = 0; j < n; j++) { - float tvec[2]; - mul_v2_v2_cw(tvec, dvec, points_hull[j]); - - min[0] = min_ff(min[0], tvec[0]); - min[1] = min_ff(min[1], tvec[1]); - - max[0] = max_ff(max[0], tvec[0]); - max[1] = max_ff(max[1], tvec[1]); - - area = (max[0] - min[0]) * (max[1] - min[1]); - if (area > area_best) { - break; - } - } - - if (area < area_best) { - area_best = area; - copy_v2_v2(dvec_best, dvec); - } - } - - i_prev = i; - } - - return (area_best != FLT_MAX) ? atan2f(dvec_best[0], dvec_best[1]) : 0.0f; -} - -/** - * Wrap #BLI_convexhull_aabb_fit_hull_2d and do the convex hull calculation. - * - * \param points arbitrary 2d points. - */ -float BLI_convexhull_aabb_fit_points_2d(const float (*points)[2], unsigned int n) -{ - int *index_map; - int tot; - - float angle; - - index_map = MEM_mallocN(sizeof(*index_map) * n * 2, __func__); - - tot = BLI_convexhull_2d(points, (int)n, index_map); - - if (tot) { - float (*points_hull)[2]; - int j; - - points_hull = MEM_mallocN(sizeof(*points_hull) * (size_t)tot, __func__); - for (j = 0; j < tot; j++) { - copy_v2_v2(points_hull[j], points[index_map[j]]); - } - - angle = BLI_convexhull_aabb_fit_hull_2d(points_hull, (unsigned int)tot); - MEM_freeN(points_hull); - } - else { - angle = 0.0f; - } - - MEM_freeN(index_map); - - return angle; -} - -/** \} */ diff --git a/source/blender/blenlib/intern/convexhull_2d.c b/source/blender/blenlib/intern/convexhull_2d.c new file mode 100644 index 00000000000..38928dbbaa0 --- /dev/null +++ b/source/blender/blenlib/intern/convexhull_2d.c @@ -0,0 +1,331 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenlib/intern/convexhull_2d.c + * \ingroup bli + */ + + +#include +#include + +#include "MEM_guardedalloc.h" + +#include "BLI_convexhull_2d.h" +#include "BLI_math.h" +#include "BLI_strict_flags.h" +#include "BLI_utildefines.h" + +/* Copyright 2001, softSurfer (www.softsurfer.com) + * This code may be freely used and modified for any purpose + * providing that this copyright notice is included with it. + * SoftSurfer makes no warranty for this code, and cannot be held + * liable for any real or imagined damage resulting from its use. + * Users of this code must verify correctness for their application. + * http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm + */ + +/** \name Main Convex-Hull Calculation + * \{ */ + +/** + * tests if a point is Left|On|Right of an infinite line. + * Input: three points P0, P1, and P2 + * \returns > 0.0 for P2 left of the line through P0 and P1. + * = 0.0 for P2 on the line. + * < 0.0 for P2 right of the line. + */ +static float is_left(const float p0[2], const float p1[2], const float p2[2]) +{ + return (p1[0] - p0[0]) * (p2[1] - p0[1]) - (p2[0] - p0[0]) * (p1[1] - p0[1]); +} + +/** + * A.M. Andrew's monotone chain 2D convex hull algorithm + * + * \param points An array of 2D points presorted by increasing x and y-coords. + * \param n The number of points in points. + * \param r_points An array of the convex hull vertex indices (max is n). + * \returns the number of points in r_points. + */ +int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points[]) +{ + /* the output array r_points[] will be used as the stack */ + int bot = 0; + int top = -1; /* indices for bottom and top of the stack */ + int i; /* array scan index */ + int minmin, minmax; + int maxmin, maxmax; + float xmax; + + /* Get the indices of points with min x-coord and min|max y-coord */ + float xmin = points[0][0]; + for (i = 1; i < n; i++) { + if (points[i][0] != xmin) { + break; + } + } + + minmin = 0; + minmax = i - 1; + if (minmax == n - 1) { /* degenerate case: all x-coords == xmin */ + r_points[++top] = minmin; + if (points[minmax][1] != points[minmin][1]) /* a nontrivial segment */ + r_points[++top] = minmax; + r_points[++top] = minmin; /* add polygon endpoint */ + return top + 1; + } + + /* Get the indices of points with max x-coord and min|max y-coord */ + + maxmax = n - 1; + xmax = points[n - 1][0]; + for (i = n - 2; i >= 0; i--) { + if (points[i][0] != xmax) { + break; + } + } + maxmin = i + 1; + + /* Compute the lower hull on the stack r_points */ + r_points[++top] = minmin; /* push minmin point onto stack */ + i = minmax; + while (++i <= maxmin) { + /* the lower line joins points[minmin] with points[maxmin] */ + if (is_left(points[minmin], points[maxmin], points[i]) >= 0 && i < maxmin) { + continue; /* ignore points[i] above or on the lower line */ + } + + while (top > 0) { /* there are at least 2 points on the stack */ + /* test if points[i] is left of the line at the stack top */ + if (is_left(points[r_points[top - 1]], points[r_points[top]], points[i]) > 0.0f) { + break; /* points[i] is a new hull vertex */ + } + else { + top--; /* pop top point off stack */ + } + } + + r_points[++top] = i; /* push points[i] onto stack */ + } + + /* Next, compute the upper hull on the stack r_points above the bottom hull */ + if (maxmax != maxmin) { /* if distinct xmax points */ + r_points[++top] = maxmax; /* push maxmax point onto stack */ + } + + bot = top; /* the bottom point of the upper hull stack */ + i = maxmin; + while (--i >= minmax) { + /* the upper line joins points[maxmax] with points[minmax] */ + if (is_left(points[maxmax], points[minmax], points[i]) >= 0 && i > minmax) { + continue; /* ignore points[i] below or on the upper line */ + } + + while (top > bot) { /* at least 2 points on the upper stack */ + /* test if points[i] is left of the line at the stack top */ + if (is_left(points[r_points[top - 1]], points[r_points[top]], points[i]) > 0.0f) { + break; /* points[i] is a new hull vertex */ + } + else { + top--; /* pop top point off stack */ + } + } + + if (points[i][0] == points[r_points[0]][0] && points[i][1] == points[r_points[0]][1]) { + return top + 1; /* special case (mgomes) */ + } + + r_points[++top] = i; /* push points[i] onto stack */ + } + + if (minmax != minmin) { + r_points[++top] = minmin; /* push joining endpoint onto stack */ + } + + return top + 1; +} + +struct PointRef { + const float *pt; /* 2d vector */ +}; + +static int pointref_cmp_yx(const void *a_, const void *b_) +{ + const struct PointRef *a = a_; + const struct PointRef *b = b_; + + if (a->pt[1] > b->pt[1]) return 1; + else if (a->pt[1] < b->pt[1]) return -1; + + if (a->pt[0] > b->pt[0]) return 1; + else if (a->pt[0] < b->pt[0]) return -1; + + else return 0; +} + +/** + * A.M. Andrew's monotone chain 2D convex hull algorithm + * + * \param points An array of 2D points. + * \param n The number of points in points. + * \param r_points An array of the convex hull vertex indices (max is n). + * _must_ be allocated as ``n * 2`` because of how its used internally, + * even though the final result will be no more than \a n in size. + * \returns the number of points in r_points. + */ +int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[]) +{ + struct PointRef *points_ref = MEM_mallocN(sizeof(*points_ref) * (size_t)n, __func__); + float (*points_sort)[2] = MEM_mallocN(sizeof(*points_sort) * (size_t)n, __func__); + int *points_map; + int tot, i; + + for (i = 0; i < n; i++) { + points_ref[i].pt = points[i]; + } + + /* Sort the points by X, then by Y (required by the algorithm) */ + qsort(points_ref, (size_t)n, sizeof(struct PointRef), pointref_cmp_yx); + + for (i = 0; i < n; i++) { + memcpy(points_sort[i], points_ref[i].pt, sizeof(float[2])); + } + + tot = BLI_convexhull_2d_sorted(points_sort, n, r_points); + + /* map back to the original index values */ + points_map = (int *)points_sort; /* abuse float array for temp storage */ + for (i = 0; i < tot; i++) { + points_map[i] = (int)((const float(*)[2])points_ref[r_points[i]].pt - points); + } + + memcpy(r_points, points_map, (size_t)tot * sizeof(*points_map)); + + MEM_freeN(points_ref); + MEM_freeN(points_sort); + + return tot; +} + +/** \} */ + + +/* -------------------------------------------------------------------- */ +/* Helper functions */ + +/** \name Utility Convex-Hull Functions + * \{ */ + +/** + * \return The best angle for fitting the convex hull to an axis aligned bounding box. + * + * Intended to be used with #BLI_convexhull_2d + * + * \param points_hull Ordered hull points + * (result of #BLI_convexhull_2d mapped to a contiguous array). + * + * \note we could return the index of the best edge too if its needed. + */ +float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], unsigned int n) +{ + unsigned int i, i_prev; + float area_best = FLT_MAX; + float dvec_best[2]; /* best angle, delay atan2 */ + + i_prev = n - 1; + for (i = 0; i < n; i++) { + const float *ev_a = points_hull[i]; + const float *ev_b = points_hull[i_prev]; + float dvec[2]; /* 2d rotation matrix */ + + sub_v2_v2v2(dvec, ev_a, ev_b); + if (normalize_v2(dvec) != 0.0f) { + /* rotation matrix */ + float min[2] = {FLT_MAX, FLT_MAX}, max[2] = {-FLT_MAX, -FLT_MAX}; + unsigned int j; + float area; + + for (j = 0; j < n; j++) { + float tvec[2]; + mul_v2_v2_cw(tvec, dvec, points_hull[j]); + + min[0] = min_ff(min[0], tvec[0]); + min[1] = min_ff(min[1], tvec[1]); + + max[0] = max_ff(max[0], tvec[0]); + max[1] = max_ff(max[1], tvec[1]); + + area = (max[0] - min[0]) * (max[1] - min[1]); + if (area > area_best) { + break; + } + } + + if (area < area_best) { + area_best = area; + copy_v2_v2(dvec_best, dvec); + } + } + + i_prev = i; + } + + return (area_best != FLT_MAX) ? atan2f(dvec_best[0], dvec_best[1]) : 0.0f; +} + +/** + * Wrap #BLI_convexhull_aabb_fit_hull_2d and do the convex hull calculation. + * + * \param points arbitrary 2d points. + */ +float BLI_convexhull_aabb_fit_points_2d(const float (*points)[2], unsigned int n) +{ + int *index_map; + int tot; + + float angle; + + index_map = MEM_mallocN(sizeof(*index_map) * n * 2, __func__); + + tot = BLI_convexhull_2d(points, (int)n, index_map); + + if (tot) { + float (*points_hull)[2]; + int j; + + points_hull = MEM_mallocN(sizeof(*points_hull) * (size_t)tot, __func__); + for (j = 0; j < tot; j++) { + copy_v2_v2(points_hull[j], points[index_map[j]]); + } + + angle = BLI_convexhull_aabb_fit_hull_2d(points_hull, (unsigned int)tot); + MEM_freeN(points_hull); + } + else { + angle = 0.0f; + } + + MEM_freeN(index_map); + + return angle; +} + +/** \} */ diff --git a/source/blender/blenlib/intern/jitter.c b/source/blender/blenlib/intern/jitter.c deleted file mode 100644 index bc2b5677fa5..00000000000 --- a/source/blender/blenlib/intern/jitter.c +++ /dev/null @@ -1,186 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file blender/blenlib/intern/jitter.c - * \ingroup bli - * \brief Jitter offset table - */ - -#include -#include -#include "MEM_guardedalloc.h" - -#include "BLI_rand.h" -#include "BLI_jitter.h" - -#include "BLI_strict_flags.h" - - -void BLI_jitterate1(float (*jit1)[2], float (*jit2)[2], int num, float rad1) -{ - int i, j, k; - float vecx, vecy, dvecx, dvecy, x, y, len; - - for (i = num - 1; i >= 0; i--) { - dvecx = dvecy = 0.0; - x = jit1[i][0]; - y = jit1[i][1]; - for (j = num - 1; j >= 0; j--) { - if (i != j) { - vecx = jit1[j][0] - x - 1.0f; - vecy = jit1[j][1] - y - 1.0f; - for (k = 3; k > 0; k--) { - if (fabsf(vecx) < rad1 && fabsf(vecy) < rad1) { - len = sqrtf(vecx * vecx + vecy * vecy); - if (len > 0 && len < rad1) { - len = len / rad1; - dvecx += vecx / len; - dvecy += vecy / len; - } - } - vecx += 1.0f; - - if (fabsf(vecx) < rad1 && fabsf(vecy) < rad1) { - len = sqrtf(vecx * vecx + vecy * vecy); - if (len > 0 && len < rad1) { - len = len / rad1; - dvecx += vecx / len; - dvecy += vecy / len; - } - } - vecx += 1.0f; - - if (fabsf(vecx) < rad1 && fabsf(vecy) < rad1) { - len = sqrtf(vecx * vecx + vecy * vecy); - if (len > 0 && len < rad1) { - len = len / rad1; - dvecx += vecx / len; - dvecy += vecy / len; - } - } - vecx -= 2.0f; - vecy += 1.0f; - } - } - } - - x -= dvecx / 18.0f; - y -= dvecy / 18.0f; - x -= floorf(x); - y -= floorf(y); - jit2[i][0] = x; - jit2[i][1] = y; - } - memcpy(jit1, jit2, 2 * (unsigned int)num * sizeof(float)); -} - -void BLI_jitterate2(float (*jit1)[2], float (*jit2)[2], int num, float rad2) -{ - int i, j; - float vecx, vecy, dvecx, dvecy, x, y; - - for (i = num - 1; i >= 0; i--) { - dvecx = dvecy = 0.0; - x = jit1[i][0]; - y = jit1[i][1]; - for (j = num - 1; j >= 0; j--) { - if (i != j) { - vecx = jit1[j][0] - x - 1.0f; - vecy = jit1[j][1] - y - 1.0f; - - if (fabsf(vecx) < rad2) dvecx += vecx * rad2; - vecx += 1.0f; - if (fabsf(vecx) < rad2) dvecx += vecx * rad2; - vecx += 1.0f; - if (fabsf(vecx) < rad2) dvecx += vecx * rad2; - - if (fabsf(vecy) < rad2) dvecy += vecy * rad2; - vecy += 1.0f; - if (fabsf(vecy) < rad2) dvecy += vecy * rad2; - vecy += 1.0f; - if (fabsf(vecy) < rad2) dvecy += vecy * rad2; - - } - } - - x -= dvecx / 2.0f; - y -= dvecy / 2.0f; - x -= floorf(x); - y -= floorf(y); - jit2[i][0] = x; - jit2[i][1] = y; - } - memcpy(jit1, jit2, (unsigned int)num * sizeof(float[2])); -} - - -void BLI_jitter_init(float (*jitarr)[2], int num) -{ - float (*jit2)[2]; - float num_fl, num_fl_sqrt; - float x, rad1, rad2, rad3; - RNG *rng; - int i; - - if (num == 0) { - return; - } - - num_fl = (float)num; - num_fl_sqrt = sqrtf(num_fl); - - jit2 = MEM_mallocN(12 + (unsigned int)num * sizeof(float[2]), "initjit"); - rad1 = 1.0f / num_fl_sqrt; - rad2 = 1.0f / num_fl; - rad3 = num_fl_sqrt / num_fl; - - rng = BLI_rng_new(31415926 + (unsigned int)num); - - x = 0; - for (i = 0; i < num; i++) { - jitarr[i][0] = x + rad1 * (float)(0.5 - BLI_rng_get_double(rng)); - jitarr[i][1] = (float)i / num_fl + rad1 * (float)(0.5 - BLI_rng_get_double(rng)); - x += rad3; - x -= floorf(x); - } - - BLI_rng_free(rng); - - for (i = 0; i < 24; i++) { - BLI_jitterate1(jitarr, jit2, num, rad1); - BLI_jitterate1(jitarr, jit2, num, rad1); - BLI_jitterate2(jitarr, jit2, num, rad2); - } - - MEM_freeN(jit2); - - /* finally, move jittertab to be centered around (0, 0) */ - for (i = 0; i < num; i++) { - jitarr[i][0] -= 0.5f; - jitarr[i][1] -= 0.5f; - } -} diff --git a/source/blender/blenlib/intern/jitter_2d.c b/source/blender/blenlib/intern/jitter_2d.c new file mode 100644 index 00000000000..6c51eeb36d9 --- /dev/null +++ b/source/blender/blenlib/intern/jitter_2d.c @@ -0,0 +1,186 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): none yet. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenlib/intern/jitter.c + * \ingroup bli + * \brief Jitter offset table + */ + +#include +#include +#include "MEM_guardedalloc.h" + +#include "BLI_rand.h" +#include "BLI_jitter_2d.h" + +#include "BLI_strict_flags.h" + + +void BLI_jitterate1(float (*jit1)[2], float (*jit2)[2], int num, float rad1) +{ + int i, j, k; + float vecx, vecy, dvecx, dvecy, x, y, len; + + for (i = num - 1; i >= 0; i--) { + dvecx = dvecy = 0.0; + x = jit1[i][0]; + y = jit1[i][1]; + for (j = num - 1; j >= 0; j--) { + if (i != j) { + vecx = jit1[j][0] - x - 1.0f; + vecy = jit1[j][1] - y - 1.0f; + for (k = 3; k > 0; k--) { + if (fabsf(vecx) < rad1 && fabsf(vecy) < rad1) { + len = sqrtf(vecx * vecx + vecy * vecy); + if (len > 0 && len < rad1) { + len = len / rad1; + dvecx += vecx / len; + dvecy += vecy / len; + } + } + vecx += 1.0f; + + if (fabsf(vecx) < rad1 && fabsf(vecy) < rad1) { + len = sqrtf(vecx * vecx + vecy * vecy); + if (len > 0 && len < rad1) { + len = len / rad1; + dvecx += vecx / len; + dvecy += vecy / len; + } + } + vecx += 1.0f; + + if (fabsf(vecx) < rad1 && fabsf(vecy) < rad1) { + len = sqrtf(vecx * vecx + vecy * vecy); + if (len > 0 && len < rad1) { + len = len / rad1; + dvecx += vecx / len; + dvecy += vecy / len; + } + } + vecx -= 2.0f; + vecy += 1.0f; + } + } + } + + x -= dvecx / 18.0f; + y -= dvecy / 18.0f; + x -= floorf(x); + y -= floorf(y); + jit2[i][0] = x; + jit2[i][1] = y; + } + memcpy(jit1, jit2, 2 * (unsigned int)num * sizeof(float)); +} + +void BLI_jitterate2(float (*jit1)[2], float (*jit2)[2], int num, float rad2) +{ + int i, j; + float vecx, vecy, dvecx, dvecy, x, y; + + for (i = num - 1; i >= 0; i--) { + dvecx = dvecy = 0.0; + x = jit1[i][0]; + y = jit1[i][1]; + for (j = num - 1; j >= 0; j--) { + if (i != j) { + vecx = jit1[j][0] - x - 1.0f; + vecy = jit1[j][1] - y - 1.0f; + + if (fabsf(vecx) < rad2) dvecx += vecx * rad2; + vecx += 1.0f; + if (fabsf(vecx) < rad2) dvecx += vecx * rad2; + vecx += 1.0f; + if (fabsf(vecx) < rad2) dvecx += vecx * rad2; + + if (fabsf(vecy) < rad2) dvecy += vecy * rad2; + vecy += 1.0f; + if (fabsf(vecy) < rad2) dvecy += vecy * rad2; + vecy += 1.0f; + if (fabsf(vecy) < rad2) dvecy += vecy * rad2; + + } + } + + x -= dvecx / 2.0f; + y -= dvecy / 2.0f; + x -= floorf(x); + y -= floorf(y); + jit2[i][0] = x; + jit2[i][1] = y; + } + memcpy(jit1, jit2, (unsigned int)num * sizeof(float[2])); +} + + +void BLI_jitter_init(float (*jitarr)[2], int num) +{ + float (*jit2)[2]; + float num_fl, num_fl_sqrt; + float x, rad1, rad2, rad3; + RNG *rng; + int i; + + if (num == 0) { + return; + } + + num_fl = (float)num; + num_fl_sqrt = sqrtf(num_fl); + + jit2 = MEM_mallocN(12 + (unsigned int)num * sizeof(float[2]), "initjit"); + rad1 = 1.0f / num_fl_sqrt; + rad2 = 1.0f / num_fl; + rad3 = num_fl_sqrt / num_fl; + + rng = BLI_rng_new(31415926 + (unsigned int)num); + + x = 0; + for (i = 0; i < num; i++) { + jitarr[i][0] = x + rad1 * (float)(0.5 - BLI_rng_get_double(rng)); + jitarr[i][1] = (float)i / num_fl + rad1 * (float)(0.5 - BLI_rng_get_double(rng)); + x += rad3; + x -= floorf(x); + } + + BLI_rng_free(rng); + + for (i = 0; i < 24; i++) { + BLI_jitterate1(jitarr, jit2, num, rad1); + BLI_jitterate1(jitarr, jit2, num, rad1); + BLI_jitterate2(jitarr, jit2, num, rad2); + } + + MEM_freeN(jit2); + + /* finally, move jittertab to be centered around (0, 0) */ + for (i = 0; i < num; i++) { + jitarr[i][0] -= 0.5f; + jitarr[i][1] -= 0.5f; + } +} diff --git a/source/blender/blenlib/intern/lasso.c b/source/blender/blenlib/intern/lasso.c deleted file mode 100644 index 710da09521a..00000000000 --- a/source/blender/blenlib/intern/lasso.c +++ /dev/null @@ -1,93 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * - * ***** END GPL LICENSE BLOCK ***** - * - */ - -/** \file blender/blenlib/intern/lasso.c - * \ingroup bli - */ - -#include "DNA_vec_types.h" - -#include "BLI_math.h" -#include "BLI_strict_flags.h" - -#include "BLI_lasso.h" /* own include */ - -void BLI_lasso_boundbox(rcti *rect, const int mcords[][2], const unsigned int moves) -{ - unsigned int a; - - rect->xmin = rect->xmax = mcords[0][0]; - rect->ymin = rect->ymax = mcords[0][1]; - - for (a = 1; a < moves; a++) { - if (mcords[a][0] < rect->xmin) rect->xmin = mcords[a][0]; - else if (mcords[a][0] > rect->xmax) rect->xmax = mcords[a][0]; - if (mcords[a][1] < rect->ymin) rect->ymin = mcords[a][1]; - else if (mcords[a][1] > rect->ymax) rect->ymax = mcords[a][1]; - } -} - - -bool BLI_lasso_is_point_inside(const int mcords[][2], const unsigned int moves, - const int sx, const int sy, - const int error_value) -{ - if (sx == error_value || moves == 0) { - return false; - } - else { - int pt[2] = {sx, sy}; - return isect_point_poly_v2_int(pt, mcords, moves, true); - } -} - -/* edge version for lasso select. we assume boundbox check was done */ -bool BLI_lasso_is_edge_inside(const int mcords[][2], const unsigned int moves, - int x0, int y0, int x1, int y1, - const int error_value) -{ - - if (x0 == error_value || x1 == error_value || moves == 0) { - return false; - } - - const int v1[2] = {x0, y0}, v2[2] = {x1, y1}; - - /* check points in lasso */ - if (BLI_lasso_is_point_inside(mcords, moves, v1[0], v1[1], error_value)) return true; - if (BLI_lasso_is_point_inside(mcords, moves, v2[0], v2[1], error_value)) return true; - - /* no points in lasso, so we have to intersect with lasso edge */ - - if (isect_seg_seg_v2_int(mcords[0], mcords[moves - 1], v1, v2) > 0) return true; - for (unsigned int a = 0; a < moves - 1; a++) { - if (isect_seg_seg_v2_int(mcords[a], mcords[a + 1], v1, v2) > 0) return true; - } - - return false; -} diff --git a/source/blender/blenlib/intern/lasso_2d.c b/source/blender/blenlib/intern/lasso_2d.c new file mode 100644 index 00000000000..663f3ffea22 --- /dev/null +++ b/source/blender/blenlib/intern/lasso_2d.c @@ -0,0 +1,93 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): none yet. + * + * ***** END GPL LICENSE BLOCK ***** + * + */ + +/** \file blender/blenlib/intern/lasso_2d.c + * \ingroup bli + */ + +#include "DNA_vec_types.h" + +#include "BLI_math.h" +#include "BLI_strict_flags.h" + +#include "BLI_lasso_2d.h" /* own include */ + +void BLI_lasso_boundbox(rcti *rect, const int mcords[][2], const unsigned int moves) +{ + unsigned int a; + + rect->xmin = rect->xmax = mcords[0][0]; + rect->ymin = rect->ymax = mcords[0][1]; + + for (a = 1; a < moves; a++) { + if (mcords[a][0] < rect->xmin) rect->xmin = mcords[a][0]; + else if (mcords[a][0] > rect->xmax) rect->xmax = mcords[a][0]; + if (mcords[a][1] < rect->ymin) rect->ymin = mcords[a][1]; + else if (mcords[a][1] > rect->ymax) rect->ymax = mcords[a][1]; + } +} + + +bool BLI_lasso_is_point_inside(const int mcords[][2], const unsigned int moves, + const int sx, const int sy, + const int error_value) +{ + if (sx == error_value || moves == 0) { + return false; + } + else { + int pt[2] = {sx, sy}; + return isect_point_poly_v2_int(pt, mcords, moves, true); + } +} + +/* edge version for lasso select. we assume boundbox check was done */ +bool BLI_lasso_is_edge_inside(const int mcords[][2], const unsigned int moves, + int x0, int y0, int x1, int y1, + const int error_value) +{ + + if (x0 == error_value || x1 == error_value || moves == 0) { + return false; + } + + const int v1[2] = {x0, y0}, v2[2] = {x1, y1}; + + /* check points in lasso */ + if (BLI_lasso_is_point_inside(mcords, moves, v1[0], v1[1], error_value)) return true; + if (BLI_lasso_is_point_inside(mcords, moves, v2[0], v2[1], error_value)) return true; + + /* no points in lasso, so we have to intersect with lasso edge */ + + if (isect_seg_seg_v2_int(mcords[0], mcords[moves - 1], v1, v2) > 0) return true; + for (unsigned int a = 0; a < moves - 1; a++) { + if (isect_seg_seg_v2_int(mcords[a], mcords[a + 1], v1, v2) > 0) return true; + } + + return false; +} diff --git a/source/blender/blenlib/intern/polyfill2d.c b/source/blender/blenlib/intern/polyfill2d.c deleted file mode 100644 index 018e2f9be5a..00000000000 --- a/source/blender/blenlib/intern/polyfill2d.c +++ /dev/null @@ -1,969 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file blender/blenlib/intern/polyfill2d.c - * \ingroup bli - * - * 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 - * - * Changes made for Blender. - * - * - loop the array to clip last verts first (less array resizing) - * - * - advance the ear to clip each iteration - * to avoid fan-filling convex shapes (USE_CLIP_EVEN). - * - * - avoid intersection tests when there are no convex points (USE_CONVEX_SKIP). - * - * \note - * - * No globals - keep threadsafe. - */ - -#include "BLI_utildefines.h" -#include "BLI_math.h" - -#include "BLI_memarena.h" -#include "BLI_alloca.h" - -#include "BLI_polyfill2d.h" /* own include */ - -#include "BLI_strict_flags.h" - -/* avoid fan-fill topology */ -#define USE_CLIP_EVEN -#define USE_CONVEX_SKIP -/* sweep back-and-forth about convex ears (avoids lop-sided fans) */ -#define USE_CLIP_SWEEP -// #define USE_CONVEX_SKIP_TEST - -#ifdef USE_CONVEX_SKIP -# define USE_KDTREE -#endif - -/* disable in production, it can fail on near zero area ngons */ -// #define USE_STRICT_ASSERT - -// #define DEBUG_TIME -#ifdef DEBUG_TIME -# include "PIL_time_utildefines.h" -#endif - - -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. - * - * - * - #KDTreeNode2D is kept small (only 16 bytes), - * by not storing coords in the nodes and using index values rather then pointers - * to reference neg/pos values. - * - * - #kdtree2d_isect_tri is the only function currently used. - * This simply intersects a triangle with the kdtree points. - * - * - the KDTree is only built & used when the polygon is concave. - */ - -typedef bool axis_t; - -/* use for sorting */ -typedef struct KDTreeNode2D_head { - uint neg, pos; - uint index; -} KDTreeNode2D_head; - -typedef struct KDTreeNode2D { - uint neg, pos; - uint index; - axis_t axis; /* range is only (0-1) */ - ushort flag; - uint parent; -} KDTreeNode2D; - -struct KDTree2D { - KDTreeNode2D *nodes; - const float (*coords)[2]; - uint root; - uint totnode; - uint *nodes_map; /* index -> node lookup */ -}; - -struct KDRange2D { - float min, max; -}; -#endif /* USE_KDTREE */ - -enum { - CONCAVE = -1, - TANGENTIAL = 0, - CONVEX = 1, -}; - -typedef struct PolyFill { - struct PolyIndex *indices; /* vertex aligned */ - - const float (*coords)[2]; - uint coords_tot; -#ifdef USE_CONVEX_SKIP - uint coords_tot_concave; -#endif - - /* A polygon with n vertices has a triangulation of n-2 triangles. */ - uint (*tris)[3]; - uint tris_tot; - -#ifdef USE_KDTREE - struct KDTree2D kdtree; -#endif -} PolyFill; - - -/* circular linklist */ -typedef struct PolyIndex { - struct PolyIndex *next, *prev; - uint index; - eSign sign; -} PolyIndex; - - -/* based on libgdx 2013-11-28, apache 2.0 licensed */ - -static void pf_coord_sign_calc(PolyFill *pf, PolyIndex *pi); - -static PolyIndex *pf_ear_tip_find( - PolyFill *pf -#ifdef USE_CLIP_EVEN - , PolyIndex *pi_ear_init -#endif -#ifdef USE_CLIP_SWEEP - , bool reverse -#endif - ); - -static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip); -static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip); - - -BLI_INLINE eSign signum_enum(float a) -{ - if (UNLIKELY(a == 0.0f)) - return 0; - else if (a > 0.0f) - return 1; - else - return -1; -} - -/** - * alternative version of #area_tri_signed_v2 - * needed because of float precision issues - * - * \note removes / 2 since its not needed since we only need the sign. - */ -BLI_INLINE float area_tri_signed_v2_alt_2x(const float v1[2], const float v2[2], const float v3[2]) -{ - return ((v1[0] * (v2[1] - v3[1])) + - (v2[0] * (v3[1] - v1[1])) + - (v3[0] * (v1[1] - v2[1]))); -} - - -static eSign span_tri_v2_sign(const float v1[2], const float v2[2], const float v3[2]) -{ - return signum_enum(area_tri_signed_v2_alt_2x(v3, v2, v1)); -} - - -#ifdef USE_KDTREE -#define KDNODE_UNSET ((uint)-1) - -enum { - KDNODE_FLAG_REMOVED = (1 << 0), -}; - -static void kdtree2d_new( - struct KDTree2D *tree, - uint tot, - const float (*coords)[2]) -{ - /* set by caller */ - // tree->nodes = nodes; - tree->coords = coords; - tree->root = KDNODE_UNSET; - tree->totnode = tot; -} - -/** - * no need for kdtree2d_insert, since we know the coords array. - */ -static void kdtree2d_init( - struct KDTree2D *tree, - const uint coords_tot, - const PolyIndex *indices) -{ - KDTreeNode2D *node; - uint i; - - for (i = 0, node = tree->nodes; i < coords_tot; i++) { - if (indices[i].sign != CONVEX) { - node->neg = node->pos = KDNODE_UNSET; - node->index = indices[i].index; - node->axis = 0; - node->flag = 0; - node++; - } - } - - BLI_assert(tree->totnode == (uint)(node - tree->nodes)); -} - -static uint kdtree2d_balance_recursive( - KDTreeNode2D *nodes, uint totnode, axis_t axis, - const float (*coords)[2], const uint ofs) -{ - KDTreeNode2D *node; - uint neg, pos, median, i, j; - - if (totnode <= 0) { - return KDNODE_UNSET; - } - else if (totnode == 1) { - return 0 + ofs; - } - - /* quicksort style sorting around median */ - neg = 0; - pos = totnode - 1; - median = totnode / 2; - - while (pos > neg) { - const float co = coords[nodes[pos].index][axis]; - i = neg - 1; - j = pos; - - while (1) { - while (coords[nodes[++i].index][axis] < co) ; - while (coords[nodes[--j].index][axis] > co && j > neg) ; - - if (i >= j) { - break; - } - SWAP(KDTreeNode2D_head, *(KDTreeNode2D_head *)&nodes[i], *(KDTreeNode2D_head *)&nodes[j]); - } - - SWAP(KDTreeNode2D_head, *(KDTreeNode2D_head *)&nodes[i], *(KDTreeNode2D_head *)&nodes[pos]); - if (i >= median) { - pos = i - 1; - } - if (i <= median) { - neg = i + 1; - } - } - - /* set node and sort subnodes */ - node = &nodes[median]; - node->axis = axis; - axis = !axis; - node->neg = kdtree2d_balance_recursive(nodes, median, axis, coords, ofs); - node->pos = kdtree2d_balance_recursive(&nodes[median + 1], (totnode - (median + 1)), axis, coords, (median + 1) + ofs); - - return median + ofs; -} - -static void kdtree2d_balance( - struct KDTree2D *tree) -{ - tree->root = kdtree2d_balance_recursive(tree->nodes, tree->totnode, 0, tree->coords, 0); -} - - -static void kdtree2d_init_mapping( - struct KDTree2D *tree) -{ - uint i; - KDTreeNode2D *node; - - for (i = 0, node = tree->nodes; i < tree->totnode; i++, node++) { - if (node->neg != KDNODE_UNSET) { - tree->nodes[node->neg].parent = i; - } - if (node->pos != KDNODE_UNSET) { - tree->nodes[node->pos].parent = i; - } - - /* build map */ - BLI_assert(tree->nodes_map[node->index] == KDNODE_UNSET); - tree->nodes_map[node->index] = i; - } - - tree->nodes[tree->root].parent = KDNODE_UNSET; -} - -static void kdtree2d_node_remove( - struct KDTree2D *tree, - uint index) -{ - uint node_index = tree->nodes_map[index]; - KDTreeNode2D *node; - - if (node_index == KDNODE_UNSET) { - return; - } - else { - tree->nodes_map[index] = KDNODE_UNSET; - } - - node = &tree->nodes[node_index]; - tree->totnode -= 1; - - BLI_assert((node->flag & KDNODE_FLAG_REMOVED) == 0); - node->flag |= KDNODE_FLAG_REMOVED; - - while ((node->neg == KDNODE_UNSET) && - (node->pos == KDNODE_UNSET) && - (node->parent != KDNODE_UNSET)) - { - KDTreeNode2D *node_parent = &tree->nodes[node->parent]; - - BLI_assert((uint)(node - tree->nodes) == node_index); - if (node_parent->neg == node_index) { - node_parent->neg = KDNODE_UNSET; - } - else { - BLI_assert(node_parent->pos == node_index); - node_parent->pos = KDNODE_UNSET; - } - - if (node_parent->flag & KDNODE_FLAG_REMOVED) { - node_index = node->parent; - node = node_parent; - } - else { - break; - } - } -} - -static bool kdtree2d_isect_tri_recursive( - const struct KDTree2D *tree, - const uint tri_index[3], - const float *tri_coords[3], - const float tri_center[2], - const struct KDRange2D bounds[2], - const KDTreeNode2D *node) -{ - const float *co = tree->coords[node->index]; - - /* bounds then triangle intersect */ - if ((node->flag & KDNODE_FLAG_REMOVED) == 0) { - /* bounding box test first */ - if ((co[0] >= bounds[0].min) && - (co[0] <= bounds[0].max) && - (co[1] >= bounds[1].min) && - (co[1] <= bounds[1].max)) - { - if ((span_tri_v2_sign(tri_coords[0], tri_coords[1], co) != CONCAVE) && - (span_tri_v2_sign(tri_coords[1], tri_coords[2], co) != CONCAVE) && - (span_tri_v2_sign(tri_coords[2], tri_coords[0], co) != CONCAVE)) - { - if (!ELEM(node->index, tri_index[0], tri_index[1], tri_index[2])) { - return true; - } - } - } - } - -#define KDTREE2D_ISECT_TRI_RECURSE_NEG \ - (((node->neg != KDNODE_UNSET) && (co[node->axis] >= bounds[node->axis].min)) && \ - (kdtree2d_isect_tri_recursive(tree, tri_index, tri_coords, tri_center, bounds, \ - &tree->nodes[node->neg]))) -#define KDTREE2D_ISECT_TRI_RECURSE_POS \ - (((node->pos != KDNODE_UNSET) && (co[node->axis] <= bounds[node->axis].max)) && \ - (kdtree2d_isect_tri_recursive(tree, tri_index, tri_coords, tri_center, bounds, \ - &tree->nodes[node->pos]))) - - if (tri_center[node->axis] > co[node->axis]) { - if (KDTREE2D_ISECT_TRI_RECURSE_POS) { - return true; - } - if (KDTREE2D_ISECT_TRI_RECURSE_NEG) { - return true; - } - } - else { - if (KDTREE2D_ISECT_TRI_RECURSE_NEG) { - return true; - } - if (KDTREE2D_ISECT_TRI_RECURSE_POS) { - return true; - } - } - -#undef KDTREE2D_ISECT_TRI_RECURSE_NEG -#undef KDTREE2D_ISECT_TRI_RECURSE_POS - - BLI_assert(node->index != KDNODE_UNSET); - - return false; -} - -static bool kdtree2d_isect_tri( - struct KDTree2D *tree, - const uint ind[3]) -{ - const float *vs[3]; - uint i; - struct KDRange2D bounds[2] = { - {FLT_MAX, -FLT_MAX}, - {FLT_MAX, -FLT_MAX}, - }; - float tri_center[2] = {0.0f, 0.0f}; - - for (i = 0; i < 3; i++) { - vs[i] = tree->coords[ind[i]]; - - add_v2_v2(tri_center, vs[i]); - - CLAMP_MAX(bounds[0].min, vs[i][0]); - CLAMP_MIN(bounds[0].max, vs[i][0]); - CLAMP_MAX(bounds[1].min, vs[i][1]); - CLAMP_MIN(bounds[1].max, vs[i][1]); - } - - mul_v2_fl(tri_center, 1.0f / 3.0f); - - return kdtree2d_isect_tri_recursive(tree, ind, vs, tri_center, bounds, &tree->nodes[tree->root]); -} - -#endif /* USE_KDTREE */ - - -static uint *pf_tri_add(PolyFill *pf) -{ - return pf->tris[pf->tris_tot++]; -} - -static void pf_coord_remove(PolyFill *pf, PolyIndex *pi) -{ -#ifdef USE_KDTREE - /* avoid double lookups, since convex coords are ignored when testing intersections */ - if (pf->kdtree.totnode) { - kdtree2d_node_remove(&pf->kdtree, pi->index); - } -#endif - - pi->next->prev = pi->prev; - pi->prev->next = pi->next; - - if (UNLIKELY(pf->indices == pi)) { - pf->indices = pi->next; - } -#ifdef DEBUG - pi->index = (uint)-1; - pi->next = pi->prev = NULL; -#endif - - pf->coords_tot -= 1; -} - -static void pf_triangulate(PolyFill *pf) -{ - /* localize */ - PolyIndex *pi_ear; - -#ifdef USE_CLIP_EVEN - PolyIndex *pi_ear_init = pf->indices; -#endif -#ifdef USE_CLIP_SWEEP - bool reverse = false; -#endif - - while (pf->coords_tot > 3) { - PolyIndex *pi_prev, *pi_next; - eSign sign_orig_prev, sign_orig_next; - - pi_ear = pf_ear_tip_find( - pf -#ifdef USE_CLIP_EVEN - , pi_ear_init -#endif -#ifdef USE_CLIP_SWEEP - , reverse -#endif - ); - -#ifdef USE_CONVEX_SKIP - if (pi_ear->sign != CONVEX) { - pf->coords_tot_concave -= 1; - } -#endif - - pi_prev = pi_ear->prev; - pi_next = pi_ear->next; - - pf_ear_tip_cut(pf, pi_ear); - - /* The type of the two vertices adjacent to the clipped vertex may have changed. */ - sign_orig_prev = pi_prev->sign; - sign_orig_next = pi_next->sign; - - /* check if any verts became convex the (else if) - * case is highly unlikely but may happen with degenerate polygons */ - if (sign_orig_prev != CONVEX) { - pf_coord_sign_calc(pf, pi_prev); -#ifdef USE_CONVEX_SKIP - if (pi_prev->sign == CONVEX) { - pf->coords_tot_concave -= 1; -#ifdef USE_KDTREE - kdtree2d_node_remove(&pf->kdtree, pi_prev->index); -#endif - } -#endif - } - if (sign_orig_next != CONVEX) { - pf_coord_sign_calc(pf, pi_next); -#ifdef USE_CONVEX_SKIP - if (pi_next->sign == CONVEX) { - pf->coords_tot_concave -= 1; -#ifdef USE_KDTREE - kdtree2d_node_remove(&pf->kdtree, pi_next->index); -#endif - } -#endif - } - -#ifdef USE_CLIP_EVEN -#ifdef USE_CLIP_SWEEP - pi_ear_init = reverse ? pi_prev->prev : pi_next->next; -#else - pi_ear_init = pi_next->next; -#endif -#endif - -#ifdef USE_CLIP_EVEN -#ifdef USE_CLIP_SWEEP - if (pi_ear_init->sign != CONVEX) { - /* take the extra step since this ear isn't a good candidate */ - pi_ear_init = reverse ? pi_ear_init->prev : pi_ear_init->next; - reverse = !reverse; - } -#endif -#else - if ((reverse ? pi_prev->prev : pi_next->next)->sign != CONVEX) { - reverse = !reverse; - } -#endif - - } - - if (pf->coords_tot == 3) { - uint *tri = pf_tri_add(pf); - pi_ear = pf->indices; - tri[0] = pi_ear->index; pi_ear = pi_ear->next; - tri[1] = pi_ear->index; pi_ear = pi_ear->next; - tri[2] = pi_ear->index; - } -} - -/** - * \return CONCAVE, TANGENTIAL or CONVEX - */ -static void pf_coord_sign_calc(PolyFill *pf, PolyIndex *pi) -{ - /* localize */ - const float (*coords)[2] = pf->coords; - - pi->sign = span_tri_v2_sign( - coords[pi->prev->index], - coords[pi->index], - coords[pi->next->index]); -} - -static PolyIndex *pf_ear_tip_find( - PolyFill *pf -#ifdef USE_CLIP_EVEN - , PolyIndex *pi_ear_init -#endif -#ifdef USE_CLIP_SWEEP - , bool reverse -#endif - ) -{ - /* localize */ - const uint coords_tot = pf->coords_tot; - PolyIndex *pi_ear; - - uint i; - -#ifdef USE_CLIP_EVEN - pi_ear = pi_ear_init; -#else - pi_ear = pf->indices; -#endif - - i = coords_tot; - while (i--) { - if (pf_ear_tip_check(pf, pi_ear)) { - return pi_ear; - } -#ifdef USE_CLIP_SWEEP - pi_ear = reverse ? pi_ear->prev : pi_ear->next; -#else - pi_ear = pi_ear->next; -#endif - } - - /* Desperate mode: if no vertex is an ear tip, we are dealing with a degenerate polygon (e.g. nearly collinear). - * Note that the input was not necessarily degenerate, but we could have made it so by clipping some valid ears. - * - * Idea taken from Martin Held, "FIST: Fast industrial-strength triangulation of polygons", Algorithmica (1998), - * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.291 - * - * Return a convex or tangential vertex if one exists. - */ - -#ifdef USE_CLIP_EVEN - pi_ear = pi_ear_init; -#else - pi_ear = pf->indices; -#endif - - i = coords_tot; - while (i--) { - if (pi_ear->sign != CONCAVE) { - return pi_ear; - } - pi_ear = pi_ear->next; - } - - /* If all vertices are concave, just return the last one. */ - return pi_ear; -} - -static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip) -{ -#ifndef USE_KDTREE - /* localize */ - const float (*coords)[2] = pf->coords; - PolyIndex *pi_curr; - - const float *v1, *v2, *v3; -#endif - -#if defined(USE_CONVEX_SKIP) && !defined(USE_KDTREE) - uint coords_tot_concave_checked = 0; -#endif - - -#ifdef USE_CONVEX_SKIP - -#ifdef USE_CONVEX_SKIP_TEST - /* check if counting is wrong */ - { - uint coords_tot_concave_test = 0; - PolyIndex *pi_iter = pi_ear_tip; - do { - if (pi_iter->sign != CONVEX) { - coords_tot_concave_test += 1; - } - } while ((pi_iter = pi_iter->next) != pi_ear_tip); - BLI_assert(coords_tot_concave_test == pf->coords_tot_concave); - } -#endif - - /* fast-path for circles */ - if (pf->coords_tot_concave == 0) { - return true; - } -#endif - - if (UNLIKELY(pi_ear_tip->sign == CONCAVE)) { - return false; - } - -#ifdef USE_KDTREE - { - const uint ind[3] = { - pi_ear_tip->index, - pi_ear_tip->next->index, - pi_ear_tip->prev->index}; - - if (kdtree2d_isect_tri(&pf->kdtree, ind)) { - return false; - } - } -#else - - v1 = coords[pi_ear_tip->prev->index]; - v2 = coords[pi_ear_tip->index]; - v3 = coords[pi_ear_tip->next->index]; - - /* Check if any point is inside the triangle formed by previous, current and next vertices. - * Only consider vertices that are not part of this triangle, or else we'll always find one inside. */ - - for (pi_curr = pi_ear_tip->next->next; pi_curr != pi_ear_tip->prev; pi_curr = pi_curr->next) { - /* Concave vertices can obviously be inside the candidate ear, but so can tangential vertices - * if they coincide with one of the triangle's vertices. */ - if (pi_curr->sign != CONVEX) { - const float *v = coords[pi_curr->index]; - /* Because the polygon has clockwise winding order, - * the area sign will be positive if the point is strictly inside. - * It will be 0 on the edge, which we want to include as well. */ - - /* note: check (v3, v1) first since it fails _far_ more often then the other 2 checks (those fail equally). - * It's logical - the chance is low that points exist on the same side as the ear we're clipping off. */ - if ((span_tri_v2_sign(v3, v1, v) != CONCAVE) && - (span_tri_v2_sign(v1, v2, v) != CONCAVE) && - (span_tri_v2_sign(v2, v3, v) != CONCAVE)) - { - return false; - } - -#ifdef USE_CONVEX_SKIP - coords_tot_concave_checked += 1; - if (coords_tot_concave_checked == pf->coords_tot_concave) { - break; - } -#endif - } - } -#endif /* USE_KDTREE */ - - return true; -} - -static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip) -{ - uint *tri = pf_tri_add(pf); - - tri[0] = pi_ear_tip->prev->index; - tri[1] = pi_ear_tip->index; - tri[2] = pi_ear_tip->next->index; - - pf_coord_remove(pf, pi_ear_tip); -} - -/** - * Initializes the #PolyFill structure before tessellating with #polyfill_calc. - */ -static void polyfill_prepare( - PolyFill *pf, - const float (*coords)[2], - const uint coords_tot, - int coords_sign, - uint (*r_tris)[3], - PolyIndex *r_indices) -{ - /* localize */ - PolyIndex *indices = r_indices; - - uint i; - - /* assign all polyfill members here */ - pf->indices = r_indices; - pf->coords = coords; - pf->coords_tot = coords_tot; -#ifdef USE_CONVEX_SKIP - pf->coords_tot_concave = 0; -#endif - pf->tris = r_tris; - pf->tris_tot = 0; - - if (coords_sign == 0) { - coords_sign = (cross_poly_v2(coords, coords_tot) >= 0.0f) ? 1 : -1; - } - else { - /* check we're passing in correcty args */ -#ifdef USE_STRICT_ASSERT -#ifndef NDEBUG - if (coords_sign == 1) { - BLI_assert(cross_poly_v2(coords, coords_tot) >= 0.0f); - } - else { - BLI_assert(cross_poly_v2(coords, coords_tot) <= 0.0f); - } -#endif -#endif - } - - if (coords_sign == 1) { - for (i = 0; i < coords_tot; i++) { - indices[i].next = &indices[i + 1]; - indices[i].prev = &indices[i - 1]; - indices[i].index = i; - } - } - else { - /* reversed */ - uint n = coords_tot - 1; - for (i = 0; i < coords_tot; i++) { - indices[i].next = &indices[i + 1]; - indices[i].prev = &indices[i - 1]; - indices[i].index = (n - i); - } - } - indices[0].prev = &indices[coords_tot - 1]; - indices[coords_tot - 1].next = &indices[0]; - - for (i = 0; i < coords_tot; i++) { - PolyIndex *pi = &indices[i]; - pf_coord_sign_calc(pf, pi); -#ifdef USE_CONVEX_SKIP - if (pi->sign != CONVEX) { - pf->coords_tot_concave += 1; - } -#endif - } -} - -static void polyfill_calc( - PolyFill *pf) -{ -#ifdef USE_KDTREE -#ifdef USE_CONVEX_SKIP - if (pf->coords_tot_concave) -#endif - { - kdtree2d_new(&pf->kdtree, pf->coords_tot_concave, pf->coords); - kdtree2d_init(&pf->kdtree, pf->coords_tot, pf->indices); - kdtree2d_balance(&pf->kdtree); - kdtree2d_init_mapping(&pf->kdtree); - } -#endif - - pf_triangulate(pf); -} - -/** - * A version of #BLI_polyfill_calc that uses a memory arena to avoid re-allocations. - */ -void BLI_polyfill_calc_arena( - const float (*coords)[2], - const uint coords_tot, - const int coords_sign, - uint (*r_tris)[3], - - struct MemArena *arena) -{ - PolyFill pf; - PolyIndex *indices = BLI_memarena_alloc(arena, sizeof(*indices) * coords_tot); - -#ifdef DEBUG_TIME - TIMEIT_START(polyfill2d); -#endif - - polyfill_prepare( - &pf, - coords, coords_tot, coords_sign, - r_tris, - /* cache */ - indices); - -#ifdef USE_KDTREE - if (pf.coords_tot_concave) { - pf.kdtree.nodes = BLI_memarena_alloc(arena, sizeof(*pf.kdtree.nodes) * pf.coords_tot_concave); - pf.kdtree.nodes_map = memset(BLI_memarena_alloc(arena, sizeof(*pf.kdtree.nodes_map) * coords_tot), - 0xff, sizeof(*pf.kdtree.nodes_map) * coords_tot); - } - else { - pf.kdtree.totnode = 0; - } -#endif - - polyfill_calc(&pf); - - /* indices are no longer needed, - * caller can clear arena */ - -#ifdef DEBUG_TIME - TIMEIT_END(polyfill2d); -#endif -} - -/** - * Triangulates the given (convex or concave) simple polygon to a list of triangle vertices. - * - * \param coords: 2D coordinates describing vertices of the polygon, - * in either clockwise or counterclockwise order. - * \param coords_tot: Total points in the array. - * \param coords_sign: Pass this when we know the sign in advance to avoid extra calculations. - * - * \param r_tris: This array is filled in with triangle indices in clockwise order. - * The length of the array must be ``coords_tot - 2``. - * Indices are guaranteed to be assigned to unique triangles, with valid indices, - * even in the case of degenerate input (self intersecting polygons, zero area ears... etc). - */ -void BLI_polyfill_calc( - const float (*coords)[2], - const uint coords_tot, - const int coords_sign, - uint (*r_tris)[3]) -{ - PolyFill pf; - PolyIndex *indices = BLI_array_alloca(indices, coords_tot); - -#ifdef DEBUG_TIME - TIMEIT_START(polyfill2d); -#endif - - polyfill_prepare( - &pf, - coords, coords_tot, coords_sign, - r_tris, - /* cache */ - indices); - -#ifdef USE_KDTREE - if (pf.coords_tot_concave) { - pf.kdtree.nodes = BLI_array_alloca(pf.kdtree.nodes, pf.coords_tot_concave); - pf.kdtree.nodes_map = memset(BLI_array_alloca(pf.kdtree.nodes_map, coords_tot), - 0xff, sizeof(*pf.kdtree.nodes_map) * coords_tot); - } - else { - pf.kdtree.totnode = 0; - } -#endif - - polyfill_calc(&pf); - -#ifdef DEBUG_TIME - TIMEIT_END(polyfill2d); -#endif -} diff --git a/source/blender/blenlib/intern/polyfill2d_beautify.c b/source/blender/blenlib/intern/polyfill2d_beautify.c deleted file mode 100644 index 625c54d0e9b..00000000000 --- a/source/blender/blenlib/intern/polyfill2d_beautify.c +++ /dev/null @@ -1,439 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file blender/blenlib/intern/polyfill2d_beautify.c - * \ingroup bli - * - * This function is to improve the tessellation resulting from polyfill2d, - * creating optimal topology. - * - * The functionality here matches #BM_mesh_beautify_fill, - * but its far simpler to perform this operation in 2d, - * on a simple polygon representation where we _know_: - * - * - The polygon is primitive with no holes with a continuous boundary. - * - Tris have consistent winding. - * - 2d (saves some hassles projecting face pairs on an axis for every edge-rotation) - * also saves us having to store all previous edge-states (see #EdRotState in bmesh_beautify.c) - * - * \note - * - * No globals - keep threadsafe. - */ - -#include "BLI_utildefines.h" -#include "BLI_math.h" - -#include "BLI_memarena.h" -#include "BLI_heap.h" - -#include "BLI_polyfill2d_beautify.h" /* own include */ - -#include "BLI_strict_flags.h" - -/* Used to find matching edges. */ -struct OrderEdge { - uint verts[2]; - uint e_half; -}; - -/* Half edge used for rotating in-place. */ -struct HalfEdge { - uint v; - uint e_next; - uint e_radial; - uint base_index; -}; - -static int oedge_cmp(const void *a1, const void *a2) -{ - const struct OrderEdge *x1 = a1, *x2 = a2; - if (x1->verts[0] > x2->verts[0]) { - return 1; - } - else if (x1->verts[0] < x2->verts[0]) { - return -1; - } - - if (x1->verts[1] > x2->verts[1]) { - return 1; - } - else if (x1->verts[1] < x2->verts[1]) { - return -1; - } - - /* only for pradictability */ - if (x1->e_half > x2->e_half) { - return 1; - } - else if (x1->e_half < x2->e_half) { - return -1; - } - /* Should never get here, no two edges should be the same. */ - BLI_assert(false); - return 0; -} - -BLI_INLINE bool is_boundary_edge(uint i_a, uint i_b, const uint coord_last) -{ - BLI_assert(i_a < i_b); - return ((i_a + 1 == i_b) || UNLIKELY((i_a == 0) && (i_b == coord_last))); -} -/** - * Assuming we have 2 triangles sharing an edge (2 - 4), - * check if the edge running from (1 - 3) gives better results. - * - * \param lock_degenerate: Use to avoid rotating out of a degenerate state. - * - When true, an existing zero area face on either side of the (2 - 4) split will return a positive value. - * - When false, the check must be non-biased towards either split direction. - * - * \return (negative number means the edge can be rotated, lager == better). - */ -float BLI_polyfill_beautify_quad_rotate_calc_ex( - const float v1[2], const float v2[2], const float v3[2], const float v4[2], - const bool lock_degenerate) -{ - /* not a loop (only to be able to break out) */ - do { - /* Allow very small faces to be considered non-zero. */ - const float eps_zero_area = 1e-12f; - const float area_2x_234 = cross_tri_v2(v2, v3, v4); - const float area_2x_241 = cross_tri_v2(v2, v4, v1); - - const float area_2x_123 = cross_tri_v2(v1, v2, v3); - const float area_2x_134 = cross_tri_v2(v1, v3, v4); - - BLI_assert((ELEM(v1, v2, v3, v4) == false) && - (ELEM(v2, v1, v3, v4) == false) && - (ELEM(v3, v1, v2, v4) == false) && - (ELEM(v4, v1, v2, v3) == false)); - /* - * Test for unusable (1-3) state. - * - Area sign flipping to check faces aren't going to point in opposite directions. - * - Area epsilon check that the one of the faces won't be zero area. - */ - if ((area_2x_123 >= 0.0f) != (area_2x_134 >= 0.0f)) { - break; - } - else if ((fabsf(area_2x_123) <= eps_zero_area) || (fabsf(area_2x_134) <= eps_zero_area)) { - break; - } - - /* Test for unusable (2-4) state (same as above). */ - if ((area_2x_234 >= 0.0f) != (area_2x_241 >= 0.0f)) { - if (lock_degenerate) { - break; - } - else { - return -FLT_MAX; /* always rotate */ - } - } - else if ((fabsf(area_2x_234) <= eps_zero_area) || (fabsf(area_2x_241) <= eps_zero_area)) { - return -FLT_MAX; /* always rotate */ - } - - { - /* testing rule: the area divided by the perimeter, - * check if (1-3) beats the existing (2-4) edge rotation */ - float area_a, area_b; - float prim_a, prim_b; - float fac_24, fac_13; - - float len_12, len_23, len_34, len_41, len_24, len_13; - - /* edges around the quad */ - len_12 = len_v2v2(v1, v2); - len_23 = len_v2v2(v2, v3); - len_34 = len_v2v2(v3, v4); - len_41 = len_v2v2(v4, v1); - /* edges crossing the quad interior */ - len_13 = len_v2v2(v1, v3); - len_24 = len_v2v2(v2, v4); - - /* note, area is in fact (area * 2), - * but in this case its OK, since we're comparing ratios */ - - /* edge (2-4), current state */ - area_a = fabsf(area_2x_234); - area_b = fabsf(area_2x_241); - prim_a = len_23 + len_34 + len_24; - prim_b = len_41 + len_12 + len_24; - fac_24 = (area_a / prim_a) + (area_b / prim_b); - - /* edge (1-3), new state */ - area_a = fabsf(area_2x_123); - area_b = fabsf(area_2x_134); - prim_a = len_12 + len_23 + len_13; - prim_b = len_34 + len_41 + len_13; - fac_13 = (area_a / prim_a) + (area_b / prim_b); - - /* negative number if (1-3) is an improved state */ - return fac_24 - fac_13; - } - } while (false); - - return FLT_MAX; -} - -static float polyedge_rotate_beauty_calc( - const float (*coords)[2], - const struct HalfEdge *edges, - const struct HalfEdge *e_a) -{ - const struct HalfEdge *e_b = &edges[e_a->e_radial]; - - const struct HalfEdge *e_a_other = &edges[edges[e_a->e_next].e_next]; - const struct HalfEdge *e_b_other = &edges[edges[e_b->e_next].e_next]; - - const float *v1, *v2, *v3, *v4; - - v1 = coords[e_a_other->v]; - v2 = coords[e_a->v]; - v3 = coords[e_b_other->v]; - v4 = coords[e_b->v]; - - return BLI_polyfill_beautify_quad_rotate_calc(v1, v2, v3, v4); -} - -static void polyedge_beauty_cost_update_single( - const float (*coords)[2], - const struct HalfEdge *edges, - struct HalfEdge *e, - Heap *eheap, HeapNode **eheap_table) -{ - const uint i = e->base_index; - /* recalculate edge */ - const float cost = polyedge_rotate_beauty_calc(coords, edges, e); - /* We can get cases where both choices generate very small negative costs, which leads to infinite loop. - * Anyway, costs above that are not worth recomputing, maybe we could even optimize it to a smaller limit? - * Actually, FLT_EPSILON is too small in some cases, 1e-6f seems to work OK hopefully? - * See T43578, T49478. */ - if (cost < -1e-6f) { - BLI_heap_insert_or_update(eheap, &eheap_table[i], cost, e); - } - else { - if (eheap_table[i]) { - BLI_heap_remove(eheap, eheap_table[i]); - eheap_table[i] = NULL; - } - } -} - -static void polyedge_beauty_cost_update( - const float (*coords)[2], - struct HalfEdge *edges, - struct HalfEdge *e, - Heap *eheap, HeapNode **eheap_table) -{ - struct HalfEdge *e_arr[4]; - e_arr[0] = &edges[e->e_next]; - e_arr[1] = &edges[e_arr[0]->e_next]; - - e = &edges[e->e_radial]; - e_arr[2] = &edges[e->e_next]; - e_arr[3] = &edges[e_arr[2]->e_next]; - - for (uint i = 0; i < 4; i++) { - if (e_arr[i] && e_arr[i]->base_index != UINT_MAX) { - polyedge_beauty_cost_update_single( - coords, edges, - e_arr[i], - eheap, eheap_table); - } - } -} - -static void polyedge_rotate( - struct HalfEdge *edges, - struct HalfEdge *e) -{ - /** CCW winding, rotate internal edge to new vertical state. - * 
-	 *   Before         After
-	 *      X             X
-	 *     / \           /|\
-	 *  e4/   \e5     e4/ | \e5
-	 *   / e3  \       /  |  \
-	 * X ------- X -> X e0|e3 X
-	 *   \ e0  /       \  |  /
-	 *  e2\   /e1     e2\ | /e1
-	 *     \ /           \|/
-	 *      X             X
-	 *
- */ - struct HalfEdge *ed[6]; - uint ed_index[6]; - - ed_index[0] = (uint)(e - edges); - ed[0] = &edges[ed_index[0]]; - ed_index[1] = ed[0]->e_next; - ed[1] = &edges[ed_index[1]]; - ed_index[2] = ed[1]->e_next; - ed[2] = &edges[ed_index[2]]; - - ed_index[3] = e->e_radial; - ed[3] = &edges[ed_index[3]]; - ed_index[4] = ed[3]->e_next; - ed[4] = &edges[ed_index[4]]; - ed_index[5] = ed[4]->e_next; - ed[5] = &edges[ed_index[5]]; - - ed[0]->e_next = ed_index[2]; - ed[1]->e_next = ed_index[3]; - ed[2]->e_next = ed_index[4]; - ed[3]->e_next = ed_index[5]; - ed[4]->e_next = ed_index[0]; - ed[5]->e_next = ed_index[1]; - - ed[0]->v = ed[5]->v; - ed[3]->v = ed[2]->v; -} - -/** - * The intention is that this calculates the output of #BLI_polyfill_calc - * - * - * \note assumes the \a coords form a boundary, - * so any edges running along contiguous (wrapped) indices, - * are ignored since the edges wont share 2 faces. - */ -void BLI_polyfill_beautify( - const float (*coords)[2], - const uint coords_tot, - uint (*tris)[3], - - /* structs for reuse */ - MemArena *arena, Heap *eheap) -{ - const uint coord_last = coords_tot - 1; - const uint tris_len = coords_tot - 2; - /* internal edges only (between 2 tris) */ - const uint edges_len = tris_len - 1; - - HeapNode **eheap_table; - - const uint half_edges_len = 3 * tris_len; - struct HalfEdge *half_edges = BLI_memarena_alloc(arena, sizeof(*half_edges) * half_edges_len); - struct OrderEdge *order_edges = BLI_memarena_alloc(arena, sizeof(struct OrderEdge) * 2 * edges_len); - uint order_edges_len = 0; - - /* first build edges */ - for (uint i = 0; i < tris_len; i++) { - for (uint j_curr = 0, j_prev = 2; j_curr < 3; j_prev = j_curr++) { - const uint e_index_prev = (i * 3) + j_prev; - const uint e_index_curr = (i * 3) + j_curr; - - half_edges[e_index_prev].v = tris[i][j_prev]; - half_edges[e_index_prev].e_next = e_index_curr; - half_edges[e_index_prev].e_radial = UINT_MAX; - half_edges[e_index_prev].base_index = UINT_MAX; - - uint e_pair[2] = {tris[i][j_prev], tris[i][j_curr]}; - if (e_pair[0] > e_pair[1]) { - SWAP(uint, e_pair[0], e_pair[1]); - } - - /* ensure internal edges. */ - if (!is_boundary_edge(e_pair[0], e_pair[1], coord_last)) { - order_edges[order_edges_len].verts[0] = e_pair[0]; - order_edges[order_edges_len].verts[1] = e_pair[1]; - order_edges[order_edges_len].e_half = e_index_prev; - order_edges_len += 1; - } - } - } - BLI_assert(edges_len * 2 == order_edges_len); - - qsort(order_edges, order_edges_len, sizeof(struct OrderEdge), oedge_cmp); - - for (uint i = 0, base_index = 0; i < order_edges_len; base_index++) { - const struct OrderEdge *oe_a = &order_edges[i++]; - const struct OrderEdge *oe_b = &order_edges[i++]; - BLI_assert(oe_a->verts[0] == oe_a->verts[0] && oe_a->verts[1] == oe_a->verts[1]); - half_edges[oe_a->e_half].e_radial = oe_b->e_half; - half_edges[oe_b->e_half].e_radial = oe_a->e_half; - half_edges[oe_a->e_half].base_index = base_index; - half_edges[oe_b->e_half].base_index = base_index; - } - /* order_edges could be freed now. */ - - /* Now perform iterative rotations. */ -#if 0 - eheap_table = BLI_memarena_alloc(arena, sizeof(HeapNode *) * (size_t)edges_len); -#else - /* We can re-use this since its big enough. */ - eheap_table = (void *)order_edges; - order_edges = NULL; -#endif - - /* Build heap. */ - { - struct HalfEdge *e = half_edges; - for (uint i = 0; i < half_edges_len; i++, e++) { - /* Accounts for boundary edged too (UINT_MAX). */ - if (e->e_radial < i) { - const float cost = polyedge_rotate_beauty_calc(coords, half_edges, e); - if (cost < 0.0f) { - eheap_table[e->base_index] = BLI_heap_insert(eheap, cost, e); - } - else { - eheap_table[e->base_index] = NULL; - } - } - } - } - - while (BLI_heap_is_empty(eheap) == false) { - struct HalfEdge *e = BLI_heap_pop_min(eheap); - eheap_table[e->base_index] = NULL; - - polyedge_rotate(half_edges, e); - - /* recalculate faces connected on the heap */ - polyedge_beauty_cost_update( - coords, half_edges, - e, - eheap, eheap_table); - } - - BLI_heap_clear(eheap, NULL); - - /* MEM_freeN(eheap_table); */ /* arena */ - - /* get tris from half edge. */ - uint tri_index = 0; - for (uint i = 0; i < half_edges_len; i++) { - struct HalfEdge *e = &half_edges[i]; - if (e->v != UINT_MAX) { - uint *tri = tris[tri_index++]; - - tri[0] = e->v; - e->v = UINT_MAX; - - e = &half_edges[e->e_next]; - tri[1] = e->v; - e->v = UINT_MAX; - - e = &half_edges[e->e_next]; - tri[2] = e->v; - e->v = UINT_MAX; - } - } -} diff --git a/source/blender/blenlib/intern/polyfill_2d.c b/source/blender/blenlib/intern/polyfill_2d.c new file mode 100644 index 00000000000..8c0870f0c07 --- /dev/null +++ b/source/blender/blenlib/intern/polyfill_2d.c @@ -0,0 +1,969 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenlib/intern/polyfill_2d.c + * \ingroup bli + * + * 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 + * + * Changes made for Blender. + * + * - loop the array to clip last verts first (less array resizing) + * + * - advance the ear to clip each iteration + * to avoid fan-filling convex shapes (USE_CLIP_EVEN). + * + * - avoid intersection tests when there are no convex points (USE_CONVEX_SKIP). + * + * \note + * + * No globals - keep threadsafe. + */ + +#include "BLI_utildefines.h" +#include "BLI_math.h" + +#include "BLI_memarena.h" +#include "BLI_alloca.h" + +#include "BLI_polyfill_2d.h" /* own include */ + +#include "BLI_strict_flags.h" + +/* avoid fan-fill topology */ +#define USE_CLIP_EVEN +#define USE_CONVEX_SKIP +/* sweep back-and-forth about convex ears (avoids lop-sided fans) */ +#define USE_CLIP_SWEEP +// #define USE_CONVEX_SKIP_TEST + +#ifdef USE_CONVEX_SKIP +# define USE_KDTREE +#endif + +/* disable in production, it can fail on near zero area ngons */ +// #define USE_STRICT_ASSERT + +// #define DEBUG_TIME +#ifdef DEBUG_TIME +# include "PIL_time_utildefines.h" +#endif + + +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. + * + * + * - #KDTreeNode2D is kept small (only 16 bytes), + * by not storing coords in the nodes and using index values rather then pointers + * to reference neg/pos values. + * + * - #kdtree2d_isect_tri is the only function currently used. + * This simply intersects a triangle with the kdtree points. + * + * - the KDTree is only built & used when the polygon is concave. + */ + +typedef bool axis_t; + +/* use for sorting */ +typedef struct KDTreeNode2D_head { + uint neg, pos; + uint index; +} KDTreeNode2D_head; + +typedef struct KDTreeNode2D { + uint neg, pos; + uint index; + axis_t axis; /* range is only (0-1) */ + ushort flag; + uint parent; +} KDTreeNode2D; + +struct KDTree2D { + KDTreeNode2D *nodes; + const float (*coords)[2]; + uint root; + uint totnode; + uint *nodes_map; /* index -> node lookup */ +}; + +struct KDRange2D { + float min, max; +}; +#endif /* USE_KDTREE */ + +enum { + CONCAVE = -1, + TANGENTIAL = 0, + CONVEX = 1, +}; + +typedef struct PolyFill { + struct PolyIndex *indices; /* vertex aligned */ + + const float (*coords)[2]; + uint coords_tot; +#ifdef USE_CONVEX_SKIP + uint coords_tot_concave; +#endif + + /* A polygon with n vertices has a triangulation of n-2 triangles. */ + uint (*tris)[3]; + uint tris_tot; + +#ifdef USE_KDTREE + struct KDTree2D kdtree; +#endif +} PolyFill; + + +/* circular linklist */ +typedef struct PolyIndex { + struct PolyIndex *next, *prev; + uint index; + eSign sign; +} PolyIndex; + + +/* based on libgdx 2013-11-28, apache 2.0 licensed */ + +static void pf_coord_sign_calc(PolyFill *pf, PolyIndex *pi); + +static PolyIndex *pf_ear_tip_find( + PolyFill *pf +#ifdef USE_CLIP_EVEN + , PolyIndex *pi_ear_init +#endif +#ifdef USE_CLIP_SWEEP + , bool reverse +#endif + ); + +static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip); +static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip); + + +BLI_INLINE eSign signum_enum(float a) +{ + if (UNLIKELY(a == 0.0f)) + return 0; + else if (a > 0.0f) + return 1; + else + return -1; +} + +/** + * alternative version of #area_tri_signed_v2 + * needed because of float precision issues + * + * \note removes / 2 since its not needed since we only need the sign. + */ +BLI_INLINE float area_tri_signed_v2_alt_2x(const float v1[2], const float v2[2], const float v3[2]) +{ + return ((v1[0] * (v2[1] - v3[1])) + + (v2[0] * (v3[1] - v1[1])) + + (v3[0] * (v1[1] - v2[1]))); +} + + +static eSign span_tri_v2_sign(const float v1[2], const float v2[2], const float v3[2]) +{ + return signum_enum(area_tri_signed_v2_alt_2x(v3, v2, v1)); +} + + +#ifdef USE_KDTREE +#define KDNODE_UNSET ((uint)-1) + +enum { + KDNODE_FLAG_REMOVED = (1 << 0), +}; + +static void kdtree2d_new( + struct KDTree2D *tree, + uint tot, + const float (*coords)[2]) +{ + /* set by caller */ + // tree->nodes = nodes; + tree->coords = coords; + tree->root = KDNODE_UNSET; + tree->totnode = tot; +} + +/** + * no need for kdtree2d_insert, since we know the coords array. + */ +static void kdtree2d_init( + struct KDTree2D *tree, + const uint coords_tot, + const PolyIndex *indices) +{ + KDTreeNode2D *node; + uint i; + + for (i = 0, node = tree->nodes; i < coords_tot; i++) { + if (indices[i].sign != CONVEX) { + node->neg = node->pos = KDNODE_UNSET; + node->index = indices[i].index; + node->axis = 0; + node->flag = 0; + node++; + } + } + + BLI_assert(tree->totnode == (uint)(node - tree->nodes)); +} + +static uint kdtree2d_balance_recursive( + KDTreeNode2D *nodes, uint totnode, axis_t axis, + const float (*coords)[2], const uint ofs) +{ + KDTreeNode2D *node; + uint neg, pos, median, i, j; + + if (totnode <= 0) { + return KDNODE_UNSET; + } + else if (totnode == 1) { + return 0 + ofs; + } + + /* quicksort style sorting around median */ + neg = 0; + pos = totnode - 1; + median = totnode / 2; + + while (pos > neg) { + const float co = coords[nodes[pos].index][axis]; + i = neg - 1; + j = pos; + + while (1) { + while (coords[nodes[++i].index][axis] < co) ; + while (coords[nodes[--j].index][axis] > co && j > neg) ; + + if (i >= j) { + break; + } + SWAP(KDTreeNode2D_head, *(KDTreeNode2D_head *)&nodes[i], *(KDTreeNode2D_head *)&nodes[j]); + } + + SWAP(KDTreeNode2D_head, *(KDTreeNode2D_head *)&nodes[i], *(KDTreeNode2D_head *)&nodes[pos]); + if (i >= median) { + pos = i - 1; + } + if (i <= median) { + neg = i + 1; + } + } + + /* set node and sort subnodes */ + node = &nodes[median]; + node->axis = axis; + axis = !axis; + node->neg = kdtree2d_balance_recursive(nodes, median, axis, coords, ofs); + node->pos = kdtree2d_balance_recursive(&nodes[median + 1], (totnode - (median + 1)), axis, coords, (median + 1) + ofs); + + return median + ofs; +} + +static void kdtree2d_balance( + struct KDTree2D *tree) +{ + tree->root = kdtree2d_balance_recursive(tree->nodes, tree->totnode, 0, tree->coords, 0); +} + + +static void kdtree2d_init_mapping( + struct KDTree2D *tree) +{ + uint i; + KDTreeNode2D *node; + + for (i = 0, node = tree->nodes; i < tree->totnode; i++, node++) { + if (node->neg != KDNODE_UNSET) { + tree->nodes[node->neg].parent = i; + } + if (node->pos != KDNODE_UNSET) { + tree->nodes[node->pos].parent = i; + } + + /* build map */ + BLI_assert(tree->nodes_map[node->index] == KDNODE_UNSET); + tree->nodes_map[node->index] = i; + } + + tree->nodes[tree->root].parent = KDNODE_UNSET; +} + +static void kdtree2d_node_remove( + struct KDTree2D *tree, + uint index) +{ + uint node_index = tree->nodes_map[index]; + KDTreeNode2D *node; + + if (node_index == KDNODE_UNSET) { + return; + } + else { + tree->nodes_map[index] = KDNODE_UNSET; + } + + node = &tree->nodes[node_index]; + tree->totnode -= 1; + + BLI_assert((node->flag & KDNODE_FLAG_REMOVED) == 0); + node->flag |= KDNODE_FLAG_REMOVED; + + while ((node->neg == KDNODE_UNSET) && + (node->pos == KDNODE_UNSET) && + (node->parent != KDNODE_UNSET)) + { + KDTreeNode2D *node_parent = &tree->nodes[node->parent]; + + BLI_assert((uint)(node - tree->nodes) == node_index); + if (node_parent->neg == node_index) { + node_parent->neg = KDNODE_UNSET; + } + else { + BLI_assert(node_parent->pos == node_index); + node_parent->pos = KDNODE_UNSET; + } + + if (node_parent->flag & KDNODE_FLAG_REMOVED) { + node_index = node->parent; + node = node_parent; + } + else { + break; + } + } +} + +static bool kdtree2d_isect_tri_recursive( + const struct KDTree2D *tree, + const uint tri_index[3], + const float *tri_coords[3], + const float tri_center[2], + const struct KDRange2D bounds[2], + const KDTreeNode2D *node) +{ + const float *co = tree->coords[node->index]; + + /* bounds then triangle intersect */ + if ((node->flag & KDNODE_FLAG_REMOVED) == 0) { + /* bounding box test first */ + if ((co[0] >= bounds[0].min) && + (co[0] <= bounds[0].max) && + (co[1] >= bounds[1].min) && + (co[1] <= bounds[1].max)) + { + if ((span_tri_v2_sign(tri_coords[0], tri_coords[1], co) != CONCAVE) && + (span_tri_v2_sign(tri_coords[1], tri_coords[2], co) != CONCAVE) && + (span_tri_v2_sign(tri_coords[2], tri_coords[0], co) != CONCAVE)) + { + if (!ELEM(node->index, tri_index[0], tri_index[1], tri_index[2])) { + return true; + } + } + } + } + +#define KDTREE2D_ISECT_TRI_RECURSE_NEG \ + (((node->neg != KDNODE_UNSET) && (co[node->axis] >= bounds[node->axis].min)) && \ + (kdtree2d_isect_tri_recursive(tree, tri_index, tri_coords, tri_center, bounds, \ + &tree->nodes[node->neg]))) +#define KDTREE2D_ISECT_TRI_RECURSE_POS \ + (((node->pos != KDNODE_UNSET) && (co[node->axis] <= bounds[node->axis].max)) && \ + (kdtree2d_isect_tri_recursive(tree, tri_index, tri_coords, tri_center, bounds, \ + &tree->nodes[node->pos]))) + + if (tri_center[node->axis] > co[node->axis]) { + if (KDTREE2D_ISECT_TRI_RECURSE_POS) { + return true; + } + if (KDTREE2D_ISECT_TRI_RECURSE_NEG) { + return true; + } + } + else { + if (KDTREE2D_ISECT_TRI_RECURSE_NEG) { + return true; + } + if (KDTREE2D_ISECT_TRI_RECURSE_POS) { + return true; + } + } + +#undef KDTREE2D_ISECT_TRI_RECURSE_NEG +#undef KDTREE2D_ISECT_TRI_RECURSE_POS + + BLI_assert(node->index != KDNODE_UNSET); + + return false; +} + +static bool kdtree2d_isect_tri( + struct KDTree2D *tree, + const uint ind[3]) +{ + const float *vs[3]; + uint i; + struct KDRange2D bounds[2] = { + {FLT_MAX, -FLT_MAX}, + {FLT_MAX, -FLT_MAX}, + }; + float tri_center[2] = {0.0f, 0.0f}; + + for (i = 0; i < 3; i++) { + vs[i] = tree->coords[ind[i]]; + + add_v2_v2(tri_center, vs[i]); + + CLAMP_MAX(bounds[0].min, vs[i][0]); + CLAMP_MIN(bounds[0].max, vs[i][0]); + CLAMP_MAX(bounds[1].min, vs[i][1]); + CLAMP_MIN(bounds[1].max, vs[i][1]); + } + + mul_v2_fl(tri_center, 1.0f / 3.0f); + + return kdtree2d_isect_tri_recursive(tree, ind, vs, tri_center, bounds, &tree->nodes[tree->root]); +} + +#endif /* USE_KDTREE */ + + +static uint *pf_tri_add(PolyFill *pf) +{ + return pf->tris[pf->tris_tot++]; +} + +static void pf_coord_remove(PolyFill *pf, PolyIndex *pi) +{ +#ifdef USE_KDTREE + /* avoid double lookups, since convex coords are ignored when testing intersections */ + if (pf->kdtree.totnode) { + kdtree2d_node_remove(&pf->kdtree, pi->index); + } +#endif + + pi->next->prev = pi->prev; + pi->prev->next = pi->next; + + if (UNLIKELY(pf->indices == pi)) { + pf->indices = pi->next; + } +#ifdef DEBUG + pi->index = (uint)-1; + pi->next = pi->prev = NULL; +#endif + + pf->coords_tot -= 1; +} + +static void pf_triangulate(PolyFill *pf) +{ + /* localize */ + PolyIndex *pi_ear; + +#ifdef USE_CLIP_EVEN + PolyIndex *pi_ear_init = pf->indices; +#endif +#ifdef USE_CLIP_SWEEP + bool reverse = false; +#endif + + while (pf->coords_tot > 3) { + PolyIndex *pi_prev, *pi_next; + eSign sign_orig_prev, sign_orig_next; + + pi_ear = pf_ear_tip_find( + pf +#ifdef USE_CLIP_EVEN + , pi_ear_init +#endif +#ifdef USE_CLIP_SWEEP + , reverse +#endif + ); + +#ifdef USE_CONVEX_SKIP + if (pi_ear->sign != CONVEX) { + pf->coords_tot_concave -= 1; + } +#endif + + pi_prev = pi_ear->prev; + pi_next = pi_ear->next; + + pf_ear_tip_cut(pf, pi_ear); + + /* The type of the two vertices adjacent to the clipped vertex may have changed. */ + sign_orig_prev = pi_prev->sign; + sign_orig_next = pi_next->sign; + + /* check if any verts became convex the (else if) + * case is highly unlikely but may happen with degenerate polygons */ + if (sign_orig_prev != CONVEX) { + pf_coord_sign_calc(pf, pi_prev); +#ifdef USE_CONVEX_SKIP + if (pi_prev->sign == CONVEX) { + pf->coords_tot_concave -= 1; +#ifdef USE_KDTREE + kdtree2d_node_remove(&pf->kdtree, pi_prev->index); +#endif + } +#endif + } + if (sign_orig_next != CONVEX) { + pf_coord_sign_calc(pf, pi_next); +#ifdef USE_CONVEX_SKIP + if (pi_next->sign == CONVEX) { + pf->coords_tot_concave -= 1; +#ifdef USE_KDTREE + kdtree2d_node_remove(&pf->kdtree, pi_next->index); +#endif + } +#endif + } + +#ifdef USE_CLIP_EVEN +#ifdef USE_CLIP_SWEEP + pi_ear_init = reverse ? pi_prev->prev : pi_next->next; +#else + pi_ear_init = pi_next->next; +#endif +#endif + +#ifdef USE_CLIP_EVEN +#ifdef USE_CLIP_SWEEP + if (pi_ear_init->sign != CONVEX) { + /* take the extra step since this ear isn't a good candidate */ + pi_ear_init = reverse ? pi_ear_init->prev : pi_ear_init->next; + reverse = !reverse; + } +#endif +#else + if ((reverse ? pi_prev->prev : pi_next->next)->sign != CONVEX) { + reverse = !reverse; + } +#endif + + } + + if (pf->coords_tot == 3) { + uint *tri = pf_tri_add(pf); + pi_ear = pf->indices; + tri[0] = pi_ear->index; pi_ear = pi_ear->next; + tri[1] = pi_ear->index; pi_ear = pi_ear->next; + tri[2] = pi_ear->index; + } +} + +/** + * \return CONCAVE, TANGENTIAL or CONVEX + */ +static void pf_coord_sign_calc(PolyFill *pf, PolyIndex *pi) +{ + /* localize */ + const float (*coords)[2] = pf->coords; + + pi->sign = span_tri_v2_sign( + coords[pi->prev->index], + coords[pi->index], + coords[pi->next->index]); +} + +static PolyIndex *pf_ear_tip_find( + PolyFill *pf +#ifdef USE_CLIP_EVEN + , PolyIndex *pi_ear_init +#endif +#ifdef USE_CLIP_SWEEP + , bool reverse +#endif + ) +{ + /* localize */ + const uint coords_tot = pf->coords_tot; + PolyIndex *pi_ear; + + uint i; + +#ifdef USE_CLIP_EVEN + pi_ear = pi_ear_init; +#else + pi_ear = pf->indices; +#endif + + i = coords_tot; + while (i--) { + if (pf_ear_tip_check(pf, pi_ear)) { + return pi_ear; + } +#ifdef USE_CLIP_SWEEP + pi_ear = reverse ? pi_ear->prev : pi_ear->next; +#else + pi_ear = pi_ear->next; +#endif + } + + /* Desperate mode: if no vertex is an ear tip, we are dealing with a degenerate polygon (e.g. nearly collinear). + * Note that the input was not necessarily degenerate, but we could have made it so by clipping some valid ears. + * + * Idea taken from Martin Held, "FIST: Fast industrial-strength triangulation of polygons", Algorithmica (1998), + * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.291 + * + * Return a convex or tangential vertex if one exists. + */ + +#ifdef USE_CLIP_EVEN + pi_ear = pi_ear_init; +#else + pi_ear = pf->indices; +#endif + + i = coords_tot; + while (i--) { + if (pi_ear->sign != CONCAVE) { + return pi_ear; + } + pi_ear = pi_ear->next; + } + + /* If all vertices are concave, just return the last one. */ + return pi_ear; +} + +static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip) +{ +#ifndef USE_KDTREE + /* localize */ + const float (*coords)[2] = pf->coords; + PolyIndex *pi_curr; + + const float *v1, *v2, *v3; +#endif + +#if defined(USE_CONVEX_SKIP) && !defined(USE_KDTREE) + uint coords_tot_concave_checked = 0; +#endif + + +#ifdef USE_CONVEX_SKIP + +#ifdef USE_CONVEX_SKIP_TEST + /* check if counting is wrong */ + { + uint coords_tot_concave_test = 0; + PolyIndex *pi_iter = pi_ear_tip; + do { + if (pi_iter->sign != CONVEX) { + coords_tot_concave_test += 1; + } + } while ((pi_iter = pi_iter->next) != pi_ear_tip); + BLI_assert(coords_tot_concave_test == pf->coords_tot_concave); + } +#endif + + /* fast-path for circles */ + if (pf->coords_tot_concave == 0) { + return true; + } +#endif + + if (UNLIKELY(pi_ear_tip->sign == CONCAVE)) { + return false; + } + +#ifdef USE_KDTREE + { + const uint ind[3] = { + pi_ear_tip->index, + pi_ear_tip->next->index, + pi_ear_tip->prev->index}; + + if (kdtree2d_isect_tri(&pf->kdtree, ind)) { + return false; + } + } +#else + + v1 = coords[pi_ear_tip->prev->index]; + v2 = coords[pi_ear_tip->index]; + v3 = coords[pi_ear_tip->next->index]; + + /* Check if any point is inside the triangle formed by previous, current and next vertices. + * Only consider vertices that are not part of this triangle, or else we'll always find one inside. */ + + for (pi_curr = pi_ear_tip->next->next; pi_curr != pi_ear_tip->prev; pi_curr = pi_curr->next) { + /* Concave vertices can obviously be inside the candidate ear, but so can tangential vertices + * if they coincide with one of the triangle's vertices. */ + if (pi_curr->sign != CONVEX) { + const float *v = coords[pi_curr->index]; + /* Because the polygon has clockwise winding order, + * the area sign will be positive if the point is strictly inside. + * It will be 0 on the edge, which we want to include as well. */ + + /* note: check (v3, v1) first since it fails _far_ more often then the other 2 checks (those fail equally). + * It's logical - the chance is low that points exist on the same side as the ear we're clipping off. */ + if ((span_tri_v2_sign(v3, v1, v) != CONCAVE) && + (span_tri_v2_sign(v1, v2, v) != CONCAVE) && + (span_tri_v2_sign(v2, v3, v) != CONCAVE)) + { + return false; + } + +#ifdef USE_CONVEX_SKIP + coords_tot_concave_checked += 1; + if (coords_tot_concave_checked == pf->coords_tot_concave) { + break; + } +#endif + } + } +#endif /* USE_KDTREE */ + + return true; +} + +static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip) +{ + uint *tri = pf_tri_add(pf); + + tri[0] = pi_ear_tip->prev->index; + tri[1] = pi_ear_tip->index; + tri[2] = pi_ear_tip->next->index; + + pf_coord_remove(pf, pi_ear_tip); +} + +/** + * Initializes the #PolyFill structure before tessellating with #polyfill_calc. + */ +static void polyfill_prepare( + PolyFill *pf, + const float (*coords)[2], + const uint coords_tot, + int coords_sign, + uint (*r_tris)[3], + PolyIndex *r_indices) +{ + /* localize */ + PolyIndex *indices = r_indices; + + uint i; + + /* assign all polyfill members here */ + pf->indices = r_indices; + pf->coords = coords; + pf->coords_tot = coords_tot; +#ifdef USE_CONVEX_SKIP + pf->coords_tot_concave = 0; +#endif + pf->tris = r_tris; + pf->tris_tot = 0; + + if (coords_sign == 0) { + coords_sign = (cross_poly_v2(coords, coords_tot) >= 0.0f) ? 1 : -1; + } + else { + /* check we're passing in correcty args */ +#ifdef USE_STRICT_ASSERT +#ifndef NDEBUG + if (coords_sign == 1) { + BLI_assert(cross_poly_v2(coords, coords_tot) >= 0.0f); + } + else { + BLI_assert(cross_poly_v2(coords, coords_tot) <= 0.0f); + } +#endif +#endif + } + + if (coords_sign == 1) { + for (i = 0; i < coords_tot; i++) { + indices[i].next = &indices[i + 1]; + indices[i].prev = &indices[i - 1]; + indices[i].index = i; + } + } + else { + /* reversed */ + uint n = coords_tot - 1; + for (i = 0; i < coords_tot; i++) { + indices[i].next = &indices[i + 1]; + indices[i].prev = &indices[i - 1]; + indices[i].index = (n - i); + } + } + indices[0].prev = &indices[coords_tot - 1]; + indices[coords_tot - 1].next = &indices[0]; + + for (i = 0; i < coords_tot; i++) { + PolyIndex *pi = &indices[i]; + pf_coord_sign_calc(pf, pi); +#ifdef USE_CONVEX_SKIP + if (pi->sign != CONVEX) { + pf->coords_tot_concave += 1; + } +#endif + } +} + +static void polyfill_calc( + PolyFill *pf) +{ +#ifdef USE_KDTREE +#ifdef USE_CONVEX_SKIP + if (pf->coords_tot_concave) +#endif + { + kdtree2d_new(&pf->kdtree, pf->coords_tot_concave, pf->coords); + kdtree2d_init(&pf->kdtree, pf->coords_tot, pf->indices); + kdtree2d_balance(&pf->kdtree); + kdtree2d_init_mapping(&pf->kdtree); + } +#endif + + pf_triangulate(pf); +} + +/** + * A version of #BLI_polyfill_calc that uses a memory arena to avoid re-allocations. + */ +void BLI_polyfill_calc_arena( + const float (*coords)[2], + const uint coords_tot, + const int coords_sign, + uint (*r_tris)[3], + + struct MemArena *arena) +{ + PolyFill pf; + PolyIndex *indices = BLI_memarena_alloc(arena, sizeof(*indices) * coords_tot); + +#ifdef DEBUG_TIME + TIMEIT_START(polyfill2d); +#endif + + polyfill_prepare( + &pf, + coords, coords_tot, coords_sign, + r_tris, + /* cache */ + indices); + +#ifdef USE_KDTREE + if (pf.coords_tot_concave) { + pf.kdtree.nodes = BLI_memarena_alloc(arena, sizeof(*pf.kdtree.nodes) * pf.coords_tot_concave); + pf.kdtree.nodes_map = memset(BLI_memarena_alloc(arena, sizeof(*pf.kdtree.nodes_map) * coords_tot), + 0xff, sizeof(*pf.kdtree.nodes_map) * coords_tot); + } + else { + pf.kdtree.totnode = 0; + } +#endif + + polyfill_calc(&pf); + + /* indices are no longer needed, + * caller can clear arena */ + +#ifdef DEBUG_TIME + TIMEIT_END(polyfill2d); +#endif +} + +/** + * Triangulates the given (convex or concave) simple polygon to a list of triangle vertices. + * + * \param coords: 2D coordinates describing vertices of the polygon, + * in either clockwise or counterclockwise order. + * \param coords_tot: Total points in the array. + * \param coords_sign: Pass this when we know the sign in advance to avoid extra calculations. + * + * \param r_tris: This array is filled in with triangle indices in clockwise order. + * The length of the array must be ``coords_tot - 2``. + * Indices are guaranteed to be assigned to unique triangles, with valid indices, + * even in the case of degenerate input (self intersecting polygons, zero area ears... etc). + */ +void BLI_polyfill_calc( + const float (*coords)[2], + const uint coords_tot, + const int coords_sign, + uint (*r_tris)[3]) +{ + PolyFill pf; + PolyIndex *indices = BLI_array_alloca(indices, coords_tot); + +#ifdef DEBUG_TIME + TIMEIT_START(polyfill2d); +#endif + + polyfill_prepare( + &pf, + coords, coords_tot, coords_sign, + r_tris, + /* cache */ + indices); + +#ifdef USE_KDTREE + if (pf.coords_tot_concave) { + pf.kdtree.nodes = BLI_array_alloca(pf.kdtree.nodes, pf.coords_tot_concave); + pf.kdtree.nodes_map = memset(BLI_array_alloca(pf.kdtree.nodes_map, coords_tot), + 0xff, sizeof(*pf.kdtree.nodes_map) * coords_tot); + } + else { + pf.kdtree.totnode = 0; + } +#endif + + polyfill_calc(&pf); + +#ifdef DEBUG_TIME + TIMEIT_END(polyfill2d); +#endif +} diff --git a/source/blender/blenlib/intern/polyfill_2d_beautify.c b/source/blender/blenlib/intern/polyfill_2d_beautify.c new file mode 100644 index 00000000000..93bfb02bce4 --- /dev/null +++ b/source/blender/blenlib/intern/polyfill_2d_beautify.c @@ -0,0 +1,439 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenlib/intern/polyfill2d_beautify.c + * \ingroup bli + * + * This function is to improve the tessellation resulting from polyfill2d, + * creating optimal topology. + * + * The functionality here matches #BM_mesh_beautify_fill, + * but its far simpler to perform this operation in 2d, + * on a simple polygon representation where we _know_: + * + * - The polygon is primitive with no holes with a continuous boundary. + * - Tris have consistent winding. + * - 2d (saves some hassles projecting face pairs on an axis for every edge-rotation) + * also saves us having to store all previous edge-states (see #EdRotState in bmesh_beautify.c) + * + * \note + * + * No globals - keep threadsafe. + */ + +#include "BLI_utildefines.h" +#include "BLI_math.h" + +#include "BLI_memarena.h" +#include "BLI_heap.h" + +#include "BLI_polyfill_2d_beautify.h" /* own include */ + +#include "BLI_strict_flags.h" + +/* Used to find matching edges. */ +struct OrderEdge { + uint verts[2]; + uint e_half; +}; + +/* Half edge used for rotating in-place. */ +struct HalfEdge { + uint v; + uint e_next; + uint e_radial; + uint base_index; +}; + +static int oedge_cmp(const void *a1, const void *a2) +{ + const struct OrderEdge *x1 = a1, *x2 = a2; + if (x1->verts[0] > x2->verts[0]) { + return 1; + } + else if (x1->verts[0] < x2->verts[0]) { + return -1; + } + + if (x1->verts[1] > x2->verts[1]) { + return 1; + } + else if (x1->verts[1] < x2->verts[1]) { + return -1; + } + + /* only for pradictability */ + if (x1->e_half > x2->e_half) { + return 1; + } + else if (x1->e_half < x2->e_half) { + return -1; + } + /* Should never get here, no two edges should be the same. */ + BLI_assert(false); + return 0; +} + +BLI_INLINE bool is_boundary_edge(uint i_a, uint i_b, const uint coord_last) +{ + BLI_assert(i_a < i_b); + return ((i_a + 1 == i_b) || UNLIKELY((i_a == 0) && (i_b == coord_last))); +} +/** + * Assuming we have 2 triangles sharing an edge (2 - 4), + * check if the edge running from (1 - 3) gives better results. + * + * \param lock_degenerate: Use to avoid rotating out of a degenerate state. + * - When true, an existing zero area face on either side of the (2 - 4) split will return a positive value. + * - When false, the check must be non-biased towards either split direction. + * + * \return (negative number means the edge can be rotated, lager == better). + */ +float BLI_polyfill_beautify_quad_rotate_calc_ex( + const float v1[2], const float v2[2], const float v3[2], const float v4[2], + const bool lock_degenerate) +{ + /* not a loop (only to be able to break out) */ + do { + /* Allow very small faces to be considered non-zero. */ + const float eps_zero_area = 1e-12f; + const float area_2x_234 = cross_tri_v2(v2, v3, v4); + const float area_2x_241 = cross_tri_v2(v2, v4, v1); + + const float area_2x_123 = cross_tri_v2(v1, v2, v3); + const float area_2x_134 = cross_tri_v2(v1, v3, v4); + + BLI_assert((ELEM(v1, v2, v3, v4) == false) && + (ELEM(v2, v1, v3, v4) == false) && + (ELEM(v3, v1, v2, v4) == false) && + (ELEM(v4, v1, v2, v3) == false)); + /* + * Test for unusable (1-3) state. + * - Area sign flipping to check faces aren't going to point in opposite directions. + * - Area epsilon check that the one of the faces won't be zero area. + */ + if ((area_2x_123 >= 0.0f) != (area_2x_134 >= 0.0f)) { + break; + } + else if ((fabsf(area_2x_123) <= eps_zero_area) || (fabsf(area_2x_134) <= eps_zero_area)) { + break; + } + + /* Test for unusable (2-4) state (same as above). */ + if ((area_2x_234 >= 0.0f) != (area_2x_241 >= 0.0f)) { + if (lock_degenerate) { + break; + } + else { + return -FLT_MAX; /* always rotate */ + } + } + else if ((fabsf(area_2x_234) <= eps_zero_area) || (fabsf(area_2x_241) <= eps_zero_area)) { + return -FLT_MAX; /* always rotate */ + } + + { + /* testing rule: the area divided by the perimeter, + * check if (1-3) beats the existing (2-4) edge rotation */ + float area_a, area_b; + float prim_a, prim_b; + float fac_24, fac_13; + + float len_12, len_23, len_34, len_41, len_24, len_13; + + /* edges around the quad */ + len_12 = len_v2v2(v1, v2); + len_23 = len_v2v2(v2, v3); + len_34 = len_v2v2(v3, v4); + len_41 = len_v2v2(v4, v1); + /* edges crossing the quad interior */ + len_13 = len_v2v2(v1, v3); + len_24 = len_v2v2(v2, v4); + + /* note, area is in fact (area * 2), + * but in this case its OK, since we're comparing ratios */ + + /* edge (2-4), current state */ + area_a = fabsf(area_2x_234); + area_b = fabsf(area_2x_241); + prim_a = len_23 + len_34 + len_24; + prim_b = len_41 + len_12 + len_24; + fac_24 = (area_a / prim_a) + (area_b / prim_b); + + /* edge (1-3), new state */ + area_a = fabsf(area_2x_123); + area_b = fabsf(area_2x_134); + prim_a = len_12 + len_23 + len_13; + prim_b = len_34 + len_41 + len_13; + fac_13 = (area_a / prim_a) + (area_b / prim_b); + + /* negative number if (1-3) is an improved state */ + return fac_24 - fac_13; + } + } while (false); + + return FLT_MAX; +} + +static float polyedge_rotate_beauty_calc( + const float (*coords)[2], + const struct HalfEdge *edges, + const struct HalfEdge *e_a) +{ + const struct HalfEdge *e_b = &edges[e_a->e_radial]; + + const struct HalfEdge *e_a_other = &edges[edges[e_a->e_next].e_next]; + const struct HalfEdge *e_b_other = &edges[edges[e_b->e_next].e_next]; + + const float *v1, *v2, *v3, *v4; + + v1 = coords[e_a_other->v]; + v2 = coords[e_a->v]; + v3 = coords[e_b_other->v]; + v4 = coords[e_b->v]; + + return BLI_polyfill_beautify_quad_rotate_calc(v1, v2, v3, v4); +} + +static void polyedge_beauty_cost_update_single( + const float (*coords)[2], + const struct HalfEdge *edges, + struct HalfEdge *e, + Heap *eheap, HeapNode **eheap_table) +{ + const uint i = e->base_index; + /* recalculate edge */ + const float cost = polyedge_rotate_beauty_calc(coords, edges, e); + /* We can get cases where both choices generate very small negative costs, which leads to infinite loop. + * Anyway, costs above that are not worth recomputing, maybe we could even optimize it to a smaller limit? + * Actually, FLT_EPSILON is too small in some cases, 1e-6f seems to work OK hopefully? + * See T43578, T49478. */ + if (cost < -1e-6f) { + BLI_heap_insert_or_update(eheap, &eheap_table[i], cost, e); + } + else { + if (eheap_table[i]) { + BLI_heap_remove(eheap, eheap_table[i]); + eheap_table[i] = NULL; + } + } +} + +static void polyedge_beauty_cost_update( + const float (*coords)[2], + struct HalfEdge *edges, + struct HalfEdge *e, + Heap *eheap, HeapNode **eheap_table) +{ + struct HalfEdge *e_arr[4]; + e_arr[0] = &edges[e->e_next]; + e_arr[1] = &edges[e_arr[0]->e_next]; + + e = &edges[e->e_radial]; + e_arr[2] = &edges[e->e_next]; + e_arr[3] = &edges[e_arr[2]->e_next]; + + for (uint i = 0; i < 4; i++) { + if (e_arr[i] && e_arr[i]->base_index != UINT_MAX) { + polyedge_beauty_cost_update_single( + coords, edges, + e_arr[i], + eheap, eheap_table); + } + } +} + +static void polyedge_rotate( + struct HalfEdge *edges, + struct HalfEdge *e) +{ + /** CCW winding, rotate internal edge to new vertical state. + * 
+	 *   Before         After
+	 *      X             X
+	 *     / \           /|\
+	 *  e4/   \e5     e4/ | \e5
+	 *   / e3  \       /  |  \
+	 * X ------- X -> X e0|e3 X
+	 *   \ e0  /       \  |  /
+	 *  e2\   /e1     e2\ | /e1
+	 *     \ /           \|/
+	 *      X             X
+	 *
+ */ + struct HalfEdge *ed[6]; + uint ed_index[6]; + + ed_index[0] = (uint)(e - edges); + ed[0] = &edges[ed_index[0]]; + ed_index[1] = ed[0]->e_next; + ed[1] = &edges[ed_index[1]]; + ed_index[2] = ed[1]->e_next; + ed[2] = &edges[ed_index[2]]; + + ed_index[3] = e->e_radial; + ed[3] = &edges[ed_index[3]]; + ed_index[4] = ed[3]->e_next; + ed[4] = &edges[ed_index[4]]; + ed_index[5] = ed[4]->e_next; + ed[5] = &edges[ed_index[5]]; + + ed[0]->e_next = ed_index[2]; + ed[1]->e_next = ed_index[3]; + ed[2]->e_next = ed_index[4]; + ed[3]->e_next = ed_index[5]; + ed[4]->e_next = ed_index[0]; + ed[5]->e_next = ed_index[1]; + + ed[0]->v = ed[5]->v; + ed[3]->v = ed[2]->v; +} + +/** + * The intention is that this calculates the output of #BLI_polyfill_calc + * + * + * \note assumes the \a coords form a boundary, + * so any edges running along contiguous (wrapped) indices, + * are ignored since the edges wont share 2 faces. + */ +void BLI_polyfill_beautify( + const float (*coords)[2], + const uint coords_tot, + uint (*tris)[3], + + /* structs for reuse */ + MemArena *arena, Heap *eheap) +{ + const uint coord_last = coords_tot - 1; + const uint tris_len = coords_tot - 2; + /* internal edges only (between 2 tris) */ + const uint edges_len = tris_len - 1; + + HeapNode **eheap_table; + + const uint half_edges_len = 3 * tris_len; + struct HalfEdge *half_edges = BLI_memarena_alloc(arena, sizeof(*half_edges) * half_edges_len); + struct OrderEdge *order_edges = BLI_memarena_alloc(arena, sizeof(struct OrderEdge) * 2 * edges_len); + uint order_edges_len = 0; + + /* first build edges */ + for (uint i = 0; i < tris_len; i++) { + for (uint j_curr = 0, j_prev = 2; j_curr < 3; j_prev = j_curr++) { + const uint e_index_prev = (i * 3) + j_prev; + const uint e_index_curr = (i * 3) + j_curr; + + half_edges[e_index_prev].v = tris[i][j_prev]; + half_edges[e_index_prev].e_next = e_index_curr; + half_edges[e_index_prev].e_radial = UINT_MAX; + half_edges[e_index_prev].base_index = UINT_MAX; + + uint e_pair[2] = {tris[i][j_prev], tris[i][j_curr]}; + if (e_pair[0] > e_pair[1]) { + SWAP(uint, e_pair[0], e_pair[1]); + } + + /* ensure internal edges. */ + if (!is_boundary_edge(e_pair[0], e_pair[1], coord_last)) { + order_edges[order_edges_len].verts[0] = e_pair[0]; + order_edges[order_edges_len].verts[1] = e_pair[1]; + order_edges[order_edges_len].e_half = e_index_prev; + order_edges_len += 1; + } + } + } + BLI_assert(edges_len * 2 == order_edges_len); + + qsort(order_edges, order_edges_len, sizeof(struct OrderEdge), oedge_cmp); + + for (uint i = 0, base_index = 0; i < order_edges_len; base_index++) { + const struct OrderEdge *oe_a = &order_edges[i++]; + const struct OrderEdge *oe_b = &order_edges[i++]; + BLI_assert(oe_a->verts[0] == oe_a->verts[0] && oe_a->verts[1] == oe_a->verts[1]); + half_edges[oe_a->e_half].e_radial = oe_b->e_half; + half_edges[oe_b->e_half].e_radial = oe_a->e_half; + half_edges[oe_a->e_half].base_index = base_index; + half_edges[oe_b->e_half].base_index = base_index; + } + /* order_edges could be freed now. */ + + /* Now perform iterative rotations. */ +#if 0 + eheap_table = BLI_memarena_alloc(arena, sizeof(HeapNode *) * (size_t)edges_len); +#else + /* We can re-use this since its big enough. */ + eheap_table = (void *)order_edges; + order_edges = NULL; +#endif + + /* Build heap. */ + { + struct HalfEdge *e = half_edges; + for (uint i = 0; i < half_edges_len; i++, e++) { + /* Accounts for boundary edged too (UINT_MAX). */ + if (e->e_radial < i) { + const float cost = polyedge_rotate_beauty_calc(coords, half_edges, e); + if (cost < 0.0f) { + eheap_table[e->base_index] = BLI_heap_insert(eheap, cost, e); + } + else { + eheap_table[e->base_index] = NULL; + } + } + } + } + + while (BLI_heap_is_empty(eheap) == false) { + struct HalfEdge *e = BLI_heap_pop_min(eheap); + eheap_table[e->base_index] = NULL; + + polyedge_rotate(half_edges, e); + + /* recalculate faces connected on the heap */ + polyedge_beauty_cost_update( + coords, half_edges, + e, + eheap, eheap_table); + } + + BLI_heap_clear(eheap, NULL); + + /* MEM_freeN(eheap_table); */ /* arena */ + + /* get tris from half edge. */ + uint tri_index = 0; + for (uint i = 0; i < half_edges_len; i++) { + struct HalfEdge *e = &half_edges[i]; + if (e->v != UINT_MAX) { + uint *tri = tris[tri_index++]; + + tri[0] = e->v; + e->v = UINT_MAX; + + e = &half_edges[e->e_next]; + tri[1] = e->v; + e->v = UINT_MAX; + + e = &half_edges[e->e_next]; + tri[2] = e->v; + e->v = UINT_MAX; + } + } +} diff --git a/source/blender/blenlib/intern/voronoi.c b/source/blender/blenlib/intern/voronoi.c deleted file mode 100644 index e0cbe278ffb..00000000000 --- a/source/blender/blenlib/intern/voronoi.c +++ /dev/null @@ -1,832 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2012 Blender Foundation. - * All rights reserved. - * - * Contributor(s): Sergey Sharybin - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/* - * Fortune's algorithm implemented using explanation and some code snippets from - * http://blog.ivank.net/fortunes-algorithm-and-implementation.html - */ - -/** \file blender/blenlib/intern/voronoi.c - * \ingroup bli - */ - -#include "MEM_guardedalloc.h" - -#include "BLI_listbase.h" -#include "BLI_math.h" -#include "BLI_voronoi.h" -#include "BLI_utildefines.h" - -#define VORONOI_EPS 1e-2f - -enum { - voronoiEventType_Site = 0, - voronoiEventType_Circle = 1 -}; - -typedef struct VoronoiEvent { - struct VoronoiEvent *next, *prev; - - int type; /* type of event (site or circle) */ - float site[2]; /* site for which event was generated */ - - struct VoronoiParabola *parabola; /* parabola for which event was generated */ -} VoronoiEvent; - -typedef struct VoronoiParabola { - struct VoronoiParabola *left, *right, *parent; - VoronoiEvent *event; - VoronoiEdge *edge; - float site[2]; - bool is_leaf; -} VoronoiParabola; - -typedef struct VoronoiProcess { - ListBase queue, edges; - VoronoiParabola *root; - int width, height; - float current_y; -} VoronoiProcess; - -/* event */ - -static void voronoi_insertEvent(VoronoiProcess *process, VoronoiEvent *event) -{ - VoronoiEvent *current_event = process->queue.first; - - while (current_event) { - if (current_event->site[1] < event->site[1]) { - break; - } - if (current_event->site[1] == event->site[1]) { - event->site[1] -= VORONOI_EPS; - } - - current_event = current_event->next; - } - - BLI_insertlinkbefore(&process->queue, current_event, event); -} - -/* edge */ -static VoronoiEdge *voronoiEdge_new(float start[2], float left[2], float right[2]) -{ - VoronoiEdge *edge = MEM_callocN(sizeof(VoronoiEdge), "voronoi edge"); - - copy_v2_v2(edge->start, start); - copy_v2_v2(edge->left, left); - copy_v2_v2(edge->right, right); - - edge->neighbor = NULL; - edge->end[0] = 0; - edge->end[1] = 0; - - edge->f = (right[0] - left[0]) / (left[1] - right[1]); - edge->g = start[1] - edge->f * start[0]; - - edge->direction[0] = right[1] - left[1]; - edge->direction[1] = -(right[0] - left[0]); - - return edge; -} - -/* parabola */ - -static VoronoiParabola *voronoiParabola_new(void) -{ - VoronoiParabola *parabola = MEM_callocN(sizeof(VoronoiParabola), "voronoi parabola"); - - parabola->is_leaf = false; - parabola->event = NULL; - parabola->edge = NULL; - parabola->parent = NULL; - - return parabola; -} - -static VoronoiParabola *voronoiParabola_newSite(float site[2]) -{ - VoronoiParabola *parabola = MEM_callocN(sizeof(VoronoiParabola), "voronoi parabola site"); - - copy_v2_v2(parabola->site, site); - parabola->is_leaf = true; - parabola->event = NULL; - parabola->edge = NULL; - parabola->parent = NULL; - - return parabola; -} - -/* returns the closest leave which is on the left of current node */ -static VoronoiParabola *voronoiParabola_getLeftChild(VoronoiParabola *parabola) -{ - VoronoiParabola *current_parabola; - - if (!parabola) - return NULL; - - current_parabola = parabola->left; - while (!current_parabola->is_leaf) { - current_parabola = current_parabola->right; - } - - return current_parabola; -} - -/* returns the closest leave which is on the right of current node */ -static VoronoiParabola *voronoiParabola_getRightChild(VoronoiParabola *parabola) -{ - VoronoiParabola *current_parabola; - - if (!parabola) - return NULL; - - current_parabola = parabola->right; - while (!current_parabola->is_leaf) { - current_parabola = current_parabola->left; - } - - return current_parabola; -} - -/* returns the closest parent which is on the left */ -static VoronoiParabola *voronoiParabola_getLeftParent(VoronoiParabola *parabola) -{ - VoronoiParabola *current_par = parabola->parent; - VoronoiParabola *last_parabola = parabola; - - while (current_par->left == last_parabola) { - if (!current_par->parent) - return NULL; - - last_parabola = current_par; - current_par = current_par->parent; - } - - return current_par; -} - -/* returns the closest parent which is on the right */ -static VoronoiParabola *voronoiParabola_getRightParent(VoronoiParabola *parabola) -{ - VoronoiParabola *current_parabola = parabola->parent; - VoronoiParabola *last_parabola = parabola; - - while (current_parabola->right == last_parabola) { - if (!current_parabola->parent) - return NULL; - - last_parabola = current_parabola; - current_parabola = current_parabola->parent; - } - - return current_parabola; -} - -static void voronoiParabola_setLeft(VoronoiParabola *parabola, VoronoiParabola *left) -{ - parabola->left = left; - left->parent = parabola; -} - -static void voronoiParabola_setRight(VoronoiParabola *parabola, VoronoiParabola *right) -{ - parabola->right = right; - right->parent = parabola; -} - -static float voronoi_getY(VoronoiProcess *process, float p[2], float x) -{ - float ly = process->current_y; - - float dp = 2 * (p[1] - ly); - float a1 = 1 / dp; - float b1 = -2 * p[0] / dp; - float c1 = ly + dp / 4 + p[0] * p[0] / dp; - - return a1 * x * x + b1 * x + c1; -} - -static float voronoi_getXOfEdge(VoronoiProcess *process, VoronoiParabola *par, float y) -{ - VoronoiParabola *left = voronoiParabola_getLeftChild(par); - VoronoiParabola *right = voronoiParabola_getRightChild(par); - float p[2], r[2]; - float dp, a1, b1, c1, a2, b2, c2, a, b, c, disc, ry, x1, x2; - float ly = process->current_y; - - copy_v2_v2(p, left->site); - copy_v2_v2(r, right->site); - - dp = 2.0f * (p[1] - y); - a1 = 1.0f / dp; - b1 = -2.0f * p[0] / dp; - c1 = y + dp / 4 + p[0] * p[0] / dp; - - dp = 2.0f * (r[1] - y); - a2 = 1.0f / dp; - b2 = -2.0f * r[0] / dp; - c2 = ly + dp / 4 + r[0] * r[0] / dp; - - a = a1 - a2; - b = b1 - b2; - c = c1 - c2; - - disc = b * b - 4 * a * c; - x1 = (-b + sqrtf(disc)) / (2 * a); - x2 = (-b - sqrtf(disc)) / (2 * a); - - if (p[1] < r[1]) - ry = max_ff(x1, x2); - else - ry = min_ff(x1, x2); - - return ry; -} - -static VoronoiParabola *voronoi_getParabolaByX(VoronoiProcess *process, float xx) -{ - VoronoiParabola *par = process->root; - float x = 0.0f; - float ly = process->current_y; - - while (!par->is_leaf) { - x = voronoi_getXOfEdge(process, par, ly); - - if (x > xx) - par = par->left; - else - par = par->right; - } - - return par; -} - -static int voronoi_getEdgeIntersection(VoronoiEdge *a, VoronoiEdge *b, float p[2]) -{ - float x = (b->g - a->g) / (a->f - b->f); - float y = a->f * x + a->g; - - if ((x - a->start[0]) / a->direction[0] < 0) - return 0; - - if ((y - a->start[1]) / a->direction[1] < 0) - return 0; - - if ((x - b->start[0]) / b->direction[0] < 0) - return 0; - - if ((y - b->start[1]) / b->direction[1] < 0) - return 0; - - p[0] = x; - p[1] = y; - - return 1; -} - -static void voronoi_checkCircle(VoronoiProcess *process, VoronoiParabola *b) -{ - VoronoiParabola *lp = voronoiParabola_getLeftParent(b); - VoronoiParabola *rp = voronoiParabola_getRightParent(b); - - VoronoiParabola *a = voronoiParabola_getLeftChild(lp); - VoronoiParabola *c = voronoiParabola_getRightChild(rp); - - VoronoiEvent *event; - - float ly = process->current_y; - float s[2], dx, dy, d; - - if (!a || !c || len_squared_v2v2(a->site, c->site) < VORONOI_EPS) - return; - - if (!voronoi_getEdgeIntersection(lp->edge, rp->edge, s)) - return; - - dx = a->site[0] - s[0]; - dy = a->site[1] - s[1]; - - d = sqrtf((dx * dx) + (dy * dy)); - - if (s[1] - d >= ly) - return; - - event = MEM_callocN(sizeof(VoronoiEvent), "voronoi circle event"); - - event->type = voronoiEventType_Circle; - - event->site[0] = s[0]; - event->site[1] = s[1] - d; - - b->event = event; - event->parabola = b; - - voronoi_insertEvent(process, event); -} - -static void voronoi_addParabola(VoronoiProcess *process, float site[2]) -{ - VoronoiParabola *root = process->root; - VoronoiParabola *par, *p0, *p1, *p2; - VoronoiEdge *el, *er; - float start[2]; - - if (!process->root) { - process->root = voronoiParabola_newSite(site); - - return; - } - - if (root->is_leaf && root->site[1] - site[1] < 0) { - float *fp = root->site; - float s[2]; - - root->is_leaf = false; - voronoiParabola_setLeft(root, voronoiParabola_newSite(fp)); - voronoiParabola_setRight(root, voronoiParabola_newSite(site)); - - s[0] = (site[0] + fp[0]) / 2.0f; - s[1] = process->height; - - if (site[0] > fp[0]) - root->edge = voronoiEdge_new(s, fp, site); - else - root->edge = voronoiEdge_new(s, site, fp); - - BLI_addtail(&process->edges, root->edge); - - return; - } - - par = voronoi_getParabolaByX(process, site[0]); - - if (par->event) { - BLI_freelinkN(&process->queue, par->event); - - par->event = NULL; - } - - start[0] = site[0]; - start[1] = voronoi_getY(process, par->site, site[0]); - - el = voronoiEdge_new(start, par->site, site); - er = voronoiEdge_new(start, site, par->site); - - el->neighbor = er; - BLI_addtail(&process->edges, el); - - par->edge = er; - par->is_leaf = false; - - p0 = voronoiParabola_newSite(par->site); - p1 = voronoiParabola_newSite(site); - p2 = voronoiParabola_newSite(par->site); - - voronoiParabola_setRight(par, p2); - voronoiParabola_setLeft(par, voronoiParabola_new()); - par->left->edge = el; - - voronoiParabola_setLeft(par->left, p0); - voronoiParabola_setRight(par->left, p1); - - voronoi_checkCircle(process, p0); - voronoi_checkCircle(process, p2); -} - -static void voronoi_removeParabola(VoronoiProcess *process, VoronoiEvent *event) -{ - VoronoiParabola *p1 = event->parabola; - - VoronoiParabola *xl = voronoiParabola_getLeftParent(p1); - VoronoiParabola *xr = voronoiParabola_getRightParent(p1); - - VoronoiParabola *p0 = voronoiParabola_getLeftChild(xl); - VoronoiParabola *p2 = voronoiParabola_getRightChild(xr); - - VoronoiParabola *higher = NULL, *par, *gparent; - - float p[2]; - - if (p0->event) { - BLI_freelinkN(&process->queue, p0->event); - p0->event = NULL; - } - - if (p2->event) { - BLI_freelinkN(&process->queue, p2->event); - p2->event = NULL; - } - - p[0] = event->site[0]; - p[1] = voronoi_getY(process, p1->site, event->site[0]); - - copy_v2_v2(xl->edge->end, p); - copy_v2_v2(xr->edge->end, p); - - par = p1; - while (par != process->root) { - par = par->parent; - - if (par == xl) - higher = xl; - if (par == xr) - higher = xr; - } - - higher->edge = voronoiEdge_new(p, p0->site, p2->site); - BLI_addtail(&process->edges, higher->edge); - - gparent = p1->parent->parent; - if (p1->parent->left == p1) { - if (gparent->left == p1->parent) - voronoiParabola_setLeft(gparent, p1->parent->right); - if (gparent->right == p1->parent) - voronoiParabola_setRight(gparent, p1->parent->right); - } - else { - if (gparent->left == p1->parent) - voronoiParabola_setLeft(gparent, p1->parent->left); - if (gparent->right == p1->parent) - voronoiParabola_setRight(gparent, p1->parent->left); - } - - MEM_freeN(p1->parent); - MEM_freeN(p1); - - voronoi_checkCircle(process, p0); - voronoi_checkCircle(process, p2); -} - -static void voronoi_finishEdge(VoronoiProcess *process, VoronoiParabola *parabola) -{ - float mx; - - if (parabola->is_leaf) { - MEM_freeN(parabola); - return; - } - - if (parabola->edge->direction[0] > 0.0f) - mx = max_ff(process->width, parabola->edge->start[0] + 10); - else - mx = min_ff(0.0f, parabola->edge->start[0] - 10.0f); - - parabola->edge->end[0] = mx; - parabola->edge->end[1] = mx * parabola->edge->f + parabola->edge->g; - - voronoi_finishEdge(process, parabola->left); - voronoi_finishEdge(process, parabola->right); - - MEM_freeN(parabola); -} - -static void voronoi_clampEdgeVertex(int width, int height, float *coord, float *other_coord) -{ - const float corners[4][2] = {{0.0f, 0.0f}, - {width - 1, 0.0f}, - {width - 1, height - 1}, - {0.0f, height - 1}}; - int i; - - if (IN_RANGE_INCL(coord[0], 0, width - 1) && IN_RANGE_INCL(coord[1], 0, height - 1)) { - return; - } - - for (i = 0; i < 4; i++) { - float v1[2], v2[2]; - float p[2]; - - copy_v2_v2(v1, corners[i]); - - if (i == 3) - copy_v2_v2(v2, corners[0]); - else - copy_v2_v2(v2, corners[i + 1]); - - if (isect_seg_seg_v2_point(v1, v2, coord, other_coord, p) == 1) { - if (i == 0 && coord[1] > p[1]) - continue; - if (i == 1 && coord[0] < p[0]) - continue; - if (i == 2 && coord[1] < p[1]) - continue; - if (i == 3 && coord[0] > p[0]) - continue; - - copy_v2_v2(coord, p); - } - } -} - -static void voronoi_clampEdges(ListBase *edges, int width, int height, ListBase *clamped_edges) -{ - VoronoiEdge *edge; - - edge = edges->first; - while (edge) { - VoronoiEdge *new_edge = MEM_callocN(sizeof(VoronoiEdge), "clamped edge"); - - *new_edge = *edge; - BLI_addtail(clamped_edges, new_edge); - - voronoi_clampEdgeVertex(width, height, new_edge->start, new_edge->end); - voronoi_clampEdgeVertex(width, height, new_edge->end, new_edge->start); - - edge = edge->next; - } -} - -static int voronoi_getNextSideCoord(ListBase *edges, float coord[2], int dim, int dir, float next_coord[2]) -{ - VoronoiEdge *edge = edges->first; - float distance = FLT_MAX; - int other_dim = dim ? 0 : 1; - - while (edge) { - bool ok = false; - float co[2], cur_distance; - - if (fabsf(edge->start[other_dim] - coord[other_dim]) < VORONOI_EPS && - len_squared_v2v2(coord, edge->start) > VORONOI_EPS) - { - copy_v2_v2(co, edge->start); - ok = true; - } - - if (fabsf(edge->end[other_dim] - coord[other_dim]) < VORONOI_EPS && - len_squared_v2v2(coord, edge->end) > VORONOI_EPS) - { - copy_v2_v2(co, edge->end); - ok = true; - } - - if (ok) { - if (dir > 0 && coord[dim] > co[dim]) { - ok = false; - } - else if (dir < 0 && coord[dim] < co[dim]) { - ok = false; - } - } - - if (ok) { - cur_distance = len_squared_v2v2(coord, co); - if (cur_distance < distance) { - copy_v2_v2(next_coord, co); - distance = cur_distance; - } - } - - edge = edge->next; - } - - return distance < FLT_MAX; -} - -static void voronoi_createBoundaryEdges(ListBase *edges, int width, int height) -{ - const float corners[4][2] = {{width - 1, 0.0f}, - {width - 1, height - 1}, - {0.0f, height - 1}, - {0.0f, 0.0f}}; - int i, dim = 0, dir = 1; - - float coord[2] = {0.0f, 0.0f}; - float next_coord[2] = {0.0f, 0.0f}; - - for (i = 0; i < 4; i++) { - while (voronoi_getNextSideCoord(edges, coord, dim, dir, next_coord)) { - VoronoiEdge *edge = MEM_callocN(sizeof(VoronoiEdge), "boundary edge"); - - copy_v2_v2(edge->start, coord); - copy_v2_v2(edge->end, next_coord); - BLI_addtail(edges, edge); - - copy_v2_v2(coord, next_coord); - } - - if (len_squared_v2v2(coord, corners[i]) > VORONOI_EPS) { - VoronoiEdge *edge = MEM_callocN(sizeof(VoronoiEdge), "boundary edge"); - - copy_v2_v2(edge->start, coord); - copy_v2_v2(edge->end, corners[i]); - BLI_addtail(edges, edge); - copy_v2_v2(coord, corners[i]); - } - - dim = dim ? 0 : 1; - if (i == 1) - dir = -1; - } -} - -void BLI_voronoi_compute(const VoronoiSite *sites, int sites_total, int width, int height, ListBase *edges) -{ - VoronoiProcess process; - VoronoiEdge *edge; - int i; - - memset(&process, 0, sizeof(VoronoiProcess)); - - process.width = width; - process.height = height; - - for (i = 0; i < sites_total; i++) { - VoronoiEvent *event = MEM_callocN(sizeof(VoronoiEvent), "voronoi site event"); - - event->type = voronoiEventType_Site; - copy_v2_v2(event->site, sites[i].co); - - voronoi_insertEvent(&process, event); - } - - while (process.queue.first) { - VoronoiEvent *event = process.queue.first; - - process.current_y = event->site[1]; - - if (event->type == voronoiEventType_Site) { - voronoi_addParabola(&process, event->site); - } - else { - voronoi_removeParabola(&process, event); - } - - BLI_freelinkN(&process.queue, event); - } - - voronoi_finishEdge(&process, process.root); - - edge = process.edges.first; - while (edge) { - if (edge->neighbor) { - copy_v2_v2(edge->start, edge->neighbor->end); - MEM_freeN(edge->neighbor); - } - - edge = edge->next; - } - - BLI_movelisttolist(edges, &process.edges); -} - -static bool testVoronoiEdge(const float site[2], const float point[2], const VoronoiEdge *edge) -{ - float p[2]; - - if (isect_seg_seg_v2_point(site, point, edge->start, edge->end, p) == 1) { - if (len_squared_v2v2(p, edge->start) > VORONOI_EPS && - len_squared_v2v2(p, edge->end) > VORONOI_EPS) - { - return false; - } - } - - return true; -} - -static int voronoi_addTriangulationPoint(const float coord[2], const float color[3], - VoronoiTriangulationPoint **triangulated_points, - int *triangulated_points_total) -{ - VoronoiTriangulationPoint *triangulation_point; - int i; - - for (i = 0; i < *triangulated_points_total; i++) { - if (equals_v2v2(coord, (*triangulated_points)[i].co)) { - triangulation_point = &(*triangulated_points)[i]; - - add_v3_v3(triangulation_point->color, color); - triangulation_point->power++; - - return i; - } - } - - if (*triangulated_points) { - *triangulated_points = MEM_reallocN(*triangulated_points, - sizeof(VoronoiTriangulationPoint) * (*triangulated_points_total + 1)); - } - else { - *triangulated_points = MEM_callocN(sizeof(VoronoiTriangulationPoint), "triangulation points"); - } - - triangulation_point = &(*triangulated_points)[(*triangulated_points_total)]; - copy_v2_v2(triangulation_point->co, coord); - copy_v3_v3(triangulation_point->color, color); - - triangulation_point->power = 1; - - (*triangulated_points_total)++; - - return (*triangulated_points_total) - 1; -} - -static void voronoi_addTriangle(int v1, int v2, int v3, int (**triangles)[3], int *triangles_total) -{ - int *triangle; - - if (*triangles) { - *triangles = MEM_reallocN(*triangles, sizeof(int[3]) * (*triangles_total + 1)); - } - else { - *triangles = MEM_callocN(sizeof(int[3]), "trianglulation triangles"); - } - - triangle = (int *)&(*triangles)[(*triangles_total)]; - - triangle[0] = v1; - triangle[1] = v2; - triangle[2] = v3; - - (*triangles_total)++; -} - -void BLI_voronoi_triangulate(const VoronoiSite *sites, int sites_total, ListBase *edges, int width, int height, - VoronoiTriangulationPoint **triangulated_points_r, int *triangulated_points_total_r, - int (**triangles_r)[3], int *triangles_total_r) -{ - VoronoiTriangulationPoint *triangulated_points = NULL; - int (*triangles)[3] = NULL; - int triangulated_points_total = 0, triangles_total = 0; - int i; - ListBase boundary_edges = {NULL, NULL}; - - voronoi_clampEdges(edges, width, height, &boundary_edges); - voronoi_createBoundaryEdges(&boundary_edges, width, height); - - for (i = 0; i < sites_total; i++) { - VoronoiEdge *edge; - int v1; - - v1 = voronoi_addTriangulationPoint(sites[i].co, sites[i].color, &triangulated_points, &triangulated_points_total); - - edge = boundary_edges.first; - while (edge) { - VoronoiEdge *test_edge = boundary_edges.first; - bool ok_start = true, ok_end = true; - - while (test_edge) { - if (ok_start && !testVoronoiEdge(sites[i].co, edge->start, test_edge)) { - ok_start = false; - break; - } - - if (ok_end && !testVoronoiEdge(sites[i].co, edge->end, test_edge)) { - ok_end = false; - break; - } - - test_edge = test_edge->next; - } - - if (ok_start && ok_end) { - int v2, v3; - - v2 = voronoi_addTriangulationPoint(edge->start, sites[i].color, &triangulated_points, &triangulated_points_total); - v3 = voronoi_addTriangulationPoint(edge->end, sites[i].color, &triangulated_points, &triangulated_points_total); - - voronoi_addTriangle(v1, v2, v3, &triangles, &triangles_total); - } - - edge = edge->next; - } - } - - for (i = 0; i < triangulated_points_total; i++) { - VoronoiTriangulationPoint *triangulation_point = &triangulated_points[i]; - - mul_v3_fl(triangulation_point->color, 1.0f / triangulation_point->power); - } - - *triangulated_points_r = triangulated_points; - *triangulated_points_total_r = triangulated_points_total; - - *triangles_r = triangles; - *triangles_total_r = triangles_total; - - BLI_freelistN(&boundary_edges); -} diff --git a/source/blender/blenlib/intern/voronoi_2d.c b/source/blender/blenlib/intern/voronoi_2d.c new file mode 100644 index 00000000000..40e98d5914c --- /dev/null +++ b/source/blender/blenlib/intern/voronoi_2d.c @@ -0,0 +1,830 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2012 Blender Foundation. + * All rights reserved. + * + * Contributor(s): Sergey Sharybin + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenlib/intern/voronoi_2d.c + * \ingroup bli + * + * Fortune's algorithm implemented using explanation and some code snippets from + * http://blog.ivank.net/fortunes-algorithm-and-implementation.html + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_listbase.h" +#include "BLI_math.h" +#include "BLI_voronoi_2d.h" +#include "BLI_utildefines.h" + +#define VORONOI_EPS 1e-2f + +enum { + voronoiEventType_Site = 0, + voronoiEventType_Circle = 1 +}; + +typedef struct VoronoiEvent { + struct VoronoiEvent *next, *prev; + + int type; /* type of event (site or circle) */ + float site[2]; /* site for which event was generated */ + + struct VoronoiParabola *parabola; /* parabola for which event was generated */ +} VoronoiEvent; + +typedef struct VoronoiParabola { + struct VoronoiParabola *left, *right, *parent; + VoronoiEvent *event; + VoronoiEdge *edge; + float site[2]; + bool is_leaf; +} VoronoiParabola; + +typedef struct VoronoiProcess { + ListBase queue, edges; + VoronoiParabola *root; + int width, height; + float current_y; +} VoronoiProcess; + +/* event */ + +static void voronoi_insertEvent(VoronoiProcess *process, VoronoiEvent *event) +{ + VoronoiEvent *current_event = process->queue.first; + + while (current_event) { + if (current_event->site[1] < event->site[1]) { + break; + } + if (current_event->site[1] == event->site[1]) { + event->site[1] -= VORONOI_EPS; + } + + current_event = current_event->next; + } + + BLI_insertlinkbefore(&process->queue, current_event, event); +} + +/* edge */ +static VoronoiEdge *voronoiEdge_new(float start[2], float left[2], float right[2]) +{ + VoronoiEdge *edge = MEM_callocN(sizeof(VoronoiEdge), "voronoi edge"); + + copy_v2_v2(edge->start, start); + copy_v2_v2(edge->left, left); + copy_v2_v2(edge->right, right); + + edge->neighbor = NULL; + edge->end[0] = 0; + edge->end[1] = 0; + + edge->f = (right[0] - left[0]) / (left[1] - right[1]); + edge->g = start[1] - edge->f * start[0]; + + edge->direction[0] = right[1] - left[1]; + edge->direction[1] = -(right[0] - left[0]); + + return edge; +} + +/* parabola */ + +static VoronoiParabola *voronoiParabola_new(void) +{ + VoronoiParabola *parabola = MEM_callocN(sizeof(VoronoiParabola), "voronoi parabola"); + + parabola->is_leaf = false; + parabola->event = NULL; + parabola->edge = NULL; + parabola->parent = NULL; + + return parabola; +} + +static VoronoiParabola *voronoiParabola_newSite(float site[2]) +{ + VoronoiParabola *parabola = MEM_callocN(sizeof(VoronoiParabola), "voronoi parabola site"); + + copy_v2_v2(parabola->site, site); + parabola->is_leaf = true; + parabola->event = NULL; + parabola->edge = NULL; + parabola->parent = NULL; + + return parabola; +} + +/* returns the closest leave which is on the left of current node */ +static VoronoiParabola *voronoiParabola_getLeftChild(VoronoiParabola *parabola) +{ + VoronoiParabola *current_parabola; + + if (!parabola) + return NULL; + + current_parabola = parabola->left; + while (!current_parabola->is_leaf) { + current_parabola = current_parabola->right; + } + + return current_parabola; +} + +/* returns the closest leave which is on the right of current node */ +static VoronoiParabola *voronoiParabola_getRightChild(VoronoiParabola *parabola) +{ + VoronoiParabola *current_parabola; + + if (!parabola) + return NULL; + + current_parabola = parabola->right; + while (!current_parabola->is_leaf) { + current_parabola = current_parabola->left; + } + + return current_parabola; +} + +/* returns the closest parent which is on the left */ +static VoronoiParabola *voronoiParabola_getLeftParent(VoronoiParabola *parabola) +{ + VoronoiParabola *current_par = parabola->parent; + VoronoiParabola *last_parabola = parabola; + + while (current_par->left == last_parabola) { + if (!current_par->parent) + return NULL; + + last_parabola = current_par; + current_par = current_par->parent; + } + + return current_par; +} + +/* returns the closest parent which is on the right */ +static VoronoiParabola *voronoiParabola_getRightParent(VoronoiParabola *parabola) +{ + VoronoiParabola *current_parabola = parabola->parent; + VoronoiParabola *last_parabola = parabola; + + while (current_parabola->right == last_parabola) { + if (!current_parabola->parent) + return NULL; + + last_parabola = current_parabola; + current_parabola = current_parabola->parent; + } + + return current_parabola; +} + +static void voronoiParabola_setLeft(VoronoiParabola *parabola, VoronoiParabola *left) +{ + parabola->left = left; + left->parent = parabola; +} + +static void voronoiParabola_setRight(VoronoiParabola *parabola, VoronoiParabola *right) +{ + parabola->right = right; + right->parent = parabola; +} + +static float voronoi_getY(VoronoiProcess *process, float p[2], float x) +{ + float ly = process->current_y; + + float dp = 2 * (p[1] - ly); + float a1 = 1 / dp; + float b1 = -2 * p[0] / dp; + float c1 = ly + dp / 4 + p[0] * p[0] / dp; + + return a1 * x * x + b1 * x + c1; +} + +static float voronoi_getXOfEdge(VoronoiProcess *process, VoronoiParabola *par, float y) +{ + VoronoiParabola *left = voronoiParabola_getLeftChild(par); + VoronoiParabola *right = voronoiParabola_getRightChild(par); + float p[2], r[2]; + float dp, a1, b1, c1, a2, b2, c2, a, b, c, disc, ry, x1, x2; + float ly = process->current_y; + + copy_v2_v2(p, left->site); + copy_v2_v2(r, right->site); + + dp = 2.0f * (p[1] - y); + a1 = 1.0f / dp; + b1 = -2.0f * p[0] / dp; + c1 = y + dp / 4 + p[0] * p[0] / dp; + + dp = 2.0f * (r[1] - y); + a2 = 1.0f / dp; + b2 = -2.0f * r[0] / dp; + c2 = ly + dp / 4 + r[0] * r[0] / dp; + + a = a1 - a2; + b = b1 - b2; + c = c1 - c2; + + disc = b * b - 4 * a * c; + x1 = (-b + sqrtf(disc)) / (2 * a); + x2 = (-b - sqrtf(disc)) / (2 * a); + + if (p[1] < r[1]) + ry = max_ff(x1, x2); + else + ry = min_ff(x1, x2); + + return ry; +} + +static VoronoiParabola *voronoi_getParabolaByX(VoronoiProcess *process, float xx) +{ + VoronoiParabola *par = process->root; + float x = 0.0f; + float ly = process->current_y; + + while (!par->is_leaf) { + x = voronoi_getXOfEdge(process, par, ly); + + if (x > xx) + par = par->left; + else + par = par->right; + } + + return par; +} + +static int voronoi_getEdgeIntersection(VoronoiEdge *a, VoronoiEdge *b, float p[2]) +{ + float x = (b->g - a->g) / (a->f - b->f); + float y = a->f * x + a->g; + + if ((x - a->start[0]) / a->direction[0] < 0) + return 0; + + if ((y - a->start[1]) / a->direction[1] < 0) + return 0; + + if ((x - b->start[0]) / b->direction[0] < 0) + return 0; + + if ((y - b->start[1]) / b->direction[1] < 0) + return 0; + + p[0] = x; + p[1] = y; + + return 1; +} + +static void voronoi_checkCircle(VoronoiProcess *process, VoronoiParabola *b) +{ + VoronoiParabola *lp = voronoiParabola_getLeftParent(b); + VoronoiParabola *rp = voronoiParabola_getRightParent(b); + + VoronoiParabola *a = voronoiParabola_getLeftChild(lp); + VoronoiParabola *c = voronoiParabola_getRightChild(rp); + + VoronoiEvent *event; + + float ly = process->current_y; + float s[2], dx, dy, d; + + if (!a || !c || len_squared_v2v2(a->site, c->site) < VORONOI_EPS) + return; + + if (!voronoi_getEdgeIntersection(lp->edge, rp->edge, s)) + return; + + dx = a->site[0] - s[0]; + dy = a->site[1] - s[1]; + + d = sqrtf((dx * dx) + (dy * dy)); + + if (s[1] - d >= ly) + return; + + event = MEM_callocN(sizeof(VoronoiEvent), "voronoi circle event"); + + event->type = voronoiEventType_Circle; + + event->site[0] = s[0]; + event->site[1] = s[1] - d; + + b->event = event; + event->parabola = b; + + voronoi_insertEvent(process, event); +} + +static void voronoi_addParabola(VoronoiProcess *process, float site[2]) +{ + VoronoiParabola *root = process->root; + VoronoiParabola *par, *p0, *p1, *p2; + VoronoiEdge *el, *er; + float start[2]; + + if (!process->root) { + process->root = voronoiParabola_newSite(site); + + return; + } + + if (root->is_leaf && root->site[1] - site[1] < 0) { + float *fp = root->site; + float s[2]; + + root->is_leaf = false; + voronoiParabola_setLeft(root, voronoiParabola_newSite(fp)); + voronoiParabola_setRight(root, voronoiParabola_newSite(site)); + + s[0] = (site[0] + fp[0]) / 2.0f; + s[1] = process->height; + + if (site[0] > fp[0]) + root->edge = voronoiEdge_new(s, fp, site); + else + root->edge = voronoiEdge_new(s, site, fp); + + BLI_addtail(&process->edges, root->edge); + + return; + } + + par = voronoi_getParabolaByX(process, site[0]); + + if (par->event) { + BLI_freelinkN(&process->queue, par->event); + + par->event = NULL; + } + + start[0] = site[0]; + start[1] = voronoi_getY(process, par->site, site[0]); + + el = voronoiEdge_new(start, par->site, site); + er = voronoiEdge_new(start, site, par->site); + + el->neighbor = er; + BLI_addtail(&process->edges, el); + + par->edge = er; + par->is_leaf = false; + + p0 = voronoiParabola_newSite(par->site); + p1 = voronoiParabola_newSite(site); + p2 = voronoiParabola_newSite(par->site); + + voronoiParabola_setRight(par, p2); + voronoiParabola_setLeft(par, voronoiParabola_new()); + par->left->edge = el; + + voronoiParabola_setLeft(par->left, p0); + voronoiParabola_setRight(par->left, p1); + + voronoi_checkCircle(process, p0); + voronoi_checkCircle(process, p2); +} + +static void voronoi_removeParabola(VoronoiProcess *process, VoronoiEvent *event) +{ + VoronoiParabola *p1 = event->parabola; + + VoronoiParabola *xl = voronoiParabola_getLeftParent(p1); + VoronoiParabola *xr = voronoiParabola_getRightParent(p1); + + VoronoiParabola *p0 = voronoiParabola_getLeftChild(xl); + VoronoiParabola *p2 = voronoiParabola_getRightChild(xr); + + VoronoiParabola *higher = NULL, *par, *gparent; + + float p[2]; + + if (p0->event) { + BLI_freelinkN(&process->queue, p0->event); + p0->event = NULL; + } + + if (p2->event) { + BLI_freelinkN(&process->queue, p2->event); + p2->event = NULL; + } + + p[0] = event->site[0]; + p[1] = voronoi_getY(process, p1->site, event->site[0]); + + copy_v2_v2(xl->edge->end, p); + copy_v2_v2(xr->edge->end, p); + + par = p1; + while (par != process->root) { + par = par->parent; + + if (par == xl) + higher = xl; + if (par == xr) + higher = xr; + } + + higher->edge = voronoiEdge_new(p, p0->site, p2->site); + BLI_addtail(&process->edges, higher->edge); + + gparent = p1->parent->parent; + if (p1->parent->left == p1) { + if (gparent->left == p1->parent) + voronoiParabola_setLeft(gparent, p1->parent->right); + if (gparent->right == p1->parent) + voronoiParabola_setRight(gparent, p1->parent->right); + } + else { + if (gparent->left == p1->parent) + voronoiParabola_setLeft(gparent, p1->parent->left); + if (gparent->right == p1->parent) + voronoiParabola_setRight(gparent, p1->parent->left); + } + + MEM_freeN(p1->parent); + MEM_freeN(p1); + + voronoi_checkCircle(process, p0); + voronoi_checkCircle(process, p2); +} + +static void voronoi_finishEdge(VoronoiProcess *process, VoronoiParabola *parabola) +{ + float mx; + + if (parabola->is_leaf) { + MEM_freeN(parabola); + return; + } + + if (parabola->edge->direction[0] > 0.0f) + mx = max_ff(process->width, parabola->edge->start[0] + 10); + else + mx = min_ff(0.0f, parabola->edge->start[0] - 10.0f); + + parabola->edge->end[0] = mx; + parabola->edge->end[1] = mx * parabola->edge->f + parabola->edge->g; + + voronoi_finishEdge(process, parabola->left); + voronoi_finishEdge(process, parabola->right); + + MEM_freeN(parabola); +} + +static void voronoi_clampEdgeVertex(int width, int height, float *coord, float *other_coord) +{ + const float corners[4][2] = {{0.0f, 0.0f}, + {width - 1, 0.0f}, + {width - 1, height - 1}, + {0.0f, height - 1}}; + int i; + + if (IN_RANGE_INCL(coord[0], 0, width - 1) && IN_RANGE_INCL(coord[1], 0, height - 1)) { + return; + } + + for (i = 0; i < 4; i++) { + float v1[2], v2[2]; + float p[2]; + + copy_v2_v2(v1, corners[i]); + + if (i == 3) + copy_v2_v2(v2, corners[0]); + else + copy_v2_v2(v2, corners[i + 1]); + + if (isect_seg_seg_v2_point(v1, v2, coord, other_coord, p) == 1) { + if (i == 0 && coord[1] > p[1]) + continue; + if (i == 1 && coord[0] < p[0]) + continue; + if (i == 2 && coord[1] < p[1]) + continue; + if (i == 3 && coord[0] > p[0]) + continue; + + copy_v2_v2(coord, p); + } + } +} + +static void voronoi_clampEdges(ListBase *edges, int width, int height, ListBase *clamped_edges) +{ + VoronoiEdge *edge; + + edge = edges->first; + while (edge) { + VoronoiEdge *new_edge = MEM_callocN(sizeof(VoronoiEdge), "clamped edge"); + + *new_edge = *edge; + BLI_addtail(clamped_edges, new_edge); + + voronoi_clampEdgeVertex(width, height, new_edge->start, new_edge->end); + voronoi_clampEdgeVertex(width, height, new_edge->end, new_edge->start); + + edge = edge->next; + } +} + +static int voronoi_getNextSideCoord(ListBase *edges, float coord[2], int dim, int dir, float next_coord[2]) +{ + VoronoiEdge *edge = edges->first; + float distance = FLT_MAX; + int other_dim = dim ? 0 : 1; + + while (edge) { + bool ok = false; + float co[2], cur_distance; + + if (fabsf(edge->start[other_dim] - coord[other_dim]) < VORONOI_EPS && + len_squared_v2v2(coord, edge->start) > VORONOI_EPS) + { + copy_v2_v2(co, edge->start); + ok = true; + } + + if (fabsf(edge->end[other_dim] - coord[other_dim]) < VORONOI_EPS && + len_squared_v2v2(coord, edge->end) > VORONOI_EPS) + { + copy_v2_v2(co, edge->end); + ok = true; + } + + if (ok) { + if (dir > 0 && coord[dim] > co[dim]) { + ok = false; + } + else if (dir < 0 && coord[dim] < co[dim]) { + ok = false; + } + } + + if (ok) { + cur_distance = len_squared_v2v2(coord, co); + if (cur_distance < distance) { + copy_v2_v2(next_coord, co); + distance = cur_distance; + } + } + + edge = edge->next; + } + + return distance < FLT_MAX; +} + +static void voronoi_createBoundaryEdges(ListBase *edges, int width, int height) +{ + const float corners[4][2] = {{width - 1, 0.0f}, + {width - 1, height - 1}, + {0.0f, height - 1}, + {0.0f, 0.0f}}; + int i, dim = 0, dir = 1; + + float coord[2] = {0.0f, 0.0f}; + float next_coord[2] = {0.0f, 0.0f}; + + for (i = 0; i < 4; i++) { + while (voronoi_getNextSideCoord(edges, coord, dim, dir, next_coord)) { + VoronoiEdge *edge = MEM_callocN(sizeof(VoronoiEdge), "boundary edge"); + + copy_v2_v2(edge->start, coord); + copy_v2_v2(edge->end, next_coord); + BLI_addtail(edges, edge); + + copy_v2_v2(coord, next_coord); + } + + if (len_squared_v2v2(coord, corners[i]) > VORONOI_EPS) { + VoronoiEdge *edge = MEM_callocN(sizeof(VoronoiEdge), "boundary edge"); + + copy_v2_v2(edge->start, coord); + copy_v2_v2(edge->end, corners[i]); + BLI_addtail(edges, edge); + copy_v2_v2(coord, corners[i]); + } + + dim = dim ? 0 : 1; + if (i == 1) + dir = -1; + } +} + +void BLI_voronoi_compute(const VoronoiSite *sites, int sites_total, int width, int height, ListBase *edges) +{ + VoronoiProcess process; + VoronoiEdge *edge; + int i; + + memset(&process, 0, sizeof(VoronoiProcess)); + + process.width = width; + process.height = height; + + for (i = 0; i < sites_total; i++) { + VoronoiEvent *event = MEM_callocN(sizeof(VoronoiEvent), "voronoi site event"); + + event->type = voronoiEventType_Site; + copy_v2_v2(event->site, sites[i].co); + + voronoi_insertEvent(&process, event); + } + + while (process.queue.first) { + VoronoiEvent *event = process.queue.first; + + process.current_y = event->site[1]; + + if (event->type == voronoiEventType_Site) { + voronoi_addParabola(&process, event->site); + } + else { + voronoi_removeParabola(&process, event); + } + + BLI_freelinkN(&process.queue, event); + } + + voronoi_finishEdge(&process, process.root); + + edge = process.edges.first; + while (edge) { + if (edge->neighbor) { + copy_v2_v2(edge->start, edge->neighbor->end); + MEM_freeN(edge->neighbor); + } + + edge = edge->next; + } + + BLI_movelisttolist(edges, &process.edges); +} + +static bool testVoronoiEdge(const float site[2], const float point[2], const VoronoiEdge *edge) +{ + float p[2]; + + if (isect_seg_seg_v2_point(site, point, edge->start, edge->end, p) == 1) { + if (len_squared_v2v2(p, edge->start) > VORONOI_EPS && + len_squared_v2v2(p, edge->end) > VORONOI_EPS) + { + return false; + } + } + + return true; +} + +static int voronoi_addTriangulationPoint(const float coord[2], const float color[3], + VoronoiTriangulationPoint **triangulated_points, + int *triangulated_points_total) +{ + VoronoiTriangulationPoint *triangulation_point; + int i; + + for (i = 0; i < *triangulated_points_total; i++) { + if (equals_v2v2(coord, (*triangulated_points)[i].co)) { + triangulation_point = &(*triangulated_points)[i]; + + add_v3_v3(triangulation_point->color, color); + triangulation_point->power++; + + return i; + } + } + + if (*triangulated_points) { + *triangulated_points = MEM_reallocN(*triangulated_points, + sizeof(VoronoiTriangulationPoint) * (*triangulated_points_total + 1)); + } + else { + *triangulated_points = MEM_callocN(sizeof(VoronoiTriangulationPoint), "triangulation points"); + } + + triangulation_point = &(*triangulated_points)[(*triangulated_points_total)]; + copy_v2_v2(triangulation_point->co, coord); + copy_v3_v3(triangulation_point->color, color); + + triangulation_point->power = 1; + + (*triangulated_points_total)++; + + return (*triangulated_points_total) - 1; +} + +static void voronoi_addTriangle(int v1, int v2, int v3, int (**triangles)[3], int *triangles_total) +{ + int *triangle; + + if (*triangles) { + *triangles = MEM_reallocN(*triangles, sizeof(int[3]) * (*triangles_total + 1)); + } + else { + *triangles = MEM_callocN(sizeof(int[3]), "trianglulation triangles"); + } + + triangle = (int *)&(*triangles)[(*triangles_total)]; + + triangle[0] = v1; + triangle[1] = v2; + triangle[2] = v3; + + (*triangles_total)++; +} + +void BLI_voronoi_triangulate(const VoronoiSite *sites, int sites_total, ListBase *edges, int width, int height, + VoronoiTriangulationPoint **triangulated_points_r, int *triangulated_points_total_r, + int (**triangles_r)[3], int *triangles_total_r) +{ + VoronoiTriangulationPoint *triangulated_points = NULL; + int (*triangles)[3] = NULL; + int triangulated_points_total = 0, triangles_total = 0; + int i; + ListBase boundary_edges = {NULL, NULL}; + + voronoi_clampEdges(edges, width, height, &boundary_edges); + voronoi_createBoundaryEdges(&boundary_edges, width, height); + + for (i = 0; i < sites_total; i++) { + VoronoiEdge *edge; + int v1; + + v1 = voronoi_addTriangulationPoint(sites[i].co, sites[i].color, &triangulated_points, &triangulated_points_total); + + edge = boundary_edges.first; + while (edge) { + VoronoiEdge *test_edge = boundary_edges.first; + bool ok_start = true, ok_end = true; + + while (test_edge) { + if (ok_start && !testVoronoiEdge(sites[i].co, edge->start, test_edge)) { + ok_start = false; + break; + } + + if (ok_end && !testVoronoiEdge(sites[i].co, edge->end, test_edge)) { + ok_end = false; + break; + } + + test_edge = test_edge->next; + } + + if (ok_start && ok_end) { + int v2, v3; + + v2 = voronoi_addTriangulationPoint(edge->start, sites[i].color, &triangulated_points, &triangulated_points_total); + v3 = voronoi_addTriangulationPoint(edge->end, sites[i].color, &triangulated_points, &triangulated_points_total); + + voronoi_addTriangle(v1, v2, v3, &triangles, &triangles_total); + } + + edge = edge->next; + } + } + + for (i = 0; i < triangulated_points_total; i++) { + VoronoiTriangulationPoint *triangulation_point = &triangulated_points[i]; + + mul_v3_fl(triangulation_point->color, 1.0f / triangulation_point->power); + } + + *triangulated_points_r = triangulated_points; + *triangulated_points_total_r = triangulated_points_total; + + *triangles_r = triangles; + *triangles_total_r = triangles_total; + + BLI_freelistN(&boundary_edges); +} diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index 66d0a83eb9f..bcb940f8b96 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -36,8 +36,8 @@ #include "BLI_alloca.h" #include "BLI_math.h" #include "BLI_memarena.h" -#include "BLI_polyfill2d.h" -#include "BLI_polyfill2d_beautify.h" +#include "BLI_polyfill_2d.h" +#include "BLI_polyfill_2d_beautify.h" #include "BLI_linklist.h" #include "BLI_edgehash.h" #include "BLI_heap.h" diff --git a/source/blender/bmesh/operators/bmo_connect_concave.c b/source/blender/bmesh/operators/bmo_connect_concave.c index 80774323d31..d1811ac6a83 100644 --- a/source/blender/bmesh/operators/bmo_connect_concave.c +++ b/source/blender/bmesh/operators/bmo_connect_concave.c @@ -39,8 +39,8 @@ #include "BLI_alloca.h" #include "BLI_memarena.h" #include "BLI_heap.h" -#include "BLI_polyfill2d.h" -#include "BLI_polyfill2d_beautify.h" +#include "BLI_polyfill_2d.h" +#include "BLI_polyfill_2d_beautify.h" #include "BLI_linklist.h" #include "bmesh.h" diff --git a/source/blender/bmesh/tools/bmesh_beautify.c b/source/blender/bmesh/tools/bmesh_beautify.c index 81f0b4822a2..d3972363bb4 100644 --- a/source/blender/bmesh/tools/bmesh_beautify.c +++ b/source/blender/bmesh/tools/bmesh_beautify.c @@ -37,7 +37,7 @@ #include "BLI_math.h" #include "BLI_heap.h" -#include "BLI_polyfill2d_beautify.h" +#include "BLI_polyfill_2d_beautify.h" #include "MEM_guardedalloc.h" diff --git a/source/blender/bmesh/tools/bmesh_decimate_collapse.c b/source/blender/bmesh/tools/bmesh_decimate_collapse.c index 3aa9e5278bc..c1b2bc2625b 100644 --- a/source/blender/bmesh/tools/bmesh_decimate_collapse.c +++ b/source/blender/bmesh/tools/bmesh_decimate_collapse.c @@ -38,8 +38,8 @@ #include "BLI_alloca.h" #include "BLI_memarena.h" #include "BLI_edgehash.h" -#include "BLI_polyfill2d.h" -#include "BLI_polyfill2d_beautify.h" +#include "BLI_polyfill_2d.h" +#include "BLI_polyfill_2d_beautify.h" #include "BLI_utildefines_stack.h" diff --git a/source/blender/bmesh/tools/bmesh_triangulate.c b/source/blender/bmesh/tools/bmesh_triangulate.c index bd201fa89bf..a3a3355d20f 100644 --- a/source/blender/bmesh/tools/bmesh_triangulate.c +++ b/source/blender/bmesh/tools/bmesh_triangulate.c @@ -38,8 +38,8 @@ #include "BLI_linklist.h" /* only for defines */ -#include "BLI_polyfill2d.h" -#include "BLI_polyfill2d_beautify.h" +#include "BLI_polyfill_2d.h" +#include "BLI_polyfill_2d_beautify.h" #include "bmesh.h" diff --git a/source/blender/compositor/operations/COM_KeyingScreenOperation.h b/source/blender/compositor/operations/COM_KeyingScreenOperation.h index b1a5c0c39c7..45195b1e98d 100644 --- a/source/blender/compositor/operations/COM_KeyingScreenOperation.h +++ b/source/blender/compositor/operations/COM_KeyingScreenOperation.h @@ -35,7 +35,7 @@ #include "BLI_string.h" extern "C" { -# include "BLI_voronoi.h" +# include "BLI_voronoi_2d.h" } /** diff --git a/source/blender/compositor/operations/COM_PlaneDistortCommonOperation.cpp b/source/blender/compositor/operations/COM_PlaneDistortCommonOperation.cpp index 1145abd076a..75a85ad7e33 100644 --- a/source/blender/compositor/operations/COM_PlaneDistortCommonOperation.cpp +++ b/source/blender/compositor/operations/COM_PlaneDistortCommonOperation.cpp @@ -28,7 +28,7 @@ extern "C" { #include "BLI_listbase.h" #include "BLI_math.h" #include "BLI_math_color.h" -#include "BLI_jitter.h" +#include "BLI_jitter_2d.h" #include "BKE_movieclip.h" #include "BKE_node.h" diff --git a/source/blender/editors/animation/keyframes_edit.c b/source/blender/editors/animation/keyframes_edit.c index 9d25fc9e1a3..0ef6aa4bd4a 100644 --- a/source/blender/editors/animation/keyframes_edit.c +++ b/source/blender/editors/animation/keyframes_edit.c @@ -36,7 +36,7 @@ #include "BLI_blenlib.h" #include "BLI_utildefines.h" -#include "BLI_lasso.h" +#include "BLI_lasso_2d.h" #include "BLI_math.h" #include "DNA_anim_types.h" diff --git a/source/blender/editors/gpencil/drawgpencil.c b/source/blender/editors/gpencil/drawgpencil.c index 100e2dc8295..b23b9a06fbb 100644 --- a/source/blender/editors/gpencil/drawgpencil.c +++ b/source/blender/editors/gpencil/drawgpencil.c @@ -41,7 +41,7 @@ #include "BLI_math.h" #include "BLI_utildefines.h" -#include "BLI_polyfill2d.h" +#include "BLI_polyfill_2d.h" #include "BLF_api.h" #include "BLT_translation.h" diff --git a/source/blender/editors/gpencil/gpencil_select.c b/source/blender/editors/gpencil/gpencil_select.c index 07abab8af2e..dc3483163bf 100644 --- a/source/blender/editors/gpencil/gpencil_select.c +++ b/source/blender/editors/gpencil/gpencil_select.c @@ -37,7 +37,7 @@ #include "BLI_blenlib.h" #include "BLI_ghash.h" -#include "BLI_lasso.h" +#include "BLI_lasso_2d.h" #include "BLI_utildefines.h" #include "BLI_math_vector.h" diff --git a/source/blender/editors/mask/mask_select.c b/source/blender/editors/mask/mask_select.c index 9f2f6de8a09..7ffd82e262c 100644 --- a/source/blender/editors/mask/mask_select.c +++ b/source/blender/editors/mask/mask_select.c @@ -33,7 +33,7 @@ #include "BLI_utildefines.h" #include "BLI_rect.h" -#include "BLI_lasso.h" +#include "BLI_lasso_2d.h" #include "BLI_math.h" #include "BKE_context.h" diff --git a/source/blender/editors/physics/particle_edit.c b/source/blender/editors/physics/particle_edit.c index da66ec44235..1cbc6aa39fa 100644 --- a/source/blender/editors/physics/particle_edit.c +++ b/source/blender/editors/physics/particle_edit.c @@ -45,7 +45,7 @@ #include "DNA_space_types.h" #include "BLI_math.h" -#include "BLI_lasso.h" +#include "BLI_lasso_2d.h" #include "BLI_listbase.h" #include "BLI_string.h" #include "BLI_kdtree.h" diff --git a/source/blender/editors/sculpt_paint/paint_mask.c b/source/blender/editors/sculpt_paint/paint_mask.c index 264135d1d03..9d960980f30 100644 --- a/source/blender/editors/sculpt_paint/paint_mask.c +++ b/source/blender/editors/sculpt_paint/paint_mask.c @@ -41,7 +41,7 @@ #include "BLI_math_matrix.h" #include "BLI_math_geom.h" #include "BLI_utildefines.h" -#include "BLI_lasso.h" +#include "BLI_lasso_2d.h" #include "BLI_task.h" #include "BKE_pbvh.h" diff --git a/source/blender/editors/sculpt_paint/sculpt.c b/source/blender/editors/sculpt_paint/sculpt.c index d631a23bee0..67cd6e433c3 100644 --- a/source/blender/editors/sculpt_paint/sculpt.c +++ b/source/blender/editors/sculpt_paint/sculpt.c @@ -37,7 +37,7 @@ #include "BLI_math.h" #include "BLI_blenlib.h" -#include "BLI_dial.h" +#include "BLI_dial_2d.h" #include "BLI_task.h" #include "BLI_utildefines.h" #include "BLI_ghash.h" diff --git a/source/blender/editors/space_action/action_select.c b/source/blender/editors/space_action/action_select.c index 110c4d1789d..3c3a71d00fd 100644 --- a/source/blender/editors/space_action/action_select.c +++ b/source/blender/editors/space_action/action_select.c @@ -36,7 +36,7 @@ #include "BLI_blenlib.h" #include "BLI_dlrbTree.h" -#include "BLI_lasso.h" +#include "BLI_lasso_2d.h" #include "BLI_utildefines.h" #include "DNA_anim_types.h" diff --git a/source/blender/editors/space_clip/tracking_select.c b/source/blender/editors/space_clip/tracking_select.c index 4ee85ace271..ecbc1f5ae1e 100644 --- a/source/blender/editors/space_clip/tracking_select.c +++ b/source/blender/editors/space_clip/tracking_select.c @@ -37,7 +37,7 @@ #include "BLI_utildefines.h" #include "BLI_math.h" #include "BLI_rect.h" -#include "BLI_lasso.h" +#include "BLI_lasso_2d.h" #include "BKE_context.h" #include "BKE_tracking.h" diff --git a/source/blender/editors/space_graph/graph_select.c b/source/blender/editors/space_graph/graph_select.c index 392db4ef4b5..0b7ce7d7310 100644 --- a/source/blender/editors/space_graph/graph_select.c +++ b/source/blender/editors/space_graph/graph_select.c @@ -37,7 +37,7 @@ #include "BLI_blenlib.h" #include "BLI_math.h" #include "BLI_utildefines.h" -#include "BLI_lasso.h" +#include "BLI_lasso_2d.h" #include "DNA_anim_types.h" #include "DNA_screen_types.h" diff --git a/source/blender/editors/space_node/node_select.c b/source/blender/editors/space_node/node_select.c index dc7863bb354..4b4add0e698 100644 --- a/source/blender/editors/space_node/node_select.c +++ b/source/blender/editors/space_node/node_select.c @@ -34,7 +34,7 @@ #include "BLI_utildefines.h" #include "BLI_rect.h" -#include "BLI_lasso.h" +#include "BLI_lasso_2d.h" #include "BLI_math.h" #include "BLI_string.h" #include "BLI_string_utf8.h" diff --git a/source/blender/editors/space_view3d/view3d_draw.c b/source/blender/editors/space_view3d/view3d_draw.c index cdbb57c436a..f999fab88ac 100644 --- a/source/blender/editors/space_view3d/view3d_draw.c +++ b/source/blender/editors/space_view3d/view3d_draw.c @@ -48,7 +48,7 @@ #include "BLI_blenlib.h" #include "BLI_math.h" -#include "BLI_jitter.h" +#include "BLI_jitter_2d.h" #include "BLI_utildefines.h" #include "BLI_endian_switch.h" #include "BLI_threads.h" diff --git a/source/blender/editors/space_view3d/view3d_select.c b/source/blender/editors/space_view3d/view3d_select.c index 05cf552e5cc..82c239eb320 100644 --- a/source/blender/editors/space_view3d/view3d_select.c +++ b/source/blender/editors/space_view3d/view3d_select.c @@ -48,7 +48,7 @@ #include "MEM_guardedalloc.h" #include "BLI_math.h" -#include "BLI_lasso.h" +#include "BLI_lasso_2d.h" #include "BLI_rect.h" #include "BLI_linklist.h" #include "BLI_listbase.h" diff --git a/source/blender/editors/uvedit/uvedit_ops.c b/source/blender/editors/uvedit/uvedit_ops.c index 522640e4bda..928a0fc7d1e 100644 --- a/source/blender/editors/uvedit/uvedit_ops.c +++ b/source/blender/editors/uvedit/uvedit_ops.c @@ -49,7 +49,7 @@ #include "BLI_utildefines.h" #include "BLI_alloca.h" #include "BLI_math.h" -#include "BLI_lasso.h" +#include "BLI_lasso_2d.h" #include "BLI_blenlib.h" #include "BLI_array.h" diff --git a/source/blender/editors/uvedit/uvedit_parametrizer.c b/source/blender/editors/uvedit/uvedit_parametrizer.c index f8a93bd2ce3..c510c12ae53 100644 --- a/source/blender/editors/uvedit/uvedit_parametrizer.c +++ b/source/blender/editors/uvedit/uvedit_parametrizer.c @@ -32,8 +32,8 @@ #include "BLI_math.h" #include "BLI_rand.h" #include "BLI_heap.h" -#include "BLI_boxpack2d.h" -#include "BLI_convexhull2d.h" +#include "BLI_boxpack_2d.h" +#include "BLI_convexhull_2d.h" #include "uvedit_parametrizer.h" diff --git a/source/blender/python/mathutils/mathutils_bvhtree.c b/source/blender/python/mathutils/mathutils_bvhtree.c index 22e7bf3dd27..c044cc54965 100644 --- a/source/blender/python/mathutils/mathutils_bvhtree.c +++ b/source/blender/python/mathutils/mathutils_bvhtree.c @@ -33,7 +33,7 @@ #include "BLI_utildefines.h" #include "BLI_kdopbvh.h" -#include "BLI_polyfill2d.h" +#include "BLI_polyfill_2d.h" #include "BLI_math.h" #include "BLI_ghash.h" #include "BLI_memarena.h" diff --git a/source/blender/python/mathutils/mathutils_geometry.c b/source/blender/python/mathutils/mathutils_geometry.c index 72f92d210d7..fa0d271f7d3 100644 --- a/source/blender/python/mathutils/mathutils_geometry.c +++ b/source/blender/python/mathutils/mathutils_geometry.c @@ -34,8 +34,8 @@ #ifndef MATH_STANDALONE /* define when building outside blender */ # include "MEM_guardedalloc.h" # include "BLI_blenlib.h" -# include "BLI_boxpack2d.h" -# include "BLI_convexhull2d.h" +# include "BLI_boxpack_2d.h" +# include "BLI_convexhull_2d.h" # include "BKE_displist.h" # include "BKE_curve.h" #endif diff --git a/source/blender/render/intern/source/initrender.c b/source/blender/render/intern/source/initrender.c index fbf18405093..ce3331e9a92 100644 --- a/source/blender/render/intern/source/initrender.c +++ b/source/blender/render/intern/source/initrender.c @@ -38,7 +38,7 @@ #include "BLI_math.h" #include "BLI_blenlib.h" -#include "BLI_jitter.h" +#include "BLI_jitter_2d.h" #include "BLI_utildefines.h" #include "DNA_camera_types.h" diff --git a/source/blender/render/intern/source/shadbuf.c b/source/blender/render/intern/source/shadbuf.c index 7c62bf4cd94..fb441662829 100644 --- a/source/blender/render/intern/source/shadbuf.c +++ b/source/blender/render/intern/source/shadbuf.c @@ -40,7 +40,7 @@ #include "BLI_math.h" #include "BLI_blenlib.h" -#include "BLI_jitter.h" +#include "BLI_jitter_2d.h" #include "BLI_memarena.h" #include "BLI_rand.h" #include "BLI_utildefines.h" diff --git a/source/blender/render/intern/source/zbuf.c b/source/blender/render/intern/source/zbuf.c index 1481e7a8059..14184f4404b 100644 --- a/source/blender/render/intern/source/zbuf.c +++ b/source/blender/render/intern/source/zbuf.c @@ -42,7 +42,7 @@ #include "BLI_math.h" #include "BLI_blenlib.h" -#include "BLI_jitter.h" +#include "BLI_jitter_2d.h" #include "BLI_threads.h" #include "BLI_utildefines.h" diff --git a/source/blender/windowmanager/intern/wm_gesture.c b/source/blender/windowmanager/intern/wm_gesture.c index b63962ffce2..1a4381a1275 100644 --- a/source/blender/windowmanager/intern/wm_gesture.c +++ b/source/blender/windowmanager/intern/wm_gesture.c @@ -41,7 +41,7 @@ #include "BLI_blenlib.h" #include "BLI_math.h" #include "BLI_utildefines.h" -#include "BLI_lasso.h" +#include "BLI_lasso_2d.h" #include "BKE_context.h" diff --git a/source/blender/windowmanager/intern/wm_operators.c b/source/blender/windowmanager/intern/wm_operators.c index 4674df9983b..744f6cf0ef2 100644 --- a/source/blender/windowmanager/intern/wm_operators.c +++ b/source/blender/windowmanager/intern/wm_operators.c @@ -58,7 +58,7 @@ #include "PIL_time.h" #include "BLI_blenlib.h" -#include "BLI_dial.h" +#include "BLI_dial_2d.h" #include "BLI_dynstr.h" /*for WM_operator_pystring */ #include "BLI_math.h" #include "BLI_utildefines.h" -- cgit v1.2.3