How the AutoRemesher Quad Extraction Algorithm Converts Triangles to Quad Topology

The AutoRemesher quad extraction algorithm transforms triangle meshes into quad-dominant topology by computing UV isoline intersections to generate cross points, building a connection graph, applying topological simplifications like edge collapsing and degree-2 vertex merging, and finally extracting closed loops of 4–7 vertices to form quadrilateral faces.

The AutoRemesher library by huxingyi/autoremesher implements a sophisticated multi-stage pipeline to remesh arbitrary triangle surfaces into clean, quad-dominant geometry. This article examines the C++ implementation in src/AutoRemesher/quadextractor.cpp to explain exactly how the AutoRemesher quad extraction algorithm converts triangles to quad topology through isoline-based vertex extraction and iterative graph simplification.

Stage 1: Isoline Intersection and Cross Point Generation

The pipeline begins by analyzing the input triangle mesh's UV parameterization to locate where integer-valued isolines intersect the mesh edges.

Computing UV Isoline Intersections

The extractConnections() function (lines 698–720) iterates over every triangle in the source mesh and calculates where the integer UV grid lines cross the triangle edges. These intersection points become cross points that lie exactly on the original surface, serving as candidate vertices for the final quad mesh. The function populates a crossPoints vector and builds a preliminary list of connections (edges) between these points.

Stage 2: Graph Construction and Topological Cleaning

Once cross points are established, the algorithm constructs an undirected adjacency map and applies a series of cleaning operations to remove artifacts that would prevent proper quad formation.

Building the Connection Graph

The extractEdges() function (lines 84–92) copies the initial connection set into edgeConnectMap and immediately calls simplifyGraph() to prepare the data structure for iterative refinement.

Collapsing Short Edges

To eliminate spurious vertices that fragment the topology, collapseShortEdges() (lines 66–94) measures every edge in the graph. Any edge whose length is ≤ 1% of the average edge length is collapsed, merging its vertices and updating the adjacency map. This threshold prevents over-segmentation while preserving significant geometric features.

Simplifying Degree-2 Vertices

The simplifyGraph() function (lines 195–224) repeatedly identifies vertices with exactly two connections (degree-2) and merges them, effectively turning two-edge chains into single direct edges. This reduction eliminates redundant vertices and enforces a cleaner topological structure essential for valid quad extraction.

Removing Dangling Endpoints

The removeSingleEndpoints() function (lines 226–256) detects and prunes "leaf" vertices connected to only one other vertex. Removing these dangling endpoints prevents isolated edges from polluting the mesh and ensures that all remaining vertices participate in meaningful face loops.

Stage 3: Triangle Cycle Collapse

Before quad extraction, the algorithm addresses small triangular configurations that cannot form valid quads.

Merging Small Triangle Cycles

The collapseTriangles() function (lines 58–64) identifies groups of three vertices that form closed triangle cycles. It computes the centroid of each triangle, moves the first vertex to that position, and rewires the connections. This operation transforms small triangles into single vertices, creating opportunities for adjacent geometry to form quadrilateral faces rather than remaining as degenerate triangles.

Stage 4: Polygon Extraction and Mesh Repair

With the graph cleaned and simplified, the algorithm extracts actual polygon faces and repairs boundary defects.

Extracting Quad Polygons

The extractMesh() function (lines 125–195) implements the core extraction logic. It traverses the adjacency map to find closed loops containing 4 to 7 vertices. For each candidate loop, the algorithm performs two validation checks:

• calculateSide(): Verifies normal consistency to ensure the loop is geometrically valid.
• isFaceHalfEdgeExist(): Confirms the loop does not duplicate an existing face.

Valid loops are added as faces to m_remeshedPolygons, with the vertex positions stored in m_remeshedVertices.

Repairing Holes

After initial quad generation, fixHoles() calls fixHoleWithQuads() (lines 100–114) to patch boundary loops. The algorithm iteratively fills holes by inserting new quads (or triangles when necessary), scoring candidate quads based on edge alignment and discarding any that would intersect existing geometry.

Ensuring Manifold Geometry

The removeNonManifoldFaces() function (lines 156–188) builds an edge-to-face map and filters out any faces that share edges in non-manifold configurations or lie on open boundaries. This step guarantees the output is a clean, manifold quad mesh suitable for subdivision or simulation.

Finalization and Output

Before returning the result, the pipeline optimizes the vertex buffer to eliminate waste.

Vertex Compaction

The final compaction block (lines 143–162) in QuadExtractor::extract() purges unused vertices and re-indexes the remaining indices to ensure the vertex list is tight and contiguous. The final quad-dominant mesh is stored in m_remeshedVertices (positions) and m_remeshedPolygons (face index vectors, typically of size 4).

Implementation Example

The following C++ example demonstrates how to invoke the extraction pipeline using the QuadMeshGenerator wrapper class, mirroring the GUI implementation in src/mainwindow.cpp (around line 770):

#include <AutoRemesher/QuadMeshGenerator>
#include <vector>
#include <array>
#include <fstream>

// Assume input triangle mesh is loaded
std::vector<Vector3> vertices;
std::vector<std::array<size_t, 3>> triangles;
std::vector<Vector2> triangleUvs;  // Per-vertex UVs for isoline extraction

// Initialize the generator
AutoRemesher::QuadMeshGenerator generator(&vertices, &triangles);
generator.setTriangleUvs(&triangleUvs);  // Required for isoline-based extraction
generator.process();                     // Executes the full pipeline

// Retrieve quad-dominant results
std::vector<Vector3> quadVertices = generator.remeshedVertices();
std::vector<std::vector<size_t>> quadPolygons = generator.remeshedPolygons();

// Export as OBJ
std::ofstream out("quad_result.obj");
for (const auto& v : quadVertices) {
    out << "v " << v.x() << " " << v.y() << " " << v.z() << "\n";
}
for (const auto& face : quadPolygons) {
    out << "f";
    for (size_t idx : face) {
        out << " " << (idx + 1);  // OBJ uses 1-based indexing
    }
    out << "\n";
}

Summary

• Isoline-Based Vertex Creation: The algorithm generates cross points by intersecting integer UV isolines with triangle edges in extractConnections() (lines 698–720).
• Graph Simplification: The pipeline aggressively cleans the connection graph by collapsing short edges (≤1% threshold), merging degree-2 vertices, and removing dangling endpoints.
• Triangle Cycle Removal: Small triangular loops are collapsed into single vertices via collapseTriangles() to promote quad formation.
• Loop Extraction: Valid quads are identified by finding closed 4–7 vertex loops in extractMesh() (lines 125–195), validated for normal consistency and uniqueness.
• Manifold Guarantee: Post-processing steps repair holes and remove non-manifold faces to produce production-ready topology.

Frequently Asked Questions

What is the entry point for the quad extraction pipeline in AutoRemesher?

The entry point is QuadExtractor::extract() implemented in src/AutoRemesher/quadextractor.cpp. This method orchestrates the entire conversion process by sequentially calling extractConnections(), extractEdges(), the various simplification routines, extractMesh(), and finally the cleanup functions.

How does AutoRemesher determine where to place vertices when converting triangles to quads?

Vertex placement is driven by UV parameterization. The algorithm computes where integer-valued isolines intersect the edges of the input triangles. These intersection points become the cross points that define the new vertex positions on the surface, ensuring the quad layout follows the underlying parameterization grid.

Why does the algorithm collapse edges shorter than 1% of the average length?

The 1% threshold in collapseShortEdges() (lines 66–94) eliminates spurious vertices created by numerical precision issues or parameterization distortion. Collapsing these micro-edges prevents the formation of degenerate quads and reduces vertex count without significantly altering the mesh geometry.

What is the maximum number of vertices allowed per polygon during extraction?

The extractMesh() function searches for closed loops containing 4 to 7 vertices. While the target is primarily quadrilaterals (4 vertices), the algorithm allows up to 7 vertices to capture valid polygons in complex topology regions. Non-quad polygons can be subsequently split or processed by the hole-fixing routines to achieve quad-dominant output.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}