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

[Sergey Sharybin]

Wouldn't really worry about speed at this point, it could be optimized any
time later.

Is it all commited so checking out your branch would let playing around
with the new tessellator?

Also, bet you're pretty close to modifying nurbs DNA to support trimming.
Any particular plans how it'll fit all together already?


On Thu, Jul 10, 2014 at 1:16 PM, Jonathan deWerd <jjoonathan at gmail.com>
wrote:

> Apparently it performs slightly better :->
>
> Untrimmed quads do get a fast path, so this isn't fantastically
> surprising. Even so the benchmark probably isn't very meaningful because I
> did it in a debug build without optimization -- perhaps the order my code
> accesses everything (without compiler optimization) was slightly easier on
> the cache. The advantage could disappear at -O2 (it's late, maybe I'll try
> it tomorrow, probably not). Regardless, I'm happy with it.
>
> I'm not happy with the growth in time as the number of sides on the
> trimming poly increases, but this is due to a missing optimization that I
> haven't implemented yet (point_in_poly gets called needlessly often if the
> grid is intersected in certain ways). Now I guess there's reason to
> actually go and fix it.
>
>
>
> On Jul 9, 2014, at 4:47 AM, Sergey Sharybin <sergey.vfx at gmail.com> wrote:
>
> 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
>  _______________________________________________
> 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/20140710/889a100a/attachment-0001.htm