Края на контурах многоугольников не всегда правильные - PullRequest
6 голосов
/ 14 июня 2010

Я использую приведенный ниже алгоритм для генерации четырехугольников, которые затем визуализируются для создания контура, подобного этому

http://img810.imageshack.us/img810/8530/uhohz.png

Проблема, как видно наИзображение таково, что иногда линии слишком тонкие, когда они всегда должны быть одинаковой ширины.Мой алгоритм находит 4 вершины для первой, затем верхние 2 вершины следующих являются нижними 2 предыдущей.Это создает связанные линии, но, кажется, не всегда работает.Как я мог это исправить?

Это мой алгоритм:

 void OGLENGINEFUNCTIONS::GenerateLinePoly(const std::vector<std::vector<GLdouble>> &input,
                          std::vector<GLfloat> &output, int width)
 {
     output.clear();

     if(input.size() < 2)
     {
         return;
     }

     int temp;
     float dirlen;
     float perplen;
     POINTFLOAT start;
     POINTFLOAT end;
     POINTFLOAT dir;
     POINTFLOAT ndir;
     POINTFLOAT perp;
     POINTFLOAT nperp;

     POINTFLOAT perpoffset;
     POINTFLOAT diroffset;

     POINTFLOAT p0, p1, p2, p3;

     for(unsigned int i = 0; i < input.size() - 1; ++i)
     {

         start.x = static_cast<float>(input[i][0]);
         start.y = static_cast<float>(input[i][1]);

         end.x = static_cast<float>(input[i + 1][0]);
         end.y = static_cast<float>(input[i + 1][1]);

         dir.x = end.x - start.x;
         dir.y = end.y - start.y;

         dirlen = sqrt((dir.x * dir.x) + (dir.y * dir.y));

         ndir.x = static_cast<float>(dir.x * 1.0 / dirlen);
         ndir.y = static_cast<float>(dir.y * 1.0 / dirlen);

         perp.x = dir.y;
         perp.y = -dir.x;

         perplen = sqrt((perp.x * perp.x) + (perp.y * perp.y));

         nperp.x = static_cast<float>(perp.x * 1.0 / perplen);
         nperp.y = static_cast<float>(perp.y * 1.0 / perplen);

         perpoffset.x = static_cast<float>(nperp.x * width * 0.5);
         perpoffset.y = static_cast<float>(nperp.y * width * 0.5);

         diroffset.x = static_cast<float>(ndir.x * 0 * 0.5);
         diroffset.y = static_cast<float>(ndir.y * 0 * 0.5);

            // p0 = start + perpoffset - diroffset
            // p1 = start - perpoffset - diroffset
            // p2 = end + perpoffset + diroffset
            // p3 = end - perpoffset + diroffset 

         p0.x = start.x + perpoffset.x - diroffset.x;
         p0.y = start.y + perpoffset.y - diroffset.y;

         p1.x = start.x - perpoffset.x - diroffset.x;
         p1.y = start.y - perpoffset.y - diroffset.y;

         if(i > 0)
         {
             temp = (8 * (i - 1));
             p2.x = output[temp + 2];
             p2.y = output[temp + 3];
             p3.x = output[temp + 4];
             p3.y = output[temp + 5];

         }
         else
         {
             p2.x = end.x + perpoffset.x + diroffset.x;
             p2.y = end.y + perpoffset.y + diroffset.y;

             p3.x = end.x - perpoffset.x + diroffset.x;
             p3.y = end.y - perpoffset.y + diroffset.y;
         }



         output.push_back(p2.x);
         output.push_back(p2.y);
         output.push_back(p0.x);
         output.push_back(p0.y);
         output.push_back(p1.x);
         output.push_back(p1.y);
         output.push_back(p3.x);
         output.push_back(p3.y);

     }
 }

Редактировать:

 POINTFLOAT multiply(const POINTFLOAT &a, float b)
 {
     POINTFLOAT result;
     result.x = a.x * b;
     result.y = a.y * b;
     return result;
 }

 POINTFLOAT normalize(const POINTFLOAT &a)
 {
     return multiply(a, 1.0f / sqrt(a.x * a.x + a.y * a.y));
 }


 POINTFLOAT slerp2d( const POINTFLOAT v0, 
                     const POINTFLOAT v1, float t )
 {
     float dot = (v0.x * v1.x + v1.y * v1.y);
     if( dot < -1.0f ) dot = -1.0f;
     if( dot > 1.0f ) dot = 1.0f;

     float theta_0 = acos( dot );
     float theta = theta_0 * t;

     POINTFLOAT v2;
     v2.x = -v0.y;
     v2.y = v0.x;

     POINTFLOAT result;
     result.x = v0.x * cos(theta) + v2.x * sin(theta);
     result.y = v0.y * cos(theta) + v2.y * sin(theta);

     return result;
 }

 void OGLENGINEFUNCTIONS::GenerateLinePoly(const std::vector<std::vector<GLdouble> > &input,
                          std::vector<GLfloat> &output, int width)
 {
     output.clear();

     if(input.size() < 2)
     {
         return;
     }

     float w = width / 2.0f;

     //glBegin(GL_TRIANGLES);
     for( size_t i = 0; i < input.size()-1; ++i )
     {
         POINTFLOAT cur;
         cur.x = input[i][0];
         cur.y = input[i][1];


         POINTFLOAT nxt;
         nxt.x = input[i+1][0];
         nxt.y = input[i+1][1];

         POINTFLOAT b;
         b.x = nxt.x - cur.x;
         b.y = nxt.y - cur.y;

         b = normalize(b);



         POINTFLOAT b_perp;
         b_perp.x = -b.y;
         b_perp.y = b.x;


         POINTFLOAT p0;
         POINTFLOAT p1;
         POINTFLOAT p2;
         POINTFLOAT p3;

         p0.x = cur.x + b_perp.x * w;
         p0.y = cur.y + b_perp.y * w;

         p1.x = cur.x - b_perp.x * w;
         p1.y = cur.y - b_perp.y * w;

         p2.x = nxt.x + b_perp.x * w;
         p2.y = nxt.y + b_perp.y * w;

         p3.x = nxt.x - b_perp.x * w;
         p3.y = nxt.y - b_perp.y * w;

         output.push_back(p0.x);
         output.push_back(p0.y);
         output.push_back(p1.x);
         output.push_back(p1.y);
         output.push_back(p2.x);
         output.push_back(p2.y);

         output.push_back(p2.x);
         output.push_back(p2.y);
         output.push_back(p1.x);
         output.push_back(p1.y);
         output.push_back(p3.x);
         output.push_back(p3.y);



         // only do joins when we have a prv
         if( i == 0 ) continue;

         POINTFLOAT prv;
         prv.x = input[i-1][0];
         prv.y = input[i-1][1];

         POINTFLOAT a;
         a.x = prv.x - cur.x;
         a.y = prv.y - cur.y;

         a = normalize(a);

         POINTFLOAT a_perp;
         a_perp.x = a.y;
         a_perp.y = -a.x;

         float det = a.x * b.y - b.x * a.y;
         if( det > 0 )
         {
             a_perp.x = -a_perp.x;
             a_perp.y = -a_perp.y;

             b_perp.x = -b_perp.x;
             b_perp.y = -b_perp.y;
         }

         // TODO: do inner miter calculation

         // flip around normals and calculate round join points
         a_perp.x = -a_perp.x;
         a_perp.y = -a_perp.y;

         b_perp.x = -b_perp.x;
         b_perp.y = -b_perp.y;

         size_t num_pts = 4;

         std::vector< POINTFLOAT> round( 1 + num_pts + 1 );
         POINTFLOAT nc;
         nc.x = cur.x + (a_perp.x * w);
         nc.y = cur.y + (a_perp.y * w);

         round.front() = nc;

         nc.x = cur.x + (b_perp.x * w);
         nc.y = cur.y + (b_perp.y * w);

         round.back() = nc;

         for( size_t j = 1; j < num_pts+1; ++j )
         {
             float t = (float)j / (float)(num_pts + 1);
             if( det > 0 )
             {
                 POINTFLOAT nin;
                 nin = slerp2d( b_perp, a_perp, 1.0f-t );
                 nin.x *= w;
                 nin.y *= w;

                 nin.x += cur.x;
                 nin.y += cur.y;

                 round[j] = nin;
             }
             else
             {
                 POINTFLOAT nin;
                 nin = slerp2d( a_perp, b_perp, t );
                 nin.x *= w;
                 nin.y *= w;

                 nin.x += cur.x;
                 nin.y += cur.y;

                 round[j] = nin;
             }
         }

         for( size_t j = 0; j < round.size()-1; ++j )
         {

             output.push_back(cur.x);
             output.push_back(cur.y);

             if( det > 0 )
             {
                 output.push_back(round[j + 1].x);
                 output.push_back(round[j + 1].y);
                 output.push_back(round[j].x);
                 output.push_back(round[j].y);
             }
             else
             {

                 output.push_back(round[j].x);
                 output.push_back(round[j].y);

                 output.push_back(round[j + 1].x);
                 output.push_back(round[j + 1].y);
             }
         }
     }
 }

Ответы [ 6 ]

8 голосов
/ 17 июня 2010

Требуется Собственное , как написано, но основные операции должны легко отображаться на любой используемый вами векторный класс.

// v0 and v1 are normalized
// t can vary between 0 and 1
// http://number-none.com/product/Understanding%20Slerp,%20Then%20Not%20Using%20It/
Vector2f slerp2d( const Vector2f& v0, const Vector2f& v1, float t )
{
    float dot = v0.dot(v1);
    if( dot < -1.0f ) dot = -1.0f;
    if( dot > 1.0f ) dot = 1.0f;

    float theta_0 = acos( dot );
    float theta = theta_0 * t;

    Vector2f v2( -v0.y(), v0.x() );

    return ( v0*cos(theta) + v2*sin(theta) );
}


void glPolyline( const vector<Vector2f>& polyline, float width )
{
    if( polyline.size() < 2 ) return;
    float w = width / 2.0f;

    glBegin(GL_TRIANGLES);
    for( size_t i = 0; i < polyline.size()-1; ++i )
    {
        const Vector2f& cur = polyline[ i ];
        const Vector2f& nxt = polyline[i+1];

        Vector2f b = (nxt - cur).normalized();
        Vector2f b_perp( -b.y(), b.x() );

        Vector2f p0( cur + b_perp*w );
        Vector2f p1( cur - b_perp*w );
        Vector2f p2( nxt + b_perp*w );
        Vector2f p3( nxt - b_perp*w );

        // first triangle
        glVertex2fv( p0.data() );
        glVertex2fv( p1.data() );
        glVertex2fv( p2.data() );
        // second triangle
        glVertex2fv( p2.data() );
        glVertex2fv( p1.data() );
        glVertex2fv( p3.data() );

        // only do joins when we have a prv
        if( i == 0 ) continue;

        const Vector2f& prv = polyline[i-1];
        Vector2f a = (prv - cur).normalized();
        Vector2f a_perp( a.y(), -a.x() );

        float det = a.x()*b.y() - b.x()*a.y();
        if( det > 0 )
        {
            a_perp = -a_perp;
            b_perp = -b_perp;
        }

        // TODO: do inner miter calculation

        // flip around normals and calculate round join points
        a_perp = -a_perp;
        b_perp = -b_perp;

        size_t num_pts = 4;
        vector< Vector2f > round( 1 + num_pts + 1 );
        for( size_t j = 0; j <= num_pts+1; ++j )
        {
            float t = (float)j/(float)(num_pts+1);
            if( det > 0 )
                round[j] = cur + (slerp2d( b_perp, a_perp, 1.0f-t ) * w);
            else
                round[j] = cur + (slerp2d( a_perp, b_perp, t ) * w);
        }

        for( size_t j = 0; j < round.size()-1; ++j )
        {
            glVertex2fv( cur.data() );
            if( det > 0 )
            {
                glVertex2fv( round[j+1].data() );
                glVertex2fv( round[j+0].data() );
            }
            else
            {
                glVertex2fv( round[j+0].data() );
                glVertex2fv( round[j+1].data() );
            }
        }
    }
    glEnd();
}

РЕДАКТИРОВАТЬ: Скриншоты:

Wireframe

Filled

3 голосов
/ 15 июня 2010

Как насчет:

  1. Нарисуйте каждую линию до внутренней части угла
  2. Нарисуйте дополнительную линию в каждом углу, перпендикулярном углу угла

Примерно так:

альтернативный текст http://www.geekops.co.uk/photos/0000-00-02%20%28Forum%20images%29/CorrectAngleDrawing.png

Синий / красный представляют две линии, которые вы пытаетесь соединить.Пунктирный зеленый цвет - это то, что вы добавляете для сглаживания угла.На изображении выше показано, что содержимое будет обрезано очень немного для острых углов.Если это проблема, вы можете расширить две соединительные линии дальше наружу и провести дополнительную линию дальше.

[Редактировать] Я заметил недостаток в моем предложении.У вас есть несколько вогнутых участков, которые не будут работать вообще.Для этих случаев вы захотите сделать что-то вроде рисования скошенного края:

альтернативный текст http://www.geekops.co.uk/photos/0000-00-02%20%28Forum%20images%29/CorrectAngleDrawing2.png

[Edit2] Я сделал небольшую отладкуна код, который я разместил ранее.Следующее должно быть более полезным:

    // PolygonOutlineGen.cpp : A small program to calculate 4-point polygons 
// to surround an input polygon.

#include <vector>
#include <math.h>
#include <iostream>
#include <iomanip>

using namespace std;

// Describe some structures etc. so the code will compile without 
// requiring the GL libraries.
typedef double GLdouble;
typedef float GLfloat;
typedef struct POINTFLOAT
{
    float x;
    float y;
} POINTFLOAT;

// A function to generate two coordinates representing the start and end
// of a line perpendicular to start/end, offset by 'width' units.
void GenerateOffsetLineCoords(
    POINTFLOAT start, 
    POINTFLOAT end, 
    int width,
    POINTFLOAT& perpStart,
    POINTFLOAT& perpEnd)
{
    float dirlen;
    POINTFLOAT dir;
    POINTFLOAT ndir;
    POINTFLOAT nperp;
    POINTFLOAT perpoffset;

    // Work out the offset for a parallel line which is space outwards by 'width' units
    dir.x = end.x - start.x;
    dir.y = end.y - start.y;
    dirlen = sqrt((dir.x * dir.x) + (dir.y * dir.y));
    ndir.x = static_cast<float>(dir.x * 1.0 / dirlen);
    ndir.y = static_cast<float>(dir.y * 1.0 / dirlen);
    nperp.x = -ndir.y;
    nperp.y = ndir.x;
    perpoffset.x = static_cast<float>(nperp.x * width);
    perpoffset.y = static_cast<float>(nperp.y * width);

    // Calculate the offset coordinates for the new line
    perpStart.x = start.x + perpoffset.x;
    perpStart.y = start.y + perpoffset.y;
    perpEnd.x = end.x + perpoffset.x;
    perpEnd.y = end.y + perpoffset.y;
}

// Function to generate quads of coordinate pairs to surround the 'input'
// polygon.
void GenerateLinePoly(const std::vector<std::vector<GLdouble>> &input,
    std::vector<GLfloat> &output, int width)
{
    // Make sure we have something to produce an outline for and that it's not contaminated with previous results
    output.clear();
    if(input.size() < 2)
    {
        return;
    }

    // Storage for the pairs of lines which form sections of the outline
    POINTFLOAT line1_start;
    POINTFLOAT line1_end;
    POINTFLOAT line2_start;
    POINTFLOAT line2_end;

    // Storage for the outer edges of the quads we'll be generating
    POINTFLOAT line1offset_start;
    POINTFLOAT line1offset_end;
    POINTFLOAT line2offset_start;
    POINTFLOAT line2offset_end;

    // Storage for the line we'll use to make smooth joints between polygon sections.
    POINTFLOAT joininglineoffset_start;
    POINTFLOAT joininglineoffset_end;

    for(unsigned int i = 0; i < input.size() - 2; ++i)
    {
        // Grab the raw line input for the first line or if we've already done one, just re-use the last results
        if( i == 0 )
        {
            line1_start.x = static_cast<float>(input[i][0]);
            line1_start.y = static_cast<float>(input[i][1]);
            line1_end.x = static_cast<float>(input[i + 1][0]);
            line1_end.y = static_cast<float>(input[i + 1][1]);

            GenerateOffsetLineCoords(line1_start, line1_end, width, line1offset_start, line1offset_end);
        }
        else
        {
            line1_start = line2_start;
            line1offset_start = line2offset_start;
            line1_end = line2_end;
            line1offset_end = line2offset_end;
        }

        // Grab the second line and work out the coords of it's offset 
        line2_start.x = static_cast<float>(input[i+1][0]);
        line2_start.y = static_cast<float>(input[i+1][1]);
        line2_end.x = static_cast<float>(input[i+2][0]);
        line2_end.y = static_cast<float>(input[i+2][1]);
        GenerateOffsetLineCoords(line2_start, line2_end, width, line2offset_start, line2offset_end);

        // Grab the offset for the line which joins the open end
        GenerateOffsetLineCoords(line2offset_start, line1offset_end, width, joininglineoffset_start, joininglineoffset_end);

        // Push line 1 onto the output
        output.push_back(line1_start.x);
        output.push_back(line1_start.y);
        output.push_back(line1_end.x);
        output.push_back(line1_end.y);
        output.push_back(line1offset_end.x);
        output.push_back(line1offset_end.y);
        output.push_back(line1offset_start.x);
        output.push_back(line1offset_start.y);

        // Push the new section onto the output
        output.push_back(line1offset_end.x);
        output.push_back(line1offset_end.y);
        output.push_back(line2offset_start.x);
        output.push_back(line2offset_start.y);
        output.push_back(joininglineoffset_start.x);
        output.push_back(joininglineoffset_start.y);
        output.push_back(joininglineoffset_end.x);
        output.push_back(joininglineoffset_end.y);
    }

    // TODO: Push the remaining line 2 on.

    // TODO: Add one last joining piece between the end and the beginning.
}

int main(int argc, char* argv[])
{
    // Describe some input data
    std::vector<std::vector<GLdouble>> input;
    std::vector<GLdouble> val1; val1.push_back(010.0); val1.push_back(010.0); input.push_back(val1);
    std::vector<GLdouble> val2; val2.push_back(050.0); val2.push_back(100.0); input.push_back(val2);
    std::vector<GLdouble> val3; val3.push_back(100.0); val3.push_back(100.0); input.push_back(val3);
    std::vector<GLdouble> val4; val4.push_back(010.0); val4.push_back(010.0); input.push_back(val4);

    // Generate the quads required to outline the shape
    std::vector<GLfloat> output;
    GenerateLinePoly(input, output, 5);

    // Dump the output as pairs of coordinates, grouped into the quads they describe
    cout << setiosflags(ios::fixed) << setprecision(1);
    for(unsigned int i=0; i < output.size(); i++)
    {
       if( (i > 0) && ((i)%2==0) ) { cout << endl; }
       if( (i > 0) && ((i)%8==0) ) { cout << endl; }
       cout << setw(7) << output[i];
    }
    cout << endl;
    return 0;
}

.. который, насколько я вижу, работает для выпуклых многоугольников: -)

2 голосов
/ 17 июня 2010

Этот код отображает правильный SVG вместо неправильный .Это проще, чем решение genpfault, с преимуществом, заключающимся в том, что для рендеринга нужно меньше квадратов.

Каждое соединение здесь отображается так же, как на последнем рисунке Jon Cage .

1 голос
/ 14 июня 2010

Нельзя использовать векторы смещения из предыдущего сегмента на текущем сегменте - они перпендикулярны чему-то, что не имеет никакого отношения к текущему сегменту. Лучше всего использовать те же смещения, как это:

         p0.x = start.x + perpoffset.x;
         p0.y = start.y + perpoffset.y;

         p1.x = start.x - perpoffset.x;
         p1.y = start.y - perpoffset.y;

         p2.x = end.x + perpoffset.x;
         p2.y = end.y + perpoffset.y;

         p3.x = end.x - perpoffset.x;
         p3.y = end.y - perpoffset.y;

А затем поместите круг в каждую вершину, чтобы закруглить углы. Если раунд - это не то, что вам нужно, вам придется изменить значение ndir, которое вы добавляете к смещениям - это зависит от ОБА соединяющих сегментов в вершине, а не только в одном. Вам необходимо определить пересечение входящей и исходящей линий смещения. Начните с вышеизложенного и сделайте несколько увеличенных снимков с углами, такими как 90 или 120 градусов, чтобы почувствовать это. Извините, сейчас формулы не пригодны.

Наконец, вам не нужно нормализовать вектор преступности. То, как вы рассчитываете, в любом случае даст единичный вектор.

1 голос
/ 14 июня 2010

Вы меняете ориентацию между первым сегментом и остальными.Блок, в котором вы извлекаете предыдущие значения из выходного вектора, должен устанавливать точки p0 и p1, и вы должны каждый раз вычислять p2 и p3 на основе конечных точек.

, т.е. это должно быть:

     if(i == 0)
     {
         p0.x = start.x + perpoffset.x - diroffset.x;
         p0.y = start.y + perpoffset.y - diroffset.y;

         p1.x = start.x - perpoffset.x - diroffset.x;
         p1.y = start.y - perpoffset.y - diroffset.y;
     }
     else
     {
         temp = (8 * (i - 1));
         p0.x = output[temp + 0];
         p0.y = output[temp + 1];
         p1.x = output[temp + 6];
         p1.y = output[temp + 7];

     }

     p2.x = end.x + perpoffset.x + diroffset.x;
     p2.y = end.y + perpoffset.y + diroffset.y;

     p3.x = end.x - perpoffset.x + diroffset.x;
     p3.y = end.y - perpoffset.y + diroffset.y;
1 голос
/ 14 июня 2010

Ах, теперь я вижу. Это потому, что вы повторно используете свои старые вершины, которые не обязательно параллельны вашим новым.

Просто изучите ваш код на простом примере, где ваши входные точки резко поворачиваются на 90 градусов. Старые вершины будут параллельны dir, а новые будут перпендикулярны. Если у вас есть точки на линии, которые находятся достаточно близко друг к другу, то вы получите странное поведение, как вы видите на своей картинке.

Не существует "простого" решения для получения линий одинаковой ширины, но все выглядело бы лучше, если бы вы просто отображали линии по паре за раз (т.е. избавлялись от случая i > 0). Это даст вам некрасивые острые углы, но вы не получите тонких линий.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...