hcebke/libqex

The Robust Quad Mesh Extraction Library

libQEx – A Robust Quad Mesh Extractor

libQEx is an implementation of QEx [Ebke et al. 2013] distributed under GPLv3. Commercial licensing is available upon request.

If you make use of libQEx in your scientific work, please cite our paper. For your convenience, you can use the following bibtex snippet:

@article{Ebke:2013:QRQ:2508363.2508372,
 author = {Ebke, Hans-Christian and Bommes, David and Campen, Marcel and Kobbelt, Leif},
 title = {{QE}x: Robust Quad Mesh Extraction},
 journal = {ACM Trans. Graph.},
 issue_date = {November 2013},
 volume = {32},
 number = {6},
 month = nov,
 year = {2013},
 issn = {0730-0301},
 pages = {168:1--168:10},
 articleno = {168},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/2508363.2508372},
 doi = {10.1145/2508363.2508372},
 acmid = {2508372},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {integer-grid maps, quad extraction, quad meshing},
}

What is QEx?

QEx (pronounced 'kyü-eks\) is a method for robust quad mesh extraction from Integer-Grid Maps with imperfections. (Imperfect) Integer-Grid Maps are what is generated by most state-of-the-art quad meshing methods such as QuadCover [Kälberer et al. 2007] or our own Mixed-Integer Quadrangulation [Bommes et al. 2009].

Quad extraction is often believed to be a trivial matter but quite the opposite is true: numerous special cases, ambiguities induced by numerical inaccuracies and limited solver precision, as well as imperfections in the maps produced by most methods (unless costly countermeasures are taken) pose significant challenges to the quad extractor.

Read our paper if you want to find out why quad extraction is complicated and how we tackle it or skip ahead and download the source code if you don't care about the details and just need results.

License

libQEx is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. See http://www.gnu.org/licenses/.

If you make use of libQEx in scientific work we kindly ask you to cite our paper. (You can use the bibtex snippet above.)

Commercial licensing under negotiable terms is available upon request. Please send an email to [email protected] if you are interested.

Bibliography

Bommes, D., Zimmer, H., and Kobbelt, L. 2009. Mixed-integer quadrangulation. In Proc. SIGGRAPH 2009.

Ebke, H.-C., Bommes, D., Campen, M., and Kobbelt, L. 2013. QEx: Robust Quad Mesh Extraction. ACM Trans. Graph., 32(6):168:1–168:10, November 2013.

Kälberer, F., Nieser, M., and Polthier , K. 2007. Quadcover - surface parameterization using branched coverings. Computer Graphics Forum 26, 3, 375–384.

libqex's Issues

Preserving boundary while extracting quad-mesh

Hello! Are there any methods to preserve the boundary of original triangle mesh while extracting quad-mesh. Preserving boundary means keeping all the boundary vertices of resulting quad-mesh lying on the boundary edges of triangle mesh.

Here is the result of libQEx.

Can libQEx keep boundary while extracting quad-mesh from open triangle mesh?

What's the meaning of "VVAL file"?

Hi,
Please tell me what's the meaning of VVAL file?
Is it the dim of each vertex' valence?

Can't CMake install

Hello,
CMake gives me an error because it can't find OPENMESH_INCLUDE_DIR (see image) and I don't know what directory to provide to it.

Also, what should I put for these two:
OPENMESH_CORE_LIBRARY
OPENMESH_TOOLS_LIBRARY

Thanks
Lorenzo

some error during libqex running

I use a Global parameterization to generate texture coordinates to generate a .obj file and use this .obj file as input to libqex.During the program running，program running error occurs.I guess the error is from global parameterization.Thanks for your reply!
The error follows:
`Exact predicates initialized.
�[1;32mNot using externally supplied vertex valences.�[0m
�[1;32mMeshDecimator::decimate() collapsed 10 edges.�[0m
constructed 11193 valid transition functions -> 30 invalid ones
test exactness of transition functions before preprocessing...
... done!
found 224 inexact transitions in input with max deviation 1.60583e-12
QuadMeshExtraction Preprocess maxmial uv deviaton: 9.53674e-07
test exactness of transition functions...
... done!
�[1;32mMeshDecimator::decimate() collapsed 0 edges.�[0m
�[44mGV 538 (OnVertex) on face 4200: expected_lei_count != _gv.local_edges.size(): 2 != 3, pos_angleSum: 3.14159�[0m
�[44mGV 542 (OnVertex) on face 6856: expected_lei_count != _gv.local_edges.size(): 7 != 2, pos_angleSum: 10.9956�[0m
�[44mGV 543 (OnVertex) on face 4354: expected_lei_count != _gv.local_edges.size(): 5 != 2, pos_angleSum: 7.85398�[0m
�[44mGV 544 (OnVertex) on face 2463: expected_lei_count != _gv.local_edges.size(): 5 != 3, pos_angleSum: 7.85398�[0m
�[44mGV 545 (OnVertex) on face 3424: expected_lei_count != _gv.local_edges.size(): 3 != 1, pos_angleSum: 4.71239�[0m
�[44mGV 546 (OnVertex) on face 966: expected_lei_count != _gv.local_edges.size(): 3 != 1, pos_angleSum: 4.71239�[0m
�[44mGV 549 (OnVertex) on face 2111: expected_lei_count != _gv.local_edges.size(): 5 != 3, pos_angleSum: 7.85398�[0m
�[44mGV 553 (OnVertex) on face 1783: expected_lei_count != _gv.local_edges.size(): 5 != 3, pos_angleSum: 7.85398�[0m
�[44mGV 554 (OnVertex) on face 1873: expected_lei_count != _gv.local_edges.size(): 5 != 1, pos_angleSum: 7.85398�[0m
�[44mGV 555 (OnVertex) on face 2512: expected_lei_count != _gv.local_edges.size(): 5 != 3, pos_angleSum: 7.85398�[0m
�[44mGV 559 (OnVertex) on face 5833: expected_lei_count != _gv.local_edges.size(): 3 != 1, pos_angleSum: 4.71239�[0m
�[44mGV 560 (OnVertex) on face 2605: expected_lei_count != _gv.local_edges.size(): 5 != 1, pos_angleSum: 7.85398�[0m
�[44mGV 561 (OnVertex) on face 2625: expected_lei_count != _gv.local_edges.size(): 5 != 3, pos_angleSum: 7.85398�[0m
�[44mGV 562 (OnVertex) on face 5988: expected_lei_count != _gv.local_edges.size(): 4 != 3, pos_angleSum: 6.28319�[0m
�[44mGV 563 (OnVertex) on face 4864: expected_lei_count != _gv.local_edges.size(): 5 != 1, pos_angleSum: 7.85398�[0m
�[44mGV 565 (OnVertex) on face 5447: expected_lei_count != _gv.local_edges.size(): 5 != 2, pos_angleSum: 7.85398�[0m
�[44mGV 566 (OnVertex) on face 5479: expected_lei_count != _gv.local_edges.size(): 3 != 1, pos_angleSum: 4.71239�[0m
�[44mGV 567 (OnVertex) on face 2671: expected_lei_count != _gv.local_edges.size(): 3 != 2, pos_angleSum: 4.71239�[0m
�[44mGV 568 (OnVertex) on face 2892: expected_lei_count != _gv.local_edges.size(): 19 != 5, pos_angleSum: 29.8451�[0m
########### MeshExtractor #############
#Face -GridVertices: 536
#Edge -GridVertices: 2
#Vertex-GridVertices: 31
ERROR: found invalid connection which does not have a reverse...
vertex 316, 0 found vertex 536, 1
vertex 536, 1 found vertex 165, 1
types are OnFace, OnEdge, OnFace
�[41mWarning: When tracing from GV 316, LEI 0 I hit GV 536, LEI 1.
However, this GV is already connected to GV 165, LEI 1�[0m

Additional debug info

Grid Vertex 316
GridVertex {OnFace, non-boundary, heh: 18710, uv pos: (Point_2(2, 1)), 3d pos: (15.8813 4.00972 3.04271), local_edges: [
LocalEdgeInfo { fh_from.idx(): 4676, uv_from: (Point_2(2, 1)), uv_intended_to: (Point_2(3, 1)), uv_to: (Point_2(2, 1)), connected_to_idx: 536, orientation_idx: 1, face_constructed: 0, accumulated_tf: Rotation: 3, Translation: 2/2, primary: 1, id: 1264 },
LocalEdgeInfo { fh_from.idx(): 4676, uv_from: (Point_2(2, 1)), uv_intended_to: (Point_2(2, 2)), uv_to: (Point_2(2, 2)), connected_to_idx: 69, orientation_idx: 3, face_constructed: 0, accumulated_tf: Rotation: 0, Translation: 0/0, primary: 0, id: 1265 },
LocalEdgeInfo { fh_from.idx(): 4676, uv_from: (Point_2(2, 1)), uv_intended_to: (Point_2(1, 1)), uv_to: (Point_2(1, 1)), connected_to_idx: 252, orientation_idx: 0, face_constructed: 0, accumulated_tf: Rotation: 0, Translation: 0/0, primary: 0, id: 1266 },
LocalEdgeInfo { fh_from.idx(): 4676, uv_from: (Point_2(2, 1)), uv_intended_to: (Point_2(2, 0)), uv_to: (Point_2(2, 0)), connected_to_idx: 199, orientation_idx: 1, face_constructed: 0, accumulated_tf: Rotation: 0, Translation: 0/0, primary: 0, id: 1267 }
] }

Grid Vertex 536
GridVertex {OnEdge, non-boundary, heh: 5214, uv pos: (Point_2(3, 0)), 3d pos: (15.6063 3.65361 2.66772), local_edges: [
LocalEdgeInfo { fh_from.idx(): 950, uv_from: (Point_2(3, 0)), uv_intended_to: (Point_2(2, 0)), uv_to: (Point_2(nan, nan)), connected_to_idx: -1, orientation_idx: -1, face_constructed: 0, accumulated_tf: Rotation: 0, Translation: 0/0, primary: 0, id: 2144 },
LocalEdgeInfo { fh_from.idx(): 950, uv_from: (Point_2(3, 0)), uv_intended_to: (Point_2(3, -1)), uv_to: (Point_2(3, -1)), connected_to_idx: 165, orientation_idx: 1, face_constructed: 0, accumulated_tf: Rotation: 0, Translation: 0/0, primary: 0, id: 2145 },
LocalEdgeInfo { fh_from.idx(): 1366, uv_from: (Point_2(2, 1)), uv_intended_to: (Point_2(2, 2)), uv_to: (Point_2(nan, nan)), connected_to_idx: -1, orientation_idx: -1, face_constructed: 0, accumulated_tf: Rotation: 0, Translation: 0/0, primary: 0, id: 2146 },
LocalEdgeInfo { fh_from.idx(): 1366, uv_from: (Point_2(2, 1)), uv_intended_to: (Point_2(3, 1)), uv_to: (Point_2(nan, nan)), connected_to_idx: -1, orientation_idx: -1, face_constructed: 0, accumulated_tf: Rotation: 0, Translation: 0/0, primary: 0, id: 2147 }
] }

Grid Vertex 165
GridVertex {OnFace, non-boundary, heh: 11198, uv pos: (Point_2(3, -1)), 3d pos: (13.9937 3.65106 2.97779), local_edges: [
LocalEdgeInfo { fh_from.idx(): 2263, uv_from: (Point_2(3, -1)), uv_intended_to: (Point_2(4, -1)), uv_to: (Point_2(4, -1)), connected_to_idx: 509, orientation_idx: 2, face_constructed: 0, accumulated_tf: Rotation: 0, Translation: 0/0, primary: 1, id: 660 },
LocalEdgeInfo { fh_from.idx(): 2263, uv_from: (Point_2(3, -1)), uv_intended_to: (Point_2(3, 0)), uv_to: (Point_2(3, 0)), connected_to_idx: 536, orientation_idx: 1, face_constructed: 0, accumulated_tf: Rotation: 0, Translation: 0/0, primary: 1, id: 661 },
LocalEdgeInfo { fh_from.idx(): 2263, uv_from: (Point_2(3, -1)), uv_intended_to: (Point_2(2, -1)), uv_to: (Point_2(2, -1)), connected_to_idx: 243, orientation_idx: 0, face_constructed: 0, accumulated_tf: Rotation: 0, Translation: 0/0, primary: 1, id: 662 },
LocalEdgeInfo { fh_from.idx(): 2263, uv_from: (Point_2(3, -1)), uv_intended_to: (Point_2(3, -2)), uv_to: (Point_2(3, -2)), connected_to_idx: 202, orientation_idx: 1, face_constructed: 0, accumulated_tf: Rotation: 0, Translation: 0/0, primary: 1, id: 663 }
] }

ERROR: found invalid connection which does not have a reverse...
vertex 536, 3 found vertex 316, 0
vertex 316, 0 found vertex 536, 1
types are OnEdge, OnFace, OnEdge
Assertion failed: gvertices_[target.connected_to_idx].local_edges[target.orientation_idx].accumulated_tf == TF::IDENTITY, file f:\libqex\src\MeshExtractorT.cc, line 1534`

compiling errors

I have install OpenMesh2.4.1
when build the source of libQEx, it come the error as:
/libQEx/interfaces/c/../../src/MeshExtractorT.cc:1000:27: error： converting ‘OpenMesh::ArrayItems::Halfedge to const HEH {aka const OpenMesh::HalfedgeHandle}’
In file included from /home/yibing/libQEx/interfaces/c/../../src/MeshExtractorT.hh:665:0,

cmmdline tool demo not working

Hi, the repo builds without errors but the demo never completes, hanging indefinitely at:
MeshDecimator::decimate() collapsed __ edges.
Output prior to the halting includes:
ERROR in transition function: 9.22337e+18
ERROR in inverse transition function: 9.22337e+18
constructed 157 valid transition functions -> 29 invalid ones
test exactness of transition functions before preprocessing...
... done!
found 186 inexact transitions in input with max deviation 9.22337e+18
QuadMeshExtraction Preprocess maxmial uv deviaton: 4.29497e+10
test exactness of transition functions...
ERROR: values are not identical after preprocessing, diffs are (6.44245e+09,6.44245e+09) and (0,0)
Collapsing inconsistent edge. Length of he0 = 0, length of he1 = 3.68935e+19
If this happens prior to truncation it's ok. If it happens afterwards, this is a bug.

I have OpenMesh installed. What exactly is meant when you refer to the path to OpenMesh binaries? Any assistance in this installation would be greatly appreciated as I'd love to use this technique in my research. Thanks.

demo_minimal_c not working

I was able to get OpenMesh and libQex to build just fine, but when I try to run demo_minimal_c the only output I get is

Got the following output quad mesh:

I modified the source file to print quadMesh.quad_count and I get

quadMesh.quad_count = 0

ERROR: non-identity transition function cannot have a different rotation than 1,2,3: 0, 1, 1

when i use libQEx, it came with many "non-identity transition function cannot have a different rotation than 1,2,3:". what does this mean? how can i fix it?