Jump to content
  • Advertisement
Sign in to follow this  
marius4143

Planet rendering and floating point precision

This topic is 4081 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm in the very early stages of my procedural planet project and I'm running into floating point precision issues. I understand that I need to translate everything so the view point is at the center to eliminate rounding errors close by, and I have all that working fine. My problem involves splitting the quadtree into smaller and smaller nodes. The root node has a width and height of 2 units (-1.0 to 1.0), so when subdivided the the 4 new nodes have a width of 1.0, then 0.5, 0.25, etc. The problem is, by the time I get down to the "ground" I'm at level 15, and the width of the nodes are 0.0000305176. This is well beyond the 6 digits of precision a float gives me, and when I move or rotate the camera everything jerks around horribly. So, I've spent the last two days reading everything I can find on the subject and I've yet to find the right answer. The only thing I can think of to try is to build each node in object space (width and height are always 2 units, vertices are relative to the center which is at 0,0,0), then scale and translate the node when rendering. The translation seems simple enough, however I'm not sure how much to scale it, and it seems like the scaling would cause the same precision issues anyway. So, I'm stumped. Does anyone have any solutions for this issue? I feel like I'm probably missing something very obvious. Thanks.

Share this post


Link to post
Share on other sites
Advertisement
I've not done any planet rendering yet and so can't offer anything concrete but it's something I'm quite interested in and would like to take a shot at one day.

My take is that with something so large, you're going to have to toy with changing scales on the fly. By this I mean if you're on another planet looking back at earth, it might have a width of 1, but if you're in the atmosphere of earth each quadtree node might have a width of 1, rather than 0.0000135 etc..

Again I haven't actually put anything like this into practice, but with the very large numbers involved in planet sizes, you're probably not going to get away with one scaling system.

Share this post


Link to post
Share on other sites
Right, single precision will not cut it for planet size objects with extreme LOD. You are running out of precision.

As for being procedural, when are you generating? Do you regenerate once per frame? Or do you cache info? Static geometry or dynamic.

Regardless you are going to have to do work CPU side which is double precision. Might be able to generate higher level double precision coordinates which are near eye relative, then switch to single precision for the lower level (in the recursion) fine detail (which should be a majority of the geometry). Then when the eye moves far enough away from the cached lower level fine detail, you will have to regenerate as you run out of precision again.

Most likely you will need to keep recursion based on projected view size of your parent node bounding volume (simple projected radius works well) anyway (working in eye space), so think when your projected view size is fully within the screen, that would be a good time to switch to single precision. Running double precision for a small fraction of parent nodes should be no problem performance wise...







Share this post


Link to post
Share on other sites
You need some large integers. 64-bit should do you fine. Every modern CPU supports them, and they're far faster than double precision. They also work consistently everywhere. If you want to store positions or times relative to some random arbitrary origin, large integers is what you want.

I actually have an entire rant about double precision floating-point: http://www.eelpi.gotdns.org/blog.wiki.html#%5B%5BA%20matter%20of%20precision%5D%5D

Share this post


Link to post
Share on other sites
marius4143:
I did it the way you mention, by building patches at the same size, then scale and translate them so they line up in the view. Problem with that is your z buffer no longer works correctly between the levels! I really can't remember how I got around that problem, but I think I ended up rendering back to front which is very much less than optimal unless you can cull most overdraw first.

Share this post


Link to post
Share on other sites
Quote:
Original post by TomForsyth
You need some large integers. 64-bit should do you fine. Every modern CPU supports them, and they're far faster than double precision.


64-bit integer math is NOT as fast as double precision, this is especially true on the newer Core 2 Duo Intel processors. For example, from actual RDTSC clock cycle testing doing 1M loops of 8 unrolled register to register independent operations,

64-BIT INT
ADD : 9,450,090 (cycles/8M ops)
IMUL : 16,784,973
SAR : 4,731,480

32-BIT INT
ADD : 9,448,425
IMUL : 8,397,153
SAR : 4,738,437

SSE2 (2 DOUBLE PRECISION FLOATS PER VECTOR)
ADDPD : 8,388,738
MULPD : 8,399,025

Basically shows maximum throughput of each type of operation
with looping overhead every 8 instructions.

So the bottom line is that the Core 2 Duo using SSE2 can sustain near effective 2 double precision adds or multiplies per clock, where as a single 64-bit multiply has a throughput of 2 clock cycles per one multiply.

Don't ask why the ADD speed is slower than IMUL? I'm not sure given the optimization manual says it should get a latency of 1 clock, and a throughput of 0.333 clocks in ideal conditions. I was doing the following, and keep in mind this is GAS (gnu assembly) so the syntax is reversed from Intel, %rax is the SOURCE operand NOT the destination.

addq %rax,%rbx
addq %rax,%rdx
addq %rax,%rdi
addq %rax,%rsi
addq %rax,%r8
addq %rax,%r9
addq %rax,%r10
addq %rax,%r11

Share this post


Link to post
Share on other sites
Thanks for the replies everyone.

Quote:
Original post by TimothyFarrar
As for being procedural, when are you generating? Do you regenerate once per frame? Or do you cache info? Static geometry or dynamic.

Regardless you are going to have to do work CPU side which is double precision. Might be able to generate higher level double precision coordinates which are near eye relative, then switch to single precision for the lower level (in the recursion) fine detail (which should be a majority of the geometry). Then when the eye moves far enough away from the cached lower level fine detail, you will have to regenerate as you run out of precision again. ...


I'm currently generating the geometry when I split the node. The plan is to try to predict when a node will be needed based on camera movement and have a thread generate it. There will be caching as well. However while trying to get the precision issues ironed out I'm not even doing anything with height data - I'm just generating the new quadtree node, which creates a new 33x33 vertex terrain patch. The vertices are mapped from a cube to a sphere, which is why the coordinates range from -1 to 1 at the root node.

I'm not sure what you're saying about switching from double to single precision. Can you walk through an example?



Quote:
Original post by TomForsyth
You need some large integers. 64-bit should do you fine...


I'm not too concerned with performance at this point - just want things to work first :), so I think a double will suffice for now.

Quote:
Original post by bluntman
I did it the way you mention, by building patches at the same size, then scale and translate them so they line up in the view. Problem with that is your z buffer no longer works correctly between the levels! I really can't remember how I got around that problem, but I think I ended up rendering back to front which is very much less than optimal unless you can cull most overdraw first.


What I'm not clear on is how to determine what scale factor to use. Wouldn't scaling them down to the proper size cause the same precision issues?

Share this post


Link to post
Share on other sites
Well, patch n+1 should be half the dimensions of patch n when rendered, and you are building them the same size, so you need to render patch n twice the size of patch n+1. That is the same as drawing it twice as close to the camera.
I forgot, but you jogged my memory: I didn't scale the patches at all, just drew them at different distances from the camera. I had issues with small gaps at the joins between patches, but nothing more than other lod methods, and they were easily fixed with some skirts.
edit- I forgot to mention, using this method you don't need to use double precision, my patches were from five thousand miles across down to a few meters across all in 32 bit floats.

Share this post


Link to post
Share on other sites
I found this from the paper Planet-Sized Batched Dynamic Adaptive Meshes (P-BDAM) (Cignoni et al)...


Quote:

Accuracy of the representation. Numerical accuracy issues
are one of the most neglected aspects in the management of huge
datasets. Sending positions to the graphics hardware pipeline needs
particular care, given that the highest precision data-type is the
IEEE floating point, whose 23 bit mantissa leads to noticeable vertex
coalescing problem for metric datasets on the Earth and to camera
jitter problems in the general case [Reddy et al. 1999]. Typical
solutions (e.g. [Lindstrom et al. 1997; Reddy et al. 1999]) are to
partition the dataset into multiple tiles, each of them with an associated
local, possibly hierarchical, coordinate system, and then use
single precision floating points for representing vertex positions in
the local reference. At rendering time, tiles are separately rendered
in their local rendering systems, performing matrix transformations
on the host in double precision to reduce roundoff errors.


I believe this is more or less what TimothyFarrar was saying, and sort of matches up with my thoughts on generating each quadtree node as its own object (i.e. its own coordinate system). What I can't quite wrap my head around is the "tiles are separately rendered in their local rendering systems" part. How does one go about doing that?

Share this post


Link to post
Share on other sites
Quote:
Original post by marius4143
I believe this is more or less what TimothyFarrar was saying, and sort of matches up with my thoughts on generating each quadtree node as its own object (i.e. its own coordinate system). What I can't quite wrap my head around is the "tiles are separately rendered in their local rendering systems" part. How does one go about doing that?


That sounds about right.

CPU side you are simply generating matrices using double precision math, then converting those matrices to single precision and sending GPU side for use in viewing transformations.

Start at the root node, using double precision, and generate a matrix which can transform your root node's internal coordinate system into the viewing coordinate system.

Then traverse down through the nodes, each time, the child node gets its own view matrix which is generated by taking the parent view matrix and the parent-to-child coordinate space transform matrix and doing a matrix by matrix multiply to compute the new view matrix of the child.

... that's the over-simplified version ...

There are many ways to skin this cat, and lots of things you can do to get good performance.

I personally separate the viewing matrix (4x4) into direction (3x3), position offset (3x1) and scale (1x1), because in my application I need the inverse viewing matrix for each node also (inverse of a pure rotation matrix is the transpose) to feed back my CFD/physics results (computed in the viewing coordinate space) into the node's local coordinate space.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!