Can someone turn this into a PDF for me?

This probably should be called

RELATION OF WINGS POLYGONS TO BLENDER POLYGONS

But its mostly just structured thought processes for

considering the relation of winged edge polygons to

representations assumed of blender's polygons.

It will change as more is known about the actual representation

of winged-edges and blender's polygons..

Images that will help out in understanding the following:

http://www.bl3nder.com/UML/ModelsInBlen ... mRRose.jpg

http://www.bl3nder.com/UML/ModelsInWing ... rgoUML.jpg

These are the data files produced by the CASE tools that

produced the images above.. Just in case you have ArgoUML (0 dollar app) or Rational Rose (4000 dollar app)

http://www.bl3nder.com/UML/WingedEdgeChart.zargo

Phttp://www.bl3nder.com/UML/olygonsInBlender.mdl

The diagrams are relatively simple because the concepts are relatively

simple..

(I've revisied this several times.. I should do a UML representation

of the concept, which I will do in the next hour..)

To summarize the following brain dump.. I was thinking of the space

usage complication of winged edges, how different the

representation of a winged edge is from the way blender stores polygons,

what the time complexity is as a result of going with the winged edge

as opposed to the blender's polygons, also what kinds of

objects are possible in blender's model that are not possible with a winged edge..

The brain dump shows all my thinking, wrong or right, based on

what I know about data structures and alternate ways of representing

3D geometry with nodes and pointers. This isn't about the

representation of the geometry in a 3D space, UV texturing coordinate, color vertices,

and other data that hangs on this structure, this is more a discussion of

ease of access of edges, vertices, and faces and time it takes to

perform operations on them as well as the space requirements for

them. I did not discuss this to the complete conclusion as I would

as others to consider these issues when considering whether to

implement winged edges or similar data structures over the

way blender stores these structures now.

I determined that a data structure that does not allow for

efficient access will require multiple passes to derive relationships

that a data structure with efficient access gets for free. I am assuming

blender's data structures for polygons are inefficient in

access of data and winged edges are more efficient. Efficient

access implies more pointers, as a pointer allows a direct

reference to another data structure without having to know something

about the geometry being represented.

I did not question maintenence of the data structure, which could

make working with the polygons in a highly connected pointer-based

structure more somewhat inefficient for insertion and deletion

operations to faces and edges. So the sides that can be taken,

do we want space efficiency or time efficiency, and does it matter

that we have a

constant amount of inefficiency dealing with pointers as

opposed to the inefficiency with dealing without them.

The added bonus of having pointers in the structures would

be being able to have winged edges, the problems that

could come from having winged edges if implemented with

memory pointers and not array indices could result in memory errors

and core-dumps due to improper handling of special cases.

This adhoc analysis just serves as a lesson for the users in the

considerations the program developers will have contemplate when

going to a winged edge system. Also maybe as a starter for those

considering use of winged edges.

I only consider myself an intense thinker but not knowledgable about

the data structures that blender actually uses and the structures that

winged edges use, but merely to consider what the concerns

are that exist when thinking about data structures.. I don't do any

runtime analysis, just intuitive bit-twiddling with the data structures

and considerations of a simple polygon model of a cube..

--------------------

I've been using Wings this morning, I really came up to find a

Wings -> Blender export program.. I think everyone knows the advantages

of a wings based modeller. There is documentation

on the net about how things are organized in a Winged-Edge modeller.

I imagine its just a matter of having faces constructed from edges

instead of vertices, as it is now, then adjoing the edges with vertices.

Something that you will notice in the "Wings" modeller is there is

different functions for whether you are using edges, vertices or faces.

The particularly useful functions to me are the extrusion via normal,

dissolving (if just to simplify the visual space), subdividing edges

independent of face subdivision (that is mandatory in blender), flattening

of faces, bump, bevel.. Functions I miss when working in Wings are the usual

ways in blender to constrain transformations via closest axis,

use of absolute axis for transformations only allows you to

adjust placement, scale, rotation in an unintuitive way, blender's

handling of constrained translation/rotation is more intuitive

and not conceiveably more complex than a dot-product on the

axis-planes to determine the constraining axis. Anyhow I would have

rather had the winged edge tools in blender's interface as wings has

horrible means of orientation and navigation, it should really be

a part of blender and not bother to attempt development of its own

interface as the developers make bad judgements about efficiency

of use.

A lot of the tools in Wings are made possible by being able to know something

about the geometry via the edges.. But some of the features are features of wings

and not a result of the data structure relationships in wings. Like being

able to work on multiple faces at the same time, because there is a distinction

made between extruding individual faces or by region (sets of faces that

have common edges). This distinction can be made in blender without

implementing winged edges.. But edges in blender are not seen as primitives

as they are in wings. Edges are a byproduct of making faces from vertices,

so to define a edge to work on you must specify the vertices that connect

the edges. If you want to specify two edges of a triangle in blender, its

impossible because you need to specify all the vertices in the triangle,

so to extrude an edge you must specify two vertices but to extrude two edges

you have to specify vertices seperately because one vertex may share both

edges.. If blender supported edge based modelling, specifying edges would

not be hard, nor would subdividing edges

independent of faces, since faces are defined from edges not vertices.

Subdivide an edge and insert the new edge into the face's definition. What

does not seem to be a part of

the definition of a winged edge is the idea that a face can contain more

than 4 edges, but this may have just been the paper I was looking at.

There seems to be a problem, people say about winged edge objects that

are not encased in a volume (is the concern the same as with booleans?)..

If this is a concern, considering that a winged edge is an edge with two

pointers, It would seem that the minimal special case of a

single quad could be handled as two quads that are single-sided, the edges

can point to each quad, thus satisfying an assumption that each edge

points to two different faces, if that is a requirement.

Also edges could point to NULL's, it would just require

handling more special cases. A winged-edge seems to be just a different

way of relating information that already exists in the structure of a

polygonal object. The winged-edge gets its name from the edges

having pointers (references, or links) to left and right faces that

share the edge.. What advantage this provides is not obvious to me

other than making the data structure easy to traverse from

edge to face and back to the edge.

Its like a extension on the idea of a doublely circular linked list where

the node at the end of the list points to the beginning and the end. Its

one way to implement a bi-directional queue. But its advantage

is ease of insertions, searching it is not as good as an array because

one must traverse the linked list. Think of a winged edge as a circular

linked list of edges with every odd node being a face, and that the last

face's edge is the same as the first face's edge. Its a bit more complex

than this, each face points to a number edges that define it, and each edge

contains pointers to the vertices that define it. You could

also consider the tree data structure which is made up of nodes with

double pointers, one to the left node and one to the right. But the nodes

that are faces could contain pointers that bind parts of the tree together

in unpredictable ways. So it could be seen as a efficient storage

method that allows for relative ease of access of edges, faces and vertices..

*We could attain direct access to the edges, faces, vertices *

through the use of arrays with pointers in them, so that any vertex,

edge or face could be referenced immediately without

going through the linked data structure. So traversal would be

possible with arrays or with relative pointers to faces/edges/vertices
Anyhow, the relationship looks something like this for

a winged-edge structure..

E = edge, V = vertex, F = face

Ev -> V1, V2 // each edge can only point to two vertices

Ee -> F1 , F2 // edges can only point to two faces..

F -> E1, E2, E3, (E4) // maximum of a quad, minimum of a triangle

Its possible the vertices have pointers back to the

edges that own them, that would be a pointer for every edge..

V -> E1, E2, E3, ... // any vertex can point to one or more edges

Given this structure no edge can have more than two faces, but it

can have less than one face if we allow for null edge->face pointers,

wireframes are possible in this organization, you can still find other

edges by traversing through the vertices or the faces. It won't be common

to have more than say four edges per vertex. Lets assume a cube:

each vertex points to three edges,

each edge points to two faces.

There is 8 vertices, 12 edges.

Total space required, assuming 8-bit words (1 byte),

(8 vert * 3 pointers) + ( 12 edges * 2 pointers) +

( 6 quads * 4 pointers) = ( 24 + 24 + 24 ) = 72 bytes

(I used 8-bit pointers to simplify the math { a limitation of

addressibility of vertices, edges, faces to 256} , imagine if using

memory pointers (32-bit words) this would be 4 times as much to

store the actual data, just to represent the relationship, not

including the coordinates that determine representation in

3D space, the UV texture coordinates, vertex normals, and other

junk that rely on this relationship defining a cube)

To represent the same data structure in blender would probably require

6 faces defined from 8 vertices, so each face has pointers to

vertices. That is 6 * 4 bytes, or 24 bytes for the face to vertex pointers.

Edges are implicit in the face, the vertices can be accessed

only through the faces, but if we want to derive the relationship

of the vertex to other edges we can find all edges that

share a vertex and derive all other vertices, then do a second pass to

determine all faces that share those vertices. To deal with this structure

we would waste more time trying to find nearby vertices..

I suppose by now blender has pointers from the vertices to the

faces that point to them. That would be 3 * 8 pointers total for a cube,

because each vertex points to three owning faces.

That means the way it is in blender now, I'm assuming, 48 bytes are required to store a cube..

Other considerations: if blender stores vertices in the

faces, vertices are replicated among the faces but we save by not having

to store pointers to the vertices in the face (I was not thinking clearly

when I wrote this, to store vertex data requires 12 bytes as opposed to storing

a pointer of 4 bytes, it would only require 4 bytes more to

represent a pointer to a vertex).

But it would be impossible if vertices are stored in the faces to derive

a relationship between the faces unless faces could share vertices or the

vertices pointed to edges or similar vertices.. It gets pretty

hairy after a while.. Note that in in a representation of a cube in a

data structure that stores vertices in the faces, there is a replication

of 8 vertices which results in 8 * 12 bytes wasted to this model in a cube.

But notice that it depends on how you

organize the data.. If blender stores the quads with vertices in

them, it will be tough to go to a winged edge design without

some careful thought.

Does anyone know of how blender actually stores the quads/tris and

vertices and how they are related? We could derive a relationship

considering what is required for a winged edge..

I'm speculating on the data requirements for a winged edge,

I'm deriving my ideas from what I've read about winged edges and

what I know of data structures and pointers. I have only

touched on the runtime complexity of dealing with static versus

pointer based polygon structures, and I've thought about these

by my own intuition.. I'm not considering possible optimizations

that deal with creative, unobvious, relationships between edges/vertices/faces.

But I'm pointing out that there is something to consider when making

the jump to winged edges by considering differences in the data model,

it may require more work to maintain all the pointers, but

searching for relationships between edges and faces and vertices

will be easier due to the pointers, the alternative of a static

relationship is a breadth first search of the entire data structure

to find relationships between edges, vertices

and faces.. I imagine blender must have pointers to vertices

as it would be impossible to implement the "weld" function

without vertex pointers..

It would be nice to come up with a notation for representation

of pointer based structures so that we can discuss the model

of the data.

I can imagine that a winged edge relationship could be derived

possibly from a basic polygon model if we consider that faces

are double-sided and counted as single-sided polygons, or allowing

some special case for the implementation. But for other blender

tools to work on this new data relationship we will need to change

the way all the other tools work with winged edges as opposed to

the other way of storing objects. This implies a object oriented

language because of the handling of similar functions with

different models would involve some form of operation

overloading. If no overloading is used, there will need to be a

seperation of winged/non-winged objects, whereas it would

be possible in a object oriented design to have a hybrid model

if the operations could distinguish one model from the other

and know how to adapt given the existense or non-existence

of information (if edge pointer exists, traverse edge pointer, if

it doesn't exist, traverse the model looking for shared vertices).

At the very least every node for the vertex, edge and face could have

a flag in it that determines if its related to a blender style model

or a winged-edge model, or both. Its natural in C to keep the

data seperate, so hybrid models would need careful thought about the

data structures and the relationship between them..

Note that when you add more pointers to a data structure, if

precautions are not taken with the handling of null pointers, which will

occur, you can crash your program, that's probably why Nendo and

other Winged-edge programs have bugs in them.. Winged-edges

would probably require more pointers and more chances for failure.

Also by definition a winged edge can't have more than two faces

owning an edge, so an extrusion of a plus-shaped object

made of four faces is impossible in a winged edge system,

but is possible in blender.