BMesh Status

May 26, 2009 at 5:24 pm 42 comments

bmesh logo

Myself (Joseph Eagar), Geoffry Bantle, and Levi Schooley have been working on a replacement for the old, unmaintainable, outdated mesh modeling code in blender.  Geoffry did most of the difficult design work, and wrote bmesh, a quasi-independant mesh library, with some help from Levi, and now myself.

My task is to integrate this new mesh library into blender, which involves quite a lot of reworking of existing tools.  I’m the only developer working on this now, so it’s quite an undertaking.  The work is being done in a branch, location at https://svn.blender.org/svnroot/bf-blender/branches/bmesh.

Why This Is Important

The old mesh code suffered from two major problems: it was close to unmaintainable, and it didn’t support polygons of more then 4 sides (which is a requirement for more advanced modeling tools to work properly).

The original solution was hemesh, a half-edge mesh implementation for blender; however, half-edge turned out to be an unworkable data structure for blender, so Geoffry Bantle designed and implemented a new structure, bmesh.  The first version was used for the revamped bevel tool, while the second is what I’m integrating into blender.

How This Benefits You

bmesh spiral ngon

A complex spiral ngon

The integration of bmesh will have myriad benefits to users.  Winged extrusion, better beveling tools, and more stable tools in general will be possible.  Support for ngons will allow more flexibility in building subdivision surfaces, and produce cleaner meshes for the architectural visualization people.  Many new tools will be possible.

Current Status

Vertex Dissolve Tool

Vertex Dissolve Tool

I’ve finished ripping out the old EditMesh (which did mesh editmode) and replaced it with bmesh.  Many things are still not quite working right or missing, but (as per the initial design) most of the old editmesh tools still work, internally converting the BMesh to an EditMesh (with fgons) as needed.

I’ve recoded extrude and edge (wkey) subdivide, and I also coded three new experimental tools, vertex dissolve, face dissolve, and vertex connect (vert dissolve can be found in the xkey menu, while to dissolve faces, simply select adjacent faces and press the fkey.   To connect vertices within the same face, select them and press the fkey).

I’ve also modified the format used to store meshes outside of editmode to support ngons.  This affects the .blend format, but is mostly backwards-compatible.

Sounds Cool? Well I Wouldn’t Use It Yet

Bmesh isn’t yet ready for full-scale testing.  There’s still some bugs I need to work out, and at the moment it’s somewhat usable, but very unreliable.  I’d not recommend testing it just yet.

Donations Are Welcome

I’m currently the only developer working on this project.  It’s a massive undertaking, so any financial help I can get will go a long way.  Even small donations help.

Advertisements

Entry filed under: Coding Stuff, Status Updates.

Merge Woes Modifiers And Ngons

42 Comments Add your own

  • 1. Steren  |  May 26, 2009 at 8:41 pm

    Great article, we now fully understand the story behind BMesh.

    I would love a more technical article describing how Blender stores Meshes internally now and how it will once BMesh is used. (a list of vertices and a list of faces ? or something more complex ?)

    Reply
    • 2. Tyler T.  |  June 23, 2009 at 6:41 am

      On blender wiki it goes into some detail on it but you’d have to understand Boundary Representation Topology to understand what’s going on under the hood. It uses loops, edges, vertexes, and face datastructs in a graph. I’m hoping the Topology datatructs remain independent from the geometry since I’d like to be able to use the bmesh kernel later for free form surfaces.

      Reply
  • 3. joeedh  |  May 26, 2009 at 8:45 pm

    I intend to write plenty of documentation, which I will post links to here 🙂

    Reply
  • 4. Georg  |  May 26, 2009 at 9:49 pm

    Would like to test it now. Unfortunately I’m to lazy to compile it myself. Especially because actually I’m under windows. I have to check graphicall.org.

    Looking forward for your next posts.

    I hope I will not forget to donate something to you next month. It will be from my first salary in my whole life. But it is time to give something back to the open source community and this is a very good project!

    Reply
  • 5. n-pigeon  |  May 27, 2009 at 10:58 am

    I can’t wait to test it 😀

    Reply
  • 6. Sleeper  |  May 27, 2009 at 11:25 am

    You commented that Derived Mesh needed a ground up rewrite. I was just wondering what the issues were with it?

    Reply
  • 7. Sleeper  |  May 27, 2009 at 12:09 pm

    To be clear I’m aware that a complete rewrite of Derived Mesh isn’t part of the BMesh project.

    Reply
  • 8. Hitechboy722  |  May 27, 2009 at 2:26 pm

    So let me get this straight… Ngons are just a bonus, and it’s the extensibility of the whole mesh system that’s at core of the project right? Or were ngons the point from the start…

    Reply
  • 9. Massimiliano Puliero  |  May 27, 2009 at 2:33 pm

    when I recive my new credit card I will give you money.

    I’m not rich, but I’m a modeler and I prefer give you directly my money isted give to no body knows people 🙂

    Reply
  • 10. Billrey  |  May 27, 2009 at 3:09 pm

    Nice post. Already starting to look like something.

    Way to go

    Reply
  • 11. Corniger  |  May 27, 2009 at 5:56 pm

    I don’t quite understand what all this is about, most of it is Greek to me after 5 months of Blender, but my future lies within this so I’ll send some cash as soon as I have it on my PayPal! Cause I love modelling, and if you can help me make better models, I love you :p You’ll have my support for sure!

    Reply
  • 12. joeedh  |  May 27, 2009 at 6:45 pm

    @Corniger – Refactoring the mesh code to allow for new/better development is the core of the project, yes. NGons are a requirement of this (many tools need them to work properly, e.g. bevel). NGons themselves are very useful, of course.

    @Sleeper – DerivedMesh was supposed to be an abstract interface to all the different mesh data structures in blender. It fails miserably at this task, however, and just doesn’t work for what it’s supposed to do. For the bmesh project, I’m planning on refactoring the way faces are accessed through DerivedMesh (so ngons will work in subsurf) but that’s it.

    Reply
  • 13. bsdhacker  |  May 28, 2009 at 2:57 am

    Keep up the good work Joe. I figured I’d look up your blog here after you mentioned it to me.

    Reply
  • 14. Manny_rat  |  May 28, 2009 at 4:23 pm

    I’ve been waiting for BMesh for long time 🙂 Thanks for the explanation of what you’re doing, I will donate when I get paid.

    Reply
    • 15. joeedh  |  May 28, 2009 at 7:16 pm

      Thanks!

      Reply
  • 16. Carrozza  |  May 28, 2009 at 7:02 pm

    Compliments Joe.
    I dream that one of the first tools which will benefit from the new b–mesh will be Bevel, with recursion.
    In its actual shape Blender’s bevel tool is the worst I saw among many 3D apps (Wings, Hexagon, Modo, Cinema 4D, Truespace).
    Even Sketchup, with its FollowMe tool, can achieve quickly better bevels than Blender! 😦
    OK, let’s stop ranting, go for it Joe!

    Reply
    • 17. joeedh  |  May 28, 2009 at 7:18 pm

      Yeah I agree, it’s very awkward as it is now.

      Reply
  • 18. ShaneNewville  |  May 28, 2009 at 8:35 pm

    Joseph,

    It’s so fun and exciting to see how people are developing Blender.
    You’re awesome! …that’s all I’ve got. Keep doing in man.

    -ShaneNewville

    Reply
  • 19. dogwynn  |  June 4, 2009 at 4:03 am

    Looking forward to your tech docs on the b-mesh format.

    Am I correct in assuming that the underlying problem with using half-edge (and its peers) is the non-manifold nature of the meshes Blender tends to deal with? I’m currently studying issues surrounding boundary representations, but since my problems are constrained to manifold meshes, my knowledge base is limited to the standard brep data structures (half/winged-edge, Joy’s corner, DCEL, etc).

    When you are able to get around to documentation, could you also post a paper trail of adapted/discarded ideas that you’ve researched? Thanks again!

    Reply
    • 20. joeedh  |  June 4, 2009 at 4:53 am

      Yes, the problem was handling non-manifold meshes. As for a paper trail, well far as I know there isn’t much, really, I don’t think Geoffry posted much of any earlier design ideas for the structure.

      Reply
      • 21. dogwynn  |  June 4, 2009 at 1:50 pm

        Ah, ok. If you’d like, I can email you a few papers on non-manifold data structures. I doubt they’ll be exactly what you’re looking for, but they might help in avoiding future problems.

      • 22. joeedh  |  June 10, 2009 at 7:12 pm

        That’d be awesome.

    • 23. Briggs  |  June 4, 2009 at 2:42 pm

      Hello,

      The Bmesh structure can be traced back to radial edge, partial entity, and an off-handed remark made by another developer in IRC a couple years back.

      However Bmesh differs from these structures in several very important respects. The most significant being

      1: It does not keep track of region/shell information
      2: It does not maintain a orientable surface
      3: The ordering of all cycles (except the loop cycle) are undefined.

      All 3 of these are (probably) related in subtle ways.

      There are a lot of other technical decisions I made with the design, but I wont go into them here. Unfortunately I don’t think I would have the time to really write them all down either, but can answer specific questions.

      Reply
      • 24. dogwynn  |  June 10, 2009 at 8:04 pm

        Thanks much for your reply! Please pardon my ignorance in these questions. My knowledge of Blender-specific issues is very limited.

        – What was the off-handed remark, if I might ask?
        – When you refer to the loop cycle, are you referring to the edge loop, or something more general?

        The reason why I’m curious about Bmesh is that I’m researching mesh scissoring/decomposition methods and using Blender as a prototyping/testing environment (which has been a real pleasure!). Most of the methods I’ve been working with use curvature estimation which requires consistent orientation of faces. As it stands, I’m using my own implementation of Joy’s corner data-structure on imported manifold meshes. If your Bmesh structure could provide similar behavior on known manifold meshes, it would be better to use it rather than reinvent the wheel.

        Answer these at your leisure, if at all; I know you’re probably very busy. I’m mostly waiting to see the final design specs/API. 🙂

        Thank you joeedh, Briggs et al. for all your hard work!

      • 25. joeedh  |  June 10, 2009 at 8:15 pm

        @dogwyn: Not sure which off-hand remark you mean?

        Each face is defined by a list of loops, and each loop corresponds to an edge, and the loop cycle is the list of all such loops around the edge, from all faces that surround it.

        If you want manifold guarantees on a bmesh structure, you have to go through and validate the data yourself (e.g. orient faces, etc). Also note that a lot of the queries are unordered in bmesh, so e.g. getting a list of edges around a vert won’t go in order (though it’s fairly easy to have it do so on a manifold mesh, I do this in several places, there just isn’t an iterator for it yet, so you have to write the loop yourself).

      • 26. dogwynn  |  June 10, 2009 at 8:57 pm

        Sorry, I was referencing Briggs’s comment about “an off-handed remark” that was a factor in the design of Bmesh.

        Instead of peppering you with questions about the spec, I’ll just wait for the write-up/docs. 🙂

      • 27. Briggs  |  June 11, 2009 at 9:44 pm

        Dogwynn

        The off hand remark was made by another developer about half-edge and its restrictions. If I recall correctly they just wondered out loud why we could not just use a circular linked list of edges around verts and faces around edges for adding adjacency information to Blender’s Edit-Mesh. This is essentially what B-Mesh does today.

        The loop cycle refers to the circular linked list that bounds each face in a B-Mesh. I think I borrowed this terminology from Radial Edge/Partial Entity.

        Now B-Mesh should be able to represent any valid manifold, and its Euler system can even have operators that require manifold input however this does not make it a good candidate for your work. The reason for this is that the system was designed to provide facilities for Eulers to assure the output they produced was always a valid B-Mesh only, not a valid manifold as well. You would have to verify manifold output yourself or the Euler would have to be designed in a such a way as to make ‘pretty’ sure it’s output was manifold without actually being able to ‘prove’ it.

        Also what seems to be the two most common Euler pairs for mesh refinement/simplification operations on manifolds (split vert make edge and join vert kill edge) are missing from the B-Mesh Euler system (even though similar operators are present, they don’t work in exactly the same way). Although these could be added, and I have actually debated doing this in the past, you would still be stuck with the situation mentioned above.

        Cheers,
        Briggs

      • 28. dogwynn  |  June 11, 2009 at 9:50 pm

        Again, thanks much to both of you for your responses! Looking forward to the final product. 🙂

  • 29. joel  |  June 6, 2009 at 5:07 pm

    Hey Joeedh,

    here are the 3dsmax modeling progress images i would make for you:

    http://uploadbox.com/files/9f84233d1b

    Reply
  • 30. mixen  |  June 6, 2009 at 8:12 pm

    Happy to support you!

    Reply
  • 31. Justin  |  June 10, 2009 at 6:01 pm

    Looks like some changes are coming soon, I was reading in SVN…any news?

    Reply
    • 32. joeedh  |  June 10, 2009 at 7:14 pm

      I’ve been working on modifiers (or rather the infrastructure they use). I’ll write a nice blog pose when I’m a little further along 🙂 One of the nice things is ngons will be supported in subsurf, which can be fairly useful.

      Reply
  • 33. michael a. beaver  |  June 18, 2009 at 6:01 pm

    On the topic of donations, I would like to participate because this work is so important to the blender community and for our work in particular. Do you have a paypal account or some way to receive the donation?

    Michael A.Beaver
    cto
    3d modeling labs, inc.
    san jose, ca

    Reply
    • 34. joeedh  |  June 23, 2009 at 8:17 am

      @michael a beaver: there’s the donate link to the right. I know, it’s kindof small an unobtrusive; it’s actually kindof difficult to add a donate button on wordpress.com (they host every account running in one wordpress install, so they don’t allow plugins).

      Reply
  • 35. Muzak  |  June 19, 2009 at 1:20 am

    looking at the image with the spiral, I have to wonder can I deform the spiral further or is that ngon capping limited to flat faces for good results?

    Reply
    • 36. joeedh  |  June 23, 2009 at 8:15 am

      @Muzak: you can deform it, but there’s no guarantees of it working right with a non-planier ngon.

      Reply
  • 37. LeraJenkins  |  June 24, 2009 at 2:40 pm

    This very valuable opinion

    Reply
  • 38. unhurdof  |  June 26, 2009 at 7:48 pm

    It will be great to see n-gons fully supported in Blender. Someone here asked what modeling related features we like to see implemented. Many have made great suggestions already but here are some of the features that are important to me.

    1.) (full n-gon support ;0) )
    2.) highlighting poly families (tris, quads, n-gons)
    3.) highlighting pole types (3,5+)
    4.) operator dialogue menus (ie extrude, bevel, outline, inset, etc)
    5.) primitive dialogue (ie height, width, length segments, radius parameters etc)
    6.) widget enhancements (particularly multi-axis handles and an improved universal handle)
    7.) parametric modeling modifiers (ie shell, melt, noise, etc)
    8.) procedural modeling

    I don’t know how difficult it is to implement some of these features because I’m not much of a coder, but many of my requests seem so feasible because other open 3D source softwares have some of the features I mentioned. For example, Gsculpt has procedural modeling (and full N-Gon) support, and it is written in Python. Anyhow, as I mentioned, I don’t code much, and I don’t have much money to donate. When I do have some money to spare, this B-mesh project will get some from me, cause this is a great project, and I’m sure it takes huge amounts of time and efforts to make it possible. If I can contribute by testing builds, or perhaps by capturing some research footage as to how other 3d apps handle modeling features and procedures, please let me know, I’d be glad to help. I’ve checked the button below to notify me of replies to this post via email. Good luck team B-mesh. Thank you for you efforts. Godspeed. Peace.

    Reply
  • 39. Obex  |  April 12, 2010 at 3:16 pm

    Why is “Bmesh” named “Bmesh”? Is it because of “Blender” -> BMesh or is due to general technical term?

    Reply
    • 40. joeedh  |  May 7, 2010 at 12:51 pm

      It’s “Blender Mesh” after it’s author, Geoffry Bantle (who wrote the core API code and helped a lot in a consulting capacity as I’ve been integrating it and writing tools in it; he wasn’t in a position to actually contribute code, but his expertise was *extremely* valuable). We like to joke it’s “Briggs Mesh” after his IRC nickname 😛

      Reply
  • 41. Obex  |  May 16, 2010 at 9:00 am

    oh, ok,
    thank you

    Reply
  • 42. Obex  |  May 16, 2010 at 9:05 am

    oh, ok,
    thank you 🙂

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed


Categories

Feeds


%d bloggers like this: