Computer scientists at Carnegie Mellon University are making beautiful shapes by simulating forces that are literally repulsive — like the force between two charged particles.
When computers reason about shapes, they assume that objects can move freely through each other, like a cartoon ghost passing through a wall. As anyone who has ever struggled to untangle a mass of headphone cables knows, that's not how real objects behave — yet it is a common and vexing problem in 3D modeling.
A research team from CMU's School of Computer Science and RWTH Aachen University in Germany developed a method to make sure computer modeled curves and surfaces avoid bumping into each other. By developing fast simulators for repulsive energies, the team can discover the best way to untie complex knots or fill a shape with a mass of ramen noodles. These kinds of tools could help scientists better model the movement of cells in the human body or find safer trajectories for autonomous vehicles.
"Repulsive energies make it easy to animate untangling headphones or unlinking a pair of handcuffs, but that just scratches the surface of what these tools enable," said Chris Yu, a Ph.D. student in computer science who led the team. "We can begin to design more effective artificial tissues and muscles, help robots move safely, make 3D modeling easier, and visualize data more clearly."
Repulsive energies stem from negatively charged particles that want to move away from each other. Left in the open, these particles would continue to move away from each other forever, but when confined to a box they must share the space and spread themselves out as evenly as possible. The team's work applies this same principle to higher-dimensional shapes beyond simple points, forcing curves to wind around themselves and surfaces to wrinkle like folds in the brain.
Keenan Crane, Yu's advisor and the Michael B. Donohue Associate Professor of Computer Science and Robotics at CMU, said the computational aspects of repulsive energies are new in computer graphics and among mathematicians. There have been many algorithms for optimizing the arrangement of points using repulsive energies, but curves and surfaces are relatively unexplored territory.
The team is studying how these computational tools open doors to new applications. "We're really bringing together decades of research from mathematics, computer graphics and high-performance computing to build tools that can help people in the real world," Crane said.
The researchers will present their work at the SIGGRAPH Asia 2021 Conference on Computer Graphics and Interactive Techniques this month in Tokyo. The National Science Foundation, German Research Foundation (DFG), David and Lucile Packard Foundation, Sloan Foundation, Activision Blizzard, Autodesk, Adobe, Disney, and Facebook supported this work.