RE: [Algorithms] Fast BSP tree algorithm

[Hejl, J. <jh...@ea...>]

Apologies to gdalgorithms,

I thought I was responding to the directxdev list, (with all the implied
circumstances).

-----Original Message-----
From: gda...@li...
[mailto:gda...@li...] On Behalf Of
Ville Miettinen
Sent: Monday, January 26, 2004 10:19 AM
To: gda...@li...
Subject: RE: [Algorithms] Fast BSP tree algorithm


Jim,

although your answer has relevance in the context of HW-based rendering,
I don't think that Steve ever told us what he's using the BSP trees for.
All he asked was how to robustly generate BSP trees for huge
environments.

And to answer his original question: I'm not aware of any _robust_ open
source implementations for the problem. We've always rolled our own.
It's not that difficult, and there are some good papers on the relevant
heuristics (search Citeseer or ACM Digital Library). But I can give you
a
hint: get your hands on some multi-precision or exact arithmetic library
(GMP will work just fine, or I can lend you ours) before you try this;
otherwise you'll find yourself in floating-point hell.

cheers,
-wili

--

o Ville Miettinen
o Head of Visual Research
o Hybrid Graphics, Ltd.
o http://www.hybrid.fi


> -----Original Message-----
> From: Hejl, Jim [mailto:jh...@ea...]
> Sent: 26. tammikuuta 2004 16:55
> To: gda...@li...
> Subject: RE: [Algorithms] Fast BSP tree algorithm
>
>
> The implementation of the tree probably isn't the issue here.
>
> In general, you can't expect to achieve data throughput that you=20
> describe with the cpu looking at individual primitives. This is a=20
> formula for being bottlenecked in memory on the cpu!
>
> One good solution is to store *objects* in the bsp tree, not=20
> individual primitives. Some type of loose bounding volume can be used
> for separator
> planes. With a few modifications, the tree traversal now
> returns a list
> of visible objects (where each object may contain thousands of
> primitives!). Sort the objects as needed, (by shader or material or
> whatever) and feed them to the hardware.
>
> Also, this scheme allows for world objects to be instanced, (a concept

> doesn't work with a polygon-soup tree). If you care about memory=20
> footprint, this is a good thing.
>
> Good luck!
>
> - Jim Hejl
>
> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...] On Behalf Of=20
> Steve Lamont
> Sent: Sunday, January 25, 2004 11:37 AM
> To: gda...@li...
> Subject: [Algorithms] Fast BSP tree algorithm
>
>
> Gentlefolk:
>
> Can anyone direct me to a reasonably fast implementation of the BSP=20
> algorithm that can robustly create partitionings for scenes with large

> numbers of polygons -- sometimes running into the millions?
>
> I need something Open Source.
>
> I've tried Norman Chin's algorithm from _Graphics Gems V_ but it=20
> chokes (becomes very slow) at scenes of only a few thousand
> polygons. I suppose
> I could spend time trying to optimize it but really need to direct my
> time toward other aspects of the project and so am looking
> for something
> canned that I can adapt.
>
> Please feel free to contact me off list, since I'm sure the is very=20
> old hat to most of the folks on this list.
>
> Should this be considered off topic, please direct your excoriations=20
> to me off list, as well.
>
> Thanks.
>
> 							spl
>
>
> -------------------------------------------------------
> The SF.Net email is sponsored by EclipseCon 2004
> Premiere Conference on Open Tools Development and Integration See the=20
> breadth of Eclipse activity. February 3-5 in Anaheim, CA.=20
> http://www.eclipsecon.org/osdn=20
> _______________________________________________
> GDAlgorithms-list mailing list GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188
>
>
>
> -------------------------------------------------------
> The SF.Net email is sponsored by EclipseCon 2004
> Premiere Conference on Open Tools Development and Integration See the=20
> breadth of Eclipse activity. February 3-5 in Anaheim, CA.=20
> http://www.eclipsecon.org/osdn=20
> _______________________________________________
> GDAlgorithms-list mailing list GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_ida88
>



-------------------------------------------------------
The SF.Net email is sponsored by EclipseCon 2004
Premiere Conference on Open Tools Development and Integration See the
breadth of Eclipse activity. February 3-5 in Anaheim, CA.
http://www.eclipsecon.org/osdn
_______________________________________________
GDAlgorithms-list mailing list GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188