text:
VARIATIONAL DIRECT MODELING FOR COMPUTER-AIDED DESIGNbyQiang ZouB.A.Sc., Yangzhou University, 2011M.A.Sc., University of Chinese Academy of Sciences, 2014A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Mechanical Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)June 2019c© Qiang Zou, 2019The following individuals certify that they have read, and recommend to the Faculty ofGraduate and Postdoctoral Studies for acceptance, the thesis entitled:Variational Direct Modeling for Computer-Aided Designsubmitted by Qiang Zou in partial fulfillment of the requirements forthe degree of Doctor of Philosophyin Mechanical EngineeringExamining Committee:Hsi-Yung (Steve) Feng, Mechanical EngineeringSupervisorRyozo Nagamune, Mechanical EngineeringSupervisory Committee MemberJose R. Marti, Electrical and Computer EngineeringUniversity ExaminerMachiel Van der Loos, Mechanical EngineeringUniversity ExaminerAdditional Supervisory Committee Members:Clarence de Silva, Mechanical EngineeringSupervisory Committee MemberGary Schajer, Mechanical EngineeringSupervisory Committee MemberiiAbstractThis thesis presents a new computer-aided design (CAD) modeling approach for three-dimensional objects. Improving CAD modeling efficiency has always been a central topicin the CAD domain, especially for model editing. Currently, two CAD modeling paradigms,each with its own capabilities and limitations, dominate this subject. The parametric mod-eling paradigm offers great flexibility for global model edits involving preplanned paramet-rics but becomes very rigid for unplanned model edits. The very recent direct modelingparadigm provides flexible local model edits but barely supports parametric (global) edits.In order to improve modeling efficiency, flexible local and global model editing need tocoexist. This work proposes a novel modeling approach for this purpose, which integratesvariational modeling with direct modeling. It is for this reason that this approach is namedvariational direct modeling.The underlying problem for variational direct modeling is information inconsistencyresolution. There are three layers of information in a model: geometry, topology, and con-straint. When an information layer is edited, the changes are not reflected in the othersautomatically. As a result, the consistency of the three information layers in the pre-editmodel is broken, and an invalid model is generated. There often exist many options forresolving such inconsistencies, and the fundamental challenge lies in ensuring the validityof resulting models, which requires systematic decision-making among the options. Unfor-tunately, there has not been much existing research work on such decision-making.The main contributions of this thesis include a thorough analysis of the information in-consistencies and novel, systematic decision-making methods to resolve them. The analysisiiiprimarily discusses what forms the inconsistencies take, based on which, effective methodsare proposed to take out these inconsistencies and to rethink the relevant information. Thepresented methods yield a modeling result that (1) is guaranteed to be valid (being solid andwell-constrained) and (2) attains a continuous model shape variation for direct edits and (3)exhibits a minimal model variation for parametric edits. These methods have been validatedthrough a series of case studies.ivLay SummaryComputer-aided design (CAD) is widely used in mechanical design practices, includingautomotive, shipbuilding, and aerospace industries. In order to support mechanical designprocesses effectively, CAD systems are often expected to provide flexibility for both globaland local model edits. These two requirements are currently implemented as two respectiveCAD modeling paradigms — parametric modeling and direct modeling, largely becausethey could cause information inconsistencies in a model. This thesis presents a new CADmodeling approach to meet both requirements. The fundamental challenge lies in dealingwith the many options in resolving the possible information inconsistencies in a model. Themain contributions of this work include a thorough analysis of these information inconsis-tencies and systematic decision-making methods for resolving them. In particular, thesemethods can guarantee the validity of models after inconsistency resolution.vPrefaceThis thesis documents the research work during my Ph.D. program. Much of the work hasbeen or will be published in peer-reviewed journals. The content as presented in the indi-vidual thesis chapters was all done by me under the supervision of Dr. Hsi-Yung (Steve)Feng. Dr. Feng recommended the overall research topic of computer-aided design; I wasresponsible for the specific problem defining, methodology development/implementation,case studies, and paper/thesis writing.List of publications:1. Q. Zou and H.-Y. Feng, "Push-Pull Direct Modeling of Solid CAD Models," Advancesin Engineering Software, vol. 127, pp. 59-69, 2019.2. Q. Zou and H.-Y. Feng, "Variational B-rep Model Analysis for Direct Modeling UsingGeometric Perturbation," Journal of Computational Design and Engineering, 2019.In press. DOI:10.1016/j.jcde.2019.03.0023. Q. Zou and H.-Y. Feng, "Push-Pull Direct CAD Modeling with Movable NeighboringFaces for Preserving G1 Connections," Submitted.4. Q. Zou and H.-Y. Feng, "A Decision Support Tool for Geometric Constraint SystemMaintenance in Direct Modeling of CAD Models," Submitted.5. Q. Zou and H.-Y. Feng, "Variational Direct Modeling: A New CAD Modeling Ap-proach Integrating Direct Modeling and Parametric Modeling," In Preparation.viChapter 3 is based on articles #1, #4, and #5, in which I carried out a thorough analysis ofthe information inconsistency problem. I formulated the problem, designed the illustrativeexamples, and wrote the content with input from my supervisor for article #1.Chapter 4 is based on articles #1 and #3, in which I proposed the geometry-topologyinconsistency detection methods, implemented the methods, and wrote the manuscripts withinput from my supervisor for article #1.Chapter 5 is based on article #1 for the geometry-topology inconsistency resolutionmethod and some of the case studies, and on article #3 for the other case studies. I proposedthe method, conducted the case studies, and wrote the manuscripts with input from mysupervisor for article #1.Chapter 6 is based on article #2, in which I proposed the shape-associativity inconsis-tency detection methods, conducted the verification case studies, and wrote the manuscript.Chapter 7 is based on article #4. I developed a constraint prioritization scheme to sup-port the decision-making in resolving shape-associativity inconsistencies, conducted thecase studies, and wrote the manuscript.Besides the above journal articles, I published the following technical report as part ofmy thesis: Q. Zou and H.-Y. Feng, "On Limitations of the Witness Configuration Methodfor Geometric Constraint Solving in CAD Modeling," 2019. arXiv:1904.00526viiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiList of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviiList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviiiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Computer-Aided Design . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Variational Direct Modeling: the Proposed Approach . . . . . . . . . . . . 51.3 Scope of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.4 Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.5 Contributions of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 122 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14viii2.1 CAD Modeling Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2 Geometry-Topology Inconsistencies . . . . . . . . . . . . . . . . . . . . . 192.3 Shape-Associativity Inconsistencies . . . . . . . . . . . . . . . . . . . . . 202.3.1 Inconsistency Detection . . . . . . . . . . . . . . . . . . . . . . . . 202.3.2 Inconsistency Resolution . . . . . . . . . . . . . . . . . . . . . . . 223 Issues of Variational Direct Modeling . . . . . . . . . . . . . . . . . . . . . . 243.1 Issues of Geometry-Topology Inconsistency Resolution . . . . . . . . . . . 243.1.1 Inconsistency Formation . . . . . . . . . . . . . . . . . . . . . . . 243.1.2 Inconsistency Checking Conditions . . . . . . . . . . . . . . . . . 253.1.3 Inconsistency Resolution Issues . . . . . . . . . . . . . . . . . . . 273.2 Issues of Shape-Associativity Inconsistency Resolution . . . . . . . . . . . 293.2.1 Inconsistency Formation . . . . . . . . . . . . . . . . . . . . . . . 293.2.2 Inconsistency Checking Conditions . . . . . . . . . . . . . . . . . 303.2.3 Inconsistency Resolution Issues . . . . . . . . . . . . . . . . . . . 313.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 Geometry-Topology Inconsistency Detection . . . . . . . . . . . . . . . . . . 354.1 The Principle of Continuity . . . . . . . . . . . . . . . . . . . . . . . . . . 354.2 Geometry-Topology Inconsistency Point . . . . . . . . . . . . . . . . . . . 374.3 Proposed Detection Methodology I . . . . . . . . . . . . . . . . . . . . . . 394.4 Proposed Detection Methodology II . . . . . . . . . . . . . . . . . . . . . 444.4.1 Overview of the Methodology . . . . . . . . . . . . . . . . . . . . 454.4.2 Reverse Inferring of Critical Events . . . . . . . . . . . . . . . . . 464.4.3 Mathematical Modeling of Critical Events . . . . . . . . . . . . . . 494.5 Overall Detection Methodology: A Hybrid . . . . . . . . . . . . . . . . . . 534.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54ix5 Geometry-Topology Inconsistency Resolution . . . . . . . . . . . . . . . . . . 555.1 Boolean Operation Based Decision-Making . . . . . . . . . . . . . . . . . 555.2 Auxiliary Model Construction Details . . . . . . . . . . . . . . . . . . . . 575.2.1 Construction for One Moved Face . . . . . . . . . . . . . . . . . . 585.2.2 Construction for Multiple Moved Faces . . . . . . . . . . . . . . . 595.3 Implementation and Case Studies . . . . . . . . . . . . . . . . . . . . . . . 615.3.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625.3.2 Comparative Case Studies . . . . . . . . . . . . . . . . . . . . . . 645.3.3 Comprehensive Case Studies . . . . . . . . . . . . . . . . . . . . . 705.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 726 Shape-Associativity Inconsistency Detection . . . . . . . . . . . . . . . . . . . 746.1 The Witness Configuration Method . . . . . . . . . . . . . . . . . . . . . . 746.2 Proposed Constraint State Characterization Method . . . . . . . . . . . . . 776.2.1 From Parametric Perturbation to Geometric Perturbation . . . . . . 776.2.2 From Rigid-Body Motions to Geometry-Invariant Motions . . . . . 796.2.3 Proposed Criteria to Characterize Constraint States . . . . . . . . . 826.3 Minimal Over-Constraint Detection . . . . . . . . . . . . . . . . . . . . . 836.4 Maximal Well-Constraint Detection . . . . . . . . . . . . . . . . . . . . . 866.5 Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 896.5.1 Comparison Examples . . . . . . . . . . . . . . . . . . . . . . . . 906.5.2 Validation Case Studies . . . . . . . . . . . . . . . . . . . . . . . . 926.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 987 Shape-Associativity Inconsistency Resolution . . . . . . . . . . . . . . . . . . 997.1 Resolution Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . 997.2 Constraint Prioritization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1027.3 Over-Constraint Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . 106x7.4 Under-Constraint Resolution . . . . . . . . . . . . . . . . . . . . . . . . . 1097.5 Implementation and Case Studies . . . . . . . . . . . . . . . . . . . . . . . 1137.5.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1137.5.2 Case Study I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1147.5.3 Case Study II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1177.5.4 Discussions and Limitations . . . . . . . . . . . . . . . . . . . . . 1207.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1218 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128Appendix A Examples of the Limitations in Section 6.1 . . . . . . . . . . . . . . 136Appendix B Proof of Proposition 6.1 . . . . . . . . . . . . . . . . . . . . . . . . 139xiList of TablesTable 1.1 Capabilities and limitations of CAD modeling paradigms. . . . . . . . . 5Table 3.1 Candidate resolution options for the bottom case in Fig. 3.5. . . . . . . . 32Table 4.1 Geometry-topology inconsistency types. . . . . . . . . . . . . . . . . . 40Table 4.2 Heuristics for geometry-topology inconsistency detection. . . . . . . . . 42Table 6.1 Comparison results for the plane and line examples. . . . . . . . . . . . 91Table 7.1 Rough prioritization based on constraint type. . . . . . . . . . . . . . . 103Table 7.2 Geometric constraint look-up table. . . . . . . . . . . . . . . . . . . . . 109xiiList of FiguresFigure 1.1 Structure of geometry, topology, and constraint information in a varia-tional model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7Figure 1.2 From planes to boundary faces to constraints defined over them. . . . . 8Figure 1.3 Push-pull direct modeling examples (blue faces: push-pulled faces; curvedarrows: rotational push-pull; straight arrows: translational push-pull). . 10Figure 2.1 Illustrations of the notions of closed (left), regular (middle), and mani-fold (right). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15Figure 2.2 Examples of B-rep (a) and CSG (b). . . . . . . . . . . . . . . . . . . . 16Figure 3.1 Examples of model boundary regeneration. . . . . . . . . . . . . . . . 25Figure 3.2 Geometry-topology inconsistency types. . . . . . . . . . . . . . . . . . 26Figure 3.3 An incorrectly selected resolution option leading to an invalid model. . 27Figure 3.4 Different applicable resolution options leading to varied model shapes. . 28Figure 3.5 Model constraint update and varying constraint state change results. . . 30Figure 4.1 A push-pull edit leading to a sudden deletion of face F1. . . . . . . . . 36Figure 4.2 A geometry-topology inconsistency point: (a) push-pull move; (b) re-generated model at t; (c) crossing a GTIP at τ; and (d) regeneratedmodel at τ + ε. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38Figure 4.3 Schematic diagram of the geometry-topology inconsistency resolutionframework (GTI: geometry-topology inconsistency). . . . . . . . . . . 39Figure 4.4 Illustrations of geometry-topology inconsistency types. . . . . . . . . . 41xiiiFigure 4.5 Illustrations of the heuristics for geometry-topology inconsistency de-tection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42Figure 4.6 An example of push-pull with smooth connections. . . . . . . . . . . . 44Figure 4.7 Workflow of geometry-topology inconsistency detection (GTI: geometry-topology inconsistency). . . . . . . . . . . . . . . . . . . . . . . . . . 46Figure 4.8 Graph representation of boundary faces. . . . . . . . . . . . . . . . . . 47Figure 4.9 Example configurations of edge-edge collision. . . . . . . . . . . . . . 49Figure 4.10 An illustration of edge-edge separation. . . . . . . . . . . . . . . . . . 49Figure 4.11 An illustration of edge-curve-surface relationship. . . . . . . . . . . . . 50Figure 5.1 Crossing a GTIP: (a) push-pull blue face to τ+ ε; and (b) invalid modelgenerated at τ + ε. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56Figure 5.2 Resolution options for crossing the GTIP in Fig. 5.1: (a) resolution op-tions; and (b) continuous model variation attained from the swept volume. 56Figure 5.3 Illustrations of auxiliary model construction for one moved face. . . . . 58Figure 5.4 Issue of missed volume produced in multiple moved adjacent faces bydirectly applying Algorithm 5.1. . . . . . . . . . . . . . . . . . . . . . 60Figure 5.5 Preventing missed volume between adjacent auxiliary models by merg-ing edge-adjacent faces. . . . . . . . . . . . . . . . . . . . . . . . . . . 60Figure 5.6 Order-dependency of Boolean operations for overlapped auxiliary models. 61Figure 5.7 Application of the three-part subdivision method to the case in Fig 5.6. . 61Figure 5.8 Graphical user interface of the geometry-topology inconsistency reso-lution system (a), and modeling result of translating blue faces (b). . . . 63Figure 5.9 Comparative case studies: (a) push-pulling a vice base model; (b) push-pulling a connecting node model; and (c) push-pulling a crank model. . 65Figure 5.10 Comparison of modeling results for push-pulling the vice base model. . 67Figure 5.11 Comparison of modeling results for push-pulling the connecting rodmodel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69xivFigure 5.12 Comparison of modeling results for push-pulling the crank model. . . . 69Figure 5.13 Push-pulling the axis support model and the modeling results: (a) anormal push-pull edit; and (b) an arbitrary push-pull edit. . . . . . . . . 71Figure 5.14 Push-pulling the hook model and the modeling results. . . . . . . . . . 71Figure 5.15 Push-pulling the motorcycle triple clamp model and the modeling results. 71Figure 5.16 Push-pulling the gearbox mount model and the modeling results. . . . . 72Figure 6.1 Examples of a well-constrained variational B-rep model (a), and a non-rigid-body free motion (b). . . . . . . . . . . . . . . . . . . . . . . . . 80Figure 6.2 Illustrations of geometry-invariant motions. . . . . . . . . . . . . . . . 81Figure 6.3 Example of minimal over-constrained parts. . . . . . . . . . . . . . . . 84Figure 6.4 Example of maximal well-constrained parts. . . . . . . . . . . . . . . . 87Figure 6.5 Comparison examples: (a) the plane example; and (b) the 3D line example. 90Figure 6.6 Direct modeling of a hexahedron model (a), and model constraint update(b). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93Figure 6.7 Dependency vector of the hexahedron case (white elements indicate thezeros and blue ones the non-zeros). . . . . . . . . . . . . . . . . . . . . 93Figure 6.8 Direct modeling of a slot model (a), and model constraint update (b). . . 94Figure 6.9 Results of maximal well-constraint detection for the slot case. . . . . . 94Figure 6.10 Direct modeling of an engine bracket model (a), and model constraintupdate (b) (Dis: Distance, Ang: Angle, Per: Perpendicular, Par: Paral-lel, Tan: Tangent). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96Figure 6.11 Truncated dependency vectors of the bracket case (truncated parts arezeros; white elements indicate the zeros and blue ones the non-zeros). . 96Figure 6.12 Results of maximal well-constraint detection for the bracket case. . . . 97Figure 6.13 Bridging constraints (in rectangles) of the bracket case. . . . . . . . . . 97Figure 7.1 Workflow of shape-associativity inconsistency resolution. . . . . . . . . 101xvFigure 7.2 Application example of Eq. 7.7. . . . . . . . . . . . . . . . . . . . . . 107Figure 7.3 Application example of Eq. 7.6. . . . . . . . . . . . . . . . . . . . . . 111Figure 7.4 Graphical user interface of the shape-associativity inconsistency resolu-tion system. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114Figure 7.5 A crank model and its face indexing. . . . . . . . . . . . . . . . . . . . 115Figure 7.6 Constraint update: (a) a direct edit applied to the crank model; and (b)constraint update for the edit. . . . . . . . . . . . . . . . . . . . . . . . 115Figure 7.7 Resolution flow, maximal well-constrained parts, and resolution sugges-tions generated for the crank model. . . . . . . . . . . . . . . . . . . . 116Figure 7.8 Increase the dimension leading to varying modeling behavior under dif-ferent resolution decisions for the crank model. . . . . . . . . . . . . . 117Figure 7.9 A bracket model and its face indexing. . . . . . . . . . . . . . . . . . . 118Figure 7.10 Constraint update: (a) a direct edit applied to the bracket model; and (b)constraint update for the edit (Dis: Distance, Ang: Angle, Per: Perpen-dicular, Par: Parallel, Tan: Tangent). . . . . . . . . . . . . . . . . . . . 119Figure 7.11 Minimal over-constrained parts in the bracket model and resolution sug-gestions generated. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119Figure 7.12 Increase the dimension leading to varying modeling behavior under dif-ferent resolution decisions for the bracket model. . . . . . . . . . . . . 120Figure A.1 An under-constrained model. . . . . . . . . . . . . . . . . . . . . . . . 138Figure A.2 Results of maximal well-constraint detection. . . . . . . . . . . . . . . 138xviList of SymbolsSymbol DefinitionF (X) Constraint equationsG Geometric perturbation matrixJ Jacobian matrixM(t) Time-dependent model variationN Nominal free motion spacen(t) Time-dependent orientation vectorp(t) Time-dependent position vectorR Relative model shape change matrixRn n-dimensional Euclidean spaceT (t) Time-dependent rigid transformationτ Geometry-topology inconsistency pointε Infinitesimal perturbation∆P Constraint parameter change∆X Constraint equation variable changexviiList of AbbreviationsAbbreviation DefinitionB-rep Boundary representationCAD Computer-aided designCSG Constructive solid geometryDOD Degree of displacementDOF Degree of freedomGCS Geometric constraint systemGTIP Geometry-topology inconsistency pointxviiiAcknowledgmentsThe opportunity to write a Ph.D. thesis is a great honor to me. This would not be madepossible without the people I met along the way. First and foremost: my supervisor Dr. Hsi-Yung (Steve) Feng who has been supportive over the years. Thanks for not being demandingand letting me explore. Thanks also go to my supervisory committee members Dr. Clarencede Silva, Dr. Ryozo Nagamune, and Dr. Gary Schajer for the valuable input, especiallyat the thesis proposal stage. Before UBC, there was another supervisor Dr. Jibin Zhaowho introduced me to and prepared me for the interesting research topic of computer-aideddesign and manufacturing.Then there were my cohorts at UBC. Thanks to the older ones Dr. Jack Szu-Shen Chenand Dr. Jimin Joy for being there when I landed; you are gentlemen, and I learned a lot.Thanks too to the younger ones: (will be) Dr. Zhengwen Nie, (will be) Dr. Cheng Su, Mr.Taylor Sweet, and Mr. Min-Si Sung. With you guys, being stuck in a basement room foryears was not as bad as it sounds.Sincere thanks are due to friends and family for giving me the things my work cannot.Thank you Keyi Tang, Ji Ji, and Minglei Ma for holiday parties, drinking parties, and manyfor-no-reason parties. Keyi, Ji: thanks for being considerate; Minglei: thanks for beingdifferent. My sincerest thanks go to my family: thank you my parents for supporting all mypursuits unconditionally and loving me as always.Additionally, thanks to the financial support of the Four-Year Doctoral Fellowship fromUBC Faculty of Graduate and Postdoctoral Studies, the Faculty of Applied Science Gradu-ate Award from UBC Faculty of Applied Science, the GSI Departmental Continuing MeritxixAward from UBC Department of Mechanical Engineering, and the Natural Sciences andEngineering Research Council of Canada (NSERC) under the Discovery Grants program.xxChapter 1: IntroductionThis chapter has two objectives: (1) to briefly introduce the historical development ofcomputer-aided design (CAD); and (2) to outline the motivation and content of this the-sis. They are intended to show this work's context, to describe its scope, and to explain thebasic terminologies to be used in the following chapters.1.1 Computer-Aided DesignA product is a physical artifact; a product model is a computerized representation of a prod-uct. CAD is the use of computers to construct and edit product models. It arose in the 1960sout of: (1) a need to digitally describe products for downstream applications, e.g., numericcontrol machine tools [1], which may be summarized as machine-machine communication;and (2) a goal to develop a human-computer cooperation system for solving engineeringdesign problems [2], which may be summarized as human-machine communication. TheCAD notion was coined in a series of reports at MIT [3, 4], featuring the idea of using com-puters to assist (not automate) engineering design processes. In the beginning, the objectiveof CAD spanned the whole spectrum of engineering design, from the representation of de-signs to their physical realization into manufactured parts, components, or systems. Soon,three main streams emerged: product modeling, product analysis, and product realization.As there were parallel developments of product analysis and product realization in otherareas, the three streams evolved respectively to be three different yet associated researchfields: CAD, computer-aided engineering, and computer-aided manufacturing.1CAD modeling, in its broadest sense, is concerned with modeling all aspects of a prod-uct's information needed to support processes throughout the product's life cycle. Theseaspects consist primarily of the product's spatial information, augmented with secondary,non-spatial information such as material, hardness, and so forth [5]. In a narrow sense,CAD modeling focuses merely on modeling spatial information, which is sometimes calledgeometric modeling [6]. This definition of CAD modeling also applies to this work. To date,major CAD modeling schemes may be classified into five categories: wireframe modeling,surface modeling, solid modeling, parametric modeling, and direct modeling.Wireframe modeling, surface modeling, and solid modeling may be seen as the pre-liminary stage in CAD development. They focus on the mathematical representation ofa product's spatial information. The (2D and 3D) wireframe modeling scheme specifiesan object's spatial information using the object's edges [7]. This scheme, however, has thelimitation of representational ambiguity: a wireframe model could correspond to several dif-ferent objects [8]. The surface modeling scheme addresses this issue by allowing wireframemodels to be "surfaced" [9]. This scheme also arose out of the industry need to describe 3Dcomplex surfaces such as car bodies and aircraft fuselages [8]. Nevertheless, this schemeonly captures partial spatial attributes of an object (e.g., no volumetric information). In realapplications, a complete description of the object's spatial information is often required toanswer any possible geometric queries automatically. As a response to this need, the solidmodeling scheme emerged, which encompasses a complete collection of an object's spatialinformation from vertex to edge to face to volume [10].Solid modeling has the property of representational completeness, which makes it verysuitable for documenting designs. On the other hand, it lacks flexibility1 in model editingand is difficult to use in practice [11]. This makes solid modeling insufficient in the reuseof existing designs. Many authors have identified the ability to take existing designs asbase designs and to repurpose them for new situations as an essential factor in improving1In this work, flexibility refers to the ease with which a CAD modeling scheme can respond to the user'smodifications.2product development efficiency [12–17]. It has been reported that almost all engineeringorganizations are currently reusing existing designs, and a significant improvement in prod-uct development efficiency has been seen (a 30% reduction in design time for new productsthat are closely associated with pre-existing designs, and an 80% reduction in design timefor new products that heavily rely on design reuse at a sample company) [13, 14]. As aresponse to this need, two major improvements to solid modeling were proposed in the lastthree decades. In order to address solid modeling's deficiency for global model edits, theparametric modeling paradigm was proposed; the lack of flexibility for local model edits insolid modeling motivated the direct modeling paradigm.Parametric modeling attains flexibility for global model edits through constructing asso-ciativity between geometric entities in a solid model. The constructed associativity networkallows a locally made change (taking the form of parameter changes) to propagate auto-matically. Global model edits can thus be made to solid models easily. The associativitynetwork is often implemented as a system of geometric constraints between geometric en-tities such as distance and angle. Geometric constraints may be unidirectional [11, 18] orbi-directional [19, 20]. Unidirectional constraints have a reference-to-target entity depen-dency: if the reference is moved, the target moves to maintain the associativity, but not theother way around. Due to this precedence, the modeling scheme involving unidirectionalconstraints is often called procedural or history-based modeling [21]. Bi-directional con-straints work in both directions to maintain the associativity. The modeling scheme usingbi-directional constraints is conventionally called variational modeling, where "variational"means a collection of several different instances from the same base and comes from theterm "variation" in the area of geometric dimensioning and tolerancing [19, 22]. If wewrap an additional feature information layer around the associativity layer, a special kindof parametric modeling called feature modeling is attained [1, 23]. Features are essentiallygroupings of geometric entities in a solid model that need to be referenced together [24];they are containers for storing any useful information for downstream applications.3Despite the benefit, parametric modeling has some important limitations. The associa-tivity network must be carefully thought out before modeling because this will restrict theuser to what can be edited after the model is built [11]. In other words, parametric modelingattains flexibility at a price: flexibility is restricted to model edits preplanned by the userand embedded in the associativity network, and rigidity can be said to unplanned modeledits. Quite often, unplanned model edits take the form of local model edits as these ed-its are closely related to fine model tuning, which is hard to plan in advance. Unplannedmodel edits could lead to structural alterations made to the originally built associativity net-work. Making alterations of this kind requires the user to have a very good knowledge ofthe network's construction history and mathematical nature [17]. However, in the context ofdesign reuse, a general user is most likely unfamiliar with designs done by others, and thenthe required interaction with the parametric modeler could be very time-consuming. Thestatements above only discuss part of parametric modeling's limitations that are related tothis thesis' interest. Other limitations can be found in [17, 25–27].Direct modeling, a very recent CAD modeling paradigm, is often presented as the op-posite of parametric modeling. All direct modeling focuses on is to provide flexibility forlocal model edits. This is essentially achieved by discarding the use of associativity andmaking all geometric entities in a solid model free to change. Typically, users just need tograb, push, and pull the geometric entities of interest so as to make desired changes [28, 29].With this geometry-oriented strategy, users can directly edit the model as they see fit withoutconsidering how the model was constructed. This unprecedented model editing flexibilityis, however, gained at a high price: without associativity, direct modeling barely supportsparametric (global) model edits.The major capabilities and limitations of the CAD modeling paradigms mentioned aboveare summarized in Table 1.1. It can be concluded that the original solid modeling schemewould only be useful in design documentation scenarios where one has already completedthe design on paper. Even in such cases, one cannot afford to make mistakes because making4changes requires almost as much work as the initial design itself. The parametric modelingscheme would be useful for designing parametric part families, where one must carefullyplan the part variant space before modeling. Once the model is built, model edits fallingin the part variant space can be made easily. However, for those outside the space, the costwould be high. The direct modeling scheme would only be useful for performing localmodel edits on existing models. None of these paradigms meets the need of flexibility forboth global and local model edits in design reuse scenarios perfectly. Further research workis thus necessary to get the best of both parametric modeling and direct modeling paradigms,which states the objective of this work.Modeling Paradigms Capabilities (Major) Limitations (Major) Solid modeling Representational completeness Lack of flexibility for model edits Parametric modeling Flexibility for preplanned global model edits Lack of flexibility for unplanned local model edits Direct modeling Flexibility for local model edits Lack of parametric model edits Table 1.1: Capabilities and limitations of CAD modeling paradigms.1.2 Variational Direct Modeling: the Proposed ApproachTwo directions may be taken to attain the best of both parametric modeling and direct mod-eling paradigms: integrating direct modeling into parametric modeling, and alternativelyintegrating parametrics into direct modeling. The former direction is easy to implement us-ing existing CAD research and engineering results but has inherent limitations. Currently,the mainstream parametric CAD systems are history-based, and there are two implementa-tion versions for integrating direct modeling into such systems. The more common imple-mentation version simply adds direct edits to the end of the model construction history asadditional operations, and the original construction history remains exactly as before [29].This kind of integration could disorganize the parametric information in a model and leadto the loss of meaningful parametric controls, as also pointed out in [30]. The other imple-5mentation version is to translate direct edits into operations of tuning the model's existingparameters [31]. This approach is also limited because not all direct edits are achievablethrough parameter tuning. In these regards, this work opts for the latter integration direc-tion. This direction does not have the limitations above but introduces more challengingresearch issues.It is conceptually simple to integrate parametrics into direct modeling. The reason fordirect modeling lacking parametric model edits is that direct modeling ignores associativityinformation and only focuses on the solid model. Enabling parametrics for direct modelingcan thus be done by shifting from solid models to variational models. A variational modelconsists of a solid model and a (bi-directional) geometric constraint system (GCS) thatrelates geometric entities in the solid model [32]. With such models, parametric edits canbe made through the constraint layer (i.e., the associativity layer) in the model, and directedits can be carried out through the solid model layer in the model. For this reason, this newmodeling scheme is named variational direct modeling.The above integration idea is easy to state but difficult to realize due to the possible in-formation inconsistencies in a variational model after parametric/direct edits. A variationalmodel consists of information on both associativity and shape, which in turn includes in-formation on geometry and topology (Fig. 1.1). In other words, there are three informationlayers in a variational model: geometry, topology, and associativity. Informally, geometry,which is the first information layer, refers to a finite set of surface elements. Topology,which is the second information layer, describes connections between the surface elements;these connections basically define how the surface elements are intersected with each otherand trimmed to boundary faces [9], as shown in Fig. 1.2. The resulting boundary faces givea representation of the boundary between the 3D space occupied by the solid model andthe space outside it. Associativity, which is the third information layer, describes relationsbetween the geometric entities in the solid model, as shown in Fig. 1.2.6 Variational Model Shape: Solid Model Associativity: Geometric Constraints Topology Geometry Figure 1.1: Structure of geometry, topology, and constraint information in a variationalmodel.When an information layer is edited, the changes are not reflected in the other two layersautomatically. As a result, the consistency of the three information layers in the pre-editmodel is broken, and an invalid model is generated. Specifically, a direct edit only changesthe geometry layer, and a parametric edit merely modifies the constraint layer. In variationaldirect modeling, possible information inconsistency types are:1. Geometry-topology inconsistency means that the pre-edit topology and new geometryafter a direct edit yield a non-solid model (e.g., a self-intersecting model), which isconsidered to be nonsense/impossible in mechanical design.2. Shape-associativity inconsistency refers to situation I: the pre-edit solid model doesnot satisfy the new GCS after a parametric edit; or situation II: the new solid modelafter a direct edit makes some constraints in the GCS inapplicable, and consequentlythe well-constraint state of the model is broken. (The above concepts of informationinconsistency will be made formal in Chapter 3.)Some of the three information inconsistency types can be handled using existing re-search work, whereas others require new input. For the shape-associativity inconsistency Itype, the main task involved in resolving such inconsistencies is the re-evaluation of the newGCS resulting from a parametric edit. GCS evaluation is essentially to solve a system ofalgebraic equations representing the GCS, which is called geometric constraint solving inthe literature. Geometric constraint solving is a well established domain, and many effectivealgorithms have been made available [30].7 Geometry: Planes Geometry + Topology: Boundary Faces Shape + Associativity Plane to Boundary Face: Plane-Plane Intersection 1. Front Face, Back Face, ∥1 2. Right Face, Left Face, ∥2 3. Top Face, Bottom Face, ∥3 4. Front Face, Right Face, ∡90° 5. Front Face, Top Face, ∡90° 6. Top Face, Right Face, ∡90° Front View ∥: Distance; ∡: Angle Figure 1.2: From planes to boundary faces to constraints defined over them.For the geometry-topology inconsistency type, the main task in resolving such inconsis-tencies is to modify the model's topology so that the modified topology and new geometryafter a direct edit will generate a valid solid model. The resolution of geometry-topologyinconsistencies is an issue shared with traditional direct modeling as no constraint informa-tion is involved. Nevertheless, the underlying robustness2 issue has rarely been noted andstudied by the academic community (partly because direct modeling is relatively new) andonly partially solved by industry [33]. Varying modeling results have been observed in com-mercial CAD systems: some modeling results are good, but others are not. In other words,robustness towards generating valid modeling results in resolving geometry-topology in-consistencies still remains an open issue.For the shape-associativity inconsistency II type, the main tasks in resolving such in-consistencies are to detect and resolve the under-constrained and over-constrained parts inthe model. However, there has not been much relevant progress for these tasks [34]. Forexample, an essential part of the detection task is to extract the minimal over-constrainedparts in the model, but existing work [35–38] cannot do so effectively. This statementalso applies to the detection of under-constrained parts. The resolution task faces a worsesituation in lacking effective methods. New research is thus necessary to effectively han-2In this work, robustness refers to the ability to generate modeling results of a certain property (e.g., modelvalidity) under different model edits.8dle such inconsistencies. Hereafter, shape-associativity inconsistency refers exclusively toshape-associativity inconsistency II, unless otherwise stated.The resolution of geometry-topology inconsistencies and shape-associativity inconsis-tencies comprises the main body of this thesis. The basic technical problem here is thatthere often exist many options in resolving the inconsistencies. The fundamental challengelies in decision-making among the resolution options and ensuring that modeling results arevalid. Without systematic decision-making methods, unexpected modeling behavior willbe produced, e.g., the robustness issue observed in current commercial CAD systems forresolving geometry-topology inconsistencies. In the following chapters, effective decision-making methods are presented to solve the challenges.1.3 Scope of the ThesisIn the general form described, the problem of resolving geometry-topology inconsisten-cies and shape-associativity inconsistencies is too large to address satisfactorily in a thesisof reasonable size, a consequence of the many direct modeling operations made availablein commercial CAD systems. Implementing all these direct modeling operations does notalign with the purpose of a research project since we are not developing commercial soft-ware packages. The scope of this thesis is, therefore, narrowed to the primary direct model-ing operation: push-pull. Push-pull operations allow the user to effectively reshape a solidmodel through pushing or pulling its boundary faces, see Fig. 1.3 for examples.The above setting is not as restrictive as it sounds. Direct modeling operations may beclassified into three levels. The primary level consists merely of push-pull operations. Thesecondary level includes specializations of push-pull operations, e.g., make-parallel (whichpush-pulls one boundary face to make it parallel with the other boundary face). The tertiarylevel contains operations borrowed from previous CAD research; these operations are notexclusive to direct modeling, and they have been in existence for a while, e.g., delete face[39]. Direct modeling consists almost entirely of operations at the primary and secondary9 Figure 1.3: Push-pull direct modeling examples (blue faces: push-pulled faces; curvedarrows: rotational push-pull; straight arrows: translational push-pull).levels. For this reason, direct modelers are sometimes called push-pull systems [28, 29]. Theideas and methods to be developed in this thesis thus apply to almost all direct modelingoperations (with minor and obvious adaptations), although this thesis focuses on push-pulloperations. The only exception, for the time being, is the delete face operation.For this thesis to have good coherence, a further restriction is made to the scope: push-pull edits are not to be applied to boundary faces made of freeform surfaces. Push-pullingfreeform faces belongs to another research topic called freeform surface deformation. Thisarea focuses on attaining desired shape through tuning surface parameterization or its con-trol points [40]. Apparently, this is off the main topic — information inconsistency resolu-tion — of this thesis. This restriction will slightly affect the applicability of the proposedmodeling scheme. Fortunately, most mechanical part models are composed of linear andquadratic surfaces, and only around 5% of models in mechanical design have freeform sur-faces [41, 42].1.4 Outline of the ThesisTo understand variational direct modeling, one must understand CAD modeling. For thisreason, Chapter 2 reviews the existing CAD modeling techniques related to this work, as10well as establishes the concepts mentioned above like topology in more formal terms thanwhat was presented here.In Chapter 3, issues and challenges of the problem of resolving geometry-topology in-consistencies and shape-associativity inconsistencies will be discussed. This chapter basi-cally answers the following questions: how are the inconsistencies formed; what are thechecking conditions for them; and why is resolving them challenging?Based on the problem analysis presented in Chapter 3, effective methods that solve thechallenges to the point are to be presented in the following chapters. Effective resolutionof geometry-topology inconsistencies requires a systematic method for making decisionsamong the many resolution options. This work proposes to use the principle of continuity asthe decision-making criterion. The implementation of this principle lies in detecting criticalpoints where geometry-topology inconsistencies occur. The introduction of the continuityprinciple and the method of detecting the critical points are given in Chapter 4.Chapter 5 is a continuation of the work presented in Chapter 4 and focuses on the specificdecision-making at a detected critical point. A novel Boolean operation based decision-making method will be given in this chapter. This method, when combined with the de-tection method presented in Chapter 4, yields a robust resolution of geometry-topologyinconsistencies: the resolution is finally formulated as successive Boolean operations on themodel volume, which guarantees model validity (being solid models). A series of case stud-ies and comparisons with the state-of-the-art will also be presented to validate the proposedmethods.For resolving shape-associativity inconsistencies, the first task is to list all valid res-olution options. The essential tasks for successfully doing so are to analyze the model'sconstraint state and to decompose the model into under-, well-, and over-constrained parts.Particularly, two tasks are of critical importance: the detection of minimal over-constrainedparts in the model and detection of maximal well-constrained parts in the model. Chapter 6presents methods to deal with these tasks.11Chapter 7 focuses on the decision-making among the valid resolution options given bythe methods presented in Chapter 6. A novel decision-making criterion called the minimalshape change rate is proposed for this purpose. By combining the methods in Chapters 6and 7, effective resolution of shape-associativity inconsistencies is attained, which againensures model validity (being well-constrained). Case studies are presented to show theeffectiveness of the proposed methods.The last chapter provides a summary of this work and discusses several improvementsthat are of interest for future research studies, e.g., combining this work with virtual/aug-ment reality techniques.1.5 Contributions of the ThesisThe main contributions of this thesis are summarized as follows:1. Overall, a new CAD modeling scheme is proposed to attain full modeling flexibilityfor both local and global model edits.2. A detailed analysis of the issues and challenges in resolving geometry-topology in-consistencies and shape-associativity inconsistencies is provided (Chapter3), whichhas rarely been studied in the literature.3. A novel, systematic method of geometry-topology inconsistency resolution is pro-posed (Chapters 4 and 5). The main feature is that modeling results have guaranteedmodel validity and continuous model variations. In other words, the method is free ofthe robustness issues as observed in commercial CAD systems.4. An improved method, generalizing the existing witness configuration method, is pro-posed to analyze a model's constraint state (Chapter 6). With the generalization, themethod can correctly characterize the constraint state of 3D variational models.5. Two novel methods are proposed to detect minimal over-constrained parts and maxi-mal well-constrained parts in a model (Chapter 6). Different from the existing meth-ods, which use greedy methods to carry out the detection, the proposed methods for-12mulate the detection as sparse recovery (a.k.a. compressive sensing) problems thatcan be effectively solved with existing optimization techniques. Greedy methods can-not always give correct results, while the proposed methods can do so.6. A novel criterion to prioritize resolution options and an inconsistency resolution frame-work are proposed for shape-associativity inconsistencies (Chapter 7). With the reso-lution framework, modeling results are guaranteed to be valid (i.e., well-constrained).With the criterion, models after resolution will exhibit the minimal model shape vari-ation for parametric edits. If the user chooses to dictate the resolution process, thecriterion is able to guide the choice among all valid resolution options. This canempower the user to deal effectively with shape-associativity inconsistencies whilenot requiring him/her to have good mathematical proficiency for reasoning constraintsystems.In a word, this work proposes a new CAD modeling concept, named variational directmodeling, to attain full modeling flexibility and provides viable methods to implement thisconcept. Most notably, effective methods are presented to resolve any possible geometry-topology inconsistencies and shape-associativity inconsistencies in variational direct mod-eling.13Chapter 2: Related WorkThis chapter first introduces relevant CAD modeling techniques and then discusses existingtechnical methods related to the problem of resolving geometry-topology inconsistenciesand shape-associativity inconsistencies.2.1 CAD Modeling TechniquesAs already noted in Chapter 1, spatial information has always played a fundamental rolein mechanical design; but what exactly does spatial information mean in the domain ofmechanical design? It is impossible to have effective CAD modelers unless the answer tothis question is made precise. For this reason, researchers established the concept of solidmodels.A solid is a physical object occupying certain volume in 3D Euclidean space R3. Avolume is a subset of R3, but not all subsets of R3 are volumes. A subset has to satisfy cer-tain conditions that encapsulate the characteristics of "solidity" to be deemed a volume. Awidely accepted set of conditions are given in [8]: a solid is a subset of R3 that is bounded,closed, regular, and semi-analytic, often referred to as a r-set. Let the subset be representedby s ⊂ R3. The "bounded" condition means that s must occupy a finite portion of space;the other three conditions require that the boundary between s and R3 − s is well-behaved,where the operator − is set difference. To be more precise, the "closed" condition meansthat s contains its boundary, see Fig 2.1 for a non-closed example. The "regular" con-dition means that the boundary of s does not contain any dangling portions as shown inFig 2.1; mathematically, "regular" means that s equals to the closure of its interior. The14 Non-Closed Dangling Portion Non-Manifold Figure 2.1: Illustrations of the notions of closed (left), regular (middle), and manifold(right)."semi-analytic" condition means that the boundary of s is composed of piecewise analyticsurfaces (which are surfaces that can be described by analytic functions). These conditionsencompass the common attributes of most objects in mechanical design [6]. However, theyallow non-manifold models, which are not manufacturable [43]. For this reason, many pre-fer a solid to be a r-set with a manifold boundary. A boundary is deemed manifold if, foreach point on the boundary, there is an open neighborhood that can be continuously de-formed to a 2D disk (mathematically, homogeneous to an open disk in R2). Fig 2.1 shows acounterexample to manifold boundary.A solid model is a computerized representation of a solid. To date, several represen-tation schemes for solids have been made available, as reviewed in [8]. Among them, themainstream schemes are boundary representation (B-rep) and constructive solid geometry(CSG). B-rep, as the name indicates, describes a solid using the boundary between thesolid and non-solid. A B-rep solid model is essentially a collection of interconnected facescomprising the solid's boundary (Fig 2.2a). There exist various schemes for representingboundary faces. The basic scheme stores the boundary faces' carrying surfaces and con-nections between them [9]. Connections define how a carrying surface is intersected withother surfaces and trimmed to a bounded surface (as already shown in Fig. 1.2). Usually,we refer to the carrying surfaces as geometry and the connections as topology. Hereafter,surfaces default to carrying surfaces such as infinite planes; faces default to bounded sur-faces. Alternative schemes have also been proposed for the purpose of speeding up specific15 Union (a) (b) Union Difference Figure 2.2: Examples of B-rep (a) and CSG (b).algorithms [8]. They differ from the basic scheme in the redundant information stored. Typ-ical redundant information takes the form of faces' bounding edges and vertices, as well asconnections between them. Such information is often stored to avoid expensive searchesrequired by certain algorithms.CSG represents a solid as successive combinations of solid components via (regularized)Boolean operations [44], as shown in Fig 2.2b. CSG is often implemented as binary treeswhere leaves represent solid components, and nodes Boolean operations. Different fromB-rep that stores the solid's boundary explicitly, CSG is an implicit representation scheme:it does not store the solid's final spatial information but the construction history. Due to theuse of Boolean operations, CSG guarantees model validity [44]; by contrast, B-rep does nothave guaranteed validity. This property of Boolean operations is to be exploited in Chapter 5to attain a robust resolution of geometry-topology inconsistencies.When solid modeling based CAD systems were introduced, it met with resistance fromusers due to the difficulty of use. It was not until the introduction of parametric modelingbased CAD systems that this resistance began to melt away [11]. The primary benefit of16parametric modeling is to allow users to attain solid model variants through editing param-eters embedded in the model [17]. The embedding is done by constructing associativitybetween geometric entities in the model; the associativity often takes the form of unidi-rectional and/or bi-directional geometric constraints. With the associativity, a parameterchange will propagate automatically, and the user can design the global modeling behaviorof solid models under parametric edits. Parametric modeling also allows certain local edits,but this is not the main feature of parametric modeling.The mainstream implementation approach of parametric modeling involves three majorprocedures [11, 17]: (1) 2D sketching, (2) 3D sweeping, and (3) feature combining. Theuser defines a planar topology and specifies 2D bi-directional geometric constraints relatinggeometric entities on the 2D sketch. The 2D sketches are then used as sections for sweep-ing to be 3D solids, which are called features in most modelers. These features are similarto solid components in CSG. A new 2D sketch plane will be positioned relatively to fea-tures already specified by the user via 3D unidirectional geometric constraints. A newlygenerated feature is combined with preceding features through Boolean operations, whichis again similar to CSG. The sequence of performing the above three steps by the user isconventionally referred to as model construction history. When a change is made, the 2Dsketches are re-evaluated, then the construction history is replayed, and finally a new solidmodel is generated.The construction history will restrict the user to what can be edited and will determinehow changes are propagated, thereby defining a model variation space [11]. Flexibility canbe said to model edits falling in the space as a simple parameter change can do the job,but cannot be said to those outside the space. Thus, parametric modeling requires carefulpreplanning about the space. However, many local model edits are likely hard to plan inadvance since they correspond to fine model tuning. Making such unplanned model editswould require structural alterations to the construction history, which is very difficult andtime-consuming without a good knowledge of the modeling principles parametric model-17ing follows and the model's construction history [17]. This situation could lead to seriousproductivity issues in scenarios like collaborative design and editing others' designs. Para-metric modeling is thus often blamed for being insufficient in terms of modeling flexibility[17, 25–27].The very recent direct modeling paradigm was proposed to meet the need of flexibilityfor local model edits. "Direct" comes from this modeling scheme's main feature: interact-ing directly with the geometry of the model to make edits. Although initially introducedby industry, the direct modeling notion may be traced back to the local operations devel-oped by the academic community in the 1980s [45–47]. Some widely used local operationexamples in today's CAD systems are filleting and chamfering. The very local operationthat direct modeling stemmed from is the tweaking operation, which is the predecessor ofpush-pull operations. The essential advance made is: tweaking does not allow any viola-tions to the pre-edit model topology, while push-pulling allows such violations. With thisrelaxation, direct modeling achieves much improved modeling flexibility. The early ver-sions of direct modeling consisted primarily of push-pull operations. The recent versionsinclude more operations, most of which are just specialized push-pull operations such as themake-face-parallel operation. Despite its powerfulness, direct modeling lacks the capabilityof parametric (global) edits.The above review suggests that neither of the two major CAD modeling paradigms canprovide sufficient modeling flexibility. Some CAD vendors are integrating them to achievefull modeling flexibility, but the adopted approaches are far from being effective. A commonapproach found in commercial CAD systems is to add direct edits to the end of the modelconstruction history, and the original history remains exactly as before. This approach,however, could disorganize the parametric information in a model and lead to the loss ofmeaningful parametric controls, as pointed out in [30]. Another way is to translate directedits into operations of tuning the model's existing parameters [31], which is rather limitedbecause not all direct edits are achievable through parameter tuning.18This work presents a new CAD modeling approach to avoid the limitations as statedabove. As already discussed in Section 1.2, implementation of this new CAD modelingapproach boils down to handling two challenging problems: resolving geometry-topologyinconsistencies and resolving shape-associativity inconsistencies. The following two sec-tions will review existing methods related to these two problems in order to show the tech-nical starting point of this work. The review presented in this section can be viewed as theCAD-modeling-level starting point of this work.2.2 Geometry-Topology InconsistenciesGeometry-topology inconsistencies refer to situations where the geometry and topology inthe model after direct edits are inconsistent with each other in ways that lead to a non-solidmodel. There has not been much research work on resolving such inconsistencies, partlybecause direct modeling is a relatively new CAD modeling technique. A few commercialCAD systems are being marketed with push-pull direct modeling. Without access to howthey implement the push-pull direct modeling, an in-depth review and evaluation cannot beperformed. Nevertheless, it appears that non-systematic approaches have been employeddue to the varying modeling results observed: some results are good, but others are not.In the literature, Rossignac [46] briefly discussed the idea of converting translationalpush-pull operations to face extrusion operations, but no systematic methodology was ex-plained. Woo and Lee [48], Kim and Mun [49], and Fu et al. [31] proposed to interpretpush-pulling a face as push-pulling the volumetric feature containing the face. This lineof methods can ensure model validity, but they are used to change the volume of a fea-ture rather than individual faces. Hence, their applicability in model modification is quiterestricted. Lipp et al. [50] developed a bunch of heuristics to handle geometry-topology in-consistencies resulting from push-pulling polygonal mesh models. However, the heuristicswere developed specifically for models composed only of planar and non-holed boundaryfaces, which merely make up a very small portion of solid models.19To date, documented research work on the problem of geometry-topology inconsistencyis far from being sufficient. CAD vendors seem to have a good grasp on how to handlethis problem using their own proprietary methods. Unfortunately, their methods are notcomplete as robustness issues are observed. Robustness towards generating valid modelingresults thus remains an open issue.2.3 Shape-Associativity InconsistenciesShape-associativity inconsistencies refer to situations where the model shape after a di-rect edit makes some constraints in the associativity layer inapplicable, and consequentlythe whole model's well-constraint state is broken. There are two major tasks involved inhandling such inconsistencies: inconsistency detection and inconsistency resolution. Thedetection task includes the evaluation of the model's constraint state and the extraction ofminimal over-constrained parts and maximal well-constrained parts in the model. Based onthe detection results, the resolution task adds/removes constraints to/from the model suchthat the model becomes well-constrained again.2.3.1 Inconsistency DetectionIn the last three decades, a good number of publications related to this topic have beenpresented, and a thorough review of them can be found in [30]. The ideas presented maybe classified into four categories: solving-based, logic-based, graph-based and perturbation-based. Among them, solving-based methods are the (conceptually) simplest. They analyze amodel's constraint state by directly solving the model GCS through either symbolic methods(e.g., Grobner bases, Wu-Ritt triangulation methods) or numerical methods (e.g., Newton-Raphson, homotopy continuation methods) [30]. These methods are rarely used in practicedue to high computational load.Logic-based methods, e.g., [51, 52], develop a set of geometric theorems and derivationrules and then, based on them, check if the model GCS can be logically derived. If so, themodel is well-constrained; if there are extra constraints, it is over-constrained; otherwise, it20is under-constrained. This process is essentially an axiomatization of all possible constraintsystems, which is of great mathematical elegance. However, the library of the geometrictheorems and derivation rules developed is far from being complete for practical usages.Graph-based methods analyze the model GCS in an indirect way that converts the GCSto a graph structure and then studies this graph instead of the original GCS. There are twolines of development. The first one tries to recognize pre-defined graph patterns (corre-sponding to known shapes) in the graph. This line was pioneered by Owen [53] and muchimproved in [54–56] in the size of the pattern library. The second line compares degreesof freedom (DOFs) of the model geometry with degrees of restriction of the model GCS.This line was first proposed by Bardord [57] and Serrano [58], and detailed in [59–61].In 2001, these two lines were unified under a framework proposed by Hoffmann et al.[20]. Ever since, there has still been some good progress, e.g., [62], but the foundationsremain unchanged. Although graph-based methods could be effective in many scenarios, aknown limitation is the incapability to handle constraint dependencies (except for the sim-plest structural dependencies) [63]. The reason is that the graph representation only capturesthe combinatorial information of the model GCS and discards all geometric information.To overcome the limitations of graph-based methods, Michelucci's group [63] proposedthe witness configuration method, which basically revisited and improved the previous in-finitesimal rigid theory [64]. This method examines how constraint equations behave underinfinitesimal perturbations made to the constraint equation variables, whose relationship isdescribed by the associated Jacobian matrix of the constraint equations. That is, the depen-dent rows of this matrix characterize the (structural and non-structural) constraint dependen-cies, and the kernel of this matrix gives the model's DOFs [35, 36]. A successful applicationof this method requires the Jacobian to be evaluated at a carefully selected point called thewitness configuration, which has satisfied all the degenerate constraints (e.g., parallel andincident constraints) in the model GCS [65]. It is for this reason that this method is namedthe witness configuration method.21This method has been successfully applied to some real problems recently such as [37,38]. At present, it has been proven that all constraint dependencies (i.e., over-constraint) canbe detected using this method [36]. Nevertheless, according to the author's investigation,the developed criteria for characterizing well-constraint and under-constraint are not thateffective and may give wrong results for 3D variational models. This limitation has not beendiscussed in previous studies, and revealing it (Chapter 6) is one of this work's contributions.In addition, the methods [35–38] developed for detecting minimal over-constrained partsand maximal well-constrained parts in a model are quite ineffective. Greedy algorithmshave been used to find such parts, but it is found that these algorithms cannot always do socorrectly, a consequence of greedy algorithms' inherent limitations.2.3.2 Inconsistency ResolutionDifferent from inconsistency detection, there has been much less research work on inconsis-tency resolution. The studies related to this topic are primarily from two domains: geometricconstraint solving and CAD model beautification. In the former domain, the methods de-scribed in [60, 66] may represent the first attempt. They are based on an old idea proposed in[67], which assigns weights to candidate constraints and selects those yielding the maximalsum of weights. This way of working relies heavily on the quality of the weighting scheme,but this part was not explained in detail. The second attempt may be made in [68–70]. Theyare based on the graph-based methods reviewed previously, which have already proven in-effective for models with constraint dependencies [63]. A very recent attempt is based onthe witness configuration method [37, 38]. They are restricted to dealing merely with over-constrained models. In other words, they are not able to handle general situations involvingboth under-constrained and over-constrained parts. Even for over-constrained models, theyare limited: models in [37] were restricted to those composed only of points and lines, whichare not even solid models. The graph-based methods were still partially used in [38], in away inheriting the limitation of graph-based methods.22The CAD model beautification domain collects studies of removing imprecisions (andtherefore called beautification) in reverse engineered models through the guidance of ge-ometric constraints. These constraints are generated automatically from the reverse engi-neered model, and quite often there are more generated constraints than needed. To de-termine which constraints need to remain, a prioritization of the generated constraints isnecessary. Constraint prioritization may be done qualitatively or quantitatively. The formerscheme prioritizes constraints based on their types and a set of heuristics [71–74]. Thisscheme has the limitation that it cannot handle subtler ranking among constraints havingthe same type. This is where the quantitative scheme can help. Langbein et al. [75] andLi et al. [76] proposed to quantitatively prioritize constraints using the deviation betweenthe nominal parameter value of a constraint and its corresponding dimension in the reverseengineered model. Apparently, this deviation-based prioritization only works if there areimprecisions in the model. Due to this restriction, their methods are not applicable to thiswork. Nevertheless, the type-based prioritization methods in [71–74] are still applicableand will be adapted and incorporated into the constraint prioritization method proposed inthis work.The review above suggests that there is a better research basis for the problem of shape-associativity inconsistency resolution than for the problem of geometry-topology inconsis-tency resolution (which has few useful publications). Quite a few directions have been ex-plored for both inconsistency detection and inconsistency resolution, although most of themhave proven unsuccessful or too restrictive. This allows us to figure out the most promisingdirections quickly and to build our solution on top of them (e.g., the witness configurationmethod). Nevertheless, the development of these directions is still very preliminary in termsof addressing the specific problems in this work. This gap will be filled by the new/improvedmethods presented in Chapters 6 and 7.23Chapter 3: Issues of Variational Direct ModelingThis chapter provides a thorough analysis of the problem of geometry-topology inconsis-tency resolution and the problem of shape-associativity inconsistency resolution. Basically,it answers the following fundamental questions: how are the inconsistencies formed, whatare the checking conditions for them, and why is resolving them challenging? The answerswill direct us to propose solutions to the point in the following chapters.3.1 Issues of Geometry-Topology Inconsistency Resolution3.1.1 Inconsistency FormationWhen push-pull direct modeling is applied to a model, only the target positions and orien-tations of the push-pulled boundary faces are specified by the user. The associated changesmade to the boundaries of the push-pulled boundary faces as well as those of the other af-fected boundary faces in the solid model are not quite known. Hence, every push-pull moveneeds to be followed by a boundary regeneration process for the push-pulled model. Thisregeneration is performed through intersecting the post-edit surfaces (including surfaces ofthe push-pulled faces and those of the unmoved faces) in the geometry with respect to thepre-edit model topology.The boundary regeneration process itself is trivial, but it may fail to output a valid model(being a solid model), as shown in Fig. 3.1. If a valid model is output, the geometry infor-mation and topology information in the post-edit model are consistent with each other, andnothing further needs to be done. If not, there are inconsistencies between the geometryinformation and topology information in the post-edit model, and actions need to be taken24 Regenerated Models Pre-Edit Model Valid Invalid Figure 3.1: Examples of model boundary regeneration.to resolve them. These inconsistencies take the form of extra connections between surfacesin the geometry that are not supposed to occur regarding the topology or take the form ofimpossible connections between surfaces in the geometry, which however have been definedin the topology.3.1.2 Inconsistency Checking ConditionsIt has been presented in Section 2.1 that, for a solid to be valid, the following four conditionsmust be satisfied: bounded, closed, regular, and semi-analytic. These conditions are forsolids rather than for solid models. By doing some translations [8, 43, 77], the counterpartconditions for B-rep solid models can be given as follows:1. A face is a bounded, regular, and semi-analytic subset of an at least piecewise analyticsurface in R3, and the face interior must be connected;2. Each edge is shared by exactly two faces;3. Faces around each vertex form a closed fan; and4. Faces may intersect only at common edges or vertices.25Essentially, Condition 1 requires faces to be well-bounded, meaning each face's boundaryis not open or self-intersected [1]. Conditions 2 and 3 ensure manifoldness along each edgeand around each vertex. Condition 4 ensures manifoldness over the face interior. It shouldbe noted here that the Euler-Poincare characteristic, which was widely used to validate B-rep solid models, is only a necessary but not sufficient condition for model validity [43].When it comes to geometry-topology inconsistencies, the above checking conditions canbe further specialized. As already noted, geometry-topology inconsistencies result fromextra or impossible connections between surfaces. In other words, a geometry-topologyinconsistency is a result of either inserting a new connection or losing an old connectionbetween surfaces, as shown in Fig. 3.2. Connections represent surface-surface intersection,which in turn gives edges on faces. Hence, losing an old connection means that there isno intersection between two surfaces, and then faces become open, violating the validityCondition 1. Inserting a new connection means that there exist extra edges within a face,violating the validity Condition 4 and again, leading to an ill-bounded face. The checkingconditions for geometry-topology inconsistencies can thus be narrowed down to checkingif there exist ill-bounded faces in the regenerated model. Old Connection Lost (a) Push-Pull Boundary Regeneration (b) Boundary Regeneration Push-Pull New Connection Inserted Figure 3.2: Geometry-topology inconsistency types.263.1.3 Inconsistency Resolution IssuesIn resolving geometry-topology inconsistencies, the applied resolution method should al-ways output valid models. This is, however, not straightforward because there exist manyresolution options. For example, Fig. 3.3 shows three sample options for resolving an ill-bounded face of the case in Fig. 3.2b. These options together with those due to other ill-bounded faces correspond to multiple outcomes for the whole model. Further, any edge ona resolved face should be shared with a neighboring face so as to satisfy the manifoldnessconditions, and meanwhile the neighboring faces have to be well-bounded as well. As a re-sult, decision-making in inconsistency resolution is error-prone. For instance, if the bottomoption for the case in Fig. 3.3 is chosen, all the faces depicted as light gray should not exist.These faces will thus be deleted. This, in turn, makes the previously well-bounded facesthat are depicted as red ill-bounded, indicating a failed resolution.In addition to the validity issue, the generation of predictable modeling results is also abig problem. Among the many resolution options, some will lead to invalid modeling re-sults; among the valid results, there will only be one in line with the designer's intent. As aresult, decision-making in the inconsistency resolution is also prone to unpredictable mod-eling results. The fundamental challenge of resolving geometry-topology inconsistenciesthus lies in the robustness towards generating valid and predictable modeling results. Deleted Faces Ill-bounded Faces Ill-bounded Face Resolution Options Figure 3.3: An incorrectly selected resolution option leading to an invalid model.27Design intent is, however, too complicated to infer satisfactorily by a computer [78],and consequently a resolution method giving 100% predictable modeling results may notbe achievable at least at present. Fortunately, it has been shown in [79, 80] that much, ifnot all, of the unpredictable modeling behavior in CAD can be avoided if the model varia-tion follows a continuous change pattern. The problem of generating valid and predictablemodeling results can thus be narrowed as generating valid models with continuous modelvariations.It is equally challenging to attain continuous model variations even if the resolutionmethod successfully avoids invalid modeling results. To maintain a manifold solid model, achoice made locally to a face affects its neighboring faces, and so forth. A local choice thushas a global effect on the whole model. As a result, decision-making in the inconsistencyresolution is very subtle. For example, Fig. 3.4 shows that two different local choices canlead to two completely different outcomes. Therefore, it is hard to make appropriate localchoices so that modeling results follow a continuous change pattern. Boundary Regeneration Push-Pull Ill-bounded Face Resolution Options Figure 3.4: Different applicable resolution options leading to varied model shapes.28In summary, issues of resolving geometry-topology inconsistencies lie in the robustnesstowards generating valid modeling results and continuous model variations, a consequenceof the intrinsic ambiguity (many resolution options) in the resolution process. To date, nosystematic methods for handling these issues have been reported, and commercial CADsystems are not able to address them satisfactorily (see case studies in Chapter 5).3.2 Issues of Shape-Associativity Inconsistency Resolution3.2.1 Inconsistency FormationPush-pull direct modeling could cause not only geometry-topology inconsistencies but alsoshape-associativity inconsistencies. Before a push-pull edit is applied, the model understudy is well-constrained. After the push-pull edit is applied and the associated geometry-topology inconsistencies are resolved (if successful), the resulting solid model, or a portionthereof, has new boundary faces and dimensions. These new boundary faces and dimensionsmay disagree with the constraints in the pre-edit model GCS, as shown by the second andthird columns in Fig. 3.5. Hence, the model GCS needs to be updated accordingly: replacethe constraint parameter values with the dimensions of the new solid model and remove anyinapplicable constraints, as shown by the fourth column in Fig. 3.5.Similar to the situation in model boundary regeneration in Section 3.1, the above modelconstraint update process itself is trivial, but it may fail to output a valid model (being awell-constrained model). If a valid model is output, the shape information and associativ-ity information in the post-edit model are consistent with each other, and nothing furtherneeds to be done, as shown by the top example in Fig. 3.5. If not, there are inconsistenciesbetween them, and inconsistency resolution is a necessity. These inconsistencies take theform of under-constraint and over-constraint. Under-constraint means that there are fewerconstraints in the model GCS than needed to fully restrict the model geometry, and over-constraint means that there are more constraints than needed. Both under-constrained andover-constrained parts are not supposed to exist in a well-behaved design model. The mid-29 Pre-Edit Model Post-Edit Solid Model Updated Model GCS State Change Solid Model GCS 1. Distance(F1,F3)=1 2. Distance(F2,F4)=1 3. Distance(F5,F6)=1 4. Perpendicular(F1,F5) 5. Perpendicular(F1,F4) 6. Perpendicular(F4,F5) 1. Distance(F1,F3)=1 2. Distance(F2,F4)=2 3. Distance(F5,F6)=1 4. Perpendicular(F1,F5) 5. Perpendicular(F1,F4) 6. Perpendicular(F4,F5) Well To Well 1. Distance(F1,F3)=1 2. Distance(F2,F4)=1 3. Distance(F5,F6)=1 4. Perpendicular(F1,F6) 5. Perpendicular(F1,F4) 6. Perpendicular(F4,F6) 1. Distance(F1,F3)=1 2. Angle(F2,F4)=135° 3. (Removed) 4. Perpendicular(F1,F6) 5. Perpendicular(F1,F4) 6. Perpendicular(F4,F6) Well To Under 1. Distance(F1,F3)=1 2. Distance(F5,F6)=1 3. Perpendicular(F1,F5) 4. Perpendicular(F1,F4) 5. Perpendicular(F4,F5) 6. Angle(F2,F4)=150° 7. Angle(F2,F5)=60° 8. Length(E1)=1 1. Distance(F1,F3)=1 2. Distance(F5,F6)=1 3. Perpendicular(F1,F5) 4. Perpendicular(F1,F4) 5. Perpendicular(F4,F5) 6. Parallel(F2,F4) 7. Perpendicular(F2,F5) 8. Length(E1)=1 Well To Over F4 F3 F1 F2 F5 F6 F4 F3 F1 F2 F5 F6 F4 F3 F5 F2 F6 F1 E14 Figure 3.5: Model constraint update and varying constraint state change results.dle example in Fig. 3.5 shows the under-constraint situation (plane F2 has free motions withrespect to other planes). The bottom example in Fig. 3.5 shows the over-constraint situation(constraints 5, 6, and 7 are dependent).3.2.2 Inconsistency Checking ConditionsAs shape-associativity inconsistencies take the form of under-constraint and over-constraint,we simply need to evaluate a post-edit model's constraint state to check if there exist shape-associativity inconsistencies in the model. The evaluation of a model's constraint state canbe expressed in terms of the following definitions.Definition 1. Let F (X) = 0 be the constraint equations of a model's constraint system,and S the solution space. The model is consistently constrained if S 6= ∅, and inconsistentlyconstrained otherwise.30Definition 2. Let F (X) = 0 represent a consistently constrained model, and S thesolution space. The model is under-constrained if the cardinality |S| is infinite (up to rigidtransformations).Definition 3. Let F (X) = 0 represent a consistently constrained model, and S thesolution space. The model is consistently over-constrained if there exists a subset of themodel's GCS such that its constraint equations have the same solution space as S.Definition 4. A model is over-constrained if it is inconsistently constrained or consis-tently over-constrained.Definition 5. A model is well-constrained if it is neither under-constrained nor over-constrained.It should be noted here that, although there has been prior knowledge of these defini-tions, they are scattered in different publications like [20, 35, 38, 61] and often stated in aninformal manner. What has been presented here is a more concise and precise version ofthem.3.2.3 Inconsistency Resolution IssuesSimilar to geometry-topology inconsistency resolution, shape-associativity inconsistencyresolution is also under the situation where there are multiple resolution options. Consider,for example, the bottom case in Fig. 3.5. The updated model GCS yields an over-constrainedmodel, and the over-constraint involves a cyclical dependency among constraints 5, 6, and7: constraints 5 and 6 can derive constraint 7. Removing any constraint not involved inthe dependency cannot resolve the over-constraint and leads to a failed resolution. Onlyremoving a constraint relevant to the cyclical dependency can resolve the over-constraint,as shown in Table 3.1. Therefore, robustness towards generating valid modeling results is aalso major issue in shape-associativity inconsistency resolution.There are differences between the robustness issues here and those in geometry-topologyinconsistency resolution. Over-constrained and under-constrained parts in a model can usu-31 Updated Model GCS Candidate Resolution 1 Candidate Resolution 2 Candidate Resolution 3 1. Distance(F1,F3)=1 2. Distance(F5,F6)=1 3. Perpendicular(F1,F5) 4. Perpendicular(F1,F4) 5. Perpendicular(F4,F5) 6. Parallel(F2,F4) 7. Perpendicular(F2,F5) 8. Length(E1)=1 1. Distance(F1,F3)=1 2. Distance(F5,F6)=1 3. Perpendicular(F1,F5) 4. Perpendicular(F1,F4) 5. Perpendicular(F4,F5) 6. (Removed) 7. Perpendicular(F2,F5) 8. Length(E1)=1 1. Distance(F1,F3)=1 2. Distance(F5,F6)=1 3. Perpendicular(F1,F5) 4. Perpendicular(F1,F4) 5. (Removed) 6. Parallel(F2,F4) 7. Perpendicular(F2,F5) 8. Length(E1)=1 1. Distance(F1,F3)=1 2. Distance(F5,F6)=1 3. Perpendicular(F1,F5) 4. Perpendicular(F1,F4) 5. Perpendicular(F4,F5) 6. Parallel(F2,F4) 7. (Removed) 8. Length(E1)=1 Table 3.1: Candidate resolution options for the bottom case in Fig. 3.5.ally be resolved individually. The reason for this is that whether an option is able to resolvean individual over-constrained or under-constrained part successfully can be determinedimmediately after the corresponding constraint is added or removed. Geometry-topologyinconsistency resolution is not under such an advantageous situation: evaluating the successshould be done at the end of the resolution process and for all the ill-bounded faces togetherdue to the manifoldness requirements.The differences stated above allow for deeper insights into the robustness issues ofshape-associativity inconsistency resolution. Apparently, an effective characterization ofconstraint states can partly solve the robustness issues as it can tell whether an over- orunder-constrained part is resolved successfully or not. More importantly, over-constraintand under-constraint being able to be resolved individually implies that an effective detec-tion of over-constrained and under-constrained parts can completely solve the robustnessissues. Consider the bottom case in Fig. 3.5. Given that the only over-constrained part (con-straints 5, 6, and 7) is successfully detected, irrelevant resolution options (constraints 1, 2,3, 4, or 8) can be excluded, and then chances of attaining an invalid modeling result can beeliminated. When there are multiple over-constrained parts, the detected parts should be ofminimal sizes in order to avoid including any irrelevant constraints. For under-constrainedparts, a similar requirement can be stated: the detected under-constrained parts should haveminimal sizes. This requirement is equivalent to maximizing well-constrained parts becauseDOFs between well-constrained parts describe under-constraint. Then, the issues under-32lying the robustness issues lie in the effectiveness towards the correct characterization ofconstraint states and the optimal detection of over-constrained and well-constrained parts.Quite often, there is more than one valid resolution option even if the resolution methodsuccessfully avoids invalid resolution options. The options presented in Table 3.1 are typ-ical examples of such a situation. Decision-making among these valid resolution optionsis complicated due to the design intent issue involved. As a result, a completely automaticdecision-making method seems to be impossible [78, 81], and a decision-support schememay be a more practical choice. The key part is to have a prioritization of valid resolutionoptions so as to recommend them to users in an incremental manner. An effective prioriti-zation criterion should give a good measure of the impact of removing/adding a constrainton the model shape. The problem is, however, not straightforward since the qualitative op-eration of removing/adding constraints has no direct connections to the quantitative notionof model shape.In summary, issues of shape-associativity inconsistency resolution lie in the effective-ness towards avoiding invalid resolution options and prioritizing valid resolution options.The problem of avoiding invalid resolution options consists primarily of minimal over-constraint detection, maximal well-constraint detection, and correct constraint state char-acterization. To the author's knowledge, despite the longstanding presence of geometricconstraints in CAD, no satisfactory methods for handling these effectiveness issues havebeen given, as reviewed in Chapter 2.3.3 SummaryThe major issues in variational direct modeling lie in addressing the possible geometry-topology inconsistencies and shape-associativity inconsistencies in a post-edit model. Thegeometry-topology inconsistencies mean that there are extra or impossible connections(topology information) between surfaces (geometry information). They take the form ofill-bounded faces. The difficulty of resolving these inconsistencies lies in the robustness33towards generating valid modeling results and continuous model variations. The shape-associativity inconsistencies refer to the situations where there are extra constraints or in-sufficient constraints (associativity information) to restrict the model geometry. They takethe form of over-constraint and under-constraint. The fundamental challenge lies in theeffectiveness towards avoiding invalid resolution options and prioritizing valid resolutionoptions.These issues are to be addressed in the following four chapters. The first two chapters fo-cus on geometry-topology inconsistencies: Chapter 4 addresses the detection of geometry-topology inconsistencies in a model, and Chapter 5 the resolution of the detected inconsis-tencies, i.e., making decisions among resolution options. The next two chapters are devotedto shape-associativity inconsistencies and will be presented in a similar way to the preced-ing two chapters: Chapter 6 deals with the detection problem, and Chapter 7 the resolutionproblem.34Chapter 4: Geometry-Topology Inconsistency DetectionTo repeat, direct edits only change the geometry information layer in a model, and thischange will not be reflected in other information layers automatically. This could breakthe consistency between the geometry and topology in the model, as well as the consistencybetween the shape and associativity in the model. This chapter and the next one focus on thegeometry-topology inconsistency. To address inconsistencies of this kind, the informationin the topology that is related to the changed part in the geometry needs to be taken out andrethought. This chapter addresses the "taken out" task.By "taken out", the author does not mean just picking out ill-bounded faces in the regen-erated model (which is trivial), but rather detecting critical points where geometry-topologyinconsistencies occur during the direct edit. Such critical points are of vital importance be-cause they carry the inconsistencies' history information and serve as the building blocksof a systematic inconsistency resolution method based on the principle of continuity. Thischapter first introduces this principle, and then proposes the concept of critical points, andfinally presents the critical point detection method.4.1 The Principle of ContinuityRather than adopting a heuristic approach, which can provide acceptable results in many butnot all of the potential cases, this work develops a systematic method to attain guaranteedmodel validity and continuous model variations for resolving geometry-topology inconsis-tencies. This is essentially achieved by using the principle of continuity to govern the wholeresolution process. The principle states that an infinitesimal change in a model edit will only35yield an infinitesimal change in the resulting model [79, 80, 82]. An infinitesimal change inpush-pull direct modeling means an infinitesimal change made to the push-pull parametersuch as the translated distance or rotated angle. An infinitesimal change in the resultingmodel refers to an infinitesimal change made to a certain attribute of the model. To be moreprecise, let the push-pull move be represented by the user-specified rigid transformationmatrix, denoted as T (t), t ∈ [0, 1], and the model variation over this move be representedby M(t), t ∈ [0, 1]. The principle of continuity can then be formulated as:f(M(t+ ε), M(t))→ 0 when ε→ 0 (4.1)where f(M1, M2) is a function quantifying the difference between modelsM1 andM2 withrespect to a certain model attribute.To determine an applicable model attribute to be used in the function f , model facearea and model volume that are directly related to visual perception are good candidates.However, model faces may cancel each other out during a push-pull move, resulting in asudden, discontinuous change on the model face area. Fig. 4.1 depicts a typical examplewhere push-pulling the blue face immediately after the orange location will cause face F1to be deleted suddenly, leading to a discontinuous face area change. As a result, the modelface area is not an applicable model attribute to be used in f . Rather, the function f is to beformulated in this work using the model attribute of volume to define the continuous modelvariation. F1 Figure 4.1: A push-pull edit leading to a sudden deletion of face F1.364.2 Geometry-Topology Inconsistency PointDespite a push-pulled face is being moved continuously, the involved inconsistency reso-lution is, in fact, to be handled in a discrete manner. The push-pull move can be classifiedinto different phases, and it is transitioning from one phase to the next by going throughinconsistency resolution. Consider, for example, the push-pull move depicted in Fig. 4.2a.Let t denote an intermediate value within the push-pull domain [0, 1]. If t is relatively small,it is found that inconsistency resolution is not needed since the regenerated model remainsvalid and consistent with the principle of continuity (Fig. 4.2b). Increasing t to a certainvalue would necessitate inconsistency resolution. As depicted in Fig. 4.2c, inconsistencyresolution at τ− ε is still not needed, but it is needed at τ + ε in order to resolve the invalidmodel shown in Fig. 4.2d. As can be seen, it is the crossing of the point τ that the need ofinconsistency resolution emerges and that changes made to the model topology are needed.The more of such points a push-pull move needs to cross, the more inconsistency resolutionis needed. Due to the difficulty associated with crossing each such point, it is less likelythat a valid result with a continuous model variation can be attained when many of suchpoints are to be crossed. These points are referred to in this work as geometry-topologyinconsistency points (GTIPs). Formally, for an infinitesimal perturbation ε, if the models atτ− ε and τ + ε have different topologies, the point τ is deemed a GTIP.With GTIPs in place, a push-pull move can be applied progressively. Consider a push-pull move crossing only one GTIP, like the case of Fig. 4.2a. Instead of resolving thegeometry-topology inconsistency at the end of the push-pull move, the inconsistency formedimmediately after the GTIP is resolved first, resulting in an intermediate model. The restof the push-pull move is then applied to the intermediate model. In other words, the origi-nal push-pull move is decomposed into two sequential, smaller push-pull moves. The firstapplies the transformation T (τ + ε) to the original model M(0) where τ denotes the GTIP.The second applies the remaining transformation T (1)T (τ+ε)−1 to the intermediate modelM(τ + ε). This decomposition is beneficial because inconsistency resolution at τ + ε is37 ! 0 1 (a) (b) (d) (c) $ − & $ $ + & Figure 4.2: A geometry-topology inconsistency point: (a) push-pull move; (b) regen-erated model at t; (c) crossing a GTIP at τ; and (d) regenerated model at τ + ε.simple since a valid reference model M(τ − ε) is close by, and the principle of continuitycan thus be exploited. By contrast, inconsistency resolution at the end of the push-pull moveis not under such an advantageous situation. Generalizing the statements above to push-pulldirect modeling with multiple GTIPs yields a sequential approach to address geometry-topology inconsistencies, as shown in Fig. 4.3. With this sequential approach, the originalone-time decision-making for inconsistency resolution is decomposed into a sequence ofsmaller, simpler decision-making. If each such smaller decision-making maintains a con-tinuous change to the model, the principle of continuity is satisfied for the model throughoutthe push-pull move.Apparently, the above sequential approach cannot be made possible without an effectiveGTIP detection method. Two GTIP detection methods are to be presented in the followingtwo sections, respectively. The first is heuristic-based and computationally efficient, butthere are scenarios this method cannot handle. The second is systematic and able to coverall cases but leads to a much higher computational load. This work uses a hybrid of them toachieve the best performance.38 Input Model & Push-Pull EditAny GTIP?Output ModelUpdated Model & Push-Pull Edit Detect GTIPModel Boundary RegenerationResolve GTIYESNO Figure 2 Schematic diagram of the overall method (GTI: geometry-topology inconsistency). Figure 4.3: Schematic diagram of the geometry-topology inconsistency resolutionframework (GTI: geometry-topology inconsistency).4.3 Proposed Detection Methodology ITo the author's knowledge, existing methods related (directly and indirectly) to GTIP de-tection are [50, 83, 84]. The ideas presented are heuristic-based, which basically detectGTIPs by predicting whether a certain geometry-topology inconsistency pattern occurs dur-ing a push-pull move, based on a prior pattern library. However, the developed heuristicsare far from being sufficient for practical usages. The heuristics in [50] are specific formodels composed only of planar, non-holed faces. There are no systematic methodologiesexplained in [83, 84], but rather preliminary ideas.This section presents a new set of heuristics to achieve much broader applicability. Theheuristics are able to handle push-pull direct modeling where all faces, except for the push-pulled faces, are stationary. This way of working represents the basic mode of push-pulldirect modeling, as shown in Figs. 3.1 and 3.2. Push-pull direct modeling has the othermode where neighboring faces of push-pulled faces are also made movable to keep the39smooth connections [85] between them (Fig. 4.6 in the next section shows an example ofthis situation). For this mode, there are additional challenges that cannot be handled by theheuristic-based strategy (will be discussed in detail in the next section).GTIPs are critical points at which ill-bounded faces are formed. To list geometry-topology inconsistency types exhaustively, all boundary faces in a model are divided intotwo groups: the inner group consisting of the push-pulled face and its neighboring faces, andthe outer group consisting of the remaining faces. Then, we have three possible ways thatinconsistencies could occur, as shown in the left column of Table 4.1. Recall that geometry-topology inconsistencies take the form of either losing old connections between surfaces orinserting new connections between surfaces (Section 3.1). Each of the previous three waysthus further has two inconsistency types, which lead to, in total, six nominal inconsistencytypes (Table 4.1). In reality, three of them (as indicated by the cross marks in Table 4.1) areimpossible because the neighboring faces in the inner group and all faces in the outer groupare set stationary, and stationary faces by themselves cannot generate ill-bounded faces. Forthe three possible types as indicated by the check marks in Table 4.1, typical examples aregiven in Fig. 4.4.For each of the three possible types in Table 4.1, we can use heuristics to predict ifthe corresponding inconsistency occurs during a push-pull move. The developed heuristicsare summarized in Table 4.2, and the explanation is as follows. For type I (Fig. 4.4a),new connections are inserted on inner-group faces only, and a push-pull move will shrinkFaces Involved in Inconsistency Inconsistency Types Inserting New Connections Losing Old Connections Within inner group ü (Fig. 4.4a) ü (Fig. 4.4c) Within outer group û û Between inner and outer groups ü (Fig. 4.4b) û Table 4.1: Geometry-topology inconsistency types.40 New Connection Inserted (a) (c) Old Connection Lost (b) New Connection Inserted Figure 4.4: Illustrations of geometry-topology inconsistency types.or expand inner-group faces on their respective underlying surfaces. Hence, the potentialGTIP corresponds to a certain intersection between the underlying surfaces of the inner-group faces, as shown in Fig. 4.5a.For type II (Fig. 4.4b), new connections are inserted between inner and outer groupfaces. The push-pulled face will be the first face in the inner group to meet the outer-groupfaces since other faces are stationary. The potential GTIP thus corresponds to a certaincollision between the push-pulled surface and outer-group faces, as shown in Fig. 4.5b.For type III (Fig. 4.4c), old connections are lost on inner-group faces only, meaning thepush-pulled surface no longer intersects its neighboring surfaces. A surface-surface inter-section is lost either because one surface moves beyond the size limit of the other surface, ortwo surfaces become parallel and intersect at infinity. For the first situation, the push-pulledsurface becomes tangent to neighboring surfaces signals that the related intersection is aboutto be lost (Fig. 4.5c). For the second situation, the model becomes infinitely large with thepush-pull move. However, a design model undergoing modification cannot be made largerthan the modeling space. Hence, the geometric event signaling this situation is the collisionbetween an inner-group face and a pre-set box representing the modeling space (Fig. 4.5d).41 Inconsistency Type Heuristic Type I (Fig. 4.4a) Detect intersection between inner-group surfaces (Fig. 4.5a) Type II (Fig. 4.4b) Detect collision between a push-pulled surface and an outer-group face (Fig. 4.5b) Type III (Fig. 4.4c) 1. Detect tangency between a push-pulled surface and a neighboring surface (Fig. 4.5c) 2. Detect collision between an inner-group face and workspace (Fig. 4.5d) Table 4.2: Heuristics for geometry-topology inconsistency detection. (d) Modeling Space Collision (c) Tangency (a) Intersection Collision (b) Figure 4.5: Illustrations of the heuristics for geometry-topology inconsistency detec-tion.42With the above heuristics in place, getting the next GTIP can be done by sequentiallychecking the heuristics in Table 4.2 and then selecting the one with the smallest push-pullparameter, as shown in Algorithm 4.1. Lines 2-9 perform the checking heuristics regardinginconsistency type I, Lines 10-14 the checking heuristics regarding inconsistency type II,and Lines 15-21 the checking heuristics regarding inconsistency type III.Algorithm 4.1: GTIP Detection by HeuristicsAlgorithm 4.1: GTIP Detection Input: !,#$$ −The model and the push-pulled face Output: & − Next GTIP 1. & ← 1 // push-pull parameter, 1 means the end of the push-pull 2. #*+, ← GetNeighboringFaces(#$$) 3. for each face pair (./, .0), ./, .0 ∈ #*+, do 4. 3/, 30 ← GetUnderlyingSurface(./, .0) 5. if isIntersect(3/, 30) = 5678 then 6. &$ ← GetIntersectionPoint(3/, 30) 7. if 0 < &$ < 1 then & ← Min(&, &$) 8. end if 9. end for 10. ;$$ ← GetUnderlyingSurface(#$$) 11. for each outer-group face . ∈ ! do 12. &$ ← GetCollisionPoint(., ;$$) 13. if 0 < &$ < 1 and in #$$(&$) then & ← Min(&, &$) 14. end for 15. for each face . ∈ #*+, do 16. 3 ← GetUnderlyingSurface(.) 17. &$ ← GetTangencyPoint(3, ;$$) 18. if 0 < &$ < 1 then & ← Min(&, &$) 19. &$< ← GetCollision(., !=>?@ABC;DEF?) 20. if 0 < &$< < 1 then & ← Min(&, &$< ) 21. end for 22. Return & 434.4 Proposed Detection Methodology IIAs already noted, push-pull direct modeling has the other mode where neighboring facesof push-pulled faces are made movable to keep the smooth connections between them (re-ferred to as push-pull with smooth connections, Fig. 4.6), and the heuristic-based strategy isinapplicable to this mode. The following is the explanation for this statement. The heuristic-based strategy is essentially to predict whether a certain geometry-topology inconsistencypattern occurs during a push-pull move. Clearly, the prediction cannot work properly with-out the motion information of all movable faces. Such information is, however, not availablein the push-pull with smooth connection mode. To be more specific, the neighboring facesmove according to how the user moves the push-pulled faces, which is governed by a sys-tem of tangent constraints representing the smooth connections between faces. Not untilthis system is solved do we know the locations of the neighboring faces for any interme-diate instants within the push-pull move. In other words, there are no explicit expressionsfor the neighboring faces' motions. Without knowing these motions explicitly, predictinggeometry-topology inconsistencies cannot be made possible, and then the heuristic-basedstrategy becomes inapplicable.To address the challenge stated above, this work proposes a novel method that featuresan effective detection of GTIPs while avoiding the reliance on the motion information ofmovable faces. This is achieved via a novel reverse inference concept, which proposes Smooth Connection Moved Neighboring Face Push-Pushed Faces Kept Smooth Connection Figure 4.6: An example of push-pull with smooth connections.44to investigate geometry-topology inconsistencies presented in the regenerated model at theend of the push-pull move and then reversely track back to the critical points where theseinconsistencies occur, a concept similar to reverse engineering. To the author's knowledge,this idea has not yet been discussed in previous related studies.4.4.1 Overview of the MethodologyThe above reverse inference idea is to be implemented as three consecutive stages, as il-lustrated in Fig. 4.7. An example based on a connecting rod part is also given to assist theunderstanding of the workflow. At Stage 1, model boundary regeneration (as already dis-cussed in Section 3.1) is first performed. If there are no geometry-topology inconsistenciesin the regenerated model (i.e., a valid model is output), nothing further needs to be done. Ifotherwise, ill-bounded faces in the regenerated model are to be extracted, as shown by thecircled face in Fig. 4.7.Stage 2 investigates how topology changes on individual extracted ill-bounded faces.This is done by first identifying the edges involved in the changed topology (as shown byblue and red edges in Fig. 4.7) and then analyzing how their connection states alter: how twoedges change from being apart to being connected, or the other way around. This analysisserves as a basis for reversely inferring the critical events where the edge connection stateschange abruptly. For example, the critical event for the blue and red edges in Fig. 4.7 isthe tangency between them. Inferring such events may be straightforward using humanintuition but not the case using a computer. In the following, an effective method will bepresented to handle this challenge.At Stage 3, each of the critical events attained from Stage 2 is related to the push-pull parameter (the translation distance or rotation angle) through a system of algebraicequations. Let the push-pull parameter be represented by t ∈ [0, 1]. Solving the system forindividual critical events yields a list of critical points {ti}ni=1, and the smallest element inthis list corresponds to the next GTIP.45 Figure 3 Workflow of geometry-topology inconsistency detection (GTI: geometry-topology inconsistency). Regenerate Model & Extract Topology-Changed Faces Stage 1: GTI Extraction Topology Changed Input B-rep Model and Push-Pull Edit Push-Pull Blue Faces Stage 3: Push-Pull Parameter Calculation Relate Critical Events to Push-Pull Parameter & Choose Smallest Calculated Parameter Values Next GTI Critical Point Stage 2: GTI Critical Events Inference Identify Involved Face Edges & Infer Critical Events for Topology Changes Tangency From Edges to Events Regenerated Model Edge Connection State Change Illustration Figure 4.7: Workflow of geometry-topology inconsistency detection (GTI: geometry-top logy i onsistency).Among the three stages, the essential parts are the reverse inferring from ill-boundedfaces to critical events and the relating of these events to the push-pull parameter. Novelmethods are to be presented to deal with these problems in the remaining section of thischapter.4.4.2 Reverse Inferring of Critical EventsWithout loss of generality, we can focus on one ill-bounded face. For convenience, anextracted ill-bounded face from the regenerated model is referred to as a regenerated face; itscorresponding face in the pre-edit model is called a reference face. Recall that the very first46 Figure 4 Graph representation of boundary faces and identification of topology change subjects and history. !" !# !$ !% !& Regenerated Face 1 2 5 4 3 1 5 Difference Graph: (( − *) ∪ (* − () Reference Face Identified Topology Change Subjects & History 1 2 5 4 3 Connection Graph ( Connection Graph * Figure 4.8: Graph representation of boundary faces.task in the reverse inferring of critical events is to attain the edges involved in the changedtopology, giving rise to the need of retrieving and manipulating the topological informationon a boundary face. To facilitate such processing, a graph-based face representation schemeis used: connections of edges on a face are represented by a graph structure in which nodesencode the edge entities on the face, and arcs the connections between the edge entities.Fig. 4.8 shows an example of this graph representation scheme, using the reference andregenerated faces of the connecting rod example in Fig. 4.7.One of the benefits of using the graph representation scheme is that many operators havebeen made available to manipulate graphs. Those of interest are Boolean operations that canextract the difference between two graphs. To be more specific, the difference between theconnection graphs of the reference face Gref and regenerated face Greg is given by:∆G = (Greg −Gref ) ∪ (Gref −Greg) (4.2)The first subtraction acquires the newly added connections in Greg (w.r.t. Gref ), and the47second subtraction attains the lost connections in Greg (w.r.t. Gref ), and then their uniongives the total difference. It should be noted that Boolean operations on graphs have variousdefinitions [86]. Here, an edge-based definition is used. Let two graphs be represented byG1 = (V1, E1) and G2 = (V2, E2), where V1 or 2 is the node set and E1 or 2 the arc set. Graphsubtraction is given as G1 − G2 = ({nodes induced from E1 − E2}, E1 − E2), and thesame for graph union. Consider, for example, the two connection graphs in Fig. 4.8. Theapplication of Eq. 4.2 to them yields a difference graph that correctly captures the newlyadded connection between edges e1 and e5.The difference graph in Eq. 4.2 not only tells the subjects of topology changes but alsocarries part of the topology changes' progression history. Given a difference graph ∆G =(∆V,∆E), we can easily check if an arc e ∈ ∆E is from the regenerated connection graphGreg or the reference connection graph Gref . If e is from Greg, it represents a newly addedconnection, and thus the two edges' connection state progressed from being apart to beingconnected. If e is from Gref , it represents a lost connection, and thus the connection stateprogressed from being connected to being apart. Consider, again, the example in Fig. 4.8.The only arc of the difference graph comes from the connection graph B (i.e., Greg), andthus the topology change is a consequence of edges e1 and e5 moving into each other, asillustrated by the red arrow.A difference graph can give a list of edge pairs (having connection state changes) on anill-bounded face and their individual progression histories. Each progression thread makeseither two originally disconnected edges connected, or the other way around. The criticalevent for the progression from disconnection to connection is the collision between the twoedges. Generally, an edge-edge collision has two configurations: (1) involving only interiorpoints of both edges; and (2) having endpoints involved, as shown in Fig. 4.9. These twoconfigurations have different characteristic events. As can be seen from Fig. 4.9, the eventfor the left configuration is the interior-point tangency between the two edges, and that forthe right one is the end-point incidence. It should be noted here that no further information48 Figure 5 Example configurations of edge-edge collision. Figure 4.9: Example configurations of edge-edge collision. Figure 6 Example process of edge-edge separation. Figure 4.10: An illustration of edge-edge separation.is available for us to determine which of the two characteristic events actually occurredsince we do not know the motions of movable boundary faces. As a result, both eventsare possible and need to be checked. For the second progression type, from connection todisconnection, the critical event is the separation between the two edges' carrying curves,as shown in Fig. 4.10. To be more specific, one of the curves moved beyond the size limitof the other curve. The characteristic event is the tangency at the ends of the two edges.4.4.3 Mathematical Modeling of Critical EventsWith critical events in place, we need to relate them to the push-pull parameter to attain thecritical points at which these events occur. Based on the previous discussion, there are threecritical event types: interior-point tangency, end-point incidence, and end-point tangency.They can be further reduced to the following two basic types: tangency and incidence. It willbe shown that these two event types can be formulated as systems of algebraic equations.49A tangency (interior-point or end-point) between two edges can be expressed in terms ofthe following two sequential procedures: (1) the tangency between the two edges' carryingcurves; and (2) the examination of the tangency locating inside the limits of the edges orright at the edge ends. Formally, let two edges be represented by e1, e2, their respectivecarrying curves be c1, c2, and assume that the tangency of the two curves is at point p. Then,first of all, p has to satisfy the on-curve conditions:p ∈ c1 and p ∈ c2 (4.3)In general, carrying curves in a B-rep model are intersections of surfaces. Thus, the on-curveconditions can be modeled as:p ∈ c1 ⇔ F1(p) = 0F2(p) = 0p ∈ c2 ⇔ F2(p) = 0F3(p) = 0(4.4)where F1(·) = 0, F2(·) = 0, and F3(·) = 0 denote the equations of the surfaces adjacent tocarrying curves c1, c2, refer to Fig. 4.11 for an illustration of their relationship. !"($") !&($&) '& '" '( ') Figure 7 Illustration of edge-curve-surface relationship. Figure 4.11: An illustration of edge-curve-surface relationship.50In addition to the on-curve conditions, point p needs to satisfy the tangency conditionthat the two curves have collinear tangents at point p. The tangent for curve c1 (or c2) isgiven by the cross product of the normals of the surfaces F1 and F2 (or, F2 and F3). Thenormal of an surface F (x, y, z) = 0 is given by its gradient ∇F =(∂F∂x, ∂F∂y, ∂F∂z)[87]. Thetangency condition can then be formulated as:(∇F1(p)×∇F2(p))× (∇F2(p)×∇F3(p)) = 0⇔∇F2(p) · (∇F1(p)×∇F3(p)) = 0(4.5)where operators × and · denote the cross product and dot product, respectively. CombiningEq. 4.5 with Eq. 4.4 yields the mathematical modeling of the tangency event.For an incidence event at edge ends, it should first satisfy the on-curve conditions (i.e.,Eq. 4.4) and then satisfy the additional constraint that point p is at edge ends. As shown inFig. 4.11, the top end of edge e1 is the intersection of curve c1 and the surface F4. Thus, toimpose the edge end constraint, we only need to require that point p is on surface F4, whichis given by:F4(p) = 0 (4.6)This equation, together with Eq. 4.4, gives the mathematical modeling of the incidenceevent.In the formulation above for the tangency event, there are four equations (Eq. 4.4 and4.5) but three variables (i.e., the three coordinates of point p), and the same for the inci-dence event (Eq. 4.4 and 4.6). The missing variable is reserved for the push-pull parameter.Let the push-pull edit applied by the user be represented by a rigid transformation matrixT (t), t ∈ [0, 1]. This transformation matrix imposes the motion on push-pulled faces, andthis motion in turn drives their neighboring faces to move due to the smooth connectionsbetween them. The motions of all these faces are governed by a set of tangent constraints51between their carrying surfaces, which ensures that the smooth connections between themare to be preserved during the push-pull move. These tangent constraints can be translateddirectly to a system of algebraic equations using the existing research results in geometricconstraint solving such as [88]. Combining these equations with Eq. 4.4 and 4.5 (or 4.6)yields a new system of algebraic equations that relate the push-pull parameter to a criticalevent. In other words, by solving this new system, we can attain the exact value of thepush-pull parameter at which a given critical event occurs.Although constructing the tangent constraints and associated equations is straightfor-ward, a practical note should be made here. One can easily imagine a push-pull edit exam-ple where the push-pulled face has smooth connections with some of its neighboring faces,and these neighboring faces also have smooth connections with their neighboring faces, andso forth. The question then arises: which faces involved in this chain of smooth connectionsare movable? Different selections of faces lead to different systems of tangent constraints,which then yield different results in the push-pull parameter. The scheme used in this workis as follows: only the push-pulled faces and their immediate neighboring faces are movable.This scheme is used, simply because it is the very choice of the state-of-art CAD systemslike Siemens NX (11) and ANSYS SpaceClaim (19). Other schemes are also possible, andthe method presented here is readily applicable.In summary, Algorithm 4.2 shows how to combine the methods described previouslyto achieve an effective method of geometry-topology inconsistency detection. This algo-rithm follows the diagram in Fig. 4.7: first attain topology-changed boundary faces (Line2); then collect critical events using the method described in Section 4.4.2 (Line 5); thenrelate the collected critical events to the push-pull parameter with the method described inSection 4.4.3 (Lines 6-9); finally set the next critical point to the smallest of the calculatedcritical points.52Algorithm 4.2: GTIP Detection by Reverse InferenceAlgorithm 1: eometry-Topology Inconsistency Detection Input: !,# $ , $ ∈ 0,1 − the B-rep model and push-pull edit Output: the next critical point 1. !) ← RegenerateModel(!,#($ = 1)) 2. . ← GetIllBoundedFaces(!)) 3. #) ← ∅ // for storing critical points 4. for each face 0 ∈ . do 5. 1 ← InferCriticalEvents(0) 6. for each event 2 ∈ 1 do 7. $) ← RelateEventToPushPullParameter(2, $) 8. add $) to #) if 0 ≤ $) ≤ 1 // filter out invalid critical points 9. end for 10. end for 11. Return Min(#)) 4.5 Overall Detection Methodology: A HybridAs already noted, detection methodology I and detection methodology II have both capabil-ities and limitations, and they are complementary. To get the best of both methods, the finalgeometry-topology inconsistency detection method is made to be a hybrid of them. Thehybrid is done by using a selection control structure, based on the respective applicationconditions of the methods. To be more specific, detection methodology I is to be used inpush-pull direct modeling scenarios where movable boundary faces only involve the push-pulled boundary faces (referred to as push-pull without smooth connections), and detectionmethodology II is to be used in scenarios where movable boundary faces involve both thepush-pulled boundary faces and their neighboring boundary faces (referred to as push-pullwith smooth connections). The detailed procedures of this hybrid method are given in Al-gorithm 4.3.53Algorithm 4.3: A Hybrid GTIP Detection MethodAlgorithm 4.1: A Hybrid GTIP Detection Method Input: The given model and push-pull edit Output: Next GTIP 1. 𝑡 ← 1 // push-pull parameter, 1 means the end of the push-pull 2. if push-pull without smooth connections then 3. 𝑡 ← the output of Algorithm 4.1 4. else // represents push-pull with smooth connections 5. 𝑡 ← the output of Algorithm 4.2 6. end if 7. Return 𝑡 4.6 SummaryThis chapter first outlined a systematic approach to deal with geometry-topology inconsis-tencies, based on the principle of continuity. This principle was then formulated as succes-sive applications of GTIP detection and inconsistency resolution. The main body of thischapter was devoted to the GTIP detection problem.When developing the GTIP detection method, it was found that a whole category ofpush-pull direct modeling — push-pull without smooth connections — can be handled us-ing heuristic-based methods. On the other hand, there is the other category — push-pull withsmooth connections — which cannot be handled using heuristics at all. In this regard, a hy-brid method was developed: for push-pull without smooth connections, this work extendedand refined existing GTIP detection heuristics; for push-pull with smooth connections, thiswork proposed a novel reverse inference method. The main feature of this hybrid methodis that it gets the best out of individual sub-methods. The heuristic-based sub-method iscomputationally efficient but cannot cover all cases. The reverse inference based method issystematic and able to cover all cases but requires a higher computational load.54Chapter 5: Geometry-Topology Inconsistency ResolutionThis chapter deals with the other problem in addressing geometry-topology inconsisten-cies: rethinking the topology information relevant to the "taken out" inconsistencies. Theessential part is to make changes to such information and to handle the associated decision-making. This is to be done by a novel formulation of the continuity criterion as Booleanoperations on the model volume. This formulation, when combined with the GTIP detectionmethod presented in the previous chapter, will yield a systematic geometry-topology incon-sistency resolution method that guarantees valid modeling results and continuous modelvariations. In the following, the Boolean operation based formulation is first presented,followed by a detailed implementation of this formulation and a series of case studies vali-dating the proposed method.5.1 Boolean Operation Based Decision-MakingResolution options emerge whenever a GTIP is crossed. For example, Fig. 5.2a shows threesample options for the example in Fig. 5.1 (which is the same as the one shown in Fig. 4.2).The conceptually simplest way to make a decision among them and to apply the principleof continuity (Section 4.1) is to set a small ε and choose the resolution option that gives thesmallest volumetric difference from the model M(τ − ε), and the top option in Fig. 5.2awill be chosen. However, this requires an exhaustive list of resolution options to be availablefor comparison. A more effective way is to use Boolean operations to get to the intendedresolution option directly.55 (b) (a) 𝜏 − 𝜀 𝜏 𝜏 + 𝜀 Figure 5.1: Crossing a GTIP: (a) push-pull blue face to τ + ε; and (b) invalid modelgenerated at τ + ε. Figure 7 Crossing a TCP: (a) resolution options; and (b) continuous 𝑀(𝑡) attained from a swept volume based ∆𝑀(𝑡). (a) (b) 𝜏 + 𝜀 𝜏 𝜏 − 𝜀 Swept Volume Figure 5.2: Resolution options for crossing the GTIP in Fig. 5.1: (a) resolution op-tions; and (b) continuous model variation attained from the swept volume.It should be pointed out that as the model attribute of volume has been chosen to formu-late model difference for applying the principle of continuity, a continuous model variationM(t) means that the model volume change, represented by ∆M(t), is also continuous. Con-sider, for example, the case depicted in Fig. 5.1a. The model volume change at t ∈ [0, τ+ε]is given by:∆M(t) = M(0)−M(t) (5.1)where "−" denotes the Boolean difference operator. At τ− ε, the model volume change issimply the volume swept by the push-pulled face from 0 to τ− ε as shown in Fig. 5.2b. By56continuing this sweeping across the GTIP, a continuous model volume change is achievedover the domain [τ− ε, τ+ ε]. Refer to Fig. 5.2b for an illustration of this process. With themodel volume change ∆M(τ + ε) known, the model M(τ + ε) can then be obtained by asimple Boolean difference operation:M(τ + ε) = M(0)−∆M(τ + ε) (5.2)In the above equation, it is evident that if ∆M(t) is negative, the material/volume will beadded to the original model M(0).In the discussion above, a small perturbed value ε is utilized. In fact, the swept volume∆M(τ + ε) can be divided into two parts: one from 0 to τ and the other from τ to τ + ε.The latter part is then combined with the swept volume ∆M(t) from τ + ε to 1. Thisdivide-combine procedure should also be applied to a push-pull move with multiple GTIPs.Hereafter, the model volume change ∆M(t) from a GTIP to the next one is referred to inthis work as an auxiliary model. Combining the Boolean operation based decision-makingpresented here and the GTIP detection method (Algorithm 4.3) presented in the previouschapter yields an implementation of the resolution framework outlined in Fig. 4.3. Theonly missing part is the specific method for constructing auxiliary models, which is to beaddressed in the next section.5.2 Auxiliary Model Construction DetailsAuxiliary model construction maps the high-level intuition of the swept volume to low-level manipulation of geometric data in the model. The result is a B-rep model boundingthe volume swept by the push-pulled faces from a GTIP to the next GTIP. The proposedauxiliary model construction method is to be presented as two parts: one focuses on theconstruction for one moved face, the other for multiple moved faces (moved concurrently).This division is made because the former part will serve as the building blocks for the latter.575.2.1 Construction for One Moved FaceIn this subsection, the simpler situation is considered: only one face is push-pulled, andother faces are kept stationary. As we only consider the segment from one GTIP to thenext GTIP, the push-pulled face will not meet any faces except for its neighboring faces. Inother words, the volume swept by the push-pulled surface and bounded by the neighboringsurfaces gives the auxiliary model. The construction of the B-rep model for this volumecan be done by following this sweeping process, as illustrated in Fig. 5.3a and detailed inAlgorithm 5.1. First, a tube-like shell out of the neighboring faces is constructed by extend-ing the neighboring faces on their underlying surfaces towards the push-pulled face (Line2). Each face in this shell is then trimmed at the start and target location and orientation ofthe push-pulled surfaces (Lines 59). The trimmed shell along with the start and target facesform the desired B-rep model (Lines 8, 10 and 11).It should be noted that when the start and target surfaces intersect within the tube-likeshell, a self-intersecting auxiliary model would be generated as shown in Fig. 5.3b. For such Figure 9 Valid B-rep auxiliary model construction. (b) Next GTIP Target Surface Start Surface Subtractive Additive Next GTIP Shell (a) Auxiliary Model Trimming Start Surface Target Surface Figure 5.3: Illustrations of auxiliary model construction for one moved face.58Algorithm 5.1: Auxiliary Model Construction for One Moved Face Algorithm 3 Input: !"#$, !&&, ' − Neighboring faces, push-pulled face and the rigid transformation from a GTIP to the next one Output: ) − Auxiliary model 1. ) ← ∅ // array of boundary faces of the auxiliary model 2. !"#$ ← ExtendFaces(!"#$) 3. -. ← GetUnderlyingSurface(!&&) // the start surface 4. -/ ← TransformSurface(-., ') // the target surface 5. for each face 1 ∈ !"#$ do 6. 1 ← 1 − HalfSpaceFrom(-.) // Trim face with the start surface 7. 1 ← 1 − HalfSpaceFrom(-/) // Trim face with the target surface 8. add 1 to ) 9. end for 10. add 1 ← TrimSurfaceWithNeighborFaces(-., )) to ) // the start face 11. add 1 ← TrimSurfaceWithNeighborFaces(-/, )) to ) // the target face 12. Return A a situation, the resulting volume should be decomposed along the intersection into distinctparts as illustrated in Fig. 5.3b. The additive part is then added to the original model and thesubtractive part subtracted from the original model.5.2.2 Construction for Multiple Moved FacesTypical examples of multiple moved faces are push-pulling multiple faces concurrently,push-pulling with smooth connections, and even push-pulling edges or vertices (equivalentto push-pulling faces adjacent to the edges/vertices concurrently). Construction of auxiliarymodels for such cases can be done by applying the method presented previously to eachindividual moved face. In practical implementation, a direct application may, however, pro-duce the issues of missed volume or overlapped volume if the moved faces are adjacent.These two issues can be illustrated using the examples in Figs. 5.4 and 5.6. Consider thecommon V-slot mechanical part in Fig. 5.4. A missed volume between the individual aux-iliary models is generated by the two adjacent faces. To prevent such a missed volume,59 Figure 11 Issue of missed volume produced in concurrent push-pulling of adjacent faces by directly applying the single-face push-pulling method. Missed Volume Auxiliary Models Figure 5.4: Issue of missed volume produced in multiple moved adjacent faces bydirectly applying Algorithm 5.1. Faces to be Merged Figure 5.5: Preventing missed volume between adjacent auxiliary models by mergingedge-adjacent faces.the involved auxiliary models are to be modified slightly. As shown in Fig. 5.5, the missedvolume is prevented by preserving the edge-adjacency of the push-pulled faces and mergingthe edge-adjacent faces. It is simple to see that, if multiple faces incident to a vertex arepush-pulled, merging edge-adjacent faces automatically retains the vertex-adjacency of thepush-pulled faces.It is known that the result of Boolean operations is order-dependent when the operandmodels are volumetrically overlapped [8]. Consider, again, the V-slot model. If we push-pull towards a horizontal direction, two different modeling results will be generated, as de-picted in Fig. 5.6. To resolve this issue, a subdivision method is to be used. The overlappedvolume is to be isolated and treated separately. Let the two volumetrically overlapped auxil-iary models be denoted asA andB. They can be subdivided into three parts: the intersectionpart A∩B (the overlapped volume) and the remaining parts A− (A∩B) and B− (A∩B).60 Figure 13 Order-dependency of Boolean operations for overlapped volumes. Subtractive Auxiliary Model Additive Auxiliary Model 1. Subtraction 2. Addition 1. Addition 2. Subtraction Figure 5.6: Order-dependency of Boolean operations for overlapped auxiliary models. Figure 14 Application of the three-part decomposition method to the case in Fig. 13. Drop Intersection Addition & Subtraction Intersection Figure 5.7: Application of the three-part subdivision method to the case in Fig 5.6.The remaining parts A− (A∩B) and B− (A∩B) are then added to or subtracted from theoriginal model accordingly. If A and B are both addition (or subtraction), the intersectionpart A∩B is then to be added (or subtracted). If A and B are different (one addition and theother subtraction), the intersection part A ∩ B is then to be dropped due to the cancellationof the involved addition and subtraction. Fig. 5.7 shows the application of this subdivisionmethod to the case in Fig. 126.96.36.199 Implementation and Case StudiesWith the GTIP detection method and decision-making method made available, a systematicmethod, as outlined in Fig. 4.3, that features the robustness towards generating valid mod-eling results and continuous model variations can be attained/implemented. This sectionpresents case studies to validate this method.615.3.1 ImplementationThe methods presented previously have been implemented using C++ on top of the geomet-ric modeling kernel Open CASCADE (version 7.0). The graphical user interface module(Fig. 5.8a) was developed by using QT (version 5.7), taking the geometry processing andrendering framework OpenFlipper [89] as a reference source. To push-pull a model likethe one in Fig. 5.8a, the user presses the left button in the push-pull toolbox to activate thepush-pull direct modeling function and then selects the faces of interest. When the selec-tion is done, a graphical push-pull handle (on top of the blue faces in Fig. 5.8a) pops up,which allows the user to move the faces around. More specifically, the user clicks the tworectangular sub-handles labeled as 3 and 4 in Fig. 5.8a and moves the mouse to translateand/or rotate the push-pull handle (and therefore the selected faces). The rotation axis canbe controlled by moving the rectangular sub-handle that is labeled as 5 in Fig. 5.8a. Duringthe moving of the push-pull handle, the distance of translation and/or angle of rotation willbe displayed beside the corresponding sub-handles. When the moving is done, the methodpresented previously will update the model according to the specified push-pull parameters.For example, Fig. 5.8b shows the updated model for translating the blue faces towards theright by 7.5 mm.62 1. Imported Model 2. Push-Pull Toolbox 3. Translate Faces 4. Rotate Faces 5. Change Rotation Axis 3 5 1 2 4 Figure 8 Graphical user interface (a) of the push-pull with G1 connection system and (b) modeling result of translating blue faces. (a) (b) Figure 5.8: Graphical user interface of the geometry-topology inconsistency resolu-tion system (a), and modeling result of translating blue faces (b).635.3.2 Comparative Case StudiesCase Description. The proposed method in its complete form involves two major modules:GTIP detection and Boolean operation based decision-making. The GTIP detection moduleconsists further of two sub-modules: heuristic-based GTIP detection (Section 4.3) and re-verse inference based GTIP detection (Section 4.4). Three case studies were thus conductedto show the respective effectiveness of these modules/sub-modules. The effectiveness of theproposed method as a whole will be shown in the next section.Fig. 5.9 depicts the part models used in the three case studies. All of them were obtainedfrom the GrabCAD part library (https://grabcad.com/library). The first case study involvedpush-pulling a vice base part model; the second case study considered push-pulling a con-necting rod part model to a specialized part called angle-split connecting rod; and the lastcase study analyzed push-pulling a crank part model. If their model variations follow acontinuous change pattern, the models depicted in the bottom row of Fig. 5.9 are to beexpected.These case studies were designed carefully such that the effectiveness of the proposedmethod's constituent modules can be analyzed respectively. The first case study has multipleGTIPs (the top row of Fig. 5.10) and thus can be used to evaluate the GTIP detection module.Besides, this model consists only of planar faces, meaning there are no smooth connectionsto be kept; hence the heuristic-based GTIP detection method becomes dominant in the GTIPdetection module. The second case study differs from the first one in that there are smoothconnections to be kept, which can thus be used to show the effectiveness of the reverseinference based GTIP detection method. The third case study has only one GTIP (as shownin the top row of Fig. 5.12), and thus the influence of the GTIP detection module is notsignificant; the Boolean operation based decision-making module becomes dominant. Thiscase can thus be used to analyze the module of Boolean operation based decision-making.The modeling results of the proposed method have been compared with those of thestate-of-the-art commercial CAD systems. Five leading commercial CAD systems were64 (a) (c) (b) Figure 5.9: Comparative case studies: (a) push-pulling a vice base model; (b) push-pulling a connecting node model; and (c) push-pulling a crank model.tested: ANSYS SpaceClaim (19), Autodesk Inventor (2018), PTC Creo (Elements/Directmodeling 19), Siemens NX (11), and SolidWorks (2018). All of them support the modeof push-pull without smooth connection, and thus comparisons in the first and third casestudies were conducted using all of these CAD systems. However, for the push-pull withsmooth connection mode, not all of these CAD systems have this capability. SolidWorksbarely supports this mode; Autodesk Inventor and PTC Creo partially support this mode in afew selected scenarios; ANSYS SpaceClaim and Siemens NX fully support push-pull withsmooth connections. Between ANSYS SpaceClaim and Siemens NX, the latter has a betterperformance in terms of preserving smooth connections; sometimes the former even givesdistorted, nonsense model shapes. (ANSYS SpaceClaim, however, outperforms SiemensNX for push-pull without smooth connections.) Therefore, Siemens NX was chosen fordemonstrating the comparisons in the second case study. The comparison results are de-picted in the bottom rows of Figs. 5.10, 5.11and 5.12.Discussion. The push-pull move in the first case study needs to cross two GTIPs. Oneis the bottom face of the dovetail (labeled as F1) crossing the top face of the hole below thedovetail. The other is F1 crossing the bottom face of the hole (see the top row of Fig. 5.10).65In the figure, each GTIP has one or two branches, illustrating the flow from ill-boundedfaces (second row) to options of resolving these ill-bounded faces (third row) and then tothe resulting models from the respective options (bottom row). For the first GTIP, all thetested CAD systems were able to resolve the ill-bounded faces successfully and gave thesame modeling result as the proposed method. However, for the second GTIP, these systemswere seen to generate different modeling results. NX and SolidWorks failed to resolve thegeometry-topology inconsistencies, producing an invalid model (NX colors boundary facesin red whenever there is a resolution failure, as shown by Fig. 5.10). SpaceClaim, Creo,and Inventor were able to produce a valid model, but the model shape change was notcontinuous. Only the proposed method produced the desired result successfully.By examining the difference between the modeling result of the proposed method andthat of SpaceClaim, Creo, and Inventor, it can be seen that SpaceClaim, Creo, and Inventorgave the undesired result likely due to a lack of the GTIP-based decomposition mechanismin their methods. The modeling result of SpaceClaim, Creo, and Inventor possess extracuts (as circled in Fig. 5.10), which are very likely due to the side faces F3 and F4 of thehole. However, there should not be extra intersections between faces F3, F4 and faces F5,F6 if model regeneration for the second GTIP is performed with respect to the intermediatemodel at the first GTIP. In other words, it is impossible to get a resolution option from theill-bounded faces in the left branch of the second GTIP that can lead to the modeling resultof SpaceClaim, Creo, and Inventor. A plausible path that results in this modeling result isillustrated in the right branch of the second GTIP. It should be noted that, even followingthe right branch, the desired modeling result can still be attained as indicated by the dashedarrow. However, it would be much harder to achieve the desired modeling result this waythan having the GTIP-based decomposition. This is because the more GTIPs a push-pullmove crosses, the less similar the final model topology is to the original one. It is thus muchmore difficult to come up with the desired model topology directly at the end location of thepush-pull process.66 Key Ill-bounded Faces Key Ill-bounded Faces with Decomposition Key Ill-bounded Faces without Decomposition NX, SpaceClaim, Creo, SolidWorks, Inventor & Proposed Method Proposed Method SpaceClaim, Creo & Inventor NX & SolidWorks Resolution Options Resolution Options Resolution Options F5 F6 F2 F1 F2 F1 F2 F3 F4 Start F2 F1 GTIP 2 F5 F6 End F3 F4 GTIP 1 … … … Figure 5.10: Comparison of modeling results for push-pulling the vice base model.67The benefit and effectiveness of the GTIP detection module have already been shownin the above case study. Nevertheless, this case study only involved the heuristic-basedGTIP detection method, and the reverse inference based GTIP detection method was notactivated. The effectiveness of this method has thus not been validated. For this reason, thesecond case study was carried out, which worked in the push-pull with smooth connectionmode. Similar to the first case study, the involved push-pull move in this case study alsoneeds to cross two GTIPs (the top row of Fig. 5.11). Illustrations of the ill-bounded facesand resolution options are omitted this time as they are relatively straightforward for thiscase. Both of the GTIPs were successfully detected by the reverse inference based GTIPdetection method, and the expected intermediate and final modeling results were attained asshown in the bottom row of Fig. 5.11. By contrast, NX, which represents the industrial stateof the art, failed to generate correct modeling results at both GTIPs.The push-pull move in the third case study was purposely chosen to involve only oneGTIP so that Boolean operation based decision-making becomes dominant. The GTIP oc-curs at the point where faces F2 and F3 are eliminated when face F1 meets faces F4 andF5 (the top row of Fig. 5.12). The five CAD systems again produced inconsistent modelingresults. NX failed to produce a valid model. SpaceClaim, Creo, and Inventor output a validmodel but the model shape change was not continuous. SolidWorks gave the same mod-eling result as the proposed method. The probable reason for the discontinuous modelingresult of SpaceClaim, Creo, and Inventor is that they simply removed face F1 with the con-sumed faces F2 and F3, resulting in an abrupt change in the model geometry. The proposedmethod was able to successfully produce a valid modeling result with a continuous modelshape change by applying the principle of continuity which, for this case, simply removedthe volume swept by face F1.Based on the varying modeling results generated by the leading commercial CAD sys-tems in the three case studies, it is safe to say that robustness towards generating validmodeling results and attaining continuous model variations has not been reached yet in the68 GTIP 2 GTIP 1 Start End NX Proposed Method NX Proposed Method Figure 5.11: Comparison of modeling results for push-pulling the connecting rodmodel. SolidWorks & Proposed Method SpaceClaim, Creo & Inventor NX GTIP End Start F2 F3 F4 F5 F1 Figure 5.12: Comparison of modeling results for push-pulling the crank model.69solutions provided by industry. By contrast, the proposed method is seen to robustly resolvethe geometry-topology inconsistencies in all cases.5.3.3 Comprehensive Case StudiesThe previous section has validated the respective effectiveness of the proposed method'sconstituent modules. This section shows the effectiveness of the proposed method as awhole using a series of case studies with increasing complexity.The first case study analyzed push-pulling an axis support model where no GTIPs couldbe detected during the push-pull move (Fig. 5.13a), and thus the associated geometry-topology inconsistency resolution was trivial. For such situations, the proposed method cansuccessfully give desired modeling results even when push-pull edits were made arbitrary(for example, Fig. 5.13b), as expected.The second case study involved a push-pull move applied to a hook model with oneGTIP in between (Fig. 5.14). Both the GTIP detection module and Boolean operation baseddecision-making module came into effect. In particular, the method activated for carryingout the GTIP detection was the reverse inference based GTIP detection method.The case study above is relatively simple as there was only one GTIP involved. A muchmore complex push-pull move was thus considered in the third case study, where ten GTIPswere involved, and some of them occurred concurrently (Fig. 5.15). The configuration of thegeometry-topology inconsistencies is complex, and the associated detection and resolutiontasks are challenging. The proposed method can still correctly detect all these GTIPs andsuccessfully resolve the associated geometry-topology inconsistencies.70 Figure 9 Push-pulling the axis support model and the modeling results: (a) a normal push-pull edit; and (b) an arbitrary push-pull edit. (b) (a) Figure 5.13: Push-pulling the axis support model and the modeling results: (a) a nor-mal push-pull edit; and (b) an arbitrary push-pull edit. Figure 11 Push-pulling the hook model and the modeling results. Figure 5.14: Push-pulling the hook model and the modeling results. Figure 13 Push-pulling the motorcycle triple clamp model and the modeling results. Figure 5.15: Push-pulling the motorcycle triple clamp model and the modeling results.71 Figure 17 Modeling results for push-pulling the gear box mount model (circles indicate changed parts). Translate 6 Faces Rotate 4 Faces Translate 4 Faces Translate 1 Face Translate 1 Face Figure 5.16: Push-pulling the gearbox mount model and the modeling results.In the last case study, a more comprehensive case was analyzed. Each of the above threecase studies involved only a single push-pull edit. In this case study, five push-pull editswere performed (Fig. 5.16), containing both the translational push-pull operation type (e.g.,the first push-pull operation) and the rotational push-pull operation type (e.g., the secondpush-pull operation), as well as single-face push-pull operations (e.g., the last push-pulloperation) and multiple-face push-pull operations (e.g., the first push-pull operation). Thiscase study is thus quite comprehensive. Based on the modeling results in Fig. 5.16, as wellas those in Figs. 5.13, 5.14 and 5.15, the proposed method is seen to solve the robustnessissues quite well.5.4 SummaryThe continuity principle proposed to govern the whole process of resolving geometry-topology inconsistencies has been implemented as successive applications of the followingtwo modules: GTIP detection and Boolean-based decision-making. The novel formulationof the continuity criterion as Boolean operations on the model volume can guarantee thatmodeling results are valid and follow a continuous change pattern. In addition, it allowsan easy implementation using existing CAD research and engineering results, as most geo-72metric modeling kernels provide Boolean operation APIs (application program interfaces).This concise, effective formulation is considered as one of the most important contributionsof this thesis.A series of case studies have been conducted to validate the presented methods. Theywere carefully selected so that the respective effectiveness of the two constituent modules(GTIP detection and Boolean-based decision-making) could be validated (through compar-ing with the industrial state-of-the-art), and the effectiveness of the proposed method as awhole could be demonstrated as well.73Chapter 6: Shape-Associativity Inconsistency DetectionThis chapter and the next one deal with shape-associativity inconsistencies. Similar to whatwas done in the previous two chapters, the inconsistencies are to be taken out, and then therelevant information is to be revised. This chapter focuses on the "taken out" problem. Asalready discussed in Section 3.2, this problem is not a single problem but a set of problems,including the problem of characterizing the post-edit model's constraint state, the problem ofdetecting minimal over-constrained parts (if any) in the model, and the problem of detectingmaximal well-constrained parts (if any) in the model.This chapter will present effective methods to solve the problems, based on the existingwitness configuration method. A direct application of the witness configuration methodto this work is, however, insufficient, and significant developments are necessary. In thefollowing, a brief introduction to the witness configuration method is first given, then itslimitations are discussed, and finally the proposed improvements are presented. As we shallsee shortly, the content in this chapter is mathematically heavy. This is because a modelGCS is essentially a system of algebraic equations, and addressing the problems aboveshould be based on effective manipulations of these equations.6.1 The Witness Configuration MethodTo characterize constraint states, the witness configuration method examines how con-straint equations behave under infinitesimal perturbations made to equation variables. LetF (X) = 0 be the constraint equations of a given model GCS, whereX denotes the equationvariables (i.e., the coordinates of the geometric entities in the model geometry). The witness74configuration method applies a small disturbance ∆X to X and examines the response ∆Fof F , which are related by:∆F = J(X) ·∆X +O (‖∆X‖2) (6.1)where J(X) is the Jacobian matrix evaluated at X . The main result of the witness con-figuration method is that if J is evaluated at a carefully selected point called the witnessconfiguration, constraint dependencies (i.e., over-constraint) are described by the linearlydependent rows of the Jacobian matrix, or equivalently by the vectors in the kernel (a.k.a.null space) of JT [36]. Under-constraint is closely related to free perturbations that do notviolate existing constraints, i.e., ∆F = J ·∆X = 0. To be more precise, under-constraintis described by vectors in the kernel of J [35]. A configuration is called a witness config-uration if certain types of constraints in the model GCS have already been satisfied by theconfiguration under perturbation [35]. Satisfying this requirement is not straightforward inthe witness configuration method's original context — geometric constraint solving — butcan be made trivial in this work's context. Due to the prior procedure of model constraintupdate, all the constraints in the updated model GCS agree with the solid model, and thusthe solid model serves as a perfect witness configuration.The formal criteria of under-, well- and over-constraint given by the witness configu-ration method are as follows. A model is over-constrained if Kernel(JT) 6= ∅, whereKernel(·) denotes the kernel of a matrix, which is defined asKernel(JT ) = {x|JTx = 0}.This criterion can be rewritten as:Rank(J)−RowSize(J) < 0 (6.2)A model is under-constrained if Dim (Kernel(J)) > 6, where Dim(·) is an operator get-ting the dimension of a linear space, and the number 6 represents the six rigid-body trans-75formations. This criterion can be rewritten as:Dim (Kernel(J)) = ColumnSize(J)−Rank(J) > 6 (6.3)using the rank-nullity theorem [90]. Then, the criterion for a well-constrained model isgiven as:Rank(J)−RowSize(J) = 0ColumnSize(J)−Rank(J) = 6(6.4)These criteria were accepted once but later proved wrong. The failure is due to theassumption that a well-constrained model admits exactly 6 DOFs, which has been foundnot to be true for many real cases [91]. To address this issue, the most recent version ofthe witness configuration method replaces the fixed number 6 with a variable called thedegree of rigidity [36, 91]. The problem of this improvement is that the notion of degreeof rigidity was introduced in a way as a patch to the original witness configuration method,and no rigorous proof was given to discuss its generality. In fact, these improved criteriahave been found by the author to be ineffective for the 3D variational models considered inthis work, as will be shown by the case studies in Section 6.5.1. This chapter will propose ageneralization of the witness configuration method, with a rigorous proof.Another limitation is that the existing methods [35–38] use greedy methods to detectminimal over-constrained parts and maximal well-constrained parts in a model. However, asis well known, greedy methods could fail to give optimal solutions (and therefore incorrectdetection results). This is an inherent limitation of greedy methods. Refer to Appendix Afor a detailed discussion and examples of this limitation. Instead of improving the greedy-based methods, which may never be perfect, this chapter will present a new formulation ofthe detection problems to attain correct results effectively. It should be noted here that theabove discussion about the witness configuration method's limitations and the discussionpresented in Appendix A are original work.766.2 Proposed Constraint State Characterization MethodThe proposed constraint state characterization method, named the geometric perturbationmethod, consists of four basic steps as shown in Algorithm 6.1.Algorithm 6.1: The Geometric Perturbation MethodAlgorithm : The Geometric Perturbation Method 1. Generate the geometric perturbation matrix 𝐺 2. Calculate the free motion space 𝐾𝑒𝑟𝑛𝑒𝑙(𝐺) 3. Generate the nominal free motion space 𝑁 4. Compare the two spaces 𝐾𝑒𝑟𝑛𝑒𝑙(𝐺) and 𝑁 The geometric perturbation matrix G in Step 1 is a generalization of the Jacobian matrixJ in the original witness configuration method (Eq. 6.1). The space Kernel(G) in Step 2describes the model's free motions, resembling the free perturbations in the original witnessconfiguration method. The nominal free motion space N is a generalization of rigid-bodytransformations (a.k.a. rigid-body motions) in the original witness configuration method. Itwill be proved that a model is well-constrained if and only if Kernel(G) = N . Both mo-tions inN andKernel(G) are expressed in terms of geometric translations and/or rotations,and thus the two spaces are directly comparable. The original witness configuration methodis not under such an advantageous situation.6.2.1 From Parametric Perturbation to Geometric PerturbationThis subsection presents the method of constructing the geometric perturbation matrix. Ageometric motion of a geometric entity consists of two time-varying components: R(t) tospecify the rotational part of the motion and T (t) to describe the translational part. At timet, the geometric entity's position vector p(t) and orientation vector n(t) are expressed as:p(t) = R(t)p(0) + T (t)n(t) = R(t)n(0)(6.5)77Differentiating this equation gives the relationship between the parametric perturbations andgeometric perturbations [92]:δp = δr × p(t) + δtδn = δr × n(t)(6.6)where δr is the vector describing the rotation about the direction δr/‖δr‖ by the angle ‖δr‖,and the same for δt for describing the translation. Denoting p(t) by (px, py, pz)T and n(t)by (nx, ny, nz)T , the cross products δr × p(t) and δr × n(t) in Eq. 6.6 can be rewritten inthe following matrix form:δr × p(t) = −0 −pz pypz 0 −px−py px 0 δr = −Pδrδr × n(t) = −0 −nz nynz 0 −nx−ny nx 0 δr = −Nδr(6.7)Then, Eq. 6.6 can be rewritten as a linear transformation: δpδn = I3×3 −P0 −N δtδr (6.8)This equation describes the parametric-to-geometric conversion for a single geometric en-tity. To attain the conversion for all the geometric entities in the model, we just need to78assemble each entity's conversion matrix diagonally in the following form:δp1δn1...δpmδnm=T1. . .Tmδt1δr1...δtmδrm(6.9)where Ti = I3×3 −Pi0 −Ni. By denoting the transformation matrix in Eq. 6.9 as T andmultiplying it with the Jacobian matrix J in Eq. 6.1, the new matrix G = JT relates anygeometric perturbations (geometric translations and/or rotations) made to the model GCSand the responses. That is, this matrix allows the witness configuration method to applygeometric perturbations directly to a model. The matrix G is referred to as the geometricperturbation matrix hereafter.So far, the first step in algorithm 6.1 to construct the geometric perturbation matrix hasbeen accomplished. With this matrix in place, the second step can also be made available,which is to solve the linear system Gx = 0 using existing algorithms such as QR decompo-sition. The following subsection focuses on the third step of constructing the nominal freemotion space N .6.2.2 From Rigid-Body Motions to Geometry-Invariant MotionsFree motions of a well-constrained 3D variational model contain not only rigid-body mo-tions but also certain non-rigid-body motions. Consider, for example, the well-constrainedmodel in Fig. 6.1a. Rigid-body motions are clearly free motions. Some non-rigid-bodymotions are also applicable. By translating the top and bottom planes and rotating the fourside planes in a way as in Fig. 6.1b, we can attain a motion that is not a rigid-body motionand meanwhile does not violate the model GCS.79 (b) F6 F4 F5 F3 F2 F1 1. Distance(F1,F3)=1 2. Distance(F2,F4)=1 3. Distance(F5,F6)=1 4. Perpendicular(F1,F5) 5. Perpendicular(F1,F2) 6. Perpendicular(F2,F5) (a) Figure 6.1: Examples of a well-constrained variational B-rep model (a), and a non-rigid-body free motion (b).Apparently, an effective characterization of constraint states cannot be made possiblewithout a systematic study of the non-rigid-body free motions as stated above. A well-constrained model has a finite number of solutions or feasible geometric realizations (Def-inition 5, Section 3.2.2). Since these feasible realizations are finite, one feasible realizationcannot be continuously deformed to another without violating the existing constraints in themodel. That being said, no free motions of a well-constrained GCS will alter the model'sshape. It is proven in Proposition 6.1 that there are in total three types of geometric motionsthat preserve model shape: (1) rigid-body motions; (2) geometry-invariant motions; and (3)composites of them. The geometry-invariant motions for a geometric entity are motionsthat leave the entity invariant (e.g., translating a plane along any direction in the plane).Fig. 6.2 illustrates the geometry-invariant motions of commonly used geometric entities inCAD, including lines, planes, cylinders, spheres, cones, and tori. With Proposition 6.1, thesolution-based characterization of a well-constrained model is translated to the conditionson the free motions of the model.Proposition 6.1. Free motions of a well-constrained model are either rigid-body motionsor geometry-invariant motions, or composites of them.Proof. See Appendix B.80Geometric entities Invariant motions Illustrations Line 1. Translations along the line 2. Rotation about the line Plane 1. Translations in the plane 2. Rotations about the normal Cylinder 1. Translations along the axis 2. Rotations about the axis Sphere 1. Any rotations Cone 1. Rotations about the axis Torus 1. Rotations about the axis Figure 6.2: Illustrations of geometry-invariant motions.Based on the discussion above, a well-constrained model should not have any free mo-tions besides rigid-body motions, geometry-invariant motions, and their composites. Thespace consisting of these motions are referred to as the nominal free motion space. To geta mathematical representation of this space, we first need to vectorize the basis motions ofthe rigid-body motion space and geometry-invariant motion space and then to use the Imageoperator to get the space spanned by these basis motion vectors (linear combinations of thebasis motion vectors represent the composite motions). The Image operator is defined as[90]:N = Image(B) = {Bx|x ∈ Rn} (6.10)where B = (b1, b2, · · · , bn) denotes the basis vectors, and N represents the nominal freemotion space. The next shows how to attain B.81The rigid-body motions have six motion bases: three axial translations and three axialrotations. The translation along a coordinate axis, e.g., the x-axis, is given by:(1, 0, 0︸ ︷︷ ︸δt1, 0, 0, 0︸ ︷︷ ︸δr1· · · 1, 0, 0︸ ︷︷ ︸δtm, 0, 0, 0︸ ︷︷ ︸δrm)T (6.11)where m denotes the number of geometric entities. The representation of axial rotations issimilar. For example, the rotation about the x-axis is:(0, 0, 0︸ ︷︷ ︸δt1, 1, 0, 0︸ ︷︷ ︸δr1· · · 0, 0, 0︸ ︷︷ ︸δtm, 1, 0, 0︸ ︷︷ ︸δrm)T (6.12)The geometry-invariant motions are translational/rotational motions along/about some spe-cific vectors (Fig. 6.2). Let the vector be v = (vx, vy, vz)T . A translational geometry-invariant motion along this vector for the k-th geometric entity is:(0, 0, 0︸ ︷︷ ︸δt1, 0, 0, 0︸ ︷︷ ︸δr1· · · vx, vy, vz︸ ︷︷ ︸δtk, 0, 0, 0︸ ︷︷ ︸δrk· · · 0, 0, 0︸ ︷︷ ︸δtm, 0, 0, 0︸ ︷︷ ︸δrm)T (6.13)and the same for a rotational geometry-invariant motion about the same vector:(0, 0, 0︸ ︷︷ ︸δt1, 0, 0, 0︸ ︷︷ ︸δr1· · · 0, 0, 0︸ ︷︷ ︸δtk, vx, vy, vz︸ ︷︷ ︸δrk· · · 0, 0, 0︸ ︷︷ ︸δtm, 0, 0, 0︸ ︷︷ ︸δrm)T (6.14)The vectors in (6.11), (6.12), (6.13), and (6.14) establish a set of nominal free motion space.6.2.3 Proposed Criteria to Characterize Constraint StatesWith the free motion space Kernel(G) and nominal free motion space N = Image(B)in place, the last step in Algorithm 6.1 can be carried out, and the criteria to characterizeconstraint states can be derived. This is to be done by comparing the two spacesKernel(G)and Image(B). Noticing that the space of free motions always includes the space of rigid-body and geometry-invariant motions, comparing the two spaces is equivalent to comparing82their dimensions. Then, the criterion for well-constraint is:Dim(Kernel(G))−Dim(Image(B)) = 0⇔ColumnSize(G)−Rank(G)−Rank(B) = 0(6.15)where Dim(·) gets the dimension of a linear space. In the above equations, the rank-nullitytheorem was used [90]. If the above equations do not hold, i.e.,ColumnSize(G)−Rank(G)−Rank(B) > 0 (6.16)the model is under-constrained. In the above discussion, it is assumed that there are no con-straint dependencies. If such dependencies occur, the perturbation matrix will have linearlydependent rows, i.e., Kernel(JT ) 6= ∅, which is equivalent to:Rank(G)−RowSize(G) < 0 (6.17)The three criteria in (6.15), (6.16), and (6.17) yield a generalization of those provided in theoriginal witness configuration method. They can effectively characterize constraint states,with a proof.6.3 Minimal Over-Constraint DetectionGiven a model, whether it is well-constrained or not can be determined via the criteriain (6.15), (6.16), and (6.17). If the characterization result says that the model is over-constrained, the task of detecting the minimal over-constrained parts is to be activated. Anover-constrained part can take the form of a group of constraints having dependencies ora group of geometric entities whose associated constraints have dependencies. These twoforms are equivalent, and this work defines an over-constrained part as a group of depen-dent constraints. An over-constrained part is minimal if its size is minimized, as shown in83 F4 F3 F5 F2 F1 F6 C1. Distance(F1,F3)=1 C2. Distance(F2,F4)=1 C3. Distance(F5,F6)=1 C4. Perpendicular(F1,F5) C5. Perpendicular(F1,F4) C6. Perpendicular(F4,F5) C7. Perpendicular(F2,F3) C8. Perpendicular(F2,F3) Minimal Over-Constrained Parts: {C1,C2,C5,C7}, {C7,C8} Over-Constrained Parts: {C1,C2,C5,C7}, {C1,C2,C5,C8} Figure 6.3: Example of minimal over-constrained parts.Fig. 6.3. Such a part only consists of constraints relevant to the dependency; no irrelevantconstraints will be included.As already noted, constraint dependencies yield linearly dependent rows in the geomet-ric perturbation matrix. To be precise, a vector x ∈ Kernel(GT ) represents a dependencygroup (not necessarily minimal), and the non-zero elements of this vector indicate the con-straints involved in this dependency group. A dependency group being minimal is thus tosay that the vector x has the minimal number of non-zero elements, which can be modeledas:minx‖x‖0 s.t. GTx = 0, x 6= 0 (6.18)where ‖·‖0 is the `0 norm whose mathematical meaning is to count non-zero elements in avector. A minimal dependency group should be irreducible to smaller dependency groups.In other words, all dependency vectors {xi}ni=1 should be linearly independent. Supposewe have got the first k < n dependency vectors {xi}ki=1. The requirement that the nextdependency vector is linearly independent with {xi}ki=1 can be modeled as:minxk+1‖xk+1‖0 s.t. GTxk+1 = 0, xk+1 /∈ Span (x1 . . . xk) (6.19)The above modeling suggests that dependency vectors are to be attained sequentially. Solv-ing the optimization problem in (6.19) is not trivial due to its non-convexity. In the fol-lowing, this optimization problem will be reformulated to a typical sparse recovery (a.k.a.compressive sensing) problem, through a series of mathematical manipulations. In the re-84formulation, it is expected that the problem will become a tractable optimization problemusing existing optimization techniques. The reformulation is only of mathematical interestand does not change the essence of the modeling expressed in (6.19) or provide new insightsinto the problem.Divide the basis of Kernel(GT ) into two parts:Kernel(GT ) =(A︷ ︸︸ ︷x1 . . . xkB︷ ︸︸ ︷A′s orthogonal complement)(6.20)where x1 . . . xk are the first k dependency vectors. Then, any vector x ∈ GT can be rep-resented as a linear combination of the column vectors of A and B, denoted as Ay + Bz,where y, z are coefficient vectors. The (k + 1)-th dependency vector thus takes the form ofxk+1 = Ay + Bz with the constraint z 6= 0. Here, the constraint xk+1 /∈ Span (x1 . . . xk)is translated to z 6= 0. This constraint can be further translated to a condition on the depen-dency vector xk+1, as follows. The equation xk+1 = Ay +Bz can be expressed in terms ofthe solution to the following optimization problem:miny,z‖xk+1 − (A B)yz ‖2 (6.21)The solution to this optimization problem is (Chapter 4, [90]):(y z)T = ((A B)T (A B))−1(A B)Txk+1 (6.22)z can then be expressed as:z = (0 I)(y z)T = (0 I)((A B)T (A B))−1(A B)Txk+1 (6.23)where I is an identity matrix whose dimension is the same as the size of B's columns.Simplify the notations in Eq. 6.23 to z = Cxk+1, and constrain z to lie on a unit sphere in85order to avoid a vanished z. The optimization problem (6.19) is then transformed into:minxk+1‖xk+1‖0 s.t. GTxk+1 = 0, ‖Cxk+1‖2 = 1 (6.24)which is a typical sparse recovery problem to be solved via the method presented by Osherand Yin [93].With the formulation (6.24) in place, a sequential method of attaining minimal over-constrained parts can be made available. The overall method is summarized in Algo-rithm 6.2. The algorithm sequentially attains minimal dependency groups by first solvingthe optimization problem in (6.24) and then getting non-zero elements in the solved xi andfinally mapping these elements to their corresponding constraints.Algorithm 6.2: Minimal Over-Constraint Detection Algorithm 1: extractMinOverConstraint(𝐽) Input: 𝐺 − the perturbation matrix Output: 𝐷 − a set of minimal over-constrained parts 1. 𝐷 ← ∅ 2. 𝑁 ← Dim(𝐾𝑒𝑟𝑛𝑒𝑙(𝐺𝑇)) // number of dependency groups 3. for 𝑖 ← 1 to 𝑁 do 4. 𝑥𝑖 ← Solve the optimization problem in Eq. 6.24 5. 𝑖𝑑𝑥 ← IndexOfNonZeroElements(𝑥𝑖) 6. 𝐶 ← MapToConstriants(𝑖𝑑𝑥) 7. 𝐷 ← 𝐷 ∪ {𝐶} 8. end for 9. Return 𝐷 6.4 Maximal Well-Constraint DetectionA well-constrained part of a model refers to a subset of the model geometry whose inducedsubsystem in the model GCS is well-constrained. A part's induced subsystem is the subsetof the constraints in the model GCS that are defined within the part. A well-constrained partP is maximal if there is no another well-constrained part P ′ such that P ⊂ P ′, as shown inFig. 6.4.86 F4 F3 F5 F2 F1 F6 C1. Distance(F1,F3)=1 C2. Distance(F2,F4)=1 C3. Distance(F5,F6)=1 C4. Perpendicular(F1,F5) A Maximal Well-Constrained Part: {F1,F3,F5,F6} Sample Well-Constrained Parts: {F1,F3}, {F5,F6} Figure 6.4: Example of maximal well-constrained parts.As already noted in Section 6.2, vectors in the space Kernel(G) describe the model'sfree motions and, for a well-constrained part, all of its free motions are nominal free mo-tions. Formally, let f ∈ Kernel(G) denote a free motion, I the index set of the geometricentities in a part of interest, and δi(f) a function getting the component in f correspondingto the i-th geometric entity. The part represented by I is well-constrained if the motions(δI1(f), δI2(f), · · · , δIm(f)), ∀f ∈ Kernel(G) are all nominal free motions. Whether amotion (δI1(f), δI2(f), · · · , δIm(f)) is a nominal free motion or not can be determined bychecking if it can be expressed as a linear combination of the basis vectors of the nominalfree motion space. Let B represent a matrix whose columns are these basis vectors. Thepart is well-constrained if the following equations are solvable for any f ∈ Kernel(G):δi(Bx)− δi(f) = 0, i ∈ I (6.25)where x is the variable and represents the linear combination coefficients.If the part is maximal, any geometric entity k /∈ I should have the following property:there exists a free motion f ∈ Kernel(G) such that (δI1(f), · · · , δk(f), . . . , δIm(f)) is nota nominal free motion. To state mathematically, the following equations should have nosolution for a certain f ∈ Kernel(G):δi(Bx)− δi(f) = 0, i ∈ Iδk(Bx)− δk(f) = 0(6.26)87Or equivalently, any solution to the part δi(Bx) − δi(f) = 0, i ∈ I leads to the inequalityδk(Bx)− δk(f) 6= 0. This property is the key to attaining maximal well-constrained parts.Suppose we want to find the largest well-constrained part in the model. This part havingthe maximal size means that, in the following linear system, the number of equations thatcan be satisfied is maximal:Bx− f = 0, ∀f ∈ Kernel(G) (6.27)Eq. 6.27 can be rewritten in the following matrix form:BX − F = 0 (6.28)where F is a matrix whose columns are the basis vectors of Kernel(G). Maximizing thenumber of satisfied equations in (6.28) is equivalent to minimizing the number of unsatisfiedequations, that is:minXnumber of non-zero rows of BX − F (6.29)Mathematically, whether a row of a matrix is non-zero or not can be checked if its `2norm is zero. Let ri denote the i-th row ofBX−F . ri is a non-zero row iff ‖ri‖2=√rirTi 6=0. If we collect the rows' `2 norms into a vector v = (‖r1‖2, ‖r2‖2, · · · , ‖rm‖2), then thenumber of non-zero rows of BX − F is the `0 norm of v. The above sequential applicationof two norms is called the mixed `2/`0 norm of BX − F , denoted as ‖BX − F‖2,0. Then,the problem (6.29) can be modeled as:minX‖BX − F‖2,0 (6.30)The essential part of this optimization problem is the `0 norm. Then (6.30) is, again, a sparserecovery problem. Let X∗ be the minimizer of the above optimization problem; the zerorows of the matrix BX∗ − F correspond to the largest well-constrained part in the model.88The second largest well-constrained part (and so forth) can be attained similarly. Afterthe largest well-constrained part is attained, we can focus on the remaining geometric enti-ties in the model, and then update the matrices B and F accordingly, and finally solve theoptimization problem (6.30) again. The update of B and F can easily be done by removingthe rows corresponding to the geometric entities in the known largest well-constrained part.Apparently, by repeating the above updating and solving procedures, all the maximal well-constrained parts can be attained sequentially, from the largest to the smallest. Algorithm 6.3shows the procedures for doing so. In particular, Line 4 represents the update procedure forB and F as described above; Lines 7 and 8 exclude the detected well-constrained part fromthe model and store it as a new maximal well-constrained part.Algorithm 6.3: Maximal Well-Constraint Detection Algorithm 1: extractMaxOverConstraint(!) Input: ", $ − the nominal free motion basis and free motion basis Output: & − a set of maximal well-constrained parts 1. & ← ∅ // for storing the maximal well-constrained parts 2. ) ← GetAllGeometricEntities() 3. while |)| ≠ 0 do 4. Update " and $ 5. <∗ ← Solve the optimization problem (6.30) 6. > ← IndexOfZeroRows("<∗ − $) 7. )? ← {)(A)| A ∈ >} , ) ← ) −)? 8. & ← & ∪ {)?} 9. end while 10. Return & 6.5 Case StudiesThis section shows the effectiveness of the methods presented in this chapter. For theproposed constraint state characterization criteria, their effectiveness will be demonstratedthrough comparing with the original witness configuration method. The effectiveness of theproposed minimal over-constraint detection method and maximal well-constraint detection89 (a) (b) F3 F4 F2 F1 L1 L2 1. Distance(F1,F3)=1 2. Distance(F2,F4)=1 3. Perpendicular(F1,F2) 1.Distance(L1,L2)=1 Figure 3 Comparison examples: (a) the plane example; and (b) the 3D line example. Figure 6.5: Comparison examples: (a) the plane example; and (b) the 3D line example.method is to be shown by three case studies. In particular, the last case study is based on areal-world engine bracket model.6.5.1 Comparison ExamplesCase description. The comparisons of the proposed constraint state characterization crite-ria with those in the original witness configuration method [35, 36] were conducted usingthe two examples shown in Fig. 6.5. The first example (Fig. 6.5a) involves four planes,and the constraints are distance and perpendicularity between them. The second example(Fig. 6.5b) is based on two 3D lines, and the (only) constraint is the distance between them.These two configurations are widely used as constituent features of mechanical parts. Bothexamples are well-constrained, and thus can be used to test if the proposed method andoriginal witness configuration method can correctly characterize the constraint states.Discussion. The comparison results are given in Table 6.1. The columns of the table de-scribe the characterization results given by individual methods. The column of each methodis subdivided into three sub-columns that specify the respective methods' two importantintermediate results and correctness of the final characterization result. The intermediateresults are the calculated DOFs (the Real DOF columns) and the expected DOFs (the Nom-inal DOF columns). The values in the Nominal DOF columns were calculated as follows:they are always 6 for witness configuration method I [35]; they are the degree of rigidity forwitness configuration method II [36], which is an improved version of witness configura-90tion method I; and they are the dimension of the nominal free motion space for the proposedmethod. The rows of the table show the examples to which the above results refer. As can beseen from the table, the first example was used twice with different representation schemes1.The purpose is to show that the effectiveness of witness configuration method II is affectedby the representation scheme used, which may be the reason for the failures. Witness Method I Witness Method II The Proposed Method Real DOF Nominal DOF Matched? Real DOF Nominal DOF Matched? Real DOF Nominal DOF Matched? The plane example (Representation #1) 5 6 û 5 5 ü 17 17 ü The plane example (Representation #2) 11 6 û 11 6 û 17 17 ü The line example 7 6 û 7 6 û 8 8 ü Table 6.1: Comparison results for the plane and line examples.According to the comparison results, the proposed method is the most effective, fol-lowed by witness configuration method II and then witness configuration method I, as ex-pected. The values in the Real DOF columns show that the DOFs of a well-constrainedmodel vary with the geometric configuration and representation scheme. This requires con-straint state characterization criteria to be able to output an adaptive nominal DOF. This isthe reason that witness configuration method I failed to characterize the constraint statesof the two examples as it uses a fixed nominal DOF. The witness configuration method IIadvanced the witness configuration method by enabling the nominal DOF to be adaptiveto the geometric configuration. This method, however, only works for a certain type ofrepresentation scheme, as reflected by the results in the first two rows of Table 6.1. Theproposed criteria further advanced the witness configuration method, making the nominalDOF adaptive to both the geometric configuration and representation scheme.1Representation #1 defines a plane with the tuple (a, b, c, d) and the additional constraint a2 + b2 + c2 = 1(the plane equation is ax+ by+ cz + d = 0). Representation #2 describes a plane with a point p ∈ R3 on theplane and the normal n ∈ S2 of the plane.916.5.2 Validation Case StudiesCase description. Three case studies have been conducted. The first case study consideredediting a hexahedron model (Fig. 6.6a), which altered the model's constraint state fromwell-constrained to over-constrained (Fig. 6.6b). The second case study involved editing aslot model (Fig. 6.8a), which changed the model's constraint state from well-constrainedto under-constrained (Fig. 6.8b). To be more specific, the push-pull edit moved face F9towards the right, removing face F6, extending face F8, and shrinking face F2. These twocase studies are intended to show the respective effectiveness of the two constituent modulesof the shape-associativity inconsistency detection method. The third case study analyzed acomprehensive situation where the updated model constraints had under-, well-, and over-constrained parts. It is used to show the effectiveness of the proposed method as a whole.This case study was based on a real-world mechanical part in which the source model isa common bracket part, and the target one is a specialized bracket part used in jet engines(Fig. 6.10a). (Blends/chamfers in the model were ignored as they are secondary features.)The many constraints, equations, and variables involved in this case (Fig. 6.10b) make themodel hard to reason manually; and it is the purpose of this case study to show how thepresented methods can effectively automate this process.Discussion. The first case study was purposely chosen to contain no under-constraintso that the maximal over-constraint detection becomes dominant in the shape-associativityinconsistency detection. Fig. 6.7 shows the dependency vector given by applying Algo-rithm 6.2 to this case. Recall that the positions of the non-zero elements in a dependencyvector indicate the constraints involved in the dependency group. The specific dependencygroup for this case is thus: {C5,C6,C7}. Attributing to the small number of constraints/e-quations involved in this case, correctness of the result can be readily verified. ConstraintsC5, C6, and C7 form an over-constrained part because the parallel constraint C6 transitivelypasses the perpendicular relation (resulting from constraint C5) from the plane pair F4, F5to the plane pair F2, F5, which has, however, already been specified by constraint C7.92 Model Geometry Indices Model GCS Original Constraints Updated Constraints Equations C1. Distance(F1,F3)=1 C2. Distance(F5,F6)=1 C3. Perpendicular(F1,F5) C4. Perpendicular(F1,F4) C5. Perpendicular(F4,F5) C6. Angle(F2,F4)=120° C7. Angle(F2,F5)=60° C8. Length(E1)=1 Distance(F1,F3)=1 Distance(F5,F6)=1 Perpendicular(F1,F5) Perpendicular(F1,F4) Perpendicular(F4,F5) Parallel(F2,F4) Perpendicular(F2,F5) Length(E1)=1 1-4 5-8 9 10 11 12-14 15 16 F4 F3 F5 F2 F6 F1 E1 (a) (b) Figure 6.6: Direct modeling of a hexahedron model (a), and model constraint update(b). ⏞C5 ⏞C7 16 columns ⏞C6Figure 6.7: Dependency vector of the hexahedron case (white elements indicate thezeros and blue ones the non-zeros).In the second case study, there is no over-constraint, and thus detecting maximal well-constrained parts becomes dominant in the shape-associativity inconsistency detection. Thisallows us to evaluate exclusively Algorithm 6.3. Fig. 6.9 shows the application resultsfor this case. The model was divided into two parts: one consisting of planes F1-F5, F8,and F10, and the other having a single plane F7. Like in the first case, the number ofconstraints/equations involved in this case is still small, and the correctness of the aboveresult can be verified manually. That is, the constraints C1-C3, C5-C7 comprise a variantof a well-constrained cuboid; constraint C10 attaches the plane F8 to the cuboid variant in93 Model Geometry Indices Model GCS Original Constraints Updated Constraints Equations C1. Distance(F1,F3)=10 C2. Distance(F2,F4)=15 C3. Distance(F5,F10)=10 C4. Distance(F6,F10)=10 C5. Perpendicular(F1,F2) C6. Perpendicular(F1,F10) C7. Perpendicular(F2,F10) C8. Distance(F7,F9)=5 C9. Distance(F2,F9)=5 C10. Distance(F5,F8)=5 Distance(F1,F3)=10 Distance(F2,F4)=15 Distance(F5,F10)=10 Removed Perpendicular(F1,F2) Perpendicular(F1,F10) Perpendicular(F2,F10) Removed Removed Distance(F5,F8)=5 1-4 5-8 9-12 N/A 13 14 15 N/A N/A 16-19 F4 F10 F1 F3 F6 F5 F2 F7 F8 F9 (a) (b) Figure 6.8: Direct modeling of a slot model (a), and model constraint update (b). P1={F1-F5,F8,F10} P2={F7} P1 P2 Figure 6.9: Results of maximal well-constraint detection for the slot case.a fully constrained manner; then the planes F1-F5, F8, and F10 form a well-constrainedpart. There is no constraint between the two parts, and thus plane F7 is free and forms awell-constrained part by itself. Also, these two parts are clearly of maximal size.The constraint systems in the first and second case studies are manually manageableand thus not able to fully show the effectiveness of the proposed methods. For this rea-son, a third case study was conducted. It analyzed a real-world engine bracket model with97 equations (Fig. 6.10b). Some of the equations are redundant, and all the model con-straints are insufficient to restrict the model completely. It is hard to figure out manually94the under-constrained and over-constrained parts in such a large system. This case is thus agood candidate to show that the proposed methods can deal effectively with such complexsituations.Fig. 6.11 shows the two detected dependency vectors, which represent the following twodependency groups: {C9,C16,C18,C20} and {C9,C25,C28,C29}. With these dependencygroups in place, over-constraint reasoning becomes trivial. Take the first dependency groupas an example. Cylinder F19 is parallel with plane F13 with constraint C16; plane F13 isalso parallel to plane F14 with constraint C9; plane F14 is further parallel to plane F20 withconstraint C20; therefore, cylinder F19 is parallel to plane F20; but the remaining constraintC18 specifies the same parallelism between cylinder F19 and plane F20. As can be seenfrom the above reasoning, removing any constraint in a dependency group can break thecyclical dependency in the group and then resolve the over-constraint. Thus, such groupscan lead to two important benefits: (1) exclude invalid resolution options, i.e., constraintsoutside the groups will not be mistakenly removed; and (2) prepare all valid resolutionoptions, i.e., any constraints in the groups are applicable options.Fig. 6.12 shows the eight detected maximal well-constrained parts. With these partsin place, DOF reasoning can be made trivial. One just needs to focus on the constraintsbridging any two maximal well-constrained parts while ignoring any constraints within theparts. The bridging constraints for this case are shown in Fig 6.13. Consider, for example,the two parts P2 and P8. There is only one angle constraint between them, leading totwo rotational DOFs and three additional translational DOFs. With these DOFs, attainingconstraints that can restrict them correctly becomes easy. Or we can attain such constraintsin an automatic way: first generate all possible bridging constraints between two maximalwell-constrained parts of interest, then remove those leading to over-constraint with theexisting bridging constraints between the two parts, eventually the remaining constraintsare applicable resolution options. This automatic method is the very method to be used inthe next chapter to generate resolution suggestions for addressing under-constraint.95 (a) (b) F28 F17 F18 F12 F2 F8 F4 F6 F10 Model Geometry Indices Updated Model GCS Constraints Equations Constraints Equations C1. Dis(F2,F3)=10 C2. Dis(F4,F5)=10 C3. Dis(F6,F7)=10 C4. Dis(F8,F9)=10 C5. Dis(F10,F11)=10 C6. Ang(F1,F4)=30° C7. Ang(F1,F8)=150° C8. Dis(F1,F12)=180 C9. Dis(F13,F14)=80 C10. Ang(F3,F6)=160° C11. Ang(F6,F11)=160° C12. Per(F1,F3) C13. Per(F1,F2) C14. Per(F2,F3) C15. Dis(F19,F6)=10.62 C16. Dis(F19,F13)=57.96 C17. Coaxial(F19,F21) C18. Tan(F19,F20) C19. Tan(F19,F23) C20. Par(F20,F14) 1-4 5-8 9-12 13-16 17-20 21 22 23-26 27-30 31 32 33 34 35 36-37 38-39 40-45 46-47 48-49 50-52 C21. Ang(F23,F13)=60° C22. Ang(F4,F22)=30° C23. Dis(F22,F24)=10 C24. Dis(F28,F6)=10.62 C25. Dis(F28,F13)=57.96 C26. Coaxial(F28,F26) C27. Tan(F28,F29) C28. Tan(F28,F25) C29. Par(F25,F14) C30. Ang(F29,F13)=60° C31. Ang(F8,F30)=30° C32. Dis(F27,F30)=10 C33. Dis(F15,F1)=10 C34. Dis(F15,F13)=20 C35. Dis(F16,F1)=10 C36. Dis(F16,F14)=20 C37. Dis(F17,F12)=10 C38. Dis(F17,F13)=20 C39. Dis(F18,F12)=10 C40. Dis(F18,F14)=20 53 54 55-58 59-60 61-62 63-68 69-70 71-72 73-75 76 77 78-81 82-83 84-85 86-87 88-89 90-91 92-93 94-95 96-97 F30 F29 F22 F19 F20 F21 F23 F24 F25 F26 F27 F1 F14 F15 F16 F3 F5 F7 F9 F11 F13 Figure 6.10: Direct modeling of an engine bracket model (a), and model constraintupdate (b) (Dis: Distance, Ang: Angle, Per: Perpendicular, Par: Parallel, Tan:Tangent). ⏞C29 ⏞C28 ⏞C25 ⏞C20 ⏞C16 ⏞C9 ⏞C18 27-th column 97 columns ⋯ ⋯ 75-th column Figure 6.11: Truncated dependency vectors of the bracket case (truncated parts arezeros; white elements indicate the zeros and blue ones the non-zeros).96 P3 P1={F1,F2,F3,F12-F18,F20,F25} P2={F6,F7,F19,F21,F26,F28} P3={F23,F29} P4={F22,F24} P5={F27,F30} P6={F4,F5} P7={F8,F9} P8={F10,F11} P8 P7 P65 P5 P4 P2 P1 Figure 6.12: Results of maximal well-constraint detection for the bracket case. P8 P3 P7 P65 00 P1 P2 P4 P5 C10,C16,C18,C25,C28 C7 C6 00 C31 C19,C27 C22 C11 C21,C30 Figure 6.13: Bridging constraints (in rectangles) of the bracket case.976.6 SummaryEffective detection of shape-associativity inconsistencies is the basis of achieving effec-tive resolution of the inconsistencies. Shape-associativity inconsistency detection consistsof three basic problems: constraint state characterization, minimal over-constraint detec-tion, and maximal well-constraint detection (equivalent to minimal under-constraint detec-tion). This chapter addressed these problems by proposing a geometric perturbation method,which generalized the existing witness configuration method, to effectively characterizeconstraint states and two novel, precise formulations of the over-constraint detection andwell-constraint detection problems.The effectiveness of the proposed geometric perturbation method has been demonstratedthrough comparisons with the original witness configuration method, and the effectivenessof the minimal under-constraint detection method and maximal well-constraint detectionmethod has been shown using two case studies, respectively. Another comprehensive casestudy based on a real-world part model has also been conducted to show how the proposedmethods can effectively deal with large, complex models.98Chapter 7: Shape-Associativity Inconsistency ResolutionThis chapter deals with the other problem in addressing shape-associativity inconsistencies:revise the constraint information relevant to the "taken out" inconsistencies. The majorchallenge here is to make decisions about which constraints to add or remove in order toresolve the inconsistencies. The essential part of the decision-making is to avoid invalidresolution options and prioritize valid resolution options.The structure of this chapter is organized as follows. A resolution framework is firstgiven in Section 7.1; then a novel constraint prioritization scheme is presented in Sec-tion 7.2, based on which the decision-making methods necessary to implement the frame-work are described in the following two sections 7.3 and 7.4; case studies for validating themethods are given in the last section.7.1 Resolution FrameworkIn the presence of shape-associativity inconsistencies, the computer may assist the resolu-tion process at four levels:1. Notify the user about shape-associativity inconsistencies in an edited model and leavethe inconsistency reasoning and resolution to the user.2. Assist the user to reason about the shape-associativity inconsistencies and to avoidinvalid resolution options.3. Assist the user to reason about the shape-associativity inconsistencies and provide aguided choice among valid resolution options through an option prioritization process.4. Resolve the shape-associativity inconsistencies automatically.99The first three levels may be seen as computer-aided inconsistency resolution, while thelast level may be called computer-automated inconsistency resolution. For the first level,the user takes care of all the geometric reasoning needed to make decisions as well as theconsequence of the decisions. The second level provides automatic geometric reasoning ofthe inconsistencies and excludes resolution options leading to invalid modeling results; theuser explores the left valid resolution options manually. The third level provides not onlyautomatic geometric reasoning but also a prioritization of the valid resolution options so asto direct the user in exploring the available options. The last level works without humanintervention and always gives results in line with the design intent. This is the ultimate goalfor any inconsistency resolution problem. Nevertheless, design intent issues involved in theresolution process is too complicated to infer satisfactorily by the computer [78, 81], andthus the assistance at this level may not be possible at present.The assistance at the second level can be translated to well-defined problems, as whathas been described in Chapter 6, while that at the fourth level is quite ill-defined due to thecomplexity of design intent. The assistance at the third level is somewhere in between: if theprioritization does not work at all, it degenerates to the second level as the computer doesnot give any effective direction; if the prioritization works perfectly (which is not likely tohappen), it upgrades to the fourth level as the top option in the prioritization is always thechoice. This chapter presents a resolution system at the third level.The workflow of the proposed resolution system is shown in Fig. 7.1. It begins with awell-constrained model and a direct edit applied to it, then performs GCS update accordingto the new model shape, then sends the updated model to an analyzer (the modules in dia-mond shape) to evaluate its constraint state. If the model is still well-constrained, nothingfurther needs to be done; if not, the analyzer directs the workflow to different inconsistencyresolution branches. In both branches, it first takes out information inconsistencies (the twodetection modules) and then, based on the detection results, generates and prioritizes validresolution options (the two prioritization modules), then presents the prioritized options to100Start Direct EditsModel Constraint UpdateWell-Constrained?Generate Options & Make DecisionsOver-Constrained?Generate Options & Make DecisionsEndYESNONOYESMinimal Over-Constraint DetectionMaximal Well-Constraint DetectionUser DictationUser DictationStart Direct EditGCS UpdateWell-Constrained?Over-Constrained? EndYESNONOYESMinimal Over-Constraint DetectionMaximal Well-Constraint DetectionDecision-MakingResolution Option Generation & PrioritizationDecision-MakingResolution Option Generation & PrioritizationFigure 7.1: Workflow of shape-associativity inconsistency resolution.the user for decisions. The model after resolution is sent again to the analyzer for makingsure that the model has become well-constrained. This last procedure is necessary becausethe user can do anything beyond what is suggested.Most modules in Fig. 7.1 have been made available in previous chapters. The missingparts are the Resolution option Generation & Prioritization modules. As the name indi-cates, both modules generate a list of constraint recommendations (valid resolution options)and present them to the user incrementally or sequentially so that the user can drive theresolution process easily. If the user chooses not to dictate the resolution process, the toprecommendation in the list will be chosen by the computer. The performance of the recom-mendation list clearly relies on the quality of the prioritization of candidate constraints. Inthe following, a novel prioritization scheme is to be presented, of which the main featureis to allow a resolution option leading to a smaller model variation under parametric editsto be ranked first. Based on this prioritization scheme, effective algorithms for resolvingover-constraint and under-constraint are then proposed.1017.2 Constraint PrioritizationConstraint prioritization is to attain a permutation of given constraints in order to put themin a certain order. The key step to carry out the permutation is a comparison operation thataccepts two constraints as arguments and determines which of them should occur first in thefinal permutation. This section is devoted to such a comparison operation or, more formally,the prioritization criterion.Existing studies [72–75] have shown that certain types of constraints could carry moreengineering knowledge and occur more frequently than others and that a type-based priori-tization could be effective in some scenarios. Following them, the type-based prioritizationis also incorporated into the proposed constraint prioritization scheme, which is shown inTable 7.11, an adaptation of the existing work [74]. This table only gives a rough, quali-tative prioritization of constraints, and its limitations are obvious. If we want to comparetwo constraints with the same type, this table is clearly insufficient, giving rise to the needof quantitatively distinguishing constraints. This is the role played by the following fineprioritization scheme.Observe that parameter changes made to different constraints in a model often yielddifferent degrees of changes made to the model shape, which can be understood with thehelp of the following formulation. Let the model shape be represented by S(p1, · · · , pn),where p1, · · · , pn are constraint parameters, and assume that there is a one-to-one map-ping between the parameters and constraints for simplifying the discussion. Two parame-ter changes δpi, δpj will yield two model shape changes represented by ∆Si, ∆Sj , where∆Si = S(p1, · · · , pi+δpi, · · · pn)−S(p1, · · · , pi, · · · pn), and the same for ∆Sj . ∆Si/δpiand ∆Sj/δpj are generally not equal, and the constraint corresponding to the larger one hasmore impact on the model shape than the other.1This table does not include the precedence for a compound constraint. A compound constraint's prece-dence is defined as the highest precedence of its constituent constraints. For example, a tangent constraintbetween a plan and a cylinder has two constituent constraints: perpendicular directions and distance betweenpositions. Its precedence is then the higher one of these two, which in this case are both 1.102 Geometric Constraint Precedence (1: high, 5: low) Entities Type Face Face Parallel/perpendicular directions, Distance between positions, Equal size parameters 1 General angle between directions 2 Face Edge Parallel/perpendicular directions, Distance between positions 2 General angle between directions 4 Face Vertex Distance between positions 5 Edge Edge Equal angle/length parameters, Parallel/perpendicular directions, Distance between positions 3 General angle between directions 5 Edge Vertex Distance between positions 5 Vertex Vertex Distance between positions 5 Table 7.1: Rough prioritization based on constraint type.For a constraint with a high ∆Si/δpi, a small parameter change made to it will resultin a large change on the model shape, which may lead to a dramatic, unpredictable shapechange and a large deviation from the likely original design intent. A model under such asituation (i.e., with high sensitivity) is said to have a poor constraining scheme [81]. Becauseof these, the rate of model shape change is chosen to quantify a constraints impact on themodel shape. With this quantification, it is expected that resolution options leading to amodel with the least change rate will be chosen. Then the least model variations could beexpected for later parametric edits.For those familiar with sensitivity analysis, they will find that the above notion of modelshape change rate is somewhat similar to it. We can consider the proposed notion as adap-tation of sensitivity analysis to constraint prioritization. To the author's knowledge, noprevious research studies on constraint prioritization have introduced this notion. It should,103however, be noted here that the notion captures the local aspects of a constraint's impacton the model shape, but says nothing about how the model shape is impacted by a con-straint with large parameter changes. This implies that this notion may not be effective inall possible situations, nor could any prioritization scheme claim to be.In the above discussion, the model shape change was loosely denoted as ∆Si withouta formal definition. The next gives a mathematical modeling of this notion. It will be-gin with comparing constraints in a well-constrained model and then extend the result togeneral models involving under-constrained, well-constrained, and over-constrained parts.Certainly, there is no need to prioritize constraints in a well-constrained model since no res-olution is needed for such a model, but starting with it allows an easier presentation of themodeling.Recall that a model's constraints can be translated to a system of algebraic equationsF (X,P ) = 0, where X denotes the equation variables (the coordinates of the geometricentities in the model) and P the constraint parameters. A non-zero parameter change ∆Pwill lead to a change ∆X made to X , which are related by F (X + ∆X,P + ∆P ) = 0. Theapproximation to this relationship is given by:∂F∂X∆X +∂F∂P∆P = 0⇔ ∂F∂X∆X = −∂F∂P∆P (7.1)A variant of this equation is to replace the Jacobian matrix ∂F∂Xwith the geometric perturba-tion matrix G presented in Section 6.2.1, as follows:G∆X = −∂F∂P∆P (7.2)Then, ∆X describes shape changes expressed in terms of geometric translations and ro-tations. Among all model shape changes, we are interested in the one corresponding to aconstraint parameter change made merely to an individual constraint, say the i-th constraint.Such a constraint parameter change can be represented by a special ∆P : ∆P (i) = 1 and104∆P (j 6= i) = 0. Solving Eq. 7.2 with this ∆P gives the intended model shape change.Also, as ∆P (i) has the unit magnitude, the solution ∆X gives directly the change rate forthe i-th constraint.It seems that ∆X in Eq. 7.2 is a good candidate to define the term ∆Si. However, ∆Xis not invariant under rigid-body transformations. For this reason, we slightly modify ∆X ,introducing the notion of relative geometry change. ∆X represents the absolute changemade to the model geometry, and its i-th component ∆X(i) describes the absolute changemade to the i-th geometric entity. The relative model shape change for this geometric entityis defined as:∆X ′(i) =1∑j wij∑jwij (∆X(i)−∆X(j)) (7.3)where the weighted sum is taken over all the neighboring geometric entities j. If rewrittenin a matrix form, the above equation becomes ∆X ′ = R∆X with the transformation matrixR being:Rij =1 j = i− wij∑j wijj 6= i and j is neighboring to i0 otherwise(7.4)With ∆X ′ in place, the term ∆Si is to be defined as the following total change:‖∆X ′‖2 = ‖R∆X‖2 (7.5)where ‖·‖2 is the `2 norm measuring the vector's magnitude. Combining this equation withEq. 7.2 yields the following formulation of the rate of model shape change:‖∆X ′‖2 = ‖RG−1∂F∂P∆P‖2 (7.6)One can easily verify that ‖∆X ′‖2 is invariant under rigid-body transformations. In addi-tion, this formulation has an interesting geometric meaning. In differential geometry, the105matrix R is known as the Laplace operator that measures the model's (discrete) mean cur-vatures [94, 95]. Thus, the proposed formulation (7.6) essentially measures how the model'stotal mean curvature changes with the constraint parameter change ∆P . This may partlyexplain the effectiveness of the proposed constraint prioritization scheme.As already noted, the above formulation is only applicable to well-constrained models.In the following sections, this formulation is generalized — actually with slight modifica-tions — to handle models having over-constrained and/or under-constrained parts. Based onit, the specific algorithms for resolving over-constraint and under-constraint are developed.7.3 Over-Constraint ResolutionThe previous chapter has prepared a model's over-constraint information in the form ofgroups of minimal dependent constraints, see Section 6.3. For convenient references, letthese groups be represented byG = {g1, g2, · · · , gm} and each group be represented by gi ={c1i , c2i , · · · , cnii }. Each group gi is minimal, and thus there is only one cyclical constraintdependency in gi, meaning the removal of any constraint in gi can resolve the over-constraintin this group.As a certain constraint, say cji , is to be removed from group gi, its impact should beevaluated using the summed model shape change rate of the remaining constraints ratherthan the model shape change rate of cji itself. That is, the evaluation is based on the followingquantity: ∑k 6=jChange Rate for cki =∑k 6=j‖RG−1∂F∂P∆Pk‖2 (7.7)where the equation's right side is a direct application2 of Eq. 7.6 with ∆Pk being ∆P (k) = 1and ∆P (i 6= k) = 0. Fig. 7.2 shows an example of applying Eq. 7.7 to an over-constrainedmodel, with the weights in Eq. 7.3 being wij = 1.2Here, G−1 denotes the pseudo inverse [90] of G, instead of the ordinary inverse. This is because G is nei-ther full column rank nor full row rank in general situations where over-constrained and/or under-constrainedparts exist; for such matrices, the pseudo inverse should be used.106 Resolution Option Summed Rate Remove C5 2.2500 Remove C6 3.1250 Remove C7 2.2500 C1.Distance(F1,F3)=1 C2.Distance(F5,F6)=1 C3.Perpendicular(F1,F5) C4.Perpendicular(F1,F4) C5.Perpendicular(F4,F5) C6.Parallel(F2,F4) C7.Perpendicular(F2,F5) C8.Length(E1)=1 F4 F5 F3 F2 F6 F1 E1 Figure 7.2: Application example of Eq. 7.7.With the mathematical modeling of model shape change rate for over-constrained mod-els in place, the proposed prioritization criterion for comparing two constraints in a de-pendency group becomes readily available, as shown in Algorithm 7.1. The type-basedcomparison is used as the rough prioritization (Lines 3, 4 and 9). If the two constraints havethe same type, a fine prioritization based on Eq. 7.7 is to be carried out (Lines 6-8). Thisalgorithm outputs the constraint with lower precedence of constraint type or with the sameprecedence but a lower summed model shape change rate.With Algorithm 7.1 in place, constraints in a dependency group of any size can be prior-itized using ordinary sorting algorithms, which allows us to attain an over-constraint resolu-tion method as shown in Algorithm 7.2. This algorithm first sorts all the dependency groupsin the model regarding their sizes (Line 1) so that they can be presented to the user in as-cending order. The subsequent procedure is to zoom in on one dependency group and todecide which constraints in the group to remove. These constraints are first prioritized usingAlgorithm 7.1 as the binary comparison function (Line 5) and then presented incrementallyto the user (Lines 10-14). If the automatic mode is chosen by the user, the constraint of thetop removal priority will be removed (Lines 6-8).107Algorithm 7.1: Compare Two Constraints in A Dependency Group Algorithm 4: prioritizeConstraints(!", !$) Input: !", !$ − the given two constraints to be compared Output: ! − the constraint with a higher removal priority 1. &' ← GetConstraintType !" 2. &) ← GetConstraintType !$ 3. if &' has a higher type priority than &) then // use Table 7.1 4. ! ← !$ // ! stores the result 5. else if &' has the same type priority to &) then 6. *' ← Evaluate Eq. 7.7 with !" 7. *) ← Evaluate Eq. 7.7 with !$ 8. if *' > *) then ! ← !$ else ! ← !" 9. else ! ← !" 10. Return ! Algorithm 7.2: Over-Constraint Resolution Algorithm 5: resolveOverConstraint(𝐺) Input: 𝐺 − a set of dependency groups Output: 𝐶 − the updated model constraints after the resolution 1. 𝐺 ← SortDependencyGroups(𝐺) // w.r.t. the group size 2. 𝐶 ← GetModelConstraint() // get all the original model constraints 3. for each group 𝑔 ∈ 𝐺 do 4. if 𝑔 has no dependency then continue // resolved in previous iterations 5. 𝑔 ← PrioritizeConstraints(𝑔) // using Algorithm 7.1 6. if automatic mode then 7. 𝑐 ← PopFirstElement(𝑔) 8. 𝐶 ← 𝐶 − {𝑐} 9. else // the decision-support mode 10. for each constraint 𝑐 ∈ 𝑔 do 11. if 𝑐 is accepted by the user then 12. 𝐶 ← 𝐶 − {𝑐} 13. Terminate this loop 14. end for 15. end for 16. Return 𝐶 1087.4 Under-Constraint ResolutionThe previous chapter has prepared a model's under-constraint information in the form ofmaximal well-constrained parts (Section 6.4); the DOFs between these parts describe theunder-constraint. As the parts are maximal, viable constraints to eliminate the DOFs arethose bridging any two of the parts while not adding new over-constraint to the model.Once such constraints are generated, they will be prioritized and then presented to the user,similar to what was done in the previous over-constraint resolution algorithm.In this work, the generation of candidate constraints for two maximal well-constrainedparts begins with a naive constraint set consisting of all possible constraints between thesetwo parts. The primitive procedure is to generate all possible geometric constraints betweena pair of geometric entities belonging respectively to the two parts. This can easily bedone by looking up a constraint table using the pair of geometric entities as the key. Anyconstraints that can be expressed by the constraint types in Table 7.2 will be generated inthis work and stored in the naive constraint set.If added to the model, some of the naive constraints could cause over-constraint with theexisting constraints. For this reason, an additional step excluding such invalid constraints isnecessary, which checks if a constraint causes a dependency with the existing constraints.This can be done by the constraint state characterization method presented in Section 6.2. Geometric Constraint Equation Representation Angle 𝛼 between directions 𝑑1, 𝑑2 𝑑1𝑇𝑑2 = 𝑐𝑜𝑠(𝛼) Parallel directions 𝑑1, 𝑑2 𝑑1 × 𝑑2 = 0 Distance 𝑙 between two positions 𝑝1, 𝑝2 ‖𝑝1 − 𝑝2‖2 = 𝑙 Equal position 𝑝1, 𝑝2 𝑝1 = 𝑝2 Equal angle parameters 𝛼1, 𝛼2 𝛼1 = 𝛼2 Equal length parameters 𝑙1, 𝑙2 𝑙1 = 𝑙2 Table 7.2: Geometric constraint look-up table.109After the over-constraint checking, a much reduced set of candidate constraints is at-tained, each of which can eliminate the DOFs between the two maximal well-constrainedparts of interest. The subsequent task is to determine which of them are to be added to themodel, returning to the constraint prioritization problem. Almost identical to Algorithm 7.1,the prioritization here uses the type-based comparison as a primary criterion and the rate ofmodel shape change as a secondary one, as shown in Algorithm 7.3. The major differenceis that the constraint preferred for addition (i.e., the output of the algorithm) is the one withhigher precedence of constraint type or with the same precedence but a lower rate of modelshape change. The formulation used to evaluate the rate of model shape change is alsodifferent. Algorithm 7.1 uses Eq. 7.7 for the evaluation; here, Eq. 7.6 is used for the evalu-ation. Fig. 7.3 shows an example of applying Eq. 7.6 to an under-constrained model, withthe weights in Eq. 7.3 being wij = 1.Algorithm 7.3: Compare Two Constraints in A Candidate Constraint Set Algorithm 4: prioritizeConstraints(𝑐𝑖, 𝑐𝑗) Input: 𝑐𝑖, 𝑐𝑗 − the given two constraints to be compared Output: 𝑐 − the constraint with a higher addition priority 1. 𝑡1 ← GetConstraintType(𝑐𝑖) 2. 𝑡2 ← GetConstraintType(𝑐𝑗) 3. if 𝑡1 has a higher type priority than 𝑡2 then // use Table 7.1 4. 𝑐 ← 𝑐𝑖 // 𝑐 stores the result 5. else if 𝑡1 has the same type priority to 𝑡2 then 6. 𝑠1 ← Evaluate Eq. 7.6 with 𝑐𝑖 // note: use pseudo inverse for 𝐺−1 7. 𝑠2 ← Evaluate Eq. 7.6 with 𝑐𝑗 // note: use pseudo inverse for 𝐺−1 8. if 𝑠1 > 𝑠2 then 𝑐 ← 𝑐𝑗 else 𝑐 ← 𝑐𝑖 9. else 𝑐 ← 𝑐𝑗 10. Return 𝑐 With both candidate constraints and their prioritization in place, the algorithm to re-solve under-constraint is readily available, as shown in Algorithm 7.4. Let the generatednaive constraints between two maximal well-constrained parts Pi and Pj be represented byCij . The algorithm first removes the invalid candidate constraints in Cij (Line 6) and then110 Resolution Option Rate Add Distance(F4,F7) 0.0258 Add Distance(F2,F7) 0.0258 Add Perpendicular(F7,F5) 1.1806 Add Perpendicular(F7,F3) 1.0172 Add Perpendicular(F7,F8) 1.1806 Add Perpendicular(F7,F1) 1.0172 Add Perpendicular(F7,F10) 1.1806 ⋮ ⋮ F4 F10 F1 F3 F5 F2 F7 F8 C1.Distance(F1,F3)=10 C2.Distance(F2,F4)=15 C3.Distance(F5,F10)=10 C4.Perpendicular(F1,F2) C5.Perpendicular(F1,F10) C6.Perpendicular(F2,F10) C7.Distance(F5,F8)=5 Figure 7.3: Application example of Eq. 7.6.prioritizes the remaining valid candidate constraints (Line 7). Similar to over-constraint res-olution, the first constraint in the sorted constraint set is added to the model if the automatedmode is used (Lines 8-16), or these constraints are presented incrementally to the user if thedecision-support mode is used (Lines 17-26).Nevertheless, there are three differences from the over-constraint resolution algorithm.First, when there are multiple DOFs between Pi and Pj , more than one constraint are tobe added, and this is done by using a while loop to constantly add constraints until all theDOFs are eliminated (equivalently, a local well-constraint is reached between the two parts)(Lines 12-14 and 22-24). The second difference is that, once a constraint is accepted/added,another round of over-constraint checking is conducted to remove invalid candidate con-straints regarding the newly added constraint (Lines 15 and 25). The last difference is thattwo parts are merged once a local well-constraint has been reached between them (Lines13 and 23). The last difference is not strictly necessary since if we do not merge them, theover-constraint checking in later iterations can still remove invalid constraints. With thisstep, unnecessary checking can be avoided, and time saved.111Algorithm 7.4: Under-Constraint Resolution Algorithm 6: resolveUnderConstraint(𝑃) Input: 𝑃 − a set of maximal well-constrained parts Output: 𝐶 − the updated model constraints after the resolution 1. for each pair (𝑃𝑖, 𝑃𝑗), 𝑃𝑖, 𝑃𝑗 ∈ 𝑃 do 2. 𝐶𝑖𝑗 ← ∅ // for storing candidate constraints 3. for each entity pair 𝑒𝑘 ∈ 𝑃𝑖 and 𝑒𝑙 ∈ 𝑃𝑗 do 4. 𝐶𝑖𝑗 ← 𝐶𝑖𝑗 ∪ {GenerateCandidateConstraints(𝑒𝑘, 𝑒𝑙)} 5. end for 6. 𝐶𝑖𝑗 ← RemoveInvalidConstraint(𝐶𝑖𝑗) 7. 𝐶𝑖𝑗 ← PrioritizeConstraints(𝐶𝑖𝑗) // use Algorithm 7.3 8. if automatic mode then 9. while 𝐶𝑖𝑗 is not empty do 10. 𝑐 ← PopFirstElement(𝐶𝑖𝑗) 11. 𝐶 ← 𝐶 ∪ {𝑐} 12. if 𝑃𝑖 ∪ 𝑃𝑗 becomes a well-constrained part then 13. Merge two parts 𝑃𝑖, 𝑃𝑗 14. Terminate this loop (the for loop on the upper level) 15. else 𝐶𝑖𝑗 ← RemoveInvalidConstraint(𝐶𝑖𝑗) 16. end while 17. else // the decision-support mode 18. while 𝐶𝑖𝑗 is not empty do 19. 𝑐 ← PopFirstElement(𝐶𝑖𝑗) 20. if 𝑐 is accepted by the user then 21. 𝐶 ← 𝐶 ∪ {𝑐} 22. if 𝑃𝑖 ∪ 𝑃𝑗 becomes a well-constrained part then 23. Merge two parts 𝑃𝑖, 𝑃𝑗 24. Terminate this loop (the for loop on the upper level) 25. T else 𝐶𝑖𝑗 ← RemoveInvalidConstraint(𝐶𝑖𝑗) 26. end while 27. end for 28. Return 𝐶 1127.5 Implementation and Case StudiesThe methods presented in this chapter have been tested using models from both real andsimulated data, and some of the results are provided in this section. Two examples basedon simulated data have already been given in the previous sections, see Figs. 7.2 and 7.3.Two more examples based on real-world data are to be presented here. These two examplesare based on two mechanical part models: a crank model and an engine bracket model.They were chosen because they can balance the following two factors. On the one hand, theexamples are preferred to being based on models that allow easy demonstration of majorintermediate and final results; on the other hand, the models should be real-world models,which however tend to be complex and to generate a large number of intermediate resolutionsuggestions that are hard to present in detail.7.5.1 ImplementationThe shape-associativity resolution system has been implemented using C++ on top of thegeometry-topology inconsistency resolution system developed in Chapter 5. The system'sgraphical user interface as shown in Fig. 7.4 was developed using QT (version 5.7). All theinvolved numeric solving/optimization was carried out using the linear algebra library Eigen(version 3.2.9) and MATLAB (version R2017a). To detect and resolve shape-associativityinconsistencies in a model, the user presses the Analyze/Resolve button in the inconsistencyresolution toolbox (labeled as 3). The user has the option to let the computer take care of allthe work by checking the two Auto options in the toolbox. When the activation is done, thecomputer will first analyze the constraint state of the model. If the model if well-constrained,a message box pops up to notify the user of this state; otherwise, a panel pops up to showthe analysis results (labeled as 4) and resolution suggestions (labeled as 5). The user thenmakes a decision among these suggestions with the help of the analysis results.113 1 1. Direct Modeling Toolbox 2. List of Model Constraints 3. Inconsistency Resolution Toolbox 4. Information of DOF in the Model 5. List of Resolution Suggestions 2 4 3 5 Figure 7.4: Graphical user interface of the shape-associativity inconsistency resolutionsystem.7.5.2 Case Study IThis case study is based on a crank model as shown in Fig. 7.5. The involved direct editis shown in Fig. 7.6a, and the model constraints3 before and after the direct edit are shownin Fig. 7.6b. To simplify the presentation, constraints for the model's part depicted in thedashed rectangle (Fig. 7.5) were omitted, as this part is the same as the left part. The majorchanges made to the solid model were the removal of faces F2 and F3, which in turn led tothe removal of constraints C6, C7, and C10-C13 in the model GCS.The changes made to the model GCS resulted in an under-constrained model, and threemaximal well-constrained parts were detected in the model, a result of applying the maxi-3Note that, in this case, a distance constraint between a plane and a cylinder refers to the distance measuredfrom the cylinder's position to the plane.114 Side Front Top F9 F11 F15 F16 F14 F18 F17 F12 F10 F3 F2 F4 F5 F6 F7 F8 F1 F13 Figure 7.5: A crank model and its face indexing. Original Constraints Updated Constraints C1. Distance(F1,F9)=55 C2. Distance(F6,F9)=40 C3. CoplanarAxis(F1,F6,F9) C4. Coaxial(F1,F10,F11) C5. Coaxial(F9,F12,F13) C6. Tangent(F1,F2) C7. Tangent(F1,F3) C8. Tangent(F6,F5) C9. Tangent(F6,F4) C10. Angle(F2,F4)=16.92° C11. Angle(F3,F5)=16.92° C12. Distance(F2,F9)=30 C13. Distance(F3,F9)=30 C14. Tangent(F15,F11) C15. Distance(F15,F12)=30 C16. Tangent(F16,F11) C17. Distance(F16,F12)=30 C18. Perpendicular(F8,F6) C19. Distance(F7,F8)=20 C20. Distance(F8,F14)=15 C21. Distance(F14,F17)=40 C22. Distance(F17,F18)=15 C1. Distance(F1,F9)=34 C2. Distance(F6,F9)=40 C3. CoplanarAxis(F1,F6,F9) C4. Coaxial(F1,F10,F11) C5. Coaxial(F9,F12,F13) C6. Removed C7. Removed C8. Tangent(F6,F5) C9. Tangent(F6,F4) C10. Removed C11. Removed C12. Removed C13. Removed C14. Tangent(F15,F11) C15. Distance(F15,F12)=30 C16. Tangent(F16,F11) C17. Distance(F16,F12)=30 C18. Perpendicular(F8,F6) C19. Distance(F7,F8)=20 C20. Distance(F8,F14)=15 C21. Distance(F14,F17)=40 C22. Distance(F17,F18)=15 (a) (b) Figure 7.6: Constraint update: (a) a direct edit applied to the crank model; and (b)constraint update for the edit.115 Maximal Well-Constrained Part I Maximal Well-Constrained Part II Prioritized Resolution Suggestions (To Be Added) Distance(F5,F1)=30 Distance(F5,F10)=30 Distance(F5,F11)=30 Distance(F5,F9)=39.89 Distance(F5,F12)= 39.89 ⋮ Angle(F5,F16)=16.92° Angle(F5,F15)=163.08° ⋮ Merged Maximal Well-Constrained Part Maximal Well-Constrained Part III Prioritized Resolution Suggestions (To Be Added) Distance(F4,F1)=30 Distance(F4,F10)=30 Distance(F5,F11)=30 Distance(F4,F9)=39.89 Distance(F4,F12)= 39.89 ⋮ Angle(F4,F5)=146.16° Angle(F4,F15)= 163.08° Angle(F4,F16)= 16.92 ° ⋮ Final Well-Constrained Model Figure 7.7: Resolution flow, maximal well-constrained parts, and resolution sugges-tions generated for the crank model.mal well-constraint detection method in Section 6.4. These maximal well-constrained partsare shown in Fig. 7.7 and labeled as Maximal Well-Constrained Parts I, II, and III. TheDOF between part I and part II is a rotation of face F5 about the axis of face F6. The reso-lution suggestions generated by the proposed methods for eliminating this DOF are shownin the left rectangle as a list in Fig. 7.7. Due to the large number of resolution suggestionsproduced, we do not present them in detail; only the primary suggestions and those to bereferenced in later discussions are presented. The suggested constraint in the red rectanglewill be selected if the automatic resolution mode is activated; otherwise, the user will decidewhich of the suggested constraints is to be selected. Once a suggested constraint is selected,there is no DOF between part I and part II anymore; then, these two parts will be mergedto form a new maximal well-constrained part, as shown in Fig. 7.7 by the model labeled asMerged Maximal Well-Constrained Part.We then zoom in on the DOFs between the merged part and part III. There is only oneDOF between the two parts, which is a rotation of face F4 about the axis of face F6. This issimilar to the situation for part I and part II. For this reason, the resolution suggestions hereare almost the same as the previous ones, differing in that there are suggested constraints116 Model Variation: 185.39 Model Variation: 188 (a) (b) (c) 34 54 54 Figure 7.8: Increase the dimension leading to varying modeling behavior under differ-ent resolution decisions for the crank model.generated for faces F4 and F5 (e.g., the listed resolution suggestion Angle(F4,F5)=146.16◦).After selecting one constraint from the suggestion list, the whole model becomes well-constrained. This concludes the resolution flow for the first case study.As already noted, different selections of suggested resolution options will lead to dif-ferent modeling behavior under parametric edits. Fig. 7.8 shows the varying modeling be-havior of the crank model for different resolution decisions with regard to a same paramet-ric change made to a key dimension that relates all of the three maximal well-constrainedparts. Fig. 7.8b shows the result of choosing the top suggested constraints. Fig. 7.8cshows the result of choosing two other suggested constraints: Angle(F5,F16)=16.92◦ andAngle(F4,F5)=146.16◦. As expected, the resolution decision whose constraints occur firstin the recommendation list yielded a lower model variation value. From an intuitive pointof view, the shape of the model in Fig. 7.8a is preserved better in the model of Fig. 7.8b thanin that of Fig. 7.8c, which is quite consistent with the notion of model shape change rate.7.5.3 Case Study IIThis case study is based on a bracket model, which is a variant of the model used in Fig. 6.10.The original model and its face reference indices are shown in Fig. 7.9. The applied di-rect edit and the associated model constraint update are shown in Fig. 7.10. The changesmade to the model resulted in two minimal over-constrained parts {C2,C20,C30,C34} and117 Side Front F6 F5 F7 F8 F10 F9 F11 F12 F13 F14 Top F1 F3 F4 F2 F15 F18 F17 F16 F19 F20 F21 F22 F23 F24 F25 F26 F27 F28 F29 F30 Figure 7.9: A bracket model and its face indexing.{C2,C28,C32,C36} (Fig. 7.11), a result of applying the over-constraint detection methodin Section 6.3. This case study and the first case study are complementary to each other.The first case study has only under-constrained parts in the model, which allows us to focuson the under-constraint resolution function of the proposed inconsistency resolution sys-tem. The second case study has only over-constrained parts in the model, which allowsus to zoom in on the over-constraint resolution function. These two case studies togethercomprise a comprehensive evaluation of the methods presented in this chapter.Due to the symmetry of the model, the two constraint dependency groups have similarconfigurations. We thus only need to focus on one of them, and the other can be resolvedwith the same process. Take part I as an example. The prioritization of its four constraints isshown in the mid-left rectangle in Fig. 7.11. As in the first case, if the automatic resolutionmode is activated, the first suggested constraint will be removed; otherwise, the user willdecide which of the suggested constraints is to be removed. Once a suggested constraint isselected and removed, the cyclic dependency in the group under resolution is broken, andthe associated over-constraint is resolved.118 Original Constraints Updated Constraints C1. Dis(F1,F3)=210 C2. Dis(F2,F4)=80 C3. Dis(F5,F6)=10 C4. Dis(F7,F8)=10 C5. Dis(F9,F10)=10 C6. Dis(F11,F12)=10 C7. Dis(F13,F14)=10 C8. Per(F1,F2) C9. Per(F2,F6) C10. Per(F1,F6) C11. Per(F2,F8) C12. Per(F2,F10) C13. Per(F2,F12) C14. Coplanar(F6,F14) C15. Ang(F1,F7)=30° C16. Ang(F3,F11)=30° C17. Dis(F1,Edge(F6,F8))=40.77 C18. Dis(F3,Edge(F12,F14))=40.77 C19. Dis(F6,F23)=72 C20. Dis(F2,F23)=40 C21. Dis(F10,F23)=32 C22. Dis(F1,F15)=75 C23. Dis(F3,F18)=75 C24. Dis(F15,F16)=10 C25. Dis(F17,F18)=10 C26. Coaxial(F23,F25) C27. Dis(F14,F24)=72 C28. Dis(F2,F24)=40 C29. Coaxial(F24,F26) C30. Tangent(F23,F19) C31. Tangent(F23,F20) C32. Tangent(F24,F21) C33. Tangent(F24,F22) C34. Ang(F19,F4)=20° C35. Ang(F20,F2)=20° C36. Ang(F21,F4)=20° C37. Ang(F22,F2)=20° C38. Dis(F27,F1)=10 C39. Dis(F27,F2)=20 C40. Dis(F28,F1)=10 C41. Dis(F28,F4)=20 C42. Dis(F29,F3)=10 C43. Dis(F29,F2)=20 C44. Dis(F30,F3)=10 C45. Dis(F30,F2)=20 C1. Dis(F1,F3)=210 C2. Dis(F2,F4)=80 C3. Dis(F5,F6)=10 C4. Dis(F7,F8)=10 C5. Dis(F9,F10)=10 C6. Dis(F11,F12)=10 C7. Dis(F13,F14)=10 C8. Per(F1,F2) C9. Per(F2,F6) C10. Per(F1,F6) C11. Per(F2,F8) C12. Ang(F2,F10)=110° C13. Per(F2,F12) C14. Coplanar(F6,F14) C15. Ang(F1,F7)=30° C16. Ang(F3,F11)=30° C17. Dis(F1,Edge(F6,F8))=40.77 C18. Dis(F3,Edge(F12,F14))=40.77 C19. Dis(F6,F23)= 56.99 C20. Dis(F2,F23)=45.10 C21. Dis(F10,F23)=32 C22. Dis(F1,F15)=75 C23. Dis(F3,F18)=75 C24. Dis(F15,F16)=10 C25. Dis(F17,F18)=10 C26. Coaxial(F23,F25) C27. Dis(F14,F24)=56.99 C28. Dis(F2,F24)=45.10 C29. Coaxial(F24,F26) C30. Tangent(F23,F19) C31. Tangent(F23,F20) C32. Tangent(F24,F21) C33. Tangent(F24,F22) C34. Par(F19,F4) C35. Ang(F20,F2)=40° C36. Par(F21,F4) C37. Ang(F22,F2)=40° C38. Dis(F27,F1)=10 C39. Dis(F27,F2)=20 C40. Dis(F28,F1)=10 C41. Dis(F28,F4)=20 C42. Dis(F29,F3)=10 C43. Dis(F29,F2)=20 C44. Dis(F30,F3)=10 C45. Dis(F30,F2)=20 (a) (b) Figure 7.10: Constraint update: (a) a direct edit applied to the bracket model; and (b)constraint update for the edit (Dis: Distance, Ang: Angle, Per: Perpendicular,Par: Parallel, Tan: Tangent). Prioritized Resolution Suggestions (To Be Removed) C34: Parallel(F19,F4) C30: Tangent(F23,F19) C20: Distance(F2,F23)=45.10 C2: Distance(F2,F4)=80 Minimal Over- Constrained Part I C2: Distance(F2,F4)=80 C20: Distance(F2,F23)=45.10 C30: Tangent(F23,F19) C34: Parallel(F19,F4) Prioritized Resolution Suggestions (To Be Removed) C36: Parallel(F21,F4) C32: Tangent(F24,F21) C28: Distance(F2,F24)=45.10 C2: Distance(F2,F4)=80 Minimal Over- Constrained Part II C2: Distance(F2,F4)=80 C28: Distance(F2,F24)=45.10 C32: Tangent(F24,F21) C36: Parallel(F21,F4) Figure 7.11: Minimal over-constrained parts in the bracket model and resolution sug-gestions generated.119Fig. 7.12 shows the modeling behavior of different resolution decisions under a sameparametric edit. Fig. 7.12b shows the result of choosing the top suggested constraints, i.e.,removing constraints C34 and C36. Fig. 7.12c shows the result of choosing two other sug-gested constraints: removing constraints C30 and C32. As can be seen from the model vari-ation values in Fig. 7.12b and Fig. 7.12c, the proposed methods, again, assigned a higherpriority to the resolution suggestions leading to less model variation and a better resem-blance to the original model. (a) (b) (c) 45.10 50.10 50.10 Model Variation: 18 Model Variation: 29.5 Figure 7.12: Increase the dimension leading to varying modeling behavior under dif-ferent resolution decisions for the bracket model.7.5.4 Discussions and LimitationsThe varying modeling behavior shown in Fig. 7.8 and Fig. 7.12 has been presented to threeexperienced mechanical engineers in the university's machine shop. They all chose Fig. 7.8band Fig. 7.12b over those depicted in Fig. 7.8c and Fig. 7.12c, which may confirm the effec-tiveness of the proposed inconsistency resolution system. Nevertheless, two of them furtherpointed out that Fig. 7.8c was also possible in real practice, although quite uncommon. Thisbasically implies that it may not be possible to have a general criterion that always resultsin the most intended resolution option (at least for general CAD systems and at present). Acompletely automatic shape-associativity inconsistency resolution may thus not be achiev-able and should be working as a secondary mode, and the decision-support mode should bethe primary way of working in practice.120Although the presented resolution system is seen to be quite effective in the case studiesabove, it is expected that the ambiguity among resolution options will increase in morecomplicated cases. As a result, the prioritization results may deviate from the user's designintent more, and the user may need to go through more resolution suggestions before gettingthe right constraint(s). There are hints for such a situation in the crank-based case study. Thefirst three options in the left suggestion list of Fig. 7.11 have the same change rate value (=0.9517), meaning that the change rate notion cannot distinguish them. But they clearlyrepresent different design intents. This implies that the change rate notion is not in line withthe design intent perfectly, partly because this notion only characterizes the local modelvariation behavior under parametric edits without considering the global behavior.This work's research so far suggests that the resolution system can be used to assistshape-associativity inconsistency resolution. In particular, the detection system can providean automatic geometric reasoning of shape-associativity inconsistencies as well as an effec-tive assistance for the user to understand the inconsistencies quickly. The recommendationsystem ensures that only valid resolution options are presented to the user and provides aguided assistance for the user to explore these options through prioritizing them with respectto the notion of model shape change rate. With this guided assistance, it is expected thatthe user can reach the intended resolution options more quickly. The change rate notion isa good quantification of a constraints impact on the model shape, but it does not match thedesign intent perfectly. This gap may be improved by priorities incorporating both local andglobal characterizations of model variation. Modeling a models global variation behavioris, however, very challenging due to the nonlinearity issues involved.7.6 SummaryThis chapter first presented the overall framework of shape-associativity inconsistency res-olution and then focused on the two missing parts for implementing this framework: over-constraint resolution and under-constraint resolution. The major tasks in these two missing121parts are to avoid invalid resolution options and to prioritize valid ones. The former task canbe addressed effectively based on the methods presented in the previous chapter. The lattertask thus comprised the main body of this chapter.A hierarchical prioritization scheme, which consists of a rough prioritization level and afine prioritization level, was proposed to prioritize valid resolution options. The rough pri-oritization level ranks constraints according to their types, an adaptation of existing work.The fine prioritization level ranks constraints of the same type through a novel notion ofmodel shape change rate. This notion characterizes how removing/adding a constraint im-pacts the model shape variation under parametric edits. The intuition behind this notion isthat a resolution option with a smaller model shape change rate yields less model variation,and then the model after parametric edits could resemble better the model as it was beforethe edits. This notion allows the resolution option leading to less model variation to be pre-sented to the user first, and allows the resolution option leading to the least model variationto be chosen by the computer in the automatic resolution mode. By doing so, it is expectedthat decision-making among resolution options can be done fast. The effectiveness of theresolution framework and prioritization scheme has been demonstrated through case studiesbased on both artificial models and real-world mechanical part models.122Chapter 8: ConclusionThe subject of this thesis is a new CAD modeling scheme called variational direct model-ing. Its motivation lies in the limitations of current CAD modeling paradigms. The mostadvanced modeling schemes are parametric modeling and direct modeling. The former of-fers great flexibility for parametric (global) model edits due to the parent-child dependenciesconstructed between geometric entities in a model. It is due to the same dependencies thatthe geometric entities are divided into parent entities and child entities, and that child enti-ties are rigid for model edits, in particular for local model edits. Direct modeling noticedthis modeling rigidity issue and presented a straightforward solution: since the rigidity issueis a result of the division of geometric entities into parent entities and child entities, whichin turn results from the parent-child dependencies, it removes the division by completelyremoving the dependencies. In doing so, all geometric entities are made free to change, andthen direct modeling can provide unprecedented flexibility for local model edits but, on theother hand, it barely supports parametric (global) model edits. The capabilities and limita-tions stated above motivated the author to define the objective of this thesis as: proposing anew CAD modeling approach with both the capabilities while avoiding their limitations.To achieve this goal, variational direct modeling uses a new, different thinking fromdirect modeling. It removes the division by adding some stuff into the dependencies: theunidirectional parent-child dependencies are replaced by bi-directional relationships. Indoing so, all geometric entities are made equal, and then they are all free to change. Also,parametric (global) model edits are still available due to the bi-directional relationships(geometric constraints).123The above idea is easy to state but difficult to realize. The major challenges are to ad-dress the possible information inconsistencies in a model after parametric/direct edits. Thereare three different types of information in a model: geometry, topology, and constraint. Theycan ultimately lead to three different information inconsistency types: geometry-topologyinconsistency, shape-associativity inconsistency I, and shape-associativity inconsistency II.Having these inconsistency types in mind, a review of existing research work was then con-ducted to summarize what is already possible, what developments can be expected in thenear feature, and which parts remain problematic. The results are as follows:1. Shape-associativity inconsistency I can be well-addressed using existing research re-sults in the area of geometric constraint solving.2. There has not been much research work related to geometry-topology inconsistencies.3. There are many existing studies related to shape-associativity inconsistency II. How-ever, the most related work is still very preliminary, and significant development isnecessary.Based on the review results, the research problems this thesis focuses on were narroweddown to resolving possible geometry-topology inconsistencies and shape-associativity in-consistencies (type II) after direct model edits.An analysis of the two inconsistency resolution problems was subsequently conductedto answer the following fundamental questions: how are the inconsistencies formed; whatare the checking conditions of the inconsistencies; and why is handling the inconsistencieschallenging? Based on the answers, this thesis' problem statement, at a more technical level,was finally crafted as: given a model after direct edits, (1) robustly resolve the possiblegeometry-topology inconsistencies to attain a valid modeling result and a continuous modelvariation, and (2) correctly characterize the model's constraint state, and optimally detectthe over-constrained parts and well-constrained parts (i.e., the possible shape-associativityinconsistencies) in the model, and effectively prioritize valid resolution options. In theabove formulation, from a conceptual objective to technical problems, it was not expected124to include comprehensively all the issues of implementing variational direct modeling, butto focus on the most important and challenging problems.Problem (1) was solved by a novel, systematic method, based on the continuity principle.The principle was formulated as successive applications of two tasks — GTIP detection andcontinuity-based decision-making, which were discussed in chapters 4 and 5, respectively.A hybrid method was proposed to accomplish the GTIP detection task. The sub-method Iof the hybrid method is a generalization of existing heuristic-based methods, and the sub-method II is a novel one. For the continuity-based decision-making task, a novel method wasproposed to formulate the continuity requirement as Boolean operations on model volume.Combining these methods gives a systematic method of geometry-topology inconsistencyresolution, which features guaranteed model validity and continuous model variations. Aseries of case studies was conducted to validate the methods.Problem (2) consists of two sub-problems: inconsistency detection and inconsistencyresolution. The detection sub-problem further consists of three problems: the characteriza-tion of constraint states, the detection of minimal over-constrained parts, and the detectionof maximal well-constrained parts. The characterization problem was solved by generaliz-ing the existing witness configuration method. The two detection problems were addressedby two novel methods that formulate the problems as sparse recovery problems that can beeffectively solved with existing optimization techniques. The resolution sub-problem washandled using a novel constraint prioritization scheme. The effectiveness of these meth-ods has been demonstrated through comparisons with the existing method and case studiesbased on real-world part models.Most methods/ideas presented in this work are novel, and their effectiveness has beenvalidated through case studies ranging from simple to complex and from virtual part modelsto real-world part models. These methods solved the most fundamental issue — informationinconsistency resolution — of variational direct modeling. Nevertheless, they only repre-sent a starting point for developing the variational direct modeling system, and much work125remains to be done:1. Most notably, the present decision-making methods — the continuity-based methodand model shape change rate based method — can generate good results for the casestudies in this work, but may not be able to do so in all possible situations. In the fu-ture, these methods may be augmented by artificial intelligence algorithms. It should,however, be noted that a 100% correct decision-making method seems to be impossi-ble in the CAD domain since there are subjective aspects in engineering design.2. Another interesting augment that could be made to variational direct modeling is toinclude the delete-face operation, which will lead to the same problem of makingdecisions among multiple resolution options. This operation, by its very nature, doesnot follow a continuous model variation pattern. Thus, the continuity-based decision-making criterion proposed in this work is not applicable, and new decision-makingcriteria are necessary.3. One may also be tempted to combine variational direct modeling with virtual/aug-mented reality techniques, as their ways of working are compatible.4. Even with the presented technical methods, however, there are several interesting av-enues to pursue. In particular, heuristics are still used in GTIP detection (Section 4.3).Use of heuristics is a lazy way to solve problems, and the resulting methods are oftennot systematic or elegant. The second detection method presented in Section 4.4 issystematic, but the required computational load is high. Therefore, increasing thismethod's efficiency and then completely avoiding the use of heuristics could be aninteresting improvement direction.5. From a more practical perspective, the shape-associativity inconsistency resolutionmethods in Section 7.3 and Section 7.4 present prioritized constraints to the user viaplain text of the constraints. Animations simulating model variations under parameterchanges made to these constraints could be beneficial for the user to quickly under-stand the consequences of adding or removing the constraints.1266. A promising avenue for future work is a more thorough investigation of the notionof model shape change rate presented in Section 7.2. The current modeling of modelshape change rate only considered a constraint's impact on the model shape on a localscale; the quantification of the global impact of adding or removing a constraint mayprove useful in constraint prioritization.127Bibliography[1] J. Shah and M. Mantyla, Parametric and Feature-Based CAD/CAM: Concepts, Tech-niques, and Applications. John Wiley & Sons, 1995. → pages 1, 3, 26[2] S. Coons, "An outline of the requirements for a computer-aided design system," inProceedings of the Spring Joint Computer conference, pp. 299–304, ACM, 1963. →page 1[3] S. Coons and and R. W. Mann, "Computer-aided design related to the engineeringdesign process," tech. rep., Massachusetts Institute of Technology, 1960. → page 1[4] D. T. Ross, "Computer-aided design: a statement of objectives," tech. rep., Mas-sachusetts Institute of Technology, 1960. → page 1[5] S. Jayanti, Y. Kalyanaraman, N. Iyer, and K. Ramani, "Developing an engineeringshape benchmark for CAD models," Computer-Aided Design, vol. 38, no. 9, pp. 939–953, 2006. → page 2[6] A. A. Requicha, "Mathematical models of rigid solid objects," tech. rep., Universityof Rochester, 1977. → pages 2, 15[7] I. E. Sutherland, "Sketchpad a man-machine graphical communication system," Sim-ulation, vol. 2, no. 5, pp. R–3, 1964. → page 2[8] A. A. G. Requicha, "Representations for rigid solids: theory, methods, and sys-tems," ACM Computing Surveys, vol. 12, pp. 437–464, dec 1980. → pages2, 14, 15, 16, 25, 60[9] I. C. Braid, "Geometric modelling," in Advances in Computer Graphics I, pp. 325–362, Springer, 1986. → pages 2, 6, 15[10] V. Shapiro, "Solid modeling," in Handbook of Computer Aided Geometric Design,pp. 473–518, North-Holland, 2002. → page 2[11] J. J. Shah, "Designing with parametric CAD: classification and comparison of con-struction techniques," in Geometric Modelling, pp. 53–68, Springer, 2001. → pages2, 3, 4, 16, 17[12] N. Iyer, S. Jayanti, K. Lou, Y. Kalyanaraman, and K. Ramani, "Shape-based searchingfor product lifecycle applications," Computer-Aided Design, vol. 37, no. 13, pp. 1435–1446, 2005. → page 3128[13] C. Jackson and M. Buxton, "The design reuse benchmark report: seizing the opportu-nity to shorten product development," tech. rep., Aberdeen Group, Boston, 2007. →page 3[14] J. Chad and H. David, "Synchronous technology: the best of both worlds for engineer-ing organizations," tech. rep., Aberdeen Group, Boston, 2008. → page 3[15] M. A. El Hani, L. Rivest, and R. Maranzana, "Product data reuse in product devel-opment: a practitioner's perspective," in IFIP International Conference on ProductLifecycle Management, pp. 243–256, Springer, 2012.[16] R. P. Diwakaran and M. D. Johnson, "Analyzing the effect of alternative goals andmodel attributes on CAD model creation and alteration," Computer-Aided Design,vol. 44, no. 4, pp. 343–353, 2012.[17] J. D. Camba, M. Contero, and P. Company, "Parametric CAD modeling: an analysisof strategies for design reusability," Computer Aided Design, vol. 74, pp. 18–31, 2016.→ pages 3, 4, 17, 18[18] D. Roller, "An approach to computer-aided parametric design," Computer-Aided De-sign, vol. 23, no. 5, pp. 385–391, 1991. → page 3[19] R. Light and D. Gossard, "Modification of geometric models through variational ge-ometry," Computer-Aided Design, vol. 14, no. 4, pp. 209–214, 1982. → page 3[20] C. M. Hoffman, A. Lomonosov, and M. Sitharam, "Decomposition plans for geomet-ric constraint systems, part I: performance measures for CAD," Journal of SymbolicComputation, vol. 31, no. 4, pp. 367–408, 2001. → pages 3, 21, 31[21] D. Mun, S. Han, J. Kim, and Y. Oh, "A set of standard modeling commands forthe history-based parametric approach," Computer-Aided Design, vol. 35, no. 13,pp. 1171–1179, 2003. → page 3[22] S. Gupta, Turner Joshua U., and J. Turner, "Variational solid modeling for toleranceanalysis," IEEE Computer Graphics and Applications, vol. 13, no. 3, pp. 64–74, 1993.→ page 3[23] J. J. Shah and M. T. Rogers, "Functional requirements and conceptual design ofthe Feature-Based Modelling System," Computer-Aided Engineering Journal, vol. 5,no. 1, pp. 9–15, 1988. → page 3[24] J. J. Shah, "Assessment of features technology," Computer-Aided Design, vol. 23,no. 5, pp. 331–343, 1991. → page 3[25] P. Andrews, T. Shahin, and S. Sivaloganathan, "Design reuse in a CAD environmentfour case studies," Computers & Industrial Engineering, vol. 37, no. 1-2, pp. 105–109,1999. → pages 4, 18129[26] J. Monedero, "Parametric design: a review and some experiences," Automation inConstruction, vol. 9, no. 4, pp. 369–377, 2000.[27] B. Bettig, V. Bapat, and B. Bharadwaj, "Limitations of parametric operators for sup-porting systematic design," in Proceedings of the 17th International Conference onDesign Theory and Methodology, vol. 2005, pp. 131–142, ASME, 2005. → pages4, 18[28] S. Tornincasa and F. D. Monaco, "The future and the evolution of CAD," in Proceed-ings of the 14th International Research/Expert Conference, no. 1, pp. 11–18, 2010. →pages 4, 10[29] H. Ault and A. Phillips, "Direct modeling: easy changes in CAD," in Proceedings ofthe 70th ASEE Engineering Design Graphics Division Midyear Conference, pp. 99–106, 2016. → pages 4, 5, 10[30] B. Bettig and C. M. Hoffmann, "Geometric constraint solving in parametric computer-aided design," Journal of Computing and Information Science in Engineering, vol. 11,no. 2, p. 021001, 2011. → pages 5, 7, 18, 20[31] J. Fu, X. Chen, and S. Gao, "Automatic synchronization of a feature model with directediting based on cellular model," Computer-Aided Design and Applications, vol. 14,no. 5, pp. 680–692, 2017. → pages 6, 18, 19[32] R. Anderl and R. Mendgen, "Modelling with constraints: theoretical foundation andapplication," Computer-Aided Design, vol. 28, no. 3, pp. 155–168, 1996. → page 6[33] Q. Zou and H.-Y. Feng, "Push-pull direct modeling of solid CAD models," Advancesin Engineering Software, vol. 127, pp. 59–69, 2019. → page 8[34] Q. Zou and H.-Y. Feng, "Variational B-rep model analysis for direct modeling us-ing geometric perturbation," Journal of Computational Design and Engineering doi:https://doi.org/10.1016/j.jcde.2019.03.002, 2019. → page 8[35] S. E. Thierry, P. Schreck, D. Michelucci, C. Funfzig, and J. D. Ge´nevaux, "Extensionsof the witness method to characterize under-, over- and well-constrained geometricconstraint systems," Computer Aided Design, vol. 43, no. 10, pp. 1234–1249, 2011.→ pages 8, 21, 22, 31, 75, 76, 90, 136, 137[36] S. Foufou and D. Michelucci, "Interrogating witnesses for geometric constraintsolving," Information and Computation, vol. 216, pp. 24–38, 2012. → pages21, 22, 75, 76, 90, 137[37] M. Moinet, G. Mandil, and P. Serre, "Defining tools to address over-constrainedgeometric problems in Computer Aided Design," Computer-Aided Design, vol. 48,pp. 42–52, 2014. → page 22130[38] H. Hu, M. Kleiner, and J.-P. Pernot, "Over-constraints detection and resolution in geo-metric equation systems," Computer-Aided Design, vol. 90, pp. 84–94, 2017.→ pages8, 22, 31, 76, 136[39] I. Stroud, Boundary Representation Modelling Techniques. Springer, 2006. → page 9[40] L. A. Piegl and W. Tiller, The NURBS book. Springer, 1997. → page 10[41] W. Wang, "Modeling and processing with quadric surfaces," in Handbook of ComputerAided Geometric Design, pp. 777–795, North-Holland, 2002. → page 10[42] T. Rabbani and F. Van Den Heuvel, "Efficient Hough transform for automatic detectionof cylinders in point clouds," in Proceedings of the 11th Annual Conference of theAdvanced School for Computing and Imaging, pp. 60–65, 2005. → page 10[43] M. Mantyla, "A note on the modeling space of Euler operators," Computer Vision,Graphics, and Image Processing, vol. 26, no. 1, pp. 45–60, 1984. → pages 15, 25, 26[44] A. A. Requicha and H. B. Voelcker, "Boolean operations in solid modeling: boundaryevaluation and merging algorithms," Proceedings of the IEEE, vol. 73, no. 1, pp. 30–44, 1985. → page 16[45] A. R. Grayer, "Alternative approaches in geometric modelling," Computer-Aided De-sign, vol. 12, no. 4, pp. 189–192, 1980. → page 18[46] J. R. Rossignac, "Issues on feature-based editing and interrogation of solid models,"Computers and Graphics, vol. 14, no. 2, pp. 149–172, 1990. → page 19[47] I. Stroud and P. C. Xirouchakis, "CAGD - Computer-aided gravestone design," Ad-vances in Engineering Software, vol. 37, no. 5, pp. 277–286, 2006. → page 18[48] Y. Woo and S. H. Lee, "Volumetric modification of solid CAD models independentof design features," Advances in Engineering Software, vol. 37, no. 12, pp. 826–835,2006. → page 19[49] B. C. Kim and D. W. Mun, "Stepwise volume decomposition for the modificationof B-rep models," The International Journal of Advanced Manufacturing Technology,vol. 75, no. 9-12, pp. 1393–1403, 2014. → page 19[50] M. Lipp, P. Wonka, and P. Mu¨ller, "PushPull++," ACM Transactions on Graphics,vol. 33, no. 4, pp. 1–9, 2014. → pages 19, 39[51] J.-F. Dufourd, P. Mathis, and P. Schreck, "Geometric construction by assemblingsolved subfigures," Artificial Intelligence, vol. 99, no. 1, pp. 73–119, 1998. → page 20[52] R. Joan-Arinyo and A. Soto, "A correct rule-based geometric constraint solver," Com-puters & Graphics, vol. 21, no. 5, pp. 599–609, 1997. → page 20131[53] J. C. Owen, "Algebraic solution for geometry from dimensional constraints," in Pro-ceedings of the First ACM symposium on Solid Modeling Foundations and CAD/CAMApplications, pp. 397–407, 1991. → page 21[54] W. Bouma, I. Fudos, C. Hoffmann, J. Cai, and R. Paige, "Geometric constraint solver,"Computer-Aided Design, vol. 27, no. 6, pp. 487–501, 1995. → page 21[55] I. Fudos and C. M. Hoffmann, "A graph-constructive approach to solving systems ofgeometric constraints," ACM Transactions on Graphics, vol. 16, no. 2, pp. 179–216,1997.[56] X.-S. Gao, C. M. Hoffmann, and W.-Q. Yang, "Solving spatial basic geometric con-straint configurations with locus intersection," in Proceedings of the Seventh ACMSymposium on Solid Modeling and Applications, pp. 111–122, 2002. → page 21[57] L. A. Bardord, A graphical, language-based editor for generic solid models repre-sented by constraints. Phd thesis, Cornell University, 1987. → page 21[58] D. Serrano, Constraint management in conceptual design. PhD thesis, MassachusettsInstitute of Technology, 1987. → page 21[59] S. Ait-Aoudia, R. Jegou, and D. Michelucci, "Reduction of constraint systems," inProceedings of Compugraphics, pp. 83–92, 1993. → page 21[60] R. Latham and A. Middleditch, "Connectivity analysis: a tool for processing geometricconstraints," Computer-Aided Design, vol. 28, no. 11, pp. 917–928, 1996. → page 22[61] C. M. Hoffmann, A. Lomonosov, and M. Sitharam, "Finding solvable subsets of con-straint graphs," in Proceedings of International Conference on Principles and Practiceof Constraint Programming, pp. 463–477, 1997. → pages 21, 31[62] X.-S. Gao, Q. Lin, and G.-F. Zhang, "A C-tree decomposition algorithm for 2D and3D geometric constraint solving," Computer-Aided Design, vol. 38, no. 1, pp. 1–13,2006. → page 21[63] D. Michelucci and S. Foufou, "Geometric constraint solving: the witness configurationmethod," Computer Aided Design, vol. 38, no. 4, pp. 284–299, 2006. → pages 21, 22[64] J. E. Graver, B. Servatius, and H. Servatius, Combinatorial rigidity. American Math-ematical Society, 1993. → page 21[65] A. Kubicki, D. Michelucci, and S. Foufou, "Witness computation for solving geomet-ric constraint systems," in Proceedings of the 2014 Science and Information Confer-ence, pp. 759–770, 2014. → page 21[66] C. Jermann and H. Hosobe, "A constraint hierarchies approach to geometric con-straints on sketches," in Proceedings of the 2008 ACM Symposium on Applied Com-puting, pp. 1843–1844, ACM, 2008. → page 22132[67] A. Borning, B. Freeman-Benson, and M. Wilson, "Constraint hierarchies," Lisp andSymbolic Computation, vol. 5, no. 3, pp. 223–270, 1992. → page 22[68] R. Joan Arinyo, A. Soto Riera, S. Vila Marta, and J. Vilaplana Pasto, "Transform-ing an under-constrained geometric constraint problem into a well-constrained one,"in Proceedings of the eighth ACM Symposium on Solid Modeling and Applications,pp. 33–44, ACM, 2002. → page 22[69] C. M. Hoffmann, M. Sitharam, and B. Yuan, "Making constraint solvers more usable:overconstraint problem," Computer-Aided Design, vol. 36, no. 4, pp. 377–399, 2004.[70] G.-F. Zhang and X.-S. Gao, "Well-constrained Completion and Decomposition forunder-constrained Geometric Constraint Problems," International Journal of Compu-tational Geometry & Applications, vol. 16, no. 05n06, pp. 461–478, 2006. → page22[71] S. Murugappan, S. Sellamani, and K. Ramani, "Towards beautification of freehandsketches using suggestions," in Proceedings of the 6th Eurographics Symposium onSketch-Based Interfaces and Modeling, pp. 69–76, ACM, 2009. → page 23[72] B. I. Mills, F. C. Langbein, A. D. Marshall, and R. R. Martin, "Estimate of frequenciesof geometric regularities for use in reverse engineering of simple mechanical compo-nents," tech. rep., Cardiff University, 2001. → page 102[73] M. Luisa Martı´nez and J. Fe´lez, "A constraint solver to define correctly dimensionedand overdimensioned parts," Computer-Aided Design, vol. 37, no. 13, pp. 1353–1369,2005.[74] H. Zou and Y. Lee, "Constraint-based beautification and dimensioning of 3D polyhe-dral models reconstructed from 2D sketches," Computer-Aided Design, vol. 39, no. 11,pp. 1025–1036, 2007. → pages 23, 102[75] F. Langbein, A. Marshall, and R. Martin, "Choosing consistent constraints for beau-tification of reverse engineered geometric models," Computer-Aided Design, vol. 36,no. 3, pp. 261–278, 2004. → pages 23, 102[76] Y. Li, X. Wu, Y. Chrysathou, A. Sharf, D. Cohen, O. Niloy, and J. M. Siat, "GlobFit:consistently fitting primitives by discovering global relations," ACM transactions ongraphics, vol. 30, no. 4, p. 52, 2011. → page 23[77] G. Shen, T. Sakkalis, and N. Patrikalakis, "Analysis of boundary representation modelrectification," in Proceedings of the 6th ACM Symposium on Solid Modeling and Ap-plications, pp. 149–158, 2001. → page 25[78] J. D. Camba and M. Contero, "Assessing the impact of geometric design intent an-notations on parametric model alteration activities," Computers in Industry, vol. 71,pp. 35–45, 2015. → pages 28, 33, 100133[79] V. Shapiro and D. L. Vossler, "What is a parametric family of solids?," in Proceedingsof the 3rd ACM Symposium on Solid Modeling and Applications, pp. 43–54, 1995. →pages 28, 36[80] S. Raghothama and V. Shapiro, "Boundary representation deformation in parametricsolid modeling," ACM Transactions on Graphics, vol. 17, no. 4, pp. 259–286, 1998.→ pages 28, 36[81] R. Hillyard and I. Braid, "Analysis of dimensions and tolerances in computer-aidedmechanical design," Computer-Aided Design, vol. 10, no. 3, pp. 161–166, 1978. →pages 33, 100, 103[82] S. Raghothama and V. Shapiro, "Topological framework for part families," in Proceed-ings of the Seventh ACM Symposium on Solid Modeling and Applications, pp. 1–12,ACM, 2002. → page 36[83] H. A. Van der Meiden and W. F. Bronsvoort, "Tracking topological changes in para-metric models," Computer Aided Geometric Design, vol. 27, no. 3, pp. 281–293, 2010.→ page 39[84] M. Hidalgo and R. Joan-Arinyo, "Computing parameter ranges in constructive ge-ometric constraint solving: implementation and correctness proof," Computer-AidedDesign, vol. 44, no. 7, pp. 709–720, 2012. → page 39[85] J. Peters, "Geometric continuity," in Handbook of Computer Aided Geometric Design,pp. 193–227, North-Holland, 2002. → page 40[86] J. A. Bondy and U. S. R. Murty, "Graph Theory with Applications," 1976. → page 48[87] M. P. Do Carmo, Differential Geometry of Curves and Surfaces. Prentice Hall, 1976.→ page 51[88] B. Bettig and J. Shah, "Derivation of a standard set of geometric constraints for para-metric modeling and data exchange," Computer-Aided Design, vol. 33, no. 1, pp. 17–33, 2001. → page 52[89] J. Mo¨bius and L. Kobbelt, "OpenFlipper: an open source geometry processing andrendering framework," in Proceedings of the International Conference on Curves andSurfaces, pp. 488–500, 2012. → page 62[90] G. Strang, Introduction to Linear Algebra. Wellesley-Cambridge Press, 2016. →pages 76, 81, 83, 85, 106[91] C. Jermann, B. Neveu, and G. Trombettoni, "A new structural rigidity for geometricconstraint systems," in Proceedings of International Workshop on Automated Deduc-tion in Geometry, pp. 87–105, Springer, 2002. → page 76[92] R. Gilmore, Lie groups, Lie Algebras, and Some of Their Applications. Courier Cor-poration, 2012. → page 78134[93] S. Osher and W. Yin, "Sparse recovery via l1 and L1 optimization," tech. rep., Univer-sity of California, Los Angeles, 2014. → page 86[94] M. Desbrun, M. Meyer, P. Schro¨der, and A. H. Barr, "Implicit fairing of irregularmeshes using diffusion and curvature flow," in Proceedings of the 26th annual confer-ence on Computer graphics and interactive techniques, pp. 317–324, ACM, 1999. →page 106[95] M. Meyer, M. Desbrun, P. Schro¨der, and A. H. Barr, "Discrete differential-geometryoperators for triangulated 2-manifolds," in Visualization and Mathematics III, pp. 35–57, Springer, 2003. → page 106135Appendix A: Examples of the Limitations in Section 6.1The basic idea of the greedy-based methods in [35–38] for detecting the minimal over-constrained parts in a model can be understood with the help with the example in Eq. A.1.The methods start from a seed equation, e.g., Eq. A.1a, then iterate through all equationsto greedily find a maximal subset of independent equations. For this case, the result willbe {Eq. A.1a, Eq. A.1b, Eq. A.1c}. Subsequently, the dependencies of the rest constraintswith the constraints in the subset will be checked. For example, Eq. A.1d is dependent withall the three constraints in the subset, and the same for Eq. A.1e. Finally, the methods willoutput two minimal over-constrained parts: {Eq. A.1a, Eq. A.1b, Eq. A.1c, Eq. A.1d} and{Eq. A.1a, Eq. A.1b, Eq. A.1c, Eq. A.1e}.x+ y + z = 0 (A.1a)2x+ y + z = 1 (A.1b)3x+ 2y + z = 1 (A.1c)x+ 2y + 3z = 1 (A.1d)2x+ 4y + 3z = 2 (A.1e)The methods are not always effective because the maximal independent subset is notunique, and this non-uniqueness could lead to wrong detection results. Consider the exam-ple in Eq. A.2 (a slight modification of Eq. A.1). The methods will give the same results asthose for Eq. A.1. However, it is easy to see that there is another dependency group with a136smaller size: {Eq. A.1d, Eq. A.1e}.x+ y + z = 0 (A.2a)2x+ y + z = 1 (A.2b)3x+ 2y + z = 1 (A.2c)x+ 2y + 3z = 1 (A.2d)2x+ 4y + 6z = 2 (A.2e)The basic idea presented in [35, 36] to greedily detect the maximal well-constrained partsin a model is as follows. First, a geometric entity set S is initialized with a seed geometricentity (randomly chosen). Then, we iterate through other geometric entities in the model tocheck if any of them can form a well-constrained part with the geometric entities alreadyincluded in S and, if so, add the geometric entity to S. The resulting S gives a "maximal"well-constrained part. Repeating these procedures on the remaining geometric entities inthe model until no geometric entity remains gives all the "maximal" well-constrained parts.Similar to the situation in over-constraint detection, the initialization (i.e., the choice of seedgeometric entities) has a significant effect on the methods' success.An example of this limitation is given in Figs. A.1 and A.2. A crank model with twoDOFs is shown in Fig. A.1, and the two DOFs are a rotation of plane F2 about cylinderF4's axis and a rotation of plane F3 about cylinder F4's axis. Fig. A.2a shows one resultof using the greedy methods, where the seed geometric entity for part I is plane F3, theseed geometric entity for part II is cylinder F7, and that for part III is plane F2. However,Fig. A.2b shows another solution with a larger size on the well-constrained part I.137 Top F14 F11 F15 Side F3 F2 F4 F5 F6 F1 Front F9 F13 F12 F10 F8 F7 C1. Distance(F1,F7)=34 C2. Distance(F4,F7)=40 C3. CoplanarAxis(F1,F4,F7) C4. Coaxial(F1,F8,F9) C5. Coaxial(F7,F10) C6. Tangent(F4,F2) C7. Tangent(F4,F3) C8. Tangent(F10,F14) C9. Distance(F9,F14)=30 C10. Tangent(F10,F15) C11. Distance(F9,F15)=30 C12. Perpendicular(F6,F7) C13. Distance(F5,F6)=20 C14. Distance(F6,F11)=15 C15. Distance(F11,F12)=40 C16. Distance(F12,F13)=15 Figure A.1: An under-constrained model. Figure 4 Results of maximal well-constraint detection. Part III Size: 1 Faces: F2 Part II Size: 1 Faces: F3 Part I Size: 13 Faces: F1,F4-F15 Part III Size: 1 Faces: F2 Part II Size: 7 Faces: F1,F7,F8,F9,F10,F14,F15 Part I Size: 7 Faces: F3,F4,F5,F6,F11,F12,F13 (b) (a) Figure A.2: Results of maximal well-constraint detection.138Appendix B: Proof of Proposition 6.1Proof. Rigid-body motions are evidently motions preserving the model shape, and thusthere is no need for a proof. The proof here is focused on geometry-invariant motions. LetM be a model having m geometric entities {gi}mi=1. Without loss of generality, assumethat there is a motion T applied to the first k geometric entities of the model, producinga perturbed model M ′ : {Tg1, · · · , Tgk, gk+1, · · · , gm}, and assume that T preserves themodel shape. As M and M ′ have the same shape, there exists a rigid-body transforma-tion T ′ that is able to transform M to M ′ . This means that T ′gi and Tgi, 1 ≤ i ≤ k,describe the same entity (they are geometrically same but the parameters may be different,e.g., two planes having collinear orientation vectors and coplanar positions are geometri-cally same). Therefore, the difference between the two transformations T and T ′ shouldbe a geometry-invariant motion for the first k geometry entities. This difference is to bedenoted as T ′′i , with T′= T′′i T . For the rigid-body transformation T′ , its inverse T ′−1is also a rigid-body transformation and can be used to transform M ′ back to M , yielding{T ′−1Tg1, · · · , T ′−1Tgk, T ′−1gk+1, · · · , T ′−1gm}. Again, this means that T ′−1gi and gi,k + 1 ≤ i ≤ m, describe the same entity. Then, T ′−1 is not only a rigid-body motion butalso a geometry-invariant motion for the geometric entities from k + 1 to m. Note that if atransformation is geometry-invariant, its inverse is also a geometry-invariant motion. Thus,from the previous equation T ′ = T ′′i T , we have that the applied motion T = T′′−1T′ isa composite of two geometry-invariant motions. If geometry-invariant motions are com-posited with rigid-body motions, the resulting motions obviously preserve the model shape,which concludes the proof.139
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Variational direct modeling for computer-aided design Qiang, Zou 2019
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Item Metadata
- Media
- 24-ubc_2019_september_zou_qiang.pdf [ 22.14MB ]
- Metadata
- JSON: 24-1.0379562.json
- JSON-LD: 24-1.0379562-ld.json
- RDF/XML (Pretty): 24-1.0379562-rdf.xml
- RDF/JSON: 24-1.0379562-rdf.json
- Turtle: 24-1.0379562-turtle.txt
- N-Triples: 24-1.0379562-rdf-ntriples.txt
- Original Record: 24-1.0379562-source.json
- Full Text
- 24-1.0379562-fulltext.txt
- Citation
- 24-1.0379562.ris
Full Text
Citation Scheme:
Usage Statistics
Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
async >
Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url: