which is the fastest way to perform a selection?

[HanWu]

i would like to know which is the fastest way to perform a selection, let say we have about 10000 polygon and each polygon consist of 10 point(3D point). If we use glLoadName() to assign an id to each polygon, when we select all the object, the hits record will store 10000 hits, and i use this method to check which polygons are in the selected area.

m_object// my list to store all the object
m_selection// list to store selected object

// draw object

POSITION pos=m_object.GetHeadPosition();

while(pos!=NULL){
CDrawObj *pObj= m_object.GetNext(pos);

glLoadName(pObj->GetObjectId());
}

// selection
int id[40000];

GLuint buffer[BUF_SIZE];
glSelectBuffer (BUF_SIZE, buffer);

for(int i=0;i<40000;i++)
id[i]=0;

for(int i=0;i<hits;i++){

if(id[i]==1)
continue;
POSITION pos= m_object.GetHeadPosition();
while(pos!=NULL){
CDrawObj *pObj=m_object.GetNext(pos);
if(m_selection.Find(pObj))
continue;
if(pObj->GetObjectId()==buffer[i*3])
// if buffer record equal to object id
m_selection.AddTail(pObj);

}
}
i find that this method is slow when the number of object is increace. Does anyone know the better way to perform selection.

[Adrian67]

If the geometry is fairly static you could store it in an octree (or quadtree if it's 2D), and them determine which nodes of the tree were hit by the selection point and only perform the selection on the polygons within those nodes.

[HanWu]

i am doing a CAD program, and the list to store objects is declared dynamic. Which can be one object or even 100000 objects. i wonder autocad can do a selection very fast even with a big model. Does anyone know how autocad do it.

[mikael_aronsson]

Hi !

One way is to keep a bounding box around all complex objects and do a picking on the bounding boxes, once you have found the object that was hit you can do a new picking but only render the object that was hit the first time.

This would cut down the amount of geometry you need to process for the picking.

Mikael