nicopietroni / quadwild Goto Github PK

Implementation of Reliable Feature-Line Driven Quad-Remeshing

License: GNU General Public License v3.0

C++ 71.02% QMake 0.15% C 17.82% M4 0.03% Lex 0.03% Yacc 0.09% Shell 1.56% CMake 1.76% Makefile 0.25% Perl 0.20% HTML 0.80% Python 0.05% CSS 0.03% Gnuplot 0.01% PHP 0.03% Fortran 5.99% JavaScript 0.03% Hack 0.17%

geometry computer-graphics geometry-processing quadrangulation remeshing

quadwild's Introduction

Reliable Feature-Line Driven Quad-Remeshing

Nico Pietroni, Stefano Nuvoli, Thomas Alderighi, Paolo Cignoni, Marco Tarini
SIGGRAPH 2021

Abstract

We present a new algorithm for the semi-regular quadrangulation of an input surface, driven by its line features, such as sharp creases. We define a perfectly feature-aligned cross-field and a coarse layout of polygonal-shaped patches where we strictly ensure that all the feature-lines are represented as patch boundaries. To be able to consistently do so, we allow non-quadrilateral patches and T-junctions in the layout; the key is the ability to constrain the layout so that it still admits a globally consistent, T-junction-free, and pure-quad internal tessellation of its patches. This requires the insertion of additional irregular-vertices inside patches, but the regularity of the final- mesh is safeguarded by optimizing for both their number and for their reciprocal alignment. In total, our method guarantees the reproduction of feature-lines by construction, while still producing good quality, isometric, pure-quad, conforming meshes, making it an ideal candidate for CAD models. Moreover, the method is fully automatic, requiring no user intervention, and remarkably reliable, requiring little assumptions on the input mesh, as we demonstrate by batch processing the entire Thingi10K repository, with less than 0.5% of the attempted cases failing to produce a usable mesh.

Website: https://www.quadmesh.cloud/
DOI: 10.1145/3450626.3459941 ACM Transactions on Graphics (SIGGRAPH), 2021

BibTex

@article{10.1145/3450626.3459941,
author = {Pietroni, Nico and Nuvoli, Stefano and Alderighi, Thomas and Cignoni, Paolo and Tarini, Marco},
title = {Reliable Feature-Line Driven Quad-Remeshing},
year = {2021},
issue_date = {August 2021},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {40},
number = {4},
issn = {0730-0301},
url = {https://doi.org/10.1145/3450626.3459941},
doi = {10.1145/3450626.3459941},
abstract = {We present a new algorithm for the semi-regular quadrangulation of an input surface, driven by its line features, such as sharp creases. We define a perfectly feature-aligned cross-field and a coarse layout of polygonal-shaped patches where we strictly ensure that all the feature-lines are represented as patch boundaries. To be able to consistently do so, we allow non-quadrilateral patches and T-junctions in the layout; the key is the ability to constrain the layout so that it still admits a globally consistent, T-junction-free, and pure-quad internal tessellation of its patches. This requires the insertion of additional irregular-vertices inside patches, but the regularity of the final-mesh is safeguarded by optimizing for both their number and for their reciprocal alignment. In total, our method guarantees the reproduction of feature-lines by construction, while still producing good quality, isometric, pure-quad, conforming meshes, making it an ideal candidate for CAD models. Moreover, the method is fully automatic, requiring no user intervention, and remarkably reliable, requiring little assumptions on the input mesh, as we demonstrate by batch processing the entire Thingi10K repository, with less than 0.5% of the attempted cases failing to produce a usable mesh.},
journal = {ACM Trans. Graph.},
month = {jul},
articleno = {155},
numpages = {17},
keywords = {geometry processing, quad-meshing, modelling}
}

Download

git clone --recursive https://github.com/nicopietroni/quadwild

Build

Install the libraries boost and gurobi. In Ubuntu you can install boost easily with the following terminal commands:

apt-get install libboost-dev

Open the file libs/libs.pri and set the paths of the requested libraries and the gurobi parameters:

#External libraries
BOOST_PATH          = /usr/include/boost/
GUROBI_PATH         = /opt/gurobi950/linux64/
GUROBI_COMPILER     = gurobi_g++5.2
GUROBI_LIB          = gurobi95

If you do not need CoMISo, you can simply remove the define COMISO_FIELD in the file libs.pri:

#DEFINES += COMISO_FIELD

However, for organic meshes, we suggest to abilitate CoMISo. You need to compile it along with its dependencies (BLAS):

apt install libblas-dev
cd quadwild/libs/CoMISo
mkdir build
cd build
cmake ..
make

You can now compile the project quadwild/quadwild.pro with qmake or QtCreator.

In case you have technical issues or building problems, please write to [email protected] or [email protected].

Run

The package is composed of the main command-line quad-remesher (quadwild) and three different components (field_computation, field_tracing, quad_from_patches) that perform different steps of the pipeline.

quadwild

This project has no visual interface and can be used via command-line. This can be helpful to batch run entire datasets of models. To run the project, once builded, execute the following terminal command:

./quadwild <mesh> [.txt setup file] [.rosy file] [.sharp file]

The command takes as input a mesh and three optional configuration files:

<mesh>: filename of the input triangle mesh. The mesh can be either an obj or a ply.
.txt setup file (optional): The txt setup file contains the parameters in the pipeline. By default, the executable loads the file basic_setup.txt and two other examples are included: basic_setup_mechanical.txt and basic_setup_organic.txt. Any setup parameter can be specified to control the output result. The setup file has the following fields:

do_remesh 1 		  //remesh (1) or not (0) the input mesh
sharp_feature_thr 35      //the dihedral angle of sharp features (-1 no features)
alpha 0.02                //regularity vs isometry of the final tessellation. Close to zero -> more regular, Close to 1 -> more singularity are inserted
scaleFact 1               //the scale of the final quadrangulation (the bigger the bigger the quads)

.rosy file (optional): This optional file contains parameters for the field computation of the field.

fn              //number of faces of the mesh
4               //directions of the field (always 4 for a cross-field)
x0 y0 z0        //XYZ directions of one vector of the cross-field of the first face
...
xn yn zn        //XYZ directions of one vector of the cross-field of the n-th face

.sharp file (optional): This optional file contains the informations of the sharp features. Note that, in the pipeline, border edges are considered sharp features by default.

sn                //number of sharp features
t0 f0 e0          //for each sharp edge: the first integer is 0 if the edge is concave 1 if convex, then the face and the index of the sharp edge
...
tn fn en          //nth sharp edge

The output of quadwild consists of several files:

The output smooth quadrangulation (suffix quadrangulation_smooth.obj).
The output quadrangulation before being smoothed (suffix quadrangulation.obj).
Other files:
- The re-meshed triangulated mesh (suffix rem.obj), the relative field and the sharp features automatically computed (.rosy and .sharp files as above).
- The mesh decomposed after the tracing (suffix rem_p0.obj).
- The patch decomposition (.patch file) contains the patch index for each triangle of the rem_p0 mesh.
- The files .corners, .c_feature, .feature files that contain per patch information (respectively corners of each patch, corners to be fixed and feature lines on the patches).

field_computation.

The program can be used either with a GUI or by command line (useful to batch run entire datasets of models).

./field_computation <mesh> [.txt setup file] [.rosy file][.sharp file] [batch]

The "batch" option makes the program run in the shell without the GUI. The setup file includes additional parameters. By default, the executable loads the file basic_setup.txt.

field_tracing

This program is used to trace fields and split the mesh into patches.

./field_tracing <mesh> [.txt setup file] [batch]

It requires having a .rosy and a .sharp file (with the same name of the mesh file). The "batch" option makes the program run in the shell without the GUI. The setup file includes additional parameters. By default, the executable loads the file basic_setup.txt.

quad_from_patches

This program is used to obtain a quadrangulation from a patch decomposition.

./quad_from_patches <mesh> [.txt setup file]

It requires to have in the same folder a .corners, .c_feature, .feature files (with the same name of the mesh file). The setup file includes additional parameters. By default, the executable loads the file basic_setup.txt.

Note

The code has slightly changed and the results could be different from the ones showed in the paper.

License

GPL3 licensed (FAQ)

quadwild's People

Contributors

Stargazers

Watchers

quadwild's Issues

Field Tracing Problem

I found that in the function PreProcessMesh , calling the function
VertSplitter<MeshType>::SplitAlongEdgeSel(mesh);
may cause parts of the mesh to be non-manifold (even if I didn't mark any sharp edge), and this is probably caused by the function
SplitAdjacentSingularities(mesh);
(when I call both two functions, non-manifold vertices around singularities occur, otherwise not).
Are those non-manifold parts desirable? Thanks for your answer.

Unable to compile quadwild due to lack of gurobi

On Rocky Linux (rhel8).

yum install boost-devel blas-devel ninja-build cmake
cd quadwild/libs/CoMISo
mkdir build
cd build
cmake .. -GNinja
ninja
sudo yum install -y qt5-devel
make

Unable to compile due to lack of gurobi.

Can this method be used for open boundary surfaces?

Different level of detail/quad density

Hello,

First of all, thank you for the excellent work and the published code.
While testing your algorithm, I noticed that sometimes quads with different edge lengths are obtained, not only with the one specified in the algorithm parameters. (Example on the picture)

Could you, please, clarify how I can intentionally change the length of quad edges/density of quads in the algorithm? If it is possible.

To ensure adoption of quadwild, provide binaries for Windows, Mac and Linux.

Status: proposed
Deciders: V-Sekai,fire,
Tags: V-Sekai,quadwild

Context and Problem Statement

quadwild appears to only be a source distribution on github.

I want to make the technology more accessible.

Describe the proposed option and how it helps to overcome the problem or limitation

Use github actions to automatically build quadwild for Windows, Mac, and Linux.

Describe how your proposal will work, with code, pseudo-code, mock-ups, or diagrams

Switch from gurobi to anything that can be redistributed and remixed.
Automate Linux builds
flatpak? appimage?
Automate Windows builds
Automate Macos builds
Default to organic shapes for my characters usecase.
Package all three platforms into the releases section.

Positive Consequences

Widespread adoption
Allows making an external addon for Blender

Negative Consequences

Requires devops work.

Option graveyard:

Option: Keep the current situation.
Rejection Reason: It is difficult to build.

If this enhancement will not be used often, can it be worked around with a few lines of script?

This not a small github action.

Is there a reason why this should be core and done by us?

Wanted to share the work with the quadwild maintainers.

References

https://github.com/nicopietroni/quadwild/

Relicense to be importabled into Godot Engine as a c++ module

Hi!

It's ok, if you refuse, but I was wondering about your thoughts about relicensing to be Godot Engine compatible.

Godot Engine is MIT licensed.

MPL2 is good too.

References

Skip quadrangulation and extract tracing results as coarse mesh

Thank you for open-sourcing the amazing work!
I'm wondering if there is a suggested way to extract tracing results as a coarse mesh (it's okay to get non-quad mesh)

Appreciate any help!

qmake

I've followed your instructions for the first few steps, but when I do this step "You can now compile the project quadwild/quadwild.pro with qmake or QtCreator.", the code gives me an error, I first type in the terminal "qmake I first type "qmake.pro" and then "make" in the terminal, the code will report an error as shown in this figure

Do you have any good suggestions or programs to solv

e this problem? Sorry to bother you! Have a nice life!

Unable to compile even with Gurobi Solver.

I generate the makefile using qmake.
When I run make -j8 I get this error.

../components/field_tracing/tracing/metamesh.h: In member function ‘std::size_t MetaMesh<MeshType>::SideStartingE(std::size_t, std::size_t) const [with MeshType = TraceMesh]’:
../components/field_tracing/tracing/metamesh.h:185:5: warning: control reaches end of non-void function [-Wreturn-type]
  185 |     }
      |     ^
Makefile:5815: recipe for target 'quadwild.o' failed
make: *** [quadwild.o] Error 1

Is it possible to use quadwild without gurobi solver?

Since gurobi is a commercial software package, Is it possible to use quadwild without gurobi solver?
How to configure the quadwild wth comiso miq solver runing witrhout gurobi backend?

does it preserve the features after remeshing?

Features in my mesh changes after running the project. In the function "remeshAndField", the code use the function of vcglib to remesh. However the function seems to fail to preserve the features such as the borders.
here is the relavant code:
`
static void RemeshAdapt(Mesh & m, Params & par)
{

    vcg::tri::UpdateBounding<Mesh>::Box(m);
    vcg::tri::UpdateTopology<Mesh>::FaceFace(m);

    typename vcg::tri::IsotropicRemeshing<Mesh>::Params para;
    para.iter = par.iterations;
    //para.SetFeatureAngleDeg(par.creaseAngle);

    para.splitFlag    = true;
    para.swapFlag     = true;
    para.collapseFlag = true;
    para.smoothFlag   = true;
    para.projectFlag  = true;
    para.selectedOnly = false;
    para.adapt=false;
    para.aspectRatioThr = 0.3;
    para.cleanFlag = true;

    para.minAdaptiveMult = par.minAdaptiveMult;
    para.maxAdaptiveMult = par.maxAdaptiveMult;

    para.maxSurfDist = m.bbox.Diag() / 2500.;
    para.surfDistCheck = m.FN() < 400000 ? par.surfDistCheck : false;
    para.userSelectedCreases = true;



    ScalarType edgeL = ExpectedEdgeL(m);//,par.initialApproximateFN);//std::sqrt(2.309 * vcg::tri::Stat<Mesh>::ComputeMeshArea(m) / par.initialApproximateFN);//m.bbox.Diag() * 0.025;//std::sqrt(vcg::tri::Stat<Mesh>::ComputeMeshArea(m) * 2 / par.initialApproximateFN);

    if (par.targetEdgeLen == 0)
        par.targetEdgeLen = edgeL;

    para.SetTargetLen(par.targetEdgeLen);


    std::cout << "Before Remeshing - faces: " << m.FN() << " quality: " <<  computeAR(m) << std::endl;
    vcg::tri::IsotropicRemeshing<Mesh>::Do(m, para);
    std::cout << "After Iter 0 - faces: " << m.FN() << " quality: " <<  computeAR(m) << std::endl;


    const ScalarType thr = 0.01;

    //vcg::tri::UpdateSelection<Mesh>::VertexClear(m);
    collapseSurvivingMicroEdges(m,thr);

    UpdateCoherentSharp(m,par);

    para.adapt = true;
    para.smoothFlag   = true;
    para.maxSurfDist = m.bbox.Diag() / 2500.;

    vcg::tri::IsotropicRemeshing<Mesh>::Do(m, para);

    m.UpdateDataStructures();

    std::cout << "After Iter 1 - faces: " << m.FN() << " quality: " <<  computeAR(m) << std::endl;

// MakeEdgeSelConsistent(m);
// SelectAllBoundaryV(m);
// typename Local_Param_Smooth::UVSmoothParam UVP;
// UVP.FixSel=true;

// Local_Param_Smooth::Smooth(m,UVP);
// m.UpdateDataStructures();
// std::cout << "After Iter 2 - faces: " << m.FN() << " quality: " << computeAR(m) << std::endl;

how to use the three components?

first, thank you for your contribution !
i have successfully compile the field_computation and field_tracing program
but i don't know how to use those funcitons on the GUI
can you give me some details?

Stuck on 1 - Remesh and field

Quadwild takes a very looooong time (or freezes), without error.

I launch the software:

quadwild quadwild.ply basic_setup_organic.txt 
Reading input...
READ CONFIG FILE
Successful config import
READ CONFIG FILE
Successful config import
Loading:quadwild.ply
Loaded 942452 faces and 479417 vertices

--------------------- 1 - Remesh and field ---------------------
There is 62.2286 sharp lenght
EndPoints 0
KScale 14.2021
Before Remeshing - faces: 942452 quality: 0.3297

after 4 hours of this I kill the process.

Mesh is a surface resulting from a photogrammetry. Is the software suitable for this kind of work / polycount ?

Thank you,
Riccardo

Unable to compile quadwild using Gurobi

I followed all of the instructions on the Github, including adjusting my Gurobi path. When I type qmake, the MakeFile gets generated. Then when I type make, I get the error

Makefile:1750: recipe for target 'lp_rlp.o' failed
make: *** [lp_rlp.o] Error 1

Here's an example error block, I don't understand how I would solve this. I am compiling on a linux 64 machine:

../libs/quadretopology/patterns/patterns/lp_solve_5.5/lp_rlp.y:30:26: error: ‘yyscanner’ undeclared (first use in this function); did you mean ‘scanner’?
 #define PARM yyget_extra(yyscanner)
                          ^
../libs/quadretopology/patterns/patterns/lp_solve_5.5/lp_rlp.h:996:20: note: in expansion of macro ‘PARM’
   parse_parm *pp = PARM;
                    ^~~~
../libs/quadretopology/patterns/patterns/lp_solve_5.5/lp_rlp.y:30:26: note: each undeclared identifier is reported only once for each function it appears in
 #define PARM yyget_extra(yyscanner)
                          ^
../libs/quadretopology/patterns/patterns/lp_solve_5.5/lp_rlp.h:996:20: note: in expansion of macro ‘PARM’
   parse_parm *pp = PARM;
                    ^~~~
In file included from ../libs/quadretopology/patterns/patterns/lp_solve_5.5/lp_rlp.y:107:0:
../libs/quadretopology/patterns/patterns/lp_solve_5.5/lp_rlp.h:999:10: error: ‘COMMA’ undeclared (first use in this function); did you mean ‘ECOMM’?
   return(COMMA);
          ^~~~~
          ECOMM

Segment violation (generated `core')

Thank you so much for sharing your work. It´s one of the best quad-remeshing software I have found.

I want to share an issue I´m facing trying to remesh this 3D model (the size is around 2.5 Mb)
https://www.cgtrader.com/items/47809/download-page

Do you know what the problem could be?

$ ./quadwild 3d/mandela.obj

Reading input...
READ CONFIG FILE
Successful config import
Loading:3d/mandela.obj
Loaded 77294 faces and 38923 vertices

--------------------- 1 - Remesh and field ---------------------
There is 41.5161 sharp lenght
EndPoints 29
KScale 0.677321
Before Remeshing - faces: 77294 quality: 0.396167
After Iter 0 - faces: 14315 quality: 0.492314
After Iter 1 - faces: 12493 quality: 0.530295
Performing 39 face refinement ops
Performing 369 split ops
Performing 0 split ops
Sqrt Area 3.97434
Sharp Lenght 28.4447
Ratio 7.15708
Using NPoly
[fieldComputation] Smooth Field Computation...
..Global Orientation..
..Update Singularities..
..Update Features..
Saving Mesh TO:3d/8_rem.obj
Saving Field TO:3d/8_rem.rosy
Saving Sharp TO:3d/8_rem.sharp

--------------------- 2 - Tracing ---------------------
Loading Remeshed M:3d/8_rem.obj
Loading Rosy Field:3d/8_rem.rosy
Loading Sharp F:3d/8_rem.sharp
Loading the mesh
Importing ROSY field
Imported ROSY field
Num 1321
Repositioning 5 duplicated vertices
Adjusted 0 zero area faces
Adjusted 0 zero area faces
splitting along sharp features
done
updating attributes
compact vectors
counting non manifold Vert
splitted
Non Manif 0
setting rest pos
done
**** FIRST TRACING STEP ****
Updating Patches
Updated
**** FIRST SUBTRACING STEP ****
**** RETRIEVING NON OK PATCHES ****
Filtered out 0 patches
**** SUBPATCH TRACING - THERE ARE 142 Unsolved Partitions ****
** UNSATISFIED PATCHES **
*Num Patches:25
*Low Sides:25
*High Sides:2
*Non Disks:0
*Has Emit:36
*Max CCbility:5
*Wrong Valence:74
*IsOk:0
Has traced into 75 patches
Updating Patches
Done Updating Patches
**** RETRIEVING NON OK PATCHES ****
Filtered out 63 patches
**** SUBPATCH TRACING - THERE ARE 94 Unsolved Partitions ****
** UNSATISFIED PATCHES **
*Num Patches:18
*Low Sides:18
*High Sides:1
*Non Disks:0
*Has Emit:1
*Max CCbility:2
*Wrong Valence:135
*IsOk:0
Has traced into 15 patches
Updating Patches
Done Updating Patches
**** RETRIEVING NON OK PATCHES ****
Filtered out 142 patches
**** SUBPATCH TRACING - THERE ARE 13 Unsolved Partitions ****
** UNSATISFIED PATCHES **
*Num Patches:18
*Low Sides:18
*High Sides:1
*Non Disks:0
*Has Emit:0
*Max CCbility:1
*Wrong Valence:135
*IsOk:0
Has traced into 1 patches
Updating Patches
Done Updating Patches
**** RETRIEVING NON OK PATCHES ****
Filtered out 154 patches
**** SUBPATCH TRACING - THERE ARE 0 Unsolved Partitions ****
** UNSATISFIED PATCHES **
*Num Patches:18
*Low Sides:18
*High Sides:1
*Non Disks:0
*Has Emit:0
*Max CCbility:1
*Wrong Valence:134
*IsOk:0
Has traced into 0 patches
Updating Patches
Done Updating Patches
**** CHECK NO DISK ONES ****
**** RETRIEVING NON OK PATCHES ****
**** SUBPATCH TRACING - THERE ARE 0 Unsolved Partitions ****
Has traced into 0 patches
Updating Patches
Done Updating Patches
**** FORCE SOLVING NO DISK ONES ****
**** RETRIEVING NON OK PATCHES ****
**** SUBPATCH TRACING - THERE ARE 0 Unsolved Partitions ****
Has traced into 0 patches
Updating Patches
Done Updating Patches
**** After All Insertion Steps ****
**** FINAL REMOVAL ****
** FACES IGNORED IN METAMESH **:0
Initializing Adjacency
Done
There are 425 paths labels
Performed 2 removal loops
Removed 161 paths
** FACES IGNORED IN METAMESH **:0
Initializing Adjacency
Done
There are 627 paths labels
Performed 2 removal loops
Removed 91 paths
**** After Last Removal Step ****
Updating Patches
**** FINAL THERE ARE 161 Unsolved Partitions ****
**** TOTAL 379 Partitions ****
Updated
Smoothing
There are 507 folds
End Smoothing
FINAL STATS

Num Patches 379
Low Valence Patches 18
High Valence Patches 1
Non Disk Like Patches 0
Non Match Quality Patches 0
With Emitters Patches 0
Patch with 0 corners are: 0
Patch with 1 corners are: 0
Patch with 2 corners are: 0
Patch with 3 corners are: 220
Patch with 4 corners are: 113
Patch with 5 corners are: 46
Patch with 6 corners are: 0
Patch with 7 corners are: 0
**** FINAL ELAPSED TIME 2.64466 Seconds ****
There are 480 folds
FINAL STATS
Num Patches 379
Low Valence Patches 18
High Valence Patches 1
Non Disk Like Patches 0
Non Match Quality Patches 0
With Emitters Patches 0
Patch with 0 corners are: 0
Patch with 1 corners are: 0
Patch with 2 corners are: 0
Patch with 3 corners are: 220
Patch with 4 corners are: 113
Patch with 5 corners are: 46
Patch with 6 corners are: 0
Patch with 7 corners are: 0
**** SAVING MESH ****

--------------------- 3 - Quadrangulation ---------------------
Loaded 379 patches
Loaded 379 corners set
Loaded 1005 features
Loaded 17 corner features
Alpha: 0.01
CHECKING ORIENTATION
Edge size: 0.0457049
Initial cluster 0 composed of 300 charts.
Initial cluster 1 composed of 16 charts.
Initial cluster 2 composed of 2 charts.
Initial cluster 3 composed of 7 charts.
Initial cluster 4 composed of 8 charts.
Initial cluster 5 composed of 2 charts.
Initial cluster 6 composed of 1 charts.
Initial cluster 7 composed of 9 charts.
Initial cluster 8 composed of 8 charts.
Initial cluster 9 composed of 4 charts.
Initial cluster 10 composed of 6 charts.
Initial cluster 11 composed of 2 charts.
Initial cluster 12 composed of 14 charts.
Cluster 0 is composed of 336 charts.
Cluster 7 is composed of 9 charts.
Cluster 8 is composed of 8 charts.
Cluster 9 is composed of 4 charts.
Cluster 10 is composed of 6 charts.
Cluster 11 is composed of 2 charts.
Cluster 12 is composed of 14 charts.
Patches clustered in: 7 clusters.
Fixed 0 / 957 subsides.