Ok, there was a misunderstanding...
In the last revision (1.20 point_locator_tree.C, 1.22 tree_node.C) the ELEMENTS version works better then the NODES version in the search (it doesn't involve the linear search) but it is slower when you populate the tree. I also prefer the 1.19 version of point_locator_tree.C.
The NODES version doesn't inserts the element to all the tree nodes that have non empty intersection with the element bounding box, it insert the element to all the tree that bounds an element's node. With the NODES version it is possible that the point you are searching isn't contained in any element assigned to the node of the tree that bounds
the point and so you will need the linear search.
The ELEMENT version is slower when it populates the tree because it needs to calculate the element bounding box many times and probably it builds more tree nodes.

I actually use a different version of tree_node.C and I'll try  to post it in a new  tread.
Lorenzo


2007/9/13, Tim Kröger < tim@cevis.uni-bremen.de>:
Dear Lorenzo,

On Wed, 12 Sep 2007, Lorenzo Botti wrote:

>>   However, it seems to me that the NODES version requires the linear
>>   search at the end of PointLocatorTree::operator() to be involved more
>>   often than the ELEMENTS version; in particular, the ELEMENTS version
>>   did *never* need the linear search in the case for linear elements,
>>   whereas the NODES version does (in my case, for linear TET10
>>   elements).  While I don't doubt that it is still much faster in the
>>   mean, it causes approximately two problems for my application:
>
>>  1.) Since I am using out_of_mesh_mode, I get wrong results, since the
>>  linear search is disabled in out_of_mesh_mode.

> this sounds strange... the NODES BOUNDING BOX version should avoid
> (completely in case of elements with rectilinear edges) the linear search
> for points within the mesh.
> You shouldn't  find any element forcing the linear search in out of mesh
> mode.
> With the ELEMENT CENTROID insertion method (revision 1.19) the linear search
> deals with the particular situations in witch the point you are searching
> isn't contained in any element assigned to the node of the tree that bounds
> the point.

The ELEMENT method is no longer using the centroids.  It inserts the
given element to all tree nodes that have non-empty intersection with
the element's bounding box.  This method is in use since August 4th of
last year.  See also the discussion in libmesh-devel around that date
with the subject "Patch".  (I admit that I am responsible for that
silly subject.)  This should work (i.e. not need the linear search)
always except for elements with curved boundaries.  In particular, it
always worked (and still works) for my application (with TET10
elements).

I don't know exactly what the NODES method is doing, but it doesn't
seem to work for my example.  Since I am not a native English speaker,
I am not sure what you mean with "rectilinear edges"; do you just mean
"non-curved edges" or do you mean "edges parallel to coordinate axes"?

Please find attached a test program with which the problem can be
verified.  I have place my example mesh file at
http://www.cevis.uni-bremen.de/~tim/a.xdr ; use that file together with
the test program.  You will see that 29 positions in the mesh are not
found without the linear search.

Then replace point_locator_tree.C with its 1.19 version and repeat the
test.  All points will then be found without linear search.

Best Regards,

Tim

--
Dr. Tim Kroeger                            Phone +49-421-218-7710
tim@mevis.de, tim@cevis.uni-bremen.de      Fax   +49-421-218-4236

MeVis Research GmbH, Universitaetsallee 29, D-28359 Bremen, Germany

Amtsgericht Bremen HRB 16222
Geschaeftsfuehrer: Prof. Dr. H.-O. Peitgen