数学上产生球形六边形网格

Question

我正在尝试创建一个类似于此的形状,具有12个五边形的六边形,任意大小.

(图片来源)

唯一的问题是,我完全不知道生成它需要什么样的代码!

目标是能够在3D空间中获取一个点并将其转换为网格上的位置坐标,反之亦然,并获取网格位置并获取绘制网格的相关顶点.

我甚至不知道如何为此存储网格位置.3个五边形之间的每个"三部分"是否都有自己的2D坐标？

我很可能会使用C#,但我更感兴趣的是使用哪种算法以及它们如何工作的解释,而不是只给我一段代码的人.

Answer 1

首先对问题中的图像进行一些分析:由相邻五边形中心跨越的球面三角形似乎是等边的.当五个等边三角形在一个角落相遇并覆盖整个球体时,这只能是由二十面体引起的配置.所以有12个五边形和20个贴片的六角形网格的三角形切口映射到球体.

所以这是在球体上构造这样的六边形网格的一种方法:

1. 创建六角网格的三角形切口:固定三角形(I选择(-0.5,0),(0.5,0),(0,SQRT(3)/ 2))被叠加有期望的分辨率在六边形网格nST三角形拐角重合有六角形中心,请参阅以下示例n = 0,1,2,20:

2. 计算二十面体的角并定义它的20个三角形面(参见下面的代码).二十面体的角落定义了五边形的中心,二十面体的面部定义了映射的六边形网格的斑块.(二十面体将球体表面最精细的规则划分为三角形,即划分为等长的等边三角形.其他此类划分可以从四面体或八面体中导出;然后在三角形的角上,一个将具有三角形或正方形,此外,越少和越大的三角形将使平面网格在曲面上的任何映射中不可避免的失真更加明显.因此,选择二十面体作为三角形补丁的基础有助于最大限度地减少六边形的扭曲.)

3. 将六边形网格的三角形切口映射到与icosaeder面相对应的球形三角形:基于重心坐标的双重slerp就可以了.下面是六角形网格的三角形切口与分辨率在一个球形三角形(由icosaeder的一个面定义)上的映射图,以及将网格映射到覆盖整个球体的所有这些球形三角形的图示(不同的颜色)对于不同的映射):n = 10

这是用于生成二十面体的角(坐标)和三角形(点索引)的Python代码:

from math import sin,cos,acos,sqrt,pi
s,c = 2/sqrt(5),1/sqrt(5)
topPoints = [(0,0,1)] + [(s*cos(i*2*pi/5.), s*sin(i*2*pi/5.), c) for i in range(5)]
bottomPoints = [(-x,y,-z) for (x,y,z) in topPoints]
icoPoints = topPoints + bottomPoints
icoTriangs = [(0,i+1,(i+1)%5+1) for i in range(5)] +\
             [(6,i+7,(i+1)%5+7) for i in range(5)] +\
             [(i+1,(i+1)%5+1,(7-i)%5+7) for i in range(5)] +\
             [(i+1,(7-i)%5+7,(8-i)%5+7) for i in range(5)]

以下是使用双slerp将固定三角形(点)映射到球形三角形的Python代码:

# barycentric coords for triangle (-0.5,0),(0.5,0),(0,sqrt(3)/2)
def barycentricCoords(p):
  x,y = p
  # l3*sqrt(3)/2 = y
  l3 = y*2./sqrt(3.)
  # l1 + l2 + l3 = 1
  # 0.5*(l2 - l1) = x
  l2 = x + 0.5*(1 - l3)
  l1 = 1 - l2 - l3
  return l1,l2,l3

from math import atan2
def scalProd(p1,p2):
  return sum([p1[i]*p2[i] for i in range(len(p1))])
# uniform interpolation of arc defined by p0, p1 (around origin)
# t=0 -> p0, t=1 -> p1
def slerp(p0,p1,t):
  assert abs(scalProd(p0,p0) - scalProd(p1,p1)) < 1e-7
  ang0Cos = scalProd(p0,p1)/scalProd(p0,p0)
  ang0Sin = sqrt(1 - ang0Cos*ang0Cos)
  ang0 = atan2(ang0Sin,ang0Cos)
  l0 = sin((1-t)*ang0)
  l1 = sin(t    *ang0)
  return tuple([(l0*p0[i] + l1*p1[i])/ang0Sin for i in range(len(p0))])

# map 2D point p to spherical triangle s1,s2,s3 (3D vectors of equal length)
def mapGridpoint2Sphere(p,s1,s2,s3):
  l1,l2,l3 = barycentricCoords(p)
  if abs(l3-1) < 1e-10: return s3
  l2s = l2/(l1+l2)
  p12 = slerp(s1,s2,l2s)
  return slerp(p12,s3,l3)

Answer 2

The shape you have is one of so called "Goldberg polyhedra", is also a geodesic polyhedra.

The (rather elegant) algorithm to generate this (and many many more) can be succinctly encoded in something called a Conway Polyhedron Notation.

The construction is easy to follow step by step, you can click the images below to get a live preview.

1. The polyhedron you are looking for can be generated from an isosahedron -- Initialise a mesh with an isosahedron.

2. We apply a "Truncate" operation (Conway notation t) to the mesh (the sperical mapping of this one is a football).

3. We apply the "Dual" operator (Conway notation d).

4. We apply a "Truncate" operation again. At this point the recipe is tdtI (read from right!). You can already see where this is going.

5. Apply steps 3 & 4 repeatedly until you are satisfied.

For example below is the mesh for dtdtdtdtI.

This is quite easy to implement. I would suggest using a datastructure that makes it easy to traverse the neighbourhood give a vertex, edge etc. such as winged-edge or half-edge datastructures for your mesh. You only need to implement truncate and dual operators for the shape you are looking for.

Answer 3

[完全重新编辑18.10.2017]

几何存储在你身上.您可以将其存储在某种Mesh中,也可以在运行中生成它.我喜欢存放它.以2个表的形式.一个包含所有顶点(没有重复),另一个包含每个十六进制的使用点的6个索引,以及一些附加信息,如球形位置,以简化后期处理.

现在如何生成这个:

1. 创建十六进制三角

   大小应该是球体的半径.不包括角hexess并且还跳过三角形(在径向和轴向因此对球面邻居三角形之间1个十六进制间隙)的最后一行作为接合出三角形段时,将重叠.

2. 将60deg六角形三角形转换为72deg饼形

   所以简单地转换为极坐标coordiantes(radius,angle),中心三角形0 deg.然后乘以半径cos(angle)/cos(30);,将三角形转换为Pie.然后用比例重新缩放角度72/60.这将使我们的三角形可以连接......

3. 复制并旋转三角形以填充5段五边形

   轻松旋转第一个三角形的点并存储为新的三角形.

4. 计算 z

   基于半球形的半球形,您可以将2D地图中的距离转换为弧长,以尽可能地限制扭曲.

   然而,当我尝试它时(下面的示例)六边形有点失真,因此深度和缩放需要一些调整.或后期处理.

5. 复制半球形成一个球体

   只需复制点/六角和否定z轴(或者如果要保留缠绕,则旋转180度).

6. 添加赤道和所有缺失的五边形和六边形

   您应该使用相邻六边形的坐标,以便不再向网格添加失真和重叠.这里预览:

   

   蓝色是三角形.深蓝色是它的副本.红色是杆五边形.深绿色是赤道,浅绿色是三角形之间的连接线.在淡黄色附近失踪赤道六边形深橙色五边形.

这里是简单的C++ OpenGL示例(由#4中的链接答案构成):

//$$---- Form CPP ----
//---------------------------------------------------------------------------
#include <vcl.h>
#include <math.h>
#pragma hdrstop
#include "win_main.h"
#include "gl/OpenGL3D_double.cpp"
#include "PolyLine.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TMain *Main;
OpenGLscreen scr;
bool _redraw=true;
double animx=  0.0,danimx=0.0;
double animy=  0.0,danimy=0.0;
//---------------------------------------------------------------------------
PointTab     pnt;   // (x,y,z)

struct _hexagon
    {
    int ix[6];      // index of 6 points, last point duplicate for pentagon
    int a,b;        // spherical coordinate
    DWORD col;      // color

    // inline
    _hexagon()      {}
    _hexagon(_hexagon& a)   { *this=a; }
    ~_hexagon() {}
    _hexagon* operator = (const _hexagon *a) { *this=*a; return this; }
    //_hexagon* operator = (const _hexagon &a) { ...copy... return this; }
    };
List<_hexagon> hex;
//---------------------------------------------------------------------------
// https://stackoverflow.com/a/46787885/2521214
//---------------------------------------------------------------------------
void hex_sphere(int N,double R)
    {
    const double c=cos(60.0*deg);
    const double s=sin(60.0*deg);
    const double sy=       R/(N+N-2);
    const double sz=sy/s;
    const double sx=sz*c;
    const double sz2=0.5*sz;

    const int na=5*(N-2);
    const int nb=  N;
    const int b0=  N;
    double *q,p[3],ang,len,l,l0,ll;
    int i,j,n,a,b,ix;
    _hexagon h,*ph;

    hex.allocate(na*nb);
    hex.num=0;
    pnt.reset3D(N*N);
    b=0; a=0; ix=0;

    // generate triangle hex grid
    h.col=0x00804000;
    for (b=1;b<N-1;b++)                             // skip first line b=0
     for (a=1;a<b;a++)                              // skip first and last line
        {
        p[0]=double(a       )*(sx+sz);
        p[1]=double(b-(a>>1))*(sy*2.0);
        p[2]=0.0;
        if (int(a&1)!=0) p[1]-=sy;
        ix=pnt.add(p[0]+sz2+sx,p[1]   ,p[2]); h.ix[0]=ix; //  2 1
        ix=pnt.add(p[0]+sz2   ,p[1]+sy,p[2]); h.ix[1]=ix; // 3   0
        ix=pnt.add(p[0]-sz2   ,p[1]+sy,p[2]); h.ix[2]=ix; //  4 5
        ix=pnt.add(p[0]-sz2-sx,p[1]   ,p[2]); h.ix[3]=ix;
        ix=pnt.add(p[0]-sz2   ,p[1]-sy,p[2]); h.ix[4]=ix;
        ix=pnt.add(p[0]+sz2   ,p[1]-sy,p[2]); h.ix[5]=ix;
        h.a=a;
        h.b=N-1-b;
        hex.add(h);
        } n=hex.num; // remember number of hexs for the first triangle

    // distort points to match area
    for (ix=0;ix<pnt.nn;ix+=3)
        {
        // point pointer
        q=pnt.pnt.dat+ix;
        // convert to polar coordinates
        ang=atan2(q[1],q[0]);
        len=vector_len(q);
        // match area of pentagon (72deg) triangle as we got hexagon (60deg) triangle
        ang-=60.0*deg;  // rotate so center of generated triangle is angle 0deg
        while (ang>+60.0*deg) ang-=pi2;
        while (ang<-60.0*deg) ang+=pi2;
        len*=cos(ang)/cos(30.0*deg);        // scale radius so triangle converts to pie
        ang*=72.0/60.0;                     // scale up angle so rotated triangles merge
        // convert back to cartesian
        q[0]=len*cos(ang);
        q[1]=len*sin(ang);
        }

    // copy and rotate the triangle to cover pentagon
    h.col=0x00404000;
    for (ang=72.0*deg,a=1;a<5;a++,ang+=72.0*deg)
     for (ph=hex.dat,i=0;i<n;i++,ph++)
        {
        for (j=0;j<6;j++)
            {
            vector_copy(p,pnt.pnt.dat+ph->ix[j]);
            rotate2d(-ang,p[0],p[1]);
            h.ix[j]=pnt.add(p[0],p[1],p[2]);
            }
        h.a=ph->a+(a*(N-2));
        h.b=ph->b;
        hex.add(h);
        }

    // compute z
    for (q=pnt.pnt.dat,ix=0;ix<pnt.nn;ix+=pnt.dn,q+=pnt.dn)
        {
        q[2]=0.0;
        ang=vector_len(q)*0.5*pi/R;
        q[2]=R*cos(ang);
        ll=fabs(R*sin(ang)/sqrt((q[0]*q[0])+(q[1]*q[1])));
        q[0]*=ll;
        q[1]*=ll;
        }

    // copy and mirror the other half-sphere
    n=hex.num;
    for (ph=hex.dat,i=0;i<n;i++,ph++)
        {
        for (j=0;j<6;j++)
            {
            vector_copy(p,pnt.pnt.dat+ph->ix[j]);
            p[2]=-p[2];
            h.ix[j]=pnt.add(p[0],p[1],p[2]);
            }
        h.a= ph->a;
        h.b=-ph->b;
        hex.add(h);
        }

    // create index search table
    int i0,i1,j0,j1,a0,a1,ii[5];
    int **ab=new int*[na];
    for (a=0;a<na;a++)
        {
        ab[a]=new int[nb+nb+1];
        for (b=-nb;b<=nb;b++) ab[a][b0+b]=-1;
        }
    n=hex.num;
    for (ph=hex.dat,i=0;i<n;i++,ph++) ab[ph->a][b0+ph->b]=i;

    // add join ring
    h.col=0x00408000;
    for (a=0;a<na;a++)
        {
        h.a=a;
        h.b=0;
        a0=a;
        a1=a+1; if (a1>=na) a1-=na;
        i0=ab[a0][b0+1];
        i1=ab[a1][b0+1];
        j0=ab[a0][b0-1];
        j1=ab[a1][b0-1];
        if ((i0>=0)&&(i1>=0))
         if ((j0>=0)&&(j1>=0))
            {
            h.ix[0]=hex[i1].ix[1];
            h.ix[1]=hex[i0].ix[0];
            h.ix[2]=hex[i0].ix[1];
            h.ix[3]=hex[j0].ix[1];
            h.ix[4]=hex[j0].ix[0];
            h.ix[5]=hex[j1].ix[1];
            hex.add(h);
            ab[h.a][b0+h.b]=hex.num-1;
            }
        }

    // add 2x5 join lines
    h.col=0x00008040;
    for (a=0;a<na;a+=N-2)
     for (b=1;b<N-3;b++)
        {
        // +b hemisphere
        h.a= a;
        h.b=+b;
        a0=a-b; if (a0<  0) a0+=na; i0=ab[a0][b0+b+0];
        a0--;   if (a0<  0) a0+=na; i1=ab[a0][b0+b+1];
        a1=a+1; if (a1>=na) a1-=na; j0=ab[a1][b0+b+0];
                                    j1=ab[a1][b0+b+1];
        if ((i0>=0)&&(i1>=0))
         if ((j0>=0)&&(j1>=0))
            {
            h.ix[0]=hex[i0].ix[5];
            h.ix[1]=hex[i0].ix[4];
            h.ix[2]=hex[i1].ix[5];
            h.ix[3]=hex[j1].ix[3];
            h.ix[4]=hex[j0].ix[4];
            h.ix[5]=hex[j0].ix[3];
            hex.add(h);
            }
        // -b hemisphere
        h.a= a;
        h.b=-b;
        a0=a-b; if (a0<  0) a0+=na; i0=ab[a0][b0-b+0];
        a0--;   if (a0<  0) a0+=na; i1=ab[a0][b0-b-1];
        a1=a+1; if (a1>=na) a1-=na; j0=ab[a1][b0-b+0];
                                    j1=ab[a1][b0-b-1];
        if ((i0>=0)&&(i1>=0))
         if ((j0>=0)&&(j1>=0))
            {
            h.ix[0]=hex[i0].ix[5];
            h.ix[1]=hex[i0].ix[4];
            h.ix[2]=hex[i1].ix[5];
            h.ix[3]=hex[j1].ix[3];
            h.ix[4]=hex[j0].ix[4];
            h.ix[5]=hex[j0].ix[3];
            hex.add(h);
            }
        }

    // add pentagons at poles
    _hexagon h0,h1;
    h0.col=0x00000080;
    h0.a=0; h0.b=N-1; h1=h0; h1.b=-h1.b;
    p[2]=sqrt((R*R)-(sz*sz));
    for (ang=0.0,a=0;a<5;a++,ang+=72.0*deg)
        {
        p[0]=2.0*sz*cos(ang);
        p[1]=2.0*sz*sin(ang);
        h0.ix[a]=pnt.add(p[0],p[1],+p[2]);
        h1.ix[a]=pnt.add(p[0],p[1],-p[2]);
        }
    h0.ix[5]=h0.ix[4]; hex.add(h0);
    h1.ix[5]=h1.ix[4]; hex.add(h1);

    // add 5 missing hexagons at poles
    h.col=0x00600060;
    for (ph=&h0,b=N-3,h.b=N-2,i=0;i<2;i++,b=-b,ph=&h1,h.b=-h.b)
        {
        a =  1; if (a>=na) a-=na; ii[0]=ab[a][b0+b];
        a+=N-2; if (a>=na) a-=na; ii[1]=ab[a][b0+b];
        a+=N-2; if (a>=na) a-=na; ii[2]=ab[a][b0+b];
        a+=N-2; if (a>=na) a-=na; ii[3]=ab[a][b0+b];
        a+=N-2; if (a>=na) a-=na; ii[4]=ab[a][b0+b];
        for (j=0;j<5;j++)
            {
            h.a=((4+j)%5)*(N-2)+1;
            h.ix[0]=ph->ix[ (5-j)%5 ];
            h.ix[1]=ph->ix[ (6-j)%5 ];
            h.ix[2]=hex[ii[(j+4)%5]].ix[4];
            h.ix[3]=hex[ii[(j+4)%5]].ix[5];
            h.ix[4]=hex[ii[ j     ]].ix[3];
            h.ix[5]=hex[ii[ j     ]].ix[4];
            hex.add(h);
            }
        }

    // add 2*5 pentagons and 2*5 missing hexagons at equator
    h0.a=0; h0.b=N-1; h1=h0; h1.b=-h1.b;
    for (ang=36.0*deg,a=0;a<na;a+=N-2,ang-=72.0*deg)
        {
        p[0]=R*cos(ang);
        p[1]=R*sin(ang);
        p[2]=sz;
        i0=pnt.add(p[0],p[1],+p[2]);
        i1=pnt.add(p[0],p[1],-p[2]);
        a0=a-1;if (a0<  0) a0+=na;
        a1=a+1;if (a1>=na) a1-=na;
        ii[0]=ab[a0][b0-1]; ii[2]=ab[a1][b0-1];
        ii[1]=ab[a0][b0+1]; ii[3]=ab[a1][b0+1];
        // hexagons
        h.col=0x00008080;
        h.a=a; h.b=0;
        h.ix[0]=hex[ii[0]].ix[0];
        h.ix[1]=hex[ii[0]].ix[1];
        h.ix[2]=hex[ii[1]].ix[1];
        h.ix[3]=hex[ii[1]].ix[0];
        h.ix[4]=i0;
        h.ix[5]=i1;
        hex.add(h);
        h.a=a; h.b=0;
        h.ix[0]=hex[ii[2]].ix[2];
        h.ix[1]=hex[ii[2]].ix[1];
        h.ix[2]=hex[ii[3]].ix[1];
        h.ix[3]=hex[ii[3]].ix[2];
        h.ix[4]=i0;
        h.ix[5]=i1;
        hex.add(h);
        // pentagons
        h.col=0x000040A0;
        h.a=a; h.b=0;
        h.ix[0]=hex[ii[0]].ix[0];
        h.ix[1]=hex[ii[0]].ix[5];
        h.ix[2]=hex[ii[2]].ix[3];
        h.ix[3]=hex[ii[2]].ix[2];
        h.ix[4]=i1;
        h.ix[5]=i1;
        hex.add(h);
        h.a=a; h.b=0;
        h.ix[0]=hex[ii[1]].ix[0];
        h.ix[1]=hex[ii[1]].ix[5];
        h.ix[2]=hex[ii[3]].ix[3];
        h.ix[3]=hex[ii[3]].ix[2];
        h.ix[4]=i0;
        h.ix[5]=i0;
        hex.add(h);
        }

    // release index search table
    for (a=0;a<na;a++) delete[] ab[a];
    delete[] ab;
    }
//---------------------------------------------------------------------------
void hex_draw(GLuint style)     // draw hex
    {
    int i,j;
    _hexagon *h;
    for (h=hex.dat,i=0;i<hex.num;i++,h++)
        {
        if (style==GL_POLYGON) glColor4ubv((BYTE*)&h->col);
        glBegin(style);
        for (j=0;j<6;j++) glVertex3dv(pnt.pnt.dat+h->ix[j]);
        glEnd();
        }
    if (0)
    if (style==GL_POLYGON)
        {
        scr.text_init_pixel(0.1,-0.2);
        glColor3f(1.0,1.0,1.0);
        for (h=hex.dat,i=0;i<hex.num;i++,h++)
         if (abs(h->b)<2)
            {
            double p[3];
            vector_ld(p,0.0,0.0,0.0);
            for (j=0;j<6;j++)
             vector_add(p,p,pnt.pnt.dat+h->ix[j]);
            vector_mul(p,p,1.0/6.0);
            scr.text(p[0],p[1],p[2],AnsiString().sprintf("%i,%i",h->a,h->b));
            }
        scr.text_exit_pixel();
        }
    }
//---------------------------------------------------------------------------
void TMain::draw()
    {
    scr.cls();
    int x,y;

    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
    glTranslatef(0.0,0.0,-5.0);
    glRotated(animx,1.0,0.0,0.0);
    glRotated(animy,0.0,1.0,0.0);

    hex_draw(GL_POLYGON);

    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
    glTranslatef(0.0,0.0,-5.0+0.01);
    glRotated(animx,1.0,0.0,0.0);
    glRotated(animy,0.0,1.0,0.0);

    glColor3f(1.0,1.0,1.0);
    glLineWidth(2);
    hex_draw(GL_LINE_LOOP);
    glCirclexy(0.0,0.0,0.0,1.5);
    glLineWidth(1);

    scr.exe();
    scr.rfs();
    }
//---------------------------------------------------------------------------
__fastcall TMain::TMain(TComponent* Owner) : TForm(Owner)
    {
    scr.init(this);
    hex_sphere(10,1.5);
    _redraw=true;
    }
//---------------------------------------------------------------------------
void __fastcall TMain::FormDestroy(TObject *Sender)
    {
    scr.exit();
    }
//---------------------------------------------------------------------------
void __fastcall TMain::FormPaint(TObject *Sender)
    {
    _redraw=true;
    }
//---------------------------------------------------------------------------
void __fastcall TMain::FormResize(TObject *Sender)
    {
    scr.resize();
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluPerspective(60,float(scr.xs)/float(scr.ys),0.1,100.0);
    _redraw=true;
    }
//-----------------------------------------------------------------------
void __fastcall TMain::Timer1Timer(TObject *Sender)
    {
    animx+=danimx; if (animx>=360.0) animx-=360.0; _redraw=true;
    animy+=danimy; if (animy>=360.0) animy-=360.0; _redraw=true;
    if (_redraw) { draw(); _redraw=false; }
    }
//---------------------------------------------------------------------------
void __fastcall TMain::FormKeyDown(TObject *Sender, WORD &Key, TShiftState Shift)
    {
    Caption=Key;
    if (Key==40){ animx+=2.0; _redraw=true; }
    if (Key==38){ animx-=2.0; _redraw=true; }
    if (Key==39){ animy+=2.0; _redraw=true; }
    if (Key==37){ animy-=2.0; _redraw=true; }
    }
//---------------------------------------------------------------------------

我知道这是一个索引混乱,也不能保证缠绕规则,因为我懒得做统一的索引.谨防a每个十六进制的指标是不是线性的,如果你想使用它们映射到2D地图,你将需要用它来重新计算atan2在x,y其中心点位置.

这里预览:

仍然存在一些扭曲.它们是由于我们使用5个三角形在赤道连接(因此保证了连接).这意味着圆周5*R代替6.28*R.然而,通过现场模拟仍然可以改善这一点.只需取出所有点并根据它们的距离添加回缩力并绑定到球体表面.运行模拟,当振荡低于阈值时,你得到球形网格......

另一种选择是找出一些方程式来重新映射网格点(类似于我为三角形到饼形转换所做的那样),它会产生更好的结果.