Octree implementation crashes

Berfandil

Hey all!

I am currently trying to implement voxel in Godot and am trying to use an octree for storing the voxel points's position in 3D space.

I am storing the data in a file which the program reads, while building the octree of the voxel points - or at least it tries, since it crashes at: (voxel.cpp) "registerVoxelCorner( x_place, y_place, z_place, newVoxelCorner );"

I don't really know what could have gone wrong, spent some time figuring it out, but without any luck. :(

So, here is how it should work:

Data is stored in the .txt file as: first line: <min_x> <max_x> <min_y> <max_y> <min_z> <max_z> --> the first and last position of the voxel points by the axis-es next line: <height of the highest voxel point in the given (x;z) column> <material type of the voxel point> <next voxel point's height> etc. next line: just like before... etc. ( (max_x-min_x)*(max_z-min_z) number of these lines)

I read a line, voxel point after voxel point, and try building the octree, first only having the head node, then appending it when needed, or traversing the already made nodes, getting to the nodes where I can store the actual voxel point's data. This way I get branches and leaves of the octree, the branches having at least one of their next pointers filled (next_greater_or_equal, nest_less), and the leaves having their data pointer filled.

I would really appreciate any help I could get. :)

My code: ( I call the voxel points VoxelCorner. )

Posting it in answer...

Berfandil

--- voxel.h ---

	#include "reference.h"
	#include "voxelcorner.h"
	#include "voxelcorneroctree.h"
	#include "voxelbox.h"
	
	class Voxel : public Reference {
		GDCLASS(Voxel,Reference);
		
		uint32_t min_x;
		uint32_t max_x;
		uint32_t min_y;
		uint32_t max_y;
		uint32_t min_z;
		uint32_t max_z;
		
		VoxelSearchNode *octreeHead;
		
		void registerVoxelCorner( uint32_t &goal_x, uint32_t &goal_y, uint32_t &goal_z, VoxelCorner *newVoxelCorner );
		
	protected:
		static void _bind_methods();
		
	public:
		
		void init_from_file(const String &filename);
		
		Voxel();
	};

--- voxel.cpp ---

	#include "voxel.h"
	#include "os/file_access.h"
	
	void Voxel::init_from_file(const String &filename) {
		
		// open the file
		Error err;
		FileAccess *f = FileAccess::open(filename, FileAccess::READ, &err);
		
		// should check for errors here
		//
		// TBD
		//
		
		// reading the data from the file
		uint32_t num;
		Vector< String > line;
		//
		// read the first line
		line = f->get_line().split(" ");
		min_x = line[0].to_int();
		max_x = line[1].to_int();
		min_y = line[2].to_int();
		max_y = line[3].to_int();
		min_z = line[4].to_int();
		max_z = line[5].to_int();
		//
		// read the remaining lines (the voxel data) and construct the VoxelCorner-s
		for (uint32_t x_place=min_x; x_place<=max_x; ++x_place) {
			for (uint32_t z_place=min_z; z_place<=max_z; ++z_place) {
				//
				line = f->get_line().split(" ");
				//
				uint32_t y_place = line[0].to_int();
				int k = 1;
				while ( y_place != 0 ) {
					//
					unsigned char material_type = line[k].to_int();
					//
					VoxelCorner *newVoxelCorner = memnew( VoxelCorner(material_type) );
					registerVoxelCorner( x_place, y_place, z_place, newVoxelCorner );
					//
					y_place = line[k+1].to_int();
					k += 2;
				}
			}
		}
	}
	
	// placing a new VoxelCorner in the octree
	//
	// the helper function
	//    By the x/y/z direction, it halves the given (between act_max and act_min) space,
	//    then checks which half made this way covers the place we want to put the new VoxelCorner.
	//    If a node exists for that subspace, that node becomes the actual node,
	//    otherwise we create a new node for that subspace and that node becomes the actual node.
	void appendCheckOctreeNode( uint32_t &act_max, uint32_t &act_min, uint32_t &goal, VoxelSearchNode *act_node ) {
		
		double act_delimiter;
		if ( act_min!=act_max ) {
			act_delimiter = ceil( (act_max-act_min) / 2.0 ) + act_min;
		}
		else {
			act_delimiter = act_max;
		}
		
		if ( goal >= act_delimiter ) {
			if ( act_node->next_greater_or_equal==NULL ) {
				act_node->next_greater_or_equal = memnew( VoxelSearchNode );
			}
			act_node = act_node->next_greater_or_equal;
			act_min = act_delimiter;
		}
		else {
			if ( act_node->next_less==NULL ) {
				act_node->next_less = memnew( VoxelSearchNode );
			}
			act_node = act_node->next_less;
			act_max = act_delimiter - 1;
		}
	}
	//
	// the function itself
	void Voxel::registerVoxelCorner( uint32_t &goal_x, uint32_t &goal_y, uint32_t &goal_z, VoxelCorner *newVoxelCorner ) {
		
		VoxelSearchNode *act_node = octreeHead;
		uint32_t act_min_x = min_x;
		uint32_t act_max_x = max_x;
		uint32_t act_min_y = min_y;
		uint32_t act_max_y = max_y;
		uint32_t act_min_z = min_z;
		uint32_t act_max_z = max_z;
		
		// search in the octree, creating new nodes if need be
		while ( act_min_x!=act_max_x || act_min_y!=act_max_y || act_min_z!=act_max_z ) {
			appendCheckOctreeNode( act_max_x, act_min_x, goal_x, act_node );
			appendCheckOctreeNode( act_max_y, act_min_y, goal_y, act_node );
			appendCheckOctreeNode( act_max_z, act_min_z, goal_z, act_node );
		}
		
		act_node->data = newVoxelCorner;
	}
	
	void Voxel::_bind_methods() {
		
		ClassDB::bind_method(D_METHOD("init_from_file"), &Voxel::init_from_file);
		
		ClassDB::bind_method(D_METHOD("get_mesh"), &Voxel::get_mesh);
		
		//ClassDB::bind_method(D_METHOD("subtract_from_mesh"), &Voxel::subtract_from_mesh);
		//ClassDB::bind_method(D_METHOD("add_to_mesh"), &Voxel::add_to_mesh);
	}
	
	Voxel::Voxel() {
		
		;
	}

--- voxelbox.h ---

	#ifndef VOXELBOX_H
	#define VOXELBOX_H
	
	#include "voxelcorner.h"
	
	
	class VoxelCorner;
	
	
	class VoxelBox {
	
	public:
		
		// the VoxelCorner-s at each edge of the VoxelBox
		// naming convention is similar to the one seen for VoxelCorner
		VoxelCorner* corner_xP_yP_zP;
		VoxelCorner* corner_xP_yP_zM;
		VoxelCorner* corner_xP_yM_zP;
		VoxelCorner* corner_xP_yM_zM;
		VoxelCorner* corner_xM_yP_zP;
		VoxelCorner* corner_xM_yP_zM;
		VoxelCorner* corner_xM_yM_zP;
		VoxelCorner* corner_xM_yM_zM;
		
		Vector3 base_point;		// the point inside the box which is to be counted according to the VoxelCorner-s' 		weights
		Vector3 new_point;		// the point in the middle between:
								//								- base_point
								//								- the point where the base_point is translated 		using the least swuares method for it's
								//								  distances from the neighbouring VoxelBox-es' 		base_points
	};
	
	#endif

--- voxelcorner.h ---

	#ifndef VOXELCORNER_H
	#define VOXELCORNER_H
	
	#include "voxelbox.h"
	
	class VoxelBox;
	
	class VoxelCorner {
	
	public:
		
		// the VoxelBox-s on which's corners the VoxelCorner is located at
		// naming convention: if the box's center is positioned in a positive direction on the x-axis compared to the 		Voxelcorner ==> xP (xPlus) ; else it is xM (xMinus) ...
		VoxelBox* box_xP_yP_zP;
		VoxelBox* box_xP_yP_zM;
		VoxelBox* box_xP_yM_zP;
		VoxelBox* box_xP_yM_zM;
		VoxelBox* box_xM_yP_zP;
		VoxelBox* box_xM_yP_zM;
		VoxelBox* box_xM_yM_zP;
		VoxelBox* box_xM_yM_zM;
		
		// the material type
		unsigned char material_type;
		
		VoxelCorner( unsigned char &_material_type ) : material_type(_material_type) {};
	};
	
	#endif

--- voxelcorneroctree.h ---

	#ifndef VOXELCORNEROCTREE_H
	#define VOXELCORNEROCTREE_H
	
	#include "voxelcorner.h"
	
	
	// nodes of a sparse octree
	class VoxelSearchNode {
	
	public:
		
		// not a null pointer   <==>   this node is not a leaf of the tree
		VoxelSearchNode *next_greater_or_equal;
		VoxelSearchNode *next_less;
		
		// not a null pointer   <==>   this node is a leaf of the tree
		VoxelCorner *data;
	};
	
	
	#endif

--- voxel_test_data.txt --- 0 6 0 6 0 6 0 0 0 4 0 0 0 0 0 0 5 0 4 0 3 0 0 6 0 5 0 4 0 3 0 2 0 0 6 0 5 0 4 0 3 0 2 0 0 6 0 5 0 4 0 3 0 2 0 0 5 0 4 0 3 0 0 0 0 6 0 5 0 4 0 3 0 2 0 0 6 0 5 0 3 0 2 0 0 6 0 2 0 0 6 0 5 0 3 0 2 0 0 6 0 5 0 4 0 3 0 2 0 0 0 4 0 0 6 0 5 0 4 0 3 0 2 0 0 6 0 2 0 0 7 0 6 0 2 0 1 0 0 6 0 2 0 0 6 0 5 0 4 0 3 0 2 0 0 4 0 0 0 6 0 5 0 4 0 3 0 2 0 0 6 0 5 0 3 0 2 0 0 6 0 2 0 0 6 0 5 0 3 0 2 0 0 6 0 5 0 4 0 3 0 2 0 0 0 0 5 0 4 0 3 0 0 6 0 5 0 4 0 3 0 2 0 0 6 0 5 0 4 0 3 0 2 0 0 6 0 5 0 4 0 3 0 2 0 0 5 0 4 0 3 0 0 0 0 0 0 4 0 0 0 0 0

Berfandil

I found one problem: The octreeHead is a pointer, and there was no memory space assigned to it, so I added a line to the end of the init_from_file() function: octreeHead = memnew( VoxelSearchNode );

But unfortunately there must be at least one other problem, since it still crashes when run.

Berfandil

Okay, it was still my bad, I had put that line the wrong place, after the reading (and thus the building of the octree is done). So, placing it before that solved the problem, it works as intended now. :)