HELP: Fast picking?

billy · March 4, 2002, 2:13am

I am writing a program. I have used the selection routines of OpenGL and found that they were a bit slow.

The way I use to select entities (points, triangles, etc.) is this:

I use gluProject to compute all primitives window coordinates
I choose the one closest to the mouse coordinates

The problem: I found that this is way too slow when you have more than 1000 entities.

Does anyone know a better way? I was thinking of creating an array that mapped the window with the entities in each region and then computing the closest in that region and not in the whole window.

Any suggestions?

Thanks in advance.

Billy.

harryx · March 4, 2002, 11:21am

How come you dont use the selection buffer?

fritzlang · March 4, 2002, 5:26pm

What I do is that I draw a color-coded version in the backbuffer, then read back
the picked pixel = picked obj.
should be fast enough in a vertex array.
cheers.

billy · March 5, 2002, 12:42am

Harryx: I found that the selection buffer is also very slow.

I want to do pre-selection. In other words, when I hover an object with many entities (points, triangles, etc.) it indicates the reference of that entity.
I have seen this in a CAD program and it is very fast. I wonder how they do it.

billy · March 5, 2002, 12:43am

fritzlang: Color based picking?
You mean you retrieve the color of a pixel that is under the mouse?
How does this work?

billy · March 5, 2002, 12:58am

To show what I mean, I posted some images at:
http://planeta.clix.pt/billy/preselect.zip

harryx · March 5, 2002, 3:53am

Ah, I see…

The color picking method involves rendering every entity twice, once in a unique color and then in its standard display color.

Youd then call readpixels to find the pixel color under the mouse cursor (inbetween the two render passes), and use it to index the object.

Apart from the obvious downside of rendering everything twice and using readpixels (luckily only on a very small part of the screen), my guess is this would probably be pretty fast and worth a try…

billy · March 5, 2002, 4:36am

Thanks harryx I will give it a try.

What about raycasting? I have read something about this. Is that better?

zeckensack · March 5, 2002, 4:46am

The performance of the multi-passing stuff will be very acceptable if you do it only when needed. IE only do the second pass when the user clicks the mouse. Or maybe when the mouse has hovered in one place for a certain amount of time and you want to display a tooltip. My point is, don’t do it every frame.

harryx · March 5, 2002, 5:21am

I get the impression ray-casting is the prefferred method for this kind of thing, but it would probably be a pain to implement well i.e doing ray/line intersections and creating a hierrachy to speed up intersection tests.

Ive never actually done it though, so I could be wrong.

billy · March 5, 2002, 11:30pm

How about using glUnproject? Is it faster than glProject?

billy · March 6, 2002, 11:09pm

The problem is that glReadPixels gives you a color, right? How do you associate this with a point?
Also I want it to snap to the closest entity, not only when it is exactly on top of it. That would be very dificult if we are considering a point of size 1.

harryx · March 7, 2002, 8:08am

You supply each entity with a unique color.
You read the desired pixels color and search your entities to find a match.

A neater but slightly less robust solution would be to use each entity’s address as its (32-bit) color. Hence no lookup search would be needed as the color is a pointer to the entity.

The “snap to” problem could be solved by reading pixels from a rectangle (around the mouse cursor) and using the nearest (valid) pixel color.

[This message has been edited by harryx (edited 03-07-2002).]

Chromebender · March 7, 2002, 9:29am

Raycasting by gluUnprojecting the mouse coordinates is probably slower than reading a color identifier from the backbuffer, the benefit to using it would be determining exactly where within a given triangle or polygon the user has clicked.

edit: actually I have no data to substantiate this being slower, but anyway it is longer to code.

[This message has been edited by Chromebender (edited 03-07-2002).]

Furrage · March 7, 2002, 10:15am

I don’t know how unProjecting fares against picking with colour. I think it should be faster than projecting though. I figure you can section off your vertices, do a quick test to see which section(s) the mouses line passes through and minimise your testing accordingly. Also using gluProject or gluUnProject apparently requires you to do 3 matrix multiplications. However, if you use gluUnProject you only do that twice (Unproject to near plane and to far plane). If you use gluProject you have to do that for all vertices

(ie 3 MatrixMults * 2 vs 3 MatrixMults * Numvertexes)

billy · March 7, 2002, 11:56pm

The problem is always speed. But not because gluProject or gluUnProject or glReadPixels, etc., because of testing which vertice is closest to the mouse pointer.

There must be some way to optimise this: Instead of testing all vertices in the whole window and we may consider 10000000 vertices, I was thinking of testing only a small region around the mouse. Does this sound ok? Has anyone done this already?

[This message has been edited by billy (edited 03-08-2002).]

harryx · March 8, 2002, 2:57am

I mentioned this in my last post, if you are using readpixels then simply read in say a 20x20 pixel rectangle and check for the closest valid pixel to the centre.

You could obviously do a similar thing with un/project.

You then have a trade off between snap to distance and performance, but then you wouldnt want to snap to entities that are too far away anyway.

billy · March 8, 2002, 6:07am

Yes, I agree with you. There is no point in testing all entities. I was just hopping somebody could post some code.

amstel · March 9, 2002, 1:10am

Dear Billy,

  Would you mind if you give me your code only in the selection routine. I prefer to your work after I have seen the image you have posted. And if this does not so disturb you,please give me your sampling code about object selection in  order to I will learn one. Now I pragram about object selection too. Thanks in advance

Best regard,
amstel.

billy · March 10, 2002, 11:39pm

I am programing this with VB but the routines are almost the same in VC.

Sub PreSelect(x1 As Single, y1 As Single)

Dim objx, objy, objz As GLdouble
Dim winx#, winy#, winz#

Dim mMatrix(15) As GLdouble
Dim pMatrix(15) As GLdouble
Dim vMatrix(3) As GLint

Dim cdist As Single
Dim mindist As Single
Dim typesel As Integer
Dim numbsel As Long
Dim selwx As Double
Dim selwy As Double

mindist = 15

glGetDoublev glgModelViewMatrix, mMatrix(0)
glGetDoublev glgProjectionMatrix, pMatrix(0)
glGetIntegerv glgViewport, vMatrix(0)

For i = 1 To m_numbpnt

'm_pnt(i).psel = False

objx = m_pnt(i).v(1)
objy = m_pnt(i).v(2)
objz = m_pnt(i).v(3)

gluProject objx, objy, objz, mMatrix(0), pMatrix(0), vMatrix(0), winx#, winy#, winz#
    
winy# = Me.ScaleHeight - winy#
  
cdist = Sqr((x1 - winx#) ^ 2 + (y1 - winy#) ^ 2)
  
If cdist &lt; mindist Then
      
  numbsel = i
  mindist = cdist
  typesel = 1
            
  selwx = winx#
  selwy = winy#
  
End If

Next i

For i = 1 To m_numbtri

'm_tri(i).psel = False

objx = (m_pnt(m_tri(i).pnt(1)).v(1) + m_pnt(m_tri(i).pnt(2)).v(1) + m_pnt(m_tri(i).pnt(3)).v(1)) * 0.333333333333333
objy = (m_pnt(m_tri(i).pnt(1)).v(2) + m_pnt(m_tri(i).pnt(2)).v(2) + m_pnt(m_tri(i).pnt(3)).v(2)) * 0.333333333333333
objz = (m_pnt(m_tri(i).pnt(1)).v(3) + m_pnt(m_tri(i).pnt(2)).v(3) + m_pnt(m_tri(i).pnt(3)).v(3)) * 0.333333333333333

gluProject objx, objy, objz, mMatrix(0), pMatrix(0), vMatrix(0), winx#, winy#, winz#
    
winy# = Me.ScaleHeight - winy#
  
cdist = Sqr((x1 - winx#) ^ 2 + (y1 - winy#) ^ 2)
  
If cdist &lt; mindist Then
      
  numbsel = i
  mindist = cdist
  typesel = 2
            
  selwx = winx#
  selwy = winy#
  
End If

Next i

End Sub