VisDiff: SDF-Guided Polygon Generation for Visibility Reconstruction and Recognition
Polygon Reconstruction;Visibility Reconstruction;Triangulation Dual;Geometric Reasoning;Generative Models
Yes
No ethics review needed.
You have the diffusion model generate the SDF and then the prediction model re-encode the SDF to generate the vertices. It would be interesting to see how much of the performance is due to the diffusion, and how much is re-aligned by the prediction module. In other words, how good are the SDFs before the prediction module?

EDIT: I was thinking how to measure this, as it always hard with generative models where you do not have a ground truth. One way to al least understand whether the generated SDF fits the final shape is to compare the generated SDF with the actual SDF of the shape generated by the prediction module. This will not tell us how good the SDF was, but at least will gives us an idea of how much leeway the prediction module has.
Good performance with respect to the baselines on the generated dataset
The paper presents a diffusion model for 2D polygonal shapes represented in terms of their visibility graph (a skeleton-like structure obtained by taking the dual of a triangulation of the shape)
The diffusion model generates the signed-distance-function (SDF) of the polygonal shape constrained by the structure of the visibility graph, then the actual vertices of the polygon (at the zero level set of the SDF) are extracted by a second module, where an encoder with Spatial Transformer Cross Attention encodes the SDF into a latent space, and then several MLPs decode the vertices.
1) the problem is a bit contrived, in the sense that the way it is evaluated the focus is not in shape analysis, but on extracting something from the chosen skeletal representation. This results in no analysis on the underlying problem, thus not using any of the several datasets that have been used by the community for several years, and comparisons to approaches that can only be described as baselines for the problem actually analyzed. This severely limits the readership of this paper.

Further, I had to read the papers several times because key elements (such as the visibility graph)  do not have proper definitions, but are defined inline in the text.
Yes
No ethics review needed.
See Weaknesses.
To my understanding, this is the first paper to design a deep model specifically for generating polygons from visibility graphs.
The visibility graph of a planar polygon is the graph whose vertices are those of the polygon and two vertices are linked with an edge iff the line segment connecting them lies inside the polygon. The paper presents a deep model to generate polygons from a visibility graph. This model is then used to sample polygons approximately consistent with a given visibility graph. As a side result, this is also applied to deciding whether a given graph is a (valid) visibility graph of some polygon.

The main block of the model is diffusion, based on U-Net. The output of the diffusion is a signed distance function (represented as a matrix) from the polygon boundary. The SDF is finally regressed to a set of polygon vertices.

The dataset for training and testing consists of polygons each with 25 vertices, First, 60k polygons are  randomly generated by an existing heuristic. Then they are augmented by shear and small vertex perturbations to obtain 400k polygons of random. This dataset defines an empirical distribution both on visibility graphs and on polygons consistent with a given vis. graph. For testing, other out-of-distribution polygons are generated, based on 5 base shapes.

The model is compared to several known deep models suitable for the  task (such as transformers or GNN) and a direct approach based on optimiation (Nelder-Mead amoeba algorithm). The model is reported to perform best in all criteria, except sometimes accuracy.
Novelty:

First, I am not sure about novelty. On one hand, this paper seems to be the first to propose a deep generative model for generating polygons from vis. graphs (I think so because no such paper is cited). Though there has been a lot of theoretical results and algorithms on visibility graphs of polygons, these are not deep models.

On the other hand, I am not sure if this alone should guarantee acceptance. The proposed model is composed of well-known blocks and does not bring any really novel ideas - perhaps except using SDF as an intermediate representation of polygons. Moreover, the practical utility of the task is questionable. There are many very different polygons consistent with a single vis. graph and vis. graph is unstable to small polygon perturbations. Indeed, look at Figure 5: the polygons sampled from the vis. graph are all very dissimilar to the GT polygon. I believe that  for the tasks like representing a hand (mentioned in the intro), representation that includes also metric info would be better. I do not see many applications benefiting from such a model.

Experiments:

As no deep models specifically tailored for the task have been published before, all competing models in the experimental comparison seem to be coded by the authors themselves, using known general deep learning models and no details on these models are given (code is promised but not yet available). This is not seen from the text (sorry if I overlooked something) until you look at the references cited with the models. This may introduce positive bias towards the published model, since the authors may have given more care to implementing this model rather than the other methods. E.g, it is mentioned on line 452 that in visibility reconstruction, 50 polygons are sampled from the vis. graph and the best of them is picked. Is this done also in the competing methods?

The polygons in the dataset are all of the same "type", obtained by a single heuristic. It would be more informative to have a richer distribution of polygons.

In visibility recognition (Section 6.5), my understanding is that the way how "non-valid" vis. graphs are generated may sometimes produce valid ones. At least, I do not see why the vis. graph generated using a polygon with a hole should be invalid, because there can be some polygon consitent with it. Please exaplain.

Clarity:

The technical parts of the paper are sometimes unclear and imprecise. The worst is Section 4 on designing the loss function (a key section of the paper): the part on the visibility term is unreadable. Examples:

Line 189, "the dimensionality of the input 25-by-25 matrix is reduced to 512": Since 25*25 = 525, is this worth it? Moreover, one can use only a half of the vis. graph adjacency matrix, since it is symmetric.

Paragraph starting at line 275: I do not see how the visibility loss term is computed, too little detail is given. Moreover, math formulas in this par is inacceptably informal. One cannot write things like max(L_int), because what is L_int? Softmax on the rhs of (6) has not been defined. In (7), i\neq j should be in the sedond sum, P_i was not defined.

Line 282: What function precisely is differentiable?

Eq. (3): one cannot write this, you need a norm instead of just the parentheses (and what is X, exactly?).

Line 515: There is no such thing as concave polygon (or concave set), correct word is "non-convex".
Yes
No ethics review needed.
1. Can we use Unsigned Distance Field (UDF) instead of SDF, so that we can cover wider range of polygons (e.g. polygons with holes)?

2. Can we extend this approach to 3D? If we can, it would be really cool. I assume there would be much more difficulty in vertex selection & connecting them to get valid watertight mesh.

3. On line 236, it says that "the generated SDF embedding is then passed through multiple MLP layers to predict the **ordered** vertex locations". I think there are multiple (valid) ordered vertex locations for the same polygon, right? For instance, vertex ordering of (1-2-3-4) would be same as (2-3-4-1). How did yout resolve such ambiguity? Didn't it raise any problem during training?

4. How does the performance change when we increase the number of points?

* minor typo

Line 496: "...threshold X, it is ..."
1. The paper was easy to follow, as the target problems were explained clearly.

2. The approach seems to be novel. It cleverly applied generative model for solving this kind of geometric / topological problem. However, I could be wrong as I'm not an expert about this topic.

3. The results clearly show that this approach is better than the other baselines.
This paper presents a way to infer polygonal information from given combinatorial structure, such as visibility graph or triangulation. To do this, this paper proposes to use a diffusion model. The model takes in a visibility graph as an input, and first generates a SDF, from which they select vertex locations, which satisfy the given visibility graph. To train this model, this paper proposes a loss function for comparing the output polygon's visibility graph with the given one in a differentiable manner. The loss formulation is based on geometric algorithms, such as line-line intersection. One another contribution is in using cancavity-aware dataset for training. By using this approach, it achieves much better performance in reconstructing valid polygons from visibility graphs than the other baseline methods. Also, as this approach can sample multiple polygons from different seeds, it can be used for visibility characterization. Finally, it could give a hint about solving recognition problem.
1. There is no comparison with the baselines for the out of distribution data (Table 2), which makes it hard to see if this approach is better than the baselines for such data.

2. As far as I know, the diffusion denoisinig process takes some computational cost, and this paper says that it generated 50 polygons from the given visibility graph and chose the best one among them, which might have led to longer computation time than the other baseline methods. It would be better to have analysis about computational cost.

3. Generally, the figure quality is not very good. It would be better to use figures of better rendering quality. Also, I believe Figure 2 can be further improved (it is too abstract).
Yes
No ethics review needed.
(Q1) Is there a reason why characterization is not mentioned in the title too? You make such a nice distinction between reconstruction, characterization and recognition (see S1 above), but you only mention two of them in the title, whereas your experiments consider all three problems? Similar formulations come back at other moments in the paper too, e.g., first sentence in the Conclusion.

(Q2) How did you get the graph in Figure 1 right with Isomap, i.e., how did you decide which vertices are connected with an edge? Also, what do the different colors of the vertices represent? Related to (Q1), could this figure also include the visibility graph of P? Note also that you use notation G for three different things in the three plots of this figure, this should be made more precise? Instead of "Object", should you not use "P"?

(Q3) Do you truly address the problem of polygon characterization?  On line 111, you seem to imply that this is indeed the case, "we can sample *the* set of polygons which have a given visibility graph". However, in Section 6.4 on visibility characterization, you write "We generate multiple polygons given the same visibility graph G by drawing different samples from Gaussian distribution for diffusion initialization." Are you in this way generating *some/many*, or *all* polygons with the desired property? This needs to be made very precise.

(Q4) Is the Related work not missing the optimization (integer programming and heuristic) approaches? More importantly, and related to (W1) above, if the main contributions of the paper lie in the novel loss function and data set, please include these in your discussion. What types of loss functions have been used in the literature, have any comparisons been done so far? What other data sets are used, are there benchmarks, what are some their properties?

(Q5) Can you motivate your choices for the VisDiff architecture, e.g, why do you opt for U-Net or Spatial Transformer Cross Attention? Can Figure 2 explicitly label the three main modules, i.e., also the graph encoding / U-Net and SDF (and possibly also DDIM)? Should the caption, or at least the main text, not explain what X_T, X_9, K, Q, V are? As it is, the figure is not helping me understand the architecture. 

(Q6) Why is your approach not compared against other methods also for the out-of-distribution data (Table 2)?

(Q7) What kind of loss function is typically used in the literature, is it only L_MSE, see related (Q4) above? This will help to clarify wherein lies the novelty of your approach, i.e., if you are the first to introduce L_validity, L_visibility and L_SDF, or is it in the differentiability i.e. approximating max with softmaximum. In the former case, the ablation study needs to assess the added value of each of the components. Moreover, you consider the same weight for each of the four components in the loss function, but if this is the main contribution of the paper, would it not be particularly interesting to consider different weight schemes?


Minor comments:
- For better readability, the order in which different notions are listed throughout the paper can be improved. For example, a more logical order in the first sentence of Figure 2 caption would be graph encoder (U-Net), denoising U-Net and vertex prediction. As another example, consider the order of models in Table 1 and Figure 5 (for better clarity, it would also be better if the model acronyms were included in the figure itself). Also, the order of plots in Figure 9 is opposite from Figure 8.
- line 188: At this moment, the reader is not yet familiar with the data set, i.e., with the fact that polygons have 25 vertices, so this should at least briefly be mentioned in brackets.
- line 228: image.Furthemore -> image. Furthermore
- There are some issues with numbering or formatting of the section titles. The section and subsection titles are mostly capitalized, but then this is not the case for Section 6.3, 6.4, 6.5 - are these maybe supposed to be subsections 6.2.1, 6.2.2 and 6.2.3? 
- Explain in Figure 5 caption why the F1 scores do not match the F1 scores from Table 1.
- line 496: X. It -> X, it
- line 539: more efficient representations such as (Park et al, Mitchell et al). Can you describe in a few words what these representations are, or what the main idea/ingredient is?
- Check formatting in the references, e.g., capitalization of journals, Polydiff, 3d, Sd, 3dgen, Deepsdf, delaunay ...
(S1) I really like the Introduction paragraph on lines 075-100 that very nicely describes the main goal and problems studied in the paper.

(S2) I also appreciate that you generated the in- and out-of-distribution polygons that bear some significant differences, and that the test data your experiments considers both cases.
This paper introduces a diffusion-based approach for polygon reconstruction, characterization and recognition, which is guided by signed distance function (SDF). The main contributions lie in a novel differentiable loss function and data set with variable link diameter.
(W1) Strength of contributions: At some moments in the manuscript, it seems that the authors imply that (at least some of) the novelty of the paper is related to diffusion and SDF. For instance:

- Abstract: "We introduce VisDiff, a novel diffusion-based approach ..."
- Abstract: "Our main insight is that going through the SDF significantly improves learning..."
- Introduction: "Our main insight is that going through the SDF as an intermediate representation yields superior results over using established methods to predict the vertex locations directly"
- Section 3 (when motivating the use of diffusion models): "Diffusion model have shown the ability to efficiently learn the space of all images" (without a reference), which seems to imply that their use in the context of polygon reconstruction is novel. 

However, when looking at the list of references included in the paper, I see that the diffusion models have already been used in this context, and that seemingly more complicated settings such as pseudo-polygons, polygons with holes have been studied (whereas this paper focuses on the very basic setting of simply-connected polygons with boundary that does not self intersect). Moreover, a quick Google Scholar search makes it clear that both diffusion and SDF have been used in this area of research. 

On the other hand, at different moments in the paper, the authors state that the main contributions lie in the novel loss function and a carefully designed data set of polygons. If this is the case, then the Related work section needs to focus or at least discuss these aspects as well, and the experiments need to evaluate their added value better, see see (Q4), (W2) and the related (Q7) below. What I then find confusing is that these two aspects are never mentioned in the Conclusion either, whereas the diffusion and SDF are discussed.

Finally, in the Conclusions, the authors write: "Overall, our results provide evidence that recent architectures can learn representations of non-trivial combinatorial structures as polygons", but I assume that this has been done before too? Also, such a formulation implies that this is your main contribution?

Overall, the above shows that some parts of the paper need to be rewritten to make it much clearer where the main contributions lie, what has been done before and in what way.

(W2) Quality of experiments: The paper has no theoretical results, and the experiments are not extensive enough. If the main contribution is the novel loss function, a more extensive ablation study is needed, that evaluates the added value of each of the components (whereas at the moment, you only consider the visibility loss), see (Q7). If the other main contribution is the data set, I wonder to what extent is it interesting to consider only polygons with 25 vertices? Would a more diverse data set with different number of vertices not make it possible to better differentiate the power of different models? Also, I find it rather striking that the other baseline state-of-the-art methods perform so poorly (e.g., in Figure 5), which makes me wonder if the data set you curate is not in some way specifically tailored to the proposed method. Would it not be fair to compare the performance of your and the baseline methods also on other data sets that are studied in those other papers? A quick look makes me think that these other baselines are developed to tackle completely different tasks, it is not then fair to claim that these are state-of-the-art methods for polygon reconstruction (that you outperform)? Why not compare with some other polgyon reconstruction approaches, and also using other existing data?
Yes
No ethics review needed.
NA
* Applying ML methods to significantly improve state-of-the-art on a hard problem such as polygon generation is important.
* The paper is extremely well-written and I was able to appreciate the various intricate issues that arise in solving this problem
This paper considers the following problem: Given a combinatorial structure such as a graph representing either the visibility graph or a triangulation, construct a polygon whose visibility graph/triangulation is this input graph G. Note that the coordinates of vertices are not provided in the input. This is the problem of visibility reconstruction. The problem is known to be incredibly hard and lies somewhere between NP and PSPACE. 

The key contribution of this paper is to introduce a diffusion based method to reconstruct a polygon from its visibility graph. There are two main contribution of this paper. First, instead of generating the polygon directly, they first generate the signed distance function using which they then extract the vertex locations. The second contribution is in the training process where the authors design a novel loss function as well as create a curated data set. Combined together, they produce (both quantitatively and qualitatively) better results for this problem.
I did not find any major weakness. 

My confidence in evaluation is lower only because I’ve not explicitly worked in this space and may not be aware of all the existing work.
Yes
No ethics review needed.
Refer to the weakness section for questions.
1. The research problem addressed in this paper is of significant importance
2. The organization of the content is clear and logical, facilitating an easy understanding of the complex concepts presented.
This paper learns latent representations for combinatorial structures focusing on polygons. It introduces "VisDiff," a diffusion-based model for reconstructing polygons from their visibility graphs. This process involves estimating the signed distance function (SDF) of a polygon from its visibility graph and extracting vertex locations in an ordered sequence that maintains the visibility relationships indicated by the graph's edges. This approach is enhanced by the integration of loss functions that enable the computation of visibility in a differentiable manner, alongside the creation of a specialized dataset for training.
1.1 The presentation of the paper could be improved for clarity and flow. In particular, the concept of "dual" introduced in line 51 is unclear. It would be helpful if the authors could explain whether this "dual" has a one-to-one correspondence with polygons, how it is derived, and its relationship to the polygons discussed. 

1.2. The definition of the graph G also lacks clarity. Figure 1 seems to depict three different types of graphs labeled as "G", which is confusing. Could the authors specify what each graph represents? And in line 76 authors mentioned “G can be visibility graph or triangulation dual of the polygon”.  Are the visibility graph and the triangulation dual equivalent? how they are related?

2. The motivation behind the paper is currently not compelling. The introduction lists problems that appear purely mathematical with unclear real-world applications. The reasoning behind the inclusion of 'dual' and the visibility graph remains unclear.
3. Some relevant works are not discussed. For instance, [1] proposes modeling polygons using visibility graphs and a graph neural network for learning representations. 
4. The experimental section raises concerns about reproducibility and the selection methodology. In line 375, the authors mention that the visibility graph is not unique for a given polygon. It is crucial to explain how the experimental process was standardized to ensure reproducibility. Moreover, considering the paper's objective to reproduce polygons, why not evaluate the effectiveness directly from the polygons instead of using a proxy? The high F1 score reported in Figure 6 does not seem to correspond well with the visual similarity of the generated polygons to the ground truth.

5.1 Technical details need clarification. For example, in line 188, the reasoning behind the choice of a 25*25, 512 configuration should be explained. What is the size of x and the noise in line 198? 

5.2. The introduction of a "differentiable" max operation is intriguing. Since max is commonly used in machine learning and supported by frameworks like PyTorch, what specific advantages does your design offer?

[1] PolygonGNN: Representation Learning for Polygonal Geometries with Heterogeneous Visibility Graph. KDD '24: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
Pages 4012 - 4022 https://doi.org/10.1145/3637528.3671738
Representation learning for polygons and visibility
@inproceedings{
anonymous2024visdiff,
title={VisDiff: {SDF}-Guided Polygon Generation for Visibility Reconstruction and Recognition},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=rn8r7GqJm6},
note={under review}
}
The capability to learn latent representations plays a key role in the effectiveness
of recent machine learning methods. An active frontier in representation learning
is understanding representations for combinatorial structures which may not
admit well-behaved local neighborhoods or distance functions. For example, for
polygons, slightly perturbing vertex locations might lead to significant changes in
their combinatorial structure (expressed as their triangulation or visibility graph)
and may even lead to invalid polygons. In this paper, we investigate representations
to capture the underlying combinatorial structures of polygons. Specifically,
we study the open problem of Visibility Reconstruction: Given a visibility graph
G, construct a polygon P whose visibility graph is G. Visibility Reconstruction
belongs to the Existential Theory of Reals (∃R) complexity class (which lies between
NP and P-SPACE). Currently, reconstruction algorithms are available only
for specific polygon classes. Establishing the hardness of the general problem is
open.


We introduce VisDiff, a novel diffusion-based approach to reconstruct a polygon
from its given visibility graph G. Our method first estimates the signed distance
function (SDF) of P from G. Afterwards, it extracts ordered vertex locations
that have the pairwise visibility relationship given by the edges of G. Our main
insight is that going through the SDF significantly improves learning for reconstruction.
In order to train VisDiff, we make two main contributions: (1) We
design novel loss components for computing the visibility in a differentiable manner
and (2) create a carefully curated dataset. We use this dataset to benchmark
our method and achieve 21% improvement in F1-Score over standard methods.
We also demonstrate effective generalization to out-of-distribution polygon types
and show that learning a generative model allows us to sample the set of polygons
with a given visibility graph. Finally, we extend our method to the related
combinatorial problem of reconstruction from a triangulation. We achieve 95%
classification accuracy of triangulation edges and a 4% improvement in Chamfer
distance compared to current architectures. Lastly, we provide preliminary results
on the harder visibility graph recognition problem in which the input G is not
guaranteed to be a visibility graph.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Polygon Reconstruction Visibility Reconstruction Triangulation Dual Geometric Reasoning Generative Models
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/8352b2c5e67cd65aae11be4fca77e4942815be61.pdf
learning on graphs and other geometries & topologies
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
VisDiff: SDF-Guided Polygon Generation for Visibility Reconstruction and Recognition
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission