void Piece::RotateXCCW() {
	isMoved = true;
	unsigned int n = size;
	unsigned int colLimit = floor((float) n / 2.0);
	unsigned int rowLimit = ceil((float) n / 2.0);

	for (unsigned int c = 0; c < n; c++) {
		for (unsigned int d = 0; d < colLimit; d++) {
			for (unsigned int r = 0; r < rowLimit; r++) {

				Voxel* temp = container[c][r][d];
				if (temp != 0) {
					temp = temp->Copy();
				}

				//SwapVoxels(c, r, d, container[n - 1 - r][c][d]);
				SwapVoxels(c, r, d, container[c][d][n - 1 - r]);

				//SwapVoxels(n - 1 - r, c, d, container[n - 1 - c][n - 1 - r][d]);
				SwapVoxels(c, d, n - 1 - r, container[c][n - 1 - r][n - 1 - d]);

				//SwapVoxels(n - 1 - c, n - 1 - r, d, container[r][n - 1 - c][d]);
				SwapVoxels(c, n - 1 - r, n - 1 - d, container[c][n - 1 - d][r]);

				//SwapVoxels(r, n - 1 - c, d, temp);
				SwapVoxels(c, n - 1 - d, r, temp);

			}
		}
	}
}

 virtual void init(Voxel& voxel)
 {
     if(!voxel.grad_dev.empty() || voxel.qsdr)
         voxel.calculate_q_vec_t(q_vectors_time);
     else
         voxel.calculate_sinc_ql(sinc_ql);
 }

/**
 * Performs element-wise addition of `offset` and the position of each voxel.
 * 
 * @param offset
 *          offset vector
 */
void Chunk::shiftVoxels(Position offset)
{
    unsigned long long x;
    unsigned long long y;
    unsigned long long z;

    unsigned long long dx = std::get<0>(offset);
    unsigned long long dy = std::get<1>(offset);
    unsigned long long dz = std::get<2>(offset);

    for(unsigned int i=0;i<this->size;i++)
    {
        for(unsigned int j=0;j<this->size;j++)
        {
            for(unsigned int k=0;k<this->size;k++)
            {
                Voxel currVoxel = this->voxels[i][j][k];

                x = std::get<0>(currVoxel.getPosition());
                y = std::get<1>(currVoxel.getPosition());
                z = std::get<2>(currVoxel.getPosition());
                
                this->voxels[i][j][k].setPosition(std::make_tuple(x+dx, y+dy, z+dz));
            }
        }
    }
}

bool voxelAppartientCylindre(Point origine, Vector vecteur,double rayon, Voxel v){

	Point limite(origine.getX()+vecteur.getX(), origine.getY()+vecteur.getY(),origine.getZ()+vecteur.getZ());
	int distancePointProjete;
	int distanceOrigineProjete;

	for( int i = 0; i<8; i++ ){
		Point projete(v.getSommet(i).projectOnLine(origine,limite));
		distancePointProjete = sqrt( pow(v.getSommet(i).getX()-projete.getX(),2)
				           + pow(v.getSommet(i).getY()-projete.getY(),2) 
				           + pow(v.getSommet(i).getZ()-projete.getZ(),2) 
				   );

		distanceOrigineProjete = sqrt( pow(origine.getX()-projete.getX(),2)
				      	     + pow(origine.getY()-projete.getY(),2) 
				             + pow(origine.getZ()-projete.getZ(),2) 
				   );				   
				   
		if( distancePointProjete > rayon || projete.getY() < origine.getY() || projete.getY() > limite.getY()   ){
			return false;
		}

	}
	
	return true;
}

std::pair<std::pair<ParticleID, Voxel>, bool>
SpatiocyteWorld::new_voxel(const Voxel& v)
{
    const private_coordinate_type private_coord(coord2private(v.coordinate()));
    return new_voxel_private(
        Voxel(v.species(), private_coord, v.radius(), v.D(), v.loc()));
}

bool GridAccel::IntersectP(const Ray &ray) const {
	if (!gridForRefined) { // NOBOOK
		rayTests.Add(0, 1); // NOBOOK
		rayHits.Add(0, 1); // NOBOOK
	} // NOBOOK
	int rayId = ++curMailboxId;
	// Check ray against overall grid bounds
	float rayT;
	if (bounds.Inside(ray(ray.mint)))
		rayT = ray.mint;
	else if (!bounds.IntersectP(ray, &rayT))
		return false;
	Point gridIntersect = ray(rayT);
	// Set up 3D DDA for ray
	float NextCrossingT[3], DeltaT[3];
	int Step[3], Out[3], Pos[3];
	for (int axis = 0; axis < 3; ++axis) {
		// Compute current voxel for axis
		Pos[axis] = PosToVoxel(gridIntersect, axis);
		if (ray.d[axis] >= 0) {
			// Handle ray with positive direction for voxel stepping
			NextCrossingT[axis] = rayT +
				(VoxelToPos(Pos[axis]+1, axis) - gridIntersect[axis]) /
					ray.d[axis];
			DeltaT[axis] = Width[axis] / ray.d[axis];
			Step[axis] = 1;
			Out[axis] = NVoxels[axis];
		}
		else {
			// Handle ray with negative direction for voxel stepping
			NextCrossingT[axis] = rayT +
				(VoxelToPos(Pos[axis], axis) - gridIntersect[axis]) /
					ray.d[axis];
			DeltaT[axis] = -Width[axis] / ray.d[axis];
			Step[axis] = -1;
			Out[axis] = -1;
		}
	}
	// Walk grid for shadow ray
	for (;;) {
		int offset = Offset(Pos[0], Pos[1], Pos[2]);
		Voxel *voxel = voxels[offset];
		if (voxel && voxel->IntersectP(ray, rayId))
			return true;
		// Advance to next voxel
		// Find _stepAxis_ for stepping to next voxel
		int bits = ((NextCrossingT[0] < NextCrossingT[1]) << 2) +
			((NextCrossingT[0] < NextCrossingT[2]) << 1) +
			((NextCrossingT[1] < NextCrossingT[2]));
		const int cmpToAxis[8] = { 2, 1, 2, 1, 2, 2, 0, 0 };
		int stepAxis = cmpToAxis[bits];
		if (ray.maxt < NextCrossingT[stepAxis])
			break;
		Pos[stepAxis] += Step[stepAxis];
		if (Pos[stepAxis] == Out[stepAxis])
			break;
		NextCrossingT[stepAxis] += DeltaT[stepAxis];
	}
	return false;
}

void AbstractPiece::Set(unsigned int col, unsigned int row, unsigned int dep, bool flag) {
	if (!Validate(col, row, dep))
		return;

	Voxel* v = 0;
	if (flag) {
		v = new Voxel();

		VoxelColour colour;
		colour.alpha = 1.0;
		colour.red = 0.0;
		colour.green = 0.0;
		colour.blue = 1.0;
		v->SetColour(colour);

		VoxelLocation location;
		location.col = col;
		location.row = row;
		location.dep = dep;
		v->SetLocation(location);

		VoxelDrawPosition position;
		position.x = 0.0;
		position.y = 0.0;
		position.z = 0.0;
		v->SetPosition(position);
	}
	Set(col, row, dep, v);
}

/**
 * Add edges of the neighbouring path tiles.
 * @param xpos X coordinate of the central voxel with a path tile.
 * @param ypos Y coordinate of the central voxel with a path tile.
 * @param zpos Z coordinate of the central voxel with a path tile.
 * @param slope Imploded path slope of the central voxel.
 * @param dirs Edge directions to change (bitset of #TileEdge), usually #EDGE_ALL.
 * @param use_additions Use #_additions rather than #_world.
 * @param add_edges If set, add edges (else, remove them).
 * @return Updated (imploded) slope at the central voxel.
 */
uint8 AddRemovePathEdges(uint16 xpos, uint16 ypos, uint8 zpos, uint8 slope, uint8 dirs, bool use_additions, bool add_edges)
{
	for (TileEdge edge = EDGE_BEGIN; edge < EDGE_COUNT; edge++) {
		if ((dirs & (1 << edge)) == 0) continue; // Skip directions that should not be updated.
		int delta_z = 0;
		if (slope >= PATH_FLAT_COUNT) {
			if (_path_down_from_edge[edge] == slope) {
				delta_z = 1;
			} else if (_path_up_from_edge[edge] != slope) {
				continue;
			}
		}
		Point16 dxy = _tile_dxy[edge];
		if ((dxy.x < 0 && xpos == 0) || (dxy.x > 0 && xpos == _world.GetXSize() - 1)) continue;
		if ((dxy.y < 0 && ypos == 0) || (dxy.y > 0 && ypos == _world.GetYSize() - 1)) continue;

		TileEdge edge2 = (TileEdge)((edge + 2) % 4);
		bool modified = false;
		if (delta_z <= 0 || zpos < WORLD_Z_SIZE - 1) {
			Voxel *v;
			if (use_additions) {
				v = _additions.GetCreateVoxel(xpos + dxy.x, ypos + dxy.y, zpos + delta_z, false);
			} else {
				v = _world.GetCreateVoxel(xpos + dxy.x, ypos + dxy.y, zpos + delta_z, false);
			}
			if (v != nullptr) {
				uint16 number = v->GetInstance();
				if (number == SRI_PATH) { // Valid path.
					v->SetInstanceData(SetPathEdge(v->GetInstanceData(), edge2, add_edges));
					MarkVoxelDirty(xpos + dxy.x, ypos + dxy.y, zpos + delta_z);
					modified = true;
				} else if (number >= SRI_FULL_RIDES) { // A ride instance. Does it have an entrance here?
					if ((v->GetInstanceData() & (1 << edge2)) != 0) modified = true;
				}
			}
		}
		delta_z--;
		if (delta_z >= 0 || zpos > 0) {
			Voxel *v;
			if (use_additions) {
				v = _additions.GetCreateVoxel(xpos + dxy.x, ypos + dxy.y, zpos + delta_z, false);
			} else {
				v = _world.GetCreateVoxel(xpos + dxy.x, ypos + dxy.y, zpos + delta_z, false);
			}
			if (v != nullptr) {
				uint16 number = v->GetInstance();
				if (number == SRI_PATH) { // Valid path.
					v->SetInstanceData(SetPathEdge(v->GetInstanceData(), edge2, add_edges));
					MarkVoxelDirty(xpos + dxy.x, ypos + dxy.y, zpos + delta_z);
					modified = true;
				} else if (number >= SRI_FULL_RIDES) { // A ride instance. Does it have an entrance here?
					if ((v->GetInstanceData() & (1 << edge2)) != 0) modified = true;
				}
			}
		}
		if (modified && slope < PATH_FLAT_COUNT) slope = SetPathEdge(slope, edge, add_edges);
	}
	return slope;
}

std::pair<std::pair<ParticleID, Voxel>, bool>
SpatiocyteWorld::new_voxel_structure(const Voxel& v)
{
    const bool is_succeeded((*space_).update_voxel_private(ParticleID(), v));
    const coordinate_type coord(private2coord(v.coordinate()));
    return std::make_pair(std::make_pair(ParticleID(),
                Voxel(v.species(), coord, v.radius(), v.D(), v.loc())),
        is_succeeded);
}

void BrickDensityRegion::set(int i, int j, int k, float val) {
    if(i < 0 || i > m_brickData.size_x() ||
       j < 0 || j > m_brickData.size_y() ||
       k < 0 || k > m_brickData.size_z()) {
        printf("Error: setting index out of value [%d, %d, %d]\n", i, j, k);
        exit(1);
    }

    Voxel *tmp = m_brickData(i,j,k);
    tmp->set(0, val);
}

 bool reconstruct(unsigned int thread_count)
 {
     begin_prog("reconstruction");
     voxel.image_model = this;
     voxel.CreateProcesses<ProcessType>();
     voxel.init(thread_count);
     boost::thread_group threads;
     for (unsigned int index = 1;index < thread_count;++index)
         threads.add_thread(new boost::thread(&Voxel::thread_run,&voxel,
                                              index,thread_count,mask));
     voxel.thread_run(0,thread_count,mask);
     threads.join_all();
     return !prog_aborted();
 }

/**
 * Move a voxel stack to this world. May destroy the original stack in the process.
 * @param vs Source stack.
 */
void VoxelStack::MoveStack(VoxelStack *vs)
{
	/* Clean up the stack a bit before copying it, and get lowest and highest non-empty voxel. */
	int vs_first = 0;
	int vs_last = 0;
	for (int i = 0; i < (int)vs->height; i++) {
		Voxel *v = &vs->voxels[i];
		assert(!v->HasVoxelObjects()); // There should be no voxel objects in the stack being moved.

		if (!v->IsEmpty()) {
			vs_last = i;
		} else {
			if (vs_first == i) vs_first++;
		}
	}

	/* There should be at least one surface voxel. */
	assert(vs_first <= vs_last);

	/* Examine current stack with respect to persons. */
	int old_first = 0;
	int old_last = 0;
	for (int i = 0; i < (int)this->height; i++) {
		const Voxel *v = &this->voxels[i];
		if (v->HasVoxelObjects()) {
			old_last = i;
		} else {
			if (old_first == i) old_first++;
		}
	}

	int new_base = std::min(vs->base + vs_first, this->base + old_first);
	int new_height = std::max(vs->base + vs_last, this->base + old_last) - new_base + 1;
	assert(new_base >= 0);

	/* Make a new stack. Copy new surface, then copy the persons. */
	Voxel *new_voxels = MakeNewVoxels(new_height);
	CopyStackData(new_voxels + (vs->base + vs_first) - new_base, vs->voxels + vs_first, vs_last - vs_first + 1, false);
	int i = (this->base + old_first) - new_base;
	while (old_first <= old_last) {
		CopyVoxelObjectList(&new_voxels[i], &this->voxels[old_first]);
		i++;
		old_first++;
	}

	this->base = new_base;
	this->height = new_height;
	delete[] this->voxels;
	this->voxels = new_voxels;
}

/**
 * Change the path type of a currently existing path.
 * @param voxel_pos Coordinate of the voxel.
 * @param path_type The type of path to change to.
 * @param path_spr Imploded sprite number.
 */
static void ChangePathAtTile(const XYZPoint16 &voxel_pos, PathType path_type, uint8 path_spr)
{
	VoxelStack *avs = _additions.GetModifyStack(voxel_pos.x, voxel_pos.y);

	Voxel *av = avs->GetCreate(voxel_pos.z, false);
	AddRemovePathEdges(voxel_pos, path_spr, EDGE_ALL, true, PAS_UNUSED);

	/* Reset flat path to one without edges or corners. */
	if (path_spr < PATH_FLAT_COUNT)
		path_spr = PATH_EMPTY;

	uint8 slope = AddRemovePathEdges(voxel_pos, path_spr, EDGE_ALL, true, _sprite_manager.GetPathStatus(path_type));
	av->SetInstanceData(MakePathInstanceData(slope, path_type));

	MarkVoxelDirty(voxel_pos);
}

//---------------------------------------------------------------------------
void OGLGeo::voxel(Voxel &v_in)
{
//Voxel
int i,j,k,index_temp;
for(k=0;k<v_in.mesh_z;k++)
{
for(j=0;j<v_in.mesh_y;j++)
{
for(i=0;i<v_in.mesh_x;i++)
{
   index_temp=v_in.index(i,j,k);
    if(v_in.flag[index_temp]!=0)
    {
    double x0=v_in.x0+i*v_in.dx;
    double x1=v_in.x0+(i+1)*v_in.dx;
    double y0=v_in.y0+j*v_in.dy;
    double y1=v_in.y0+(j+1)*v_in.dy;
    double z0=v_in.z0+k*v_in.dz;
    double z1=v_in.z0+(k+1)*v_in.dz;
    GL_Box(x0,x1,y0,y1,z0,z1);
    }
}
}
}

 }

/**
 * Examine, and perhaps modify a neighbouring path edge or ride connection, to make it connect (or not if not \a add_edges)
 * to the centre examined tile.
 * @param voxel_pos Coordinate of the neighbouring voxel.
 * @param edge Edge to examine, and/or connected to.
 * @param add_edges If set, add edges (else, remove them).
 * @param at_bottom Whether a path connection is expected at the bottom (if \c false, it should be at the top).
 * @param dest_voxel [out] %Voxel containing the neighbouring path, or \c nullptr.
 * @param dest_inst_data [out] New instance of the voxel. Only valid if \a dest_voxel is not \c nullptr.
 * @param dest_status [out] Status of the neighbouring path.
 * @return Neighbouring voxel was (logically) connected to the centre tile.
 */
static bool ExamineNeighbourPathEdge(const XYZPoint16 &voxel_pos, TileEdge edge, bool add_edges, bool at_bottom,
		Voxel **dest_voxel, uint16 *dest_inst_data, PathStatus *dest_status)
{
	Voxel *v;

	*dest_voxel = nullptr;
	*dest_status = PAS_UNUSED;
	*dest_inst_data = PATH_INVALID;

	v = _world.GetCreateVoxel(voxel_pos, false);
	if (v == nullptr) return false;

	uint16 fences = v->GetFences();
	FenceType fence_type = GetFenceType(fences, edge);
	if (fence_type != FENCE_TYPE_INVALID) return false;

	uint16 number = v->GetInstance();
	if (number == SRI_PATH) {
		uint16 instance_data = v->GetInstanceData();
		if (!HasValidPath(instance_data)) return false;

		uint8 slope = GetImplodedPathSlope(instance_data);
		if (at_bottom) {
			if (slope >= PATH_FLAT_COUNT && slope != _path_up_from_edge[edge]) return false;
		} else {
			if (slope != _path_down_from_edge[edge]) return false;
		}

		PathStatus status = _sprite_manager.GetPathStatus(GetPathType(instance_data));
		if (add_edges && status == PAS_QUEUE_PATH) { // Only try to connect to queue paths if they are not yet connected to 2 (or more) neighbours.
			if (GetQuePathEdgeConnectCount(slope) > 1) return false;
		}

		slope = SetPathEdge(slope, edge, add_edges);
		*dest_status = status;
		*dest_voxel = v;
		*dest_inst_data = SetImplodedPathSlope(instance_data, slope);
		return true;

	} else if (number >= SRI_FULL_RIDES) { // A ride instance. Does it have an entrance here?
		if ((v->GetInstanceData() & (1 << edge)) != 0) {
			*dest_status = PAS_QUEUE_PATH;
			return true;
		}
	}
	return false;
}

void Snake::AddBody(int x, int y, int z)
{
	// if cube is already max size, remove the tail
	if(size >= MaxLength)
	{
		Voxel *temp = Body[size%MaxLength];
		int tx = temp->Get_X();
		int ty = temp->Get_Y();
		int tz = temp->Get_Z();
		Cube->SetVoxel(tx,ty,tz,0);
		free(temp); // frees up the tail in memory
	}

	Body[size%MaxLength] =  new Voxel(Cur_x,Cur_y,Cur_z);
	Cube->SetVoxel(Cur_x,Cur_y,Cur_z,1);	
	size ++;
}

inline bool is_face_visible(const VoxelLibrary &lib, const Voxel &vt, int other_voxel_id) {
	if (other_voxel_id == 0) // air
		return true;
	if (lib.has_voxel(other_voxel_id)) {
		const Voxel &other_vt = lib.get_voxel_const(other_voxel_id);
		return other_vt.is_transparent() && vt.get_id() != other_voxel_id;
	}
	return true;
}

void Fibertracking::trackFiber_forward()
{
  using namespace std;

	Voxel *current = &voxels[cur_voxel_index];
	Vector *curVec;
	
	start_o = *new Vector( (current->getX()+0.5)*voxelext_x, (current->getY()+0.5)*voxelext_y, (current->getZ()+0.5)*voxelext_z );

	curVectorList = *new VectorList();
	
	while (current->getAnisotropy() > min_anisotropy && !current->isVisited() && (fabs(intersec_angle) < max_intersec_angle) )
	{
	  // current->print();
		
		currentFiber.add_at_end(*current);
		
		curVectorList.add_at_end(start_o);  // schreibt den Schnittpunkt an die verkettete Liste
		
		curVec = new Vector((double)(voxels[cur_voxel_index].getDir_Index()), (double)cur_voxel_index, 0.);
		curVectorList.add_at_end(*curVec);

		nextVoxel_forward();

		if ( current == &voxels[cur_voxel_index]) // || voxels[cur_voxel_index].isVisited()
		{
			break;
		}
		else
		{
			current->setVisited(true);
			current = &voxels[cur_voxel_index];
		}
	}
	
	if (current->isVisited())
	{
		n_visited++;
	}
	else
	{
		if (current->getAnisotropy() < min_anisotropy)
		{
			n_aniso++;
		}
		else
		{
			if (fabs(intersec_angle) > max_intersec_angle)
			{
				n_angle++;
			}
		}
	}
}

bool voxelHorsSphere(Voxel voxel, Point centreSphere, double rayonSphere){

	for( int i = 0; i<8; i++ ){
		if( distance(centreSphere, voxel.getSommet(i)) < rayonSphere ){
			return false;
		}
	}
	
	return true;
}

/**
 * Creates a world of flat tiles.
 * @param z Height of the tiles.
 */
void VoxelWorld::MakeFlatWorld(int16 z)
{
	for (uint16 xpos = 0; xpos < this->x_size; xpos++) {
		for (uint16 ypos = 0; ypos < this->y_size; ypos++) {
			Voxel *v = this->GetCreateVoxel(XYZPoint16(xpos, ypos, z), true);
			v->SetFoundationType(FDT_INVALID);
			v->SetGroundType(GTP_GRASS0);
			v->SetGroundSlope(ImplodeTileSlope(SL_FLAT));
			v->ClearInstances();
		}
	}
	for (uint16 xpos = 0; xpos < this->x_size; xpos++) {
		AddFoundations(this, xpos, 0, z, 0xC0);
		AddFoundations(this, xpos, this->y_size - 1, z, 0x0C);
	}
	for (uint16 ypos = 0; ypos < this->y_size; ypos++) {
		AddFoundations(this, 0, ypos, z, 0x03);
		AddFoundations(this, this->x_size - 1, ypos, z, 0x30);
	}
}