It seems really hard to check whether something in a mesh intersects with itself (at least with halfedge data structures) since it seems like you would have to check every single halfedge.
clam
Are detections of collisions of large meshes something that will take a large animation studio hours to do? Or have algorithms become optimized enough to the point where its possible to do real-time, or somewhere in between? The fact that this is such a difficult problem to the point where entirely new data structures need to be developed for just geometric problems is very interesting to me.
keenan
@raymondx You're right that if all you have is a topological mesh data structure (like halfedge, or vertex-face adjacency list) then there's no great algorithm to check for self-intersection other than trying all pairs (though maybe you have some clever heuristics, like using normal bounds). The right tool for the job is really a spatial data structure, like a BVH, kd-tree, etc.
keenan
@clam If you're using a good spatial data structure, you can actually make collision detection quite fast. For instance, the image above comes from a fast GPU-accelerated scheme. Real time is not outside the realm of possibility. But it is indeed very interesting how these different geometric problems lead to the development of very different data structures!
It seems really hard to check whether something in a mesh intersects with itself (at least with halfedge data structures) since it seems like you would have to check every single halfedge.
Are detections of collisions of large meshes something that will take a large animation studio hours to do? Or have algorithms become optimized enough to the point where its possible to do real-time, or somewhere in between? The fact that this is such a difficult problem to the point where entirely new data structures need to be developed for just geometric problems is very interesting to me.
@raymondx You're right that if all you have is a topological mesh data structure (like halfedge, or vertex-face adjacency list) then there's no great algorithm to check for self-intersection other than trying all pairs (though maybe you have some clever heuristics, like using normal bounds). The right tool for the job is really a spatial data structure, like a BVH, kd-tree, etc.
@clam If you're using a good spatial data structure, you can actually make collision detection quite fast. For instance, the image above comes from a fast GPU-accelerated scheme. Real time is not outside the realm of possibility. But it is indeed very interesting how these different geometric problems lead to the development of very different data structures!