Abstract: We present an improved technique for data hiding in polygonal meshes, which is based on the work of Bogomjakov et al. (Comput. Graph. Forum 27(2):637-642, 2008). Like their method, we use an arrangement on primitives relative to a reference ordering to embed a message. But instead of directly interpreting the index of a primitive in the reference ordering as the encoded/decoded bits, our method slightly modifies the mapping so that our modification doubles the chance of encoding an additional bit compared to Bogomjakov et al.'s (Comput. Graph. Forum 27(2):637-642, 2008). We illustrate the inefficiency in the original mapping of Bogomjakov et al. (Comput. Graph. Forum 27(2):637-642, 2008) with an intuitive representation using a binary tree.

Although both methods have the same minimal and maximal capacities and are both only one bit per primitive less than optimal, our method improves the average capacity up to 0.63 bits per primitive. Our embedding and extraction algorithms are just as simple to implement and just as efficient, O(n), as those of Bogomjakov et al. (Comput. Graph. Forum 27(2):637-642, 2008).