Changeset 3532Tweet

Timestamp:

May 27, 2009, 7:04:48 AM (11 years ago)

Author:

Sam Hocevar

Message:

Another img2twit space optimisation: if we have remaining bits at the end
of the cell allocation, we try to use them to improve the RGB precision as
well as the inner-grid coordinates.

File:

• libpipi/trunk/examples/img2twit.cpp (modified) (4 diffs)

libpipi/trunk/examples/img2twit.cpp

@@ -66 +66 @@
 #define RANGE_H 4000
 
-/* How does the algorithm work: one point per cell, or two */
+/* How does the algorithm work: one point per cell, or two? XXX: changing
+ * this value breaks compatibility with other images. */
 #define POINTS_PER_CELL 2
 
@@ -128 +129 @@
 /* Global triangulation */
 static Delaunay_triangulation dt;
+
+/*
+ * Bit allocation handling
+ */
+
+void compute_ranges(int width, int height)
+{
+    TOTAL_BITS = MAX_MSG_LEN * logf(NUM_CHARACTERS) / logf(2);
+    HEADER_BITS = logf(RANGE_W * RANGE_H) / logf(2);
+    DATA_BITS = TOTAL_BITS - HEADER_BITS;
+#if POINTS_PER_CELL == 1
+    CELL_BITS = logf(RANGE_SYXRGB) / logf(2);
+#else
+    // TODO: implement the following shit
+    //float coord_bits = logf((RANGE_Y * RANGE_X) * (RANGE_Y * RANGE_X + 1) / 2);
+    //float other_bits = logf(RANGE_R * RANGE_G * RANGE_B * RANGE_S);
+    //CELL_BITS = (coord_bits + 2 * other_bits) / logf(2);
+    CELL_BITS = 2 * logf(RANGE_SYXRGB) / logf(2);
+#endif
+    TOTAL_CELLS = (int)(DATA_BITS / CELL_BITS);
+    MAX_ITERATIONS = ITERATIONS_PER_POINT * POINTS_PER_CELL * TOTAL_CELLS;
+
+    /* Compute "best" w/h ratio */
+    dw = 1; dh = TOTAL_CELLS;
+    for(unsigned int i = 1; i <= TOTAL_CELLS; i++)
+    {
+        int j = TOTAL_CELLS / i;
+
+        float r = (float)width / (float)height;
+        float ir = (float)i / (float)j;
+        float dwr = (float)dw / (float)dh;
+
+        if(fabs(logf(r / ir)) < fabs(logf(r / dwr)))
+        {
+            dw = i;
+            dh = TOTAL_CELLS / dw;
+        }
+    }
+    while((dh + 1) * dw <= TOTAL_CELLS) dh++;
+    while(dh * (dw + 1) <= TOTAL_CELLS) dw++;
+}
 
 /*
@@ -445 +487 @@
 static inline void index2cell(int index, int *dx, int *dy)
 {
-    // This check will be used once we add points to our list
-    //if(index < dw * dh * POINTS_PER_CELL)
-    {
-        *dx = (index / POINTS_PER_CELL) % dw;
-        *dy = (index / POINTS_PER_CELL) / dw;
-    }
+    *dx = (index / POINTS_PER_CELL) % dw;
+    *dy = (index / POINTS_PER_CELL) / dw;
 }
 
@@ -1022 +1060 @@
     }
 
-    TOTAL_BITS = MAX_MSG_LEN * logf(NUM_CHARACTERS) / logf(2);
-    HEADER_BITS = logf(RANGE_W * RANGE_H) / logf(2);
-    DATA_BITS = TOTAL_BITS - HEADER_BITS;
-#if POINTS_PER_CELL == 1
-    CELL_BITS = logf(RANGE_SYXRGB) / logf(2);
-#else
-    // TODO: implement the following shit
-    //float coord_bits = logf((RANGE_Y * RANGE_X) * (RANGE_Y * RANGE_X + 1) / 2);
-    //float other_bits = logf(RANGE_R * RANGE_G * RANGE_B * RANGE_S);
-    //CELL_BITS = (coord_bits + 2 * other_bits) / logf(2);
-    CELL_BITS = 2 * logf(RANGE_SYXRGB) / logf(2);
-#endif
-    TOTAL_CELLS = (int)(DATA_BITS / CELL_BITS);
-    MAX_ITERATIONS = ITERATIONS_PER_POINT * POINTS_PER_CELL * TOTAL_CELLS;
-
-    /* Compute "best" w/h ratio */
-    dw = 1; dh = TOTAL_CELLS;
-    for(unsigned int i = 1; i <= TOTAL_CELLS; i++)
-    {
-        int j = TOTAL_CELLS / i;
-
-        float r = (float)width / (float)height;
-        float ir = (float)i / (float)j;
-        float dwr = (float)dw / (float)dh;
-
-        if(fabs(logf(r / ir)) < fabs(logf(r / dwr)))
-        {
-            dw = i;
-            dh = TOTAL_CELLS / dw;
-        }
-    }
-    while((dh + 1) * dw <= TOTAL_CELLS) dh++;
-    while(dh * (dw + 1) <= TOTAL_CELLS) dw++;
+    compute_ranges(width, height);
+
+    /* Try to cram some more information into our points as long as it
+     * does not change the cell distribution. This cannot be too clever,
+     * because we want the computation to depend only on the source image
+     * coordinates. */
+#define TRY(op, revert) \
+    do { \
+        unsigned int olddw = dw, olddh = dh; \
+        op; compute_ranges(width, height); \
+        if(dw != olddw || dh != olddh) \
+            { revert; compute_ranges(width, height); } \
+    } while(0)
+
+    for(int i = 0; i < 5; i++)
+    {
+        TRY(RANGE_G++, RANGE_G--);
+        TRY(RANGE_R++, RANGE_R--);
+        TRY(RANGE_B++, RANGE_B--);
+    }
+
+    for(int i = 0; i < 10; i++)
+    {
+        if((float)width / dw >= (float)height / dh)
+        {
+            TRY(RANGE_X++, RANGE_X--);
+            TRY(RANGE_Y++, RANGE_Y--);
+        }
+        else
+        {
+            TRY(RANGE_Y++, RANGE_Y--);
+            TRY(RANGE_X++, RANGE_X--);
+        }
+    }
 
     /* Print debug information */