diff options
author | Martin Poirier <theeth@yahoo.com> | 2008-10-29 03:11:58 +0300 |
---|---|---|
committer | Martin Poirier <theeth@yahoo.com> | 2008-10-29 03:11:58 +0300 |
commit | 19094597b39682c3cf9289cfb20e280f54db82d3 (patch) | |
tree | 430c2ecc875aaf3fa2d29d579a753f9f3b7c2b28 /source/blender/blenlib | |
parent | 3db27c9acbf0fa525b473e6b0d869275147ca487 (diff) | |
parent | 481831bd27b69b5afa6b54dab1e18bf5c8d27f6e (diff) |
merge trunk 17122:17213
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r-- | source/blender/blenlib/BLI_arithb.h | 2 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_ghash.h | 16 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_graph.h | 125 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_threads.h | 26 | ||||
-rw-r--r-- | source/blender/blenlib/SConscript | 2 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_ghash.c | 17 | ||||
-rw-r--r-- | source/blender/blenlib/intern/arithb.c | 17 | ||||
-rw-r--r-- | source/blender/blenlib/intern/graph.c | 1087 | ||||
-rw-r--r-- | source/blender/blenlib/intern/threads.c | 130 |
9 files changed, 1413 insertions, 9 deletions
diff --git a/source/blender/blenlib/BLI_arithb.h b/source/blender/blenlib/BLI_arithb.h index 3c8d2915cf9..1d4b5cf16b2 100644 --- a/source/blender/blenlib/BLI_arithb.h +++ b/source/blender/blenlib/BLI_arithb.h @@ -245,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]); @@ -265,6 +266,7 @@ void Vec2Copyf(float *v1, float *v2); void Vec2Lerpf(float *target, float *a, float *b, float t); 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); 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_threads.h b/source/blender/blenlib/BLI_threads.h index 39162b8bd91..5a7e84c42fb 100644 --- a/source/blender/blenlib/BLI_threads.h +++ b/source/blender/blenlib/BLI_threads.h @@ -39,17 +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/SConscript b/source/blender/blenlib/SConscript index 65cebf02f62..e7a4f2eaf13 100644 --- a/source/blender/blenlib/SConscript +++ b/source/blender/blenlib/SConscript @@ -10,7 +10,7 @@ incs += ' ' + env['BF_ZLIB_INC'] incs += ' ' + env['BF_SDL_INC'] defs = '' -if env['WITH_BF_INTERNATIONAL'] == 1: +if env['WITH_BF_INTERNATIONAL']: defs = 'WITH_FREETYPE2' if env['WITH_BF_VERSE']: diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index e9271ca3bb5..1967b8a88e2 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -200,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; @@ -219,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); } diff --git a/source/blender/blenlib/intern/arithb.c b/source/blender/blenlib/intern/arithb.c index 54e1bd5fc57..0db87a819bd 100644 --- a/source/blender/blenlib/intern/arithb.c +++ b/source/blender/blenlib/intern/arithb.c @@ -1371,6 +1371,18 @@ void NormalQuat(float *q) } } +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]; @@ -2219,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]; 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/threads.c b/source/blender/blenlib/intern/threads.c index 92fad291e83..9df8bbc81e3 100644 --- a/source/blender/blenlib/intern/threads.c +++ b/source/blender/blenlib/intern/threads.c @@ -38,6 +38,8 @@ #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" @@ -199,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; @@ -265,4 +295,104 @@ int BLI_system_thread_count( void ) 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 */ |