You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Sven Rathgeber <sv...@web.de> on 2020/06/10 07:28:40 UTC
[geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D ?)
Hi Matt,
first of all:
Thanks a lot for all your work (rewrite) on the library !!!!
Could you give me a hint how to make the transition from PolyhedronSet
to the new data structures ?
This is my current code:
public static PolyhedronsSet createPrism(
List< Position2D > basePolygon,
int upperBound,
int lowerBound )
{
List< Vector3D > vertices = createVertices( polygon, upperBound,
lowerBound );
int[][] facets = createFacets( polygon );
return new PolyhedronsSet( vertices, Arrays.asList( facets ),
PRECISION_CONTEXT );
}
Cheers. Sven
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D ?)
Posted by Gilles Sadowski <gi...@gmail.com>.
Hello.
Le mer. 17 juin 2020 à 04:22, Matt Juntunen
<ma...@hotmail.com> a écrit :
>
> Hi Sven,
>
> If the createVertices and createFacets methods don't construct convex polygons then perhaps you could bypass them completely and just construct the tree directly from the boundaries. Assuming that I understand your use case correctly, the following methods should do what you want:
>
> private RegionBSPTree3D createPrism(List<Vector2D> polygon,
> double upperBound, double lowerBound,
> DoublePrecisionContext precision) {
>
> EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, lowerBound),
> Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, precision);
>
> Vector3D extrudeVector = plane.getNormal().withNorm(upperBound - lowerBound);
>
> return extrudePolygon(polygon, plane, extrudeVector, precision);
> }
>
> private RegionBSPTree3D extrudePolygon(List<Vector2D> polygon, EmbeddingPlane plane,
> Vector3D extrudeVector, DoublePrecisionContext precision) {
>
> List<Vector3D> basePoints = plane.toSpace(polygon);
> List<Vector3D> extrudedPoints = basePoints.stream()
> .map(extrudeVector::add)
> .collect(Collectors.toList());
>
> RegionBSPTree3D tree = RegionBSPTree3D.empty();
>
> // treat the plane as the top and the extruded plane as the bottom;
> // we'll invert the tree at the end if needed
> tree.insert(plane.span()); // top
> tree.insert(Planes.fromPointAndNormal(
> plane.getOrigin().add(extrudeVector),
> plane.getNormal().negate(),
> precision).span()); // bottom
>
> // create the sides of the prism
> int size = polygon.size();
> for (int i = 0; i < size; ++i) {
> tree.insert(Planes.convexPolygonFromVertices(Arrays.asList(
> basePoints.get(i),
> extrudedPoints.get(i),
> extrudedPoints.get((i + 1) % size),
> basePoints.get((i + 1) % size)
> ), precision));
> }
>
> // complement the tree if the "top" wasn't actually the top
> if (plane.getNormal().dot(extrudeVector) > 0) {
> tree.complement();
> }
>
> return tree;
> }
Would this belong to the user guide?
Regards,
Gilles
> Note that these methods assume that the polygon contains at least 3 unique vertices, the first vertex is not repeated at the end, and that the upper and lower bounds are not equal.
>
> Hopefully this helps.
>
> Regards,
> Matt
>
> ________________________________
> From: Sven Rathgeber <sv...@web.de>
> Sent: Tuesday, June 16, 2020 3:46 AM
> To: Commons Developers List <de...@commons.apache.org>
> Subject: Re: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D ?)
>
> Hi Matt,
>
> > 2. Yes, the LinecastPoint3D object that you get from linecasting
> contains the intersection point as well as the surface normal at the
> point of intersection.
>
> thanks - that did the job and I could do the whole refactoring, but the
> tests fail.
>
> We used the PolyHedronsSet to model non-convex regions and that worked well.
>
> Now the "indexedConvexPolygons" is strict and forbids that (walk your
> talk :) ).
>
> Is there a way to handle non-convex regions ?
>
> Regards,
>
> Sven
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D
?)
Posted by Matt Juntunen <ma...@hotmail.com>.
Glad to hear it, Sven!
Gilles, this could definitely go in the user documentation. I may include it somewhere in the bsp/csg tutorial.
-Matt
________________________________
From: Sven Rathgeber <sv...@web.de>
Sent: Wednesday, June 17, 2020 9:38 AM
To: Commons Developers List <de...@commons.apache.org>
Subject: Re: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D ?)
Hi Matt,
yes !!! My refactoring is done. All the tests work fine.
(I have added one example of a non-convex structure (horseshoe))
Thank you.
Regards.
Sven
/*
------------------------+
| |
| |
| |
| +----------------|
| |
| | x (1.5, 1.5, 0.5) Outside
| |-----------------+
| |
| |
+---------------------+
*/
@Test
public void outsideHorseshoe()
{
List< Vector2D > vertices2D = new ArrayList<>();
// some kind of a horseshoe
vertices2D.add( Vector2D.of( 0, 0 ) );
vertices2D.add( Vector2D.of( 3, 0 ) );
vertices2D.add( Vector2D.of( 3, 1 ) );
vertices2D.add( Vector2D.of( 1, 1 ) );
vertices2D.add( Vector2D.of( 1, 2 ) );
vertices2D.add( Vector2D.of( 3, 2 ) );
vertices2D.add( Vector2D.of( 3, 3 ) );
vertices2D.add( Vector2D.of( 0, 3 ) );
RegionBSPTree3D horseshoe = createPrism( vertices2D, 1, 0 );
assertFalse( horseshoe.contains( Vector3D.of( 1.5, 1.5, 0.5 ) ) );
}
On 6/17/20 4:21 AM, Matt Juntunen wrote:
> Hi Sven,
>
> If the createVertices and createFacets methods don't construct convex polygons then perhaps you could bypass them completely and just construct the tree directly from the boundaries. Assuming that I understand your use case correctly, the following methods should do what you want:
>
> private RegionBSPTree3D createPrism(List<Vector2D> polygon,
> double upperBound, double lowerBound,
> DoublePrecisionContext precision) {
>
> EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, lowerBound),
> Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, precision);
>
> Vector3D extrudeVector = plane.getNormal().withNorm(upperBound - lowerBound);
>
> return extrudePolygon(polygon, plane, extrudeVector, precision);
> }
>
> private RegionBSPTree3D extrudePolygon(List<Vector2D> polygon, EmbeddingPlane plane,
> Vector3D extrudeVector, DoublePrecisionContext precision) {
>
> List<Vector3D> basePoints = plane.toSpace(polygon);
> List<Vector3D> extrudedPoints = basePoints.stream()
> .map(extrudeVector::add)
> .collect(Collectors.toList());
>
> RegionBSPTree3D tree = RegionBSPTree3D.empty();
>
> // treat the plane as the top and the extruded plane as the bottom;
> // we'll invert the tree at the end if needed
> tree.insert(plane.span()); // top
> tree.insert(Planes.fromPointAndNormal(
> plane.getOrigin().add(extrudeVector),
> plane.getNormal().negate(),
> precision).span()); // bottom
>
> // create the sides of the prism
> int size = polygon.size();
> for (int i = 0; i < size; ++i) {
> tree.insert(Planes.convexPolygonFromVertices(Arrays.asList(
> basePoints.get(i),
> extrudedPoints.get(i),
> extrudedPoints.get((i + 1) % size),
> basePoints.get((i + 1) % size)
> ), precision));
> }
>
> // complement the tree if the "top" wasn't actually the top
> if (plane.getNormal().dot(extrudeVector) > 0) {
> tree.complement();
> }
>
> return tree;
> }
>
> Note that these methods assume that the polygon contains at least 3 unique vertices, the first vertex is not repeated at the end, and that the upper and lower bounds are not equal.
>
> Hopefully this helps.
>
> Regards,
> Matt
>
> ________________________________
> From: Sven Rathgeber<sv...@web.de>
> Sent: Tuesday, June 16, 2020 3:46 AM
> To: Commons Developers List<de...@commons.apache.org>
> Subject: Re: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D ?)
>
> Hi Matt,
>
> > 2. Yes, the LinecastPoint3D object that you get from linecasting
> contains the intersection point as well as the surface normal at the
> point of intersection.
>
> thanks - that did the job and I could do the whole refactoring, but the
> tests fail.
>
> We used the PolyHedronsSet to model non-convex regions and that worked well.
>
> Now the "indexedConvexPolygons" is strict and forbids that (walk your
> talk :) ).
>
> Is there a way to handle non-convex regions ?
>
> Regards,
>
> Sven
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:dev-unsubscribe@commons.apache.org
> For additional commands, e-mail:dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D
?)
Posted by Sven Rathgeber <sv...@web.de>.
Hi Matt,
yes !!! My refactoring is done. All the tests work fine.
(I have added one example of a non-convex structure (horseshoe))
Thank you.
Regards.
Sven
/*
------------------------+
| |
| |
| |
| +----------------|
| |
| | x (1.5, 1.5, 0.5) Outside
| |-----------------+
| |
| |
+---------------------+
*/
@Test
public void outsideHorseshoe()
{
List< Vector2D > vertices2D = new ArrayList<>();
// some kind of a horseshoe
vertices2D.add( Vector2D.of( 0, 0 ) );
vertices2D.add( Vector2D.of( 3, 0 ) );
vertices2D.add( Vector2D.of( 3, 1 ) );
vertices2D.add( Vector2D.of( 1, 1 ) );
vertices2D.add( Vector2D.of( 1, 2 ) );
vertices2D.add( Vector2D.of( 3, 2 ) );
vertices2D.add( Vector2D.of( 3, 3 ) );
vertices2D.add( Vector2D.of( 0, 3 ) );
RegionBSPTree3D horseshoe = createPrism( vertices2D, 1, 0 );
assertFalse( horseshoe.contains( Vector3D.of( 1.5, 1.5, 0.5 ) ) );
}
On 6/17/20 4:21 AM, Matt Juntunen wrote:
> Hi Sven,
>
> If the createVertices and createFacets methods don't construct convex polygons then perhaps you could bypass them completely and just construct the tree directly from the boundaries. Assuming that I understand your use case correctly, the following methods should do what you want:
>
> private RegionBSPTree3D createPrism(List<Vector2D> polygon,
> double upperBound, double lowerBound,
> DoublePrecisionContext precision) {
>
> EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, lowerBound),
> Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, precision);
>
> Vector3D extrudeVector = plane.getNormal().withNorm(upperBound - lowerBound);
>
> return extrudePolygon(polygon, plane, extrudeVector, precision);
> }
>
> private RegionBSPTree3D extrudePolygon(List<Vector2D> polygon, EmbeddingPlane plane,
> Vector3D extrudeVector, DoublePrecisionContext precision) {
>
> List<Vector3D> basePoints = plane.toSpace(polygon);
> List<Vector3D> extrudedPoints = basePoints.stream()
> .map(extrudeVector::add)
> .collect(Collectors.toList());
>
> RegionBSPTree3D tree = RegionBSPTree3D.empty();
>
> // treat the plane as the top and the extruded plane as the bottom;
> // we'll invert the tree at the end if needed
> tree.insert(plane.span()); // top
> tree.insert(Planes.fromPointAndNormal(
> plane.getOrigin().add(extrudeVector),
> plane.getNormal().negate(),
> precision).span()); // bottom
>
> // create the sides of the prism
> int size = polygon.size();
> for (int i = 0; i < size; ++i) {
> tree.insert(Planes.convexPolygonFromVertices(Arrays.asList(
> basePoints.get(i),
> extrudedPoints.get(i),
> extrudedPoints.get((i + 1) % size),
> basePoints.get((i + 1) % size)
> ), precision));
> }
>
> // complement the tree if the "top" wasn't actually the top
> if (plane.getNormal().dot(extrudeVector) > 0) {
> tree.complement();
> }
>
> return tree;
> }
>
> Note that these methods assume that the polygon contains at least 3 unique vertices, the first vertex is not repeated at the end, and that the upper and lower bounds are not equal.
>
> Hopefully this helps.
>
> Regards,
> Matt
>
> ________________________________
> From: Sven Rathgeber<sv...@web.de>
> Sent: Tuesday, June 16, 2020 3:46 AM
> To: Commons Developers List<de...@commons.apache.org>
> Subject: Re: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D ?)
>
> Hi Matt,
>
> > 2. Yes, the LinecastPoint3D object that you get from linecasting
> contains the intersection point as well as the surface normal at the
> point of intersection.
>
> thanks - that did the job and I could do the whole refactoring, but the
> tests fail.
>
> We used the PolyHedronsSet to model non-convex regions and that worked well.
>
> Now the "indexedConvexPolygons" is strict and forbids that (walk your
> talk :) ).
>
> Is there a way to handle non-convex regions ?
>
> Regards,
>
> Sven
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:dev-unsubscribe@commons.apache.org
> For additional commands, e-mail:dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D
?)
Posted by Matt Juntunen <ma...@hotmail.com>.
Hi Sven,
If the createVertices and createFacets methods don't construct convex polygons then perhaps you could bypass them completely and just construct the tree directly from the boundaries. Assuming that I understand your use case correctly, the following methods should do what you want:
private RegionBSPTree3D createPrism(List<Vector2D> polygon,
double upperBound, double lowerBound,
DoublePrecisionContext precision) {
EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, lowerBound),
Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, precision);
Vector3D extrudeVector = plane.getNormal().withNorm(upperBound - lowerBound);
return extrudePolygon(polygon, plane, extrudeVector, precision);
}
private RegionBSPTree3D extrudePolygon(List<Vector2D> polygon, EmbeddingPlane plane,
Vector3D extrudeVector, DoublePrecisionContext precision) {
List<Vector3D> basePoints = plane.toSpace(polygon);
List<Vector3D> extrudedPoints = basePoints.stream()
.map(extrudeVector::add)
.collect(Collectors.toList());
RegionBSPTree3D tree = RegionBSPTree3D.empty();
// treat the plane as the top and the extruded plane as the bottom;
// we'll invert the tree at the end if needed
tree.insert(plane.span()); // top
tree.insert(Planes.fromPointAndNormal(
plane.getOrigin().add(extrudeVector),
plane.getNormal().negate(),
precision).span()); // bottom
// create the sides of the prism
int size = polygon.size();
for (int i = 0; i < size; ++i) {
tree.insert(Planes.convexPolygonFromVertices(Arrays.asList(
basePoints.get(i),
extrudedPoints.get(i),
extrudedPoints.get((i + 1) % size),
basePoints.get((i + 1) % size)
), precision));
}
// complement the tree if the "top" wasn't actually the top
if (plane.getNormal().dot(extrudeVector) > 0) {
tree.complement();
}
return tree;
}
Note that these methods assume that the polygon contains at least 3 unique vertices, the first vertex is not repeated at the end, and that the upper and lower bounds are not equal.
Hopefully this helps.
Regards,
Matt
________________________________
From: Sven Rathgeber <sv...@web.de>
Sent: Tuesday, June 16, 2020 3:46 AM
To: Commons Developers List <de...@commons.apache.org>
Subject: Re: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D ?)
Hi Matt,
> 2. Yes, the LinecastPoint3D object that you get from linecasting
contains the intersection point as well as the surface normal at the
point of intersection.
thanks - that did the job and I could do the whole refactoring, but the
tests fail.
We used the PolyHedronsSet to model non-convex regions and that worked well.
Now the "indexedConvexPolygons" is strict and forbids that (walk your
talk :) ).
Is there a way to handle non-convex regions ?
Regards,
Sven
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D
?)
Posted by Sven Rathgeber <sv...@web.de>.
Hi Matt,
> 2. Yes, the LinecastPoint3D object that you get from linecasting
contains the intersection point as well as the surface normal at the
point of intersection.
thanks - that did the job and I could do the whole refactoring, but the
tests fail.
We used the PolyHedronsSet to model non-convex regions and that worked well.
Now the "indexedConvexPolygons" is strict and forbids that (walk your
talk :) ).
Is there a way to handle non-convex regions ?
Regards,
Sven
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D
?)
Posted by Matt Juntunen <ma...@hotmail.com>.
Hi Sven,
1. Yes, you can use RegionBSPTree3D.linecast to get the intersection of a line or line subset with the boundaries of a region. That is the intended use case. "Linecasting" is a superset of "raycasting". [1]
2. Yes, the LinecastPoint3D object that you get from linecasting contains the intersection point as well as the surface normal at the point of intersection. You can use those to construct a plane tangent to the region surface with "Planes.fromPointAndNormal(linecastPt.getPoint(), linecastPt.getNormal(), precision);"
On a related note, I found an issue with the BSP tree code that makes the approach I suggested of subdividing the tree prior to boundary insertion not work when one or more of the inserted boundaries lies on one of the subdivisions. I'm working through it now.
Let me know how the rest of the refactoring goes!
Regards,
Matt
[1] https://en.wikipedia.org/wiki/Ray_casting
________________________________
From: Sven Rathgeber <sv...@web.de>
Sent: Sunday, June 14, 2020 11:32 AM
To: Commons Developers List <de...@commons.apache.org>; Matt Juntunen <ma...@hotmail.com>
Subject: Re: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D ?)
Hi Matt,
thanks for the help. With your hint I could refactor a lot of the old
code. There are two questions left:
I used the PolyhedronSet to determine the intersections with a line.
First I got a Plane and then I had to find the intersection with the Plane.
My code makes use of both, the Plane and the intersection.
1. Can I use RegionBSPTree3D.linecast for the intersection part ?
2. Is there a way to find out the intersected Plane ?
Regards,
Sven
On 6/11/20 3:57 AM, Matt Juntunen wrote:
> Hi Sven,
>
> No problem! To answer your question in the subject line, yes, RegionBSPTree3D is the replacement for the old PolyhedronsSet. They both represent 3D regions using BSP trees. As for your code example, you're probably going to want to use Planes.indexedConvexPolygons() [1] or Planes.indexedTriangles() [2] to create a list of ConvexPolygon3D instances and then use those to create a RegionBSPTree3D:
>
> public static PolyhedronsSet createPrism(
> List<Position2D> basePolygon,
> int upperBound,
> int lowerBound) {
>
> List<Vector3D> vertices = createVertices(polygon, upperBound, lowerBound);
> int[][] facets = createFacets(polygon);
>
> List<ConvexPolygon3D> polys = Planes.indexedConvexPolygons(vertices, facets, PRECISION_CONTEXT);
>
> return RegionBSPTree3D.from(polys);
> }
>
> There is actually a unit test here [3] that does exactly this.
>
> Note that if the region is convex and you have a large number of polygons to insert, the resulting tree will be highly unbalanced and will suffer from poor performance. To help with this, you can insert partitions into the BSP tree that do not affect the represented region but help keep the tree balanced and shallow. Here's an example:
>
> public static PolyhedronsSet createPrism(
> List<Position2D> basePolygon,
> int upperBound,
> int lowerBound) {
>
> List<Vector3D> vertices = createVertices(polygon, upperBound, lowerBound);
> int[][] facets = createFacets(polygon);
>
> // compute the region bounds and centroid
> Bounds3D bounds = Bounds3D.from(vertices);
> Vector3D centroid = bounds.getCentroid();
>
> // create an empty region
> RegionBSPTree3D tree = RegionBSPTree3D.empty();
>
> // insert structural partitions into the tree (RegionCutRule.INHERIT) at the centroid; the
> // resulting tree has internal partitions but the represented region is still empty
> tree.insert(Planes.fromPointAndNormal(center, Vector3D.Unit.PLUS_X, PRECISION_CONTEXT).span(), RegionCutRule.INHERIT);
> tree.insert(Planes.fromPointAndNormal(center, Vector3D.Unit.PLUS_Y, PRECISION_CONTEXT).span(), RegionCutRule.INHERIT);
> tree.insert(Planes.fromPointAndNormal(center, Vector3D.Unit.PLUS_Z, PRECISION_CONTEXT).span(), RegionCutRule.INHERIT);
>
> // create and insert the region boundaries
> List<ConvexPolygon3D> polys = Planes.indexedConvexPolygons(vertices, facets, PRECISION_CONTEXT);
> tree.insert(polys);
>
> return tree;
> }
>
> I've created a RegionBSPTree.subdivided() factory method in my current working branch that abstracts this internal partitioning so this should be less verbose in the near future.
>
> Let me know if you have any other questions or run into issues. I'm working now on a tutorial focusing on the BSP tree usage (GEOMETRY-95) so if you find anything that's confusing or messed up, I can try to address it.
>
>
> Regards,
> Matt
>
> [1] https://github.com/apache/commons-geometry/blob/master/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Planes.java#L295
> [2] https://github.com/apache/commons-geometry/blob/master/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Planes.java#L234
> [3] https://github.com/apache/commons-geometry/blob/master/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PlanesTest.java#L448
>
>
> ________________________________
> From: Sven Rathgeber <sv...@web.de>
> Sent: Wednesday, June 10, 2020 3:28 AM
> To: Commons Developers List <de...@commons.apache.org>
> Subject: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D ?)
>
> Hi Matt,
>
> first of all:
>
> Thanks a lot for all your work (rewrite) on the library !!!!
>
> Could you give me a hint how to make the transition from PolyhedronSet
> to the new data structures ?
>
> This is my current code:
>
> public static PolyhedronsSet createPrism(
> List< Position2D > basePolygon,
> int upperBound,
> int lowerBound )
> {
> List< Vector3D > vertices = createVertices( polygon, upperBound,
> lowerBound );
> int[][] facets = createFacets( polygon );
>
> return new PolyhedronsSet( vertices, Arrays.asList( facets ),
> PRECISION_CONTEXT );
> }
>
> Cheers. Sven
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
Re: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D
?)
Posted by Sven Rathgeber <sv...@web.de>.
Hi Matt,
thanks for the help. With your hint I could refactor a lot of the old
code. There are two questions left:
I used the PolyhedronSet to determine the intersections with a line.
First I got a Plane and then I had to find the intersection with the Plane.
My code makes use of both, the Plane and the intersection.
1. Can I use RegionBSPTree3D.linecast for the intersection part ?
2. Is there a way to find out the intersected Plane ?
Regards,
Sven
On 6/11/20 3:57 AM, Matt Juntunen wrote:
> Hi Sven,
>
> No problem! To answer your question in the subject line, yes, RegionBSPTree3D is the replacement for the old PolyhedronsSet. They both represent 3D regions using BSP trees. As for your code example, you're probably going to want to use Planes.indexedConvexPolygons() [1] or Planes.indexedTriangles() [2] to create a list of ConvexPolygon3D instances and then use those to create a RegionBSPTree3D:
>
> public static PolyhedronsSet createPrism(
> List<Position2D> basePolygon,
> int upperBound,
> int lowerBound) {
>
> List<Vector3D> vertices = createVertices(polygon, upperBound, lowerBound);
> int[][] facets = createFacets(polygon);
>
> List<ConvexPolygon3D> polys = Planes.indexedConvexPolygons(vertices, facets, PRECISION_CONTEXT);
>
> return RegionBSPTree3D.from(polys);
> }
>
> There is actually a unit test here [3] that does exactly this.
>
> Note that if the region is convex and you have a large number of polygons to insert, the resulting tree will be highly unbalanced and will suffer from poor performance. To help with this, you can insert partitions into the BSP tree that do not affect the represented region but help keep the tree balanced and shallow. Here's an example:
>
> public static PolyhedronsSet createPrism(
> List<Position2D> basePolygon,
> int upperBound,
> int lowerBound) {
>
> List<Vector3D> vertices = createVertices(polygon, upperBound, lowerBound);
> int[][] facets = createFacets(polygon);
>
> // compute the region bounds and centroid
> Bounds3D bounds = Bounds3D.from(vertices);
> Vector3D centroid = bounds.getCentroid();
>
> // create an empty region
> RegionBSPTree3D tree = RegionBSPTree3D.empty();
>
> // insert structural partitions into the tree (RegionCutRule.INHERIT) at the centroid; the
> // resulting tree has internal partitions but the represented region is still empty
> tree.insert(Planes.fromPointAndNormal(center, Vector3D.Unit.PLUS_X, PRECISION_CONTEXT).span(), RegionCutRule.INHERIT);
> tree.insert(Planes.fromPointAndNormal(center, Vector3D.Unit.PLUS_Y, PRECISION_CONTEXT).span(), RegionCutRule.INHERIT);
> tree.insert(Planes.fromPointAndNormal(center, Vector3D.Unit.PLUS_Z, PRECISION_CONTEXT).span(), RegionCutRule.INHERIT);
>
> // create and insert the region boundaries
> List<ConvexPolygon3D> polys = Planes.indexedConvexPolygons(vertices, facets, PRECISION_CONTEXT);
> tree.insert(polys);
>
> return tree;
> }
>
> I've created a RegionBSPTree.subdivided() factory method in my current working branch that abstracts this internal partitioning so this should be less verbose in the near future.
>
> Let me know if you have any other questions or run into issues. I'm working now on a tutorial focusing on the BSP tree usage (GEOMETRY-95) so if you find anything that's confusing or messed up, I can try to address it.
>
>
> Regards,
> Matt
>
> [1] https://github.com/apache/commons-geometry/blob/master/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Planes.java#L295
> [2] https://github.com/apache/commons-geometry/blob/master/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Planes.java#L234
> [3] https://github.com/apache/commons-geometry/blob/master/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PlanesTest.java#L448
>
>
> ________________________________
> From: Sven Rathgeber <sv...@web.de>
> Sent: Wednesday, June 10, 2020 3:28 AM
> To: Commons Developers List <de...@commons.apache.org>
> Subject: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D ?)
>
> Hi Matt,
>
> first of all:
>
> Thanks a lot for all your work (rewrite) on the library !!!!
>
> Could you give me a hint how to make the transition from PolyhedronSet
> to the new data structures ?
>
> This is my current code:
>
> public static PolyhedronsSet createPrism(
> List< Position2D > basePolygon,
> int upperBound,
> int lowerBound )
> {
> List< Vector3D > vertices = createVertices( polygon, upperBound,
> lowerBound );
> int[][] facets = createFacets( polygon );
>
> return new PolyhedronsSet( vertices, Arrays.asList( facets ),
> PRECISION_CONTEXT );
> }
>
> Cheers. Sven
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D
?)
Posted by Matt Juntunen <ma...@hotmail.com>.
Hi Sven,
No problem! To answer your question in the subject line, yes, RegionBSPTree3D is the replacement for the old PolyhedronsSet. They both represent 3D regions using BSP trees. As for your code example, you're probably going to want to use Planes.indexedConvexPolygons() [1] or Planes.indexedTriangles() [2] to create a list of ConvexPolygon3D instances and then use those to create a RegionBSPTree3D:
public static PolyhedronsSet createPrism(
List<Position2D> basePolygon,
int upperBound,
int lowerBound) {
List<Vector3D> vertices = createVertices(polygon, upperBound, lowerBound);
int[][] facets = createFacets(polygon);
List<ConvexPolygon3D> polys = Planes.indexedConvexPolygons(vertices, facets, PRECISION_CONTEXT);
return RegionBSPTree3D.from(polys);
}
There is actually a unit test here [3] that does exactly this.
Note that if the region is convex and you have a large number of polygons to insert, the resulting tree will be highly unbalanced and will suffer from poor performance. To help with this, you can insert partitions into the BSP tree that do not affect the represented region but help keep the tree balanced and shallow. Here's an example:
public static PolyhedronsSet createPrism(
List<Position2D> basePolygon,
int upperBound,
int lowerBound) {
List<Vector3D> vertices = createVertices(polygon, upperBound, lowerBound);
int[][] facets = createFacets(polygon);
// compute the region bounds and centroid
Bounds3D bounds = Bounds3D.from(vertices);
Vector3D centroid = bounds.getCentroid();
// create an empty region
RegionBSPTree3D tree = RegionBSPTree3D.empty();
// insert structural partitions into the tree (RegionCutRule.INHERIT) at the centroid; the
// resulting tree has internal partitions but the represented region is still empty
tree.insert(Planes.fromPointAndNormal(center, Vector3D.Unit.PLUS_X, PRECISION_CONTEXT).span(), RegionCutRule.INHERIT);
tree.insert(Planes.fromPointAndNormal(center, Vector3D.Unit.PLUS_Y, PRECISION_CONTEXT).span(), RegionCutRule.INHERIT);
tree.insert(Planes.fromPointAndNormal(center, Vector3D.Unit.PLUS_Z, PRECISION_CONTEXT).span(), RegionCutRule.INHERIT);
// create and insert the region boundaries
List<ConvexPolygon3D> polys = Planes.indexedConvexPolygons(vertices, facets, PRECISION_CONTEXT);
tree.insert(polys);
return tree;
}
I've created a RegionBSPTree.subdivided() factory method in my current working branch that abstracts this internal partitioning so this should be less verbose in the near future.
Let me know if you have any other questions or run into issues. I'm working now on a tutorial focusing on the BSP tree usage (GEOMETRY-95) so if you find anything that's confusing or messed up, I can try to address it.
Regards,
Matt
[1] https://github.com/apache/commons-geometry/blob/master/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Planes.java#L295
[2] https://github.com/apache/commons-geometry/blob/master/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Planes.java#L234
[3] https://github.com/apache/commons-geometry/blob/master/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PlanesTest.java#L448
________________________________
From: Sven Rathgeber <sv...@web.de>
Sent: Wednesday, June 10, 2020 3:28 AM
To: Commons Developers List <de...@commons.apache.org>
Subject: [geometry] Transition from PolyhedronSet to ??? (RegionBSPTree3D ?)
Hi Matt,
first of all:
Thanks a lot for all your work (rewrite) on the library !!!!
Could you give me a hint how to make the transition from PolyhedronSet
to the new data structures ?
This is my current code:
public static PolyhedronsSet createPrism(
List< Position2D > basePolygon,
int upperBound,
int lowerBound )
{
List< Vector3D > vertices = createVertices( polygon, upperBound,
lowerBound );
int[][] facets = createFacets( polygon );
return new PolyhedronsSet( vertices, Arrays.asList( facets ),
PRECISION_CONTEXT );
}
Cheers. Sven
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org