Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender/blenlib
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r--source/blender/blenlib/BLI_arithb.h569
-rw-r--r--source/blender/blenlib/BLI_array.h91
-rw-r--r--source/blender/blenlib/BLI_cellalloc.h49
-rw-r--r--source/blender/blenlib/BLI_edgehash.h106
-rw-r--r--source/blender/blenlib/BLI_editVert.h3
-rw-r--r--source/blender/blenlib/BLI_ghash.h163
-rw-r--r--source/blender/blenlib/intern/BLI_cellalloc.c174
-rw-r--r--source/blender/blenlib/intern/BLI_ghash.c134
-rw-r--r--source/blender/blenlib/intern/BLI_mempool.c18
-rw-r--r--source/blender/blenlib/intern/edgehash.c124
-rw-r--r--source/blender/blenlib/intern/math_vector_inline.c21
-rw-r--r--source/blender/blenlib/intern/scanfill.c47
12 files changed, 1253 insertions, 246 deletions
diff --git a/source/blender/blenlib/BLI_arithb.h b/source/blender/blenlib/BLI_arithb.h
new file mode 100644
index 00000000000..dd673ff095e
--- /dev/null
+++ b/source/blender/blenlib/BLI_arithb.h
@@ -0,0 +1,569 @@
+#undef TEST_ACTIVE
+//#define ACTIVE 1
+/**
+ * blenlib/BLI_math.h mar 2001 Nzc
+ *
+ * $Id$
+ *
+ * ***** 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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_ARITHB_H
+#define BLI_ARITHB_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#ifdef WIN32
+#define _USE_MATH_DEFINES
+#endif
+
+#include <math.h>
+
+#ifndef M_PI
+#define M_PI 3.14159265358979323846
+#endif
+#ifndef M_PI_2
+#define M_PI_2 1.57079632679489661923
+#endif
+#ifndef M_SQRT2
+#define M_SQRT2 1.41421356237309504880
+#endif
+#ifndef M_SQRT1_2
+#define M_SQRT1_2 0.70710678118654752440
+#endif
+#ifndef M_1_PI
+#define M_1_PI 0.318309886183790671538
+#endif
+
+#ifndef M_E
+#define M_E 2.7182818284590452354
+#endif
+#ifndef M_LOG2E
+#define M_LOG2E 1.4426950408889634074
+#endif
+#ifndef M_LOG10E
+#define M_LOG10E 0.43429448190325182765
+#endif
+#ifndef M_LN2
+#define M_LN2 0.69314718055994530942
+#endif
+#ifndef M_LN10
+#define M_LN10 2.30258509299404568402
+#endif
+
+#ifndef sqrtf
+#define sqrtf(a) ((float)sqrt(a))
+#endif
+#ifndef powf
+#define powf(a, b) ((float)pow(a, b))
+#endif
+#ifndef cosf
+#define cosf(a) ((float)cos(a))
+#endif
+#ifndef sinf
+#define sinf(a) ((float)sin(a))
+#endif
+#ifndef acosf
+#define acosf(a) ((float)acos(a))
+#endif
+#ifndef asinf
+#define asinf(a) ((float)asin(a))
+#endif
+#ifndef atan2f
+#define atan2f(a, b) ((float)atan2(a, b))
+#endif
+#ifndef tanf
+#define tanf(a) ((float)tan(a))
+#endif
+#ifndef atanf
+#define atanf(a) ((float)atan(a))
+#endif
+#ifndef floorf
+#define floorf(a) ((float)floor(a))
+#endif
+#ifndef ceilf
+#define ceilf(a) ((float)ceil(a))
+#endif
+#ifndef fabsf
+#define fabsf(a) ((float)fabs(a))
+#endif
+#ifndef logf
+#define logf(a) ((float)log(a))
+#endif
+#ifndef expf
+#define expf(a) ((float)exp(a))
+#endif
+#ifndef fmodf
+#define fmodf(a, b) ((float)fmod(a, b))
+#endif
+
+#ifdef WIN32
+ #ifndef FREE_WINDOWS
+ #define isnan(n) _isnan(n)
+ #define finite _finite
+ #endif
+#endif
+
+#define MAT4_UNITY {{ 1.0, 0.0, 0.0, 0.0},\
+ { 0.0, 1.0, 0.0, 0.0},\
+ { 0.0, 0.0, 1.0, 0.0},\
+ { 0.0, 0.0, 0.0, 1.0}}
+
+#define MAT3_UNITY {{ 1.0, 0.0, 0.0},\
+ { 0.0, 1.0, 0.0},\
+ { 0.0, 0.0, 1.0}}
+
+
+void cent_tri_v3(float *cent, float *v1, float *v2, float *v3);
+void cent_quad_v3(float *cent, float *v1, float *v2, float *v3, float *v4);
+
+void cross_v3_v3v3(float *c, float *a, float *b);
+void project_v3_v3v3(float *c, float *v1, float *v2);
+
+float dot_v3v3(float *v1, float *v2);
+float dot_v2v2(float *v1, float *v2);
+
+float normalize_v3(float *n);
+float normalize_v2(float *n);
+double normalize_dv3(double n[3]);
+
+float Sqrt3f(float f);
+double sqrt3d(double d);
+
+float saacos(float fac);
+float saasin(float fac);
+float sasqrt(float fac);
+float saacosf(float fac);
+float saasinf(float fac);
+float sasqrtf(float fac);
+
+int compare_v3v3(float *v1, float *v2, float limit);
+int compare_v4v4(float *v1, float *v2, float limit);
+float interpf(float target, float origin, float fac);
+
+float normal_tri_v3( float *n,float *v1, float *v2, float *v3);
+float normal_quad_v3( float *n,float *v1, float *v2, float *v3, float *v4);
+
+void CalcNormLong(int *v1, int *v2, int *v3, float *n);
+/* CalcNormShort: is ook uitprodukt - (translates as 'is also out/cross product') */
+void CalcNormShort(short *v1, short *v2, short *v3, float *n);
+float power_of_2(float val);
+
+/**
+ * @section Euler conversion routines (With Custom Order)
+ */
+
+/* Defines for rotation orders
+ * WARNING: must match the eRotationModes in DNA_action_types.h
+ * order matters - types are saved to file!
+ */
+typedef enum eEulerRotationOrders {
+ EULER_ORDER_DEFAULT = 1, /* Blender 'default' (classic) is basically XYZ */
+ EULER_ORDER_XYZ = 1, /* Blender 'default' (classic) - must be as 1 to sync with PoseChannel rotmode */
+ EULER_ORDER_XZY,
+ EULER_ORDER_YXZ,
+ EULER_ORDER_YZX,
+ EULER_ORDER_ZXY,
+ EULER_ORDER_ZYX,
+ /* NOTE: there are about 6 more entries when including duplicated entries too */
+} eEulerRotationOrders;
+
+void eulO_to_quat( float quat[4],float eul[3], short order);
+void quat_to_eulO( float eul[3], short order,float quat[4]);
+
+void eulO_to_mat3( float Mat[3][3],float eul[3], short order);
+void eulO_to_mat4( float Mat[4][4],float eul[3], short order);
+
+void mat3_to_eulO( float eul[3], short order,float Mat[3][3]);
+void mat4_to_eulO( float eul[3], short order,float Mat[4][4]);
+
+void mat3_to_compatible_eulO( float eul[3], float oldrot[3], short order,float mat[3][3]);
+
+void rotate_eulO(float beul[3], short order, char axis, float ang);
+
+/**
+ * @section Euler conversion routines (Blender XYZ)
+ */
+
+void eul_to_mat3( float mat[][3],float *eul);
+void eul_to_mat4( float mat[][4],float *eul);
+
+void mat3_to_eul( float *eul,float tmat[][3]);
+void mat4_to_eul(float *eul,float tmat[][4]);
+
+void eul_to_quat( float *quat,float *eul);
+
+void mat3_to_compatible_eul( float *eul, float *oldrot,float mat[][3]);
+void eulO_to_gimbal_axis(float gmat[][3], float *eul, short order);
+
+
+void compatible_eul(float *eul, float *oldrot);
+void rotate_eul(float *beul, char axis, float ang);
+
+
+/**
+ * @section Quaternion arithmetic routines
+ */
+
+int is_zero_qt(float *q);
+void quat_to_eul( float *eul,float *quat);
+void unit_qt(float *);
+void mul_qt_qtqt(float *, float *, float *);
+void mul_qt_v3(float *q, float *v);
+void mul_qt_fl(float *q, float f);
+void mul_fac_qt_fl(float *q, float fac);
+
+void normalize_qt(float *);
+void axis_angle_to_quat( float *quat,float *vec, float phi);
+
+void sub_qt_qtqt(float *q, float *q1, float *q2);
+void conjugate_qt(float *q);
+void invert_qt(float *q);
+float dot_qtqt(float *q1, float *q2);
+void copy_qt_qt(float *q1, float *q2);
+
+void print_qt(char *str, float q[4]);
+
+void interp_qt_qtqt(float *result, float *quat1, float *quat2, float t);
+void add_qt_qtqt(float *result, float *quat1, float *quat2, float t);
+
+void quat_to_mat3( float m[][3],float *q);
+void quat_to_mat4( float m[][4],float *q);
+
+/**
+ * @section matrix multiplication and copying routines
+ */
+
+void mul_m3_fl(float *m, float f);
+void mul_m4_fl(float *m, float f);
+void mul_mat3_m4_fl(float *m, float f);
+
+void transpose_m3(float mat[][3]);
+void transpose_m4(float mat[][4]);
+
+int invert_m4_m4(float inverse[][4], float mat[][4]);
+void invert_m4_m4(float inverse[][4], float mat[][4]);
+void invert_m4_m4(float *m1, float *m2);
+void invert_m4_m4(float out[][4], float in[][4]);
+void invert_m3_m3(float m1[][3], float m2[][3]);
+
+void copy_m3_m4(float m1[][3],float m2[][4]);
+void copy_m4_m3(float m1[][4], float m2[][3]);
+
+void blend_m3_m3m3(float out[][3], float dst[][3], float src[][3], float srcweight);
+void blend_m4_m4m4(float out[][4], float dst[][4], float src[][4], float srcweight);
+
+float determinant_m2(float a,float b,float c, float d);
+
+float determinant_m3(
+ float a1, float a2, float a3,
+ float b1, float b2, float b3,
+ float c1, float c2, float c3
+);
+
+float determinant_m4(float m[][4]);
+
+void adjoint_m3_m3(float m1[][3], float m[][3]);
+void adjoint_m4_m4(float out[][4], float in[][4]);
+
+void mul_m4_m4m4(float m1[][4], float m2[][4], float m3[][4]);
+void subMat4MulMat4(float *m1, float *m2, float *m3);
+#ifndef TEST_ACTIVE
+void mul_m3_m3m3(float m1[][3], float m3[][3], float m2[][3]);
+#else
+void mul_m3_m3m3(float *m1, float *m3, float *m2);
+#endif
+void mul_m4_m3m4(float (*m1)[4], float (*m3)[3], float (*m2)[4]);
+void copy_m4_m4(float m1[][4], float m2[][4]);
+void swap_m4m4(float m1[][4], float m2[][4]);
+void copy_m3_m3(float m1[][3], float m2[][3]);
+
+void mul_serie_m3(float answ[][3],
+ float m1[][3], float m2[][3], float m3[][3],
+ float m4[][3], float m5[][3], float m6[][3],
+ float m7[][3], float m8[][3]
+);
+
+void mul_serie_m4(float answ[][4], float m1[][4],
+ float m2[][4], float m3[][4], float m4[][4],
+ float m5[][4], float m6[][4], float m7[][4],
+ float m8[][4]
+);
+
+void zero_m4(float *m);
+void zero_m3(float *m);
+
+void unit_m3(float m[][3]);
+void unit_m4(float m[][4]);
+
+/* NOTE: These only normalise the matrix, they don't make it orthogonal */
+void normalize_m3(float mat[][3]);
+void normalize_m4(float mat[][4]);
+
+int is_orthogonal_m3(float mat[][3]);
+void orthogonalize_m3(float mat[][3], int axis); /* axis is the one to keep in place (assumes it is non-null) */
+int is_orthogonal_m4(float mat[][4]);
+void orthogonalize_m4(float mat[][4], int axis); /* axis is the one to keep in place (assumes it is non-null) */
+
+void mul_v3_m4v3(float *in, float mat[][4], float *vec);
+void mul_m4_m4m3(float (*m1)[4], float (*m3)[4], float (*m2)[3]);
+void mul_m3_m3m4(float m1[][3], float m2[][3], float m3[][4]);
+
+void Mat4MulVec(float mat[][4],int *vec);
+void mul_m4_v3(float mat[][4], float *vec);
+void mul_mat3_m4_v3(float mat[][4], float *vec);
+void mul_project_m4_v4(float mat[][4],float *vec);
+void mul_m4_v4(float mat[][4], float *vec);
+void Mat3MulVec(float mat[][3],int *vec);
+void mul_m3_v3(float mat[][3], float *vec);
+void mul_m3_v3_double(float mat[][3], double *vec);
+void mul_transposed_m3_v3(float mat[][3], float *vec);
+
+void add_m3_m3m3(float m1[][3], float m2[][3], float m3[][3]);
+void add_m4_m4m4(float m1[][4], float m2[][4], float m3[][4]);
+
+void VecUpMat3old(float *vec, float mat[][3], short axis);
+void VecUpMat3(float *vec, float mat[][3], short axis);
+
+void copy_v3_v3(float *v1, float *v2);
+int VecLen(int *v1, int *v2);
+float len_v3v3(float v1[3], float v2[3]);
+float len_v3(float *v);
+void mul_v3_fl(float *v1, float f);
+void negate_v3(float *v1);
+
+int compare_len_v3v3(float *v1, float *v2, float limit);
+int compare_v3v3(float *v1, float *v2, float limit);
+int equals_v3v3(float *v1, float *v2);
+int is_zero_v3(float *v);
+
+void print_v3(char *str,float v[3]);
+void print_v4(char *str, float v[4]);
+
+void add_v3_v3v3(float *v, float *v1, float *v2);
+void sub_v3_v3v3(float *v, float *v1, float *v2);
+void mul_v3_v3v3(float *v, float *v1, float *v2);
+void interp_v3_v3v3(float *target, const float *a, const float *b, const float t);
+void interp_v3_v3v3v3(float p[3], const float v1[3], const float v2[3], const float v3[3], const float w[3]);
+void mid_v3_v3v3(float *v, float *v1, float *v2);
+
+void ortho_basis_v3v3_v3( float *v1, float *v2,float *v);
+
+float len_v2v2(float *v1, float *v2);
+float len_v2(float *v);
+void mul_v2_fl(float *v1, float f);
+void add_v2_v2v2(float *v, float *v1, float *v2);
+void sub_v2_v2v2(float *v, float *v1, float *v2);
+void copy_v2_v2(float *v1, float *v2);
+void interp_v2_v2v2(float *target, const float *a, const float *b, const float t);
+void interp_v2_v2v2v2(float p[2], const float v1[2], const float v2[2], const float v3[2], const float w[3]);
+
+void axis_angle_to_quat(float q[4], float axis[3], float angle);
+void quat_to_axis_angle( float axis[3], float *angle,float q[4]);
+void axis_angle_to_eulO( float eul[3], short order,float axis[3], float angle);
+void eulO_to_axis_angle( float axis[3], float *angle,float eul[3], short order);
+void axis_angle_to_mat3( float mat[3][3],float axis[3], float angle);
+void axis_angle_to_mat4( float mat[4][4],float axis[3], float angle);
+void mat3_to_axis_angle( float axis[3], float *angle,float mat[3][3]);
+void mat4_to_axis_angle( float axis[3], float *angle,float mat[4][4]);
+
+void mat3_to_vec_rot( float axis[3], float *angle,float mat[3][3]);
+void mat4_to_vec_rot( float axis[3], float *angle,float mat[4][4]);
+void vec_rot_to_mat3( float mat[][3],float *vec, float phi);
+void vec_rot_to_mat4( float mat[][4],float *vec, float phi);
+
+void rotation_between_vecs_to_quat(float *q, float v1[3], float v2[3]);
+void vec_to_quat( float *q,float *vec, short axis, short upflag);
+void mat3_to_quat_is_ok( float *q,float wmat[][3]);
+
+void reflect_v3_v3v3(float *out, float *v1, float *v2);
+void bisect_v3_v3v3v3(float *v, float *v1, float *v2, float *v3);
+float angle_v2v2(float *v1, float *v2);
+float angle_v3v3v3(float *v1, float *v2, float *v3);
+float angle_normalized_v3v3(float *v1, float *v2);
+
+float angle_v2v2v2(float *v1, float *v2, float *v3);
+float angle_normalized_v2v2(float *v1, float *v2);
+
+void normal_short_to_float_v3(float *out, short *in);
+void normal_float_to_short_v3(short *out, float *in);
+
+float dist_to_line_v2(float *v1, float *v2, float *v3);
+float dist_to_line_segment_v2(float *v1, float *v2, float *v3);
+float dist_to_line_segment_v3(float *v1, float *v2, float *v3);
+void closest_to_line_segment_v3(float *closest, float v1[3], float v2[3], float v3[3]);
+float area_tri_v2(float *v1, float *v2, float *v3);
+float area_quad_v3(float *v1, float *v2, float *v3, float *v4);
+float area_tri_v3(float *v1, float *v2, float *v3);
+float area_poly_v3(int nr, float *verts, float *normal);
+
+/* intersect Line-Line
+ return:
+ -1: colliniar
+ 0: no intersection of segments
+ 1: exact intersection of segments
+ 2: cross-intersection of segments
+*/
+extern short isect_line_line_v2(float *v1, float *v2, float *v3, float *v4);
+extern short isect_line_line_v2_short(short *v1, short *v2, short *v3, short *v4);
+
+/*point in tri, 0 no intersection, 1 intersect */
+int isect_point_tri_v2(float pt[2], float v1[2], float v2[2], float v3[2]);
+/* point in quad, 0 no intersection, 1 intersect */
+int isect_point_quad_v2(float pt[2], float v1[2], float v2[2], float v3[2], float v4[2]);
+
+/* interpolation weights of point in a triangle or quad, v4 may be NULL */
+void interp_weights_face_v3( float *w,float *v1, float *v2, float *v3, float *v4, float *co);
+/* interpolation weights of point in a polygon with >= 3 vertices */
+void interp_weights_poly_v3( float *w,float v[][3], int n, float *co);
+
+void i_lookat(
+ float vx, float vy,
+ float vz, float px,
+ float py, float pz,
+ float twist, float mat[][4]
+);
+
+void i_window(
+ float left, float right,
+ float bottom, float top,
+ float nearClip, float farClip,
+ float mat[][4]
+);
+
+#define BLI_CS_SMPTE 0
+#define BLI_CS_REC709 1
+#define BLI_CS_CIE 2
+
+#define RAD2DEG(_rad) ((_rad)*(180.0/M_PI))
+#define DEG2RAD(_deg) ((_deg)*(M_PI/180.0))
+
+void hsv_to_rgb(float h, float s, float v, float *r, float *g, float *b);
+void hex_to_rgb(char *hexcol, float *r, float *g, float *b);
+void rgb_to_yuv(float r, float g, float b, float *ly, float *lu, float *lv);
+void yuv_to_rgb(float y, float u, float v, float *lr, float *lg, float *lb);
+void ycc_to_rgb(float y, float cb, float cr, float *lr, float *lg, float *lb);
+void rgb_to_ycc(float r, float g, float b, float *ly, float *lcb, float *lcr);
+void rgb_to_hsv(float r, float g, float b, float *lh, float *ls, float *lv);
+void xyz_to_rgb(float x, float y, float z, float *r, float *g, float *b, int colorspace);
+int constrain_rgb(float *r, float *g, float *b);
+unsigned int hsv_to_cpack(float h, float s, float v);
+unsigned int rgb_to_cpack(float r, float g, float b);
+void cpack_to_rgb(unsigned int col, float *r, float *g, float *b);
+void minmax_rgb(short c[]);
+
+
+
+void star_m3_v3(float mat[][3],float *vec);
+
+short EenheidsMat(float mat[][3]);
+
+void orthographic_m4( float matrix[][4],float left, float right, float bottom, float top, float nearClip, float farClip);
+void polarview_m4( float Vm[][4],float dist, float azimuth, float incidence, float twist);
+void translate_m4( float mat[][4],float Tx, float Ty, float Tz);
+void i_multmatrix(float icand[][4], float Vm[][4]);
+void rotate_m4( float mat[][4], char axis,float angle);
+
+
+
+void minmax_v3_v3v3(float *min, float *max, float *vec);
+void size_to_mat3( float mat[][3],float *size);
+void size_to_mat4( float mat[][4],float *size);
+
+float mat3_to_scale(float mat[][3]);
+float mat4_to_scale(float mat[][4]);
+
+void print_m3(char *str, float m[][3]);
+void print_m4(char *str, float m[][4]);
+
+/* uit Sig.Proc.85 pag 253 */
+void mat3_to_quat( float *q,float wmat[][3]);
+void mat4_to_quat( float *q,float m[][4]);
+
+void mat3_to_size( float *size,float mat[][3]);
+void mat4_to_size( float *size,float mat[][4]);
+
+void tri_to_quat( float *quat,float *v1, float *v2, float *v3);
+
+void loc_eul_size_to_mat4(float mat[4][4], float loc[3], float eul[3], float size[3]);
+void loc_eulO_size_to_mat4(float mat[4][4], float loc[3], float eul[3], float size[3], short rotOrder);
+void loc_quat_size_to_mat4(float mat[4][4], float loc[3], float quat[4], float size[3]);
+
+void map_to_tube( float *u, float *v,float x, float y, float z);
+void map_to_sphere( float *u, float *v,float x, float y, float z);
+
+int isect_line_line_v3(float v1[3], float v2[3], float v3[3], float v4[3], float i1[3], float i2[3]);
+int isect_line_line_strict_v3(float v1[3], float v2[3], float v3[3], float v4[3], float vi[3], float *lambda);
+int isect_line_tri_v3(float p1[3], float p2[3], float v0[3], float v1[3], float v2[3], float *lambda, float *uv);
+int isect_ray_tri_v3(float p1[3], float d[3], float v0[3], float v1[3], float v2[3], float *lambda, float *uv);
+int isect_ray_tri_threshold_v3(float p1[3], float d[3], float v0[3], float v1[3], float v2[3], float *lambda, float *uv, float threshold);
+int isect_sweeping_sphere_tri_v3(float p1[3], float p2[3], float radius, float v0[3], float v1[3], float v2[3], float *lambda, float *ipoint);
+int isect_axial_line_tri_v3(int axis, float co1[3], float co2[3], float v0[3], float v1[3], float v2[3], float *lambda);
+int isect_aabb_aabb_v3(float min1[3], float max1[3], float min2[3], float max2[3]);
+void interp_cubic_v3( float *x, float *v,float *x1, float *v1, float *x2, float *v2, float t);
+void isect_point_quad_uv_v2(float v0[2], float v1[2], float v2[2], float v3[2], float pt[2], float *uv);
+void isect_point_face_uv_v2(int isquad, float v0[2], float v1[2], float v2[2], float v3[2], float pt[2], float *uv);
+int isect_point_tri_v2(float v1[2], float v2[2], float v3[2], float pt[2]);
+int isect_point_tri_v2_int(int x1, int y1, int x2, int y2, int a, int b);
+int isect_point_tri_prism_v3(float p[3], float v1[3], float v2[3], float v3[3]);
+
+float closest_to_line_v3( float cp[3],float p[3], float l1[3], float l2[3]);
+
+float shell_angle_to_dist(const float angle);
+
+typedef struct DualQuat {
+ float quat[4];
+ float trans[4];
+
+ float scale[4][4];
+ float scale_weight;
+} DualQuat;
+
+void mat4_to_dquat( DualQuat *dq,float basemat[][4], float mat[][4]);
+void dquat_to_mat4( float mat[][4],DualQuat *dq);
+void add_weighted_dq_dq(DualQuat *dqsum, DualQuat *dq, float weight);
+void normalize_dq(DualQuat *dq, float totweight);
+void mul_v3m3_dq( float *co, float mat[][3],DualQuat *dq);
+void copy_dq_dq(DualQuat *dq1, DualQuat *dq2);
+
+/* Tangent stuff */
+typedef struct VertexTangent {
+ float tang[3], uv[2];
+ struct VertexTangent *next;
+} VertexTangent;
+
+void sum_or_add_vertex_tangent(void *arena, VertexTangent **vtang, float *tang, float *uv);
+float *find_vertex_tangent(VertexTangent *vtang, float *uv);
+void tangent_from_uv(float *uv1, float *uv2, float *uv3, float *co1, float *co2, float *co3, float *n, float *tang);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
+
diff --git a/source/blender/blenlib/BLI_array.h b/source/blender/blenlib/BLI_array.h
new file mode 100644
index 00000000000..c01d821cb8b
--- /dev/null
+++ b/source/blender/blenlib/BLI_array.h
@@ -0,0 +1,91 @@
+/**
+ * Array library
+ *
+ *
+ * ***** 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2008 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Geoffrey Bantle.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/*
+this library needs to be changed to not use macros quite so heavily,
+and to be more of a complete array API. The way arrays are
+exposed to client code as normal C arrays is very useful though, imho.
+it does require some use of macros, however.
+
+anyway, it's used a bit too heavily to simply rewrite as a
+more "correct" solution without macros entirely. I originally wrote this
+to be very easy to use, without the normal pain of most array libraries.
+This was especially helpful when it came to the massive refactors necessary for
+bmesh, and really helped to speed the process up. - joeedh
+
+little array macro library. example of usage:
+
+int *arr = NULL;
+BLI_array_declare(arr);
+int i;
+
+for (i=0; i<10; i++) {
+ BLI_array_growone(arr);
+ arr[i] = something;
+}
+BLI_array_free(arr);
+
+arrays are buffered, using double-buffering (so on each reallocation,
+the array size is doubled). supposedly this should give good Big Oh
+behaviour, though it may not be the best in practice.
+*/
+
+#define BLI_array_declare(arr) int _##arr##_count=0; void *_##arr##_tmp
+
+/*this returns the entire size of the array, including any buffering.*/
+#define BLI_array_totalsize(arr) ((signed int)((arr)==NULL ? 0 : MEM_allocN_len(arr) / sizeof(*arr)))
+
+/*this returns the logical size of the array, not including buffering.*/
+#define BLI_array_count(arr) _##arr##_count
+
+/*grow the array by one. zeroes the new elements.*/
+#define BLI_array_growone(arr) \
+ BLI_array_totalsize(arr) > _##arr##_count ? _##arr##_count++ : \
+ ((_##arr##_tmp = MEM_callocN(sizeof(*arr)*(_##arr##_count*2+2), #arr " " __FILE__ " ")),\
+ (arr && memcpy(_##arr##_tmp, arr, sizeof(*arr) * _##arr##_count)),\
+ (arr && (MEM_freeN(arr),1)),\
+ (arr = _##arr##_tmp),\
+ _##arr##_count++)
+
+/*appends an item to the array and returns a pointer to the item in the array.
+ item is not a pointer, but actual data value.*/
+#define BLI_array_append(arr, item) (BLI_array_growone(arr), arr[_##arr##_count] = item, (arr+_##arr##_count))
+
+/*grow an array by a specified number of items.*/
+#define BLI_array_growitems(arr, num) {int _i; for (_i=0; _i<(num); _i++) {BLI_array_growone(arr);}}
+#define BLI_array_free(arr) if (arr) MEM_freeN(arr)
+
+/*resets the logical size of an array to zero, but doesn't
+ free the memory.*/
+#define BLI_array_empty(arr) _##arr##_count=0
+
+/*set the count of the array, doesn't actually increase the allocated array
+ size. don't use this unless you know what your doing.*/
+#define BLI_array_set_length(arr, count) _##arr##_count = (count)
diff --git a/source/blender/blenlib/BLI_cellalloc.h b/source/blender/blenlib/BLI_cellalloc.h
new file mode 100644
index 00000000000..cd10e9febe8
--- /dev/null
+++ b/source/blender/blenlib/BLI_cellalloc.h
@@ -0,0 +1,49 @@
+/**
+ *
+ * ***** 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2008 by Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/*
+ I wrote this as a hack so vgroups won't be quite so slow. I really
+ should replace it with something else, but I need to spend some time
+ thinking as to what the proper solution would be (other then totally
+ rewriting vgroups, of course).
+
+ this is just a simple allocator that spawns mempools for unique size
+ requests. hardly ideal, I know. *something* like this may be
+ unavoidable, but it should certainly be possible to make it
+ non-global and internal to the vgroup code.
+
+ -joeedh sep. 17 2009
+*/
+
+//BMESH_TODO: kill this library before merging with trunk
+void *BLI_cellalloc_malloc(long size, char *tag);
+void *BLI_cellalloc_calloc(long size, char *tag);
+void BLI_cellalloc_free(void *mem);
+void BLI_cellalloc_printleaks(void);
+int BLI_cellalloc_get_totblock(void);
+void BLI_cellalloc_destroy(void);
diff --git a/source/blender/blenlib/BLI_edgehash.h b/source/blender/blenlib/BLI_edgehash.h
index abbd17c3635..85b0b9023ec 100644
--- a/source/blender/blenlib/BLI_edgehash.h
+++ b/source/blender/blenlib/BLI_edgehash.h
@@ -32,6 +32,10 @@
#ifndef BLI_EDGEHASH_H
#define BLI_EDGEHASH_H
+#include "MEM_guardedalloc.h"
+#include "BKE_utildefines.h"
+#include "BLI_mempool.h"
+
struct EdgeHash;
struct EdgeHashIterator;
typedef struct EdgeHash EdgeHash;
@@ -45,22 +49,22 @@ void BLI_edgehash_free (EdgeHash *eh, EdgeHashFreeFP valfreefp);
/* Insert edge (v0,v1) into hash with given value, does
* not check for duplicates.
*/
-void BLI_edgehash_insert (EdgeHash *eh, int v0, int v1, void *val);
+//void BLI_edgehash_insert (EdgeHash *eh, int v0, int v1, void *val);
/* Return value for given edge (v0,v1), or NULL if
* if key does not exist in hash. (If need exists
* to differentiate between key-value being NULL and
* lack of key then see BLI_edgehash_lookup_p().
*/
-void* BLI_edgehash_lookup (EdgeHash *eh, int v0, int v1);
+//void* BLI_edgehash_lookup (EdgeHash *eh, int v0, int v1);
/* Return pointer to value for given edge (v0,v1),
* or NULL if key does not exist in hash.
*/
-void** BLI_edgehash_lookup_p (EdgeHash *eh, int v0, int v1);
+//void** BLI_edgehash_lookup_p (EdgeHash *eh, int v0, int v1);
/* Return boolean true/false if edge (v0,v1) in hash. */
-int BLI_edgehash_haskey (EdgeHash *eh, int v0, int v1);
+//int BLI_edgehash_haskey (EdgeHash *eh, int v0, int v1);
/* Return number of keys in hash. */
int BLI_edgehash_size (EdgeHash *eh);
@@ -95,5 +99,99 @@ void BLI_edgehashIterator_step (EdgeHashIterator *ehi);
/* Determine if an iterator is done. */
int BLI_edgehashIterator_isDone (EdgeHashIterator *ehi);
+/**************inlined code************/
+static unsigned int _ehash_hashsizes[]= {
+ 1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209,
+ 16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169,
+ 4194319, 8388617, 16777259, 33554467, 67108879, 134217757,
+ 268435459
+};
+
+#define EDGEHASH(v0,v1) ((v0*39)^(v1*31))
+
+/***/
+
+typedef struct EdgeEntry EdgeEntry;
+struct EdgeEntry {
+ EdgeEntry *next;
+ int v0, v1;
+ void *val;
+};
+
+struct EdgeHash {
+ EdgeEntry **buckets;
+ BLI_mempool *epool;
+ int nbuckets, nentries, cursize;
+};
+
+
+BM_INLINE void BLI_edgehash_insert(EdgeHash *eh, int v0, int v1, void *val) {
+ unsigned int hash;
+ EdgeEntry *e= BLI_mempool_alloc(eh->epool);
+
+ if (v1<v0) {
+ v0 ^= v1;
+ v1 ^= v0;
+ v0 ^= v1;
+ }
+ hash = EDGEHASH(v0,v1)%eh->nbuckets;
+
+ e->v0 = v0;
+ e->v1 = v1;
+ e->val = val;
+ e->next= eh->buckets[hash];
+ eh->buckets[hash]= e;
+
+ if (++eh->nentries>eh->nbuckets*3) {
+ EdgeEntry *e, **old= eh->buckets;
+ int i, nold= eh->nbuckets;
+
+ eh->nbuckets= _ehash_hashsizes[++eh->cursize];
+ eh->buckets= MEM_mallocN(eh->nbuckets*sizeof(*eh->buckets), "eh buckets");
+ BMEMSET(eh->buckets, 0, eh->nbuckets*sizeof(*eh->buckets));
+
+ for (i=0; i<nold; i++) {
+ for (e= old[i]; e;) {
+ EdgeEntry *n= e->next;
+
+ hash= EDGEHASH(e->v0,e->v1)%eh->nbuckets;
+ e->next= eh->buckets[hash];
+ eh->buckets[hash]= e;
+
+ e= n;
+ }
+ }
+
+ MEM_freeN(old);
+ }
+}
+
+BM_INLINE void** BLI_edgehash_lookup_p(EdgeHash *eh, int v0, int v1) {
+ unsigned int hash;
+ EdgeEntry *e;
+
+ if (v1<v0) {
+ v0 ^= v1;
+ v1 ^= v0;
+ v0 ^= v1;
+ }
+ hash = EDGEHASH(v0,v1)%eh->nbuckets;
+ for (e= eh->buckets[hash]; e; e= e->next)
+ if (v0==e->v0 && v1==e->v1)
+ return &e->val;
+
+ return NULL;
+}
+
+BM_INLINE void* BLI_edgehash_lookup(EdgeHash *eh, int v0, int v1) {
+ void **value_p = BLI_edgehash_lookup_p(eh,v0,v1);
+
+ return value_p?*value_p:NULL;
+}
+
+BM_INLINE int BLI_edgehash_haskey(EdgeHash *eh, int v0, int v1) {
+ return BLI_edgehash_lookup_p(eh, v0, v1)!=NULL;
+}
+
#endif
diff --git a/source/blender/blenlib/BLI_editVert.h b/source/blender/blenlib/BLI_editVert.h
index 35081086783..22a9b5edcaf 100644
--- a/source/blender/blenlib/BLI_editVert.h
+++ b/source/blender/blenlib/BLI_editVert.h
@@ -42,6 +42,7 @@
struct DerivedMesh;
struct RetopoPaintData;
+struct BLI_mempool;
/* note; changing this also might affect the undo copy in editmesh.c */
typedef struct EditVert
@@ -154,6 +155,8 @@ typedef struct EditMesh
HashEdge *hashedgetab;
/* this is for the editmesh_fastmalloc */
+ struct BLI_mempool *vertpool, *edgepool, *facepool;
+
EditVert *allverts, *curvert;
EditEdge *alledges, *curedge;
EditFace *allfaces, *curface;
diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h
index c9a8b1b841f..703115630fe 100644
--- a/source/blender/blenlib/BLI_ghash.h
+++ b/source/blender/blenlib/BLI_ghash.h
@@ -32,31 +32,48 @@
#ifndef BLI_GHASH_H
#define BLI_GHASH_H
-#ifdef __cplusplus
-extern "C" {
-#endif
+#include "stdio.h"
+#include "stdlib.h"
+#include "string.h"
-struct GHash;
-typedef struct GHash GHash;
+#include "BKE_utildefines.h"
-typedef struct GHashIterator {
- GHash *gh;
- int curBucket;
- struct Entry *curEntry;
-} GHashIterator;
+#include "BLI_mempool.h"
+#include "BLI_blenlib.h"
typedef unsigned int (*GHashHashFP) (void *key);
typedef int (*GHashCmpFP) (void *a, void *b);
typedef void (*GHashKeyFreeFP) (void *key);
typedef void (*GHashValFreeFP) (void *val);
+typedef struct Entry {
+ struct Entry *next;
+
+ void *key, *val;
+} Entry;
+
+typedef struct GHash {
+ GHashHashFP hashfp;
+ GHashCmpFP cmpfp;
+
+ Entry **buckets;
+ struct BLI_mempool *entrypool;
+ int nbuckets, nentries, cursize;
+} GHash;
+
+typedef struct GHashIterator {
+ GHash *gh;
+ int curBucket;
+ struct Entry *curEntry;
+} GHashIterator;
+
GHash* BLI_ghash_new (GHashHashFP hashfp, GHashCmpFP cmpfp);
void BLI_ghash_free (GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
-void BLI_ghash_insert (GHash *gh, void *key, void *val);
-int BLI_ghash_remove (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
-void* BLI_ghash_lookup (GHash *gh, void *key);
-int BLI_ghash_haskey (GHash *gh, void *key);
+//BM_INLINE void BLI_ghash_insert (GHash *gh, void *key, void *val);
+//BM_INLINE int BLI_ghash_remove (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
+//BM_INLINE void* BLI_ghash_lookup (GHash *gh, void *key);
+//BM_INLINE int BLI_ghash_haskey (GHash *gh, void *key);
int BLI_ghash_size (GHash *gh);
@@ -129,9 +146,121 @@ int BLI_ghashutil_strcmp (void *a, void *b);
unsigned int BLI_ghashutil_inthash (void *ptr);
int BLI_ghashutil_intcmp(void *a, void *b);
-#ifdef __cplusplus
-}
-#endif
+/*begin of macro-inlined functions*/
+extern unsigned int hashsizes[];
+#if 0
+#define BLI_ghash_insert(gh, _k, _v){\
+ unsigned int _hash= (gh)->hashfp(_k)%gh->nbuckets;\
+ Entry *_e= BLI_mempool_alloc((gh)->entrypool);\
+ _e->key= _k;\
+ _e->val= _v;\
+ _e->next= (gh)->buckets[_hash];\
+ (gh)->buckets[_hash]= _e;\
+ if (++(gh)->nentries>(gh)->nbuckets*3) {\
+ Entry *_e, **_old= (gh)->buckets;\
+ int _i, _nold= (gh)->nbuckets;\
+ (gh)->nbuckets= hashsizes[++(gh)->cursize];\
+ (gh)->buckets= malloc((gh)->nbuckets*sizeof(*(gh)->buckets));\
+ memset((gh)->buckets, 0, (gh)->nbuckets*sizeof(*(gh)->buckets));\
+ for (_i=0; _i<_nold; _i++) {\
+ for (_e= _old[_i]; _e;) {\
+ Entry *_n= _e->next;\
+ _hash= (gh)->hashfp(_e->key)%(gh)->nbuckets;\
+ _e->next= (gh)->buckets[_hash];\
+ (gh)->buckets[_hash]= _e;\
+ _e= _n;\
+ }\
+ }\
+ free(_old); } }
#endif
+/*---------inlined functions---------*/
+BM_INLINE void BLI_ghash_insert(GHash *gh, void *key, void *val) {
+ unsigned int hash= gh->hashfp(key)%gh->nbuckets;
+ Entry *e= (Entry*) BLI_mempool_alloc(gh->entrypool);
+
+ e->key= key;
+ e->val= val;
+ e->next= gh->buckets[hash];
+ gh->buckets[hash]= e;
+
+ if (++gh->nentries>gh->nbuckets*3) {
+ Entry *e, **old= gh->buckets;
+ int i, nold= gh->nbuckets;
+
+ gh->nbuckets= hashsizes[++gh->cursize];
+ gh->buckets= (Entry**)malloc(gh->nbuckets*sizeof(*gh->buckets));
+ memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
+
+ for (i=0; i<nold; i++) {
+ for (e= old[i]; e;) {
+ Entry *n= e->next;
+
+ hash= gh->hashfp(e->key)%gh->nbuckets;
+ e->next= gh->buckets[hash];
+ gh->buckets[hash]= e;
+
+ e= n;
+ }
+ }
+
+ free(old);
+ }
+}
+
+BM_INLINE void* BLI_ghash_lookup(GHash *gh, void *key)
+{
+ if(gh) {
+ unsigned int hash= gh->hashfp(key)%gh->nbuckets;
+ Entry *e;
+
+ for (e= gh->buckets[hash]; e; e= e->next)
+ if (gh->cmpfp(key, e->key)==0)
+ return e->val;
+ }
+ return NULL;
+}
+
+BM_INLINE int BLI_ghash_remove (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
+{
+ unsigned int hash= gh->hashfp(key)%gh->nbuckets;
+ Entry *e;
+ Entry *p = 0;
+
+ for (e= gh->buckets[hash]; e; e= e->next) {
+ if (gh->cmpfp(key, e->key)==0) {
+ Entry *n= e->next;
+
+ if (keyfreefp) keyfreefp(e->key);
+ if (valfreefp) valfreefp(e->val);
+ BLI_mempool_free(gh->entrypool, e);
+
+
+ e= n;
+ if (p)
+ p->next = n;
+ else
+ gh->buckets[hash] = n;
+
+ --gh->nentries;
+ return 1;
+ }
+ p = e;
+ }
+
+ return 0;
+}
+
+BM_INLINE int BLI_ghash_haskey(GHash *gh, void *key) {
+ unsigned int hash= gh->hashfp(key)%gh->nbuckets;
+ Entry *e;
+
+ for (e= gh->buckets[hash]; e; e= e->next)
+ if (gh->cmpfp(key, e->key)==0)
+ return 1;
+
+ return 0;
+}
+
+#endif
diff --git a/source/blender/blenlib/intern/BLI_cellalloc.c b/source/blender/blenlib/intern/BLI_cellalloc.c
new file mode 100644
index 00000000000..efed99011d0
--- /dev/null
+++ b/source/blender/blenlib/intern/BLI_cellalloc.c
@@ -0,0 +1,174 @@
+/**
+ *
+ * ***** 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2008 by Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Joseph Eagar
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/*
+ Simple, fast memory allocator that uses many BLI_mempools for allocation.
+ this is meant to be used by lots of relatively small objects.
+
+ this is a temporary and inperfect fix for performance issues caused
+ by vgroups. it needs to be replaced with something better, preferably
+ integrated into guardedalloc.
+*/
+
+#include "MEM_guardedalloc.h"
+
+#include "BKE_utildefines.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_linklist.h"
+
+#include "DNA_listBase.h"
+#include "BLI_mempool.h"
+
+#include <string.h>
+
+static BLI_mempool **pools;
+static int totpool = 0;
+ListBase active_mem = {NULL, NULL};
+static int celltotblock = 0;
+
+#define MEMIDCHECK ('a' | ('b' << 4) | ('c' << 8) | ('d' << 12))
+
+typedef struct MemHeader {
+ struct MemHeader *next, *prev;
+
+ int size;
+ char *tag;
+ int idcheck;
+} MemHeader;
+
+//#define USE_GUARDEDALLOC
+
+void *BLI_cellalloc_malloc(long size, char *tag)
+{
+ MemHeader *memh;
+ int slot = size + sizeof(MemHeader);
+
+#ifdef USE_GUARDEDALLOC
+ return MEM_mallocN(size, tag);
+#endif
+ if (!slot)
+ return NULL;
+
+ /*stupid optimization trick.
+ round up to nearest 16 bytes boundary.
+ this is to reduce the number of potential
+ pools. hopefully it'll help.*/
+ slot += 16 - (slot & 15);
+
+ if (slot >= totpool) {
+ void *tmp;
+
+ tmp = calloc(1, sizeof(void*)*(slot+1));
+ if (pools) {
+ memcpy(tmp, pools, totpool*sizeof(void*));
+ }
+
+ pools = tmp;
+ totpool = slot+1;
+ }
+
+ if (!pools[slot]) {
+ pools[slot] = BLI_mempool_create(slot, 1, 128);
+ }
+
+ memh = BLI_mempool_alloc(pools[slot]);
+ memh->size = size;
+ memh->idcheck = MEMIDCHECK;
+ memh->tag = tag;
+ BLI_addtail(&active_mem, memh);
+ celltotblock++;
+
+ return memh + 1;
+}
+
+void *BLI_cellalloc_calloc(long size, char *tag)
+{
+ void *mem = BLI_cellalloc_malloc(size, tag);
+ BMEMSET(mem, 0, size);
+
+ return mem;
+}
+
+void BLI_cellalloc_free(void *mem)
+{
+ MemHeader *memh = mem;
+ int slot;
+
+#ifdef USE_GUARDEDALLOC
+ MEM_freeN(mem);
+ return;
+#endif
+ if (!memh)
+ return;
+
+ memh--;
+ if (memh->idcheck != MEMIDCHECK) {
+ printf("Error in BLI_cellalloc: attempt to free invalid block.\n");
+ return;
+ }
+
+ slot = memh->size + sizeof(MemHeader);
+ slot += 16 - (slot & 15);
+
+ if (memh->size > 0 && slot < totpool) {
+ BLI_remlink(&active_mem, memh);
+ BLI_mempool_free(pools[slot], memh);
+ celltotblock--;
+ } else {
+ printf("Error in BLI_cellalloc: attempt to free corrupted block.\n");
+ }
+}
+
+void BLI_cellalloc_printleaks(void)
+{
+ MemHeader *memh;
+
+ if (!active_mem.first) return;
+
+ for (memh=active_mem.first; memh; memh=memh->next) {
+ printf("%s %d %p\n", memh->tag, memh->size, memh+1);
+ }
+}
+
+int BLI_cellalloc_get_totblock(void)
+{
+ return celltotblock;
+}
+
+void BLI_cellalloc_destroy(void)
+{
+ int i;
+
+ for (i=0; i<totpool; i++) {
+ if (pools[i]) {
+ BLI_mempool_destroy(pools[i]);
+ pools[i] = NULL;
+ }
+ }
+} \ No newline at end of file
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c
index 80cd507520c..c8918b11368 100644
--- a/source/blender/blenlib/intern/BLI_ghash.c
+++ b/source/blender/blenlib/intern/BLI_ghash.c
@@ -33,16 +33,19 @@
#include "MEM_guardedalloc.h"
#include "BLI_ghash.h"
+#include "BLI_mempool.h"
#include "BLO_sys_types.h" // for intptr_t support
+#include "BKE_utildefines.h"
+
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
/***/
-static unsigned int hashsizes[]= {
+unsigned int hashsizes[]= {
1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209,
16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169,
4194319, 8388617, 16777259, 33554467, 67108879, 134217757,
@@ -51,28 +54,14 @@ static unsigned int hashsizes[]= {
/***/
-typedef struct Entry Entry;
-struct Entry {
- Entry *next;
-
- void *key, *val;
-};
-
-struct GHash {
- GHashHashFP hashfp;
- GHashCmpFP cmpfp;
-
- Entry **buckets;
- int nbuckets, nentries, cursize;
-};
-
/***/
GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp) {
GHash *gh= MEM_mallocN(sizeof(*gh), "GHash");
gh->hashfp= hashfp;
gh->cmpfp= cmpfp;
-
+ gh->entrypool = BLI_mempool_create(sizeof(Entry), 1024, 1024);
+
gh->cursize= 0;
gh->nentries= 0;
gh->nbuckets= hashsizes[gh->cursize];
@@ -83,92 +72,9 @@ GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp) {
return gh;
}
-void BLI_ghash_insert(GHash *gh, void *key, void *val) {
- unsigned int hash= gh->hashfp(key)%gh->nbuckets;
- Entry *e= malloc(sizeof(*e));
-
- e->key= key;
- e->val= val;
- e->next= gh->buckets[hash];
- gh->buckets[hash]= e;
-
- if (++gh->nentries>gh->nbuckets*3) {
- Entry *e, **old= gh->buckets;
- int i, nold= gh->nbuckets;
-
- gh->nbuckets= hashsizes[++gh->cursize];
- gh->buckets= malloc(gh->nbuckets*sizeof(*gh->buckets));
- memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
-
- for (i=0; i<nold; i++) {
- for (e= old[i]; e;) {
- Entry *n= e->next;
-
- hash= gh->hashfp(e->key)%gh->nbuckets;
- e->next= gh->buckets[hash];
- gh->buckets[hash]= e;
-
- e= n;
- }
- }
-
- free(old);
- }
-}
-
-void* BLI_ghash_lookup(GHash *gh, void *key)
-{
- if(gh) {
- unsigned int hash= gh->hashfp(key)%gh->nbuckets;
- Entry *e;
-
- for (e= gh->buckets[hash]; e; e= e->next)
- if (gh->cmpfp(key, e->key)==0)
- return e->val;
- }
- return NULL;
-}
-
-int BLI_ghash_remove (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
-{
- unsigned int hash= gh->hashfp(key)%gh->nbuckets;
- Entry *e;
- Entry *p = 0;
-
- for (e= gh->buckets[hash]; e; e= e->next) {
- if (gh->cmpfp(key, e->key)==0) {
- Entry *n= e->next;
-
- if (keyfreefp) keyfreefp(e->key);
- if (valfreefp) valfreefp(e->val);
- free(e);
-
-
- e= n;
- if (p)
- p->next = n;
- else
- gh->buckets[hash] = n;
-
- --gh->nentries;
- return 1;
- }
- p = e;
- }
-
- return 0;
-}
-
-int BLI_ghash_haskey(GHash *gh, void *key) {
- unsigned int hash= gh->hashfp(key)%gh->nbuckets;
- Entry *e;
-
- for (e= gh->buckets[hash]; e; e= e->next)
- if (gh->cmpfp(key, e->key)==0)
- return 1;
-
- return 0;
-}
+#ifdef BLI_ghash_insert
+#undef BLI_ghash_insert
+#endif
int BLI_ghash_size(GHash *gh) {
return gh->nentries;
@@ -177,21 +83,23 @@ int BLI_ghash_size(GHash *gh) {
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) {
int i;
- for (i=0; i<gh->nbuckets; i++) {
- Entry *e;
-
- for (e= gh->buckets[i]; e; ) {
- Entry *n= e->next;
-
- if (keyfreefp) keyfreefp(e->key);
- if (valfreefp) valfreefp(e->val);
- free(e);
+ if (keyfreefp || valfreefp) {
+ for (i=0; i<gh->nbuckets; i++) {
+ Entry *e;
- e= n;
+ for (e= gh->buckets[i]; e; ) {
+ Entry *n= e->next;
+
+ if (keyfreefp) keyfreefp(e->key);
+ if (valfreefp) valfreefp(e->val);
+
+ e= n;
+ }
}
}
free(gh->buckets);
+ BLI_mempool_destroy(gh->entrypool);
gh->buckets = 0;
gh->nentries = 0;
gh->nbuckets = 0;
diff --git a/source/blender/blenlib/intern/BLI_mempool.c b/source/blender/blenlib/intern/BLI_mempool.c
index 485ba7cbd08..9c4113bb13a 100644
--- a/source/blender/blenlib/intern/BLI_mempool.c
+++ b/source/blender/blenlib/intern/BLI_mempool.c
@@ -21,7 +21,7 @@
*
* The Original Code is: all of this file.
*
- * Contributor(s): none yet.
+ * Contributor(s): Geoffery Bantle
*
* ***** END GPL LICENSE BLOCK *****
*/
@@ -31,9 +31,14 @@
*/
#include "MEM_guardedalloc.h"
+
+#include "BKE_utildefines.h"
+
#include "BLI_blenlib.h"
-#include "DNA_listBase.h"
#include "BLI_linklist.h"
+
+#include "DNA_listBase.h"
+
#include <string.h>
typedef struct BLI_freenode{
@@ -60,6 +65,9 @@ BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk)
if (esize < sizeof(void*))
esize = sizeof(void*);
+ if (esize < sizeof(void*))
+ esize = sizeof(void*);
+
/*allocate the pool structure*/
pool = MEM_mallocN(sizeof(BLI_mempool),"memory pool");
pool->esize = esize;
@@ -68,7 +76,8 @@ BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk)
pool->chunks.first = pool->chunks.last = NULL;
maxchunks = tote / pchunk;
-
+ if (maxchunks==0) maxchunks = 1;
+
/*allocate the actual chunks*/
for(i=0; i < maxchunks; i++){
BLI_mempool_chunk *mpchunk = MEM_mallocN(sizeof(BLI_mempool_chunk), "BLI_Mempool Chunk");
@@ -88,6 +97,7 @@ BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk)
/*set the end of this chunks memoryy to the new tail for next iteration*/
lasttail = curnode;
}
+
/*terminate the list*/
curnode->next = NULL;
return pool;
@@ -123,7 +133,7 @@ void *BLI_mempool_alloc(BLI_mempool *pool){
void *BLI_mempool_calloc(BLI_mempool *pool){
void *retval=NULL;
retval = BLI_mempool_alloc(pool);
- memset(retval, 0, pool->esize);
+ BMEMSET(retval, 0, pool->esize);
return retval;
}
diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c
index 603c85655d7..5b98c3194bc 100644
--- a/source/blender/blenlib/intern/edgehash.c
+++ b/source/blender/blenlib/intern/edgehash.c
@@ -22,7 +22,7 @@
*
* The Original Code is: none of this file.
*
- * Contributor(s): Daniel Dunbar
+ * Contributor(s): Daniel Dunbar, Joseph Eagar
*
* ***** END GPL LICENSE BLOCK *****
* A general (pointer -> pointer) hash table ADT
@@ -33,112 +33,20 @@
#include "MEM_guardedalloc.h"
#include "BLI_edgehash.h"
-
-/***/
-
-static unsigned int hashsizes[]= {
- 1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209,
- 16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169,
- 4194319, 8388617, 16777259, 33554467, 67108879, 134217757,
- 268435459
-};
-
-#define EDGEHASH(v0,v1) ((v0*39)^(v1*31))
-
-/***/
-
-typedef struct Entry Entry;
-struct Entry {
- Entry *next;
- int v0, v1;
- void *val;
-};
-
-struct EdgeHash {
- Entry **buckets;
- int nbuckets, nentries, cursize;
-};
+#include "BLI_mempool.h"
/***/
EdgeHash *BLI_edgehash_new(void) {
- EdgeHash *eh= MEM_mallocN(sizeof(*eh), "EdgeHash");
+ EdgeHash *eh= MEM_callocN(sizeof(*eh), "EdgeHash");
eh->cursize= 0;
eh->nentries= 0;
- eh->nbuckets= hashsizes[eh->cursize];
-
- eh->buckets= malloc(eh->nbuckets*sizeof(*eh->buckets));
- memset(eh->buckets, 0, eh->nbuckets*sizeof(*eh->buckets));
+ eh->nbuckets= _ehash_hashsizes[eh->cursize];
- return eh;
-}
-
-void BLI_edgehash_insert(EdgeHash *eh, int v0, int v1, void *val) {
- unsigned int hash;
- Entry *e= malloc(sizeof(*e));
+ eh->buckets= MEM_callocN(eh->nbuckets*sizeof(*eh->buckets), "eh buckets 2");
+ eh->epool = BLI_mempool_create(sizeof(EdgeEntry), 512, 512);
- if (v1<v0) {
- v0 ^= v1;
- v1 ^= v0;
- v0 ^= v1;
- }
- hash = EDGEHASH(v0,v1)%eh->nbuckets;
-
- e->v0 = v0;
- e->v1 = v1;
- e->val = val;
- e->next= eh->buckets[hash];
- eh->buckets[hash]= e;
-
- if (++eh->nentries>eh->nbuckets*3) {
- Entry *e, **old= eh->buckets;
- int i, nold= eh->nbuckets;
-
- eh->nbuckets= hashsizes[++eh->cursize];
- eh->buckets= malloc(eh->nbuckets*sizeof(*eh->buckets));
- memset(eh->buckets, 0, eh->nbuckets*sizeof(*eh->buckets));
-
- for (i=0; i<nold; i++) {
- for (e= old[i]; e;) {
- Entry *n= e->next;
-
- hash= EDGEHASH(e->v0,e->v1)%eh->nbuckets;
- e->next= eh->buckets[hash];
- eh->buckets[hash]= e;
-
- e= n;
- }
- }
-
- free(old);
- }
-}
-
-void** BLI_edgehash_lookup_p(EdgeHash *eh, int v0, int v1) {
- unsigned int hash;
- Entry *e;
-
- if (v1<v0) {
- v0 ^= v1;
- v1 ^= v0;
- v0 ^= v1;
- }
- hash = EDGEHASH(v0,v1)%eh->nbuckets;
- for (e= eh->buckets[hash]; e; e= e->next)
- if (v0==e->v0 && v1==e->v1)
- return &e->val;
-
- return NULL;
-}
-
-void* BLI_edgehash_lookup(EdgeHash *eh, int v0, int v1) {
- void **value_p = BLI_edgehash_lookup_p(eh,v0,v1);
-
- return value_p?*value_p:NULL;
-}
-
-int BLI_edgehash_haskey(EdgeHash *eh, int v0, int v1) {
- return BLI_edgehash_lookup_p(eh, v0, v1)!=NULL;
+ return eh;
}
int BLI_edgehash_size(EdgeHash *eh) {
@@ -149,13 +57,13 @@ void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp) {
int i;
for (i=0; i<eh->nbuckets; i++) {
- Entry *e;
+ EdgeEntry *e;
for (e= eh->buckets[i]; e; ) {
- Entry *n= e->next;
+ EdgeEntry *n= e->next;
if (valfreefp) valfreefp(e->val);
- free(e);
+ BLI_mempool_free(eh->epool, e);
e= n;
}
@@ -167,8 +75,10 @@ void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp) {
void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp) {
BLI_edgehash_clear(eh, valfreefp);
-
- free(eh->buckets);
+
+ BLI_mempool_destroy(eh->epool);
+
+ MEM_freeN(eh->buckets);
MEM_freeN(eh);
}
@@ -178,11 +88,11 @@ void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp) {
struct EdgeHashIterator {
EdgeHash *eh;
int curBucket;
- Entry *curEntry;
+ EdgeEntry *curEntry;
};
EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh) {
- EdgeHashIterator *ehi= malloc(sizeof(*ehi));
+ EdgeHashIterator *ehi= MEM_mallocN(sizeof(*ehi), "eh iter");
ehi->eh= eh;
ehi->curEntry= NULL;
ehi->curBucket= -1;
@@ -195,7 +105,7 @@ EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh) {
return ehi;
}
void BLI_edgehashIterator_free(EdgeHashIterator *ehi) {
- free(ehi);
+ MEM_freeN(ehi);
}
void BLI_edgehashIterator_getKey(EdgeHashIterator *ehi, int *v0_r, int *v1_r) {
diff --git a/source/blender/blenlib/intern/math_vector_inline.c b/source/blender/blenlib/intern/math_vector_inline.c
index 6830f44ae1b..182ccd9d67e 100644
--- a/source/blender/blenlib/intern/math_vector_inline.c
+++ b/source/blender/blenlib/intern/math_vector_inline.c
@@ -254,5 +254,26 @@ MINLINE float normalize_v3(float n[3])
return d;
}
+
+MINLINE double normalize_dv3(double n[3])
+{
+ double d= n[0]*n[0] + n[1]*n[1] + n[2]*n[2];
+
+ /* a larger value causes normalize errors in a
+ scaled down models with camera xtreme close */
+ if(d > 1.0e-35f) {
+ d= 1.0 / sqrt(d);
+ n[0] *= d;
+ n[1] *= d;
+ n[2] *= d;
+ }
+ else {
+ n[0] = n[1] = n[2] = 0.0;
+ d= 0.0;
+ }
+
+ return d;
+}
+
#endif /* BLI_MATH_VECTOR_INLINE */
diff --git a/source/blender/blenlib/intern/scanfill.c b/source/blender/blenlib/intern/scanfill.c
index e54382c9392..b89adbefc79 100644
--- a/source/blender/blenlib/intern/scanfill.c
+++ b/source/blender/blenlib/intern/scanfill.c
@@ -31,6 +31,7 @@
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
+#include <string.h>
#include "MEM_guardedalloc.h"
@@ -44,6 +45,8 @@
#include "BLI_scanfill.h"
#include "BLI_callbacks.h"
+#include "BKE_utildefines.h"
+
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
@@ -152,7 +155,7 @@ static void *new_mem_element(int size)
{
int blocksize= 16384;
static int offs= 0; /* the current free adress */
- static struct mem_elements *cur= 0;
+ static struct mem_elements *cur= 0, *first;
static ListBase lb= {0, 0};
void *adr;
@@ -160,6 +163,10 @@ static void *new_mem_element(int size)
printf("incorrect use of new_mem_element\n");
}
else if(size== -1) {
+ /*keep the first block*/
+ first = lb.first;
+ BLI_remlink(&lb, first);
+
cur= lb.first;
while(cur) {
MEM_freeN(cur->data);
@@ -167,6 +174,12 @@ static void *new_mem_element(int size)
}
BLI_freelistN(&lb);
+ /*reset the block we're keeping*/
+ BLI_addtail(&lb, first);
+ memset(first->data, 0, blocksize);
+ cur = first;
+ offs = 0;
+
return NULL;
}
@@ -768,6 +781,7 @@ int BLI_edgefill(int mode, int mat_nr)
- struct elements xs en ys are not used here: don't hide stuff in it
- edge flag ->f becomes 2 when it's a new edge
- mode: & 1 is check for crossings, then create edges (TO DO )
+ - mode: & 2 is enable shortest diagonal test for quads
*/
ListBase tempve, temped;
EditVert *eve;
@@ -778,11 +792,42 @@ int BLI_edgefill(int mode, int mat_nr)
/* reset variables */
eve= fillvertbase.first;
+ a = 0;
while(eve) {
eve->f= 0;
eve->xs= 0;
eve->h= 0;
eve= eve->next;
+ a += 1;
+ }
+
+ if (a == 3) {
+ eve = fillvertbase.first;
+
+ addfillface(eve, eve->next, eve->next->next, 0);
+ return 1;
+ } else if (a == 4) {
+ float vec1[3], vec2[3];
+
+ eve = fillvertbase.first;
+
+ if (mode & 2) {
+ /*use shortest diagonal for quad*/
+ sub_v3_v3v3(vec1, eve->co, eve->next->next->co);
+ sub_v3_v3v3(vec2, eve->next->co, eve->next->next->next->co);
+
+ if (INPR(vec1, vec1) < INPR(vec2, vec2)) {
+ addfillface(eve, eve->next, eve->next->next, 0);
+ addfillface(eve->next->next, eve->next->next->next, eve, 0);
+ } else{
+ addfillface(eve->next, eve->next->next, eve->next->next->next, 0);
+ addfillface(eve->next->next->next, eve, eve->next, 0);
+ }
+ } else {
+ addfillface(eve, eve->next, eve->next->next, 0);
+ addfillface(eve->next->next, eve->next->next->next, eve, 0);
+ }
+ return 1;
}
/* first test vertices if they are in edges */
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-07 11:03:41 +0300