Quadrilateral and Tetrahedral Network Stripification Utilizing the 2-Element Dividing of the Double Chart.


62 views
Uploaded on:
Category: Music / Dance
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
Slide 1

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

Slide 2

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

Slide 3

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

Slide 4

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

Slide 5

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

Slide 6

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

Slide 7

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

Slide 8

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

Slide 9

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

Slide 10

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

Slide 11

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

Slide 12

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

Slide 13

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

Slide 14

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

Slide 15

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

Slide 16

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

Slide 17

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

Slide 18

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

Slide 19

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

Slide 20

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

Slide 21

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

Slide 22

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

Slide 23

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

Slide 24

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

Slide 25

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

Slide 26

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

Slide 27

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

Slide 28

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

Slide 29

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

Slide 30

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

Slide 31

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

Slide 32

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

Slide 33

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

Slide 34

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

Slide 35

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

Slide 36

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

Slide 37

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

Slide 38

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

Slide 39

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

Slide 40

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

Slide 41

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

Slide 42

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

Slide 43

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

Slide 44

http://graphics.ics.uci.edu

Slide 45

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

Slide 46

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

Slide 47

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

Slide 48

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

Slide 49

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

Slide 50

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

Recommended
View more...