Manta Interactive Ray Tracer Development Mailing List

Text archives Help


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


Chronological Thread 
  • From: David E DeMarle < >
  • To:
  • Subject: [Manta] Re: Re: Re: Re: information about the acceleration structures?
  • Date: Wed, 14 Apr 2010 15:54:58 -0400
Better benchmarks are welcome.

Mine doesn't make a hull. I just make randomly drifting vertices and
then make triangles from them. X controls the size of the sliding
window into the vertex list that triangles choose from. With x=0 the
triangles don't overlap since they never (well rarely if ever) share
vertices. When x is bigger, vertices tend to get picked by more and
more triangles and so many of the triangles in the sliding window
"overlap".

Features I needed:
* exactly controllable number of triangles
* has to be separable, so that any number of processors can generate
independent swaths of triangles and the union of all those swaths has
to be exactly the same (which makes the total size "unlimited")
* variability in triangle size, placement and orientation
* quick build time
* readable in VTK, in parallel

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



On Wed, Apr 14, 2010 at 3:28 PM, Carson Brownlee 
< >
 wrote:
> 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