CGAL users discussion list

["Tomislav Maric" <>]

Thanks a lot for the explanation. I think I get it now, finally. Instead of 
using the triangle 
geometry/boxes I am dealing directly with orthogonal range searching, in case 
I can 
build a space partitioning tree from my mesh.  I'll do some reading on this 
topic, 
since it is completely new to me (I have found a book of DeBerg on 
Computational Geometry). 

One question: k-d tree in CGAL is based on a static datastructure (CGAL 
manual)? 

I am asking because there will be mesh refinement done for the hexa-mesh, in 
which case, 
the structure of the tree should change or I should throw away the tree and 
create a completely 
new one.. I am counting on having hexa meshes in sizes of milion of cells, 
and the code should run
in parallel (task based, OpenMPI, not multithread) on a cluster at some 
point. 

The refinement is octree based, maybe I can use this data structure as well 
for the task of range
searching... I have to read "a bit" first. :) 

Thanks again, 
Tomislav

> ----- Original Message -----
> From: Sebastien Loriot (GeometryFactory)
> Sent: 02/29/12 06:34 PM
> To: 
> 
> Subject: Re: [cgal-discuss] Polyhedron_3 points / Array of boxes
> 
> I understood that you hexa-mesh an be represented as a kd-tree 
> (http://en.wikipedia.org/wiki/K-d_tree). If this is the case, then
> for each point you'll make at most the depth of the tree requests to
> find the correct cube.
> 
> Sebastien
> 
> 
> On 02/28/2012 08:24 PM, Tomislav Maric wrote:
> > Thank you very much for your help! :)
> >
> > I have to apologize for asking simple (stupid) questions, but I'm 
> > completely new to CGAL / Comp Geometry.
> >
> > Not sure if I understood completely what you suggested:
> >
> > #1) intersection of d-dimensional boxes
> > #2) k-d tree to position the point in a single box out of those resulting 
> > from #1 based on the in-box simple test
> >
> > did you have this in mind?
> >
> > If I do the in-box test for every point against all boxes, the alg will 
> > be very slow. This is why I wanted to narrow down the candidates using 
> > the bounding box for the triangles and a query built up from the whole 
> > mesh (at least it won't be Np * Nc , where Np = number of triangle 
> > points, and Nc = number of voulme mesh cells).
> >
> > I still don't understand how the k-d tree can help me...
> >
> > Best regards,
> > Tomislav
> >
> >> ----- Original Message -----
> >> From: Sebastien Loriot (GeometryFactory)
> >> Sent: 02/28/12 07:10 PM
> >> To: 
> >> 
> >> Subject: Re: [cgal-discuss] Polyhedron_3 points / Array of boxes
> >>
> >> If the boxes are axis aligned, the test is pretty simple, just check
> >> each cartesian coordinates to that of the bounding planes of the box (up
> >> to 6 comparison of double).
> >> The usual approch is then to use a hierarchical data-structure to locate
> >> efficiently the point in the mesh.
> >>
> >> If it match your hexa-mesh constraints, in CGAL we have a kd-tree:
> >> http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Spatial_searching_ref/Class_Kd_tree.htm
> >>
> >> HTH,
> >>
> >> Sebastien.
> >>
> >>
> >> On 02/28/2012 03:03 PM, Tomislav Maric wrote:
> >>> Well, the mesh is hexahedral and arbitrary. To be sure, by arbitrary I 
> >>> mean this:
> >>>
> >>> - mesh is a set of cells with boundary patches (lists of labels (IDs) 
> >>> to the total face list, corresponding to the boundary faces)
> >>> - a cell is a list of labels referring to an array of faces
> >>> - a face is a list of (counterclockwise counted) labels referring to an 
> >>> array of points
> >>>
> >>> The mesh connectivity is computed accross the faces: there is an 
> >>> owner-neighbour relationship which is defined by the cell ID (needed 
> >>> for the communication: which cell needs to communicate data to which 
> >>> Polyedron_3 point, and vice-versa). The cells with lower IDs "own" the 
> >>> faces. Each face represents a boundary between max two cells.
> >>>
> >>> This kind of construction is used as an unstructured mesh used for a 
> >>> Finite Volume numerical method solution. In its basis, the mesh is 
> >>> consisted of waterproof (logical: faces are not checked for planarity) 
> >>> polyhedra, but I am interested only in hexagonal cell geometry, for now.
> >>>
> >>> The boxes are axis alligned, because the cells of the mesh are axis 
> >>> alligned.
> >>>
> >>> Because I need to perform communications between the Polyhedron_3 and 
> >>> this Mesh, I'm thinking in the direction of an implementation of the 
> >>> BoxIntersectionBox_d concept, that will inherit from the "cell" class 
> >>> of the Mesh and provide the requirements needed by the concept. This 
> >>> way, I can re-use the info from the Mesh, and call CGAL algorithms on 
> >>> it. Either this, or build the Box from the array of points of each cell 
> >>> (min, max) + cell ID.
> >>>
> >>>
> >>> Thanks a lot!
> >>>
> >>> Tomislav
> >>>
> >>>
> >>>> ----- Original Message -----
> >>>> From: Sebastien Loriot (GeometryFactory)
> >>>> Sent: 02/28/12 02:45 PM
> >>>> To: 
> >>>> 
> >>>> Subject: Re: [cgal-discuss] Polyhedron_3 points / Array of boxes
> >>>>
> >>>> How is you hexa-mesh? is it regular or arbitrary? are the boxes
> >>>> axis-aligned?
> >>>>
> >>>> A screenshot can be helpful too if you have one.
> >>>>
> >>>> Sebastien.
> >>>>
> >>>> On 02/28/2012 11:22 AM, Tomislav Maric wrote:
> >>>>> Hi everyone,
> >>>>>
> >>>>> what would be the fastest way to compute something like "point in 
> >>>>> box" for the points of the Polyhedron_3? I have an array of boxes 
> >>>>> (extremely large, well over hundreds of thousands) and a rather large 
> >>>>> Polyhedron_3 depicting a surface mesh. What I am aiming at is a fast 
> >>>>> way of communicating data between an underlying hexahedral mesh 
> >>>>> (array of boxes) and the vertices of the Polyhedron..
> >>>>>
> >>>>> I've read the chapter on Intersecting sequences of d-Dimensional 
> >>>>> boxes, and I'm thinking about this:
> >>>>>
> >>>>> 1) Create an array of boxes for the Polyhedron_3 facets (triangular 
> >>>>> mesh)
> >>>>> 2) Create an array of boxes for the hex mesh.
> >>>>> 3) Compute the intersection test.
> >>>>> 4) Sub process: go through every triangle, take the point of the 
> >>>>> triangle and find the box (out of the candidates given by the 
> >>>>> intersection test) within which the point is located.
> >>>>>
> >>>>> This sounds a bit... slow... so any advice is appreciated! :)
> >>>>>
> >>>>> Thanks!
> >>>>>
> >>>>> Tomislav
> >>>>>
> >>>>
> >>>>
> >>>> --
> >>>> You are currently subscribed to cgal-discuss.
> >>>> To unsubscribe or access the archives, go to
> >>>> https://lists-sop.inria.fr/wws/info/cgal-discuss
> >>>
> >>>
> >>
> >>
> >> --
> >> You are currently subscribed to cgal-discuss.
> >> To unsubscribe or access the archives, go to
> >> https://lists-sop.inria.fr/wws/info/cgal-discuss
> >
> >
> 
> 
> -- 
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss