Determining which face is clicked

The last time I was here, I posted a similar question to what I’m going to ask now (thanks for the replies in that other thread; I didn’t want to bump it by the time I got around to implementing it). But now, I’m extending my domain to arbitrary meshes.

Given a mesh drawn to the screen, I want the user to be able to draw a line on the screen, across the mesh, and the corresponding points along the mesh be found (in addition, I need to know exactly which face corresponds to each mouse input). That is, for any given click on the screen, I want to know a (intersection point, face index) pair where that click hits the mesh. Also, in a separate but related problem at another stage of my program, I will have a large array (eg, 500) of 3D data points and a constant direction (the “normal”). I will want to center the camera at each data point, look down the direction of the normal, draw the surface and see which point on the surface is right in the middle of the screen. To put it more clearly, I want to conceptually “draw a line” from each data point in the array, along the direction of a constant “normal”, and see exactly where it hits the surface in an (intersection point, face index) pair.

Here are my ideas:

1. Use an intersection algorithm, as found in a ray tracer. Aside from the naive solution of testing every triangle in the mesh, this would take a bit of time I may not be able to invest (building an octree or something). I need pretty good performance, since I’ll be doing 500+ vertices in a row and want it to compute in < 1 second.

2. Render the mesh and use GL picking (the name system) to determine which face was used. Then, I can shrink the viewport and use glScissor (like I do in the other post I linked at the top) to draw a very small part of the mesh. I think this is the preferred way, but the problem is, I plan on using VBOs to draw my mesh. How can I give names to each triangle drawn if I can’t change the name inbetween glVertex calls? In the other post, I drew the parametric surface in a special “color mode”, which does not apply to this general mesh case. Some extra information: I will be rendering a fully triangular mesh (using Loop subdivision), so this is well suited to VBOs since each polygon has the same number of sides, and our meshes may be somewhat large.

I think if I use immediate mode to render the mesh, I can solve this problem. I can specify names for each face, then render the mesh in selection mode for those times. However, I don’t think this solution is applicable with VBOs, am I correct? VBOs provide such a performance boost, especially for large meshes which I will be drawing hundreds of times in these sections, that I don’t really want to abandon them.

Any help would be appreciated!

As GL picking is not hardware accelerated, you won’t get any benefits from using VBOs here. I recommend you to use ray tracing, it would be faster and more robust. Even brute-force testing would be very fast if you only have so few triangles (500+ is not much!). Another method is to assign each face an unique color and read the color of the partcular ixel after the rendering – thus determining the face.

How can I assign each face a unique color? I only have control over the color of the vertices, and I can’t just assign every vertex a solid color because then some faces will have gradient shading. I suppose I could duplicate all the vertices three times in the drawing, but that seems bad as well.

Also, it is worth noting that the number of data points in my array (ie, 500 or so) is not related to the number of triangles on my mesh, which could be very large. Coding a naive ray tracing solution is very easy of course, but it just seems like it won’t be fast enough if I have several thousand faces.

Due to VBOs, I really think finding a way to draw each face a unique color is the best way to go. Then I’ll just have to come up with a way to generate n different colors (where n could be > 10,000) which can identify a face. It seems like an easy problem, but I’m just worried about the floating point error becoming a factor here. Should I be?

When rendering the faces for picking, disable lighting, use glShadeModel(GL_FLAT) and set all three vertex colors associated with the face to be the same (one vertex color would suffice actually, but you can’t skip item sin a vertex array). The interpolation error should be of no problem, because there will be no interpolation taking place

Hmm… yeah, I had forgotten about GL_FLAT, mainly because it’s never really used. After looking up the documentation on it, though, they note that the color of each face will be determined by the color of the last vertex specified for the triangle. With immediate mode, this seems like a cakewalk, but… I’m not entirely sure this is generalizable to VBOs. Even if I guarantee the mesh consists only of triangles, it could have arbitrary topology, and each vertex could have varying valences. Therefore, I have to determine ahead of time a UNIQUE vertex for each face (the one that will specify the color)… I can’t seem to convince myself that this is even possible for some meshes. By that, I mean there may be some meshes where some inner triangle’s three vertices are already “used” to specify the color for surrounding triangles.

At the very least, I imagine the algorithm for determining this to be extremely complex. Or am I missing something here? I mean, when I create my color array at mesh creation time, how can I pinpoint exactly which vertices will be the “last” to be drawn for each triangle… and how can I guarantee each triangle has a unique such vertex?

I guess I could just use immediate mode, and then I can easily just specify the last vertex directly and call glColor before each one. Argh, I really hate this solution, especially since I’ll lose many orders of magnitude in performance.

As already said, you can’t omit elements from a vertex array. The best solution would be to replicate vertices used by multiple faces. With another words, you loop throgh the faces and write the three vertices that make them up to the array. True, you will have some redundancy this way, but this can’t be helped. On newer NVIDIA hardware you can also use gl_PrimitiveID (is it calld this way?) in the vertex shader.

Set render-target to be some FBO in R32f format. 
Clear screen to black. 

Set vertex-shader to be:
void main(){ gl_Position = ftransform(); }
Set frag-shader to be:
uniform float colorID;
void main(){ gl_FragColor=vec4(colorID,0,0,0);}

foreach(VBO){
   GLuint ID = VBO.ID; // this is the VBO opengl "Name" 
   float fVboID = (float)ID;
   SetFragShaderUniformFloat(0,fVboID);
   VBO.Draw();
}   

//-----------------
void MyWindow_OnClick(int x,int y){
    float fVboID = xglGetPixel(x,y,GL_FLOAT); // make this func
    GLuint ID = (GLuint)fVboID;
    if(ID==0)return; // nothing selected
    CVbo VBO = GetVboByID(ID); 
    
    //----[ set Depth at x:y to be = zFar ]-----[
    // either by pixel-shader with
    // gl_FragDepth, or manually glDrawPixels
    xglDrawZDot(x,y); 
    //------------------------------------------/
    glDepthFunc(GL_LESS);


    now, decompose the VBO into triangles, set TexCoord0 of each vertex to be the triangle-ID (converted to float), and draw
    
    float fTriID = xglGetPixel(x,y,GL_FLOAT);
    int TriangleID = (int)fTriID;

    
}

The second part might possibly be sped-up by a frag-shader, that uses 2 calls to dFdx to roughly triangulate one of the vertices of the current triangle - but it’s just an idea that is only brewing in my head right now. (can’t test if the theory is ok)

Another method to speed-up the second part is binary-search:

First, do this at the start of the function:
AddUserClippingPlanesAroundPixel(x,y); // can be roughly defined

Then,

// this is right after glDepthFunc(GL_LESS); from the above code


glDepthMask(false);
BindVBO(vertices = VBO, indices = VBO.Indices);
SetShader( the one above, that uses "colorID" );

int chunkSize = (VBO.NumTris/10);
for(int i=0;i<10;i++){ // divide VBO triangles in 10 chunks
   SetFragShaderUniformFloat("colorID",(float)i);
   int chunkStart = i * ChunkSize;
   int chunkEnd = chunkStart+ChunkSize;
   if(i==9)chunkEnd=VBO.NumTris; // last chunk could be largest, with different size!
   xglDrawVBORange(chunkStart,chunkEnd);// use glDrawRangeElements in this
}
int chunkID = (int)xglGetPixel(x,y,GL_FLOAT);

int start=chunkID*chunkSize;
int end=start+chunkSize; if(chunkID==9)end = VBO.NumTris;

while(start<end-1){
   int mid = (start+end)/2;
   SetFragShaderUniformFloat("colorID",0.0f);
   xglDrawVBORange(start,mid);
   SetFragShaderUniformFloat("colorID",1.0f);
   xglDrawVBORange(mid,end);
   float px = xglGetPixel(x,y,GL_FLOAT);
   if(px==0){ // triangle is in first half of drawn tris
       end=mid;
   }else{
       start=mid;
   }
}

int DONE_PolygonID = start; // the end ^^
}

Also, it’s likely that fragment-shaders get re-uploaded if a uniform-constant is changed on nVidia cards (I’ve heard a rumour). If that’s the case, then you can simply move the colorID value to a vtx-shader uniform.

Ilian, your method won’t work here well, because he wants to select individual triangles, and your method would imply rendering each triangle in a separate call (=immediate mode). It is much better to pack the face colors into a color array.

How can face colors be packed into an array? Without converting the VBO data into from glDrawElements-suitable to glDrawArrays, that is. I thought with arrays/VBOs you can’t really specify per-polygon data (on <=SM3.0 cards).
Because I’ve seen the horrors of 400 vertices in a common type of model become 8700 when you remove the index.

Or maybe I didn’t explain the idea in the first method well - it’s to create those 8700 unwelded vertices (removing the index, yeah) into a streaming VBO, where every 3 vertices have the same glColor. These colors are encoded in RGBA8 format, render-target is also RGBA - and you can this way use any integer value when doing unpack_4ubyte()/pack_4ubyte()-like tricks on the cpu. (actually you just need to use a pack_4ubyte-like func in xglGetPixelAt(x,y)).

The second method I posted works completely differently - doesn’t do any vertex-unwelding - just marks ranges of the VBO in different colors, to gradually find the triangleID. Most useful on larger meshes.

Ah, ok, sorry, I didn’t read it throughfully. Well, my proposal was to replicate (what you call unwield) the vertices from the beginning (brute force), but your more intelligent approach may be faster, depending on the rendered data. Still, if he is rendering one object with 10k faces (as I understood), 30k vertices shouldn’t be a problem, IMHO.

Yes, depending on the number of triangles in the VBO, one of the two algorithms can be chosen. And if the #tris is very high, the second algorithm can be optimized by increasing the number of first chunks from 10 to i.e 100.

I’ve seen modelers use the expression “unweld vertices” for making no vertex belong to 2 or more polygons.

Also, an R32f rendertarget, or whatever separate rendertarget might be not necessary - as I mentioned above any 32-bit number or pointer can be encoded in RGBA8. [I’m a bit iffy about sharing depthbuffers between rendertargets, as it doesn’t work for me now]

vec4 Encode32bit(unsigned int i){
     unsigned char* p=(unsigned char*)&i;
     vec4 result;
     result.x = (*p++)/255.0;
     result.y = (*p++)/255.0;
     result.z = (*p++)/255.0;
     result.w = (*p++)/255.0;
     return result; // set a shader's uniform with this value
}
vec4 Encode32bit(void* ptrWhateverObject){
     return Encode32bit((unsigned int)ptrWhateverObject);
}

// uniform vec4 colorID; void main(){gl_FragColor=colorID;}

I appreciate your help, guys. I’m a little lost on the technicalities of Ilian’s post, so I will first just use Zengar’s method. I will have each vertex duplicated as much as necessary in the vertex array, set the shading mode to GL_FLAT, and then just set the 3 vertices for each face to a color which can be used to calculate the index for that face.

For this particular application, I won’t be drawing large meshes (ie, 1 million faces). I should be able to keep everything to 10k-50k or so, I’m sure (but I suppose if the application grows in scope, I will have to revisit this problem and use shaders).

If this doesn’t work out too well, I’ll be sure to post more questions.

So, the method to color faces in this way is working quite well. I turn the face index into a 3-digit (at most) number of base b, where b is the ceiling of the cube root of the max number of faces. Then I just normalize everything between 0 and 1 and I have my RGB color <-> face index conversion.

I also programmed a quick ray-triangle intersection, so when I do my intersection test and I get which face is in the color buffer, I can do a ray-triangle intersection test with that one face (which I know is a hit) to get the exact point of intersection.

To sum up, I want to know the (intersection point, face index) pair for a mesh in these two cases: 1) where a user clicks on the screen and 2) for a given ray (ie, data point and direction). What is the best way to handle case 1? Should I try to build a ray from the camera location through the window click point? This seems difficult to me, since then I have to apply multiple steps, such as finding the rotated/scaled/translated camera point and figure out how to cast a ray based on the viewing frustum through (windowX, windowY). Is there an easier way to handle this?

Hm, can’t gluProject() and gluUnproject() help you?