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.
