Dev:Source/Textures/UV/Unwrapping

UV Unwrapping

This project aims to further improve the UV editing tools. First the code in unwrapper.c will be refactored, which will allow current and future algorithms to (re)use the same data structures and code.

The new code is in the bf-blender, in source/blender/src/parametrizer.c.

Tutorial on unwrapping Suzanne: BlenderDev/UvUnwrapping/Suzanne

• done
   LSCM: better choice of 2 default pinned UV's
• done
   Enhanced LSCM Live Mode.
• done
   Minimize Stretch from Tuhopuu.
• done
   Subsurf UV.
• done
   Hole filling before unwrapping, to prevent overlaps.
• done
   Seam cutting in Face Select Mode.
• done
   ABF unwrapping.
  • done
     Main remaining problem is degenerate triangles.
  • Teaser Image
• done
   Multiple UV Sets.
• Other ideas:
  • done
     Better packing algorithms.
  • Simple automatic seams for e.g. texture baking, port archimapper?
  • done
     Live seam cutting.

Code Documentation

API

The API is in parametrizer.h should be used in three steps:

• Load mesh and construct charts based on seams or UV coordinates.
• Run some algorithm on the charts.
• Flush UV coordinates back to the original mesh and cleanup.

Mesh

The mesh data structure used is a half edge mesh. This means each edge is limited to two faces, which works fine because a valid unwrap can't have more than that. For an edge with one face the edge->pair pointer is set to NULL.

The vertex, edge and face structs look like this:

typedef struct PVert {
    struct PVert *nextlink;
    union PVertUnion {...} u;
    struct PEdge *edge;
    float *co;
    float uv[2];
    unsigned char flag;
} PVert; 

typedef struct PEdge {
    struct PEdge *nextlink;
    union PEdgeUnion {...} u;
    struct PVert *vert;
    struct PEdge *pair;
    struct PEdge *next;
    struct PFace *face;
    unsigned short flag;
} PEdge;

typedef struct PFace {
    struct PFace *nextlink;
    union PFaceUnion {...} u;
    struct PEdge *edge;
    unsigned char flag;
} PFace;

During the construction phase these are stored in hashes. The nextlink pointer is then used by the hash and the hash key is stored in the unions. Once the charts are constructed the nextlink pointer is used to make single linked lists, and the union members are used for different purposes by different tools. The flag member is used by different algorithms. The possible flags are enumerated further in the file to avoid collisions.

LSCM

The Least Squares Conformal Maps algorithm by itself is relatively simple. It involves solving a system of linear equations which we can write in matrix math as A*x = b. Where A is a huge 2 * number of faces x 2 * number of vertices matrix, but it's filled mostly with zeros. Luckily we've got superLU to solve that quickly. A and b are construct based on the face angles in the original mesh, and after solving x magically contains the resulting UV coordinates.

ABF

Angle Based Flattening uses a more expensive approach. The input are again the face angles, and the ouput are the face angles of the 2d mesh. Then these 2d angles are used as input to LSCM, which then computes the final UV coordinates. ABF uses non-linear constrained minimization to find 2d angles that are as close as possible to the original angles, under the following constraints:

• All angles around an interior vertex sum up to 2*PI.
• Angles in a triangle sum up to PI.
• The length of an edge between two triangles must be the same.

It starts from the 3d angles as an initial guess and then iteratively solves a linear system until it's close enough to the solution.

Implementation was based on this paper: A. Sheffer, B. Lévy, M. Mogilnitsky, A, Bogomyakov, ABF++: Fast and Robust Angle Based Flattening, ACM Transactions on Graphics, 24(2), 311-330 2005.

Brecht Van Lommel.