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 Sun, 26 Aug 2012 10:45:09 GMT
Le 26/08/2012 11:42, Martin Ennemoser a écrit :
> 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?

I think some of these steps could be gathered in a utility method, but
we didn't do it. Patches are welcome! One should be aware of the facets
orientation, so it may be difficult to set up a robust method though.

Another way to build polyhedrons is to use the basic constructive
geometry operations (union, intersection, difference, symmetric
difference, complement ...).

best regards,

> Best regards,
> Martin
> -------- 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:

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

View raw message