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

Closed list
Subscribers: 0
Owners

sparker

thiago

Subscribe
Unsubscribe
Info
Admin
Archive

Post

Shared documents

Manta Interactive Ray Tracer Development Mailing List

Text archives Help

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

From: David E DeMarle < >
To:
Subject: [Manta] Re: Re: Re: Re: information about the acceleration structures?
Date: Wed, 14 Apr 2010 19:32:36 -0400

Sorry that wasn't quite accurate.

The overlap happens because all the triangles within the sliding
window extent use vertices in a small region of space. The fact that
more of them share vertices is immaterial.

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:54 PM, David E DeMarle
< >
wrote:
> 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
>>>         > >
>>>
>>
>>
>>
>

[Manta] Re: Re: information about the acceleration structures?, (continued)

Archive powered by MHonArc 2.6.16.