Nonobtuse mesh: Difference between revisions
Content deleted Content added
No edit summary |
m Open access bot: doi added to citation with #oabot. |
||
| (31 intermediate revisions by 18 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Polygon mesh composed of triangles with all angles ≤ 90°}} |
|||
A nonobtuse triangle mesh is composed of a set of triangles in which every angle is less than or equal to 90◦; we call these triangles nonobtuse triangles. If each (triangle) face angle is strictly less than 90◦, then the triangle mesh is said to be acute. Immediate benefits of having a nonobtuse or acute mesh include more efficient and more accurate geodesic computation on meshes using fast marching, guaranteed validity for planar mesh embeddings via discrete Harmonic maps, among others. |
|||
In [[computer graphics]], a '''nonobtuse triangle mesh''' is a [[polygon mesh]] composed of a set of [[triangle]]s in which no [[angle]] is obtuse, ''i.e.'' greater than 90°. If each (triangle) face angle is strictly less than 90°, then the [[triangle mesh]] is said to be acute. Every [[polygon]] with <math>n</math> sides has a nonobtuse triangulation with <math>O(n)</math> triangles (expressed in [[big O notation]]), allowing some triangle vertices to be added to the sides and interior of the polygon.<ref name=bmr>{{citation |
|||
The first guaranteed nonobtuse mesh generation in 3D was first introduced in [http://www.geometryprocessing.org/ Eurographics Symposium on Geometry Processing] 2006 by [http://www.cs.sfu.ca/~ysl/personal/ Li] and [http://www.cs.sfu.ca/~haoz/ Zhang]. |
|||
| last1 = Bern | first1 = M. |
|||
| last2 = Mitchell | first2 = S. |
|||
| last3 = Ruppert | first3 = J. |
|||
| doi = 10.1007/BF02570715 |
|||
| issue = 4 |
|||
| journal = Discrete & Computational Geometry |
|||
| mr = 1360945 |
|||
| pages = 411–428 |
|||
| title = Linear-size nonobtuse triangulation of polygons |
|||
| volume = 14 |
|||
| year = 1995| doi-access = free |
|||
}}</ref> These nonobtuse triangulations can be further refined to produce acute triangulations with <math>O(n)</math> triangles.<ref>{{citation |
|||
| last = Maehara | first = H. |
|||
| doi = 10.1006/eujc.2001.0531 |
|||
| issue = 1 |
|||
| journal = European Journal of Combinatorics |
|||
| mr = 1878775 |
|||
| pages = 45–55 |
|||
| title = Acute triangulations of polygons |
|||
| volume = 23 |
|||
| year = 2002| doi-access = free |
|||
}}</ref><ref>{{citation |
|||
| last = Yuan | first = Liping |
|||
| doi = 10.1007/s00454-005-1188-9 |
|||
| issue = 4 |
|||
| journal = Discrete & Computational Geometry |
|||
| mr = 2173934 |
|||
| pages = 697–706 |
|||
| title = Acute triangulations of polygons |
|||
| volume = 34 |
|||
| year = 2005| s2cid = 26601451 |
|||
| doi-access = free |
|||
}}</ref> |
|||
Nonobtuse meshes avoid certain problems of nonconvergence or of convergence to the wrong numerical solution as demonstrated by the [[Schwarz lantern]].<ref name=bmr/> The immediate benefits of a nonobtuse or acute mesh include more efficient and more accurate [[geodesic]] computation using [[fast marching method|fast marching]], and guaranteed validity for planar mesh embeddings via discrete harmonic maps. |
|||
==References== |
==References== |
||
{{reflist}} |
|||
==See also== |
|||
*[[Triangle mesh]] |
|||
[[Category:Computer graphics data structures]] |
|||
*[http://www.cs.sfu.ca/~ysl/personal/publication/sgp06_electronic.pdf Nonobtuse Remeshing and Mesh Decimation] |
|||
[[Category:3D computer graphics]] |
|||
*[http://www.cs.sfu.ca/~ysl/personal/publication/TR-CMPT2006-13.pdf Guaranteed Nonobtuse Meshes via Constrainted Optimizations] |
|||
[[Category:Triangulation (geometry)]] |
|||
Latest revision as of 20:06, 28 January 2023
In computer graphics, a nonobtuse triangle mesh is a polygon mesh composed of a set of triangles in which no angle is obtuse, i.e. greater than 90°. If each (triangle) face angle is strictly less than 90°, then the triangle mesh is said to be acute. Every polygon with sides has a nonobtuse triangulation with triangles (expressed in big O notation), allowing some triangle vertices to be added to the sides and interior of the polygon.[1] These nonobtuse triangulations can be further refined to produce acute triangulations with triangles.[2][3]
Nonobtuse meshes avoid certain problems of nonconvergence or of convergence to the wrong numerical solution as demonstrated by the Schwarz lantern.[1] The immediate benefits of a nonobtuse or acute mesh include more efficient and more accurate geodesic computation using fast marching, and guaranteed validity for planar mesh embeddings via discrete harmonic maps.
References
[edit]- ^ a b Bern, M.; Mitchell, S.; Ruppert, J. (1995), "Linear-size nonobtuse triangulation of polygons", Discrete & Computational Geometry, 14 (4): 411–428, doi:10.1007/BF02570715, MR 1360945
- ^ Maehara, H. (2002), "Acute triangulations of polygons", European Journal of Combinatorics, 23 (1): 45–55, doi:10.1006/eujc.2001.0531, MR 1878775
- ^ Yuan, Liping (2005), "Acute triangulations of polygons", Discrete & Computational Geometry, 34 (4): 697–706, doi:10.1007/s00454-005-1188-9, MR 2173934, S2CID 26601451