performance of intersectWithLine alg

[John Biddiscombe]

>I am trying to cast rays into a scene consists of 10000 randomly
>distributed boxes with average width about 0.025 unit.
>I have tried to use intersectWithLine from vtkCellLocator, and
>vtkOBBTree, the performance was terrible,
>and what strike me is that vtkCellLocator out perform vtkOBBTree by a
>significant amount (in 100 times magnitude)
>I have set both alg to use Automatic max depth and bucket size ajustment
>(for celllocator).  I also set tolerance to
>be 0.025   Is there something that I did wrong?

The intersect with line implementation in vtk is very cumbersome. Because
of the way cells are stored - BBoxes, normals, other parametric coordinates
are computed on the fly at each cell/line test.

Speed improvement of a large magnitude can be achieved by by tweaking the
bucket sizes etc etc, here are some speed results I generated when trying
to find an optimal tree size for a raytrace simulation I'm doing

vtkModifiedBSPTree
------------------
depth = 12
Debug   : Time processing :  0:08:13:069
depth = 11
Debug   : Time processing :  0:06:05:355
depth = 10
Debug   : Time processing :  0:04:49:497
Release : Time processing :  0:02:52:358
depth = 9
Debug   : Time processing :  0:04:59:180
Release : Time processing :  0:03:43:532
depth = 8
Debug   : Time processing :  0:06:59:693
Debug   : Time processing :  0:06:51:572
depth = 6
Time processing : Large

vtkCellLocator
--------------
depth = 4
Time processing :  0:03:45:093
depth = 5
Time processing :  0:01:19:955
depth = 6
Time processing :  0:00:43:382
depth = 7
Time processing :  0:00:46:347
depth = 8
too much disk thrashing

See the vtkCellLocator differences between depth 4 and depth 6. Nothing
else changed.

My vtkModifiedBSPTree class came out significantly worse in this particular
case however for other special cases (depends on geometry of test dataset)
it outperformed vtkCellLocator by 10:1. 

Considerations such as time spent building the tree will be important when
dealing with data that is changing. The test above is when the dataset to
be tested is constantly being warped and the tree is rebuilt at every pass
of the algorithm (about 40,000 rays shot at each pass - times are for two
or four passes I think), building an OBB or BSP tree will be much much
slower than building the (regular) CellLocator OctTree in this situation.

I'm working on a better ModifiedBSPTree class which will precompute all
BBoxes, normals etc etc and work only on polydatasets with additions for
handling transparent intersections and storing multiple intersection
points, however this will be some time in the finishing. It's a pity that
the cell storage in vtk doesn't allow for more storage of temporary stuff,
but then again field data and scalars can be used instead.

But I would advise you to test many different depths for the tree and
compare results. if your data is fairly homogeneous then vtkCellLocator
will probably be your best bet every time. If you have wide open spaces
between regions of data, OBBTree may well be best, but tuning the depths of
the tree is essential. You want to try to get 'a few' cells per bucket. If
you have 10,000 cells (of roughly equal size) there's not much point
building an OctTree of depth 6 as 8^4 = 4096, 8^5 = 32768  8^6 = very
large..... Likewise you don't want to go for depth 2 as 8^2 = 64 and you
will test many many cells per bucket. Because the intersect with cell
routines are a bit handicapped you want to try and get a good balance
between testing cells (slow) and tree walking (fast). In the case above
depths of 4,5 would probably be best. (Cells/bucket in range 0->10 ish but
aim for 1 or 2 if you can!)

Don't know if any of this helps...

John B



-----------------------------------------------------------------------------
This is the private VTK discussion list.  Please keep messages on-topic.
Check the FAQ at: <http://www.automatrix.com/cgi-bin/vtkfaq>
To UNSUBSCRIBE, send message body containing "unsubscribe vtkusers" to
<majordomo at gsao.med.ge.com>.  For help, send message body containing
"info vtkusers" to the same address.     Live long and prosper.
-----------------------------------------------------------------------------