Cómo dibujar una cuadrícula en perspectiva correcta en 2D
https://stackoverflow.com/questions/530396
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Tengo una aplicación que define una verdadera rectángulo mundo en la parte superior de una imagen / fotografía, por supuesto, en 2D puede que no sea un rectángulo, ya que están mirando desde un ángulo.
El problema es que dicen que el rectángulo tiene que tener líneas de la cuadrícula dibujadas en él, por ejemplo si se trata de 3x5, así que necesito para dibujar 2 líneas de lado 1 a 3 lateral, y 4 líneas de la cara 2 a lado 4.
A partir de ahora estoy rompiendo a cada línea en partes equidistantes, para obtener el punto de todas las líneas de la cuadrícula de inicio y fin. Sin embargo, más de un ángulo del rectángulo está activado, los más "incorrectas" estas líneas se vuelven, como líneas horizontales más lejos de usted debe estar más cerca juntos.
¿Alguien sabe el nombre del algoritmo que debería estar buscando?
Sí sé que usted puede hacer esto en 3D, sin embargo yo estoy limitado a 2D para esta aplicación en particular.
Solución
Aquí es la solución.
La idea básica es que se puede encontrar la perspectiva correcta "centro" de su rectángulo mediante la conexión de las esquinas en diagonal. La intersección de las dos líneas resultantes es su perspectiva central correcta. Desde allí se subdivide a su rectángulo en cuatro rectángulos más pequeños, y se repite el proceso. El número de veces depende de la precisión que lo desee. Se puede subdividir hasta justo por debajo del tamaño de un pixel para la perspectiva de eficacia perfecta.
Luego, en sus subrentángulos sólo se aplican los triángulos estándar sin corregir "texturizado", o rectángulos o lo que sea.
Puede llevar a cabo este algoritmo sin tener que ir al complejo problema de la construcción de un mundo 3D 'real'. también es bueno para si hace tener un verdadero mundo 3D modelado, pero sus textriangles no están perspectiva corregida en hardware, o si necesita una manera performant para obtener perspectiva planos correctos, sin por engaño prestación de píxeles.
Otros consejos
Image: Ejemplo de bilineal y perspectiva de transformación (Nota: La altura de la parte superior y las líneas de cuadrícula horizontal inferior es en realidad un medio de la altura de las líneas de descanso, en ambos dibujos)
========================================
Sé que esto es una vieja pregunta, pero tengo una solución genérica, así que decidí publicarla saltando será útil a los futuros lectores. El abajo código puede dibujar una cuadrícula de perspectiva arbitraria sin la necesidad de cálculos repetitivos.
Comienzo de hecho con un problema similar: para dibujar una cuadrícula de perspectiva en 2D y luego transformar la imagen de subrayado para restaurar la perspectiva
.empecé a leer aquí: http://www.imagemagick.org/Usage/distorts/#bilinear_forward
y luego aquí (la Biblioteca Leptonica): http://www.leptonica.com/affine.html
eran encontré esto:
Cuando se mira un objeto en un plano de alguna dirección arbitraria en una distancia finita, se obtiene una distorsión adicional "clave" en el imagen. Este es un proyectiva transformar, lo que mantiene las líneas rectas recto pero no conserva los ángulos entre líneas. esta deformación no puede ser descrito por una transformación afín lineal, y de hecho difiere en términos X e Y-dependientes en el denominador.
La transformación no es lineal, ya que muchas personas ya se ha señalado en este hilo. Se trata de la resolución de un sistema lineal de ecuaciones 8 (una vez) para calcular los coeficientes necesarios 8 y luego se puede utilizar para transformar tantos puntos como desee.
Para evitar la inclusión de toda la biblioteca Leptonica en mi proyecto, tomé algunas piezas de código de él, quité todas las especiales Leptonica tipos de datos y macros, me han solucionado algunos pérdidas de memoria y me convertí a una clase de C ++ (en su mayoría para la encapsulación razones), que se limita a una sola cosa: Se asigna un (Qt) flotador QPointF (x, y) de coordenadas a la perspectiva coordenada correspondiente.
Si desea adaptar el código a otra biblioteca de C ++, el único que se puede redefinir / sustituto es la coordenada QPointF clase.
Espero que algunos futuros lectores les resultaría útil. El abajo código se divide en 3 partes:
A. Un ejemplo de cómo usar la genImageProjective clase de C ++ para dibujar una 2D perspectiva de la red
B. genImageProjective.h archivo
C. genImageProjective.cpp archivo
//============================================================
// 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
}
}
//========================================
Mientras mi google-fu no ha presentado ninguna solución matemática sólida como una roca, tal vez este dibujo que encontré podría ayudar un poco.
http://studiochalkboard.evansville.edu/lp-diminish.html
Creo que en realidad podría ser bastante difícil para llegar a la correcta matemáticas por su cuenta, es probable que sea una especie de expresión logarítmica o suma. Con suerte el dibujo y los términos en que enlazan podrían proporcionar algo un poco más búsquedas para usted.
Utilizando el método de subdivisión de Breton (que está relacionada con el método de extensión de Mongo), te llevará precisos arbitrarias divisiones de potencias de dos. Para dividir en divisiones no-poder-de-dos usando los métodos que tendrá que subdividir al espaciamiento de sub-píxeles, que puede ser costoso computacionalmente.
Sin embargo, creo que puede ser capaz de aplicar una variación de Teorema de Haga (que se utiliza en Origami dividir un lado en NTHS dado un lado dividido en (N-1) THS) en las subdivisiones del perspectiva-cuadrado para producir divisiones arbitrarias de la potencia más cercano de 2 sin tener para continuar subdividiendo.
La solución más elegante y más rápido sería encontrar la matriz de homografía, que mapea el rectángulo en coordenadas de fotos.
Con una librería de matriz decente no debe ser una tarea difícil, ya que siempre que se sepa su matemática.
Palabras clave: colineación, homografía, transformación directa lineal
Sin embargo, el algoritmo recursivo anterior debería funcionar, pero probablemente si sus recursos son limitados, la geometría proyectiva es el único camino a seguir.
En el caso especial cuando se mira perpendicularmente a los lados 1 y 3, se puede dividir esos lados en partes iguales. Entonces dibujar una diagonal, y establecer paralelismos a lado 1 a través de cada intersección de la diagonal y las líneas divisorias dibujados anteriormente.
Esta solución geométrica pensé cabo. No sé si el 'algoritmo' tiene un nombre.
Supongamos que quiere empezar dividiendo el 'rectángulo' en n piezas con líneas verticales en primer lugar.
El objetivo es colocar puntos P1..Pn-1 en la línea superior que podemos utilizar para dibujar líneas a través de ellos a los puntos en los que no existe la izquierda y la derecha se encuentran la línea o en paralelo a ellos tal punto.
Si la parte superior y la línea inferior son paralelas entre sí sólo tiene que colocar thoose puntos para dividir la línea superior entre las esquinas de manera equidistante.
lugar Else n puntos Q1..Qn en la línea izquierda de modo que theese y la esquina superior izquierda son equidistantes y i
Haga esto analógica para las líneas horizontales.
Dada una rotación alrededor del eje y, especialmente si las superficies de rotación son planas, la perspectiva se genera por gradientes verticales. Estos se van haciendo progresivamente más cerca en perspectiva. En lugar de utilizar las diagonales para definir cuatro rectángulos, que puede trabajar poderes dados de dos ... definir dos rectángulos, izquierda y derecha. Van a ser más alto que ancho, con el tiempo, si se sigue dividiendo a la superficie en segmentos verticales más estrechas. Esto puede acomodar las superficies que no son cuadradas. Si una rotación es alrededor del eje x, se necesitan gradientes entonces horizontales.
Creo que la respuesta seleccionada no es la mejor solución disponible. Una solución mejor es aplicar perspectiva (proyectiva) transformación de un rectángulo a la red simple como siguiente secuencia de comandos Matlab y mostrar la imagen. Puede implementar este algoritmo con C ++ y OpenCV también.
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;
El problema es que es la transformación de 3D a 2D que está recibiendo.
Aquí 'sa tutorial sobre cómo se hace.
Lo que hay que hacer es representarla en 3D (mundial) y luego proyectarla hacia 2D (pantalla).
Para ello será necesario utilizar una matriz de transformación 4D que realiza la proyección en una 4D homogénea a un vector 3D homogénea, que luego se puede convertir a un vector de espacio de la pantalla 2D.
No pude encontrarlo en Google tampoco, pero unos buenos libros de gráficos por ordenador tendrá los detalles.
Las palabras clave son matriz de proyección, la transformación de proyección, transformación afín, vector homogénea, espacio del mundo, el espacio de pantalla, la transformación de perspectiva, la transformación 3D
Y, por cierto, esto por lo general toma unos conferencias para explicar todo eso. Así que buena suerte.
