[Bf-committers] New mesh data type
Matthew H. Plough
bf-committers@blender.org
Wed, 17 Dec 2003 22:06:19 -0500
This is a multi-part message in MIME format.
------=_NextPart_000_001E_01C3C4E9.FFFC3A50
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Hi all --
You probably don't remember what I'm talking about since I last wrote =
about this on November 25, but I've been researching a new mesh data =
structure because of a subdivision surface project I'm working on. =20
First, the underlying reason for my mesh rewrite:
I have been working on a modification to Blender's subdivision surfaces =
that allows semi-sharp subdivision to happen when the user marks certain =
edges as creases. I successfully implemented this code in Tuhopuu about =
a month ago, and today finished adding it to the official BF tree. =
However, Blender does not store data about edges, so the current =
implementation only allows the user to modify the sharp subdivision =
level of entire meshes. This is great for beveling, but now that real =
beveling code has been added, my limited implementation is rather =
useless. =20
Second, information about the mesh rewrite:
Therefore, I propose the addition of a mesh data type that can coexist =
with the current implementation, as per Ton's recommendation. The new =
data type will need to store data about all edges in the mesh =
explicitly, so that the sharp subdivision level can be set on a per-edge =
basis. =20
The most basic data structure that includes edges is a structure that =
stores vertex geometry, and a face list and edge list that each =
references the vertex list. Although such a data structure is small, it =
does not have any benefit besides the ability to store information about =
edges. =20
Ton writes, however,
The data representation type could be designed in two steps:
1. A compact & simple, preferable compressed, format to store in =
memory =20
and save in files. Preferably consisting out of as few data chunks as =
possible, and easily to parse for creating display lists and do =20
conversions.
2. A highly flexible and advanced 'editing format', for tools to =20
operate on. This fits within Blender's convention to have EditMode.
By creating conversions to/from current Mesh data it can (eventually) =
become invisible for users, where internally this conversion just =20
happens automatically.
This most basic data structure, then, would be ideal for storage in a =
file or for storage outside of edit mode, as it would not include the =
overhead of adjacency information. It would also be extremely easy to =
parse for display; the current display code could be reused verbatim. =
Edge data would simply be ignored. The structure would also allow easy =
parsing in the subsurf.c module, since the only addition would be =
references to edge data.
A more advanced data structure would be needed in edit mode, and I have =
focused my research on determining what this structure should be. I =
immediately eliminated the winged edge, radial edge, and similar data =
structures as candidates for the new representation, as they cannot =
represent open meshes or non-manifold meshes without heavy modification. =
Two data structures of note have been designed to represent =
non-manifold or open meshes: the partial entity data structure, and the =
non-manifold indexed data structure with adjacencies (NMIA data =
structure). The NMIA data structure is designed to scale with the =
degree of "non-manifoldness," a property that the partial entity =
structure does not possess. =20
At first glance, then, the NMIA structure seemed ideal for the job. =
However, that structure does not encode data about all edges, a crucial =
property. Although it would be smaller in memory than the partial =
entity structure, the NMIA data structure cannot be used for the job! I =
therefore decided that the partial entity structure should be used =
instead; it does encode information about all edges, albeit at a higher =
memory cost. However, this cost is justified, as it will only be =
experienced while the user is editing a mesh. =20
Ton, you'll be getting that email about how to write a new type shortly!
Please criticize this email as much as possible, since I'm designing =
this for the long term.
Blend on!
Matthew H. Plough
------=_NextPart_000_001E_01C3C4E9.FFFC3A50
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=3DContent-Type content=3D"text/html; =
charset=3Diso-8859-1">
<META content=3D"MSHTML 6.00.2800.1276" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT face=3DArial size=3D2>Hi all --</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>You probably don't remember what I'm =
talking about=20
since I last wrote about this on November 25, but I've been researching =
a new=20
mesh data structure because of a subdivision surface project I'm working =
on. </FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>First, the underlying reason for my =
mesh=20
rewrite:</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>I have been working on a modification =
to Blender's=20
subdivision surfaces that allows semi-sharp subdivision to happen when =
the user=20
marks certain edges as creases. I successfully implemented this =
code in=20
Tuhopuu about a month ago, and today finished adding it to the official =
BF=20
tree. However, Blender does not store data about edges, so =
the=20
current implementation only allows the user to modify the sharp =
subdivision=20
level of entire meshes. This is great for beveling, but now that =
real=20
beveling code has been added, my limited implementation is rather =
useless. =20
</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Second, information about the mesh=20
rewrite:</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>Therefore, I propose the addition of a =
mesh data=20
type that can coexist with the current implementation, as per Ton's=20
recommendation. The new data type will need to store data about =
all edges=20
in the mesh explicitly, so that the sharp subdivision level can be set =
on a=20
per-edge basis. </FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT><FONT face=3DArial =
size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>The most basic data structure that =
includes edges=20
is a structure that stores vertex geometry, and a face list and edge =
list that=20
each references the vertex list. Although such a data structure is =
small,=20
it does not have any benefit besides the ability to store information =
about=20
edges. </FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Ton writes, however,</FONT></DIV>
<BLOCKQUOTE dir=3Dltr style=3D"MARGIN-RIGHT: 0px">
<DIV>The data representation type could be designed in two =
steps:<BR><BR>1. A=20
compact & simple, preferable compressed, format to store in =
memory =20
<BR>and save in files. Preferably consisting out of as few data chunks =
as <BR>possible, and easily to parse for creating display lists =
and=20
do <BR>conversions.<BR>2. A highly flexible and advanced =
'editing=20
format', for tools to <BR>operate on. This fits within Blender's =
convention to have EditMode.<BR><BR>By creating conversions to/from =
current=20
Mesh data it can (eventually) <BR>become invisible for users, =
where=20
internally this conversion just <BR>happens=20
automatically.</DIV></BLOCKQUOTE>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>This most basic data =
structure,=20
then, would be ideal for storage in a file or for storage outside =
of edit=20
mode, as it would not include the overhead of adjacency =
information. It=20
would also be extremely easy to parse for display; the current display =
code=20
could be reused verbatim. Edge data would simply be ignored. =
The=20
structure would also allow easy parsing in the subsurf.c module, since =
the only=20
addition would be references to edge data.</FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>A more advanced data =
structure would be=20
needed in edit mode, and I have focused my research on determining what =
this=20
structure should be.</FONT><FONT face=3DArial size=3D2> I =
immediately=20
eliminated the winged edge, radial edge, and similar data structures as=20
candidates for the new representation, as they cannot represent open =
meshes or=20
non-manifold meshes without heavy modification. Two data =
structures of=20
note have been designed to represent non-manifold or open meshes: the =
partial=20
entity data structure, and the non-manifold indexed data structure with=20
adjacencies (NMIA data structure). The NMIA data structure is =
designed to scale with the degree of "non-manifoldness," a property that =
the=20
partial entity structure does not possess. </FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>At first glance, then, the =
NMIA structure=20
seemed ideal for the job. However, that structure does not encode =
data=20
about <EM>all</EM> edges, a crucial property. Although it would be =
smaller=20
in memory than the partial entity structure, the NMIA data structure =
cannot be=20
used for the job! I therefore decided that the partial entity =
structure=20
should be used instead; it does encode information about all edges, =
albeit at a=20
higher memory cost. However, this cost is justified, as it will =
only be=20
experienced while the user is editing a mesh. </FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>Ton, you'll be getting that =
email about how=20
to write a new type shortly!</FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>Please criticize this email =
as much as=20
possible, since I'm designing this for the long term.</FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>Blend on!</FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>Matthew H.=20
Plough</FONT></DIV></BODY></HTML>
------=_NextPart_000_001E_01C3C4E9.FFFC3A50--