[Bf-committers] New mesh data type

[Ton Roosendaal]

Hi,

Hurms... difficult topic. When it is *only* for storing edge =20
information in a Mesh, the current Mesh type can just be expanded for =20=

it. The Mesh already has more optional data blocks linked, like for =20
vertex color, texture faces, or 'sticky' coordinates.

I recently received a request from a games company who liked to have =20
normals stored, and editible in Meshes. This is a useful addition as =20
well, and can still coexist with Mesh. (They're willing to pay for =20
someone coding it!)

As Matt already replies, the need for a new Mesh type in Blender would =20=

be better served when we can include real new features as well. The =20
winged edge approach here can still be incorporated as option as well, =20=

like using a "Lath" instead:
http://www.blender.org/pipermail/bf-committers/2003-June/003238.html
Or we can build further on the 'HyperMesh' as in =20
blenkernel/intern/subsurf.c

Best is to check on your code first, to see:
- what info on edges need to be stored
- what kind of access have tools to this
- and of course, what new tools should be added! Is it a painting thing?

-Ton-



> First, the underlying reason for my mesh rewrite:
> I have been working on a modification to Blender's subdivision =20
> surfaces that allows semi-sharp subdivision to happen when the user =20=

> marks certain edges as creases.=A0 I successfully implemented this =
code =20
> in Tuhopuu about a month ago, and today finished adding it to the =20
> official BF tree.=A0 However, Blender=A0does not store data about =
edges, =20
> so the current implementation only allows the user to modify the sharp =
=20
> subdivision level of entire meshes.=A0 This is great for beveling, but =
=20
> now that real beveling code has been added, my limited implementation =20=

> is rather useless.=A0
> =A0
> Second, information about the mesh rewrite:
> Therefore, I propose the addition of a mesh data type that can coexist =
=20
> with the current implementation, as per Ton's recommendation.=A0 The =
new =20
> data type will need to store data about all edges in the mesh =20
> explicitly, so that the sharp subdivision level can be set on a =20
> per-edge basis.=A0
> =A0
> The most basic data structure that includes edges is a structure that =20=

> stores vertex geometry, and a face list and edge list that each =20
> references the vertex list.=A0 Although such a data structure is =
small, =20
> it does not have any benefit besides the ability to store information =20=

> about edges.=A0
> =A0
> Ton writes, however,
>
> The data representation type could be designed in two steps:
>
> 1. A compact & simple, preferable compressed, format to store in =20
> memory=A0
> and save in files. Preferably consisting out of as few data chunks as=A0=

> possible, and easily to parse for creating display lists and do=A0
> conversions.
> 2. A highly flexible and advanced 'editing format', for tools to=A0
> operate on. This fits within Blender's convention to have EditMode.
>
> By creating conversions to/from current Mesh data it can (eventually)=A0=

> become invisible for users, where internally this conversion just=A0
> happens automatically.
>
> This most basic data structure, then,=A0would be ideal for storage in =
a =20
> file or for storage outside of edit mode, as it would not include the =20=

> overhead of adjacency information.=A0 It would also be extremely easy =
to =20
> parse for display; the current display code could be reused verbatim.=A0=
 =20
> Edge data would simply be ignored.=A0 The structure would also allow =20=

> easy parsing in the subsurf.c module, since the only addition would be =
=20
> references to edge data.
> =A0
> A more advanced data structure would be needed in edit mode, and I =20
> have focused my research on determining what this structure should =20
> be.=A0 I immediately eliminated the winged edge, radial edge, and =20
> similar data structures as candidates for the new representation, as =20=

> they cannot represent open meshes or non-manifold meshes without heavy =
=20
> modification.=A0 Two data structures of note have been designed to =20
> represent non-manifold or open meshes: the partial entity data =20
> structure, and the non-manifold indexed data structure with =20
> adjacencies (NMIA data structure).=A0 The NMIA data=A0structure is =20
> designed to scale with the degree of "non-manifoldness," a property =20=

> that the partial entity structure does not possess.=A0
> =A0
> At first glance, then, the NMIA structure seemed ideal for the job.=A0 =
=20
> However, that structure does not encode data about all edges, a =20
> crucial property.=A0 Although it would be smaller in memory than the =20=

> partial entity structure, the NMIA data structure cannot be used for =20=

> the job!=A0 I therefore decided that the partial entity structure =
should =20
> be used instead; it does encode information about all edges, albeit at =
=20
> a higher memory cost.=A0 However, this cost is justified, as it will =20=

> only be experienced while the user is editing a mesh.=A0
> =A0
> Ton, you'll be getting that email about how to write a new type =20
> shortly!
> =A0
> Please criticize this email as much as possible, since I'm designing =20=

> this for the long term.
> =A0
> Blend on!
> Matthew H. Plough
>
------------------------------------------------------------------------=20=

--
Ton Roosendaal  Blender Foundation ton@blender.org =20
http://www.blender.org