commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Matt Juntunen <>
Subject Re: [geometry] GEOMTRY-32 Feedback Requested
Date Sat, 17 Aug 2019 02:57:53 GMT
Hi Gilles,

  1.  I just rebased from master so hopefully that fixed the repo weirdness.
  2.  The best place to start working with the new code is probably the RegionBSPTreeXD classes.
These are the replacements for the old IntervalsSet, PolygonsSet, and PolyhedronsSet classes.
I'm including a short example at the end of this email that shows some of the functionality.
  3.  Anything could be stored in the AttributeBSPTree nodes, but there isn't specific functionality
for computing the surface of portions of the tree, since that requires the concept of inside
and outside nodes, which is present in the RegionBSPTree subclasses but not here. Is that
what you were asking?
  4.  I was picturing adding both an examples module and a benchmark module a littler later,
along with a user guide.


DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-10);

// Create a pyramid region with its base on the xy plane and its apex
// along the positive z axis. The base is 2 units to a side and the pyramid
// is 2 units high.
Vector3D[] vertices = {
    Vector3D.of(1, 1, 0),
    Vector3D.of(1, -1, 0),
    Vector3D.of(-1, -1, 0),
    Vector3D.of(-1, 1, 0),
    Vector3D.of(0, 0, 2)

RegionBSPTree3D region = RegionBSPTree3D.builder(precision)

        // add the faces; these could alternatively be given as a 2d array
        .addIndexedFacet(0, 1, 2, 3)
        .addIndexedFacet(0, 4, 1)
        .addIndexedFacet(1, 4, 2)
        .addIndexedFacet(2, 4, 3)
        .addIndexedFacet(3, 4, 0)

System.out.println("# Pyramid" +
        "\nbarycenter= " + region.getBarycenter() +
        "\nvolume= " + region.getSize() +
        "\nsurface area= " + region.getBoundarySize());

// Create a unit box centered at the origin
RegionBSPTree3D box = RegionBSPTree3D.builder(precision)
        .addCenteredCube(Vector3D.ZERO, 1)

System.out.println("\n# Box" +
        "\nbarycenter= " + box.getBarycenter() +
        "\nvolume= " + box.getSize() +
        "\nsurface area= " + box.getBoundarySize());

// Move the box center to the pyramid center and lengthen it
// along the z-axis
AffineTransformMatrix3D mat = AffineTransformMatrix3D.identity()
        .scale(0.75, 0.75, 4);


System.out.println("\n# Transformed Box" +
        "\nbarycenter= " + box.getBarycenter() +
        "\nvolume= " + box.getSize() +
        "\nsurface area= " + box.getBoundarySize());

// Subtract the box from the pyramid. The pyramid is modified but
// the box is not.

System.out.println("\n# Pyramid with hole" +
        "\nbarycenter= " + region.getBarycenter() +
        "\nvolume= " + region.getSize() +
        "\nsurface area= " + region.getBoundarySize());

// Print out the vertices of the faces that make up the modified
// pyramid. The faces are not simplified; they represent the internal
// structure of the bsp tree.
System.out.println("\n# Faces");
for (ConvexSubPlane face : region.boundaries()) {

From: Gilles Sadowski <>
Sent: Friday, August 16, 2019 11:37 AM
To: Commons Developers List <>
Subject: Re: [geometry] GEOMTRY-32 Feedback Requested

Hello Matt.

Thanks for continuing to work on this.

Le jeu. 15 août 2019 à 17:56, Matt Juntunen
<> a écrit :
> Hi all,
> I've been working on the BSP tree refactor and general API cleanup for a while now and
I finally have the core and Euclidean classes complete. I have the code in a draft PR on github
[1] and I'm hoping to get as much feedback on it as I can.

There is a spurious change of ".travis.yml".  Also there are wrong EOL
in that file:
$ file .travis.yml
.travis.yml: ASCII text, with CRLF line terminators
Perhaps you should merge or rebase on "master".

> Everything is in its final state from my point of view with the exception of the spherical
module, which still needs to be switched over to the new API. Here are some highlights of
the new code:
>   *   More user-friendly API
>      *   Does not require users to make unchecked casts to implementation types.
>      *   BSP tree classes are much more powerful and easy to use. State is managed internally
so that users do not need to be experts in BSP trees to avoid corrupting the data structures.
>      *   Uses builder pattern instead of large factory methods to build complicated geometries.

That would suit me. ;-)
Actually, I'd like to try it with a simple geometry (i.e. build a sphere).
Where should I start looking?

>      *   Most classes are immutable.
>   *   A general-purpose AttributeBSPTree class is available so that users can associate
arbitrary data with spatial partitionings. I'm picturing this being used for spatial data
lookups, painter's algorithms, etc.

Can it be associated with a surface element?

>   *   All geometric types now support arbitrary transforms (eg, rotate, scale, translate,
etc) via the Transform interface.
>   *   The Transform interface is greatly simplified (GEOMETRY-24). It is now functional
and simply extends java.util.Function.


>   *   Better performance. My highly unsophisticated stdout benchmarking put the new code
at about 3-4 times faster than the old when performing boolean operations on 3D regions.


It would be great to create a maven module for systematizing the benchmarks;
see e.g. what is being done in "Commons RNG":;a=tree;f=commons-rng-examples/examples-jmh

A "commons-geometry-examples" module would be a place to collect
useful code, e.g. simple "howtos" (like the one I mentioned above) and
conversion routines from/to popular formats, without the requirement of
backwards compatibility (even between minor releases).


> Regards,
> Matt
> [1]

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

  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message