Trebol

• input curves

• original mesh (~5k triangles)

• subdivided mesh, 1 iter

• subdivided mesh, 2 iters

• subdivided mesh, 3 iters

Bowl

• input curves

• original mesh (~5k triangles)

• subdivided mesh, 1 iter

• subdivided mesh, 2 iter

Bumpycube

• input curves

• original mesh (~5k triangles)

• subdivided mesh, 1 iter

• subdivided mesh, 2 iter

• subdivided mesh, 3 iter

Gamepad

• input curves

• original mesh (dense, ~100k triangles)

• subdivided mesh, 1 iter

TEST

debugging

Comiso vs. Gurobi

with input

Meeting with ADJM

• parametrization issues: sphere case
  • do the issues occur at cut surfaces?
  • are transition functions applied correctly?
• frame field issues
  • the optimization I’m using right now is not the best solution
  • alternatives: LBFGS optimization, David Palmer’s SDP projection (https://github.com/dpa1mer/arff)

Synthetic generation of oversketched curves

Results on synthetic oversketched input

Latest improvements

Mesh generation

Current pipeline:

1. Uniformly resample input curves.
2. Define a narrow band, i.e. an implicit volume around the curves with a user-specified radius.
3. Using CGAL, compute a tet mesh bounded by the implicit volume.
4. Using TetGen, compute a constrained tet mesh containing the input curves bounded by the surface mesh from Step 3.

Notes:

• Step 3 is necessary since TetGen needs an explicit boundary surface.
• Step 4 is necessary since CGAL cannot compute constrained Delaunay triangulations in 3D.
• Using this pipeline, we make sure that each input edge has a corresponding tet edge. No Steiner points are added on the input edges (nor on the surface mesh).

Examples:

Frame field

I’ve had a problem with projection onto feasible SH coefficients (the curved corner example). I’ve solved it by replacing the project_original method with the project_variant_h, which seems to work better.

project_original (used previously)

project_variant_h (now using)

Parametrization

Snapping constraints are now enforced along curves instead of pointwise. In practice, we determine if neighboring curve edges should be snapped to the same isoline, if yes, they share auxiliary integers used for soft snapping. This ensures the continuity of isolines along the input curves, and prevents jumps.

Another benefit of this approach is that the number of integer variables is significanlty lower (thanks to the grouping approach), the parametrization is therefore computed much faster (we’re still using CoMISo).

ToDo and Questions

Mesh generation

ok for now.

Frame field

• iterative scheme: compute frame field, get the labels, smooth them (?), recompute the frame field with additional constraints on labels (?)
• Q: is biharmonic energy valid with current boundary constraints? What happens at tet mesh boundary? Do we even need biharmonic fields?

Parametrization

• snapping: make sure we don’t snap the same corner multiple times, or even to all three axes (?)
• add constraints between auxiliary integers at cuts
• anisotropic scale: finer scale in the tangent direction, coarser in the two non-tangent directions
• smart strategy for the order of greedy rounding?

(output) Curve network extraction

• instead of greedily choosing the nearest hex edge, use weights for hex edges
• extraction weight: measure alignment of input curves and the frame field
• extraction weight: estimate density of input samples (using KNN?)

Data generation

• Q: what kind of data do we want to apply this method to?
  • Q: what are the strengths of our method?
  • Q: what data can we generate?
  • Q: can we get data from professional designers? (e.g. Fiverr)

Surface generation

• Q: can we use the extra information (frame field, param., hex mesh) to surface the resulting curve network? Can we even do it directly? (what we were thinking of doing originally). Iterative scheme?

Comparisons

• implement baseline comparison using binary extraction from a tet mesh edges (instead of hex mesh edges)

Visualisation

• visualise quality of the tet mesh
• visualise quality of the parametrization
  1. Jacobian: colormap blue->white->red
  2. tet type: valid=green, degenerate=red, inverted=blue
• visualise quality of the hex mesh
• visualise isolines that we snap to in the parametric space
• filter hex edges by extraction costs
• color interior tet faces differently
• color uvw cut faces in the tet mesh differently, only show them
• color tet mesh vertices/corners according to which auxiliary integer they are snapped to

Import/Export

• import/export isolines to/from a file

Misc - low priority

• add timings
• list details of tests from .json
• export extraction weights?
• smart import - don’t crash if not available

Hyperbolic

point

curve

Curved corner

point

curve

Elliptic

point

curve

Bowl

point

curve

Previous focus: extraction

• issue: how do we make sure that the (selected) output edges cover well the input curves?
• heuristic: for each input edge e_input, greedily choose the closest hex edge e_nearest
• optimization: for binary labeling, assign a large negative cost to e_nearest (high probability of being selected), while penalizing the number of selected edges (uniform positive cost per edge)
• results: ok-ish on clean inputs (curved corner, bowl, trebol), unusable on oversketched inputs (sphere circles, round roof, cross) since too many edges get pre-selected
• conclusion: extraction still an open problem, right now now ideas on how to improve it that would not require a more difficult and slow optimization (OT, stochastic, …)

Next steps: parametrization

Extraction gets easier with a good parametrization. In order to improve the parametrization, I want to try two things:

1. modify the snapping
   • instead of point-wise snapping, snap all tets intersected by the input curves
   • snap adjacent tets to the same isoline where we know they should be snapped to the same isoline
   • in practice: create groups of tets, tets in a group will share the two auxiliary integer variables (i.e., they will get snapped to the same isoline). Moreover, don’t forget to include transition functions: if two adjacent groups are separated by a cut, but should still be on the same isoline up to the cut, make sure to include that constraint in the optimization (i.e., tie the two groups of aux variables using the transition functions, same as the ones used for parametric coords)
2. anisotropic scale
   • similar to what we’ve experimented with in 2d
   • in 3d, the estimation of tangent direction should be much more robust
   • use fine scale in the tangent direction, coarse scale in the non-tangent directions
   • this could be one of the technical novelties

Next steps: data generation and collection

Another open challenge is to get the input curve clouds / curve soups. Sources can include:

1. prior work
   • ILoveSketch [Bae et al. UIST 2008]
   • EverybodyLovesSketch [Bae et al. UIST 2009]
   • Analytic Drawing of 3D Scaffolds [Schmidt et al. SA 2009]
   • Agile 3D sketching with air scaffolding [Kim et al. CHI 2018]
   • VIPSS [Huang et al. SIG 2019]
2. synthetic data: take a clean network and artificially add noise/oversketching to it. Clean networks can be taken from e.g.
   • Flow Aligned Surfacing of Curve Networks [Pan et al. SIG 2015]
   • Surfacing curve networks with normal control [Stanko et al. CAG 2016]
3. hire designers to draw stuff for us. If we do that, we will need to provide very specific guidelines to
   • what should be drawn (target photo, target 3d model)
   • how it should be drawn (curves only)
   • the challenge is that we want them to draw freely, but at the same time provide data that we can work with
4. draw stuff ourselves in TiltBrush or Emilie’s tool.
   • freehand drawing
   • constrained drawing (e.g. first draw a bunch of straight lines, then freely draw curves)
   • trace curves on existing 3d model or existing curve network imported to TiltBrush

Other open questions

• what type of data can this method be strong with? (oversketched, but not too much)
• frame field convergence, alternative optimization? (David mentioned LBFGS)

Other ToDos

1. housework
   • timings
   • readme
   • script to process json in order to collect details for experiments
   • better organization of experiments
2. import/export
   • export extracted isolines (verts, edges, params)
   • export extraction weights
   • smarter import: don’t crash if json parameters not available (solution: wrap each in try-catch)
3. visualisation
   • tet mesh vertices, snapped tet mesh vertices, tet mesh vertices snapping groups
   • uvw mesh: cut faces
4. comparisons
   • binary labeling on edges of a (field-aligned or not) tet mesh?

FF convergence

Nearby edge heuristic

sphere

bowl

round roof, fine param.

round roof, mid param.

round roof, coarse param.

cross, coarse param.

cross, mid param.

cross, fine param.

Nearby edge heuristic

Bowl

Curved corner

Trebol

Bowl

Parabolic

Curved corner

Cube

Elliptic

Hyperbolic

Church

Meeting notes (16/12/2019, ADJMT)

• T: news – narrow band, extraction ispired by PolyFit
• T: current priority is to improve the extraction cost (Chamfer distance?)
• D: is twisting a problem? T: Probably ok for now
• A: why do we need fitting and coverage terms in PolyFit? Seems like it’s redundant. T also lacks intuition.
• D: can we try PolyFit coverage term in 1D?
• M: merge tangent + fitting terms together
• A: to start, we can penalize the number of selected edges for the coverage term
• J: is current hex mesh sufficient? T: we can play with parameters and hope for the best (nb size etc.)
• D: harmonic or biharmonic frame field? T: Biharmonic might be better (curved corner example)
• next meeting: send mail beginning of January

ToDo

• implement better extraction costs: two-sided distance of the input edges and the output edges

3d drawing datasets

• From Multiview Image Curves to 3D Drawings [ECCV 2016]
• poly.google.com

Bowl experiments – extraction

PolyFit tests

PolyFit project page (Nan & Wonka, ICCV 2017)

Energy terms: Data fitting vs. Point coverage

Left to right, data fitting weight w_fit is decreasing and point coverage weight w_pc is increasing.

Setting w_fit = 0.1, w_pc = 0.9 (last screenshot) the algorithm does not select any of the faces, that is why the result is empty.

Current results (soft snapping works)

Curved corner

Double wave

Elliptic

Hyperbolic

Parabolic

Church

Box

Bowl

HexEx bug?

Biharmonic

Harmonic

Current status

• “vectorization in 3D”
• given a hex mesh, we now have a simple binary labeling for extracting a clean curve network, see this post

Questions and comments

• David: can we restrict the hex mesh to a narrow band around the input curves? What should be the size of the narrow band? What should be the grid size?
• objective function for extraction? Negative weights?
• locally decide if an edge should have positive or negative weight
• symmetric distance, similar to [Nan and Wonka 2017] or [deGoes et al. 2011] (see below)
• Justin: this seems like a very convoluted way to get a clean curve network. Hex meshing is hard, why not just do tet meshing with alignment constraints?

ToDo

• improve binary labeling: symmetric distance, negative weights, more general constraints
• experiments with real data (TiltBrush)

Next meeting

• Monday, Dec 2, 2019, 2pm/8am

Related papers

[Nan and Wonka, ICCV 2017]
PolyFit

[deGoes et al. 2011]
An Optimal Transport Approach to Robust Reconstruction and Simplification of 2D Shapes

[Ni et al., SGP 2018]
Field-Aligned and Lattice-Guided Tetrahedral Meshing

[Levy and Liu, SIGGRAPH 2010]
Lp Centroidal Voronoi Tesselation and its applications

smoothness

• w_uniform
• w_align
• w_distance

constraints

• c_topology
• c_hard_edges

Summary: I’m implementing the snapping term for the 3D parametrization. For each vertex lying on an input curve, we require two of three parametric coordinates to be close to integers. To that end, I introduce new integer variables i and a set of soft constraints (x - i)^2 for each coordinate that is required to be close to an integer.

The one parametric direction that is not required to be an integer is the one closest to the curve tangent in the combed frame field.

Problem: After the optimization, all of the auxiliary integer variables i are zeros – the constrained vertices collapse onto isolines x=y=0, x=z=0, y=z=0.

Here is a very simple example. This is the input mesh, and the ground truth surface:

Below is a parametrization computed with soft snapping, but only constraining the z-coordinate to be close to an integer. The auxiliary integer variables are all 0, but in this trivial case it works out, and the blue points are close to the plane z=0. Transition fn are all identities here, so the only integer vars are the auxiliary ones.

Here is the hex mesh extracted from the above parametrization:

If we add the proper constraints (i.e. two integers per vertex), we start to see the degeneracies (again, all aux integer vars are 0).

If we increase the snapping penalty weight, we see that the curve points collapse onto coordinate axes:

• in general, higher mesh density –> more linearization artifacts (field tends to get ‘more constant’)

20 input points per curve

simple_parabolic

simple_wave_1

simple_wave_2

simple_elliptic

40 input points per curve

simple_parabolic

simple_wave_2

80 input points per curve

simple_wave_2

misc

Barycentric interpolation: original SH coeffs (before projection)

Summary of results

• tests on boundary curves of Coons patches
• focusing on the frame field
• biharmonic smoothness seems to work well in many cases

Next steps

Frame field: weighted smoothness

• FF smoothness is more important where we expect the surface to be = distance-based weights
• How to get the distance field?
• Start with experiments with a known ground truth surface, see if the result improves with a ‘perfect’ distance field. If that works, we can start worrying about how to get the distance field from the input curves.
• We will probably need some kind of iterative approach: start with some initial guess for the surface, get the distance field from that, update the frame field and the surface, iterate.

Frame field: biharmonic smoothness

• Verify if we need to update the way the field is optimized if we change the smoothness term (?)

Param: customize

• For our custom parametrization, start by dropping the boundary alignment term (we don’t need that).
• Then update the parametrization energy to match our needs: we want the integer sheets to be close the the input curves.
• David thinks we might need soft transition functions.

Extraction

• For visualisation, start by implementing a simple filter to select a subset of quads that are somehow close to the input curves. Maybe start with a given GT surface?
• Modify the extraction algorithm – drop the boundary sanitization (again, we don’t need that).

Tests

• Start doing tests with multiple smooth patches and sharp features

Better field interpolation

More projection iterations (converged after 297)

Crappy field visualisation

More stuff

Explanation

• This test involves computing a 3D frame field aligned to the boundary curve of a cylindrical patch.
• I’m using both tangent and normal constraints.
• Input curve (4 sides) is normalized to have unit AABB diagonal.
• There are two inputs taken from patches with angular size 90 deg and 180 deg.
• I compare two types of boundary surface: unit cube (centered at 0) and the AABB box of the (normalized) curve with a small padding (set to 0.1 here).
• I also compare two types of meshes, a coarse mesh and a fine mesh (max tet volume = 0.00001)
• The constraints are sampled quite densely along the boundary curve (128 samples along the quarter- / half-circle). This seems to prevent the undesirable twisting of frames along the input curves (example here)
• Frame field is discretized per-vertex of the tet mesh and computed using unconstrained quadratic optimization (smoothness + alignment energy), ignoring the non-linear quadratic constraint. I then do a projection on the feasible set via the gradient descent from [Ray & Sokolov 2015].
• For visualisation, the frame field is sampled on the surface of the cylinder: barycentric interpolation of spherical harmonic coefficients on tetmesh vertices + projection on the feasible set of frames.

Comments

• Some of the frames are obviously wrong: that’s most likely a bug in the projection on the feasible set that occurs when the frame is a rotation of the reference frame around x-, y- or z-axis by pi/4
• Harmonic energy gives a constant field away from circles – not what we want
• Biharmonic is a bit better, but – strangely – the results depend too much on the input mesh. For instance the result is close to what we want (both input, 90 and 180 deg) using unit cube as boundary and coarse mesh, but it no longer works if we take a fine mesh or use the AABB boundary surf.

Legend

• magenta: frame field constraints
• blue: boundary vertices of the tet mesh
• green: interior vertices of the tet mesh
• stats in the top: cylinder params, mesh stats (#verts, #tets), boundary type (cube or aabb), smoothness type (harmonic or biharmonic), optimization weights (smoothness and alignment), computation time in seconds (solve, projection)

Harmonic smoothness

Quarter-circle (90° arc)

Bd surf: unit cube

• coarse mesh (+ dense network)

• fine mesh (+ dense network)

Bd surf: AABB + margin

• coarse mesh (+ dense network)

• fine mesh (+ dense network)

Half-circle (180° arc)

Bd surf: unit cube

• coarse mesh (+ dense network)

• fine mesh (+ dense network)

Bd surf: AABB + margin

• coarse mesh (+ dense network)

• fine mesh (+ dense network)

Biharmonic smoothness

Quarter-circle (90° arc)

Bd surf: unit cube

• coarse mesh (+ dense network)

• fine mesh (+ dense network)

Bd surf: AABB + margin

• coarse mesh (+ dense network)

• fine mesh (+ dense network)

Half-circle (180° arc)

Bd surf: unit cube

• coarse mesh (+ dense network)

• fine mesh (+ dense network)

Bd surf: AABB + margin

• coarse mesh (+ dense network)

• fine mesh (+ dense network)