Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have a world with 100s of simple objects on screen at once. Most objects don't have more than 40-50 vertices. The vertex coordinates for these objects are very large (planetary scale), so I use the 'floating origin' method to draw my data (actual coordinates are close to the origin and then you apply a translation out to where you want the object).

Based on the user's position, these objects are dynamically created and destroyed. Other than that, the objects are static. With my previous implementation, I was drawing these objects separately, and the result was significant slow down (I'm targeting mobile devices)... since the total number of triangles on screen is sort of trivial (even though there are many objects), I assume that the slow down is because of the multiple draw calls.

So I tried packing my objects into a single buffer to draw them all with a single call. This works, but I also use a 'floating origin' transform to position the geometry. The final transform matrix is calculated with the CPU to maintain precision and then sent to my vertex shader. The problem is applying the floating origin fix is CPU intensive:

  • If I use a single floating origin for the vertex buffer:

    • (good) only need to calculate one transform matrix
    • (bad) I need to perform an offset subtraction on every vertex in the buffer. The upper limits of scene complexity reaches 50k+ vertices, so this is expensive.
  • If I use multiple objects:

    • (sorta good) only need to compute as many matrices as there are objects (this is still really expensive though, since there are a ton of objects)
    • (bad) I need to pass the shader a large array of matrix uniforms

I feel like I'm stuck. Are there any other ways to maintain precision I could use? Or maybe a better way to use the floating origin method? The problem is basically "how do I draw a ton of simple geometry with really large numerical coordinates with OpenGL ES 2?"... I'd appreciate any advice.

EDIT

Just some clarification on the offset. The vertex should always be a valid float. The maximum distance a vertex can be from the origin is the maximum radius of the earth +/- few thousand meters. Assume 1 unit = 1 meter. The distances are never so large that they can't be represented by floats at all.

The objects themselves are things you find in a map on the surface of the earth: buildings/roads/etc. So relative to the coordinates being used, the objects are very small.

I'm not confident on the floating origin stuff, but here's my take...

When you calculate the MVP on the CPU where your vertex is offset, you're getting something you calculate with double precision that goes from an offset vertex position (say its 10.1,10.2,10.3) to the normalized opengl coordinates (I think thats +/- 1 in xy and 0-1 in z... I don't remember right now). You then pass the shader a vertex thats close to the origin, so no huge loss in precision, and a transform matrix that was calculated with double precision.

That's way better than sending the shader a vertex with much larger values since you lose a bunch of precision right away.

share|improve this question
    
It's not clear from your question why you can't simply modify the transform matrix to do whatever offset you are applying to each vertex. I can't think of any reason transforming on the CPU or GPU would have any affect on the precision - maybe you can clarify if I'm not seeing the issue. –  Jeff Gates Jul 25 '12 at 9:34
    
@JeffGates I believe he's referring to the fact that a vertex with an extremely large floating point coordinate (when baked into a vertex buffer), when translated by a floating point matrix to near the origin, may lose a substantial amount of precision. –  John Calsbeek Jul 25 '12 at 14:50
    
If you have a vertex at translate it to near the origin by subtracting on the CPU or using the matrix math on the GPU, it should have the same effects. Matrix operations are just adds and multiplies no less precise than CPU operations. The only way I can even think of that would cause a precision change is if the CPU representation were ints vs a float rep on the GPU - this is wild speculation so my question was to try and find out exactly why the poster is losing precision. –  Jeff Gates Jul 25 '12 at 18:25
    
I'm using double precision on the CPU which is adequate for my values, but the GPU uses 32-bit floats, which aren't okay. Using double precision to calculate the final transform matrix and then sending it to the shader to transform a vertex that's close to the origin loses less precision compared to calculating the final transform matrix on the GPU. –  Pris Jul 25 '12 at 19:09
    
Followup question, what do you do with a vertex when you offset it and it is not in a valid float? (I'm trying to get a sense of what your CPU offset is actually doing to 'get you more precision') –  Jeff Gates Jul 25 '12 at 21:04

1 Answer 1

up vote 0 down vote accepted

It sounds like your world is not entirely visible on screen at once (you mention creating/destroying objects based on the camera's position, and why else would you need such huge precision?). I would try to divide your world up into grid cells, where each object is entirely contained in a cell, and each cell is backed by its own vertex buffer. Because a cell has finite extent, you can use use normalized integral coordinates for the positions of your vertices, which will be more efficient (from a bits-per-precision standpoint) than floating-point vertices. You can compute a transformation matrix for each individual cell on the CPU (there shouldn't be that many cells, so it should be fairly fast), and the shader can apply it to every vertex.

This will work better if your game is 2D (or, at least, if your three dimensions aren't completely interchangeable), as you'll need significantly fewer cells to cover your world. You should be able to render all visible parts of your world with only four draw calls in the worst case (which should be negligible overhead compared to one draw call).

In order to not constrain the positions of your objects, you may have to treat the borders of your cell as loose (i.e. expand them by half the radius of the largest object; see the picture below).

enter image description here

  • (good) only need to calculate a handful of matrices on the CPU
  • (good) the matrices will maintain precision and be applied by the GPU (fast)
  • (good) only a handful of draw calls
  • (possibly bad) the size of the grid cells may need to be tuned, and if the grid is significantly bigger than the screen, the vertex cost can fluctuate by a factor of 4 or so
  • (bad) much less useful if you need a fully 3D grid
  • (bad) everything in a grid needs to use the same rendering state (standard batching caveat)
share|improve this answer
    
To store a grid, you can use a hashmap, where key is 2d or 3d vector of integers, and value is the list of contained objects. This way empty grid cells consume no RAM at all, regardless on how large the grid is. See my demo here: const.me/articles/bubbles –  Soonts Jul 25 '12 at 14:23
    
Thanks for the reply (@John). When I said 'planetary scale' in my question, I was being literal. The grid idea means I can use latitude and longitude to define cells... it'll be interesting to see how it works out. @Soonts: Thanks for the link! –  Pris Jul 25 '12 at 19:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.