Search code examples
qtgraphics2dcomputational-geometryuv-mapping

Mapping random 2D shape to uv parametric rectangular grid

I want to map some random 2D shape to uv parametric space, e.g A: (u: 0.0 v: 1.0) B: (u: 0.0 v :0.0) C: (u: 1.0 v: 1.0) D : (u:1.0 v: 0.0), and want to map a random point P, at the inside of the item, to the parametric space.

Line AB, AC, BD, CD are consist of path, or can be represented as connected edges.

So the question is, how should I get the correct uv value of P? I got a few knowledge in graphics and geometry, so if needed, could you please recommend any basic article that I can find any hint of solution of the problem? Thank you so much

enter image description here

Solution

  • What you are asking isn't so easy.

    You can generate a transformation from (u, v) coordinates to Cartesian (x, y) by means of two Coons interpolants X(u, v) and Y(u, v).

    Now if you want to invert the relation, you will need to solve the system

    X(u, v) = x
Y(u, v) = y

    which is nonlinear.

    If you have many points to map (which is likely), a way to address the problem is to apply a grid in the (u, v) space and compute the corresponding mesh in (x, y). The grid should be fine enough to ensure accuracy. Then for given x and y, you need to find the quadrilateral they belong to and obtain u and v for instance by bilinear interpolation, computing the intersection of an horizontal with the sides, then intersecting with the vertical.

    To accelerate the search of the containing tiles, you can use bounding boxes and store them in an interval tree. Possibly also, perform a search for the nearest vertex (by means of a kD-tree) and search for the enclosing quadrilateral in the adjoining tiles.

    All of this is pretty technical.

    If your purpose is just to provide a triangulation with (u, v) information available at the vertices, meshing as described above is sufficient.