Build

cmake -B build -DCMAKE_BUILD_TYPE=Release
cd build 
make -j

Run

build/src/main [bord] [quad]

build/src/main ./assets/lapin_bord.obj ./assets/lapin_quad_mesh.obj

# To visualize with graphite
graphite ./output/* 

Principle

Build a smooth and derivable signed and unsigned distance function of a polyline for gradient descent purposes.

• function defined only in a certain neighborhood of the polyline
• used for quad mesh smoothing algorithm

Use of HRBF: interpolation of values for a set of points and normals with compact elliptic support RBF

Pipeline

• Initialization: 1 point and normal per segment of input polyline with default ellipse radius.
• Fit ellipse: find functions' ellipses radii so each function interacts with its neighbors.
• Fit HRBF: find $\alpha$ and $\beta$ (HRBF coefficients) that fit the input polyline the best.

Project structure

• ./assets/ input polylines and quad meshes
• ./output/ program output
• ./src/ :
  • debug_macros.hpp: macros for debug verbose
  • ellipse_fitter.cpp: ellipse_fitter implementation
  • hrbf_fitter.cpp: hrbf_fitter implementation
  • input.hpp: functions for processing inputs
  • main.cpp
  • quadtree.hpp: quadtree structure for sdf evaluation
  • sdf.hpp: sdf and udf
  • smoother.cpp: smoother implementation
  • smoother.hpp: smoother interface

Project pipeline

• Process inputs
  • extract subpolylines
  • mark quad mesh vertices attributes
• Build UDFs
• Smooth mesh

Main

Input::process_and_cut_polyline(quad, polyline, sharp_angle) : extract subpolylines from the frontier by cutting on intersection of more than two edges or where angle between two angles > sharp_angle, and mark quad mesh vertices that are locked or belong to a subpolyline.

• quad : Quads
• polyline : PolyLine
• sharp_angle : double -- max angle in radians

Not implemented decimate(angle) : reduce number of functions (= simplify polyline) with clustering

fit_ellipses(W, K): find radii for ellipses using BFGS

• W: double -- target distance function width of defined space around polyline, depends on input coordinate space
• K: int -- number of neighbors ellipses should contain

optimize(): precompute some parameters and generate a quadtree structure to speed up sdf evaluation

fit_hrbf(nsample, sample_margin, lambda_distance): find HRBF parameters using least squares

• nsample: int ($\ge 1$) -- number of samples per polyline segment
• sample_margin: double ($\in [0, 0.5[$) -- left and right margin for samples to prevent having two samples on segment start and end point
• lambda_distance: double -- weight of the distance term in least squares

Smoother::smooth(m, lock, slide, udfs, frontier_W): Smooth the input quad mesh, while keeping points on frontier

• m: Quads -- a quad mesh
• lock: PointAttribute<bool> -- boolean attributes on quadmesh points that are true for points that are locked
• slide: CornerAttribute<int> -- int attributes on quadmesh halfedges that is -1 when points are not on a frontier, and i >= 0 if they are, with i the index of the corresponding frontier
• udfs: std::vector<UDF> -- vector of frontier distance functions, indices must coincide with slide
• frontier_W: double -- weight of the stick to frontier term inside smoother energy, depends on distance function magnitude (max value)

Default main

Default main for a input of one single extern frontier with no locked points

UM::PolyLine pl;
Quads quad;

read_by_extension(bord_file, pl);
read_by_extension(quad_file, quad);

pl.connect();
quad.connect();

PointAttribute<bool> lock(quad.points, false);
CornerAttribute<int> slide(quad, -1);

write_by_extension(std::string(OUTPUT_DIR) + "bord.geogram", pl);
write_by_extension(std::string(OUTPUT_DIR) + "input_quad.geogram", quad, {{"slide", slide}, {"lock", lock}});

std::vector<UDF> udfs;
udfs.emplace_back(pl);

auto& udf = udfs[0];

udf.fit_ellipses(0.05, 6);
udf.optimize();
udf.fit_hrbf(5);

for (const auto& h : quad.iter_halfedges()) {
    if (!h.opposite().active()) {
        slide[h] = 0;
    }
}

Smoother::smooth(quad, lock, slide, udfs, 1e2); 

write_by_extension(std::string(OUTPUT_DIR) + "smoothed.geogram", quad, {{"slide", slide}, {"lock", lock}});