💻 computer science

Rendering Separoid Information: Rate-Distortion Reconstruction of Convex Apartness Scenes

This paper frames the rendering of convex scenes as a rate-distortion problem where the goal is to optimize the geometric encoding of a scene to maximize the recoverability of its discrete relational "apartness" structure from noisy visual data, rather than merely achieving pixel-level fidelity.

Original authors: Faruk Alpay, Baris Basaran

Published 2026-06-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Faruk Alpay, Baris Basaran

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: Drawing to Tell a Story, Not Just to Look Pretty

Imagine you are trying to explain a complex situation to a friend over a text message. You have two choices:

Send a high-definition photo of the scene (lots of data, but maybe the friend misses the point).
Send a simple sketch with arrows and labels that says, "These two groups are far apart, but these three are touching."

This paper argues that for many diagrams (like maps, molecular models, or mechanism drawings), the second option is actually the goal. The "message" isn't the pretty colors or the exact shape of the objects; the message is the logical relationship between them: Who is separated from whom? Who is overlapping?

The authors call this relationship the "Apartness Table." It's a list of yes/no answers to questions like, "Can I draw a straight line between Group A and Group B without hitting anything?"

The Problem: The "Noisy Channel"

Usually, when we render a 3D scene into a 2D image (like on a computer screen), we try to make it look realistic. But if the image is blurry, pixelated, or has bad lighting, a human (or a computer) might misread the relationships. They might think two groups are touching when they are actually apart.

The authors ask: How can we design a scene so that even if the image is messy or low-resolution, the "logical story" (the apartness) still comes through clearly?

The Solution: A "Certificate" System

Instead of trying to preserve every single pixel, the authors treat the scene like a code.

The Skeleton (The Certificates):
Imagine you have a jigsaw puzzle. You don't need to show every single piece to prove the picture is complete; you just need to show the "corner pieces" and the "edge pieces" that lock everything together.
In this paper, the "skeleton" consists of two types of critical proofs:
- Maximal Separations: The strongest proof that two groups are apart.
- Minimal Crossings: The smallest proof that two groups are touching.
The paper proves a cool mathematical fact: If you get these "skeleton" pieces right, the rest of the logical story (the whole table) falls into place automatically. You don't need to optimize the whole table; just the skeleton.
The Rate-Distortion Trade-off:
Think of this like packing a suitcase.
- Rate: How much "space" (or geometric complexity) you use to describe the scene.
- Distortion: How much the meaning gets messed up.
Traditional rendering tries to minimize "pixel error" (making the image look exactly like the reference). This paper tries to minimize "meaning error." It asks: What is the simplest, smallest shape I can draw that still guarantees the viewer knows Group A is separated from Group B?

If you make the gap between two groups huge, it's easy to see they are apart, even if the image is blurry. If the gap is tiny, a little bit of noise might make them look like they are touching. The authors' method automatically widens those gaps just enough to be safe, without wasting space on unnecessary details.

The Experiments: What They Found

The team tested this on flat, 2D shapes (like polygons on a piece of paper). Here is what happened:

Recovering the Story: They took the "Apartness Table" (the list of who is apart from whom) and tried to build a scene from it. Even though they only optimized the "skeleton" (the critical proofs), the resulting scene was 99.9% accurate in preserving the relationships. It was like rebuilding a house just by knowing where the load-bearing walls were; the rest of the house fell into place correctly.
The "Fidelity" Test: They compared their method to standard rendering. Standard rendering cares if a pixel is the wrong color. Their method cares if the logic is wrong. They found that standard rendering often fails at low resolutions because it misses the "important" logical bits. Their method prioritizes the "high-consequence" bits (the big separations) so the story remains clear even when the image is small or noisy.
The Best Angle: They also figured out the best way to take a picture of these scenes. Just like taking a photo of a sculpture, some angles show the separation clearly, while others hide it. They found that by rotating the scene slightly to a "smart angle," you can prove almost all the separations from a single view. It's like finding the one angle of a knot that clearly shows the two ends are tied together.

The Takeaway

This paper proposes a new way to think about computer graphics. Instead of asking, "Does this image look photorealistic?" we should ask, "Does this image successfully transmit the logical truth about how objects relate to each other?"

By treating the scene as a code that carries a specific "payload" of relationships, and by optimizing the geometry to protect that payload against noise and low resolution, they created a system that is much more efficient at communicating the meaning of a diagram than traditional rendering methods.

Technical Summary: Rate–Distortion Reconstruction of Convex Apartness Scenes

Problem Statement
Traditional rendering evaluation focuses on pixel-level fidelity to a reference appearance. However, many visualizations (e.g., mechanism diagrams, molecular cartoons, scene graphs) primarily communicate relational facts: which groups of objects are mutually apart and which cross. The paper posits that for such scenes, the geometry is merely a carrier for a discrete, logical payload—the pattern of separations and crossings. The core problem is to formalize rendering not as image reproduction, but as the transmission of this "apartness" structure through a noisy visual channel. The goal is to minimize the geometric description length (rate) required to faithfully transmit the separation structure (distortion), rather than minimizing pixel error.

Methodology
The authors frame the problem as a rate–distortion optimization where the apartness table is the source, the convex scene is the encoder, and the rendered image is the channel.

Source Representation (The Separoid):
- The scene consists of a finite family of convex bodies. The "apartness table" $\Sigma$ is a binary matrix indicating whether the convex hulls of any two disjoint groups of bodies are disjoint ( $\sigma_{A,B}=1$ ) or intersecting ( $\sigma_{A,B}=0$ ).
- The authors identify that the full table is redundant. It is fully determined by a certificate skeleton consisting of:
  - Maximal Separations: Pairs of groups that are separated but cannot be extended by adding more bodies without intersecting.
  - Minimal Radon Partitions: Pairs of groups that intersect, but become separated if any single body is removed from either group.
- Proposition 1 proves that this skeleton is a sufficient statistic for the entire table, reducing the source entropy from $O(3^n)$ to $O(n \log n)$ .
Differentiable Channel and Objective:
- Encoder: A scene $V$ is defined by vertices of convex polygons. The encoder optimizes these vertices to realize the source structure.
- Renderer: A soft support-function rasterizer maps the scene to an image $Y$ , introducing noise, occlusion, and finite resolution.
- Decoder: An object-centric decoder estimates the apartness bits from the image moments.
- Distortion ( $d_{sep}$ ): Instead of Hamming error, the authors define a closure-aware distortion. It weights errors based on logical consequence: a wrong maximal separation falsifies all sub-separations, and a wrong minimal Radon partition falsifies all super-crossings. The loss is the sum of these weighted errors.
- Rate ( $R(V)$ ): A differentiable geometric code length comprising quantized coordinate costs and boundary curvature entropy (favoring smooth, compact shapes).
- Robustness: The objective includes a term to widen the "witnessing cone" of separating directions, ensuring separations are visible from a broader range of viewpoints.
Information-Theoretic Metrics:
- The paper utilizes a variational lower bound on the mutual information $I(\Sigma; Y)$ to measure how many bits of apartness the rendered image conveys.
- Viewpoint selection is treated as a submodular maximization problem to find views that certify the maximum number of separations with minimal redundancy.

Key Contributions

Formalization of Rendering as a Channel: The paper casts apartness-preserving rendering as a rate–distortion problem where the fidelity criterion is the transmission of logical certificates (maximal separations and minimal Radon partitions) rather than pixel accuracy.
Certificate-Aware Distortion: It introduces a distortion metric that accounts for the logical consequences of errors. A single error in a high-consequence certificate is penalized more heavily than errors in redundant bits, reflecting the structural nature of the data.
Differentiable Pipeline: The authors provide a fully differentiable realization using support functions, allowing end-to-end optimization of the scene geometry to maximize the mutual information between the source structure and the rendered image.
Information-Optimal View Selection: They derive a criterion for selecting viewpoints that maximize the certification of separations, demonstrating that a greedy selection strategy effectively covers the separation structure.

Experimental Results
Experiments were conducted on planar convex scenes with 5 to 7 bodies:

Recovery from Skeleton: Scenes optimized using only the certificate skeleton (which is significantly smaller than the full table) recovered the full apartness table with 99.9% bit accuracy, confirming the sufficiency of the skeleton.
Rate–Distortion Frontier: A clear operational frontier emerged between geometric rate and certificate distortion. The consequence-weighted distortion was found to be a stricter and more meaningful metric than plain Hamming error, as low-rate rendering preferentially damages high-consequence structural bits.
Channel Capacity: A rendered $48 \times 48$ image delivered 0.72 of the apartness-graph entropy. The information score scaled with resolution and collapsed with noise, behaving like a capacity-limited channel.
Viewpoint Robustness: A single optimal view certified approximately 58.7% of separations. Increasing the robustness weight in the objective function widened the witnessing cones of separations, making them readable from a wider cone of viewpoints with only a modest increase in geometric rate.

Significance and Claims
The paper claims to establish a new framework for evaluating and optimizing rendering where the "message" is the relational structure of the scene. By treating the apartness table as a source and the image as a channel, the work shifts the objective from visual fidelity to informational fidelity.

The authors assert that this approach reveals that:

The "skeleton" of separations is the true payload of a convex scene.
Standard pixel-based metrics fail to capture the degradation of logical structure at low bitrates.
Viewpoint selection can be rigorously optimized using information-theoretic principles to maximize the recovery of structural facts.
The trade-off between geometric complexity (rate) and structural robustness (viewpoint invariance) can be explicitly controlled.

The work is presented as a foundational step connecting separoid theory, convex geometry, and information theory to create rendering objectives that are "honest about what a picture is supposed to make recoverable." The authors acknowledge limitations, noting that exact table computation is exponential in the number of bodies and that the current experiments are restricted to planar scenes, but they posit the framework is extensible to 3D and learned renderers.