[Soc-2014-dev] Weekly Report #7: NURBS Modernization

Sun Jul 6 19:58:19 CEST 2014

Sorry this week's report is late. We talked about it at the developer meeting -- in the future I need to give up on the "just one more day and I'll have something much better to show" trap and report my progress regardless. Friday report needs to actually be on Friday. Impeding communication doesn't do anyone any favors.

I have a picture version of this report posted to the wiki:
http://wiki.blender.org/index.php/User:Jjoonathan/Trim_Algorithms_(Update)#Integration_of_Trimming_in_Blender

Text summary of tasks completed last week:
* Generalized the trim code to handle intersecting trim curves (required substantial alterations)
* Wrote code to handle the "trim curve completely inside tessellation polygon" special case even in situations where finding a connection is tricky (e.g. requires reversing one of the polygons and checking for intersections).
* Made progress integrating this into blender, but I'm not to the point of actually importing trimmed surfaces yet.

Todo next week:
* Finish the actual blender integration
* Handle revolution surfaces using the technique from the libnurbs library (opennurbs doesn't want to convert them to NURBS surfaces even though it's completely possible)
* Figure out how trim curves are handled in polar coordinates
* Make sure trimming lines up at the edges both for periodic surfaces and for mated boundaries.

Todo beyond next week:
* Expose NURBS tools for generating revolution/loft/sweep surfaces.

On Jun 30, 2014, at 2:28 PM, Campbell Barton <ideasman42 at gmail.com> wrote:

> Hi, I've been recently working on blender's triangulators, heres a
> brief overview.
> 
> polyfill2d (used for bmesh ngons)
> - originally based on simple tessellator from libgdx (though its been
> updated quite a lot),
> - guarantees valid topology even for degenerate cases
> - quite fast (optimized recently for large polygons 100,000+ sides)
> - no hole support. (but could be supported by creating edges between
> holes and treating as one large polygon).
> 
> scanfill (used for text and 2d curves)
> - supports holes
> - no guarantees for valid geometry (degenerate polygons may miss faces)
> - own recent tests its approx 6x slower then polyfill2d on ~75k-sided
> concave polygon. - ymmv.
> - takes 3d points and handles conversion to 2d, (though this is really a detail)
> 
> Both are quite robust, libgdx found and fixed many corner cases.
> scanfill has been in blender for ~20 years.
> 
> 
> On Tue, Jul 1, 2014 at 3:20 AM, Sergey Sharybin <sergey.vfx at gmail.com> wrote:
>> For my knowledge blender's triangulator first projects 3d vertex coordinates
>> onto the plane using face normal as a direction, then calls
>> BLI_polyfill_calc in order to get triangles.
>> 
>> As for OO interface, i'm not sure why it's needed? Blender's core is written
>> in C, and you'll end up adding C-API for the tesselator i'm afraid?
>> 
>> 
>> On Sat, Jun 28, 2014 at 12:51 PM, Jonathan deWerd <jjoonathan at gmail.com>
>> wrote:
>>> 
>>> Progress:
>>> 1. Wrote a quick triangulator (concave polygon->triangles) using GLU [1].
>>> I doubt this is acceptable for integration into blender but I don't know how
>>> to hook directly to blender's triangulation code, at least not without
>>> making a BMesh. I'd appreciate help here -- Blender's mesh data structures
>>> are intimidating to navigate.
>>> 
>>> Once I implemented the triangulation code it became apparent that code I
>>> had written earlier had significant bugs, both of the trivial sort and the
>>> structural sort. Much of last week was spent chasing down the "structural"
>>> bugs.
>>> 
>>> 2. Altered debug visualization code to pull degenerate lines off one
>>> another so I could see the problem (see attached screenshots and note that
>>> proximal parallel lines are actually degenerate in the data structures).
>>> 
>>> 3. The raster code used to bring the number of line-line intersection
>>> checks from O(N^3) to O(N) did not preserve the order of the intersections,
>>> leading to degenerate trim lines that zig-zagged back and forth on top of
>>> one another. These degenerate appeared fine in my visualization code but
>>> obviously did not triangulate correctly. Altering the code to preserve
>>> intersection order required expanding all 8 cases of the simplified 2-case
>>> raster algorithm and writing simple GL code to ensure it actually worked. It
>>> is worth mentioning that this improvement will perform double-duty in the
>>> future RSD tessellator.
>>> 
>>> 4. The uniform grid hit a nasty edge-case of the chalk-cart algorithm when
>>> it crossed the border from one cell to another (the entry and exit
>>> intersections were degenerate). After one failed fix (keeping a linked list
>>> of degenerate intersections) I stumbled on an approach that works much
>>> better by keeping track of the parent polygon of each vertex.
>>> 
>>> 5. I migrated this code into an OO interface that a) dramatically cut down
>>> on the number of globals+parameters passed to each function, b) reduced
>>> duplication and the silly mistakes I kept making as a result, c) made it
>>> easier to debug since vertices are now identified with small integers rather
>>> than pointers, d) probably made things faster because vertices are ~1/3 the
>>> size and local in memory.
>>> 
>>> Todo:
>>> 1. Figure out how to use blender's triangulation code (or if I can use
>>> GLU's).
>>> 2. Hook it up to the import code!
>>> 
>>> 
>>> [1] http://www.songho.ca/opengl/gl_tessellation.html
>>> 
>>> On Jun 22, 2014, at 6:10 AM, Jonathan deWerd <jjoonathan at gmail.com> wrote:
>>> 
>>> Sorry the report is a day late -- I was really hoping to have everything
>>> wrapped up so that I could report complete success for importing trimmed
>>> surfaces. I am very close, but it won't be done in time for the weekly
>>> meeting, so now I'm aiming for the end of Sunday.
>>> 
>>> Progress:
>>> * Generalized trim to multiple subject polygons
>>> * Generalized trim to multiple subject polygons with overlapping edges
>>> * Implemented raster algorithm so that line intersection against a grid is
>>> fast (+ debug viz code to prove it works as intended)
>>> * Added surfaces to the 3dm import code. It now imports all ON_Curve and
>>> ON_Mesh subclasses. ON_Surface subclasses are imported if they can be
>>> coerced into ON_NurbsNurface form.
>>> * Began writing OO interface to the trim code (the RSD tesselator will
>>> subclass this interface)
>>> 
>>> Todo:
>>> * Finish writing the interface
>>> * Figure out how to use the blender 2d polygon->triangle code
>>> * Transplant the trim code into blender's tessellation routine
>>> 
>>> I aim to have the "Todo" tasks finished by tomorrow so that I can have a
>>> gallery of trimmed surfaces for the midterm. Right now I only have untrimmed
>>> surfaces and crummy GLUT visualizations of the trimming process :)
>>> 
>>> On Jun 19, 2014, at 1:21 PM, Jonathan deWerd <jjoonathan at gmail.com> wrote:
>>> 
>>> No problem, I'll merge it in. It looks like I can do it while maintaining
>>> history, but at the cost of introducing a history branch with radically
>>> different structure. This might confuse history-parsing scripts so I'm
>>> inclined to just copy it instead.
>>> 
>>> 
>>> http://gbayer.com/development/moving-files-from-one-git-repository-to-another-preserving-history/
>>> 
>>> One question. My original motivation for putting it on github was that I
>>> have debug GLUT code that I don't know where to put. If there's a bug in the
>>> tessellator, it would be helpful to have the GLUT debug code. Should I just
>>> put the cpp files in the same folder but not add them to CMake?
>>> 
>>> On Jun 19, 2014, at 5:21 AM, Ton Roosendaal <ton at blender.org> wrote:
>>> 
>>> Hi,
>>> 
>>> I want to refer to the instructions of 19 May.
>>> 
>>> - Do not use github, please work on the git.blender.org repo you had.
>>> - Commit as much as possible, at least at end of day.
>>> 
>>> -Ton-
>>> 
>>> --------------------------------------------------------
>>> Ton Roosendaal  -  ton at blender.org   -   www.blender.org
>>> Chairman Blender Foundation - Producer Blender Institute
>>> Entrepotdok 57A  -  1018AD Amsterdam  -  The Netherlands
>>> 
>>> 
>>> 
>>> On 17 Jun, 2014, at 6:22, Jonathan deWerd wrote:
>>> 
>>> Last week was a low-productivity week, there's no denying that. It
>>> happened due to a handful of factors. A few things to keep in mind:
>>> * The "chalk-cart" logic is actually still in the display routine, not
>>> poly.cpp.
>>> * Learning about Rhino's trim tools didn't produce an immediate
>>> deliverable, but it almost certainly will be helpful or necessary for the
>>> midterm.
>>> * Time spent looking at raster literature hasn't filtered through the
>>> pipeline yet. Not until tomorrow.
>>> * Subdivision/tessellation and trimming require different algorithms,
>>> which meant more reading before I could start writing code. My intent was to
>>> produce an implementation, not a literature survey, so you don't see a pile
>>> of text, just a relatively small bit of code. Code that someone with a
>>> proper computational geometry background could have written and debugged in
>>> an afternoon rather than days. But I don't come from a computational
>>> geometry background, I come from a numerics background, so I have to learn.
>>> * I didn't find IsectLLPt2Df(), so I wound up re-implementing it. I must
>>> remember to search for these things more thoroughly. It represents a sizable
>>> fraction of the deliverable but not as large a fraction of the time spent
>>> producing the deliverable. LL was easy to find, easy to understand, easy to
>>> write, and didn't need debugging.
>>> * External: a cold during the later part of the week/weekend. Better now.
>>> 
>>> I have to scramble to get UGC working before the midterm, but I'm still
>>> confident I can get it done in time.
>>> 
>>> Regards,
>>> Jon
>>> 
>>> 
>>> On Jun 16, 2014, at 5:21 PM, Sergey Sharybin <sergey.vfx at gmail.com> wrote:
>>> 
>>> I'm not really sure why it's taking so much time. That's like rather
>>> simple OGL visualization file and the file which is assumed to have trimming
>>> code only contains few of the functions. And half of the functions does
>>> exist in BLI, remaining part doesn't seem to do the actual business.
>>> 
>>> Getting into account you've spent whole previous week in the research
>>> looking into algorithm details i'm not really sure what's causing
>>> difficulties now.
>>> 
>>> 
>>> On Sat, Jun 14, 2014 at 10:56 PM, Jonathan deWerd <jjoonathan at gmail.com>
>>> wrote:
>>> That would be great! Send me 3dm files and I'll try to include them in my
>>> midterm. I can't make promises this early: it's possible you make heavy use
>>> of a feature that I won't get around to implementing until after the
>>> midterm, but I'll do what I can. Either way production 3dm files will
>>> provide valuable information regarding what work I should prioritize.
>>> 
>>> Thanks for your interest,
>>> Jon
>>> 
>>> 
>>> On Jun 14, 2014, at 10:59 AM, claas kuhnen <info at ckbrd.de> wrote:
>>> 
>>> I can provide you think models from my design work including meshes from
>>> example moi so you can compare if you are interested.
>>> 
>>> I am very excited about this project.
>>> 
>>> Claas
>>> 
>>> On Jun 14, 2014 5:45 AM, "Jonathan deWerd" <jjoonathan at gmail.com> wrote:
>>> This week's progress:
>>> - About 75% of the way to the trimming code for the UGC tessellator.
>>> -- Details:
>>> http://wiki.blender.org/index.php/User:Jjoonathan/Trim_Algorithms
>>> -- Code: https://github.com/jjoonathan/PolyTest/tree/master/PolyTest
>>> - Not sure how I should write up my midterm proposal, but I stated my
>>> intention on the wiki page to put up a gallery of imported 3dm files. I
>>> anticipate being able to show at least one from an interested artist, a
>>> handful from grabcad.com, and a few of my own that really show off trimming
>>> (I've gone through the lynda.com tutorials for the corresponding parts of
>>> Rhino)
>>> 
>>> What I want to have done by next friday:
>>> - Finish the trimming code
>>> - Put the UGC+trimming code in blender
>>> - Demos for the midterm to show it off
>>> 
>>> On Jun 7, 2014, at 5:50 AM, Jonathan deWerd <jjoonathan at gmail.com> wrote:
>>> 
>>> This week's progress:
>>> - Finished integrating opennurbs into cmake
>>> - Wiki page detailing the literature search and
>>> existing-implementation-review I did for the tessellator
>>> 
>>> http://wiki.blender.org/index.php/User:Jjoonathan/NURBS_Tessellation_Survey
>>> - Extensive comments in Nurbana (Uniform Grid Cut) and Mesa (Recursive
>>> Subdivision) tessellation code.
>>> 
>>> What I want to have done by next friday:
>>> - Surface import with Uniform Grid Cut trimming (yep, slid another week,
>>> as expected last week)
>>> - Midterm proposal (I really need to get on that!)
>>> 
>>> On May 31, 2014, at 3:56 AM, Jonathan deWerd <jjoonathan at gmail.com> wrote:
>>> 
>>> This week's progress:
>>> - I can successfully load order 2, 3, and 4 NURBS curves! To be clear: no
>>> surfaces yet and I haven't added support for a bunch of .3dm features, from
>>> small ones (not-open curves with irregular knots) to big ones (trimming).
>>> But I'm not held up on these, I'm hung up on...
>>> - Integrating opennurbs into cmake. I got my first result by manually
>>> tweaking the Xcode files that came out of cmake but this is no good in
>>> general. I've put opennurbs in the "extern" folder and I'm still working out
>>> how to persuade cmake to generate the appropriate build files.
>>> - Got a stakeholder .3dm testfile. It's not production data but it tests
>>> for a specific cut that was needed in production. I have lots of .3dms now:
>>> I have 3dms that I made, 3dms from stakeholders, and lots of 3dms from the
>>> Rhino example libraries.
>>> 
>>> Things that were done this week that weren't progress:
>>> - Reading trimming literature
>>> 
>>> What I want to have done by next Friday:
>>> - Integrating opennurbs into cmake
>>> - Surface import (ideally including trimming although I suspect it will
>>> slide another week)
>>> - Midterm proposal (didn't really work on it this week)
>>> 
>>> 
>>> Cheers,
>>> Jon
>>> 
>>> 
>>> 
>>> _______________________________________________
>>> Soc-2014-dev mailing list
>>> Soc-2014-dev at blender.org
>>> http://lists.blender.org/mailman/listinfo/soc-2014-dev
>>> _______________________________________________
>>> Soc-2014-dev mailing list
>>> Soc-2014-dev at blender.org
>>> http://lists.blender.org/mailman/listinfo/soc-2014-dev
>>> 
>>> 
>>> 
>>> _______________________________________________
>>> Soc-2014-dev mailing list
>>> Soc-2014-dev at blender.org
>>> http://lists.blender.org/mailman/listinfo/soc-2014-dev
>>> 
>>> 
>>> 
>>> 
>>> --
>>> With best regards, Sergey Sharybin
>>> _______________________________________________
>>> Soc-2014-dev mailing list
>>> Soc-2014-dev at blender.org
>>> http://lists.blender.org/mailman/listinfo/soc-2014-dev
>>> 
>>> 
>>> _______________________________________________
>>> Soc-2014-dev mailing list
>>> Soc-2014-dev at blender.org
>>> http://lists.blender.org/mailman/listinfo/soc-2014-dev
>>> 
>>> 
>>> _______________________________________________
>>> Soc-2014-dev mailing list
>>> Soc-2014-dev at blender.org
>>> http://lists.blender.org/mailman/listinfo/soc-2014-dev
>>> 
>>> 
>>> 
>>> 
>>> 
>>> _______________________________________________
>>> Soc-2014-dev mailing list
>>> Soc-2014-dev at blender.org
>>> http://lists.blender.org/mailman/listinfo/soc-2014-dev
>>> 
>> 
>> 
>> 
>> --
>> With best regards, Sergey Sharybin
>> 
>> _______________________________________________
>> Soc-2014-dev mailing list
>> Soc-2014-dev at blender.org
>> http://lists.blender.org/mailman/listinfo/soc-2014-dev
>> 
> 
> 
> 
> -- 
> - Campbell
> _______________________________________________
> Soc-2014-dev mailing list
> Soc-2014-dev at blender.org
> http://lists.blender.org/mailman/listinfo/soc-2014-dev