Manta Interactive Ray Tracer Development Mailing List

Text archives Help


[Manta] Re: information about the acceleration structures?


Chronological Thread 
  • From: Thiago Ize < >
  • To:
  • Subject: [Manta] Re: information about the acceleration structures?
  • Date: Tue, 13 Apr 2010 14:34:37 -0600
I took a quick look at the scene you generated and it's a very evil scene.  The triangles are all on top of each other which causes issues with most acceleration structures.  I had never really thought much about this, but the BVH does have the nice property that the build time is unaffected by the triangle sizes or distribution and depends solely on the triangle count. This makes sense since BVHs are object partitioning structures and will have a guaranteed upper bound on the number of nodes (usually 2n-1).  The grid and kd-tree are spatial splitting structures and so will end up doing lots of extra work when the triangles are overlapping each other in an effort to create nodes/cells with only a few triangles.  However, when it comes to render time, the grid, and sometimes the kd-tree, will win out since they do end up separating the triangles and space better.  In theory the kd-tree would do just as well as the grid if the build were smart enough to handle this case, but alas it currently is not.  If I was patient enough, I'd be very interested in seeing how the BSP would handle this.

DynBVH: 1.7s,  4.7fps
rgrid 1:      4.5s,  3.2fps
rgrid 2:       94s,  8fps
rgrid 3:     360s, 8.9fps
KDTree:   6.2s, 2.1fps
KDTree (with perfect splits): 284s, 6fps

The specific problem you are seeing with respect to the grid is that each triangle ends up lying in many grid cells and so we get tons of triangle references.  With more grid levels you end up with smaller grid cells and so a triangle will lie in even more grid cells.  So in this case I'd recommend a 1 or 2 level grid.  Although to be honest, I think this benchmark is testing for a worst case degenerative type scene then the normal case scene.  If a user creates something where the triangles are all on top of each other then chance are there is something very wrong either with the code that produced those triangles or with their method of visualizing that data.  I've included a screenshot of just how ugly those triangles are.  This is a cool test case though for checking out worst case performance and if you are worried about worst case build time, then BVH is the way to go.  But if you want a structure for normal situations, then I would recommend a different benchmark.



Thiago

David E DeMarle wrote:
" type="cite"> 
Here is a summary:

All tests are on a mac pro running leopard with 8 2.6GHz 64bit CPUs and 10G ram.

The test data is randomly generated (randomly sized and oriented)
triangles. The triangles drift so they aren't all completely located
but they are clumped.
Attached are sample images for 1000 and 250000 tris. See
vtkMantaTestSource in the ParaView source for details.

These pure manta tests don't do camera orbits or colormap but are
qualitatively similar to the rest.

A representative test command is:
  bin/manta -res 512x512 -np 8 -bench 100 1  -shadow noshadows -scene
"lib/libscene_triangleSceneViewer(-model
/Users/demarle/tmp/mesh_1000.ply -triangleType Wald_tri)"

#NAME, #numPROC, #numThread, #numTri, #build time, #avg framerate
MANTA_DYN, 1, 8, 1000, 0.006706, 209.551
MANTA_DYN, 1, 8, 5000, 0.040952, 183.941
MANTA_DYN 1, 8, 10000, 0.089845, 111.36
MANTA_DYN, 1, 8, 50000, 0.534879, 46.9353
MANTA_DYN, 1, 8, 100000, 1.18454, 30.5049
MANTA_DYN, 1, 8, 250000, 3.27977, 13.5604
MANTA_DYN, 1, 8, 500000, 7.30346, 7.05025
MANTA_DYN, 1, 8, 750000, 11.4801, 5.61708
MANTA_DYN, 1, 8, 1000000, 15.5694, 3.9836
MANTA_DYN, 1, 8, 2500000, 44.9804, 1.43034
MANTA_DYN, 1, 8, 5000000, 105.155, 0.600696

MANTA_RG3, 1, 8, 1000, 0.021551, 90.2758
MANTA_RG3, 1, 8, 5000,  0.360524,99.7973
MANTA_RG3, 1, 8, 10000, 1.710166, 85.0091
MANTA_RG3, 1, 8, 50000, 38.843968, 86.2438
MANTA_RG3, 1, 8,100000,  272.700091, 75.805
crash/killed above this

vtkManta is about 50% the framerate above, mostly because we have to
ask manta to render 2x to get a picture out of what the we've asked
for, but also because build time is included in the framerate (compare
1/render time).

A representative test command is
  mpirun -np 1 bin/MantaBenchmark -screensize 512 -threads 8
-noChanges -triangles 1000

#NAME, #numPROC, #numThread, #numTri, #build time, #render time,
#composite time, avg framerate
VTKMANTA_DYN, 1, 8, 1000, 0.159514, 0.0116025, 0, 56.3087
VTKMANTA_DYN, 1, 8, 5000, 0.215516, 0.0163282, 0, 45.7362
VTKMANTA_DYN, 1, 8, 10000, 0.294489, 0.0152193, 0, 52.5233
VTKMANTA_DYN, 1, 8, 50000, 0.949177, 0.0322921, 0, 24.6086
VTKMANTA_DYN, 1, 8, 100000, 1.86205, 0.0649788, 0, 12.3498
VTKMANTA_DYN, 1, 8, 250000, 5.02568, 0.113499, 0, 6.37497
VTKMANTA_DYN, 1, 8, 500000, 10.978, 0.202382, 0, 3.37314
VTKMANTA_DYN, 1, 8, 750000, 18.7495, 0.288325, 0, 2.22531
VTKMANTA_DYN, 1, 8, 1000000, 31.5962, 0.336292, 0, 1.64294
VTKMANTA_DYN, 1, 8, 2500000, 115.183, 1.02509, 0, 0.495391
VTKMANTA_DYN, 1, 8, 5000000, 285.524, 2.66965, 0, 0.194939

VTKMANTA_DYN, 1, 1, 1000, 0.192624, 0.0461057, 0, 20.9861
VTKMANTA_DYN, 1, 1, 5000, 0.242418, 0.0578603, 0, 16.7351
VTKMANTA_DYN, 1, 1, 10000, 0.327631, 0.087255, 0, 11.1571
VTKMANTA_DYN, 1, 1, 50000, 1.02266, 0.167914, 0, 5.69547
VTKMANTA_DYN, 1, 1, 100000, 2.03976, 0.358396, 0, 2.67876
VTKMANTA_DYN, 1, 1, 500000, 11.4847, 1.186, 0, 0.783819

The exact same test with MESA (7.6.2) is:

MESA, 1, 1, 1000, 0.0263782, 0.00566359, 0, 102.432
MESA, 1, 1, 5000, 0.04706, 0.0160004, 0, 53.1379
MESA, 1, 1, 10000, 0.0824239, 0.0387112, 0, 24.0468
MESA, 1, 1, 50000, 0.255554, 0.103142, 0, 9.34801
MESA, 1, 1, 100000, 0.581918, 0.299732, 0, 3.28216
MESA, 1, 1, 250000, 1.55697, 0.537817, 0, 1.82149
MESA, 1, 1, 500000, 3.63054, 1.18965, 0, 0.824423

And with the 512Mbit NVIDIA 8800GT
NVIDIA, 1, 1, 1000, 0.117104, 0.00857559, 0, 56.2237
NVIDIA, 1, 1, 5000, 0.127745, 0.00820931, 0, 56.7612
NVIDIA, 1, 1, 10000, 0.144963, 0.00814167, 0, 56.2256
NVIDIA, 1, 1, 50000, 0.273312, 0.00866277, 0, 52.4685
NVIDIA, 1, 1, 100000, 0.45417, 0.00889918, 0, 48.9557
NVIDIA, 1, 1, 250000, 1.25211, 0.00939326, 0, 23.3149
NVIDIA, 1, 1, 500000, 2.76642, 0.0255764, 0, 16.6894
NVIDIA, 1, 1, 750000, 5.9455, 0.0385038, 0, 9.68741
NVIDIA, 1, 1, 1000000, 14.4165, 0.0478288, 0, 5.14866
NVIDIA, 1, 1, 2500000, 65.545, 0.105334, 0, 1.3805
NVIDIA, 1, 1, 5000000, 171.056, 1.2384, 0, 0.361464

David E DeMarle
Kitware, Inc.
R&D Engineer
28 Corporate Drive
Clifton Park, NY 12065-8662
Phone: 518-371-3971 x109



On Sun, Apr 11, 2010 at 11:20 PM, Thiago Ize 
 
 "><
 > wrote:
  
So RecursiveGrid is crashing with more than 100k triangles?  That's odd.
I've gotten it to build 10M+ triangle scenes.  Are these triangles
distributed in some weird fashion?  For instance, are the triangles large
and overlapping each other so that a single triangle ends up being in lots
of grid cells?  Any chance you could send me a screenshot of what the 100k
scene looks like?

Here's an example where I built a 1M tri scene on my laptop:

$bin/manta -scene "lib/libscene_triangleSceneViewer.dylib(-rgrid -model
/Users/thiago/data/models/happy_vrip.ply -triangleType Wald_tri)"
-nodisplaybench 10 10
Recursive Grid built in 9.577648 seconds for a 1087474 object scene
There are 1, 457, 51970, 0 grids per level for a total of 14674215 cells
7 x 18 x 7
Benchmark completed in 1.37217 seconds (10 frames, 7.28771 frames per
second)

So 1.4s to render 20 frames and it took 9.5s to load the model and build the
structure with the recursive grid.  The peak memory usage during the build
was about 250MB and for rendering it stayed at 250MB.

$bin/manta -scene "lib/libscene_triangleSceneViewer.dylib(-DynBVH -model
/Users/thiago/data/models/happy_vrip.ply -triangleType Wald_tri)"
-nodisplaybench 10 10
DynBVH::preprocess START (1087474 objects)

DynBVH build time: Total (24.1661)
object_ids initialization (0.366518)
build (23.6126)
updateBounds (0.18699)
num_nodes = 1188560

Benchmark completed in 0.984006 seconds (10 frames, 10.1625 frames per
second)

So DynBVH took 2.5 times longer to build than recursive grid and was 1.36x
faster to render. It's peak memory usage was 300MB during the build (more
than the rgrid) and then 240MB during rendering.  So from a build
perspective rgrid wins hands down, at least for triangle meshes.
Incidentally, as an example of why rgrid's build is unoptimized and could be
much faster, I tried building the same scene using my optimized grid build
(not in manta) and I get a build time of about 1s (on one thread).

Thiago

Archive powered by MHonArc 2.6.16.

Top of page