Updating the AABB-tree to work in both 2D and 3D #8057

sloriot · 2024-03-04T11:57:20Z

Make the AABB-tree dimension agnostic

Todo

Release Management

Affected package(s): AABB-tree
Issue(s) solved (if any):
Feature/Small Feature (if any): link, pre-approved by @MaelRL 22 April 2024
Link to compiled documentation (obligatory for small feature) link
License and copyright ownership: unchanged

github-actions · 2024-03-04T12:40:31Z

The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/8057/v0/Manual/index.html

afabri · 2024-03-04T14:22:54Z

AABB_tree/include/CGAL/AABB_traits_3.h

+// AABB_traits_intersection_base brings in the Intersection_distance predicate,
+// if GeomTraits is a model RayIntersectionGeomTraits.
+template <typename GeomTraits, bool ray_intersection_geom_traits=Is_ray_intersection_geomtraits<GeomTraits>::value>
+struct AABB_traits_intersection_base;


Don't they need the _3 suffix?

I only renamed to avoid the _2 that would be misleading in the context of this PR. If nothing can be shared it indeed should be _3

AABB_tree/include/CGAL/AABB_traits_3.h

Co-authored-by: Andreas Fabri <andreas.fabri@geometryfactory.com>

AABB_tree/doc/AABB_tree/PackageDescription.txt

afabri · 2024-03-04T16:12:10Z

AABB_tree/doc/AABB_tree/PackageDescription.txt

+- `CGAL::AABB_triangle_primitive_2<GeomTraits, Iterator, CacheDatum>`
+- `CGAL::AABB_segment_primitive_2<GeomTraits, Iterator, CacheDatum>`
+- `CGAL::AABB_triangle_primitive_3<GeomTraits, Iterator, CacheDatum>`
+- `CGAL::AABB_segment_primitive_3<GeomTraits, Iterator, CacheDatum>`
 - `CGAL::AABB_primitive<Id,ObjectPropertyMap,PointPropertyMap,ExternalPropertyMaps,CacheDatum>`
 - `CGAL::AABB_halfedge_graph_segment_primitive<HalfedgeGraph,Vpm,OneHalfedgeGraphPerTree,CacheDatum>`
 - `CGAL::AABB_face_graph_triangle_primitive<FaceGraph,Vpm,OneFaceGraphPerTree,CacheDatum>`


Here an equivalent would be useful when we shoot rays inside a polygon.

AABB_tree/doc/AABB_tree/Concepts/AABBGeomTraits_2.h

AABB_tree/doc/AABB_tree/Concepts/AABBRayIntersectionGeomTraits_2.h

AABB_tree/doc/AABB_tree/Concepts/AABBRayIntersectionGeomTraits_3.h

AABB_tree/doc/AABB_tree/Concepts/AABBRayIntersectionGeomTraits_2.h

AABB_tree/doc/AABB_tree/Concepts/AABBTraits.h

MaelRL · 2024-04-22T12:53:56Z

AABB_tree/doc/AABB_tree/Concepts/AABBTraits.h

@@ -145,21 +138,21 @@ typedef unspecified_type Compare_distance;

 /*!
 A functor object to compute closest point from the query on a primitive. Provides the operator:
-`Point_3 operator()(const Query& query, const Primitive& primitive, const Point_3 & closest);` which returns the closest point to `query`, among `closest` and all points of the primitive.
+`Point operator()(const Query& query, const Primitive& primitive, const Point & closest);` which returns the closest point to `query`, among `closest` and all points of the primitive.


Sorry, but even with the explanation it's not clear to me and I don't know how I would implement this.

We can put it aside because it's not really what the PR is about...

MaelRL · 2024-04-22T12:55:16Z

AABB_tree/doc/AABB_tree/PackageDescription.txt

@@ -5,12 +5,12 @@

 /*!
 \addtogroup PkgAABBTreeRef
-\cgalPkgDescriptionBegin{3D Fast Intersection and Distance Computation,PkgAABBTree}
+\cgalPkgDescriptionBegin{2D and 3D Fast Intersection and Distance Computation,PkgAABBTree}


Suggested change

\cgalPkgDescriptionBegin{2D and 3D Fast Intersection and Distance Computation,PkgAABBTree}

\cgalPkgDescriptionBegin{Fast Intersection and Distance Computation,PkgAABBTree}

WIth or without 2D and 3D seems fine. The AABBTree should be able to handle d dimensions.

Co-authored-by: Mael <mael.rouxel.labbe@geometryfactory.com>

sloriot · 2024-04-24T20:09:02Z

Successfully tested in CGAL-6.0-Ic-228

github-actions · 2024-04-25T07:05:57Z

This pull-request was previously marked with the label Tested, but has been modified with new commits. That label has been removed.

sloriot · 2024-05-06T07:21:06Z

Successfully tested in CGAL-6.0-Ic-235

lrineau · 2024-05-08T14:38:45Z

Successfully tested in CGAL-6.0-Ic-235

AABB_tree is really an important package for many CGAL packages, and for a lot of user code, including CGAL developers out-of-tree pieces of code.

As far as I can see, this package deprecates <CGAL/AABB_traits.h> and CGAL::AABB_traits, and we now have an template alias for backward compatibility.

template<typename GeomTraits, typename AABBPrimitive, typename BboxMap = Default>
using AABB_traits = AABB_traits_3<GeomTraits, AABBPrimitive, BboxMap>;

And similar for a new template classes about "primitives".

There are only two small test files testing the for deprecated names. Can we really be confident it is enough to trust that the compatibility is working well enough?

sloriot · 2024-05-10T07:23:57Z

If you first apply the boost::optional -> std::optional update in CGAL-5.6 examples, the code compiles.
This PR does not really break something. The "real" breaking change is that the concept AABBTraits now refines the SearchTraits concept (instead of SearchGeomTraits_3). It means that a user defined traits might not longer works (but it's kind of unlikely to happen). Also, the swig bindings will no longer compile as they are using some classes that were deprecated since many years. I'll do the update after the merge.

lrineau · 2024-05-23T15:08:13Z

If you first apply the boost::optional -> std::optional update in CGAL-5.6 examples, the code compiles. This PR does not really break something. The "real" breaking change is that the concept AABBTraits now refines the SearchTraits concept (instead of SearchGeomTraits_3). It means that a user defined traits might not longer works (but it's kind of unlikely to happen). Also, the swig bindings will no longer compile as they are using some classes that were deprecated since many years. I'll do the update after the merge.

@sloriot Can you please fix https://github.com/CGAL/cgal-swig-bindings?

See https://github.com/CGAL/cgal-swig-bindings/actions/runs/9144362571/job/25142119159#step:9:731

With all the downstream packagers testing our releases automatically, even the beta ones, that compilation error is a blocker for CGAL-6.0-beta1.

sloriot · 2024-05-24T15:08:53Z

If you first apply the boost::optional -> std::optional update in CGAL-5.6 examples, the code compiles. This PR does not really break something. The "real" breaking change is that the concept AABBTraits now refines the SearchTraits concept (instead of SearchGeomTraits_3). It means that a user defined traits might not longer works (but it's kind of unlikely to happen). Also, the swig bindings will no longer compile as they are using some classes that were deprecated since many years. I'll do the update after the merge.

@sloriot Can you please fix https://github.com/CGAL/cgal-swig-bindings?

See https://github.com/CGAL/cgal-swig-bindings/actions/runs/9144362571/job/25142119159#step:9:731

With all the downstream packagers testing our releases automatically, even the beta ones, that compilation error is a blocker for CGAL-6.0-beta1.

Done in CGAL/cgal-swig-bindings#270

start updating the AABB-tree to work in both 2D and 3D

006d46b

sloriot added Pkg::AABB_tree Small feature labels Mar 4, 2024

This comment was marked as outdated.

Sign in to view

sloriot added the Work in progress label Mar 4, 2024

This comment was marked as outdated.

Sign in to view

compatibility headers

4a482dd

This comment was marked as outdated.

Sign in to view

sloriot added 2 commits March 4, 2024 13:50

add missing files

2eff0eb

rename concept

26d40e7

afabri reviewed Mar 4, 2024

View reviewed changes

AABB_tree/include/CGAL/AABB_traits_3.h Outdated Show resolved Hide resolved

sloriot and others added 10 commits March 4, 2024 15:27

Update AABB_tree/include/CGAL/AABB_traits_3.h

ae0f114

Co-authored-by: Andreas Fabri <andreas.fabri@geometryfactory.com>

use Search_traits_adapter instead of Decorated_point

ee187c5

AABB_traits_3 is model of Search_traits

c4a1197

fix concept doc

32e68f8

more doc fixes

6453b08

Add Construct_projected_point_2::operator()(Segment_2,Point_2)

84362a2

Changes so that the 2D example compiles

26d8793

Typo in concept AABBGeomTraits_3

a76cc2b

whitespace

14efb2c

Add AABBGeomTraits_2

b34c63c

afabri reviewed Mar 4, 2024

View reviewed changes

AABB_tree/doc/AABB_tree/PackageDescription.txt Show resolved Hide resolved

afabri reviewed Mar 4, 2024

View reviewed changes

afabri added 5 commits March 4, 2024 19:31

Make Minkowski_sum_2 work

f0bdc2d

Replace deprecated classes

eb49100

Replace deprecated classes

b70a736

Add AABB_triangle_primitive_2

6c1185d

Replace deprecated classes

56ac3a5

update history

b49b2a8

sloriot removed the Work in progress label Apr 22, 2024

MaelRL reviewed Apr 22, 2024

View reviewed changes

MaelRL added pre-approved For pre-approved small features. After 15 days the feature will be accepted. Ready to be tested and removed Not yet approved The feature or pull-request has not yet been approved. labels Apr 22, 2024

Apply suggestions from code review

696683f

Co-authored-by: Mael <mael.rouxel.labbe@geometryfactory.com>

sloriot added Tested and removed Ready to be tested Under Testing labels Apr 24, 2024

doc fixes

4f5bcc6

github-actions bot removed the Tested label Apr 25, 2024

Fix tiny doc issues

6727f78

sloriot added Under Testing Accepted small feature and removed pre-approved For pre-approved small features. After 15 days the feature will be accepted. labels May 2, 2024

sloriot added Tested and removed Under Testing labels May 6, 2024

lrineau self-assigned this May 8, 2024

lrineau added the rm only: ready for master For the release team only: that indicates that a PR is about to be merged in 'master' label May 13, 2024

lrineau merged commit 022b19d into CGAL:master May 15, 2024
9 checks passed

lrineau removed the rm only: ready for master For the release team only: that indicates that a PR is about to be merged in 'master' label May 16, 2024

lrineau deleted the AABB_tree-2d_and_3d branch May 16, 2024 10:26

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Updating the AABB-tree to work in both 2D and 3D #8057

Updating the AABB-tree to work in both 2D and 3D #8057

sloriot commented Mar 4, 2024 •

edited by lrineau

Loading

This comment was marked as outdated.

This comment was marked as outdated.

This comment was marked as outdated.

github-actions bot commented Mar 4, 2024

afabri Mar 4, 2024

sloriot Mar 4, 2024

afabri Mar 4, 2024

MaelRL Apr 22, 2024

MaelRL Apr 22, 2024

soesau Apr 22, 2024

sloriot commented Apr 24, 2024

github-actions bot commented Apr 25, 2024

sloriot commented May 6, 2024

lrineau commented May 8, 2024

sloriot commented May 10, 2024

lrineau commented May 23, 2024 •

edited

Loading

sloriot commented May 24, 2024

	\cgalPkgDescriptionBegin{2D and 3D Fast Intersection and Distance Computation,PkgAABBTree}
	\cgalPkgDescriptionBegin{Fast Intersection and Distance Computation,PkgAABBTree}

Updating the AABB-tree to work in both 2D and 3D #8057

Updating the AABB-tree to work in both 2D and 3D #8057

Conversation

sloriot commented Mar 4, 2024 • edited by lrineau Loading

Todo

Release Management

This comment was marked as outdated.

This comment was marked as outdated.

This comment was marked as outdated.

github-actions bot commented Mar 4, 2024

afabri Mar 4, 2024

Choose a reason for hiding this comment

sloriot Mar 4, 2024

Choose a reason for hiding this comment

afabri Mar 4, 2024

Choose a reason for hiding this comment

MaelRL Apr 22, 2024

Choose a reason for hiding this comment

MaelRL Apr 22, 2024

Choose a reason for hiding this comment

soesau Apr 22, 2024

Choose a reason for hiding this comment

sloriot commented Apr 24, 2024

github-actions bot commented Apr 25, 2024

sloriot commented May 6, 2024

lrineau commented May 8, 2024

sloriot commented May 10, 2024

lrineau commented May 23, 2024 • edited Loading

sloriot commented May 24, 2024

sloriot commented Mar 4, 2024 •

edited by lrineau

Loading

lrineau commented May 23, 2024 •

edited

Loading