Subject: CGAL users discussion list
List archive
- From: gupta61 <>
- To:
- Subject: [cgal-discuss] AABB Tree bug - URGENT
- Date: Sun, 11 Mar 2012 14:08:07 -0700 (PDT)
Hi,
I am a student in UIUC currently working in the field of computational
mechanics. We use a lot of CGAL for computational geometry. We use AABB tree
to find out the intersections and other stuff. I was recently solving a
problem and I found a bug in AABB tree. I am attaching the figure of problem
with the message. In the figure "A" and "B" shows the bounding box
definition and "1" and "2" are the two segments to which I am trying to find
the intersections. No as you can see from the figure that it should not give
me any intersections for either of the segments. I also tried to create
"opposite segments" by changing the source and target point. Now it gives me
the different result from segment which should not be the case as the
segment created by changing the source and target points is still the same.
http://cgal-discuss.949826.n4.nabble.com/file/n4464619/testAABB.png
testAABB.png
I have tried with this problem with three versions of CGAL (3.8, 3.9,
4.0-beta1).
I also tried these kernels:
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
#include <CGAL/Simple_cartesian.h>
typedef CGAL::Simple_cartesian<double> Kernel;
and got the same wrong results...
I am also mentioning the code which we used for this.
#include <cstdlib>
#include <string>
#include <cstdio>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
#include <CGAL/intersections.h>
#include <CGAL/Bbox_3.h>
typedef CGAL::Point_3<Kernel> CGALPoint3;
typedef CGAL::Segment_3<Kernel> CGALSegment3;
int main(int argc, char** argv) {
CGAL::Bbox_3 bbox_elem_1834(2, 1.81818, 0.166666, 2.18182, 2.18182,
0.333333);
CGALPoint3 source_1834(2, 2, 1);
CGALPoint3 target_1834(2, 2, 0.75);
CGALSegment3 segment_query_1834( source_1834, target_1834 );
bool do_intersect_bbox = CGAL::do_intersect( bbox_elem_1834,
segment_query_1834 );
bool do_oppos_intersect_bbox = CGAL::do_intersect( bbox_elem_1834,
segment_query_1834.opposite() );
std::cout << "\n***TestAABB WARNING:"
<< "\n\tSegment intersect BBOX (0/1) = " << do_intersect_bbox
<< "\n\tSegment.opposite intersect BBOX (0/1) = " <<
do_oppos_intersect_bbox
<< "\n\tBBOX : " << bbox_elem_1834
<< "\n\tSegment query : " << segment_query_1834 << std::endl;
CGALPoint3 source_1834a(2, 2, 0.5);
CGALPoint3 target_1834a(2, 2, 0.75);
CGALSegment3 segment_query_1834a( source_1834a, target_1834a );
do_intersect_bbox = CGAL::do_intersect( bbox_elem_1834,
segment_query_1834a );
do_oppos_intersect_bbox = CGAL::do_intersect( bbox_elem_1834,
segment_query_1834a.opposite() );
std::cout << "\n***TestAABB WARNING:"
<< "\n\tSegment intersect BBOX (0/1) = " << do_intersect_bbox
<< "\n\tSegment.opposite intersect BBOX (0/1) = " <<
do_oppos_intersect_bbox
<< "\n\tBBOX : " << bbox_elem_1834
<< "\n\tSegment query : " << segment_query_1834a << std::endl;
return 0;
}
We got the following result which is obviously wrong as explained before.
***TestAABB WARNING:
Segment intersect BBOX (0/1) = 0
Segment.opposite intersect BBOX (0/1) = 1
BBOX : 2 1.81818 0.166666 2.18182 2.18182 0.333333
Segment query : 2 2 1 2 2 0.75
***TestAABB WARNING:
Segment intersect BBOX (0/1) = 1
Segment.opposite intersect BBOX (0/1) = 0
BBOX : 2 1.81818 0.166666 2.18182 2.18182 0.333333
Segment query : 2 2 0.5 2 2 0.75
Can you explain why I am getting this result or if you can confirm if it is
a bug ?
Thanks,
Piyush Gupta
UIUC
--
View this message in context:
http://cgal-discuss.949826.n4.nabble.com/AABB-Tree-bug-URGENT-tp4464619p4464619.html
Sent from the cgal-discuss mailing list archive at Nabble.com.
- [cgal-discuss] AABB Tree bug - URGENT, gupta61, 03/11/2012
- Re: [cgal-discuss] AABB Tree bug - URGENT, Marc Glisse, 03/11/2012
- [cgal-discuss] Re: AABB Tree bug - URGENT, gupta61, 03/13/2012
- Re: [cgal-discuss] Re: AABB Tree bug - URGENT, Marc Glisse, 03/13/2012
- [cgal-discuss] Re: AABB Tree bug - URGENT, gupta61, 03/13/2012
- Re: [cgal-discuss] Re: AABB Tree bug - URGENT, Marc Glisse, 03/13/2012
- Re: [cgal-discuss] Re: AABB Tree bug - URGENT, Laurent Rineau (GeometryFactory), 03/13/2012
- [cgal-discuss] Re: AABB Tree bug - URGENT, gupta61, 03/13/2012
- Re: [cgal-discuss] Re: AABB Tree bug - URGENT, Marc Glisse, 03/13/2012
- [cgal-discuss] Re: AABB Tree bug - URGENT, gupta61, 03/13/2012
- Re: [cgal-discuss] AABB Tree bug - URGENT, Doug Epps, 03/12/2012
- [cgal-discuss] Re: AABB Tree bug - URGENT, gupta61, 03/12/2012
- Re: [cgal-discuss] AABB Tree bug - URGENT, Marc Glisse, 03/11/2012
Archive powered by MHonArc 2.6.16.