commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Luc Maisonobe <>
Subject Re: [math] How to use the BSP Tree?
Date Sat, 25 Aug 2012 12:03:33 GMT
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,

> Thank you!
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

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

View raw message