CGAL users discussion list

["Tomislav Maric" <>]

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