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

Mon Jun 30 19:20:45 CEST 2014

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.blender.org/pipermail/soc-2014-dev/attachments/20140630/b7c2e83e/attachment-0001.htm 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: screenshot2.png
Type: image/png
Size: 24424 bytes
Desc: not available
Url : http://lists.blender.org/pipermail/soc-2014-dev/attachments/20140630/b7c2e83e/attachment-0003.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: screenshot1.png
Type: image/png
Size: 23157 bytes
Desc: not available
Url : http://lists.blender.org/pipermail/soc-2014-dev/attachments/20140630/b7c2e83e/attachment-0004.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: screenshot3.png
Type: image/png
Size: 17269 bytes
Desc: not available
Url : http://lists.blender.org/pipermail/soc-2014-dev/attachments/20140630/b7c2e83e/attachment-0005.png 