[Bf-blender-cvs] [97c2b66] soc-2016-uv_tools: WIP: Simulated Annealing
Phil Gosch
noreply at git.blender.org
Mon Jul 18 17:28:57 CEST 2016
Commit: 97c2b665ad13efdc31cd24c5639f76385316d1a8
Author: Phil Gosch
Date: Mon Jul 18 17:28:13 2016 +0200
Branches: soc-2016-uv_tools
https://developer.blender.org/rB97c2b665ad13efdc31cd24c5639f76385316d1a8
WIP: Simulated Annealing
Basics of the simulated annealing approach to iteratively find the optimal packing solution
===================================================================
M source/blender/editors/uvedit/uvedit_parametrizer.c
M source/blender/editors/uvedit/uvedit_parametrizer.h
M source/blender/editors/uvedit/uvedit_unwrap_ops.c
===================================================================
diff --git a/source/blender/editors/uvedit/uvedit_parametrizer.c b/source/blender/editors/uvedit/uvedit_parametrizer.c
index c03580d..e64c292 100644
--- a/source/blender/editors/uvedit/uvedit_parametrizer.c
+++ b/source/blender/editors/uvedit/uvedit_parametrizer.c
@@ -5304,7 +5304,8 @@ bool p_chart_pack_individual(PHandle *phandle, PChart *item)
}
MEM_freeN(nfps);
printf("-freeing stuff done!\n");
- /* p_flush_uvs(phandle, item); */ /* ToDo SaphireS: Needs update to work ... */
+ p_flush_uvs(phandle, item); /* ToDo SaphireS: Needs update to work ... */
+
return found;
}
@@ -5386,6 +5387,12 @@ bool p_compute_packing_solution(PHandle *phandle /* ToDo SaphireS: Simulated Ann
}
}
+ /* Un-set placed property of charts so next iteration works as expected */
+ for (i = 0; i < phandle->ncharts; i++) {
+ chart = phandle->charts[i];
+ chart->u.ipack.convex_hull->placed = false;
+ }
+
return true;
}
@@ -5414,6 +5421,9 @@ void param_irregular_pack_begin(ParamHandle *handle)
p_face_backup_uvs(f);
}
+ /* Set initial scale of charts */
+ /* ToDo SaphireS: Idea: set initial scale so that combined chart area is about 1.0 of UV area */
+
/* Compute convex hull for each chart -> CW */
chart->u.ipack.convex_hull = p_convex_hull_new(chart);
@@ -5439,24 +5449,22 @@ void param_irregular_pack_begin(ParamHandle *handle)
}
-void param_irregular_pack_iter(ParamHandle *handle, float *w_area)
+void param_irregular_pack_iter(ParamHandle *handle, float *w_area, unsigned int seed)
{
PHandle *phandle = (PHandle *)handle;
- param_assert(phandle->state == PHANDLE_STATE_PACK);
-
- /* ToDo (SaphireS): packing solution computation */
+ BLI_rng_seed(phandle->rng, seed);
- /* Compute inner fit polygon */
+ param_assert(phandle->state == PHANDLE_STATE_PACK);
- /* For every chart: */
+ /* Set initial scale of charts so finding a better solution is possible */
- /* Compute no-fit polygon for current chart against all placed charts so far */
- /* This includes a decomposition of non-convex shapes into convex ones */
- /* Compute collision-free area for current chart */
+ /* ToDo (SaphireS): packing solution computation */
- /* Place chart according to parameters from simulated annealing algorithm */
+ if (p_compute_packing_solution(phandle)) {
+ printf("packing solution found---------------------------------------------\n");
+ }
float used_area = p_face_uv_area_combined(handle);
diff --git a/source/blender/editors/uvedit/uvedit_parametrizer.h b/source/blender/editors/uvedit/uvedit_parametrizer.h
index 1460b22..3698c52 100644
--- a/source/blender/editors/uvedit/uvedit_parametrizer.h
+++ b/source/blender/editors/uvedit/uvedit_parametrizer.h
@@ -105,7 +105,7 @@ void param_pack(ParamHandle *handle, float margin, bool do_rotate);
/* Packing 2.0 */
void param_irregular_pack_begin(ParamHandle *handle);
-void param_irregular_pack_iter(ParamHandle *handle, float *w_area);
+void param_irregular_pack_iter(ParamHandle *handle, float *w_area, int seed);
void param_irregular_pack_end(ParamHandle *handle);
/* Average area for all charts */
diff --git a/source/blender/editors/uvedit/uvedit_unwrap_ops.c b/source/blender/editors/uvedit/uvedit_unwrap_ops.c
index 9f9cf7a..deeaca1 100644
--- a/source/blender/editors/uvedit/uvedit_unwrap_ops.c
+++ b/source/blender/editors/uvedit/uvedit_unwrap_ops.c
@@ -46,6 +46,7 @@
#include "BLI_utildefines.h"
#include "BLI_alloca.h"
#include "BLI_math.h"
+#include "BLI_rand.h"
#include "BLI_uvproject.h"
#include "BLI_string.h"
@@ -828,6 +829,15 @@ void UV_OT_pack_islands(wmOperatorType *ot)
/* ******************** Pack Islands operator 2.0 **************** */
+typedef struct SimulatedAnnealing {
+ RNG *rng;
+ int seed;
+ float theta;
+ float f;
+ float r;
+ float temperature;
+} SimulatedAnnealing;
+
typedef struct PackIslands {
Scene *scene;
Object *obedit;
@@ -837,6 +847,7 @@ typedef struct PackIslands {
int i, iterations;
wmTimer *timer;
float wasted_area_last;
+ SimulatedAnnealing *sa;
} PackIslands;
static bool irregular_pack_islands_init(bContext *C, wmOperator *op)
@@ -845,6 +856,8 @@ static bool irregular_pack_islands_init(bContext *C, wmOperator *op)
Object *obedit = CTX_data_edit_object(C);
BMEditMesh *em = BKE_editmesh_from_object(obedit);
PackIslands *pi;
+ SimulatedAnnealing *simann;
+ unsigned int seed = 31415926;
/* Keep for now, needed when making packing work with current selection */
/*if (!uvedit_have_selection(scene, em, implicit)) {
@@ -862,6 +875,15 @@ static bool irregular_pack_islands_init(bContext *C, wmOperator *op)
pi->handle = construct_param_handle(scene, obedit, em->bm, hparams);
pi->lasttime = PIL_check_seconds_timer();
+ simann = MEM_callocN(sizeof(SimulatedAnnealing), "SimulatedAnnealing");
+ simann->rng = BLI_rng_new(seed);
+ simann->seed = seed;
+ simann->theta = 0.0f;
+ simann->f = 0.0f;
+ simann->r = 0.0f;
+ simann->temperature = 1.0f;
+ pi->sa = simann;
+
param_irregular_pack_begin(pi->handle);
op->customdata = pi;
@@ -873,17 +895,38 @@ static void irregular_pack_islands_iteration(bContext *C, wmOperator *op, bool i
{
PackIslands *pi = op->customdata;
ScrArea *sa = CTX_wm_area(C);
- float wasted_area = 0.0f;
-
- param_irregular_pack_iter(pi->handle, &wasted_area);
+ float wasted_area = 0.0f, dE, r1, r2;
+ float a = 0.95f; /*ToDo SaphireS: Make operator parameter for testing */
+ float k = 5.670367e-8f; /* Stefan-Boltzman constant-like parameter */
+
+ pi->i++;
+ /* Cooling Schedule */
+ pi->sa->temperature = pi->wasted_area_last * a;
- /* ToDo (SaphireS): simulated annealing, based on wasted areas ("temperature") of last and current solution */
+ /* Find neigbohring solution */
+ /*ToDo Saphires: Pass SA parameters */
+ param_irregular_pack_iter(pi->handle, &wasted_area, pi->i);
+ /* delta Energy */
+ dE = wasted_area - pi->wasted_area_last;
+ if (dE < 0) {
+ /* Current solution is new best solution */
+ /* ToDo SaphireS: Store last best solution */
+ pi->wasted_area_last = wasted_area;
+ }
+ else {
+ r1 = BLI_rng_get_float(pi->sa->rng);
- pi->wasted_area_last = wasted_area;
+ r2 = (float)exp(-dE/(k * pi->sa->temperature));
- pi->i++;
+ if (r1 < r2) {
+ /* Current solution is new best solution */
+ /* ToDo SaphireS: Store last best solution */
+ pi->wasted_area_last = wasted_area;
+ }
+ }
+
RNA_int_set(op->ptr, "iterations", pi->i);
if (interactive && (PIL_check_seconds_timer() - pi->lasttime > 0.5)) {
@@ -922,6 +965,9 @@ static void irregular_pack_islands_exit(bContext *C, wmOperator *op, bool cancel
param_irregular_pack_end(pi->handle);
param_delete(pi->handle);
+ BLI_rng_free(pi->sa->rng);
+ MEM_freeN(pi->sa);
+
DAG_id_tag_update(pi->obedit->data, 0);
WM_event_add_notifier(C, NC_GEOM | ND_DATA, pi->obedit->data);
More information about the Bf-blender-cvs
mailing list