FDGL: Improve flow-directed layout.

Allow apps to specify nodes as sources to improve layout.


git-svn-id: http://svn.drobilla.net/lad/trunk/ganv@5185 a436a847-0d15-0410-975c-d299462d15a1

5 files changed, 104 insertions, 45 deletions

diff --git a/src/Canvas.cpp b/src/Canvas.cpp
index 21b6255..20180e3 100644
--- a/src/Canvas.cpp
+++ b/src/Canvas.cpp
@@ -731,30 +731,14 @@ apply_force(GanvNode* a, GanvNode* b, const Vector& f)
 gboolean
 GanvCanvasImpl::layout_iteration()
 {
-	// Calculate repelling forces between nodes
-	FOREACH_ITEM(_items, i) {
-		if (!GANV_IS_MODULE(*i) && !GANV_IS_CIRCLE(*i)) {
-			continue;
-		}
-		GanvNode* const node = GANV_NODE(*i);
-		const Region    reg  = get_region(node);
-
-		FOREACH_ITEM(_items, j) {
-			if (i == j || (!GANV_IS_MODULE(*i) && !GANV_IS_CIRCLE(*i))) {
-				continue;
-			}
-			GanvNode* const node2 = GANV_NODE(*j);
-			const Region    reg2  = get_region(node2);
-			apply_force(node, node2, repel_force(reg, reg2));
-		}
+	static const double SPRING_K = 14.0;
 
-		// Add fake long spring to partner to line up as if connected
-		GanvNode* partner = ganv_node_get_partner(node);
-		if (partner) {
-			const Region preg = get_region(partner);
-			apply_force(node, partner,
-			            spring_force(preg.pos, reg.pos, preg.area.x));
-		}
+	// A light directional force to push sources to the top left
+	static const double DIR_MAGNITUDE = -300.0;
+	Vector              dir           = { 0.0, 0.0 };
+	switch (_gcanvas->direction) {
+	case GANV_DIRECTION_RIGHT: dir.x = DIR_MAGNITUDE; break;
+	case GANV_DIRECTION_DOWN:  dir.y = DIR_MAGNITUDE; break;
 	}
 
 	// Calculate attractive spring forces for edges
@@ -772,19 +756,57 @@ GanvCanvasImpl::layout_iteration()
 			continue;
 		}
 
-		// Add slight directional force to push sinks to the right/down
-		static const double DIR_MAGNITUDE = -400.0;
-		Vector              dir           = { 0.0, 0.0 };
-		switch (_gcanvas->direction) {
-		case GANV_DIRECTION_RIGHT: dir.x = DIR_MAGNITUDE; break;
-		case GANV_DIRECTION_DOWN:  dir.y = DIR_MAGNITUDE; break;
-		}
+		head->impl->has_in_edges  = TRUE;
+		tail->impl->has_out_edges = TRUE;
 
 		const Vector tpos = { edge->impl->coords.x1, edge->impl->coords.y1 };
 		const Vector hpos = { edge->impl->coords.x2, edge->impl->coords.y2 };
-		const Vector f    = vec_add(dir, spring_force(hpos, tpos, 0.5));
 
-		apply_force(tail, head, f);
+		apply_force(tail, head, edge_force(dir, hpos, tpos, 0.0001, SPRING_K));
+	}
+
+	// Calculate repelling forces between nodes
+	FOREACH_ITEM(_items, i) {
+		if (!GANV_IS_MODULE(*i) && !GANV_IS_CIRCLE(*i)) {
+			continue;
+		}
+		GanvNode* const node = GANV_NODE(*i);
+		const Region    reg  = get_region(node);
+
+		GanvNode* partner = ganv_node_get_partner(node);
+		if (partner) {
+			// Add fake long spring to partner to line up as if connected
+			const Region preg = get_region(partner);
+			apply_force(node, partner,
+			            edge_force(dir, preg.pos, reg.pos,
+			                       preg.area.x, SPRING_K));
+		}
+
+		if (node->impl->is_source) {
+			// Add fake weak spring from origin to sources to anchor graph layout
+			const Vector anchor = { 16.0, 16.0 };
+			node->impl->force = vec_add(
+				node->impl->force,
+				spring_force(anchor, reg.pos, 12.0, SPRING_K / 6.0));
+		} else if (!node->impl->partner &&
+		           !node->impl->has_in_edges &&
+		           !node->impl->has_out_edges) {
+			// Not a source and disconnected, don't repel other nodes
+			continue;
+		}
+
+		FOREACH_ITEM(_items, j) {
+			if (i == j || (!GANV_IS_MODULE(*i) && !GANV_IS_CIRCLE(*i))) {
+				continue;
+			}
+			GanvNode* const node2 = GANV_NODE(*j);
+			if ((!node2->impl->has_in_edges && !node2->impl->has_out_edges) &&
+			    !node2->impl->is_source) {
+				continue;
+			}
+
+			apply_force(node, node2, repel_force(reg, get_region(node2)));
+		}
 	}
 
 	// Update positions based on calculated forces
@@ -796,10 +818,12 @@ GanvCanvasImpl::layout_iteration()
 
 		GanvNode* const node = GANV_NODE(*i);
 
-		static const float dur  = 0.1;  // Time duration
+		static const float dur  = 0.15;  // Time duration
 		static const float damp = 0.7;  // Velocity damping (momentum loss)
 
-		if (node->impl->grabbed) {
+		const bool has_edges = (node->impl->has_in_edges ||
+		                        node->impl->has_out_edges);
+		if (node->impl->grabbed || (!has_edges && !node->impl->is_source)) {
 			node->impl->vel.x = 0.0;
 			node->impl->vel.y = 0.0;
 		} else {
@@ -816,8 +840,10 @@ GanvCanvasImpl::layout_iteration()
 		}
 
 		// Reset forces for next time
-		node->impl->force.x = 0.0;
-		node->impl->force.y = 0.0;
+		node->impl->force.x       = 0.0;
+		node->impl->force.y       = 0.0;
+		node->impl->has_in_edges  = FALSE;
+		node->impl->has_out_edges = FALSE;
 	}
 
 	if (n_moved == 0) {
diff --git a/src/fdgl.hpp b/src/fdgl.hpp
index b28df82..42b3538 100644
--- a/src/fdgl.hpp
+++ b/src/fdgl.hpp
@@ -16,8 +16,8 @@
 #include <float.h>
 #include <math.h>
 
-static const double SPRING_K    = 14.0;
-static const double CHARGE_KE   = 60000.0;
+static const double SPRING_K    = 16.0;
+static const double CHARGE_KE   = 40000.0;
 static const double AREA_WEIGHT = 0.5;
 
 struct Region {
@@ -61,12 +61,23 @@ vec_rmag(const Vector& vec)
 
 /** Hooke's law */
 inline Vector
-spring_force(const Vector& a, const Vector& b, const double length)
+spring_force(const Vector& a, const Vector& b, double length, double k)
 {
 	const Vector vec          = vec_sub(b, a);
 	const double rmag         = vec_rmag(vec);
 	const double displacement = length - (1.0 / rmag);
-	return vec_mult(vec, rmag * SPRING_K * displacement * 0.5);
+	return vec_mult(vec, rmag * k * displacement * 0.5);
+}
+
+/** Spring force with a directional force to align with flow direction. */
+static const Vector
+edge_force(const Vector& dir,
+           const Vector& hpos,
+           const Vector& tpos,
+           double        length,
+           double        k)
+{
+	return vec_add(dir, spring_force(hpos, tpos, length, k));
 }
 
 /** Modified Coulomb's law */
diff --git a/src/ganv-private.h b/src/ganv-private.h
index bc09505..272381d 100644
--- a/src/ganv-private.h
+++ b/src/ganv-private.h
@@ -108,6 +108,7 @@ struct _GanvNodeImpl {
 	guint             layer;
 	gboolean          can_tail;
 	gboolean          can_head;
+	gboolean          is_source;
 	gboolean          selected;
 	gboolean          highlighted;
 	gboolean          draggable;
@@ -116,6 +117,8 @@ struct _GanvNodeImpl {
 #ifdef GANV_FDGL
 	Vector            force;
 	Vector            vel;
+	gboolean          has_in_edges;
+	gboolean          has_out_edges;
 #endif
 };
 
diff --git a/src/module.c b/src/module.c
index f685a99..507da22 100644
--- a/src/module.c
+++ b/src/module.c
@@ -832,4 +832,3 @@ ganv_module_for_each_port(GanvModule*  module,
 
 	free(copy);
 }
-
diff --git a/src/node.c b/src/node.c
index af487c2..5fe09a3 100644
--- a/src/node.c
+++ b/src/node.c
@@ -42,6 +42,7 @@ enum {
 	PROP_BORDER_COLOR,
 	PROP_CAN_TAIL,
 	PROP_CAN_HEAD,
+	PROP_IS_SOURCE,
 	PROP_SELECTED,
 	PROP_HIGHLIGHTED,
 	PROP_DRAGGABLE
@@ -64,16 +65,19 @@ ganv_node_init(GanvNode* node)
 	impl->border_color = DEFAULT_BORDER_COLOR;
 	impl->can_tail     = FALSE;
 	impl->can_head     = FALSE;
+	impl->is_source    = FALSE;
 	impl->selected     = FALSE;
 	impl->highlighted  = FALSE;
 	impl->draggable    = FALSE;
 	impl->show_label   = TRUE;
 	impl->grabbed      = FALSE;
 #ifdef GANV_FDGL
-	impl->force.x      = 0.0;
-	impl->force.y      = 0.0;
-	impl->vel.x        = 0.0;
-	impl->vel.y        = 0.0;
+	impl->force.x       = 0.0;
+	impl->force.y       = 0.0;
+	impl->vel.x         = 0.0;
+	impl->vel.y         = 0.0;
+	impl->has_in_edges  = FALSE;
+	impl->has_out_edges = FALSE;
 #endif
 }
 
@@ -145,6 +149,7 @@ ganv_node_set_property(GObject*      object,
 		SET_CASE(BORDER_COLOR, uint, impl->border_color);
 		SET_CASE(CAN_TAIL, boolean, impl->can_tail);
 		SET_CASE(CAN_HEAD, boolean, impl->can_head);
+		SET_CASE(IS_SOURCE, boolean, impl->is_source);
 		SET_CASE(HIGHLIGHTED, boolean, impl->highlighted);
 		SET_CASE(DRAGGABLE, boolean, impl->draggable);
 	case PROP_SELECTED:
@@ -204,6 +209,7 @@ ganv_node_get_property(GObject*    object,
 		GET_CASE(BORDER_COLOR, uint, impl->border_color);
 		GET_CASE(CAN_TAIL, boolean, impl->can_tail);
 		GET_CASE(CAN_HEAD, boolean, impl->can_head);
+		GET_CASE(IS_SOURCE, boolean, impl->is_source);
 		GET_CASE(SELECTED, boolean, impl->selected);
 		GET_CASE(HIGHLIGHTED, boolean, impl->highlighted);
 		GET_CASE(DRAGGABLE, boolean, impl->draggable);
@@ -636,6 +642,14 @@ ganv_node_class_init(GanvNodeClass* klass)
 			G_PARAM_READWRITE));
 
 	g_object_class_install_property(
+		gobject_class, PROP_IS_SOURCE, g_param_spec_boolean(
+			"is-source",
+			_("Is source"),
+			_("Whether this object should be positioned at the start of signal flow."),
+			0,
+			G_PARAM_READWRITE));
+
+	g_object_class_install_property(
 		gobject_class, PROP_SELECTED, g_param_spec_boolean(
 			"selected",
 			_("Selected"),
@@ -698,6 +712,12 @@ ganv_node_can_head(const GanvNode* self)
 	return self->impl->can_head;
 }
 
+void
+ganv_node_set_is_source(const GanvNode* node, gboolean is_source)
+{
+	node->impl->is_source = is_source;
+}
+
 gboolean
 ganv_node_is_within(const GanvNode* node,
                     double          x1,