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

Sat Jun 28 08:51:14 CEST 2014

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
>> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.blender.org/pipermail/soc-2014-dev/attachments/20140628/186327b0/attachment-0001.htm 
-------------- 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/20140628/186327b0/attachment-0003.png 
-------------- 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/20140628/186327b0/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/20140628/186327b0/attachment-0005.png 