   3D File Browser - Efficient Collision Detection methods?
  I hate asking about a topic that many people have asked about, but I feel my problem is unique.  I've got a functional 3D file browser.  Right now it's nothing too fancy and the idea is simple:Scan whatever file folder the user is currently in, and generate a torus for each file/folder that is in the current folder (or root directory).I need to be able to detect if the user is within the inner area of the ring.Currently the code I have devised is:void checkCollisions(){index = 0;for(unsigned int i=0; i<folderIndex.size(); ++i){if(camXpos >= positionx[folderIndex]-(centerx+outerRadius) && camXpos <= positionx[folderIndex]-(centerx-outerRadius) &&   camYpos >= positiony[folderIndex]-(centery+outerRadius) && camYpos <= positiony[folderIndex]-(centery-outerRadius) &&   camZpos >= positionz[folderIndex]-distancez && camZpos <= positionz[folderIndex]-distancez+1.5){index = folderIndex;reInit = true; // used in the display() function in Main.cpp}}}Now, this works perfectly for my needs actually.  I'm simply comparing the x, y, and z positions of my camera to the area of each torus.  I'm only doing this for torii that represent folders, not files.  But there can still be a lot of processing overhead if there's a lot of folders.  So far, the program can go through most of my folders with no problem.But I run into a folder called winsxs on Windows Vista.  This folder on my laptop has 35,481 files and 8,499 folders.  So, based on the code I posted above, the global variable totalObjs represents the total number of folders in the current directory.  So... it's doing the collision check for all 8,499 folders.Is there a better way of doing collision detection for my problem?I should mention even with me not running that collision loop, there is still slowdown in that folder because it's not only drawing 8,499 torii that represent folders, but also 35,481 torii that represent files >_<.  So for this program, I'll probably have it toggle between 3d view, and a "simple" view (where simple view would show a traditional listing of text or something like that if there are too many folders or torii to draw).--------------------- non-relevant --------------------------I've used Tactile 3D and it's an excellent 3D file browser for the most part (but it DOES crash when you enter the winsxs folder), so my program is already better since it doesn't crash (and you can still move through the areas of rings, but very slowly).I AM using display lists... now I have a problem with integrating text for the folder names... but one problem at a time.   
  Maybe you could convert the center of the torus into screen space coordinates, then check the distance between the cursor position and the center of the torus, like such.for_each( file in file_list ){vec2 pos = file.getTorus().getScreenSpacePosition();vec2 mpos = getMousePosition();float radius = file.getTorus.getOuterRadius();if( distanceSquared(mpos, pos) <= radius * radius )//User is hovering over that torus};  This may be too obvious a question, but are you doing any sort of broad-phase culling to reduce the number of narrow-phase intersection tests you have to perform?   ;Quote:This may be too obvious a question, but are you doing any sort of broad-phase culling to reduce the number of narrow-phase intersection tests you have to perform?Forgive me, I'm actually new to graphics programming.  I just started this project a little over two weeks ago >_<.  But if I understand the question right...I've spent the past couple hours trying to figure out how I could reduce the number of intersection tests.I'm still not too happy with the answer, but there seems to be less processing.I'll try to explain how the graphics are drawn and how I'm testing intersections in few words as possible...Currently, I'm drawing groups of 8 x 8 grids of rings that represent the files and folders.  And I keep track of the number of groups.So let's say there are 130 files/folders...There should be 3 groups...First group would be 64 rings, then the second group of 64 is drawn 30 points behind the first group (on the z axis), then the third group of the remainder is drawn 30 points behind the second group (on the z axis).  Etc... so-on for larger numbers of files/folders.So the program keeps track of the camera's position on the z axis, and the program now says:if the camera is within this group of rings, then test the x and y coordinates for JUST that group...but it still seems like I could be doing this more efficiently : /.  Not unless there really isn't any other way...// FILEBLOCK is a global variable defined as 64void trackCamera(){for(int i=0; i < group+1; ++i){if(camZpos >= (-distancez-i*30)-1.5 && camZpos <= (-distancez - i * 30)){if(totalObjs < FILEBLOCK) // If there are less than 64 items totalcheckCollisions(0, totalObjs); // Check the group of objectselse if(i == group && totalObjs > FILEBLOCK) // If we're at the last group, and there are more than 64 total objectscheckCollisions(i*FILEBLOCK, totalObjs); // Check the last group of objectselsecheckCollisions(i*FILEBLOCK, ((i+1)*FILEBLOCK)-1); // Check each group (which should be 64 objects)}}}And this new function was actually necessary because I found that in folders with large numbers of files/folders, there was a delayed response in updating the directory path, scanning the new directory, updating data vectors, calculating positions, etc...   ;  You could switch to a much easier intersection test based on the distance of the torus to the camera. Like a sphere - point "intersection" test.I'm still not sure what you're doing exactly. Are your collisions done in world space? If so then insert your torii into an octree (read it up on wikipedia) and only run the collision tests for those nodes and subnodes, the camera is inside. This should give you a huge performance gain, since your world seems static (or do the torii move?).*edit*You should really combine the second and the first method I described:-For every torus inside an octree node, run a sphere intersection test, which is a simple distance check, then if the test is positive, run the detailed test you described:void checkCollision(){    foreach( Torus torus, m_torii )    {   if( length( cameraPosition, torus.position ) <= torus.boundingRadius )   {  // Detailed test that you described in your first post   }}Just out of curiosity, why are you not using vectors? It seems that you have 3 arrays that contain the distance to the world axes. You should really group it together to one class.class Torus{    vector3 m_position;    float   m_boundingRadius;};;you need some spatial sorting, to detect which of the tori are close to your camera. 35,000 would not be much of a challenge if your files / folders are organised correctly.How do you place those torii spatially? in a 3D voxel map (in a sort of cube grid fashion like a giant rubick's cube, where all objects are equally spaced). If the organisation is more anarchic, there are slightly more complicated methods of sorting your objects.  Furthermore, with adequate spatial sorting, you can also do frustum clipping, and only render what is visible (so you wont need to use a 'simple' view, or use several levels of detail of your torii mesh, a simple thing to do). And also, ray picking (mouse click objects in 3D).   ;  I do have spatial sorting.  That's what I was trying to explain >_<  I'm drawing a wall of 64 torii, then after 64, move back on the z axis.  I spent a couple hours last night rewriting the code to track the z position and compare it to the z positions of the grids.  I'll have to show a screen-shot...Anyway, there's a lot of things I don't know because I'm just learning all of this.  But the suggestions in this thread are pointing me in the right direction.  I didn't know there was a such a thing as an octree for instance.  I thought about maybe implementing hash tables? for position lookups.  Frustrum clipping is another thing I needed to know about too!But really this is the process:Scan the current directoryDraw a torus for each file/folder starting at x,y,z=0.And then I just want to test if the camera moved through a particular ringUpdate the filepathScan the new directoryUpdate the graphicsRepeatIf you guys have any links to how to use the octree and any other methods that would be helpful!But I am using spatial sorting, my torii are spaced apart, and I'm usin multiple arrays to associate the centers of the torii with foldernames.I just need an efficient method of intersection tests (which I'm guessing is bounds checking in the code).And if someone can point me to an efficient way to print an array of text that doesn't horribly destroy the framerate, that would be great too :D   ;  If your objects are placed in a regular grid, in that case, you would only need to check one torus at a time. You just need to know which voxel you camera position is in, there is actually no need for octrees and such. Say you have a folder with 120,000 files and subfolders.You place the render objects in a voxel array of 64 columns x 64 rows x 30 in depth.Each voxel cell has a size of 100 units (so each torus will fit in a 100x100x100 cube).your camera is at position (12.3, 450.4, 1203.4).Mapping your camera into the voxel array, you get coordinates (12.3 / 100.0, 450.4/100.0, 1203.4/100.0)so you test against the torus at the cell(0, 4, 12).In short, your camera will be in the cell that has a bounding box (0, 400, 1200), (100, 500, 1300).since you have a (64 x 64) voxel base, the torus to check will be the one at index = (0 + 4 * (64) + 12 * (64 * 64)) = 49,408.Similarly, for rendering, you can detect what voxels are intersecting your camera frustum, however it is a bit more complicated than just querying a point in a voxelmap.EDIT : mapping could be wrong, that's just an example. Above, you would actually place the centre of the first torus at (50, 50, 50), not (0, 0, 0).   