撥叉零件的機械加工工藝規(guī)程及銑削86左側端面工裝夾具設計,撥叉零件的機械加工工藝規(guī)程及銑削86左側端面工裝夾具設計,零件,機械,加工,工藝,規(guī)程,銑削,86,左側,端面,工裝,夾具,設計 ORIGINAL ARTICLEFast collision detection approach to facilitate interactivemodular fixture assembly design in a virtual environmentGaoliang Peng&Xin Hou&Chong Wu&Tianguo Jin&Xutang ZhangReceived: 27 May 2008 /Accepted: 21 April 2009 /Published online: 9 May 2009#Springer-Verlag London Limited 2009Abstract Collision detection is a fundamental componentto simulate realistic and natural object behaviors in virtualreality-based system. In this paper, a hybrid method ofspace decomposition and bounding volume approach ispresented to assist modular fixture assembly design in avirtual environment. Based on characteristics of modularfixture, a novel space decomposition methodology at objectlevel is proposed, which is achieved by automaticallypartitioning the checking space into cells according to theoriented bounding boxes of assembled elements after theinitial approximate collision detection using the intersectionchecking method based on separation plane-based bound-ing box. Then the pairs of candidate objects are determinedfor narrow phase exact polygons overlap tests. Results fromseveral performance tests on modular fixture design systemshow that an important advantage of this proposed methodcompared with other universal algorithms is its simpleinformation representation and low preprocessing cost.Keywords Collisiondetection.Virtualassembly.Modularfixture.Spacedecomposition.Boundingvolume1 IntroductionVirtual reality (VR) became a very common mean duringthe development of the industrial products. The aidprovided by VR is noticeable, since the user can interactwith the virtual prototype in a very natural way 13. VRholds great potential in manufacturing applications to solveproblems before fatal mistakes occur in practical manufac-turing so that great costs are prevented. VR applicationshave gained increasing attention internationally.Fixture design takes a significant part of the total time(cost) necessary for technical and technological productionpreparation. The design of a fixture is a highly complex andintuitive process, which requires knowledge and experience4. Modular fixtures are one of the important aspects ofmanufacturing. Proper fixture design is crucial to productquality with regard to the precision, accuracy, and finish ofthe machined part. Modular fixture is a system ofinterchangeable and highly standardized componentsdesigned to securely and accurately position, hold, andsupport the workpiece throughout the machining process5. Traditionally, fixture designers rely on experiences oruse trial-and-error methods to determine an appropriatefixture scheme.Since the potentially high degree of “reality” experi-enced in a virtual environment (VE), the VR-based modularfixture design has the advantages of designing a fixture in anatural and instructive manner, providing better match tothe working conditions, reducing lead-time, and generallyproviding a significant enhancement to fixture productivityand economy 6. In order to achieve this goal, the VRsystem must be able to simulate realistic and natural objectbehaviors. First of all, as a basic requirement of fixturedesign, there should be no collision between fixture,component and machine tool 7, 8; the objects notInt J Adv Manuf Technol (2010) 46:315328DOI 10.1007/s00170-009-2073-0G. Peng (*):X. Hou:T. Jin:X. ZhangSchool of Mechanical and Electrical Engineering,Harbin Institute of Technology,Harbin, Chinae-mail: C. WuSchool of Management, Harbin Institute of Technology,Harbin, Chinapenetrating into others must be guaranteed. Therefore, a fastinteractive collision detection (CD) algorithm is fundamen-tal in such a VR system.However, collision checking for a complex VE iscomputationally intensive. Researchers have addressedsome “universal” algorithms to reduce the computationalcosts. But these algorithms often need auxiliary datastructures and require intensive preprocessing time cost.In addition, the implementation of such algorithm is verycomplicated. Therefore, based on the well study of modularfixture characteristics and practical requirements, wedevelop a “special” CD algorithm to keep the associatedcosts as low as possible for VR-based modular fixtureassembly design.The paper is organized as follows. A review of relatedwork of the existing CD algorithms is presented inSection 2. Section 3 gives an overview of our proposedalgorithm. In Section 4, we describe the space subdivisionmodel used in our algorithm. Section 5 provides the detailsabout the broad phase of our proposed algorithm, in whichirrelevant objects are discarded and a set of objects that canpossibly collide are determined. The narrow phase for exactpolygon based overlap tests is described in Section 6.Section 7 presents some experimental results of ouralgorithm, and finally, in Section 8, we give concludingremarks and outline directions for future extensions of thiswork.2 Related workDuring the past few years, a great deal of effort has beenmade to solve the CD problem for various types ofinteractive 3D graphics and scenarios. For a workspacefilled with n objects, the most obvious problem is the O(n2)problem of detecting collisions between all objects, whichis time consuming and not bearable if the number n is large.Thus, some necessary techniques are needed to reduce thecomputational costs. Generally, a CD algorithm consists oftwo main steps, namely broad phase and narrow phase 9.The first phase aims to filter out pairs of objects which areimpossible to interact and determine which objects in theentire workspace potentially interact. The second phase isto perform a more accurate test to identify collisionbetween those selected object parts in the first phase,moreover if necessary, to find the pairs of contactingprimitive geometric elements (polygons), and to calculatethe overlapping distance.For a CD algorithm, it is critical to reduce the number ofpairs of objects or primitives that need to be checked.Therefore, a number of different techniques have been usedto make coarse grain detection, among which spacedecomposition and bounding volumes is most popular.In space decomposition methods, the environment issubdivided into space grids using hierarchical spacesubdivision. Objects in the environment are clusteredhierarchically according to the regions that they fall into.These objects are then checked for intersection by testingfor overlapping grid cells exploiting spatial partitioningmethods like Octrees 10, 11, BSP-trees 12, k-d trees13, etc. Using such decompositions in a hierarchicalmanner can further speed up the collision detection processbut leads to extremely high storage requirements.Bounding volume (BV) approach is used in previouscomputer graphics algorithms to speed up computation andrendering process. The BVof a geometric object is a simplevolume enclosing the object. Typically, BV types are axis-aligned boxes (AABBs) 14, spheres 15, and orientedbounding boxes (OBB) 16.Since AABBs method is simple to compute and allowsefficient overlap queries, it is often used in hierarchy, but italso may be a particularly poor approximation of the setthat they bound, leaving large “empty corners.” Thesystems utilizing AABBS include I-COLLIDE 17, Q-COLLIDE 18, and SOLID 19, etc.Bounding sphere is another natural choice to approxi-mate an object as it is particularly simple to test pairs foroverlap, and the update for a moving object is trivial.However, spheres are similar to AABBs as they can be poorapproximations to the convex hull of contained objects.In comparison, an OBB is a rectangular bounding box atarbitrary orientations in 3D space. In an ideal case, theOBB can be repositioned such that it is able to enclose anobject as tightly as possible. In other words, the OBB is thesmallest possible bounding box of arbitrary orientation thatcan enclose the geometry in question. This approach is verygood at performing fast rejection tests. A system calledRAPID 20 for interference detection based on OBB hasbeen built, which approximates geometry better thanAABBs. The shortcomings of OBB-tree against sphere treelie in its slowness to update and orientation sensitive 9.Most CD-related researches are involved in “universal”algorithms, and few literatures are found to develop CDapproach in a special application like virtual assembly.Actually, a fast and interactive collision detection algorithmis fundamental to a virtual assembly environment, whichallows designers to move parts or components to performassembly and disassembly operations.Figueiredo 21 presented a faster algorithm for thebroad and narrow phases of the collision detectionalgorithm of determining precise collisions between surfa-ces of 3D assembly models in virtual prototype environ-ments. The algorithm used the overlapping AABB and theR-tree data structure to improve performance in both thebroad and narrow phases of the collision detection. Thisapproach is for such a VE with objects dispersed in the316Int J Adv Manuf Technol (2010) 46:315328space. In addition, the R-tree data structure is very memoryintensive.Stephane 22 worked on continuous collision detectionmethods and constraints to deal with rigid polyhedralobjects for desktop virtual prototyping. Whereas such a4D method is only useful for handling the path of knownmoving objects. Especially, the algorithm is so computa-tionally intensive that it has to run on high-end computers.Collision detection is a critical problem in multi-axisnumerical control (NC) machining with complex machiningenvironments. There has been much previous work oninterference detection and avoidance in NC machiningsimulation. Wang 23 developed a graphics-assistedcollision detection approach for multi-axis NC machining.In this method, a combination of machining environmentculling and a two-phase collision detection strategy wasused.Researches surveyed above provided various efficienttechniques to carry out collision detection for polygonalmodels. However, these popular algorithms aimed atgeneral polygonal models, most of which need expensivepretreatments or large system memory or both of them inorder to improve the performance and meet real-timerequirements. Therefore, when these algorithms are utilizedin desktop VR application system such as modular fixturedesign, the requirement of real time cannot be wellguaranteed.Few CD researches can be found in the area ofcomputer-aided fixture design. Hu 24 presented analgorithm of fast interference checking between themachining tool and fixture units, as well as between fixtureunits, to replace the visually checked method. Moreover, inKumars work 25, in order to automate interference-freemodular fixture assembly design, the machining interferencedetection is accomplished through the use of cutter-sweptsolid based on cutter-swept volume approach. However,these algorithms are only capable of static interferencechecking and applied in CAD software packages.The research presented in this paper makes a solution tothese issues by addressing a “special” collision detectionalgorithm for VR-based modular fixture design. Theproposed algorithm uses the hybrid approach of spacedecomposition and bounding volume method to get highperformance.3 Algorithm overview3.1 Requirements for proposed algorithmWe aimed to develop a desktop VR-based modular fixtureassembly design system, in which the designer can selectsuitable fixture elements and put them together to generatea fixture structure, like “building blocks.” Without physicalfixture elements, he/she can test different structure schemesand finally design a feasible fixture configuration that meetsthe fixturing function requirements. In order to retain highdegree of “reality” in engineering application, there arethree main requirements for a CD algorithm to performmodular fixture configuration design:1.Precise and fast: During the simulation of assemblyand disassembly operations, finding precise collisionsis an important task for achieving realistic behavior26. When the user interactively assembles a part or acomponent, the “flying” object may collide with staticmodels, thus the system must find out the “colliding”event immediately. The interval between two checkingpoints should be near enough to achieve betterperformance. Otherwise, when objects move very fast,they may appear before checking, which will reduce theimmersive feelings. Therefore, the proposed systemcarries out a CD checking task in each rendering loopof VE. In addition, in modular fixture assembly designprocess, the designer selects elements and assemblesthem to right position or disassembles them to changethe fixture configuration. Once an element is assembledor disassembled, the “static” environment models areupdated. Accordingly, the CD checking model needsrestructure. So the preprocess should not take too long;otherwise, the performance of proposed system will beimpaired severely for certain “smooth feel” cannot beachieved.2.Low system requirements: Finding collisions in a 3Denvironment is time-consuming. In some cases, it caneasily consume up to 50% of the total run time 21.However, in modular fixture design workspace, thereare some other time-consuming tasks, such as designprocess control and reasoning, automatic geometricconstraints recognition and solving, etc. In spite of thecomplexity of the 3D virtual prototypes due tothousands of polygons, the designed CD checkingprocedure must be done in real time with relativelylow system resource demands.3.Low hardware cost: In order to achieve wider engi-neering applications, the proposed modular fixtureassembly system is designed to run on common PClike popular CAD commercial software. Althoughmuch research has engaged in developing hardware-accelerated CD algorithms, which utilize special graph-ic hardware, like graphics processing unit, to deal withthe computing collisions, thus the systems CPU can befreed. Nevertheless, we did not plan to adopt this kindof method and optimize performance only fromsoftware implementation. The objective of this researchis to develop a CD algorithmInt J Adv Manuf Technol (2010) 46:315328317Taking into account all above requirements, unfortunate-ly, these objectives usually are in conflict. To meet theprecise demand, we must increase checking frequencywhich will enormously increase the computational com-plexity and the memory bandwidth requirement. So, howcan a balance be reached with regard to these? In otherwords, how can the utilization of system resources beminimized yet the performance optimized without the helpof extra hardware? It is the start point of our algorithm.3.2 Modular fixture analysisThe objective of this research is to develop a CD algorithmfor assisting in modular fixture assembly design operationsin VE. To simplify the algorithm and to gain highperformance, the characteristics of modular fixture shouldbe well studied.1.Process of modular fixture assembly design: The tasksof modular fixture assembly design are to select theproper fixture elements and assemble them to aconfiguration one by one according to the designedfixturing plan. Thus, the CD problem in VR-basedmodular fixture assembly design can be stated as: theintersection checking between one moving object(assembling element or unit) with the static environ-ment objects (assembled elements) at discrete time.2.Fixture element shape: Modular fixture elements withregular shape can be classified into three types, namely,block, cylinder, and block-cylinder 27. Other compli-cated assembly units can be regarded as compositionsof these three meta-elements. It is well known that theOBB is tighter than the AABB and sphere. Moreover,when an object changes its position and orientation inVE, its OBB does not need to rebuild. Therefore, wecan construct OBBs of modular fixture elements off-line and store them as attributes of element models.During the assembly design process, such attributes canbe retrieved directly; thus, complex work for construct-ing bounding volume in run time can be avoided.3.Fixture element layout: A modular fixture system oftenconsists of supporting units, locating units, and clamp-ing units. These units lie out on the base plate andprovide corresponding functions at certain positions. AsFig. 1 shows, in the projection view parallel to the baseplate, the units are arranged in some kind of “regions.”In addition, to meet the height requirement of fixturingpoint, a unit often utilizes a number of supportingelements severed as blocking up objects. Therefore, atthe direction perpendicular to the baseplate, theelements lay out hierarchically. Accordingly, we candecompose the space with regard to elements layoutfeature.3.3 Algorithm flowchartAccording to the above characteristics of modular fixture,the proposed algorithm is designed to decrease thecomplexity and meet the requirements of VR-basedmodular fixture assembly design. As Fig. 2 shows, at thepreprocessing stage, once an element or component isassembled or disassembled, the Layer-based ProjectionModel (LPM) is established in terms of OBBs of thoseassembled elements. Such an LPM is used for the CDchecking when a new object is assembled.Just like the traditional CD method, proposed algorithmconsists of two steps, namely, broad phase and narrowphase. The broad phase is responsible for filtering pairs ofobjects that cannot intersect. At this stage, it determinespairs of objects in the same subspace, whose silhouettes inLPM overlap and their OBBs intersect. These pairs ofobjects are candidates for exact polygon-based collisiontests in the next narrow phase. During the broad phase, the(a)default view(b)downtown view Fig. 1 Modular fixture structure318Int J Adv Manuf Technol (2010) 46:315328test may cease at any time if no intersection is found, whichhelps to reject many noncollision or trivial collision cases.In the narrow phase, the collision detection algorithm willcalculate detailed intersection between geometrical meshesof the objects. If no intersection polygons are found, thecollide will not occur, and the active object can keep onmoving. Otherwise, whenever overlaps are detected, relatedreactions (for proposed system, it highlights objects anddoes back-tracking) may arise.4 Space decomposition for identifyingneighboring objectsConsidering the fact that most regions of the “universe” areoccupied by only a few objects or left empty, it means thatcollision only happens among objects that are close enough.So we can use this phenomenon to filter out most of “far-away” objects. Space decomposition is the commonapproach to be used for this intention. It first splits the“universe” into cells and then does further collision tests forobjects in the same cell. In order to keep generality, most ofexisting space subdivision approaches are based on a set ofpolygons. Such a “polygon-oriented” approach is socomputationally intensive to deal with large number ofpolygons. Since standard components are almost withrelatively regular shapes, we plan to develop an “object-oriented” space decomposition method.4.1 Space decomposition modelAfter the baseplate is arranged, the remaining work is toassemble the fixture elements or units onto the baseplate.As the assembling elements or units move to the assembledposition, collisions may happen between active object andthe assembled elements that have been fixed in the spacearound the baseplate. Hence, the CD checking processneeds start-up only after the active object enters into thisspace. Firstly, as Fig. 3a shows, we define a valid collisionspace noted as , which is a cuboid whose bottom face isdecided by the baseplate, and its height would change alongwith the assembling operation. The top of is determinedby the vertex coordinates of OBBs. is defined toguarantee that all the assembled elements are inside.After the checking space is identified, we need todecompose the space into a number of cells. How can weorganize these cells into proper structure and represent therelevant information to facilitate interaction checking? Inliterature, some