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

[Sergey Sharybin]

Did you try using new tessellator instead of the old one and see how it
performs on the non-trimmed NURBS?


On Sun, Jul 6, 2014 at 11:58 PM, Jonathan deWerd <jjoonathan at gmail.com>
wrote:

> 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
>
> _______________________________________________
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.blender.org/pipermail/soc-2014-dev/attachments/20140709/5baa126d/attachment-0001.htm