Volumes Of Fun
http://www.volumesoffun.com/phpBB3/

Faster decimation?
http://www.volumesoffun.com/phpBB3/viewtopic.php?f=14&t=190		 Page 1 of 1
Author:  psquare [ Wed Apr 06, 2011 7:43 am ]
Post subject:  Faster decimation?
@David:

I use decimation as recommended by you here:

http://www.thermite3d.org/phpBB3/viewtopic.php?f=2&t=142

That post also enumerates the things we are currently doing, so it serves as a refresher.

We have a (theoretically) infinite world where we generate the pages on the fly as they come in/out of view. We use perlin noise etc to make random terrains. All is fine, however, the decimation seems to be a major bottleneck.

We do the decimation in the background already, but the app still seems to be hiccuping.

We also do not want to really save anything that can be regenerated on the fly (e.g. if its not modified)

I profiled the app, and did most of the optimizations on my side. Now most of the time seems to be spent in the decimation.

Is it possible to speed this up? I realize that much of the time is because of the complex nature of decimation itself, but maybe you can identify 'bottleneck' functions as obvious candidates for optimization. For example, see images:


Image Image
Author:  David Williams [ Wed Apr 06, 2011 9:19 pm ]
Post subject:  Re: Faster decimation?
Yep, overall your results don't suprise me, the decimation is definatly one of the slow parts of PolyVox.

When I wrote the MeshDecimator I made two decisions which with the benefit of hindsight did not work out that well. The first decision is that the MeshDecimator is completely decoupled from the surface extractors. This seemed sensible (so that data can potentially come from different sources) but it results in a lot of wasted effort. One of the frst things the MeshDecimator has to do is compute the connentivity between the vertices and this is a pretty slow process (it's the call to buildConnectivityData()). But during surface extraction this information is much more readily available, it's just we already threw it away.

Secondly, the MeshDecimator is generic for the different mesh types (PositionMaterial and PositionMaterialNormal). Again this was to cut down on code but it throws away optimisation oppertunities. For example, it should be very fast to check whether a Minecraft style mesh can collapse was it it constrained to three axes, but it is more complex for a generic marching cubes mesh. Also, the 'collapseChangesFaceNormals()' function is pretty horrible.

The other issue is that I'm not using any of this decimation stuff myself simply because I haven't had a need for it. Have you tried this demo? The large hills map is 1024x1024x256 and runs at 35FPS on my NVidia GTX 280. The result of this is that there hasn't been much incentive to improve the MeshDecimator. In your case, when you do perform the decimation, how much do you find it helps the framerate?

I might need it eventually for physics integration, and when that happens I will probably reimplement it very differently. If you want a crack at it your self this is what I would do:

  • Change the surface extractor to generate quads instead of triangles. Keep track of the connectivity.
  • Within the same function, perform the decimation by collapsing quads. Use fast tests designed just for cubic maps.
  • Trianglulate the result.

Also, you might want to check out this thread: http://www.thermite3d.org/phpBB3/viewtopic.php?t=98. I would aim to do something like that but inside the surface extractor.

One other thing I should point out is that the MeshDecimator currently get very expensive as the number of vertices increases (it is not a linear relationship). So if you wish to decimate a 32x32x32 region you might be better off generating 8 16x16x16 meshes, decimating those, and then stitching the results together. The result won't be quite the same (because of the stitching boundary) but it might be faster.
Author:  psquare [ Thu Apr 07, 2011 7:01 am ]
Post subject:  Re: Faster decimation?
Quote:
In your case, when you do perform the decimation, how much do you find it helps the framerate?

See images. Without decimation the data increases 4 fold and a significant fps drop. I think today's monster cards might easily handle these many verts/tris, but that apart, so many verts is simply not needed. I think we still need to use decimation or a variant of it thereof. See next point.

Image Image

Quote:
Also, you might want to check out this thread: viewtopic.php?t=98. I would aim to do something like that but inside the surface extractor.

Quote:
* Change the surface extractor to generate quads instead of triangles. Keep track of the connectivity.
* Within the same function, perform the decimation by collapsing quads. Use fast tests designed just for cubic maps.
* Trianglulate the result.

Yes. This seems like a good starting point. I will investigate further in this area.
Quote:
The other issue is that I'm not using any of this decimation stuff myself simply because I haven't had a need for it. Have you tried this demo? The large hills map is 1024x1024x256 and runs at 35FPS on my NVidia GTX 280.

Yes I tried the demo. However I use paging and multiple volumes. For various reasons (not directly related to polyvox), using a single large volume and shifting data around is not the way to go for us.
Author:  Shanee [ Thu Apr 07, 2011 3:24 pm ]
Post subject:  Re: Faster decimation?
decimation completely messes up normals for smooth meshes btw, so triplanar texturing turns bad.
Author:  psquare [ Thu Apr 07, 2011 4:37 pm ]
Post subject:  Re: Faster decimation?
I don't use smooth meshes. I use cubic meshes. Besides, I don't use normals, I gen them in the shader using derivatives.
Author:  David Williams [ Thu Apr 07, 2011 5:40 pm ]
Post subject:  Re: Faster decimation?
psquare wrote:
...so many verts is simply not needed...


Well yes, I do agree. Guess I'm just feeling defensive because the MeshDecimetor isn't working so great :-)

Quote:
Yes. This seems like a good starting point. I will investigate further in this area.


You should also check onimatrix's posts from this thread as there might be something useful. Also see here for some work beyzend did on avoiding decimation by generating less triangles in the first place. This was written for the old version of the Volume so I don't know how well it still works.

Shanee wrote:
decimation completely messes up normals for smooth meshes btw, so triplanar texturing turns bad.


Yes, I can imagine this could be an issue, though I'm not sure if the MeshDecimator is really at fault. I think the normals of a low resolution mesh will always be different from the high resolution version. You could try recomputing the normals from neighbouring faces or directly from the volume data but I doubt if you can solve the issue completly.
Author:  beyzend [ Thu Apr 07, 2011 7:35 pm ]
Post subject:  Re: Faster decimation?
Oh btw I made some changes to the RLE extractor to generate "skirts" around the faces, to solve the T-Junction problem (a big problem for night scenes because you will see tiny little dots). The skirting does eliminate the problem, in rare circumstances though I still see holes, and I assume it's because I have bugs in my code. (I will say the improvement is good enough so that I'm avoiding bug fixes because I'm lazy.)

I will post the new code later if you want it.

Right now I'm not really using it because I'm doing some experiments with lighting that require per vertex baking on the CPU side which won't work with this (RLE thing) unless I do it in the pixel shader. So maybe eventually I will go back to it.

Another thing is I also tried to use the Decimator but for some strange reason when I look at the decimated mesh in wire-frame mode for both RLE and PolyVox decimation, they both look exactly the same. I never got around to finding out why that is.
Author:  beyzend [ Thu Apr 07, 2011 8:49 pm ]
Post subject:  Re: Faster decimation?
Oh yeah, also I've noticed that in my case, I get the same FPS using CubicSurfaceExtractor and my RLEExtractor. But using CubicSurfaceExtractorWithNormals bring the FPS down by a lot. Actually, I need to look at my timings for everyting: graphics and physics.

TL;DR You should probably not use my RLE extractor because I don't see much difference therefore. Unless I see a difference in Physics mesh extractor I may just stop using it.
Page 1 of 1 All times are UTC
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/