Manta Interactive Ray Tracer Development Mailing List

Text archives Help


[Manta] Re: Re: Re: information about the acceleration structures?


Chronological Thread 
  • From: Carson Brownlee < >
  • To:
  • Subject: [Manta] Re: Re: Re: information about the acceleration structures?
  • Date: Wed, 14 Apr 2010 13:28:02 -0600
Does that random triangle strip form a hull or is it just slightly less
overlapping because the triangles are attached to eachother?  Perhaps a
variable number of variably subdivided polygonal spheres would make for
a better benchmark.  
I believe this is one of the options in the primtest scene, or at least
you can repeat objects a certain number of times spaced out along a
grid.  
Carson

On Wed, 2010-04-14 at 11:57 -0400, David E DeMarle wrote:
> Thanks for the explanation.
> 
> The degree of "evilness" (or fuzziness, or co-location of triangles)
> is controllable in the test source generator. See,
> vtkMantaTestSource::SetSlidingWindow(x).
> 
> As x goes from 0.01 (which I was used) down to 0.0, the data
> degenerates to a random triangle strip. As it goes up to 1.0 I think
> it degenerates to random triangles within a cube. 
> 
> The build times and frame rates are improve greatly as it approaches
> 0.0.
> 
> For 100k triangles, at 0.0:
> grid build 1.26s
> grid render 22.7fps
> 
> dynbvh build 1.8s
> dynbvh render 27.7fps
> 
> For 100k triangles at 0.005
> grid build 109.7s
> grid render 1.0fps
> 
> dynbvh build 1.91127
> dynbvh render 16.7594
> 
> 
> David E DeMarle
> Kitware, Inc.
> R&D Engineer
> 28 Corporate Drive
> Clifton Park, NY 12065-8662
> Phone: 518-371-3971 x109
> 
> 
> On Tue, Apr 13, 2010 at 4:34 PM, Thiago Ize 
> < >
> wrote:
>         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: 
>         > 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