diff options
Diffstat (limited to 'source/blender/blenlib/intern')
26 files changed, 1317 insertions, 921 deletions
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index 6747e5c4e7e..c87b60f08db 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -28,7 +28,8 @@ /** \file blender/blenlib/intern/BLI_ghash.c * \ingroup bli * - * A general (pointer -> pointer) hash table ADT + * A general (pointer -> pointer) chaining hash table + * for 'Abstract Data Types' (known as an ADT Hash Table). * * \note edgehash.c is based on this, make sure they stay in sync. */ diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c index 55dee4e8677..66dfa87b7b9 100644 --- a/source/blender/blenlib/intern/BLI_heap.c +++ b/source/blender/blenlib/intern/BLI_heap.c @@ -49,7 +49,6 @@ struct Heap { unsigned int bufsize; MemArena *arena; HeapNode *freenodes; - HeapNode *nodes; HeapNode **tree; }; @@ -139,9 +138,9 @@ Heap *BLI_heap_new(void) void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) { - unsigned int i; - if (ptrfreefp) { + unsigned int i; + for (i = 0; i < heap->size; i++) { ptrfreefp(heap->tree[i]->ptr); } @@ -152,6 +151,21 @@ void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) MEM_freeN(heap); } +void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp) +{ + if (ptrfreefp) { + unsigned int i; + + for (i = 0; i < heap->size; i++) { + ptrfreefp(heap->tree[i]->ptr); + } + } + + heap->size = 0; + BLI_memarena_clear(heap->arena); + heap->freenodes = NULL; +} + HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr) { HeapNode *node; @@ -163,7 +177,7 @@ HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr) if (heap->freenodes) { node = heap->freenodes; - heap->freenodes = (HeapNode *)(((HeapNode *)heap->freenodes)->ptr); + heap->freenodes = heap->freenodes->ptr; } else { node = (HeapNode *)BLI_memarena_alloc(heap->arena, sizeof(*node)); @@ -206,13 +220,8 @@ void *BLI_heap_popmin(Heap *heap) heap->tree[0]->ptr = heap->freenodes; heap->freenodes = heap->tree[0]; - if (UNLIKELY(heap->size == 1)) { - heap->size--; - } - else { - heap_swap(heap, 0, heap->size - 1); - heap->size--; - + if (--heap->size) { + heap_swap(heap, 0, heap->size); heap_down(heap, 0); } diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index d28215ee8ed..b76b925e6cc 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -986,7 +986,7 @@ bool BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const /* check if index exists */ if (index > tree->totleaf) - return 0; + return false; node = tree->nodearray + index; @@ -1001,7 +1001,7 @@ bool BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const node->bv[(2 * axis_iter) + 1] += tree->epsilon; /* maximum */ } - return 1; + return true; } /* call BLI_bvhtree_update_node() first for every node/point/triangle */ diff --git a/source/blender/blenlib/intern/BLI_linklist.c b/source/blender/blenlib/intern/BLI_linklist.c index a0b61e7945c..6b79cf97e86 100644 --- a/source/blender/blenlib/intern/BLI_linklist.c +++ b/source/blender/blenlib/intern/BLI_linklist.c @@ -32,6 +32,8 @@ #include "MEM_guardedalloc.h" + +#include "BLI_utildefines.h" #include "BLI_linklist.h" #include "BLI_memarena.h" #include "BLI_mempool.h" @@ -96,7 +98,7 @@ void BLI_linklist_prepend_nlink(LinkNode **listp, void *ptr, LinkNode *nlink) void BLI_linklist_prepend(LinkNode **listp, void *ptr) { - LinkNode *nlink = MEM_mallocN(sizeof(*nlink), "nlink"); + LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__); BLI_linklist_prepend_nlink(listp, ptr, nlink); } @@ -135,7 +137,7 @@ void BLI_linklist_append_nlink(LinkNode **listp, void *ptr, LinkNode *nlink) void BLI_linklist_append(LinkNode **listp, void *ptr) { - LinkNode *nlink = MEM_mallocN(sizeof(*nlink), "nlink"); + LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__); BLI_linklist_append_nlink(listp, ptr, nlink); } @@ -177,7 +179,7 @@ void *BLI_linklist_pop_pool(struct LinkNode **listp, struct BLI_mempool *mempool void BLI_linklist_insert_after(LinkNode **listp, void *ptr) { - LinkNode *nlink = MEM_mallocN(sizeof(*nlink), "nlink"); + LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__); LinkNode *node = *listp; nlink->link = ptr; diff --git a/source/blender/blenlib/intern/convexhull2d.c b/source/blender/blenlib/intern/convexhull2d.c index 361e4b4eadb..5f64088f433 100644 --- a/source/blender/blenlib/intern/convexhull2d.c +++ b/source/blender/blenlib/intern/convexhull2d.c @@ -187,8 +187,8 @@ static int pointref_cmp_yx(const void *a_, const void *b_) * \param points An array of 2D points. * \param n The number of points in points. * \param r_points An array of the convex hull vertex indices (max is n). - * _must_ be allocated as ``n * 2`` because of how its used internally, - * even though the final result will be no more then \a n in size. + * _must_ be allocated as ``n * 2`` because of how its used internally, + * even though the final result will be no more than \a n in size. * \returns the number of points in r_points. */ int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[]) diff --git a/source/blender/blenlib/intern/easing.c b/source/blender/blenlib/intern/easing.c index 80f02d54eaa..90c8528338e 100644 --- a/source/blender/blenlib/intern/easing.c +++ b/source/blender/blenlib/intern/easing.c @@ -139,7 +139,7 @@ float BLI_easing_cubic_ease_in_out(float time, float begin, float change, float #ifdef USE_ELASTIC_BLEND /** - * When the amplitude is less then the change, we need to blend + * When the amplitude is less than the change, we need to blend * \a f when we're close to the crossing point (int time), else we get an ugly sharp falloff. */ static float elastic_blend(float time, float change, float duration, float amplitude, float s, float f) diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index 4ed82f8a473..82d57dad753 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -23,12 +23,13 @@ /** \file blender/blenlib/intern/edgehash.c * \ingroup bli * - * A general (pointer -> pointer) hash table ADT + * An (edge -> pointer) chaining hash table. + * Using unordered int-pairs as keys. * - * \note Based on 'BLI_ghash.c', make sure these stay in sync. + * \note Based on 'BLI_ghash.c', which is a more generalized hash-table + * make sure these stay in sync. */ - #include <stdlib.h> #include <string.h> #include <limits.h> @@ -146,7 +147,7 @@ BLI_INLINE void edgehash_buckets_reserve(EdgeHash *eh, const unsigned int nentri /** * Internal lookup function. - * Takes a hash argument to avoid calling #ghash_keyhash multiple times. + * Takes a hash argument to avoid calling #edgehash_keyhash multiple times. */ BLI_INLINE EdgeEntry *edgehash_lookup_entry_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, const unsigned int hash) @@ -256,6 +257,35 @@ BLI_INLINE void edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, } /** + * Remove the entry and return it, caller must free from eh->epool. + */ +static EdgeEntry *edgehash_remove_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, EdgeHashFreeFP valfreefp, + unsigned int hash) +{ + EdgeEntry *e; + EdgeEntry *e_prev = NULL; + + BLI_assert(v0 < v1); + + for (e = eh->buckets[hash]; e; e = e->next) { + if (UNLIKELY(v0 == e->v0 && v1 == e->v1)) { + EdgeEntry *e_next = e->next; + + if (valfreefp) valfreefp(e->val); + + if (e_prev) e_prev->next = e_next; + else eh->buckets[hash] = e_next; + + eh->nentries--; + return e; + } + e_prev = e; + } + + return NULL; +} + +/** * Run free callbacks for freeing entries. */ static void edgehash_free_cb(EdgeHash *eh, EdgeHashFreeFP valfreefp) @@ -366,6 +396,57 @@ void *BLI_edgehash_lookup_default(EdgeHash *eh, unsigned int v0, unsigned int v1 } /** + * Remove \a key from \a eh, or return false if the key wasn't found. + * + * \param key The key to remove. + * \param valfreefp Optional callback to free the value. + * \return true if \a key was removed from \a eh. + */ +bool BLI_edgehash_remove(EdgeHash *eh, unsigned int v0, unsigned int v1, EdgeHashFreeFP valfreefp) +{ + unsigned int hash; + EdgeEntry *e; + + EDGE_ORD(v0, v1); /* ensure v0 is smaller */ + hash = edgehash_keyhash(eh, v0, v1); + e = edgehash_remove_ex(eh, v0, v1, valfreefp, hash); + if (e) { + BLI_mempool_free(eh->epool, e); + return true; + } + else { + return false; + } +} + +/* same as above but return the value, + * no free value argument since it will be returned */ +/** + * Remove \a key from \a eh, returning the value or NULL if the key wasn't found. + * + * \param key The key to remove. + * \return the value of \a key int \a eh or NULL. + */ +void *BLI_edgehash_popkey(EdgeHash *eh, unsigned int v0, unsigned int v1) +{ + unsigned int hash; + EdgeEntry *e; + + EDGE_ORD(v0, v1); /* ensure v0 is smaller */ + hash = edgehash_keyhash(eh, v0, v1); + e = edgehash_remove_ex(eh, v0, v1, NULL, hash); + IS_EDGEHASH_ASSERT(eh); + if (e) { + void *val = e->val; + BLI_mempool_free(eh->epool, e); + return val; + } + else { + return NULL; + } +} + +/** * Return boolean true/false if edge (v0,v1) in hash. */ bool BLI_edgehash_haskey(EdgeHash *eh, unsigned int v0, unsigned int v1) @@ -404,6 +485,14 @@ void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP valfreefp, BLI_mempool_clear_ex(eh->epool, nentries_reserve ? (int)nentries_reserve : -1); } +/** + * Wraps #BLI_edgehash_clear_ex with zero entries reserved. + */ +void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp) +{ + BLI_edgehash_clear_ex(eh, valfreefp, 0); +} + void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp) { BLI_assert((int)eh->nentries == BLI_mempool_count(eh->epool)); @@ -440,7 +529,7 @@ void BLI_edgehash_flag_clear(EdgeHash *eh, unsigned int flag) /** * Create a new EdgeHashIterator. The hash table must not be mutated * while the iterator is in use, and the iterator will step exactly - * BLI_edgehash_size(gh) times before becoming done. + * BLI_edgehash_size(eh) times before becoming done. */ EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh) { diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c index d4d87dfdbf6..81cc9fde01f 100644 --- a/source/blender/blenlib/intern/graph.c +++ b/source/blender/blenlib/intern/graph.c @@ -170,11 +170,11 @@ bool BLI_hasAdjacencyList(BGraph *graph) for (node = graph->nodes.first; node; node = node->next) { if (node->arcs == NULL) { - return 0; + return false; } } - return 1; + return true; } void BLI_replaceNodeInArc(BGraph *graph, BArc *arc, BNode *node_src, BNode *node_replaced) @@ -337,7 +337,7 @@ static bool detectCycle(BNode *node, BArc *src_arc) } } else { - value = 1; + value = true; } return value; @@ -354,7 +354,7 @@ bool BLI_isGraphCyclic(BGraph *graph) BLI_flagNodes(graph, 0); /* detectCycles in subgraphs */ - for (node = graph->nodes.first; node && value == 0; node = node->next) { + for (node = graph->nodes.first; node && value == false; node = node->next) { /* only for nodes in subgraphs that haven't been visited yet */ if (node->flag == 0) { value = value || detectCycle(node, NULL); diff --git a/source/blender/blenlib/intern/md5.c b/source/blender/blenlib/intern/hash_md5.c index 3d1a9cdb7a4..4eec38278e9 100644 --- a/source/blender/blenlib/intern/md5.c +++ b/source/blender/blenlib/intern/hash_md5.c @@ -22,20 +22,20 @@ * Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>. */ -/** \file blender/blenlib/intern/md5.c +/** \file blender/blenlib/intern/hash_md5.c * \ingroup bli * * Functions to compute MD5 message digest of files or memory blocks * according to the definition of MD5 in RFC 1321 from April 1992. */ -#include "BLI_md5.h" /* own include */ - #include <stdlib.h> #include <string.h> #include <stdio.h> #include <sys/types.h> +#include "BLI_hash_md5.h" /* own include */ + #if defined HAVE_LIMITS_H || defined _LIBC # include <limits.h> #endif @@ -77,7 +77,8 @@ #endif -/* Following code is low level, upon which are built up the functions 'md5_stream' and 'md5_buffer'. */ +/* Following code is low level, upon which are built up the functions + * 'BLI_hash_md5_stream' and 'BLI_hash_md5_buffer'. */ /* Structure to save state of computation between the single steps. */ struct md5_ctx @@ -284,7 +285,7 @@ static void *md5_read_ctx(const struct md5_ctx *ctx, void *resbuf) * The resulting message digest number will be written into the 16 bytes beginning at 'resblock'. * \return Non-zero if an error occurred. */ -int md5_stream(FILE *stream, void *resblock) +int BLI_hash_md5_stream(FILE *stream, void *resblock) { #define BLOCKSIZE 4096 /* Important: must be a multiple of 64. */ struct md5_ctx ctx; @@ -356,7 +357,7 @@ int md5_stream(FILE *stream, void *resblock) * The result is always in little endian byte order, so that a byte-wise output yields to the wanted * ASCII representation of the message digest. */ -void *md5_buffer(const char *buffer, size_t len, void *resblock) +void *BLI_hash_md5_buffer(const char *buffer, size_t len, void *resblock) { struct md5_ctx ctx; char restbuf[64 + 72]; @@ -390,7 +391,7 @@ void *md5_buffer(const char *buffer, size_t len, void *resblock) return md5_read_ctx(&ctx, resblock); } -char *md5_to_hexdigest(void *resblock, char r_hex_digest[33]) +char *BLI_hash_md5_to_hexdigest(void *resblock, char r_hex_digest[33]) { static const char hex_map[17] = "0123456789abcdef"; const unsigned char *p; diff --git a/source/blender/blenlib/intern/hash_mm2a.c b/source/blender/blenlib/intern/hash_mm2a.c new file mode 100644 index 00000000000..8b4242fa5be --- /dev/null +++ b/source/blender/blenlib/intern/hash_mm2a.c @@ -0,0 +1,107 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + * + * Copyright (C) 2014 Blender Foundation. + * + */ + +/** \file blender/blenlib/intern/hash_mm2a.c + * \ingroup bli + * + * Functions to compute Murmur2A hash key. + * + * A very fast hash generating int32 result, with few collisions and good repartition. + * + * See also: + * reference implementation: https://smhasher.googlecode.com/svn-history/r130/trunk/MurmurHash2.cpp + * and http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed + * + * \warning Do not store that hash in files or such, it is not endian-agnostic, so you should only use it + * for temporary data. + */ + +#include "BLI_hash_mm2a.h" /* own include */ + +/* Helpers. */ +#define MM2A_M 0x5bd1e995 + +#define MM2A_MIX(h, k) \ +{ \ + (k) *= MM2A_M; \ + (k) ^= (k) >> 24; \ + (k) *= MM2A_M; \ + (h) = ((h) * MM2A_M) ^ (k); \ +} (void)0 + +static void mm2a_mix_tail(BLI_HashMurmur2A *mm2, const unsigned char **data, size_t *len) +{ + while (*len && ((*len < 4) || mm2->count)) { + mm2->tail |= (uint32_t)(**data) << (mm2->count * 8); + + mm2->count++; + (*len)--; + (*data)++; + + if (mm2->count == 4) { + MM2A_MIX(mm2->hash, mm2->tail); + mm2->tail = 0; + mm2->count = 0; + } + } +} + +void BLI_hash_mm2a_init(BLI_HashMurmur2A *mm2, uint32_t seed) +{ + mm2->hash = seed; + mm2->tail = 0; + mm2->count = 0; + mm2->size = 0; +} + +void BLI_hash_mm2a_add(BLI_HashMurmur2A *mm2, const unsigned char *data, size_t len) +{ + mm2->size += (uint32_t)len; + + mm2a_mix_tail(mm2, &data, &len); + + for (; len >= 4; data += 4, len -= 4) { + uint32_t k = *(uint32_t *)data; + + MM2A_MIX(mm2->hash, k); + } + + mm2a_mix_tail(mm2, &data, &len); +} + +void BLI_hash_mm2a_add_int(BLI_HashMurmur2A *mm2, int data) +{ + BLI_hash_mm2a_add(mm2, (const unsigned char *)&data, sizeof(data)); +} + +uint32_t BLI_hash_mm2a_end(BLI_HashMurmur2A *mm2) +{ + MM2A_MIX(mm2->hash, mm2->tail); + MM2A_MIX(mm2->hash, mm2->size); + + mm2->hash ^= mm2->hash >> 13; + mm2->hash *= MM2A_M; + mm2->hash ^= mm2->hash >> 15; + + return mm2->hash; +} diff --git a/source/blender/blenlib/intern/lasso.c b/source/blender/blenlib/intern/lasso.c index e89f7fd795b..23704538413 100644 --- a/source/blender/blenlib/intern/lasso.c +++ b/source/blender/blenlib/intern/lasso.c @@ -33,7 +33,6 @@ #include "DNA_vec_types.h" #include "BLI_math.h" -#include "BLI_rect.h" #include "BLI_strict_flags.h" #include "BLI_lasso.h" /* own include */ diff --git a/source/blender/blenlib/intern/listbase.c b/source/blender/blenlib/intern/listbase.c index d9cf8971246..bd3e1e0bbb0 100644 --- a/source/blender/blenlib/intern/listbase.c +++ b/source/blender/blenlib/intern/listbase.c @@ -130,6 +130,44 @@ bool BLI_remlink_safe(ListBase *listbase, void *vlink) } /** + * Swaps \a vlinka and \a vlinkb in the list. Assumes they are both already in the list! + */ +void BLI_listbase_swaplinks(ListBase *listbase, void *vlinka, void *vlinkb) +{ + Link *linka = vlinka; + Link *linkb = vlinkb; + + if (!linka || !linkb) + return; + + if (linkb->next == linka) { + SWAP(Link *, linka, linkb); + } + + if (linka->next == linkb) { + linka->next = linkb->next; + linkb->prev = linka->prev; + linka->prev = linkb; + linkb->next = linka; + } + else { /* Non-contiguous items, we can safely swap. */ + SWAP(Link *, linka->prev, linkb->prev); + SWAP(Link *, linka->next, linkb->next); + } + + /* Update neighbors of linka and linkb. */ + if (linka->prev) linka->prev->next = linka; + if (linka->next) linka->next->prev = linka; + if (linkb->prev) linkb->prev->next = linkb; + if (linkb->next) linkb->next->prev = linkb; + + if (listbase->last == linka) listbase->last = linkb; + else if (listbase->last == linkb) listbase->last = linka; + if (listbase->first == linka) listbase->first = linkb; + else if (listbase->first == linkb) listbase->first = linka; +} + +/** * Removes the head from \a listbase and returns it. */ void *BLI_pophead(ListBase *listbase) @@ -173,7 +211,7 @@ void BLI_freelinkN(ListBase *listbase, void *vlink) * (which should return 1 iff its first arg should come after its second arg). * This uses insertion sort, so NOT ok for large list. */ -void BLI_sortlist(ListBase *listbase, int (*cmp)(const void *, const void *)) +void BLI_listbase_sort(ListBase *listbase, int (*cmp)(const void *, const void *)) { Link *current = NULL; Link *previous = NULL; @@ -195,7 +233,7 @@ void BLI_sortlist(ListBase *listbase, int (*cmp)(const void *, const void *)) } } -void BLI_sortlist_r(ListBase *listbase, void *thunk, int (*cmp)(void *, const void *, const void *)) +void BLI_listbase_sort_r(ListBase *listbase, void *thunk, int (*cmp)(void *, const void *, const void *)) { Link *current = NULL; Link *previous = NULL; @@ -334,22 +372,35 @@ void BLI_freelistN(ListBase *listbase) BLI_listbase_clear(listbase); } +/** + * Returns the number of elements in \a listbase, up until (and including count_max) + * + * \note Use to avoid redundant looping. + */ +int BLI_listbase_count_ex(const ListBase *listbase, const int count_max) +{ + Link *link; + int count = 0; + + for (link = listbase->first; link && count != count_max; link = link->next) { + count++; + } + + return count; +} /** * Returns the number of elements in \a listbase. */ -int BLI_countlist(const ListBase *listbase) +int BLI_listbase_count(const ListBase *listbase) { Link *link; int count = 0; - - if (listbase) { - link = listbase->first; - while (link) { - count++; - link = link->next; - } + + for (link = listbase->first; link; link = link->next) { + count++; } + return count; } diff --git a/source/blender/blenlib/intern/math_base_inline.c b/source/blender/blenlib/intern/math_base_inline.c index e6217329145..39116d6f30f 100644 --- a/source/blender/blenlib/intern/math_base_inline.c +++ b/source/blender/blenlib/intern/math_base_inline.c @@ -44,6 +44,24 @@ # define UNLIKELY(x) (x) #endif +/* powf is really slow for raising to integer powers. */ +MINLINE float pow2f(float x) +{ + return x * x; +} +MINLINE float pow3f(float x) +{ + return pow2f(x) * x; +} +MINLINE float pow4f(float x) +{ + return pow2f(pow2f(x)); +} +MINLINE float pow7f(float x) +{ + return pow2f(pow3f(x)) * x; +} + MINLINE float sqrt3f(float f) { if (UNLIKELY(f == 0.0f)) return 0.0f; diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index da0855ad022..42aa24d284d 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -912,12 +912,12 @@ bool isect_point_tri_v2_cw(const float pt[2], const float v1[2], const float v2[ if (line_point_side_v2(v1, v2, pt) >= 0.0f) { if (line_point_side_v2(v2, v3, pt) >= 0.0f) { if (line_point_side_v2(v3, v1, pt) >= 0.0f) { - return 1; + return true; } } } - return 0; + return false; } int isect_point_tri_v2(const float pt[2], const float v1[2], const float v2[2], const float v3[2]) @@ -983,28 +983,28 @@ bool isect_line_tri_v3(const float p1[3], const float p2[3], cross_v3_v3v3(p, d, e2); a = dot_v3v3(e1, p); - if (a == 0.0f) return 0; + if (a == 0.0f) return false; f = 1.0f / a; sub_v3_v3v3(s, p1, v0); u = f * dot_v3v3(s, p); - if ((u < 0.0f) || (u > 1.0f)) return 0; + if ((u < 0.0f) || (u > 1.0f)) return false; cross_v3_v3v3(q, s, e1); v = f * dot_v3v3(d, q); - if ((v < 0.0f) || ((u + v) > 1.0f)) return 0; + if ((v < 0.0f) || ((u + v) > 1.0f)) return false; *r_lambda = f * dot_v3v3(e2, q); - if ((*r_lambda < 0.0f) || (*r_lambda > 1.0f)) return 0; + if ((*r_lambda < 0.0f) || (*r_lambda > 1.0f)) return false; if (r_uv) { r_uv[0] = u; r_uv[1] = v; } - return 1; + return true; } /* like isect_line_tri_v3, but allows epsilon tolerance around triangle */ @@ -1022,28 +1022,28 @@ bool isect_line_tri_epsilon_v3(const float p1[3], const float p2[3], cross_v3_v3v3(p, d, e2); a = dot_v3v3(e1, p); - if (a == 0.0f) return 0; + if (a == 0.0f) return false; f = 1.0f / a; sub_v3_v3v3(s, p1, v0); u = f * dot_v3v3(s, p); - if ((u < -epsilon) || (u > 1.0f + epsilon)) return 0; + if ((u < -epsilon) || (u > 1.0f + epsilon)) return false; cross_v3_v3v3(q, s, e1); v = f * dot_v3v3(d, q); - if ((v < -epsilon) || ((u + v) > 1.0f + epsilon)) return 0; + if ((v < -epsilon) || ((u + v) > 1.0f + epsilon)) return false; *r_lambda = f * dot_v3v3(e2, q); - if ((*r_lambda < 0.0f) || (*r_lambda > 1.0f)) return 0; + if ((*r_lambda < 0.0f) || (*r_lambda > 1.0f)) return false; if (r_uv) { r_uv[0] = u; r_uv[1] = v; } - return 1; + return true; } /* moved from effect.c @@ -1064,28 +1064,28 @@ bool isect_ray_tri_v3(const float p1[3], const float d[3], a = dot_v3v3(e1, p); /* note: these values were 0.000001 in 2.4x but for projection snapping on * a human head (1BU == 1m), subsurf level 2, this gave many errors - campbell */ - if ((a > -0.00000001f) && (a < 0.00000001f)) return 0; + if ((a > -0.00000001f) && (a < 0.00000001f)) return false; f = 1.0f / a; sub_v3_v3v3(s, p1, v0); u = f * dot_v3v3(s, p); - if ((u < 0.0f) || (u > 1.0f)) return 0; + if ((u < 0.0f) || (u > 1.0f)) return false; cross_v3_v3v3(q, s, e1); v = f * dot_v3v3(d, q); - if ((v < 0.0f) || ((u + v) > 1.0f)) return 0; + if ((v < 0.0f) || ((u + v) > 1.0f)) return false; *r_lambda = f * dot_v3v3(e2, q); - if ((*r_lambda < 0.0f)) return 0; + if ((*r_lambda < 0.0f)) return false; if (r_uv) { r_uv[0] = u; r_uv[1] = v; } - return 1; + return true; } /** @@ -1107,7 +1107,7 @@ bool isect_ray_plane_v3(const float p1[3], const float d[3], a = dot_v3v3(e1, p); /* note: these values were 0.000001 in 2.4x but for projection snapping on * a human head (1BU == 1m), subsurf level 2, this gave many errors - campbell */ - if ((a > -0.00000001f) && (a < 0.00000001f)) return 0; + if ((a > -0.00000001f) && (a < 0.00000001f)) return false; f = 1.0f / a; sub_v3_v3v3(s, p1, v0); @@ -1119,9 +1119,9 @@ bool isect_ray_plane_v3(const float p1[3], const float d[3], /* v = f * dot_v3v3(d, q); */ /*UNUSED*/ *r_lambda = f * dot_v3v3(e2, q); - if (clip && (*r_lambda < 0.0f)) return 0; + if (clip && (*r_lambda < 0.0f)) return false; - return 1; + return true; } bool isect_ray_tri_epsilon_v3(const float p1[3], const float d[3], @@ -1142,22 +1142,22 @@ bool isect_ray_tri_epsilon_v3(const float p1[3], const float d[3], sub_v3_v3v3(s, p1, v0); u = f * dot_v3v3(s, p); - if ((u < -epsilon) || (u > 1.0f + epsilon)) return 0; + if ((u < -epsilon) || (u > 1.0f + epsilon)) return false; cross_v3_v3v3(q, s, e1); v = f * dot_v3v3(d, q); - if ((v < -epsilon) || ((u + v) > 1.0f + epsilon)) return 0; + if ((v < -epsilon) || ((u + v) > 1.0f + epsilon)) return false; *r_lambda = f * dot_v3v3(e2, q); - if ((*r_lambda < 0.0f)) return 0; + if ((*r_lambda < 0.0f)) return false; if (uv) { uv[0] = u; uv[1] = v; } - return 1; + return true; } bool isect_ray_tri_threshold_v3(const float p1[3], const float d[3], @@ -1173,14 +1173,14 @@ bool isect_ray_tri_threshold_v3(const float p1[3], const float d[3], cross_v3_v3v3(p, d, e2); a = dot_v3v3(e1, p); - if ((a > -0.000001f) && (a < 0.000001f)) return 0; + if ((a > -0.000001f) && (a < 0.000001f)) return false; f = 1.0f / a; sub_v3_v3v3(s, p1, v0); cross_v3_v3v3(q, s, e1); *r_lambda = f * dot_v3v3(e2, q); - if ((*r_lambda < 0.0f)) return 0; + if ((*r_lambda < 0.0f)) return false; u = f * dot_v3v3(s, p); v = f * dot_v3v3(d, q); @@ -1204,7 +1204,7 @@ bool isect_ray_tri_threshold_v3(const float p1[3], const float d[3], mul_v3_fl(e2, dv); if (len_squared_v3(e1) + len_squared_v3(e2) > threshold * threshold) { - return 0; + return false; } if (r_uv) { @@ -1212,7 +1212,7 @@ bool isect_ray_tri_threshold_v3(const float p1[3], const float d[3], r_uv[1] = v; } - return 1; + return true; } /** @@ -1363,7 +1363,7 @@ bool isect_sweeping_sphere_tri_v3(const float p1[3], const float p2[3], const fl if (t0 > t1) SWAP(float, t0, t1); - if (t0 > 1.0f || t1 < 0.0f) return 0; + if (t0 > 1.0f || t1 < 0.0f) return false; /* clamp to [0, 1] */ CLAMP(t0, 0.0f, 1.0f); @@ -1542,7 +1542,7 @@ bool isect_axial_line_tri_v3(const int axis, const float p1[3], const float p2[3 if ((f > -0.000001f) && (f < 0.000001f)) return false; v = (p[a2] * e1[a1] - p[a1] * e1[a2]) / f; - if ((v < 0.0f) || (v > 1.0f)) return 0; + if ((v < 0.0f) || (v > 1.0f)) return false; f = e1[a1]; if ((f > -0.000001f) && (f < 0.000001f)) { @@ -1553,7 +1553,7 @@ bool isect_axial_line_tri_v3(const int axis, const float p1[3], const float p2[3 else u = (-p[a1] - v * e2[a1]) / f; - if ((u < 0.0f) || ((u + v) > 1.0f)) return 0; + if ((u < 0.0f) || ((u + v) > 1.0f)) return false; *r_lambda = (p[a0] + u * e1[a0] + v * e2[a0]) / (p2[a0] - p1[a0]); @@ -1756,8 +1756,8 @@ bool isect_ray_aabb(const IsectRayAABBData *data, const float bb_min[3], if (tzmin > tmin) tmin = tzmin; - /* XXX jwilkins: tmax does not need to be updated since we don't use it - * keeping this here for future reference */ + /* Note: tmax does not need to be updated since we don't use it + * keeping this here for future reference - jwilkins */ //if (tzmax < tmax) tmax = tzmax; if (tmin_out) @@ -1840,7 +1840,7 @@ float line_plane_factor_v3(const float plane_co[3], const float plane_no[3], return (dot != 0.0f) ? -dot_v3v3(plane_no, h) / dot : 0.0f; } -/** Ensure the distance between these points is no greater then 'dist'. +/** Ensure the distance between these points is no greater than 'dist'. * If it is, scale then both into the center. */ void limit_dist_v3(float v1[3], float v2[3], const float dist) @@ -4016,3 +4016,31 @@ bool is_poly_convex_v2(const float verts[][2], unsigned int nr) return true; } + +/** + * Check if either of the diagonals along this quad create flipped triangles + * (normals pointing away from eachother). + * - (1 << 0): (v1-v3) is flipped. + * - (1 << 1): (v2-v4) is flipped. + */ +int is_quad_flip_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3]) +{ + float d_12[3], d_23[3], d_34[3], d_41[3]; + float cross_a[3], cross_b[3]; + int ret = 0; + + sub_v3_v3v3(d_12, v1, v2); + sub_v3_v3v3(d_23, v2, v3); + sub_v3_v3v3(d_34, v3, v4); + sub_v3_v3v3(d_41, v4, v1); + + cross_v3_v3v3(cross_a, d_12, d_23); + cross_v3_v3v3(cross_b, d_34, d_41); + ret |= ((dot_v3v3(cross_a, cross_b) < 0.0f) << 0); + + cross_v3_v3v3(cross_a, d_23, d_34); + cross_v3_v3v3(cross_b, d_41, d_12); + ret |= ((dot_v3v3(cross_a, cross_b) < 0.0f) << 1); + + return ret; +} diff --git a/source/blender/blenlib/intern/math_interp.c b/source/blender/blenlib/intern/math_interp.c index 4feb954a31a..a0c47be8d48 100644 --- a/source/blender/blenlib/intern/math_interp.c +++ b/source/blender/blenlib/intern/math_interp.c @@ -467,7 +467,7 @@ void BLI_ewa_filter(const int width, const int height, /* scaling dxt/dyt by full resolution can cause overflow because of huge A/B/C and esp. F values, * scaling by aspect ratio alone does the opposite, so try something in between instead... */ const float ff2 = (float)width, ff = sqrtf(ff2), q = (float)height / ff; - const float Ux = du[0] * ff, Vx = dv[0] * q, Uy = du[1] * ff, Vy = dv[1] * q; + const float Ux = du[0] * ff, Vx = du[1] * q, Uy = dv[0] * ff, Vy = dv[1] * q; float A = Vx * Vx + Vy * Vy; float B = -2.0f * (Ux * Vx + Uy * Vy); float C = Ux * Ux + Uy * Uy; diff --git a/source/blender/blenlib/intern/math_matrix.c b/source/blender/blenlib/intern/math_matrix.c index af42af88582..1b4bbafdb04 100644 --- a/source/blender/blenlib/intern/math_matrix.c +++ b/source/blender/blenlib/intern/math_matrix.c @@ -639,7 +639,16 @@ void mul_mat3_m4_fl(float m[4][4], float f) m[i][j] *= f; } -void negate_m3(float m[4][4]) +void negate_m3(float m[3][3]) +{ + int i, j; + + for (i = 0; i < 3; i++) + for (j = 0; j < 3; j++) + m[i][j] *= -1.0f; +} + +void negate_mat3_m4(float m[4][4]) { int i, j; @@ -839,9 +848,10 @@ bool invert_m4_m4(float inverse[4][4], float mat[4][4]) } } - temp = tempmat[i][i]; - if (temp == 0) - return 0; /* No non-zero pivot */ + if (UNLIKELY(tempmat[i][i] == 0.0f)) { + return false; /* No non-zero pivot */ + } + temp = (double)tempmat[i][i]; for (k = 0; k < 4; k++) { tempmat[i][k] = (float)((double)tempmat[i][k] / temp); inverse[i][k] = (float)((double)inverse[i][k] / temp); @@ -856,7 +866,7 @@ bool invert_m4_m4(float inverse[4][4], float mat[4][4]) } } } - return 1; + return true; } /****************************** Linear Algebra *******************************/ @@ -876,6 +886,37 @@ void transpose_m3(float mat[3][3]) mat[2][1] = t; } +void transpose_m3_m3(float rmat[3][3], float mat[3][3]) +{ + BLI_assert(rmat != mat); + + rmat[0][0] = mat[0][0]; + rmat[0][1] = mat[1][0]; + rmat[0][2] = mat[2][0]; + rmat[1][0] = mat[0][1]; + rmat[1][1] = mat[1][1]; + rmat[1][2] = mat[2][1]; + rmat[2][0] = mat[0][2]; + rmat[2][1] = mat[1][2]; + rmat[2][2] = mat[2][2]; +} + +/* seems obscure but in-fact a common operation */ +void transpose_m3_m4(float rmat[3][3], float mat[4][4]) +{ + BLI_assert(&rmat[0][0] != &mat[0][0]); + + rmat[0][0] = mat[0][0]; + rmat[0][1] = mat[1][0]; + rmat[0][2] = mat[2][0]; + rmat[1][0] = mat[0][1]; + rmat[1][1] = mat[1][1]; + rmat[1][2] = mat[2][1]; + rmat[2][0] = mat[0][2]; + rmat[2][1] = mat[1][2]; + rmat[2][2] = mat[2][2]; +} + void transpose_m4(float mat[4][4]) { float t; @@ -902,6 +943,28 @@ void transpose_m4(float mat[4][4]) mat[3][2] = t; } +void transpose_m4_m4(float rmat[4][4], float mat[4][4]) +{ + BLI_assert(rmat != mat); + + rmat[0][0] = mat[0][0]; + rmat[0][1] = mat[1][0]; + rmat[0][2] = mat[2][0]; + rmat[0][3] = mat[3][0]; + rmat[1][0] = mat[0][1]; + rmat[1][1] = mat[1][1]; + rmat[1][2] = mat[2][1]; + rmat[1][3] = mat[3][1]; + rmat[2][0] = mat[0][2]; + rmat[2][1] = mat[1][2]; + rmat[2][2] = mat[2][2]; + rmat[2][3] = mat[3][2]; + rmat[3][0] = mat[0][3]; + rmat[3][1] = mat[1][3]; + rmat[3][2] = mat[2][3]; + rmat[3][3] = mat[3][3]; +} + int compare_m4m4(float mat1[4][4], float mat2[4][4], float limit) { if (compare_v4v4(mat1[0], mat2[0], limit)) @@ -1087,11 +1150,11 @@ bool is_orthogonal_m3(float m[3][3]) for (i = 0; i < 3; i++) { for (j = 0; j < i; j++) { if (fabsf(dot_v3v3(m[i], m[j])) > 1.5f * FLT_EPSILON) - return 0; + return false; } } - return 1; + return true; } bool is_orthogonal_m4(float m[4][4]) @@ -1101,12 +1164,12 @@ bool is_orthogonal_m4(float m[4][4]) for (i = 0; i < 4; i++) { for (j = 0; j < i; j++) { if (fabsf(dot_v4v4(m[i], m[j])) > 1.5f * FLT_EPSILON) - return 0; + return false; } } - return 1; + return true; } bool is_orthonormal_m3(float m[3][3]) @@ -1116,12 +1179,12 @@ bool is_orthonormal_m3(float m[3][3]) for (i = 0; i < 3; i++) if (fabsf(dot_v3v3(m[i], m[i]) - 1) > 1.5f * FLT_EPSILON) - return 0; + return false; - return 1; + return true; } - return 0; + return false; } bool is_orthonormal_m4(float m[4][4]) @@ -1131,12 +1194,12 @@ bool is_orthonormal_m4(float m[4][4]) for (i = 0; i < 4; i++) if (fabsf(dot_v4v4(m[i], m[i]) - 1) > 1.5f * FLT_EPSILON) - return 0; + return false; - return 1; + return true; } - return 0; + return false; } bool is_uniform_scaled_m3(float m[3][3]) @@ -1145,8 +1208,7 @@ bool is_uniform_scaled_m3(float m[3][3]) float t[3][3]; float l1, l2, l3, l4, l5, l6; - copy_m3_m3(t, m); - transpose_m3(t); + transpose_m3_m3(t, m); l1 = len_squared_v3(m[0]); l2 = len_squared_v3(m[1]); @@ -1387,7 +1449,7 @@ float mat3_to_scale(float mat[3][3]) { /* unit length vector */ float unit_vec[3]; - copy_v3_fl(unit_vec, (float)(1.0 / M_SQRT3)); + copy_v3_fl(unit_vec, (float)M_SQRT1_3); mul_m3_v3(mat, unit_vec); return len_v3(unit_vec); } @@ -1396,7 +1458,7 @@ float mat4_to_scale(float mat[4][4]) { /* unit length vector */ float unit_vec[3]; - copy_v3_fl(unit_vec, (float)(1.0 / M_SQRT3)); + copy_v3_fl(unit_vec, (float)M_SQRT1_3); mul_mat3_m4_v3(mat, unit_vec); return len_v3(unit_vec); } @@ -1413,9 +1475,7 @@ void mat3_to_rot_size(float rot[3][3], float size[3], float mat3[3][3]) /* note: this is a workaround for negative matrix not working for rotation conversion, FIXME */ normalize_m3_m3(mat3_n, mat3); if (is_negative_m3(mat3)) { - negate_v3(mat3_n[0]); - negate_v3(mat3_n[1]); - negate_v3(mat3_n[2]); + negate_m3(mat3_n); } /* rotation */ @@ -1425,11 +1485,19 @@ void mat3_to_rot_size(float rot[3][3], float size[3], float mat3[3][3]) /* scale */ /* note: mat4_to_size(ob->size, mat) fails for negative scale */ invert_m3_m3(imat3_n, mat3_n); + + /* better not edit mat3 */ +#if 0 mul_m3_m3m3(mat3, imat3_n, mat3); size[0] = mat3[0][0]; size[1] = mat3[1][1]; size[2] = mat3[2][2]; +#else + size[0] = dot_m3_v3_row_x(imat3_n, mat3[0]); + size[1] = dot_m3_v3_row_y(imat3_n, mat3[1]); + size[2] = dot_m3_v3_row_z(imat3_n, mat3[2]); +#endif } void mat4_to_loc_rot_size(float loc[3], float rot[3][3], float size[3], float wmat[4][4]) @@ -1454,9 +1522,7 @@ void mat4_to_loc_quat(float loc[3], float quat[4], float wmat[4][4]) /* so scale doesn't interfere with rotation [#24291] */ /* note: this is a workaround for negative matrix not working for rotation conversion, FIXME */ if (is_negative_m3(mat3)) { - negate_v3(mat3_n[0]); - negate_v3(mat3_n[1]); - negate_v3(mat3_n[2]); + negate_m3(mat3_n); } mat3_to_quat(quat, mat3_n); @@ -2183,14 +2249,14 @@ void svd_m4(float U[4][4], float s[4], float V[4][4], float A_[4][4]) } } -void pseudoinverse_m4_m4(float Ainv[4][4], float A[4][4], float epsilon) +void pseudoinverse_m4_m4(float Ainv[4][4], float A_[4][4], float epsilon) { /* compute moon-penrose pseudo inverse of matrix, singular values * below epsilon are ignored for stability (truncated SVD) */ - float V[4][4], W[4], Wm[4][4], U[4][4]; + float A[4][4], V[4][4], W[4], Wm[4][4], U[4][4]; int i; - transpose_m4(A); + transpose_m4_m4(A, A_); svd_m4(V, W, U, A); transpose_m4(U); transpose_m4(V); diff --git a/source/blender/blenlib/intern/math_rotation.c b/source/blender/blenlib/intern/math_rotation.c index 9a6515daf68..3ac031d7b90 100644 --- a/source/blender/blenlib/intern/math_rotation.c +++ b/source/blender/blenlib/intern/math_rotation.c @@ -1867,7 +1867,7 @@ float angle_wrap_deg(float angle) /* returns an angle compatible with angle_compat */ float angle_compat_rad(float angle, float angle_compat) { - return angle + (floorf(((angle_compat - angle) / (float)M_PI) + 0.5f)) * (float)M_PI; + return angle_compat + angle_wrap_rad(angle - angle_compat); } /* axis conversion */ diff --git a/source/blender/blenlib/intern/path_util.c b/source/blender/blenlib/intern/path_util.c index d5af980e373..0a30a35ba7c 100644 --- a/source/blender/blenlib/intern/path_util.c +++ b/source/blender/blenlib/intern/path_util.c @@ -45,12 +45,6 @@ #include "BLI_string_utf8.h" #include "BLI_fnmatch.h" -#include "../blenkernel/BKE_blender.h" /* BLENDER_VERSION, bad level include (no function call) */ - -#include "GHOST_Path-api.h" - -#include "MEM_guardedalloc.h" - #ifdef WIN32 # include "utf_winfunc.h" # include "utfconv.h" @@ -62,21 +56,12 @@ # include <windows.h> # include <shlobj.h> # include "BLI_winstuff.h" -#else /* non windows */ -# ifdef WITH_BINRELOC -# include "binreloc.h" -# endif -# include <unistd.h> /* mkdtemp on OSX (and probably all *BSD?), not worth making specific check for this OS. */ +# include "MEM_guardedalloc.h" #endif /* WIN32 */ /* local */ #define UNIQUE_NAME_MAX 128 -static char bprogname[FILE_MAX]; /* full path to program executable */ -static char bprogdir[FILE_MAX]; /* full path to directory in which executable is located */ -static char btempdir_base[FILE_MAX]; /* persistent temporary directory */ -static char btempdir_session[FILE_MAX] = ""; /* volatile temporary directory */ - /* implementation */ /** @@ -954,8 +939,6 @@ bool BLI_path_abs(char *path, const char *basepath) BLI_strncpy(path, tmp, FILE_MAX); } - BLI_cleanup_path(NULL, path); - #ifdef WIN32 /* skip first two chars, which in case of * absolute path will be drive:/blabla and @@ -965,7 +948,10 @@ bool BLI_path_abs(char *path, const char *basepath) */ BLI_char_switch(path + 2, '/', '\\'); #endif - + + /* ensure this is after correcting for path switch */ + BLI_cleanup_path(NULL, path); + return wasrelative; } @@ -1038,446 +1024,6 @@ void BLI_getlastdir(const char *dir, char *last, const size_t maxlen) } } -/* This is now only used to really get the user's default document folder */ -/* On Windows I chose the 'Users/<MyUserName>/Documents' since it's used - * as default location to save documents */ -const char *BLI_getDefaultDocumentFolder(void) -{ -#ifndef WIN32 - const char * const xdg_documents_dir = getenv("XDG_DOCUMENTS_DIR"); - - if (xdg_documents_dir) - return xdg_documents_dir; - - return getenv("HOME"); -#else /* Windows */ - static char documentfolder[MAXPATHLEN]; - HRESULT hResult; - - /* Check for %HOME% env var */ - if (uput_getenv("HOME", documentfolder, MAXPATHLEN)) { - if (BLI_is_dir(documentfolder)) return documentfolder; - } - - /* add user profile support for WIN 2K / NT. - * This is %APPDATA%, which translates to either - * %USERPROFILE%\Application Data or since Vista - * to %USERPROFILE%\AppData\Roaming - */ - hResult = SHGetFolderPath(NULL, CSIDL_PERSONAL, NULL, SHGFP_TYPE_CURRENT, documentfolder); - - if (hResult == S_OK) { - if (BLI_is_dir(documentfolder)) return documentfolder; - } - - return NULL; -#endif /* WIN32 */ -} - -/* NEW stuff, to be cleaned up when fully migrated */ -/* ************************************************************* */ -/* ************************************************************* */ - -// #define PATH_DEBUG - -/* returns a formatted representation of the specified version number. Non-reentrant! */ -static char *blender_version_decimal(const int ver) -{ - static char version_str[5]; - sprintf(version_str, "%d.%02d", ver / 100, ver % 100); - return version_str; -} - -/** - * Concatenates path_base, (optional) path_sep and (optional) folder_name into targetpath, - * returning true if result points to a directory. - */ -static bool test_path(char *targetpath, const char *path_base, const char *path_sep, const char *folder_name) -{ - char tmppath[FILE_MAX]; - - if (path_sep) BLI_join_dirfile(tmppath, sizeof(tmppath), path_base, path_sep); - else BLI_strncpy(tmppath, path_base, sizeof(tmppath)); - - /* rare cases folder_name is omitted (when looking for ~/.blender/2.xx dir only) */ - if (folder_name) - BLI_make_file_string("/", targetpath, tmppath, folder_name); - else - BLI_strncpy(targetpath, tmppath, sizeof(tmppath)); - /* FIXME: why is "//" on front of tmppath expanded to "/" (by BLI_join_dirfile) - * if folder_name is specified but not otherwise? */ - - if (BLI_is_dir(targetpath)) { -#ifdef PATH_DEBUG - printf("\t%s found: %s\n", __func__, targetpath); -#endif - return true; - } - else { -#ifdef PATH_DEBUG - printf("\t%s missing: %s\n", __func__, targetpath); -#endif - //targetpath[0] = '\0'; - return false; - } -} - -/** - * Puts the value of the specified environment variable into *path if it exists - * and points at a directory. Returns true if this was done. - */ -static bool test_env_path(char *path, const char *envvar) -{ - const char *env = envvar ? getenv(envvar) : NULL; - if (!env) return false; - - if (BLI_is_dir(env)) { - BLI_strncpy(path, env, FILE_MAX); -#ifdef PATH_DEBUG - printf("\t%s env %s found: %s\n", __func__, envvar, env); -#endif - return true; - } - else { - path[0] = '\0'; -#ifdef PATH_DEBUG - printf("\t%s env %s missing: %s\n", __func__, envvar, env); -#endif - return false; - } -} - -/** - * Constructs in \a targetpath the name of a directory relative to a version-specific - * subdirectory in the parent directory of the Blender executable. - * - * \param targetpath String to return path - * \param folder_name Optional folder name within version-specific directory - * \param subfolder_name Optional subfolder name within folder_name - * \param ver To construct name of version-specific directory within bprogdir - * \return true if such a directory exists. - */ -static bool get_path_local(char *targetpath, const char *folder_name, const char *subfolder_name, const int ver) -{ - char relfolder[FILE_MAX]; - -#ifdef PATH_DEBUG - printf("%s...\n", __func__); -#endif - - if (folder_name) { - if (subfolder_name) { - BLI_join_dirfile(relfolder, sizeof(relfolder), folder_name, subfolder_name); - } - else { - BLI_strncpy(relfolder, folder_name, sizeof(relfolder)); - } - } - else { - relfolder[0] = '\0'; - } - - /* try EXECUTABLE_DIR/2.5x/folder_name - new default directory for local blender installed files */ -#ifdef __APPLE__ - static char osx_resourses[FILE_MAX]; /* due new codesign situation in OSX > 10.9.5 we must move the blender_version dir with contents to Resources */ - sprintf(osx_resourses, "%s../Resources", bprogdir); - return test_path(targetpath, osx_resourses, blender_version_decimal(ver), relfolder); -#else - return test_path(targetpath, bprogdir, blender_version_decimal(ver), relfolder); -#endif -} - -/** - * Is this an install with user files kept together with the Blender executable and its - * installation files. - */ -static bool is_portable_install(void) -{ - /* detect portable install by the existence of config folder */ - const int ver = BLENDER_VERSION; - char path[FILE_MAX]; - - return get_path_local(path, "config", NULL, ver); -} - -/** - * Returns the path of a folder within the user-files area. - * - * - * \param targetpath String to return path - * \param folder_name default name of folder within user area - * \param subfolder_name optional name of subfolder within folder - * \param envvar name of environment variable which, if defined, overrides folder_name - * \param ver Blender version, used to construct a subdirectory name - * \return true if it was able to construct such a path. - */ -static bool get_path_user(char *targetpath, const char *folder_name, const char *subfolder_name, const char *envvar, const int ver) -{ - char user_path[FILE_MAX]; - const char *user_base_path; - - /* for portable install, user path is always local */ - if (is_portable_install()) - return get_path_local(targetpath, folder_name, subfolder_name, ver); - - user_path[0] = '\0'; - - if (test_env_path(user_path, envvar)) { - if (subfolder_name) { - return test_path(targetpath, user_path, NULL, subfolder_name); - } - else { - BLI_strncpy(targetpath, user_path, FILE_MAX); - return true; - } - } - - user_base_path = (const char *)GHOST_getUserDir(ver, blender_version_decimal(ver)); - if (user_base_path) - BLI_strncpy(user_path, user_base_path, FILE_MAX); - - if (!user_path[0]) - return false; - -#ifdef PATH_DEBUG - printf("%s: %s\n", __func__, user_path); -#endif - - if (subfolder_name) { - return test_path(targetpath, user_path, folder_name, subfolder_name); - } - else { - return test_path(targetpath, user_path, NULL, folder_name); - } -} - -/** - * Returns the path of a folder within the Blender installation directory. - * - * \param targetpath String to return path - * \param folder_name default name of folder within installation area - * \param subfolder_name optional name of subfolder within folder - * \param envvar name of environment variable which, if defined, overrides folder_name - * \param ver Blender version, used to construct a subdirectory name - * \return true if it was able to construct such a path. - */ -static bool get_path_system(char *targetpath, const char *folder_name, const char *subfolder_name, const char *envvar, const int ver) -{ - char system_path[FILE_MAX]; - const char *system_base_path; - char cwd[FILE_MAX]; - char relfolder[FILE_MAX]; - - if (folder_name) { - if (subfolder_name) { - BLI_join_dirfile(relfolder, sizeof(relfolder), folder_name, subfolder_name); - } - else { - BLI_strncpy(relfolder, folder_name, sizeof(relfolder)); - } - } - else { - relfolder[0] = '\0'; - } - - /* first allow developer only overrides to the system path - * these are only used when running blender from source */ - - /* try CWD/release/folder_name */ - if (BLI_current_working_dir(cwd, sizeof(cwd))) { - if (test_path(targetpath, cwd, "release", relfolder)) { - return true; - } - } - - /* try EXECUTABLE_DIR/release/folder_name */ - if (test_path(targetpath, bprogdir, "release", relfolder)) - return true; - - /* end developer overrides */ - - - - system_path[0] = '\0'; - - if (test_env_path(system_path, envvar)) { - if (subfolder_name) { - return test_path(targetpath, system_path, NULL, subfolder_name); - } - else { - BLI_strncpy(targetpath, system_path, FILE_MAX); - return true; - } - } - - system_base_path = (const char *)GHOST_getSystemDir(ver, blender_version_decimal(ver)); - if (system_base_path) - BLI_strncpy(system_path, system_base_path, FILE_MAX); - - if (!system_path[0]) - return false; - -#ifdef PATH_DEBUG - printf("%s: %s\n", __func__, system_path); -#endif - - if (subfolder_name) { - /* try $BLENDERPATH/folder_name/subfolder_name */ - return test_path(targetpath, system_path, folder_name, subfolder_name); - } - else { - /* try $BLENDERPATH/folder_name */ - return test_path(targetpath, system_path, NULL, folder_name); - } -} - -/* get a folder out of the 'folder_id' presets for paths */ -/* returns the path if found, NULL string if not */ -const char *BLI_get_folder(int folder_id, const char *subfolder) -{ - const int ver = BLENDER_VERSION; - static char path[FILE_MAX] = ""; - - switch (folder_id) { - case BLENDER_DATAFILES: /* general case */ - if (get_path_user(path, "datafiles", subfolder, "BLENDER_USER_DATAFILES", ver)) break; - if (get_path_local(path, "datafiles", subfolder, ver)) break; - if (get_path_system(path, "datafiles", subfolder, "BLENDER_SYSTEM_DATAFILES", ver)) break; - return NULL; - - case BLENDER_USER_DATAFILES: - if (get_path_user(path, "datafiles", subfolder, "BLENDER_USER_DATAFILES", ver)) break; - return NULL; - - case BLENDER_SYSTEM_DATAFILES: - if (get_path_local(path, "datafiles", subfolder, ver)) break; - if (get_path_system(path, "datafiles", subfolder, "BLENDER_SYSTEM_DATAFILES", ver)) break; - return NULL; - - case BLENDER_USER_AUTOSAVE: - if (get_path_user(path, "autosave", subfolder, "BLENDER_USER_DATAFILES", ver)) break; - return NULL; - - case BLENDER_USER_CONFIG: - if (get_path_user(path, "config", subfolder, "BLENDER_USER_CONFIG", ver)) break; - return NULL; - - case BLENDER_USER_SCRIPTS: - if (get_path_user(path, "scripts", subfolder, "BLENDER_USER_SCRIPTS", ver)) break; - return NULL; - - case BLENDER_SYSTEM_SCRIPTS: - if (get_path_local(path, "scripts", subfolder, ver)) break; - if (get_path_system(path, "scripts", subfolder, "BLENDER_SYSTEM_SCRIPTS", ver)) break; - return NULL; - - case BLENDER_SYSTEM_PYTHON: - if (get_path_local(path, "python", subfolder, ver)) break; - if (get_path_system(path, "python", subfolder, "BLENDER_SYSTEM_PYTHON", ver)) break; - return NULL; - - default: - BLI_assert(0); - break; - } - - return path; -} - -/** - * Returns the path to a folder in the user area without checking that it actually exists first. - */ -const char *BLI_get_user_folder_notest(int folder_id, const char *subfolder) -{ - const int ver = BLENDER_VERSION; - static char path[FILE_MAX] = ""; - - switch (folder_id) { - case BLENDER_USER_DATAFILES: - get_path_user(path, "datafiles", subfolder, "BLENDER_USER_DATAFILES", ver); - break; - case BLENDER_USER_CONFIG: - get_path_user(path, "config", subfolder, "BLENDER_USER_CONFIG", ver); - break; - case BLENDER_USER_AUTOSAVE: - get_path_user(path, "autosave", subfolder, "BLENDER_USER_AUTOSAVE", ver); - break; - case BLENDER_USER_SCRIPTS: - get_path_user(path, "scripts", subfolder, "BLENDER_USER_SCRIPTS", ver); - break; - default: - BLI_assert(0); - break; - } - - if ('\0' == path[0]) { - return NULL; - } - return path; -} - -/** - * Returns the path to a folder in the user area, creating it if it doesn't exist. - */ -const char *BLI_get_folder_create(int folder_id, const char *subfolder) -{ - const char *path; - - /* only for user folders */ - if (!ELEM(folder_id, BLENDER_USER_DATAFILES, BLENDER_USER_CONFIG, BLENDER_USER_SCRIPTS, BLENDER_USER_AUTOSAVE)) - return NULL; - - path = BLI_get_folder(folder_id, subfolder); - - if (!path) { - path = BLI_get_user_folder_notest(folder_id, subfolder); - if (path) BLI_dir_create_recursive(path); - } - - return path; -} - -/** - * Returns the path of the top-level version-specific local, user or system directory. - * If do_check, then the result will be NULL if the directory doesn't exist. - */ -const char *BLI_get_folder_version(const int id, const int ver, const bool do_check) -{ - static char path[FILE_MAX] = ""; - bool ok; - switch (id) { - case BLENDER_RESOURCE_PATH_USER: - ok = get_path_user(path, NULL, NULL, NULL, ver); - break; - case BLENDER_RESOURCE_PATH_LOCAL: - ok = get_path_local(path, NULL, NULL, ver); - break; - case BLENDER_RESOURCE_PATH_SYSTEM: - ok = get_path_system(path, NULL, NULL, NULL, ver); - break; - default: - path[0] = '\0'; /* in case do_check is false */ - ok = false; - BLI_assert(!"incorrect ID"); - break; - } - - if (!ok && do_check) { - return NULL; - } - - return path; -} - -/* End new stuff */ -/* ************************************************************* */ -/* ************************************************************* */ - - - -#ifdef PATH_DEBUG -# undef PATH_DEBUG -#endif /** * Sets the specified environment variable to the specified value, @@ -1580,7 +1126,7 @@ void BLI_make_existing_file(const char *name) char di[FILE_MAX]; BLI_split_dir_part(name, di, sizeof(di)); - /* make if if the dir doesn't exist */ + /* make if the dir doesn't exist */ BLI_dir_create_recursive(di); } @@ -1707,11 +1253,10 @@ bool BLI_testextensie_n(const char *str, ...) while ((ext = (const char *) va_arg(args, void *))) { if (testextensie_ex(str, str_len, ext, strlen(ext))) { ret = true; - goto finally; + break; } } -finally: va_end(args); return ret; @@ -2153,310 +1698,6 @@ void BLI_path_native_slash(char *path) #endif } -/** - * Tries appending each of the semicolon-separated extensions in the PATHEXT - * environment variable (Windows-only) onto *name in turn until such a file is found. - * Returns success/failure. - */ -static int add_win32_extension(char *name) -{ - int retval = 0; - int type; - - type = BLI_exists(name); - if ((type == 0) || S_ISDIR(type)) { -#ifdef _WIN32 - char filename[FILE_MAX]; - char ext[FILE_MAX]; - const char *extensions = getenv("PATHEXT"); - if (extensions) { - char *temp; - do { - strcpy(filename, name); - temp = strstr(extensions, ";"); - if (temp) { - strncpy(ext, extensions, temp - extensions); - ext[temp - extensions] = 0; - extensions = temp + 1; - strcat(filename, ext); - } - else { - strcat(filename, extensions); - } - - type = BLI_exists(filename); - if (type && (!S_ISDIR(type))) { - retval = 1; - strcpy(name, filename); - break; - } - } while (temp); - } -#endif - } - else { - retval = 1; - } - - return (retval); -} - -/** - * Checks if name is a fully qualified filename to an executable. - * If not it searches $PATH for the file. On Windows it also - * adds the correct extension (.com .exe etc) from - * $PATHEXT if necessary. Also on Windows it translates - * the name to its 8.3 version to prevent problems with - * spaces and stuff. Final result is returned in fullname. - * - * \param fullname The full path and full name of the executable - * (must be FILE_MAX minimum) - * \param name The name of the executable (usually argv[0]) to be checked - */ -static void bli_where_am_i(char *fullname, const size_t maxlen, const char *name) -{ - char filename[FILE_MAX]; - const char *path = NULL, *temp; - -#ifdef _WIN32 - const char *separator = ";"; -#else - const char *separator = ":"; -#endif - - -#ifdef WITH_BINRELOC - /* linux uses binreloc since argv[0] is not reliable, call br_init( NULL ) first */ - path = br_find_exe(NULL); - if (path) { - BLI_strncpy(fullname, path, maxlen); - free((void *)path); - return; - } -#endif - -#ifdef _WIN32 - wchar_t *fullname_16 = MEM_mallocN(maxlen * sizeof(wchar_t), "ProgramPath"); - if (GetModuleFileNameW(0, fullname_16, maxlen)) { - conv_utf_16_to_8(fullname_16, fullname, maxlen); - if (!BLI_exists(fullname)) { - printf("path can't be found: \"%.*s\"\n", (int)maxlen, fullname); - MessageBox(NULL, "path contains invalid characters or is too long (see console)", "Error", MB_OK); - } - MEM_freeN(fullname_16); - return; - } - - MEM_freeN(fullname_16); -#endif - - /* unix and non linux */ - if (name && name[0]) { - - BLI_strncpy(fullname, name, maxlen); - if (name[0] == '.') { - char wdir[FILE_MAX] = ""; - BLI_current_working_dir(wdir, sizeof(wdir)); /* backup cwd to restore after */ - - // not needed but avoids annoying /./ in name - if (name[1] == SEP) - BLI_join_dirfile(fullname, maxlen, wdir, name + 2); - else - BLI_join_dirfile(fullname, maxlen, wdir, name); - - add_win32_extension(fullname); /* XXX, doesnt respect length */ - } - else if (BLI_last_slash(name)) { - // full path - BLI_strncpy(fullname, name, maxlen); - add_win32_extension(fullname); - } - else { - // search for binary in $PATH - path = getenv("PATH"); - if (path) { - do { - temp = strstr(path, separator); - if (temp) { - strncpy(filename, path, temp - path); - filename[temp - path] = 0; - path = temp + 1; - } - else { - strncpy(filename, path, sizeof(filename)); - } - BLI_path_append(fullname, maxlen, name); - if (add_win32_extension(filename)) { - BLI_strncpy(fullname, filename, maxlen); - break; - } - } while (temp); - } - } -#if defined(DEBUG) - if (strcmp(name, fullname)) { - printf("guessing '%s' == '%s'\n", name, fullname); - } -#endif - } -} - -void BLI_init_program_path(const char *argv0) -{ - bli_where_am_i(bprogname, sizeof(bprogname), argv0); - BLI_split_dir_part(bprogname, bprogdir, sizeof(bprogdir)); -} - -/** - * Path to executable - */ -const char *BLI_program_path(void) -{ - return bprogname; -} - -/** - * Path to directory of executable - */ -const char *BLI_program_dir(void) -{ - return bprogdir; -} - -/** - * 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 temporary temp directory - * \param basename The full path to the persistent temp directory (may be NULL) - * \param maxlen The size of the fullname buffer - * \param userdir Directory specified in user preferences - */ -static void BLI_where_is_temp(char *fullname, char *basename, const size_t maxlen, char *userdir) -{ - /* Clear existing temp dir, if needed. */ - BLI_temp_dir_session_purge(); - - fullname[0] = '\0'; - if (basename) { - basename[0] = '\0'; - } - - if (userdir && BLI_is_dir(userdir)) { - BLI_strncpy(fullname, userdir, maxlen); - } - - -#ifdef WIN32 - if (fullname[0] == '\0') { - const char *tmp = getenv("TEMP"); /* Windows */ - if (tmp && BLI_is_dir(tmp)) { - BLI_strncpy(fullname, tmp, maxlen); - } - } -#else - /* Other OS's - Try TMP and TMPDIR */ - if (fullname[0] == '\0') { - const char *tmp = getenv("TMP"); - if (tmp && BLI_is_dir(tmp)) { - BLI_strncpy(fullname, tmp, maxlen); - } - } - - if (fullname[0] == '\0') { - const char *tmp = getenv("TMPDIR"); - if (tmp && BLI_is_dir(tmp)) { - BLI_strncpy(fullname, tmp, maxlen); - } - } -#endif - - if (fullname[0] == '\0') { - BLI_strncpy(fullname, "/tmp/", maxlen); - } - else { - /* add a trailing slash if needed */ - BLI_add_slash(fullname); -#ifdef WIN32 - if (userdir && userdir != fullname) { - BLI_strncpy(userdir, fullname, maxlen); /* also set user pref to show %TEMP%. /tmp/ is just plain confusing for Windows users. */ - } -#endif - } - - /* Now that we have a valid temp dir, add system-generated unique sub-dir. */ - if (basename) { - /* 'XXXXXX' is kind of tag to be replaced by mktemp-familly by an uuid. */ - char *tmp_name = BLI_strdupcat(fullname, "blender_XXXXXX"); - const size_t ln = strlen(tmp_name) + 1; - if (ln <= maxlen) { -#ifdef WIN32 - if (_mktemp_s(tmp_name, ln) == 0) { - BLI_dir_create_recursive(tmp_name); - } -#else - mkdtemp(tmp_name); -#endif - } - if (BLI_is_dir(tmp_name)) { - BLI_strncpy(basename, fullname, maxlen); - BLI_strncpy(fullname, tmp_name, maxlen); - BLI_add_slash(fullname); - } - else { - printf("Warning! Could not generate a temp file name for '%s', falling back to '%s'\n", tmp_name, fullname); - } - - MEM_freeN(tmp_name); - } -} - -/** - * Sets btempdir_base to userdir if specified and is a valid directory, otherwise - * chooses a suitable OS-specific temporary directory. - * Sets btempdir_session to a mkdtemp-generated sub-dir of btempdir_base. - */ -void BLI_temp_dir_init(char *userdir) -{ - BLI_where_is_temp(btempdir_session, btempdir_base, FILE_MAX, userdir); -; -} - -/** - * Path to temporary directory (with trailing slash) - */ -const char *BLI_temp_dir_session(void) -{ - return btempdir_session[0] ? btempdir_session : BLI_temp_dir_base(); -} - -/** - * Path to persistent temporary directory (with trailing slash) - */ -const char *BLI_temp_dir_base(void) -{ - return btempdir_base; -} - -/** - * Path to the system temporary directory (with trailing slash) - */ -void BLI_system_temporary_dir(char *dir) -{ - BLI_where_is_temp(dir, NULL, FILE_MAX, NULL); -} - -/** - * Delete content of this instance's temp dir. - */ -void BLI_temp_dir_session_purge(void) -{ - if (btempdir_session[0] && BLI_is_dir(btempdir_session)) { - BLI_delete(btempdir_session, true, true); - } -} #ifdef WITH_ICONV diff --git a/source/blender/blenlib/intern/polyfill2d_beautify.c b/source/blender/blenlib/intern/polyfill2d_beautify.c new file mode 100644 index 00000000000..c4e333d0094 --- /dev/null +++ b/source/blender/blenlib/intern/polyfill2d_beautify.c @@ -0,0 +1,499 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenlib/intern/polyfill2d_beautify.c + * \ingroup bli + * + * This function is to improve the tessellation resulting from polyfill2d, + * creating optimal topology. + * + * The functionality here matches #BM_mesh_beautify_fill, + * but its far simpler to perform this operation in 2d, + * on a simple polygon representation where we _know_: + * + * - The polygon is primitive with no holes with a continuous boundary. + * - Tris have consistent winding. + * - 2d (saves some hassles projecting face pairs on an axis for every edge-rotation) + * also saves us having to store all previous edge-states (see #EdRotState in bmesh_beautify.c) + * + * \note + * + * No globals - keep threadsafe. + */ + +#include "BLI_utildefines.h" +#include "BLI_math.h" + +#include "BLI_memarena.h" +#include "BLI_edgehash.h" +#include "BLI_heap.h" + +#include "BLI_polyfill2d_beautify.h" /* own include */ + +#include "BLI_strict_flags.h" + +struct PolyEdge { + /** ordered vert indices (smaller first) */ + unsigned int verts[2]; + /** ordered face indices (depends on winding compared to the edge verts) + * - (verts[0], verts[1]) == faces[0] + * - (verts[1], verts[0]) == faces[1] + */ + unsigned int faces[2]; + /** + * The face-index which isn't used by either of the edges verts [0 - 2]. + * could be calculated each time, but cleaner to store for reuse. + */ + unsigned int faces_other_v[2]; +}; + + +#ifndef NDEBUG +/** + * Only to check for error-cases. + */ +static void polyfill_validate_tri(unsigned int (*tris)[3], unsigned int tri_index, EdgeHash *ehash) +{ + const unsigned int *tri = tris[tri_index]; + int j_curr; + + BLI_assert(!ELEM(tri[0], tri[1], tri[2]) && + !ELEM(tri[1], tri[0], tri[2]) && + !ELEM(tri[2], tri[0], tri[1])); + + for (j_curr = 0; j_curr < 3; j_curr++) { + struct PolyEdge *e; + unsigned int e_v1 = tri[(j_curr ) ]; + unsigned int e_v2 = tri[(j_curr + 1) % 3]; + e = BLI_edgehash_lookup(ehash, e_v1, e_v2); + if (e) { + if (e->faces[0] == tri_index) { + BLI_assert(e->verts[0] == e_v1); + BLI_assert(e->verts[1] == e_v2); + } + else if (e->faces[1] == tri_index) { + BLI_assert(e->verts[0] == e_v2); + BLI_assert(e->verts[1] == e_v1); + } + else { + BLI_assert(0); + } + + BLI_assert(e->faces[0] != e->faces[1]); + BLI_assert(ELEM(e_v1, UNPACK3(tri))); + BLI_assert(ELEM(e_v2, UNPACK3(tri))); + BLI_assert(ELEM(e_v1, UNPACK2(e->verts))); + BLI_assert(ELEM(e_v2, UNPACK2(e->verts))); + BLI_assert(e_v1 != tris[e->faces[0]][e->faces_other_v[0]]); + BLI_assert(e_v1 != tris[e->faces[1]][e->faces_other_v[1]]); + BLI_assert(e_v2 != tris[e->faces[0]][e->faces_other_v[0]]); + BLI_assert(e_v2 != tris[e->faces[1]][e->faces_other_v[1]]); + + BLI_assert(ELEM(tri_index, UNPACK2(e->faces))); + } + } +} +#endif + +BLI_INLINE bool is_boundary_edge(unsigned int i_a, unsigned int i_b, const unsigned int coord_last) +{ + BLI_assert(i_a < i_b); + return ((i_a + 1 == i_b) || UNLIKELY((i_a == 0) && (i_b == coord_last))); +} +/** + * Assuming we have 2 triangles sharing an edge (2 - 4), + * check if the edge running from (1 - 3) gives better results. + * + * \return (negative number means the edge can be rotated, lager == better). + */ +static float quad_v2_rotate_beauty_calc( + const float v1[2], const float v2[2], const float v3[2], const float v4[2]) +{ + /* not a loop (only to be able to break out) */ + do { + bool is_zero_a, is_zero_b; + + const float area_2x_234 = cross_tri_v2(v2, v3, v4); + const float area_2x_241 = cross_tri_v2(v2, v4, v1); + + const float area_2x_123 = cross_tri_v2(v1, v2, v3); + const float area_2x_134 = cross_tri_v2(v1, v3, v4); + + { + BLI_assert((ELEM(v1, v2, v3, v4) == false) && + (ELEM(v2, v1, v3, v4) == false) && + (ELEM(v3, v1, v2, v4) == false) && + (ELEM(v4, v1, v2, v3) == false)); + + is_zero_a = (fabsf(area_2x_234) <= FLT_EPSILON); + is_zero_b = (fabsf(area_2x_241) <= FLT_EPSILON); + + if (is_zero_a && is_zero_b) { + break; + } + } + + if (is_zero_a == false && is_zero_b == false) { + /* both tri's are valid, check we make a concave quad */ + if (!is_quad_convex_v2(v1, v2, v3, v4)) { + break; + } + } + else { + /* one of the tri's was degenerate, chech we're not rotating + * into a different degenerate shape or flipping the face */ + if ((fabsf(area_2x_123) <= FLT_EPSILON) || (fabsf(area_2x_134) <= FLT_EPSILON)) { + /* one of the new rotations is degenerate */ + break; + } + + if ((area_2x_123 >= 0.0f) != (area_2x_134 >= 0.0f)) { + /* rotation would cause flipping */ + break; + } + } + + { + /* testing rule: the area divided by the perimeter, + * check if (1-3) beats the existing (2-4) edge rotation */ + float area_a, area_b; + float prim_a, prim_b; + float fac_24, fac_13; + + float len_12, len_23, len_34, len_41, len_24, len_13; + +#define AREA_FROM_CROSS(val) (fabsf(val) / 2.0f) + + /* edges around the quad */ + len_12 = len_v2v2(v1, v2); + len_23 = len_v2v2(v2, v3); + len_34 = len_v2v2(v3, v4); + len_41 = len_v2v2(v4, v1); + /* edges crossing the quad interior */ + len_13 = len_v2v2(v1, v3); + len_24 = len_v2v2(v2, v4); + + /* edge (2-4), current state */ + area_a = AREA_FROM_CROSS(area_2x_234); + area_b = AREA_FROM_CROSS(area_2x_241); + prim_a = len_23 + len_34 + len_24; + prim_b = len_24 + len_41 + len_12; + fac_24 = (area_a / prim_a) + (area_b / prim_b); + + /* edge (1-3), new state */ + area_a = AREA_FROM_CROSS(area_2x_123); + area_b = AREA_FROM_CROSS(area_2x_134); + prim_a = len_12 + len_23 + len_13; + prim_b = len_34 + len_41 + len_13; + fac_13 = (area_a / prim_a) + (area_b / prim_b); + +#undef AREA_FROM_CROSS + + /* negative number if (1-3) is an improved state */ + return fac_24 - fac_13; + } + } while (false); + + return FLT_MAX; +} + +static float polyedge_rotate_beauty_calc( + const float (*coords)[2], + const unsigned int (*tris)[3], + const struct PolyEdge *e) +{ + const float *v1, *v2, *v3, *v4; + + v1 = coords[tris[e->faces[0]][e->faces_other_v[0]]]; + v3 = coords[tris[e->faces[1]][e->faces_other_v[1]]]; + v2 = coords[e->verts[0]]; + v4 = coords[e->verts[1]]; + + return quad_v2_rotate_beauty_calc(v1, v2, v3, v4); +} + +static void polyedge_beauty_cost_update_single( + const float (*coords)[2], + const unsigned int (*tris)[3], + const struct PolyEdge *edges, + struct PolyEdge *e, + Heap *eheap, HeapNode **eheap_table) +{ + const unsigned int i = (unsigned int)(e - edges); + + if (eheap_table[i]) { + BLI_heap_remove(eheap, eheap_table[i]); + eheap_table[i] = NULL; + } + + { + /* recalculate edge */ + const float cost = polyedge_rotate_beauty_calc(coords, tris, e); + if (cost < 0.0f) { + eheap_table[i] = BLI_heap_insert(eheap, cost, e); + } + else { + eheap_table[i] = NULL; + } + } +} + +static void polyedge_beauty_cost_update( + const float (*coords)[2], + const unsigned int (*tris)[3], + const struct PolyEdge *edges, + struct PolyEdge *e, + Heap *eheap, HeapNode **eheap_table, + EdgeHash *ehash) +{ + const unsigned int *tri_0 = tris[e->faces[0]]; + const unsigned int *tri_1 = tris[e->faces[1]]; + unsigned int i; + + struct PolyEdge *e_arr[4] = { + BLI_edgehash_lookup(ehash, + tri_0[(e->faces_other_v[0] ) % 3], + tri_0[(e->faces_other_v[0] + 1) % 3]), + BLI_edgehash_lookup(ehash, + tri_0[(e->faces_other_v[0] + 2) % 3], + tri_0[(e->faces_other_v[0] ) % 3]), + BLI_edgehash_lookup(ehash, + tri_1[(e->faces_other_v[1] ) % 3], + tri_1[(e->faces_other_v[1] + 1) % 3]), + BLI_edgehash_lookup(ehash, + tri_1[(e->faces_other_v[1] + 2) % 3], + tri_1[(e->faces_other_v[1] ) % 3]), + }; + + + for (i = 0; i < 4; i++) { + if (e_arr[i]) { + BLI_assert(!(ELEM(e_arr[i]->faces[0], UNPACK2(e->faces)) && + ELEM(e_arr[i]->faces[1], UNPACK2(e->faces)))); + + polyedge_beauty_cost_update_single( + coords, tris, edges, + e_arr[i], + eheap, eheap_table); + } + } +} + +static void polyedge_rotate( + unsigned int (*tris)[3], + struct PolyEdge *e, + EdgeHash *ehash) +{ + unsigned int e_v1_new = tris[e->faces[0]][e->faces_other_v[0]]; + unsigned int e_v2_new = tris[e->faces[1]][e->faces_other_v[1]]; + +#ifndef NDEBUG + polyfill_validate_tri(tris, e->faces[0], ehash); + polyfill_validate_tri(tris, e->faces[1], ehash); +#endif + + BLI_assert(e_v1_new != e_v2_new); + BLI_assert(!ELEM(e_v2_new, UNPACK3(tris[e->faces[0]]))); + BLI_assert(!ELEM(e_v1_new, UNPACK3(tris[e->faces[1]]))); + + tris[e->faces[0]][(e->faces_other_v[0] + 1) % 3] = e_v2_new; + tris[e->faces[1]][(e->faces_other_v[1] + 1) % 3] = e_v1_new; + + e->faces_other_v[0] = (e->faces_other_v[0] + 2) % 3; + e->faces_other_v[1] = (e->faces_other_v[1] + 2) % 3; + + BLI_assert((tris[e->faces[0]][e->faces_other_v[0]] != e_v1_new) && + (tris[e->faces[0]][e->faces_other_v[0]] != e_v2_new)); + BLI_assert((tris[e->faces[1]][e->faces_other_v[1]] != e_v1_new) && + (tris[e->faces[1]][e->faces_other_v[1]] != e_v2_new)); + + BLI_edgehash_remove(ehash, e->verts[0], e->verts[1], NULL); + BLI_edgehash_insert(ehash, e_v1_new, e_v2_new, e); + + if (e_v1_new < e_v2_new) { + e->verts[0] = e_v1_new; + e->verts[1] = e_v2_new; + } + else { + /* maintain winding info */ + e->verts[0] = e_v2_new; + e->verts[1] = e_v1_new; + + SWAP(unsigned int, e->faces[0], e->faces[1]); + SWAP(unsigned int, e->faces_other_v[0], e->faces_other_v[1]); + } + + /* update adjacent data */ + { + unsigned int e_side = 0; + + for (e_side = 0; e_side < 2; e_side++) { + /* 't_other' which we need to swap out is always the same edge-order */ + const unsigned int t_other = (((e->faces_other_v[e_side]) + 2)) % 3; + unsigned int t_index = e->faces[e_side]; + unsigned int t_index_other = e->faces[!e_side]; + unsigned int *tri = tris[t_index]; + + struct PolyEdge *e_other; + unsigned int e_v1 = tri[(t_other ) ]; + unsigned int e_v2 = tri[(t_other + 1) % 3]; + + e_other = BLI_edgehash_lookup(ehash, e_v1, e_v2); + if (e_other) { + BLI_assert(t_index != e_other->faces[0] && t_index != e_other->faces[1]); + if (t_index_other == e_other->faces[0]) { + e_other->faces[0] = t_index; + e_other->faces_other_v[0] = (t_other + 2) % 3; + BLI_assert(!ELEM(tri[e_other->faces_other_v[0]], e_v1, e_v2)); + } + else if (t_index_other == e_other->faces[1]) { + e_other->faces[1] = t_index; + e_other->faces_other_v[1] = (t_other + 2) % 3; + BLI_assert(!ELEM(tri[e_other->faces_other_v[1]], e_v1, e_v2)); + } + else { + BLI_assert(0); + } + } + } + } + +#ifndef NDEBUG + polyfill_validate_tri(tris, e->faces[0], ehash); + polyfill_validate_tri(tris, e->faces[1], ehash); +#endif + + BLI_assert(!ELEM(tris[e->faces[0]][e->faces_other_v[0]], UNPACK2(e->verts))); + BLI_assert(!ELEM(tris[e->faces[1]][e->faces_other_v[1]], UNPACK2(e->verts))); +} + +/** + * The intention is that this calculates the output of #BLI_polyfill_calc + * + * + * \note assumes the \a coords form a boundary, + * so any edges running along contiguous (wrapped) indices, + * are ignored since the edges wont share 2 faces. + */ +void BLI_polyfill_beautify( + const float (*coords)[2], + const unsigned int coords_tot, + unsigned int (*tris)[3], + + /* structs for reuse */ + MemArena *arena, Heap *eheap, EdgeHash *ehash) +{ + const unsigned int coord_last = coords_tot - 1; + const unsigned int tris_tot = coords_tot - 2; + /* internal edges only (between 2 tris) */ + const unsigned int edges_tot = tris_tot - 1; + unsigned int edges_tot_used = 0; + unsigned int i; + + HeapNode **eheap_table; + + struct PolyEdge *edges = BLI_memarena_alloc(arena, edges_tot * sizeof(*edges)); + + BLI_assert(BLI_heap_size(eheap) == 0); + BLI_assert(BLI_edgehash_size(ehash) == 0); + + /* first build edges */ + for (i = 0; i < tris_tot; i++) { + unsigned int j_prev, j_curr, j_next; + j_prev = 2; + j_next = 1; + for (j_curr = 0; j_curr < 3; j_next = j_prev, j_prev = j_curr++) { + int e_index; + + unsigned int e_pair[2] = { + tris[i][j_prev], + tris[i][j_curr], + }; + + if (e_pair[0] > e_pair[1]) { + SWAP(unsigned int, e_pair[0], e_pair[1]); + e_index = 1; + } + else { + e_index = 0; + } + + if (!is_boundary_edge(e_pair[0], e_pair[1], coord_last)) { + struct PolyEdge *e = BLI_edgehash_lookup(ehash, e_pair[0], e_pair[1]); + if (e == NULL) { + e = &edges[edges_tot_used++]; + BLI_edgehash_insert(ehash, e_pair[0], e_pair[1], e); + memcpy(e->verts, e_pair, sizeof(e->verts)); +#ifndef NDEBUG + e->faces[!e_index] = (unsigned int)-1; +#endif + } + else { + + /* ensure each edge only ever has 2x users */ +#ifndef NDEBUG + BLI_assert(e->faces[e_index] == (unsigned int)-1); + BLI_assert((e->verts[0] == e_pair[0]) && + (e->verts[1] == e_pair[1])); +#endif + } + + e->faces[e_index] = i; + e->faces_other_v[e_index] = j_next; + } + } + } + + /* now perform iterative rotations */ + eheap_table = BLI_memarena_alloc(arena, sizeof(HeapNode *) * (size_t)edges_tot); + + // for (i = 0; i < tris_tot; i++) { polyfill_validate_tri(tris, i, eh); } + + /* build heap */ + for (i = 0; i < edges_tot; i++) { + struct PolyEdge *e = &edges[i]; + const float cost = polyedge_rotate_beauty_calc(coords, (const unsigned int (*)[3])tris, e); + if (cost < 0.0f) { + eheap_table[i] = BLI_heap_insert(eheap, cost, e); + } + else { + eheap_table[i] = NULL; + } + } + + while (BLI_heap_is_empty(eheap) == false) { + struct PolyEdge *e = BLI_heap_popmin(eheap); + i = (unsigned int)(e - edges); + eheap_table[i] = NULL; + + polyedge_rotate(tris, e, ehash); + + /* recalculate faces connected on the heap */ + polyedge_beauty_cost_update( + coords, (const unsigned int (*)[3])tris, edges, + e, + eheap, eheap_table, ehash); + } + + BLI_heap_clear(eheap, NULL); + BLI_edgehash_clear_ex(ehash, NULL, BLI_POLYFILL_ALLOC_NGON_RESERVE); + + /* MEM_freeN(eheap_table); */ /* arena */ +} diff --git a/source/blender/blenlib/intern/scanfill.c b/source/blender/blenlib/intern/scanfill.c index cf0d8cff870..8a96daeeb91 100644 --- a/source/blender/blenlib/intern/scanfill.c +++ b/source/blender/blenlib/intern/scanfill.c @@ -173,13 +173,13 @@ static bool boundisect(PolyFill *pf2, PolyFill *pf1) /* has pf2 been touched (intersected) by pf1 ? with bounding box */ /* test first if polys exist */ - if (pf1->edges == 0 || pf2->edges == 0) return 0; + if (pf1->edges == 0 || pf2->edges == 0) return false; - if (pf2->max_xy[0] < pf1->min_xy[0]) return 0; - if (pf2->max_xy[1] < pf1->min_xy[1]) return 0; + if (pf2->max_xy[0] < pf1->min_xy[0]) return false; + if (pf2->max_xy[1] < pf1->min_xy[1]) return false; - if (pf2->min_xy[0] > pf1->max_xy[0]) return 0; - if (pf2->min_xy[1] > pf1->max_xy[1]) return 0; + if (pf2->min_xy[0] > pf1->max_xy[0]) return false; + if (pf2->min_xy[1] > pf1->max_xy[1]) return false; /* join */ if (pf2->max_xy[0] < pf1->max_xy[0]) pf2->max_xy[0] = pf1->max_xy[0]; @@ -188,7 +188,7 @@ static bool boundisect(PolyFill *pf2, PolyFill *pf1) if (pf2->min_xy[0] > pf1->min_xy[0]) pf2->min_xy[0] = pf1->min_xy[0]; if (pf2->min_xy[1] > pf1->min_xy[1]) pf2->min_xy[1] = pf1->min_xy[1]; - return 1; + return true; } @@ -225,13 +225,13 @@ static bool testedgeside(const float v1[2], const float v2[2], const float v3[2] (v1[1] - v2[1]) * (v1[0] - v3[0]); if (inp < 0.0f) { - return 0; + return false; } else if (inp == 0.0f) { - if (v1[0] == v3[0] && v1[1] == v3[1]) return 0; - if (v2[0] == v3[0] && v2[1] == v3[1]) return 0; + if (v1[0] == v3[0] && v1[1] == v3[1]) return false; + if (v2[0] == v3[0] && v2[1] == v3[1]) return false; } - return 1; + return true; } static bool addedgetoscanvert(ScanFillVertLink *sc, ScanFillEdge *eed) @@ -261,7 +261,7 @@ static bool addedgetoscanvert(ScanFillVertLink *sc, ScanFillEdge *eed) for (ed = sc->edge_first; ed; ed = ed->next) { if (ed->v2 == eed->v2) { - return 0; + return false; } fac = ed->v2->xy[1] - y; @@ -279,7 +279,7 @@ static bool addedgetoscanvert(ScanFillVertLink *sc, ScanFillEdge *eed) if (ed) BLI_insertlinkbefore((ListBase *)&(sc->edge_first), ed, eed); else BLI_addtail((ListBase *)&(sc->edge_first), eed); - return 1; + return true; } @@ -341,10 +341,10 @@ static bool boundinsideEV(ScanFillEdge *eed, ScanFillVert *eve) maxy = eed->v1->xy[1]; } if (eve->xy[1] >= miny && eve->xy[1] <= maxy) { - return 1; + return true; } } - return 0; + return false; } @@ -807,7 +807,7 @@ unsigned int BLI_scanfill_calc_ex(ScanFillContext *sf_ctx, const int flag, const #if 0 if (flag & BLI_SCANFILL_CALC_QUADTRI_FASTPATH) { - const int totverts = BLI_countlist(&sf_ctx->fillvertbase); + const int totverts = BLI_listbase_count(&sf_ctx->fillvertbase); if (totverts == 3) { eve = sf_ctx->fillvertbase.first; diff --git a/source/blender/blenlib/intern/scanfill_utils.c b/source/blender/blenlib/intern/scanfill_utils.c index 9fc1db1f1e4..6ddea300404 100644 --- a/source/blender/blenlib/intern/scanfill_utils.c +++ b/source/blender/blenlib/intern/scanfill_utils.c @@ -76,7 +76,7 @@ typedef struct ScanFillIsect { #if 0 -void BKE_scanfill_obj_dump(ScanFillContext *sf_ctx) +void BLI_scanfill_obj_dump(ScanFillContext *sf_ctx) { FILE *f = fopen("test.obj", "w"); unsigned int i = 1; @@ -96,7 +96,7 @@ void BKE_scanfill_obj_dump(ScanFillContext *sf_ctx) #endif #if 0 -void BKE_scanfill_view3d_dump(ScanFillContext *sf_ctx) +void BLI_scanfill_view3d_dump(ScanFillContext *sf_ctx) { ScanFillEdge *eed; @@ -265,7 +265,7 @@ static bool scanfill_preprocess_self_isect( } if (BLI_listbase_is_single(e_ls) == false) { - BLI_sortlist_r(e_ls, eed->v2->co, edge_isect_ls_sort_cb); + BLI_listbase_sort_r(e_ls, eed->v2->co, edge_isect_ls_sort_cb); } /* move original edge to filledgebase and add replacement @@ -508,8 +508,8 @@ bool BLI_scanfill_calc_self_isect( sf_ctx->poly_nr = SF_POLY_UNSET; #if 0 - BKE_scanfill_view3d_dump(sf_ctx); - BKE_scanfill_obj_dump(sf_ctx); + BLI_scanfill_view3d_dump(sf_ctx); + BLI_scanfill_obj_dump(sf_ctx); #endif return changed; diff --git a/source/blender/blenlib/intern/smallhash.c b/source/blender/blenlib/intern/smallhash.c index 0cf9f69b9ae..ba336ab6c4b 100644 --- a/source/blender/blenlib/intern/smallhash.c +++ b/source/blender/blenlib/intern/smallhash.c @@ -118,7 +118,7 @@ BLI_INLINE void smallhash_buckets_reserve(SmallHash *sh, const unsigned int nent } } -BLI_INLINE SmallHashEntry *smallhash_lookup(SmallHash *sh, const uintptr_t key) +BLI_INLINE SmallHashEntry *smallhash_lookup(const SmallHash *sh, const uintptr_t key) { SmallHashEntry *e; unsigned int h = smallhash_key(key); @@ -246,6 +246,26 @@ void BLI_smallhash_insert(SmallHash *sh, uintptr_t key, void *val) e->val = val; } +/** + * Inserts a new value to a key that may already be in ghash. + * + * Avoids #BLI_smallhash_remove, #BLI_smallhash_insert calls (double lookups) + * + * \returns true if a new key has been added. + */ +bool BLI_smallhash_reinsert(SmallHash *sh, uintptr_t key, void *item) +{ + SmallHashEntry *e = smallhash_lookup(sh, key); + if (e) { + e->val = item; + return false; + } + else { + BLI_smallhash_insert(sh, key, item); + return true; + } +} + #ifdef USE_REMOVE bool BLI_smallhash_remove(SmallHash *sh, uintptr_t key) { @@ -264,33 +284,33 @@ bool BLI_smallhash_remove(SmallHash *sh, uintptr_t key) } #endif -void *BLI_smallhash_lookup(SmallHash *sh, uintptr_t key) +void *BLI_smallhash_lookup(const SmallHash *sh, uintptr_t key) { SmallHashEntry *e = smallhash_lookup(sh, key); return e ? e->val : NULL; } -void **BLI_smallhash_lookup_p(SmallHash *sh, uintptr_t key) +void **BLI_smallhash_lookup_p(const SmallHash *sh, uintptr_t key) { SmallHashEntry *e = smallhash_lookup(sh, key); return e ? &e->val : NULL; } -bool BLI_smallhash_haskey(SmallHash *sh, uintptr_t key) +bool BLI_smallhash_haskey(const SmallHash *sh, uintptr_t key) { SmallHashEntry *e = smallhash_lookup(sh, key); return (e != NULL); } -int BLI_smallhash_count(SmallHash *sh) +int BLI_smallhash_count(const SmallHash *sh) { return (int)sh->nentries; } -void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key) +BLI_INLINE SmallHashEntry *smallhash_iternext(SmallHashIter *iter, uintptr_t *key) { while (iter->i < iter->sh->nbuckets) { if (smallhash_val_is_used(iter->sh->buckets[iter->i].val)) { @@ -298,7 +318,7 @@ void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key) *key = iter->sh->buckets[iter->i].key; } - return iter->sh->buckets[iter->i++].val; + return &iter->sh->buckets[iter->i++]; } iter->i++; @@ -307,7 +327,21 @@ void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key) return NULL; } -void *BLI_smallhash_iternew(SmallHash *sh, SmallHashIter *iter, uintptr_t *key) +void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key) +{ + SmallHashEntry *e = smallhash_iternext(iter, key); + + return e ? e->val : NULL; +} + +void **BLI_smallhash_iternext_p(SmallHashIter *iter, uintptr_t *key) +{ + SmallHashEntry *e = smallhash_iternext(iter, key); + + return e ? &e->val : NULL; +} + +void *BLI_smallhash_iternew(const SmallHash *sh, SmallHashIter *iter, uintptr_t *key) { iter->sh = sh; iter->i = 0; @@ -315,6 +349,15 @@ void *BLI_smallhash_iternew(SmallHash *sh, SmallHashIter *iter, uintptr_t *key) return BLI_smallhash_iternext(iter, key); } +void **BLI_smallhash_iternew_p(const SmallHash *sh, SmallHashIter *iter, uintptr_t *key) +{ + iter->sh = sh; + iter->i = 0; + + return BLI_smallhash_iternext_p(iter, key); +} + + /** \name Debugging & Introspection * \{ */ diff --git a/source/blender/blenlib/intern/sort.c b/source/blender/blenlib/intern/sort.c index 9fad7505f79..c5922feb0ed 100644 --- a/source/blender/blenlib/intern/sort.c +++ b/source/blender/blenlib/intern/sort.c @@ -32,7 +32,9 @@ #include <stdlib.h> -#ifndef __GLIBC__ +#if defined(__GLIBC__) && (__GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8)) +/* do nothing! */ +#else #include "BLI_utildefines.h" diff --git a/source/blender/blenlib/intern/storage.c b/source/blender/blenlib/intern/storage.c index f3ecc799e1e..c062d62bca5 100644 --- a/source/blender/blenlib/intern/storage.c +++ b/source/blender/blenlib/intern/storage.c @@ -280,7 +280,7 @@ static void bli_builddir(struct BuildDirCtx *dir_ctx, const char *dirname) closedir(dir); } else { - printf("%s non-existant directory\n", dirname); + printf("%s non-existent directory\n", dirname); } } diff --git a/source/blender/blenlib/intern/system.c b/source/blender/blenlib/intern/system.c index e6389bc68f3..51b8efbb79f 100644 --- a/source/blender/blenlib/intern/system.c +++ b/source/blender/blenlib/intern/system.c @@ -22,9 +22,18 @@ * \ingroup bli */ +#include <stdio.h> +#include <stdlib.h> #include "BLI_system.h" +/* for backtrace */ +#if defined(__linux__) || defined(__APPLE__) +# include <execinfo.h> +#elif defined(_MSV_VER) +# include <DbgHelp.h> +#endif + int BLI_cpu_support_sse2(void) { #if defined(__x86_64__) || defined(_M_X64) @@ -57,3 +66,69 @@ int BLI_cpu_support_sse2(void) #endif } +/** + * Write a backtrace into a file for systems which support it. + */ +void BLI_system_backtrace(FILE *fp) +{ + /* ------------- */ + /* Linux / Apple */ +#if defined(__linux__) || defined(__APPLE__) + +#define SIZE 100 + void *buffer[SIZE]; + int nptrs; + char **strings; + int i; + + /* include a backtrace for good measure */ + nptrs = backtrace(buffer, SIZE); + strings = backtrace_symbols(buffer, nptrs); + for (i = 0; i < nptrs; i++) { + fputs(strings[i], fp); + fputc('\n', fp); + } + + free(strings); +#undef SIZE + + /* -------- */ + /* Windows */ +#elif defined(_MSC_VER) + + (void)fp; +#if 0 +#define MAXSYMBOL 256 + unsigned short i; + void *stack[SIZE]; + unsigned short nframes; + SYMBOL_INFO *symbolinfo; + HANDLE process; + + process = GetCurrentProcess(); + + SymInitialize(process, NULL, true); + + nframes = CaptureStackBackTrace(0, SIZE, stack, NULL); + symbolinfo = MEM_callocN(sizeof(SYMBOL_INFO) + MAXSYMBOL * sizeof(char), "crash Symbol table"); + symbolinfo->MaxNameLen = MAXSYMBOL - 1; + symbolinfo->SizeOfStruct = sizeof(SYMBOL_INFO); + + for (i = 0; i < nframes; i++) { + SymFromAddr(process, ( DWORD64 )( stack[ i ] ), 0, symbolinfo); + + fprintf(fp, "%u: %s - 0x%0X\n", nframes - i - 1, symbolinfo->Name, symbolinfo->Address); + } + + MEM_freeN(symbolinfo); +#undef MAXSYMBOL +#endif + + /* ------------------ */ + /* non msvc/osx/linux */ +#else + (void)fp; +#endif + +} +/* end BLI_system_backtrace */ diff --git a/source/blender/blenlib/intern/task.c b/source/blender/blenlib/intern/task.c index 8d867b9f295..d187a8d1968 100644 --- a/source/blender/blenlib/intern/task.c +++ b/source/blender/blenlib/intern/task.c @@ -29,9 +29,12 @@ #include "MEM_guardedalloc.h" #include "BLI_listbase.h" +#include "BLI_math.h" #include "BLI_task.h" #include "BLI_threads.h" +#include "atomic_ops.h" + /* Types */ typedef struct Task { @@ -48,6 +51,8 @@ struct TaskPool { volatile size_t num; volatile size_t done; + size_t num_threads; + size_t currently_running_tasks; ThreadMutex num_mutex; ThreadCondition num_cond; @@ -83,6 +88,7 @@ static void task_pool_num_decrease(TaskPool *pool, size_t done) BLI_assert(pool->num >= done); pool->num -= done; + atomic_sub_z(&pool->currently_running_tasks, done); pool->done += done; if (pool->num == 0) @@ -103,19 +109,37 @@ static void task_pool_num_increase(TaskPool *pool) static bool task_scheduler_thread_wait_pop(TaskScheduler *scheduler, Task **task) { + bool found_task = false; BLI_mutex_lock(&scheduler->queue_mutex); while (!scheduler->queue.first && !scheduler->do_exit) BLI_condition_wait(&scheduler->queue_cond, &scheduler->queue_mutex); - if (!scheduler->queue.first) { - BLI_mutex_unlock(&scheduler->queue_mutex); - BLI_assert(scheduler->do_exit); - return false; - } - - *task = scheduler->queue.first; - BLI_remlink(&scheduler->queue, *task); + do { + Task *current_task; + if (!scheduler->queue.first) { + BLI_mutex_unlock(&scheduler->queue_mutex); + BLI_assert(scheduler->do_exit); + return false; + } + for (current_task = scheduler->queue.first; + current_task != NULL; + current_task = current_task->next) + { + TaskPool *pool = current_task->pool; + if (pool->num_threads == 0 || + pool->currently_running_tasks < pool->num_threads) + { + *task = current_task; + found_task = true; + atomic_add_z(&pool->currently_running_tasks, 1); + BLI_remlink(&scheduler->queue, *task); + break; + } + } + if (!found_task) + BLI_condition_wait(&scheduler->queue_cond, &scheduler->queue_mutex); + } while (!found_task); BLI_mutex_unlock(&scheduler->queue_mutex); @@ -287,6 +311,8 @@ TaskPool *BLI_task_pool_create(TaskScheduler *scheduler, void *userdata) pool->scheduler = scheduler; pool->num = 0; + pool->num_threads = 0; + pool->currently_running_tasks = 0; pool->do_cancel = false; BLI_mutex_init(&pool->num_mutex); @@ -350,12 +376,16 @@ void BLI_task_pool_work_and_wait(TaskPool *pool) /* find task from this pool. if we get a task from another pool, * we can get into deadlock */ - for (task = scheduler->queue.first; task; task = task->next) { - if (task->pool == pool) { - work_task = task; - found_task = true; - BLI_remlink(&scheduler->queue, task); - break; + if (pool->num_threads == 0 || + pool->currently_running_tasks < pool->num_threads) + { + for (task = scheduler->queue.first; task; task = task->next) { + if (task->pool == pool) { + work_task = task; + found_task = true; + BLI_remlink(&scheduler->queue, task); + break; + } } } @@ -364,6 +394,7 @@ void BLI_task_pool_work_and_wait(TaskPool *pool) /* if found task, do it, otherwise wait until other tasks are done */ if (found_task) { /* run task */ + atomic_add_z(&pool->currently_running_tasks, 1); work_task->run(pool, work_task->taskdata, 0); /* delete task */ @@ -386,6 +417,12 @@ void BLI_task_pool_work_and_wait(TaskPool *pool) BLI_mutex_unlock(&pool->num_mutex); } +void BLI_pool_set_num_threads(TaskPool *pool, int num_threads) +{ + /* NOTE: Don't try to modify threads while tasks are running! */ + pool->num_threads = num_threads; +} + void BLI_task_pool_cancel(TaskPool *pool) { pool->do_cancel = true; @@ -428,3 +465,131 @@ size_t BLI_task_pool_tasks_done(TaskPool *pool) return pool->done; } +/* Parallel range routines */ + +/** + * + * Main functions: + * - #BLI_task_parallel_range + * + * TODO: + * - #BLI_task_parallel_foreach_listbase (#ListBase - double linked list) + * - #BLI_task_parallel_foreach_link (#Link - single linked list) + * - #BLI_task_parallel_foreach_ghash/gset (#GHash/#GSet - hash & set) + * - #BLI_task_parallel_foreach_mempool (#BLI_mempool - iterate over mempools) + * + * Possible improvements: + * + * - Chunk iterations to reduce number of spin locks. + */ + +typedef struct ParallelRangeState { + int start, stop; + void *userdata; + TaskParallelRangeFunc func; + + int iter; + int chunk_size; + SpinLock lock; +} ParallelRangeState; + +BLI_INLINE bool parallel_range_next_iter_get( + ParallelRangeState * __restrict state, + int * __restrict iter, int * __restrict count) +{ + bool result = false; + if (state->iter < state->stop) { + BLI_spin_lock(&state->lock); + if (state->iter < state->stop) { + *count = min_ii(state->chunk_size, state->stop - state->iter); + *iter = state->iter; + state->iter += *count; + result = true; + } + BLI_spin_unlock(&state->lock); + } + return result; +} + +static void parallel_range_func( + TaskPool * __restrict pool, + void *UNUSED(taskdata), + int UNUSED(threadid)) +{ + ParallelRangeState * __restrict state = BLI_task_pool_userdata(pool); + int iter, count; + while (parallel_range_next_iter_get(state, &iter, &count)) { + int i; + for (i = 0; i < count; ++i) { + state->func(state->userdata, iter + i); + } + } +} + +void BLI_task_parallel_range_ex( + int start, int stop, + void *userdata, + TaskParallelRangeFunc func, + const int range_threshold, + const bool use_dynamic_scheduling) +{ + TaskScheduler *task_scheduler; + TaskPool *task_pool; + ParallelRangeState state; + int i, num_threads, num_tasks; + + BLI_assert(start < stop); + + /* If it's not enough data to be crunched, don't bother with tasks at all, + * do everything from the main thread. + */ + if (stop - start < range_threshold) { + for (i = start; i < stop; ++i) { + func(userdata, i); + } + return; + } + + task_scheduler = BLI_task_scheduler_get(); + task_pool = BLI_task_pool_create(task_scheduler, &state); + num_threads = BLI_task_scheduler_num_threads(task_scheduler); + + /* The idea here is to prevent creating task for each of the loop iterations + * and instead have tasks which are evenly distributed across CPU cores and + * pull next iter to be crunched using the queue. + */ + num_tasks = num_threads * 2; + + BLI_spin_init(&state.lock); + state.start = start; + state.stop = stop; + state.userdata = userdata; + state.func = func; + state.iter = start; + if (use_dynamic_scheduling) { + state.chunk_size = 32; + } + else { + state.chunk_size = (stop - start) / (num_tasks); + } + + for (i = 0; i < num_tasks; i++) { + BLI_task_pool_push(task_pool, + parallel_range_func, + NULL, false, + TASK_PRIORITY_HIGH); + } + + BLI_task_pool_work_and_wait(task_pool); + BLI_task_pool_free(task_pool); + + BLI_spin_end(&state.lock); +} + +void BLI_task_parallel_range( + int start, int stop, + void *userdata, + TaskParallelRangeFunc func) +{ + BLI_task_parallel_range_ex(start, stop, userdata, func, 64, false); +} |