C++ 2D Perspective Transformations
От: McSeem2 США http://www.antigrain.com
Дата: 30.11.03 21:39
Оценка: 93 (7) +1
Наконец-то я имплементировал перспективные преобразования в 2D. Все, что есть готового, мне по тем или иным причинам не нравилось — либо очень сложно и много зависимостей (как в ImageMagic — там любой файл тащит за собой полбиблиотеки, хотя, конечно же, неисчерпаемый кладезь), либо тормозно и глючно.

Итак, в общем случае, выполняется преобразование из произвольного четырехугольника в другой произвольный четырехугольник. Для удобства сделаны функции rect_to_quad() и quad_to_rect() (надеюсь, понятно) и соответствующие конструкторы. Случаи невыпуклых четырехугольников не отслеживаются, то есть, что дали, то и будет — ничего лишнего, только алгоритмическо-вычислительная часть. К тому же, есть случаи, когда перспективные преобразования все еще можно использовать и при невыпуклых четырехугольниках.

Как использовать, например:

agg::trans_perspective tr(x1, y1, x2, y2, quad);

double x = 100.0;
double y = 100.0;
tr.transform(&x, &y);


Здесь x1,y1,x2,y2 — исходный прямоугольник, quad — четырехугольник, заданный массивом double[8], то есть, x1,y1,x2,y2,x3,y3,x4,y4.

Несколько скриншотов:
http://www.antigrain.com/perspective1.gif
http://www.antigrain.com/perspective2.gif
http://www.antigrain.com/perspective3.gif
http://www.antigrain.com/perspective4.jpg
http://www.antigrain.com/perspective5.jpg


Ну и как это все работает (exe для Win32):
http://www.antigrain.com/perspective.zip
Ох, бедное животное — над вами бы так поиздевались

Кроме того, есть аналогичный класс для билинейных преобразований (agg::trans_bilinear), как в GDI+.
Дальнейние посты — собственно исходники.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re: C++ 2D Perspective Transformations
От: McSeem2 США http://www.antigrain.com
Дата: 30.11.03 21:44
Оценка:
Начинаем с решения системы линейных уравнений. Это просто и весьма коротко для данного применения.


//----------------------------------------------------------------------------
// Anti-Grain Geometry - Version 2.0 
// Copyright (C) 2002 Maxim Shemanarev (McSeem)
//
// Permission to copy, use, modify, sell and distribute this software 
// is granted provided this copyright notice appears in all copies. 
// This software is provided "as is" without express or implied
// warranty, and with no claim as to its suitability for any purpose.
//
//----------------------------------------------------------------------------
// Contact: mcseem@antigrain.com
//          mcseemagg@yahoo.com
//          http://www.antigrain.com
//----------------------------------------------------------------------------
//
// Solving simultaneous equations
//
//----------------------------------------------------------------------------
#ifndef AGG_SIMUL_EQ_INCLUDED
#define AGG_SIMUL_EQ_INCLUDED

#include <math.h>

namespace agg
{

    //========================================================================
    template<class T> void swap_arrays(T* a1, T* a2, unsigned n)
    {
        unsigned i;
        for(i = 0; i < n; i++)
        {
            T tmp = *a1;
            *a1++ = *a2;
            *a2++ = tmp;
        }
    }


    //========================================================================
    template<unsigned Rows, unsigned Cols>
    struct matrix_pivot
    {
        static int pivot(double m[Rows][Cols], unsigned row)
        {
            int k = int(row);
            double max_val, tmp;

            max_val = -1.0;
            unsigned i;
            for(i = row; i < Rows; i++)
            {
                if((tmp = fabs(m[i][row])) > max_val && tmp != 0.0)
                {
                    max_val = tmp;
                    k = i;
                }
            }

            if(m[k][row] == 0.0)
            {
                return -1;
            }

            if(k != int(row))
            {
                swap_arrays(m[k], m[row], Cols);
                return k;
            }
            return 0;
        }
    };
    


    //========================================================================
    template<unsigned Size, unsigned RightCols>
    struct simul_eq
    {
        static bool solve(const double left[Size][Size], 
                          const double right[Size][RightCols],
                          double result[Size][RightCols])
        {
            unsigned i, j, k;
            double a1;

            double tmp[Size][Size + RightCols];

            for(i = 0; i < Size; i++)
            {
                for(j = 0; j < Size; j++)
                {
                    tmp[i][j] = left[i][j];
                } 
                for(j = 0; j < RightCols; j++)
                {
                    tmp[i][Size + j] = right[i][j];
                }
            }

            for(k = 0; k < Size; k++)
            {
                if(matrix_pivot<Size, Size + RightCols>::pivot(tmp, k) < 0)
                {
                    return false; // Singularity....
                }

                a1 = tmp[k][k];

                for(j = k; j < Size + RightCols; j++)
                {
                    tmp[k][j] /= a1;
                }

                for(i = k + 1; i < Size; i++)
                {
                    a1 = tmp[i][k];
                    for (j = k; j < Size + RightCols; j++)
                    {
                        tmp[i][j] -= a1 * tmp[k][j];
                    }
                }
            }


            for(k = 0; k < RightCols; k++)
            {
                int m;
                for(m = int(Size - 1); m >= 0; m--)
                {
                    result[m][k] = tmp[m][Size + k];
                    for(j = m + 1; j < Size; j++)
                    {
                        result[m][k] -= tmp[m][j] * result[j][k];
                    }
                }
            }
            return true;
        }

    };


}

#endif
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re: C++ 2D Perspective Transformations
От: McSeem2 США http://www.antigrain.com
Дата: 30.11.03 21:46
Оценка:
Далее идут собственно перспективные преобразования agg_trans_perspective.h:
(Забыл сказать, что предыдущий файл — agg_simul_eq.h)


//----------------------------------------------------------------------------
// Anti-Grain Geometry - Version 2.0 
// Copyright (C) 2002 Maxim Shemanarev (McSeem)
//
// Permission to copy, use, modify, sell and distribute this software 
// is granted provided this copyright notice appears in all copies. 
// This software is provided "as is" without express or implied
// warranty, and with no claim as to its suitability for any purpose.
//
//----------------------------------------------------------------------------
// Contact: mcseem@antigrain.com
//          mcseemagg@yahoo.com
//          http://www.antigrain.com
//----------------------------------------------------------------------------
//
// Perspective 2D transformations
//
//----------------------------------------------------------------------------
#ifndef AGG_TRANS_PERSPECTIVE_INCLUDED
#define AGG_TRANS_PERSPECTIVE_INCLUDED

#include "agg_simul_eq.h"

namespace agg
{
    //========================================================================
    class trans_perspective
    {
    public:
        //--------------------------------------------------------------------
        trans_perspective() : m_valid(false) {}


        //--------------------------------------------------------------------
        // Arbitrary quadrangle transformations
        trans_perspective(const double* src, const double* dst) 
        {
            quad_to_quad(src, dst);
        }


        //--------------------------------------------------------------------
        // Direct transformations 
        trans_perspective(double x1, double y1, double x2, double y2, 
                          const double* quad)
        {
            rect_to_quad(x1, y1, x2, y2, quad);
        }


        //--------------------------------------------------------------------
        // Reverse transformations 
        trans_perspective(const double* quad, 
                          double x1, double y1, double x2, double y2)
        {
            quad_to_rect(quad, x1, y1, x2, y2);
        }


        //--------------------------------------------------------------------
        // Set the transformations using two arbitrary quadrangles.
        void quad_to_quad(const double* src, const double* dst)
        {

            double left[8][8];
            double right[8][1];

            unsigned i;
            for (i = 0; i < 4; i++)
            {
                unsigned ix = i * 2;
                unsigned iy = ix + 1;

                left[ix][0]  =  1.0;
                left[ix][1]  =  src[ix];
                left[ix][2]  =  src[iy];
                left[ix][3]  =  0.0;
                left[ix][4]  =  0.0;
                left[ix][5]  =  0.0;
                left[ix][6]  = -src[ix] * dst[ix];
                left[ix][7]  = -src[iy] * dst[ix];
                right[ix][0] =  dst[ix];

                left[iy][0]  =  0.0;
                left[iy][1]  =  0.0;
                left[iy][2]  =  0.0;
                left[iy][3]  =  1.0;
                left[iy][4]  =  src[ix];
                left[iy][5]  =  src[iy];
                left[iy][6]  = -src[ix] * dst[iy];
                left[iy][7]  = -src[iy] * dst[iy];
                right[iy][0] =  dst[iy];
            }
            m_valid = simul_eq<8, 1>::solve(left, right, m_mtx);
        }


        //--------------------------------------------------------------------
        // Set the direct transformations, i.e., rectangle -> quadrangle
        void rect_to_quad(double x1, double y1, double x2, double y2, 
                          const double* quad)
        {
            double src[8];
            src[0] = src[6] = x1;
            src[2] = src[4] = x2;
            src[1] = src[3] = y1;
            src[5] = src[7] = y2;
            quad_to_quad(src, quad);
        }


        //--------------------------------------------------------------------
        // Set the reverse transformations, i.e., quadrangle -> rectangle
        void quad_to_rect(const double* quad, 
                          double x1, double y1, double x2, double y2)
        {
            double dst[8];
            dst[0] = dst[6] = x1;
            dst[2] = dst[4] = x2;
            dst[1] = dst[3] = y1;
            dst[5] = dst[7] = y2;
            quad_to_quad(quad, dst);
        }

        //--------------------------------------------------------------------
        // Check if the equations were solved successfully
        bool is_valid() const { return m_valid; }

        //--------------------------------------------------------------------
        // Transform a point (x, y)
        void transform(double* x, double* y) const
        {
            double tx = *x;
            double ty = *y;
            double d = 1.0 / (m_mtx[6][0] * tx + m_mtx[7][0] * ty + 1.0);
            *x = (m_mtx[0][0] + m_mtx[1][0] * tx + m_mtx[2][0] * ty) * d;
            *y = (m_mtx[3][0] + m_mtx[4][0] * tx + m_mtx[5][0] * ty) * d;
        }

    private:
        double m_mtx[8][1];
        bool   m_valid;
    };

}

#endif
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re: C++ 2D Perspective Transformations
От: McSeem2 США http://www.antigrain.com
Дата: 30.11.03 21:49
Оценка:
Ну и билинейные преобразования (agg_trans_bilinear.h)


//----------------------------------------------------------------------------
// Anti-Grain Geometry - Version 2.0 
// Copyright (C) 2002 Maxim Shemanarev (McSeem)
//
// Permission to copy, use, modify, sell and distribute this software 
// is granted provided this copyright notice appears in all copies. 
// This software is provided "as is" without express or implied
// warranty, and with no claim as to its suitability for any purpose.
//
//----------------------------------------------------------------------------
// Contact: mcseem@antigrain.com
//          mcseemagg@yahoo.com
//          http://www.antigrain.com
//----------------------------------------------------------------------------
//
// Bilinear 2D transformations
//
//----------------------------------------------------------------------------
#ifndef AGG_TRANS_BILINEAR_INCLUDED
#define AGG_TRANS_BILINEAR_INCLUDED

#include "agg_simul_eq.h"

namespace agg
{

    //========================================================================
    class trans_bilinear
    {
    public:
        //--------------------------------------------------------------------
        trans_bilinear() : m_valid(false) {}

        //--------------------------------------------------------------------
        // Arbitrary quadrangle transformations
        trans_bilinear(const double* src, const double* dst) 
        {
            quad_to_quad(src, dst);
        }


        //--------------------------------------------------------------------
        // Direct transformations 
        trans_bilinear(double x1, double y1, double x2, double y2, 
                       const double* quad)
        {
            rect_to_quad(x1, y1, x2, y2, quad);
        }


        //--------------------------------------------------------------------
        // Reverse transformations 
        trans_bilinear(const double* quad, 
                       double x1, double y1, double x2, double y2)
        {
            quad_to_rect(quad, x1, y1, x2, y2);
        }


        //--------------------------------------------------------------------
        // Set the transformations using two arbitrary quadrangles.
        void quad_to_quad(const double* src, const double* dst)
        {
            double left[4][4];
            double right[4][2];

            unsigned i;
            for(i = 0; i < 4; i++)
            {
                unsigned ix = i * 2;
                unsigned iy = ix + 1;
                left[i][0] = 1.0;
                left[i][1] = src[ix] * src[iy];
                left[i][2] = src[ix];
                left[i][3] = src[iy];

                right[i][0] = dst[ix];
                right[i][1] = dst[iy];
            }
            m_valid = simul_eq<4, 2>::solve(left, right, m_mtx);
        }


        //--------------------------------------------------------------------
        // Set the direct transformations, i.e., rectangle -> quadrangle
        void rect_to_quad(double x1, double y1, double x2, double y2, 
                          const double* quad)
        {
            double src[8];
            src[0] = src[6] = x1;
            src[2] = src[4] = x2;
            src[1] = src[3] = y1;
            src[5] = src[7] = y2;
            quad_to_quad(src, quad);
        }


        //--------------------------------------------------------------------
        // Set the reverse transformations, i.e., quadrangle -> rectangle
        void quad_to_rect(const double* quad, 
                          double x1, double y1, double x2, double y2)
        {
            double dst[8];
            dst[0] = dst[6] = x1;
            dst[2] = dst[4] = x2;
            dst[1] = dst[3] = y1;
            dst[5] = dst[7] = y2;
            quad_to_quad(quad, dst);
        }

        //--------------------------------------------------------------------
        // Check if the equations were solved successfully
        bool is_valid() const { return m_valid; }

        //--------------------------------------------------------------------
        // Transform a point (x, y)
        void transform(double* x, double* y) const
        {
            double tx = *x;
            double ty = *y;
            double xy = tx * ty;
            *x = m_mtx[0][0] + m_mtx[1][0] * xy + m_mtx[2][0] * tx + m_mtx[3][0] * ty;
            *y = m_mtx[0][1] + m_mtx[1][1] * xy + m_mtx[2][1] * tx + m_mtx[3][1] * ty;
        }

    private:
        double m_mtx[4][2];
        bool   m_valid;
    };

}

#endif
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re: C++ 2D Perspective Transformations
От: unprogrammer Россия  
Дата: 01.12.03 02:51
Оценка:
Здравствуйте, McSeem2, Вы писали:

MS>Наконец-то я имплементировал перспективные преобразования в 2D. Все, что есть готового, мне по тем или иным причинам не нравилось — либо очень сложно и много зависимостей (как в ImageMagic — там любой файл тащит за собой полбиблиотеки, хотя, конечно же, неисчерпаемый кладезь), либо тормозно и глючно.




А будет ли полноценный релиз AGG 2.X+ ?

Кстати либо в примере отсутствует векторный clipping(если он нужен растеризатору), либо растеризатор глючит.

Re[2]: C++ 2D Perspective Transformations
От: McSeem2 США http://www.antigrain.com
Дата: 01.12.03 03:37
Оценка:
Здравствуйте, unprogrammer, Вы писали:

U>А будет ли полноценный релиз AGG 2.X+ ?


Будет!

U>Кстати либо в примере отсутствует векторный clipping(если он нужен растеризатору), либо растеризатор глючит.


Это не растеризатор и не отсекатель. Все это есть и оно не глючит. Просто это все обусловлено сущностью преобразований — при таких "задвигах" там просто бесконечнсти получаются. Вот простой эллипс:
http://www.antigrain.com/perspective6.gif

А вот во что он может превратиться:
http://www.antigrain.com/perspective7.gif

Его 4 луча уходят в бесконечность и возвращаются с другой стороны — ну, теорию о замкнутом пространстве-времени слыхал?

Отслеживать такие вещи на уровне преобразований точек — это очень накладно. Гораздо проще ограничить геометрическую конфигурацию четырехугольника, но это надо делать где-то снаружи. Я этого просто не делаю, дабы не тормозить и не ограничивать прав и свобод граждан

http://www.antigrain.com/agg2.zip
или CVS:
http://sourceforge.net/cvs/?group_id=42020
Так же, список рассылки:
http://lists.sourceforge.net/lists/listinfo/vector-agg-general
Архив:
http://sourceforge.net/mailarchive/forum.php?forum=vector-agg-general

Пока вот, но все в процессе. Все это пока не вполне устаканено, то есть некоторые интерфейсы могут поменяться.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[3]: C++ 2D Perspective Transformations
От: Аноним  
Дата: 30.01.04 13:02
Оценка:
Строка для обновления ветки в RSDN@Home
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.