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

Mon Jun 30 20:28:32 CEST 2014

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