“Well, are you in or are you out?”
Senior high school student Jodi Kramer in the 1993 film Dazed and Confused poses this question to freshman Sabrina Davis, who answers, “In.”
The reference is used in a paper by University of Toronto researchers who have applied the question to the graphics subfield of geometry processing, resulting in promising new directions for 3D printing technology.
“Some of us like to say that a computer graphic is skin deep, in the sense that you’re only seeing its surface,” says Gavin Barill, a master’s student in the department of computer science. “Geometry processing is taking a shape and saying: What can we really do with this? How can we change it? How can we consume it differently?”
The researchers propose a winding number algorithm that can quickly evaluate computer renderings, up to 1,000 times faster, by determining whether the surface is inside or outside.
“Once you know inside, you know outside, and the place in between is the surface,” says Barill, who will present their paper, “Fast Winding Numbers for Soups and Clouds” this weekend at the Association of Computing Machinery’s (ACM) Special Interest Group on Computer and Interactive Techniques (SIGGRAPH), held in Vancouver.
The premier annual event attracts tens of thousands of computation professionals, including software companies and filmmakers. Researchers from U of T’s Dynamic Graphics Project lab have contributed to six papers at this year’s proceedings.
Barrill worked with David I. W. Levin, an assistant professor of computer science and Canada Research Chair in Simulation-Driven Graphics and Fabrication, and Alec Jacobson, an assistant professor and Canada Research Chair in Geometry Processing, as well as Toronto-based industry collaborators Neil G. Dickson of SideFX, a visual effects software company, and Ryan Schmidt of GradientSpace, a 3D software product studio.
Jacobson, who is Barill’s graduate supervisor, is conducting research that focuses on robust geometry processing – taking a shape and using algorithms to define its qualities or help deform it.
“In [Jacobson’s] previous work, he [helped develop] the winding number,” says Barill. “The winding number is a concept that exists in mathematics and it’s a 2D notion. “You have a point, and you have a curve, and it will count how many times the curve wraps around the surface. If it wraps around once, you know you’re inside. And if it wraps around zero times, it means you’re outside [the surface].”
The researchers applied the winding number to 3D, resulting in novel approaches to 3D printing technology.
Barill explains old video games, like The Legend of Zelda, have polygon-looking creatures because surfaces are represented by polygonal triangles, or triangle meshes. Today’s computer graphics can look quite smooth, because the triangle meshes, connected by a series of shared edges, are small. He says the field of computer graphics is advancing beyond the traditional form of representing geometry with triangle meshes. Point clouds present a new form of data.
“A point cloud is just a series of points that would lie on the surface. You might not know what it is. All you have are the [data] points,” he says.
“We noticed that if you have a single point and you want to check if it’s inside a point cloud, it matters to exactly check the ones that it’s close to, and then the ones that are far away from it we can just approximate,” says Barill. “We use a method of approximation rather than checking two million points – that’s a big difference.”
He says a triangle soup – not unlike a bowl of alphabet soup, where the triangles are floating in space – results in a disconnected surface. It’s similar to point clouds, he says, because both have no connection to nearby points or triangles. Using their algorithmic winding number approach to inside and outside segmentation, the researchers found they could 3D print a point cloud, directly from a point cloud.
The research was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), the Canada Research Chairs program, the University of Toronto Connaught Fund and Adobe Systems Inc.