Sign in to follow this  
MaxIBoy

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

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this