Archived

This topic is now archived and is closed to further replies.

finding all faces infront of a plane, worst case

This topic is 5749 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Use an octree to group faces together. Test the nodes of the octree. If a node is in front of the plane, then you automatically know that the faces in the node(and its children) exist in front of the plane.

Edited by - acw83 on February 23, 2002 11:03:11 AM

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites