[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [31065] branches/particles-2010/source/ blender: Implemented algorithm for finding linked groups of type-adaptable sockets (called "islands" to avoid confusion with group nodes).
Lukas Toenne
lukas.toenne at googlemail.com
Thu Aug 5 13:55:20 CEST 2010
Revision: 31065
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=31065
Author: lukastoenne
Date: 2010-08-05 13:55:20 +0200 (Thu, 05 Aug 2010)
Log Message:
-----------
Implemented algorithm for finding linked groups of type-adaptable sockets (called "islands" to avoid confusion with group nodes). This method will also be used to implement propagation of data context among sockets, which is necessary to avoid bad combinations of data sets. Adaptable sockets (of SOCK_ANY type) now also have "memory", so they keep their current socket type until relinked to a fixed-type socket, which should lessen confusion when relinking independent node sets.
Modified Paths:
--------------
branches/particles-2010/source/blender/blenkernel/BKE_node.h
branches/particles-2010/source/blender/blenkernel/intern/node.c
branches/particles-2010/source/blender/blenkernel/intern/particleset.c
branches/particles-2010/source/blender/editors/space_node/drawnode.c
branches/particles-2010/source/blender/makesdna/DNA_modifier_types.h
branches/particles-2010/source/blender/makesdna/DNA_node_types.h
branches/particles-2010/source/blender/makesrna/intern/rna_nodetree.c
branches/particles-2010/source/blender/modifiers/intern/MOD_nodetree.c
branches/particles-2010/source/blender/nodes/intern/SIM_nodes/SIM_get_vertex_data.c
branches/particles-2010/source/blender/nodes/intern/SIM_nodes/SIM_if.c
branches/particles-2010/source/blender/nodes/intern/SIM_nodes/SIM_program.c
branches/particles-2010/source/blender/nodes/intern/SIM_nodes/SIM_subprogram.c
branches/particles-2010/source/blender/nodes/intern/SIM_util.c
branches/particles-2010/source/blender/nodes/intern/SIM_util.h
branches/particles-2010/source/blender/nodes/intern/node_tree_simulation.c
Modified: branches/particles-2010/source/blender/blenkernel/BKE_node.h
===================================================================
--- branches/particles-2010/source/blender/blenkernel/BKE_node.h 2010-08-05 11:08:52 UTC (rev 31064)
+++ branches/particles-2010/source/blender/blenkernel/BKE_node.h 2010-08-05 11:55:20 UTC (rev 31065)
@@ -56,6 +56,7 @@
struct GPUNode;
struct GPUNodeStack;
struct SimulationContext;
+struct SimNodeThreadContext;
struct SimNodeJob;
struct PointerRNA;
struct bContext;
@@ -110,8 +111,10 @@
int (*gpufunc)(struct GPUMaterial *mat, struct bNode *node, struct GPUNodeStack *in, struct GPUNodeStack *out);
/* simulation nodes */
- int (*sim_exec)(struct SimulationContext *sim, struct bNode *node, struct SimNodeJob *job);
- int (*sim_opexec)(struct SimulationContext *sim, struct bNode *node, int level, int *r_opsock);
+ int (*sim_execfunc)(struct SimNodeThreadContext *ctx, struct SimNodeJob *job);
+ int (*sim_opexecfunc)(struct SimNodeThreadContext *ctx, struct bNode *node, int level, int *r_opsock);
+ void (*sim_initjobfunc)(struct SimNodeJob *job);
+ void (*sim_endjobfunc)(struct SimNodeJob *job);
} bNodeType;
/* node->exec, now in use for composites (#define for break is same as ready yes) */
@@ -158,6 +161,8 @@
void (*beginExec)(struct bNodeTree *ntree);
void (*endExec)(struct bNodeTree *ntree);
void (*exec)(struct bNodeTree *ntree, void *callerdata, int thread);
+ int (*compatibleSocketTypes)(int type_a, int type_b);
+ int (*preferredSocketType)(int type_a, int type_b);
} bNodeTreeTypeInfo;
/* ************** GENERIC API, TREES *************** */
Modified: branches/particles-2010/source/blender/blenkernel/intern/node.c
===================================================================
--- branches/particles-2010/source/blender/blenkernel/intern/node.c 2010-08-05 11:08:52 UTC (rev 31064)
+++ branches/particles-2010/source/blender/blenkernel/intern/node.c 2010-08-05 11:55:20 UTC (rev 31065)
@@ -1285,7 +1285,7 @@
ntreeEndExecTree(ntree); /* checks for if it is still initialized */
BKE_free_animdata((ID *)ntree);
-
+
BLI_freelistN(&ntree->links); /* do first, then unlink_node goes fast */
for(node= ntree->nodes.first; node; node= next) {
@@ -1706,139 +1706,210 @@
}
}
-static int socktype_greater_than(int a, int b)
+static void printf_socket_islands(bNodeSocketIsland *island, int totsock)
{
- static int prefmap[] = { 0, 6, 5, 0, 1, 2, 3, 4 };
- return prefmap[a] > prefmap[b];
+ int i, number;
+ bNodeSocketIsland *cur;
+
+ number = -1;
+ for (i = 0; i < totsock; ++i, ++island) {
+ if (island->sock->island > number) {
+ number = island->sock->island;
+ printf ("Island %d = { ", number);
+ for (cur = island; cur; cur = cur->next) {
+ printf("%s", cur->sock->name);
+ if (cur->next)
+ printf(", ");
+ }
+ printf(" }\n");
+ }
+ }
}
-static void ntreeUpdateSocketTypes(bNodeTree *ntree)
+static void printf_links(bNodeTree *ntree)
{
+ bNodeLink *link;
+ for (link=ntree->links.first; link; link = link->next) {
+ printf("\t");
+ if (link->fromnode)
+ printf("'%s:%s'", link->fromnode->name, link->fromsock->name);
+ printf(" -> ");
+ if (link->tonode)
+ printf("'%s:%s'", link->tonode->name, link->tosock->name);
+ printf("\n");
+ }
+}
+
+static void merge_socket_type_islands(bNodeSocketIsland *islands, int a, int b)
+{
+ bNodeSocketIsland *i;
+
+ if (a == b)
+ return;
+ if (a < b) {
+ /* merge island b into a */
+ for (i = islands + a; i->next; i = i->next);
+ i->next = islands + b;
+ islands[b].prev = i;
+
+ for (i = islands + b; i; i = i->next)
+ i->sock->island = a;
+ }
+ else {
+ /* merge island a into b */
+ for (i = islands + b; i->next; i = i->next);
+ i->next = islands + a;
+ islands[a].prev = i;
+
+ for (i = islands + a; i; i = i->next)
+ i->sock->island = b;
+ }
+}
+
+static void node_merge_islands(bNode *node, bNodeSocketIsland *islands)
+{
+ bNodeSocket *sock;
+ int any_island = -1;
+ for (sock=node->inputs.first; sock; sock = sock->next) {
+ if (sock->stype->type == SOCK_ANY) {
+ if (any_island > 0)
+ merge_socket_type_islands(islands, any_island, sock->island);
+ else
+ any_island = sock->island;
+ }
+ }
+ for (sock=node->outputs.first; sock; sock = sock->next) {
+ if (sock->stype->type == SOCK_ANY) {
+ if (any_island > 0)
+ merge_socket_type_islands(islands, any_island, sock->island);
+ else
+ any_island = sock->island;
+ }
+ }
+}
+
+static void ntreeFindSocketTypeIslands(bNodeTree *ntree, bNodeSocketIsland **r_islands, int *r_totsock)
+{
bNode *node;
- bNodeSocket *sock, *fromsock;
- int resolved;
+ bNodeSocket *sock;
+ bNodeLink *link;
+ bNodeSocketIsland *islands, *cur;
+ int totsock;
- /* reset SOCK_ANY sockets */
+ /* initialise island indices */
+ totsock = 0;
for (node=ntree->nodes.first; node; node = node->next) {
- for (sock= node->inputs.first; sock; sock = sock->next) {
- if (sock->stype->type == SOCK_ANY)
- sock->type = SOCK_ANY;
+ for (sock=node->inputs.first; sock; sock = sock->next)
+ sock->island = totsock++;
+ for (sock=node->outputs.first; sock; sock = sock->next)
+ sock->island = totsock++;
+ }
+
+ /* create the island pointer array */
+ cur = islands = MEM_callocN(totsock * sizeof(bNodeSocketIsland), "bNodeSocketIsland");
+ for (node=ntree->nodes.first; node; node = node->next) {
+ for (sock=node->inputs.first; sock; sock = sock->next) {
+ cur->sock = sock;
+ cur->next = cur->prev = NULL;
+ ++cur;
}
- for (sock= node->outputs.first; sock; sock = sock->next) {
- if (sock->stype->type == SOCK_ANY)
- sock->type = SOCK_ANY;
+ for (sock=node->outputs.first; sock; sock = sock->next) {
+ cur->sock = sock;
+ cur->next = cur->prev = NULL;
+ ++cur;
}
}
- /* repeat this until no more sockets can be resolved */
- /* Note: this is kind of a brute-force approach, but it's not a speed-critical
- * area and not extremely bad either. Also the number of nodes will probably not be
- * big enough to make this noticable, but if necessary a breadth-first-search method
- * to find "type islands" could be implemented later. - phonybone */
- do {
- resolved = 0;
-
- /* first resolve types from outputs (left to right) */
- for (node=ntree->nodes.first; node; node = node->next) {
- /* only atomic nodes get resolved. */
- if (node->type == NODE_GROUP) {
- /* TODO */
- }
- else {
- for (sock= node->inputs.first; sock; sock = sock->next) {
- if (sock->link && sock->link->fromsock) {
- fromsock = sock->link->fromsock;
- if (sock->stype->type == SOCK_ANY && socktype_greater_than(fromsock->type, sock->type)) {
- sock->type = fromsock->type;
- ++resolved;
- }
- }
+ /* merge islands inside nodes */
+ for (node=ntree->nodes.first; node; node = node->next) {
+ node_merge_islands(node, islands);
+ }
+ /* merge islands by links */
+ for (link=ntree->links.first; link; link = link->next) {
+ if (link->fromsock && link->tosock)
+ if (link->fromsock->stype->type == SOCK_ANY || link->tosock->stype->type == SOCK_ANY)
+ merge_socket_type_islands(islands, link->fromsock->island, link->tosock->island);
+ }
+
+ *r_islands = islands;
+ *r_totsock = totsock;
+}
+
+static void ntreeUpdateSocketTypes(bNodeTree *ntree)
+{
+ bNodeTreeTypeInfo *tti;
+ bNodeSocketIsland *island_map, *island;
+ int totsock;
+ int i, number;
+ bNodeSocketIsland *cur;
+ int restype, resolved;
+
+ tti = ntreeGetTypeInfo(ntree->type);
+ if (!tti->preferredSocketType || !tti->compatibleSocketTypes)
+ return;
+
+ ntreeFindSocketTypeIslands(ntree, &island_map, &totsock);
+
+ printf("Socket Islands:\n");
+ printf_socket_islands(island_map, totsock);
+
+ number = -1;
+ island = island_map;
+ for (i = 0; i < totsock; ++i, ++island) {
+ if (island->sock->island > number) {
+ number = island->sock->island;
+ resolved = 0;
+ restype = SOCK_ANY;
+ for (cur = island; cur; cur = cur->next) {
+ if (!resolved) {
+ restype = cur->sock->type;
+ resolved = (cur->sock->stype->type != SOCK_ANY);
}
- }
- }
- /* now resolve remaining types from inputs (right to left) */
- for (node=ntree->nodes.last; node; node = node->prev) {
- /* only atomic nodes get resolved. */
- if (node->type == NODE_GROUP) {
- /* TODO */
- }
- else {
- /* choose the "best" socket type for output sockets among the linked sockets */
- for (sock= node->inputs.first; sock; sock = sock->next) {
- if (sock->link && sock->link->fromsock) {
- fromsock = sock->link->fromsock;
- if (fromsock->stype->type == SOCK_ANY && socktype_greater_than(sock->type, fromsock->type)) {
- fromsock->type = sock->type;
- ++resolved;
- }
+ else {
+ /* restype == SOCK_ANY means the island contains incompatible types and cannot be resolved! */
+ if (restype != SOCK_ANY && cur->sock->stype->type != SOCK_ANY) {
+ if (tti->compatibleSocketTypes(restype, cur->sock->type))
+ restype = tti->preferredSocketType(restype, cur->sock->type);
+ else
+ restype = SOCK_ANY;
}
}
}
- }
-
- /* finally upgrade socket types if possible */
- for (node=ntree->nodes.first; node; node = node->next) {
- int besttype = -1;
- for (sock= node->inputs.first; sock; sock = sock->next) {
- if (sock->stype->type == SOCK_ANY && socktype_greater_than(sock->type, besttype))
- besttype = sock->type;
- }
- for (sock= node->outputs.first; sock; sock = sock->next) {
- if (sock->stype->type == SOCK_ANY && socktype_greater_than(sock->type, besttype))
- besttype = sock->type;
- }
- if (besttype >= 0) {
- for (sock= node->inputs.first; sock; sock = sock->next) {
- if (sock->stype->type == SOCK_ANY) {
- sock->type = besttype;
- }
- }
- for (sock= node->outputs.first; sock; sock = sock->next) {
- if (sock->stype->type == SOCK_ANY) {
- sock->type = besttype;
- }
- }
- }
+ for (cur = island; cur; cur = cur->next)
+ if (cur->sock->stype->type == SOCK_ANY)
+ cur->sock->type = restype;
}
- } while (resolved > 0);
+ }
+
+ MEM_freeN(island_map);
}
static void ntreeUpdateLinks(bNodeTree *ntree)
{
+ bNodeTreeTypeInfo *tti = ntreeGetTypeInfo(ntree->type);
bNodeLink *link;
- for (link = ntree->links.first; link; link = link->next) {
- int valid = 1;
- if (link->fromsock == NULL || link->tosock == NULL) {
- /* don't assume bad links when they're incomplete (e.g. in modal operator) */
- valid = 1;
- }
- else {
- int fromtype = link->fromsock->type;
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list