|
Polygons In Octant Question submitted by (31 July 2000)  |
Return to The Archives |
 |
 |
|
| I've been recently programming a Octree Space Partitioning system for my engine. As I got into it, I noticed that I couldn't think of many ways to figure out which polygons were inside an octant. Many people had ideas but were only partially successful. Aside from there being almost no documentation on this issue, I still obviously want to proceed with my OSP system. Have any advice or a point to documentation that can? | ||
 |
 |
 |
|
|
|
The answer requires clipping. But it's not as bad as it may seem... Start with your root node and determine the X-axis bisection plane. Create two lists of polygons based on this bisection. Remember, this is an orthogonal plane, so any polygons whose vertices all have x-coordinates that are less than X (the location of the bisection plane) will be grouped in the first list. Any polygons whose vertices all have x-coordinates greater than X will be grouped in the second list. All the other polygons intersect the plane and must be clipped (orthogonally.) Add each clipped fragment to it's associated list. You now have two lists. Perform this same operation, but this time you'll use the Y-axis bisection plane and you'll need to bisect both lists. Since you're splitting two lists, you'll end up with four lists. Finally, take those resulting four lists, and perform the final step using the Z-axis bisection plane on all four lists. The result will be eight lists. These eight lists represent the lists polygons that intersect each of the eight child nodes of the root. Perform this process recursively. You can still store references to a polygon in multiple nodes (to avoid clipping them in the final database.) The clipping process outlined above is only to determine spatial interaction, not final database occupation. If you store a reference to the original polygon within each clipped fragment during the recursive build process, you can quickly revert to the original geometry when storing the database. Response provided by Paul Nettle |
||
|
|
|
This article was originally an entry in flipCode's Ask Midnight, a Question and Answer column with Paul Nettle that's no longer active. |