LAND 655 Project 2: Optimize mesh cells with generic algorithm and scripting

 

Presentation Video

This study aims to optimize the mesh cells to make the mesh edges approach same lengths. Method 1 is to use kangaroo physic simulator and Galapagos solver to find the most appropriate rest length and strength of mesh edges as springs, in order to achieve the lowest standard deviation of edge lengths. The lowest standard deviation of mesh edges represent the situation that mesh edges are most similar to each other and least deviated from the average length. Method 2 will calculate the new position of each mesh vertex based on the middle point of its six closed neighboring vertices on the mesh. The method 2 process will repeat in multiple loops until the standard deviation reach the lowest value possible. 

Method One: Mesh relation with Kangaroo and Galapagos solver

The graph below shows the basic model of this method. The rest length and spring strength are used as the genomes of Galapagos solver, which will be input variables. The standard deviation of mesh edge lengths is used as the fitness value, which will represent the performance of the model. The Galapagos solver is set to look for the variables resulting in the lowest possible value of standard deviation as the best model. 

Python scripting is used to calculate the standard deviation. Since the standard deviation output in this code involves an extra square root calculation that will increase calculation burden, the later model used the variances as the fitness value to increase calculation speed. 

In the first several attempts, it is found that the Galapagos solver tends to give the best model with longest rest length possible that cannot shrink to a flat and smooth mesh during kangaroo spring simulation. It can be explained as the Galapagos solver thinks longer spring length leads a lower standard deviation. However, we have to purposively maintain the mesh as a flat and clean surface as an architectural component. The later model adds punishment modules to reduce such behaviors. The spring strength is visibly associated with anchor point movement, which means that when the spring strength is too large, the anchor point will significantly deviated from its original position. The movement of anchor point is undesirable because the mesh shape need to be preserved to fit into the outside architecture. The total moving distance of all anchor points is also added into the punishment module.

The total moving distance of all anchor points is got from the mass addition of all vector length from the new position of anchor points to their original positions. The total moving distance is added to the final fitness value. The longer moving distance will indicate a worse model performance. 

When observing the appropriate interval for spring length, it can be visually observed that the spring length over 3 makes distorted mesh. The initial slider is set to be from 0.0000 to 3.0000. The spring length under 2 generally produce reasonable mesh appearances . In order to find the best spring length value that doesn't break mesh surface but still give the lowest standard deviation, the punish module will multiple a large value of the portion of  spring rest length over 2 and add it to the final fitness value. 

The final model considers the best inputs are 0.1998 spring length and 1 spring strength. The lowest standard deviation got from this method is 0.112266. The output mesh is shown below.

Method Two: Recalculating mesh vertices based on neighboring points

The algorithm of this method can be simply explained as calculating the new position of each clothed vertices on mesh to be the center point of its six nearest neighbor on mesh. It involves steps below:

1. Finding the six neighbors of each clothed point on mesh (grasshopper "nakedvertices" node and Kangaroo plugin "VerticesNeighbor" node)
2. Calculating their center point (grasshopper "average" node)
3. Move each clothed vertices to their new position ("Vector2Pt" and "move" nodes)

Besides the algorithm. one of the key issues of this method is to establish the mesh with vertices in their new positions. This could be made possible with python scripting to capture the mesh vertices as a data list and replace the data list with new data. It is still relevant to the fundamental logic of how to construct a mesh.

To construct a mesh in grasshopper using "construct mesh" node, we need all the vertices on the mesh and corresponding mesh faces (vertex color is optional). The mesh faces are little triangles composed of three vertices. Each mesh vertices have an index in their data list. As long as the point list order is not changed, the mesh can be constructed with the original face data list and the new vertices data list with recalculated positions.

To verify this theory, I experimented from deconstructing a mesh and moving all vertices to a new position and then constructing a new mesh with the original face data and new vertices data, which worked fine. 

Since the project will only move the clothed vertices. I also tested if moving a part of the vertices influencing the final result, which also worked flawlessly.

To verify if the list order of vertices influencing the mesh construction, I used the "naked vertices" node to split all vertices into clothed and naked, and then simply flattened the two data list as the vertex data, which creates a crushed mesh surface with messy edges, because the data list order has been randomly shifted. After I sort the point list based on their original index, the mesh can be constructed normally. In the newer model, I implemented python scripting node to simply replace all clothed point position data their corresponding new position. 

Then I use anemone plugin to loop the process of deconstruct mesh - reposition vertices - construct mesh. I set initial loop numbers to be 1000, and output its mesh length standard deviation. During the loops, it's found that the standard deviation is not continuously reducing but stopping at a certain value. More loops will not bring down the standard deviation.

I plotted the loop number and standard deviation as a scatter point graph to find out its changing trend. The loop number is on x-axis, and the standard deviation is on the y-axis. To make the trend more visible, the y-axis is exaggerated 10000 times. 

The trend shows that the standard deviation is decreasing at first 1 -23 loops, but gradually increase and stabilize at a certain value when loop numbers increase.  The lowest standard deviation is got when loop number is 23. It can be explained because during each loop the new position of each vertices are based on their original neighbor vertices, but their position actually changed in the process. For each loop, it brings in some position errors because the average position is not updated with their neighbor's new position. The accumulated errors result that the standard deviation cannot be eliminated by the end. 

The resulting mesh is shown below. The lowest standard deviation from this method is still higher than it from the previous method. 

Looping animation

Conclusion:

Both methods make great optimization for the input meshes. The standard deviation for mesh edges is lower in both methods, which means the mesh cells become more even and more visually appealing. Although the second model produces a slightly higher standard deviation than method one, the results still improve from the input mesh. And the second method calculation cost significantly shorter time than the first method which employs generic algorithm. The first method generally takes over one hour for the solver to get the best model. The second models run less than 30 seconds even for 1000 loops. Loops less than 100 are completed within seconds. Both methods have their applicable occasions based on project preference on precision or on calculation speed. 

Reference

1. The mesh data structure in Grasshopper - James Ramsden (james-ramsden.com)

2. Mesh Vertex Neighbours - Grasshopper (grasshopper3d.com)

3. Vertex Neighbours - Kangaroo 2 - Component for Grasshopper | Grasshopper Docs

4. How to move mesh vertices in script? - Scripting - McNeel Forum