Jump to content
  • Advertisement
Sign in to follow this  

generate pair of parallel planes to evenly divide set of 3d points

This topic is 3471 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

Okay, I'm creating a game engine for a "space sim" type game, where you do a lot of interstellar travel. Consequently, the entities are easily represented as single points, and the biggest challenge is what to do with all that empty space. My plan is to create something akin to a binary tree. I need an algorithm that will do this, as part of the map pre-compiling process: Take a set of unsorted 3D points (a parent node.) Generate two parallel planes. The two planes act as a "thick" plane that divides up the 3D points into two sets (child nodes.) The planes must fit these criteria: * None of the points fall between the two planes (mandatory.) * None of the points are on the two planes (mandatory.) * The two sets of 3D points should have as similar a number of points as possible. * The two planes must be as far apart as possible, to maximize the amount of negative space being removed. How will I go about generating these planes? EDIT: By the way, the only languages I know are BASH, C++, and Python. I plan to prototype it in Python, and rewrite it in C++ if I have to.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!