Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.
Close
From: Bryan Bishop <kanzure@gm...>  20090319 19:12:21

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 gearCAD 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 searchandreplace, more or less. Each grammar rule has a lefthand side and a righthand side. The lefthand side represents a subgraph that it should 'match', and the righthand 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 breadthfirst manner or depthfirst 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. GraphSynthrelated 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/Wed3KurtogluCampbellFrom%20BlackBox%20To%20Component%20Selection.odp ** Relevant diagrams ** RecognizeChooseApply http://www.me.utexas.edu/~adl/graphsynth/images/generationProcess.png ^ the general recognizechooseapply that is automatically executed for depthfirst and breadthfirst search methods. Lefthand => right hand translocation http://www.me.utexas.edu/~adl/graphsynth/images/applyProcess.png ^ the above is a diagram of how the lefthand 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/20081211/20081211_waterlifting.gxml screenshot of that example in GraphSynth http://heybryan.org/~bbishop/docs/repo/20081211/20081211_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 recognizechooseapply 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/20081125_gnuplot.png http://heybryan.org/bioreactor/membraneless_filtration/20081215_brlcad.png http://heybryan.org/bioreactor/membraneless_filtration/20081216_spiral_generator_2.png http://heybryan.org/bioreactor/membraneless_filtration/20081216_spiral_generator_2_other_issue.png http://heybryan.org/bioreactor/membraneless_filtration/20081216_spiral_generator_works.png http://heybryan.org/bioreactor/membraneless_filtration/20090122.png http://heybryan.org/bioreactor/membraneless_filtration/20090201.png onehalf the physical object: http://heybryan.org/bioreactor/membraneless_filtration/20090318_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 offtopic.) 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, singularityrelated 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 offlist 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=brlcaddevel 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 
From: Dawn Thomas <thedawnthomas@gm...>  20090320 02:39:15
Attachments:
Message as HTML

Hi Kanzure, 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. Now take two spheres and you might want to guarantee that they are always perfectly tangent to each other  that'd be an explicit constraint. Or consider just the one sphere and say that you want to require that the sphere always have a radius between 1 meter and 12 meters  another explicit constraint. Those constraints, whether implicit or explicit are a series of expressions that associate with and refer to geometric entities. The MVM he refers to there is a system for evaluation those expressions and constraints. This is pretty common in most CAD systems where you can fully/under/over constrain a given model. Some even give you a convenient little red light / green light to let you know when you're fully constrained. Implicit constraints as Sean explained are basically constraints implicit in the definition of each primitive. It might be simple like perpendicularity, parallelism, equality etc. to more complex cases (tgc for instance) Explicit constraints are effectively 1. constraints between primitives ( variables of primitives : radius of sphere == radius of a cone for instance) or 2. constraints between variables of the same primitive (consider a cone whose volume is fixed : height is dependent on its radius squared) These two cases can be unified into saying constraints between "Variables" which are not necessarily involved in the definition of the geometry. Regarding MathVM : Our idea of constraint expression is to support a large spectrum of mathematical expressions in defining the constraints. This is a very critical part of the actual utility of constraints since otherwise we would be limiting the type of constraints defineable. For this purpose we could take various approaches. Lazy functions seem to be a good bet. The idea is that the solver would call the MathVM to evaluate the constraint expressions while traversing the hypergraph modifying the state of the constraints. If you have used CATIA for instance using f(x) tool u can specify quite advanced expressions between primitive parameters. 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. > Regarding BGL: My primary thoughts were the advantages of not having to recode various traversal alorithms and boost being a very good container library in a sense it is a very sensible approach to code reuse. Spirit and Phoenix libraries are very helpful in terms of parsing of the expressions i mentioned above. There's a few classes there for the representation of graphs. The way > that graph grammars work is by searchandreplace, more or less. Each > grammar rule has a lefthand side and a righthand side. The lefthand > side represents a subgraph that it should 'match', and the righthand > 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 > breadthfirst manner or depthfirst 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. > > GraphSynthrelated references full bibliography (in BibTeX): > http://heybryan.org/books/Manufacturing/campbell/bibliography/campbell.bib > Regarding Graphsynth, regarding the query about the conditional constraints, your suggestion was to specify the same in the Grammar. Let me just restate the case here: Vertices : A, B, C, D ,E and F Constraints: 1. A perp B 2. C perp. D 3. E perp. F if A perp. B and C perp. D else E parallel F I am wonering whether by that you meant specifying a ruleset ( hope i am not messing up on Graphsynth terminology here) specifying if you find A perp. B and C perp. D make E perp. F. But there maybe other parts in the graph ( say X perp. Y and Z perp. W which need to be connected in a similar way to T perp. U) What I am trying to say is , don't you think the arc object definition as per the xml here( http://www.me.utexas.edu/~adl/graphsynth/graphs.htm ) is insufficient to take into consideration such cases. Could you share the xml and ruleset for the above case if it is possible ? My idea is that the designgraph should be completely able to reprsent the particular design with the ruleset there being to do the actual "Evaluation" and "Generation". Am I wrong in this regard? Also regarding an example of a logical constraint ( see again tgc implicit constraint 4), though i feel this might be reprsentable in Graphsynth. A pattern based search for constraints and associated graph reduction based solutions is very effective for various applications as graphsynth shows with its breadth. But do you think it has any clear advantages in terms of geometrical constraint modeling ? Also, are there any results on the scalability ? Compared to various discrete problems ( circuitry for instance or linkages ) performance is going to be a major issuing when searching a large solution space. I understand that you are comfortable with Graphsynth. But do you think it would have any significant advantages over 1. brlcad coding our own solver ( not transforming graphsynth code for instance) 2. utilization of some generic constraint solvers like minion. 3. utilization of geometric constraint solvers. > > presentations: http://heybryan.org/~bbishop/docs/repo/presentations/<http://heybryan.org/%7Ebbishop/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/Wed3KurtogluCampbellFrom%20BlackBox%20To%20Component%20Selection.odp<http://heybryan.org/%7Ebbishop/docs/repo/presentations/Wed3KurtogluCampbellFrom%20BlackBox%20To%20Component%20Selection.odp>; > > ** Relevant diagrams ** > > seed graph example > > http://heybryan.org/~bbishop/docs/repo/20081211/20081211_waterlifting.gxml<http://heybryan.org/%7Ebbishop/docs/repo/20081211/20081211_waterlifting.gxml>; > > screenshot of that example in GraphSynth > > http://heybryan.org/~bbishop/docs/repo/20081211/20081211_waterlifting.png.PNG<http://heybryan.org/%7Ebbishop/docs/repo/20081211/20081211_waterlifting.png.PNG>; > [Offtopic: Interesting :) Are these energy based constraints ? What are the coloured edges ] > 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. Refer to the example i mentioned above. > And again, the idea would be that > GraphSynth would go through the recognizechooseapply 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). In terms of the user interface the scenario I am visualizing is ( eg. say a sphere is constrained in relation with a box : lets say there are three variables which are presently not constrained enough : Radius of the sphere, point of tangency ( considering the constraint is that the spehere and box touch each other tangentially). The user could be shown a slider for instance showing the spectrum of radii possible as well as (two sliders?) for the position of tangency. Now selection of any one of these might completely constrain the objects : Selection of a radius for instance might if the centre of the sphere is already constrained, Or selection of the xcoordinate for the point of tangency ( It may not in which case the y coordinate might be constrained and again request the user for the radius) ) http://heybryan.org/bioreactor/membraneless_filtration/20081125_gnuplot.png > > http://heybryan.org/bioreactor/membraneless_filtration/20081215_brlcad.png > > http://heybryan.org/bioreactor/membraneless_filtration/20081216_spiral_generator_2.png > > http://heybryan.org/bioreactor/membraneless_filtration/20081216_spiral_generator_2_other_issue.png > > http://heybryan.org/bioreactor/membraneless_filtration/20081216_spiral_generator_works.png > http://heybryan.org/bioreactor/membraneless_filtration/20090122.png > http://heybryan.org/bioreactor/membraneless_filtration/20090201.png > onehalf the physical object: > > http://heybryan.org/bioreactor/membraneless_filtration/20090318_spiral.jpg > neat ;) hope this helps, sincerely yours,  Dawn Thomas " the strength to change what i can, the inability to accept what i can't, and the incapacity to tell the difference" 
From: Bryan Bishop <kanzure@gm...>  20090323 14:24:00

On Thu, Mar 19, 2009 at 9:39 PM, Dawn Thomas <thedawnthomas@...> wrote: > I understand that you are comfortable with Graphsynth. But do you think it > would have any significant advantages over > > 1. brlcad coding our own solver ( not transforming graphsynth code for > instance) No. > 2. utilization of some generic constraint solvers like minion. Nope. > 3. utilization of geometric constraint solvers. Not at all. I think these methods would be much better, since they would be doing things "right". >> seed graph example >> >> http://heybryan.org/~bbishop/docs/repo/20081211/20081211_waterlifting.gxml >> >> screenshot of that example in GraphSynth >> >> http://heybryan.org/~bbishop/docs/repo/20081211/20081211_waterlifting.png.PNG > > [Offtopic: Interesting :) Are these energy based constraints ? What are the > coloured edges ] The colored edges were a cheap hack I implemented in GraphSynth. You see, when you get a seed graph, you know that you have some rules in your ruleset that are going to replace certain nodes or subgraphs or something, but what you don't know immediately is whether or not your graph is solveable. It's entirely possible that your ruleset (domain knowledge, I guess) isn't complete, so what I implemented was a way to color the edges and nodes to represent whether or not there's a rule that recognizes them. This way, we don't spend a few hours going through hundreds of thousands of designs all only to realize that we weren't ready to begin.  Bryan http://heybryan.org/ 1 512 203 0507 