利用者:Ansimionescu/Notes/Geometry
目次
Convex/concave/tangent/reflex points
A vertex in a polygon can be of three kinds, depending of the value of alpha, the angle made by the polygon at that vertex:
- alpha < pi: convex vertex
- alpha = pi: tangential point
- alpha > pi: reflex point OR concave point
Ear clipping
In a polygon, P, three "consecutive" vertices, vi, vj, vk, form an ear if vi, vk is a diagonal of P. (It's been proved that every simple polygon that is not a triangle has at least two non-overlapping ears.) The ear is clipped by connecting vi and vk with an additional edge.
FIST uses repeated ear clippings to create a triangulation. More on wikipedia.
Earity test
Determining if a triplet of vertices form an ear with respect to a polygon.
Non-simple polygons / degenerate cases
A simple polygon is usually one that doesn't have:
- self-intersections
- an edge passing through another vertex
- zero-length edges
- edges that partially overlap
- holes that overlap with the outer boundary
Subdivision
Subdivision is a term borrowed by computer graphics from graph theory.
in graph theory
In general, a subdivision of a graph G is a graph resulting from the subdivision of edges in G. The subdivision of some edge e with endpoints {u,v} yields a graph containing one new vertex w, and with an edge set replacing e by two new edges, {u,w} and {w,v}.
The reverse operation, smoothing out or smoothing a vertex w with regards to the pair of edges (e,f) incident on w, removes both edges containing w and replaces (e,f) with a new edge that connects the other endpoints of the pair. Only 2-valent vertices can be smoothed.
in computer graphics
The wikipedia definition:
A subdivision surface, in the field of 3D computer graphics, is a method of representing a smooth surface via the specification of a coarser piecewise linear polygon mesh. The smooth surface can be calculated from the coarse mesh as the limit of a recursive process of subdividing each polygonal face into smaller faces that better approximate the smooth surface.
Basically, there are a couple of methods of representing
Trapezoidal decomposition
More types of subdivision decomposition on Wikipedia.
Triangulating a 3D polygon
The non-planar (i.e., 3D) cases are handled by choosing an axis to project the 3D polygon onto a convenient plane. FIST, for example, uses a "reliable heuristic for finding a decent plane".
Obviously, this approach may create some inconveniences:
- co-planar vertices
- special cases that can create bugs (??)
