static void face_duplilist(ListBase *lb, ID *id, Scene *scene, Object *par, float par_space_mat[][4], int level, int animated)
{
	Object *ob, *ob_iter;
	Base *base = NULL;
	DupliObject *dob;
	DerivedMesh *dm;
	Mesh *me= par->data;
	MTFace *mtface;
	MFace *mface;
	MVert *mvert;
	float pmat[4][4], imat[3][3], (*orco)[3] = NULL, w;
	int lay, oblay, totface, a;
	Scene *sce = NULL;
	Group *group = NULL;
	GroupObject *go = NULL;
	EditMesh *em;
	float ob__obmat[4][4]; /* needed for groups where the object matrix needs to be modified */
	
	/* simple preventing of too deep nested groups */
	if(level>MAX_DUPLI_RECUR) return;
	
	Mat4CpyMat4(pmat, par->obmat);
	
	em = BKE_mesh_get_editmesh(me);
	if(em) {
		int totvert;
		
		dm= editmesh_get_derived_cage(scene, par, em, CD_MASK_BAREMESH);
		
		totface= dm->getNumFaces(dm);
		mface= MEM_mallocN(sizeof(MFace)*totface, "mface temp");
		dm->copyFaceArray(dm, mface);
		totvert= dm->getNumVerts(dm);
		mvert= MEM_mallocN(sizeof(MVert)*totvert, "mvert temp");
		dm->copyVertArray(dm, mvert);

		BKE_mesh_end_editmesh(me, em);
	}
	else {
		dm = mesh_get_derived_deform(scene, par, CD_MASK_BAREMESH);
		
		totface= dm->getNumFaces(dm);
		mface= dm->getFaceArray(dm);
		mvert= dm->getVertArray(dm);
	}

	if(G.rendering) {

		orco= (float(*)[3])get_mesh_orco_verts(par);
		transform_mesh_orco_verts(me, orco, me->totvert, 0);
		mtface= me->mtface;
	}
	else {
		orco= NULL;
		mtface= NULL;
	}
	
	/* having to loop on scene OR group objects is NOT FUN */
	if (GS(id->name) == ID_SCE) {
		sce = (Scene *)id;
		lay= sce->lay;
		base= sce->base.first;
	} else {
		group = (Group *)id;
		lay= group->layer;
		go = group->gobject.first;
	}
	
	/* Start looping on Scene OR Group objects */
	while (base || go) { 
		if (sce) {
			ob_iter= base->object;
			oblay = base->lay;
		} else {
			ob_iter= go->ob;
			oblay = ob_iter->lay;
		}
		
		if (lay & oblay && scene->obedit!=ob_iter) {
			ob=ob_iter->parent;
			while(ob) {
				if(ob==par) {
					ob = ob_iter;
	/* End Scene/Group object loop, below is generic */
					
					/* par_space_mat - only used for groups so we can modify the space dupli's are in
					   when par_space_mat is NULL ob->obmat can be used instead of ob__obmat
					*/
					if(par_space_mat)
						Mat4MulMat4(ob__obmat, ob->obmat, par_space_mat);
					else
						Mat4CpyMat4(ob__obmat, ob->obmat);
					
					Mat3CpyMat4(imat, ob->parentinv);
						
					/* mballs have a different dupli handling */
					if(ob->type!=OB_MBALL) ob->flag |= OB_DONE;	/* doesnt render */

					for(a=0; a<totface; a++) {
						int mv1 = mface[a].v1;
//.........这里部分代码省略.........

/**
 * This function populates an array of verts for the triangles of a mesh
 * Tangent and Normals are also stored
 */
static TriTessFace *mesh_calc_tri_tessface(
        Mesh *me, bool tangent, DerivedMesh *dm)
{
	int i;
	MVert *mvert;
	TSpace *tspace;
	float *precomputed_normals = NULL;
	bool calculate_normal;

	const int tottri = poly_to_tri_count(me->totpoly, me->totloop);
	MLoopTri *looptri;
	TriTessFace *triangles;

	/* calculate normal for each polygon only once */
	unsigned int mpoly_prev = UINT_MAX;
	float no[3];

	mvert = CustomData_get_layer(&me->vdata, CD_MVERT);
	looptri = MEM_mallocN(sizeof(*looptri) * tottri, __func__);
	triangles = MEM_mallocN(sizeof(TriTessFace) * tottri, __func__);

	if (tangent) {
		DM_ensure_normals(dm);
		DM_calc_loop_tangents(dm);

		precomputed_normals = dm->getPolyDataArray(dm, CD_NORMAL);
		calculate_normal = precomputed_normals ? false : true;

		tspace = dm->getLoopDataArray(dm, CD_TANGENT);
		BLI_assert(tspace);
	}

	BKE_mesh_recalc_looptri(
	            me->mloop, me->mpoly,
	            me->mvert,
	            me->totloop, me->totpoly,
	            looptri);

	for (i = 0; i < tottri; i++) {
		MLoopTri *lt = &looptri[i];
		MPoly *mp = &me->mpoly[lt->poly];

		triangles[i].mverts[0] = &mvert[me->mloop[lt->tri[0]].v];
		triangles[i].mverts[1] = &mvert[me->mloop[lt->tri[1]].v];
		triangles[i].mverts[2] = &mvert[me->mloop[lt->tri[2]].v];
		triangles[i].is_smooth = (mp->flag & ME_SMOOTH) != 0;

		if (tangent) {
			triangles[i].tspace[0] = &tspace[lt->tri[0]];
			triangles[i].tspace[1] = &tspace[lt->tri[1]];
			triangles[i].tspace[2] = &tspace[lt->tri[2]];

			if (calculate_normal) {
				if (lt->poly != mpoly_prev) {
					const MPoly *mp = &me->mpoly[lt->poly];
					BKE_mesh_calc_poly_normal(mp, &me->mloop[mp->loopstart], me->mvert, no);
					mpoly_prev = lt->poly;
				}
				copy_v3_v3(triangles[i].normal, no);
			}
			else {
				copy_v3_v3(triangles[i].normal, &precomputed_normals[lt->poly]);
			}
		}
	}

	MEM_freeN(looptri);

	return triangles;
}

void RE_bake_pixels_populate(
        Mesh *me, BakePixel pixel_array[],
        const size_t num_pixels, const BakeImages *bake_images, const char *uv_layer)
{
	BakeDataZSpan bd;
	size_t i;
	int a, p_id;

	const MLoopUV *mloopuv;
	const int tottri = poly_to_tri_count(me->totpoly, me->totloop);
	MLoopTri *looptri;

	/* we can't bake in edit mode */
	if (me->edit_btmesh)
		return;

	bd.pixel_array = pixel_array;
	bd.zspan = MEM_callocN(sizeof(ZSpan) * bake_images->size, "bake zspan");

	/* initialize all pixel arrays so we know which ones are 'blank' */
	for (i = 0; i < num_pixels; i++) {
		pixel_array[i].primitive_id = -1;
	}

	for (i = 0; i < bake_images->size; i++) {
		zbuf_alloc_span(&bd.zspan[i], bake_images->data[i].width, bake_images->data[i].height, R.clipcrop);
	}

	if ((uv_layer == NULL) || (uv_layer[0] == '\0')) {
		mloopuv = CustomData_get_layer(&me->ldata, CD_MLOOPUV);
	}
	else {
		int uv_id = CustomData_get_named_layer(&me->ldata, CD_MLOOPUV, uv_layer);
		mloopuv = CustomData_get_layer_n(&me->ldata, CD_MTFACE, uv_id);
	}

	if (mloopuv == NULL)
		return;

	looptri = MEM_mallocN(sizeof(*looptri) * tottri, __func__);

	BKE_mesh_recalc_looptri(
	        me->mloop, me->mpoly,
	        me->mvert,
	        me->totloop, me->totpoly,
	        looptri);

	p_id = -1;
	for (i = 0; i < tottri; i++) {
		const MLoopTri *lt = &looptri[i];
		const MPoly *mp = &me->mpoly[lt->poly];
		float vec[3][2];
		int mat_nr = mp->mat_nr;
		int image_id = bake_images->lookup[mat_nr];

		bd.bk_image = &bake_images->data[image_id];
		bd.primitive_id = ++p_id;

		for (a = 0; a < 3; a++) {
			const float *uv = mloopuv[lt->tri[a]].uv;

			/* Note, workaround for pixel aligned UVs which are common and can screw up our intersection tests
			 * where a pixel gets in between 2 faces or the middle of a quad,
			 * camera aligned quads also have this problem but they are less common.
			 * Add a small offset to the UVs, fixes bug #18685 - Campbell */
			vec[a][0] = uv[0] * (float)bd.bk_image->width - (0.5f + 0.001f);
			vec[a][1] = uv[1] * (float)bd.bk_image->height - (0.5f + 0.002f);
		}

		bake_differentials(&bd, vec[0], vec[1], vec[2]);
		zspan_scanconvert(&bd.zspan[image_id], (void *)&bd, vec[0], vec[1], vec[2], store_bake_pixel);
	}

	for (i = 0; i < bake_images->size; i++) {
		zbuf_free_span(&bd.zspan[i]);
	}

	MEM_freeN(looptri);
	MEM_freeN(bd.zspan);
}

static void waveModifier_do(WaveModifierData *md, 
                            Scene *scene, Object *ob, DerivedMesh *dm,
                            float (*vertexCos)[3], int numVerts)
{
	WaveModifierData *wmd = (WaveModifierData *) md;
	MVert *mvert = NULL;
	MDeformVert *dvert;
	int defgrp_index;
	float ctime = BKE_scene_frame_get(scene);
	float minfac = (float)(1.0 / exp(wmd->width * wmd->narrow * wmd->width * wmd->narrow));
	float lifefac = wmd->height;
	float (*tex_co)[3] = NULL;
	const int wmd_axis = wmd->flag & (MOD_WAVE_X | MOD_WAVE_Y);
	const float falloff = wmd->falloff;
	float falloff_fac = 1.0f; /* when falloff == 0.0f this stays at 1.0f */

	if ((wmd->flag & MOD_WAVE_NORM) && (ob->type == OB_MESH))
		mvert = dm->getVertArray(dm);

	if (wmd->objectcenter) {
		float mat[4][4];
		/* get the control object's location in local coordinates */
		invert_m4_m4(ob->imat, ob->obmat);
		mul_m4_m4m4(mat, ob->imat, wmd->objectcenter->obmat);

		wmd->startx = mat[3][0];
		wmd->starty = mat[3][1];
	}

	/* get the index of the deform group */
	modifier_get_vgroup(ob, dm, wmd->defgrp_name, &dvert, &defgrp_index);

	if (wmd->damp == 0) wmd->damp = 10.0f;

	if (wmd->lifetime != 0.0f) {
		float x = ctime - wmd->timeoffs;

		if (x > wmd->lifetime) {
			lifefac = x - wmd->lifetime;

			if (lifefac > wmd->damp) lifefac = 0.0;
			else lifefac = (float)(wmd->height * (1.0f - sqrtf(lifefac / wmd->damp)));
		}
	}

	if (wmd->texture) {
		tex_co = MEM_mallocN(sizeof(*tex_co) * numVerts,
		                     "waveModifier_do tex_co");
		get_texture_coords((MappingInfoModifierData *)wmd, ob, dm, vertexCos, tex_co, numVerts);

		modifier_init_texture(wmd->modifier.scene, wmd->texture);
	}

	if (lifefac != 0.0f) {
		/* avoid divide by zero checks within the loop */
		float falloff_inv = falloff ? 1.0f / falloff : 1.0f;
		int i;

		for (i = 0; i < numVerts; i++) {
			float *co = vertexCos[i];
			float x = co[0] - wmd->startx;
			float y = co[1] - wmd->starty;
			float amplit = 0.0f;
			float def_weight = 1.0f;

			/* get weights */
			if (dvert) {
				def_weight = defvert_find_weight(&dvert[i], defgrp_index);

				/* if this vert isn't in the vgroup, don't deform it */
				if (def_weight == 0.0f) {
					continue;
				}
			}

			switch (wmd_axis) {
				case MOD_WAVE_X | MOD_WAVE_Y:
					amplit = sqrtf(x * x + y * y);
					break;
				case MOD_WAVE_X:
					amplit = x;
					break;
				case MOD_WAVE_Y:
					amplit = y;
					break;
			}

			/* this way it makes nice circles */
			amplit -= (ctime - wmd->timeoffs) * wmd->speed;

			if (wmd->flag & MOD_WAVE_CYCL) {
				amplit = (float)fmodf(amplit - wmd->width, 2.0f * wmd->width) +
				         wmd->width;
			}

			if (falloff != 0.0f) {
				float dist = 0.0f;

				switch (wmd_axis) {
					case MOD_WAVE_X | MOD_WAVE_Y:
//.........这里部分代码省略.........

void render_view3d_draw(RenderEngine *engine, const bContext *C)
{
	Render *re = engine->re;
	RenderResult rres;
	char name[32];
	
	render_view3d_do(engine, C);
	
	if (re == NULL) {
		sprintf(name, "View3dPreview %p", (void *)CTX_wm_region(C));
		re = RE_GetRender(name);
	
		if (re == NULL) return;
	}
	
	RE_AcquireResultImage(re, &rres);
	
	if (rres.rectf) {
		Scene *scene = CTX_data_scene(C);
		bool force_fallback = false;
		bool need_fallback = true;
		float dither = scene->r.dither_intensity;

		/* Dithering is not supported on GLSL yet */
		force_fallback |= dither != 0.0f;

		/* If user decided not to use GLSL, fallback to glaDrawPixelsAuto */
		force_fallback |= (U.image_draw_method != IMAGE_DRAW_METHOD_GLSL);

		/* Try using GLSL display transform. */
		if (force_fallback == false) {
			if (IMB_colormanagement_setup_glsl_draw(NULL, &scene->display_settings, TRUE)) {
				glEnable(GL_BLEND);
				glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
				glaDrawPixelsTex(rres.xof, rres.yof, rres.rectx, rres.recty, GL_RGBA, GL_FLOAT,
				                 GL_LINEAR, rres.rectf);
				glDisable(GL_BLEND);

				IMB_colormanagement_finish_glsl_draw();
				need_fallback = false;
			}
		}

		/* If GLSL failed, use old-school CPU-based transform. */
		if (need_fallback) {
			unsigned char *display_buffer = MEM_mallocN(4 * rres.rectx * rres.recty * sizeof(char),
			                                            "render_view3d_draw");

			IMB_colormanagement_buffer_make_display_space(rres.rectf, display_buffer, rres.rectx, rres.recty,
			                                              4, dither, NULL, &scene->display_settings);

			glEnable(GL_BLEND);
			glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
			glaDrawPixelsAuto(rres.xof, rres.yof, rres.rectx, rres.recty, GL_RGBA, GL_UNSIGNED_BYTE,
			                  GL_LINEAR, display_buffer);
			glDisable(GL_BLEND);

			MEM_freeN(display_buffer);
		}
	}

	RE_ReleaseResultImage(re);
}

/**
 * Main boxpacking function accessed from other functions
 * This sets boxes x,y to positive values, sorting from 0,0 outwards.
 * There is no limit to the space boxes may take, only that they will be packed
 * tightly into the lower left hand corner (0,0)
 *
 * \param boxarray: a pre allocated array of boxes.
 *      only the 'box->x' and 'box->y' are set, 'box->w' and 'box->h' are used,
 *      'box->index' is not used at all, the only reason its there
 *          is that the box array is sorted by area and programs need to be able
 *          to have some way of writing the boxes back to the original data.
 * \param len: the number of boxes in the array.
 * \param r_tot_x, r_tot_y: set so you can normalize the data.
 *  */
void BLI_box_pack_2d(BoxPack *boxarray, const uint len, float *r_tot_x, float *r_tot_y)
{
	uint box_index, verts_pack_len, i, j, k;
	uint *vertex_pack_indices;  /* an array of indices used for sorting verts */
	bool isect;
	float tot_x = 0.0f, tot_y = 0.0f;

	BoxPack *box, *box_test; /*current box and another for intersection tests*/
	BoxVert *vert; /* the current vert */

	struct VertSortContext vs_ctx;

	if (!len) {
		*r_tot_x = tot_x;
		*r_tot_y = tot_y;
		return;
	}

	/* Sort boxes, biggest first */
	qsort(boxarray, (size_t)len, sizeof(BoxPack), box_areasort);

	/* add verts to the boxes, these are only used internally  */
	vert = MEM_mallocN((size_t)len * 4 * sizeof(BoxVert), "BoxPack Verts");
	vertex_pack_indices = MEM_mallocN((size_t)len * 3 * sizeof(int), "BoxPack Indices");

	vs_ctx.vertarray = vert;

	for (box = boxarray, box_index = 0, i = 0; box_index < len; box_index++, box++) {

		vert->blb = vert->brb = vert->tlb =
		            vert->isect_cache[0] = vert->isect_cache[1] =
		            vert->isect_cache[2] = vert->isect_cache[3] = NULL;
		vert->free = CORNERFLAGS & ~TRF;
		vert->trb = box;
		vert->used = false;
		vert->index = i++;
		box->v[BL] = vert++;

		vert->trb = vert->brb = vert->tlb =
		            vert->isect_cache[0] = vert->isect_cache[1] =
		            vert->isect_cache[2] = vert->isect_cache[3] = NULL;
		vert->free = CORNERFLAGS & ~BLF;
		vert->blb = box;
		vert->used = false;
		vert->index = i++;
		box->v[TR] = vert++;

		vert->trb = vert->blb = vert->tlb =
		            vert->isect_cache[0] = vert->isect_cache[1] =
		            vert->isect_cache[2] = vert->isect_cache[3] = NULL;
		vert->free = CORNERFLAGS & ~BRF;
		vert->brb = box;
		vert->used = false;
		vert->index = i++;
		box->v[TL] = vert++;

		vert->trb = vert->blb = vert->brb =
		            vert->isect_cache[0] = vert->isect_cache[1] =
		            vert->isect_cache[2] = vert->isect_cache[3] = NULL;
		vert->free = CORNERFLAGS & ~TLF;
		vert->tlb = box;
		vert->used = false;
		vert->index = i++;
		box->v[BR] = vert++;
	}
	vert = NULL;

	/* Pack the First box!
	 * then enter the main box-packing loop */

	box = boxarray; /* get the first box  */
	/* First time, no boxes packed */
	box->v[BL]->free = 0; /* Can't use any if these */
	box->v[BR]->free &= ~(BLF | BRF);
	box->v[TL]->free &= ~(BLF | TLF);

	tot_x = box->w;
	tot_y = box->h;

	/* This sets all the vertex locations */
	box_xmin_set(box, 0.0f);
	box_ymin_set(box, 0.0f);
	box->x = box->y = 0.0f;

	for (i = 0; i < 4; i++) {
		box->v[i]->used = true;
//.........这里部分代码省略.........

/* screen can be NULL */
static ImBuf *blend_file_thumb(Scene *scene, bScreen *screen, int **thumb_pt)
{
	/* will be scaled down, but gives some nice oversampling */
	ImBuf *ibuf;
	int *thumb;
	char err_out[256] = "unknown";

	/* screen if no camera found */
	ScrArea *sa = NULL;
	ARegion *ar = NULL;
	View3D *v3d = NULL;

	*thumb_pt = NULL;

	/* scene can be NULL if running a script at startup and calling the save operator */
	if (G.background || scene == NULL)
		return NULL;

	if ((scene->camera == NULL) && (screen != NULL)) {
		sa = BKE_screen_find_big_area(screen, SPACE_VIEW3D, 0);
		ar = BKE_area_find_region_type(sa, RGN_TYPE_WINDOW);
		if (ar) {
			v3d = sa->spacedata.first;
		}
	}

	if (scene->camera == NULL && v3d == NULL) {
		return NULL;
	}

	/* gets scaled to BLEN_THUMB_SIZE */
	if (scene->camera) {
		ibuf = ED_view3d_draw_offscreen_imbuf_simple(scene, scene->camera,
		                                             BLEN_THUMB_SIZE * 2, BLEN_THUMB_SIZE * 2,
		                                             IB_rect, OB_SOLID, FALSE, FALSE, R_ADDSKY, err_out);
	}
	else {
		ibuf = ED_view3d_draw_offscreen_imbuf(scene, v3d, ar, BLEN_THUMB_SIZE * 2, BLEN_THUMB_SIZE * 2,
		                                      IB_rect, FALSE, R_ADDSKY, err_out);
	}

	if (ibuf) {
		float aspect = (scene->r.xsch * scene->r.xasp) / (scene->r.ysch * scene->r.yasp);

		/* dirty oversampling */
		IMB_scaleImBuf(ibuf, BLEN_THUMB_SIZE, BLEN_THUMB_SIZE);

		/* add pretty overlay */
		IMB_overlayblend_thumb(ibuf->rect, ibuf->x, ibuf->y, aspect);
		
		/* first write into thumb buffer */
		thumb = MEM_mallocN(((2 + (BLEN_THUMB_SIZE * BLEN_THUMB_SIZE))) * sizeof(int), "write_file thumb");

		thumb[0] = BLEN_THUMB_SIZE;
		thumb[1] = BLEN_THUMB_SIZE;

		memcpy(thumb + 2, ibuf->rect, BLEN_THUMB_SIZE * BLEN_THUMB_SIZE * sizeof(int));
	}
	else {
		/* '*thumb_pt' needs to stay NULL to prevent a bad thumbnail from being handled */
		fprintf(stderr, "blend_file_thumb failed to create thumbnail: %s\n", err_out);
		thumb = NULL;
	}
	
	/* must be freed by caller */
	*thumb_pt = thumb;
	
	return ibuf;
}

//.........这里部分代码省略.........
				v1= eva[ icoface[a][0] ];
				v2= eva[ icoface[a][1] ];
				v3= eva[ icoface[a][2] ];
				evtemp = addfacelist(em, v1, v2, v3, 0, NULL, NULL);
				evtemp->e1->f = 1+2;
				evtemp->e2->f = 1+2;
				evtemp->e3->f = 1+2;
			}

			dia*=200;
			for(a=1; a<subdiv; a++) esubdivideflag(obedit, em, 2, dia, 0, B_SPHERE,1, SUBDIV_CORNER_PATH, 0);
			/* and now do imat */
			eve= em->verts.first;
			while(eve) {
				if(eve->f & 2) {
					mul_m4_v3(mat,eve->co);
				}
				eve= eve->next;
			}
			
			// Clear the flag 2 from the edges
			for(eed=em->edges.first;eed;eed=eed->next){
				if(eed->f & 2){
					   eed->f &= !2;
				}   
			}
		}
		break;
	case PRIM_MONKEY: /* Monkey */
		{
			//extern int monkeyo, monkeynv, monkeynf;
			//extern signed char monkeyf[][4];
			//extern signed char monkeyv[][3];
			EditVert **tv= MEM_mallocN(sizeof(*tv)*monkeynv*2, "tv");
			int i;

			for (i=0; i<monkeynv; i++) {
				float v[3];
				v[0]= (monkeyv[i][0]+127)/128.0, v[1]= monkeyv[i][1]/128.0, v[2]= monkeyv[i][2]/128.0;
				tv[i]= addvertlist(em, v, NULL);
				tv[i]->f |= SELECT;
				tv[monkeynv+i]= (fabs(v[0]= -v[0])<0.001)?tv[i]:addvertlist(em, v, NULL);
				tv[monkeynv+i]->f |= SELECT;
			}
			for (i=0; i<monkeynf; i++) {
				addfacelist(em, tv[monkeyf[i][0]+i-monkeyo], tv[monkeyf[i][1]+i-monkeyo], tv[monkeyf[i][2]+i-monkeyo], (monkeyf[i][3]!=monkeyf[i][2])?tv[monkeyf[i][3]+i-monkeyo]:NULL, NULL, NULL);
				addfacelist(em, tv[monkeynv+monkeyf[i][2]+i-monkeyo], tv[monkeynv+monkeyf[i][1]+i-monkeyo], tv[monkeynv+monkeyf[i][0]+i-monkeyo], (monkeyf[i][3]!=monkeyf[i][2])?tv[monkeynv+monkeyf[i][3]+i-monkeyo]:NULL, NULL, NULL);
			}

			MEM_freeN(tv);

			/* and now do imat */
			for(eve= em->verts.first; eve; eve= eve->next) {
				if(eve->f & SELECT) {
					mul_m4_v3(mat,eve->co);
				}
			}
			recalc_editnormals(em);
		}
		break;
	default: /* all types except grid, sphere... */
		if(type==PRIM_CONE);
		else if(ext==0) 
			depth= 0.0f;
	
		/* first vertex at 0° for circular objects */

/* Object Surface Area Heuristic splitter */
int rtbuild_heuristic_object_split(RTBuilder *b, int nchilds)
{
	int size = rtbuild_size(b);
	assert(nchilds == 2);
	assert(size > 1);
	int baxis = -1, boffset = 0;

	if (size > nchilds) {
		float bcost = FLT_MAX;
		baxis = -1, boffset = size / 2;

		SweepCost *sweep = (SweepCost *)MEM_mallocN(sizeof(SweepCost) * size, "RTBuilder.HeuristicSweep");
		
		for (int axis = 0; axis < 3; axis++) {
			SweepCost sweep_left;

			RTBuilder::Object **obj = b->sorted_begin[axis];
			
//			float right_cost = 0;
			for (int i = size - 1; i >= 0; i--) {
				if (i == size - 1) {
					copy_v3_v3(sweep[i].bb, obj[i]->bb);
					copy_v3_v3(sweep[i].bb + 3, obj[i]->bb + 3);
					sweep[i].cost = obj[i]->cost;
				}
				else {
					sweep[i].bb[0] = min_ff(obj[i]->bb[0], sweep[i + 1].bb[0]);
					sweep[i].bb[1] = min_ff(obj[i]->bb[1], sweep[i + 1].bb[1]);
					sweep[i].bb[2] = min_ff(obj[i]->bb[2], sweep[i + 1].bb[2]);
					sweep[i].bb[3] = max_ff(obj[i]->bb[3], sweep[i + 1].bb[3]);
					sweep[i].bb[4] = max_ff(obj[i]->bb[4], sweep[i + 1].bb[4]);
					sweep[i].bb[5] = max_ff(obj[i]->bb[5], sweep[i + 1].bb[5]);
					sweep[i].cost  = obj[i]->cost + sweep[i + 1].cost;
				}
//				right_cost += obj[i]->cost;
			}
			
			sweep_left.bb[0] = obj[0]->bb[0];
			sweep_left.bb[1] = obj[0]->bb[1];
			sweep_left.bb[2] = obj[0]->bb[2];
			sweep_left.bb[3] = obj[0]->bb[3];
			sweep_left.bb[4] = obj[0]->bb[4];
			sweep_left.bb[5] = obj[0]->bb[5];
			sweep_left.cost  = obj[0]->cost;
			
//			right_cost -= obj[0]->cost;	if (right_cost < 0) right_cost = 0;

			for (int i = 1; i < size; i++) {
				//Worst case heuristic (cost of each child is linear)
				float hcost, left_side, right_side;
				
				// not using log seems to have no impact on raytracing perf, but
				// makes tree construction quicker, left out for now to test (brecht)
				// left_side  = bb_area(sweep_left.bb, sweep_left.bb + 3) * (sweep_left.cost + logf((float)i));
				// right_side = bb_area(sweep[i].bb,   sweep[i].bb   + 3) * (sweep[i].cost   + logf((float)size - i));
				left_side = bb_area(sweep_left.bb, sweep_left.bb + 3) * (sweep_left.cost);
				right_side = bb_area(sweep[i].bb, sweep[i].bb + 3) * (sweep[i].cost);
				hcost = left_side + right_side;

				assert(left_side >= 0);
				assert(right_side >= 0);
				
				if (left_side > bcost) break;   //No way we can find a better heuristic in this axis

				assert(hcost >= 0);
				// this makes sure the tree built is the same whatever is the order of the sorting axis
				if (hcost < bcost || (hcost == bcost && axis < baxis)) {
					bcost = hcost;
					baxis = axis;
					boffset = i;
				}
				DO_MIN(obj[i]->bb,   sweep_left.bb);
				DO_MAX(obj[i]->bb + 3, sweep_left.bb + 3);

				sweep_left.cost += obj[i]->cost;
//				right_cost -= obj[i]->cost; if (right_cost < 0) right_cost = 0;
			}
			
			//assert(baxis >= 0 && baxis < 3);
			if (!(baxis >= 0 && baxis < 3))
				baxis = 0;
		}
			
		
		MEM_freeN(sweep);
	}
	else if (size == 2) {
		baxis = 0;
		boffset = 1;
	}
	else if (size == 1) {
		b->child_offset[0] = 0;
		b->child_offset[1] = 1;
		return 1;
	}
		
	b->child_offset[0] = 0;
	b->child_offset[1] = boffset;
	b->child_offset[2] = size;
//.........这里部分代码省略.........

size_t blf_font_width_to_rstrlen(FontBLF *font, const char *str, size_t len, float width, float *r_width)
{
	unsigned int c;
	GlyphBLF *g, *g_prev = NULL;
	FT_Vector delta;
	int pen_x = 0;
	size_t i = 0, i_prev;
	GlyphBLF **glyph_ascii_table = font->glyph_cache->glyph_ascii_table;
	const int width_i = (int)width + 1;
	int width_new;

	bool is_malloc;
	int (*width_accum)[2];
	int width_accum_ofs = 0;

	BLF_KERNING_VARS(font, has_kerning, kern_mode);

	/* skip allocs in simple cases */
	len = BLI_strnlen(str, len);
	if (width_i <= 1 || len == 0) {
		if (r_width) {
			*r_width = 0.0f;
		}
		return len;
	}

	if (len < 2048) {
		width_accum = BLI_array_alloca(width_accum, len);
		is_malloc = false;
	}
	else {
		width_accum = MEM_mallocN(sizeof(*width_accum) * len, __func__);
		is_malloc = true;
	}

	blf_font_ensure_ascii_table(font);

	while ((i < len) && str[i]) {
		BLF_UTF8_NEXT_FAST(font, g, str, i, c, glyph_ascii_table);

		if (UNLIKELY(c == BLI_UTF8_ERR))
			break;
		if (UNLIKELY(g == NULL))
			continue;
		if (has_kerning)
			BLF_KERNING_STEP(font, kern_mode, g_prev, g, delta, pen_x);

		pen_x += g->advance_i;

		width_accum[width_accum_ofs][0] = (int)i;
		width_accum[width_accum_ofs][1] = pen_x;
		width_accum_ofs++;

		g_prev = g;
	}

	if (pen_x > width_i && width_accum_ofs != 0) {
		const int min_x = pen_x - width_i;

		/* search backwards */
		width_new = pen_x;
		while (width_accum_ofs-- > 0) {
			if (min_x > width_accum[width_accum_ofs][1]) {
				break;
			}
		}
		width_accum_ofs++;
		width_new = pen_x - width_accum[width_accum_ofs][1];
		i_prev = (size_t)width_accum[width_accum_ofs][0];
	}
	else {
		width_new = pen_x;
		i_prev = 0;
	}

	if (is_malloc) {
		MEM_freeN(width_accum);
	}

	if (r_width) {
		*r_width = (float)width_new;
	}

	return i_prev;
}

void calc_curvepath(Object *ob)
{
	BevList *bl;
	BevPoint *bevp, *bevpn, *bevpfirst, *bevplast;
	PathPoint *pp;
	Curve *cu;
	Nurb *nu;
	Path *path;
	float *fp, *dist, *maxdist, xyz[3];
	float fac, d=0, fac1, fac2;
	int a, tot, cycl=0;
	

	/* in a path vertices are with equal differences: path->len = number of verts */
	/* NOW WITH BEVELCURVE!!! */
	
	if(ob==NULL || ob->type != OB_CURVE) return;
	cu= ob->data;
	if(cu->editnurb) 
		nu= cu->editnurb->first;
	else 
		nu= cu->nurb.first;
	
	if(cu->path) free_path(cu->path);
	cu->path= NULL;
	
	bl= cu->bev.first;
	if(bl==NULL || !bl->nr) return;

	cu->path=path= MEM_callocN(sizeof(Path), "path");
	
	/* if POLY: last vertice != first vertice */
	cycl= (bl->poly!= -1);
	
	if(cycl) tot= bl->nr;
	else tot= bl->nr-1;
	
	path->len= tot+1;
	/* exception: vector handle paths and polygon paths should be subdivided at least a factor resolu */
	if(path->len<nu->resolu*SEGMENTSU(nu)) path->len= nu->resolu*SEGMENTSU(nu);
	
	dist= (float *)MEM_mallocN((tot+1)*4, "calcpathdist");

		/* all lengths in *dist */
	bevp= bevpfirst= (BevPoint *)(bl+1);
	fp= dist;
	*fp= 0;
	for(a=0; a<tot; a++) {
		fp++;
		if(cycl && a==tot-1)
			VecSubf(xyz, bevpfirst->vec, bevp->vec);
		else
			VecSubf(xyz, (bevp+1)->vec, bevp->vec);
		
		*fp= *(fp-1)+VecLength(xyz);
		bevp++;
	}
	
	path->totdist= *fp;

		/* the path verts  in path->data */
		/* now also with TILT value */
	pp= path->data = (PathPoint *)MEM_callocN(sizeof(PathPoint)*4*path->len, "pathdata"); // XXX - why *4? - in 2.4x each element was 4 and the size was 16, so better leave for now - Campbell
	
	bevp= bevpfirst;
	bevpn= bevp+1;
	bevplast= bevpfirst + (bl->nr-1);
	fp= dist+1;
	maxdist= dist+tot;
	fac= 1.0f/((float)path->len-1.0f);
        fac = fac * path->totdist;

	for(a=0; a<path->len; a++) {
		
		d= ((float)a)*fac;
		
		/* we're looking for location (distance) 'd' in the array */
		while((d>= *fp) && fp<maxdist) {
			fp++;
			if(bevp<bevplast) bevp++;
			bevpn= bevp+1;
			if(bevpn>bevplast) {
				if(cycl) bevpn= bevpfirst;
				else bevpn= bevplast;
			}
		}
		
		fac1= *(fp)- *(fp-1);
		fac2= *(fp)-d;
		fac1= fac2/fac1;
		fac2= 1.0f-fac1;

		VecLerpf(pp->vec, bevp->vec, bevpn->vec, fac2);
		pp->vec[3]= fac1*bevp->alfa + fac2*bevpn->alfa;
		pp->radius= fac1*bevp->radius + fac2*bevpn->radius;
		QuatInterpol(pp->quat, bevp->quat, bevpn->quat, fac2);
		NormalQuat(pp->quat);
		
		pp++;
	}
//.........这里部分代码省略.........

static void warpModifier_do(WarpModifierData *wmd, Object *ob,
                            DerivedMesh *dm, float (*vertexCos)[3], int numVerts)
{
	float obinv[4][4];
	float mat_from[4][4];
	float mat_from_inv[4][4];
	float mat_to[4][4];
	float mat_unit[4][4];
	float mat_final[4][4];

	float tmat[4][4];

	float strength = wmd->strength;
	float fac = 1.0f, weight;
	int i;
	int defgrp_index;
	MDeformVert *dvert, *dv = NULL;

	float (*tex_co)[3] = NULL;

	if (!(wmd->object_from && wmd->object_to))
		return;

	modifier_get_vgroup(ob, dm, wmd->defgrp_name, &dvert, &defgrp_index);

	if (wmd->curfalloff == NULL) /* should never happen, but bad lib linking could cause it */
		wmd->curfalloff = curvemapping_add(1, 0.0f, 0.0f, 1.0f, 1.0f);

	if (wmd->curfalloff) {
		curvemapping_initialize(wmd->curfalloff);
	}

	invert_m4_m4(obinv, ob->obmat);

	mul_m4_m4m4(mat_from, obinv, wmd->object_from->obmat);
	mul_m4_m4m4(mat_to, obinv, wmd->object_to->obmat);

	invert_m4_m4(tmat, mat_from); // swap?
	mul_m4_m4m4(mat_final, tmat, mat_to);

	invert_m4_m4(mat_from_inv, mat_from);

	unit_m4(mat_unit);

	if (strength < 0.0f) {
		float loc[3];
		strength = -strength;

		/* inverted location is not useful, just use the negative */
		copy_v3_v3(loc, mat_final[3]);
		invert_m4(mat_final);
		negate_v3_v3(mat_final[3], loc);

	}
	weight = strength;

	if (wmd->texture) {
		tex_co = MEM_mallocN(sizeof(*tex_co) * numVerts, "warpModifier_do tex_co");
		get_texture_coords((MappingInfoModifierData *)wmd, ob, dm, vertexCos, tex_co, numVerts);

		modifier_init_texture(wmd->modifier.scene, wmd->texture);
	}

	for (i = 0; i < numVerts; i++) {
		float *co = vertexCos[i];

		if (wmd->falloff_type == eWarp_Falloff_None ||
		    ((fac = len_v3v3(co, mat_from[3])) < wmd->falloff_radius &&
		     (fac = (wmd->falloff_radius - fac) / wmd->falloff_radius)))
		{
			/* skip if no vert group found */
			if (dvert && defgrp_index != -1) {
				dv = &dvert[i];

				if (dv) {
					weight = defvert_find_weight(dv, defgrp_index) * strength;
					if (weight <= 0.0f) /* Should never occure... */
						continue;
				}
			}


			/* closely match PROP_SMOOTH and similar */
			switch (wmd->falloff_type) {
				case eWarp_Falloff_None:
					fac = 1.0f;
					break;
				case eWarp_Falloff_Curve:
					fac = curvemapping_evaluateF(wmd->curfalloff, 0, fac);
					break;
				case eWarp_Falloff_Sharp:
					fac = fac * fac;
					break;
				case eWarp_Falloff_Smooth:
					fac = 3.0f * fac * fac - 2.0f * fac * fac * fac;
					break;
				case eWarp_Falloff_Root:
					fac = (float)sqrt(fac);
					break;
				case eWarp_Falloff_Linear:
//.........这里部分代码省略.........

/**
 * Take as inputs two sets of verts, to be processed for detection of doubles and mapping.
 * Each set of verts is defined by its start within mverts array and its num_verts;
 * It builds a mapping for all vertices within source, to vertices within target, or -1 if no double found
 * The int doubles_map[num_verts_source] array must have been allocated by caller.
 */
static void dm_mvert_map_doubles(
        int *doubles_map,
        const MVert *mverts,
        const int target_start,
        const int target_num_verts,
        const int source_start,
        const int source_num_verts,
        const float dist,
        const bool with_follow)
{
	const float dist3 = ((float)M_SQRT3 + 0.00005f) * dist;   /* Just above sqrt(3) */
	int i_source, i_target, i_target_low_bound, target_end, source_end;
	SortVertsElem *sorted_verts_target, *sorted_verts_source;
	SortVertsElem *sve_source, *sve_target, *sve_target_low_bound;
	bool target_scan_completed;

	target_end = target_start + target_num_verts;
	source_end = source_start + source_num_verts;

	/* build array of MVerts to be tested for merging */
	sorted_verts_target = MEM_mallocN(sizeof(SortVertsElem) * target_num_verts, __func__);
	sorted_verts_source = MEM_mallocN(sizeof(SortVertsElem) * source_num_verts, __func__);

	/* Copy target vertices index and cos into SortVertsElem array */
	svert_from_mvert(sorted_verts_target, mverts + target_start, target_start, target_end);

	/* Copy source vertices index and cos into SortVertsElem array */
	svert_from_mvert(sorted_verts_source, mverts + source_start, source_start, source_end);

	/* sort arrays according to sum of vertex coordinates (sumco) */
	qsort(sorted_verts_target, target_num_verts, sizeof(SortVertsElem), svert_sum_cmp);
	qsort(sorted_verts_source, source_num_verts, sizeof(SortVertsElem), svert_sum_cmp);

	sve_target_low_bound = sorted_verts_target;
	i_target_low_bound = 0;
	target_scan_completed = false;

	/* Scan source vertices, in SortVertsElem sorted array, */
	/* all the while maintaining the lower bound of possible doubles in target vertices */
	for (i_source = 0, sve_source = sorted_verts_source;
	     i_source < source_num_verts;
	     i_source++, sve_source++)
	{
		bool double_found;
		float sve_source_sumco;

		/* If source has already been assigned to a target (in an earlier call, with other chunks) */
		if (doubles_map[sve_source->vertex_num] != -1) {
			continue;
		}

		/* If target fully scanned already, then all remaining source vertices cannot have a double */
		if (target_scan_completed) {
			doubles_map[sve_source->vertex_num] = -1;
			continue;
		}

		sve_source_sumco = sum_v3(sve_source->co);

		/* Skip all target vertices that are more than dist3 lower in terms of sumco */
		/* and advance the overall lower bound, applicable to all remaining vertices as well. */
		while ((i_target_low_bound < target_num_verts) &&
		       (sve_target_low_bound->sum_co < sve_source_sumco - dist3))
		{
			i_target_low_bound++;
			sve_target_low_bound++;
		}
		/* If end of target list reached, then no more possible doubles */
		if (i_target_low_bound >= target_num_verts) {
			doubles_map[sve_source->vertex_num] = -1;
			target_scan_completed = true;
			continue;
		}
		/* Test target candidates starting at the low bound of possible doubles, ordered in terms of sumco */
		i_target = i_target_low_bound;
		sve_target = sve_target_low_bound;

		/* i_target will scan vertices in the [v_source_sumco - dist3;  v_source_sumco + dist3] range */

		double_found = false;
		while ((i_target < target_num_verts) &&
		       (sve_target->sum_co <= sve_source_sumco + dist3))
		{
			/* Testing distance for candidate double in target */
			/* v_target is within dist3 of v_source in terms of sumco;  check real distance */
			if (compare_len_v3v3(sve_source->co, sve_target->co, dist)) {
				/* Double found */
				/* If double target is itself already mapped to other vertex,
				 * behavior depends on with_follow option */
				int target_vertex = sve_target->vertex_num;
				if (doubles_map[target_vertex] != -1) {
					if (with_follow) { /* with_follow option:  map to initial target */
						target_vertex = doubles_map[target_vertex];
					}
//.........这里部分代码省略.........

static struct ImageUI_Data *ui_imageuser_data_copy(const struct ImageUI_Data *rnd_pt_src)
{
  struct ImageUI_Data *rnd_pt_dst = MEM_mallocN(sizeof(*rnd_pt_src), __func__);
  memcpy(rnd_pt_dst, rnd_pt_src, sizeof(*rnd_pt_src));
  return rnd_pt_dst;
}

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

	/* calculate the maximum number of copies which will fit within the
	 * prescribed length */
	if (amd->fit_type == MOD_ARR_FITLENGTH || amd->fit_type == MOD_ARR_FITCURVE) {
		float dist = len_v3(offset[3]);

		if (dist > eps) {
			/* this gives length = first copy start to last copy end
			 * add a tiny offset for floating point rounding errors */
			count = (length + eps) / dist;
		}
		else {
			/* if the offset has no translation, just make one copy */
			count = 1;
		}
	}

	if (count < 1)
		count = 1;

	/* The number of verts, edges, loops, polys, before eventually merging doubles */
	result_nverts = chunk_nverts * count + start_cap_nverts + end_cap_nverts;
	result_nedges = chunk_nedges * count + start_cap_nedges + end_cap_nedges;
	result_nloops = chunk_nloops * count + start_cap_nloops + end_cap_nloops;
	result_npolys = chunk_npolys * count + start_cap_npolys + end_cap_npolys;

	/* Initialize a result dm */
	result = CDDM_from_template(dm, result_nverts, result_nedges, 0, result_nloops, result_npolys);
	result_dm_verts = CDDM_get_verts(result);

	if (use_merge) {
		/* Will need full_doubles_map for handling merge */
		full_doubles_map = MEM_mallocN(sizeof(int) * result_nverts, "mod array doubles map");
		fill_vn_i(full_doubles_map, result_nverts, -1);
	}

	/* copy customdata to original geometry */
	DM_copy_vert_data(dm, result, 0, 0, chunk_nverts);
	DM_copy_edge_data(dm, result, 0, 0, chunk_nedges);
	DM_copy_loop_data(dm, result, 0, 0, chunk_nloops);
	DM_copy_poly_data(dm, result, 0, 0, chunk_npolys);

	/* subsurf for eg wont have mesh data in the
	 * now add mvert/medge/mface layers */

	if (!CustomData_has_layer(&dm->vertData, CD_MVERT)) {
		dm->copyVertArray(dm, result_dm_verts);
	}
	if (!CustomData_has_layer(&dm->edgeData, CD_MEDGE)) {
		dm->copyEdgeArray(dm, CDDM_get_edges(result));
	}
	if (!CustomData_has_layer(&dm->polyData, CD_MPOLY)) {
		dm->copyLoopArray(dm, CDDM_get_loops(result));
		dm->copyPolyArray(dm, CDDM_get_polys(result));
	}

	/* Remember first chunk, in case of cap merge */
	first_chunk_start = 0;
	first_chunk_nverts = chunk_nverts;

	unit_m4(current_offset);
	for (c = 1; c < count; c++) {
		/* copy customdata to new geometry */
		DM_copy_vert_data(result, result, 0, c * chunk_nverts, chunk_nverts);
		DM_copy_edge_data(result, result, 0, c * chunk_nedges, chunk_nedges);

//.........这里部分代码省略.........
		widthx= obr->strandbuf->maxwidth*obwinmat[0][0];
		widthy= obr->strandbuf->maxwidth*obwinmat[1][1];

		/* for each bounding box containing a number of strands */
		sbound= obr->strandbuf->bound;
		for (c=0; c<obr->strandbuf->totbound; c++, sbound++) {
			if (clip_render_object(sbound->boundbox, bounds, obwinmat))
				continue;

			/* for each strand in this bounding box */
			for (a=sbound->start; a<sbound->end; a++) {
				strand= RE_findOrAddStrand(obr, a);
				svert= strand->vert;

				/* keep clipping and z depth for 4 control points */
				clip[1]= strand_test_clip(obwinmat, &zspan, bounds, svert->co, &z[1], widthx, widthy);
				clip[2]= strand_test_clip(obwinmat, &zspan, bounds, (svert+1)->co, &z[2], widthx, widthy);
				clip[0]= clip[1]; z[0]= z[1];

				for (b=0; b<strand->totvert-1; b++, svert++) {
					/* compute 4th point clipping and z depth */
					if (b < strand->totvert-2) {
						clip[3]= strand_test_clip(obwinmat, &zspan, bounds, (svert+2)->co, &z[3], widthx, widthy);
					}
					else {
						clip[3]= clip[2]; z[3]= z[2];
					}

					/* check clipping and add to sortsegments buffer */
					if (!(clip[0] & clip[1] & clip[2] & clip[3])) {
						sortseg= BLI_memarena_alloc(memarena, sizeof(StrandSortSegment));
						sortseg->obi= i;
						sortseg->strand= strand->index;
						sortseg->segment= b;

						sortseg->z= 0.5f*(z[1] + z[2]);

						sortseg->next= firstseg;
						firstseg= sortseg;
						totsegment++;
					}

					/* shift clipping and z depth */
					clip[0]= clip[1]; z[0]= z[1];
					clip[1]= clip[2]; z[1]= z[2];
					clip[2]= clip[3]; z[2]= z[3];
				}
			}
		}
	}

	if (!re->test_break(re->tbh)) {
		/* convert list to array and sort */
		sortsegments= MEM_mallocN(sizeof(StrandSortSegment)*totsegment, "StrandSortSegment");
		for (a=0, sortseg=firstseg; a<totsegment; a++, sortseg=sortseg->next)
			sortsegments[a]= *sortseg;
		qsort(sortsegments, totsegment, sizeof(StrandSortSegment), compare_strand_segment);
	}

	BLI_memarena_free(memarena);

	spart.totapixbuf= MEM_callocN(sizeof(int)*pa->rectx*pa->recty, "totapixbuf");

	if (!re->test_break(re->tbh)) {
		/* render segments in sorted order */
		sortseg= sortsegments;
		for (a=0; a<totsegment; a++, sortseg++) {
			if (re->test_break(re->tbh))
				break;

			obi= &re->objectinstance[sortseg->obi];
			obr= obi->obr;

			sseg.obi= obi;
			sseg.strand= RE_findOrAddStrand(obr, sortseg->strand);
			sseg.buffer= sseg.strand->buffer;
			sseg.sqadaptcos= sseg.buffer->adaptcos;
			sseg.sqadaptcos *= sseg.sqadaptcos;

			svert= sseg.strand->vert + sortseg->segment;
			sseg.v[0]= (sortseg->segment > 0)? (svert-1): svert;
			sseg.v[1]= svert;
			sseg.v[2]= svert+1;
			sseg.v[3]= (sortseg->segment < sseg.strand->totvert-2)? svert+2: svert+1;
			sseg.shaded= 0;

			spart.segment= &sseg;

			render_strand_segment(re, winmat, &spart, &zspan, 1, &sseg);
		}
	}

	if (sortsegments)
		MEM_freeN(sortsegments);
	MEM_freeN(spart.totapixbuf);
	
	zbuf_free_span(&zspan);

	return totsegment;
}