The Experts below are selected from a list of 29190 Experts worldwide ranked by ideXlab platform

Xiao-shan Gao - One of the best experts on this subject based on the ideXlab platform.

  • well constrained completion and decomposition for under constrained Geometric Constraint problems
    International Journal of Computational Geometry and Applications, 2006
    Co-Authors: Guifang Zhang, Xiao-shan Gao
    Abstract:

    In this paper, we consider the optimal well-constrained completion problem, that is, for an under-constrained Geometric Constraint problem, add automatically new Constraints in such a way that the new Constraint problem G is well-constrained and the set of equations to be solved simultaneously in order to solve G has the smallest size. We propose a polynomial time algorithm which gives a partial solution to the above problem.

  • spatial Geometric Constraint solving based on k connected graph decomposition
    ACM Symposium on Applied Computing, 2006
    Co-Authors: Guifang Zhang, Xiao-shan Gao
    Abstract:

    We propose a Geometric Constraint solving method based on connectivity analysis in graph theory, which can be used to decompose a well-constrained problem into some smaller ones if possible. We also show how to merge two rigid bodies if they share two or three Geometric primitives in a bi-connected or tri-connected graph respectively. Based on this analysis, problems similar to the "double banana problem" could be easily detected.

  • solving spatial basic Geometric Constraint configurations with locus intersection
    Computer-aided Design, 2004
    Co-Authors: Xiao-shan Gao, Christoph M. Hoffmann, Weiqiang Yang
    Abstract:

    Abstract A basic idea of Geometric Constraint solving (GCS) is to decompose the Constraint problem into smaller ones according to some basic configurations. In this paper, we find all spatial basic configurations involving points, lines, and planes containing up to six Geometric primitives in an automated way. Many of these basic configurations still resist effective analytical solutions. We propose the locus intersection method (LIM) for GCS, a hybrid method based on Geometric computation and numerical search that can be used to find all the solutions for a Geometric Constraint problem. We show that the LIM can be used to solve all the above basic configurations.

  • Geometric Constraint solving based on connectivity of graph
    Computer-aided Design and Applications, 2004
    Co-Authors: Guifang Zhang, Xiao-shan Gao
    Abstract:

    AbstractWe propose a Geometric Constraint solving method based on connectivity analysis in graph theory, which can be used to decompose a structurally well-constrained problem in 2D into some smaller ones if possible. We also show how to merge two rigid bodies if they share two or three Geometric primitives in a bi-connected or tri-connected graph respectively.

  • Geometric Constraint solving via c tree decomposition
    ACM Symposium on Solid Modeling and Applications, 2003
    Co-Authors: Xiao-shan Gao, Guifang Zhang
    Abstract:

    This paper has two parts. First, we propose a method which can be used to decompose a Geometric Constraint graph into a c-tree. With this decomposition, solving for a well-constrained problem is reduced to the solving for smaller rigid bodies if possible. Second, we give the analytical solutions to one of the basic merge patterns used to solve a c-tree: the 3A3D general Stewart platform, which is to determine the position of a rigid body relative to another rigid body when we know three angular and three distance Constraints between the two rigid bodies.

Christoph M. Hoffmann - One of the best experts on this subject based on the ideXlab platform.

  • Geometric Constraint Solving in Parametric Computer-Aided Design
    Journal of Computing and Information Science in Engineering, 2011
    Co-Authors: Bernhard Bettig, Christoph M. Hoffmann
    Abstract:

    With parametric computer-aided design (CAD) software, designers can create Geometric models that are easily updated (within limits) by modifying the values of controlling parameters. These numeric and non-numeric parameters control the geometry in two ways: parametric operations and Geometric Constraint solving. This paper examines the advances over the last decade in the representation of parametric operations and of solving Geometric Constraint problems. An extensive literature has grown up surrounding Geometric Constraint solving and there has been substantial progress in the types of objects and Constraints that can be handled robustly. Yet parametric operations have remained largely within the same conceptualization and begin to limit the flexibility of CAD systems, since they still do not align well with a systematic design process.

  • solving spatial basic Geometric Constraint configurations with locus intersection
    Computer-aided Design, 2004
    Co-Authors: Xiao-shan Gao, Christoph M. Hoffmann, Weiqiang Yang
    Abstract:

    Abstract A basic idea of Geometric Constraint solving (GCS) is to decompose the Constraint problem into smaller ones according to some basic configurations. In this paper, we find all spatial basic configurations involving points, lines, and planes containing up to six Geometric primitives in an automated way. Many of these basic configurations still resist effective analytical solutions. We propose the locus intersection method (LIM) for GCS, a hybrid method based on Geometric computation and numerical search that can be used to find all the solutions for a Geometric Constraint problem. We show that the LIM can be used to solve all the above basic configurations.

  • solving spatial basic Geometric Constraint configurations with locus intersection
    ACM Symposium on Solid Modeling and Applications, 2002
    Co-Authors: Xiao-shan Gao, Christoph M. Hoffmann, Weiqiang Yang
    Abstract:

    A basic idea of Geometric Constraint solving is to decompose the Constraint problem into smaller ones according to some basic configurations. In this paper, we find all spatial basic configurations involving points, lines, and planes containing up to six Geometric primitives in an automated way. Many of these basic configurations still resist effective analytical solutions. We propose the locus intersection method for Geometric Constraint solving, which is used to solve all these basic configurations.

  • planning Geometric Constraint decomposition via optimal graph transformations
    Lecture Notes in Computer Science, 2000
    Co-Authors: Christoph M. Hoffmann, Andrew Lomonosov, Meera Sitharam
    Abstract:

    A central issue in dealing with Geometric Constraint systems that arise in Computer Aided Design and Assembly is the generation of an optimal decomposition recombination plan that is the foundation of an efficient solution of the Constraint system. For the first time, in this paper, we formalize, motivate and explain the optimal decompositionrecombination (DR) planning problem as a problem of finding a sequence of graph transformations T i that maximizes an objective function subject to a certain criteria. We also give several performance measures phrased as graph transformation properties by which DR-planning algorithms can be analyzed and compared. Using these perfomance measures and formulation of the problem we develop a new DR-planner which represents a significant improvement over existing algorithms.

  • Geometric Constraint decomposition
    1998
    Co-Authors: Christoph M. Hoffmann, Andrew Lomonosov, Meera Sitharam
    Abstract:

    We present a flow-based method for decomposing the graph of a Geometric Constraint problem. The method fully generalizes degree-of-freedom calculations, prior approaches based on matching specific subgraph patterns, as well as prior flow-based approaches. Moreover, the method generically iterates to obtain a decomposition of the underlying algebraic system into small subsystems.

Meera Sitharam - One of the best experts on this subject based on the ideXlab platform.

  • reconciling conflicting combinatorial preprocessors for Geometric Constraint systems
    International Journal of Computational Geometry and Applications, 2010
    Co-Authors: Meera Sitharam, Yong Zhou, Jörg Peters
    Abstract:

    Polynomial equation systems arising from real applications often have associated combinatorial information, expressible as graphs and underlying matroids. To simplify the system and improve its numerical robustness before attempting to solve it with numeric-algebraic techniques, solvers can employ graph algorithms to extract substructures satisfying or optimizing various combinatorial properties. When there are underlying matroids, these algorithms can be greedy and efficient. In practice, correct and effective merging of the outputs of different graph algorithms to simultaneously satisfy their goals is a key challenge. This paper merges and improves two highly effective but separate graph-based algorithms that preprocess systems for resolving the relative position and orientation of a collection of incident rigid bodies. Such collections naturally arise in many situations, for example in the recombination of decomposed large Geometric Constraint systems. Each algorithm selects a subset of incidences, one...

  • Solution space navigation for Geometric Constraint systems
    ACM Transactions on Graphics, 2006
    Co-Authors: Meera Sitharam, Adam Arbree, Yong Zhou, Naganandhini Kohareswaran
    Abstract:

    We study the well documented problem of systematically navigating the potentially exponentially many roots or realizations of well-constrained, variational Geometric Constraint systems. We give a scalable method called the Equation and Solution Manager (ESM) that can be used both for automatic searches and visual, user-driven searches for desired realizations. The method incrementally assembles the desired solution of the entire system and avoids combinatorial explosion by offering the user a visual walk-through of the solutions to recursively constructed subsystems and by permitting the user to make gradual, adaptive solution choices.We isolate requirements on companion methods that are essential and desirable for efficient, meaningful solution space navigation. Specifically, they permit (a) incorporation of many existing approaches to solution space steering or navigation into the ESM; and (b) integration of the ESM into a standard Geometric Constraint solver architecture. We address the latter challenge and explain how the integration is achieved. Additionally, we sketch the ESM implementation as part of an opensource, 2D and 3D Geometric Constraint solver, FRONTIER.

  • elimination in generically rigid 3d Geometric Constraint systems
    Algebraic Geometry and Geometric Modeling, 2006
    Co-Authors: Jörg Peters, Meera Sitharam, Yong Zhou, Jianhua Fan
    Abstract:

    Modern Geometric Constraint solvers use combinatorial graph algorithms to recursively decompose the system of polynomial Constraint equations into generically rigid subsystems and then solve the overall system by solving subsystems, from the leave nodes up, to be able to access any and all solutions. Since the overall algebraic complexity of the solution task is dominated by the size of the largest subsystem, such graph algorithms attempt to minimize the fan-in at each recombination stage. Recently, we found that, especially for 3D Geometric Constraint systems, a further graph-theoretic optimization of each rigid subsystem is both possible, and often necessary to solve wellconstrained systems: a minimum spanning tree characterizes what partial eliminations should be performed before a generic algebraic or numeric solver is called. The weights and therefore the elimination hierarchy defined by this minimum spanning tree computation depend crucially on the representation of the Constraints. This paper presents a simple representation that turns many previously untractable systems into easy exercises. We trace a solution family for varying Constraint data.

  • graph and combinatorial algorithms for Geometric Constraint solving
    2004
    Co-Authors: Andrew Lomonosov, Meera Sitharam
    Abstract:

    Geometric Constraints are at the heart of CAD/CAM applications and also arise in many Geometric modeling contexts such as virtual reality, robotics, molecular modeling, teaching geometry, etc. Informally, a Geometric Constraint problem consists of a finite set of Geometric objects and a finite set of Constraints between them. The Geometric objects are drawn from a fixed set of types such as points, lines, circles and conics in the plane, or points, lines, planes, cylinders and spheres in 3 dimensions. The Constraints are spatial and include logical Constraints such as incidence, tangency, perpendicularity and metric Constraints such as distance, angle, radius. The spatial Constraints can usually be written as algebraic equations whose variables are the coordinates of the participating Geometric objects. A solution of a Geometric Constraint problem is a real zero of the corresponding algebraic system. Currently there is a lack of effective spatial variational Constraint solvers and assembly Constraint solvers that scale to large problem sizes and can be used interactively by the designer as conceptual tools throughout the design process. The requirement is a Constraint solver that uses Geometric domain knowledge to develop a plan for decomposing the Constraint system into small subsystems, whose solutions can be recombined by solving other small subsystems. The primary aim of this decomposition plan is to restrict the use of direct algebraic/numeric solvers to subsystems that are as small as possible. Hence the optimal or most efficient decomposition plan would minimize the size of the largest such subsystem. Any Geometric Constraint solver should first solve the problem of efficiently finding a close-to-optimal decomposition-recombination (DR) plan, because that dictates the usability of the solver. In this thesis we state this problem of finding a close-to-optimal solution as a problem that deals with weighted graphs and also identify several important subproblems. One class of such subproblem involves finding dense subgraphs—graphs such that sum of weights of its edges is greater than sum of weights of its vertices. Dense graphs that present interest for finding a DR-plan are (a) minimum (smallest possible dense graphs), (b) minimal (not containing any other dense subgraphs), (c) maximum (largest dense ones), (d) maximal (not contained in any other dense subgraph). This thesis presents polynomial time algorithms for problems (b), (c) and (d). Problem (a) is shown to be NP-complete, and various approximation algorithms are suggested, as well as explicit solutions for special cases that arise from CAD/CAM applications.

  • planning Geometric Constraint decomposition via optimal graph transformations
    Lecture Notes in Computer Science, 2000
    Co-Authors: Christoph M. Hoffmann, Andrew Lomonosov, Meera Sitharam
    Abstract:

    A central issue in dealing with Geometric Constraint systems that arise in Computer Aided Design and Assembly is the generation of an optimal decomposition recombination plan that is the foundation of an efficient solution of the Constraint system. For the first time, in this paper, we formalize, motivate and explain the optimal decompositionrecombination (DR) planning problem as a problem of finding a sequence of graph transformations T i that maximizes an objective function subject to a certain criteria. We also give several performance measures phrased as graph transformation properties by which DR-planning algorithms can be analyzed and compared. Using these perfomance measures and formulation of the problem we develop a new DR-planner which represents a significant improvement over existing algorithms.

Cad Support - One of the best experts on this subject based on the ideXlab platform.

  • Constraint Transformation Method for Solving 3D Geometric Constraint System of Closed-loop Assemblies
    Mechanical Science and Technology, 2014
    Co-Authors: Cad Support
    Abstract:

    A Constraint transformation method is put forward to solve Geometric Constraint system with closed-loops for 3D assembly design. Firstly,the equivalence analysis method is employed to eliminate the pseudo closed-loops of 3D Geometric Constraint system,whose Geometric Constraint graph will be decomposed into independent-edge subgraph,independent-loop subgraph,and coupling-loop subgraph with the block-finding algorithm of undirected graph. Then,the screw theory is utilized to recognize the kinematic pair from the assembly Geometric Constraint combination,and map the Geometric Constraint graph with closed-loops to the kinematic pair graph. Based on the topological structure analysis of kinematic pair graph,some cut-Constraints are determined to transform the closedloop structure of Geometric Constraint graph into the open-loop structure,and the relative coordinate representation of Constraint system is also established,so as to convert the whole iteration solution of Geometric Constraint system to the partial iteration solution of some cut-Constraints and relative coordinates. The proposed method can reduced the size of Constraint equations and variables that have to be solved simultaneously so that its stability and efficiency can be improved dramatically. Meanwhile,the proposed method can ensure the correctness of solution result via introducing additional direction Constraint.

  • A Recursive Decomposition Algorithm for 3D Assembly Geometric Constraint System with Closed-loops
    Journal of Computer-aided Design & Computer Graphics, 2013
    Co-Authors: Cad Support
    Abstract:

    Numerical methods are always employed to solve 3Dassembly Geometric Constraint system with closed-loops which can not be decomposed by the existing decomposition methods,but their inherent inefficiency and instability can not be overcome.In this paper,with the analysis of the structural Constraint of serial kinematic chain and the topological structure of Geometric Constraint closed-loop graph,a recursive decomposition algorithm for 3DGeometric Constraint system with closedloops is proposed.The basic idea of the proposed algorithm is to introduce the equivalent Geometric Constraint combination to substitute the structural Constraint of serial kinematic chain,and separate the Geometric Constraint subsystems which can be solved independently from the Geometric Constraint system with closed-loops.The proposed method can decompose most 3DGeometric Constraint closedloop systems which are always solved by numerical method into a series of Geometric Constraint subsystems between two rigid bodies which can be solved by analytical or reasoning method,so that the computational efficiency and stability can be improved dramatically.Finally,a typical example has been given to validate the correctness and effectiveness of the proposed method.

  • Equivalence Analysis of 3D Geometric Constraint Systems
    Journal of Software, 2011
    Co-Authors: Huang Xue, Cad Support
    Abstract:

    This paper proposes a 3D Geometric Constraint solving method,based on equivalence analysis in graph theory,that can handle over-constrained,well-constrained,and under-constrained configurations naturally and efficiently.The basic idea is that there are equivalent Geometric Constraint systems with different Geometric Constraint graphs.If the Geometric domain knowledge is exploited to transform a Geometric Constraint system into an equivalent one that has a better Geometric Constraint graph structure using equivalent Constraint substitution,the decomposition of Geometric Constraint system can be optimized.Therefore,the proposed approach will not depend on the initial Geometric Constraint graph structure,but on the inherent characteristic of the Geometric Constraint system.This proposition can usually find the optimal decomposition of the Geometric Constraint system.Several typical examples have been given to illustrate the correctness and effectiveness of the proposed method.

  • A Projection Transformation Method for Solving 3D Assembly Geometric Constraint Closed-Loops
    Journal of Computer-aided Design & Computer Graphics, 2010
    Co-Authors: Cad Support
    Abstract:

    In order to avoid the iterative solution of complex nonlinear equations derived from 3D assembly Geometric Constraint closed-loops,a projection transformation approach is proposed to solve the planar Geometric Constraint closed-loop problem in 3D assembly design.Firstly,the equivalence analysis algorithm is adopted to eliminate pseudo Geometric Constraint closed-loops and the block finding algorithm of undirected graph is utilized to decompose Geometric Constraint graph.Then,the subgraphs of the Geometric Constraint closed-loops are converted to kinematic joint graphs using screw theory,and the characteristic parameters of the kinematic joints are analyzed to determine whether the Geometric Constraint closed-loops can be projected to the 2D plane.At last,the 3D Geometric Constraint closed-loops that can be projected to the 2D plane is transformed into 2D Geometric Constraint system,which will be solved to obtain the solution of the 3D Geometric Constraint closed-loops.The proposed method can downsize the Constraint equations and variables that have to be solved simultaneously and reduce the complexity of Constraint equations,so it can improve the efficiency and robustness of an assembly Constraint solver significantly.

  • 3D Geometric Constraint Solving for Integrated Variational Design
    Journal of Computer-aided Design & Computer Graphics, 2010
    Co-Authors: Cad Support
    Abstract:

    A modified directed graph method is proposed to solve hybrid Geometric Constraint systems including 3D Geometric Constraints and assembly Constraints derived from integrated variational design.Firstly,several basic Constraints are defined to describe diverse Geometric Constraints,and two abstract dual objects are used to encapsulate various Geometric entities.Then,the hybrid Geometric Constraint digraph model is established by introducing the irreversible directed arc to represent the intrinsic dependency between two interrelated objects.Subsequently,the optimal decomposition of Geometric Constraint system is achieved by optimal processing of the Constraint digraph,from which the efficient parallel solving sequence can be obtained.Finally,a series of examples are presented to demonstrate the correctness and effectiveness of the proposed approach.

Dominique Michelucci - One of the best experts on this subject based on the ideXlab platform.

  • Interrogating witnesses for Geometric Constraint solving
    Information and Computation, 2012
    Co-Authors: Sebti Foufou, Dominique Michelucci
    Abstract:

    Classically, Geometric Constraint solvers use graph-based methods to decompose systems of Geometric Constraints. These methods have intrinsic limitations, which the witness method overcomes; a witness is a solution of a variant of the system. This paper details the computation of a basis of the vector space of free infinitesimal motions of a typical witness, and explains how to use this basis to interrogate the witness for dependence detection. The paper shows that the witness method detects all kinds of dependences: structural dependences already detectable by graph-based methods, but also non-structural dependences, due to known or unknown Geometric theorems, which are undetectable by graph-based methods. It also discusses how to decide about the rigidity of a witness and how to decompose it.

  • Geometric Constraint solving: The witness configuration method
    Computer-Aided Design, 2006
    Co-Authors: Dominique Michelucci, Sebti Foufou
    Abstract:

    Geometric Constraint solving is a key issue in CAD, CAM and PLM. The systems of Geometric Constraints are today studied and decomposed with graph-based methods, before their numerical resolution. However, graph-based methods can detect only the simplest (called structural) dependences between Constraints; they cannot detect subtle dependences due to theorems. To overcome these limitations, this paper proposes a new method: the system is studied (with linear algebra tools) at a witness configuration, which is intuitively similar to the unknown one, and easy to compute.