New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Kenya Rutherford


Kenya Rutherford
GPA 3.79

X. Li

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

X. Li
Class Notes
25 ?




Popular in Course

Popular in Electrical Engineering

This 16 page Class Notes was uploaded by Kenya Rutherford on Tuesday October 13, 2015. The Class Notes belongs to EE 4700 at Louisiana State University taught by X. Li in Fall. Since its upload, it has received 24 views. For similar materials see /class/223165/ee-4700-louisiana-state-university in Electrical Engineering at Louisiana State University.




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/13/15
HalfEdge Structure for Triangle Meshes Xin Shane Li xinlilsuedu Course Email ee4700fal2009gmailcom Lectures Tu Th 1210pm 130pm 2150 PaTrick Taylor Hall Office Hours Tu Th 930am 1100am 313 ElecTrical Engineering Building Louisiana STaTe UniversiTy K hTTpwwwece3ueduxinIiTeachingEE47OOFaII2009hTm j Last class Wha r is Compu rer Graphics 0 Various applica rions of compu rer graphics Techniques movies games scien rific research engineering design vir rual reali ry CG pipeline Da ra acquisi rion 9 modeling rocessini 9 out u rrenderini Shape represen ra rion me rhods overview par r Polygonal meshes CSG me rhod Implici r represen ra rion Today Ou rline Shape representation me rhods overview cont Spa rial par ri rioning me rhod 9 quadTree 2D oc r rree 3D will revisi r if when we do animation and collision deTeCTion Spline represen ra rion in a few weeks Skele ron represen ra rion 6 will revisi r if when we do shape comparison animaTion Generalized cylinders represen ra rion Focus on HalfEdge Da ra S rruc rure Halfedge da ra s rruc rure Triangle mesh as a general represen ra rion scheme before you can I roJram ever ThinJ QuadTree Rep 0 A hierarchical sTrucTure based on divideandconquer subdivision for 2D shapes 0 A quadTree 9 hierarchically represenT a shape in The plane 0 Each cell ma be full arTia fuor em T de endin on how much of Theycell inTerlsDecTs The shape p y p g o A parTially full cell is recursively subdivided inTo subcells o ConTinue The subdivision unTi all quadranTs are homogeneous eiTher full or empTy or a predeTermined cuToff depTh is reached J Warnock A Hidden Surface Algorithm for Computer Generated Half Tone Pictures Technical Report Univ of Utah 1969 chree Rep 0 Similar To The quad rree bu r in 3D 6 22 3i Each cell 9 8 children 1121 l 0 Much research on efficienfly sforing and quotLA 1l K processing quadfrees and ocfrees 4 5 sJ eg Boolean operafions Neighbor finding Only horizonfalverfical cuffing one varianf mefhods 9Binary spaceparfifioning free divide The space info pairs of subspaces by an arbifrary plane A 2D BSP free Skeleton Rep El Skele ron 9 a Thin 1D representation of 2D3D Objecfs El Skele ron Rep of a Shape a hierarchical set of bones a r rached skins El Widely used in animation ma rching objecf recogni rion El A re resenTaTion good for modeling El A shape 2 axis a crosssecTion curve a Generalized Cylinder Rep ar TiculaTed objecTs scaling funcTion Good for39 symmetric shapes wiTh few local deTails and with clear39 skele39ral sTr39ucTur39e Widely wed in vision community for39 shape recognition and shape recover 6C axis generaTion l CrossSecTions GeneraTion j HalfEdge Data S rruc rure 39 A common way To represen r Triangular mesh for geome rric processing 0 we focus on Trianglemesh here i r works for general polygonal mesh 0 3D analogy halfface da ra s rruc rure for re rrahedral mesh Effective for main raining incidence informa rion of ver rices 0 Efficien r local Traversal 0 Low spa rial COST 0 Suppor ring dynamic local upda resmanipula rions edge collapse ver rex spli r e rc QuesTions of mesh rep 0 Remember when we sTore a Triangle mesh by 9A verTex Table geomeTry A faceT Table connecTiviTy 0 Enough To preserve all The informaTion buT how will you use This represenTaTion To solve The following quesTions and how efficienT your algoriThm can be WheTher a given verTex is on The boundary 5g WhaT are The 1rIng neighboring verTIces of a verTex ZI V How To Traverse from one verTex To anoTher verTex 74 We need to answer these questions when we manipulate meshes e g computing surface normal detecting how curved a region is o BuT very difficulT by jusT looking aT Those Two Tables 0 Need a more efficienT represenTaTion k HalfEdge Data Structure Looking aT a Triangle mesh EIZ verTices share an edge 2 faces share an edge Deach face has 3 verTices and 3 ed es gtWe can sTore all incidence information and build a big neTwork EIBuT a verTex can have many neighboring verTices edges and faces gtS roring half edgesquot is simply enough EIEach edge has 2 half edges The boundary edge only has 1 VK 0 mm gt Hamdae Face Nye HalfEdge DaTa STr39ucTur39e conT EIFor39 each edge CIiT has 2 halfedges The boundary edge has 1 CIThey are called Twins To each oTher39 l7O EIFor39 each halfedge Elbounds 1 face and 1 edge 9 a face poinTer39 an edge pounTer39 r39especnvely Elhas one origin and one Tar39geT ver39Tex 9 a ver39Tex poi Men for39 The Tar39geT c Vertex Mme gtTo be able To walk around a face A We EIiT has a poinTer39 To The nexT halfedge Elalso a poinTer39 To The previous halfedge EIFor39 each face EITo simply access all iTs incidenT elemenTs 9 Only need a pounTer39 To any halfedge EIFor39 each vertex CIA poinTer39 To an ar39biTr39ar39y halfedge ThaT has iT as The TargeT EIRecor39d iTs 3D coor39dinaTes iTs geomeTr39ic locaTion Note the directions of those half edges bounding a face HaltEdge Data Structure example 9 Containers to store primitives TheVertex Container v1 v6 The Face Container f1v1v2v3 f5v4v3v6 Remember the HaltEdge direction V1 2 or a v1 around each face Should be consistent e C W in our confi1uration ri1ht hand rule Note the container could be array list binary search ree it depends but usually List is good enough HalfEdge Data Structure example 9 Con rainers To sfore primi rives v1v6 TheVertex Container The f1v1v2v3 f5v4v3v6 The Face Container 9 Relationship between primi rives HalfEdge Examples 2 iquot F F Using HalfEdge Data Structure How to check whether a vertexedgetace is on the boundary Simply check whether an edge has one halfedge How to find the onering neighboring vertices of a vertex v e halfedge targeting v i e ivell Je next then twino How to travel along the boundary get a boundary vertex and its most CLW outwards halfedge iteratively do next twin nexto Some other operations such as subdivisionsimplification Half Edge Resources for HalfEdgequot Data Structure To geT beTTer undersTanding abouT iT you can 1 Download and read codes from htt wwwecelsueduxinliteachin MeshLibSim lezi 2 Google Halfedge daTa sTrucTure for TuTorials 3 In CompuTaTional GeomeTry iT is well n as doublyconnecTed edge lisT sTrucTure exTendible To general polygonal mesh Comp Geom book Computational Geometry Algorithms and Applications by M de Berg M van Kreveld M Overmars and O Schwarzkopf SpringerVerlag HinT for 1 El 60 Through The read meThod in The class I Face Mesh see how we build up halfedge sTrucTure from The verTex Table face Table El Go Through iteratorsh see whaT iTeraTor you can use To help you Traverse around HalfEdge Some other issues Next class How to write a simple OpenGL program to render a Triangle mesh take our time to read halfede data structure not usin it here et On the other hand if you hate data structure and programming for people don39t use OpenGL but work on 3D shapes and meshes El Store meshes with 2 tables u3e some viewersI ro rams written b others as a black box to vi3ualize even edit the model only manipulate compute over and analyze the file El Before we can design a fully robustpowerful GUI and vi3ualization system which we ma kee39 doin throuh the Semester here are somethin for us to firstl I la a little bit with triangle meshes and 3D shapes El Some mesh data m format can be downloaded at httpwwwecesueduxinIiteachinqmeshdata1zig El A small viewer G3dOGLexequot for m format mesh can be downloaded at httpwwwecesueduxinIiToolsG3dOGLexe El Many 3D triangle mesh models online but in different format El Stanford 3D Scanning Repository httpgraghicsstanfordedudata3Dscanreg El Aim5hape Re ositor httpshagesaimatshagenetindexth gt Part of hw 1 convert meshes with other formats to format will be explained later so that they are compatible to our language


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.