CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

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