On Mar 1, 2014, at 7:59 AM, H.S.Rai wrote: > Following paper reported use of binary space partitioning tree (BSP) > in CSG, and claimed efficiency by use of it. > > http://www.andrew.cmu.edu/user/jackiey/resources/CSG/CSG_report.pdf > > Can it be of any benefit to BRL-CAD?
Short answer: yes, for mesh evaluation. Longer answer: we already use (and have always used) a non-uniform binary space partitioning (BSP) tree during ray tracing (which is how we evaluate the CSG Booleans). If we didn't, we'd be running orders of magnitude slower. However, this paper is about performing CSG Booleans on polygonal mesh geometry. We do CSG mesh evaluation when displaying or exporting geometry (e.g., to STL and DXF). We do not currently use a BSP when exporting meshes, and using one would most definitely speed things up. In fact, we have a TODO on this very topic: * use spatial partitioning during boolean processing of polygonal meshes. good approach might be to generalize TIE's kd-tree to polygons or even create a new scheme (e.g., an integer-indexed grid layout). data coherence would be nice (but not essential). current approach is at least O(N^2) with large constant time. New should be O(N*log(N)). It suggest kd-trees but really any spatial partitioning method would work. Cheers! Sean ------------------------------------------------------------------------------ Flow-based real-time traffic analytics software. Cisco certified tool. Monitor traffic, SLAs, QoS, Medianet, WAAS etc. with NetFlow Analyzer Customize your own dashboards, set traffic alerts and generate reports. Network behavioral analysis & security monitoring. All-in-one tool. http://pubads.g.doubleclick.net/gampad/clk?id=126839071&iu=/4140/ostg.clktrk _______________________________________________ BRL-CAD Developer mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/brlcad-devel
