#
**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)