[Bf-committers] New mesh data type

Ton Roosendaal bf-committers@blender.org
Thu, 18 Dec 2003 15:19:59 +0100


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:
Or we can build further on the 'HyperMesh' as in =20

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?


> 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 =
> subdivision level of entire meshes.=A0 This is great for beveling, but =
> 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 =
> 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=
> 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 =
> 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 =
> 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 =
> 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 =
> 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

Ton Roosendaal  Blender Foundation ton@blender.org =20