Como desenhar uma grade de perspectiva-Correct em 2D
https://stackoverflow.com/questions/530396
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho um aplicativo que define um retângulo mundo real em cima de uma imagem / fotografia, é claro, em 2D, pode não ser um retângulo porque você está olhando para ele de um ângulo.
O problema é, dizer que as necessidades do retângulo de ter linhas de posição desenhadas sobre ele, por exemplo, se for 3x5 assim que eu preciso para desenhar 2 linhas de lado 1 para o outro 3, e 4 linhas de lado 2 a lado 4.
A partir de agora eu estou quebrando cada linha em partes eqüidistantes, para obter o ponto de início e fim de todas as linhas de grade. No entanto, a mais de um ângulo do retângulo está ligado, o mais "incorreto" essas linhas tornam-se, como linhas horizontais mais de você deve ser mais juntos.
Alguém sabe o nome do algoritmo que eu deveria estar procurando?
Sim, eu sei que você pode fazer isso em 3D, no entanto estou limitado a 2D para esta aplicação particular.
Solução
Eis a solução.
A idéia básica é que você pode encontrar a perspectiva correta "centro" do seu retângulo, ligando os cantos diagonalmente. A interseção das duas linhas resultantes é a sua perspectiva de centro correta. De lá você subdividir seu retângulo em quatro retângulos menores, e você repita o processo. O número de vezes depende de quão preciso você quer. Você pode subdividir até um pouco abaixo do tamanho de um pixel para a perspectiva efetivamente perfeito.
Então, em seus subrectangles você acabou de aplicar o seu padrão não corrigida "texturizada" triângulos ou retângulos ou o que quer.
Você pode executar este algoritmo sem indo para o trabalho complexo de construir um mundo 3D 'real'. também é bom para se você do tem um mundo 3D real, modelada, mas seus textriangles não são perspectiva corrigido no hardware, ou você precisa de uma maneira performance para obter perspectiva aviões corretos, sem por artifícios de renderização pixel.
Outras dicas
Imagem: Exemplo de bilinear & Perspectiva Transform (Nota: A altura da parte superior e as linhas de grelha horizontais inferior é, na verdade, a metade da altura de repouso linhas, em ambos os desenhos)
========================================
Eu sei que isto é uma questão antiga, mas eu tenho uma solução genérica então eu decidi publicá-lo pulando será útil para os futuros leitores. O código abaixo pode desenhar uma grade de perspectiva arbitrária, sem a necessidade de cálculos repetitivos.
Eu começo realmente com um problema semelhante: para desenhar uma 2D perspectiva da grade e, em seguida, transformar a imagem sublinhado para restaurar a perspectiva
.Eu comecei a ler aqui: http://www.imagemagick.org/Usage/distorts/#bilinear_forward
e, em seguida, aqui (na Biblioteca Leptonica): http://www.leptonica.com/affine.html
foram Achei isso:
Quando você olha para um objeto em um avião de alguma direção arbitrária na uma distância finita, você recebe uma distorção adicional "distorção" na imagem. Este é transformar um projetiva, que mantém linhas retas reta, mas não preserva os ângulos entre as linhas. esta deformação não podem ser descritas por uma transformação afim linear, e na verdade afastar em termos X- e dependente-y no denominador.
A transformação não é linear, como muitas pessoas já apontado neste segmento. Trata-se de resolver um sistema linear de 8 equações (uma vez) para calcular as 8 coeficientes necessários e então você pode usá-los para transformar tantos pontos quanto você quiser.
Para evitar incluindo todos os biblioteca Leptonica no meu projeto, eu levei alguns pedaços de código a partir dele, tirei todos os Leptonica dados-tipos e macros especiais, eu corrigidos alguns vazamentos de memória e I converteu-o para uma classe C ++ (principalmente para encapsulamento razões) que faz apenas uma coisa: Ele mapeia um (Qt) QPointF flutuador (x, y) de coordenadas para o Perspectiva correspondente de coordenadas.
Se você quiser adaptar o código para outra biblioteca C ++, a única coisa a redefinir / substituto é o QPointF coordenar classe.
Espero que alguns leitores futuros iria encontrá-lo útil. O código abaixo é dividido em 3 partes:
A. Um exemplo de como usar a classe do genImageProjective C ++ para desenhar um 2D perspectiva da grade
B. arquivo genImageProjective.h
C. arquivo 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
}
}
//========================================
Enquanto o meu google-fu não conseguiu produzir qualquer solução matemática rocha sólida, talvez este desenho que eu encontrei poderia ajudar um pouco.
http://studiochalkboard.evansville.edu/lp-diminish.html
Eu acho que ele pode realmente ser muito difícil chegar com a matemática correta em seu próprio país, é provavelmente algum tipo de expressão logarítmica ou somatório. Esperemos que o desenho e os termos em que o link pode fornecer algo um pouco mais procurado para você.
Usando o método de subdivisão de Breton (que está relacionado com método de extensão do Mongo), você vai chegar arbitrárias divisões precisas potência de dois. Para dividido em divisões sem motor-de-dois, usando esses métodos você terá que subdividir ao espaçamento sub-pixel, o que pode ser computacionalmente caro.
No entanto, eu acredito que você pode ser capaz de aplicar uma variação de Teorema de Haga (que é usado no origami para dividir um lado em Nths dadas um lado dividido em (n-1) ths) para as subdivisões perspective-quadrado para produzir divisões arbitrárias da potência mais próxima de 2, sem ter para continuar parcelamento.
A solução mais elegante e mais rápido seria encontrar a matriz homografia, que mapeia coordenadas retângulo em coordenadas de fotos.
Com uma biblioteca de matriz decente não deve ser uma tarefa difícil, desde que você saiba a sua matemática.
Palavras-chave: Collineation, homografia, Transformação Linear Direta
No entanto, o algoritmo recursivo acima deve funcionar, mas provavelmente se seus recursos são limitados, geometria projetiva é o único caminho a percorrer.
No caso especial quando você olha perpendicular para os lados 1 e 3, você pode dividir esses lados em partes iguais. Em seguida, desenhe uma diagonal, e estabelecer paralelos ao lado de 1 a cada intersecção da diagonal e as linhas divisórias desenhada anteriormente.
Esta uma solução geométrica I pensado. Eu não sei se o 'algoritmo' tem um nome.
Digamos que você queira começar dividindo o 'rectângulo' em n peças com linhas verticais em primeiro lugar.
O objetivo é colocar pontos P1..Pn-1 na linha superior que podemos usar para desenhar linhas através deles para os pontos onde se encontram linha esquerda e direita ou paralelos a eles quando tal ponto não existe.
Se a parte superior e linha inferior são paralelos um ao outro lugar apenas thoose pontos para dividir a linha superior entre os cantos de forma equidistante.
Else lugar n pontos Q1..Qn na linha de esquerda para que theese eo canto superior esquerdo são eqüidistantes e i
Faça isso analógico para as linhas horizontais.
Dada uma rotação em torno do eixo y, especialmente se as superfícies de rotação serem planas, o perspectiva é gerado por gradientes verticais. Estes ficam progressivamente mais perto em perspectiva. Em vez de usar diagonais para definir quatro retângulos, que pode trabalhar dado poderes de dois ... definir dois retângulos, esquerda e direita. Eles vão ser mais elevada do que largo, finalmente, se uma continua a dividir a superfície em segmentos verticais mais estreitas. Isto pode acomodar superfícies que não são quadrados. Se uma rotação é em torno do eixo x, são necessários gradientes horizontais, em seguida.
Eu acho que a resposta escolhida não é a melhor solução disponível. Uma solução melhor é aplicar perspectiva de transformação (projetiva) de um retângulo à grade simples como seguir Matlab script e imagem show. Você pode implementar este algoritmo com C ++ e OpenCV também.
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;
O problema é que é a transformação de 3D para 2D que é ficar com você.
Aqui 'sa tutorial sobre como ele é feito.
O que você precisa fazer é representá-lo em 3D (mundial) e, em seguida, projectá-la para baixo para 2D (tela).
Isso vai exigir que você use uma matriz de transformação 4D que faz a projeção em um baixo homogênea 4D para um vetor homogêneo 3D, que pode então ser convertido para baixo para um vetor espaço na tela 2D.
Eu não poderia encontrá-lo no Google quer, mas uma boa computação gráfica livros terá os detalhes.
Palavras-chave são matriz de projeção, transformação de projeção, transformação afim, vetor homogêneo, espaço do mundo, o espaço na tela, transformação de perspectiva, a transformação 3D
E, a propósito, isso geralmente leva algumas palestras para explicar tudo isso. Então, boa sorte.
