Deterministic Linear Time Constrained Triangulation Using Simplified Earcut.

Triangulation algorithms that conform to a set of non-intersecting input segments typically proceed in an incremental fashion, by inserting points first, and then segments. Inserting a segment amounts to: (1) deleting all the triangles it intersects; (2) filling the so generated hole with two polygons that have the wanted segment as shared edge; (3) triangulate each polygon separately. In this article we prove that these polygons are such that all their convex vertices but two can be used to form triangles in an earcut fashion, without the need to check whether other polygon points are located within each ear.

Scalable Mesh Refinement for Canonical Polygonal Schemas of Extremely High Genus Shapes.

Any closed manifold of genus g can be cut open to form a topological disk and then mapped to a regular polygon with 4g sides. This construction is called the canonical polygonal schema of the manifold, and is a key ingredient for many applications in graphics and engineering, where a parameterization between two shapes with same topology is often needed. The sides of the 4g-gon define on the manifold a system of loops, which all intersect at a single point and are disjoint elsewhere.

Reconstructing the Curve-Skeletons of 3D Shapes Using the Visual Hull.

Curve-skeletons are the most important descriptors for shapes, capable of capturing in a synthetic manner the most relevant features. They are useful for many different applications: from shape matching and retrieval, to medical imaging, to animation. This has led, over the years, to the development of several different techniques for extraction, each trying to comply with specific goals.