Data structure for triangle meshes(redblobgames.com)
redblobgames.com
Data structure for triangle meshes
http://www.redblobgames.com/x/1722-b-rep-triangle-meshes/
3 comments
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
[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
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
[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!
The list is huge!
mapping and path planning in robotics comes to mind
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).