Data structure for triangle meshes | Hacker News Reader

Data structure for triangle meshes

redblobgames.com

92 pointsthe-enemy12 comments

Another particular interesting representation is Guibas and Stolfi's "quadedge" data structure from their 1985 paper at "Primitives for the manipulation of general subdivisions and the computation of Voronoi," source http://dl.acm.org/citation.cfm?doid=282918.282923 and pdf at http://www.sccg.sk/~samuelcik/dgs/quad_edge.pdf.

It really is an elegant use of some basic topology with impressive results, a full Voronoi/Delaunay linear-log time algorithm in less than a page of easily implementable pseudocode (once the data structure is written).

Careful, that pseudocode has a famous error in it. Finding it is an illuminating exercise.

Could you give more details?

I believe the error is only in the incremental algorithm. Spoiler: https://people.eecs.berkeley.edu/~jrs/meshpapers/GSflaws.

Amit's pages in general [0][1] are an absolutely amazing and invaluable source of high-quality game programming information.

[0] http://www.redblobgames.com/

[1] http://www-cs-students.stanford.edu/~amitp/gameprog.html

I think they're great too. I'm a complete novice to game development and my normal dev gig doesn't require much understanding of the math I learned in high school.

I needed to draw lines in a little thing I'm doing for https://itch.io/jam/cga-jam and stumbled across http://www.redblobgames.com/grids/line-drawing.html

Implemented it last night and it worked wonderfully.

http://ix.io/wSG/nim

This is cool. Does it have applications beyond computer graphics?

It would provide a fast, grid-like interpolation for any 2D data: think geospatial, GIS, etc. If I understand correctly, could also be used recursively to provide a lazy (but inefficient) way to calculate locations to an arbitrary precision.

Reminds me of topojson[0], a GeoJSON extension, that encodes features as topologies, instead of geometries.

[0]: https://github.com/topojson

Meshes are used in various kinds of simulation calculations: https://en.wikipedia.org/wiki/Finite_element_method ; there's also discrete exterior calculus: http://brickisland.net/cs177fa12/?cat=5

"various" is a crazy simplification: the propogation of radiation (think modeling wifi antenna output, on-chip photonic components, etc.), thermal properties of various electrical objects (think like exact temerature distribution across a resistor, heat distribution around a CPU, jet engines), modelling various materials for mechanical sturdiness and springiness, fluid modelling (the weather, aerodynamicity, etc.).

The list is huge!

mapping and path planning in robotics comes to mind

Reply on news.ycombinator.com