diff options
Diffstat (limited to 'source/blender/blenlib')
35 files changed, 5696 insertions, 770 deletions
diff --git a/source/blender/blenlib/BLI_arithb.h b/source/blender/blenlib/BLI_arithb.h index 6697a7b2ba5..186681fad7d 100644 --- a/source/blender/blenlib/BLI_arithb.h +++ b/source/blender/blenlib/BLI_arithb.h @@ -50,10 +50,14 @@ extern "C" { #ifndef M_SQRT1_2 #define M_SQRT1_2 0.70710678118654752440 #endif +#ifndef M_1_PI +#define M_1_PI 0.318309886183790671538 +#endif #ifdef WIN32 #ifndef FREE_WINDOWS #define isnan(n) _isnan(n) + #define finite _finite #endif #endif @@ -87,6 +91,7 @@ float saasin(float fac); float sasqrt(float fac); int FloatCompare(float *v1, float *v2, float limit); +int FloatCompare4(float *v1, float *v2, float limit); float FloatLerpf(float target, float origin, float fac); float CalcNormFloat(float *v1, float *v2, float *v3, float *n); @@ -95,7 +100,7 @@ float CalcNormFloat4(float *v1, float *v2, float *v3, float *v4, float *n); 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 @@ -160,6 +165,7 @@ void Mat3Inv(float m1[][3], float m2[][3]); void Mat3CpyMat4(float m1[][3],float m2[][4]); void Mat4CpyMat3(float m1[][4], float m2[][3]); +void Mat3BlendMat3(float out[][3], float dst[][3], float src[][3], float srcweight); void Mat4BlendMat4(float out[][4], float dst[][4], float src[][4], float srcweight); float Det2x2(float a,float b,float c, float d); @@ -239,6 +245,7 @@ void VecMulf(float *v1, float f); int VecLenCompare(float *v1, float *v2, float limit); int VecCompare(float *v1, float *v2, float limit); int VecEqual(float *v1, float *v2); +int VecIsNull(float *v); void printvecf(char *str,float v[3]); void printvec4f(char *str, float v[4]); @@ -256,15 +263,23 @@ void Vec2Mulf(float *v1, float f); void Vec2Addf(float *v, float *v1, float *v2); void Vec2Subf(float *v, float *v1, float *v2); void Vec2Copyf(float *v1, float *v2); +void Vec2Lerpf(float *target, float *a, float *b, float t); -float *vectoquat(float *vec, short axis, short upflag); +void AxisAngleToQuat(float *q, float *axis, float angle); +void RotationBetweenVectorsToQuat(float *q, float v1[3], float v2[3]); +void vectoquat(float *vec, short axis, short upflag, float *q); float VecAngle2(float *v1, float *v2); float VecAngle3(float *v1, float *v2, float *v3); float NormalizedVecAngle2(float *v1, float *v2); +float VecAngle3_2D(float *v1, float *v2, float *v3); +float NormalizedVecAngle2_2D(float *v1, float *v2); + void euler_rot(float *beul, float ang, char axis); +void NormalShortToFloat(float *out, short *in); +void NormalFloatToShort(short *out, float *in); float DistVL2Dfl(float *v1, float *v2, float *v3); float PdistVL2Dfl(float *v1, float *v2, float *v3); @@ -309,6 +324,10 @@ void i_window( float mat[][4] ); +#define BLI_CS_SMPTE 0 +#define BLI_CS_REC709 1 +#define BLI_CS_CIE 2 + 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); @@ -316,6 +335,9 @@ 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); +void gamma_correct_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); @@ -367,7 +389,9 @@ void LocQuatSizeToMat4(float mat[][4], float loc[3], float quat[4], float size[3 void tubemap(float x, float y, float z, float *u, float *v); void spheremap(float x, float y, float z, float *u, float *v); +int LineIntersectLine(float v1[3], float v2[3], float v3[3], float v4[3], float i1[3], float i2[3]); int LineIntersectsTriangle(float p1[3], float p2[3], float v0[3], float v1[3], float v2[3], float *lambda, float *uv); +int RayIntersectsTriangle(float p1[3], float d[3], float v0[3], float v1[3], float v2[3], float *lambda, float *uv); int SweepingSphereIntersectsTriangleUV(float p1[3], float p2[3], float radius, float v0[3], float v1[3], float v2[3], float *lambda, float *ipoint); int AxialLineIntersectsTriangle(int axis, float co1[3], float co2[3], float v0[3], float v1[3], float v2[3], float *lambda); int AabbIntersectAabb(float min1[3], float max1[3], float min2[3], float max2[3]); @@ -395,6 +419,16 @@ void DQuatNormalize(DualQuat *dq, float totweight); void DQuatMulVecfl(DualQuat *dq, float *co, float mat[][3]); void DQuatCpyDQuat(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 diff --git a/source/blender/blenlib/BLI_blenlib.h b/source/blender/blenlib/BLI_blenlib.h index efeab705913..f65aaa72a75 100644 --- a/source/blender/blenlib/BLI_blenlib.h +++ b/source/blender/blenlib/BLI_blenlib.h @@ -67,14 +67,14 @@ #include "DNA_listBase.h" #include <stdlib.h> - extern ListBase fillfacebase; extern ListBase fillvertbase; /** * @attention Defined in scanfill.c */ extern ListBase filledgebase; -extern int totblock; + +extern char btempdir[]; /* creator.c temp dir used instead of U.tempdir, set with BLI_where_is_temp( btempdir, 1 ); */ struct chardesc; struct direntry; @@ -94,7 +94,8 @@ char *BLI_gethome(void); void BLI_make_file_string(const char *relabase, char *string, const char *dir, const char *file); void BLI_make_exist(char *dir); void BLI_make_existing_file(char *name); -void BLI_split_dirfile(const char *string, char *dir, char *file); +void BLI_split_dirfile(char *string, char *dir, char *file); +void BLI_split_dirfile_basic(const char *string, char *dir, char *file); void BLI_join_dirfile(char *string, const char *dir, const char *file); int BLI_testextensie(const char *str, const char *ext); void addlisttolist(ListBase *list1, ListBase *list2); @@ -104,6 +105,7 @@ int BLI_findindex(struct ListBase *listbase, void *vlink); void BLI_freelistN(struct ListBase *listbase); void BLI_addtail(struct ListBase *listbase, void *vlink); void BLI_remlink(struct ListBase *listbase, void *vlink); +void BLI_uniquename(struct ListBase *list, void *vlink, char defname[], short name_offs, short len); void BLI_newname(char * name, int add); int BLI_stringdec(char *string, char *kop, char *start, unsigned short *numlen); void BLI_stringenc(char *string, char *kop, char *start, unsigned short numlen, int pic); @@ -135,7 +137,11 @@ void BLI_dlist_reinit(struct DynamicList *dlist); * converts it to a regular full path. * Also removes garbage from directory paths, like /../ or double slashes etc */ -void BLI_cleanup_dir(const char *relabase, char *dir); +void BLI_cleanup_file(const char *relabase, char *dir); +void BLI_cleanup_dir(const char *relabase, char *dir); /* same as above but adds a trailing slash */ + +/* go back one directory */ +int BLI_parent_dir(char *path); /** * Blender's path code replacement function. @@ -149,7 +155,9 @@ void BLI_cleanup_dir(const char *relabase, char *dir); * @a framenum The framenumber to replace the frame code with. * @retval Returns true if the path was relative (started with "//"). */ -int BLI_convertstringcode(char *path, const char *basepath, int framenum); +int BLI_convertstringcode(char *path, const char *basepath); +int BLI_convertstringframe(char *path, int frame); +int BLI_convertstringcwd(char *path); void BLI_makestringcode(const char *relfile, char *file); @@ -222,7 +230,7 @@ int BLI_strcaseeq(char *a, char *b); /* in util.c */ #ifdef WITH_ICONV -void BLI_string_to_utf8(char *original, char *utf_8, char *code); +void BLI_string_to_utf8(char *original, char *utf_8, const char *code); #endif /** @@ -253,7 +261,19 @@ void BLI_free_file_lines(struct LinkNode *lines); * @param fullname The full path and full name of the executable * @param name The name of the executable (usually argv[0]) to be checked */ -void BLI_where_am_i(char *fullname, char *name); +void BLI_where_am_i(char *fullname, const char *name); + +char *get_install_dir(void); + /** + * Gets the temp directory when blender first runs. + * If the default path is not found, use try $TEMP + * + * Also make sure the temp dir has a trailing slash + * + * @param fullname The full path to the temp directory + */ +void BLI_where_is_temp(char *fullname, int usertemp); + /** * determines the full path to the application bundle on OS X @@ -270,6 +290,7 @@ int BLI_getInstallationDir(char *str); /* BLI_storage.h */ int BLI_filesize(int file); +int BLI_filepathsize(const char *path); double BLI_diskfree(char *dir); char *BLI_getwdN(char *dir); void BLI_hide_dot_files(int set); @@ -283,7 +304,6 @@ int BLI_exist(char *name); /* BLI_fileops.h */ void BLI_recurdir_fileops(char *dirname); int BLI_link(char *file, char *to); -int BLI_backup(char *file, char *from, char *to); int BLI_is_writable(char *filename); /** @@ -295,8 +315,10 @@ int BLI_rename(char *from, char *to); int BLI_gzip(char *from, char *to); int BLI_delete(char *file, int dir, int recursive); int BLI_move(char *file, char *to); -int BLI_touch(char *file); -char *BLI_last_slash(char *string); +int BLI_touch(const char *file); +char *BLI_last_slash(const char *string); +void BLI_add_slash(char *string); +void BLI_del_slash(char *string); /* BLI_rct.c */ /** @@ -397,7 +419,7 @@ void *BLI_pointer_from_int(int val); * @param member The name of a member field of @a strct * @retval The offset in bytes of @a member within @a strct */ -#define BLI_STRUCT_OFFSET(strct, member) ((int) &((strct*) 0)->member) +#define BLI_STRUCT_OFFSET(strct, member) ((int)(intptr_t) &((strct*) 0)->member) #ifdef __cplusplus } diff --git a/source/blender/blenlib/BLI_bpath.h b/source/blender/blenlib/BLI_bpath.h index 9426064f59f..874c8c7828c 100644 --- a/source/blender/blenlib/BLI_bpath.h +++ b/source/blender/blenlib/BLI_bpath.h @@ -29,6 +29,13 @@ /* Based on ghash, difference is ghash is not a fixed size, * so for BPath we dont need to malloc */ +struct BPathIteratorSeqData { + int totseq; + int seq; + struct Sequence **seqar; /* Sequence */ + struct Scene *scene; /* Current scene */ +}; + struct BPathIterator { char* path; char* lib; @@ -36,21 +43,30 @@ struct BPathIterator { void* data; int len; int type; + + void (*setpath_callback)(struct BPathIterator *, char *); + void (*getpath_callback)(struct BPathIterator *, char *); + + /* only for seq data */ + struct BPathIteratorSeqData seqdata; }; -void BLI_bpathIterator_init (struct BPathIterator *bpi); -char* BLI_bpathIterator_getPath (struct BPathIterator *bpi); -char* BLI_bpathIterator_getLib (struct BPathIterator *bpi); -char* BLI_bpathIterator_getName (struct BPathIterator *bpi); -int BLI_bpathIterator_getType (struct BPathIterator *bpi); -int BLI_bpathIterator_getPathMaxLen(struct BPathIterator *bpi); -void BLI_bpathIterator_step (struct BPathIterator *bpi); -int BLI_bpathIterator_isDone (struct BPathIterator *bpi); -void BLI_bpathIterator_copyPathExpanded( struct BPathIterator *bpi, char *path_expanded); +void BLI_bpathIterator_init (struct BPathIterator *bpi); +void BLI_bpathIterator_free (struct BPathIterator *bpi); +char* BLI_bpathIterator_getLib (struct BPathIterator *bpi); +char* BLI_bpathIterator_getName (struct BPathIterator *bpi); +int BLI_bpathIterator_getType (struct BPathIterator *bpi); +int BLI_bpathIterator_getPathMaxLen (struct BPathIterator *bpi); +void BLI_bpathIterator_step (struct BPathIterator *bpi); +int BLI_bpathIterator_isDone (struct BPathIterator *bpi); +void BLI_bpathIterator_getPath (struct BPathIterator *bpi, char *path); +void BLI_bpathIterator_getPathExpanded (struct BPathIterator *bpi, char *path_expanded); +void BLI_bpathIterator_setPath (struct BPathIterator *bpi, char *path); /* high level funcs */ /* creates a text file with missing files if there are any */ -struct Text * checkMissingFiles(void); -void makeFilesRelative(int *tot, int *changed, int *failed, int *linked); +void checkMissingFiles(char *txtname ); +void makeFilesRelative(char *txtname, int *tot, int *changed, int *failed, int *linked); +void makeFilesAbsolute(char *txtname, int *tot, int *changed, int *failed, int *linked); void findMissingFiles(char *str); diff --git a/source/blender/blenlib/BLI_edgehash.h b/source/blender/blenlib/BLI_edgehash.h index f3aa69d77ff..abbd17c3635 100644 --- a/source/blender/blenlib/BLI_edgehash.h +++ b/source/blender/blenlib/BLI_edgehash.h @@ -86,6 +86,9 @@ void BLI_edgehashIterator_getKey (EdgeHashIterator *ehi, int *v0_r, int *v1 /* Retrieve the value from an iterator. */ void* BLI_edgehashIterator_getValue (EdgeHashIterator *ehi); + /* Set the value for an iterator. */ +void BLI_edgehashIterator_setValue (EdgeHashIterator *ehi, void *val); + /* Steps the iterator to the next index. */ void BLI_edgehashIterator_step (EdgeHashIterator *ehi); diff --git a/source/blender/blenlib/BLI_editVert.h b/source/blender/blenlib/BLI_editVert.h index ae7697c7c7e..447f6a2a485 100644 --- a/source/blender/blenlib/BLI_editVert.h +++ b/source/blender/blenlib/BLI_editVert.h @@ -38,6 +38,8 @@ #include "DNA_customdata_types.h" #include "DNA_mesh_types.h" +#include "BLO_sys_types.h" // for intptr_t support + struct DerivedMesh; struct RetopoPaintData; @@ -53,7 +55,7 @@ typedef struct EditVert struct EditEdge *e; struct EditFace *f; void *p; - long l; + intptr_t l; float fp; } tmp; float no[3]; /*vertex normal */ @@ -64,6 +66,7 @@ typedef struct EditVert h for hidden. if (!eve->h) {... f1 and f2 can be used for temp data, clear them first*/ unsigned char f, h, f1, f2; + float bweight; short fast; /* only 0 or 1, for editmesh_fastmalloc, do not store temp data here! */ int hash; int keyindex; /* original index #, for restoring key information */ @@ -94,12 +97,13 @@ typedef struct EditEdge struct EditEdge *e; struct EditFace *f; void *p; - long l; + intptr_t l; float fp; } tmp; short f1, f2; /* short, f1 is (ab)used in subdiv */ unsigned char f, h, dir, seam, sharp; float crease; + float bweight; short fast; /* only 0 or 1, for editmesh_fastmalloc */ short fgoni; /* index for fgon, for search */ HashEdge hash; @@ -120,7 +124,7 @@ typedef struct EditFace struct EditEdge *e; struct EditFace *f; void *p; - long l; + intptr_t l; float fp; } tmp; float n[3], cent[3]; diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h index aec77f5f385..c77e82f0a2b 100644 --- a/source/blender/blenlib/BLI_ghash.h +++ b/source/blender/blenlib/BLI_ghash.h @@ -34,7 +34,12 @@ struct GHash; typedef struct GHash GHash; -typedef struct GHashIterator GHashIterator; + +typedef struct GHashIterator { + GHash *gh; + int curBucket; + struct Entry *curEntry; +} GHashIterator; typedef unsigned int (*GHashHashFP) (void *key); typedef int (*GHashCmpFP) (void *a, void *b); @@ -63,6 +68,15 @@ int BLI_ghash_size (GHash *gh); */ GHashIterator* BLI_ghashIterator_new (GHash *gh); /** + * Init an already allocated GHashIterator. The hash table must not + * be mutated while the iterator is in use, and the iterator will + * step exactly BLI_ghash_size(gh) times before becoming done. + * + * @param ghi The GHashIterator to initialize. + * @param gh The GHash to iterate over. + */ +void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh); + /** * Free a GHashIterator. * * @param ghi The iterator to free. diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h new file mode 100644 index 00000000000..160c2e04cf5 --- /dev/null +++ b/source/blender/blenlib/BLI_graph.h @@ -0,0 +1,125 @@ +#ifndef BLI_GRAPH_H_ +#define BLI_GRAPH_H_ + +#include "DNA_listBase.h" + +struct BGraph; +struct BNode; +struct BArc; + +struct RadialArc; + +typedef void (*FreeArc)(struct BArc*); +typedef void (*FreeNode)(struct BNode*); +typedef void (*RadialSymmetry)(struct BNode* root_node, struct RadialArc* ring, int total); +typedef void (*AxialSymmetry)(struct BNode* root_node, struct BNode* node1, struct BNode* node2, struct BArc* arc1, struct BArc* arc2); + +/* IF YOU MODIFY THOSE TYPES, YOU NEED TO UPDATE ALL THOSE THAT "INHERIT" FROM THEM + * + * RigGraph, ReebGraph + * + * */ + +typedef struct BGraph { + ListBase arcs; + ListBase nodes; + + float length; + + /* function pointer to deal with custom fonctionnality */ + FreeArc free_arc; + FreeNode free_node; + RadialSymmetry radial_symmetry; + AxialSymmetry axial_symmetry; +} BGraph; + +typedef struct BNode { + void *next, *prev; + float p[3]; + int flag; + + int degree; + struct BArc **arcs; + + int subgraph_index; + + int symmetry_level; + int symmetry_flag; + float symmetry_axis[3]; +} BNode; + +typedef struct BArc { + void *next, *prev; + struct BNode *head, *tail; + int flag; + + float length; + + int symmetry_level; + int symmetry_group; + int symmetry_flag; +} BArc; + +/* Helper structure for radial symmetry */ +typedef struct RadialArc +{ + struct BArc *arc; + float n[3]; /* normalized vector joining the nodes of the arc */ +} RadialArc; + +BNode *BLI_otherNode(BArc *arc, BNode *node); + +void BLI_freeNode(BGraph *graph, BNode *node); +void BLI_removeNode(BGraph *graph, BNode *node); + +void BLI_removeArc(BGraph *graph, BArc *arc); + +void BLI_flagNodes(BGraph *graph, int flag); +void BLI_flagArcs(BGraph *graph, int flag); + +int BLI_hasAdjacencyList(BGraph *rg); +void BLI_buildAdjacencyList(BGraph *rg); +void BLI_rebuildAdjacencyList(BGraph* rg); +void BLI_rebuildAdjacencyListForNode(BGraph* rg, BNode *node); +void BLI_freeAdjacencyList(BGraph *rg); + +int BLI_FlagSubgraphs(BGraph *graph); +void BLI_ReflagSubgraph(BGraph *graph, int old_subgraph, int new_subgraph); + +#define SHAPE_RADIX 10 /* each shape level is encoded this base */ + +int BLI_subtreeShape(BGraph *graph, BNode *node, BArc *rootArc, int include_root); +float BLI_subtreeLength(BNode *node); +void BLI_calcGraphLength(BGraph *graph); + +void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced); +void BLI_replaceNodeInArc(BGraph *graph, BArc *arc, BNode *node_src, BNode *node_replaced); +void BLI_removeDoubleNodes(BGraph *graph, float limit); +BNode * BLI_FindNodeByPosition(BGraph *graph, float *p, float limit); + +BArc * BLI_findConnectedArc(BGraph *graph, BArc *arc, BNode *v); + +int BLI_isGraphCyclic(BGraph *graph); + +/*------------ Symmetry handling ------------*/ +void BLI_markdownSymmetry(BGraph *graph, BNode *root_node, float limit); + +void BLI_mirrorAlongAxis(float v[3], float center[3], float axis[3]); + +/* BNode symmetry flags */ +#define SYM_TOPOLOGICAL 1 +#define SYM_PHYSICAL 2 + +/* the following two are exclusive */ +#define SYM_AXIAL 4 +#define SYM_RADIAL 8 + +/* BArc symmetry flags + * + * axial symetry sides */ +#define SYM_SIDE_POSITIVE 1 +#define SYM_SIDE_NEGATIVE 2 +/* Anything higher is the order in radial symmetry */ +#define SYM_SIDE_RADIAL 3 + +#endif /*BLI_GRAPH_H_*/ diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h new file mode 100644 index 00000000000..e3591a84e98 --- /dev/null +++ b/source/blender/blenlib/BLI_kdopbvh.h @@ -0,0 +1,97 @@ +/** + * + * $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) 2006 by NaN Holding BV. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): Daniel Genrich, Andre Pinto + * + * ***** END GPL LICENSE BLOCK ***** + */ + + +#ifndef BLI_KDOPBVH_H +#define BLI_KDOPBVH_H + +#include <float.h> + +struct BVHTree; +typedef struct BVHTree BVHTree; + +typedef struct BVHTreeOverlap { + int indexA; + int indexB; +} BVHTreeOverlap; + +typedef struct BVHTreeNearest +{ + int index; /* the index of the nearest found (untouched if none is found within a dist radius from the given coordinates) */ + float co[3]; /* nearest coordinates (untouched it none is found within a dist radius from the given coordinates) */ + float no[3]; /* normal at nearest coordinates (untouched it none is found within a dist radius from the given coordinates) */ + float dist; /* squared distance to search arround */ +} BVHTreeNearest; + +typedef struct BVHTreeRay +{ + float origin[3]; /* ray origin */ + float direction[3]; /* ray direction */ + float radius; /* radius around ray */ +} BVHTreeRay; + +typedef struct BVHTreeRayHit +{ + int index; /* index of the tree node (untouched if no hit is found) */ + float co[3]; /* coordinates of the hit point */ + float no[3]; /* normal on hit point */ + float dist; /* distance to the hit point */ +} BVHTreeRayHit; + +/* callback must update nearest in case it finds a nearest result */ +typedef void (*BVHTree_NearestPointCallback) (void *userdata, int index, const float *co, BVHTreeNearest *nearest); + +/* callback must update hit in case it finds a nearest successful hit */ +typedef void (*BVHTree_RayCastCallback) (void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit); + + +BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis); +void BLI_bvhtree_free(BVHTree *tree); + +/* construct: first insert points, then call balance */ +int BLI_bvhtree_insert(BVHTree *tree, int index, float *co, int numpoints); +void BLI_bvhtree_balance(BVHTree *tree); + +/* update: first update points/nodes, then call update_tree to refit the bounding volumes */ +int BLI_bvhtree_update_node(BVHTree *tree, int index, float *co, float *co_moving, int numpoints); +void BLI_bvhtree_update_tree(BVHTree *tree); + +/* collision/overlap: check two trees if they overlap, alloc's *overlap with length of the int return value */ +BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, int *result); + +float BLI_bvhtree_getepsilon(BVHTree *tree); + +/* find nearest node to the given coordinates (if nearest is given it will only search nodes where square distance is smaller than nearest->dist) */ +int BLI_bvhtree_find_nearest(BVHTree *tree, const float *co, BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata); + +int BLI_bvhtree_ray_cast(BVHTree *tree, const float *co, const float *dir, float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata); + +#endif // BLI_KDOPBVH_H + diff --git a/source/blender/blenlib/BLI_mempool.h b/source/blender/blenlib/BLI_mempool.h new file mode 100644 index 00000000000..8b31459dd38 --- /dev/null +++ b/source/blender/blenlib/BLI_mempool.h @@ -0,0 +1,44 @@ +/** + * Simple fast memory allocator + * + * + * ***** 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 ***** + */ + +#ifndef BLI_MEMPOOL_H +#define BLI_MEMPOOL_H + +struct BLI_mempool; +typedef struct BLI_mempool BLI_mempool; + +BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk); +void *BLI_mempool_alloc(BLI_mempool *pool); +void *BLI_mempool_calloc(BLI_mempool *pool); +void BLI_mempool_free(BLI_mempool *pool, void *addr); +void BLI_mempool_destroy(BLI_mempool *pool); + + +#endif diff --git a/source/blender/blenlib/BLI_rand.h b/source/blender/blenlib/BLI_rand.h index 0e534783c17..266aa347aff 100644 --- a/source/blender/blenlib/BLI_rand.h +++ b/source/blender/blenlib/BLI_rand.h @@ -44,6 +44,7 @@ struct RNG* rng_new (unsigned int seed); void rng_free (struct RNG* rng); void rng_seed (struct RNG* rng, unsigned int seed); +void rng_srandom(struct RNG *rng, unsigned int seed); int rng_getInt (struct RNG* rng); double rng_getDouble (struct RNG* rng); float rng_getFloat (struct RNG* rng); diff --git a/source/blender/blenlib/BLI_threads.h b/source/blender/blenlib/BLI_threads.h index 60ecce3f9d8..5a7e84c42fb 100644 --- a/source/blender/blenlib/BLI_threads.h +++ b/source/blender/blenlib/BLI_threads.h @@ -39,16 +39,41 @@ #define BLENDER_MAX_THREADS 8 struct ListBase; - void BLI_init_threads (struct ListBase *threadbase, void *(*do_thread)(void *), int tot); int BLI_available_threads(struct ListBase *threadbase); int BLI_available_thread_index(struct ListBase *threadbase); void BLI_insert_thread (struct ListBase *threadbase, void *callerdata); void BLI_remove_thread (struct ListBase *threadbase, void *callerdata); +void BLI_remove_thread_index(struct ListBase *threadbase, int index); +void BLI_remove_threads(struct ListBase *threadbase); void BLI_end_threads (struct ListBase *threadbase); void BLI_lock_thread (int type); void BLI_unlock_thread (int type); +int BLI_system_thread_count( void ); /* gets the number of threads the system can make use of */ + +/* ThreadedWorker is a simple tool for dispatching work to a limited number of threads in a transparent + * fashion from the caller's perspective + * */ + +struct ThreadedWorker; + +/* Create a new worker supporting tot parallel threads. + * When new work in inserted and all threads are busy, sleep(sleep_time) before checking again + */ +struct ThreadedWorker *BLI_create_worker(void *(*do_thread)(void *), int tot, int sleep_time); + +/* join all working threads */ +void BLI_end_worker(struct ThreadedWorker *worker); + +/* also ends all working threads */ +void BLI_destroy_worker(struct ThreadedWorker *worker); + +/* Spawns a new work thread if possible, sleeps until one is available otherwise + * NOTE: inserting work is NOT thread safe, so make sure it is only done from one thread */ +void BLI_insert_work(struct ThreadedWorker *worker, void *param); + + #endif diff --git a/source/blender/blenlib/BLI_winstuff.h b/source/blender/blenlib/BLI_winstuff.h index 54d70626dd5..3bb63506c95 100644 --- a/source/blender/blenlib/BLI_winstuff.h +++ b/source/blender/blenlib/BLI_winstuff.h @@ -61,6 +61,10 @@ // These definitions are also in arithb for simplicity +#ifdef __cplusplus +extern "C" { +#endif + #ifndef M_PI #define M_PI 3.14159265358979323846 #endif @@ -73,6 +77,9 @@ #ifndef M_SQRT1_2 #define M_SQRT1_2 0.70710678118654752440 #endif +#ifndef M_1_PI +#define M_1_PI 0.318309886183790671538 +#endif #define MAXPATHLEN MAX_PATH @@ -110,7 +117,12 @@ void RegisterBlendExtension(char * str); DIR *opendir (const char *path); struct dirent *readdir(DIR *dp); int closedir (DIR *dp); -void get_default_root(char* root); +void get_default_root(char *root); +int check_file_chars(char *filename); + +#ifdef __cplusplus +} +#endif #endif /* __WINSTUFF_H__ */ diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index d5e34d7d4de..4eb01a50f39 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -33,6 +33,13 @@ SET(INC ${ZLIB_INC} ) +IF(CMAKE_SYSTEM_NAME MATCHES "Linux") +SET(INC + ${INC} + ${BINRELOC_INC} +) +ENDIF(CMAKE_SYSTEM_NAME MATCHES "Linux") + IF(WITH_VERSE) ADD_DEFINITIONS(-DWITH_VERSE) SET(INC ${INC} ${VERSE_INC}) diff --git a/source/blender/blenlib/SConscript b/source/blender/blenlib/SConscript index 9d81ac05472..01a9a1eab0e 100644 --- a/source/blender/blenlib/SConscript +++ b/source/blender/blenlib/SConscript @@ -7,20 +7,23 @@ cflags='' incs = '. ../makesdna ../blenkernel #/intern/guardedalloc ../editors/include' incs += ' ' + env['BF_FREETYPE_INC'] incs += ' ' + env['BF_ZLIB_INC'] -incs += ' ' + env['BF_SDL_INC'] defs = '' -if env['WITH_BF_INTERNATIONAL'] == 1: - defs = 'WITH_FREETYPE2' +if env['WITH_BF_SDL']: + incs += ' ' + env['BF_SDL_INC'] + +if env['WITH_BF_INTERNATIONAL']: + defs = 'WITH_FREETYPE2' if env['WITH_BF_VERSE']: defs += ' WITH_VERSE' incs += ' ' + env['BF_VERSE_INCLUDE'] if env['OURPLATFORM'] == 'linux2': - cflags='-pthread' + cflags='-pthread' + incs += ' ../../../extern/binreloc/include' if env['OURPLATFORM'] in ('win32-vc', 'win32-mingw'): - incs += ' ' + env['BF_PTHREADS_INC'] + incs += ' ' + env['BF_PTHREADS_INC'] -env.BlenderLib ( 'bf_blenlib', sources, Split(incs), Split(defs), libtype=['core','player'], priority = [100,195], compileflags =cflags ) +env.BlenderLib ( 'bf_blenlib', sources, Split(incs), Split(defs), libtype=['core', 'intern', 'player'], priority = [85,150,195], compileflags =cflags ) diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index 227cb8f5e9a..1967b8a88e2 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -34,6 +34,8 @@ #include "MEM_guardedalloc.h" #include "BLI_ghash.h" +#include "BLO_sys_types.h" // for intptr_t support + #ifdef HAVE_CONFIG_H #include <config.h> #endif @@ -198,12 +200,6 @@ void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreef /***/ -struct GHashIterator { - GHash *gh; - int curBucket; - Entry *curEntry; -}; - GHashIterator *BLI_ghashIterator_new(GHash *gh) { GHashIterator *ghi= malloc(sizeof(*ghi)); ghi->gh= gh; @@ -217,6 +213,17 @@ GHashIterator *BLI_ghashIterator_new(GHash *gh) { } return ghi; } +void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh) { + ghi->gh= gh; + ghi->curEntry= NULL; + ghi->curBucket= -1; + while (!ghi->curEntry) { + ghi->curBucket++; + if (ghi->curBucket==ghi->gh->nbuckets) + break; + ghi->curEntry= ghi->gh->buckets[ghi->curBucket]; + } +} void BLI_ghashIterator_free(GHashIterator *ghi) { free(ghi); } @@ -256,11 +263,7 @@ int BLI_ghashutil_ptrcmp(void *a, void *b) { } unsigned int BLI_ghashutil_inthash(void *ptr) { -#if defined(_WIN64) - unsigned __int64 key = (unsigned __int64)ptr; -#else - unsigned long key = (unsigned long)ptr; -#endif + uintptr_t key = (uintptr_t)ptr; key += ~(key << 16); key ^= (key >> 5); diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c new file mode 100644 index 00000000000..30472beb3e6 --- /dev/null +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -0,0 +1,1526 @@ +/** + * + * ***** 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) 2006 by NaN Holding BV. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): Daniel Genrich, Andre Pinto + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#include "math.h" +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <assert.h> + +#include "MEM_guardedalloc.h" + +#include "BKE_utildefines.h" + +#include "BLI_kdopbvh.h" +#include "BLI_arithb.h" + +#ifdef _OPENMP +#include <omp.h> +#endif + + + +#define MAX_TREETYPE 32 +#define DEFAULT_FIND_NEAREST_HEAP_SIZE 1024 + +typedef struct BVHNode +{ + struct BVHNode **children; + struct BVHNode *parent; // some user defined traversed need that + float *bv; // Bounding volume of all nodes, max 13 axis + int index; // face, edge, vertex index + char totnode; // how many nodes are used, used for speedup + char main_axis; // Axis used to split this node +} BVHNode; + +struct BVHTree +{ + BVHNode **nodes; + BVHNode *nodearray; /* pre-alloc branch nodes */ + BVHNode **nodechild; // pre-alloc childs for nodes + float *nodebv; // pre-alloc bounding-volumes for nodes + float epsilon; /* epslion is used for inflation of the k-dop */ + int totleaf; // leafs + int totbranch; + char tree_type; // type of tree (4 => quadtree) + char axis; // kdop type (6 => OBB, 7 => AABB, ...) + char start_axis, stop_axis; // KDOP_AXES array indices according to axis +}; + +typedef struct BVHOverlapData +{ + BVHTree *tree1, *tree2; + BVHTreeOverlap *overlap; + int i, max_overlap; /* i is number of overlaps */ + int start_axis, stop_axis; +} BVHOverlapData; + +typedef struct BVHNearestData +{ + BVHTree *tree; + const float *co; + BVHTree_NearestPointCallback callback; + void *userdata; + float proj[13]; //coordinates projection over axis + BVHTreeNearest nearest; + +} BVHNearestData; + +typedef struct BVHRayCastData +{ + BVHTree *tree; + + BVHTree_RayCastCallback callback; + void *userdata; + + + BVHTreeRay ray; + float ray_dot_axis[13]; + + BVHTreeRayHit hit; +} BVHRayCastData; +////////////////////////////////////////m + + +//////////////////////////////////////////////////////////////////////// +// Bounding Volume Hierarchy Definition +// +// Notes: From OBB until 26-DOP --> all bounding volumes possible, just choose type below +// Notes: You have to choose the type at compile time ITM +// Notes: You can choose the tree type --> binary, quad, octree, choose below +//////////////////////////////////////////////////////////////////////// + +static float KDOP_AXES[13][3] = +{ {1.0, 0, 0}, {0, 1.0, 0}, {0, 0, 1.0}, {1.0, 1.0, 1.0}, {1.0, -1.0, 1.0}, {1.0, 1.0, -1.0}, +{1.0, -1.0, -1.0}, {1.0, 1.0, 0}, {1.0, 0, 1.0}, {0, 1.0, 1.0}, {1.0, -1.0, 0}, {1.0, 0, -1.0}, +{0, 1.0, -1.0} +}; + +/* + * Generic push and pop heap + */ +#define PUSH_HEAP_BODY(HEAP_TYPE,PRIORITY,heap,heap_size) \ +{ \ + HEAP_TYPE element = heap[heap_size-1]; \ + int child = heap_size-1; \ + while(child != 0) \ + { \ + int parent = (child-1) / 2; \ + if(PRIORITY(element, heap[parent])) \ + { \ + heap[child] = heap[parent]; \ + child = parent; \ + } \ + else break; \ + } \ + heap[child] = element; \ +} + +#define POP_HEAP_BODY(HEAP_TYPE, PRIORITY,heap,heap_size) \ +{ \ + HEAP_TYPE element = heap[heap_size-1]; \ + int parent = 0; \ + while(parent < (heap_size-1)/2 ) \ + { \ + int child2 = (parent+1)*2; \ + if(PRIORITY(heap[child2-1], heap[child2])) \ + --child2; \ + \ + if(PRIORITY(element, heap[child2])) \ + break; \ + \ + heap[parent] = heap[child2]; \ + parent = child2; \ + } \ + heap[parent] = element; \ +} + +int ADJUST_MEMORY(void *local_memblock, void **memblock, int new_size, int *max_size, int size_per_item) +{ + int new_max_size = *max_size * 2; + void *new_memblock = NULL; + + if(new_size <= *max_size) + return TRUE; + + if(*memblock == local_memblock) + { + new_memblock = malloc( size_per_item * new_max_size ); + memcpy( new_memblock, *memblock, size_per_item * *max_size ); + } + else + new_memblock = realloc(*memblock, size_per_item * new_max_size ); + + if(new_memblock) + { + *memblock = new_memblock; + *max_size = new_max_size; + return TRUE; + } + else + return FALSE; +} + + +////////////////////////////////////////////////////////////////////////////////////////////////////// +// Introsort +// with permission deriven from the following Java code: +// http://ralphunden.net/content/tutorials/a-guide-to-introsort/ +// and he derived it from the SUN STL +////////////////////////////////////////////////////////////////////////////////////////////////////// +static int size_threshold = 16; +/* +* Common methods for all algorithms +*/ +static int floor_lg(int a) +{ + return (int)(floor(log(a)/log(2))); +} + +/* +* Insertion sort algorithm +*/ +static void bvh_insertionsort(BVHNode **a, int lo, int hi, int axis) +{ + int i,j; + BVHNode *t; + for (i=lo; i < hi; i++) + { + j=i; + t = a[i]; + while((j!=lo) && (t->bv[axis] < (a[j-1])->bv[axis])) + { + a[j] = a[j-1]; + j--; + } + a[j] = t; + } +} + +static int bvh_partition(BVHNode **a, int lo, int hi, BVHNode * x, int axis) +{ + int i=lo, j=hi; + while (1) + { + while ((a[i])->bv[axis] < x->bv[axis]) i++; + j--; + while (x->bv[axis] < (a[j])->bv[axis]) j--; + if(!(i < j)) + return i; + SWAP( BVHNode* , a[i], a[j]); + i++; + } +} + +/* +* Heapsort algorithm +*/ +static void bvh_downheap(BVHNode **a, int i, int n, int lo, int axis) +{ + BVHNode * d = a[lo+i-1]; + int child; + while (i<=n/2) + { + child = 2*i; + if ((child < n) && ((a[lo+child-1])->bv[axis] < (a[lo+child])->bv[axis])) + { + child++; + } + if (!(d->bv[axis] < (a[lo+child-1])->bv[axis])) break; + a[lo+i-1] = a[lo+child-1]; + i = child; + } + a[lo+i-1] = d; +} + +static void bvh_heapsort(BVHNode **a, int lo, int hi, int axis) +{ + int n = hi-lo, i; + for (i=n/2; i>=1; i=i-1) + { + bvh_downheap(a, i,n,lo, axis); + } + for (i=n; i>1; i=i-1) + { + SWAP(BVHNode*, a[lo],a[lo+i-1]); + bvh_downheap(a, 1,i-1,lo, axis); + } +} + +static BVHNode *bvh_medianof3(BVHNode **a, int lo, int mid, int hi, int axis) // returns Sortable +{ + if ((a[mid])->bv[axis] < (a[lo])->bv[axis]) + { + if ((a[hi])->bv[axis] < (a[mid])->bv[axis]) + return a[mid]; + else + { + if ((a[hi])->bv[axis] < (a[lo])->bv[axis]) + return a[hi]; + else + return a[lo]; + } + } + else + { + if ((a[hi])->bv[axis] < (a[mid])->bv[axis]) + { + if ((a[hi])->bv[axis] < (a[lo])->bv[axis]) + return a[lo]; + else + return a[hi]; + } + else + return a[mid]; + } +} +/* +* Quicksort algorithm modified for Introsort +*/ +static void bvh_introsort_loop (BVHNode **a, int lo, int hi, int depth_limit, int axis) +{ + int p; + + while (hi-lo > size_threshold) + { + if (depth_limit == 0) + { + bvh_heapsort(a, lo, hi, axis); + return; + } + depth_limit=depth_limit-1; + p=bvh_partition(a, lo, hi, bvh_medianof3(a, lo, lo+((hi-lo)/2)+1, hi-1, axis), axis); + bvh_introsort_loop(a, p, hi, depth_limit, axis); + hi=p; + } +} + +static void sort(BVHNode **a0, int begin, int end, int axis) +{ + if (begin < end) + { + BVHNode **a=a0; + bvh_introsort_loop(a, begin, end, 2*floor_lg(end-begin), axis); + bvh_insertionsort(a, begin, end, axis); + } +} +void sort_along_axis(BVHTree *tree, int start, int end, int axis) +{ + sort(tree->nodes, start, end, axis); +} + +//after a call to this function you can expect one of: +// every node to left of a[n] are smaller or equal to it +// every node to the right of a[n] are greater or equal to it +int partition_nth_element(BVHNode **a, int _begin, int _end, int n, int axis){ + int begin = _begin, end = _end, cut; + while(end-begin > 3) + { + cut = bvh_partition(a, begin, end, bvh_medianof3(a, begin, (begin+end)/2, end-1, axis), axis ); + if(cut <= n) + begin = cut; + else + end = cut; + } + bvh_insertionsort(a, begin, end, axis); + + return n; +} + +////////////////////////////////////////////////////////////////////////////////////////////////////// + +/* + * BVHTree bounding volumes functions + */ +static void create_kdop_hull(BVHTree *tree, BVHNode *node, float *co, int numpoints, int moving) +{ + float newminmax; + float *bv = node->bv; + int i, k; + + // don't init boudings for the moving case + if(!moving) + { + for (i = tree->start_axis; i < tree->stop_axis; i++) + { + bv[2*i] = FLT_MAX; + bv[2*i + 1] = -FLT_MAX; + } + } + + for(k = 0; k < numpoints; k++) + { + // for all Axes. + for (i = tree->start_axis; i < tree->stop_axis; i++) + { + newminmax = INPR(&co[k * 3], KDOP_AXES[i]); + if (newminmax < bv[2 * i]) + bv[2 * i] = newminmax; + if (newminmax > bv[(2 * i) + 1]) + bv[(2 * i) + 1] = newminmax; + } + } +} + +// depends on the fact that the BVH's for each face is already build +static void refit_kdop_hull(BVHTree *tree, BVHNode *node, int start, int end) +{ + float newmin,newmax; + int i, j; + float *bv = node->bv; + + + for (i = tree->start_axis; i < tree->stop_axis; i++) + { + bv[2*i] = FLT_MAX; + bv[2*i + 1] = -FLT_MAX; + } + + for (j = start; j < end; j++) + { +// for all Axes. + for (i = tree->start_axis; i < tree->stop_axis; i++) + { + newmin = tree->nodes[j]->bv[(2 * i)]; + if ((newmin < bv[(2 * i)])) + bv[(2 * i)] = newmin; + + newmax = tree->nodes[j]->bv[(2 * i) + 1]; + if ((newmax > bv[(2 * i) + 1])) + bv[(2 * i) + 1] = newmax; + } + } + +} + +// only supports x,y,z axis in the moment +// but we should use a plain and simple function here for speed sake +static char get_largest_axis(float *bv) +{ + float middle_point[3]; + + middle_point[0] = (bv[1]) - (bv[0]); // x axis + middle_point[1] = (bv[3]) - (bv[2]); // y axis + middle_point[2] = (bv[5]) - (bv[4]); // z axis + if (middle_point[0] > middle_point[1]) + { + if (middle_point[0] > middle_point[2]) + return 1; // max x axis + else + return 5; // max z axis + } + else + { + if (middle_point[1] > middle_point[2]) + return 3; // max y axis + else + return 5; // max z axis + } +} + +// bottom-up update of bvh node BV +// join the children on the parent BV +static void node_join(BVHTree *tree, BVHNode *node) +{ + int i, j; + + for (i = tree->start_axis; i < tree->stop_axis; i++) + { + node->bv[2*i] = FLT_MAX; + node->bv[2*i + 1] = -FLT_MAX; + } + + for (i = 0; i < tree->tree_type; i++) + { + if (node->children[i]) + { + for (j = tree->start_axis; j < tree->stop_axis; j++) + { + // update minimum + if (node->children[i]->bv[(2 * j)] < node->bv[(2 * j)]) + node->bv[(2 * j)] = node->children[i]->bv[(2 * j)]; + + // update maximum + if (node->children[i]->bv[(2 * j) + 1] > node->bv[(2 * j) + 1]) + node->bv[(2 * j) + 1] = node->children[i]->bv[(2 * j) + 1]; + } + } + else + break; + } +} + +/* + * Debug and information functions + */ +static void bvhtree_print_tree(BVHTree *tree, BVHNode *node, int depth) +{ + int i; + for(i=0; i<depth; i++) printf(" "); + printf(" - %d (%ld): ", node->index, node - tree->nodearray); + for(i=2*tree->start_axis; i<2*tree->stop_axis; i++) + printf("%.3f ", node->bv[i]); + printf("\n"); + + for(i=0; i<tree->tree_type; i++) + if(node->children[i]) + bvhtree_print_tree(tree, node->children[i], depth+1); +} + +static void bvhtree_info(BVHTree *tree) +{ + printf("BVHTree info\n"); + printf("tree_type = %d, axis = %d, epsilon = %f\n", tree->tree_type, tree->axis, tree->epsilon); + printf("nodes = %d, branches = %d, leafs = %d\n", tree->totbranch + tree->totleaf, tree->totbranch, tree->totleaf); + printf("Memory per node = %ldbytes\n", sizeof(BVHNode) + sizeof(BVHNode*)*tree->tree_type + sizeof(float)*tree->axis); + printf("BV memory = %dbytes\n", MEM_allocN_len(tree->nodebv)); + + printf("Total memory = %ldbytes\n", sizeof(BVHTree) + + MEM_allocN_len(tree->nodes) + + MEM_allocN_len(tree->nodearray) + + MEM_allocN_len(tree->nodechild) + + MEM_allocN_len(tree->nodebv) + ); + +// bvhtree_print_tree(tree, tree->nodes[tree->totleaf], 0); +} + +#if 0 + + +static void verify_tree(BVHTree *tree) +{ + int i, j, check = 0; + + // check the pointer list + for(i = 0; i < tree->totleaf; i++) + { + if(tree->nodes[i]->parent == NULL) + printf("Leaf has no parent: %d\n", i); + else + { + for(j = 0; j < tree->tree_type; j++) + { + if(tree->nodes[i]->parent->children[j] == tree->nodes[i]) + check = 1; + } + if(!check) + { + printf("Parent child relationship doesn't match: %d\n", i); + } + check = 0; + } + } + + // check the leaf list + for(i = 0; i < tree->totleaf; i++) + { + if(tree->nodearray[i].parent == NULL) + printf("Leaf has no parent: %d\n", i); + else + { + for(j = 0; j < tree->tree_type; j++) + { + if(tree->nodearray[i].parent->children[j] == &tree->nodearray[i]) + check = 1; + } + if(!check) + { + printf("Parent child relationship doesn't match: %d\n", i); + } + check = 0; + } + } + + printf("branches: %d, leafs: %d, total: %d\n", tree->totbranch, tree->totleaf, tree->totbranch + tree->totleaf); +} +#endif + +//Helper data and structures to build a min-leaf generalized implicit tree +//This code can be easily reduced (basicly this is only method to calculate pow(k, n) in O(1).. and stuff like that) +typedef struct BVHBuildHelper +{ + int tree_type; // + int totleafs; // + + int leafs_per_child [32]; //Min number of leafs that are archievable from a node at depth N + int branches_on_level[32]; //Number of nodes at depth N (tree_type^N) + + int remain_leafs; //Number of leafs that are placed on the level that is not 100% filled + +} BVHBuildHelper; + +static void build_implicit_tree_helper(BVHTree *tree, BVHBuildHelper *data) +{ + int depth = 0; + int remain; + int nnodes; + + data->totleafs = tree->totleaf; + data->tree_type= tree->tree_type; + + //Calculate the smallest tree_type^n such that tree_type^n >= num_leafs + for( + data->leafs_per_child[0] = 1; + data->leafs_per_child[0] < data->totleafs; + data->leafs_per_child[0] *= data->tree_type + ); + + data->branches_on_level[0] = 1; + + //We could stop the loop first (but I am lazy to find out when) + for(depth = 1; depth < 32; depth++) + { + data->branches_on_level[depth] = data->branches_on_level[depth-1] * data->tree_type; + data->leafs_per_child [depth] = data->leafs_per_child [depth-1] / data->tree_type; + } + + remain = data->totleafs - data->leafs_per_child[1]; + nnodes = (remain + data->tree_type - 2) / (data->tree_type - 1); + data->remain_leafs = remain + nnodes; +} + +// return the min index of all the leafs archivable with the given branch +static int implicit_leafs_index(BVHBuildHelper *data, int depth, int child_index) +{ + int min_leaf_index = child_index * data->leafs_per_child[depth-1]; + if(min_leaf_index <= data->remain_leafs) + return min_leaf_index; + else if(data->leafs_per_child[depth]) + return data->totleafs - (data->branches_on_level[depth-1] - child_index) * data->leafs_per_child[depth]; + else + return data->remain_leafs; +} + +/** + * Generalized implicit tree build + * + * An implicit tree is a tree where its structure is implied, thus there is no need to store child pointers or indexs. + * Its possible to find the position of the child or the parent with simple maths (multiplication and adittion). This type + * of tree is for example used on heaps.. where node N has its childs at indexs N*2 and N*2+1. + * + * Altought in this case the tree type is general.. and not know until runtime. + * tree_type stands for the maximum number of childs that a tree node can have. + * All tree types >= 2 are supported. + * + * Advantages of the used trees include: + * - No need to store child/parent relations (they are implicit); + * - Any node child always has an index greater than the parent; + * - Brother nodes are sequencial in memory; + * + * + * Some math relations derived for general implicit trees: + * + * K = tree_type, ( 2 <= K ) + * ROOT = 1 + * N child of node A = A * K + (2 - K) + N, (0 <= N < K) + * + * Util methods: + * TODO... + * (looping elements, knowing if its a leaf or not.. etc...) + */ + +// This functions returns the number of branches needed to have the requested number of leafs. +static int implicit_needed_branches(int tree_type, int leafs) +{ + return MAX2(1, (leafs + tree_type - 3) / (tree_type-1) ); +} + +/* + * This function handles the problem of "sorting" the leafs (along the split_axis). + * + * It arranges the elements in the given partitions such that: + * - any element in partition N is less or equal to any element in partition N+1. + * - if all elements are diferent all partition will get the same subset of elements + * as if the array was sorted. + * + * partition P is described as the elements in the range ( nth[P] , nth[P+1] ] + * + * TODO: This can be optimized a bit by doing a specialized nth_element instead of K nth_elements + */ +static void split_leafs(BVHNode **leafs_array, int *nth, int partitions, int split_axis) +{ + int i; + for(i=0; i < partitions-1; i++) + { + if(nth[i] >= nth[partitions]) + break; + + partition_nth_element(leafs_array, nth[i], nth[partitions], nth[i+1], split_axis); + } +} + +/* + * This functions builds an optimal implicit tree from the given leafs. + * Where optimal stands for: + * - The resulting tree will have the smallest number of branches; + * - At most only one branch will have NULL childs; + * - All leafs will be stored at level N or N+1. + * + * This function creates an implicit tree on branches_array, the leafs are given on the leafs_array. + * + * The tree is built per depth levels. First branchs at depth 1.. then branches at depth 2.. etc.. + * The reason is that we can build level N+1 from level N witouth any data dependencies.. thus it allows + * to use multithread building. + * + * To archieve this is necessary to find how much leafs are accessible from a certain branch, BVHBuildHelper + * implicit_needed_branches and implicit_leafs_index are auxiliar functions to solve that "optimal-split". + */ +static void non_recursive_bvh_div_nodes(BVHTree *tree, BVHNode *branches_array, BVHNode **leafs_array, int num_leafs) +{ + int i; + + const int tree_type = tree->tree_type; + const int tree_offset = 2 - tree->tree_type; //this value is 0 (on binary trees) and negative on the others + const int num_branches= implicit_needed_branches(tree_type, num_leafs); + + BVHBuildHelper data; + int depth; + + // set parent from root node to NULL + BVHNode *tmp = branches_array+0; + tmp->parent = NULL; + + //Most of bvhtree code relies on 1-leaf trees having at least one branch + //We handle that special case here + if(num_leafs == 1) + { + BVHNode *root = branches_array+0; + refit_kdop_hull(tree, root, 0, num_leafs); + root->main_axis = get_largest_axis(root->bv) / 2; + root->totnode = 1; + root->children[0] = leafs_array[0]; + root->children[0]->parent = root; + return; + } + + branches_array--; //Implicit trees use 1-based indexs + + build_implicit_tree_helper(tree, &data); + + //Loop tree levels (log N) loops + for(i=1, depth = 1; i <= num_branches; i = i*tree_type + tree_offset, depth++) + { + const int first_of_next_level = i*tree_type + tree_offset; + const int end_j = MIN2(first_of_next_level, num_branches + 1); //index of last branch on this level + int j; + + //Loop all branches on this level +#pragma omp parallel for private(j) schedule(static) + for(j = i; j < end_j; j++) + { + int k; + const int parent_level_index= j-i; + BVHNode* parent = branches_array + j; + int nth_positions[ MAX_TREETYPE + 1]; + char split_axis; + + int parent_leafs_begin = implicit_leafs_index(&data, depth, parent_level_index); + int parent_leafs_end = implicit_leafs_index(&data, depth, parent_level_index+1); + + //This calculates the bounding box of this branch + //and chooses the largest axis as the axis to divide leafs + refit_kdop_hull(tree, parent, parent_leafs_begin, parent_leafs_end); + split_axis = get_largest_axis(parent->bv); + + //Save split axis (this can be used on raytracing to speedup the query time) + parent->main_axis = split_axis / 2; + + //Split the childs along the split_axis, note: its not needed to sort the whole leafs array + //Only to assure that the elements are partioned on a way that each child takes the elements + //it would take in case the whole array was sorted. + //Split_leafs takes care of that "sort" problem. + nth_positions[ 0] = parent_leafs_begin; + nth_positions[tree_type] = parent_leafs_end; + for(k = 1; k < tree_type; k++) + { + int child_index = j * tree_type + tree_offset + k; + int child_level_index = child_index - first_of_next_level; //child level index + nth_positions[k] = implicit_leafs_index(&data, depth+1, child_level_index); + } + + split_leafs(leafs_array, nth_positions, tree_type, split_axis); + + + //Setup children and totnode counters + //Not really needed but currently most of BVH code relies on having an explicit children structure + for(k = 0; k < tree_type; k++) + { + int child_index = j * tree_type + tree_offset + k; + int child_level_index = child_index - first_of_next_level; //child level index + + int child_leafs_begin = implicit_leafs_index(&data, depth+1, child_level_index); + int child_leafs_end = implicit_leafs_index(&data, depth+1, child_level_index+1); + + if(child_leafs_end - child_leafs_begin > 1) + { + parent->children[k] = branches_array + child_index; + parent->children[k]->parent = parent; + } + else if(child_leafs_end - child_leafs_begin == 1) + { + parent->children[k] = leafs_array[ child_leafs_begin ]; + parent->children[k]->parent = parent; + } + else + break; + + parent->totnode = k+1; + } + } + } +} + + +/* + * BLI_bvhtree api + */ +BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis) +{ + BVHTree *tree; + int numnodes, i; + + // theres not support for trees below binary-trees :P + if(tree_type < 2) + return NULL; + + if(tree_type > MAX_TREETYPE) + return NULL; + + tree = (BVHTree *)MEM_callocN(sizeof(BVHTree), "BVHTree"); + + //tree epsilon must be >= FLT_EPSILON + //so that tangent rays can still hit a bounding volume.. + //this bug would show up when casting a ray aligned with a kdop-axis and with an edge of 2 faces + epsilon = MAX2(FLT_EPSILON, epsilon); + + if(tree) + { + tree->epsilon = epsilon; + tree->tree_type = tree_type; + tree->axis = axis; + + if(axis == 26) + { + tree->start_axis = 0; + tree->stop_axis = 13; + } + else if(axis == 18) + { + tree->start_axis = 7; + tree->stop_axis = 13; + } + else if(axis == 14) + { + tree->start_axis = 0; + tree->stop_axis = 7; + } + else if(axis == 8) // AABB + { + tree->start_axis = 0; + tree->stop_axis = 4; + } + else if(axis == 6) // OBB + { + tree->start_axis = 0; + tree->stop_axis = 3; + } + else + { + MEM_freeN(tree); + return NULL; + } + + + //Allocate arrays + numnodes = maxsize + implicit_needed_branches(tree_type, maxsize) + tree_type; + + tree->nodes = (BVHNode **)MEM_callocN(sizeof(BVHNode *)*numnodes, "BVHNodes"); + + if(!tree->nodes) + { + MEM_freeN(tree); + return NULL; + } + + tree->nodebv = (float*)MEM_callocN(sizeof(float)* axis * numnodes, "BVHNodeBV"); + if(!tree->nodebv) + { + MEM_freeN(tree->nodes); + MEM_freeN(tree); + } + + tree->nodechild = (BVHNode**)MEM_callocN(sizeof(BVHNode*) * tree_type * numnodes, "BVHNodeBV"); + if(!tree->nodechild) + { + MEM_freeN(tree->nodebv); + MEM_freeN(tree->nodes); + MEM_freeN(tree); + } + + tree->nodearray = (BVHNode *)MEM_callocN(sizeof(BVHNode)* numnodes, "BVHNodeArray"); + + if(!tree->nodearray) + { + MEM_freeN(tree->nodechild); + MEM_freeN(tree->nodebv); + MEM_freeN(tree->nodes); + MEM_freeN(tree); + return NULL; + } + + //link the dynamic bv and child links + for(i=0; i< numnodes; i++) + { + tree->nodearray[i].bv = tree->nodebv + i * axis; + tree->nodearray[i].children = tree->nodechild + i * tree_type; + } + + } + + return tree; +} + +void BLI_bvhtree_free(BVHTree *tree) +{ + if(tree) + { + MEM_freeN(tree->nodes); + MEM_freeN(tree->nodearray); + MEM_freeN(tree->nodebv); + MEM_freeN(tree->nodechild); + MEM_freeN(tree); + } +} + +void BLI_bvhtree_balance(BVHTree *tree) +{ + int i; + + BVHNode* branches_array = tree->nodearray + tree->totleaf; + BVHNode** leafs_array = tree->nodes; + + //This function should only be called once (some big bug goes here if its being called more than once per tree) + assert(tree->totbranch == 0); + + //Build the implicit tree + non_recursive_bvh_div_nodes(tree, branches_array, leafs_array, tree->totleaf); + + //current code expects the branches to be linked to the nodes array + //we perform that linkage here + tree->totbranch = implicit_needed_branches(tree->tree_type, tree->totleaf); + for(i = 0; i < tree->totbranch; i++) + tree->nodes[tree->totleaf + i] = branches_array + i; + + //bvhtree_info(tree); +} + +int BLI_bvhtree_insert(BVHTree *tree, int index, float *co, int numpoints) +{ + int i; + BVHNode *node = NULL; + + // insert should only possible as long as tree->totbranch is 0 + if(tree->totbranch > 0) + return 0; + + if(tree->totleaf+1 >= MEM_allocN_len(tree->nodes)/sizeof(*(tree->nodes))) + return 0; + + // TODO check if have enough nodes in array + + node = tree->nodes[tree->totleaf] = &(tree->nodearray[tree->totleaf]); + tree->totleaf++; + + create_kdop_hull(tree, node, co, numpoints, 0); + node->index= index; + + // inflate the bv with some epsilon + for (i = tree->start_axis; i < tree->stop_axis; i++) + { + node->bv[(2 * i)] -= tree->epsilon; // minimum + node->bv[(2 * i) + 1] += tree->epsilon; // maximum + } + + return 1; +} + + +// call before BLI_bvhtree_update_tree() +int BLI_bvhtree_update_node(BVHTree *tree, int index, float *co, float *co_moving, int numpoints) +{ + int i; + BVHNode *node= NULL; + + // check if index exists + if(index > tree->totleaf) + return 0; + + node = tree->nodearray + index; + + create_kdop_hull(tree, node, co, numpoints, 0); + + if(co_moving) + create_kdop_hull(tree, node, co_moving, numpoints, 1); + + // inflate the bv with some epsilon + for (i = tree->start_axis; i < tree->stop_axis; i++) + { + node->bv[(2 * i)] -= tree->epsilon; // minimum + node->bv[(2 * i) + 1] += tree->epsilon; // maximum + } + + return 1; +} + +// call BLI_bvhtree_update_node() first for every node/point/triangle +void BLI_bvhtree_update_tree(BVHTree *tree) +{ + //Update bottom=>top + //TRICKY: the way we build the tree all the childs have an index greater than the parent + //This allows us todo a bottom up update by starting on the biger numbered branch + + BVHNode** root = tree->nodes + tree->totleaf; + BVHNode** index = tree->nodes + tree->totleaf + tree->totbranch-1; + + for (; index >= root; index--) + node_join(tree, *index); +} + +float BLI_bvhtree_getepsilon(BVHTree *tree) +{ + return tree->epsilon; +} + + +/* + * BLI_bvhtree_overlap + */ +// overlap - is it possbile for 2 bv's to collide ? +static int tree_overlap(BVHNode *node1, BVHNode *node2, int start_axis, int stop_axis) +{ + float *bv1 = node1->bv; + float *bv2 = node2->bv; + + float *bv1_end = bv1 + (stop_axis<<1); + + bv1 += start_axis<<1; + bv2 += start_axis<<1; + + // test all axis if min + max overlap + for (; bv1 != bv1_end; bv1+=2, bv2+=2) + { + if ((*(bv1) > *(bv2 + 1)) || (*(bv2) > *(bv1 + 1))) + return 0; + } + + return 1; +} + +static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2) +{ + int j; + + if(tree_overlap(node1, node2, data->start_axis, data->stop_axis)) + { + // check if node1 is a leaf + if(!node1->totnode) + { + // check if node2 is a leaf + if(!node2->totnode) + { + + if(node1 == node2) + { + return; + } + + if(data->i >= data->max_overlap) + { + // try to make alloc'ed memory bigger + data->overlap = realloc(data->overlap, sizeof(BVHTreeOverlap)*data->max_overlap*2); + + if(!data->overlap) + { + printf("Out of Memory in traverse\n"); + return; + } + data->max_overlap *= 2; + } + + // both leafs, insert overlap! + data->overlap[data->i].indexA = node1->index; + data->overlap[data->i].indexB = node2->index; + + data->i++; + } + else + { + for(j = 0; j < data->tree2->tree_type; j++) + { + if(node2->children[j]) + traverse(data, node1, node2->children[j]); + } + } + } + else + { + + for(j = 0; j < data->tree2->tree_type; j++) + { + if(node1->children[j]) + traverse(data, node1->children[j], node2); + } + } + } + return; +} + +BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, int *result) +{ + int j, total = 0; + BVHTreeOverlap *overlap = NULL, *to = NULL; + BVHOverlapData **data; + + // check for compatibility of both trees (can't compare 14-DOP with 18-DOP) + if((tree1->axis != tree2->axis) && (tree1->axis == 14 || tree2->axis == 14) && (tree1->axis == 18 || tree2->axis == 18)) + return 0; + + // fast check root nodes for collision before doing big splitting + traversal + if(!tree_overlap(tree1->nodes[tree1->totleaf], tree2->nodes[tree2->totleaf], MIN2(tree1->start_axis, tree2->start_axis), MIN2(tree1->stop_axis, tree2->stop_axis))) + return 0; + + data = MEM_callocN(sizeof(BVHOverlapData *)* tree1->tree_type, "BVHOverlapData_star"); + + for(j = 0; j < tree1->tree_type; j++) + { + data[j] = (BVHOverlapData *)MEM_callocN(sizeof(BVHOverlapData), "BVHOverlapData"); + + // init BVHOverlapData + data[j]->overlap = (BVHTreeOverlap *)malloc(sizeof(BVHTreeOverlap)*MAX2(tree1->totleaf, tree2->totleaf)); + data[j]->tree1 = tree1; + data[j]->tree2 = tree2; + data[j]->max_overlap = MAX2(tree1->totleaf, tree2->totleaf); + data[j]->i = 0; + data[j]->start_axis = MIN2(tree1->start_axis, tree2->start_axis); + data[j]->stop_axis = MIN2(tree1->stop_axis, tree2->stop_axis ); + } + +#pragma omp parallel for private(j) schedule(static) + for(j = 0; j < MIN2(tree1->tree_type, tree1->nodes[tree1->totleaf]->totnode); j++) + { + traverse(data[j], tree1->nodes[tree1->totleaf]->children[j], tree2->nodes[tree2->totleaf]); + } + + for(j = 0; j < tree1->tree_type; j++) + total += data[j]->i; + + to = overlap = (BVHTreeOverlap *)MEM_callocN(sizeof(BVHTreeOverlap)*total, "BVHTreeOverlap"); + + for(j = 0; j < tree1->tree_type; j++) + { + memcpy(to, data[j]->overlap, data[j]->i*sizeof(BVHTreeOverlap)); + to+=data[j]->i; + } + + for(j = 0; j < tree1->tree_type; j++) + { + free(data[j]->overlap); + MEM_freeN(data[j]); + } + MEM_freeN(data); + + (*result) = total; + return overlap; +} + + +/* + * Nearest neighbour - BLI_bvhtree_find_nearest + */ +static float squared_dist(const float *a, const float *b) +{ + float tmp[3]; + VECSUB(tmp, a, b); + return INPR(tmp, tmp); +} + +//Determines the nearest point of the given node BV. Returns the squared distance to that point. +static float calc_nearest_point(BVHNearestData *data, BVHNode *node, float *nearest) +{ + int i; + const float *bv = node->bv; + + //nearest on AABB hull + for(i=0; i != 3; i++, bv += 2) + { + if(bv[0] > data->proj[i]) + nearest[i] = bv[0]; + else if(bv[1] < data->proj[i]) + nearest[i] = bv[1]; + else + nearest[i] = data->proj[i]; + } + +/* + //nearest on a general hull + VECCOPY(nearest, data->co); + for(i = data->tree->start_axis; i != data->tree->stop_axis; i++, bv+=2) + { + float proj = INPR( nearest, KDOP_AXES[i]); + float dl = bv[0] - proj; + float du = bv[1] - proj; + + if(dl > 0) + { + VECADDFAC(nearest, nearest, KDOP_AXES[i], dl); + } + else if(du < 0) + { + VECADDFAC(nearest, nearest, KDOP_AXES[i], du); + } + } +*/ + return squared_dist(data->co, nearest); +} + + +typedef struct NodeDistance +{ + BVHNode *node; + float dist; + +} NodeDistance; + +#define NodeDistance_priority(a,b) ( (a).dist < (b).dist ) + +// TODO: use a priority queue to reduce the number of nodes looked on +static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node) +{ + if(node->totnode == 0) + { + if(data->callback) + data->callback(data->userdata , node->index, data->co, &data->nearest); + else + { + data->nearest.index = node->index; + data->nearest.dist = calc_nearest_point(data, node, data->nearest.co); + } + } + else + { + //Better heuristic to pick the closest node to dive on + int i; + float nearest[3]; + + if(data->proj[ node->main_axis ] <= node->children[0]->bv[node->main_axis*2+1]) + { + + for(i=0; i != node->totnode; i++) + { + if( calc_nearest_point(data, node->children[i], nearest) >= data->nearest.dist) continue; + dfs_find_nearest_dfs(data, node->children[i]); + } + } + else + { + for(i=node->totnode-1; i >= 0 ; i--) + { + if( calc_nearest_point(data, node->children[i], nearest) >= data->nearest.dist) continue; + dfs_find_nearest_dfs(data, node->children[i]); + } + } + } +} + +static void dfs_find_nearest_begin(BVHNearestData *data, BVHNode *node) +{ + float nearest[3], sdist; + sdist = calc_nearest_point(data, node, nearest); + if(sdist >= data->nearest.dist) return; + dfs_find_nearest_dfs(data, node); +} + + +static void NodeDistance_push_heap(NodeDistance *heap, int heap_size) +PUSH_HEAP_BODY(NodeDistance, NodeDistance_priority, heap, heap_size) + +static void NodeDistance_pop_heap(NodeDistance *heap, int heap_size) +POP_HEAP_BODY(NodeDistance, NodeDistance_priority, heap, heap_size) + +//NN function that uses an heap.. this functions leads to an optimal number of min-distance +//but for normal tri-faces and BV 6-dop.. a simple dfs with local heuristics (as implemented +//in source/blender/blenkernel/intern/shrinkwrap.c) works faster. +// +//It may make sense to use this function if the callback queries are very slow.. or if its impossible +//to get a nice heuristic +// +//this function uses "malloc/free" instead of the MEM_* because it intends to be openmp safe +static void bfs_find_nearest(BVHNearestData *data, BVHNode *node) +{ + int i; + NodeDistance default_heap[DEFAULT_FIND_NEAREST_HEAP_SIZE]; + NodeDistance *heap=default_heap, current; + int heap_size = 0, max_heap_size = sizeof(default_heap)/sizeof(default_heap[0]); + float nearest[3]; + + int callbacks = 0, push_heaps = 0; + + if(node->totnode == 0) + { + dfs_find_nearest_dfs(data, node); + return; + } + + current.node = node; + current.dist = calc_nearest_point(data, node, nearest); + + while(current.dist < data->nearest.dist) + { +// printf("%f : %f\n", current.dist, data->nearest.dist); + for(i=0; i< current.node->totnode; i++) + { + BVHNode *child = current.node->children[i]; + if(child->totnode == 0) + { + callbacks++; + dfs_find_nearest_dfs(data, child); + } + else + { + //adjust heap size + if(heap_size >= max_heap_size + && ADJUST_MEMORY(default_heap, (void**)&heap, heap_size+1, &max_heap_size, sizeof(heap[0])) == FALSE) + { + printf("WARNING: bvh_find_nearest got out of memory\n"); + + if(heap != default_heap) + free(heap); + + return; + } + + heap[heap_size].node = current.node->children[i]; + heap[heap_size].dist = calc_nearest_point(data, current.node->children[i], nearest); + + if(heap[heap_size].dist >= data->nearest.dist) continue; + heap_size++; + + NodeDistance_push_heap(heap, heap_size); + // PUSH_HEAP_BODY(NodeDistance, NodeDistance_priority, heap, heap_size); + push_heaps++; + } + } + + if(heap_size == 0) break; + + current = heap[0]; + NodeDistance_pop_heap(heap, heap_size); +// POP_HEAP_BODY(NodeDistance, NodeDistance_priority, heap, heap_size); + heap_size--; + } + +// printf("hsize=%d, callbacks=%d, pushs=%d\n", heap_size, callbacks, push_heaps); + + if(heap != default_heap) + free(heap); +} + + +int BLI_bvhtree_find_nearest(BVHTree *tree, const float *co, BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata) +{ + int i; + + BVHNearestData data; + BVHNode* root = tree->nodes[tree->totleaf]; + + //init data to search + data.tree = tree; + data.co = co; + + data.callback = callback; + data.userdata = userdata; + + for(i = data.tree->start_axis; i != data.tree->stop_axis; i++) + { + data.proj[i] = INPR(data.co, KDOP_AXES[i]); + } + + if(nearest) + { + memcpy( &data.nearest , nearest, sizeof(*nearest) ); + } + else + { + data.nearest.index = -1; + data.nearest.dist = FLT_MAX; + } + + //dfs search + if(root) + dfs_find_nearest_begin(&data, root); + + //copy back results + if(nearest) + { + memcpy(nearest, &data.nearest, sizeof(*nearest)); + } + + return data.nearest.index; +} + + +/* + * Raycast - BLI_bvhtree_ray_cast + * + * raycast is done by performing a DFS on the BVHTree and saving the closest hit + */ + +//Determines the distance that the ray must travel to hit the bounding volume of the given node +static float ray_nearest_hit(BVHRayCastData *data, BVHNode *node) +{ + int i; + const float *bv = node->bv; + + float low = 0, upper = data->hit.dist; + + for(i=0; i != 3; i++, bv += 2) + { + if(data->ray_dot_axis[i] == 0.0f) + { + //axis aligned ray + if(data->ray.origin[i] < bv[0] - data->ray.radius + || data->ray.origin[i] > bv[1] + data->ray.radius) + return FLT_MAX; + } + else + { + float ll = (bv[0] - data->ray.radius - data->ray.origin[i]) / data->ray_dot_axis[i]; + float lu = (bv[1] + data->ray.radius - data->ray.origin[i]) / data->ray_dot_axis[i]; + + if(data->ray_dot_axis[i] > 0.0f) + { + if(ll > low) low = ll; + if(lu < upper) upper = lu; + } + else + { + if(lu > low) low = lu; + if(ll < upper) upper = ll; + } + + if(low > upper) return FLT_MAX; + } + } + return low; +} + +static void dfs_raycast(BVHRayCastData *data, BVHNode *node) +{ + int i; + + //ray-bv is really fast.. and simple tests revealed its worth to test it + //before calling the ray-primitive functions + float dist = ray_nearest_hit(data, node); + if(dist >= data->hit.dist) return; + + if(node->totnode == 0) + { + if(data->callback) + data->callback(data->userdata, node->index, &data->ray, &data->hit); + else + { + data->hit.index = node->index; + data->hit.dist = dist; + VECADDFAC(data->hit.co, data->ray.origin, data->ray.direction, dist); + } + } + else + { + //pick loop direction to dive into the tree (based on ray direction and split axis) + if(data->ray_dot_axis[ node->main_axis ] > 0.0f) + { + for(i=0; i != node->totnode; i++) + { + dfs_raycast(data, node->children[i]); + } + } + else + { + for(i=node->totnode-1; i >= 0; i--) + { + dfs_raycast(data, node->children[i]); + } + } + } +} + +int BLI_bvhtree_ray_cast(BVHTree *tree, const float *co, const float *dir, float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata) +{ + int i; + BVHRayCastData data; + BVHNode * root = tree->nodes[tree->totleaf]; + + data.tree = tree; + + data.callback = callback; + data.userdata = userdata; + + VECCOPY(data.ray.origin, co); + VECCOPY(data.ray.direction, dir); + data.ray.radius = radius; + + Normalize(data.ray.direction); + + for(i=0; i<3; i++) + { + data.ray_dot_axis[i] = INPR( data.ray.direction, KDOP_AXES[i]); + + if(fabs(data.ray_dot_axis[i]) < FLT_EPSILON) + data.ray_dot_axis[i] = 0.0; + } + + + if(hit) + memcpy( &data.hit, hit, sizeof(*hit) ); + else + { + data.hit.index = -1; + data.hit.dist = FLT_MAX; + } + + if(root) + dfs_raycast(&data, root); + + + if(hit) + memcpy( hit, &data.hit, sizeof(*hit) ); + + return data.hit.index; +} + diff --git a/source/blender/blenlib/intern/BLI_kdtree.c b/source/blender/blenlib/intern/BLI_kdtree.c index 03b7561bad5..8e8b2e9f0e9 100644 --- a/source/blender/blenlib/intern/BLI_kdtree.c +++ b/source/blender/blenlib/intern/BLI_kdtree.c @@ -163,11 +163,18 @@ int BLI_kdtree_find_nearest(KDTree *tree, float *co, float *nor, KDTreeNearest * min_node= root; min_dist= squared_distance(root->co,co,root->nor,nor); - if(root->left) - stack[cur++]=root->left; - - if(root->right) - stack[cur++]=root->right; + if(co[root->d] < root->co[root->d]) { + if(root->right) + stack[cur++]=root->right; + if(root->left) + stack[cur++]=root->left; + } + else { + if(root->left) + stack[cur++]=root->left; + if(root->right) + stack[cur++]=root->right; + } while(cur--){ node=stack[cur]; @@ -263,11 +270,18 @@ int BLI_kdtree_find_n_nearest(KDTree *tree, int n, float *co, float *nor, KDTree cur_dist= squared_distance(root->co,co,root->nor,nor); add_nearest(nearest,&found,n,root->index,cur_dist,root->co); - if(root->left) - stack[cur++]=root->left; - - if(root->right) - stack[cur++]=root->right; + if(co[root->d] < root->co[root->d]) { + if(root->right) + stack[cur++]=root->right; + if(root->left) + stack[cur++]=root->left; + } + else { + if(root->left) + stack[cur++]=root->left; + if(root->right) + stack[cur++]=root->right; + } while(cur--){ node=stack[cur]; diff --git a/source/blender/blenlib/intern/BLI_mempool.c b/source/blender/blenlib/intern/BLI_mempool.c new file mode 100644 index 00000000000..7ac7b8b1791 --- /dev/null +++ b/source/blender/blenlib/intern/BLI_mempool.c @@ -0,0 +1,140 @@ +/** + * + * ***** 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 ***** + */ + +/* + Simple, fast memory allocator for allocating many elements of the same size. +*/ + +#include "MEM_guardedalloc.h" +#include "BLI_blenlib.h" +#include "DNA_listBase.h" +#include "BLI_linklist.h" +#include <string.h> + +typedef struct BLI_freenode{ + struct BLI_freenode *next; +}BLI_freenode; + +typedef struct BLI_mempool_chunk{ + struct BLI_mempool_chunk *next, *prev; + void *data; +}BLI_mempool_chunk; + +typedef struct BLI_mempool{ + struct ListBase chunks; + int esize, csize, pchunk; /*size of elements and chunks in bytes and number of elements per chunk*/ + struct BLI_freenode *free; /*free element list. Interleaved into chunk datas.*/ +}BLI_mempool; + +BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk) +{ BLI_mempool *pool = NULL; + BLI_freenode *lasttail = NULL, *curnode = NULL; + int i,j, maxchunks; + char *addr; + + /*allocate the pool structure*/ + pool = MEM_mallocN(sizeof(BLI_mempool),"memory pool"); + pool->esize = esize; + pool->pchunk = pchunk; + pool->csize = esize * pchunk; + pool->chunks.first = pool->chunks.last = NULL; + + maxchunks = tote / pchunk; + + /*allocate the actual chunks*/ + for(i=0; i < maxchunks; i++){ + BLI_mempool_chunk *mpchunk = MEM_mallocN(sizeof(BLI_mempool_chunk), "BLI_Mempool Chunk"); + mpchunk->next = mpchunk->prev = NULL; + mpchunk->data = MEM_mallocN(pool->csize, "BLI Mempool Chunk Data"); + BLI_addtail(&(pool->chunks), mpchunk); + + if(i==0) pool->free = mpchunk->data; /*start of the list*/ + /*loop through the allocated data, building the pointer structures*/ + for(addr = mpchunk->data, j=0; j < pool->pchunk; j++){ + curnode = ((BLI_freenode*)addr); + addr += pool->esize; + curnode->next = (BLI_freenode*)addr; + } + /*final pointer in the previously allocated chunk is wrong.*/ + if(lasttail) lasttail->next = mpchunk->data; + /*set the end of this chunks memoryy to the new tail for next iteration*/ + lasttail = curnode; + } + /*terminate the list*/ + curnode->next = NULL; + return pool; +} +void *BLI_mempool_alloc(BLI_mempool *pool){ + void *retval=NULL; + BLI_freenode *curnode=NULL; + char *addr=NULL; + int j; + + if(!(pool->free)){ + /*need to allocate a new chunk*/ + BLI_mempool_chunk *mpchunk = MEM_mallocN(sizeof(BLI_mempool_chunk), "BLI_Mempool Chunk"); + mpchunk->next = mpchunk->prev = NULL; + mpchunk->data = MEM_mallocN(pool->csize, "BLI_Mempool Chunk Data"); + BLI_addtail(&(pool->chunks), mpchunk); + + pool->free = mpchunk->data; /*start of the list*/ + for(addr = mpchunk->data, j=0; j < pool->pchunk; j++){ + curnode = ((BLI_freenode*)addr); + addr += pool->esize; + curnode->next = (BLI_freenode*)addr; + } + curnode->next = NULL; /*terminate the list*/ + } + + retval = pool->free; + pool->free = pool->free->next; + //memset(retval, 0, pool->esize); + return retval; +} + +void *BLI_mempool_calloc(BLI_mempool *pool){ + void *retval=NULL; + retval = BLI_mempool_alloc(pool); + memset(retval, 0, pool->esize); + return retval; +} + + + +void BLI_mempool_free(BLI_mempool *pool, void *addr){ //doesnt protect against double frees, dont be stupid! + BLI_freenode *newhead = addr; + newhead->next = pool->free; + pool->free = newhead; +} +void BLI_mempool_destroy(BLI_mempool *pool) +{ + BLI_mempool_chunk *mpchunk=NULL; + for(mpchunk = pool->chunks.first; mpchunk; mpchunk = mpchunk->next) MEM_freeN(mpchunk->data); + BLI_freelistN(&(pool->chunks)); + MEM_freeN(pool); +} diff --git a/source/blender/blenlib/intern/BLI_storage.h b/source/blender/blenlib/intern/BLI_storage.h index 022a579fb66..3e0dec367da 100644 --- a/source/blender/blenlib/intern/BLI_storage.h +++ b/source/blender/blenlib/intern/BLI_storage.h @@ -28,6 +28,13 @@ #ifndef BLI_STORAGE_H #define BLI_STORAGE_H +#ifndef __APPLE__ +#ifndef WIN32 +#define _LARGEFILE_SOURCE 1 +#define _FILE_OFFSET_BITS 64 +#endif +#endif + #include "BLI_storage_types.h" void BLI_adddirstrings(void); diff --git a/source/blender/blenlib/intern/Makefile b/source/blender/blenlib/intern/Makefile index 8d6ca9b6dc3..f92fa0a7e25 100644 --- a/source/blender/blenlib/intern/Makefile +++ b/source/blender/blenlib/intern/Makefile @@ -56,3 +56,6 @@ endif ifeq ($(WITH_FREETYPE2), true) CPPFLAGS += -DWITH_FREETYPE2 endif +ifeq ($(OS),linux) + CPPFLAGS += -I$(OCGDIR)/extern/binreloc/include +endif diff --git a/source/blender/blenlib/intern/arithb.c b/source/blender/blenlib/intern/arithb.c index 735ff2e65f7..0f2226fc872 100644 --- a/source/blender/blenlib/intern/arithb.c +++ b/source/blender/blenlib/intern/arithb.c @@ -54,11 +54,13 @@ #include <stdio.h> #include "BLI_arithb.h" +#include "BLI_memarena.h" /* A few small defines. Keep'em local! */ #define SMALL_NUMBER 1.e-8 #define ABS(x) ((x) < 0 ? -(x) : (x)) #define SWAP(type, a, b) { type sw_ap; sw_ap=(a); (a)=(b); (b)=sw_ap; } +#define CLAMP(a, b, c) if((a)<(b)) (a)=(b); else if((a)>(c)) (a)=(c) #if defined(WIN32) || defined(__APPLE__) @@ -757,6 +759,28 @@ void Mat4MulSerie(float answ[][4], float m1[][4], } } +void Mat3BlendMat3(float out[][3], float dst[][3], float src[][3], float srcweight) +{ + float squat[4], dquat[4], fquat[4]; + float ssize[3], dsize[3], fsize[4]; + float rmat[3][3], smat[3][3]; + + Mat3ToQuat(dst, dquat); + Mat3ToSize(dst, dsize); + + Mat3ToQuat(src, squat); + Mat3ToSize(src, ssize); + + /* do blending */ + QuatInterpol(fquat, dquat, squat, srcweight); + VecLerpf(fsize, dsize, ssize, srcweight); + + /* compose new matrix */ + QuatToMat3(fquat, rmat); + SizeToMat3(fsize, smat); + Mat3MulMat3(out, rmat, smat); +} + void Mat4BlendMat4(float out[][4], float dst[][4], float src[][4], float srcweight) { float squat[4], dquat[4], fquat[4]; @@ -1002,6 +1026,19 @@ int FloatCompare( float *v1, float *v2, float limit) return 0; } +int FloatCompare4( float *v1, float *v2, float limit) +{ + + if( fabs(v1[0]-v2[0])<limit ) { + if( fabs(v1[1]-v2[1])<limit ) { + if( fabs(v1[2]-v2[2])<limit ) { + if( fabs(v1[3]-v2[3])<limit ) return 1; + } + } + } + return 0; +} + float FloatLerpf( float target, float origin, float fac) { return (fac*target) + (1.0f-fac)*origin; @@ -1334,9 +1371,36 @@ void NormalQuat(float *q) } } -float *vectoquat( float *vec, short axis, short upflag) +void RotationBetweenVectorsToQuat(float *q, float v1[3], float v2[3]) +{ + float axis[3]; + float angle; + + Crossf(axis, v1, v2); + + angle = NormalizedVecAngle2(v1, v2); + + AxisAngleToQuat(q, axis, angle); +} + +void AxisAngleToQuat(float *q, float *axis, float angle) +{ + float nor[3]; + float si; + + VecCopyf(nor, axis); + Normalize(nor); + + angle /= 2; + si = (float)sin(angle); + q[0] = (float)cos(angle); + q[1] = nor[0] * si; + q[2] = nor[1] * si; + q[3] = nor[2] * si; +} + +void vectoquat(float *vec, short axis, short upflag, float *q) { - static float q1[4]; float q2[4], nor[3], *fp, mat[3][3], angle, si, co, x2, y2, z2, len1; /* first rotate to axis */ @@ -1348,11 +1412,11 @@ float *vectoquat( float *vec, short axis, short upflag) x2= -vec[0] ; y2= -vec[1] ; z2= -vec[2]; } - q1[0]=1.0; - q1[1]=q1[2]=q1[3]= 0.0; + q[0]=1.0; + q[1]=q[2]=q[3]= 0.0; len1= (float)sqrt(x2*x2+y2*y2+z2*z2); - if(len1 == 0.0) return(q1); + if(len1 == 0.0) return; /* nasty! I need a good routine for this... * problem is a rotation of an Y axis to the negative Y-axis for example. @@ -1363,9 +1427,8 @@ float *vectoquat( float *vec, short axis, short upflag) nor[1]= -z2; nor[2]= y2; - if( fabs(y2)+fabs(z2)<0.0001 ) { + if(fabs(y2)+fabs(z2)<0.0001) nor[1]= 1.0; - } co= x2; } @@ -1374,9 +1437,8 @@ float *vectoquat( float *vec, short axis, short upflag) nor[1]= 0.0; nor[2]= -x2; - if( fabs(x2)+fabs(z2)<0.0001 ) { + if(fabs(x2)+fabs(z2)<0.0001) nor[2]= 1.0; - } co= y2; } @@ -1385,9 +1447,8 @@ float *vectoquat( float *vec, short axis, short upflag) nor[1]= x2; nor[2]= 0.0; - if( fabs(x2)+fabs(y2)<0.0001 ) { + if(fabs(x2)+fabs(y2)<0.0001) nor[0]= 1.0; - } co= z2; } @@ -1397,13 +1458,13 @@ float *vectoquat( float *vec, short axis, short upflag) angle= 0.5f*saacos(co); si= (float)sin(angle); - q1[0]= (float)cos(angle); - q1[1]= nor[0]*si; - q1[2]= nor[1]*si; - q1[3]= nor[2]*si; + q[0]= (float)cos(angle); + q[1]= nor[0]*si; + q[2]= nor[1]*si; + q[3]= nor[2]*si; if(axis!=upflag) { - QuatToMat3(q1, mat); + QuatToMat3(q, mat); fp= mat[2]; if(axis==0) { @@ -1426,10 +1487,8 @@ float *vectoquat( float *vec, short axis, short upflag) q2[2]= y2*si; q2[3]= z2*si; - QuatMul(q1,q2,q1); + QuatMul(q,q2,q); } - - return(q1); } void VecUpMat3old( float *vec, float mat[][3], short axis) @@ -1729,9 +1788,13 @@ void DQuatToMat4(DualQuat *dq, float mat[][4]) void DQuatAddWeighted(DualQuat *dqsum, DualQuat *dq, float weight) { + int flipped= 0; + /* make sure we interpolate quats in the right direction */ - if (QuatDot(dq->quat, dqsum->quat) < 0) - weight = -weight; + if (QuatDot(dq->quat, dqsum->quat) < 0) { + flipped= 1; + weight= -weight; + } /* interpolate rotation and translation */ dqsum->quat[0] += weight*dq->quat[0]; @@ -1748,6 +1811,9 @@ void DQuatAddWeighted(DualQuat *dqsum, DualQuat *dq, float weight) if (dq->scale_weight) { float wmat[4][4]; + if(flipped) /* we don't want negative weights for scaling */ + weight= -weight; + Mat4CpyMat4(wmat, dq->scale); Mat4MulFloat((float*)wmat, weight); Mat4AddMat4(dqsum->scale, dqsum->scale, wmat); @@ -2094,6 +2160,14 @@ void VecLerpf(float *target, float *a, float *b, float t) target[2]= s*a[2] + t*b[2]; } +void Vec2Lerpf(float *target, float *a, float *b, float t) +{ + float s = 1.0f-t; + + target[0]= s*a[0] + t*b[0]; + target[1]= s*a[1] + t*b[1]; +} + void VecMidf(float *v, float *v1, float *v2) { v[0]= 0.5f*(v1[0]+ v2[0]); @@ -2111,8 +2185,9 @@ void VecMulf(float *v1, float f) void VecOrthoBasisf(float *v, float *v1, float *v2) { - if (v[0] == 0.0f && v[1] == 0.0f) - { + float f = sqrt(v[0]*v[0] + v[1]*v[1]); + + if (f < 1e-35f) { // degenerate case v1[0] = 0.0f; v1[1] = 1.0f; v1[2] = 0.0f; if (v[2] > 0.0f) { @@ -2122,9 +2197,8 @@ void VecOrthoBasisf(float *v, float *v1, float *v2) v2[0] = -1.0f; v2[1] = v2[2] = 0.0f; } } - else - { - float f = 1.0f/sqrt(v[0]*v[0] + v[1]*v[1]); + else { + f = 1.0f/f; v1[0] = v[1]*f; v1[1] = -v[0]*f; v1[2] = 0.0f; @@ -2157,6 +2231,11 @@ int VecEqual(float *v1, float *v2) return ((v1[0]==v2[0]) && (v1[1]==v2[1]) && (v1[2]==v2[2])); } +int VecIsNull(float *v) +{ + return (v[0] == 0 && v[1] == 0 && v[2] == 0); +} + void CalcNormShort( short *v1, short *v2, short *v3, float *n) /* is also cross product */ { float n1[3],n2[3]; @@ -2256,6 +2335,20 @@ double Sqrt3d(double d) else return exp(log(d)/3); } +void NormalShortToFloat(float *out, short *in) +{ + out[0] = in[0] / 32767.0; + out[1] = in[1] / 32767.0; + out[2] = in[2] / 32767.0; +} + +void NormalFloatToShort(short *out, float *in) +{ + out[0] = (short)(in[0] * 32767.0); + out[1] = (short)(in[1] * 32767.0); + out[2] = (short)(in[2] * 32767.0); +} + /* distance v1 to line v2-v3 */ /* using Hesse formula, NO LINE PIECE! */ float DistVL2Dfl( float *v1, float *v2, float *v3) { @@ -2427,7 +2520,7 @@ short IsectLL2Df(float *v1, float *v2, float *v3, float *v4) 1: intersection */ -short IsectLLPt2Df(float x0,float y0,float x1,float y1, +static short IsectLLPt2Df(float x0,float y0,float x1,float y1, float x2,float y2,float x3,float y3, float *xi,float *yi) { @@ -2477,37 +2570,50 @@ short IsectLLPt2Df(float x0,float y0,float x1,float y1, } // end Intersect_Lines #define SIDE_OF_LINE(pa,pb,pp) ((pa[0]-pp[0])*(pb[1]-pp[1]))-((pb[0]-pp[0])*(pa[1]-pp[1])) -#define ISECT_EPSILON 1e-6 - /* point in tri */ int IsectPT2Df(float pt[2], float v1[2], float v2[2], float v3[2]) { - if ((SIDE_OF_LINE(v1,v2,pt)>=-ISECT_EPSILON) && - (SIDE_OF_LINE(v2,v3,pt)>=-ISECT_EPSILON) && - (SIDE_OF_LINE(v3,v1,pt)>=-ISECT_EPSILON)) - return 1; - else { - return 0; + if (SIDE_OF_LINE(v1,v2,pt)>=0.0) { + if (SIDE_OF_LINE(v2,v3,pt)>=0.0) { + if (SIDE_OF_LINE(v3,v1,pt)>=0.0) { + return 1; + } + } + } else { + if (! (SIDE_OF_LINE(v2,v3,pt)>=0.0) ) { + if (! (SIDE_OF_LINE(v3,v1,pt)>=0.0)) { + return -1; + } + } } + + return 0; } /* point in quad - only convex quads */ int IsectPQ2Df(float pt[2], float v1[2], float v2[2], float v3[2], float v4[2]) { - if ((SIDE_OF_LINE(v1,v2,pt)>=-ISECT_EPSILON) && - (SIDE_OF_LINE(v2,v3,pt)>=-ISECT_EPSILON) && - (SIDE_OF_LINE(v3,v4,pt)>=-ISECT_EPSILON) && - (SIDE_OF_LINE(v4,v1,pt)>=-ISECT_EPSILON)) - return 1; - else - return 0; + if (SIDE_OF_LINE(v1,v2,pt)>=0.0) { + if (SIDE_OF_LINE(v2,v3,pt)>=0.0) { + if (SIDE_OF_LINE(v3,v4,pt)>=0.0) { + if (SIDE_OF_LINE(v4,v1,pt)>=0.0) { + return 1; + } + } + } + } else { + if (! (SIDE_OF_LINE(v2,v3,pt)>=0.0) ) { + if (! (SIDE_OF_LINE(v3,v4,pt)>=0.0)) { + if (! (SIDE_OF_LINE(v4,v1,pt)>=0.0)) { + return -1; + } + } + } + } + + return 0; } - - /* copied from Geometry.c - todo - move to arithb.c or some other generic place we can reuse */ -#define SIDE_OF_LINE(pa,pb,pp) ((pa[0]-pp[0])*(pb[1]-pp[1]))-((pb[0]-pp[0])*(pa[1]-pp[1])) -#define POINT_IN_TRI(p0,p1,p2,p3) ((SIDE_OF_LINE(p1,p2,p0)>=0) && (SIDE_OF_LINE(p2,p3,p0)>=0) && (SIDE_OF_LINE(p3,p1,p0)>=0)) - /** * * @param min @@ -2871,6 +2977,22 @@ float VecAngle3(float *v1, float *v2, float *v3) return NormalizedVecAngle2(vec1, vec2) * 180.0/M_PI; } +float VecAngle3_2D(float *v1, float *v2, float *v3) +{ + float vec1[2], vec2[2]; + + vec1[0] = v2[0]-v1[0]; + vec1[1] = v2[1]-v1[1]; + + vec2[0] = v2[0]-v3[0]; + vec2[1] = v2[1]-v3[1]; + + Normalize2(vec1); + Normalize2(vec2); + + return NormalizedVecAngle2_2D(vec1, vec2) * 180.0/M_PI; +} + /* Return the shortest angle in degrees between the 2 vectors */ float VecAngle2(float *v1, float *v2) { @@ -2900,6 +3022,21 @@ float NormalizedVecAngle2(float *v1, float *v2) return 2.0f*saasin(VecLenf(v2, v1)/2.0); } +float NormalizedVecAngle2_2D(float *v1, float *v2) +{ + /* this is the same as acos(Inpf(v1, v2)), but more accurate */ + if (Inp2f(v1, v2) < 0.0f) { + float vec[2]; + + vec[0]= -v2[0]; + vec[1]= -v2[1]; + + return (float)M_PI - 2.0f*saasin(Vec2Lenf(vec, v1)/2.0f); + } + else + return 2.0f*saasin(Vec2Lenf(v2, v1)/2.0); +} + void euler_rot(float *beul, float ang, char axis) { float eul[3], mat1[3][3], mat2[3][3], totmat[3][3]; @@ -3351,6 +3488,80 @@ void rgb_to_hsv(float r, float g, float b, float *lh, float *ls, float *lv) *lv = v; } +/*http://brucelindbloom.com/index.html?Eqn_RGB_XYZ_Matrix.html */ + +void xyz_to_rgb(float xc, float yc, float zc, float *r, float *g, float *b, int colorspace) +{ + switch (colorspace) { + case BLI_CS_SMPTE: + *r = (3.50570 * xc) + (-1.73964 * yc) + (-0.544011 * zc); + *g = (-1.06906 * xc) + (1.97781 * yc) + (0.0351720 * zc); + *b = (0.0563117 * xc) + (-0.196994 * yc) + (1.05005 * zc); + break; + case BLI_CS_REC709: + *r = (3.240476 * xc) + (-1.537150 * yc) + (-0.498535 * zc); + *g = (-0.969256 * xc) + (1.875992 * yc) + (0.041556 * zc); + *b = (0.055648 * xc) + (-0.204043 * yc) + (1.057311 * zc); + break; + case BLI_CS_CIE: + *r = (2.28783848734076f * xc) + (-0.833367677835217f * yc) + (-0.454470795871421f * zc); + *g = (-0.511651380743862f * xc) + (1.42275837632178f * yc) + (0.0888930017552939f * zc); + *b = (0.00572040983140966f * xc) + (-0.0159068485104036f * yc) + (1.0101864083734f * zc); + break; + } +} + +/*If the requested RGB shade contains a negative weight for + one of the primaries, it lies outside the colour gamut + accessible from the given triple of primaries. Desaturate + it by adding white, equal quantities of R, G, and B, enough + to make RGB all positive. The function returns 1 if the + components were modified, zero otherwise.*/ +int constrain_rgb(float *r, float *g, float *b) +{ + float w; + + /* Amount of white needed is w = - min(0, *r, *g, *b) */ + + w = (0 < *r) ? 0 : *r; + w = (w < *g) ? w : *g; + w = (w < *b) ? w : *b; + w = -w; + + /* Add just enough white to make r, g, b all positive. */ + + if (w > 0) { + *r += w; *g += w; *b += w; + return 1; /* Colour modified to fit RGB gamut */ + } + + return 0; /* Colour within RGB gamut */ +} + +/*Transform linear RGB values to nonlinear RGB values. Rec. + 709 is ITU-R Recommendation BT. 709 (1990) ``Basic + Parameter Values for the HDTV Standard for the Studio and + for International Programme Exchange'', formerly CCIR Rec. + 709.*/ +static void gamma_correct(float *c) +{ + /* Rec. 709 gamma correction. */ + float cc = 0.018; + + if (*c < cc) { + *c *= ((1.099 * pow(cc, 0.45)) - 0.099) / cc; + } else { + *c = (1.099 * pow(*c, 0.45)) - 0.099; + } +} + +void gamma_correct_rgb(float *r, float *g, float *b) +{ + gamma_correct(r); + gamma_correct(g); + gamma_correct(b); +} + /* we define a 'cpack' here as a (3 byte color code) number that can be expressed like 0xFFAA66 or so. for that reason it is sensitive for endianness... with this function it works correctly @@ -3412,6 +3623,8 @@ void tubemap(float x, float y, float z, float *u, float *v) len= sqrt(x*x+y*y); if(len>0) { *u = (1.0 - (atan2(x/len,y/len) / M_PI)) / 2.0; + } else { + *v = *u = 0.0f; /* to avoid un-initialized variables */ } } @@ -3429,11 +3642,15 @@ void spheremap(float x, float y, float z, float *u, float *v) z/=len; *v = 1.0- saacos(z)/M_PI; + } else { + *v = *u = 0.0f; /* to avoid un-initialized variables */ } } /* ------------------------------------------------------------------------- */ +/* proposed api by ton and zr, not used yet */ +#if 0 /* ***************** m1 = m2 ***************** */ void cpy_m3_m3(float m1[][3], float m2[][3]) { @@ -3457,7 +3674,6 @@ void ident_m4(float m[][4]) m[3][0]= m[3][1]= m[3][2]= 0.0; } - /* ***************** m1 = m2 (pre) * m3 (post) ***************** */ void mul_m3_m3m3(float m1[][3], float m2[][3], float m3[][3]) { @@ -3595,6 +3811,8 @@ void mul_v3_v3m4(float *v1, float *v2, float mat[][4]) } +#endif + /* moved from effect.c test if the line starting at p1 ending at p2 intersects the triangle v0..v2 return non zero if it does @@ -3634,14 +3852,89 @@ int LineIntersectsTriangle(float p1[3], float p2[3], float v0[3], float v1[3], f return 1; } +/* moved from effect.c + test if the ray starting at p1 going in d direction intersects the triangle v0..v2 + return non zero if it does +*/ +int RayIntersectsTriangle(float p1[3], float d[3], float v0[3], float v1[3], float v2[3], float *lambda, float *uv) +{ + float p[3], s[3], e1[3], e2[3], q[3]; + float a, f, u, v; + + VecSubf(e1, v1, v0); + VecSubf(e2, v2, v0); + + Crossf(p, d, e2); + a = Inpf(e1, p); + if ((a > -0.000001) && (a < 0.000001)) return 0; + f = 1.0f/a; + + VecSubf(s, p1, v0); + + Crossf(q, s, e1); + *lambda = f * Inpf(e2, q); + if ((*lambda < 0.0)) return 0; + + u = f * Inpf(s, p); + if ((u < 0.0)||(u > 1.0)) return 0; + + v = f * Inpf(d, q); + if ((v < 0.0)||((u + v) > 1.0)) return 0; + + if(uv) { + uv[0]= u; + uv[1]= v; + } + + return 1; +} + /* Adapted from the paper by Kasper Fauerby */ /* "Improved Collision detection and Response" */ +static int getLowestRoot(float a, float b, float c, float maxR, float* root) +{ + // Check if a solution exists + float determinant = b*b - 4.0f*a*c; + + // If determinant is negative it means no solutions. + if (determinant >= 0.0f) + { + // calculate the two roots: (if determinant == 0 then + // x1==x2 but let’s disregard that slight optimization) + float sqrtD = sqrt(determinant); + float r1 = (-b - sqrtD) / (2.0f*a); + float r2 = (-b + sqrtD) / (2.0f*a); + + // Sort so x1 <= x2 + if (r1 > r2) + SWAP( float, r1, r2); + + // Get lowest root: + if (r1 > 0.0f && r1 < maxR) + { + *root = r1; + return 1; + } + + // It is possible that we want x2 - this can happen + // if x1 < 0 + if (r2 > 0.0f && r2 < maxR) + { + *root = r2; + return 1; + } + } + // No (valid) solutions + return 0; +} + int SweepingSphereIntersectsTriangleUV(float p1[3], float p2[3], float radius, float v0[3], float v1[3], float v2[3], float *lambda, float *ipoint) { float e1[3], e2[3], e3[3], point[3], vel[3], /*dist[3],*/ nor[3], temp[3], bv[3]; - float a, b, c, d, e, x, y, z, t, t0, t1, radius2=radius*radius; + float a, b, c, d, e, x, y, z, radius2=radius*radius; float elen2,edotv,edotbv,nordotv,vel2; - int embedded_in_plane=0, found_by_sweep=0; + float newLambda; + int found_by_sweep=0; VecSubf(e1,v1,v0); VecSubf(e2,v2,v0); @@ -3650,44 +3943,41 @@ int SweepingSphereIntersectsTriangleUV(float p1[3], float p2[3], float radius, f /*---test plane of tri---*/ Crossf(nor,e1,e2); Normalize(nor); + /* flip normal */ if(Inpf(nor,vel)>0.0f) VecMulf(nor,-1.0f); a=Inpf(p1,nor)-Inpf(v0,nor); - nordotv=Inpf(nor,vel); - if ((nordotv > -0.000001) && (nordotv < 0.000001)) { - if(fabs(a)>=1.0f) + if (fabs(nordotv) < 0.000001) + { + if(fabs(a)>=radius) + { return 0; - else{ - embedded_in_plane=1; - t0=0.0f; - t1=1.0f; } } - else{ - t0=(radius-a)/nordotv; - t1=(-radius-a)/nordotv; - /* make t0<t1 */ - if(t0>t1){b=t1; t1=t0; t0=b;} + else + { + float t0=(-a+radius)/nordotv; + float t1=(-a-radius)/nordotv; + + if(t0>t1) + SWAP(float, t0, t1); if(t0>1.0f || t1<0.0f) return 0; /* clamp to [0,1] */ - t0=(t0<0.0f)?0.0f:((t0>1.0f)?1.0:t0); - t1=(t1<0.0f)?0.0f:((t1>1.0f)?1.0:t1); - } + CLAMP(t0, 0.0f, 1.0f); + CLAMP(t1, 0.0f, 1.0f); -/*---test inside of tri---*/ - if(embedded_in_plane==0){ + /*---test inside of tri---*/ /* plane intersection point */ - VecCopyf(point,vel); - VecMulf(point,t0); - VecAddf(point,point,p1); - VecCopyf(temp,nor); - VecMulf(temp,radius); - VecSubf(point,point,temp); + + point[0] = p1[0] + vel[0]*t0 - nor[0]*radius; + point[1] = p1[1] + vel[1]*t0 - nor[1]*radius; + point[2] = p1[2] + vel[2]*t0 - nor[2]*radius; + /* is the point in the tri? */ a=Inpf(e1,e1); @@ -3702,14 +3992,19 @@ int SweepingSphereIntersectsTriangleUV(float p1[3], float p2[3], float radius, f y=e*a-d*b; z=x+y-(a*c-b*b); - if(( ((unsigned int)z)& ~(((unsigned int)x)|((unsigned int)y)) ) & 0x80000000){ + + if( z <= 0.0f && (x >= 0.0f && y >= 0.0f)) + { + //( ((unsigned int)z)& ~(((unsigned int)x)|((unsigned int)y)) ) & 0x80000000){ *lambda=t0; VecCopyf(ipoint,point); return 1; } } + *lambda=1.0f; + /*---test points---*/ a=vel2=Inpf(vel,vel); @@ -3717,73 +4012,42 @@ int SweepingSphereIntersectsTriangleUV(float p1[3], float p2[3], float radius, f VecSubf(temp,p1,v0); b=2.0f*Inpf(vel,temp); c=Inpf(temp,temp)-radius2; - d=b*b-4*a*c; - - if(d>=0.0f){ - if(d==0.0f) - t=-b/2*a; - else{ - z=sqrt(d); - x=(-b-z)*0.5/a; - y=(-b+z)*0.5/a; - t=x<y?x:y; - } - if(t>0.0 && t < *lambda){ - *lambda=t; - VecCopyf(ipoint,v0); - found_by_sweep=1; - } + if(getLowestRoot(a, b, c, *lambda, lambda)) + { + VecCopyf(ipoint,v0); + found_by_sweep=1; } /*v1*/ VecSubf(temp,p1,v1); b=2.0f*Inpf(vel,temp); c=Inpf(temp,temp)-radius2; - d=b*b-4*a*c; - - if(d>=0.0f){ - if(d==0.0f) - t=-b/2*a; - else{ - z=sqrt(d); - x=(-b-z)*0.5/a; - y=(-b+z)*0.5/a; - t=x<y?x:y; - } - if(t>0.0 && t < *lambda){ - *lambda=t; - VecCopyf(ipoint,v1); - found_by_sweep=1; - } + if(getLowestRoot(a, b, c, *lambda, lambda)) + { + VecCopyf(ipoint,v1); + found_by_sweep=1; } + /*v2*/ VecSubf(temp,p1,v2); b=2.0f*Inpf(vel,temp); c=Inpf(temp,temp)-radius2; - d=b*b-4*a*c; - - if(d>=0.0f){ - if(d==0.0f) - t=-b/2*a; - else{ - z=sqrt(d); - x=(-b-z)*0.5/a; - y=(-b+z)*0.5/a; - t=x<y?x:y; - } - if(t>0.0 && t < *lambda){ - *lambda=t; - VecCopyf(ipoint,v2); - found_by_sweep=1; - } + if(getLowestRoot(a, b, c, *lambda, lambda)) + { + VecCopyf(ipoint,v2); + found_by_sweep=1; } /*---test edges---*/ + VecSubf(e3,v2,v1); //wasnt yet calculated + + /*e1*/ VecSubf(bv,v0,p1); + elen2 = Inpf(e1,e1); edotv = Inpf(e1,vel); edotbv = Inpf(e1,bv); @@ -3791,27 +4055,18 @@ int SweepingSphereIntersectsTriangleUV(float p1[3], float p2[3], float radius, f a=elen2*(-Inpf(vel,vel))+edotv*edotv; b=2.0f*(elen2*Inpf(vel,bv)-edotv*edotbv); c=elen2*(radius2-Inpf(bv,bv))+edotbv*edotbv; - d=b*b-4*a*c; - if(d>=0.0f){ - if(d==0.0f) - t=-b/2*a; - else{ - z=sqrt(d); - x=(-b-z)*0.5/a; - y=(-b+z)*0.5/a; - t=x<y?x:y; - } - - e=(edotv*t-edotbv)/elen2; - if((e>=0.0f) && (e<=1.0f)){ - if(t>0.0 && t < *lambda){ - *lambda=t; - VecCopyf(ipoint,e1); - VecMulf(ipoint,e); - VecAddf(ipoint,ipoint,v0); - found_by_sweep=1; - } + if(getLowestRoot(a, b, c, *lambda, &newLambda)) + { + e=(edotv*newLambda-edotbv)/elen2; + + if(e >= 0.0f && e <= 1.0f) + { + *lambda = newLambda; + VecCopyf(ipoint,e1); + VecMulf(ipoint,e); + VecAddf(ipoint,ipoint,v0); + found_by_sweep=1; } } @@ -3824,32 +4079,27 @@ int SweepingSphereIntersectsTriangleUV(float p1[3], float p2[3], float radius, f a=elen2*(-Inpf(vel,vel))+edotv*edotv; b=2.0f*(elen2*Inpf(vel,bv)-edotv*edotbv); c=elen2*(radius2-Inpf(bv,bv))+edotbv*edotbv; - d=b*b-4*a*c; - if(d>=0.0f){ - if(d==0.0f) - t=-b/2*a; - else{ - z=sqrt(d); - x=(-b-z)*0.5/a; - y=(-b+z)*0.5/a; - t=x<y?x:y; - } - e=(edotv*t-edotbv)/elen2; - - if((e>=0.0f) && (e<=1.0f)){ - if(t>0.0 && t < *lambda){ - *lambda=t; - VecCopyf(ipoint,e2); - VecMulf(ipoint,e); - VecAddf(ipoint,ipoint,v0); - found_by_sweep=1; - } + if(getLowestRoot(a, b, c, *lambda, &newLambda)) + { + e=(edotv*newLambda-edotbv)/elen2; + + if(e >= 0.0f && e <= 1.0f) + { + *lambda = newLambda; + VecCopyf(ipoint,e2); + VecMulf(ipoint,e); + VecAddf(ipoint,ipoint,v0); + found_by_sweep=1; } } /*e3*/ - VecSubf(e3,v2,v1); + VecSubf(bv,v0,p1); + elen2 = Inpf(e1,e1); + edotv = Inpf(e1,vel); + edotbv = Inpf(e1,bv); + VecSubf(bv,v1,p1); elen2 = Inpf(e3,e3); edotv = Inpf(e3,vel); @@ -3858,30 +4108,22 @@ int SweepingSphereIntersectsTriangleUV(float p1[3], float p2[3], float radius, f a=elen2*(-Inpf(vel,vel))+edotv*edotv; b=2.0f*(elen2*Inpf(vel,bv)-edotv*edotbv); c=elen2*(radius2-Inpf(bv,bv))+edotbv*edotbv; - d=b*b-4*a*c; - if(d>=0.0f){ - if(d==0.0f) - t=-b/2*a; - else{ - z=sqrt(d); - x=(-b-z)*0.5/a; - y=(-b+z)*0.5/a; - t=x<y?x:y; - } - e=(edotv*t-edotbv)/elen2; - - if((e>=0.0f) && (e<=1.0f)){ - if(t>0.0 && t < *lambda){ - *lambda=t; - VecCopyf(ipoint,e3); - VecMulf(ipoint,e); - VecAddf(ipoint,ipoint,v1); - found_by_sweep=1; - } + if(getLowestRoot(a, b, c, *lambda, &newLambda)) + { + e=(edotv*newLambda-edotbv)/elen2; + + if(e >= 0.0f && e <= 1.0f) + { + *lambda = newLambda; + VecCopyf(ipoint,e3); + VecMulf(ipoint,e); + VecAddf(ipoint,ipoint,v1); + found_by_sweep=1; } } + return found_by_sweep; } int AxialLineIntersectsTriangle(int axis, float p1[3], float p2[3], float v0[3], float v1[3], float v2[3], float *lambda) @@ -3928,6 +4170,74 @@ int AxialLineIntersectsTriangle(int axis, float p1[3], float p2[3], float v0[3], return 1; } +/* Returns the number of point of interests + * 0 - lines are colinear + * 1 - lines are coplanar, i1 is set to intersection + * 2 - i1 and i2 are the nearest points on line 1 (v1, v2) and line 2 (v3, v4) respectively + * */ +int LineIntersectLine(float v1[3], float v2[3], float v3[3], float v4[3], float i1[3], float i2[3]) +{ + float a[3], b[3], c[3], ab[3], cb[3], dir1[3], dir2[3]; + float d; + + VecSubf(c, v3, v1); + VecSubf(a, v2, v1); + VecSubf(b, v4, v3); + + VecCopyf(dir1, a); + Normalize(dir1); + VecCopyf(dir2, b); + Normalize(dir2); + d = Inpf(dir1, dir2); + if (d == 1.0f || d == -1.0f) { + /* colinear */ + return 0; + } + + Crossf(ab, a, b); + d = Inpf(c, ab); + + /* test if the two lines are coplanar */ + if (d > -0.000001f && d < 0.000001f) { + Crossf(cb, c, b); + + VecMulf(a, Inpf(cb, ab) / Inpf(ab, ab)); + VecAddf(i1, v1, a); + VecCopyf(i2, i1); + + return 1; /* one intersection only */ + } + /* if not */ + else { + float n[3], t[3]; + float v3t[3], v4t[3]; + VecSubf(t, v1, v3); + + /* offset between both plane where the lines lies */ + Crossf(n, a, b); + Projf(t, t, n); + + /* for the first line, offset the second line until it is coplanar */ + VecAddf(v3t, v3, t); + VecAddf(v4t, v4, t); + + VecSubf(c, v3t, v1); + VecSubf(a, v2, v1); + VecSubf(b, v4t, v3); + + Crossf(ab, a, b); + Crossf(cb, c, b); + + VecMulf(a, Inpf(cb, ab) / Inpf(ab, ab)); + VecAddf(i1, v1, a); + + /* for the second line, just substract the offset from the first intersection point */ + VecSubf(i2, i1, t); + + return 2; /* two nearest points */ + } +} + int AabbIntersectAabb(float min1[3], float max1[3], float min2[3], float max2[3]) { return (min1[0]<max2[0] && min1[1]<max2[1] && min1[2]<max2[2] && @@ -3950,7 +4260,7 @@ float lambda_cp_line_ex(float p[3], float l1[3], float l2[3], float cp[3]) } /* little sister we only need to know lambda */ -float lambda_cp_line(float p[3], float l1[3], float l2[3]) +static float lambda_cp_line(float p[3], float l1[3], float l2[3]) { float h[3],u[3]; VecSubf(u, l2, l1); @@ -4166,7 +4476,7 @@ void VecfCubicInterpol(float *x1, float *v1, float *x2, float *v2, float t, floa v[2]= 3*a[2]*t2 + 2*b[2]*t + v1[2]; } -int point_in_slice(float p[3], float v1[3], float l1[3], float l2[3]) +static int point_in_slice(float p[3], float v1[3], float l1[3], float l2[3]) { /* what is a slice ? @@ -4193,7 +4503,7 @@ but see a 'spat' which is a deformed cube with paired parallel planes needs only /*adult sister defining the slice planes by the origin and the normal NOTE |normal| may not be 1 but defining the thickness of the slice*/ -int point_in_slice_as(float p[3],float origin[3],float normal[3]) +static int point_in_slice_as(float p[3],float origin[3],float normal[3]) { float h,rp[3]; VecSubf(rp,p,origin); @@ -4203,7 +4513,7 @@ int point_in_slice_as(float p[3],float origin[3],float normal[3]) } /*mama (knowing the squared lenght of the normal)*/ -int point_in_slice_m(float p[3],float origin[3],float normal[3],float lns) +static int point_in_slice_m(float p[3],float origin[3],float normal[3],float lns) { float h,rp[3]; VecSubf(rp,p,origin); @@ -4293,3 +4603,80 @@ void LocQuatSizeToMat4(float mat[][4], float loc[3], float quat[4], float size[3 mat[3][1] = loc[1]; mat[3][2] = loc[2]; } + +/* Tangents */ + +/* For normal map tangents we need to detect uv boundaries, and only average + * tangents in case the uvs are connected. Alternative would be to store 1 + * tangent per face rather than 4 per face vertex, but that's not compatible + * with games */ + + +/* from BKE_mesh.h */ +#define STD_UV_CONNECT_LIMIT 0.0001f + +void sum_or_add_vertex_tangent(void *arena, VertexTangent **vtang, float *tang, float *uv) +{ + VertexTangent *vt; + + /* find a tangent with connected uvs */ + for(vt= *vtang; vt; vt=vt->next) { + if(fabs(uv[0]-vt->uv[0]) < STD_UV_CONNECT_LIMIT && fabs(uv[1]-vt->uv[1]) < STD_UV_CONNECT_LIMIT) { + VecAddf(vt->tang, vt->tang, tang); + return; + } + } + + /* if not found, append a new one */ + vt= BLI_memarena_alloc((MemArena *)arena, sizeof(VertexTangent)); + VecCopyf(vt->tang, tang); + vt->uv[0]= uv[0]; + vt->uv[1]= uv[1]; + + if(*vtang) + vt->next= *vtang; + *vtang= vt; +} + +float *find_vertex_tangent(VertexTangent *vtang, float *uv) +{ + VertexTangent *vt; + static float nulltang[3] = {0.0f, 0.0f, 0.0f}; + + for(vt= vtang; vt; vt=vt->next) + if(fabs(uv[0]-vt->uv[0]) < STD_UV_CONNECT_LIMIT && fabs(uv[1]-vt->uv[1]) < STD_UV_CONNECT_LIMIT) + return vt->tang; + + return nulltang; /* shouldn't happen, except for nan or so */ +} + +void tangent_from_uv(float *uv1, float *uv2, float *uv3, float *co1, float *co2, float *co3, float *n, float *tang) +{ + float tangv[3], ct[3], e1[3], e2[3], s1, t1, s2, t2, det; + + s1= uv2[0] - uv1[0]; + s2= uv3[0] - uv1[0]; + t1= uv2[1] - uv1[1]; + t2= uv3[1] - uv1[1]; + det= 1.0f / (s1 * t2 - s2 * t1); + + /* normals in render are inversed... */ + VecSubf(e1, co1, co2); + VecSubf(e2, co1, co3); + tang[0] = (t2*e1[0] - t1*e2[0])*det; + tang[1] = (t2*e1[1] - t1*e2[1])*det; + tang[2] = (t2*e1[2] - t1*e2[2])*det; + tangv[0] = (s1*e2[0] - s2*e1[0])*det; + tangv[1] = (s1*e2[1] - s2*e1[1])*det; + tangv[2] = (s1*e2[2] - s2*e1[2])*det; + Crossf(ct, tang, tangv); + + /* check flip */ + if ((ct[0]*n[0] + ct[1]*n[1] + ct[2]*n[2]) < 0.0f) + VecMulf(tang, -1.0f); +} + +/* used for zoom values*/ +float power_of_2(float val) { + return pow(2, ceil(log(val) / log(2))); +} diff --git a/source/blender/blenlib/intern/boxpack2d.c b/source/blender/blenlib/intern/boxpack2d.c index 21810613c7f..db7bae8a91d 100644 --- a/source/blender/blenlib/intern/boxpack2d.c +++ b/source/blender/blenlib/intern/boxpack2d.c @@ -42,6 +42,8 @@ #define TRF 2 #define TLF 4 #define BRF 8 +#define CORNERFLAGS (BLF|TRF|TLF|BRF) + #define BL 0 #define TR 1 #define TL 2 @@ -130,7 +132,7 @@ static int vertex_sort(const void *p1, const void *p2) * 'box->index' is not used at all, the only reason its there * is that the box array is sorted by area and programs need to be able * to have some way of writing the boxes back to the original data. - * len - the number of boxes in teh array. + * len - the number of boxes in the array. * tot_width and tot_height are set so you can normalize the data. * */ void boxPack2D(boxPack *boxarray, int len, float *tot_width, float *tot_height) @@ -159,7 +161,7 @@ void boxPack2D(boxPack *boxarray, int len, float *tot_width, float *tot_height) 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 = 15 &~ TRF; + vert->free = CORNERFLAGS &~ TRF; vert->trb = box; vert->index = i; i++; box->v[BL] = vert; vert++; @@ -167,7 +169,7 @@ void boxPack2D(boxPack *boxarray, int len, float *tot_width, float *tot_height) 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 = 15 &~ BLF; + vert->free = CORNERFLAGS &~ BLF; vert->blb = box; vert->index = i; i++; box->v[TR] = vert; vert++; @@ -175,7 +177,7 @@ void boxPack2D(boxPack *boxarray, int len, float *tot_width, float *tot_height) 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 = 15 &~ BRF; + vert->free = CORNERFLAGS &~ BRF; vert->brb = box; vert->index = i; i++; box->v[TL] = vert; vert++; @@ -183,7 +185,7 @@ void boxPack2D(boxPack *boxarray, int len, float *tot_width, float *tot_height) 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 = 15 &~ TLF; + vert->free = CORNERFLAGS &~ TLF; vert->tlb = box; vert->index = i; i++; box->v[BR] = vert; vert++; diff --git a/source/blender/blenlib/intern/bpath.c b/source/blender/blenlib/intern/bpath.c index 17d428a6b10..16eb3ff3865 100644 --- a/source/blender/blenlib/intern/bpath.c +++ b/source/blender/blenlib/intern/bpath.c @@ -28,11 +28,13 @@ #include "BLI_bpath.h" #include "BKE_global.h" +//XXX #include "BIF_screen.h" /* only for wait cursor */ #include "DNA_ID.h" /* Library */ #include "DNA_vfont_types.h" #include "DNA_image_types.h" #include "DNA_sound_types.h" #include "DNA_scene_types.h" /* to get the current frame */ +#include "DNA_sequence_types.h" #include <stdlib.h> #include <string.h> @@ -40,6 +42,10 @@ #include "BKE_image.h" /* so we can check the image's type */ #include "BKE_utildefines.h" +#include "MEM_guardedalloc.h" + +/* for sequence */ +//XXX #include "BSE_sequence.h" /* for writing to a textblock */ #include "BKE_text.h" @@ -66,39 +72,66 @@ #define FILE_MAX 240 - /* TODO - BPATH_PLUGIN, BPATH_SEQ */ enum BPathTypes { BPATH_IMAGE = 0, BPATH_SOUND, BPATH_FONT, BPATH_LIB, + BPATH_SEQ, BPATH_DONE }; - void BLI_bpathIterator_init( struct BPathIterator *bpi ) { bpi->type = BPATH_IMAGE; bpi->data = NULL; + + bpi->getpath_callback = NULL; + bpi->setpath_callback = NULL; + + /* Sequencer spesific */ + bpi->seqdata.totseq = 0; + bpi->seqdata.seq = 0; + bpi->seqdata.seqar = NULL; + bpi->seqdata.scene = NULL; + BLI_bpathIterator_step(bpi); } -char* BLI_bpathIterator_getPath( struct BPathIterator *bpi) { - return bpi->path; +void BLI_bpathIterator_free( struct BPathIterator *bpi ) { + if (bpi->seqdata.seqar) + MEM_freeN((void *)bpi->seqdata.seqar); + bpi->seqdata.seqar = NULL; + bpi->seqdata.scene = NULL; } -void BLI_bpathIterator_copyPathExpanded( struct BPathIterator *bpi, char *path_expanded) { - char *filepath, *libpath; + +void BLI_bpathIterator_getPath( struct BPathIterator *bpi, char *path) { + if (bpi->getpath_callback) { + bpi->getpath_callback( bpi, path ); + } else { + strcpy(path, bpi->path); /* warning, we assume 'path' are long enough */ + } +} + +void BLI_bpathIterator_setPath( struct BPathIterator *bpi, char *path) { + if (bpi->setpath_callback) { + bpi->setpath_callback( bpi, path ); + } else { + strcpy(bpi->path, path); /* warning, we assume 'path' are long enough */ + } +} + +void BLI_bpathIterator_getPathExpanded( struct BPathIterator *bpi, char *path_expanded) { + char *libpath; - filepath = BLI_bpathIterator_getPath(bpi); + BLI_bpathIterator_getPath(bpi, path_expanded); libpath = BLI_bpathIterator_getLib(bpi); - BLI_strncpy(path_expanded, filepath, FILE_MAXDIR*2); - if (libpath) { /* check the files location relative to its library path */ - BLI_convertstringcode(path_expanded, libpath, G.scene->r.cfra); + BLI_convertstringcode(path_expanded, libpath); } else { /* local data, use the blend files path */ - BLI_convertstringcode(path_expanded, G.sce, G.scene->r.cfra); + BLI_convertstringcode(path_expanded, G.sce); } } char* BLI_bpathIterator_getLib( struct BPathIterator *bpi) { @@ -115,7 +148,7 @@ int BLI_bpathIterator_getPathMaxLen( struct BPathIterator *bpi) { } /* gets the first or the next image that has a path - not a viewer node or generated image */ -static struct Image *ima_getpath__internal(struct Image *ima, int step_next) { +static struct Image *ima_stepdata__internal(struct Image *ima, int step_next) { if (ima==NULL) return NULL; @@ -131,7 +164,7 @@ static struct Image *ima_getpath__internal(struct Image *ima, int step_next) { return ima; } -static struct VFont *vf_getpath__internal(struct VFont *vf, int step_next) { +static struct VFont *vf_stepdata__internal(struct VFont *vf, int step_next) { if (vf==NULL) return NULL; @@ -149,7 +182,7 @@ static struct VFont *vf_getpath__internal(struct VFont *vf, int step_next) { return vf; } -static struct bSound *snd_getpath__internal(struct bSound *snd, int step_next) { +static struct bSound *snd_stepdata__internal(struct bSound *snd, int step_next) { if (snd==NULL) return NULL; @@ -167,13 +200,117 @@ static struct bSound *snd_getpath__internal(struct bSound *snd, int step_next) { return snd; } +static struct Sequence *seq_stepdata__internal(struct BPathIterator *bpi, int step_next) { + Sequence *seq; + + /* Initializing */ + if (bpi->seqdata.scene==NULL) { + bpi->seqdata.scene= G.main->scene.first; + } + + if (step_next) { + bpi->seqdata.seq++; + } + + while (bpi->seqdata.scene) { + + if (bpi->seqdata.scene->ed) { + if (bpi->seqdata.seqar == NULL) { + /* allocate the sequencer array */ + build_seqar( &(((Editing *)bpi->seqdata.scene->ed)->seqbase), &bpi->seqdata.seqar, &bpi->seqdata.totseq); + bpi->seqdata.seq = 0; + } + + if (bpi->seqdata.seq >= bpi->seqdata.totseq) { + seq = NULL; + } else { + seq = bpi->seqdata.seqar[bpi->seqdata.seq]; + while (!SEQ_HAS_PATH(seq)) { + bpi->seqdata.seq++; + if (bpi->seqdata.seq >= bpi->seqdata.totseq) { + seq = NULL; + break; + } + seq = bpi->seqdata.seqar[bpi->seqdata.seq]; + } + } + if (seq) { + return seq; + } else { + /* keep looking through the next scene, reallocate seq array */ + if (bpi->seqdata.seqar) { + MEM_freeN((void *)bpi->seqdata.seqar); + bpi->seqdata.seqar = NULL; + } + bpi->seqdata.scene = bpi->seqdata.scene->id.next; + } + } else { + /* no seq data in this scene, next */ + bpi->seqdata.scene = bpi->seqdata.scene->id.next; + } + } + + return NULL; +} + +static void seq_getpath(struct BPathIterator *bpi, char *path) { + Sequence *seq = (Sequence *)bpi->data; + + + path[0] = '\0'; /* incase we cant get the path */ + if (seq==NULL) return; + if (SEQ_HAS_PATH(seq)) { + if (seq->type == SEQ_IMAGE || seq->type == SEQ_MOVIE) { + BLI_strncpy(path, seq->strip->dir, FILE_MAX); + BLI_add_slash(path); /* incase its missing */ + if (seq->strip->stripdata) { /* should always be true! */ + /* Using the first image is weak for image sequences */ + strcat(path, seq->strip->stripdata->name); + } + } else { + /* simple case */ + BLI_strncpy(seq->strip->dir, path, sizeof(seq->strip->dir)); + } + } +} + +static void seq_setpath(struct BPathIterator *bpi, char *path) { + Sequence *seq = (Sequence *)bpi->data; + if (seq==NULL) return; + + if (SEQ_HAS_PATH(seq)) { + if (seq->type == SEQ_IMAGE || seq->type == SEQ_MOVIE) { + BLI_split_dirfile_basic(path, seq->strip->dir, seq->strip->stripdata->name); + } else { + /* simple case */ + BLI_strncpy(seq->strip->dir, path, sizeof(seq->strip->dir)); + } + } +} + +static void bpi_type_step__internal( struct BPathIterator *bpi) { + bpi->type++; /* advance to the next type */ + bpi->data = NULL; + + switch (bpi->type) { + case BPATH_SEQ: + bpi->getpath_callback = seq_getpath; + bpi->setpath_callback = seq_setpath; + break; + default: + bpi->getpath_callback = NULL; + bpi->setpath_callback = NULL; + break; + } +} + void BLI_bpathIterator_step( struct BPathIterator *bpi) { while (bpi->type != BPATH_DONE) { if ((bpi->type) == BPATH_IMAGE) { /*if (bpi->data) bpi->data = ((ID *)bpi->data)->next;*/ - if (bpi->data) bpi->data = ima_getpath__internal( (Image *)bpi->data, 1 ); /* must skip images that have no path */ - else bpi->data = ima_getpath__internal(G.main->image.first, 0); + if (bpi->data) bpi->data = ima_stepdata__internal( (Image *)bpi->data, 1 ); /* must skip images that have no path */ + else bpi->data = ima_stepdata__internal(G.main->image.first, 0); if (bpi->data) { /* get the path info from this datatype */ @@ -188,13 +325,13 @@ void BLI_bpathIterator_step( struct BPathIterator *bpi) { break; } else { - bpi->type+=1; /* advance to the next type */ + bpi_type_step__internal(bpi); } } else if ((bpi->type) == BPATH_SOUND) { - if (bpi->data) bpi->data = snd_getpath__internal( (bSound *)bpi->data, 1 ); /* must skip images that have no path */ - else bpi->data = snd_getpath__internal(G.main->sound.first, 0); + if (bpi->data) bpi->data = snd_stepdata__internal( (bSound *)bpi->data, 1 ); /* must skip images that have no path */ + else bpi->data = snd_stepdata__internal(G.main->sound.first, 0); if (bpi->data) { /* get the path info from this datatype */ @@ -208,14 +345,14 @@ void BLI_bpathIterator_step( struct BPathIterator *bpi) { /* we are done, advancing to the next item, this type worked fine */ break; } else { - bpi->type+=1; /* advance to the next type */ + bpi_type_step__internal(bpi); } } else if ((bpi->type) == BPATH_FONT) { - if (bpi->data) bpi->data = vf_getpath__internal( (VFont *)bpi->data, 1 ); - else bpi->data = vf_getpath__internal( G.main->vfont.first, 0 ); + if (bpi->data) bpi->data = vf_stepdata__internal( (VFont *)bpi->data, 1 ); + else bpi->data = vf_stepdata__internal( G.main->vfont.first, 0 ); if (bpi->data) { /* get the path info from this datatype */ @@ -229,12 +366,10 @@ void BLI_bpathIterator_step( struct BPathIterator *bpi) { /* we are done, advancing to the next item, this type worked fine */ break; } else { - bpi->type+=1; /* advance to the next type */ + bpi_type_step__internal(bpi); } - } else if ((bpi->type) == BPATH_LIB) { - if (bpi->data) bpi->data = ((ID *)bpi->data)->next; else bpi->data = G.main->library.first; @@ -250,7 +385,19 @@ void BLI_bpathIterator_step( struct BPathIterator *bpi) { /* we are done, advancing to the next item, this type worked fine */ break; } else { - bpi->type+=1; /* advance to the next type */ + bpi_type_step__internal(bpi); + } + } else if ((bpi->type) == BPATH_SEQ) { + if (bpi->data) bpi->data = seq_stepdata__internal( bpi, 1 ); + else bpi->data = seq_stepdata__internal( bpi, 0 ); + if (bpi->data) { + Sequence *seq = (Sequence *)bpi->data; + bpi->lib = NULL; + bpi->name = seq->name+2; + bpi->len = sizeof(seq->strip->stripdata->name); + break; + } else { + bpi_type_step__internal(bpi); } } } @@ -279,6 +426,9 @@ static void bpathToText(Text *btxt, struct BPathIterator *bpi) case BPATH_LIB: txt_insert_buf( btxt, "Library \"" ); break; + case BPATH_SEQ: + txt_insert_buf( btxt, "Sequence \"" ); + break; default: txt_insert_buf( btxt, "Unknown \"" ); break; @@ -291,7 +441,7 @@ static void bpathToText(Text *btxt, struct BPathIterator *bpi) } txt_insert_buf( btxt, "\" " ); - BLI_bpathIterator_copyPathExpanded(bpi, path_expanded); + BLI_bpathIterator_getPathExpanded(bpi, path_expanded); txt_insert_buf( btxt, path_expanded ); txt_insert_buf( btxt, "\n" ); @@ -299,74 +449,148 @@ static void bpathToText(Text *btxt, struct BPathIterator *bpi) } /* high level function */ -Text *checkMissingFiles(void) { +void checkMissingFiles( char *txtname ) { Text *btxt = NULL; struct BPathIterator bpi; /* be sure there is low chance of the path being too short */ char filepath_expanded[FILE_MAXDIR*2]; - char *filepath, *libpath; - int files_missing = 0; BLI_bpathIterator_init(&bpi); while (!BLI_bpathIterator_isDone(&bpi)) { - filepath = BLI_bpathIterator_getPath(&bpi); - libpath = BLI_bpathIterator_getLib(&bpi); - - BLI_bpathIterator_copyPathExpanded( &bpi, filepath_expanded ); + BLI_bpathIterator_getPathExpanded( &bpi, filepath_expanded ); if (!BLI_exists(filepath_expanded)) { - if (!btxt) - btxt = add_empty_text( "missing_files.txt" ); - + if (!btxt) { + btxt = add_empty_text( "missing_files.log" ); + if (txtname) { + BLI_strncpy(txtname, btxt->id.name+2, 24); + } + } bpathToText(btxt, &bpi); - files_missing = 1; } BLI_bpathIterator_step(&bpi); } - return btxt; + BLI_bpathIterator_free(&bpi); } /* dont log any errors at the moment, should probably do this */ -void makeFilesRelative(int *tot, int *changed, int *failed, int *linked) { +void makeFilesRelative(char *txtname, int *tot, int *changed, int *failed, int *linked) { struct BPathIterator bpi; - char *filepath, *libpath; + char filepath[FILE_MAX], *libpath; /* be sure there is low chance of the path being too short */ char filepath_relative[(FILE_MAXDIR * 2) + FILE_MAXFILE]; + Text *btxt = NULL; + *tot = *changed = *failed = *linked = 0; BLI_bpathIterator_init(&bpi); while (!BLI_bpathIterator_isDone(&bpi)) { - filepath = BLI_bpathIterator_getPath(&bpi); + BLI_bpathIterator_getPath(&bpi, filepath); libpath = BLI_bpathIterator_getLib(&bpi); if(strncmp(filepath, "//", 2)) { - if (libpath) { /* cant make relative if we are kibrary - TODO, LOG THIS */ + if (libpath) { /* cant make relative if we are library - TODO, LOG THIS */ (*linked)++; } else { /* local data, use the blend files path */ BLI_strncpy(filepath_relative, filepath, sizeof(filepath_relative)); + /* Important BLI_cleanup_dir runs before the path is made relative + * because it wont work for paths that start with "//../" */ + BLI_cleanup_file(G.sce, filepath_relative); /* fix any /foo/../foo/ */ BLI_makestringcode(G.sce, filepath_relative); - if (BLI_bpathIterator_getPathMaxLen(&bpi) < strlen(filepath_relative)) { + /* be safe and check the length */ + if (BLI_bpathIterator_getPathMaxLen(&bpi) <= strlen(filepath_relative)) { + if (!btxt) { + btxt = add_empty_text( "missing_no_rel.log" ); + if (txtname) { + BLI_strncpy(txtname, btxt->id.name+2, 24); + } + } + bpathToText(btxt, &bpi); (*failed)++; } else { - /* safe to to check the length */ if(strncmp(filepath_relative, "//", 2)==0) { - strcpy(filepath, filepath_relative); + BLI_bpathIterator_setPath(&bpi, filepath_relative); (*changed)++; } else { + if (!btxt) { + btxt = add_empty_text( "missing_no_rel.log" ); + if (txtname) { + BLI_strncpy(txtname, btxt->id.name+2, 24); + } + } + bpathToText(btxt, &bpi); (*failed)++; } } } } + BLI_bpathIterator_step(&bpi); + (*tot)++; + } + BLI_bpathIterator_free(&bpi); +} + +/* dont log any errors at the moment, should probably do this - + * Verry similar to makeFilesRelative - keep in sync! */ +void makeFilesAbsolute(char *txtname, int *tot, int *changed, int *failed, int *linked) { + struct BPathIterator bpi; + char filepath[FILE_MAX], *libpath; + + /* be sure there is low chance of the path being too short */ + char filepath_absolute[(FILE_MAXDIR * 2) + FILE_MAXFILE]; + + Text *btxt = NULL; + + *tot = *changed = *failed = *linked = 0; + + BLI_bpathIterator_init(&bpi); + while (!BLI_bpathIterator_isDone(&bpi)) { + BLI_bpathIterator_getPath(&bpi, filepath); + libpath = BLI_bpathIterator_getLib(&bpi); + if(strncmp(filepath, "//", 2)==0) { + if (libpath) { /* cant make absolute if we are library - TODO, LOG THIS */ + (*linked)++; + } else { /* get the expanded path and check it is relative or too long */ + BLI_bpathIterator_getPathExpanded( &bpi, filepath_absolute ); + BLI_cleanup_file(G.sce, filepath_absolute); /* fix any /foo/../foo/ */ + /* to be safe, check the length */ + if (BLI_bpathIterator_getPathMaxLen(&bpi) <= strlen(filepath_absolute)) { + if (!btxt) { + btxt = add_empty_text( "missing_no_abs.log" ); + if (txtname) { + BLI_strncpy(txtname, btxt->id.name+2, 24); + } + } + bpathToText(btxt, &bpi); + (*failed)++; + } else { + if(strncmp(filepath_absolute, "//", 2)) { + BLI_bpathIterator_setPath(&bpi, filepath_absolute); + (*changed)++; + } else { + if (!btxt) { + btxt = add_empty_text( "missing_no_abs.log" ); + if (txtname) { + BLI_strncpy(txtname, btxt->id.name+2, 24); + } + } + bpathToText(btxt, &bpi); + (*failed)++; + } + } + } + } BLI_bpathIterator_step(&bpi); (*tot)++; } + BLI_bpathIterator_free(&bpi); } + /* find this file recursively, use the biggest file so thumbnails dont get used by mistake - dir: subdir to search - filename: set this filename @@ -377,14 +601,11 @@ static int findFileRecursive(char *filename_new, const char *dirname, const char { /* file searching stuff */ DIR *dir; - int file = 0; struct dirent *de; struct stat status; char path[FILE_MAX]; int size; - printf("DIR %s\n", dirname); - dir = opendir(dirname); if (dir==0) @@ -406,14 +627,10 @@ static int findFileRecursive(char *filename_new, const char *dirname, const char if (S_ISREG(status.st_mode)) { /* is file */ if (strncmp(filename, de->d_name, FILE_MAX)==0) { /* name matches */ /* open the file to read its size */ - file = open(path, O_BINARY|O_RDONLY); - if (file >=0 ) { - size = BLI_filesize(file); - if (size > *filesize) { /* find the biggest file */ - *filesize = size; - BLI_strncpy(filename_new, path, FILE_MAX); - } - close(file); + size = BLI_filepathsize(path); + if ((size > 0) && (size > *filesize)) { /* find the biggest file */ + *filesize = size; + BLI_strncpy(filename_new, path, FILE_MAX); } } } else if (S_ISDIR(status.st_mode)) { /* is subdir */ @@ -434,28 +651,35 @@ void findMissingFiles(char *str) { /* be sure there is low chance of the path being too short */ char filepath_expanded[FILE_MAXDIR*2]; - char *filepath, *libpath; + char filepath[FILE_MAX], *libpath; int filesize, recur_depth; - char dirname[FILE_MAX], filename[FILE_MAX], filename_new[FILE_MAX], dummyname[FILE_MAX]; + char dirname[FILE_MAX], filename[FILE_MAX], filename_new[FILE_MAX]; + + //XXX waitcursor( 1 ); - BLI_split_dirfile(str, dirname, dummyname); + BLI_split_dirfile_basic(str, dirname, NULL); BLI_bpathIterator_init(&bpi); while (!BLI_bpathIterator_isDone(&bpi)) { - filepath = BLI_bpathIterator_getPath(&bpi); + BLI_bpathIterator_getPath(&bpi, filepath); libpath = BLI_bpathIterator_getLib(&bpi); + /* Check if esc was pressed because searching files can be slow */ + /*XXX if (blender_test_break()) { + break; + }*/ + if (libpath==NULL) { - BLI_bpathIterator_copyPathExpanded( &bpi, filepath_expanded ); + BLI_bpathIterator_getPathExpanded( &bpi, filepath_expanded ); if (!BLI_exists(filepath_expanded)) { /* can the dir be opened? */ filesize = -1; recur_depth = 0; - BLI_split_dirfile(filepath, dummyname, filename); /* the file to find */ + BLI_split_dirfile_basic(filepath, NULL, filename); /* the file to find */ findFileRecursive(filename_new, dirname, filename, &filesize, &recur_depth); if (filesize == -1) { /* could not open dir */ @@ -472,11 +696,14 @@ void findMissingFiles(char *str) { if (G.relbase_valid) BLI_makestringcode(G.sce, filename_new); - strcpy( BLI_bpathIterator_getPath( &bpi ), filename_new ); + BLI_bpathIterator_setPath( &bpi, filename_new ); } } } } BLI_bpathIterator_step(&bpi); } + BLI_bpathIterator_free(&bpi); + + //XXX waitcursor( 0 ); } diff --git a/source/blender/blenlib/intern/dynlib.c b/source/blender/blenlib/intern/dynlib.c index c4692995f20..858aa6e60bf 100644 --- a/source/blender/blenlib/intern/dynlib.c +++ b/source/blender/blenlib/intern/dynlib.c @@ -77,12 +77,9 @@ char *PIL_dynlib_get_error_as_string(PILdynlib* lib) { int err; /* if lib is NULL reset the last error code */ - if (!lib) { - SetLastError(ERROR_SUCCESS); - return NULL; - } - err= GetLastError(); + if (!lib) SetLastError(ERROR_SUCCESS); + if (err) { static char buf[1024]; @@ -96,7 +93,7 @@ char *PIL_dynlib_get_error_as_string(PILdynlib* lib) { return buf; } - return NULL; + return err; } void PIL_dynlib_close(PILdynlib *lib) { diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index 6aa0ded63b9..603c85655d7 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -77,8 +77,12 @@ void BLI_edgehash_insert(EdgeHash *eh, int v0, int v1, void *val) { unsigned int hash; Entry *e= malloc(sizeof(*e)); - if (v1<v0) v0 ^= v1 ^= v0 ^= v1; - hash = EDGEHASH(v0,v1)%eh->nbuckets; + if (v1<v0) { + v0 ^= v1; + v1 ^= v0; + v0 ^= v1; + } + hash = EDGEHASH(v0,v1)%eh->nbuckets; e->v0 = v0; e->v1 = v1; @@ -114,7 +118,11 @@ void** BLI_edgehash_lookup_p(EdgeHash *eh, int v0, int v1) { unsigned int hash; Entry *e; - if (v1<v0) v0 ^= v1 ^= v0 ^= v1; + 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) @@ -200,6 +208,11 @@ void *BLI_edgehashIterator_getValue(EdgeHashIterator *ehi) { return ehi->curEntry?ehi->curEntry->val:NULL; } +void BLI_edgehashIterator_setValue(EdgeHashIterator *ehi, void *val) { + if(ehi->curEntry) + ehi->curEntry->val= val; +} + void BLI_edgehashIterator_step(EdgeHashIterator *ehi) { if (ehi->curEntry) { ehi->curEntry= ehi->curEntry->next; diff --git a/source/blender/blenlib/intern/fileops.c b/source/blender/blenlib/intern/fileops.c index f55cd05e53e..a64185a896a 100644 --- a/source/blender/blenlib/intern/fileops.c +++ b/source/blender/blenlib/intern/fileops.c @@ -6,7 +6,7 @@ * 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. + * 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 @@ -56,6 +56,8 @@ #include "BKE_utildefines.h" #include <errno.h> +#include "BLO_sys_types.h" // for intptr_t support + /* implementations: */ char *first_slash(char *string) { char *ffslash, *fbslash; @@ -66,11 +68,11 @@ char *first_slash(char *string) { if (!ffslash) return fbslash; else if (!fbslash) return ffslash; - if ((long)ffslash < (long)fbslash) return ffslash; + if ((intptr_t)ffslash < (intptr_t)fbslash) return ffslash; else return fbslash; } -char *BLI_last_slash(char *string) { +char *BLI_last_slash(const char *string) { char *lfslash, *lbslash; lfslash= strrchr(string, '/'); @@ -79,10 +81,43 @@ char *BLI_last_slash(char *string) { if (!lfslash) return lbslash; else if (!lbslash) return lfslash; - if ((long)lfslash < (long)lbslash) return lbslash; + if ((intptr_t)lfslash < (intptr_t)lbslash) return lbslash; else return lfslash; } +/* adds a slash if there isnt one there alredy */ +void BLI_add_slash(char *string) { + int len = strlen(string); +#ifdef WIN32 + if (len==0 || string[len-1]!='\\') { + string[len] = '\\'; + string[len+1] = '\0'; + } +#else + if (len==0 || string[len-1]!='/') { + string[len] = '/'; + string[len+1] = '\0'; + } +#endif +} + +/* removes a slash if there is one */ +void BLI_del_slash(char *string) { + int len = strlen(string); + while (len) { +#ifdef WIN32 + if (string[len-1]=='\\') { +#else + if (string[len-1]=='/') { +#endif + string[len-1] = '\0'; + len--; + } else { + break; + } + } +} + /* gzip the file in from and write it to "to". return -1 if zlib fails, -2 if the originating file does not exist note: will remove the "from" file @@ -131,6 +166,23 @@ int BLI_is_writable(char *filename) } } +int BLI_touch(const char *file) +{ + FILE *f = fopen(file,"r+b"); + if (f != NULL) { + char c = getc(f); + rewind(f); + putc(c,f); + } else { + f = fopen(file,"wb"); + } + if (f) { + fclose(f); + return 1; + } + return 0; +} + #ifdef WIN32 static char str[MAXPATHLEN+12]; @@ -152,12 +204,6 @@ int BLI_delete(char *file, int dir, int recursive) { return err; } -int BLI_touch(char *file) { - callLocalErrorCallBack("Touching files is unsupported on Windows"); - - return 1; -} - int BLI_move(char *file, char *to) { int err; @@ -214,12 +260,6 @@ int BLI_link(char *file, char *to) { return 1; } -int BLI_backup(char *file, char *from, char *to) { - callLocalErrorCallBack("Backing up files is unsupported on Windows"); - - return 1; -} - int BLI_exists(char *file) { return (GetFileAttributes(file) != 0xFFFFFFFF); } @@ -257,7 +297,8 @@ void BLI_recurdir_fileops(char *dirname) { int BLI_rename(char *from, char *to) { if (!BLI_exists(from)) return 0; - if (BLI_exists(to)) + /* make sure the filenames are different (case insensitive) before removing */ + if (BLI_exists(to) && BLI_strcasecmp(from, to)) if(BLI_delete(to, 0, 0)) return 1; return rename(from, to); @@ -278,26 +319,21 @@ int BLI_delete(char *file, int dir, int recursive) printf("Error: not deleted file %s because of quote!\n", file); } else { - if (recursive) sprintf(str, "/bin/rm -rf \"%s\"", file); - else if (dir) sprintf(str, "/bin/rmdir \"%s\"", file); - else sprintf(str, "/bin/rm -f \"%s\"", file); - - return system(str); + if (recursive) { + sprintf(str, "/bin/rm -rf \"%s\"", file); + return system(str); + } + else if (dir) { + sprintf(str, "/bin/rmdir \"%s\"", file); + return system(str); + } + else { + return remove(file); //sprintf(str, "/bin/rm -f \"%s\"", file); + } } return -1; } -int BLI_touch(char *file) -{ - - if( BLI_exists("/bin/touch") ) - sprintf(str, "/bin/touch %s", file); - else - sprintf(str, "/usr/bin/touch %s", file); - - return system(str); -} - int BLI_move(char *file, char *to) { sprintf(str, "/bin/mv -f \"%s\" \"%s\"", file, to); @@ -316,12 +352,6 @@ int BLI_link(char *file, char *to) { return system(str); } -int BLI_backup(char *file, char *from, char *to) { - sprintf(str, "/bin/su root -c 'cd %s; /bin/tar cf - \"%s\" | (/bin/cd %s; /bin/tar xf -)'", from, file, to); - - return system(str); -} - int BLI_exists(char *file) { return BLI_exist(file); } diff --git a/source/blender/blenlib/intern/freetypefont.c b/source/blender/blenlib/intern/freetypefont.c index f788f9cf255..2c114ea6971 100644 --- a/source/blender/blenlib/intern/freetypefont.c +++ b/source/blender/blenlib/intern/freetypefont.c @@ -151,7 +151,7 @@ void freetypechar_to_vchar(FT_Face face, FT_ULong charcode, VFontData *vfd) nu->type= CU_BEZIER+CU_2D; nu->pntsu = onpoints[j]; nu->resolu= 8; - nu->flagu= 1; + nu->flagu= CU_CYCLIC; nu->bezt = bezt; //individual curve loop, start-end @@ -399,8 +399,6 @@ static VFontData *objfnt_to_ftvfontdata(PackedFile * pf) break; lcode = charcode; } - - err = FT_Set_Charmap( face, (FT_CharMap) FT_ENCODING_UNICODE ); return vfd; } diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c new file mode 100644 index 00000000000..8f35b38379e --- /dev/null +++ b/source/blender/blenlib/intern/graph.c @@ -0,0 +1,1087 @@ +/** + * $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. + * + * Contributor(s): Martin Poirier + * + * ***** END GPL LICENSE BLOCK ***** + * graph.c: Common graph interface and methods + */ + +#include <float.h> +#include <math.h> + +#include "MEM_guardedalloc.h" + +#include "BLI_graph.h" +#include "BLI_blenlib.h" +#include "BLI_arithb.h" + +#include "BKE_utildefines.h" + +static void testRadialSymmetry(BGraph *graph, BNode* root_node, RadialArc* ring, int total, float axis[3], float limit, int group); + +static void handleAxialSymmetry(BGraph *graph, BNode *root_node, int depth, float axis[3], float limit); +static void testAxialSymmetry(BGraph *graph, BNode* root_node, BNode* node1, BNode* node2, BArc* arc1, BArc* arc2, float axis[3], float limit, int group); +static void flagAxialSymmetry(BNode *root_node, BNode *end_node, BArc *arc, int group); + +void BLI_freeNode(BGraph *graph, BNode *node) +{ + if (node->arcs) + { + MEM_freeN(node->arcs); + } + + if (graph->free_node) + { + graph->free_node(node); + } +} + +void BLI_removeNode(BGraph *graph, BNode *node) +{ + BLI_freeNode(graph, node); + BLI_freelinkN(&graph->nodes, node); +} + +BNode *BLI_otherNode(BArc *arc, BNode *node) +{ + return (arc->head == node) ? arc->tail : arc->head; +} + +void BLI_removeArc(BGraph *graph, BArc *arc) +{ + if (graph->free_arc) + { + graph->free_arc(arc); + } + + BLI_freelinkN(&graph->arcs, arc); +} + +void BLI_flagNodes(BGraph *graph, int flag) +{ + BNode *node; + + for(node = graph->nodes.first; node; node = node->next) + { + node->flag = flag; + } +} + +void BLI_flagArcs(BGraph *graph, int flag) +{ + BArc *arc; + + for(arc = graph->arcs.first; arc; arc = arc->next) + { + arc->flag = flag; + } +} + +static void addArcToNodeAdjacencyList(BNode *node, BArc *arc) +{ + node->arcs[node->flag] = arc; + node->flag++; +} + +void BLI_buildAdjacencyList(BGraph *graph) +{ + BNode *node; + BArc *arc; + + for(node = graph->nodes.first; node; node = node->next) + { + if (node->arcs != NULL) + { + MEM_freeN(node->arcs); + } + + node->arcs = MEM_callocN((node->degree) * sizeof(BArc*), "adjacency list"); + + /* temporary use to indicate the first index available in the lists */ + node->flag = 0; + } + + for(arc = graph->arcs.first; arc; arc= arc->next) + { + addArcToNodeAdjacencyList(arc->head, arc); + addArcToNodeAdjacencyList(arc->tail, arc); + } + + for(node = graph->nodes.first; node; node = node->next) + { + if (node->degree != node->flag) + { + printf("error in node [%p]. Added only %i arcs out of %i\n", node, node->flag, node->degree); + } + } +} + +void BLI_rebuildAdjacencyListForNode(BGraph* graph, BNode *node) +{ + BArc *arc; + + if (node->arcs != NULL) + { + MEM_freeN(node->arcs); + } + + node->arcs = MEM_callocN((node->degree) * sizeof(BArc*), "adjacency list"); + + /* temporary use to indicate the first index available in the lists */ + node->flag = 0; + + for(arc = graph->arcs.first; arc; arc= arc->next) + { + if (arc->head == node) + { + addArcToNodeAdjacencyList(arc->head, arc); + } + else if (arc->tail == node) + { + addArcToNodeAdjacencyList(arc->tail, arc); + } + } + + if (node->degree != node->flag) + { + printf("error in node [%p]. Added only %i arcs out of %i\n", node, node->flag, node->degree); + } +} + +void BLI_freeAdjacencyList(BGraph *graph) +{ + BNode *node; + + for(node = graph->nodes.first; node; node = node->next) + { + if (node->arcs != NULL) + { + MEM_freeN(node->arcs); + node->arcs = NULL; + } + } +} + +int BLI_hasAdjacencyList(BGraph *graph) +{ + BNode *node; + + for(node = graph->nodes.first; node; node = node->next) + { + if (node->arcs == NULL) + { + return 0; + } + } + + return 1; +} + +void BLI_replaceNodeInArc(BGraph *graph, BArc *arc, BNode *node_src, BNode *node_replaced) +{ + if (arc->head == node_replaced) + { + arc->head = node_src; + node_src->degree++; + } + + if (arc->tail == node_replaced) + { + arc->tail = node_src; + node_src->degree++; + } + + if (arc->head == arc->tail) + { + node_src->degree -= 2; + + graph->free_arc(arc); + BLI_freelinkN(&graph->arcs, arc); + } + + if (node_replaced->degree == 0) + { + BLI_removeNode(graph, node_replaced); + } +} + +void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced) +{ + BArc *arc, *next_arc; + + for (arc = graph->arcs.first; arc; arc = next_arc) + { + next_arc = arc->next; + + if (arc->head == node_replaced) + { + arc->head = node_src; + node_replaced->degree--; + node_src->degree++; + } + + if (arc->tail == node_replaced) + { + arc->tail = node_src; + node_replaced->degree--; + node_src->degree++; + } + + if (arc->head == arc->tail) + { + node_src->degree -= 2; + + graph->free_arc(arc); + BLI_freelinkN(&graph->arcs, arc); + } + } + + if (node_replaced->degree == 0) + { + BLI_removeNode(graph, node_replaced); + } +} + +void BLI_removeDoubleNodes(BGraph *graph, float limit) +{ + BNode *node_src, *node_replaced; + + for(node_src = graph->nodes.first; node_src; node_src = node_src->next) + { + for(node_replaced = graph->nodes.first; node_replaced; node_replaced = node_replaced->next) + { + if (node_replaced != node_src && VecLenf(node_replaced->p, node_src->p) <= limit) + { + BLI_replaceNode(graph, node_src, node_replaced); + } + } + } + +} + +BNode * BLI_FindNodeByPosition(BGraph *graph, float *p, float limit) +{ + BNode *closest_node = NULL, *node; + float min_distance; + + for(node = graph->nodes.first; node; node = node->next) + { + float distance = VecLenf(p, node->p); + if (distance <= limit && (closest_node == NULL || distance < min_distance)) + { + closest_node = node; + min_distance = distance; + } + } + + return closest_node; +} +/************************************* SUBGRAPH DETECTION **********************************************/ + +void flagSubgraph(BNode *node, int subgraph) +{ + if (node->subgraph_index == 0) + { + BArc *arc; + int i; + + node->subgraph_index = subgraph; + + for(i = 0; i < node->degree; i++) + { + arc = node->arcs[i]; + flagSubgraph(BLI_otherNode(arc, node), subgraph); + } + } +} + +int BLI_FlagSubgraphs(BGraph *graph) +{ + BNode *node; + int subgraph = 0; + + if (BLI_hasAdjacencyList(graph) == 0) + { + BLI_buildAdjacencyList(graph); + } + + for(node = graph->nodes.first; node; node = node->next) + { + node->subgraph_index = 0; + } + + for (node = graph->nodes.first; node; node = node->next) + { + if (node->subgraph_index == 0) + { + subgraph++; + flagSubgraph(node, subgraph); + } + } + + return subgraph; +} + +void BLI_ReflagSubgraph(BGraph *graph, int old_subgraph, int new_subgraph) +{ + BNode *node; + + for (node = graph->nodes.first; node; node = node->next) + { + if (node->flag == old_subgraph) + { + node->flag = new_subgraph; + } + } +} + +/*************************************** CYCLE DETECTION ***********************************************/ + +int detectCycle(BNode *node, BArc *src_arc) +{ + int value = 0; + + if (node->flag == 0) + { + int i; + + /* mark node as visited */ + node->flag = 1; + + for(i = 0; i < node->degree && value == 0; i++) + { + BArc *arc = node->arcs[i]; + + /* don't go back on the source arc */ + if (arc != src_arc) + { + value = detectCycle(BLI_otherNode(arc, node), arc); + } + } + } + else + { + value = 1; + } + + return value; +} + +int BLI_isGraphCyclic(BGraph *graph) +{ + BNode *node; + int value = 0; + + /* NEED TO CHECK IF ADJACENCY LIST EXIST */ + + /* Mark all nodes as not visited */ + BLI_flagNodes(graph, 0); + + /* detectCycles in subgraphs */ + for(node = graph->nodes.first; node && value == 0; node = node->next) + { + /* only for nodes in subgraphs that haven't been visited yet */ + if (node->flag == 0) + { + value = value || detectCycle(node, NULL); + } + } + + return value; +} + +BArc * BLI_findConnectedArc(BGraph *graph, BArc *arc, BNode *v) +{ + BArc *nextArc = arc->next; + + for(nextArc = graph->arcs.first; nextArc; nextArc = nextArc->next) + { + if (arc != nextArc && (nextArc->head == v || nextArc->tail == v)) + { + break; + } + } + + return nextArc; +} + +/*********************************** GRAPH AS TREE FUNCTIONS *******************************************/ + +int subtreeShape(BNode *node, BArc *rootArc, int include_root) +{ + int depth = 0; + + node->flag = 1; + + if (include_root) + { + BNode *newNode = BLI_otherNode(rootArc, node); + return subtreeShape(newNode, rootArc, 0); + } + else + { + /* Base case, no arcs leading away */ + if (node->arcs == NULL || *(node->arcs) == NULL) + { + return 0; + } + else + { + int i; + + for(i = 0; i < node->degree; i++) + { + BArc *arc = node->arcs[i]; + BNode *newNode = BLI_otherNode(arc, node); + + /* stop immediate and cyclic backtracking */ + if (arc != rootArc && newNode->flag == 0) + { + depth += subtreeShape(newNode, arc, 0); + } + } + } + + return SHAPE_RADIX * depth + 1; + } +} + +int BLI_subtreeShape(BGraph *graph, BNode *node, BArc *rootArc, int include_root) +{ + BNode *test_node; + + BLI_flagNodes(graph, 0); + return subtreeShape(node, rootArc, include_root); +} + +float BLI_subtreeLength(BNode *node) +{ + float length = 0; + int i; + + node->flag = 0; /* flag node as visited */ + + for(i = 0; i < node->degree; i++) + { + BArc *arc = node->arcs[i]; + BNode *other_node = BLI_otherNode(arc, node); + + if (other_node->flag != 0) + { + float subgraph_length = arc->length + BLI_subtreeLength(other_node); + length = MAX2(length, subgraph_length); + } + } + + return length; +} + +void BLI_calcGraphLength(BGraph *graph) +{ + float length = 0; + int nb_subgraphs; + int i; + + nb_subgraphs = BLI_FlagSubgraphs(graph); + + for (i = 1; i <= nb_subgraphs; i++) + { + BNode *node; + + for (node = graph->nodes.first; node; node = node->next) + { + /* start on an external node of the subgraph */ + if (node->subgraph_index == i && node->degree == 1) + { + float subgraph_length = BLI_subtreeLength(node); + length = MAX2(length, subgraph_length); + break; + } + } + } + + graph->length = length; +} + +/********************************* SYMMETRY DETECTION **************************************************/ + +void markdownSymmetryArc(BGraph *graph, BArc *arc, BNode *node, int level, float limit); + +void BLI_mirrorAlongAxis(float v[3], float center[3], float axis[3]) +{ + float dv[3], pv[3]; + + VecSubf(dv, v, center); + Projf(pv, dv, axis); + VecMulf(pv, -2); + VecAddf(v, v, pv); +} + +static void testRadialSymmetry(BGraph *graph, BNode* root_node, RadialArc* ring, int total, float axis[3], float limit, int group) +{ + int symmetric = 1; + int i; + + /* sort ring by angle */ + for (i = 0; i < total - 1; i++) + { + float minAngle = FLT_MAX; + int minIndex = -1; + int j; + + for (j = i + 1; j < total; j++) + { + float angle = Inpf(ring[i].n, ring[j].n); + + /* map negative values to 1..2 */ + if (angle < 0) + { + angle = 1 - angle; + } + + if (angle < minAngle) + { + minIndex = j; + minAngle = angle; + } + } + + /* swap if needed */ + if (minIndex != i + 1) + { + RadialArc tmp; + tmp = ring[i + 1]; + ring[i + 1] = ring[minIndex]; + ring[minIndex] = tmp; + } + } + + for (i = 0; i < total && symmetric; i++) + { + BNode *node1, *node2; + float tangent[3]; + float normal[3]; + float p[3]; + int j = (i + 1) % total; /* next arc in the circular list */ + + VecAddf(tangent, ring[i].n, ring[j].n); + Crossf(normal, tangent, axis); + + node1 = BLI_otherNode(ring[i].arc, root_node); + node2 = BLI_otherNode(ring[j].arc, root_node); + + VECCOPY(p, node2->p); + BLI_mirrorAlongAxis(p, root_node->p, normal); + + /* check if it's within limit before continuing */ + if (VecLenf(node1->p, p) > limit) + { + symmetric = 0; + } + + } + + if (symmetric) + { + /* mark node as symmetric physically */ + VECCOPY(root_node->symmetry_axis, axis); + root_node->symmetry_flag |= SYM_PHYSICAL; + root_node->symmetry_flag |= SYM_RADIAL; + + /* FLAG SYMMETRY GROUP */ + for (i = 0; i < total; i++) + { + ring[i].arc->symmetry_group = group; + ring[i].arc->symmetry_flag = SYM_SIDE_RADIAL + i; + } + + if (graph->radial_symmetry) + { + graph->radial_symmetry(root_node, ring, total); + } + } +} + +static void handleRadialSymmetry(BGraph *graph, BNode *root_node, int depth, float axis[3], float limit) +{ + RadialArc *ring = NULL; + RadialArc *unit; + int total = 0; + int group; + int first; + int i; + + /* mark topological symmetry */ + root_node->symmetry_flag |= SYM_TOPOLOGICAL; + + /* total the number of arcs in the symmetry ring */ + for (i = 0; i < root_node->degree; i++) + { + BArc *connectedArc = root_node->arcs[i]; + + /* depth is store as a negative in flag. symmetry level is positive */ + if (connectedArc->symmetry_level == -depth) + { + total++; + } + } + + ring = MEM_callocN(sizeof(RadialArc) * total, "radial symmetry ring"); + unit = ring; + + /* fill in the ring */ + for (unit = ring, i = 0; i < root_node->degree; i++) + { + BArc *connectedArc = root_node->arcs[i]; + + /* depth is store as a negative in flag. symmetry level is positive */ + if (connectedArc->symmetry_level == -depth) + { + BNode *otherNode = BLI_otherNode(connectedArc, root_node); + float vec[3]; + + unit->arc = connectedArc; + + /* project the node to node vector on the symmetry plane */ + VecSubf(unit->n, otherNode->p, root_node->p); + Projf(vec, unit->n, axis); + VecSubf(unit->n, unit->n, vec); + + Normalize(unit->n); + + unit++; + } + } + + /* sort ring by arc length + * using a rather bogus insertion sort + * butrings will never get too big to matter + * */ + for (i = 0; i < total; i++) + { + int j; + + for (j = i - 1; j >= 0; j--) + { + BArc *arc1, *arc2; + + arc1 = ring[j].arc; + arc2 = ring[j + 1].arc; + + if (arc1->length > arc2->length) + { + /* swap with smaller */ + RadialArc tmp; + + tmp = ring[j + 1]; + ring[j + 1] = ring[j]; + ring[j] = tmp; + } + else + { + break; + } + } + } + + /* Dispatch to specific symmetry tests */ + first = 0; + group = 0; + + for (i = 1; i < total; i++) + { + int dispatch = 0; + int last = i - 1; + + if (fabs(ring[first].arc->length - ring[i].arc->length) > limit) + { + dispatch = 1; + } + + /* if not dispatching already and on last arc + * Dispatch using current arc as last + * */ + if (dispatch == 0 && i == total - 1) + { + last = i; + dispatch = 1; + } + + if (dispatch) + { + int sub_total = last - first + 1; + + group += 1; + + if (sub_total == 1) + { + group -= 1; /* not really a group so decrement */ + /* NOTHING TO DO */ + } + else if (sub_total == 2) + { + BArc *arc1, *arc2; + BNode *node1, *node2; + + arc1 = ring[first].arc; + arc2 = ring[last].arc; + + node1 = BLI_otherNode(arc1, root_node); + node2 = BLI_otherNode(arc2, root_node); + + testAxialSymmetry(graph, root_node, node1, node2, arc1, arc2, axis, limit, group); + } + else if (sub_total != total) /* allocate a new sub ring if needed */ + { + RadialArc *sub_ring = MEM_callocN(sizeof(RadialArc) * sub_total, "radial symmetry ring"); + int sub_i; + + /* fill in the sub ring */ + for (sub_i = 0; sub_i < sub_total; sub_i++) + { + sub_ring[sub_i] = ring[first + sub_i]; + } + + testRadialSymmetry(graph, root_node, sub_ring, sub_total, axis, limit, group); + + MEM_freeN(sub_ring); + } + else if (sub_total == total) + { + testRadialSymmetry(graph, root_node, ring, total, axis, limit, group); + } + + first = i; + } + } + + + MEM_freeN(ring); +} + +static void flagAxialSymmetry(BNode *root_node, BNode *end_node, BArc *arc, int group) +{ + float vec[3]; + + arc->symmetry_group = group; + + VecSubf(vec, end_node->p, root_node->p); + + if (Inpf(vec, root_node->symmetry_axis) < 0) + { + arc->symmetry_flag |= SYM_SIDE_NEGATIVE; + } + else + { + arc->symmetry_flag |= SYM_SIDE_POSITIVE; + } +} + +static void testAxialSymmetry(BGraph *graph, BNode* root_node, BNode* node1, BNode* node2, BArc* arc1, BArc* arc2, float axis[3], float limit, int group) +{ + float nor[3], vec[3], p[3]; + + VecSubf(p, node1->p, root_node->p); + Crossf(nor, p, axis); + + VecSubf(p, root_node->p, node2->p); + Crossf(vec, p, axis); + VecAddf(vec, vec, nor); + + Crossf(nor, vec, axis); + + if (abs(nor[0]) > abs(nor[1]) && abs(nor[0]) > abs(nor[2]) && nor[0] < 0) + { + VecMulf(nor, -1); + } + else if (abs(nor[1]) > abs(nor[0]) && abs(nor[1]) > abs(nor[2]) && nor[1] < 0) + { + VecMulf(nor, -1); + } + else if (abs(nor[2]) > abs(nor[1]) && abs(nor[2]) > abs(nor[0]) && nor[2] < 0) + { + VecMulf(nor, -1); + } + + /* mirror node2 along axis */ + VECCOPY(p, node2->p); + BLI_mirrorAlongAxis(p, root_node->p, nor); + + /* check if it's within limit before continuing */ + if (VecLenf(node1->p, p) <= limit) + { + /* mark node as symmetric physically */ + VECCOPY(root_node->symmetry_axis, nor); + root_node->symmetry_flag |= SYM_PHYSICAL; + root_node->symmetry_flag |= SYM_AXIAL; + + /* flag side on arcs */ + flagAxialSymmetry(root_node, node1, arc1, group); + flagAxialSymmetry(root_node, node2, arc2, group); + + if (graph->axial_symmetry) + { + graph->axial_symmetry(root_node, node1, node2, arc1, arc2); + } + } + else + { + /* NOT SYMMETRIC */ + } +} + +static void handleAxialSymmetry(BGraph *graph, BNode *root_node, int depth, float axis[3], float limit) +{ + BArc *arc1 = NULL, *arc2 = NULL; + BNode *node1 = NULL, *node2 = NULL; + int i; + + /* mark topological symmetry */ + root_node->symmetry_flag |= SYM_TOPOLOGICAL; + + for (i = 0; i < root_node->degree; i++) + { + BArc *connectedArc = root_node->arcs[i]; + + /* depth is store as a negative in flag. symmetry level is positive */ + if (connectedArc->symmetry_level == -depth) + { + if (arc1 == NULL) + { + arc1 = connectedArc; + node1 = BLI_otherNode(arc1, root_node); + } + else + { + arc2 = connectedArc; + node2 = BLI_otherNode(arc2, root_node); + break; /* Can stop now, the two arcs have been found */ + } + } + } + + /* shouldn't happen, but just to be sure */ + if (node1 == NULL || node2 == NULL) + { + return; + } + + testAxialSymmetry(graph, root_node, node1, node2, arc1, arc2, axis, limit, 1); +} + +static void markdownSecondarySymmetry(BGraph *graph, BNode *node, int depth, int level, float limit) +{ + float axis[3] = {0, 0, 0}; + int count = 0; + int i; + + /* count the number of branches in this symmetry group + * and determinte the axis of symmetry + * */ + for (i = 0; i < node->degree; i++) + { + BArc *connectedArc = node->arcs[i]; + + /* depth is store as a negative in flag. symmetry level is positive */ + if (connectedArc->symmetry_level == -depth) + { + count++; + } + /* If arc is on the axis */ + else if (connectedArc->symmetry_level == level) + { + VecAddf(axis, axis, connectedArc->head->p); + VecSubf(axis, axis, connectedArc->tail->p); + } + } + + Normalize(axis); + + /* Split between axial and radial symmetry */ + if (count == 2) + { + handleAxialSymmetry(graph, node, depth, axis, limit); + } + else + { + handleRadialSymmetry(graph, node, depth, axis, limit); + } + + /* markdown secondary symetries */ + for (i = 0; i < node->degree; i++) + { + BArc *connectedArc = node->arcs[i]; + + if (connectedArc->symmetry_level == -depth) + { + /* markdown symmetry for branches corresponding to the depth */ + markdownSymmetryArc(graph, connectedArc, node, level + 1, limit); + } + } +} + +void markdownSymmetryArc(BGraph *graph, BArc *arc, BNode *node, int level, float limit) +{ + int i; + + /* if arc is null, we start straight from a node */ + if (arc) + { + arc->symmetry_level = level; + + node = BLI_otherNode(arc, node); + } + + for (i = 0; i < node->degree; i++) + { + BArc *connectedArc = node->arcs[i]; + + if (connectedArc != arc) + { + BNode *connectedNode = BLI_otherNode(connectedArc, node); + + /* symmetry level is positive value, negative values is subtree depth */ + connectedArc->symmetry_level = -BLI_subtreeShape(graph, connectedNode, connectedArc, 0); + } + } + + arc = NULL; + + for (i = 0; i < node->degree; i++) + { + int issymmetryAxis = 0; + BArc *connectedArc = node->arcs[i]; + + /* only arcs not already marked as symetric */ + if (connectedArc->symmetry_level < 0) + { + int j; + + /* true by default */ + issymmetryAxis = 1; + + for (j = 0; j < node->degree; j++) + { + BArc *otherArc = node->arcs[j]; + + /* different arc, same depth */ + if (otherArc != connectedArc && otherArc->symmetry_level == connectedArc->symmetry_level) + { + /* not on the symmetry axis */ + issymmetryAxis = 0; + break; + } + } + } + + /* arc could be on the symmetry axis */ + if (issymmetryAxis == 1) + { + /* no arc as been marked previously, keep this one */ + if (arc == NULL) + { + arc = connectedArc; + } + else if (connectedArc->symmetry_level < arc->symmetry_level) + { + /* go with more complex subtree as symmetry arc */ + arc = connectedArc; + } + } + } + + /* go down the arc continuing the symmetry axis */ + if (arc) + { + markdownSymmetryArc(graph, arc, node, level, limit); + } + + + /* secondary symmetry */ + for (i = 0; i < node->degree; i++) + { + BArc *connectedArc = node->arcs[i]; + + /* only arcs not already marked as symetric and is not the next arc on the symmetry axis */ + if (connectedArc->symmetry_level < 0) + { + /* subtree depth is store as a negative value in the symmetry */ + markdownSecondarySymmetry(graph, node, -connectedArc->symmetry_level, level, limit); + } + } +} + +void BLI_markdownSymmetry(BGraph *graph, BNode *root_node, float limit) +{ + BNode *node; + BArc *arc; + + if (BLI_isGraphCyclic(graph)) + { + return; + } + + /* mark down all arcs as non-symetric */ + BLI_flagArcs(graph, 0); + + /* mark down all nodes as not on the symmetry axis */ + BLI_flagNodes(graph, 0); + + node = root_node; + + /* sanity check REMOVE ME */ + if (node->degree > 0) + { + arc = node->arcs[0]; + + if (node->degree == 1) + { + markdownSymmetryArc(graph, arc, node, 1, limit); + } + else + { + markdownSymmetryArc(graph, NULL, node, 1, limit); + } + + + + /* mark down non-symetric arcs */ + for (arc = graph->arcs.first; arc; arc = arc->next) + { + if (arc->symmetry_level < 0) + { + arc->symmetry_level = 0; + } + else + { + /* mark down nodes with the lowest level symmetry axis */ + if (arc->head->symmetry_level == 0 || arc->head->symmetry_level > arc->symmetry_level) + { + arc->head->symmetry_level = arc->symmetry_level; + } + if (arc->tail->symmetry_level == 0 || arc->tail->symmetry_level > arc->symmetry_level) + { + arc->tail->symmetry_level = arc->symmetry_level; + } + } + } + } +} + diff --git a/source/blender/blenlib/intern/noise.c b/source/blender/blenlib/intern/noise.c index a678c44d4bf..0bd30a69d05 100644 --- a/source/blender/blenlib/intern/noise.c +++ b/source/blender/blenlib/intern/noise.c @@ -387,55 +387,521 @@ static char p[512+2]= { float g[512+2][3]= { -0.33783,0.715698,-0.611206,-0.944031,-0.326599,-0.045624,-0.101074,-0.416443,-0.903503,0.799286,0.49411,-0.341949,-0.854645,0.518036,0.033936,0.42514,-0.437866,-0.792114,-0.358948,0.597046,0.717377,-0.985413,0.144714,0.089294,-0.601776,-0.33728,-0.723907,-0.449921,0.594513,0.666382,0.208313,-0.10791, -0.972076,0.575317,0.060425,0.815643,0.293365,-0.875702,-0.383453,0.293762,0.465759,0.834686,-0.846008,-0.233398,-0.47934,-0.115814,0.143036,-0.98291,0.204681,-0.949036,-0.239532,0.946716,-0.263947,0.184326,-0.235596,0.573822,0.784332,0.203705,-0.372253,-0.905487,0.756989,-0.651031,0.055298,0.497803, -0.814697,-0.297363,-0.16214,0.063995,-0.98468,-0.329254,0.834381,0.441925,0.703827,-0.527039,-0.476227,0.956421,0.266113,0.119781,0.480133,0.482849,0.7323,-0.18631,0.961212,-0.203125,-0.748474,-0.656921,-0.090393,-0.085052,-0.165253,0.982544,-0.76947,0.628174,-0.115234,0.383148,0.537659,0.751068, -0.616486,-0.668488,-0.415924,-0.259979,-0.630005,0.73175,0.570953,-0.087952,0.816223,-0.458008,0.023254,0.888611,-0.196167,0.976563,-0.088287,-0.263885,-0.69812,-0.665527,0.437134,-0.892273,-0.112793,-0.621674,-0.230438,0.748566,0.232422,0.900574,-0.367249,0.22229,-0.796143,0.562744,-0.665497,-0.73764, -0.11377,0.670135,0.704803,0.232605,0.895599,0.429749,-0.114655,-0.11557,-0.474243,0.872742,0.621826,0.604004,-0.498444,-0.832214,0.012756,0.55426,-0.702484,0.705994,-0.089661,-0.692017,0.649292,0.315399,-0.175995,-0.977997,0.111877,0.096954,-0.04953,0.994019,0.635284,-0.606689,-0.477783,-0.261261, --0.607422,-0.750153,0.983276,0.165436,0.075958,-0.29837,0.404083,-0.864655,-0.638672,0.507721,0.578156,0.388214,0.412079,0.824249,0.556183,-0.208832,0.804352,0.778442,0.562012,0.27951,-0.616577,0.781921,-0.091522,0.196289,0.051056,0.979187,-0.121216,0.207153,-0.970734,-0.173401,-0.384735,0.906555, -0.161499,-0.723236,-0.671387,0.178497,-0.006226,-0.983887,-0.126038,0.15799,0.97934,0.830475,-0.024811,0.556458,-0.510132,-0.76944,0.384247,0.81424,0.200104,-0.544891,-0.112549,-0.393311,-0.912445,0.56189,0.152222,-0.813049,0.198914,-0.254517,-0.946381,-0.41217,0.690979,-0.593811,-0.407257,0.324524, -0.853668,-0.690186,0.366119,-0.624115,-0.428345,0.844147,-0.322296,-0.21228,-0.297546,-0.930756,-0.273071,0.516113,0.811798,0.928314,0.371643,0.007233,0.785828,-0.479218,-0.390778,-0.704895,0.058929,0.706818,0.173248,0.203583,0.963562,0.422211,-0.904297,-0.062469,-0.363312,-0.182465,0.913605,0.254028, --0.552307,-0.793945,-0.28891,-0.765747,-0.574554,0.058319,0.291382,0.954803,0.946136,-0.303925,0.111267,-0.078156,0.443695,-0.892731,0.182098,0.89389,0.409515,-0.680298,-0.213318,0.701141,0.062469,0.848389,-0.525635,-0.72879,-0.641846,0.238342,-0.88089,0.427673,0.202637,-0.532501,-0.21405,0.818878, -0.948975,-0.305084,0.07962,0.925446,0.374664,0.055817,0.820923,0.565491,0.079102,0.25882,0.099792,-0.960724,-0.294617,0.910522,0.289978,0.137115,0.320038,-0.937408,-0.908386,0.345276,-0.235718,-0.936218,0.138763,0.322754,0.366577,0.925934,-0.090637,0.309296,-0.686829,-0.657684,0.66983,0.024445, -0.742065,-0.917999,-0.059113,-0.392059,0.365509,0.462158,-0.807922,0.083374,0.996399,-0.014801,0.593842,0.253143,-0.763672,0.974976,-0.165466,0.148285,0.918976,0.137299,0.369537,0.294952,0.694977,0.655731,0.943085,0.152618,-0.295319,0.58783,-0.598236,0.544495,0.203796,0.678223,0.705994,-0.478821, --0.661011,0.577667,0.719055,-0.1698,-0.673828,-0.132172,-0.965332,0.225006,-0.981873,-0.14502,0.121979,0.763458,0.579742,0.284546,-0.893188,0.079681,0.442474,-0.795776,-0.523804,0.303802,0.734955,0.67804,-0.007446,0.15506,0.986267,-0.056183,0.258026,0.571503,-0.778931,-0.681549,-0.702087,-0.206116, --0.96286,-0.177185,0.203613,-0.470978,-0.515106,0.716095,-0.740326,0.57135,0.354095,-0.56012,-0.824982,-0.074982,-0.507874,0.753204,0.417969,-0.503113,0.038147,0.863342,0.594025,0.673553,-0.439758,-0.119873,-0.005524,-0.992737,0.098267,-0.213776,0.971893,-0.615631,0.643951,0.454163,0.896851,-0.441071, -0.032166,-0.555023,0.750763,-0.358093,0.398773,0.304688,0.864929,-0.722961,0.303589,0.620544,-0.63559,-0.621948,-0.457306,-0.293243,0.072327,0.953278,-0.491638,0.661041,-0.566772,-0.304199,-0.572083,-0.761688,0.908081,-0.398956,0.127014,-0.523621,-0.549683,-0.650848,-0.932922,-0.19986,0.299408,0.099426, -0.140869,0.984985,-0.020325,-0.999756,-0.002319,0.952667,0.280853,-0.11615,-0.971893,0.082581,0.220337,0.65921,0.705292,-0.260651,0.733063,-0.175537,0.657043,-0.555206,0.429504,-0.712189,0.400421,-0.89859,0.179352,0.750885,-0.19696,0.630341,0.785675,-0.569336,0.241821,-0.058899,-0.464111,0.883789, -0.129608,-0.94519,0.299622,-0.357819,0.907654,0.219238,-0.842133,-0.439117,-0.312927,-0.313477,0.84433,0.434479,-0.241211,0.053253,0.968994,0.063873,0.823273,0.563965,0.476288,0.862152,-0.172516,0.620941,-0.298126,0.724915,0.25238,-0.749359,-0.612122,-0.577545,0.386566,0.718994,-0.406342,-0.737976, -0.538696,0.04718,0.556305,0.82959,-0.802856,0.587463,0.101166,-0.707733,-0.705963,0.026428,0.374908,0.68457,0.625092,0.472137,0.208405,-0.856506,-0.703064,-0.581085,-0.409821,-0.417206,-0.736328,0.532623,-0.447876,-0.20285,-0.870728,0.086945,-0.990417,0.107086,0.183685,0.018341,-0.982788,0.560638, --0.428864,0.708282,0.296722,-0.952576,-0.0672,0.135773,0.990265,0.030243,-0.068787,0.654724,0.752686,0.762604,-0.551758,0.337585,-0.819611,-0.407684,0.402466,-0.727844,-0.55072,-0.408539,-0.855774,-0.480011,0.19281,0.693176,-0.079285,0.716339,0.226013,0.650116,-0.725433,0.246704,0.953369,-0.173553, --0.970398,-0.239227,-0.03244,0.136383,-0.394318,0.908752,0.813232,0.558167,0.164368,0.40451,0.549042,-0.731323,-0.380249,-0.566711,0.730865,0.022156,0.932739,0.359741,0.00824,0.996552,-0.082306,0.956635,-0.065338,-0.283722,-0.743561,0.008209,0.668579,-0.859589,-0.509674,0.035767,-0.852234,0.363678, --0.375977,-0.201965,-0.970795,-0.12915,0.313477,0.947327,0.06546,-0.254028,-0.528259,0.81015,0.628052,0.601105,0.49411,-0.494385,0.868378,0.037933,0.275635,-0.086426,0.957336,-0.197937,0.468903,-0.860748,0.895599,0.399384,0.195801,0.560791,0.825012,-0.069214,0.304199,-0.849487,0.43103,0.096375, -0.93576,0.339111,-0.051422,0.408966,-0.911072,0.330444,0.942841,-0.042389,-0.452362,-0.786407,0.420563,0.134308,-0.933472,-0.332489,0.80191,-0.566711,-0.188934,-0.987946,-0.105988,0.112518,-0.24408,0.892242,-0.379791,-0.920502,0.229095,-0.316376,0.7789,0.325958,0.535706,-0.912872,0.185211,-0.36377, --0.184784,0.565369,-0.803833,-0.018463,0.119537,0.992615,-0.259247,-0.935608,0.239532,-0.82373,-0.449127,-0.345947,-0.433105,0.659515,0.614349,-0.822754,0.378845,-0.423676,0.687195,-0.674835,-0.26889,-0.246582,-0.800842,0.545715,-0.729187,-0.207794,0.651978,0.653534,-0.610443,-0.447388,0.492584,-0.023346, -0.869934,0.609039,0.009094,-0.79306,0.962494,-0.271088,-0.00885,0.2659,-0.004913,0.963959,0.651245,0.553619,-0.518951,0.280548,-0.84314,0.458618,-0.175293,-0.983215,0.049805,0.035339,-0.979919,0.196045,-0.982941,0.164307,-0.082245,0.233734,-0.97226,-0.005005,-0.747253,-0.611328,0.260437,0.645599, -0.592773,0.481384,0.117706,-0.949524,-0.29068,-0.535004,-0.791901,-0.294312,-0.627167,-0.214447,0.748718,-0.047974,-0.813477,-0.57959,-0.175537,0.477264,-0.860992,0.738556,-0.414246,-0.53183,0.562561,-0.704071,0.433289,-0.754944,0.64801,-0.100586,0.114716,0.044525,-0.992371,0.966003,0.244873,-0.082764, -0.33783,0.715698,-0.611206,-0.944031,-0.326599,-0.045624,-0.101074,-0.416443,-0.903503,0.799286,0.49411,-0.341949,-0.854645,0.518036,0.033936,0.42514,-0.437866,-0.792114,-0.358948,0.597046,0.717377,-0.985413,0.144714,0.089294,-0.601776,-0.33728,-0.723907,-0.449921,0.594513,0.666382,0.208313,-0.10791, -0.972076,0.575317,0.060425,0.815643,0.293365,-0.875702,-0.383453,0.293762,0.465759,0.834686,-0.846008,-0.233398,-0.47934,-0.115814,0.143036,-0.98291,0.204681,-0.949036,-0.239532,0.946716,-0.263947,0.184326,-0.235596,0.573822,0.784332,0.203705,-0.372253,-0.905487,0.756989,-0.651031,0.055298,0.497803, -0.814697,-0.297363,-0.16214,0.063995,-0.98468,-0.329254,0.834381,0.441925,0.703827,-0.527039,-0.476227,0.956421,0.266113,0.119781,0.480133,0.482849,0.7323,-0.18631,0.961212,-0.203125,-0.748474,-0.656921,-0.090393,-0.085052,-0.165253,0.982544,-0.76947,0.628174,-0.115234,0.383148,0.537659,0.751068, -0.616486,-0.668488,-0.415924,-0.259979,-0.630005,0.73175,0.570953,-0.087952,0.816223,-0.458008,0.023254,0.888611,-0.196167,0.976563,-0.088287,-0.263885,-0.69812,-0.665527,0.437134,-0.892273,-0.112793,-0.621674,-0.230438,0.748566,0.232422,0.900574,-0.367249,0.22229,-0.796143,0.562744,-0.665497,-0.73764, -0.11377,0.670135,0.704803,0.232605,0.895599,0.429749,-0.114655,-0.11557,-0.474243,0.872742,0.621826,0.604004,-0.498444,-0.832214,0.012756,0.55426,-0.702484,0.705994,-0.089661,-0.692017,0.649292,0.315399,-0.175995,-0.977997,0.111877,0.096954,-0.04953,0.994019,0.635284,-0.606689,-0.477783,-0.261261, --0.607422,-0.750153,0.983276,0.165436,0.075958,-0.29837,0.404083,-0.864655,-0.638672,0.507721,0.578156,0.388214,0.412079,0.824249,0.556183,-0.208832,0.804352,0.778442,0.562012,0.27951,-0.616577,0.781921,-0.091522,0.196289,0.051056,0.979187,-0.121216,0.207153,-0.970734,-0.173401,-0.384735,0.906555, -0.161499,-0.723236,-0.671387,0.178497,-0.006226,-0.983887,-0.126038,0.15799,0.97934,0.830475,-0.024811,0.556458,-0.510132,-0.76944,0.384247,0.81424,0.200104,-0.544891,-0.112549,-0.393311,-0.912445,0.56189,0.152222,-0.813049,0.198914,-0.254517,-0.946381,-0.41217,0.690979,-0.593811,-0.407257,0.324524, -0.853668,-0.690186,0.366119,-0.624115,-0.428345,0.844147,-0.322296,-0.21228,-0.297546,-0.930756,-0.273071,0.516113,0.811798,0.928314,0.371643,0.007233,0.785828,-0.479218,-0.390778,-0.704895,0.058929,0.706818,0.173248,0.203583,0.963562,0.422211,-0.904297,-0.062469,-0.363312,-0.182465,0.913605,0.254028, --0.552307,-0.793945,-0.28891,-0.765747,-0.574554,0.058319,0.291382,0.954803,0.946136,-0.303925,0.111267,-0.078156,0.443695,-0.892731,0.182098,0.89389,0.409515,-0.680298,-0.213318,0.701141,0.062469,0.848389,-0.525635,-0.72879,-0.641846,0.238342,-0.88089,0.427673,0.202637,-0.532501,-0.21405,0.818878, -0.948975,-0.305084,0.07962,0.925446,0.374664,0.055817,0.820923,0.565491,0.079102,0.25882,0.099792,-0.960724,-0.294617,0.910522,0.289978,0.137115,0.320038,-0.937408,-0.908386,0.345276,-0.235718,-0.936218,0.138763,0.322754,0.366577,0.925934,-0.090637,0.309296,-0.686829,-0.657684,0.66983,0.024445, -0.742065,-0.917999,-0.059113,-0.392059,0.365509,0.462158,-0.807922,0.083374,0.996399,-0.014801,0.593842,0.253143,-0.763672,0.974976,-0.165466,0.148285,0.918976,0.137299,0.369537,0.294952,0.694977,0.655731,0.943085,0.152618,-0.295319,0.58783,-0.598236,0.544495,0.203796,0.678223,0.705994,-0.478821, --0.661011,0.577667,0.719055,-0.1698,-0.673828,-0.132172,-0.965332,0.225006,-0.981873,-0.14502,0.121979,0.763458,0.579742,0.284546,-0.893188,0.079681,0.442474,-0.795776,-0.523804,0.303802,0.734955,0.67804,-0.007446,0.15506,0.986267,-0.056183,0.258026,0.571503,-0.778931,-0.681549,-0.702087,-0.206116, --0.96286,-0.177185,0.203613,-0.470978,-0.515106,0.716095,-0.740326,0.57135,0.354095,-0.56012,-0.824982,-0.074982,-0.507874,0.753204,0.417969,-0.503113,0.038147,0.863342,0.594025,0.673553,-0.439758,-0.119873,-0.005524,-0.992737,0.098267,-0.213776,0.971893,-0.615631,0.643951,0.454163,0.896851,-0.441071, -0.032166,-0.555023,0.750763,-0.358093,0.398773,0.304688,0.864929,-0.722961,0.303589,0.620544,-0.63559,-0.621948,-0.457306,-0.293243,0.072327,0.953278,-0.491638,0.661041,-0.566772,-0.304199,-0.572083,-0.761688,0.908081,-0.398956,0.127014,-0.523621,-0.549683,-0.650848,-0.932922,-0.19986,0.299408,0.099426, -0.140869,0.984985,-0.020325,-0.999756,-0.002319,0.952667,0.280853,-0.11615,-0.971893,0.082581,0.220337,0.65921,0.705292,-0.260651,0.733063,-0.175537,0.657043,-0.555206,0.429504,-0.712189,0.400421,-0.89859,0.179352,0.750885,-0.19696,0.630341,0.785675,-0.569336,0.241821,-0.058899,-0.464111,0.883789, -0.129608,-0.94519,0.299622,-0.357819,0.907654,0.219238,-0.842133,-0.439117,-0.312927,-0.313477,0.84433,0.434479,-0.241211,0.053253,0.968994,0.063873,0.823273,0.563965,0.476288,0.862152,-0.172516,0.620941,-0.298126,0.724915,0.25238,-0.749359,-0.612122,-0.577545,0.386566,0.718994,-0.406342,-0.737976, -0.538696,0.04718,0.556305,0.82959,-0.802856,0.587463,0.101166,-0.707733,-0.705963,0.026428,0.374908,0.68457,0.625092,0.472137,0.208405,-0.856506,-0.703064,-0.581085,-0.409821,-0.417206,-0.736328,0.532623,-0.447876,-0.20285,-0.870728,0.086945,-0.990417,0.107086,0.183685,0.018341,-0.982788,0.560638, --0.428864,0.708282,0.296722,-0.952576,-0.0672,0.135773,0.990265,0.030243,-0.068787,0.654724,0.752686,0.762604,-0.551758,0.337585,-0.819611,-0.407684,0.402466,-0.727844,-0.55072,-0.408539,-0.855774,-0.480011,0.19281,0.693176,-0.079285,0.716339,0.226013,0.650116,-0.725433,0.246704,0.953369,-0.173553, --0.970398,-0.239227,-0.03244,0.136383,-0.394318,0.908752,0.813232,0.558167,0.164368,0.40451,0.549042,-0.731323,-0.380249,-0.566711,0.730865,0.022156,0.932739,0.359741,0.00824,0.996552,-0.082306,0.956635,-0.065338,-0.283722,-0.743561,0.008209,0.668579,-0.859589,-0.509674,0.035767,-0.852234,0.363678, --0.375977,-0.201965,-0.970795,-0.12915,0.313477,0.947327,0.06546,-0.254028,-0.528259,0.81015,0.628052,0.601105,0.49411,-0.494385,0.868378,0.037933,0.275635,-0.086426,0.957336,-0.197937,0.468903,-0.860748,0.895599,0.399384,0.195801,0.560791,0.825012,-0.069214,0.304199,-0.849487,0.43103,0.096375, -0.93576,0.339111,-0.051422,0.408966,-0.911072,0.330444,0.942841,-0.042389,-0.452362,-0.786407,0.420563,0.134308,-0.933472,-0.332489,0.80191,-0.566711,-0.188934,-0.987946,-0.105988,0.112518,-0.24408,0.892242,-0.379791,-0.920502,0.229095,-0.316376,0.7789,0.325958,0.535706,-0.912872,0.185211,-0.36377, --0.184784,0.565369,-0.803833,-0.018463,0.119537,0.992615,-0.259247,-0.935608,0.239532,-0.82373,-0.449127,-0.345947,-0.433105,0.659515,0.614349,-0.822754,0.378845,-0.423676,0.687195,-0.674835,-0.26889,-0.246582,-0.800842,0.545715,-0.729187,-0.207794,0.651978,0.653534,-0.610443,-0.447388,0.492584,-0.023346, -0.869934,0.609039,0.009094,-0.79306,0.962494,-0.271088,-0.00885,0.2659,-0.004913,0.963959,0.651245,0.553619,-0.518951,0.280548,-0.84314,0.458618,-0.175293,-0.983215,0.049805,0.035339,-0.979919,0.196045,-0.982941,0.164307,-0.082245,0.233734,-0.97226,-0.005005,-0.747253,-0.611328,0.260437,0.645599, -0.592773,0.481384,0.117706,-0.949524,-0.29068,-0.535004,-0.791901,-0.294312,-0.627167,-0.214447,0.748718,-0.047974,-0.813477,-0.57959,-0.175537,0.477264,-0.860992,0.738556,-0.414246,-0.53183,0.562561,-0.704071,0.433289,-0.754944,0.64801,-0.100586,0.114716,0.044525,-0.992371,0.966003,0.244873,-0.082764, -0.33783,0.715698,-0.611206,-0.944031,-0.326599,-0.045624}; + {0.33783, 0.715698, -0.611206}, + {-0.944031, -0.326599, -0.045624}, + {-0.101074, -0.416443, -0.903503}, + {0.799286, 0.49411, -0.341949}, + {-0.854645, 0.518036, 0.033936}, + {0.42514, -0.437866, -0.792114}, + {-0.358948, 0.597046, 0.717377}, + {-0.985413, 0.144714, 0.089294}, + {-0.601776, -0.33728, -0.723907}, + {-0.449921, 0.594513, 0.666382}, + {0.208313, -0.10791, 0.972076}, + {0.575317, 0.060425, 0.815643}, + {0.293365, -0.875702, -0.383453}, + {0.293762, 0.465759, 0.834686}, + {-0.846008, -0.233398, -0.47934}, + {-0.115814, 0.143036, -0.98291}, + {0.204681, -0.949036, -0.239532}, + {0.946716, -0.263947, 0.184326}, + {-0.235596, 0.573822, 0.784332}, + {0.203705, -0.372253, -0.905487}, + {0.756989, -0.651031, 0.055298}, + {0.497803, 0.814697, -0.297363}, + {-0.16214, 0.063995, -0.98468}, + {-0.329254, 0.834381, 0.441925}, + {0.703827, -0.527039, -0.476227}, + {0.956421, 0.266113, 0.119781}, + {0.480133, 0.482849, 0.7323}, + {-0.18631, 0.961212, -0.203125}, + {-0.748474, -0.656921, -0.090393}, + {-0.085052, -0.165253, 0.982544}, + {-0.76947, 0.628174, -0.115234}, + {0.383148, 0.537659, 0.751068}, + {0.616486, -0.668488, -0.415924}, + {-0.259979, -0.630005, 0.73175}, + {0.570953, -0.087952, 0.816223}, + {-0.458008, 0.023254, 0.888611}, + {-0.196167, 0.976563, -0.088287}, + {-0.263885, -0.69812, -0.665527}, + {0.437134, -0.892273, -0.112793}, + {-0.621674, -0.230438, 0.748566}, + {0.232422, 0.900574, -0.367249}, + {0.22229, -0.796143, 0.562744}, + {-0.665497, -0.73764, 0.11377}, + {0.670135, 0.704803, 0.232605}, + {0.895599, 0.429749, -0.114655}, + {-0.11557, -0.474243, 0.872742}, + {0.621826, 0.604004, -0.498444}, + {-0.832214, 0.012756, 0.55426}, + {-0.702484, 0.705994, -0.089661}, + {-0.692017, 0.649292, 0.315399}, + {-0.175995, -0.977997, 0.111877}, + {0.096954, -0.04953, 0.994019}, + {0.635284, -0.606689, -0.477783}, + {-0.261261, -0.607422, -0.750153}, + {0.983276, 0.165436, 0.075958}, + {-0.29837, 0.404083, -0.864655}, + {-0.638672, 0.507721, 0.578156}, + {0.388214, 0.412079, 0.824249}, + {0.556183, -0.208832, 0.804352}, + {0.778442, 0.562012, 0.27951}, + {-0.616577, 0.781921, -0.091522}, + {0.196289, 0.051056, 0.979187}, + {-0.121216, 0.207153, -0.970734}, + {-0.173401, -0.384735, 0.906555}, + {0.161499, -0.723236, -0.671387}, + {0.178497, -0.006226, -0.983887}, + {-0.126038, 0.15799, 0.97934}, + {0.830475, -0.024811, 0.556458}, + {-0.510132, -0.76944, 0.384247}, + {0.81424, 0.200104, -0.544891}, + {-0.112549, -0.393311, -0.912445}, + {0.56189, 0.152222, -0.813049}, + {0.198914, -0.254517, -0.946381}, + {-0.41217, 0.690979, -0.593811}, + {-0.407257, 0.324524, 0.853668}, + {-0.690186, 0.366119, -0.624115}, + {-0.428345, 0.844147, -0.322296}, + {-0.21228, -0.297546, -0.930756}, + {-0.273071, 0.516113, 0.811798}, + {0.928314, 0.371643, 0.007233}, + {0.785828, -0.479218, -0.390778}, + {-0.704895, 0.058929, 0.706818}, + {0.173248, 0.203583, 0.963562}, + {0.422211, -0.904297, -0.062469}, + {-0.363312, -0.182465, 0.913605}, + {0.254028, -0.552307, -0.793945}, + {-0.28891, -0.765747, -0.574554}, + {0.058319, 0.291382, 0.954803}, + {0.946136, -0.303925, 0.111267}, + {-0.078156, 0.443695, -0.892731}, + {0.182098, 0.89389, 0.409515}, + {-0.680298, -0.213318, 0.701141}, + {0.062469, 0.848389, -0.525635}, + {-0.72879, -0.641846, 0.238342}, + {-0.88089, 0.427673, 0.202637}, + {-0.532501, -0.21405, 0.818878}, + {0.948975, -0.305084, 0.07962}, + {0.925446, 0.374664, 0.055817}, + {0.820923, 0.565491, 0.079102}, + {0.25882, 0.099792, -0.960724}, + {-0.294617, 0.910522, 0.289978}, + {0.137115, 0.320038, -0.937408}, + {-0.908386, 0.345276, -0.235718}, + {-0.936218, 0.138763, 0.322754}, + {0.366577, 0.925934, -0.090637}, + {0.309296, -0.686829, -0.657684}, + {0.66983, 0.024445, 0.742065}, + {-0.917999, -0.059113, -0.392059}, + {0.365509, 0.462158, -0.807922}, + {0.083374, 0.996399, -0.014801}, + {0.593842, 0.253143, -0.763672}, + {0.974976, -0.165466, 0.148285}, + {0.918976, 0.137299, 0.369537}, + {0.294952, 0.694977, 0.655731}, + {0.943085, 0.152618, -0.295319}, + {0.58783, -0.598236, 0.544495}, + {0.203796, 0.678223, 0.705994}, + {-0.478821, -0.661011, 0.577667}, + {0.719055, -0.1698, -0.673828}, + {-0.132172, -0.965332, 0.225006}, + {-0.981873, -0.14502, 0.121979}, + {0.763458, 0.579742, 0.284546}, + {-0.893188, 0.079681, 0.442474}, + {-0.795776, -0.523804, 0.303802}, + {0.734955, 0.67804, -0.007446}, + {0.15506, 0.986267, -0.056183}, + {0.258026, 0.571503, -0.778931}, + {-0.681549, -0.702087, -0.206116}, + {-0.96286, -0.177185, 0.203613}, + {-0.470978, -0.515106, 0.716095}, + {-0.740326, 0.57135, 0.354095}, + {-0.56012, -0.824982, -0.074982}, + {-0.507874, 0.753204, 0.417969}, + {-0.503113, 0.038147, 0.863342}, + {0.594025, 0.673553, -0.439758}, + {-0.119873, -0.005524, -0.992737}, + {0.098267, -0.213776, 0.971893}, + {-0.615631, 0.643951, 0.454163}, + {0.896851, -0.441071, 0.032166}, + {-0.555023, 0.750763, -0.358093}, + {0.398773, 0.304688, 0.864929}, + {-0.722961, 0.303589, 0.620544}, + {-0.63559, -0.621948, -0.457306}, + {-0.293243, 0.072327, 0.953278}, + {-0.491638, 0.661041, -0.566772}, + {-0.304199, -0.572083, -0.761688}, + {0.908081, -0.398956, 0.127014}, + {-0.523621, -0.549683, -0.650848}, + {-0.932922, -0.19986, 0.299408}, + {0.099426, 0.140869, 0.984985}, + {-0.020325, -0.999756, -0.002319}, + {0.952667, 0.280853, -0.11615}, + {-0.971893, 0.082581, 0.220337}, + {0.65921, 0.705292, -0.260651}, + {0.733063, -0.175537, 0.657043}, + {-0.555206, 0.429504, -0.712189}, + {0.400421, -0.89859, 0.179352}, + {0.750885, -0.19696, 0.630341}, + {0.785675, -0.569336, 0.241821}, + {-0.058899, -0.464111, 0.883789}, + {0.129608, -0.94519, 0.299622}, + {-0.357819, 0.907654, 0.219238}, + {-0.842133, -0.439117, -0.312927}, + {-0.313477, 0.84433, 0.434479}, + {-0.241211, 0.053253, 0.968994}, + {0.063873, 0.823273, 0.563965}, + {0.476288, 0.862152, -0.172516}, + {0.620941, -0.298126, 0.724915}, + {0.25238, -0.749359, -0.612122}, + {-0.577545, 0.386566, 0.718994}, + {-0.406342, -0.737976, 0.538696}, + {0.04718, 0.556305, 0.82959}, + {-0.802856, 0.587463, 0.101166}, + {-0.707733, -0.705963, 0.026428}, + {0.374908, 0.68457, 0.625092}, + {0.472137, 0.208405, -0.856506}, + {-0.703064, -0.581085, -0.409821}, + {-0.417206, -0.736328, 0.532623}, + {-0.447876, -0.20285, -0.870728}, + {0.086945, -0.990417, 0.107086}, + {0.183685, 0.018341, -0.982788}, + {0.560638, -0.428864, 0.708282}, + {0.296722, -0.952576, -0.0672}, + {0.135773, 0.990265, 0.030243}, + {-0.068787, 0.654724, 0.752686}, + {0.762604, -0.551758, 0.337585}, + {-0.819611, -0.407684, 0.402466}, + {-0.727844, -0.55072, -0.408539}, + {-0.855774, -0.480011, 0.19281}, + {0.693176, -0.079285, 0.716339}, + {0.226013, 0.650116, -0.725433}, + {0.246704, 0.953369, -0.173553}, + {-0.970398, -0.239227, -0.03244}, + {0.136383, -0.394318, 0.908752}, + {0.813232, 0.558167, 0.164368}, + {0.40451, 0.549042, -0.731323}, + {-0.380249, -0.566711, 0.730865}, + {0.022156, 0.932739, 0.359741}, + {0.00824, 0.996552, -0.082306}, + {0.956635, -0.065338, -0.283722}, + {-0.743561, 0.008209, 0.668579}, + {-0.859589, -0.509674, 0.035767}, + {-0.852234, 0.363678, -0.375977}, + {-0.201965, -0.970795, -0.12915}, + {0.313477, 0.947327, 0.06546}, + {-0.254028, -0.528259, 0.81015}, + {0.628052, 0.601105, 0.49411}, + {-0.494385, 0.868378, 0.037933}, + {0.275635, -0.086426, 0.957336}, + {-0.197937, 0.468903, -0.860748}, + {0.895599, 0.399384, 0.195801}, + {0.560791, 0.825012, -0.069214}, + {0.304199, -0.849487, 0.43103}, + {0.096375, 0.93576, 0.339111}, + {-0.051422, 0.408966, -0.911072}, + {0.330444, 0.942841, -0.042389}, + {-0.452362, -0.786407, 0.420563}, + {0.134308, -0.933472, -0.332489}, + {0.80191, -0.566711, -0.188934}, + {-0.987946, -0.105988, 0.112518}, + {-0.24408, 0.892242, -0.379791}, + {-0.920502, 0.229095, -0.316376}, + {0.7789, 0.325958, 0.535706}, + {-0.912872, 0.185211, -0.36377}, + {-0.184784, 0.565369, -0.803833}, + {-0.018463, 0.119537, 0.992615}, + {-0.259247, -0.935608, 0.239532}, + {-0.82373, -0.449127, -0.345947}, + {-0.433105, 0.659515, 0.614349}, + {-0.822754, 0.378845, -0.423676}, + {0.687195, -0.674835, -0.26889}, + {-0.246582, -0.800842, 0.545715}, + {-0.729187, -0.207794, 0.651978}, + {0.653534, -0.610443, -0.447388}, + {0.492584, -0.023346, 0.869934}, + {0.609039, 0.009094, -0.79306}, + {0.962494, -0.271088, -0.00885}, + {0.2659, -0.004913, 0.963959}, + {0.651245, 0.553619, -0.518951}, + {0.280548, -0.84314, 0.458618}, + {-0.175293, -0.983215, 0.049805}, + {0.035339, -0.979919, 0.196045}, + {-0.982941, 0.164307, -0.082245}, + {0.233734, -0.97226, -0.005005}, + {-0.747253, -0.611328, 0.260437}, + {0.645599, 0.592773, 0.481384}, + {0.117706, -0.949524, -0.29068}, + {-0.535004, -0.791901, -0.294312}, + {-0.627167, -0.214447, 0.748718}, + {-0.047974, -0.813477, -0.57959}, + {-0.175537, 0.477264, -0.860992}, + {0.738556, -0.414246, -0.53183}, + {0.562561, -0.704071, 0.433289}, + {-0.754944, 0.64801, -0.100586}, + {0.114716, 0.044525, -0.992371}, + {0.966003, 0.244873, -0.082764}, + {0.33783, 0.715698, -0.611206}, + {-0.944031, -0.326599, -0.045624}, + {-0.101074, -0.416443, -0.903503}, + {0.799286, 0.49411, -0.341949}, + {-0.854645, 0.518036, 0.033936}, + {0.42514, -0.437866, -0.792114}, + {-0.358948, 0.597046, 0.717377}, + {-0.985413, 0.144714, 0.089294}, + {-0.601776, -0.33728, -0.723907}, + {-0.449921, 0.594513, 0.666382}, + {0.208313, -0.10791, 0.972076}, + {0.575317, 0.060425, 0.815643}, + {0.293365, -0.875702, -0.383453}, + {0.293762, 0.465759, 0.834686}, + {-0.846008, -0.233398, -0.47934}, + {-0.115814, 0.143036, -0.98291}, + {0.204681, -0.949036, -0.239532}, + {0.946716, -0.263947, 0.184326}, + {-0.235596, 0.573822, 0.784332}, + {0.203705, -0.372253, -0.905487}, + {0.756989, -0.651031, 0.055298}, + {0.497803, 0.814697, -0.297363}, + {-0.16214, 0.063995, -0.98468}, + {-0.329254, 0.834381, 0.441925}, + {0.703827, -0.527039, -0.476227}, + {0.956421, 0.266113, 0.119781}, + {0.480133, 0.482849, 0.7323}, + {-0.18631, 0.961212, -0.203125}, + {-0.748474, -0.656921, -0.090393}, + {-0.085052, -0.165253, 0.982544}, + {-0.76947, 0.628174, -0.115234}, + {0.383148, 0.537659, 0.751068}, + {0.616486, -0.668488, -0.415924}, + {-0.259979, -0.630005, 0.73175}, + {0.570953, -0.087952, 0.816223}, + {-0.458008, 0.023254, 0.888611}, + {-0.196167, 0.976563, -0.088287}, + {-0.263885, -0.69812, -0.665527}, + {0.437134, -0.892273, -0.112793}, + {-0.621674, -0.230438, 0.748566}, + {0.232422, 0.900574, -0.367249}, + {0.22229, -0.796143, 0.562744}, + {-0.665497, -0.73764, 0.11377}, + {0.670135, 0.704803, 0.232605}, + {0.895599, 0.429749, -0.114655}, + {-0.11557, -0.474243, 0.872742}, + {0.621826, 0.604004, -0.498444}, + {-0.832214, 0.012756, 0.55426}, + {-0.702484, 0.705994, -0.089661}, + {-0.692017, 0.649292, 0.315399}, + {-0.175995, -0.977997, 0.111877}, + {0.096954, -0.04953, 0.994019}, + {0.635284, -0.606689, -0.477783}, + {-0.261261, -0.607422, -0.750153}, + {0.983276, 0.165436, 0.075958}, + {-0.29837, 0.404083, -0.864655}, + {-0.638672, 0.507721, 0.578156}, + {0.388214, 0.412079, 0.824249}, + {0.556183, -0.208832, 0.804352}, + {0.778442, 0.562012, 0.27951}, + {-0.616577, 0.781921, -0.091522}, + {0.196289, 0.051056, 0.979187}, + {-0.121216, 0.207153, -0.970734}, + {-0.173401, -0.384735, 0.906555}, + {0.161499, -0.723236, -0.671387}, + {0.178497, -0.006226, -0.983887}, + {-0.126038, 0.15799, 0.97934}, + {0.830475, -0.024811, 0.556458}, + {-0.510132, -0.76944, 0.384247}, + {0.81424, 0.200104, -0.544891}, + {-0.112549, -0.393311, -0.912445}, + {0.56189, 0.152222, -0.813049}, + {0.198914, -0.254517, -0.946381}, + {-0.41217, 0.690979, -0.593811}, + {-0.407257, 0.324524, 0.853668}, + {-0.690186, 0.366119, -0.624115}, + {-0.428345, 0.844147, -0.322296}, + {-0.21228, -0.297546, -0.930756}, + {-0.273071, 0.516113, 0.811798}, + {0.928314, 0.371643, 0.007233}, + {0.785828, -0.479218, -0.390778}, + {-0.704895, 0.058929, 0.706818}, + {0.173248, 0.203583, 0.963562}, + {0.422211, -0.904297, -0.062469}, + {-0.363312, -0.182465, 0.913605}, + {0.254028, -0.552307, -0.793945}, + {-0.28891, -0.765747, -0.574554}, + {0.058319, 0.291382, 0.954803}, + {0.946136, -0.303925, 0.111267}, + {-0.078156, 0.443695, -0.892731}, + {0.182098, 0.89389, 0.409515}, + {-0.680298, -0.213318, 0.701141}, + {0.062469, 0.848389, -0.525635}, + {-0.72879, -0.641846, 0.238342}, + {-0.88089, 0.427673, 0.202637}, + {-0.532501, -0.21405, 0.818878}, + {0.948975, -0.305084, 0.07962}, + {0.925446, 0.374664, 0.055817}, + {0.820923, 0.565491, 0.079102}, + {0.25882, 0.099792, -0.960724}, + {-0.294617, 0.910522, 0.289978}, + {0.137115, 0.320038, -0.937408}, + {-0.908386, 0.345276, -0.235718}, + {-0.936218, 0.138763, 0.322754}, + {0.366577, 0.925934, -0.090637}, + {0.309296, -0.686829, -0.657684}, + {0.66983, 0.024445, 0.742065}, + {-0.917999, -0.059113, -0.392059}, + {0.365509, 0.462158, -0.807922}, + {0.083374, 0.996399, -0.014801}, + {0.593842, 0.253143, -0.763672}, + {0.974976, -0.165466, 0.148285}, + {0.918976, 0.137299, 0.369537}, + {0.294952, 0.694977, 0.655731}, + {0.943085, 0.152618, -0.295319}, + {0.58783, -0.598236, 0.544495}, + {0.203796, 0.678223, 0.705994}, + {-0.478821, -0.661011, 0.577667}, + {0.719055, -0.1698, -0.673828}, + {-0.132172, -0.965332, 0.225006}, + {-0.981873, -0.14502, 0.121979}, + {0.763458, 0.579742, 0.284546}, + {-0.893188, 0.079681, 0.442474}, + {-0.795776, -0.523804, 0.303802}, + {0.734955, 0.67804, -0.007446}, + {0.15506, 0.986267, -0.056183}, + {0.258026, 0.571503, -0.778931}, + {-0.681549, -0.702087, -0.206116}, + {-0.96286, -0.177185, 0.203613}, + {-0.470978, -0.515106, 0.716095}, + {-0.740326, 0.57135, 0.354095}, + {-0.56012, -0.824982, -0.074982}, + {-0.507874, 0.753204, 0.417969}, + {-0.503113, 0.038147, 0.863342}, + {0.594025, 0.673553, -0.439758}, + {-0.119873, -0.005524, -0.992737}, + {0.098267, -0.213776, 0.971893}, + {-0.615631, 0.643951, 0.454163}, + {0.896851, -0.441071, 0.032166}, + {-0.555023, 0.750763, -0.358093}, + {0.398773, 0.304688, 0.864929}, + {-0.722961, 0.303589, 0.620544}, + {-0.63559, -0.621948, -0.457306}, + {-0.293243, 0.072327, 0.953278}, + {-0.491638, 0.661041, -0.566772}, + {-0.304199, -0.572083, -0.761688}, + {0.908081, -0.398956, 0.127014}, + {-0.523621, -0.549683, -0.650848}, + {-0.932922, -0.19986, 0.299408}, + {0.099426, 0.140869, 0.984985}, + {-0.020325, -0.999756, -0.002319}, + {0.952667, 0.280853, -0.11615}, + {-0.971893, 0.082581, 0.220337}, + {0.65921, 0.705292, -0.260651}, + {0.733063, -0.175537, 0.657043}, + {-0.555206, 0.429504, -0.712189}, + {0.400421, -0.89859, 0.179352}, + {0.750885, -0.19696, 0.630341}, + {0.785675, -0.569336, 0.241821}, + {-0.058899, -0.464111, 0.883789}, + {0.129608, -0.94519, 0.299622}, + {-0.357819, 0.907654, 0.219238}, + {-0.842133, -0.439117, -0.312927}, + {-0.313477, 0.84433, 0.434479}, + {-0.241211, 0.053253, 0.968994}, + {0.063873, 0.823273, 0.563965}, + {0.476288, 0.862152, -0.172516}, + {0.620941, -0.298126, 0.724915}, + {0.25238, -0.749359, -0.612122}, + {-0.577545, 0.386566, 0.718994}, + {-0.406342, -0.737976, 0.538696}, + {0.04718, 0.556305, 0.82959}, + {-0.802856, 0.587463, 0.101166}, + {-0.707733, -0.705963, 0.026428}, + {0.374908, 0.68457, 0.625092}, + {0.472137, 0.208405, -0.856506}, + {-0.703064, -0.581085, -0.409821}, + {-0.417206, -0.736328, 0.532623}, + {-0.447876, -0.20285, -0.870728}, + {0.086945, -0.990417, 0.107086}, + {0.183685, 0.018341, -0.982788}, + {0.560638, -0.428864, 0.708282}, + {0.296722, -0.952576, -0.0672}, + {0.135773, 0.990265, 0.030243}, + {-0.068787, 0.654724, 0.752686}, + {0.762604, -0.551758, 0.337585}, + {-0.819611, -0.407684, 0.402466}, + {-0.727844, -0.55072, -0.408539}, + {-0.855774, -0.480011, 0.19281}, + {0.693176, -0.079285, 0.716339}, + {0.226013, 0.650116, -0.725433}, + {0.246704, 0.953369, -0.173553}, + {-0.970398, -0.239227, -0.03244}, + {0.136383, -0.394318, 0.908752}, + {0.813232, 0.558167, 0.164368}, + {0.40451, 0.549042, -0.731323}, + {-0.380249, -0.566711, 0.730865}, + {0.022156, 0.932739, 0.359741}, + {0.00824, 0.996552, -0.082306}, + {0.956635, -0.065338, -0.283722}, + {-0.743561, 0.008209, 0.668579}, + {-0.859589, -0.509674, 0.035767}, + {-0.852234, 0.363678, -0.375977}, + {-0.201965, -0.970795, -0.12915}, + {0.313477, 0.947327, 0.06546}, + {-0.254028, -0.528259, 0.81015}, + {0.628052, 0.601105, 0.49411}, + {-0.494385, 0.868378, 0.037933}, + {0.275635, -0.086426, 0.957336}, + {-0.197937, 0.468903, -0.860748}, + {0.895599, 0.399384, 0.195801}, + {0.560791, 0.825012, -0.069214}, + {0.304199, -0.849487, 0.43103}, + {0.096375, 0.93576, 0.339111}, + {-0.051422, 0.408966, -0.911072}, + {0.330444, 0.942841, -0.042389}, + {-0.452362, -0.786407, 0.420563}, + {0.134308, -0.933472, -0.332489}, + {0.80191, -0.566711, -0.188934}, + {-0.987946, -0.105988, 0.112518}, + {-0.24408, 0.892242, -0.379791}, + {-0.920502, 0.229095, -0.316376}, + {0.7789, 0.325958, 0.535706}, + {-0.912872, 0.185211, -0.36377}, + {-0.184784, 0.565369, -0.803833}, + {-0.018463, 0.119537, 0.992615}, + {-0.259247, -0.935608, 0.239532}, + {-0.82373, -0.449127, -0.345947}, + {-0.433105, 0.659515, 0.614349}, + {-0.822754, 0.378845, -0.423676}, + {0.687195, -0.674835, -0.26889}, + {-0.246582, -0.800842, 0.545715}, + {-0.729187, -0.207794, 0.651978}, + {0.653534, -0.610443, -0.447388}, + {0.492584, -0.023346, 0.869934}, + {0.609039, 0.009094, -0.79306}, + {0.962494, -0.271088, -0.00885}, + {0.2659, -0.004913, 0.963959}, + {0.651245, 0.553619, -0.518951}, + {0.280548, -0.84314, 0.458618}, + {-0.175293, -0.983215, 0.049805}, + {0.035339, -0.979919, 0.196045}, + {-0.982941, 0.164307, -0.082245}, + {0.233734, -0.97226, -0.005005}, + {-0.747253, -0.611328, 0.260437}, + {0.645599, 0.592773, 0.481384}, + {0.117706, -0.949524, -0.29068}, + {-0.535004, -0.791901, -0.294312}, + {-0.627167, -0.214447, 0.748718}, + {-0.047974, -0.813477, -0.57959}, + {-0.175537, 0.477264, -0.860992}, + {0.738556, -0.414246, -0.53183}, + {0.562561, -0.704071, 0.433289}, + {-0.754944, 0.64801, -0.100586}, + {0.114716, 0.044525, -0.992371}, + {0.966003, 0.244873, -0.082764}, + {0.33783, 0.715698, -0.611206}, + {-0.944031, -0.326599, -0.045624}, +}; diff --git a/source/blender/blenlib/intern/psfont.c b/source/blender/blenlib/intern/psfont.c index cf58f44ad2c..54d7f8ec1af 100644 --- a/source/blender/blenlib/intern/psfont.c +++ b/source/blender/blenlib/intern/psfont.c @@ -43,6 +43,8 @@ #include "DNA_packedFile_types.h" #include "DNA_curve_types.h" +#include "BLO_sys_types.h" // for intptr_t support + #ifdef HAVE_CONFIG_H #include <config.h> #endif @@ -54,7 +56,7 @@ typedef struct chardesc { short llx, lly; /* bounding box */ short urx, ury; short *data; /* char data */ - long datalen; + intptr_t datalen; } chardesc; typedef struct objfnt { @@ -256,290 +258,290 @@ static int sp; static int savesplines = 1; static pschar ISOcharlist[NASCII] = { - "/space", 040, 0, - "/exclam", 041, 0, - "/quotedbl", 042, 0, - "/numbersign", 043, 0, - "/dollar", 044, 0, - "/percent", 045, 0, - "/ampersand", 046, 0, - "/quoteright", 047, 0, - - "/parenleft", 050, 0, - "/parenright", 051, 0, - "/asterisk", 052, 0, - "/plus", 053, 0, - "/comma", 054, 0, - "/hyphen", 055, 0, - "/period", 056, 0, - "/slash", 057, 0, - - "/zero", 060, 0, - "/one", 061, 0, - "/two", 062, 0, - "/three", 063, 0, - "/four", 064, 0, - "/five", 065, 0, - "/six", 066, 0, - "/seven", 067, 0, - - "/eight", 070, 0, - "/nine", 071, 0, - "/colon", 072, 0, - "/semicolon", 073, 0, - "/less", 074, 0, - "/equal", 075, 0, - "/greater", 076, 0, - "/question", 077, 0, - - "/at", 0100, 0, - "/A", 0101, 0, - "/B", 0102, 0, - "/C", 0103, 0, - "/D", 0104, 0, - "/E", 0105, 0, - "/F", 0106, 0, - "/G", 0107, 0, - - "/H", 0110, 0, - "/I", 0111, 0, - "/J", 0112, 0, - "/K", 0113, 0, - "/L", 0114, 0, - "/M", 0115, 0, - "/N", 0116, 0, - "/O", 0117, 0, - - "/P", 0120, 0, - "/Q", 0121, 0, - "/R", 0122, 0, - "/S", 0123, 0, - "/T", 0124, 0, - "/U", 0125, 0, - "/V", 0126, 0, - "/W", 0127, 0, - - "/X", 0130, 0, - "/Y", 0131, 0, - "/Z", 0132, 0, - "/bracketleft", 0133, 0, - "/backslash", 0134, 0, - "/bracketright", 0135, 0, - "/asciicircum", 0136, 0, - "/underscore", 0137, 0, - - "/quoteleft", 0140, 0, - "/a", 0141, 0, - "/b", 0142, 0, - "/c", 0143, 0, - "/d", 0144, 0, - "/e", 0145, 0, - "/f", 0146, 0, - "/g", 0147, 0, - - "/h", 0150, 0, - "/i", 0151, 0, - "/j", 0152, 0, - "/k", 0153, 0, - "/l", 0154, 0, - "/m", 0155, 0, - "/n", 0156, 0, - "/o", 0157, 0, - - "/p", 0160, 0, - "/q", 0161, 0, - "/r", 0162, 0, - "/s", 0163, 0, - "/t", 0164, 0, - "/u", 0165, 0, - "/v", 0166, 0, - "/w", 0167, 0, - - "/x", 0170, 0, - "/y", 0171, 0, - "/z", 0172, 0, - "/braceleft", 0173, 0, - "/bar", 0174, 0, - "/braceright", 0175, 0, - "/asciitilde", 0176, 0, - "/", 0177, 0, + {"/space", 040, 0}, + {"/exclam", 041, 0}, + {"/quotedbl", 042, 0}, + {"/numbersign", 043, 0}, + {"/dollar", 044, 0}, + {"/percent", 045, 0}, + {"/ampersand", 046, 0}, + {"/quoteright", 047, 0}, + + {"/parenleft", 050, 0}, + {"/parenright", 051, 0}, + {"/asterisk", 052, 0}, + {"/plus", 053, 0}, + {"/comma", 054, 0}, + {"/hyphen", 055, 0}, + {"/period", 056, 0}, + {"/slash", 057, 0}, + + {"/zero", 060, 0}, + {"/one", 061, 0}, + {"/two", 062, 0}, + {"/three", 063, 0}, + {"/four", 064, 0}, + {"/five", 065, 0}, + {"/six", 066, 0}, + {"/seven", 067, 0}, + + {"/eight", 070, 0}, + {"/nine", 071, 0}, + {"/colon", 072, 0}, + {"/semicolon", 073, 0}, + {"/less", 074, 0}, + {"/equal", 075, 0}, + {"/greater", 076, 0}, + {"/question", 077, 0}, + + {"/at", 0100, 0}, + {"/A", 0101, 0}, + {"/B", 0102, 0}, + {"/C", 0103, 0}, + {"/D", 0104, 0}, + {"/E", 0105, 0}, + {"/F", 0106, 0}, + {"/G", 0107, 0}, + + {"/H", 0110, 0}, + {"/I", 0111, 0}, + {"/J", 0112, 0}, + {"/K", 0113, 0}, + {"/L", 0114, 0}, + {"/M", 0115, 0}, + {"/N", 0116, 0}, + {"/O", 0117, 0}, + + {"/P", 0120, 0}, + {"/Q", 0121, 0}, + {"/R", 0122, 0}, + {"/S", 0123, 0}, + {"/T", 0124, 0}, + {"/U", 0125, 0}, + {"/V", 0126, 0}, + {"/W", 0127, 0}, + + {"/X", 0130, 0}, + {"/Y", 0131, 0}, + {"/Z", 0132, 0}, + {"/bracketleft", 0133, 0}, + {"/backslash", 0134, 0}, + {"/bracketright", 0135, 0}, + {"/asciicircum", 0136, 0}, + {"/underscore", 0137, 0}, + + {"/quoteleft", 0140, 0}, + {"/a", 0141, 0}, + {"/b", 0142, 0}, + {"/c", 0143, 0}, + {"/d", 0144, 0}, + {"/e", 0145, 0}, + {"/f", 0146, 0}, + {"/g", 0147, 0}, + + {"/h", 0150, 0}, + {"/i", 0151, 0}, + {"/j", 0152, 0}, + {"/k", 0153, 0}, + {"/l", 0154, 0}, + {"/m", 0155, 0}, + {"/n", 0156, 0}, + {"/o", 0157, 0}, + + {"/p", 0160, 0}, + {"/q", 0161, 0}, + {"/r", 0162, 0}, + {"/s", 0163, 0}, + {"/t", 0164, 0}, + {"/u", 0165, 0}, + {"/v", 0166, 0}, + {"/w", 0167, 0}, + + {"/x", 0170, 0}, + {"/y", 0171, 0}, + {"/z", 0172, 0}, + {"/braceleft", 0173, 0}, + {"/bar", 0174, 0}, + {"/braceright", 0175, 0}, + {"/asciitilde", 0176, 0}, + {"/", 0177, 0}, /* nonstandard defs */ - "/quotedblleft", 0200, 0, - "/quotedblright", 0201, 0, - "/quotedblbase", 0202, 0, - "/quotesinglbase", 0203, 0, - "/guilsinglleft", 0204, 0, - "/guilsinglright", 0205, 0, - "/endash", 0206, 0, - "/dagger", 0207, 0, - - "/daggerdbl", 0210, 0, - "/trademark", 0211, 0, - "/bullet", 0212, 0, - "/perthousand", 0213, 0, - "/Lslash", 0214, 0, - "/OE", 0215, 0, - "/lslash", 0216, 0, - "/oe", 0217, 0, + {"/quotedblleft", 0200, 0}, + {"/quotedblright", 0201, 0}, + {"/quotedblbase", 0202, 0}, + {"/quotesinglbase", 0203, 0}, + {"/guilsinglleft", 0204, 0}, + {"/guilsinglright", 0205, 0}, + {"/endash", 0206, 0}, + {"/dagger", 0207, 0}, + + {"/daggerdbl", 0210, 0}, + {"/trademark", 0211, 0}, + {"/bullet", 0212, 0}, + {"/perthousand", 0213, 0}, + {"/Lslash", 0214, 0}, + {"/OE", 0215, 0}, + {"/lslash", 0216, 0}, + {"/oe", 0217, 0}, /* endnonstandard defs */ - "/dotlessi", 0220, 0, - "/grave", 0221, 0, - "/acute", 0222, 0, - "/circumflex", 0223, 0, - "/tilde", 0224, 0, - "/", 0225, 0, - "/breve", 0226, 0, - "/dotaccent", 0227, 0, - - "/", 0230, 0, - "/", 0231, 0, - "/ring", 0232, 0, - "/", 0233, 0, - "/", 0234, 0, - "/hungarumlaut", 0235, 0, - "/ogonek", 0236, 0, - "/caron", 0237, 0, - - "/", 0240, 0, - "/exclamdown", 0241, 0, - "/cent", 0242, 0, - "/sterling", 0243, 0, - "/florin", 0244, 0, - "/yen", 0245, 0, - "/brokenbar", 0246, 0, - "/section", 0247, 0, - - "/dieresis", 0250, 0, - "/copyright", 0251, 0, - "/ordfeminine", 0252, 0, - "/guillemotleft", 0253, 0, - "/logicalnot", 0254, 0, - "/hyphen", 0255, 0, - "/registered", 0256, 0, - "/macron", 0257, 0, - - "/degree", 0260, 0, - "/plusminus", 0261, 0, - "/twosuperior", 0262, 0, - "/threesuperior", 0263, 0, - "/acute", 0264, 0, - "/mu", 0265, 0, - "/paragraph", 0266, 0, - "/periodcentered", 0267, 0, - - "/cedilla", 0270, 0, - "/onesuperior", 0271, 0, - "/ordmasculine", 0272, 0, - "/guillemotright", 0273, 0, - "/onequarter", 0274, 0, - "/onehalf", 0275, 0, - "/threequarters", 0276, 0, - "/questiondown", 0277, 0, - - "/Agrave", 0300, 0, - "/Aacute", 0301, 0, - "/Acircumflex", 0302, 0, - "/Atilde", 0303, 0, - "/Adieresis", 0304, 0, - "/Aring", 0305, 0, - "/AE", 0306, 0, - "/Ccedilla", 0307, 0, - - "/Egrave", 0310, 0, - "/Eacute", 0311, 0, - "/Ecircumflex", 0312, 0, - "/Edieresis", 0313, 0, - "/Igrave", 0314, 0, - "/Iacute", 0315, 0, - "/Icircumflex", 0316, 0, - "/Idieresis", 0317, 0, - - "/Eth", 0320, 0, - "/Ntilde", 0321, 0, - "/Ograve", 0322, 0, - "/Oacute", 0323, 0, - "/Ocircumflex", 0324, 0, - "/Otilde", 0325, 0, - "/Odieresis", 0326, 0, - "/multiply", 0327, 0, - - "/Oslash", 0330, 0, - "/Ugrave", 0331, 0, - "/Uacute", 0332, 0, - "/Ucircumflex", 0333, 0, - "/Udieresis", 0334, 0, - "/Yacute", 0335, 0, - "/Thorn", 0336, 0, - "/germandbls", 0337, 0, - - "/agrave", 0340, 0, - "/aacute", 0341, 0, - "/acircumflex", 0342, 0, - "/atilde", 0343, 0, - "/adieresis", 0344, 0, - "/aring", 0345, 0, - "/ae", 0346, 0, - "/ccedilla", 0347, 0, - - "/egrave", 0350, 0, - "/eacute", 0351, 0, - "/ecircumflex", 0352, 0, - "/edieresis", 0353, 0, - "/igrave", 0354, 0, - "/iacute", 0355, 0, - "/icircumflex", 0356, 0, - "/idieresis", 0357, 0, - - "/eth", 0360, 0, - "/ntilde", 0361, 0, - "/ograve", 0362, 0, - "/oacute", 0363, 0, - "/ocircumflex", 0364, 0, - "/otilde", 0365, 0, - "/odieresis", 0366, 0, - "/divide", 0367, 0, - - "/oslash", 0370, 0, - "/ugrave", 0371, 0, - "/uacute", 0372, 0, - "/ucircumflex", 0373, 0, - "/udieresis", 0374, 0, - "/yacute", 0375, 0, - "/thorn", 0376, 0, - "/ydieresis", 0377, 0, + {"/dotlessi", 0220, 0}, + {"/grave", 0221, 0}, + {"/acute", 0222, 0}, + {"/circumflex", 0223, 0}, + {"/tilde", 0224, 0}, + {"/", 0225, 0}, + {"/breve", 0226, 0}, + {"/dotaccent", 0227, 0}, + + {"/", 0230, 0}, + {"/", 0231, 0}, + {"/ring", 0232, 0}, + {"/", 0233, 0}, + {"/", 0234, 0}, + {"/hungarumlaut", 0235, 0}, + {"/ogonek", 0236, 0}, + {"/caron", 0237, 0}, + + {"/", 0240, 0}, + {"/exclamdown", 0241, 0}, + {"/cent", 0242, 0}, + {"/sterling", 0243, 0}, + {"/florin", 0244, 0}, + {"/yen", 0245, 0}, + {"/brokenbar", 0246, 0}, + {"/section", 0247, 0}, + + {"/dieresis", 0250, 0}, + {"/copyright", 0251, 0}, + {"/ordfeminine", 0252, 0}, + {"/guillemotleft", 0253, 0}, + {"/logicalnot", 0254, 0}, + {"/hyphen", 0255, 0}, + {"/registered", 0256, 0}, + {"/macron", 0257, 0}, + + {"/degree", 0260, 0}, + {"/plusminus", 0261, 0}, + {"/twosuperior", 0262, 0}, + {"/threesuperior", 0263, 0}, + {"/acute", 0264, 0}, + {"/mu", 0265, 0}, + {"/paragraph", 0266, 0}, + {"/periodcentered", 0267, 0}, + + {"/cedilla", 0270, 0}, + {"/onesuperior", 0271, 0}, + {"/ordmasculine", 0272, 0}, + {"/guillemotright", 0273, 0}, + {"/onequarter", 0274, 0}, + {"/onehalf", 0275, 0}, + {"/threequarters", 0276, 0}, + {"/questiondown", 0277, 0}, + + {"/Agrave", 0300, 0}, + {"/Aacute", 0301, 0}, + {"/Acircumflex", 0302, 0}, + {"/Atilde", 0303, 0}, + {"/Adieresis", 0304, 0}, + {"/Aring", 0305, 0}, + {"/AE", 0306, 0}, + {"/Ccedilla", 0307, 0}, + + {"/Egrave", 0310, 0}, + {"/Eacute", 0311, 0}, + {"/Ecircumflex", 0312, 0}, + {"/Edieresis", 0313, 0}, + {"/Igrave", 0314, 0}, + {"/Iacute", 0315, 0}, + {"/Icircumflex", 0316, 0}, + {"/Idieresis", 0317, 0}, + + {"/Eth", 0320, 0}, + {"/Ntilde", 0321, 0}, + {"/Ograve", 0322, 0}, + {"/Oacute", 0323, 0}, + {"/Ocircumflex", 0324, 0}, + {"/Otilde", 0325, 0}, + {"/Odieresis", 0326, 0}, + {"/multiply", 0327, 0}, + + {"/Oslash", 0330, 0}, + {"/Ugrave", 0331, 0}, + {"/Uacute", 0332, 0}, + {"/Ucircumflex",0333, 0}, + {"/Udieresis", 0334, 0}, + {"/Yacute", 0335, 0}, + {"/Thorn", 0336, 0}, + {"/germandbls", 0337, 0}, + + {"/agrave", 0340, 0}, + {"/aacute", 0341, 0}, + {"/acircumflex",0342, 0}, + {"/atilde", 0343, 0}, + {"/adieresis", 0344, 0}, + {"/aring", 0345, 0}, + {"/ae", 0346, 0}, + {"/ccedilla", 0347, 0}, + + {"/egrave", 0350, 0}, + {"/eacute", 0351, 0}, + {"/ecircumflex", 0352, 0}, + {"/edieresis", 0353, 0}, + {"/igrave", 0354, 0}, + {"/iacute", 0355, 0}, + {"/icircumflex", 0356, 0}, + {"/idieresis", 0357, 0}, + + {"/eth", 0360, 0}, + {"/ntilde", 0361, 0}, + {"/ograve", 0362, 0}, + {"/oacute", 0363, 0}, + {"/ocircumflex",0364, 0}, + {"/otilde", 0365, 0}, + {"/odieresis", 0366, 0}, + {"/divide", 0367, 0}, + + {"/oslash", 0370, 0}, + {"/ugrave", 0371, 0}, + {"/uacute", 0372, 0}, + {"/ucircumflex",0373, 0}, + {"/udieresis", 0374, 0}, + {"/yacute", 0375, 0}, + {"/thorn", 0376, 0}, + {"/ydieresis", 0377, 0}, }; static short STDvsISO [][2] = { - 0341, 0306, /* AE */ - 0351, 0330, /* Oslash */ - 0302, 0222, /* acute */ - 0361, 0346, /* ae */ - 0306, 0226, /* breve */ - 0317, 0237, /* caron */ - 0313, 0270, /* cedilla */ - 0303, 0223, /* circumflex */ - 0250, 0244, /* currency */ - 0310, 0250, /* dieresis */ - 0307, 0227, /* dotaccent */ - 0365, 0220, /* dotlessi */ - 0373, 0337, /* germandbls */ - 0301, 0221, /* grave */ - 0315, 0235, /* hungarumlaut */ - 0055, 0255, /* hyphen */ - 0305, 0257, /* macron */ - 0316, 0236, /* ogenek */ - 0343, 0252, /* ordfeminine */ - 0353, 0272, /* ordmasculine */ - 0371, 0370, /* oslash */ - 0264, 0267, /* periodcentered */ - 0312, 0232, /* ring */ - 0304, 0224, /* tilde */ + {0341, 0306}, /* AE */ + {0351, 0330}, /* Oslash */ + {0302, 0222}, /* acute */ + {0361, 0346}, /* ae */ + {0306, 0226}, /* breve */ + {0317, 0237}, /* caron */ + {0313, 0270}, /* cedilla */ + {0303, 0223}, /* circumflex */ + {0250, 0244}, /* currency */ + {0310, 0250}, /* dieresis */ + {0307, 0227}, /* dotaccent */ + {0365, 0220}, /* dotlessi */ + {0373, 0337}, /* germandbls */ + {0301, 0221}, /* grave */ + {0315, 0235}, /* hungarumlaut */ + {0055, 0255}, /* hyphen */ + {0305, 0257}, /* macron */ + {0316, 0236}, /* ogenek */ + {0343, 0252}, /* ordfeminine */ + {0353, 0272}, /* ordmasculine */ + {0371, 0370}, /* oslash */ + {0264, 0267}, /* periodcentered */ + {0312, 0232}, /* ring */ + {0304, 0224}, /* tilde */ }; /* from objfont.c, rest is in lfm_s !!*/ @@ -975,7 +977,7 @@ static void applymat(float mat[][2], float *x, float *y) static void setcharlist(void) { - char *name, found; + char *name; /*found;*/ int i, j; for(i=0; i<NASCII; i++) ISOcharlist[i].prog = -1; @@ -983,11 +985,11 @@ static void setcharlist(void) for(j=0; j<my_nchars; j++) { name = my_charname[j]; if(name) { - found = 0; + /*found = 0;*/ for(i=0; i<NASCII; i++) { if(ISOcharlist[i].name && (strcmp(name,ISOcharlist[i].name) == 0)){ ISOcharlist[i].prog = j; - found = 1; + /*found = 1;*/ } } /*if (found == 0) printf("no match found for: %s\n", name);*/ @@ -1256,10 +1258,10 @@ static void subr0(void) int x1, y1; int x2, y2; int x3, y3; - int xpos, ypos, noise; + int noise; - ypos = pop(); - xpos = pop(); + pop(); /* xpos, unused */ + pop(); /* ypos, unused */ noise = pop(); if(coordpos!=7) { fprintf(stderr,"subr0: bad poop\n"); @@ -1946,7 +1948,7 @@ static VFontData *objfnt_to_vfontdata(objfnt *fnt) chardesc *cd; short *_data, *data; int a, i, count, stop, ready, meet; - short first[2], last[2]; + short first[2]={0,0}, last[2]={0,0}; struct Nurb *nu; struct BezTriple *bezt, *bez2; float scale, dx, dy; @@ -2017,7 +2019,7 @@ static VFontData *objfnt_to_vfontdata(objfnt *fnt) nu->type= CU_BEZIER+CU_2D; nu->pntsu = count; nu->resolu= 8; - nu->flagu= 1; + nu->flagu= CU_CYCLIC; nu->bezt = bezt; stop = 0; diff --git a/source/blender/blenlib/intern/rand.c b/source/blender/blenlib/intern/rand.c index ccc478203fe..c484a307393 100644 --- a/source/blender/blenlib/intern/rand.c +++ b/source/blender/blenlib/intern/rand.c @@ -81,6 +81,16 @@ void rng_seed(RNG *rng, unsigned int seed) { rng->X= (((r_uint64) seed)<<16) | LOWSEED; } +void rng_srandom(RNG *rng, unsigned int seed) { + extern unsigned char hash[]; // noise.c + + rng_seed(rng, seed + hash[seed & 255]); + seed= rng_getInt(rng); + rng_seed(rng, seed + hash[seed & 255]); + seed= rng_getInt(rng); + rng_seed(rng, seed + hash[seed & 255]); +} + int rng_getInt(RNG *rng) { rng->X= (MULTIPLIER*rng->X + ADDEND)&MASK; return (int) (rng->X>>17); @@ -132,13 +142,7 @@ void BLI_srand(unsigned int seed) { /* using hash table to create better seed */ void BLI_srandom(unsigned int seed) { - extern unsigned char hash[]; // noise.c - - rng_seed(&theBLI_rng, seed + hash[seed & 255]); - seed= rng_getInt(&theBLI_rng); - rng_seed(&theBLI_rng, seed + hash[seed & 255]); - seed= rng_getInt(&theBLI_rng); - rng_seed(&theBLI_rng, seed + hash[seed & 255]); + rng_srandom(&theBLI_rng, seed); } int BLI_rand(void) { diff --git a/source/blender/blenlib/intern/storage.c b/source/blender/blenlib/intern/storage.c index 6e64a98af2a..ca7a376d3a2 100644 --- a/source/blender/blenlib/intern/storage.c +++ b/source/blender/blenlib/intern/storage.c @@ -47,7 +47,9 @@ #include <time.h> #include <sys/stat.h> -#if !defined(linux) && (defined(__sgi) || defined(__sun__) || defined(__sun) || defined(__sparc) || defined(__sparc__)) +#if defined (__sun__) || defined (__sun) +#include <sys/statvfs.h> /* Other modern unix os's should probably use this also */ +#elif !defined(__FreeBSD__) && !defined(linux) && (defined(__sgi) || defined(__sparc) || defined(__sparc__)) #include <sys/statfs.h> #endif @@ -176,7 +178,12 @@ double BLI_diskfree(char *dir) return (double) (freec*bytesps*sectorspc); #else + +#if defined (__sun__) || defined (__sun) + struct statvfs disk; +#else struct statfs disk; +#endif char name[FILE_MAXDIR],*slash; int len = strlen(dir); @@ -196,12 +203,12 @@ double BLI_diskfree(char *dir) #ifdef __BeOS return -1; #endif -#if !defined(linux) && (defined (__sgi) || defined (__sun__) || defined (__sun) || defined(__sparc) || defined(__sparc__)) - if (statfs(name, &disk, sizeof(struct statfs), 0)){ - /* printf("diskfree: Couldn't get information about %s.\n",dir); */ - return(-1); - } +#if defined (__sun__) || defined (__sun) + if (statvfs(name, &disk)) return(-1); +#elif !defined(__FreeBSD__) && !defined(linux) && (defined (__sgi) || defined(__sparc) || defined(__sparc__)) + /* WARNING - This may not be supported by geeneric unix os's - Campbell */ + if (statfs(name, &disk, sizeof(struct statfs), 0)) return(-1); #endif return ( ((double) disk.f_bsize) * ((double) disk.f_bfree)); @@ -326,11 +333,11 @@ void BLI_adddirstrings() char size[250]; static char * types[8] = {"---", "--x", "-w-", "-wx", "r--", "r-x", "rw-", "rwx"}; int num, mode; - int num1, num2, num3, num4; + off_t num1, num2, num3, num4, num5; #ifdef WIN32 __int64 st_size; #else - long long st_size; + off_t st_size; #endif struct direntry * file; @@ -392,7 +399,7 @@ void BLI_adddirstrings() * will buy us some time until files get bigger than 4GB or until * everyone starts using __USE_FILE_OFFSET64 or equivalent. */ - st_size= (unsigned int)files[num].s.st_size; + st_size= (off_t)files[num].s.st_size; num1= st_size % 1000; num2= st_size/1000; @@ -401,11 +408,15 @@ void BLI_adddirstrings() num3= num3 % 1000; num4= st_size/(1000*1000*1000); num4= num4 % 1000; - - if(num4) sprintf(files[num].size, "%3d %03d %03d %03d", num4, num3, num2, num1); - else if(num3) sprintf(files[num].size, "%7d %03d %03d", num3, num2, num1); - else if(num2) sprintf(files[num].size, "%11d %03d", num2, num1); - else if(num1) sprintf(files[num].size, "%15d", num1); + num5= st_size/(1000000000000LL); + num5= num5 % 1000; + + if(num5) + sprintf(files[num].size, "%1d %03d %03d %03d K", (int)num5, (int)num4, (int)num3, (int)num2); + else if(num4) sprintf(files[num].size, "%3d %03d %03d %03d", (int)num4, (int)num3, (int)num2, (int)num1); + else if(num3) sprintf(files[num].size, "%7d %03d %03d", (int)num3, (int)num2, (int)num1); + else if(num2) sprintf(files[num].size, "%11d %03d", (int)num2, (int)num1); + else if(num1) sprintf(files[num].size, "%15d", (int)num1); else sprintf(files[num].size, "0"); strftime(datum, 32, "%d-%b-%y %H:%M", tm); @@ -469,6 +480,17 @@ int BLI_filesize(int file) return (buf.st_size); } +int BLI_filepathsize(const char *path) +{ + int size, file = open(path, O_BINARY|O_RDONLY); + + if (file <= 0) + return -1; + + size = BLI_filesize(file); + close(file); + return size; +} int BLI_exist(char *name) diff --git a/source/blender/blenlib/intern/threads.c b/source/blender/blenlib/intern/threads.c index 1f05070b034..9df8bbc81e3 100644 --- a/source/blender/blenlib/intern/threads.c +++ b/source/blender/blenlib/intern/threads.c @@ -1,6 +1,6 @@ /** * - * $Id: + * $Id$ * * ***** BEGIN GPL LICENSE BLOCK ***** * @@ -38,6 +38,17 @@ #include "BLI_blenlib.h" #include "BLI_threads.h" +#include "PIL_time.h" + +/* for checking system threads - BLI_system_thread_count */ +#ifdef WIN32 +#include "Windows.h" +#elif defined(__APPLE__) +#include <sys/types.h> +#include <sys/sysctl.h> +#else +#include <unistd.h> +#endif /* ********** basic thread control API ************ @@ -190,6 +201,34 @@ void BLI_remove_thread(ListBase *threadbase, void *callerdata) } } +void BLI_remove_thread_index(ListBase *threadbase, int index) +{ + ThreadSlot *tslot; + int counter=0; + + for(tslot = threadbase->first; tslot; tslot = tslot->next, counter++) { + if (counter == index && tslot->avail == 0) { + tslot->callerdata = NULL; + pthread_join(tslot->pthread, NULL); + tslot->avail = 1; + break; + } + } +} + +void BLI_remove_threads(ListBase *threadbase) +{ + ThreadSlot *tslot; + + for(tslot = threadbase->first; tslot; tslot = tslot->next) { + if (tslot->avail == 0) { + tslot->callerdata = NULL; + pthread_join(tslot->pthread, NULL); + tslot->avail = 1; + } + } +} + void BLI_end_threads(ListBase *threadbase) { ThreadSlot *tslot; @@ -224,4 +263,136 @@ void BLI_unlock_thread(int type) pthread_mutex_unlock(&_custom1_lock); } +/* how many threads are native on this system? */ +int BLI_system_thread_count( void ) +{ + int t; +#ifdef WIN32 + SYSTEM_INFO info; + GetSystemInfo(&info); + t = (int) info.dwNumberOfProcessors; +#else +# ifdef __APPLE__ + int mib[2]; + size_t len; + + mib[0] = CTL_HW; + mib[1] = HW_NCPU; + len = sizeof(t); + sysctl(mib, 2, &t, &len, NULL, 0); +# elif defined(__sgi) + t = sysconf(_SC_NPROC_ONLN); +# else + t = (int)sysconf(_SC_NPROCESSORS_ONLN); +# endif +#endif + + if (t>RE_MAX_THREAD) + return RE_MAX_THREAD; + if (t<1) + return 1; + + return t; +} + +/* ************************************************ */ + +typedef struct ThreadedWorker { + ListBase threadbase; + void *(*work_fnct)(void *); + char busy[RE_MAX_THREAD]; + int total; + int sleep_time; +} ThreadedWorker; + +typedef struct WorkParam { + ThreadedWorker *worker; + void *param; + int index; +} WorkParam; + +void *exec_work_fnct(void *v_param) +{ + WorkParam *p = (WorkParam*)v_param; + void *value; + + value = p->worker->work_fnct(p->param); + + p->worker->busy[p->index] = 0; + MEM_freeN(p); + + return value; +} + +ThreadedWorker *BLI_create_worker(void *(*do_thread)(void *), int tot, int sleep_time) +{ + ThreadedWorker *worker; + + worker = MEM_callocN(sizeof(ThreadedWorker), "threadedworker"); + + if (tot > RE_MAX_THREAD) + { + tot = RE_MAX_THREAD; + } + else if (tot < 1) + { + tot= 1; + } + + worker->total = tot; + worker->work_fnct = do_thread; + + BLI_init_threads(&worker->threadbase, exec_work_fnct, tot); + + return worker; +} + +void BLI_end_worker(ThreadedWorker *worker) +{ + BLI_remove_threads(&worker->threadbase); +} + +void BLI_destroy_worker(ThreadedWorker *worker) +{ + BLI_end_worker(worker); + BLI_freelistN(&worker->threadbase); + MEM_freeN(worker); +} + +void BLI_insert_work(ThreadedWorker *worker, void *param) +{ + WorkParam *p = MEM_callocN(sizeof(WorkParam), "workparam"); + int index; + + if (BLI_available_threads(&worker->threadbase) == 0) + { + index = worker->total; + while(index == worker->total) + { + PIL_sleep_ms(worker->sleep_time); + + for (index = 0; index < worker->total; index++) + { + if (worker->busy[index] == 0) + { + BLI_remove_thread_index(&worker->threadbase, index); + break; + } + } + } + } + else + { + index = BLI_available_thread_index(&worker->threadbase); + } + + worker->busy[index] = 1; + + p->param = param; + p->index = index; + p->worker = worker; + + BLI_insert_thread(&worker->threadbase, p); +} + /* eof */ diff --git a/source/blender/blenlib/intern/util.c b/source/blender/blenlib/intern/util.c index 97ed881fcc8..d3cfdf6417c 100644 --- a/source/blender/blenlib/intern/util.c +++ b/source/blender/blenlib/intern/util.c @@ -38,11 +38,14 @@ #include <string.h> #include <stdlib.h> #include <stdarg.h> +#include <math.h> /* for log10 */ #include "MEM_guardedalloc.h" -#include "BLI_blenlib.h" #include "DNA_listBase.h" +#include "DNA_userdef_types.h" + +#include "BLI_blenlib.h" #include "BLI_storage.h" #include "BLI_storage_types.h" #include "BLI_dynamiclist.h" @@ -62,6 +65,14 @@ #endif #ifdef WIN32 + +#ifdef _WIN32_IE +#undef _WIN32_IE +#endif +#define _WIN32_IE 0x0501 +#include <windows.h> +#include <shlobj.h> + #include "BLI_winstuff.h" /* for duplicate_defgroup */ @@ -81,6 +92,10 @@ #include <CoreFoundation/CoreFoundation.h> #endif +#ifdef __linux__ +#include "binreloc.h" +#endif + /* local */ static int add_win32_extension(char *name); @@ -213,6 +228,79 @@ void BLI_newname(char *name, int add) BLI_stringenc(name, head, tail, digits, pic); } +/* little helper macro for BLI_uniquename */ +#ifndef GIVE_STRADDR + #define GIVE_STRADDR(data, offset) ( ((char *)data) + offset ) +#endif + +/* Generic function to set a unique name. It is only designed to be used in situations + * where the name is part of the struct, and also that the name is at most 128 chars long. + * + * For places where this is used, see constraint.c for example... + * + * name_offs: should be calculated using offsetof(structname, membername) macro from stddef.h + * len: maximum length of string (to prevent overflows, etc.) + * defname: the name that should be used by default if none is specified already + */ +void BLI_uniquename(ListBase *list, void *vlink, char defname[], short name_offs, short len) +{ + Link *link; + char tempname[128]; + int number = 1, exists = 0; + char *dot; + + /* Make sure length can be handled */ + if ((len < 0) || (len > 128)) + return; + + /* See if we are given an empty string */ + if (ELEM(NULL, vlink, defname)) + return; + + if (GIVE_STRADDR(vlink, name_offs) == '\0') { + /* give it default name first */ + BLI_strncpy(GIVE_STRADDR(vlink, name_offs), defname, len); + } + + /* See if we even need to do this */ + if (list == NULL) + return; + + for (link = list->first; link; link= link->next) { + if (link != vlink) { + if (!strcmp(GIVE_STRADDR(link, name_offs), GIVE_STRADDR(vlink, name_offs))) { + exists = 1; + break; + } + } + } + if (exists == 0) + return; + + /* Strip off the suffix */ + dot = strchr(GIVE_STRADDR(vlink, name_offs), '.'); + if (dot) + *dot=0; + + for (number = 1; number <= 999; number++) { + BLI_snprintf(tempname, 128, "%s.%03d", GIVE_STRADDR(vlink, name_offs), number); + + exists = 0; + for (link= list->first; link; link= link->next) { + if (vlink != link) { + if (!strcmp(GIVE_STRADDR(link, name_offs), tempname)) { + exists = 1; + break; + } + } + } + if (exists == 0) { + BLI_strncpy(GIVE_STRADDR(vlink, name_offs), tempname, len); + return; + } + } +} + void BLI_addhead(ListBase *listbase, void *vlink) { @@ -787,17 +875,45 @@ int BLI_strcaseeq(char *a, char *b) { * take the dir name, make it absolute, and clean it up, replacing * excess file entry stuff (like /tmp/../tmp/../) * note that dir isn't protected for max string names... + * + * If relbase is NULL then its ignored */ void BLI_cleanup_dir(const char *relabase, char *dir) { + BLI_cleanup_file(relabase, dir); + BLI_add_slash(dir); + +} + +void BLI_cleanup_file(const char *relabase, char *dir) +{ short a; char *start, *eind; + if (relabase) { + BLI_convertstringcode(dir, relabase); + } else { + if (dir[0]=='/' && dir[1]=='/') { + if (dir[2]== '\0') { + return; /* path is "//" - cant clean it */ + } + dir = dir+2; /* skip the first // */ + } + } - BLI_convertstringcode(dir, relabase, 0); + /* Note + * memmove( start, eind, strlen(eind)+1 ); + * is the same as + * strcpy( start, eind ); + * except strcpy should not be used because there is overlap, + * so use memmove's slightly more obscure syntax - Campbell + */ #ifdef WIN32 - if(dir[0]=='.') { /* happens for example in FILE_MAIN */ + + /* Note, this should really be moved to the file selector, + * since this function is used in many areas */ + if(strcmp(dir, ".")==0) { /* happens for example in FILE_MAIN */ get_default_root(dir); return; } @@ -809,17 +925,21 @@ void BLI_cleanup_dir(const char *relabase, char *dir) if (dir[a] == '\\') break; a--; } - strcpy(dir+a,eind); + if (a<0) { + break; + } else { + memmove( dir+a, eind, strlen(eind)+1 ); + } } while ( (start = strstr(dir,"\\.\\")) ){ eind = start + strlen("\\.\\") - 1; - strcpy(start,eind); + memmove( start, eind, strlen(eind)+1 ); } while ( (start = strstr(dir,"\\\\" )) ){ eind = start + strlen("\\\\") - 1; - strcpy(start,eind); + memmove( start, eind, strlen(eind)+1 ); } if((a = strlen(dir))){ /* remove the '\\' at the end */ @@ -828,9 +948,7 @@ void BLI_cleanup_dir(const char *relabase, char *dir) dir[a] = 0; } } - - strcat(dir, "\\"); -#else +#else if(dir[0]=='.') { /* happens, for example in FILE_MAIN */ dir[0]= '/'; dir[1]= 0; @@ -844,17 +962,21 @@ void BLI_cleanup_dir(const char *relabase, char *dir) if (dir[a] == '/') break; a--; } - strcpy(dir+a,eind); + if (a<0) { + break; + } else { + memmove( dir+a, eind, strlen(eind)+1 ); + } } while ( (start = strstr(dir,"/./")) ){ eind = start + strlen("/./") - 1; - strcpy(start,eind); + memmove( start, eind, strlen(eind)+1 ); } while ( (start = strstr(dir,"//" )) ){ eind = start + strlen("//") - 1; - strcpy(start,eind); + memmove( start, eind, strlen(eind)+1 ); } if( (a = strlen(dir)) ){ /* remove all '/' at the end */ @@ -864,8 +986,6 @@ void BLI_cleanup_dir(const char *relabase, char *dir) if (a<=0) break; } } - - strcat(dir, "/"); #endif } @@ -877,7 +997,7 @@ void BLI_makestringcode(const char *relfile, char *file) char * lslash; char temp[FILE_MAXDIR+FILE_MAXFILE]; char res[FILE_MAXDIR+FILE_MAXFILE]; - + /* if file is already relative, bail out */ if(file[0]=='/' && file[1]=='/') return; @@ -909,7 +1029,11 @@ void BLI_makestringcode(const char *relfile, char *file) BLI_char_switch(temp, '\\', '/'); BLI_char_switch(file, '\\', '/'); - + + /* remove /./ which confuse the following slash counting... */ + BLI_cleanup_file(NULL, file); + BLI_cleanup_file(NULL, temp); + /* the last slash in the file indicates where the path part ends */ lslash = BLI_last_slash(temp); @@ -954,17 +1078,104 @@ void BLI_makestringcode(const char *relfile, char *file) } } -int BLI_convertstringcode(char *path, const char *basepath, int framenum) +int BLI_parent_dir(char *path) { - int len, wasrelative; - char tmp[FILE_MAXDIR+FILE_MAXFILE]; - char base[FILE_MAXDIR]; - char vol[3] = {'\0', '\0', '\0'}; +#ifdef WIN32 + static char *parent_dir="..\\"; +#else + static char *parent_dir="../"; +#endif + char tmp[FILE_MAXDIR+FILE_MAXFILE+4]; + BLI_strncpy(tmp, path, sizeof(tmp)); + BLI_add_slash(tmp); + strcat(tmp, parent_dir); + BLI_cleanup_dir(NULL, tmp); + + if (!BLI_testextensie(tmp, parent_dir)) { + BLI_strncpy(path, tmp, sizeof(tmp)); + return 1; + } else { + return 0; + } +} + +int BLI_convertstringframe(char *path, int frame) +{ + int ch_sta, ch_end, i; + /* Insert current frame: file### -> file001 */ + ch_sta = ch_end = 0; + for (i = 0; path[i] != '\0'; i++) { + if (path[i] == '\\' || path[i] == '/') { + ch_end = 0; /* this is a directory name, dont use any hashes we found */ + } else if (path[i] == '#') { + ch_sta = i; + ch_end = ch_sta+1; + while (path[ch_end] == '#') { + ch_end++; + } + i = ch_end-1; /* keep searching */ + + /* dont break, there may be a slash after this that invalidates the previous #'s */ + } + } + if (ch_end) { /* warning, ch_end is the last # +1 */ + /* Add the frame number? */ + short numlen, hashlen; + char tmp[FILE_MAX]; + + char format[16]; /* 6 is realistically the maxframe (300000), so 8 should be enough, but 16 to be safe. */ + if (((ch_end-1)-ch_sta) >= 16) { + ch_end = ch_sta+15; /* disallow values longer then 'format' can hold */ + } + + strcpy(tmp, path); + + numlen = 1 + (int)log10((double)frame); /* this is the number of chars in the number */ + hashlen = ch_end - ch_sta; + + sprintf(format, "%d", frame); + + if (numlen==hashlen) { /* simple case */ + memcpy(tmp+ch_sta, format, numlen); + } else if (numlen < hashlen) { + memcpy(tmp+ch_sta + (hashlen-numlen), format, numlen); /*dont copy the string terminator */ + memset(tmp+ch_sta, '0', hashlen-numlen); + } else { + /* number is longer then number of #'s */ + if (tmp[ch_end] == '\0') { /* hashes are last, no need to move any string*/ + /* bad juju - not testing string length here :/ */ + memcpy(tmp+ch_sta, format, numlen+1); /* add 1 to get the string terminator \0 */ + } else { + /* we need to move the end characters, reuse i */ + int j; + + i = strlen(tmp); /* +1 to copy the string terminator */ + j = i + (numlen-hashlen); /* from/to */ + + while (i >= ch_end) { + tmp[j] = tmp[i]; + i--; + j--; + } + memcpy(tmp + ch_sta, format, numlen); + } + } + strcpy(path, tmp); + return 1; + } + return 0; +} - BLI_strncpy(vol, path, 3); - wasrelative= (strncmp(vol, "//", 2)==0); +int BLI_convertstringcode(char *path, const char *basepath) +{ + int wasrelative = (strncmp(path, "//", 2)==0); + char tmp[FILE_MAX]; + char base[FILE_MAX]; #ifdef WIN32 + char vol[3] = {'\0', '\0', '\0'}; + + BLI_strncpy(vol, path, 3); /* we are checking here if we have an absolute path that is not in the current blend file as a lib main - we are basically checking for the case that a UNIX root '/' is passed. @@ -979,13 +1190,29 @@ int BLI_convertstringcode(char *path, const char *basepath, int framenum) strcat(tmp, p); } else { - strcpy(tmp, path); + BLI_strncpy(tmp, path, FILE_MAX); } #else - strcpy(tmp, path); + BLI_strncpy(tmp, path, FILE_MAX); + + /* Check for loading a windows path on a posix system + * in this case, there is no use in trying C:/ since it + * will never exist on a unix os. + * + * Add a / prefix and lowercase the driveletter, remove the : + * C:\foo.JPG -> /c/foo.JPG */ + + if (isalpha(tmp[0]) && tmp[1] == ':' && (tmp[2]=='\\' || tmp[2]=='/') ) { + tmp[1] = tolower(tmp[0]); /* replace ':' with driveletter */ + tmp[0] = '/'; + /* '\' the slash will be converted later */ + } + #endif - strcpy(base, basepath); + BLI_strncpy(base, basepath, FILE_MAX); + + BLI_cleanup_file(NULL, base); /* push slashes into unix mode - strings entering this part are potentially messed up: having both back- and forward slashes. @@ -996,28 +1223,33 @@ int BLI_convertstringcode(char *path, const char *basepath, int framenum) BLI_char_switch(tmp, '\\', '/'); BLI_char_switch(base, '\\', '/'); - if (tmp[0] == '/' && tmp[1] == '/') { - char *filepart= BLI_strdup(tmp+2); /* skip code */ + /* Paths starting with // will get the blend file as their base, + * this isnt standard in any os but is uesed in blender all over the place */ + if (wasrelative) { char *lslash= BLI_last_slash(base); - if (lslash) { int baselen= (int) (lslash-base) + 1; - + /* use path for for temp storage here, we copy back over it right away */ + BLI_strncpy(path, tmp+2, FILE_MAX); + memcpy(tmp, base, baselen); - strcpy(tmp+baselen, filepart); + strcpy(tmp+baselen, path); + strcpy(path, tmp); } else { - strcpy(tmp, filepart); + strcpy(path, tmp+2); } - - MEM_freeN(filepart); + } else { + strcpy(path, tmp); } - - len= strlen(tmp); - if(len && tmp[len-1]=='#') { - sprintf(tmp+len-1, "%04d", framenum); + + if (path[0]!='\0') { + if ( path[strlen(path)-1]=='/') { + BLI_cleanup_dir(NULL, path); + } else { + BLI_cleanup_file(NULL, path); + } } - - strcpy(path, tmp); + #ifdef WIN32 /* skip first two chars, which in case of absolute path will be drive:/blabla and @@ -1027,11 +1259,54 @@ int BLI_convertstringcode(char *path, const char *basepath, int framenum) */ BLI_char_switch(path+2, '/', '\\'); #endif + + return wasrelative; +} + +/* + * Should only be done with command line paths. + * this is NOT somthing blenders internal paths support like the // prefix + */ +int BLI_convertstringcwd(char *path) +{ + int wasrelative = 1; + int filelen = strlen(path); + +#ifdef WIN32 + if (filelen >= 3 && path[1] == ':' && (path[2] == '\\' || path[2] == '/')) + wasrelative = 0; +#else + if (filelen >= 2 && path[0] == '/') + wasrelative = 0; +#endif + + if (wasrelative==1) { + char cwd[FILE_MAXDIR + FILE_MAXFILE]; + BLI_getwdN(cwd); /* incase the full path to the blend isnt used */ + + if (cwd[0] == '\0') { + printf( "Could not get the current working directory - $PWD for an unknown reason."); + } else { + /* uses the blend path relative to cwd important for loading relative linked files. + * + * cwd should contain c:\ etc on win32 so the relbase can be NULL + * relbase being NULL also prevents // being misunderstood as relative to the current + * blend file which isnt a feature we want to use in this case since were dealing + * with a path from the command line, rather then from inside Blender */ + + char origpath[FILE_MAXDIR + FILE_MAXFILE]; + BLI_strncpy(origpath, path, FILE_MAXDIR + FILE_MAXFILE); + + BLI_make_file_string(NULL, path, cwd, origpath); + } + } + return wasrelative; } -/* copy di to fi without directory only */ + +/* copy di to fi, filename only */ void BLI_splitdirstring(char *di, char *fi) { char *lslash= BLI_last_slash(di); @@ -1055,6 +1330,8 @@ char *BLI_gethome(void) { #else /* Windows */ char * ret; static char dir[512]; + static char appdatapath[MAXPATHLEN]; + HRESULT hResult; /* Check for %HOME% env var */ @@ -1076,9 +1353,36 @@ char *BLI_gethome(void) { /* add user profile support for WIN 2K / NT */ + hResult = SHGetFolderPath(NULL, CSIDL_APPDATA, NULL, SHGFP_TYPE_CURRENT, appdatapath); + + if (hResult == S_OK) + { + if (BLI_exists(appdatapath)) { /* from fop, also below... */ + sprintf(dir, "%s\\Blender Foundation\\Blender", appdatapath); + BLI_recurdir_fileops(dir); + if (BLI_exists(dir)) { + strcat(dir,"\\.blender"); + if(BLI_exists(dir)) return(dir); + } + } + hResult = SHGetFolderPath(NULL, CSIDL_COMMON_APPDATA, NULL, SHGFP_TYPE_CURRENT, appdatapath); + if (hResult == S_OK) + { + if (BLI_exists(appdatapath)) + { /* from fop, also below... */ + sprintf(dir, "%s\\Blender Foundation\\Blender", appdatapath); + BLI_recurdir_fileops(dir); + if (BLI_exists(dir)) { + strcat(dir,"\\.blender"); + if(BLI_exists(dir)) return(dir); + } + } + } + } +#if 0 ret = getenv("USERPROFILE"); if (ret) { - if (BLI_exists(ret)) { /* from fop, also below... */ + if (BLI_exists(ret)) { /* from fop, also below... */ sprintf(dir, "%s\\Application Data\\Blender Foundation\\Blender", ret); BLI_recurdir_fileops(dir); if (BLI_exists(dir)) { @@ -1087,6 +1391,7 @@ char *BLI_gethome(void) { } } } +#endif /* Saving in the Windows dir is less than desirable. @@ -1276,9 +1581,42 @@ int BLI_testextensie(const char *str, const char *ext) return (retval); } +/* + * This is a simple version of BLI_split_dirfile that has the following advantages... + * + * Converts "/foo/bar.txt" to "/foo/" and "bar.txt" + * - wont change 'string' + * - wont create any directories + * - dosnt use CWD, or deal with relative paths. + * - Only fill's in *dir and *file when they are non NULL + * */ +void BLI_split_dirfile_basic(const char *string, char *dir, char *file) +{ + int lslash=0, i = 0; + for (i=0; string[i]!='\0'; i++) { + if (string[i]=='\\' || string[i]=='/') + lslash = i+1; + } + if (dir) { + if (lslash) { + BLI_strncpy( dir, string, lslash+1); /* +1 to include the slash and the last char */ + } else { + dir[0] = '\0'; + } + } + + if (file) { + strcpy( file, string+lslash); + } +} -void BLI_split_dirfile(const char *string, char *dir, char *file) +/* Warning, + * - May modify 'string' variable + * - May create the directory if it dosnt exist + * if this is not needed use BLI_split_dirfile_basic(...) + */ +void BLI_split_dirfile(char *string, char *dir, char *file) { int a; #ifdef WIN32 @@ -1400,12 +1738,20 @@ void BLI_join_dirfile(char *string, const char *dir, const char *file) int sl_dir = strlen(dir); BLI_strncpy(string, dir, FILE_MAX); if (sl_dir > FILE_MAX-1) sl_dir = FILE_MAX-1; + + /* only add seperator if needed */ #ifdef WIN32 - string[sl_dir] = '\\'; + if (string[sl_dir-1] != '\\') { + string[sl_dir] = '\\'; + sl_dir++; + } #else - string[sl_dir] = '/'; + if (string[sl_dir-1] != '/') { + string[sl_dir] = '/'; + sl_dir++; + } #endif - sl_dir++; + if (sl_dir <FILE_MAX) { BLI_strncpy(string + sl_dir, file, FILE_MAX-sl_dir); } @@ -1452,10 +1798,10 @@ static int add_win32_extension(char *name) return (retval); } -void BLI_where_am_i(char *fullname, char *name) +void BLI_where_am_i(char *fullname, const char *name) { char filename[FILE_MAXDIR+FILE_MAXFILE]; - char *path, *temp; + char *path = NULL, *temp; int len; #ifdef _WIN32 char *seperator = ";"; @@ -1465,6 +1811,18 @@ void BLI_where_am_i(char *fullname, char *name) char *slash = "/"; #endif + +#ifdef __linux__ + /* linux uses binreloc since argv[0] is not relyable, call br_init( NULL ) first */ + path = br_find_exe( NULL ); + if (path) { + strcpy(fullname, path); + free(path); + return; + } +#endif + + /* unix and non linux */ if (name && fullname && strlen(name)) { strcpy(fullname, name); if (name[0] == '.') { @@ -1525,6 +1883,47 @@ void BLI_where_am_i(char *fullname, char *name) } } +void BLI_where_is_temp(char *fullname, int usertemp) +{ + fullname[0] = '\0'; + + if (usertemp && BLI_exists(U.tempdir)) { + strcpy(fullname, U.tempdir); + } + + +#ifdef WIN32 + if (fullname[0] == '\0') { + char *tmp = getenv("TEMP"); /* Windows */ + if (tmp && BLI_exists(tmp)) { + strcpy(fullname, tmp); + } + } +#else + /* Other OS's - Try TMP and TMPDIR */ + if (fullname[0] == '\0') { + char *tmp = getenv("TMP"); + if (tmp && BLI_exists(tmp)) { + strcpy(fullname, tmp); + } + } + + if (fullname[0] == '\0') { + char *tmp = getenv("TMPDIR"); + if (tmp && BLI_exists(tmp)) { + strcpy(fullname, tmp); + } + } +#endif + + if (fullname[0] == '\0') { + strcpy(fullname, "/tmp/"); + } else { + /* add a trailing slash if needed */ + BLI_add_slash(fullname); + } +} + /* * returns absolute path to the app bundle * only useful on OS X @@ -1608,7 +2007,7 @@ int BLI_strncasecmp(const char *s1, const char *s2, int n) { #include "iconv.h" #include "localcharset.h" -void BLI_string_to_utf8(char *original, char *utf_8, char *code) +void BLI_string_to_utf8(char *original, char *utf_8, const char *code) { size_t inbytesleft=strlen(original); size_t outbytesleft=512; @@ -1666,7 +2065,7 @@ void BLI_timestr(double _time, char *str) int BLI_int_from_pointer(void *poin) { - long lval= (long)poin; + intptr_t lval= (intptr_t)poin; return (int)(lval>>3); } @@ -1674,17 +2073,17 @@ int BLI_int_from_pointer(void *poin) void *BLI_pointer_from_int(int val) { static int firsttime= 1; - static long basevalue= 0; + static intptr_t basevalue= 0; if(firsttime) { void *poin= malloc(10000); - basevalue= (long)poin; + basevalue= (intptr_t)poin; basevalue &= ~PMASK; printf("base: %d pointer %p\n", basevalue, poin); /* debug */ firsttime= 0; free(poin); } - return (void *)(basevalue | (((long)val)<<3)); + return (void *)(basevalue | (((intptr_t)val)<<3)); } #else diff --git a/source/blender/blenlib/intern/winstuff.c b/source/blender/blenlib/intern/winstuff.c index ace677e6045..666a54b54cc 100644 --- a/source/blender/blenlib/intern/winstuff.c +++ b/source/blender/blenlib/intern/winstuff.c @@ -196,6 +196,27 @@ void get_default_root(char* root) { } } +int check_file_chars(char *filename) +{ + char *p = filename; + while (*p) { + switch (*p) { + case ':': + case '?': + case '*': + case '|': + case '\\': + case '/': + case '\"': + return 0; + break; + } + + p++; + } + return 1; +} + #else static void BLI_WINSTUFF_C_IS_EMPTY_FOR_UNIX(void) |