数学生成 sphere-shaped 六角网格

Mathematically producing sphere-shaped hexagonal grid

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

(Image Source)

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

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

我什至不知道如何为此存储网格位置。 3 个五边形之间的每个 "triagle section" 是否都有自己的一组二维坐标?

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

[完成重新编辑 18.10.2017]

几何存储在你身上。要么将其存储在某种网格中,要么即时生成。我更喜欢存储它。以 2 表的形式。一个保存所有顶点(无重复),另一个保存每个六角形的 6 个使用点索引和一些附加信息,如球形位置,以简化 post 处理。

现在如何生成这个:

  1. 创建六角三角形

    大小应该是球体的半径。不包括角 hexess,也跳过三角形的最后一行(在径向和轴向上,因此球体上相邻三角形之间有 1 个六边形间隙),因为在连接三角形段时会重叠。

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

    所以只需转换为极坐标 (radius,angle),中心三角形围绕 0 deg。然后将半径乘以 cos(angle)/cos(30);,这会将三角形转换为饼图。然后用比率 72/60 重新缩放角度。这将使我们的三角形可连接...

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

    只需旋转第一个三角形的点并存储为新三角形即可。

  4. 计算z

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

    然而,当我尝试它时(下例),六边形有点变形,因此深度和缩放比例需要一些调整。或post处理后者。

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

    简单地复制 points/hexes 并取消 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;
//---------------------------------------------------------------------------
// 
//---------------------------------------------------------------------------
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 地图,您需要使用 atan2x,y 的中心点位置。

此处预览:

仍然存在一些失真。它们是由于我们使用 5 个三角形在赤道处连接(因此保证连接)造成的。这意味着周长是 5*R 而不是 6.28*R。然而,这仍然可以通过现场模拟来改进。只需获取所有点并根据它们的距离添加回缩力并绑定到球体表面。 运行 模拟,当振荡低于阈值时,您将获得球体网格...

另一种选择是找出一些等式来重新映射网格点(类似于我对三角形到饼图的转换所做的),这样会有更好的结果。

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

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

  1. 创建六边形网格的三角形切口:固定三角形(我选择 (-0.5,0),(0.5,0),(0,sqrt(3)/2) )叠加一个具有所需分辨率的六角网格 n s.t。三角形角与六边形中心重合,请参见 n = 0,1,2,20 的示例:

  2. 计算 icosahedron 的角并定义它的 20 个三角形面(见下面的代码)。二十面体的角定义了五边形的中心,二十面体的面定义了映射的六边形网格的面片。 (二十面体给出了最好的 规则 将球体表面划分为三角形,即划分为全等等边三角形。其他此类划分可以从四面体或八面体导出;然后在角处三角形的一个将有三角形或正方形,resp。此外,更少和更大的三角形将使平面网格到曲面的任何映射中不可避免的失真更加明显。因此选择二十面体作为三角形面片的基础有助于最小化六边形的扭曲。)

  3. 将六边形网格的三角形切口映射到对应于 icosaeder 面的球形三角形:双 slerp based on barycentric coordinates 就可以了。下面是将分辨率为 n = 10 的六边形网格的三角形切口映射到一个球形三角形(由 icosaeder 的一个面定义)的示意图,以及将网格映射到覆盖整个球体(不同映射的不同颜色):

这里是 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)]

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

# 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)

你的形状是所谓的“戈德堡多面体”之一,也是 geodesic polyhedra

生成此(以及更多)的(相当优雅)算法可以简洁地编码在称为 Conway Polyhedron Notation.

的东西中

施工过程很容易一步步进行,您可以点击下面的图片进行实时预览。

  1. 您要找的多面体可以从二十面体生成 -- 用二十面体初始化网格。

  2. 我们对网格应用"Truncate"操作(康威符号t)(这个的spical映射是一个足球)。

  3. 我们应用 "Dual" 运算符(康威符号 d)。

  4. 我们再次应用“截断”操作。此时的配方是 tdtI(从右边读!)。你已经可以看到这是怎么回事了。

  5. 重复执行步骤 3 和 4,直到您满意为止。

例如,下面是 dtdtdtdtI 的网格。

这很容易实现。我建议使用一种数据结构,它可以轻松地遍历邻域,为您的网格提供顶点、边等,例如 winged-edge 或 half-edge 数据结构。您只需为要查找的形状实现截断和对偶运算符。