From: Dawn Thomas <thedawnthomas@gm...>  20080619 15:58:01

Hi John, I have done a commit of some basic classes necessary for the constraint solution ( Variable, Domain, Interval ). The next step in the represenation of the Constraint Network is a graph. I was planning on using the boost library's graph structures ( adjacency_matrix , adjacency_list etc. http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/graph_theory_review.html) They provide sufficient traversal mechanisms which i can redefine/ overload later when we actually do the solution search using the graph structure. Would we have an existing structure in bu/bn/rt which could act as a graph with associated methods ? My immediate plan is to make a minimal/ simple constraint network solver which traverses the network graph testing the constraints using bruteforce + backtracking and stores the solution. Sean and I feel that testing that with the implicit constraint checking ( things inside rt_*_prep ) right now would be a good test to see if the whole architecture works. In effect the overall idea as of now 1. rt_*_params() << need to rename >> functions for each primitive which return parameters and constraints ( as a pc_pc_set structure) 2. src/libpc contains the necessary class definitions and headers 3. libpc takes the pc_set structure and generate the constraint network graph 4. libpc solves the constraint network graph and produces a solution structure 5. update geometry via a perprimitive function analogous to rt_*_params() This would be sufficient for implicit constraint checking. After this stage we can utilise the pc_import and export functions ( in librt) for dbio. Once the explicit constraint has been loaded into an internal struct it can be passed on to the solver analogous to the implicit ones. This part requires further clarification and thought. sincerely yours,  Dawn Thomas IIT Kharagpur " the strength to change what i can, the inability to accept what i can't, and the incapacity to tell the difference" 
From: John Anderson <D<aytona@co...>  20080621 00:07:41

Dawn, Sounds good. We have a "union tree" structure (see raytrace.h), but it is specific to the BRLCAD geometry hierarchy. I think using the Boost library is a good idea. Looks like it has a very nonconstraining license, and allows you to spend your time on the guts of the problem at hand rather than coding your own graph utilities or trying to hack ours to meet your needs. I encourage testing as you go (as you mentioned). Success is much more likely if you know that all the pieces are working before you try putting everything together. A couple random thoughts/questions: If the constraints are stored as objects in the database file, they will need names (as I see you already know). Do you intend for the constraint object names to be exposed to the users? If not, a method could be developed to provides unique names that are not likely to collide with user created names. I guess this could be addressed in a UI developed later. I suspect the solving of the constraints will need to be triggered in a few places. Obviously, some command in MGED to run the constraint solver. Also in rt, to get the constraints evaluated prior to raytracing. I suspect this should be done in "rt_gettree_leaf" (tree.c in librt) before the prep routine of the primitive is called (or perhaps from the prep routine itself). These are still down the road a bit, but just wanted to put these thoughts in the back of your mind as you proceed. I think these emails are a good way for all of us to keep up to date on what is happening. Would you be agreeable to doing this at least weekly? Of course, anytime you have questions, feel free to contact me. Keep up the good work!!! John Dawn Thomas wrote: > Hi John, > > I have done a commit of some basic classes necessary for the > constraint solution ( Variable, Domain, Interval ). The next step in > the represenation of the Constraint Network is a graph. > I was planning on using the boost library's graph structures ( > adjacency_matrix , adjacency_list etc. > http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/graph_theory_review.html) > They provide sufficient traversal mechanisms which i can redefine/ > overload later when we actually do the solution search using the graph > structure. Would we have an existing structure in bu/bn/rt which could > act as a graph with associated methods ? > > My immediate plan is to make a minimal/ simple constraint network > solver which traverses the network graph testing the constraints using > bruteforce + backtracking and stores the solution. Sean and I feel > that testing that with the implicit constraint checking ( things > inside rt_*_prep ) right now would be a good test to see if the whole > architecture works. > > In effect the overall idea as of now > > 1. rt_*_params() << need to rename >> functions for each primitive > which return parameters and constraints ( as a pc_pc_set structure) > 2. src/libpc contains the necessary class definitions and headers > 3. libpc takes the pc_set structure and generate the constraint network graph > 4. libpc solves the constraint network graph and produces a solution structure > 5. update geometry via a perprimitive function analogous to rt_*_params() > > This would be sufficient for implicit constraint checking. After this > stage we can utilise the pc_import and export functions ( in librt) > for dbio. > Once the explicit constraint has been loaded into an internal struct > it can be passed on to the solver analogous to the implicit ones. This > part requires further clarification and thought. > > sincerely yours, > > 
From: Dawn Thomas <thedawnthomas@gm...>  20080705 09:15:46

Hi John, > After thinking about it, perhaps one of my questions was ill conceived. I > was thinking that the solver would need to be called during the prep phase > of an rt execution, but it seems reasonable to me now that the constraints > would be created and solutions found during the design and building of the > geometry in mged. So that the geometry is completely defined before rt is > even called, and the solver need not be called during prep. Would you agree > with this reasoning? Yes, the geometry is completely defined before rt is called. The idea was to make simple constraints like is_perpendicular or is_positive is_tangent etc. which are basic relations in terms of generation and representation of geometry as of now and also forms a certain part of prep ( like isequal( A,B,C) or ispositive(R) and so on) As you might have seen from the commits, I have implemented a generic binary constraint solver. It is basically only a nondeterministic search system. I will be implementing various deterministic consistency techniques ( ArcConsistency 14 and Path consistency 17 ? ) over the next week. But more importantly i will be concentrating on the C side of things. In particular cleaning up the interaction with rt. Sean has done a few commits and given a rough outline in the commit messages. In particular, I will try to finish of the BNF parser as soon as possible. The idea is to have a clear separation between C structures used for storage and C++ objects used for computational solution. I will also do the much needed updation of Wiki ( apt job for network famine ) I have been traveling home over the past few days as i mentioned earlier and hence the scarcity of commits. I have reached home and am in the process of setting up broadband. Would probably be working via dialup till monday.  Dawn Thomas IIT Kharagpur " the strength to change what i can, the inability to accept what i can't, and the incapacity to tell the difference" 