Have you ever been in a situation where you wanted to create a good-looking and fast proxy representation for your 3D model which contains concavity?
In Houdini, there are a couple of ways to tackle this problem.
1- Converting the model to a VDB volume and then using VDB to Spheres
2- Using the Scatter node with the pscale option enabled such that the object surface can later be addressed by spheres.
3- Using Convex Decomposition node.
4- Using Shrinking-ball Algorithm proposed by Ma et al in 3D medial axis point approximation using nearest neighbors and the normal field.
The first option can't perform well enough in situations where minute details are required besides the input model should be converted to a VDB and then to spheres which takes time and memory and possible loss of details.
The second option applies directly to the object itself and no volume conversion is required. However, this can be challenging since the centers of spheres are located on the object's surface itself. Although spheres can be moved inward in the case of a thin object this process becomes challenging.
The third option is a great way to break down an object into separate convex pieces. It works best with the bullet solver if you simulate an object that contains concavities. The problem is that computing the convex decomposition of the input model can take time due to the complexity of the process besides less control provided by the node.
The shrinking-ball method
The fourth option is to use the shrinking-ball method. In this method, a point cloud is generated that each of which has at least two equidistant points from the point cloud to the object boundary points.
The following image shows you better:
First, let's look at the Pseudo code for this method is:
As we can see this algorithm iteratively shrinks a sphere for each point on input geometry until it can find the closest point which lies on the surface of the sphere.
As we are about to implement it in Houdini we don't need to worry about things like implementing KD trees or querying a list of points within the sphere.
To visualize the above procedure consider the following image:
The algorithm begins its process by assuming a very big circle (in 2D and a sphere in 3D) in which the center lies on the normal of the current point and passes through it then it computes the nearest point from the input geometry to the center of the circle. (Figure 3 a)
Next, it assumes another smaller circle that passes through the two points (one from the previous iteration and another one is the base point) and then finds the nearest point to the center of the circle. (Figure 3 b)
It continues to do this process until it finally converges to the final point. (Figure 3 c and d)
The shrinking-ball implementation
To this end, all we need is a point wrangle with this piece of code:
Recommended by LinkedIn
1 float compute_radius(const vector p, n, q) 2 // Compute radius of the ball that touches points p and q and whose center falls on the normal n from p3 float d = distance(p, q);4 float cos_theta = dot(n, p - q) / d;5 return d / (2 * cos_theta);6 }78 v@N = normalize(v@N);910 float radius = 100;11 int old_point = -1;1213 vector sphere_center = v@P - v@N * radius;14 int near_point = nearpoint(0, sphere_center, radius);1516 while(old_point != near_point)17 {18 vector point_position = point(0, 'P', near_point);19 radius = compute_radius(v@P, v@N, point_position);20 sphere_center = v@P - v@N * radius;21 22 old_point = near_point;23 near_point = nearpoint(0, sphere_center , radius);24 25 old_point = near_point == -1 || near_point == @ptnum ? near_point : old_point; 26 }27 int point = addpoint(0, sphere_center);28 setpointattrib(0, "pscale", point, radius);29 removepoint(0, @ptnum); Lines between 1 to 6 compute the radius of the sphere required in each iteration.
Line 8 computes and normalizes normal vectors of the input model.
Lines 10 and 11 initialize the radius and old_point variables to 100 and -1 respectively.
Line 13 initializes a vector variable called sphere_center which contains the center of the sphere the next line uses this variable to look up for the nearest point from the input model to the sphere's center.
Lines 16 to 26 iteratively shrink down the sphere and look up for more nearest point until it either can't find a new point or return the point index which the point wrangle is currently iterating over. In this case, old_point and near_point become equal, and execution flow exits the loop.
The last 3 lines create a point and then set its pscale attribute to the previously calculated radius then remove the original point respectively.
Resources and results
I used the following papers to get the upcoming results:
1- 3D medial axis point approximation using nearest neighbors and the normal field 2011
2- GEO1015/2018 Lesson 09 The Medial Axis Transform
I tested it on 4 models and Here are the results.
1- Squab
2- Tommy
3- Crag
4- Rubber Toy
The ending
That's it for now I hope it was useful for you and feel free to check the project file out:
https://drive.google.com/file/d/1kYsJN1l9-k2t3PhiJB2A-q5OC4aAqWCG/view?usp=share_link
And if you are interested in these sorts of content why don't you stick around and check other stuff as well on:
https://vimeo.com/nimaghorab
