Description

Quadrilateral and Tetrahedral Network Stripification Utilizing the 2-Variable Dividing of the Double Chart Pablo Diaz-Gutierrez M. Gopi College of California, Irvine Issue portrayal Data : Quadrilateral or Tetrahedral network Yield : Parcel the information network into primitive strip(s).

Transcripts

Quadrilateral and Tetrahedral Mesh Stripification Using the 2-Factor Partitioning of the Dual Graph Pablo Diaz-Gutierrez M. Gopi University of California, Irvine

Problem portrayal Input : Quadrilateral or Tetrahedral cross section Output : Partition the data network into primitive strip(s). Approach : Use a chart coordinating calculation on the double diagram of the cross section. http://graphics.ics.uci.edu

Problem depiction Dual charts Every quad/tetrahedron is a hub in the double diagram. Circular segments between these hubs if the comparing cross section components are neighboring in the lattice. From a solid shape to its double diagram http://graphics.ics.uci.edu

Problem portrayal Dual charts: properties Dual quad-chart : Dual diagram of a quadrilateral complex work Every hub has degree four . (4-customary) Dual tetra-diagram : Dual chart of a tetrahedral work Every hub has degree four or less . http://graphics.ics.uci.edu

Problem depiction Graph factorization K-variable of a chart G: A spreading over, k-general sub-diagram of G 1-element (flawless coordinating) 2-component 3-element http://graphics.ics.uci.edu

Problem portrayal Our Solution A 2-element F of a chart G decides an arrangement of disjoint circles in G Finding a 2-element in the 4-normal double diagram of the cross section segments the lattice into strip circles of cross section primitives. http://graphics.ics.uci.edu

Complementary strips A 2-element characterizes 2 corresponding arrangements of disjoint circles. http://graphics.ics.uci.edu

Talk diagram Problem portrayal Related work Stripification 2-pass coordinating Template substitution Merging strips Nodal simplex preparing Simplex subdivision Results Conclusion, Q&A http://graphics.ics.uci.edu

Relevant related work Several papers on triangle stripification [Gopi and Eppstein 04], and so on [Pascucci 04] on GPU for isosurface extraction Tetra strips to lessen BW 2-considering of meager charts [Pandurangan 05] Images from [Gopi et al. 04] and Pascucci 04] http://graphics.ics.uci.edu

Talk layout Problem portrayal Related work Stripification 2-pass coordinating Template substitution Merging strips Nodal simplex handling Simplex subdivision Results Conclusion, Q&A http://graphics.ics.uci.edu

Stripification Two procedures 2-pass coordinating strategy Straightforward Fast Not generally material Template substitution technique More muddled Slower (issue size grows 18x) Universal http://graphics.ics.uci.edu

Perfect Matching A 1-component of a diagram is known as an immaculate coordinating. Flawless coordinating in a 3-normal diagram http://graphics.ics.uci.edu

Talk plot Problem portrayal Related work Stripification 2-pass coordinating Template substitution Merging strips Nodal simplex handling Simplex subdivision Results Conclusion, Q&A http://graphics.ics.uci.edu

Stripification 2-pass coordinating strategy Repeat twice on a 4-customary chart: Find an immaculate coordinating. Evacuate the coordinated edges http://graphics.ics.uci.edu

Graph with a 2-consider yet without an impeccable coordinating Stripification 2-pass coordinating system Advantages: Fast Existing code for flawless coordinating Simple to actualize Disadvantages Does not take a shot at charts with odd # of vertices Â© Algorithmic Solutions http://graphics.ics.uci.edu

Talk plot Problem depiction Related work Stripification 2-pass coordinating Template substitution Merging strips Nodal simplex preparing Simplex subdivision Results Conclusion, Q&A http://graphics.ics.uci.edu

Stripification Template substitution technique Transform ( swell ) diagram G to lower degree, bigger diagram Gâ G has degree 4 and less Gâ has degree 3 and less Perfect coordinating in Gâ â 2-element in G Induce 2-element Inflate Gâ Perfect coordinating http://graphics.ics.uci.edu

Stripification Template substitution strategy Transformation by substituting every vertex V in G by a layout Vâ (extend V) G Induce 2-variable Inflate Gâ Perfect coordinating http://graphics.ics.uci.edu

Stripification Template substitution technique DOPES V Vâ http://graphics.ics.uci.edu

Stripification Template substitution technique (2-element from coordinating) Theorem : Gâ has an immaculate coordinating iff G has 2-element G Gâ http://graphics.ics.uci.edu

Template substitution Simple case http://graphics.ics.uci.edu

Talk diagram Problem portrayal Related work Stripification 2-pass coordinating Template substitution Merging strips Nodal simplex handling Simplex subdivision Results Conclusion, Q&A http://graphics.ics.uci.edu

Merging strips Disjoint (cyclic) strips in a 4-general chart (i.e. quad-diagram ) Disjoint strips in a degree-4-and-less chart (i.e. tetra-diagram ) http://graphics.ics.uci.edu

Merging strips Strip similarity Loop + circle = circle Loop + direct = straight Linear + direct - > 2 direct strips! (pointless) http://graphics.ics.uci.edu

Talk layout Problem portrayal Related work Stripification 2-pass coordinating Template substitution Merging strips Nodal simplex handling Simplex subdivision Results Conclusion, Q&A http://graphics.ics.uci.edu

Merging strips nodal simplex preparing: chart A nodal simplex: A (n-2) dimensional simplex A vertex in a quad cross section, or an edge in a tetrahedral lattice Around which matches exchange Incident cycles are one of a kind Toggle coordinating Strip circles A face in the double diagram comparing to a nodal simplex in the cross section http://graphics.ics.uci.edu

Merging strips nodal simplex handling: geometric acknowledgment on quads Nodal vertex http://graphics.ics.uci.edu

Talk plot Problem depiction Related work Stripification 2-pass coordinating Template substitution Merging strips Nodal simplex preparing Simplex subdivision Results Conclusion, Q&A http://graphics.ics.uci.edu

Merging strips Mesh subdivision Often there are insufficient nodal simplices despite everything we have to lessen #strips Subdivide two nearby primitives having a place with diverse cycles Reassign double edge matchings to consolidation cycles http://graphics.ics.uci.edu

Merging strips Dual Graph Subdivisions Dual Tetra Graph (Non-planar subdivision) Dual Quad Graph http://graphics.ics.uci.edu

Merging strips Quadrilateral subdivision (reassigning coordinating) After subdividing, distinguish a nodal simplex Apply nodal simplex preparing to union strips http://graphics.ics.uci.edu

Merging strips Quadrilateral subdivision (geometric acknowledgment) http://graphics.ics.uci.edu

Merging strips Tetrahedral subdivision (double chart re-coordinating) C A B A B a c b a c b Aâ Bâ Aâ Bâ Câ http://graphics.ics.uci.edu

Talk diagram Problem portrayal Related work Stripification 2-pass coordinating Template substitution Merging strips Nodal simplex handling Simplex subdivision Results Conclusion, Q&A http://graphics.ics.uci.edu

Results Tetrahedral stripification table http://graphics.ics.uci.edu

Results Quadrilateral strips http://graphics.ics.uci.edu

Results Quadrilateral strips http://graphics.ics.uci.edu

Results Tetrahedral strips http://graphics.ics.uci.edu

Talk plot Problem depiction Related work Stripification 2-pass coordinating Template substitution Merging strips Nodal simplex handling Simplex subdivision Results Conclusion, Q&A http://graphics.ics.uci.edu

Summary & conclusion Two calculations for 2-factorization of charts of degree 4 and less Unified methodology for quadrilateral and tetrahedral stripification Subdivision systems for decrease of number of tetrahedral and quadrilateral strips http://graphics.ics.uci.edu

Future work Tetrahedral cross section pressure utilizing strips Investigate surmised coordinating calculations Reduce number of strips without subdivision (keeping up unique lattice) http://graphics.ics.uci.edu

Acknowledgments ICS Computer Graphics Lab @ UCI http://graphics.ics.uci.edu http://graphics.ics.uci.edu

The End Thanks for tuning in!! Questions? Remarks? Rectifications? Recommendations? Grievances? Divagations? http://graphics.ics.uci.edu

http://graphics.ics.uci.edu

E D BCDE C A B ABCD ABED Dual charts Every double quad-diagram is 4-normal But not every 4-general diagram is the double of a substantial quadrangulated complex ? http://graphics.ics.uci.edu

E D BCDE C A B ABCD ABED Stripification 2-pass coordinating technique ? http://graphics.ics.uci.edu

Merging strips nodal simplex preparing: tetrahedra (n-2) dimensional nodal simplex Geometric edge Dual edges relate to faces of tetrahedra Matching of double edges (primal appearances) is flipped around nodal edge Nodal edge Faces of tetrahedra Nodal simplex handling in a double tetra-diagram http://graphics.ics.uci.edu

Merging strips Tetrahedral (subdivision in double chart) C A B a c b Aâ Bâ Câ http://graphics.ics.uci.edu

Merging strips Tetrahedral subdivision (geometric elucidation) Two tetrahedra split into 6 (3 every) Red line : nodal simplex (a hub) A,B,C : Graph edges (countenances of tetrahedra) A C B http://graphics.ics.uci.edu

Merging strips Initial contemplations We have various primitive strips Want to converge into less strips Issues: Can we adjust the cross sections? Distinctive sorts of strips