/* Raytracing for vertex to bone/vertex visibility */
static void heat_ray_tree_create(LaplacianSystem *sys)
{
	MFace *mface = sys->heat.mface;
	float (*verts)[3] = sys->heat.verts;
	int totface = sys->heat.totface;
	int totvert = sys->heat.totvert;
	int a;

	sys->heat.bvhtree = BLI_bvhtree_new(totface, 0.0f, 4, 6);
	sys->heat.vface = MEM_callocN(sizeof(MFace*)*totvert, "HeatVFaces");

	for(a=0; a<totface; a++) {
		MFace *mf = mface+a;
		float bb[6];

		INIT_MINMAX(bb, bb+3);
		DO_MINMAX(verts[mf->v1], bb, bb+3);
		DO_MINMAX(verts[mf->v2], bb, bb+3);
		DO_MINMAX(verts[mf->v3], bb, bb+3);
		if(mf->v4) {
			DO_MINMAX(verts[mf->v4], bb, bb+3);
		}

		BLI_bvhtree_insert(sys->heat.bvhtree, a, bb, 2);
		
		//Setup inverse pointers to use on isect.orig
		sys->heat.vface[mf->v1]= mf;
		sys->heat.vface[mf->v2]= mf;
		sys->heat.vface[mf->v3]= mf;
		if(mf->v4) sys->heat.vface[mf->v4]= mf;
	}

	BLI_bvhtree_balance(sys->heat.bvhtree); 
}

/* find the bounding box of an objectinstance in global space */
void global_bounds_obi(Render *re, ObjectInstanceRen *obi, float *bbmin, float *bbmax)
{
	ObjectRen *obr = obi->obr;
	VolumePrecache *vp = obi->volume_precache;
	VertRen *ver= NULL;
	float co[3];
	int a;
	
	if (vp->bbmin != NULL && vp->bbmax != NULL) {
		copy_v3_v3(bbmin, vp->bbmin);
		copy_v3_v3(bbmax, vp->bbmax);
		return;
	}
	
	vp->bbmin = MEM_callocN(sizeof(float)*3, "volume precache min boundbox corner");
	vp->bbmax = MEM_callocN(sizeof(float)*3, "volume precache max boundbox corner");
	
	INIT_MINMAX(bbmin, bbmax);
	
	for(a=0; a<obr->totvert; a++) {
		if((a & 255)==0) ver= obr->vertnodes[a>>8].vert;
		else ver++;
		
		copy_v3_v3(co, ver->co);
		
		/* transformed object instance in camera space */
		if(obi->flag & R_TRANSFORMED)
			mul_m4_v3(obi->mat, co);
		
		/* convert to global space */
		mul_m4_v3(re->viewinv, co);
		
		DO_MINMAX(co, vp->bbmin, vp->bbmax);
	}

/* if end, ob can be NULL */
intptr_t mesh_octree_table(Object *ob, EditMesh *em, float *co, char mode)
{
	MocNode **bt;
	
	if(mode=='u') {		/* use table */
		if(MeshOctree.table==NULL)
			mesh_octree_table(ob, em, NULL, 's');
	   
		if(MeshOctree.table) {
			Mesh *me= ob->data;
			bt= MeshOctree.table + mesh_octree_get_base_offs(co, MeshOctree.offs, MeshOctree.div);
			if(em)
				return mesh_octree_find_index(bt, NULL, co);
			else
				return mesh_octree_find_index(bt, me->mvert, co);
		}
		return -1;
	}
	else if(mode=='s') {	/* start table */
		Mesh *me= ob->data;
		float min[3], max[3];

		/* we compute own bounding box and don't reuse ob->bb because
		 * we are using the undeformed coordinates*/
		INIT_MINMAX(min, max);

		if(em && me->edit_mesh==em) {
			EditVert *eve;
			
			for(eve= em->verts.first; eve; eve= eve->next)
				DO_MINMAX(eve->co, min, max)
		}

bool BKE_mball_minmax_ex(MetaBall *mb, float min[3], float max[3],
                         float obmat[4][4], const short flag)
{
    const float scale = obmat ? mat4_to_scale(obmat) : 1.0f;
    MetaElem *ml;
    bool changed = false;
    float centroid[3], vec[3];

    INIT_MINMAX(min, max);

    for (ml = mb->elems.first; ml; ml = ml->next) {
        if ((ml->flag & flag) == flag) {
            const float scale_mb = (ml->rad * 0.5f) * scale;
            int i;

            if (obmat) {
                mul_v3_m4v3(centroid, obmat, &ml->x);
            }
            else {
                copy_v3_v3(centroid, &ml->x);
            }

            /* TODO, non circle shapes cubes etc, probably nobody notices - campbell */
            for (i = -1; i != 3; i += 2) {
                copy_v3_v3(vec, centroid);
                add_v3_fl(vec, scale_mb * i);
                minmax_v3v3_v3(min, max, vec);
            }
            changed = true;
        }
    }

    return changed;
}

void rtbuild_add(RTBuilder *b, RayObject *o)
{
	float bb[6];

	assert(b->primitives.begin + b->primitives.maxsize != b->primitives.end);

	INIT_MINMAX(bb, bb + 3);
	RE_rayobject_merge_bb(o, bb, bb + 3);

	/* skip objects with invalid bounding boxes, nan causes DO_MINMAX
	 * to do nothing, so we get these invalid values. this shouldn't
	 * happen usually, but bugs earlier in the pipeline can cause it. */
	if (bb[0] > bb[3] || bb[1] > bb[4] || bb[2] > bb[5])
		return;
	/* skip objects with inf bounding boxes */
	if (!finite(bb[0]) || !finite(bb[1]) || !finite(bb[2]))
		return;
	if (!finite(bb[3]) || !finite(bb[4]) || !finite(bb[5]))
		return;
	/* skip objects with zero bounding box, they are of no use, and
	 * will give problems in rtbuild_heuristic_object_split later */
	if (bb[0] == bb[3] && bb[1] == bb[4] && bb[2] == bb[5])
		return;
	
	copy_v3_v3(b->primitives.end->bb, bb);
	copy_v3_v3(b->primitives.end->bb + 3, bb + 3);
	b->primitives.end->obj = o;
	b->primitives.end->cost = RE_rayobject_cost(o);
	
	for (int i = 0; i < 3; i++) {
		*(b->sorted_end[i]) = b->primitives.end;
		b->sorted_end[i]++;
	}
	b->primitives.end++;
}

void BKE_mesh_boundbox_calc(Mesh *me, float r_loc[3], float r_size[3])
{
	BoundBox *bb;
	float min[3], max[3];
	float mloc[3], msize[3];
	
	if (me->bb == NULL) me->bb = MEM_callocN(sizeof(BoundBox), "boundbox");
	bb = me->bb;

	if (!r_loc) r_loc = mloc;
	if (!r_size) r_size = msize;
	
	INIT_MINMAX(min, max);
	if (!BKE_mesh_minmax(me, min, max)) {
		min[0] = min[1] = min[2] = -1.0f;
		max[0] = max[1] = max[2] = 1.0f;
	}

	mid_v3_v3v3(r_loc, min, max);
		
	r_size[0] = (max[0] - min[0]) / 2.0f;
	r_size[1] = (max[1] - min[1]) / 2.0f;
	r_size[2] = (max[2] - min[2]) / 2.0f;
	
	BKE_boundbox_init_from_minmax(bb, min, max);

	bb->flag &= ~BOUNDBOX_DIRTY;
}

static void generate_vert_coordinates(
        DerivedMesh *dm, Object *ob, Object *ob_center, const float offset[3],
        const int num_verts, float (*r_cos)[3], float r_size[3])
{
	float min_co[3], max_co[3];
	float diff[3];
	bool do_diff = false;

	INIT_MINMAX(min_co, max_co);

	dm->getVertCos(dm, r_cos);

	/* Get size (i.e. deformation of the spheroid generating normals), either from target object, or own geometry. */
	if (ob_center) {
		/* Not we are not interested in signs here - they are even troublesome actually, due to security clamping! */
		abs_v3_v3(r_size, ob_center->size);
	}
	else {
		minmax_v3v3_v3_array(min_co, max_co, r_cos, num_verts);
		/* Set size. */
		sub_v3_v3v3(r_size, max_co, min_co);
	}

	/* Error checks - we do not want one or more of our sizes to be null! */
	if (is_zero_v3(r_size)) {
		r_size[0] = r_size[1] = r_size[2] = 1.0f;
	}
	else {
		CLAMP_MIN(r_size[0], FLT_EPSILON);
		CLAMP_MIN(r_size[1], FLT_EPSILON);
		CLAMP_MIN(r_size[2], FLT_EPSILON);
	}

	if (ob_center) {
		float inv_obmat[4][4];

		/* Translate our coordinates so that center of ob_center is at (0, 0, 0). */
		/* Get ob_center (world) coordinates in ob local coordinates.
		 * No need to take into account ob_center's space here, see T44027. */
		invert_m4_m4(inv_obmat, ob->obmat);
		mul_v3_m4v3(diff, inv_obmat, ob_center->obmat[3]);
		negate_v3(diff);

		do_diff = true;
	}
	else if (!is_zero_v3(offset)) {
		negate_v3_v3(diff, offset);

		do_diff = true;
	}
	/* Else, no need to change coordinates! */

	if (do_diff) {
		int i = num_verts;
		while (i--) {
			add_v3_v3(r_cos[i], diff);
		}
	}
}

void BKE_lattice_center_bounds(Lattice *lt, float cent[3])
{
	float min[3], max[3];

	INIT_MINMAX(min, max);

	BKE_lattice_minmax(lt, min, max);
	mid_v3_v3v3(cent, min, max);
}

bool BL_ModifierDeformer::Update(void)
{
	bool bShapeUpdate = BL_ShapeDeformer::Update();

	if (bShapeUpdate || m_lastModifierUpdate != m_gameobj->GetLastFrame()) {
		// static derived mesh are not updated
		if (m_dm == NULL || m_bDynamic) {
			/* execute the modifiers */
			Object* blendobj = m_gameobj->GetBlendObject();
			/* hack: the modifiers require that the mesh is attached to the object
			 * It may not be the case here because of replace mesh actuator */
			Mesh *oldmesh = (Mesh*)blendobj->data;
			blendobj->data = m_bmesh;
			/* execute the modifiers */
			DerivedMesh *dm = mesh_create_derived_no_virtual(m_scene, blendobj, m_transverts, CD_MASK_MESH);
			/* restore object data */
			blendobj->data = oldmesh;
			/* free the current derived mesh and replace, (dm should never be NULL) */
			if (m_dm != NULL) {
				// HACK! use deformedOnly as a user counter
				if (--m_dm->deformedOnly == 0) {
					m_dm->needsFree = 1;
					m_dm->release(m_dm);
				}
			}
			m_dm = dm;
			// get rid of temporary data
			m_dm->needsFree = 0;
			m_dm->release(m_dm);
			// HACK! use deformedOnly as a user counter
			m_dm->deformedOnly = 1;
			DM_update_materials(m_dm, blendobj);
			/* update the graphic controller */
			PHY_IGraphicController *ctrl = m_gameobj->GetGraphicController();
			if (ctrl) {
				float min[3], max[3];
				INIT_MINMAX(min, max);
				m_dm->getMinMax(m_dm, min, max);
				ctrl->SetLocalAabb(min, max);
			}
		}
		m_lastModifierUpdate=m_gameobj->GetLastFrame();
		bShapeUpdate = true;

		int nmat = m_pMeshObject->NumMaterials();
		for (int imat=0; imat<nmat; imat++) {
			RAS_MeshMaterial *mmat = m_pMeshObject->GetMeshMaterial(imat);
			RAS_MeshSlot **slot = mmat->m_slots[(void*)m_gameobj];
			if (!slot || !*slot)
				continue;
			(*slot)->m_pDerivedMesh = m_dm;
		}
	}
	return bShapeUpdate;
}

static void particle_system_minmax(Scene *scene,
                                   Object *object,
                                   ParticleSystem *psys,
                                   float radius,
                                   float min[3], float max[3])
{
	const float size[3] = {radius, radius, radius};
	const float cfra = BKE_scene_frame_get(scene);
	ParticleSettings *part = psys->part;
	ParticleSimulationData sim = {NULL};
	ParticleData *pa = NULL;
	int i;
	int total_particles;
	float mat[4][4], imat[4][4];

	INIT_MINMAX(min, max);
	if (part->type == PART_HAIR) {
		/* TOOD(sergey): Not supported currently. */
		return;
	}

	unit_m4(mat);
	psys_render_set(object, psys, mat, mat, 1, 1, 0);

	sim.scene = scene;
	sim.ob = object;
	sim.psys = psys;
	sim.psmd = psys_get_modifier(object, psys);

	invert_m4_m4(imat, object->obmat);
	total_particles = psys->totpart + psys->totchild;
	psys->lattice_deform_data = psys_create_lattice_deform_data(&sim);

	for (i = 0, pa = psys->particles; i < total_particles; i++, pa++) {
		float co_object[3], co_min[3], co_max[3];
		ParticleKey state;
		state.time = cfra;
		if (!psys_get_particle_state(&sim, i, &state, 0)) {
			continue;
		}
		mul_v3_m4v3(co_object, imat, state.co);
		sub_v3_v3v3(co_min, co_object, size);
		add_v3_v3v3(co_max, co_object, size);
		minmax_v3v3_v3(min, max, co_min);
		minmax_v3v3_v3(min, max, co_max);
	}

	if (psys->lattice_deform_data) {
		end_latt_deform(psys->lattice_deform_data);
		psys->lattice_deform_data = NULL;
	}

	psys_render_restore(object, psys);
}

/* basic vertex data functions */
bool BKE_mball_minmax(MetaBall *mb, float min[3], float max[3])
{
    MetaElem *ml;

    INIT_MINMAX(min, max);

    for (ml = mb->elems.first; ml; ml = ml->next) {
        minmax_v3v3_v3(min, max, &ml->x);
    }

    return (BLI_listbase_is_empty(&mb->elems) == false);
}

/**
 * Recursively builds a BVH, dividing elements along the middle of the longest axis of allbox.
 */
static void build_bvh_spatial(
        PROCESS *process, MetaballBVHNode *node,
        unsigned int start, unsigned int end, const Box *allbox)
{
	unsigned int part, j, s;
	float dim[3], div;

	/* Maximum bvh queue size is number of nodes which are made, equals calls to this function. */
	process->bvh_queue_size++;

	dim[0] = allbox->max[0] - allbox->min[0];
	dim[1] = allbox->max[1] - allbox->min[1];
	dim[2] = allbox->max[2] - allbox->min[2];

	s = 0;
	if (dim[1] > dim[0] && dim[1] > dim[2]) s = 1;
	else if (dim[2] > dim[1] && dim[2] > dim[0]) s = 2;

	div = allbox->min[s] + (dim[s] / 2.0f);

	part = partition_mainb(process->mainb, start, end, s, div);

	make_box_from_metaelem(&node->bb[0], process->mainb[start]);
	node->child[0] = NULL;

	if (part > start + 1) {
		for (j = start; j < part; j++) {
			make_box_union(process->mainb[j]->bb, &node->bb[0], &node->bb[0]);
		}

		node->child[0] = BLI_memarena_alloc(process->pgn_elements, sizeof(MetaballBVHNode));
		build_bvh_spatial(process, node->child[0], start, part, &node->bb[0]);
	}

	node->child[1] = NULL;
	if (part < end) {
		make_box_from_metaelem(&node->bb[1], process->mainb[part]);

		if (part < end - 1) {
			for (j = part; j < end; j++) {
				make_box_union(process->mainb[j]->bb, &node->bb[1], &node->bb[1]);
			}

			node->child[1] = BLI_memarena_alloc(process->pgn_elements, sizeof(MetaballBVHNode));
			build_bvh_spatial(process, node->child[1], part, end, &node->bb[1]);
		}
	}
	else {
		INIT_MINMAX(node->bb[1].min, node->bb[1].max);
	}
}

static void bundle_midpoint(Scene *scene, Object *ob, float vec[3])
{
	MovieClip *clip = BKE_object_movieclip_get(scene, ob, false);
	MovieTracking *tracking;
	MovieTrackingObject *object;
	bool ok = false;
	float min[3], max[3], mat[4][4], pos[3], cammat[4][4];

	if (!clip)
		return;

	tracking = &clip->tracking;

	copy_m4_m4(cammat, ob->obmat);

	BKE_tracking_get_camera_object_matrix(scene, ob, mat);

	INIT_MINMAX(min, max);

	for (object = tracking->objects.first; object; object = object->next) {
		ListBase *tracksbase = BKE_tracking_object_get_tracks(tracking, object);
		MovieTrackingTrack *track = tracksbase->first;
		float obmat[4][4];

		if (object->flag & TRACKING_OBJECT_CAMERA) {
			copy_m4_m4(obmat, mat);
		}
		else {
			float imat[4][4];

			BKE_tracking_camera_get_reconstructed_interpolate(tracking, object, scene->r.cfra, imat);
			invert_m4(imat);

			mul_m4_m4m4(obmat, cammat, imat);
		}

		while (track) {
			if ((track->flag & TRACK_HAS_BUNDLE) && TRACK_SELECTED(track)) {
				ok = 1;
				mul_v3_m4v3(pos, obmat, track->bundle_pos);
				minmax_v3v3_v3(min, max, pos);
			}

			track = track->next;
		}
	}

	if (ok) {
		mid_v3_v3v3(vec, min, max);
	}
}

static void hair_get_boundbox(ClothModifierData *clmd, float gmin[3], float gmax[3])
{
	Cloth *cloth = clmd->clothObject;
	Implicit_Data *data = cloth->implicit;
	unsigned int mvert_num = cloth->mvert_num;
	int i;
	
	INIT_MINMAX(gmin, gmax);
	for (i = 0; i < mvert_num; i++) {
		float x[3];
		BPH_mass_spring_get_motion_state(data, i, x, NULL);
		DO_MINMAX(x, gmin, gmax);
	}
}

static void init_dualcon_mesh(DualConInput *mesh, DerivedMesh *dm)
{
	memset(mesh, 0, sizeof(DualConInput));

	mesh->co = (void *)dm->getVertArray(dm);
	mesh->co_stride = sizeof(MVert);
	mesh->totco = dm->getNumVerts(dm);

	mesh->faces = (void *)dm->getTessFaceArray(dm);
	mesh->face_stride = sizeof(MFace);
	mesh->totface = dm->getNumTessFaces(dm);

	INIT_MINMAX(mesh->min, mesh->max);
	dm->getMinMax(dm, mesh->min, mesh->max);
}

static void rtbuild_init(RTBuilder *b)
{
	b->split_axis = -1;
	b->primitives.begin   = NULL;
	b->primitives.end     = NULL;
	b->primitives.maxsize = 0;
	
	for (int i = 0; i < RTBUILD_MAX_CHILDS; i++)
		b->child_offset[i] = 0;

	for (int i = 0; i < 3; i++)
		b->sorted_begin[i] = b->sorted_end[i] = NULL;
		
	INIT_MINMAX(b->bb, b->bb + 3);
}

static void boundbox_lattice(Object *ob)
{
	BoundBox *bb;
	Lattice *lt;
	float min[3], max[3];

	if (ob->bb == NULL)
		ob->bb = MEM_mallocN(sizeof(BoundBox), "Lattice boundbox");

	bb = ob->bb;
	lt = ob->data;

	INIT_MINMAX(min, max);
	BKE_lattice_minmax_dl(ob, lt, min, max);
	BKE_boundbox_init_from_minmax(bb, min, max);
}

static void RE_rayobject_instance_bb(RayObject *o, float *min, float *max)
{
    //TODO:
    // *better bb.. calculated without rotations of bb
    // *maybe cache that better-fitted-BB at the InstanceRayObject
    InstanceRayObject *obj = (InstanceRayObject *)o;

    float m[3], M[3], t[3];
    int i, j;
    INIT_MINMAX(m, M);
    RE_rayobject_merge_bb(obj->target, m, M);

    //There must be a faster way than rotating all the 8 vertexs of the BB
    for (i = 0; i < 8; i++) {
        for (j = 0; j < 3; j++) t[j] = (i & (1 << j)) ? M[j] : m[j];
        mul_m4_v3(obj->target2global, t);
        DO_MINMAX(t, min, max);
    }
}

static void init_dualcon_mesh(DualConInput *input, Mesh *mesh)
{
  memset(input, 0, sizeof(DualConInput));

  input->co = (void *)mesh->mvert;
  input->co_stride = sizeof(MVert);
  input->totco = mesh->totvert;

  input->mloop = (void *)mesh->mloop;
  input->loop_stride = sizeof(MLoop);

  BKE_mesh_runtime_looptri_ensure(mesh);
  input->looptri = (void *)mesh->runtime.looptris.array;
  input->tri_stride = sizeof(MLoopTri);
  input->tottri = mesh->runtime.looptris.len;

  INIT_MINMAX(input->min, input->max);
  BKE_mesh_minmax(mesh, input->min, input->max);
}

static int occ_find_bbox_axis(OcclusionTree *tree, int begin, int end, float *min, float *max)
{
	float len, maxlen= -1.0f;
	int a, axis = 0;

	INIT_MINMAX(min, max);

	for(a=begin; a<end; a++)
		DO_MINMAX(tree->co[a], min, max)

	for(a=0; a<3; a++) {
		len= max[a] - min[a];

		if(len > maxlen) {
			maxlen= len;
			axis= a;
		}
	}

	return axis;
}