Hi, i''m trying to write a method that will determine all the faces that are infront of an arbitray plane. The obvious way would be to loop through all the faces in the world and compare is points to the plane, if they are all infront then the face is infront of the plane and should be added to the resulting collection. This is worst case O(n), where n is the number of planes in the world. Can this be done in less time O(lgn), given that the planes are stored in some data structure?......My engine uses bsp-trees thanks

If you''re using a BSP tree already, are you wanting to determine which static faces lie in front of the plane? Couldn''t your BSP tree store this information? Won''t work if the faces are moving and you aren''t updating your BSP tree in real-time, .

You should definitely avoid checking individual faces if you can. Are the faces grouped into objects? Why not check a bounding box for an entire object containing many faces instead of walking through all the faces. This should get you to O(< n).

You could also keep a list of faces in front and behind the plane. Initialize it when the level starts and update the lists as the game plays. When a face passes by the plane, make sure its in the correct list.

There are more formal and rigorous descriptions of how to do this, but perhaps this will get you started.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

grhodes_at_work I think you miss-understood me. i''m actually checking an arbitrary plane (created by the direction the player is facing as well as there translation) so storing the which faces are infront of these arbiratry planes at level-build time would be impossible. thanks for the help anyways