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):
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:
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:
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:
And some pseudocode describing how the script works:
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:
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.
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);
}
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;}
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;
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.
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: