[math] BSP - so given a set of polygon's it'll generate a BSP for me?

[Monty Hall <mo...@gmail.com>]

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?

Thanks,

M

Re: [math] BSP - so given a set of polygon's it'll generate a BSP for me?

[Luc Maisonobe <lu...@spaceroots.org>]

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.

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: user-unsubscribe@commons.apache.org
For additional commands, e-mail: user-help@commons.apache.org