In the previous tutorial I’ve tried to explain how to write recursive Vex code. Now we will put this information to good use and craft ourself a spanning tree that will come handy in a later tutorial.

A spanning tree is actually a kind of graph that connects every primitive once and once only. A spanning tree can be binary, tertiary or have any arbitrary branching but it has a condition that it can not have cycles and can’t be discrete.

A simple spanning tree

A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected..

www.tutorialspoint.com/data_structures_algorithms/spanning_tree.htm

In the next tutorial I will show how to unfold an object into a plane and for that process we will need a spanning tree to connect each edge to a parent.

To be able to create a spanning tree that connects each vertices (not to be confused with Houdini vertex. This is a point in Houdini but becomes a vertex for tree) we need to implement Prim’s algorithm. This is a minimum cost spanning tree algorithm and we will use point distances as cost.

What we need is two arrays that hold reached and unreached points. We fill the unreached points array with all the points and leave the reached array empty.

For the first iteration we push the first element in unreached array to reached and start comparing distances for each elements in both arrays in a nested for loop. Once we find the point with lowest distance, we record the indexes for points in each array. After the for loops are done we add a primitive connection and remove the point from unreached array and add it to reached.

In the next tutorial we will take a look at the folding process using the newly created spanning tree. Our tree will give us information about child-parent relationships and connectivitiy data.

Unfolding spanning tree

Until next tutorial see what a folding object looks like.

Thank you for reading! If you would like an example, you can purchase the Houdini file below and try to understand the algorithm.

Spanning Tree on