当前位置： 文江博客话题详情

如何在 2D 中绘制透视正确的网格

发布于 2024-07-13 00:14:46 字数 325 浏览 6 评论 0原文

我有一个应用程序在图像/照片之上定义了一个现实世界的矩形，当然在 2D 中它可能不是一个矩形，因为你是从一个角度看它。

问题是，假设矩形需要在其上绘制网格线，例如，如果它是 3x5，那么我需要从边 1 到边 3 绘制 2 条线，从边 2 到边 4 绘制 4 条线

。现在我将每条线分成等距部分，以获得所有网格线的起点和终点。 然而，矩形的角度越大，这些线就越“不正确”，因为距离您较远的水平线应该靠得更近。

有谁知道我应该搜索的算法的名称？

是的，我知道您可以在 3D 中执行此操作，但对于此特定应用程序，我仅限于 2D。

原文

I have an application that defines a real world rectangle on top of an image/photograph, of course in 2D it may not be a rectangle because you are looking at it from an angle.

The problem is, say that the rectangle needs to have grid lines drawn on it, for example if it is 3x5 so I need to draw 2 lines from side 1 to side 3, and 4 lines from side 2 to side 4.

As of right now I am breaking up each line into equidistant parts, to get the start and end point of all the grid lines. However the more of an angle the rectangle is on, the more "incorrect" these lines become, as horizontal lines further from you should be closer together.

Does anyone know the name of the algorithm that I should be searching for?

Yes I know you can do this in 3D, however I am limited to 2D for this particular application.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（9）

泡沫很甜 2024-07-20 00:14:46

这里 解决方案。

基本思想是，您可以通过对角连接角来找到矩形的透视正确“中心”。 两条所得线的交点是您的透视正确中心。 从那里，您将矩形细分为四个较小的矩形，然后重复该过程。 次数取决于您想要的准确程度。 您可以细分到略低于像素的大小，以获得有效的完美透视。

然后在子矩形中，您只需应用标准的未经校正的“纹理”三角形，或矩形或其他任何东西。

您可以执行此算法，而无需经历构建“真实”3D 世界的复杂麻烦。 如果您确实建模了真实的 3D 世界，但您的文本三角形未在硬件中进行透视校正，或者您需要一种高性能的方法来获得透视正确的平面，而无需使用每像素渲染技巧，那么它也很有用。

Here's the solution.

The basic idea is you can find the perspective correct "center" of your rectangle by connecting the corners diagonally. The intersection of the two resulting lines is your perspective correct center. From there you subdivide your rectangle into four smaller rectangles, and you repeat the process. The number of times depends on how accurate you want it. You can subdivide to just below the size of a pixel for effectively perfect perspective.

Then in your subrectangles you just apply your standard uncorrected "textured" triangles, or rectangles or whatever.

You can perform this algorithm without going to the complex trouble of building a 'real' 3d world. it's also good for if you do have a real 3d world modeled, but your textriangles are not perspective corrected in hardware, or you need a performant way to get perspective correct planes without per pixel rendering trickery.

回复 原文
紅太極 2024-07-20 00:14:46

图像描述
图片：双线性和双线性的示例 透视变换（注意：在两张图中，顶部和底部水平网格线的高度实际上是其余线高度的一半）

====================== ==================

我知道这是一个老问题，但我有一个通用的解决方案，所以我决定发布它，希望它对未来的读者有用。
下面的代码可以绘制任意透视网格，而不需要重复计算。

我实际上从一个类似的问题开始：绘制一个 2D 透视网格，然后变换下划线图像以恢复透视。

我开始在这里阅读：
然后

​这里（Leptonica 图书馆）：
http://www.leptonica.com/affine.html

我发现了这个：

当你从某个任意方向观察平面上的物体时
在有限的距离内，您会在
图像。 这是一个投影变换，它保持直线
笔直，但不保留线之间的角度。 这个翘曲
不能用线性仿射变换来描述，事实上
分母中与 x 和 y 相关的项不同。

正如许多人已经在这个帖子中指出的那样，这种转变不是线性的。 它涉及求解 8 个方程的线性系统（一次）以计算 8 个所需系数，然后您可以使用它们来变换任意数量的点。

为了避免在我的项目中包含所有 Leptonica 库，我从中取出了一些代码，删除了所有特殊的 Leptonica 数据类型和数据类型。 宏，我修复了一些内存泄漏，并将其转换为 C++ 类（主要是出于封装原因），它只做一件事：
它将 (Qt) QPointF float (x,y) 坐标映射到相应的透视坐标。

如果你想让代码适应另一个C++库，唯一需要重新定义/替换的是QPointF坐标类。

我希望未来的读者会发现它有用。
下面的代码分为 3 部分：

A. 如何使用 genImageProjective C++ 类绘制 2D 透视网格的示例

B. genImageProjective.h 文件

C. genImageProjective.cpp 文件

//============================================================
// C++ Code Example on how to use the 
//     genImageProjective class to draw a perspective 2D Grid
//============================================================

#include "genImageProjective.h"

// Input: 4 Perspective-Tranformed points:
//        perspPoints[0] = top-left
//        perspPoints[1] = top-right
//        perspPoints[2] = bottom-right
//        perspPoints[3] = bottom-left
void drawGrid(QPointF *perspPoints)
{
(...)
        // Setup a non-transformed area rectangle
        // I use a simple square rectangle here because in this case we are not interested in the source-rectangle,
        //  (we want to just draw a grid on the perspPoints[] area)
        //   but you can use any arbitrary rectangle to perform a real mapping to the perspPoints[] area
        QPointF topLeft = QPointF(0,0);
        QPointF topRight = QPointF(1000,0);
        QPointF bottomRight = QPointF(1000,1000);
        QPointF bottomLeft = QPointF(0,1000);
        float width = topRight.x() - topLeft.x();
        float height = bottomLeft.y() - topLeft.y();

        // Setup Projective trasform object
        genImageProjective imageProjective;
        imageProjective.sourceArea[0] = topLeft;
        imageProjective.sourceArea[1] = topRight;
        imageProjective.sourceArea[2] = bottomRight;
        imageProjective.sourceArea[3] = bottomLeft;
        imageProjective.destArea[0] = perspPoints[0];
        imageProjective.destArea[1] = perspPoints[1];
        imageProjective.destArea[2] = perspPoints[2];
        imageProjective.destArea[3] = perspPoints[3];
        // Compute projective transform coefficients
        if (imageProjective.computeCoeefficients() != 0)
            return; // This can actually fail if any 3 points of Source or Dest are colinear

        // Initialize Grid parameters (without transform)
        float gridFirstLine = 0.1f; // The normalized position of first Grid Line (0.0 to 1.0)
        float gridStep = 0.1f;      // The normalized Grd size (=distance between grid lines: 0.0 to 1.0)

        // Draw Horizonal Grid lines
        QPointF lineStart, lineEnd, tempPnt;
        for (float pos = gridFirstLine; pos <= 1.0f; pos += gridStep)
        {
            // Compute Grid Line Start
            tempPnt = QPointF(topLeft.x(), topLeft.y() + pos*width);
            imageProjective.mapSourceToDestPoint(tempPnt, lineStart);
            // Compute Grid Line End
            tempPnt = QPointF(topRight.x(), topLeft.y() + pos*width);
            imageProjective.mapSourceToDestPoint(tempPnt, lineEnd);

            // Draw Horizontal Line (use your prefered method to draw the line)
            (...)
        }
        // Draw Vertical Grid lines
        for (float pos = gridFirstLine; pos <= 1.0f; pos += gridStep)
        {
            // Compute Grid Line Start
            tempPnt = QPointF(topLeft.x() + pos*height, topLeft.y());
            imageProjective.mapSourceToDestPoint(tempPnt, lineStart);
            // Compute Grid Line End
            tempPnt = QPointF(topLeft.x() + pos*height, bottomLeft.y());
            imageProjective.mapSourceToDestPoint(tempPnt, lineEnd);

            // Draw Vertical Line (use your prefered method to draw the line)
            (...)
        }
(...)
}

==========================================



//========================================
//C++ Header File: genImageProjective.h
//========================================

#ifndef GENIMAGE_H
#define GENIMAGE_H

#include <QPointF>

// Class to transform an Image Point using Perspective transformation
class genImageProjective
{
public:
    genImageProjective();

    int computeCoeefficients(void);
    int mapSourceToDestPoint(QPointF& sourcePoint, QPointF& destPoint);

public:
    QPointF sourceArea[4]; // Source Image area limits (Rectangular)
    QPointF destArea[4];   // Destination Image area limits (Perspectivelly Transformed)

private:
    static int gaussjordan(float  **a, float  *b, int n);

    bool coefficientsComputed;
    float vc[8];           // Vector of Transform Coefficients
};

#endif // GENIMAGE_H
//========================================


//========================================
//C++ CPP File: genImageProjective.cpp
//========================================

#include <math.h>
#include "genImageProjective.h"

// ----------------------------------------------------
// class genImageProjective
// ----------------------------------------------------
genImageProjective::genImageProjective()
{
    sourceArea[0] = sourceArea[1] = sourceArea[2] = sourceArea[3] = QPointF(0,0);
    destArea[0] = destArea[1] = destArea[2] = destArea[3] = QPointF(0,0);
    coefficientsComputed = false;
}


// --------------------------------------------------------------
// Compute projective transform coeeeficients
// RetValue: 0: Success, !=0: Error
/*-------------------------------------------------------------*
 *                Projective coordinate transformation         *
 *-------------------------------------------------------------*/
/*!
 *  computeCoeefficients()
 *
 *      Input:  this->sourceArea[4]: (source 4 points; unprimed)
 *              this->destArea[4]:   (transformed 4 points; primed)
 *              this->vc  (computed vector of transform coefficients)
 *      Return: 0 if OK; <0 on error
 *
 *  We have a set of 8 equations, describing the projective
 *  transformation that takes 4 points (sourceArea) into 4 other
 *  points (destArea).  These equations are:
 *
 *          x1' = (c[0]*x1 + c[1]*y1 + c[2]) / (c[6]*x1 + c[7]*y1 + 1)
 *          y1' = (c[3]*x1 + c[4]*y1 + c[5]) / (c[6]*x1 + c[7]*y1 + 1)
 *          x2' = (c[0]*x2 + c[1]*y2 + c[2]) / (c[6]*x2 + c[7]*y2 + 1)
 *          y2' = (c[3]*x2 + c[4]*y2 + c[5]) / (c[6]*x2 + c[7]*y2 + 1)
 *          x3' = (c[0]*x3 + c[1]*y3 + c[2]) / (c[6]*x3 + c[7]*y3 + 1)
 *          y3' = (c[3]*x3 + c[4]*y3 + c[5]) / (c[6]*x3 + c[7]*y3 + 1)
 *          x4' = (c[0]*x4 + c[1]*y4 + c[2]) / (c[6]*x4 + c[7]*y4 + 1)
 *          y4' = (c[3]*x4 + c[4]*y4 + c[5]) / (c[6]*x4 + c[7]*y4 + 1)
 *
 *  Multiplying both sides of each eqn by the denominator, we get
 *
 *           AC = B
 *
 *  where B and C are column vectors
 *
 *         B = [ x1' y1' x2' y2' x3' y3' x4' y4' ]
 *         C = [ c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] ]
 *
 *  and A is the 8x8 matrix
 *
 *             x1   y1     1     0   0    0   -x1*x1'  -y1*x1'
 *              0    0     0    x1   y1   1   -x1*y1'  -y1*y1'
 *             x2   y2     1     0   0    0   -x2*x2'  -y2*x2'
 *              0    0     0    x2   y2   1   -x2*y2'  -y2*y2'
 *             x3   y3     1     0   0    0   -x3*x3'  -y3*x3'
 *              0    0     0    x3   y3   1   -x3*y3'  -y3*y3'
 *             x4   y4     1     0   0    0   -x4*x4'  -y4*x4'
 *              0    0     0    x4   y4   1   -x4*y4'  -y4*y4'
 *
 *  These eight equations are solved here for the coefficients C.
 *
 *  These eight coefficients can then be used to find the mapping
 *  (x,y) --> (x',y'):
 *
 *           x' = (c[0]x + c[1]y + c[2]) / (c[6]x + c[7]y + 1)
 *           y' = (c[3]x + c[4]y + c[5]) / (c[6]x + c[7]y + 1)
 *
 */
int genImageProjective::computeCoeefficients(void)
{
    int retValue = 0;
    int     i;
    float  *a[8];  /* 8x8 matrix A  */
    float  *b = this->vc; /* rhs vector of primed coords X'; coeffs returned in vc[] */

    b[0] = destArea[0].x();
    b[1] = destArea[0].y();
    b[2] = destArea[1].x();
    b[3] = destArea[1].y();
    b[4] = destArea[2].x();
    b[5] = destArea[2].y();
    b[6] = destArea[3].x();
    b[7] = destArea[3].y();

    for (i = 0; i < 8; i++)
        a[i] = NULL;
    for (i = 0; i < 8; i++)
    {
        if ((a[i] = (float *)calloc(8, sizeof(float))) == NULL)
        {
            retValue = -100; // ERROR_INT("a[i] not made", procName, 1);
            goto Terminate;
        }
    }

    a[0][0] = sourceArea[0].x();
    a[0][1] = sourceArea[0].y();
    a[0][2] = 1.;
    a[0][6] = -sourceArea[0].x() * b[0];
    a[0][7] = -sourceArea[0].y() * b[0];
    a[1][3] = sourceArea[0].x();
    a[1][4] = sourceArea[0].y();
    a[1][5] = 1;
    a[1][6] = -sourceArea[0].x() * b[1];
    a[1][7] = -sourceArea[0].y() * b[1];
    a[2][0] = sourceArea[1].x();
    a[2][1] = sourceArea[1].y();
    a[2][2] = 1.;
    a[2][6] = -sourceArea[1].x() * b[2];
    a[2][7] = -sourceArea[1].y() * b[2];
    a[3][3] = sourceArea[1].x();
    a[3][4] = sourceArea[1].y();
    a[3][5] = 1;
    a[3][6] = -sourceArea[1].x() * b[3];
    a[3][7] = -sourceArea[1].y() * b[3];
    a[4][0] = sourceArea[2].x();
    a[4][1] = sourceArea[2].y();
    a[4][2] = 1.;
    a[4][6] = -sourceArea[2].x() * b[4];
    a[4][7] = -sourceArea[2].y() * b[4];
    a[5][3] = sourceArea[2].x();
    a[5][4] = sourceArea[2].y();
    a[5][5] = 1;
    a[5][6] = -sourceArea[2].x() * b[5];
    a[5][7] = -sourceArea[2].y() * b[5];
    a[6][0] = sourceArea[3].x();
    a[6][1] = sourceArea[3].y();
    a[6][2] = 1.;
    a[6][6] = -sourceArea[3].x() * b[6];
    a[6][7] = -sourceArea[3].y() * b[6];
    a[7][3] = sourceArea[3].x();
    a[7][4] = sourceArea[3].y();
    a[7][5] = 1;
    a[7][6] = -sourceArea[3].x() * b[7];
    a[7][7] = -sourceArea[3].y() * b[7];

    retValue = gaussjordan(a, b, 8);

Terminate:
    // Clean up
    for (i = 0; i < 8; i++)
    {
        if (a[i])
            free(a[i]);
    }

    this->coefficientsComputed = (retValue == 0);
    return retValue;
}


/*-------------------------------------------------------------*
 *               Gauss-jordan linear equation solver           *
 *-------------------------------------------------------------*/
/*
 *  gaussjordan()
 *
 *      Input:   a  (n x n matrix)
 *               b  (rhs column vector)
 *               n  (dimension)
 *      Return:  0 if ok, 1 on error
 *
 *      Note side effects:
 *            (1) the matrix a is transformed to its inverse
 *            (2) the vector b is transformed to the solution X to the
 *                linear equation AX = B
 *
 *      Adapted from "Numerical Recipes in C, Second Edition", 1992
 *      pp. 36-41 (gauss-jordan elimination)
 */
#define  SWAP(a,b)   {temp = (a); (a) = (b); (b) = temp;}
int genImageProjective::gaussjordan(float  **a, float  *b, int n)
{
    int retValue = 0;
    int i, icol=0, irow=0, j, k, l, ll;
    int *indexc = NULL, *indexr = NULL, *ipiv = NULL;
    float  big, dum, pivinv, temp;

    if (!a)
    {
        retValue = -1; // ERROR_INT("a not defined", procName, 1);
        goto Terminate;
    }
    if (!b)
    {
        retValue = -2; // ERROR_INT("b not defined", procName, 1);
        goto Terminate;
    }

    if ((indexc = (int *)calloc(n, sizeof(int))) == NULL)
    {
        retValue = -3; // ERROR_INT("indexc not made", procName, 1);
        goto Terminate;
    }
    if ((indexr = (int *)calloc(n, sizeof(int))) == NULL)
    {
        retValue = -4; // ERROR_INT("indexr not made", procName, 1);
        goto Terminate;
    }
    if ((ipiv = (int *)calloc(n, sizeof(int))) == NULL)
    {
        retValue = -5; // ERROR_INT("ipiv not made", procName, 1);
        goto Terminate;
    }

    for (i = 0; i < n; i++)
    {
        big = 0.0;
        for (j = 0; j < n; j++)
        {
            if (ipiv[j] != 1)
            {
                for (k = 0; k < n; k++)
                {
                    if (ipiv[k] == 0)
                    {
                        if (fabs(a[j][k]) >= big)
                        {
                            big = fabs(a[j][k]);
                            irow = j;
                            icol = k;
                        }
                    }
                    else if (ipiv[k] > 1)
                    {
                        retValue = -6; // ERROR_INT("singular matrix", procName, 1);
                        goto Terminate;
                    }
                }
            }
        }
        ++(ipiv[icol]);

        if (irow != icol)
        {
            for (l = 0; l < n; l++)
                SWAP(a[irow][l], a[icol][l]);
            SWAP(b[irow], b[icol]);
        }

        indexr[i] = irow;
        indexc[i] = icol;
        if (a[icol][icol] == 0.0)
        {
            retValue = -7; // ERROR_INT("singular matrix", procName, 1);
            goto Terminate;
        }
        pivinv = 1.0 / a[icol][icol];
        a[icol][icol] = 1.0;
        for (l = 0; l < n; l++)
            a[icol][l] *= pivinv;
        b[icol] *= pivinv;

        for (ll = 0; ll < n; ll++)
        {
            if (ll != icol)
            {
                dum = a[ll][icol];
                a[ll][icol] = 0.0;
                for (l = 0; l < n; l++)
                    a[ll][l] -= a[icol][l] * dum;
                b[ll] -= b[icol] * dum;
            }
        }
    }

    for (l = n - 1; l >= 0; l--)
    {
        if (indexr[l] != indexc[l])
        {
            for (k = 0; k < n; k++)
                SWAP(a[k][indexr[l]], a[k][indexc[l]]);
        }
    }

Terminate:
    if (indexr)
        free(indexr);
    if (indexc)
        free(indexc);
    if (ipiv)
        free(ipiv);
    return retValue;
}


// --------------------------------------------------------------
// Map a source point to destination using projective transform
// --------------------------------------------------------------
// Params:
//  sourcePoint: initial point
//  destPoint:   transformed point
// RetValue: 0: Success, !=0: Error
// --------------------------------------------------------------
//  Notes:
//   1. You must call once computeCoeefficients() to compute
//      the this->vc[] vector of 8 coefficients, before you call
//      mapSourceToDestPoint().
//   2. If there was an error or the 8 coefficients were not computed,
//      a -1 is returned and destPoint is just set to sourcePoint value.
// --------------------------------------------------------------
int genImageProjective::mapSourceToDestPoint(QPointF& sourcePoint, QPointF& destPoint)
{
    if (coefficientsComputed)
    {
        float factor = 1.0f / (vc[6] * sourcePoint.x() + vc[7] * sourcePoint.y() + 1.);
        destPoint.setX( factor * (vc[0] * sourcePoint.x() + vc[1] * sourcePoint.y() + vc[2]) );
        destPoint.setY( factor * (vc[3] * sourcePoint.x() + vc[4] * sourcePoint.y() + vc[5]) );
        return 0;
    }
    else // There was an error while computing coefficients
    {
        destPoint = sourcePoint; // just copy the source to destination...
        return -1;               // ...and return an error
    }
}
//========================================

image description
Image: Example of Bilinear & Perspective Transform (Note: The height of top & bottom horizontal grid lines is actually half of the rest lines height, on both drawings)

========================================

I know this is an old question, but I have a generic solution so I decided to publish it hopping it will be useful to the future readers.
The code bellow can draw an arbitrary perspective grid without the need of repetitive computations.

I begin actually with a similar problem: to draw a 2D perspective Grid and then transform the underline image to restore the perspective.

I started to read here:
http://www.imagemagick.org/Usage/distorts/#bilinear_forward

and then here (the Leptonica Library):
http://www.leptonica.com/affine.html

were I found this:

When you look at an object in a plane from some arbitrary direction at
a finite distance, you get an additional "keystone" distortion in the
image. This is a projective transform, which keeps straight lines
straight but does not preserve the angles between lines. This warping
cannot be described by a linear affine transformation, and in fact
differs by x- and y-dependent terms in the denominator.

The transformation is not linear, as many people already pointed out in this thread. It involves solving a linear system of 8 equations (once) to compute the 8 required coefficients and then you can use them to transform as many points as you want.

To avoid including all Leptonica library in my project, I took some pieces of code from it, I removed all special Leptonica data-types & macros, I fixed some memory leaks and I converted it to a C++ class (mostly for encapsulation reasons) which does just one thing:
It maps a (Qt) QPointF float (x,y) coordinate to the corresponding Perspective Coordinate.

If you want to adapt the code to another C++ library, the only thing to redefine/substitute is the QPointF coordinate class.

I hope some future readers would find it useful.
The code bellow is divided into 3 parts:

A. An example on how to use the genImageProjective C++ class to draw a 2D perspective Grid

B. genImageProjective.h file

C. genImageProjective.cpp file

//============================================================
// C++ Code Example on how to use the 
//     genImageProjective class to draw a perspective 2D Grid
//============================================================

#include "genImageProjective.h"

// Input: 4 Perspective-Tranformed points:
//        perspPoints[0] = top-left
//        perspPoints[1] = top-right
//        perspPoints[2] = bottom-right
//        perspPoints[3] = bottom-left
void drawGrid(QPointF *perspPoints)
{
(...)
        // Setup a non-transformed area rectangle
        // I use a simple square rectangle here because in this case we are not interested in the source-rectangle,
        //  (we want to just draw a grid on the perspPoints[] area)
        //   but you can use any arbitrary rectangle to perform a real mapping to the perspPoints[] area
        QPointF topLeft = QPointF(0,0);
        QPointF topRight = QPointF(1000,0);
        QPointF bottomRight = QPointF(1000,1000);
        QPointF bottomLeft = QPointF(0,1000);
        float width = topRight.x() - topLeft.x();
        float height = bottomLeft.y() - topLeft.y();

        // Setup Projective trasform object
        genImageProjective imageProjective;
        imageProjective.sourceArea[0] = topLeft;
        imageProjective.sourceArea[1] = topRight;
        imageProjective.sourceArea[2] = bottomRight;
        imageProjective.sourceArea[3] = bottomLeft;
        imageProjective.destArea[0] = perspPoints[0];
        imageProjective.destArea[1] = perspPoints[1];
        imageProjective.destArea[2] = perspPoints[2];
        imageProjective.destArea[3] = perspPoints[3];
        // Compute projective transform coefficients
        if (imageProjective.computeCoeefficients() != 0)
            return; // This can actually fail if any 3 points of Source or Dest are colinear

        // Initialize Grid parameters (without transform)
        float gridFirstLine = 0.1f; // The normalized position of first Grid Line (0.0 to 1.0)
        float gridStep = 0.1f;      // The normalized Grd size (=distance between grid lines: 0.0 to 1.0)

        // Draw Horizonal Grid lines
        QPointF lineStart, lineEnd, tempPnt;
        for (float pos = gridFirstLine; pos <= 1.0f; pos += gridStep)
        {
            // Compute Grid Line Start
            tempPnt = QPointF(topLeft.x(), topLeft.y() + pos*width);
            imageProjective.mapSourceToDestPoint(tempPnt, lineStart);
            // Compute Grid Line End
            tempPnt = QPointF(topRight.x(), topLeft.y() + pos*width);
            imageProjective.mapSourceToDestPoint(tempPnt, lineEnd);

            // Draw Horizontal Line (use your prefered method to draw the line)
            (...)
        }
        // Draw Vertical Grid lines
        for (float pos = gridFirstLine; pos <= 1.0f; pos += gridStep)
        {
            // Compute Grid Line Start
            tempPnt = QPointF(topLeft.x() + pos*height, topLeft.y());
            imageProjective.mapSourceToDestPoint(tempPnt, lineStart);
            // Compute Grid Line End
            tempPnt = QPointF(topLeft.x() + pos*height, bottomLeft.y());
            imageProjective.mapSourceToDestPoint(tempPnt, lineEnd);

            // Draw Vertical Line (use your prefered method to draw the line)
            (...)
        }
(...)
}

==========================================



//========================================
//C++ Header File: genImageProjective.h
//========================================

#ifndef GENIMAGE_H
#define GENIMAGE_H

#include <QPointF>

// Class to transform an Image Point using Perspective transformation
class genImageProjective
{
public:
    genImageProjective();

    int computeCoeefficients(void);
    int mapSourceToDestPoint(QPointF& sourcePoint, QPointF& destPoint);

public:
    QPointF sourceArea[4]; // Source Image area limits (Rectangular)
    QPointF destArea[4];   // Destination Image area limits (Perspectivelly Transformed)

private:
    static int gaussjordan(float  **a, float  *b, int n);

    bool coefficientsComputed;
    float vc[8];           // Vector of Transform Coefficients
};

#endif // GENIMAGE_H
//========================================


//========================================
//C++ CPP File: genImageProjective.cpp
//========================================

#include <math.h>
#include "genImageProjective.h"

// ----------------------------------------------------
// class genImageProjective
// ----------------------------------------------------
genImageProjective::genImageProjective()
{
    sourceArea[0] = sourceArea[1] = sourceArea[2] = sourceArea[3] = QPointF(0,0);
    destArea[0] = destArea[1] = destArea[2] = destArea[3] = QPointF(0,0);
    coefficientsComputed = false;
}


// --------------------------------------------------------------
// Compute projective transform coeeeficients
// RetValue: 0: Success, !=0: Error
/*-------------------------------------------------------------*
 *                Projective coordinate transformation         *
 *-------------------------------------------------------------*/
/*!
 *  computeCoeefficients()
 *
 *      Input:  this->sourceArea[4]: (source 4 points; unprimed)
 *              this->destArea[4]:   (transformed 4 points; primed)
 *              this->vc  (computed vector of transform coefficients)
 *      Return: 0 if OK; <0 on error
 *
 *  We have a set of 8 equations, describing the projective
 *  transformation that takes 4 points (sourceArea) into 4 other
 *  points (destArea).  These equations are:
 *
 *          x1' = (c[0]*x1 + c[1]*y1 + c[2]) / (c[6]*x1 + c[7]*y1 + 1)
 *          y1' = (c[3]*x1 + c[4]*y1 + c[5]) / (c[6]*x1 + c[7]*y1 + 1)
 *          x2' = (c[0]*x2 + c[1]*y2 + c[2]) / (c[6]*x2 + c[7]*y2 + 1)
 *          y2' = (c[3]*x2 + c[4]*y2 + c[5]) / (c[6]*x2 + c[7]*y2 + 1)
 *          x3' = (c[0]*x3 + c[1]*y3 + c[2]) / (c[6]*x3 + c[7]*y3 + 1)
 *          y3' = (c[3]*x3 + c[4]*y3 + c[5]) / (c[6]*x3 + c[7]*y3 + 1)
 *          x4' = (c[0]*x4 + c[1]*y4 + c[2]) / (c[6]*x4 + c[7]*y4 + 1)
 *          y4' = (c[3]*x4 + c[4]*y4 + c[5]) / (c[6]*x4 + c[7]*y4 + 1)
 *
 *  Multiplying both sides of each eqn by the denominator, we get
 *
 *           AC = B
 *
 *  where B and C are column vectors
 *
 *         B = [ x1' y1' x2' y2' x3' y3' x4' y4' ]
 *         C = [ c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] ]
 *
 *  and A is the 8x8 matrix
 *
 *             x1   y1     1     0   0    0   -x1*x1'  -y1*x1'
 *              0    0     0    x1   y1   1   -x1*y1'  -y1*y1'
 *             x2   y2     1     0   0    0   -x2*x2'  -y2*x2'
 *              0    0     0    x2   y2   1   -x2*y2'  -y2*y2'
 *             x3   y3     1     0   0    0   -x3*x3'  -y3*x3'
 *              0    0     0    x3   y3   1   -x3*y3'  -y3*y3'
 *             x4   y4     1     0   0    0   -x4*x4'  -y4*x4'
 *              0    0     0    x4   y4   1   -x4*y4'  -y4*y4'
 *
 *  These eight equations are solved here for the coefficients C.
 *
 *  These eight coefficients can then be used to find the mapping
 *  (x,y) --> (x',y'):
 *
 *           x' = (c[0]x + c[1]y + c[2]) / (c[6]x + c[7]y + 1)
 *           y' = (c[3]x + c[4]y + c[5]) / (c[6]x + c[7]y + 1)
 *
 */
int genImageProjective::computeCoeefficients(void)
{
    int retValue = 0;
    int     i;
    float  *a[8];  /* 8x8 matrix A  */
    float  *b = this->vc; /* rhs vector of primed coords X'; coeffs returned in vc[] */

    b[0] = destArea[0].x();
    b[1] = destArea[0].y();
    b[2] = destArea[1].x();
    b[3] = destArea[1].y();
    b[4] = destArea[2].x();
    b[5] = destArea[2].y();
    b[6] = destArea[3].x();
    b[7] = destArea[3].y();

    for (i = 0; i < 8; i++)
        a[i] = NULL;
    for (i = 0; i < 8; i++)
    {
        if ((a[i] = (float *)calloc(8, sizeof(float))) == NULL)
        {
            retValue = -100; // ERROR_INT("a[i] not made", procName, 1);
            goto Terminate;
        }
    }

    a[0][0] = sourceArea[0].x();
    a[0][1] = sourceArea[0].y();
    a[0][2] = 1.;
    a[0][6] = -sourceArea[0].x() * b[0];
    a[0][7] = -sourceArea[0].y() * b[0];
    a[1][3] = sourceArea[0].x();
    a[1][4] = sourceArea[0].y();
    a[1][5] = 1;
    a[1][6] = -sourceArea[0].x() * b[1];
    a[1][7] = -sourceArea[0].y() * b[1];
    a[2][0] = sourceArea[1].x();
    a[2][1] = sourceArea[1].y();
    a[2][2] = 1.;
    a[2][6] = -sourceArea[1].x() * b[2];
    a[2][7] = -sourceArea[1].y() * b[2];
    a[3][3] = sourceArea[1].x();
    a[3][4] = sourceArea[1].y();
    a[3][5] = 1;
    a[3][6] = -sourceArea[1].x() * b[3];
    a[3][7] = -sourceArea[1].y() * b[3];
    a[4][0] = sourceArea[2].x();
    a[4][1] = sourceArea[2].y();
    a[4][2] = 1.;
    a[4][6] = -sourceArea[2].x() * b[4];
    a[4][7] = -sourceArea[2].y() * b[4];
    a[5][3] = sourceArea[2].x();
    a[5][4] = sourceArea[2].y();
    a[5][5] = 1;
    a[5][6] = -sourceArea[2].x() * b[5];
    a[5][7] = -sourceArea[2].y() * b[5];
    a[6][0] = sourceArea[3].x();
    a[6][1] = sourceArea[3].y();
    a[6][2] = 1.;
    a[6][6] = -sourceArea[3].x() * b[6];
    a[6][7] = -sourceArea[3].y() * b[6];
    a[7][3] = sourceArea[3].x();
    a[7][4] = sourceArea[3].y();
    a[7][5] = 1;
    a[7][6] = -sourceArea[3].x() * b[7];
    a[7][7] = -sourceArea[3].y() * b[7];

    retValue = gaussjordan(a, b, 8);

Terminate:
    // Clean up
    for (i = 0; i < 8; i++)
    {
        if (a[i])
            free(a[i]);
    }

    this->coefficientsComputed = (retValue == 0);
    return retValue;
}


/*-------------------------------------------------------------*
 *               Gauss-jordan linear equation solver           *
 *-------------------------------------------------------------*/
/*
 *  gaussjordan()
 *
 *      Input:   a  (n x n matrix)
 *               b  (rhs column vector)
 *               n  (dimension)
 *      Return:  0 if ok, 1 on error
 *
 *      Note side effects:
 *            (1) the matrix a is transformed to its inverse
 *            (2) the vector b is transformed to the solution X to the
 *                linear equation AX = B
 *
 *      Adapted from "Numerical Recipes in C, Second Edition", 1992
 *      pp. 36-41 (gauss-jordan elimination)
 */
#define  SWAP(a,b)   {temp = (a); (a) = (b); (b) = temp;}
int genImageProjective::gaussjordan(float  **a, float  *b, int n)
{
    int retValue = 0;
    int i, icol=0, irow=0, j, k, l, ll;
    int *indexc = NULL, *indexr = NULL, *ipiv = NULL;
    float  big, dum, pivinv, temp;

    if (!a)
    {
        retValue = -1; // ERROR_INT("a not defined", procName, 1);
        goto Terminate;
    }
    if (!b)
    {
        retValue = -2; // ERROR_INT("b not defined", procName, 1);
        goto Terminate;
    }

    if ((indexc = (int *)calloc(n, sizeof(int))) == NULL)
    {
        retValue = -3; // ERROR_INT("indexc not made", procName, 1);
        goto Terminate;
    }
    if ((indexr = (int *)calloc(n, sizeof(int))) == NULL)
    {
        retValue = -4; // ERROR_INT("indexr not made", procName, 1);
        goto Terminate;
    }
    if ((ipiv = (int *)calloc(n, sizeof(int))) == NULL)
    {
        retValue = -5; // ERROR_INT("ipiv not made", procName, 1);
        goto Terminate;
    }

    for (i = 0; i < n; i++)
    {
        big = 0.0;
        for (j = 0; j < n; j++)
        {
            if (ipiv[j] != 1)
            {
                for (k = 0; k < n; k++)
                {
                    if (ipiv[k] == 0)
                    {
                        if (fabs(a[j][k]) >= big)
                        {
                            big = fabs(a[j][k]);
                            irow = j;
                            icol = k;
                        }
                    }
                    else if (ipiv[k] > 1)
                    {
                        retValue = -6; // ERROR_INT("singular matrix", procName, 1);
                        goto Terminate;
                    }
                }
            }
        }
        ++(ipiv[icol]);

        if (irow != icol)
        {
            for (l = 0; l < n; l++)
                SWAP(a[irow][l], a[icol][l]);
            SWAP(b[irow], b[icol]);
        }

        indexr[i] = irow;
        indexc[i] = icol;
        if (a[icol][icol] == 0.0)
        {
            retValue = -7; // ERROR_INT("singular matrix", procName, 1);
            goto Terminate;
        }
        pivinv = 1.0 / a[icol][icol];
        a[icol][icol] = 1.0;
        for (l = 0; l < n; l++)
            a[icol][l] *= pivinv;
        b[icol] *= pivinv;

        for (ll = 0; ll < n; ll++)
        {
            if (ll != icol)
            {
                dum = a[ll][icol];
                a[ll][icol] = 0.0;
                for (l = 0; l < n; l++)
                    a[ll][l] -= a[icol][l] * dum;
                b[ll] -= b[icol] * dum;
            }
        }
    }

    for (l = n - 1; l >= 0; l--)
    {
        if (indexr[l] != indexc[l])
        {
            for (k = 0; k < n; k++)
                SWAP(a[k][indexr[l]], a[k][indexc[l]]);
        }
    }

Terminate:
    if (indexr)
        free(indexr);
    if (indexc)
        free(indexc);
    if (ipiv)
        free(ipiv);
    return retValue;
}


// --------------------------------------------------------------
// Map a source point to destination using projective transform
// --------------------------------------------------------------
// Params:
//  sourcePoint: initial point
//  destPoint:   transformed point
// RetValue: 0: Success, !=0: Error
// --------------------------------------------------------------
//  Notes:
//   1. You must call once computeCoeefficients() to compute
//      the this->vc[] vector of 8 coefficients, before you call
//      mapSourceToDestPoint().
//   2. If there was an error or the 8 coefficients were not computed,
//      a -1 is returned and destPoint is just set to sourcePoint value.
// --------------------------------------------------------------
int genImageProjective::mapSourceToDestPoint(QPointF& sourcePoint, QPointF& destPoint)
{
    if (coefficientsComputed)
    {
        float factor = 1.0f / (vc[6] * sourcePoint.x() + vc[7] * sourcePoint.y() + 1.);
        destPoint.setX( factor * (vc[0] * sourcePoint.x() + vc[1] * sourcePoint.y() + vc[2]) );
        destPoint.setY( factor * (vc[3] * sourcePoint.x() + vc[4] * sourcePoint.y() + vc[5]) );
        return 0;
    }
    else // There was an error while computing coefficients
    {
        destPoint = sourcePoint; // just copy the source to destination...
        return -1;               // ...and return an error
    }
}
//========================================
回复 原文
梦途 2024-07-20 00:14:46

使用 Breton 的细分方法（与 Mongo 的扩展方法相关），将为您提供准确的任意二次幂除法。 要使用这些方法分割为非二次幂除法，您必须细分为子像素间距，这在计算上可能会很昂贵。

但是，我相信您可以应用 Haga 的变体定理（在折纸中用于将一条边划分为 N 条，给定一条边被划分为 (N-1) 条）透视平方细分可从最接近的 2 次方产生任意划分，而无需继续细分。

Using Breton's subdivision method (which is related to Mongo's extension method), will get you accurate arbitrary power-of-two divisions. To split into non-power-of-two divisions using those methods you will have to subdivide to sub-pixel spacing, which can be computationally expensive.

However, I believe you may be able to apply a variation of Haga's Theorem (which is used in origami to divide a side into Nths given a side divided into (N-1)ths) to the perspective-square subdivisions to produce arbitrary divisions from the closest power of 2 without having to continue subdividing.

回复 原文
野生奥特曼 2024-07-20 00:14:46

最优雅和最快的解决方案是找到单应性矩阵，它将矩形坐标映射到照片坐标。

有了一个像样的矩阵库，只要您了解数学知识，这应该不是一项艰巨的任务。

关键词：共线、单应性、直接线性变换

但是，上面的递归算法应该可以工作，但如果您的资源有限，射影几何可能是唯一的方法。

The most elegant and fastest solution would be to find the homography matrix, which maps rectangle coordinates to photo coordinates.

With a decent matrix library it should not be a difficult task, as long as you know your math.

Keywords: Collineation, Homography, Direct Linear Transformation

However, the recursive algorithm above should work, but probably if your resources are limited, projective geometry is the only way to go.

回复 原文
痞味浪人 2024-07-20 00:14:46

我认为所选答案并不是可用的最佳解决方案。 更好的解决方案是将矩形的透视（投影）变换应用到简单网格，如下所示的 Matlab 脚本和图像所示。 您也可以使用 C++ 和 OpenCV 来实现该算法。

function drawpersgrid
sz      = [ 24, 16 ]; % [x y]
srcpt   = [ 0 0; sz(1) 0; 0 sz(2); sz(1) sz(2)];
destpt  = [ 20 50; 100 60; 0 150; 200 200;];

% make rectangular grid
[X,Y]   = meshgrid(0:sz(1),0:sz(2));

% find projective transform matching corner points
tform   = maketform('projective',srcpt,destpt);

% apply the projective transform to the grid
[X1,Y1] = tformfwd(tform,X,Y);

hold on;

%% find grid

for i=1:sz(2)
    for j=1:sz(1)
        x = [ X1(i,j);X1(i,j+1);X1(i+1,j+1);X1(i+1,j);X1(i,j)];
        y = [ Y1(i,j);Y1(i,j+1);Y1(i+1,j+1);Y1(i+1,j);Y1(i,j)];
        plot(x,y,'b');
    end
end
hold off;

投影网格

I think the selected answer is not the best solution available. A better solution is to apply perspective (projective) transformation of a rectangle to simple grid as following Matlab script and image show. You can implement this algorithm with C++ and OpenCV as well.

function drawpersgrid
sz      = [ 24, 16 ]; % [x y]
srcpt   = [ 0 0; sz(1) 0; 0 sz(2); sz(1) sz(2)];
destpt  = [ 20 50; 100 60; 0 150; 200 200;];

% make rectangular grid
[X,Y]   = meshgrid(0:sz(1),0:sz(2));

% find projective transform matching corner points
tform   = maketform('projective',srcpt,destpt);

% apply the projective transform to the grid
[X1,Y1] = tformfwd(tform,X,Y);

hold on;

%% find grid

for i=1:sz(2)
    for j=1:sz(1)
        x = [ X1(i,j);X1(i,j+1);X1(i+1,j+1);X1(i+1,j);X1(i,j)];
        y = [ Y1(i,j);Y1(i,j+1);Y1(i+1,j+1);Y1(i+1,j);Y1(i,j)];
        plot(x,y,'b');
    end
end
hold off;

Projective grid

回复 原文
星軌x 2024-07-20 00:14:46

在特殊情况，当您垂直于边 1 和边 3 观察时，您可以将这些边分成相等的部分。 然后画一条对角线，并通过对角线和之前画的分界线的每个交点绘制与边 1 平行的平行线。

In the special case when you look perpendicular to sides 1 and 3, you can divide those sides in equal parts. Then draw a diagonal, and draw parallels to side 1 through each intersection of the diagonal and the dividing lines drawn earlier.

回复 原文
过度放纵 2024-07-20 00:14:46

这是我想出的几何解决方案。 我不知道这个“算法”是否有名字。

假设您想首先将“矩形”分成 n 个垂直线块。

目标是将点 P1..Pn-1 放在顶线上，当这样的点不存在时，我们可以用它来绘制穿过它们的线到左线和右线相交或平行于它们的点。

如果顶线和底线彼此平行，只需放置这些点即可将顶线等距地分割在角之间。

否则将 n 个点 Q1..Qn 放在左线上，使这些点与左上角等距，并且 i < j => Qi 比 Qj 更靠近左上角。
为了将 Q 点映射到顶线，找到从 Qn 穿过右上角的线与通过顶线和底线交点平行于左侧线的交点 S。 现在将 S 与 Q1..Qn-1 连接。 新线与顶线的交点就是所需的 P 点。

对水平线进行类似的操作。

This a geometric solution I thought out. I do not know whether the 'algorithm' has a name.

Say you want to start by dividing the 'rectangle' into n pieces with vertical lines first.

The goal is to place points P1..Pn-1 on the top line which we can use to draw lines through them to the points where the left and right line meet or parallel to them when such point does not exist.

If the top and bottom line are parallel to each other just place thoose points to split the top line between the corners equidistantly.

Else place n points Q1..Qn on the left line so that theese and the top-left corner are equidistant and i < j => Qi is closer to the top-left cornern than Qj.
In order to map the Q-points to the top line find the intersection S of the line from Qn through the top-right corner and the parallel to the left line through the intersection of top and bottom line. Now connect S with Q1..Qn-1. The intersection of the new lines with the top line are the wanted P-points.

Do this analog for the horizontal lines.

回复 原文
平生欢 2024-07-20 00:14:46

给定绕 y 轴的旋转，特别是如果旋转表面是平面的，则透视由垂直梯度生成。 这些问题的视角逐渐接近。 不是使用对角线来定义四个矩形，它可以在给定的二的幂上工作...定义两个矩形，左和右。 如果继续将表面分成更窄的垂直部分，最终它们的高度将大于宽度。 这可以适应非方形的表面。 如果绕 x 轴旋转，则需要水平渐变。

Given a rotation around the y axis, especially if rotation surfaces are planar, the perspective is generated by vertical gradients. These get progressively closer in perspective. Instead of using diagonals to define four rectangles, which can work given powers of two... define two rectangles, left and right. They'll be higher than wide, eventually, if one continues to divide the surface into narrower vertical segments. This can accommodate surfaces that are not square. If a rotation is around the x axis, then horizontal gradients are needed.

回复 原文
简美 2024-07-20 00:14:46

您需要做的是以 3D（世界）表示它，然后将其投影到 2D（屏幕）。

这将需要您使用 4D 变换矩阵，该矩阵将 4D 齐次投影投影为 3D 齐次向量，然后您可以将其转换为 2D 屏幕空间向量。

我在谷歌上也找不到它，但是一本好的计算机图形书籍会有详细信息。

关键词是投影矩阵、投影变换、仿射变换、齐次向量、世界空间、屏幕空间、透视变换、3D 变换

顺便说一句，这通常需要几节课才能解释所有这些。 祝你好运。

What you need to do is represent it in 3D (world) and then project it down to 2D (screen).

This will require you to use a 4D transformation matrix which does the projection on a 4D homogeneous down to a 3D homogeneous vector, which you can then convert down to a 2D screen space vector.

I couldn't find it in Google either, but a good computer graphics books will have the details.

Keywords are projection matrix, projection transformation, affine transformation, homogeneous vector, world space, screen space, perspective transformation, 3D transformation

And by the way, this usually takes a few lectures to explain all of that. So good luck.

回复 原文
~没有更多了~

关于作者

箹锭⒈辈孓

暂无简介

0 文章
0 评论
21 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

不再见

文章 0 评论 0

真是无聊啊

文章 0 评论 0

樱娆

文章 0 评论 0

浅语花开

文章 0 评论 0

烛光

文章 0 评论 0

绻影浮沉

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文