Editing Libpg : A parametrics/constraint library

From BRL-CAD

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 1: Line 1:
 
{{DesignDocument}}
 
{{DesignDocument}}
==libpc: Parametrics and Constraints==
+
 
 +
= libpg : A parametrics/ constraint library =
  
 
Proposed sytem for parametrics and constraint implementation
 
Proposed sytem for parametrics and constraint implementation
Line 18: Line 19:
 
acts as a library which sits above librt using the librt methods for creation and modification of geometry
 
acts as a library which sits above librt using the librt methods for creation and modification of geometry
  
To efectively implement constraints, the library would first implement constraint functionality which currently exists in terms of implicit constraints ( Non negative radius, Perpendicular vectors etc. ) To see a list of implicit constraints in the various BRL-CAD primitives See [[A Survey of Implicit Constraints in Primitives]]
 
  
==Constraints and CSPs==
+
==Architecture==
  
 
A constraint system can be looked upon as a system of variables, their associated domains and set of constraints/relationships between the variables.
 
A constraint system can be looked upon as a system of variables, their associated domains and set of constraints/relationships between the variables.
  
Fundamentally this can be visualised using a constraint network which is a 3-tuple. Further we can have a graph based visualization of the same using vertices as variables and edges connecting vertices as constraints. It would be intuitive only for networks having binary (between two variables) or unary (with self) constraints. Otherwise, one has to visualize hypergraphs which contain hyperedges which is basically a line connecting multiple vertices for example. Also note that there could arise a situation where constraints depend on constraints ( edges connected to edges in the above discussion ) and hence such hypergraphs don't fit neatly into the bipartite graph structure.
+
Fundamentally this can be visualised using a constraint network which is a 3-tuple.For a mathematical review please see ( Constraint Networks by Dawn Thomas ). Further we can have a graph based visualization of the same using vertices as variables and edges connecting vertices as constraints. It would be intuitive only for networks having binary (between two variables) or unary (constraints on self) constraints. Otherwise, one has to visualize hypergraphs which contain hyperedges which is basically a line connecting multiple vertices for example.
 
 
For a short review of Constraints, and Constraint Satisfaction Problems as well as links to resources on Constraints in general and geometrical constraints in particular, please see [[Constraint Satisfaction]]
 
 
 
==Library architecture==
 
 
 
LibPC is composed of two sections which are functionally implemented using 4 modules as represented in the diagram below.
 
  
The modules respectively are ( in the order of operation during a read-out solution process)
+
Implementation of the above constraint network in the BRL-CAD system, involves 3 fundamental aspects.
  
# '''Reader/Import''' which reads from the .g file and generates C-based internal structs
+
# Domain extraction
# '''Constraint Network Generator/ Constraint Variable System Generator''' which takes the above structs and produces the respective Variable and Constraint (pcVariable.h and pcConstraint.h) class objects and their graph/hypergraph representation
+
# Solution
# '''Solver''' which takes the above Constraint Network as an input and generates a solution / multiple solutions or in effect a Solution object
+
# Geometry updation
  
# '''Geometry Updater''' which uses the above solution and takes care of the rest such as
+
Prerequisites for such a state is of course
* suggest user to select a value in case of multiple solutions for narrowing down the solution range
 
* update the various parameters of all '''associated geometry'''
 
* write the data onto the .g file
 
  
== Implementation Details==
+
# "Handle" generation and storage
 +
# Updated geometry storage
  
For effective integration with librt system as well as rest of existing brl-cad architecture, the Reader as well as Geometry Updater is entirely in C using standard datastructures. At the same time to make use of the functionality offered by various graph algorithms of boost as well as the power of object oriented programming model in constraint solution, the Constraint Network generator as well as solver is entirely coded in C++. Extensive use of Boost library is expected, in particular
+
A typical constraint solution operation is shown below.
  
# constrained_value system : for representing implicit constraints using a predicate system
+
==Object Architecture==
# 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.
 
Spirit is an object-oriented recursive-descent parser generator framework implemented using template meta-programming techniques. Expression templates allow us to approximate the syntax of Extended Backus-Normal Form (EBNF) completely in C++. Spirit details available at [http://www.boost.org/doc/libs/1_35_0/libs/spirit/index.html boost.org]
 
 
 
-- Content below is undergoing modification --
 
 
 
==Constraint object architecture==
 
  
 
An object oriented method of implementation would be the creation of a mixed ( in the sense that they contain both geometric and non-geometric information ) object. The object architecture is as shown below which shows the data types as well as the public and private methods.
 
An object oriented method of implementation would be the creation of a mixed ( in the sense that they contain both geometric and non-geometric information ) object. The object architecture is as shown below which shows the data types as well as the public and private methods.
Line 88: Line 73:
  
 
'''What should be the convention for naming the parameters ? Also there is a certain issue in the sense that some of the geometry are special cases of more generic geometry. So for a sphere we are concerned with only radius and center where as it is defined using ( point center) and 3 vectors (a b c). Should we name the parameter radius make 3 fastf_t * to a[0], b[1], and c[2] Or should we make 3 vectp_t to a,b,c or make 1 fast_t* to a[0], doing a further check/constraint that a[0]=b[1]=c[2] ?'''
 
'''What should be the convention for naming the parameters ? Also there is a certain issue in the sense that some of the geometry are special cases of more generic geometry. So for a sphere we are concerned with only radius and center where as it is defined using ( point center) and 3 vectors (a b c). Should we name the parameter radius make 3 fastf_t * to a[0], b[1], and c[2] Or should we make 3 vectp_t to a,b,c or make 1 fast_t* to a[0], doing a further check/constraint that a[0]=b[1]=c[2] ?'''
 
:''[I think the naming convention should be as consistent as possible with the names used in the MGED user interface. For example, when a sphere is edited in MGED, the parameters available are V (the center), and 3 radius vectors (A, B, and C). Similarly, an RCC or TRC has all the parameters of a TGC. Note also that all objects in a BRL-CAD database file are accessed by unique names. A convention for producing unique names for the constraint objects is needed. Depending on how these constraint objects are accessed by a user, the names of the constraint objects might not ever need to exposed to the user. Objects in the database can be "hidden" so that they do not normally appear in listings] - JRA''
 
  
 
The datastructures necessary for the exchange of information (pc_pc_set which itself is built using a constraint set structure and parameter set structure) are defined currently in raytrace.h (Shift to pc.h in future? )
 
The datastructures necessary for the exchange of information (pc_pc_set which itself is built using a constraint set structure and parameter set structure) are defined currently in raytrace.h (Shift to pc.h in future? )
Line 133: Line 116:
 
Initial draft/intent
 
Initial draft/intent
  
It would be ideal to provide both analytical and numeric evaluation methods the second one being of
+
It would be ideal to provide both analytical and numeric evaluation methods the second one being of primary importance in terms of constraint based calculations.
primary importance in terms of constraint based calculations. Considering the standard methods of
+
Considering the standard methods of parametrization ( see Enumeration below ) I think the implementation of an analytic solving system would be easier. Though for the solution of more complex equation as well as majority of constraints , libpg will have to provide support for numerical solutions.
parametrization ( see Enumeration below ) I think the implementation of an analytic solving system  
+
 
would be easier. Though for the solution of more complex equation as well as majority of constraints,
+
==Enumeration of Parameters and Constraints==
libpg will have to provide support for numerical solutions.
+
''Various standard methods of parametrics and constraints available in CAD Programs ( CATIA as a case study )''
 +
===Parametrics===
 +
#Point
 +
##Coordinates
 +
##On Curve
 +
##On Plane
 +
##On Surface
 +
##Circle/Sphere Centre
 +
##Tangent on Curve
 +
##Between (2 points)
 +
##Extremum
 +
##Extremum Polar
 +
#Line
 +
##Point-Point
 +
##Point-Direction
 +
##Angle/Normal to the curve
 +
##Tangent to the Curve
 +
##Normal to the surface
 +
##Bisecting
 +
#Plane
 +
##Offset from plane
 +
##Parallel through Point
 +
##Angle/Normal to Plane
 +
##Three points
 +
##Two Lines
 +
##Point and Line
 +
##Planar Curve
 +
##Normal to Curve
 +
##Tangent to Surface
 +
##Equation
 +
##Mean through points
 +
#Axis
 +
#Polyline
 +
#Circle
 +
#Corner
 +
#Connect Curve
 +
#Conic
 +
#Spline
 +
#Helix
 +
#Spiral
 +
 
 +
===Constraints===
 +
#Distance
 +
#Length
 +
#Angle
 +
#Radius/Diameter
 +
#Semimajor axis
 +
#Semiminor axis
 +
#Symmetry
 +
#Midpoint
 +
#Equidistant point
 +
#Fix
 +
#Coincidence
 +
#Cocentricity
 +
#Tangency
 +
#Parallelism
 +
#Perpendicular
 +
#Horizontal
 +
#Vertical
 +
#Angle with axis
 +
 
 +
==Notes==
 +
 
 +
===Object Overlay===
 +
===Extensibility===
 +
===Interoperability===

Please note that all contributions to BRL-CAD may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see BRL-CAD:Copyrights for details). Do not submit copyrighted work without permission!

To edit this page, please answer the question that appears below (more info):

Cancel Editing help (opens in new window)

Template used on this page: