CGAL users discussion list

["Tomislav Maric" <>]

@Sebastien: Thank you very much for your advice. 

Best regards, 
Tomislav

> ----- Original Message -----
> From: Sebastien Loriot (GeometryFactory)
> Sent: 03/05/12 09:02 AM
> To: 
> 
> Subject: Re: [cgal-discuss] Polyhedron_3 points / Array of boxes
> 
> On 02/29/2012 08:39 PM, Tomislav Maric wrote:
> > 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).
> >
> This is a good choice.
> 
> > One question: k-d tree in CGAL is based on a static datastructure (CGAL 
> > manual)?
> Right.
> 
> >
> > 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. :)
> You should definitely use the octree to do that.
> 
> Sebastien.
> 
> >
> > 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
> >
> >
> 
> 
> -- 
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss