CGAL users discussion list

[Doug Epps <>]

Hi Plyush,

I'm by no means an expert at CGAL, but thought I'd send this query on in the 
hopes it helps.

Are you sure you're building the bbox_elem correctly ?  I've seen many many 
hard to find bugs from people using
bboxes in the form (xMin, yMin, zMin, xMax, yMax, zMax) when really their 
bbox constrcutor wanted (xMin, xMax, yMin, yMax, zMin, zMax).

(or the other way around).

since you said 'URGENT' maybe we'll get lucky.

-doug

On Mar 11, 2012, at 2:08 PM, gupta61 wrote:

> 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.
> 
> -- 
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>