Accelerated Dividing Line/Plane Finding Technique

By Joshua Cantrell
last updated: 9-15-00

INTRODUCTION

As far as I know, not many (if any) 3D accelerated video cards sort 3D convex polyhedra, so this must be done through software.  Due to the large number of facets a 3D convex polyhedron may have, a fast way of findout out how they are positioned with respect to each other can be very useful.  This is not only useful in telling which is in front of the other for drawing them in a desireable order, but also to know if they intersect each other.
I'm under the impression that someone has already come up with the algorithm I discuss on this page.  Unfortunately, I believe it must be either a black art subject, or no one knows how to discuss it adaquately.  I haven't found anything that covers this subject in any desireable detail.  For this reason, I have had to unhappily research this subject and come up with my own techniques.

The Basic Idea

The basic idea is discussed in the listed documents.  They may be flawed since my major isn't in mathematics, and some of them are just a little better than notes.
  • The Algorithm (12-11-00) - Fully formed, described, and corrected algorithm for my technique.
  • Techniques with Convex Polyhedron (1-15-00) - A brief overview of how my technique would work.

    • The Hierarchical Search Idea

    To improve on the implementation.  A convex polyhedron can be surrounded by a heirarchy of less detailed convex polyhedra.  The hierarchy is only decended if the two convex polyhedra are too close together to make the dividing plane indistinct (ie., the polyhedra higher up in the heirarchy collide.).
  • 3D Object Sorting : Who's in front? (9-15-00) - Thoughts almost straight from my notebook! The notes themselves are about as old as the first document.
    • joshuacantrell@yahoo.com
    (My Home Page) - (My Computer Science Page) - (My Personal Page) - (My Resume)