[Bf-committers] Subdivision Surfaces Proposal

[Matthew H. Plough]

Hello all:

Since many people have been complaining about the status of Blender's
subdivision surfaces, I decided to investigate the ease with which the
system could be made more powerful.  After reading "Subdivision Surfaces in
Character Animation" by DeRose, Kass, and Truoung, I began looking at
Blender's subdivision code, and found it very easy to extend.  However,
fully implementing DeRose et al's semi-sharp Catmull-Clark subdivision
surfaces will require a mesh data structure that stores edge data, something
that Blender lacks.

Recently there has been a flurry of activity with edge-related features,
such as edge loop selection, knife subdivision, and loop subdivision (not to
be confused with Loop subdivision surfaces).  Right now, these features
require weird hacks such as the HashEdge data structure for their
implementation, and they don't work exactly as they should.  Since making
them work with a vertex list and face list would require a huge amount of
work, I suggest that we don't implement them with the current data
structure.  Implementing a new data structure will require an equally huge
amount of work, but the end result will be more extensible; it will allow
addition of features such as semi-sharp subdivision surfaces as implemented
in Pixar's short entitled "Geri's Game" and better decimation that uses edge
collapses.

(a note: In the past, I have been yelled at for "requesting features." I am
*not* requesting a feature.  I am *not* asking for someone to implement this
for me.  I am willing to put in countless hours of programming, late into
the night, to get this idea to see the light of day.)

Obviously, Blender's current vertex-list/indexed face list is not ideal for
supporting current features, and some proposed features.  Therefore, any
rewrite will require a lot of planning; we do not want to waste time
developing another subpar data structure.  I would like to start discussion
on the topic using the following background information:

Several options exist for a new type; the winged edge structure has been
mentioned frequently, almost certainly because many Blender users have also
used Wings3D.  However, the winged edge structure does not work for open
meshes, or non-manifold meshes in general.  Any data type that cannot
represent an open mesh would be useless in Blender; for example, the tube
primitive could no longer be used if such a data type were implemented.
Also, several users have mentioned situations where Blender would need to
represent a non-manifold mesh; after certain remove doubles operations, for
instance.  The winged edge structure would need heavy modification if it
were to be used.  The same argument applies for the half edge or partial
edge data structure.

However, S.H. Lee and K. Lee have developed a partial entity data structure
that is specifically designed to compactly represent non-manifold meshes.
The two goals of this data type coincide completely with Blender's
methodology, so I suggest that this data structure be investigated further
as a candidate for implementation.

I could probably implement such a structure on my own, but that would take
an excessively long time, and would not involve a proper amount of input
from other coders and the community in general.  Therefore, I would like to
enlist some help -- are there any coders who are willing to help me with
this project?

I thank you for your time spent reading this rather long email, and I hope
that I will receive some feedback about this proposal's feasibility and
timetable.

Sincerely,
Matthew H. Plough
mplough@princeton.edu