polygons from BSP

I have a 3d volume given by a binary space partition tree. Usually these are made from polygon models, and the splitted polygons already stored inside the tree nodes.

But mine is not, so I have no polygons. Every node has nothing but it's cut plane (given by normal and origin distance for example). Thus the tree still represent a solid 3d volume, defined by all the cuts made. However, for visualisation I need a polygonal mesh of this volume. How can that be reconstructed efficiently?

The crude method would be to convert the infinite half spaces of the leaves to large enough polhedrons (eg. cubes) and push every single one of them upwards the tree, cutting it by every node's plane it passes. That seems extremely costly, as the tree may be unbalanced (eg. if stupidly made from a convex polyhedra). Is there any classic solution?

Answers


In order to recover the polygonal surface you need to intersect the planes. Where each vertex of a polygon is generated by an intersection of three planes and each edge by an intersection of 2 planes. But making this efficient and numerical stable is no trivial task. So i propose to use qhalf that is part of qhull. A documentation of the input and ouput of qhalf can be found here. Of course you can use qhull (and the functionality from qhalf) as a library.


Need Your Help

ISNULL Date month

asp.net datetime isnull

I have two dropdownlists, one with months and the other one with year. The user selects the submit month and year for the items they want to retrieve. In database the date is entered in full eg. 0...

I want to log the Poison message that my wcf service is dropping using MSMQ 3.0 and windows 2003

wcf msmq

I want to log the Poison message that my wcf service is dropping using MSMQ 3.0 and windows 2003