bool *BKE_objdef_validmap_get(Object *ob, const int defbase_tot)
{
	bDeformGroup *dg;
	ModifierData *md;
	bool *vgroup_validmap;
	GHash *gh;
	int i, step1 = 1;
	//int defbase_tot = BLI_countlist(&ob->defbase);

	if (ob->defbase.first == NULL) {
		return NULL;
	}

	gh = BLI_ghash_str_new("BKE_objdef_validmap_get gh");

	/* add all names to a hash table */
	for (dg = ob->defbase.first; dg; dg = dg->next) {
		BLI_ghash_insert(gh, dg->name, NULL);
	}

	BLI_assert(BLI_ghash_size(gh) == defbase_tot);

	/* now loop through the armature modifiers and identify deform bones */
	for (md = ob->modifiers.first; md; md = !md->next && step1 ? (step1 = 0), modifiers_getVirtualModifierList(ob) : md->next) {
		if (!(md->mode & (eModifierMode_Realtime | eModifierMode_Virtual)))
			continue;

		if (md->type == eModifierType_Armature) {
			ArmatureModifierData *amd = (ArmatureModifierData *) md;

			if (amd->object && amd->object->pose) {
				bPose *pose = amd->object->pose;
				bPoseChannel *chan;

				for (chan = pose->chanbase.first; chan; chan = chan->next) {
					if (chan->bone->flag & BONE_NO_DEFORM)
						continue;

					if (BLI_ghash_remove(gh, chan->name, NULL, NULL)) {
						BLI_ghash_insert(gh, chan->name, SET_INT_IN_POINTER(1));
					}
				}
			}
		}
	}

	vgroup_validmap = MEM_mallocN(sizeof(*vgroup_validmap) * defbase_tot, "wpaint valid map");

	/* add all names to a hash table */
	for (dg = ob->defbase.first, i = 0; dg; dg = dg->next, i++) {
		vgroup_validmap[i] = (BLI_ghash_lookup(gh, dg->name) != NULL);
	}

	BLI_assert(i == BLI_ghash_size(gh));

	BLI_ghash_free(gh, NULL, NULL);

	return vgroup_validmap;
}

void BKE_sim_debug_data_free(void)
{
	if (_sim_debug_data) {
		if (_sim_debug_data->gh)
			BLI_ghash_free(_sim_debug_data->gh, NULL, debug_element_free);
		MEM_freeN(_sim_debug_data);
	}
}

DerivedMesh *NewBooleanDerivedMesh(DerivedMesh *dm, struct Object *ob,
                                   DerivedMesh *dm_select, struct Object *ob_select,
                                   int int_op_type)
{

	struct CarveMeshDescr *left, *right, *output = NULL;
	DerivedMesh *output_dm = NULL;
	int operation;
	bool result;
	DMArrays dm_left_arrays, dm_right_arrays;

	if (dm == NULL || dm_select == NULL) {
		return NULL;
	}

	operation = operation_from_optype(int_op_type);
	if (operation == -1) {
		return NULL;
	}

	dm_arrays_get(dm_select, &dm_left_arrays);
	dm_arrays_get(dm, &dm_right_arrays);

	left = carve_mesh_from_dm(ob_select, dm_select, &dm_left_arrays);
	right = carve_mesh_from_dm(ob, dm, &dm_right_arrays);

	result = carve_performBooleanOperation(left, right, operation, &output);

	carve_deleteMesh(left);
	carve_deleteMesh(right);

	if (result) {
		ExportMeshData export_data;

		prepare_export_data(ob_select, dm_select, &dm_left_arrays,
		                    ob, dm, &dm_right_arrays,
		                    &export_data);

		carve_exportMesh(output, &MeshExporter, &export_data);
		output_dm = export_data.dm;

		/* Free memory used by export mesh. */
		BLI_ghash_free(export_data.material_hash, NULL, NULL);

		output_dm->cd_flag |= dm->cd_flag | dm_select->cd_flag;
		output_dm->dirty |= DM_DIRTY_NORMALS;
		carve_deleteMesh(output);
	}

	dm_arrays_free(&dm_left_arrays);
	dm_arrays_free(&dm_right_arrays);

	return output_dm;
}

void WM_uilisttype_free(void)
{
	GHashIterator *iter = BLI_ghashIterator_new(uilisttypes_hash);

	for (; !BLI_ghashIterator_done(iter); BLI_ghashIterator_step(iter)) {
		uiListType *ult = BLI_ghashIterator_getValue(iter);
		if (ult->ext.free) {
			ult->ext.free(ult->ext.data);
		}
	}
	BLI_ghashIterator_free(iter);

	BLI_ghash_free(uilisttypes_hash, NULL, MEM_freeN);
	uilisttypes_hash = NULL;
}

static void text_autocomplete_free(bContext *C, wmOperator *op)
{
	GHash *gh = op->customdata;
	if (gh) {
		BLI_ghash_free(gh, NULL, MEM_freeN);
		op->customdata = NULL;
	}

	/* other stuff */
	{
		SpaceText *st = CTX_wm_space_text(C);
		st->doplugins = false;
		texttool_text_clear();
	}
}

void WM_menutype_free(void)
{
	GHashIterator *iter= BLI_ghashIterator_new(menutypes_hash);

	for( ; !BLI_ghashIterator_isDone(iter); BLI_ghashIterator_step(iter)) {
		MenuType *mt= BLI_ghashIterator_getValue(iter);
		if(mt->ext.free) {
			mt->ext.free(mt->ext.data);
		}
	}
	BLI_ghashIterator_free(iter);

	BLI_ghash_free(menutypes_hash, NULL, (GHashValFreeFP)MEM_freeN);
	menutypes_hash= NULL;
}

void DNA_sdna_free(SDNA *sdna)
{
	if (sdna->data_alloc) {
		MEM_freeN((void *)sdna->data);
	}

	MEM_freeN((void *)sdna->names);
	MEM_freeN(sdna->types);
	MEM_freeN(sdna->structs);

#ifdef WITH_DNA_GHASH
	BLI_ghash_free(sdna->structs_map, NULL, NULL);
#endif

	MEM_freeN(sdna);
}

void postEditBoneDuplicate(struct ListBase *editbones, Object *ob)
{
	if (ob->pose == NULL) {
		return;
	}

	BKE_pose_channels_hash_free(ob->pose);
	BKE_pose_channels_hash_make(ob->pose);

	GHash *name_map = BLI_ghash_str_new(__func__);

	for (EditBone *ebone_src = editbones->first; ebone_src; ebone_src = ebone_src->next) {
		EditBone *ebone_dst = ebone_src->temp.ebone;
		if (!ebone_dst) {
			ebone_dst = ED_armature_bone_get_mirrored(editbones, ebone_src);
		}
		if (ebone_dst) {
			BLI_ghash_insert(name_map, ebone_src->name, ebone_dst->name);
		}
	}

	for (EditBone *ebone_src = editbones->first; ebone_src; ebone_src = ebone_src->next) {
		EditBone *ebone_dst = ebone_src->temp.ebone;
		if (ebone_dst) {
			bPoseChannel *pchan_src = BKE_pose_channel_find_name(ob->pose, ebone_src->name);
			if (pchan_src) {
				bPoseChannel *pchan_dst = BKE_pose_channel_find_name(ob->pose, ebone_dst->name);
				if (pchan_dst) {
					if (pchan_src->custom_tx) {
						pchan_dst->custom_tx = pchan_duplicate_map(ob->pose, name_map, pchan_src->custom_tx);
					}
					if (pchan_src->bbone_prev) {
						pchan_dst->bbone_prev = pchan_duplicate_map(ob->pose, name_map, pchan_src->bbone_prev);
					}
					if (pchan_src->bbone_next) {
						pchan_dst->bbone_next = pchan_duplicate_map(ob->pose, name_map, pchan_src->bbone_next);
					}
				}
			}
		}
	}

	BLI_ghash_free(name_map, NULL, NULL);
}

void GPU_extensions_exit(void)
{
	extern Material defmaterial;    // render module abuse...

	if(defmaterial.gpumaterial.first)
		GPU_material_free(&defmaterial);

	if(FUNCTION_HASH) {
		BLI_ghash_free(FUNCTION_HASH, NULL, (GHashValFreeFP)MEM_freeN);
		FUNCTION_HASH = NULL;
	}
	/*if(FUNCTION_PROTOTYPES) {
		MEM_freeN(FUNCTION_PROTOTYPES);
		FUNCTION_PROTOTYPES = NULL;
	}*/
	/*if(FUNCTION_LIB) {
		GPU_shader_free(FUNCTION_LIB);
		FUNCTION_LIB = NULL;
	}*/
}

void tracks_map_free(TracksMap *map, void (*customdata_free)(void *customdata))
{
	int i = 0;

	BLI_ghash_free(map->hash, NULL, NULL);

	for (i = 0; i < map->num_tracks; i++) {
		if (map->customdata && customdata_free)
			customdata_free(&map->customdata[i * map->customdata_size]);

		BKE_tracking_track_free(&map->tracks[i]);
	}

	if (map->customdata)
		MEM_freeN(map->customdata);

	MEM_freeN(map->tracks);

	BLI_spin_end(&map->spin_lock);

	MEM_freeN(map);
}

void imb_tile_cache_exit(void)
{
	ImGlobalTile *gtile;
	int a;

	if(GLOBAL_CACHE.initialized) {
		for(gtile=GLOBAL_CACHE.tiles.first; gtile; gtile=gtile->next)
			imb_global_cache_tile_unload(gtile);

		for(a=0; a<GLOBAL_CACHE.totthread; a++)
			imb_thread_cache_exit(&GLOBAL_CACHE.thread_cache[a]);

		if(GLOBAL_CACHE.memarena)
			BLI_memarena_free(GLOBAL_CACHE.memarena);

		if(GLOBAL_CACHE.tilehash)
			BLI_ghash_free(GLOBAL_CACHE.tilehash, NULL, NULL);

		BLI_mutex_end(&GLOBAL_CACHE.mutex);

		memset(&GLOBAL_CACHE, 0, sizeof(ImGlobalTileCache));
	}
}

/**
 * Free (or release) any data used by this ViewLayer.
 */
void BKE_view_layer_free_ex(ViewLayer *view_layer, const bool do_id_user)
{
  view_layer->basact = NULL;

  BLI_freelistN(&view_layer->object_bases);

  if (view_layer->object_bases_hash) {
    BLI_ghash_free(view_layer->object_bases_hash, NULL, NULL);
  }

  for (LayerCollection *lc = view_layer->layer_collections.first; lc; lc = lc->next) {
    layer_collection_free(view_layer, lc);
  }
  BLI_freelistN(&view_layer->layer_collections);

  for (ViewLayerEngineData *sled = view_layer->drawdata.first; sled; sled = sled->next) {
    if (sled->storage) {
      if (sled->free) {
        sled->free(sled->storage);
      }
      MEM_freeN(sled->storage);
    }
  }
  BLI_freelistN(&view_layer->drawdata);

  MEM_SAFE_FREE(view_layer->stats);

  BKE_freestyle_config_free(&view_layer->freestyle_config, do_id_user);

  if (view_layer->id_properties) {
    IDP_FreeProperty(view_layer->id_properties);
  }

  MEM_SAFE_FREE(view_layer->object_bases_array);

  MEM_freeN(view_layer);
}

/** 
 * Move here pose function for game engine so that we can mix with GE objects
 * Principle is as follow:
 * Use Blender structures so that BKE_pose_where_is can be used unchanged
 * Copy the constraint so that they can be enabled/disabled/added/removed at runtime
 * Don't copy the constraints for the pose used by the Action actuator, it does not need them.
 * Scan the constraint structures so that the KX equivalent of target objects are identified and 
 * stored in separate list.
 * When it is about to evaluate the pose, set the KX object position in the obmat of the corresponding
 * Blender objects and restore after the evaluation.
 */
static void game_copy_pose(bPose **dst, bPose *src, int copy_constraint)
{
	bPose *out;
	bPoseChannel *pchan, *outpchan;
	GHash *ghash;
	
	/* the game engine copies the current armature pose and then swaps
	 * the object pose pointer. this makes it possible to change poses
	 * without affecting the original blender data. */

	if (!src) {
		*dst=NULL;
		return;
	}
	else if (*dst==src) {
		printf("game_copy_pose source and target are the same\n");
		*dst=NULL;
		return;
	}
	
	out= (bPose*)MEM_dupallocN(src);
	out->chanhash = NULL;
	out->agroups.first= out->agroups.last= NULL;
	out->ikdata = NULL;
	out->ikparam = MEM_dupallocN(src->ikparam);
	out->flag |= POSE_GAME_ENGINE;
	BLI_duplicatelist(&out->chanbase, &src->chanbase);

	/* remap pointers */
	ghash= BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "game_copy_pose gh");

	pchan= (bPoseChannel *)src->chanbase.first;
	outpchan= (bPoseChannel *)out->chanbase.first;
	for (; pchan; pchan=pchan->next, outpchan=outpchan->next)
		BLI_ghash_insert(ghash, pchan, outpchan);

	for (pchan = (bPoseChannel *)out->chanbase.first; pchan; pchan = pchan->next) {
		pchan->parent= (bPoseChannel *)BLI_ghash_lookup(ghash, pchan->parent);
		pchan->child= (bPoseChannel *)BLI_ghash_lookup(ghash, pchan->child);

		if (copy_constraint) {
			ListBase listb;
			// copy all constraint for backward compatibility
			// BKE_constraints_copy NULLs listb, no need to make extern for this operation.
			BKE_constraints_copy(&listb, &pchan->constraints, false);
			pchan->constraints= listb;
		}
		else {
			BLI_listbase_clear(&pchan->constraints);
		}

		if (pchan->custom) {
			id_us_plus(&pchan->custom->id);
		}

		// fails to link, props are not used in the BGE yet.
#if 0
		if (pchan->prop)
			pchan->prop= IDP_CopyProperty(pchan->prop);
#endif
		pchan->prop= NULL;
	}

	BLI_ghash_free(ghash, NULL, NULL);
	// set acceleration structure for channel lookup
	BKE_pose_channels_hash_make(out);
	*dst=out;
}

//.........这里部分代码省略.........
		if (ok) {
			BLI_ghash_insert(polyHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numPolys));
			loop_mapping[numPolys] = numLoops;
			numPolys++;
			numLoops += mp->totloop;
		}
	}
	
	
	/* now we know the number of verts, edges and faces, 
	 * we can create the new (reduced) mesh
	 */
	result = CDDM_from_template(dm, numVerts, numEdges, 0, numLoops, numPolys);
	
	mpoly_new = CDDM_get_polys(result);
	mloop_new = CDDM_get_loops(result);
	medge_new = CDDM_get_edges(result);
	mvert_new = CDDM_get_verts(result);
	
	/* using ghash-iterators, map data into new mesh */
	/* vertices */
	for (hashIter = BLI_ghashIterator_new(vertHash);
	     !BLI_ghashIterator_isDone(hashIter);
	     BLI_ghashIterator_step(hashIter) )
	{
		MVert source;
		MVert *dest;
		int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
		int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
		
		dm->getVert(dm, oldIndex, &source);
		dest = &mvert_new[newIndex];
		
		DM_copy_vert_data(dm, result, oldIndex, newIndex, 1);
		*dest = source;
	}
	BLI_ghashIterator_free(hashIter);
		
	/* edges */
	for (hashIter = BLI_ghashIterator_new(edgeHash);
	     !BLI_ghashIterator_isDone(hashIter);
	     BLI_ghashIterator_step(hashIter))
	{
		MEdge source;
		MEdge *dest;
		int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
		int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
		
		dm->getEdge(dm, oldIndex, &source);
		dest = &medge_new[newIndex];
		
		source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
		source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
		
		DM_copy_edge_data(dm, result, oldIndex, newIndex, 1);
		*dest = source;
	}
	BLI_ghashIterator_free(hashIter);
	
	/* faces */
	for (hashIter = BLI_ghashIterator_new(polyHash);
	     !BLI_ghashIterator_isDone(hashIter);
	     BLI_ghashIterator_step(hashIter) )
	{
		int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
		int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
		MPoly *source = &mpoly[oldIndex];
		MPoly *dest = &mpoly_new[newIndex];
		int oldLoopIndex = source->loopstart;
		int newLoopIndex = loop_mapping[newIndex];
		MLoop *source_loop = &mloop[oldLoopIndex];
		MLoop *dest_loop = &mloop_new[newLoopIndex];
		
		DM_copy_poly_data(dm, result, oldIndex, newIndex, 1);
		DM_copy_loop_data(dm, result, oldLoopIndex, newLoopIndex, source->totloop);

		*dest = *source;
		dest->loopstart = newLoopIndex;
		for (i = 0; i < source->totloop; i++) {
			dest_loop[i].v = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source_loop[i].v)));
			dest_loop[i].e = GET_INT_FROM_POINTER(BLI_ghash_lookup(edgeHash, SET_INT_IN_POINTER(source_loop[i].e)));
		}
	}

	BLI_ghashIterator_free(hashIter);

	MEM_freeN(loop_mapping);

	/* why is this needed? - campbell */
	/* recalculate normals */
	CDDM_calc_normals(result);
	
	/* free hashes */
	BLI_ghash_free(vertHash, NULL, NULL);
	BLI_ghash_free(edgeHash, NULL, NULL);
	BLI_ghash_free(polyHash, NULL, NULL);

	/* return the new mesh */
	return result;
}

static void make_duplis_font(const DupliContext *ctx)
{
	Object *par = ctx->object;
	GHash *family_gh;
	Object *ob;
	Curve *cu;
	struct CharTrans *ct, *chartransdata = NULL;
	float vec[3], obmat[4][4], pmat[4][4], fsize, xof, yof;
	int text_len, a;
	size_t family_len;
	const wchar_t *text = NULL;
	bool text_free = false;

	/* font dupliverts not supported inside groups */
	if (ctx->group)
		return;

	copy_m4_m4(pmat, par->obmat);

	/* in par the family name is stored, use this to find the other objects */

	BKE_vfont_to_curve_ex(G.main, par, FO_DUPLI, NULL,
	                      &text, &text_len, &text_free, &chartransdata);

	if (text == NULL || chartransdata == NULL) {
		return;
	}

	cu = par->data;
	fsize = cu->fsize;
	xof = cu->xof;
	yof = cu->yof;

	ct = chartransdata;

	/* cache result */
	family_len = strlen(cu->family);
	family_gh = BLI_ghash_int_new_ex(__func__, 256);

	/* advance matching BLI_strncpy_wchar_from_utf8 */
	for (a = 0; a < text_len; a++, ct++) {

		ob = find_family_object(cu->family, family_len, (unsigned int)text[a], family_gh);
		if (ob) {
			vec[0] = fsize * (ct->xof - xof);
			vec[1] = fsize * (ct->yof - yof);
			vec[2] = 0.0;

			mul_m4_v3(pmat, vec);

			copy_m4_m4(obmat, par->obmat);

			if (UNLIKELY(ct->rot != 0.0f)) {
				float rmat[4][4];

				zero_v3(obmat[3]);
				unit_m4(rmat);
				rotate_m4(rmat, 'Z', -ct->rot);
				mul_m4_m4m4(obmat, obmat, rmat);
			}

			copy_v3_v3(obmat[3], vec);

			make_dupli(ctx, ob, obmat, a, false, false);
		}
	}

	if (text_free) {
		MEM_freeN((void *)text);
	}

	BLI_ghash_free(family_gh, NULL, NULL);

	MEM_freeN(chartransdata);
}

//.........这里部分代码省略.........
	     cont_old;
	     cont_old = cont_old->next)
	{
		bController *cont_new2 = cont_new;

		if (cont_old->mynew != NULL) {
			cont_new2 = cont_old->mynew;
			if (!(cont_new2 == cont_new || BLI_findindex(&ob_new->controllers, cont_new2) >= 0)) {
				cont_new2 = NULL;
			}
		}
		else if (cont_new && cont_old->type != cont_new->type) {
			cont_new2 = NULL;
		}

		BLI_ghash_insert(controllers_map, cont_old, cont_new2);

		if (cont_new) {
			cont_new = cont_new->next;
		}
	}

	for (bActuator *act_old = ob_old->actuators.first, *act_new = ob_new->actuators.first;
	     act_old;
	     act_old = act_old->next)
	{
		bActuator *act_new2 = act_new;

		if (act_old->mynew != NULL) {
			act_new2 = act_old->mynew;
			if (!(act_new2 == act_new || BLI_findindex(&ob_new->actuators, act_new2) >= 0)) {
				act_new2 = NULL;
			}
		}
		else if (act_new && act_old->type != act_new->type) {
			act_new2 = NULL;
		}

		BLI_ghash_insert(actuators_map, act_old, act_new2);

		if (act_new) {
			act_new = act_new->next;
		}
	}

	for (Object *ob = bmain->object.first; ob; ob = ob->id.next) {
		if (controllers_map != NULL) {
			for (bSensor *sens = ob->sensors.first; sens; sens = sens->next) {
				for (int a = 0; a < sens->totlinks; a++) {
					if (sens->links[a]) {
						bController *old_link = sens->links[a];
						bController **new_link_p = (bController **)BLI_ghash_lookup_p(controllers_map, old_link);

						if (new_link_p == NULL) {
							/* old_link is *not* in map's keys (i.e. not to any ob_old->controllers),
							 * which means we ignore it totally here. */
						}
						else if (*new_link_p == NULL) {
							unlink_logicbricks((void **)&old_link, (void ***)&(sens->links), &sens->totlinks);
							a--;
						}
						else {
							sens->links[a] = *new_link_p;
						}
					}
				}
			}
		}

		if (actuators_map != NULL) {
			for (bController *cont = ob->controllers.first; cont; cont = cont->next) {
				for (int a = 0; a < cont->totlinks; a++) {
					if (cont->links[a]) {
						bActuator *old_link = cont->links[a];
						bActuator **new_link_p = (bActuator **)BLI_ghash_lookup_p(actuators_map, old_link);

						if (new_link_p == NULL) {
							/* old_link is *not* in map's keys (i.e. not to any ob_old->actuators),
							 * which means we ignore it totally here. */
						}
						else if (*new_link_p == NULL) {
							unlink_logicbricks((void **)&old_link, (void ***)&(cont->links), &cont->totlinks);
							a--;
						}
						else {
							cont->links[a] = *new_link_p;
						}
					}
				}
			}
		}
	}

	if (controllers_map) {
		BLI_ghash_free(controllers_map, NULL, NULL);
	}
	if (actuators_map) {
		BLI_ghash_free(actuators_map, NULL, NULL);
	}
}

//.........这里部分代码省略.........
			BLI_ghash_insert(edgeHash2,  SET_INT_IN_POINTER(edgeMap[i]),
			                 SET_INT_IN_POINTER(j));
		}
	}
	else {
		int numVerts = numVert_src * frac;

		if (bmd->randomize) {
			BLI_array_randomize(vertMap, sizeof(*vertMap),
			                    numVert_src, bmd->seed);
		}

		/* get the set of all vert indices that will be in the final mesh,
		 * mapped to the new indices
		 */
		for (i = 0; i < numVerts; i++) {
			BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(vertMap[i]), SET_INT_IN_POINTER(i));
		}
	}

	/* now we know the number of verts, edges and faces, we can create
	 * the mesh
	 */
	result = CDDM_from_template(dm, BLI_ghash_size(vertHash),
	                            BLI_ghash_size(edgeHash), 0, numLoops_dst, numFaces_dst);

	/* copy the vertices across */
	for (hashIter = BLI_ghashIterator_new(vertHash);
	     BLI_ghashIterator_done(hashIter) == false;
	     BLI_ghashIterator_step(hashIter)
	     )
	{
		MVert source;
		MVert *dest;
		int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
		int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));

		source = mvert_src[oldIndex];
		dest = CDDM_get_vert(result, newIndex);

		DM_copy_vert_data(dm, result, oldIndex, newIndex, 1);
		*dest = source;
	}
	BLI_ghashIterator_free(hashIter);
	
	/* copy the edges across, remapping indices */
	for (i = 0; i < BLI_ghash_size(edgeHash); i++) {
		MEdge source;
		MEdge *dest;
		int oldIndex = GET_INT_FROM_POINTER(BLI_ghash_lookup(edgeHash, SET_INT_IN_POINTER(i)));
		
		source = medge_src[oldIndex];
		dest = CDDM_get_edge(result, i);
		
		source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
		source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
		
		DM_copy_edge_data(dm, result, oldIndex, i, 1);
		*dest = source;
	}

	mpoly_dst = CDDM_get_polys(result);
	/* mloop_dst = */ ml_dst = CDDM_get_loops(result);
	
	/* copy the faces across, remapping indices */
	k = 0;
	for (i = 0; i < numFaces_dst; i++) {
		MPoly *source;
		MPoly *dest;
		
		source = mpoly_src + faceMap[i];
		dest = mpoly_dst + i;
		DM_copy_poly_data(dm, result, faceMap[i], i, 1);
		
		*dest = *source;
		dest->loopstart = k;
		
		DM_copy_loop_data(dm, result, source->loopstart, dest->loopstart, dest->totloop);

		ml_src = mloop_src + source->loopstart;
		for (j = 0; j < source->totloop; j++, k++, ml_src++, ml_dst++) {
			ml_dst->v = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(ml_src->v)));
			ml_dst->e = GET_INT_FROM_POINTER(BLI_ghash_lookup(edgeHash2, SET_INT_IN_POINTER(ml_src->e)));
		}
	}

	BLI_ghash_free(vertHash, NULL, NULL);
	BLI_ghash_free(edgeHash, NULL, NULL);
	BLI_ghash_free(edgeHash2, NULL, NULL);
	
	MEM_freeN(vertMap);
	MEM_freeN(edgeMap);
	MEM_freeN(faceMap);

	if (dm->dirty & DM_DIRTY_NORMALS) {
		result->dirty |= DM_DIRTY_NORMALS;
	}

	return result;
}

//.........这里部分代码省略.........
					SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
		}

		/* get the set of edges that will be in the new mesh
		*/
		for(i = 0; i < numEdges; ++i) {
			MEdge me;
			dm->getEdge(dm, edgeMap[i], &me);

			BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(BLI_ghash_size(edgeHash)),
					 SET_INT_IN_POINTER(edgeMap[i]));
		}
	} else {
		int numVerts = dm->getNumVerts(dm) * frac;

		if(bmd->randomize)
			BLI_array_randomize(vertMap, sizeof(*vertMap),
						maxVerts, bmd->seed);

		/* get the set of all vert indices that will be in the final mesh,
		* mapped to the new indices
		*/
		for(i = 0; i < numVerts; ++i)
			BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(vertMap[i]), SET_INT_IN_POINTER(i));
	}

	/* now we know the number of verts, edges and faces, we can create
	* the mesh
	*/
	result = CDDM_from_template(dm, BLI_ghash_size(vertHash),
					BLI_ghash_size(edgeHash), numFaces);

	/* copy the vertices across */
	for(	hashIter = BLI_ghashIterator_new(vertHash);
			!BLI_ghashIterator_isDone(hashIter);
			BLI_ghashIterator_step(hashIter)
	) {
		MVert source;
		MVert *dest;
		int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
		int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));

		dm->getVert(dm, oldIndex, &source);
		dest = CDDM_get_vert(result, newIndex);

		DM_copy_vert_data(dm, result, oldIndex, newIndex, 1);
		*dest = source;
	}
	BLI_ghashIterator_free(hashIter);
	
	/* copy the edges across, remapping indices */
	for(i = 0; i < BLI_ghash_size(edgeHash); ++i) {
		MEdge source;
		MEdge *dest;
		int oldIndex = GET_INT_FROM_POINTER(BLI_ghash_lookup(edgeHash, SET_INT_IN_POINTER(i)));
		
		dm->getEdge(dm, oldIndex, &source);
		dest = CDDM_get_edge(result, i);
		
		source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
		source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
		
		DM_copy_edge_data(dm, result, oldIndex, i, 1);
		*dest = source;
	}

	/* copy the faces across, remapping indices */
	for(i = 0; i < numFaces; ++i) {
		MFace source;
		MFace *dest;
		int orig_v4;
		
		dm->getFace(dm, faceMap[i], &source);
		dest = CDDM_get_face(result, i);
		
		orig_v4 = source.v4;
		
		source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
		source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
		source.v3 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v3)));
		if(source.v4)
			source.v4 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v4)));
		
		DM_copy_face_data(dm, result, faceMap[i], i, 1);
		*dest = source;
		
		test_index_face(dest, &result->faceData, i, (orig_v4 ? 4 : 3));
	}

	CDDM_calc_normals(result);
	
	BLI_ghash_free(vertHash, NULL, NULL);
	BLI_ghash_free(edgeHash, NULL, NULL);
	
	MEM_freeN(vertMap);
	MEM_freeN(edgeMap);
	MEM_freeN(faceMap);
	
	return result;
}

void BKE_outliner_treehash_free(void *treehash)
{
	BLI_assert(treehash);

	BLI_ghash_free(treehash, NULL, free_treehash_group);
}

/* Iterate over the CSG Output Descriptors and create a new DerivedMesh
   from them */
static DerivedMesh *ConvertCSGDescriptorsToDerivedMesh(
	CSG_FaceIteratorDescriptor *face_it,
	CSG_VertexIteratorDescriptor *vertex_it,
	float parinv[][4],
	float mapmat[][4],
	Material **mat,
	int *totmat,
	DerivedMesh *dm1,
	Object *ob1,
	DerivedMesh *dm2,
	Object *ob2)
{
	DerivedMesh *result, *orig_dm;
	GHash *material_hash = NULL;
	Mesh *me1= (Mesh*)ob1->data;
	Mesh *me2= (Mesh*)ob2->data;
	int i;

	// create a new DerivedMesh
	result = CDDM_new(vertex_it->num_elements, 0, face_it->num_elements);
	CustomData_merge(&dm1->faceData, &result->faceData, CD_MASK_DERIVEDMESH,
					  CD_DEFAULT, face_it->num_elements); 
	CustomData_merge(&dm2->faceData, &result->faceData, CD_MASK_DERIVEDMESH,
					  CD_DEFAULT, face_it->num_elements); 

	// step through the vertex iterators:
	for (i = 0; !vertex_it->Done(vertex_it->it); i++) {
		CSG_IVertex csgvert;
		MVert *mvert = CDDM_get_vert(result, i);

		// retrieve a csg vertex from the boolean module
		vertex_it->Fill(vertex_it->it, &csgvert);
		vertex_it->Step(vertex_it->it);

		// we have to map the vertex coordinates back in the coordinate frame
		// of the resulting object, since it was computed in world space
		mul_v3_m4v3(mvert->co, parinv, csgvert.position);
	}

	// a hash table to remap materials to indices
	if (mat) {
		material_hash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "CSG_mat gh");
		*totmat = 0;
	}

	// step through the face iterators
	for(i = 0; !face_it->Done(face_it->it); i++) {
		Mesh *orig_me;
		Object *orig_ob;
		Material *orig_mat;
		CSG_IFace csgface;
		MFace *mface;
		int orig_index, mat_nr;

		// retrieve a csg face from the boolean module
		face_it->Fill(face_it->it, &csgface);
		face_it->Step(face_it->it);

		// find the original mesh and data
		orig_ob = (csgface.orig_face < dm1->getNumFaces(dm1))? ob1: ob2;
		orig_dm = (csgface.orig_face < dm1->getNumFaces(dm1))? dm1: dm2;
		orig_me = (orig_ob == ob1)? me1: me2;
		orig_index = (orig_ob == ob1)? csgface.orig_face: csgface.orig_face - dm1->getNumFaces(dm1);

		// copy all face layers, including mface
		CustomData_copy_data(&orig_dm->faceData, &result->faceData, orig_index, i, 1);

		// set mface
		mface = CDDM_get_face(result, i);
		mface->v1 = csgface.vertex_index[0];
		mface->v2 = csgface.vertex_index[1];
		mface->v3 = csgface.vertex_index[2];
		mface->v4 = (csgface.vertex_number == 4)? csgface.vertex_index[3]: 0;

		// set material, based on lookup in hash table
		orig_mat= give_current_material(orig_ob, mface->mat_nr+1);

		if (mat && orig_mat) {
			if (!BLI_ghash_haskey(material_hash, orig_mat)) {
				mat[*totmat] = orig_mat;
				mat_nr = mface->mat_nr = (*totmat)++;
				BLI_ghash_insert(material_hash, orig_mat, SET_INT_IN_POINTER(mat_nr));
			}
			else
				mface->mat_nr = GET_INT_FROM_POINTER(BLI_ghash_lookup(material_hash, orig_mat));
		}
		else
			mface->mat_nr = 0;

		InterpCSGFace(result, orig_dm, i, orig_index, csgface.vertex_number,
					  (orig_me == me2)? mapmat: NULL);

		test_index_face(mface, &result->faceData, i, csgface.vertex_number);
	}

	if (material_hash)
		BLI_ghash_free(material_hash, NULL, NULL);

//.........这里部分代码省略.........