Comment déprojeter un quadrilatère en rectangle?

tl; dr: Problème mathématique en géométrie projective: comment trouver une matrice de caméra 4x4 qui donne une projection comme illustré ci-dessous, de telle sorte que les points A, B, C, D sont quelque part sur les bords de la boîte d'unité (par exemple, un appareil normalisé OpenGL coordonnées), et les coins de la boîte de l'unité tombent quelque part raisonnable le long des rayons EA, EB, EC, ED?

(Il peut s'agir d'un cas particulier, peut-être d'homographie, de perspective et / ou de collinéation. Pas familier avec la terminologie.)

élaboration

Étant donné un quadrilatère ABCD dans la fenêtre d'affichage, je pense qu'il existe une transformation unique (?) Qui la mappe en un rectangle. Comme le montre l'image ci-dessous: le quadrilatère ABCD dans la fenêtre agit comme une «fenêtre» physique, et si nous le mappons sur un rectangle, il apparaîtra déformé.

(l'encadré à droite représente NDC, dont je parlerai plus tard)

Le but est d'obtenir rapidement l'image de droite. Nous pourrions lancer un lancer de rayons sur chaque point pour obtenir l'image (ce que j'ai fait), mais je préférerais utiliser OpenGL ou d'autres techniques projectives parce que je voulais profiter de choses comme le mélange, les primitives, etc.

premier essai

Je crois que je peux résoudre le problème de trouver la matrice de caméra 3x4 qui rend les coordonnées homogènes 3 + 1 dimensionnelles dans 3 espaces (à gauche) et la projette vers le bas jusqu'aux coordonnées homogènes 2 + 1 dimensions dans 2 espaces (sur la droite). On peut résoudre ce problème en utilisant la transformation linéaire directe pour obtenir un système d'équations Ba=0pour les entrées inconnues ade la matrice de la caméra, et en résolvant le système en utilisant la décomposition en valeurs singulières(SVD). Je prendrais les vecteurs EA, EB, EC, ED (où E est votre œil physique ou la caméra dans l'espace-monde) comme points dans la pré-image, et (0,0), (1,0), (1 , 1), (0,1) ou quelque chose comme les points dans la post-image, et chaque paire de points donnerait quelques équations linéaires à brancher dans le SVD. La matrice résultante mapperait EA -> (0,0) etc. (en supposant qu'il y a suffisamment de degrés de liberté, c'est-à-dire si la solution est unique, ce dont je ne suis pas sûr, voir la note [a].)

Mais à mon grand regret, ce n'est pas ainsi que fonctionne OpenGL. OpenGL ne projette pas directement de 3d à 2d avec une matrice 3x4. OpenGL nécessite des "coordonnées de périphérique normalisées" (NDC), qui sont des points tridimensionnels. Après la projection dans NDC, tout dans la case «unité» de (-1, -1, -1,1) à (1,1,1,1) est dessiné; tout ce qui se trouve à l'extérieur est coupé (car nous avons affaire à des coordonnées homogènes: tout point (x, y, z, w) n'apparaîtra à l'écran que si les trois premières coordonnées de (x / w, y / w, z / w , 1) se trouvent dans la zone unitaire de -1 à 1).

Donc la question devient: existe-t-il une transformation raisonnable qui mappe un cuboïde d'aspect étrange en coordonnées homogènes (en particulier le cuboïde dessiné à gauche, avec ABCD (points avant) et A'B'C'D '(points arrière, cachés) derrière les points avant)) au cube unitaire, par exemple en utilisant une matrice 4x4? Comment fait-on?

ce que j'ai essayé

J'ai essayé quelque chose de plus fort: j'ai fait ressembler ABCD et A'B'C'D à un frustrum pyramidal régulier (par exemple gl frustrum) (c'est-à-dire que dans cette configuration hypothétique, l'image de gauche aurait juste un rectangle noir superposé sur pas un quadrilatère), puis a utilisé la transformation linéaire DLT / directe pour résoudre la matrice 4x4 présumée. Cependant, quand je l'ai essayé, il ne semblait pas y avoir suffisamment de degrés de liberté ... la matrice 4x4 résultante n'a pas mappé chaque vecteur d'entrée à chaque vecteur de sortie. En utilisant A, B, C, D, A '(5 paires de vecteurs pré-transformés et post-transformés), j'obtiens / obtiens presque le résultat que je veux ... les vecteurs sont correctement mappés, mais par exemple B', C ', D' sont mappés sur (3,3,1,1) au lieu de (-1, -1,1,1) et sont coupés par OpenGL. Si j'essaye d'ajouter un sixième point (6 paires de points pour la matrice 4x4 à projeter), ma solution semble dégénérée (zéros, infinis). À combien de degrés de liberté ai-je affaire ici, et est-ce possible avec une matrice 4x4 cartographiant les 4 vecteurs habituels (vecteurs de coordonnées homogènes à 3 + 1 dimensions) que nous connaissons et aimons?

pensées mineures aléatoires

Je suppose qu'il n'est pas possible de mapper un cuboïde arbitraire à un cuboïde arbitraire avec une matrice 4x4, bien que je sois confus parce que je pensais qu'il était possible de mapper n'importe quel quadrilatère convexe à tout autre quadrilatère convexe en 2d avec une matrice comme dans disons Photoshop? ... cela ne peut-il pas être fait avec une transformation projective? Et comment se généralise-t-il en 3D? ...... Compte tenu également de l'échec de la tentative de trouver une matrice 4x4, l'algèbre linéaire dit que nous ne devrions pas nous attendre à ce qu'une matrice NxN mappe plus de N points linéairement indépendants à N points cibles dans le meilleur des cas, mais je pense qu'en quelque sorte homogène les coordonnées trichent parce qu'il y a une colinéarité cachée? Je suppose que non?

une autre solution?

Je suppose que l'on pourrait également faire la chose laide suivante, où vous utilisez une matrice de projection de caméra frustrum typique, trouvez les points 2d correspondant aux coins, puis effectuez une homographie de distorsion en perspective 2d, mais si cela devait se produire après le rendu des pixels (par exemple Photoshop) alors il y aurait des problèmes de résolution ... peut-être que l'on pourrait imaginer une matrice pour effectuer cette transformation sur le plan XY dans l'espace NDC, puis la composer avec la matrice normale basée sur le frustrum?

(note [a]: Degré de liberté: ABCD peut être davantage contraint à être la post-image d'une transformation projective agissant sur un rectangle, si cela est nécessaire ... c'est-à-dire que le rectangle noir à gauche pourrait être considéré comme le résultat de la projection d'un modèle de clipart cadre photo)

Je pense que la solution est à la recherche de la transformation projective qui transforme correctement les quatre points.

c'est à dire

$x' = [x_0, x_1, 1]$$y = [\frac{y'_0}{y'_2}, \frac{y'_1}{y'_2}]$

$P$

Vous pouvez maintenant utiliser l'algèbre pour ce faire, ou simplement utiliser OpenCV getPerspectiveTransform:).

Consultez également les coordonnées homnogènes sur wikipedia pour vous familiariser avec le concept.

J'ai résolu ma propre question en implémentant la transformation linéaire directe . La section des exemples sur Wikipedia était mon cas d'utilisation.

Pour obtenir les équations, branchez les matrices (par exemple [x1 x2 x3 x4; x5 x6 x7 x8; x9 x10 x11 x12]) dans votre système d'algèbre informatique préféré comme SageMath, puis résolvez l'équation de matrice requise comme illustré, copiez-collez les solutions en termes de variables dans votre code et ajustez la mise en forme.

On pourrait alors adapter la solution à son cas d'utilisation en mettant à l'échelle ou en ignorant des dimensions particulières selon le cas (par exemple, ignorer la coordonnée profondeur / z dans la matrice des coordonnées de l'appareil normalisé selon le cas d'utilisation).

Vous aurez besoin d'une fonction ou d'une bibliothèque de décomposition SVD dans votre langue.