With this half-edge data structure, is it easy to tell if a point is within the solid, or like on a face?
clam
This representation was very interesting to me since it seemed to so immediately pin down what properties of manifolds/meshes matter in a way that managed to be simple and obvious. I am interested in what sorts of efforts have taken place into making this structure faster/more coherent/cache-local in practice: I looked at geometry-central.net and scanned over the source for how things we're stored and it seemed to be just a struct-of-array (using vectors as arenas) representation with some extra tricks. Is this something that is researched much (is it even close to enough a bottleneck to matter)?
keenan
@ngandhi Nope, the halfedge data structure doesn't help with that kind of query. We'll talk about a different kind of data structure, "spatial data structures," which help with such queries a couple lectures from now.
keenan
@clam Here's a survey I wrote on cache-efficient mesh layouts many years ago. It would be awesome to apply some of these principles to a more cache-friendly halfedge data structure (especially one that maintains/improves coherence as you perform local operations).
With this half-edge data structure, is it easy to tell if a point is within the solid, or like on a face?
This representation was very interesting to me since it seemed to so immediately pin down what properties of manifolds/meshes matter in a way that managed to be simple and obvious. I am interested in what sorts of efforts have taken place into making this structure faster/more coherent/cache-local in practice: I looked at geometry-central.net and scanned over the source for how things we're stored and it seemed to be just a struct-of-array (using vectors as arenas) representation with some extra tricks. Is this something that is researched much (is it even close to enough a bottleneck to matter)?
@ngandhi Nope, the halfedge data structure doesn't help with that kind of query. We'll talk about a different kind of data structure, "spatial data structures," which help with such queries a couple lectures from now.
@clam Here's a survey I wrote on cache-efficient mesh layouts many years ago. It would be awesome to apply some of these principles to a more cache-friendly halfedge data structure (especially one that maintains/improves coherence as you perform local operations).