commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Martin Ennemoser" <>
Subject Re: [math] How to use the BSP Tree?
Date Sun, 26 Aug 2012 09:42:31 GMT
Hi Luc!

Thank you for your answer. I tried it an it works. But isn't there an easier way to build
a polyhedron? Do I relly need this projection and line stuff?

Best regards,


-------- Original-Nachricht --------
> Datum: Sat, 25 Aug 2012 14:03:33 +0200
> Von: Luc Maisonobe <>
> An: Commons Users List <>
> Betreff: Re: [math] How to use the BSP Tree?

> Le 25/08/2012 12:17, Martin Ennemoser a écrit :
> > Hi!
> Hi Martin,
> > 
> > I have a polyhedron in 3D space that consists of a triangle mesh. Now I
> want to use the BSP tree to classify wheter a point is inside or outside of
> the polyhedron.
> > The problem is that I don't know how to construct a BSP tree with my
> polyhedron vertices. The user guide only gives provides little information.
> > Maybe someone could give me with a short code example.
> You can look for example at the junit tests. One example is testIssue780
> in the PolyhedronsSetTest class in package
> org.apache.commons.math3.geometry.euclidean.threed. The algorithm used
> by the test is the following:
> 1) set up the points coordinates for all vertices of the polyhedron
> 2) set up the mesh triangles by using an indirection array
>    of indices (i.e. somthing like triangle 1 uses points 1, 2 and 3,
>    triangle 2 uses point 4, 5 and 1, traingle 3 uses ...)
> 3) for each triangle, create a facet using the following stages:
>    3a) create a 3D plane from the three points
>    3b) create 2D points by projecting the 3D points into the plane
>    3c) create three 2D lines by joining all pairs of projected 3D points
>    3c) create a 2D PolygonSet using the 2D lines
>    3d) create a 3D SubPlane using the plane and the 2D PolygonSet
> 4) create the PolyhedronSet using all 3D SubPlanes
> The main trick is the 2D/3D projection that occurs at each facet.
> Beware that when you create a Region from a collection of boundary
> elements (i.e. creating a PolygonSet from lines or creating a
> PolyhedronSet from facets), the elements in the boundary must be
> oriented, as they define which half space will be the interior and which
> half space will be the exterior. The convention we use is that the
> interior is on the minus side of the hyperplane. For lines, the plus
> side is the half space on the right when traveling along the line in
> ascending coordinate direction. This implies that if you define a square
> polygon, you should define the boundary in counterclockwise direction if
> you want the interior to be the finite square (on the left as you travel
> in counterclockwise direction along the boundary) and the exterior to be
> the infinite plane minus the central square (on the right as you travel
> in counterclockwise direction along the boundary). If you define the
> boundary in the opposite direction (i.e clockwise), the interior will be
> the infinite region and the exterior will be the finite square. If you
> define your boundary with some elements in one direction and other
> elements in the opposite direction, this will fail. For planes in 3D,
> the plus half space is towards plane normal.
> best regards,
> Luc
> > 
> > Thank you!
> > 
> > ---------------------------------------------------------------------
> > 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