commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Luc Maisonobe <>
Subject Re: BSP docs (was: [math] BSP - so given a set of polygon's it'll generate a BSP for me?)
Date Fri, 14 Aug 2015 19:34:51 GMT
Hi Sebb,

Le 14/08/2015 11:21, sebb a écrit :
> On 14 August 2015 at 09:57, Luc Maisonobe <> wrote:
>> Le 13/08/2015 23:20, Monty Hall a écrit :
>>> Not exactly sure how it works.  I need a BSP on short order.  Given a set
>>> of polygons, I'd like a BSP generated.  Please advise.  Any working code on
>>> how to use it too?
>> Hi Monty,
>> Yes, BSP trees can be created from polygons in some cases, but I am not
>> sure what it does is what you want. So here is a description of what we
>> can do.
> This looks like very useful information.
> It should be added to the Javadoc and/or user docs.

I have added it to the user guide.

best regards,

>> What I am refering to is that a BSP tree, in any supported topologies
>> and dimensions, can be built from a boundary representation. This means
>> that for building a BSP tree that represents a set of polyhedrons in 3D
>> space, the boundary representation is a set of 2D polygons that
>> represent the facets of the polyhedrons set. For example a 3D cube can
>> be defined using 6 2D squares that are embedded in the 3D space.
>> There is one constructor that may be helpful to you for the
>> PolyhedronsSet class, in the
>> org.apache.commons.math3.geometry.euclidean.threed package. The
>> signature of this constructor is:
>> PolyhedronsSet(List<Vector3D> vertices, List<int[]> facets,
>>                double tolerance);
>> The vertices list contains all the vertices of the polyhedrons, the
>> facets list defines the facets, as an indirection in the vertices list.
>> Each facet is a short integer array and each element in a facet array
>> is the index of one vertex in the list. So in our cube example, the
>> vertices list would contain 8 points corresponding to the cube
>> vertices, the facets list would contain 6 facets (the sides of the
>> cube) and each facet would contain 4 integers corresponding to the
>> indices of the 4 vertices defining one side. Of course, each vertex
>> would be referenced once in three different facets.
>> Beware that despite some basic consistency checkings are performed in
>> the constructor, not everything is checked, so it remains under caller
>> responsibility to ensure the vertices and facets are consistent and
>> properly define a polyhedrons set. One particular trick is that when
>> defining a facet, the vertices *must* be provided as walking the
>> polygons boundary in *trigonometric* order (i.e. counterclockwise) as
>> seen from the *external* side of the facet. The reason for this is that
>> the walking order does define the orientation of the inside and outside
>> parts, so walking the boundary on the wrong order would reverse the
>> facet and the polyhedrons would not be the one you intended to define.
>> Coming back to our cube example, a logical orientation of the facets
>> would define the polyhedrons as the finite volume within the cube to be
>> the inside and the infinite space surrounding the cube as the outside,
>> but reversing all facets would also define a perfectly well behaved
>> polyhedrons which would have the infinite space surrounding the cube as
>> its inside and the finite volume within the cube as its outside!
>> If you want to look at how it works, there is a test parser for PLY
>> file formats in the unit tests section of the library and some basic
>> ply files for a simple geometric shape (the N pentomino) in the test
>> resources. This parser uses the constructor defined above as the PLY
>> file format uses vertices and facets to represent 3D shapes.
>> Hope this helps,
>> Luc
>>> Thanks,
>>> M
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail:
>> For additional commands, e-mail:
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message