使用OpenGL进行高多边形网格的3D光线拾取

4
如何在包含高多边形网格模型的3D场景中实现3D射线拾取?
迭代所有三角形以执行三角形-线段交点测试需要太多时间。我知道存在像八叉树等方法,可以用于场景中的模型,但我不知道如何在网格级别使用这些概念。但是,如果在网格级别使用八叉树,如何处理超出八叉树体积边界的多边形问题呢?
您有没有建议适用于实时OpenGL应用程序中高多边形模型的3D射线交集的合适或推荐方法?

这种方法能否获取网格表面与交点处的交点和法向量,还是更适合一般对象的选择? - Lemonbonbon
我认为你不必花时间编写一个示例,但还是谢谢。我想我会尝试实现某种BVH层次结构,以获得更灵活的解决方案,即使交点(由于某种原因)出现在屏幕外也能正常工作。 - Lemonbonbon
我将评论转换为答案...并附上示例:),因为这不是我第一次看到与此相关的问题,而且以前总是太懒得回答...现在我有东西可以链接了:) - Spektre
我在深度转换中发现了一个错误,已经修正了pick函数的准确性,如果zNear很大,则不准确。 - Spektre
2个回答

8
对于选取渲染对象(例如通过鼠标)的光线拾取,最好的选择是使用已经渲染的缓冲区,因为与复杂场景上的光线交叉测试相比,读取它们的成本非常小。思路是为每个您需要的信息将每个可选渲染对象呈现到单独的缓冲区中,例如:
  1. 深度缓冲

    这将为您提供射线交点与物体的三维位置。

  2. 模板缓冲

    如果每个对象都用其ID(或其在对象列表中的索引)呈现到模板,则可以直接获取选定的对象。

  3. 其他任何

    还有次要颜色附件和FBO。因此,您可以添加任何其他需要的内容,例如法向量或其他内容。

如果编码正确,所有这些都将仅略微(甚至不)降低性能,因为您不需要计算任何内容,而只需对每个缓冲区的每个片段进行一次写入。

选取本身很容易,您只需从需要的所有缓冲区中读取相应的像素并转换为所需的格式即可。

这里是一个简单的C++/VCL示例,使用固定管线(无着色器)...

//---------------------------------------------------------------------------
#include <vcl.h>
#include <math.h>
#pragma hdrstop
#include "Unit1.h"
#include "gl_simple.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
void matrix_mul_vector(double *c,double *a,double *b,double w=1.0)
    {
    double q[3];
    q[0]=(a[ 0]*b[0])+(a[ 4]*b[1])+(a[ 8]*b[2])+(a[12]*w);
    q[1]=(a[ 1]*b[0])+(a[ 5]*b[1])+(a[ 9]*b[2])+(a[13]*w);
    q[2]=(a[ 2]*b[0])+(a[ 6]*b[1])+(a[10]*b[2])+(a[14]*w);
    for(int i=0;i<3;i++) c[i]=q[i];
    }
//---------------------------------------------------------------------------
class glMouse
    {
public:
    int sx,sy;      // framebuffer position [pixels]
    double pos[3];  // [GCS] ray end coordinate (or z_far)
    double beg[3];  // [GCS] ray start (z_near)
    double dir[3];  // [GCS] ray direction
    double depth;   // [GCS] perpendicular distance to camera
    WORD id;        // selected object id
    double x0,y0,xs,ys,zFar,zNear;  // viewport and projection
    double *eye;    // camera direct matrix pointer
    double fx,fy;   // perspective scales

    glMouse(){ eye=NULL; for (int i=0;i<3;i++) { pos[i]=0.0; beg[i]=0.0; dir[i]=0.0; } id=0; x0=0.0; y0=0.0; xs=0.0; ys=0.0; fx=0.0; fy=0.0; depth=0.0; }
    glMouse(glMouse& a){ *this=a; };
    ~glMouse(){};
    glMouse* operator = (const glMouse *a) { *this=*a; return this; };
//  glMouse* operator = (const glMouse &a) { ...copy... return this; };

    void resize(double _x0,double _y0,double _xs,double _ys,double *_eye)
        {
        double per[16];
        x0=_x0; y0=_y0; xs=_xs; ys=_ys; eye=_eye;
        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];
        }

    void pick(double x,double y)    // test screen x,y [pixels] position
        {
        int i;
        double l;
        GLfloat _z;
        GLint _id;
        sx=x; sy=ys-1.0-y;
        // read depth z and linearize
        glReadPixels(sx,sy,1,1,GL_DEPTH_COMPONENT,GL_FLOAT,&_z);    // read depth value
        depth=_z;                                               // logarithmic
        depth=(2.0*depth)-1.0;                                  // logarithmic NDC
        depth=(2.0*zNear)/(zFar+zNear-(depth*(zFar-zNear)));    // linear <0,1>
        depth=zNear + depth*(zFar-zNear);                       // linear <zNear,zFar>
        // read object ID
        glReadPixels(sx,sy,1,1,GL_STENCIL_INDEX,GL_INT,&_id);   // read stencil value
        id=_id;
        // win [pixel] -> GL NDC <-1,+1>
        x=    (2.0*(x-x0)/xs)-1.0;
        y=1.0-(2.0*(y-y0)/ys);
        // ray start GL camera [LCS]
        beg[2]=-zNear;
        beg[1]=(-beg[2]/fy)*y;
        beg[0]=(-beg[2]/fx)*x;
        // ray direction GL camera [LCS]
        for (l=0.0,i=0;i<3;i++) l+=beg[i]*beg[i]; l=1.0/sqrt(l);
        for (i=0;i<3;i++) dir[0]=beg[0]*l;
        // ray end GL camera [LCS]
        pos[2]=-depth;
        pos[1]=(-pos[2]/fy)*y;
        pos[0]=(-pos[2]/fx)*x;
        // convert to [GCS]
        matrix_mul_vector(beg,eye,beg);
        matrix_mul_vector(pos,eye,pos);
        matrix_mul_vector(dir,eye,dir,0.0);
        }
    };
//---------------------------------------------------------------------------
// camera & mouse
double eye[16],ieye[16];    // direct view,inverse view and perspective matrices
glMouse mouse;
// objects
struct object
    {
    WORD id;                // unique non zero ID
    double m[16];           // direct model matrix
    object(){}; object(object& a){ *this=a; }; ~object(){}; object* operator = (const object *a) { *this=*a; return this; }; /*object* operator = (const object &a) { ...copy... return this; };*/
    };
const int objs=7;
object obj[objs];
// textures
GLuint txr=-1;
//---------------------------------------------------------------------------
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 gl_draw()
    {
    int i; object *o;
    double a;

    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT | GL_STENCIL_BUFFER_BIT );
    glEnable(GL_CULL_FACE);
    glEnable(GL_DEPTH_TEST);

    glEnable(GL_STENCIL_TEST);
    glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
    glStencilMask(0xFFFF); // Write to stencil buffer
    glStencilFunc(GL_ALWAYS,0,0xFFFF);  // Set any stencil to 0

    for (o=obj,i=0;i<objs;i++,o++)
        {
        glMatrixMode(GL_MODELVIEW);
        glLoadMatrixd(ieye);
        glMultMatrixd(o->m);
        glStencilFunc(GL_ALWAYS,o->id,0xFFFF); // Set any stencil to object ID
        vao_draw();
        }
    glStencilFunc(GL_ALWAYS,0,0xFFFF);  // Set any stencil to 0
    glDisable(GL_STENCIL_TEST);         // no need fot testing

    // render mouse
    glMatrixMode(GL_MODELVIEW);
    glLoadMatrixd(ieye);

    a=0.1*mouse.depth;
    glColor3f(0.0,1.0,0.0);
    glBegin(GL_LINES);
    glVertex3d(mouse.pos[0]+a,mouse.pos[1],mouse.pos[2]);
    glVertex3d(mouse.pos[0]-a,mouse.pos[1],mouse.pos[2]);
    glVertex3d(mouse.pos[0],mouse.pos[1]+a,mouse.pos[2]);
    glVertex3d(mouse.pos[0],mouse.pos[1]-a,mouse.pos[2]);
    glVertex3d(mouse.pos[0],mouse.pos[1],mouse.pos[2]+a);
    glVertex3d(mouse.pos[0],mouse.pos[1],mouse.pos[2]-a);
    glEnd();

    Form1->Caption=AnsiString().sprintf("%.3lf , %.3lf , %.3lf : %u",mouse.pos[0],mouse.pos[1],mouse.pos[2],mouse.id);

    // debug buffer views
    if ((Form1->ck_depth->Checked)||(Form1->ck_stencil->Checked))
        {
        glDisable(GL_DEPTH_TEST);
        glMatrixMode(GL_PROJECTION);
        glPushMatrix();
        glLoadIdentity();
        glMatrixMode(GL_MODELVIEW);
        glLoadIdentity();
        glEnable(GL_TEXTURE_2D);
        glBindTexture(GL_TEXTURE_2D,txr);
        GLfloat *f=new GLfloat[xs*ys],z;
        if (Form1->ck_depth  ->Checked)
            {
            glReadPixels(0,0,xs,ys,GL_DEPTH_COMPONENT,GL_FLOAT,f);
            for (i=0;i<xs*ys;i++) f[i]=1.0-(2.0*mouse.zNear)/(mouse.zFar+mouse.zNear-(((2.0*f[i])-1.0)*(mouse.zFar-mouse.zNear)));
            glTexImage2D(GL_TEXTURE_2D, 0, GL_RGB, xs, ys, 0, GL_RED, GL_FLOAT, f);
            }
        if (Form1->ck_stencil->Checked)
            {
            glReadPixels(0,0,xs,ys,GL_STENCIL_INDEX,GL_FLOAT,f);
            for (i=0;i<xs*ys;i++) f[i]/=float(objs);
            glTexImage2D(GL_TEXTURE_2D, 0, GL_RGB, xs, ys, 0, GL_GREEN, GL_FLOAT, f);
            }
        delete[] f;
        glColor3f(1.0,1.0,1.0);
        glBegin(GL_QUADS);
        glTexCoord2f(1.0,0.0); glVertex2f(+1.0,-1.0);
        glTexCoord2f(1.0,1.0); glVertex2f(+1.0,+1.0);
        glTexCoord2f(0.0,1.0); glVertex2f(-1.0,+1.0);
        glTexCoord2f(0.0,0.0); glVertex2f(-1.0,-1.0);
        glEnd();
        glMatrixMode(GL_PROJECTION);
        glPopMatrix();
        glDisable(GL_TEXTURE_2D);
        glEnable(GL_DEPTH_TEST);
        }
    glFlush();
    SwapBuffers(hdc);
    }
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner)
    {
    int i;
    object *o;

    gl_init(Handle);
    vao_init();

    // init textures
    glGenTextures(1,&txr);
    glEnable(GL_TEXTURE_2D);
    glBindTexture(GL_TEXTURE_2D,txr);
    glPixelStorei(GL_UNPACK_ALIGNMENT, 4);
    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S,GL_CLAMP_TO_EDGE);
    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T,GL_CLAMP_TO_EDGE);
    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER,GL_NEAREST);
    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER,GL_NEAREST);
    glTexEnvf(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE,GL_COPY);
    glDisable(GL_TEXTURE_2D);

    // init objects
    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
    glTranslatef(-1.5,4.7,-8.0);
    for (o=obj,i=0;i<objs;i++,o++)
        {
        o->id=i+1;  // unique non zero ID
        glGetDoublev(GL_MODELVIEW_MATRIX,o->m);
        glRotatef(360.0/float(objs),0.0,0.0,1.0);
        glTranslatef(-3.0,0.0,0.0);
        }
    for (o=obj,i=0;i<objs;i++,o++)
        {
        glLoadMatrixd(o->m);
        glRotatef(180.0*Random(),Random(),Random(),Random());
        glGetDoublev(GL_MODELVIEW_MATRIX,o->m);
        }
    }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormDestroy(TObject *Sender)
    {
    glDeleteTextures(1,&txr);
    gl_exit();
    vao_exit();
    }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormResize(TObject *Sender)
    {
    gl_resize(ClientWidth,ClientHeight);
    // obtain/init matrices
    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
    glTranslatef(0,0,-15.0);
    glGetDoublev(GL_MODELVIEW_MATRIX,ieye);
    matrix_inv(eye,ieye);
    mouse.resize(0,0,xs,ys,eye);
    }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender)
    {
    gl_draw();
    }
//---------------------------------------------------------------------------
void __fastcall TForm1::Timer1Timer(TObject *Sender)
    {
    gl_draw();
    }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormMouseWheel(TObject *Sender, TShiftState Shift, int WheelDelta, TPoint &MousePos, bool &Handled)
    {
    GLfloat dz=2.0;
    if (WheelDelta<0) dz=-dz;
    glMatrixMode(GL_MODELVIEW);
    glLoadMatrixd(ieye);
    glTranslatef(0,0,dz);
    glGetDoublev(GL_MODELVIEW_MATRIX,ieye);
    matrix_inv(eye,ieye);
    gl_draw();
    }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormMouseMove(TObject *Sender, TShiftState Shift, int X, int Y)
    {
    mouse.pick(X,Y);
    }
//---------------------------------------------------------------------------
void __fastcall TForm1::ck_depthClick(TObject *Sender)
    {
    gl_draw();
    }
//---------------------------------------------------------------------------

这里是从左到右的RGB、深度和模板预览:

preview

这里是捕获的GIF:

GIF preview

前三个数字是在[GCS]中选定像素的3D位置,标题中的最后一个数字是选定的ID,其中0表示没有对象。

此示例使用gl_simple.h,可以从以下链接获取:

您可以忽略VCL内容,因为它不重要,只需将事件移植到您的环境即可...

所以该怎么做:

  1. rendering

    You need add stencil buffer to your GL window pixel format so in my case I just add:

     pfd.cStencilBits = 16;
    

    into gl_init() function from gl_simple.h. Also add its bit into glClear and set each objects stencil to its ID Like I did in gl_draw().

  2. picking

    I wrote a small glMouse class that do all the heavy lifting. On each change of perspective, view, or viewport call its glMouse::resize function. That will prepare all the constants needed for the computations later. Beware it needs direct camera/view matrix !!!

    Now on each mouse movement (or click or whatever) call the glMouse::pick function and then use the results like id which will return the ID picked object was rendered with or pos which is the 3D coordinate in global world coordinates ([GCS]) of the ray object intersection.

    The function just read the depth and stencil buffers. Linearize depth like here:

    and compute the ray beg,dir,pos,depth in [GCS].

  3. Normal

    You got 2 options either render your normal as another buffer which is the simplest and most precise. Or read depths of 2 or more neighboring pixels around picked one compute their 3D positions. From that using cross product compute you normal(s) and average if needed. But this can lead to artifacts on edges.

如评论中所提到的,为了提高准确性,您应该使用线性深度缓冲而不是像这样的线性化对数:

顺便说一句,我在这里也使用了相同的技术(在基于GDI的SW等距渲染中):

[编辑1] 8位模板缓冲

现在可靠的模板位宽只有8位,这限制了标识符的数量为255。在大多数情况下,这是不够的。一个解决方法是将索引呈现为颜色,然后将帧存储到CPU内存中,然后正常地渲染颜色。然后在需要时使用存储的帧进行选择。渲染到纹理或颜色附件也是可能的。

[编辑2] 一些相关链接


1
pick(x,y) 中,z=(2.0*zNear*zFar)/(zFar+zNear-(z*(zFar-zNear))) 右侧的 z 是在哪里定义的? - John Alexiou
2
@JohnAlexiou 很好的发现 +1 ... 我不知道发生了什么(也许我错误地编辑了某些内容),花了我一段时间才找到原始项目,我再次复制了代码 ... 如果我看得对,现在我使用 depth 而不是 z,所以我可能只是部分复制了被卡在剪贴板中的已编辑代码,而不是我想要的代码(由于 W95 时代编写的键盘 ISR 处理程序不佳,有时 [Ctrl+Ins] 不按预期工作)。 - Spektre

1
使用八叉树。确保它适合于整个网格。
此外,似乎您正在将每个多边形分配给一个叶子/桶,这是不正确的。将多边形分配到它们出现的所有叶子/桶中。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接