   Toroidal Memory Access and Vertex Buffer Arrays (VBOs)
  Has anyone come across a good explanation of "Toroidal Memory Access"? So far, I've spent a good deal of time trying to figure out what it is, and how it will help when using Vertex Buffer Arrays (VBOs).The reason that I am looking into this is because I am attempting to implement Geometry Clipmaps which are described in a paper by Hoppe here:Geometry Clipmaps: Terrain Rendering Using Nested Regular GridsThe geometry clipmaping concept is very simple conceptually and, to me at least, easier to understand then quadtrees for implementing terrain.The best that I have found so far was this thread on geometry clipmaps. There is even a small class that dave j posted to help with toroidal access.My issue is understanding how toroidal access works (other than the vague "it wraps around" comment). If I am unable to understand toroidal access/loading into memory, then when I incrementally update an area (ie one row is being dropped off and and a new row is being added because the center has moved) I will do a memcpy(). I guess the next step after I figure out how toroidal memory access works is to implement that with the vertex buffer being in the GPU memory using NeHe tutorial on the vertex buffer extension.While this forum isn't language or hardware specific, I am working in C++ and using OpenGL. Currently, I am planning on using an N x N height map with n=64. From that, I create a buffer that contains GL_TRIANGLES. What that means (for non-OpenGL folk) is that the buffer array will contain groupings of 3 vertices which constitute 1 triangle. So, with a 64x64 heightmap, I would have a buffer that would hold 64x64x3x2 vertices which is 3 points per triangle (obviously) and 2 triangles per square. I haven't decided how many levels of detail I will have as I figure it is best to get one working before I try to do 10+.So, if there is anyone else out there smarter than me who understand this, thanks for the help! When we are done, if I understand, I'd be glad to write out a more formal tutorial to help anyone else undstand as well.Daniel[Edited by - redbaran on December 7, 2005 4:19:00 PM]
  Toroidal = simple wrapping in both u and v, just like walking on the surface of an imaginary weird torus.   ;  Yeah that torus thing threw me when I finally decided to look up the wiki definition of toroidal, seems obvious in retrospect.In practice it is exactly the effect you get when accessing a 2D texture using uv with texture wrapping on.It really is just wrapping around:When an x (or y) coordinate goes higher than the width (or height) of the buffer it starts at 0 again. This can easily be achieved like Hoppe suggests by using the % (mod) operator, but in my system I use a 1D array to map real coordinates to clipmap coordinates to save the fairly costly % operation.When the a clipmap grid is first created, the top left corner (in my implementation anyway) maps to coordinate <0,0> in the VBO. As soon as the camera moves, say x+1, the top left corner of the displayed grid is no longer coordinate <0,0> in the VBO. It will actually be <1,0>, because the column at x=0 now contains the new column added to the right hand side. So when the camera is moving around, keep track of the overall offset from the initial origin (by incrementing a var by the offsets each move), then apply it to all accesses to the VBOs using the % operator like this:void MoveX(int xoffs){    m_nTotalXOffset += xoffs;    // do move ....    //}int GetToroidalX(int x){    return((x+m_nTotalXOffset) % m_nGridSize);}Also I recommend you use tri-strips instead of triangles, because you will send alot less data. They are ideal for drawing regular grids.There is code on my webside, but it is largly uncommented and does not use VBOs. Also it is a spherical clipmap, for planet rendering, not a flat 2D one, so its a bit more complex. Same principles though. The code on my harddisk however does use VBOs, but is in a transitionary phase, so PM me if you want it (it might help, never know). I have been trying to add comments to it aswell.   ;  I think the previous posters have done a good job with explaining what toroidal access is, so I will not go there. I would just like to add that the % operator alone will not always work. For positive grid coordinates it will, but its behavior with negative numbers is undefined, and in most implementations it is not what we need.For example, assume that we have n = 64. If we move down one grid unit, the top row (y = 63) is no longer inside the region and needs to be overwritten with the new bottom row (y = -1). What we want with toroidal access is to have -1 mapped to 63, but -1 % 64 is going to return -1 on most implementations.I came up with this as the simplest possible solution:#define mod(a, b) (((a % b) + b) % b)The first modulus will force negative numbers less than -64 to be within -64 and 0. Then 64 is added to make them positive. And finally the modulus is taken again so that numbers that were already positive stay below 64. This will work for all negative and positive numbers, but now it is even less efficient. If there is a better way to do this, please let me know.bluntman, I'm interested to know how you implemented the 1D array. Wouldn't you need an element for every possible grid coordinate?[edit]I would also suggest that you use indexed vertex buffers so that you only need 64x64 vertices for each region rather than 64x64x3x2.[/edit]   ;  I have been reading the Hoppe paper too and I just got the GPU Gems 2 book thinking that sample code and an binary may be on the book's disk, but all that is there is the shader code, not the whole demo.  I am interested in implementing this technique too.  While I understand what the paper and book chapter are describing, I am having difficulty implementing it.And bluntman, I was going to apply it to a sphere too!  I would love to pick your brain more on this.  Have you considered writing an article on the topic for GameDev.net?   ;  Maybe I'm missing something, but can't you do a modulus for power of two numbers with a bitwise and?  For example, a % 64 == a & 63   ;Quote:Original post by Anonymous PosterMaybe I'm missing something, but can't you do a modulus for power of two numbers with a bitwise and?  For example, a % 64 == a & 63Yes, but I believe the geometry clipmaps algorithm is usually done with a grid size of either 2n - 1 or 2n + 1. I don't remember why, but it mentions it in the GPU implementation paper.   ;  Hey, thanks everyone for responding... I'm definitely starting to understand this (I think). The only place where I'm a little unclear is what the purpose of the xOffset is. I guess let me explain why I think it's not needed using an example. Let's say we have a 10x10 dataset, where 00 indicates a position of [0][0] in the 2D array, and our starting area is a 4x4 square in the upper-left as follows:+-----------+|00 10 20 30|40 50 60 70 80 90| |   |01 11 21 31|41 51 61 71 81 91| |   |02 12 22 32|42 52 62 72 82 92| |   |03 13 23 33|43 53 63 73 83 93+-----------+    04 14 24 34 44 54 64 74 84 94   05 15 25 35 45 55 65 75 85 95  06 16 26 36 46 56 66 76 86 96  07 17 27 37 47 57 67 77 87 97  08 18 28 38 48 58 68 78 88 98  09 19 29 39 49 59 69 79 89 99Now, if I use the equation: 1DPosition = x % width + (y % height) * height where x and y are the indices in the full dataset and width and height are the size of the subset (4 and 4 respectively). So, using that equation, take the value 22 which is at position [2][2]: 2%4 + (2%4)*4 yeilds 10. So, for the whole subset, we end up with the following array of 16:[0] = 00    ((0%4) + (0%4)*4) = 0[1] = 10    ((1%4) + (0%4)*4) = 1[2] = 20    ((2%4) + (0%4)*4) = 2[3] = 30    etc[4] = 01[5] = 11[6] = 21[7] = 31[8] = 02[9] = 12[10] = 22[11] = 32   ((3%4) + (2%4)*4) = (3 + 2*4) = 11[12] = 03 [13] = 13[14] = 23[15] = 33   ((3%4) + (3%4)*4) = (3 + 3*4) = 15Now, let say the subregion moves to the right 1 and now we have:   +-----------+ 00|10 20 30 40|50 60 70 80 90   | | 01|11 21 31 41|51 61 71 81 91   | | 02|12 22 32 42|52 62 72 82 92   | | 03|13 23 33 43|53 63 73 83 93   +-----------+    04 14 24 34 44 54 64 74 84 94   05 15 25 35 45 55 65 75 85 95  06 16 26 36 46 56 66 76 86 96  07 17 27 37 47 57 67 77 87 97  08 18 28 38 48 58 68 78 88 98  09 19 29 39 49 59 69 79 89 99We know our new values easily enough because most likely we would have a function to update the array and we would give it a reference to our full dataset and tell it that we want to add 4 values from the column starting at [4][0]. Then that would go through a loop and add [4][0] [4][1] [4][2] [4][3]. Using the same equation (with no xOffset), to add the [4][2] position, we have this equation: (4%4) + (2%4)*4 which yeilds 8. Now, if you look at the array of 16 that we had, you'll see that 02 was at [8]. So, 42 will now be at that place. Here is the full list of updated indices in the 1Dimensional array:[0] = 40 (it was 00) (equation: (4%4) + (0%4)*4 = 0)[4] = 41 (it was 01) (equation: (4%4) + (1%4)*4 = 4)[8] = 42 (it was 02) (equation: (4%4) + (2%4)*4 = 8) [12] = 43 (it was 03) (equation: (4%4) + (3%4)*4 = 12)Now, lets move one more to the right so our subregion looks like this: +-----------+ 00 10|20 30 40 50|60 70 80 90 | |   01 11|21 31 41 51|61 71 81 91 | |   02 12|22 32 42 52|62 72 82 92 | |   03 13|23 33 43 53|63 73 83 93 +-----------+    04 14 24 34 44 54 64 74 84 94   05 15 25 35 45 55 65 75 85 95  06 16 26 36 46 56 66 76 86 96  07 17 27 37 47 57 67 77 87 97  08 18 28 38 48 58 68 78 88 98  09 19 29 39 49 59 69 79 89 99So, our UpdateColumn function would get the pointer to the dataset and a command telling it to update 4 values starting at [5][0]. It would then do these updates:[1] = 50 (it was 10) (equation: (5%4)+(0%4)*4 = 1)[5] = 51 (it was 11) (equation: (5%4)+(1%4)*4 = 5)[9] = 52 (it was 12) (equation: (5%4)+(2%4)*4 = 9)[13] = 53 (it was 13) (equation: (5%4)+(3%4)*4 = 13)Now, lets go down one so our subregion looks like this:   00 10 20 30 40 50 60 70 80 90 +-----------+   01 11|21 31 41 51|61 71 81 91 | |   02 12|22 32 42 52|62 72 82 92 | |   03 13|23 33 43 53|63 73 83 93 | |    04 14|24 34 44 54|64 74 84 94  +-----------+   05 15 25 35 45 55 65 75 85 95  06 16 26 36 46 56 66 76 86 96  07 17 27 37 47 57 67 77 87 97  08 18 28 38 48 58 68 78 88 98  09 19 29 39 49 59 69 79 89 99Now we would go to an UpdateRow function passing it a pointer to the dataset and telling it to update 4 values starting at [2][4]. We would update the folowing indices [2][4] [3][4] [4][4] [5][4]:[2] = 24 (it was 20) (equation: (2%4)+(4%4)*4 = 2)[3] = 34 (it was 30) (equation: (3%4)+(4%4)*4 = 3)[4] = 44 (it was 40) (equation: (4%4)+(4%4)*4 = 4)[5] = 54 (it was 50) (equation: (5%4)+(4%4)*4 = 5)Now, if we went down again (and this is the last time I'm going to do this), we would have this subsection:   00 10 20 30 40 50 60 70 80 90  01 11 21 31 41 51 61 71 81 91 +-----------+   02 12|22 32 42 52|62 72 82 92 | |   03 13|23 33 43 53|63 73 83 93 | |    04 14|24 34 44 54|64 74 84 94  | |   05 15|25 35 45 55|65 75 85 95 +-----------+   06 16 26 36 46 56 66 76 86 96  07 17 27 37 47 57 67 77 87 97  08 18 28 38 48 58 68 78 88 98  09 19 29 39 49 59 69 79 89 99So, we'd once again call the UpdateRow function giving it the pointer to the dataset and telling it to update 4 values in the row starting at [2][5]. So it would update [2][5] [3][5] [4][5] [5][5] as follows:[6] = 25 (it was 21) (equation: (2%4) + (5%4)*4 = 6)[7] = 35 (it was 31) (equation: (3%4) + (5%4)*4 = 7)[8] = 45 (it was 41) (equation: (4%4) + (5%4)*4 = 8)[9] = 55 (it was 51) (equation: (5%4) + (5%4)*4 = 9)Now, that was all done without any X or Y offset values. The only reason I could see wanting to use an offset would be if we were going to add based on relative coordinates or something. Am I missing something, because this seems to work, or am I just way way off?I definitely see why you would want to worry about negative values, and that's good to have pointed out. The way I plan on doing this, I don't think it will be a problem, but if/when my app blows up, I'll know why, right?So, what are the X and Y offsets for? If I use the equation in the Toroidal class (see the thread I referenced in my first post) which is 1DPosition = (x + xOffset) % width + ((y + yOffset) % height) * height, then how does the xOffset work, is it the offset of the subsection that I am coming from or the offset of the subsection I am transitioning to? My guess, though I haven't spent time with pen and paper, is that it's the offset of the subsection that is being transitioned to and we add vertices with a relative addressing. That make sense?Alright, thanks for the help. I also need to search around for Indexed Vertex Arrays (or buffers, whatever they are called), so if anyone knows of something good off head for me to look at, don't hold back.-RedbaranPS I really do appreciate the help, and I'd like to show my thanks by "rating" everyone that has helped highly, does that matter? Does anyone care about that stuff? Because I'll do it, but not if no one gives a crap!   ;  Sorry I might have been a bit misleading there, as most of what I say comes from what I have worked out, not from the Hoppe paper (because I didn't know it existed when I wrote my clip-map engine).The x and y offsets I use are for accessing the parent of the current grid. Forget about them! I reckon you are best of diving in to a basic implementation and asking questions as you come up against brick walls.My 1D array is actually 2 1D std::deques: std::deque m_XOffsets, m_YOffsets;// Basically I fill them with thier own indicies from 0 to n:void Init(){    for(int i=0; i<m_nSize; i++)    {    m_XOffsets.push_back(i);   m_YOffsets.push_back(i);}}// then when a move in X occurs I either pop from the back and push to the // front or vice versa:void MoveX(int x){    if(x < 0)    {   for(int i=0; i<-x; i++)   {  m_XOffsets.push_front(m_XOffsets.back());  m_XOffsets.pop_back()   }    }    else    {   for(int i=0; i<x; i++)   {  m_XOffsets.push_back(m_XOffsets.front());  m_XOffsets.pop_front()   }    }}// Then instead of:int GetXOffset(int x){    return(x%width);}// We can use:int GetXOffset(int x){    return(m_XOffsets[x]);}Obviously this only maps the values 0 to n to the correct locations in the buffers, not arbitrary values.Making a 2D grid map to a 3D sphere is a tricky problem, when you don't want to completely recalculate it each move, and I ended up just bodging it as best I could. I will talk more about my method if you are interested, but I gotta do some work now!I am not really ready to write an article yet, and there are people here who have been working on this for much longer than I have (Ysaneya and Lutz come to mind).[Edited by - bluntman on December 8, 2005 10:32:17 AM];  Thanks Bluntman!I'm glad that you said that I can ignore the X and Y Offsets. That gives me more confidence that I understand how to use this. I've been working some on using this, but I couldn't do much last night while I was sleeping! I'm going to be working on this today though. I'm going to work first on keeping a 1 dimensional array of the vertex points (an array of 64x64 for me). I'm going to also look into the indexed vertex buffers, which when I looked at last night, I didn't see much, but I'm going to keep looking. I think I might have found enough at the the OpenGL website with some help from the redbook.Also, I couldn't find a link to your web page. While I think what you are doing is a little over my head for now, I am curious more than anything.Well, time jump in head first!Redbaran   