如何在顶部 2D 小地图上显示用 3D 透视渲染的平面世界的可见部分?

2021-12-19 00:00:00 opengl math c++ perspective

序言

这个问答是对以下内容的重制:

  • 如何将透视截头体(地图/平面的可见部分)映射到小地图上的红色多边形形状?

    为了更通用,假设这是输入:

    • 平面 (Z=0.0) 定义为起点 p0 和两个基向量 du,dv 映射二维地图数组到 3D ...
    • ModelView 矩阵和 Perspective 矩阵使用

    和想要的输出:

    • 4 点多边形(在小地图上)表示外平面的可见部分

    限制(或多或少符合原始问题):

    • 使用C++
    • 旧式 OpenGL (GL,GLU)
    • 没有用于矢量/矩阵数学的第 3 方库

    解决方案

    所以我们想要的是获得我们的平面 (Z=0.0) 和相机截头体之间的 4 个交点.因此,我们的想法是从相机焦点投射 4 条光线(每个平截头体边缘一条),然后简单地计算光线/平面相交.由于平面是Z=0.0,交点也有Z=0.0,所以交点很容易计算.

    1. 为每个角/边投射光线

      从相机焦点到屏幕角落(在屏幕空间中)

      并将其转换为世界全局坐标(通过恢复透视并使用逆模型视图矩阵,稍后将对其进行描述).射线应该是形式:

      p(t) = p + dp*t

      其中p是焦点,dp是方向向量(不需要归一化)

    2. 计算与XY平面的交点(Z=0.0)

      作为 z=0.0 那么:

      0 = p.z + dp.z*tt = -p.z/dp.z

      所以我们可以直接计算交点.

    3. 将 3D 交叉点转换为地图内的 u,v

      对于那个简单的点积就足够了.所以如果 p 是我们的交点,那么:

      u = dot(p-p0,du)v = 点(p-p0,dv)

      其中 u,v 是我们的 2D 地图数组或小地图中的坐标.如果您的 u,v 是轴对齐的,那么您可以直接使用 (px-p0.x,py-p0.y) 而无需任何点积

    如何将p点从相机坐标转换为全局世界坐标:

    1. 还原视角

      首先获取透视矩阵参数

      double per[16],zNear,zFar,fx,fy;glGetDoublev(GL_PROJECTION_MATRIX,per);zFar =0.5*per[14]*(1.0-((per[10]-1.0)/(per[10]+1.0)));zNear=zFar*(per[10]+1.0)/(per[10]-1.0);fx=per[0];fy=per[5];

      这将为您提供近平面和远平面的截锥体以及 x、y 轴的缩放比例.现在反转透视只是像这样反转透视鸿沟:

      p[1]*=(-p[2]/fy);//应用逆透视p[0]*=(-p[2]/fx);

      znearzfar 是投射光线所必需的.有关更多信息,请参阅:

      • 如您所见,为此我们只需要矩阵*向量乘法和伪逆矩阵函数(所有其他函数,如 dot,+,- 都非常简单,并且直接编码为内联代码)并且两者都是简单到可以直接在代码中实现它,因此不需要 GLM 或类似的库.

        我也懒得把 4 点多边形剪裁成小地图大小,所以我改用了 glViewport,它帮我做到了.

        这里是Win32 BDS2006 VCL/C++/OpenGL1.0 Demo:

        • 演示源+二进制

        只需选择慢速下载并输入图片中的验证码.除了 GL,GLU 之外,它不使用任何第 3 方库.相机是静态的,所以只需根据自己的喜好添加键盘/鼠标事件.如果您想将其移植到您的环境中,只需模仿事件行为并忽略 VCL 内容.

        OpenGL init 基于此完成:

        • C++ 中简单完整的 GL+VAO/VBO+GLSL+shaders 示例

        我刚刚删除了 GLEW、GLSL 和 VAO 的内容.

        Prologue

        This Q&A is a remake of:

        • How to highlight 3D perspective camera view (frustrum) on topside 2D minimap?

        which was closed (and failed first reopening cycle) due to lack of info and no response of the original author. However I think this is an interesting question though so I decided to Ask&Answer this myself (this time with all the needed specs).

        Question

        Let assume our world is a uniform rectangular square grid (represented by 2D array of tiles) mapped on a plane (let say plane XY (Z=0.0) for simplicity) and is rendered with perspective projection. like this:

        How to map the perspective frustrum (visible part of the map/plane) to the red colored polygonal shape on the minimap ?

        To be more universal let assume this as input:

        • plane (Z=0.0) defined as start point p0 and two basis vectors du,dv which maps the 2D map array of tiles to 3D ...
        • ModelView matrix and Perspective matrix used

        And wanted output:

        • 4 point polygon (on minimap) representing the visible part of out plane

        Limitations (to more or less match the original question):

        • use C++
        • old style OpenGL (GL,GLU)
        • no 3th party lib for vector/matrix math

        解决方案

        So what we want is to obtain the 4 intersection points between our plane (Z=0.0) and camera frustrum. So the idea is to cast 4 rays (one for each edge of frustrum) from the camera focal point and simply compute the ray/plane intersection. As the plane is Z=0.0 the intersection point has Z=0.0 too so the intersection is quite easy to compute.

        1. Cast ray for each corner/edge

          from camera focal point to screen corner (in screen space)

          and convert it to world global coordinates (by reverting perspective and using inverse modelview matrix it is described later). The ray should be in form:

          p(t) = p + dp*t
          

          where p is the focal point and dp is direction vector (does not need to be normalized)

        2. compute the intersection with XY plane (Z=0.0)

          As the z=0.0 then:

          0 = p.z + dp.z*t
          t = -p.z/dp.z
          

          so we can compute the intersection point directly.

        3. convert 3D intersection points to u,v inside map

          for that simple dot product is enough. So if p is our intersection point then:

          u = dot(p-p0,du)
          v = dot(p-p0,dv)
          

          where u,v are coordinates in our 2D map array or minimap. In case your u,v are axis aligned then you can use directly (p.x-p0.x,p.y-p0.y) without any dot product

        How to convert point p from camera coordinates to global world coordinates:

        1. revert perspective

          first obtain perspective matrix parameters

          double per[16],zNear,zFar,fx,fy;
          glGetDoublev(GL_PROJECTION_MATRIX,per);
          zFar =0.5*per[14]*(1.0-((per[10]-1.0)/(per[10]+1.0)));
          zNear=zFar*(per[10]+1.0)/(per[10]-1.0);
          fx=per[0];
          fy=per[5];
          

          This will give you the frustrums near and far planes and scaling for x,y axises. Now reverting perspective is simply inverting the perspective divide like this:

          p[1]*=(-p[2]/fy);                   // apply inverse of perspective
          p[0]*=(-p[2]/fx);
          

          The znear and zfar are needed for casting the rays. For more info see:

          • depth buffer got by glReadPixels is always 1
        2. global world coordinates

          simply use inverse of ModelView matrix on our p. So first obtain the matrix:

          double cam[16];
          glGetDoublev(GL_MODELVIEW_MATRIX,cam);
          

          As inverse you can use my matrix_inv so now the final step is:

          p = Inverse(cam)*p;
          

          but do not forget that p must be homogenuous so (x,y,z,1) for points and (x,y,z,0) for vectors.

        Look here if you lack the background knowledge or need vector/matrix math:

        • Understanding 4x4 homogenous transform matrices

        Here Small C++ example of this:

        //---------------------------------------------------------------------------
        void matrix_mul_vector(double *c,double *a,double *b)
            {
            double q[3];
            q[0]=(a[ 0]*b[0])+(a[ 4]*b[1])+(a[ 8]*b[2])+(a[12]);
            q[1]=(a[ 1]*b[0])+(a[ 5]*b[1])+(a[ 9]*b[2])+(a[13]);
            q[2]=(a[ 2]*b[0])+(a[ 6]*b[1])+(a[10]*b[2])+(a[14]);
            for(int i=0;i<3;i++) c[i]=q[i];
            }
        //---------------------------------------------------------------------------
        void  matrix_inv(double *a,double *b) // a[16] = Inverse(b[16])
            {
            double x,y,z;
            // transpose of rotation matrix
            a[ 0]=b[ 0];
            a[ 5]=b[ 5];
            a[10]=b[10];
            x=b[1]; a[1]=b[4]; a[4]=x;
            x=b[2]; a[2]=b[8]; a[8]=x;
            x=b[6]; a[6]=b[9]; a[9]=x;
            // copy projection part
            a[ 3]=b[ 3];
            a[ 7]=b[ 7];
            a[11]=b[11];
            a[15]=b[15];
            // convert origin: new_pos = - new_rotation_matrix * old_pos
            x=(a[ 0]*b[12])+(a[ 4]*b[13])+(a[ 8]*b[14]);
            y=(a[ 1]*b[12])+(a[ 5]*b[13])+(a[ 9]*b[14]);
            z=(a[ 2]*b[12])+(a[ 6]*b[13])+(a[10]*b[14]);
            a[12]=-x;
            a[13]=-y;
            a[14]=-z;
            }
        //---------------------------------------------------------------------------
        void draw_map()
            {
            int i,j;
            double u,v,p[3],dp[3];
        
            // here 3D view must be already set (modelview,projection)
            glDisable(GL_CULL_FACE);
        
            // [draw 3D map]
            const int n=30;                 // map size
            double p0[3]={0.0,0.0,0.0};     // map start point
            double du[3]={1.0,0.0,0.0};     // map u step (size of grid = 1.0 )
            double dv[3]={0.0,1.0,0.0};     // map v step (size of grid = 1.0 )
            glColor3f(0.5,0.7,1.0);
            glBegin(GL_LINES);
            for (j=0;j<=n;j++)
                {
                for (i=0;i<3;i++) p[i]=p0[i]+(double(j)*du[i])+(double(0)*dv[i]); glVertex3dv(p);
                for (i=0;i<3;i++) p[i]=p0[i]+(double(j)*du[i])+(double(n)*dv[i]); glVertex3dv(p);
                for (i=0;i<3;i++) p[i]=p0[i]+(double(0)*du[i])+(double(j)*dv[i]); glVertex3dv(p);
                for (i=0;i<3;i++) p[i]=p0[i]+(double(n)*du[i])+(double(j)*dv[i]); glVertex3dv(p);
                }
            glEnd();
        
            // [compute trapeze points]
            double cam[16],per[16],pt[4][3],zNear,zFar,fx,fy;
            glGetDoublev(GL_PROJECTION_MATRIX,per); // obtain matrices
            glGetDoublev(GL_MODELVIEW_MATRIX,cam);
            matrix_inv(cam,cam);
            zFar =0.5*per[14]*(1.0-((per[10]-1.0)/(per[10]+1.0)));
            zNear=zFar*(per[10]+1.0)/(per[10]-1.0);
            fx=per[0];
            fy=per[5];
            for (j=0;j<4;j++)                       // 4 corners
                {
                for (i=0;i<3;i++) dp[i]=0.0;        // cast ray from camera focus dp
                if (j==0) { p[0]=-1.0; p[1]=-1.0; } // to screen corner p
                if (j==1) { p[0]=-1.0; p[1]=+1.0; }
                if (j==2) { p[0]=+1.0; p[1]=+1.0; }
                if (j==3) { p[0]=+1.0; p[1]=-1.0; }
                p[2]=zNear;                         // start position at screen plane
                p[1]*=(-p[2]/fy);                   // apply inverse of perspective
                p[0]*=(-p[2]/fx);
                // transform to worlds global coordinates
                matrix_mul_vector( p,cam, p);
                matrix_mul_vector(dp,cam,dp);
                // compute intersection of ray and XY plane (z=0) as pt[j] (i exploited the fact that the intersection have z=0.0 for arbitrary plane it would be a bit more complicated)
                for (i=0;i<3;i++) dp[i]=p[i]-dp[i];
                u=p[2]/dp[2];
                if (u<0.0) u=(p[2]-zFar)/dp[2];     // no intersection means "infinite" visibility
                for (i=0;i<3;i++) pt[j][i]=p[i]-(u*dp[i]);
                u=0.0;
                }
        
            // [draw 2D minimap]
            GLint vp0[4];
            GLint vp1[4]={10,10,150,150};           // minimap position and size ppixels[
            double q0[2]={-1.0,-1.0 };              // minimap start point
            double eu[2]={2.0/double(n),0.0};       // minimap u step
            double ev[2]={0.0,2.0/double(n)};       // minimap v step
        
            // set 2D view for minimap
            glDisable(GL_DEPTH_TEST);
            glMatrixMode(GL_PROJECTION);
            glPushMatrix();
            glLoadIdentity();
            glMatrixMode(GL_MODELVIEW);
            glPushMatrix();
            glLoadIdentity();
            glGetIntegerv(GL_VIEWPORT,vp0);
            glViewport(vp1[0],vp1[1],vp1[2],vp1[3]);
        
            glColor3f(0.0,0.0,0.0);                 // clear background
            glBegin(GL_QUADS);
            for (i=0;i<2;i++) p[i]=q0[i]+(double(0)*eu[i])+(double(0)*ev[i]); glVertex2dv(p);
            for (i=0;i<2;i++) p[i]=q0[i]+(double(n)*eu[i])+(double(0)*ev[i]); glVertex2dv(p);
            for (i=0;i<2;i++) p[i]=q0[i]+(double(n)*eu[i])+(double(n)*ev[i]); glVertex2dv(p);
            for (i=0;i<2;i++) p[i]=q0[i]+(double(0)*eu[i])+(double(n)*ev[i]); glVertex2dv(p);
            glEnd();
        
            glColor3f(0.15,0.15,0.15);              // grid
            glBegin(GL_LINES);
            for (j=0;j<=n;j++)
                {
                for (i=0;i<2;i++) p[i]=q0[i]+(double(j)*eu[i])+(double(0)*ev[i]); glVertex2dv(p);
                for (i=0;i<2;i++) p[i]=q0[i]+(double(j)*eu[i])+(double(n)*ev[i]); glVertex2dv(p);
                for (i=0;i<2;i++) p[i]=q0[i]+(double(0)*eu[i])+(double(j)*ev[i]); glVertex2dv(p);
                for (i=0;i<2;i++) p[i]=q0[i]+(double(n)*eu[i])+(double(j)*ev[i]); glVertex2dv(p);
                }
            glEnd();
        
            glColor3f(0.5,0.5,0.5);                 // border of minimap
            glLineWidth(2.0);
            glBegin(GL_LINE_LOOP);
            for (i=0;i<2;i++) p[i]=q0[i]+(double(0)*eu[i])+(double(0)*ev[i]); glVertex2dv(p);
            for (i=0;i<2;i++) p[i]=q0[i]+(double(n)*eu[i])+(double(0)*ev[i]); glVertex2dv(p);
            for (i=0;i<2;i++) p[i]=q0[i]+(double(n)*eu[i])+(double(n)*ev[i]); glVertex2dv(p);
            for (i=0;i<2;i++) p[i]=q0[i]+(double(0)*eu[i])+(double(n)*ev[i]); glVertex2dv(p);
            glEnd();
            glLineWidth(1.0);
        
            // 2D minimap render of the pt[]
            glColor3f(0.7,0.1,0.1);                 // trapeze
            glBegin(GL_LINE_LOOP);
            for (j=0;j<4;j++)
                {
                // get u,v from pt[j]
                for (i=0;i<3;i++) p[i]=pt[j][i]-p0[i];
                for (u=0.0,i=0;i<3;i++) u+=p[i]*du[i];
                for (v=0.0,i=0;i<3;i++) v+=p[i]*dv[i];
                // convert to 2D position and render
                for (i=0;i<2;i++) p[i]=q0[i]+(u*eu[i])+(v*ev[i]); glVertex2dv(p);
                }
            glEnd();
        
            // restore 3D view
            glMatrixMode(GL_MODELVIEW);
            glPopMatrix();
            glMatrixMode(GL_PROJECTION);
            glPopMatrix();
            glViewport(vp0[0],vp0[1],vp0[2],vp0[3]);
            glEnable(GL_DEPTH_TEST);
            }
        //---------------------------------------------------------------------------
        

        And preview:

        As you can see we need just matrix*vector multiplication and pseudo inverse matrix functions for this (all others like dot,+,- are really simple and directly encoded as inline code) and both are simple enough to directly implement it in code so no need for GLM or similar lib.

        Also I was too lazy to clip the 4 point polygon to minimap size so instead I used glViewport which did it for me.

        Here Win32 BDS2006 VCL/C++/OpenGL1.0 Demo:

        • Demo Source+Binary

        Just select slow download and enter the validation code from image. It does not use any 3th party libs other than GL,GLU. The camera is static so just add keyboard/mouse events to your liking. If you want to port this to your environment just mimic the events behavior and ignore the VCL stuff.

        The OpenGL init is done based on this:

        • simple complete GL+VAO/VBO+GLSL+shaders example in C++

        I just removed the GLEW,GLSL and VAO stuff from it.

相关文章