[brlcad-devel] Summary from yesterday's discussions re: parametrics/constraints

[Bryan B. <ka...@gm...>]

Hello world.

I enjoyed our conversation yesterday in the channel. I was wondering
about a few things, and also figure some of the thoughts should be
documented if I'm going to seriously consider GSoC 2009 with BRLCAD
:-). First, some links. (And for the record, I don't know if this
should be counted as an official GSoC application, since I am more
interested in getting feedback at this point.)

http://brlcad.org/wiki/A_Survey_of_Implicit_Constraints_in_Primitives
http://brlcad.org/wiki/Libpg_:_A_parametrics/constraint_library
libpc src: http://brlcad.svn.sourceforge.net/viewvc/brlcad/brlcad/trunk/src/libpc/
http://brlcad.org/wiki/Google_Summer_of_Code/Project_Ideas#Constraints_and_Parametrics
http://brlcad.org/wiki/Google_Summer_of_Code/2008#Parametric_Equations_and_Constraint_Support
a blank page? http://brlcad.org/wiki/Constraint_Satisfaction
previous developer log: http://parametrics.wordpress.com/

Can someone help clarify the following section?

"""
Implicit : Constraints implicit in the definition of a primitive :
Tangency or perpendicularity of Vectors, Equality of scalars etc.
Explicit : Constraints explicitly expressed between two or more primitives.

One of the intricate parts of the work is the actual integration of
libpc with librt. Associated work going on with libpc involves the
creation of a Math Virtual Machine for parsing and evaluating (math)
expressions which would be used for stating the constraints, along
with the grammar.
"""

I was wondering about the "explicit constraints" in particular. What
does this mean, and can anyone give me an example of another CAD
software package that implements that, or how it would be used, or
something? Also, what about this "Math Virtual Machine", what does
this /mean/? So, presumably, users would type up some sort of
mathematical expression which would state/specify constraints? When
I've used parametric CAD systems before, I never had to do that- or
I've never seen those options- but it's entirely possible that it's
very important and something that I should know about.

Another topic that we were talking about--

"""
Boost Graph Library : for graph based representation of the
constraints. Since BGL does not have support for Hypergraphs, the
author plans to implement hypergraphs independently while adhering to
Boost standards ( probable addition to boost itself)

Boos Spirit Library : for the parser based generation of constraint
objects from expressions.
"""

It has been many years since I've worked with the boost library.
However, recently I have been working in the Automated Design Lab here
at the University of Texas at Austin, on projects involving generative
grammars and graph grammars for mechanical engineering problems. For
instance, some of the recent work is in the automated design and
optimization of gear trains; another fellow works on linkage design,
and another on product disassembly sequencing.

GraphSynth
http://graphsynth.com/

Example, re: gears
http://heybryan.org/~bbishop/docs/gears/gears.html
(and, btw, I'm working on a gear-CAD generator as a visualization
frontend to replace the hacked glxgears script; I've been working on
it in pythonOCC, though I might switch on over to BRLCAD)

There's a few classes there for the representation of graphs. The way
that graph grammars work is by search-and-replace, more or less. Each
grammar rule has a left-hand side and a right-hand side. The left-hand
side represents a subgraph that it should 'match', and the right-hand
side is the replacement. So, there's a 'ruleset' for different
domains- a ruleset consists of a list of different grammar rules. A
ruleset exists for linkages, for product disassembly, gears,
electronic filter circuits, etc., and maybe one will be implemented
for parametric constraints? The way that this works is that a 'seed
graph' (input) is given, and then it's recursion over the list of
possible rules that apply to it, and for each one that matches, that's
a branch that is taken, and the branches are explored either in a
breadth-first manner or depth-first manner, until there's no more
manipulations possible to the graph, at which point you have a list of
solutions to the original problem. Now, I'm not entirely sure about
explicit constraints and weird grammar notations for constraints, so
that's partly why I asked that question previously :-) so that I might
be able to see whether or not GraphSynth code (as opposed to the boost
library) would be appropriate here.

GraphSynth-related references- full bibliography (in BibTeX):
http://heybryan.org/books/Manufacturing/campbell/bibliography/campbell.bib

presentations: http://heybryan.org/~bbishop/docs/repo/presentations/
(older files are better, and I sincerely apologize for the pptx file
format- some I've been able to convert to ODP, however)

maybe this presentation would be most helpful:
http://heybryan.org/~bbishop/docs/repo/presentations/Wed3-KurtogluCampbell-From%20Black-Box%20To%20Component%20Selection.odp

** Relevant diagrams- **

Recognize-Choose-Apply
http://www.me.utexas.edu/~adl/graphsynth/images/generationProcess.png
^ the general recognize-choose-apply that is automatically executed
for depth-first and breadth-first search methods.

Left-hand => right hand translocation
http://www.me.utexas.edu/~adl/graphsynth/images/applyProcess.png
^ the above is a diagram of how the left-hand side of a grammar rule
is spliced into a host graph, i.e. to avoid dangling arcs or
misconnected arcs/edges, and other things like that.

designGraph classes are usually serialized into XML
http://www.me.utexas.edu/~adl/graphsynth/images/designGraphXML.png

seed graph example
http://heybryan.org/~bbishop/docs/repo/2008-12-11/2008-12-11_waterlifting.gxml

screenshot of that example in GraphSynth
http://heybryan.org/~bbishop/docs/repo/2008-12-11/2008-12-11_waterlifting.png.PNG

One idea that I suggested to 'madant' over IRC yesterday was the idea
of representing constraint problems as a seed graph in GraphSynth by
having two types of nodes- those nodes which represent an object in
BRLCAD's dot g database, and those nodes which represent the type of
constraint (parallel, perpendicular, etc.). So, any two nodes that are
connected by a node of label 'parallel_$unique_ID' would be required
to be parallel, and then some other labels would specify the xyz
coordinates (or something), which means the graph for two
perpendicular objects constrained to one two dimensions would be
"objectA <-> perpendicular_1 <-> objectB" (in reality, there's more
than two dimensions to deal with). The work that would need to be done
is a ruleset for manipulating those graphs by recognizing the
scenarios of perpendicularity and parallelism, and other types of
constraints, and consequently find all possible ways of solving those
constraints- which I suspect will probably involve a subset of matrix
math rules or vector math rules. And again, the idea would be that
GraphSynth would go through the recognize-choose-apply loop and
automatically generate all possible solutions to the original
constraints/seed graph, and then spit out those solutions to
{something} (which I need some clarification on, like I said- maybe a
user would select from a command line which option to use to solve the
constraints problem when resizing, or something?) How about some user
case stories? That would be amazingly helpful. I suspect this code
would be implemented and integrated as the backend constraints
solution engine, but I'm also open to the idea of gluing it together
with shell or command line utilities depending on how exactly it's
supposed to work when seamlessly integrated (just to make sure I
understand completely).

So, if I can get some feedback on those issues, that would be great,
and maybe also whether or not anyone would be interested in my working
on this for GSoC? I have to admit that I'm a little sketchy on some of
the implementation details- like how exactly the constraint expression
grammar could work, or how to integrate this into the user interface
(or, as I'd prefer, into the shell utilities), but that's something
that more seasoned developers can make some comments on. And if
there's some green lights, I'll definitely spend some more time doing
a formal writeup for GSoC. One quick dislcaimer about GraphSynth- the
professor who puts most of his effort into it has not been clear on
the licensing in the software distribution on graphsynth.com, but
however has expressed an interest in throwing it up as GPL (or
possibly LGPL), but I feel this is a minor detail and something that
can be fixed.

Since this is the first time I've made an appearance on the mailing
list, I figure I should say a few words about myself. I am a student
in mechanical engineering at the University of Texas at Austin, I'm
presently a freshman; my main medium of communication is IRC and
email- a few of you (Sean?) might know me from the channel, I was more
active a few months ago when I was playing around with BRLCAD with a
script I was working on to automatically generate spiral membraneless
filters to separate cells from water (it's for another lab I'm
employed with). I actually have some screenshots and images related to
this- if anyone is interested in how it turned out-

http://heybryan.org/bioreactor/membraneless_filtration/2008-11-25_gnuplot.png
http://heybryan.org/bioreactor/membraneless_filtration/2008-12-15_brlcad.png
http://heybryan.org/bioreactor/membraneless_filtration/2008-12-16_spiral_generator_2.png
http://heybryan.org/bioreactor/membraneless_filtration/2008-12-16_spiral_generator_2_other_issue.png
http://heybryan.org/bioreactor/membraneless_filtration/2008-12-16_spiral_generator_works.png
http://heybryan.org/bioreactor/membraneless_filtration/2009-01-22.png
http://heybryan.org/bioreactor/membraneless_filtration/2009-02-01.png
one-half the physical object:
http://heybryan.org/bioreactor/membraneless_filtration/2009-03-18_spiral.jpg

In truth, the spiral flter design generator was not used to make the
design that is in that photograph, although I am still working on it
(off and on). In particular, I remember also trying out the brlcad
pipes command (thanks to Sean, again), and maybe I'll go back to that
at some point. Recently elmerfem successfully compiled and began
working on my development machine, so there's also the opportunity to
explore the fluid dynamics of the delta density of flows through this
elegant contraption. (and also the possibility of sharpie
microfluidics- of being able to draw similar designs with a sharpie
and a paperclip between two sandwiched CDs- which I posted to the
diybio mailing list, if anybody is interested in that, or the design
possibilities related to that, but this is quickly becoming
off-topic.)

Anyway, back to the 'about me'. I have been programming for ages, been
submitting a few patches to a few different projects, my most favorite
(and most simple!) was a patch to KDE for the vertical kicker taskbar
in 3.5 so that you don't have to hold down the little arrows to scroll
when you have many hundreds of windows open (something you might
recognize from the screenshots)- so now the mousewheel properly works
and it's much easier to get to everything's that open (other than
ALT+TAB). More broadly, I cultivate an interest in mostly anything-
more recently it has been in open source hardware and open
manufacturing ( http://openmanufacturing.net/ ), which means exploring
areas like semiconductor manufacturing, machining, microfluidics,
electronic design automation, singularity-related technologies, etc. I
have over 15,000 bookmarks, 170+ mailing list subscriptions, many
hundreds of forums that I try to keep an eye on, and am generally an
intense fellow. Hi. Please don't make me list all past programming
projects :-). More stuff on my website for the "about me" aspects-
feel free to email me off-list if this isn't detailed enough, so that
I don't clog the mailing list with "me me me" :-).

After looking at Manuel's application, maybe I've gone a bit overboard
here with details?
http://sourceforge.net/mailarchive/forum.php?thread_name=200803310541.10578.manuel.montezelo%40gmail.com&forum_name=brlcad-devel

Okay. That's all for now.

- Bryan (irc nickname: 'kanzure')
http://heybryan.org/
1 512 203 0507

Automated Design Lab
University of Texas at Austin
http://www.me.utexas.edu/~adl/
http://twitter.com/UTADLab