• Hey Guest! Ever feel like entering a Game Jam, but the time limit is always too much pressure? We get it... You lead a hectic life and dedicating 3 whole days to make a game just doesn't work for you! So, why not enter the GMC SLOW JAM? Take your time! Kick back and make your game over 4 months! Interested? Then just click here!

Octree structure in GML - Discussion on implementation

TheSnidr

Heavy metal viking dentist
GMC Elder
Hello!

I would like to start a discussion on octree data structures and how they can be written to linear buffers in GML, as well as present my solution for critique. GML supports a limited number of data structures, and octrees aren't one of them, so they have to be stored in other clever ways to be reasonably fast to read and write to.

Before getting started, you can check out a demonstration on my implementation here:
Download example .yyz (GMS2 only, sorry)

I will be using 3D model collisions as an example, since this is what my solution is based on.
Say that you have the following 3D level model, and you want your player to check for collisions with it.

What you could do is to loop through all the triangles in the model and see whether or not the payer intersects any of them, and if so, displace the player out of the level model... but this will quickly bog your game down as the number of triangles increases.
Instead, you may want to partition the model into smaller pieces and have the player only check the triangles that are in the same partition as itself. There are many ways to do this. One way is to split the model into equally sized partitions based on the number and average size of the triangles. This is probably the simplest solution, but now most of the partitions will not be storing any information at all. In other words, it uses an unnecessarily large amount of memory.

Octrees are a more memory efficient way of partitioning the model based on the density of the geometry. The splitting process is done recursively by analyzing the triangles in the current region, and splitting it up into eight new regions if it meets certain criteria. Then the process is repeated for each of the child regions.
The result might look something like this:

This was generated with GML using the method I'm about to present. You can see how the regions are split into smaller pieces around denser areas.

Once a model has been imported into GM with a custom model format, you can turn it back into a normal buffer. Since most 3D collision scripts require triangles in the form of three points and a normal, we can read from the model buffer and generate a simplified collision buffer like this (only works with pr_trianglelist):
Code:
/////////////////////////////////////////////////////
//---Create collision buffer from vertex buffer---///
format_bytes = 9 * 4 //This will depend on your vertex format, you'll have to find out how many bytes each triangle in your format has
tempModelBuffer = buffer_create_from_vertex_buffer(argument0, buffer_fixed, 4); //Create buffer from vertex buffer
collisionBuffer = buffer_create(0, buffer_grow, 4);
bufferSize = buffer_get_size(tempModelBuffer);
for (i = 0; i < bufferSize; i += format_bytes * 3)
{
    //Write three vertices in a row
    for (j = 0; j < 3; j ++)
    {
        buffer_seek(tempModelBuffer, buffer_seek_start, i + j * format_bytes)
        for (k = 0; k < 3; k ++)
        {
            //Copy vertex information from model to collision buffer
            vert[j * 3 + k] = buffer_read(tempModelBuffer, buffer_f32);
            buffer_write(collisionBuffer, buffer_f32, vert[j * 3 + k]);
        }
    }
    //Make triangle normal from the cross product of two triangle lines
    cross_product(vert[3] - vert[0], vert[4] - vert[1], vert[5] - vert[2], vert[6] - vert[0], vert[7] - vert[1], vert[8] - vert[2]);
    normalize(returnX, returnY, returnZ);
    buffer_write(collisionBuffer, buffer_f32, returnX);
    buffer_write(collisionBuffer, buffer_f32, returnY);
    buffer_write(collisionBuffer, buffer_f32, returnZ);
}
This provides a simple way to access the triangles for collision checking. To read the entire triangle, just use buffer_seek on the position of the first vertex in the triangle, and read buffer_f32 12 times to get the three vertices and the triangle normal.
I'll post the collision_create_buffer script in its entirety here in case you'd like to skim through it:
Code:
/// @description smf_collision_create_buffer(modelIndex, bleedOver)
/// @param modelIndex
/// @param bleedOver
/*
THIS SHOULD NOT BE USED INGAME. ALWAYS PRECOMPILE YOUR COLLISION BUFFERS. THIS CAN EASILY BE DONE WITH THE SMF TOOL
Creates a collision buffer for the given model, so that collision checking can be performed later.
The model is split into an octree structure. Triangles that are outside a region, but not further away than bleedOver, are added to the region anyway

Script made by TheSnidr
www.TheSnidr.com
*/
var i, j, k, l, vert, Min, Max, modelSize, regionTriList, levels, tempColBuff, tempModelBuffer, bufferSize, vertexNum, triangleNum, bleedOver;
tempColBuff = buffer_create(SMF_colBuffHeader, buffer_grow, 2);
tempModelBuffer = buffer_create_from_vertex_buffer(argument0, buffer_fixed, 4);
bufferSize = buffer_get_size(tempModelBuffer);
vertexNum = bufferSize div SMF_format_bytes;
triangleNum = vertexNum div 3;
bleedOver = argument1;
for (i = 0; i < 3; i ++){Min[i] = 99999; Max[i] = -99999;}

/////////////////////////////
//---Find size of model---///
for (i = 0; i < bufferSize; i += SMF_format_bytes)
{
    buffer_seek(tempModelBuffer, buffer_seek_start, i)
    for (j = 0; j < 3; j ++)
    {
        //Find size of model
        vert = buffer_read(tempModelBuffer, buffer_f32);
        Min[j] = min(Min[j], vert);
        Max[j] = max(Max[j], vert);
    }
}
modelSize = max(Max[0] - Min[0], Max[1] - Min[1], Max[2] - Min[2]);

////////////////////////////////////////
//---Write collision buffer header---///
buffer_seek(tempColBuff, buffer_seek_start, 0);
buffer_write(tempColBuff, buffer_u32, SMF_colBuffHeader + triangleNum * SMF_colTriBytes);    /*Position of subdivision part of buffer*/
buffer_write(tempColBuff, buffer_f32, Min[0]);        /*Model x*/
buffer_write(tempColBuff, buffer_f32, Min[1]);        /*Model y*/
buffer_write(tempColBuff, buffer_f32, Min[2]);        /*Model z*/
buffer_write(tempColBuff, buffer_f32, modelSize);    /*Model size*/
buffer_write(tempColBuff, buffer_f32, bleedOver);    /*Bleed over*/
buffer_write(tempColBuff, buffer_u32, 0);            /*Levels*/
repeat 3{buffer_write(tempColBuff, buffer_f32, 0);} /*Placeholders in case more header information will be needed later*/

/////////////////////////////////////////////////////
//---Create collision buffer from vertex buffer---///
for (i = 0; i < bufferSize; i += SMF_format_bytes * 3)
{
    for (j = 0; j < 3; j ++)
    {
        buffer_seek(tempModelBuffer, buffer_seek_start, i + j * SMF_format_bytes)
        for (k = 0; k < 3; k ++)
        {
            //Copy vertex information from model to collision buffer
            vert[j * 3 + k] = buffer_read(tempModelBuffer, buffer_f32);
            buffer_write(tempColBuff, buffer_u16, 65535 * (vert[j * 3 + k] - Min[k]) / modelSize);
        }
    }
    //Make triangle normal
    smf_cross_product(vert[3] - vert[0], vert[4] - vert[1], vert[5] - vert[2], vert[6] - vert[0], vert[7] - vert[1], vert[8] - vert[2]);
    smf_normalize(returnX, returnY, returnZ);
    buffer_write(tempColBuff, buffer_s16, 32767 * returnX);
    buffer_write(tempColBuff, buffer_s16, 32767 * returnY);
    buffer_write(tempColBuff, buffer_s16, 32767 * returnZ);
}

///////////////////////////////////////////////////////////////////
//---Subdivide the model recursively into an octree structure---///
regionTriList = ds_list_create();
for (var i = 0; i < triangleNum; i ++){regionTriList[| i] = i;}
levels = smf_collision_recursive_split(tempColBuff, regionTriList, 0, 0, 0, 65535, 65535 * bleedOver / modelSize, 0);
returnBuffer = buffer_create(buffer_tell(tempColBuff), buffer_fixed, 2);
buffer_copy(tempColBuff, 0, buffer_tell(tempColBuff), returnBuffer, 0);

//Write the recursive depth to collision buffer
buffer_seek(returnBuffer, buffer_seek_start, 6 * 4);
buffer_write(returnBuffer, buffer_u32, levels);

//Clean up leftovers
buffer_delete(tempColBuff);
buffer_delete(tempModelBuffer);
ds_list_destroy(regionTriList);

return returnBuffer;

Now that we have easy access to the triangles, we can start subdividing them into smaller sections. Let's go through this step by step, with some code along the way:
Create a list of all the triangles in the current region (for the first region, this will be all the triangles in the model). To make things simple, I'll map the first triangle to index 0, the second triangle to index 1 etc so that for the first region, we end up with these two lines of code:
Code:
//Write all triangles in the model to a list
regionTriList = ds_list_create();
for (var i = 0; i < triangleNum; i ++){regionTriList[| i] = i;}
Now we can initiate the recursion. The recursive script needs to know the index of the buffer to write to, it needs a list of all the triangles its region contains, it needs information on the spatial position and size of the current region, and it needs to know the depth of recursion to be able to stop before going too deep.
I'll post the recursive script in its entirety, and then we'll go through how it's intended to work:
Code:
/// @description smf_collision_recursive_split(collisionBuffer, region_tri_list, regionX, regionY, regionZ, regionSize, bleedOver, level)
/// @param collisionBuffer
/// @param regionTriList
/// @param regionX
/// @param regionY
/// @param regionZ
/// @param regionSize
/// @param bleedOver
/// @param level
var i, tri, triInd, triVerts, rx, ry, rz, xx, yy, zz, splitList, vx, vy, vz, vr, maxX, maxY, maxZ, minX, minY, minZ, splitPos, tempLevel, is_split, bufferCurrentPos, bufferRegionPos, boxSize;
var colBuffer = argument0;
var regionTriList = argument1;
var regionX = argument2;
var regionY = argument3;
var regionZ = argument4;
var regionSize = argument5 / 2;
var bleedOver = argument6;
var level = argument7;
var triNum = ds_list_size(regionTriList);
var returnLevel = level;

//Exit condition, write a list of all triangles in this region to the buffer
if level > 0 and (level >= 10 or triNum < 30 or regionSize <= 4 * bleedOver)
{
    buffer_write(colBuffer, buffer_u16, triNum);
    for (i = 0; i < triNum; i ++)
    {
        buffer_write(colBuffer, buffer_u16, regionTriList[| i]);
    }
    return 0;
}

//Write placeholders for the pointers to the 8 next regions
bufferRegionPos = buffer_tell(colBuffer);
for (i = 0; i < 8; i ++)
{
    splitList[i] = ds_list_create();
    buffer_write(colBuffer, buffer_s32, 0);
}
splitPos[0] = buffer_tell(colBuffer);

//Loop through all triangles in this region and assign them to the regions they cross
rx = regionX + regionSize / 2;
ry = regionY + regionSize / 2;
rz = regionZ + regionSize / 2;
boxSize = regionSize / 2 + bleedOver;
for (tri = 0; tri < triNum; tri ++)
{
    triInd = regionTriList[| tri];
    triVerts = smf_get_triangle_fast(colBuffer, triInd);
    for (i = 0; i < 8; i++)
    {
        if smf_tri_box_intersection(rx + regionSize*(i mod 2), ry + regionSize*((i div 2) mod 2), rz + regionSize*(i div 4), boxSize, boxSize, boxSize, triVerts)
        {
            ds_list_add(splitList[i], triInd);
        }
    }
}

//Split each of the 8 subdivisions in a recursive manner. Each recursion writes itself to the buffer
buffer_seek(colBuffer, buffer_seek_start, splitPos[0]);
for (i = 0; i < 8; i ++)
{
    splitPos[i] = buffer_tell(colBuffer)
    tempLevel = smf_collision_recursive_split(colBuffer, splitList[i], regionX + regionSize * (i mod 2), regionY + regionSize * ((i div 2) mod 2), regionZ + regionSize * (i div 4), regionSize, bleedOver, level + 1);
    is_split[i] = (tempLevel > 0); //Level is never 0, but the script returns 0 if the region is not split. Dual functionality, b*tch!
    returnLevel = max(returnLevel, tempLevel + (tempLevel == 0));
    ds_list_destroy(splitList[i]);
}

//Write the positions in the buffer of each child region
bufferCurrentPos = buffer_tell(colBuffer);
buffer_seek(colBuffer, buffer_seek_start, bufferRegionPos)
for (i = 0; i < 8; i ++)
{
    //If the region is split, the result is positive
    //If the region is not split, the result is negative
    buffer_write(colBuffer, buffer_s32, splitPos[i] * (2 * is_split[i] - 1));
}
buffer_seek(colBuffer, buffer_seek_start, bufferCurrentPos)

//Returns the recursive depth of the octree
return returnLevel;
And some pseudocode describing how the script works:
Code:
- If this region contains less than 30 triangles, write the triangles to the buffer and exit the recursion. Otherwise the script will continue.
- Write 8 placeholder values to the buffer. These will later be replaced with the buffer positions of the next 8 regions
- Loop through all triangles in the region and assign them to the child regions they intersect. One triangle may intersect multiple regions, and will then be added to all of them.
- Run the recursive split script 8 times, once for each child region. Save the buffer positions of the child region.
- Write the buffer position of the child region to the 8 placeholders we made earlier.
Now we've created a single buffer that contains all the information we need to perform collision calculations. The start of the buffer contains the vertex information, and the end of the buffer contains the octree. Reading from the octree buffer requires some jumping back and forth, and has to be done like this:
1. Start by seeking to the octree part of the buffer.
2. Find out which child region you're in, and seek to the corresponding buffer position.
3. If the current region is split, repeat step 2 and 3
4. If the current region is not split, read the number of triangles in this region. Add all the triangles in this region to an array, and return the array.
The resulting array will be sent to the collision script, which will be able to loop through all the triangles in the region and check for collisions.
Here's the script itself:
Code:
/// @description smf_collision_get_region(collisionBuffer, x, y, z)
/// @param subdivisionBuffer
/// @param x
/// @param y
/// @param z
/*
Returns an array containing the buffer positions of all triangles in this region
The given coordinates have to be in u16 integer space, not in world space!
This means that they can only be in the range covered by 16-bit unsigned integers where (0, 0, 0) is mapped to the minimum
position of the collision buffer's bounding box, and (65535, 65535, 65535) is mapped to the maximum.

Script made by TheSnidr
www.TheSnidr.com
*/
var r, n, colBuffer = argument0, rS = 65535, ret = -1;
buffer_seek(colBuffer, buffer_seek_start, 0);
r = buffer_read(colBuffer, buffer_u32);
while r
{
    rS /= 2;
    if (argument1 >= rS){argument1 -= rS; r += 4;}
    if (argument2 >= rS){argument2 -= rS; r += 8;}
    if (argument3 >= rS){argument3 -= rS; r += 16;}
    buffer_seek(colBuffer, buffer_seek_start, r)
    r = buffer_read(colBuffer, buffer_s32);
}
buffer_seek(colBuffer, buffer_seek_start, -r);
n = buffer_read(colBuffer, buffer_u16);
repeat n{ret[--n] = buffer_read(colBuffer, buffer_u16);}
return ret;

And that's my implementation! Any thoughts? I've been told buffers are suboptimal for reading lots of data, but then again, it allows for more precise memory management.
 
Last edited:
M

Misu

Guest
Im still trying to get my head on how to make a decent octree collision system myself. You seem to nailed it good here. Although I thought perhaps there is a much simpler way of establishing through all these processes. I understand clearly that a separate customize model format is required to be able to pick up the xyz of every vertex applied on a model easily.
The only thing Im not clear of in this explanatory thread is how you go about updating a models vertex if it is dynamic.

In other words, what do you do to update the collision buffer if a vertex in a model is changed within the game (in case of animation or change of positions)?
Do you use the same script to recreate the collision buffer for that case? If so, wouldnt that cost performance?
What is the size limit you have in mind on reading and storing a model (by proportion) within a buffer?

Also here is something I like to mention about octree collisions.

I believe octree collisions are very useful for precise collision on complex models. Although not many people would go for precise collision if its a basic model structure or something without physics. On the real-side thought, how important it is to you to add such mechanism in the game? Does a collision need to be precise at all? I know lot of open world games use it for a good reason and also games with realistic physics need them as well. But if I need a collision system, I think first if it plays an important role in the game or if my model structure experiments complicated positions and angles for the interaction of the entities. Afterwards, I can determine the right collision to do the job. Just a note that a very basic primitive collisions can process less than an octree system but cannot get precise collisions like octree can. So it all depends actually on what is really necessary for a specific kind of game. I would love to use octree for any open world games I can make in the future (main reason why Im busting my head on making one myself). Think about it, simple collision as performance -wise for casual or simple games versus octree collision as complicated procedure for complex-structured games. It all depends on what is best for your game.
 
M

mothteeth

Guest
Hi, this is a pretty neat demo :)

I can't bring too much to the table in terms of this specific GML implementation, but after reading @Misu's comment, I thought I'd mention an alternative to Quadtrees that I have more experience with. I've been working on an "infinite" Open World game at work, and we have been using a lot of variations on the theme of Spatial Hashing. I'm not sure if this is very relevant to the original post, but I wanted to bring it into the conversation since it relates to some other ways people use Octrees in games.

Spatial Hashes are similar to Octrees, but they have a few characteristics that I think make them more useful for open worlds, proximity checking of large numbers of objects in an arbitrary space, etc. They can perform better in some cases, particularly when used with areas of unknown size.

There are lots of articles about them on the web, but the basic idea is that you divide space into uniformly sized cells, and store them in some kind of Dictionary or lookup data structure that uses the cell coordinate of the cell as a key. The important detail here is that the Dictionary is only sparsely populated, ie you only create a cell for places that actually have content in them. This means you can store information about objects over an abritrarily sized area without allocating an infinitely large array. Then, when you want to check if there is something in a particular area, you just create a key and check the Dictionary for content.

Another advantage of this technique is that it is fairly simple to comprehend and implement. (Simpler than Octrees I think, at least in my mind.)

You can use the spatial hash to store procedural content, which you build around the player as they move about, or you can use it on a smaller scale to keep track of entities in a scene. It gives you an efficient broad phase for collision tests.

I came across this article that compares the two techniques. It has a nice visualisation showing the difference:

https://zufallsgenerator.github.io/2014/01/26/visually-comparing-algorithms/

I've been thinking a bit about how I might implement Spatial Hashing in GML. I'm not sure which data structure would be the most suitable, but I think using Maps filled with Lists might work well. As for the keys, I think I would have to use strings, and just build keys that used x and y cell coordinates, like "324_34". I used this method when I made a spatial hash in JavaScript. (In C++ or C# you can just overload the equality operators of a custom key type containing integer coordinates.) I'd be curious to hear any suggestions on this.
 

GMWolf

aka fel666
Here are my thoughts on writing trees to a single buffer.
If we hold no further information, the actual order of the octants do not help much with looking up the regions.
A way to accelerate this would be to make use of an index.
The Index would represent the fully unpruned octree. This would allow the index to be represented as an essentially complete tree. Each octant of the index would hold null if the octant is subdivided once pruned, or a pointer to the vertex data if the octant is a leaf node once pruned.

This index would allow you to more efficiently traverse the tree, as the intervals to other nodes could be predicted.
This would allow you to both find parent and child nodes of any node in the tree. (Much like how it is done in heaps).
The predictable intervals should allow you to find a node at any depth level given a position in space.
You could then use a binary style search for the leaf node, by first finding the value of the index at mid depth, then searching for a higher depth if index is empty, or lower depth is index has leaf node.

The exact algorithm to find the nodes at any depth I have not yet worked out, but it is clear to me it is possible, by first finding the leaf node of the index (simple div operations), and working from there.

This should make the algorithm go from a log(n) relationship to a log(log(n)) relationship.

This was written I'm bed on my phone, so sorry if it isnt clear. I would be happy to provide more detail with diagrams, etc If necessary.

[Edit]
I said the index lookup would be similar to heaps. But its not. I'll work this out later, I'm fairly certain its doable.
[reedit]
I worked a simpler, and more efficient index.
Will write it up neat. I put the old idea in the spoiler above.

[Edit once-more]
Alright, So im fully awake and on my PC.

The data structure I will propose should allow to access the leaf nodes in O[1] time, by introducing only a little bit of memory overhead.

The trick is still to use an index. The index would simply be a 3d grid, with each cell pointing to the leaf node of the model it is in. Finding the leaf node at any position now becomes as easy as looking at the adress in the cell containing the point. All done in O[1] time.

The introduction of the index also means that only the leaf nodes need to be stored i the final buffer.
The final buffer format could look as follows:
Code:
width, height, length of model bounding box.
number of subdivisions of index
index: sequence of i32 seek positions to leaf nodes.
leaf nodes: number of triangles: list of points.

The numbers in the index show what seek position in the buffer to go to. The numbers in the octree leaf nodes represent their position in the buffer. (Actuall values would not look like that, naturally.)

Contructing such a buffer would be quite simple:
You would first construct the octree as outlined by @TheSnidr . (call is the data octree)
You would then only keep the leaf nodes with triangle data in them, and store them in the buffer with enough offset to store the index. As you do so, you would build another octree with just the addresses of the data being put in the buffer as the leaf nodes of this new tree. (call it the address octree).
You would then loop through a 3d grid, and construct the index by finding the addresses of the leaf node of each grid point by looking at the address octree.

You can now free the address and data octree. YOu are left with a buffer containing the index, and just the relevant octants with triangle data.

The extra space required is rather small, as adresses can be stored in single u32 integers, more so when you consider only the leaf nodes of the octree are stored.
This new index can be used both when doing point-to-model collisions, and model to model collisions. (you can loop through the leaf nodes of one model, and look at the index on the other model, yielding a O[n] relationship, as opposed to a O[n Log n] the non-index octree would yield).


As for buffers, They are about twice as slow as arrays (when using yyc), but for 32 bit values, use about 1/2 or 1/3 of the memory.
I rarely have memory problems in my games, so i would go the array route.
If using the previously mentioned index, you could even store array reference of the leaf node in the index rather than the seek position to go to, which could lead to better looking code. (with no additional performance costs)
 
Last edited:

RujiK

Member
Like @mothteeth, I haven't worked with quads or octrees, but I have used spatial hashing in my relatively large 2d game. I think spatial hashing (SH) would be faster than an octree IF you're working with mostly open terrain. So if your map is a large field with a few trees, SH would out-perform octrees. With a dense forest or city, however, octrees would probably win.

In my case, I used SH for unit-2-unit collisions. Since my world map is pretty large and there are only about 100 NPC's existing at any time, 99.9% of the map will be empty unit-wise. Thus a quad tree would be slower than SH.

For my implementation I add all units into a ds_map based on their round(16,16) position. If there is anyone in the same cell or one cell over, I perform a detailed collision. The performance boost between using SH and brute force checking all units was considerable. 250 units ran at 7 fps in native but ran at 150 fps with SH. In my case it worked extremely well.

I'm not sure how helpful this is to @TheSnidr, but I always like to have an alternative method in the back of my head for any complex tasks. Great stuff BTW.
 

GMWolf

aka fel666
So all this talk abput spacial hashing, sounding like a super cool technique, turns put to be a technique I used ages ago xD
There are problems with it though, for instance, it will end up using a lot of memory. When i implemented it in GM, memory was a bit of an issue with very large models of varying density.

I believe the data structure i outlined above to be a better alternative, as you retain the O[1] nature of spacial hashing, but does better in terms of memory usage on models varying density (quite common in games).
 

TheSnidr

Heavy metal viking dentist
GMC Elder
[...]The only thing Im not clear of in this explanatory thread is how you go about updating a models vertex if it is dynamic.

In other words, what do you do to update the collision buffer if a vertex in a model is changed within the game (in case of animation or change of positions)?
Creating an octree is a fairly slow process; in general, performing recursion in real time is a bit risky. Doing it with the large amount of data that a decent level model contains, even more so. It's best to precompile the octree and simply make the model not change. Linear transformations are easily accounted for by multiplying the player's coordinates with the inverse of the transformation matrix. This means the model and the octree can be moved, rotated and scaled without having to recreate the structure.
What is the size limit you have in mind on reading and storing a model (by proportion) within a buffer?
The octree saves triangle indices as two-byte values (ie. using buffer_u16), and because of this, the maximum triangle limit is 65,535. If you need more triangles than this, simply change it to buffer_u32 and you'll in theory be able to store 4,294,967,295 triangles. Unless your computer catches fire first.
Also here is something I like to mention about octree collisions.

I believe octree collisions are very useful for precise collision on complex models. Although not many people would go for precise collision if its a basic model structure or something without physics. On the real-side thought, how important it is to you to add such mechanism in the game? Does a collision need to be precise at all? I know lot of open world games use it for a good reason and also games with realistic physics need them as well. But if I need a collision system, I think first if it plays an important role in the game or if my model structure experiments complicated positions and angles for the interaction of the entities. Afterwards, I can determine the right collision to do the job. Just a note that a very basic primitive collisions can process less than an octree system but cannot get precise collisions like octree can. So it all depends actually on what is really necessary for a specific kind of game. I would love to use octree for any open world games I can make in the future (main reason why Im busting my head on making one myself). Think about it, simple collision as performance -wise for casual or simple games versus octree collision as complicated procedure for complex-structured games. It all depends on what is best for your game.
What do you mean by simple collision? Most 3D GM games get away with 2D collision systems because the gameplay isn't actually 3D. But what if you're making a game like this:
The engine in the video uses a combination of 3D model collisions and collisions with mathematical primitives. Using one type of collision engine doesn't exclude other kinds!

Hi, this is a pretty neat demo :)

I can't bring too much to the table in terms of this specific GML implementation, but after reading @Misu's comment, I thought I'd mention an alternative to Quadtrees that I have more experience with. I've been working on an "infinite" Open World game at work, and we have been using a lot of variations on the theme of Spatial Hashing. I'm not sure if this is very relevant to the original post, but I wanted to bring it into the conversation since it relates to some other ways people use Octrees in games.

Spatial Hashes are similar to Octrees, but they have a few characteristics that I think make them more useful for open worlds, proximity checking of large numbers of objects in an arbitrary space, etc. They can perform better in some cases, particularly when used with areas of unknown size.

There are lots of articles about them on the web, but the basic idea is that you divide space into uniformly sized cells, and store them in some kind of Dictionary or lookup data structure that uses the cell coordinate of the cell as a key. The important detail here is that the Dictionary is only sparsely populated, ie you only create a cell for places that actually have content in them. This means you can store information about objects over an abritrarily sized area without allocating an infinitely large array. Then, when you want to check if there is something in a particular area, you just create a key and check the Dictionary for content.

Another advantage of this technique is that it is fairly simple to comprehend and implement. (Simpler than Octrees I think, at least in my mind.)

You can use the spatial hash to store procedural content, which you build around the player as they move about, or you can use it on a smaller scale to keep track of entities in a scene. It gives you an efficient broad phase for collision tests.

I came across this article that compares the two techniques. It has a nice visualisation showing the difference:

https://zufallsgenerator.github.io/2014/01/26/visually-comparing-algorithms/

I've been thinking a bit about how I might implement Spatial Hashing in GML. I'm not sure which data structure would be the most suitable, but I think using Maps filled with Lists might work well. As for the keys, I think I would have to use strings, and just build keys that used x and y cell coordinates, like "324_34". I used this method when I made a spatial hash in JavaScript. (In C++ or C# you can just overload the equality operators of a custom key type containing integer coordinates.) I'd be curious to hear any suggestions on this.
This is a very interesting suggestion, I haven't read about spatial hashes before! How would it fare against large level models with varying geometric density? All the cells would have to be uniform in size, would they not?
Taken to the extreme, imagine for example a small town in the middle of a large field. The town has a high triangle density since it contains several buildings, and the buildings have walls and the walls have bricks and the bricks have small irregularities in their surface. The field consists of large triangles with little detail. Wouldn't the size of the cells need to be small enough to adequately subdivide the bricks of the houses - while also storing the triangles in the field with the same precision?

Here are my thoughts on writing trees to a single buffer.
If we hold no further information, the actual order of the octants do not help much with looking up the regions.
A way to accelerate this would be to make use of an index.
The Index would represent the fully unpruned octree. This would allow the index to be represented as an essentially complete tree. Each octant of the index would hold null if the octant is subdivided once pruned, or a pointer to the vertex data if the octant is a leaf node once pruned.

This index would allow you to more efficiently traverse the tree, as the intervals to other nodes could be predicted.
This would allow you to both find parent and child nodes of any node in the tree. (Much like how it is done in heaps).
The predictable intervals should allow you to find a node at any depth level given a position in space.
You could then use a binary style search for the leaf node, by first finding the value of the index at mid depth, then searching for a higher depth if index is empty, or lower depth is index has leaf node.

The exact algorithm to find the nodes at any depth I have not yet worked out, but it is clear to me it is possible, by first finding the leaf node of the index (simple div operations), and working from there.

This should make the algorithm go from a log(n) relationship to a log(log(n)) relationship.

This was written I'm bed on my phone, so sorry if it isnt clear. I would be happy to provide more detail with diagrams, etc If necessary.

[Edit]
I said the index lookup would be similar to heaps. But its not. I'll work this out later, I'm fairly certain its doable.
[reedit]
I worked a simpler, and more efficient index.
Will write it up neat. I put the old idea in the spoiler above.

[Edit once-more]
Alright, So im fully awake and on my PC.

The data structure I will propose should allow to access the leaf nodes in O[1] time, by introducing only a little bit of memory overhead.

The trick is still to use an index. The index would simply be a 3d grid, with each cell pointing to the leaf node of the model it is in. Finding the leaf node at any position now becomes as easy as looking at the adress in the cell containing the point. All done in O[1] time.

The introduction of the index also means that only the leaf nodes need to be stored i the final buffer.
The final buffer format could look as follows:
Code:
width, height, length of model bounding box.
number of subdivisions of index
index: sequence of i32 seek positions to leaf nodes.
leaf nodes: number of triangles: list of points.

The numbers in the index show what seek position in the buffer to go to. The numbers in the octree leaf nodes represent their position in the buffer. (Actuall values would not look like that, naturally.)

Contructing such a buffer would be quite simple:
You would first construct the octree as outlined by @TheSnidr . (call is the data octree)
You would then only keep the leaf nodes with triangle data in them, and store them in the buffer with enough offset to store the index. As you do so, you would build another octree with just the addresses of the data being put in the buffer as the leaf nodes of this new tree. (call it the address octree).
You would then loop through a 3d grid, and construct the index by finding the addresses of the leaf node of each grid point by looking at the address octree.

You can now free the address and data octree. YOu are left with a buffer containing the index, and just the relevant octants with triangle data.

The extra space required is rather small, as adresses can be stored in single u32 integers, more so when you consider only the leaf nodes of the octree are stored.
This new index can be used both when doing point-to-model collisions, and model to model collisions. (you can loop through the leaf nodes of one model, and look at the index on the other model, yielding a O[n] relationship, as opposed to a O[n Log n] the non-index octree would yield).


As for buffers, They are about twice as slow as arrays (when using yyc), but for 32 bit values, use about 1/2 or 1/3 of the memory.
I rarely have memory problems in my games, so i would go the array route.
If using the previously mentioned index, you could even store array reference of the leaf node in the index rather than the seek position to go to, which could lead to better looking code. (with no additional performance costs)
Nice suggestion, it's clear you've been thinking about this! However, here comes the problem of storing lots and lots of empty space again. The size of the cells would have to be as small as the smallest subdivision. Imagine the maximal depth of the octree is 10 levels, and this is because a tiny area of the map has a much higher triangle density than the rest. This means the width of the smallest region is 2^(-10). If you want to split the entire map into cells of this size, each side would be divided into 1024. Since 3D space has three dimensions, you'd have to store 1024^3 values, ie. 1073741824 indices. If each of these indices stores a two-byte value (buffer_u16), you'd end up with a buffer of 2147483648 bytes, or roughly 2 gigabytes, to just point at the octree. That's a lot!

Like @mothteeth, I haven't worked with quads or octrees, but I have used spatial hashing in my relatively large 2d game. I think spatial hashing (SH) would be faster than an octree IF you're working with mostly open terrain. So if your map is a large field with a few trees, SH would out-perform octrees. With a dense forest or city, however, octrees would probably win.

In my case, I used SH for unit-2-unit collisions. Since my world map is pretty large and there are only about 100 NPC's existing at any time, 99.9% of the map will be empty unit-wise. Thus a quad tree would be slower than SH.

For my implementation I add all units into a ds_map based on their round(16,16) position. If there is anyone in the same cell or one cell over, I perform a detailed collision. The performance boost between using SH and brute force checking all units was considerable. 250 units ran at 7 fps in native but ran at 150 fps with SH. In my case it worked extremely well.

I'm not sure how helpful this is to @TheSnidr, but I always like to have an alternative method in the back of my head for any complex tasks. Great stuff BTW.
Thank you, I will definitely look into spatial hashes! To me itr seems to be extremely useful for models with a fairly uniform triangle density, but once the density starts varying considerably, octrees appear more useful.
 
M

mothteeth

Guest
How would it fare against large level models with varying geometric density? All the cells would have to be uniform in size, would they not?
Taken to the extreme, imagine for example a small town in the middle of a large field. The town has a high triangle density since it contains several buildings, and the buildings have walls and the walls have bricks and the bricks have small irregularities in their surface. The field consists of large triangles with little detail. Wouldn't the size of the cells need to be small enough to adequately subdivide the bricks of the houses - while also storing the triangles in the field with the same precision?
I absolutely think that a quadtree is a better option for a static 3D model. The point you make about the density of a town compared to an open field proves that I think. My experience with Spatial Hashes has been mainly to deal with larger numbers of moving entities, or to manage a reasonably uniform distribution of static level props in open worlds. I have built quadtrees before, but always ended up going with Spatial Hashes because they seemed to perform well in my situation.

There are problems with it though, for instance, it will end up using a lot of memory. When i implemented it in GM, memory was a bit of an issue with very large models of varying density.

I believe the data structure i outlined above to be a better alternative, as you retain the O[1] nature of spacial hashing, but does better in terms of memory usage on models varying density (quite common in games).
As for memory use in SH, it is possible to make an efficient pooling system for cells, and reuse them when they become empty. The sparse nature of spatial hashing is what makes it very powerful for large areas with mostly empty space, but they do not seem to work well when there is a large amount of variation in density (eg Town vs Field).

Good to know, thanks for the insights. :)
 

chance

predictably random
Forum Staff
Moderator
Interesting discussion. Your (@TheSnidr) approach in the first post seems workable, albeit slow (as you said) for complex scenes. So I'm wondering if you've considered "non-automated" systems where you manually assign bounding boxes (cubes, spheres, rectangular parallelepipeds) to particular scene elements based on their physical extent -- rather than their vertex density. For dynamic objects, these would move with the model, and even rotate if necessary. So collision checking isn't easy, but it might be easier than burrowing into a large data tree.

Seems like assigning the octree level-of-detail based on vertex density, might be overkill for many applications, where a few bounding cubes / cuboids might do just as well.
 

GMWolf

aka fel666
Interesting discussion. Your (@TheSnidr) approach in the first post seems workable, albeit slow (as you said) for complex scenes. So I'm wondering if you've considered "non-automated" systems where you manually assign bounding boxes (cubes, spheres, rectangular parallelepipeds) to particular model or scene elements, regardless of their vertex complexity. For dynamic objects, these would move with the model, and even rotate if necessary. So collision checking isn't easy, but it might be easier than burrowing into a large data tree.

Seems like assigning the octree level-of-detail based on vertex density, might be overkill for many applications, where a few bounding cubes / cuboids might do just as well.
Some thing simmilar to BVH then? They are very popular too.

I think the benchmarking scene here is fundamentally flawed. The more detailed objects (such as the castle) would, in a real life scene not be merged with the terrain. You would more likely have a terrain mesh, and a castle mesh, ech with their own octree. The scene would then be built with either with BVH or spacial hashing.
 

chance

predictably random
Forum Staff
Moderator
Some thing simmilar to BVH then?
Yes, that's exactly what I was thinking. In many cases, the volume hierarchy wouldn't need to be more than a few children deep. An obvious example would be a walking man. He might have a single large parallelepiped for the entire body, enclosing (say) smaller ones for each limb, followed finally by volumes for each jointed section. Seems like you could get by with only three levels for most applications.

I'm sure TheSnidr has thought of this. Conceptually, it's similar to what he described above -- with the exception that the sub-divisions are based on function and physical extent, rather than vertex detail.
 
Top