33:
20:
144:
of faces, edges, and vertices when three or more surfaces come together and meet at a common edge. The ordering is such that the surfaces are ordered counter-clockwise with respect to the innate orientation of the intersection edge. Moreover the representation allows numerically unstable situations
191:
Finally, the structure of the edge record is as follows. An edge is assumed to be directed. The edge record contains two references to the vertices that make up the endpoints of the edge, two references to the faces on either side of the edge, and four references to the previous and next edges
199:
class Edge { Vertex *vert_origin, *vert_destination; Face *face_left, *face_right; Edge *edge_left_cw, *edge_left_ccw, *edge_right_cw, *edge_right_ccw; } class Vertex { float x, y, z; Edge *edge; } class Face { Edge *edge; }
187:
Similarly each face record only stores a reference to one of the edges surrounding the face. There is no need to store the direction of the edge relative to the face (CCW or CW) as the face can be trivially compared to the edge's own left and right faces to obtain this
155:
The winged edge data structure allows for quick traversal between faces, edges, and vertices due to the explicitly linked structure of the network. It serves adjacency queries in constant time with little storage overhead. This rich form of specifying an
116:
of a model. Three types of records are used: vertex records, edge records, and face records. Given a reference to an edge record, one can answer several types of adjacency queries (queries about neighboring edges, vertices and faces) in
184:
For each vertex, its record stores only the vertex's position (e.g. coordinates) and a reference to one incident edge. The other edges can be found by following further references in the edge.
367:
196:
In short, the edge record has references to all its adjacent records, both when traversing around an adjacent vertex or around an adjacent face.
281:
76:
54:
150:
362:
219:
229:
209:
169:
47:
41:
258:
317:
Polyhedral Data
Structures: CS488/688: Introduction to Interactive Computer Graphics, University of Waterloo
224:
109:
58:
333:
300:
244:
122:
287:
214:
277:
157:
90:
312:
269:
180:
The face and vertex records are relatively simple, while the edge record is more complex.
23:
Graphical representation of an edge record. Note that the edge references look like wings.
266:
AFIPS '75: Proceedings of the May 19-22, 1975, national computer conference and exposition
105:
137:
97:
356:
118:
291:
165:
161:
101:
19:
273:
149:
141:
113:
121:. This kind of adjacency information is useful for algorithms such as
164:
such as a node and element list, or the implied connectivity of a
18:
16:
Data structure for representing polygon meshes in computer memory
26:
168:. An alternative to the winged edge data structure is the
252:(Technical report). Stanford University. CS-TR-72-320.
305:
CS3621 Introduction to
Computing with Geometry Notes
259:"A polyhedron representation for computer vision"
8:
160:is in contrast to simpler specifications of
77:Learn how and when to remove this message
40:This article includes a list of general
325:
140:explicitly describes the geometry and
246:Winged Edge Polyhedron Representation
7:
307:. Michigan Technological University.
192:surrounding the left and right face.
112:and describes both the geometry and
46:it lacks sufficient corresponding
14:
368:Computer graphics data structures
334:"The Winged-Edge Data Structure"
301:"The Winged-Edge Data Structure"
148:
31:
268:. ACM Press. pp. 589–596.
1:
257:Baumgart, Bruce G. (1975).
243:Baumgart, Bruce G. (1972).
145:like that depicted below.
384:
220:Doubly connected edge list
230:Half-edge data structure
210:Quad-edge data structure
176:Structure and pseudocode
170:Half-edge data structure
274:10.1145/1499949.1500071
225:Doubly linked face list
110:boundary representation
61:more precise citations.
100:is a way to represent
24:
363:Computer-aided design
319:. University of Pisa.
299:Shene, C.-K. (2011).
22:
123:subdivision surface
215:Combinatorial maps
108:. It is a type of
25:
283:978-1-4503-7919-9
158:unstructured grid
91:computer graphics
87:
86:
79:
375:
348:
347:
345:
344:
330:
320:
308:
295:
263:
253:
251:
152:
82:
75:
71:
68:
62:
57:this article by
48:inline citations
35:
34:
27:
383:
382:
378:
377:
376:
374:
373:
372:
353:
352:
351:
342:
340:
332:
331:
327:
323:
311:
298:
284:
261:
256:
249:
242:
238:
206:
201:
178:
131:
106:computer memory
83:
72:
66:
63:
53:Please help to
52:
36:
32:
17:
12:
11:
5:
381:
379:
371:
370:
365:
355:
354:
350:
349:
324:
322:
321:
309:
296:
282:
254:
239:
237:
236:External links
234:
233:
232:
227:
222:
217:
212:
205:
202:
198:
194:
193:
189:
185:
177:
174:
162:polygon meshes
138:data structure
130:
127:
102:polygon meshes
98:data structure
85:
84:
39:
37:
30:
15:
13:
10:
9:
6:
4:
3:
2:
380:
369:
366:
364:
361:
360:
358:
339:
338:pages.mtu.edu
335:
329:
326:
318:
314:
313:"Winged Edge"
310:
306:
302:
297:
293:
289:
285:
279:
275:
271:
267:
260:
255:
248:
247:
241:
240:
235:
231:
228:
226:
223:
221:
218:
216:
213:
211:
208:
207:
203:
197:
190:
186:
183:
182:
181:
175:
173:
171:
167:
163:
159:
153:
151:
146:
143:
139:
136:
128:
126:
124:
120:
119:constant time
115:
111:
107:
103:
99:
96:
92:
81:
78:
70:
60:
56:
50:
49:
43:
38:
29:
28:
21:
341:. Retrieved
337:
328:
316:
304:
265:
245:
195:
188:information.
179:
166:regular grid
154:
147:
134:
132:
94:
88:
73:
64:
45:
135:winged edge
95:winged edge
59:introducing
357:Categories
343:2024-03-04
42:references
67:July 2018
204:See also
142:topology
129:Features
114:topology
292:9040571
55:improve
290:
280:
93:, the
44:, but
288:S2CID
262:(PDF)
250:(PDF)
278:ISBN
133:The
270:doi
104:in
89:In
359::
336:.
315:.
303:.
286:.
276:.
264:.
172:.
125:.
346:.
294:.
272::
80:)
74:(
69:)
65:(
51:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
