An Alternative Approach to a K-D Tree With Houdini

Technical Artist Ricardo Ponce Walks Through His Unconventional Approach to K-D Tree Algorithm With Side FX Houdini

What’s a K-D Tree? It’s shorthand for a k-dimensional tree, or a space partitioning structure. In computer science, a k-d tree can organize data structures and searches. In computer graphics, it can partition or subdivide 3d space.

Technical Artist Ricardo Ponce walks us through his “unconventional” approach to creating a k-d tree algorithm in Houdini. It mainly uses the Carve SOP and a few loops in Houdini 16.5. Ponce calls it unconventional because K-dimensional algorithms usually use neighboring points to define the search trees and also set its constraints. “As opposed to my ‘Parametric Clusters’ project where we utilise some altered Voronoi Fractures, this is a rather unconventional approach to a classic k-dimensional tree algorithm, which is basically a space-partitioning data structure that will only allow for quadrilateral outcomes,” Ponce notes.

Instead, Ponce randomizes the position of every perpendicular hyperplane that can split the primitive into pieces for every iteration. You can do this as many times as you like. “There are a few interesting tips and techniques to be learned from here that can also be easily expandable, and I hope this may somehow be of help or even entertainment for you,” Ponce says about the tutorial

The system creates some delightful images. Have a look at Motion Designer Dimitris Ladopoulos’ work where he subdivided Rembrandt portraits. Ladopoulos used a procedural algorithm designed in Houdini that would subdivide some of his favorite portrait paintings. “The inspiration came from the type of diagrams called ‘treemaps’” Ladopoulos says. “it takes a rectangle and splits it vertically and then horizontally.”