Edge Loop Based Modeling Tools

General discussion about the development of the open source Blender

Moderators: jesterKing, stiv

kid_tripod
Posts: 35
Joined: Sun Dec 15, 2002 10:52 pm

Post by kid_tripod »

belac wrote:edge select??? select two verticies...wow, and edge! cool!
If you only work with vertices as your basis for selection, how would you select only two sides of a triangle for example?

I'd be in the "add another editmode" school, after my earlier outburst. It would need to be a new internal data type to do it properly. You could probably do hacks on the existing one, but I for one wouldn't want to do it. Unfortunately you can't implement edge selection in python, unless you can somehow get into the GUI at that low a level (again theres better ways, and it'd be slow), but some of the functions could certainly be done in python, or at least prototyped in that manner.

My feeling is that it must reflect how the rest of Blender works (from a users view) and the current mesh tools must be left intact, and winged edge not made the default. There is certainly room for some clever selection tools to be made, a la lightwave's bandsaw, and I might have a think about that.

blendermax
Posts: 0
Joined: Sun Jan 19, 2003 8:30 pm

Post by blendermax »

face select and 5 sided polys (or x sided meta-polys, ie a pentagon made out of a triangle and a rectangle, but looks like a pentagon to the user) would be a blessing. just my 2 cents.

p_vertex
Posts: 0
Joined: Mon Jan 27, 2003 1:45 am

Re: Edge Loop Based Modeling Tools

Post by p_vertex »

Jamesk wrote:
ravioli_rancher wrote:Though Wings3d is also freeware, it requires the user to install additional software, and is fairly buggy.
Not true anymore. Sure, it's freeware allright, but there's no additional things to install. The erlang modules required have been packed into the monolithic installer for quite some time now. It's just one archive, one simple install procedure. And as far as I know, Nendo (and possibly also Mirai) are/were even more bug infested than Wings, which honestly has very few bugs left in it.
Could you direct me to the Linux version of the 'complete' download? I couldn't seem to find it on the Wings3d website.

Thanks

bob_dog
Posts: 8
Joined: Thu Oct 17, 2002 9:39 am

Post by bob_dog »

I've used both Blender and Wings3D for some time now. Both programs have advantages and disadvantages. I like to model in Wings and then export to Blender - no problem.

I understand that the Wings data structure is bulky to enable it to do what it can. Why add that "bulkyness" to the Blender code? I like my Blender lean!

cessen
Posts: 109
Joined: Tue Oct 15, 2002 11:43 pm

Post by cessen »

There are more basic things that need to be worked on first. For instance, polygons with arbitrary numbers of vertices. And better surface-based modeling tools.

Actually, with good surface-based modeling tools, polygonal-based modeling becomes rather unneccessary as anything but a learning tool (although as a learning tool it *is* a lot better than surface-based modeling, because surface-based modeling can be rather confusing without a good background in polygonal modeling).

thorax
Posts: 320
Joined: Sun Oct 27, 2002 6:45 am
Contact:

Edge modelling..

Post by thorax »

I never really have done it I suppose I should download wings,
anyhow I believe it should be easy to write an edge selection
feature into blender, edges are defined as associations of
existing vertices, like edge(75) could be vertex(3) and vertex(44).
Selecting an edge would require knowing where the edge is and how to
select it. To extrude it, the vertices could be selected and extruded..
That's easy..

If blender was based on objects, you could define a wrapping structure
to define modifications on an object, implementing undo/redo and
construction history and possibly defining reltionships between
edges by being able to traverse the construction history.. I think this is
what this edge modelling may require that is causing problems for
NewTek in that they, like blender, probably defined their structures in
a static way where polygons are either 3 or 4 edges and share vertices
with other polygons, and so on.. Edge modelling may require a different relationship between polygons, and may even require mor abstraction
of the relationship between vertices, edges and polygons..

I've been looking at some of the source code for blender, and it looks like
attempts have been made to give it and object structure, using accessor methods to access static variables in pre-link compiled code, its object oriente but not really (say you want to create a window [the part I looked at], do you require developers to manage window ids and give them access to the internal struct representation or do you force them to use methods thus seperating what is a hack and what is a proper use of window objects, also do you require the developers to know which functions work on which data structures or wouldn't it be better to maintain this policy by forcing them to use methods of the object to work on the object) but there are
places in the code I looked at where return values could have been used and were not (allowing semantic ambiguity, and thus bugs to popup),
I think we should go through the source code and analyze/comment it
to make sure others will know what the code is doing without having to go through re-reading it.. I think Ton should be doing this and anyone still left who knows about the codebase. Then we can assess what can be done to the structure to allow features like edge-modelling and construction history.. IT will involve transferring the C code base to something more dynamic and object oriented than passing structures around with pointers and flipping global flags..

thorax
Posts: 320
Joined: Sun Oct 27, 2002 6:45 am
Contact:

I THINK THAT IS IT.. N-sided polygons..

Post by thorax »

blendermax wrote:face select and 5 sided polys (or x sided meta-polys, ie a pentagon made out of a triangle and a rectangle, but looks like a pentagon to the user) would be a blessing. just my 2 cents.

Think about it, you take and edge and extrude it, what do you do about
subdividing a new edge made from the extrude? Do you create a
new vertex and replace two polygons with 3? Or do you define polygons
to be N-sided? If you define the polygons to be N-sided (this is obejct oriented abstraction of a concept guyz) then you can subdidivide a
polygon and have its external representation be a 5 sided polygon rather
than a 4 sided one. See what wonderful things you can do with object oriented abstractions? How about if you wanted to undo that subdivision?
Well you could define construction history for the edge, it was subdivided,
how do we get back to the original? Well replace what modifications were made with what was replaced, also we should define what was done to get the result so we can redo the operation.. This is important, say I decided I wanted to change the orientation of the base polygon such that it was facing in a different direction. I use the cached original edge to
replace the existing edge modification, then re perform the operations based on the modified base geometry.

It would require having a base object and each operation being a
operation off the operation before or at least the base object. Clearinig construction history involves taking the resulting object, making it the base object and deleting all the modification history and all the cached changes...

thorax
Posts: 320
Joined: Sun Oct 27, 2002 6:45 am
Contact:

I THINK THAT IS IT.. N-sided polygons..

Post by thorax »

blendermax wrote:face select and 5 sided polys (or x sided meta-polys, ie a pentagon made out of a triangle and a rectangle, but looks like a pentagon to the user) would be a blessing. just my 2 cents.

Think about it, you take and edge and extrude it, what do you do about
subdividing a new edge made from the extrude? Do you create a
new vertex and replace one polygon with 3? Or do you define polygons
to be N-sided? If you define the polygons to be N-sided (this is obejct oriented abstraction of a concept guyz) then you can subdidivide a
polygon and have its external representation be a 5 sided polygon rather
than a 4 sided one. See what wonderful things you can do with object oriented abstractions? How about if you wanted to undo that subdivision?
Well you could define construction history for the edge, it was subdivided,
how do we get back to the original? Well replace what modifications were made with what was replaced, also we should define what was done to get the result so we can redo the operation.. This is important, say I decided I wanted to change the orientation of the base polygon such that it was facing in a different direction. I use the cached original edge to
replace the existing edge modification, then re perform the operations based on the modified base geometry.

It would require having a base object and each operation being a
operation off the operation before or at least the base object. Clearinig construction history involves taking the resulting object, making it the base object and deleting all the modification history and all the cached changes...

Manuel
Posts: 56
Joined: Wed Oct 16, 2002 12:48 am
Location: Italy
Contact:

Post by Manuel »

Great work Strubi.
These are the most wanted features.
Now Blender is really complete and powerful.

Only 2 questions.
Using Xmesh, there are compatibility problems with the python
Nmesh structure?

XMesh will be in B2.28 ? 8)
I can't wait...

Thx,

Manuel

JA-forreal
Posts: 0
Joined: Sat Mar 22, 2003 10:45 pm

Post by JA-forreal »

If an edge tool solution came to Blender in the form of a added python interface like Makehuman, I'd say yes!

cekuhnen
Posts: 0
Joined: Mon Jan 13, 2003 11:04 pm

...

Post by cekuhnen »

hi guys

i am not a programmer but i work with 3d programmers together.

since i play around with wings3d as well since it works fine for lightwave
i think since there is wings3d and the import into blender works fine there
is no need to build that stuff into blender.

i do not know if you know that but as it was ppointed out winged edge data structure contains more data than blenders vertex system and that is the point why wings3d gets slow when the model gets to big while blender still behaves fine with its fast vertex system.

for modeling wings3d is a very good addition and if somebody complains about an addition to install hell than you should work in a professional enviroment. corss app working is quit commone. and since blender is fast do the animation and ik rigging in blender.

eicke

Zarf
Posts: 46
Joined: Mon Oct 14, 2002 3:54 am

Re: ...

Post by Zarf »

The WEDS could be implemented on top of blenders current data structures. Even wings dosnt store models in WE format, and AFAIK the WEDS databases in wings sit on top of a much more generic in memory mesh format (e3d_mesh) wich is very similar to blenders internal data structures. The WEDS is used to provide a high level way of editing that mesh data.

The question of how fast WE would be sitting on top of blender would be interesting to find an answer too.

thorax
Posts: 320
Joined: Sun Oct 27, 2002 6:45 am
Contact:

Thinking about time/time complexity of w-edges vs Blender's

Post by thorax »

Can someone turn this into a PDF for me? :D

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..


:shock:
(I've revisied this several times.. I should do a UML representation
of the concept, which I will do in the next hour..)

:idea: :!:
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.

Post Reply