Fast collision detection approach to facilitate interactive.pdf
气门摇杆轴支座机械加工工艺规程及铣φ32外圆端面夹具设计【铣φ32外圆端面】
收藏
资源目录
压缩包内文档预览：
编号：205528561
类型：共享资源
大小：933.55KB
格式：ZIP
上传时间：2022-03-21
上传人：221589****qq.com
认证信息
个人认证
李**（实名认证）
湖南
IP属地：湖南
15
积分
- 关 键 词：
-
铣φ32外圆端面
气门
摇杆
支座
机械
加工
工艺
规程
32
端面
夹具
设计
- 资源描述：
-
气门摇杆轴支座机械加工工艺规程及铣φ32外圆端面夹具设计【铣φ32外圆端面】,铣φ32外圆端面,气门,摇杆,支座,机械,加工,工艺,规程,32,端面,夹具,设计
- 内容简介：
-
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: pgl7782C. 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 kinds of hierarchical data structure, like R-tree structure 21, have been used to help find neighbors.In complex environment with lots of dispersed objects, thiscomplicated data structure is useful. For modular fixtureassembly design, the element models are relatively central-ized, and the number of objects is not so much. Conse-quently, the complex data structure is not needed asconstructing such a model is time-consuming.We propose a novel data model to represent partition ofthe checking space. The model gets the advantages of easyintersection tests and simple information representation. AsFig. 3b shows, the checking space is decomposed intoseveral layers along the axis vertical to the baseplate. Eachlayer can be represented as a 4-turple Li=h1, h2, V, B,where h1is the start height, h2is the end height, V is the gridinformation of this layer, and B describes the projection ofelements OBBs belonging to this layer.For each layer, the stored information is illustrated inFig. 3c. Easy to overlap checking, we orthogonally projectthe bounding box onto the x, y axis (convenient forillustration and does not lose universality). Then, withthese projections, intervals are formed on each axis for eachobject. We construct one list for each axis. Each listcontains the coordinate value of the endpoints of theinterval on the corresponding axis. By comparing theendpoints, the corresponding pair of objects that are incontact may be determined. If the intervals do not overlap,the corresponding two objects are not in contact and can bediscarded.Fig. 2 Overview of collision detection algorithmInt J Adv Manuf Technol (2010) 46:3153283194.2 Space decomposition model constructionThe above section gives the representation of our spacedecomposition model; this section will discuss how toconstruct and reconstruct this model. Most existing spacepartition methods decompose an entire space into cells interms of primitive geometric elements (polygons), bycomputing the position of each polygon and assigningthem into corresponding cells, which are often organizedinto a hierarchical data structure. Despite the data structureremarkably speeding up the CD checking procedure, theestablishment of such structure is a complex process andtime-consuming. In a situation that the objects in anenvironment are uniform or the environment models donot change frequently, the cost for preprocessing may bebearable. However, during the modular fixture virtualassembly process, objects within the checking space arechanged with time. Therefore, the space composition modelmust be rebuilt once a fixture element is assembled.To reduce preprocessing time, we propose an “element”-based space decomposition method instead of calculationbased on scattered “polygons.” That is, the space model isconstructed with regard to fixture element models. Thedetailed process of construction follows three main steps:1.Layers divisionLayers division is to find several separation planesorthogonal with z axis to divide the checking space into aset of layers. As a result, the assembled fixture elementswould distribute into different layers. During the interactionchecking, only the elements of the same layer with theassembling element will be taken for consideration.It is a good idea to divide space without cutting objects,but in general, this cannot be avoided. Nevertheless, wefind the separation planes among those across the top andbottom face of OBBs of assembled elements. Moreover, theheight of each layer should be taller than the height ofassembling elements OBB. The orthographic projectionsof all OBBs of assembled elements yield rectangles orhexagons. If these hexagons project onto z axis, it wouldgenerate a number of single intervals. We record and sorttheir endpoints and determine which point is the “separa-tion point.” A simple program can realize this function. Theprinciple is to try to make one layer to contain objects asmuch as possible without cutting them.2.OBBs projectionAccording to the results of layers division, in theorthographic view of z axis, we get the orthographicprojections of OBBs in each layer (Fig. 4). As Fig. 5shows, these may yield three types of silhouettes. Becausemost of the assembled elements are located perpendicular tothe baseplate, most of these silhouettes are rectangles (asbox A and B). But for assembling element, because itsposition and orientation will change timely along with thevirtual hand, its silhouette is a polygon with at most sixedges (as box C).After box projection, each generated silhouette willproject onto two axes of the projection plane. Under thisprojection, each silhouette forms two intervals, each one onChecking spacexP1P2P3yV33x1x2y1y2x1(p1)x2(p )(a) Checking space define(b) Space decomposition(c) Information representation of a layerFig. 3 LPM representation320Int J Adv Manuf Technol (2010) 46:315328each axis. The endpoints of these intervals are recorded inLPM.3.Grids subdivisionAfter the projection of each OBB is finished, the nextstep is dividing the projection plane into grids. We try toguarantee that each OBBs silhouette is inside one grid.And the width and length of each grid are larger than that ofthe assembling element. Figure 5 shows the process of griddivision.Through the above procedure, the division on OX axis isfinished. Then we can take the OY axis division with theabove algorithm. Finally, grid division of a projection planeof a layer is completed.By repeating the procedures of OBBs projection and gridsubdivision for all layers, the space composition model isfinally established. From the above discussion, we can seethat the process is very simple and the information can bestored for model rebuilding. When a new object isassembled, update of such a model just needs to add theprojection of new OBB and to repeat the divisionprocedure. Moreover, in some situation, especially whenmost elements are assembled, the rebuilding of spacedecomposition model can be done by adding the newOBB information in it.5 Broad phase: potential collide candidates findingThis section discusses the broad phase of the proposed CDalgorithm, which is responsible for finding out potentialcandidates for further exact checking. Such a filteringprocedure consists of two steps: silhouettes overlap check-ing and OBBs intersection test. During the test procedure,the collision detection may cease any time if no intersectionis found. This procedure can be considered as an initialcollision detection, which helps to reject many noncollisionor trivial collision cases.5.1 Approximate tests by silhouettes overlap checkingOnce the preprocessing stage is completed and the LPMdata structure is constructed, we initiate checking procedureto identify which objects are potentially interacting with theactive assembling model (Fig. 6). When the active object isentering into the checking space, at each sample time, theposition and orientation of active objects OBB are updatedand projected onto the LPM. We first determine what layerthe active object has been entered, in terms of the vertex ofits OBB. Then we project its OBB, the assembled objects toconstruct the LPM, onto the corresponding axes. So we cando overlap checking in terms of the intervals on the axes.Figure 7 illustrates how to judge if the two projectionsilhouettes are interacting.Situations (a) and (b) can be treated easily by comparingthe endpoints of intervals respectively, while situation (c)needs further complex calculation in terms of the edges ofthe two silhouettes. Because at this stage, we only carry outADCBEXXXXFOOOOOBB silhouetteprojection intervaldivision pointadjustcombinationcombinationbcdFig. 5 Division of x axis of projection plane: (a) project the OBBsilhouettes to axis OX and generate a set of intervals, (b) combine thegenerated intervals according to their endpoints, (c) subdivide the axisOX by adding some division points between the endpoints of leftintervals, (d) adjust the subdivision zone by combing the shortintervals in terms of the longest axis of OBB of assembling elementSilhouetteASilhouetteBSilhouetteCOrthographic projection planeFig. 4 The silhouettes of OBBin orthographic projection planeInt J Adv Manuf Technol (2010) 46:315328321approximate tests to identify the inferring contact objects,to simplify the process, only the first two situations areconsidered. If the intervals on the two axes are alloverlapped, we regard the two projection silhouettes areoverlapped. Further calculation about situation (c) is carriedout in the next stage.5.2 OBBs intersection testAt this stage, we further filter out pairs of candidate objectsthat cannot intersect. It determines pairs of objectsidentified in the first step, whose bounding volumesoverlap. These pairs of objects are candidates for exactcollision detection in the narrow phase.Generally, the interference algorithm typically spendsmost of its time testing pairs of OBBs for overlap. A simplealgorithm for testing the overlap status for two OBBsperforms 144 edge-face tests. In practice, it is an expensivetest. To perform the test, Gottschalk 16 presented amethod to find a “separating axis” for two boxes. Theirstrategy is to project the centers of the boxes onto the axisand compute the radii of the intervals. If the distancebetween the box centers projected onto the axis is greaterthan the sum of the radii, the intervals (and the boxes aswell) are disjointed. Although it provides a faster way forthe OBB intersection checking, such a “universal” methodhas to test 15 potential separating axes (three faces fromone box, three faces from the other box, and nine pair-wisecombinations of edges) for determining overlap status oftwo OBBs when the two boxes are exactly overlap.As mentioned earlier, the assembled fixture elements areregularly assigned onto the baseplate, which means most ofOBBs are parallel to the baseplate. Therefore, to achieve abetter performance, the algorithm proposed here uses theseparation plane-based method for OBB intersection check-ing. Comparing to the separation axis-based method, ourapproach is simple to implement since such a separationplane may easily be found just by testing vertex coordinate.Once such a plane is found, the boxes are surely to bedisjointed, so the remainder of tests is unnecessary.First of all, we introduce the principles of separationplane-based method 28. In general, for any two non-colliding convex polyhedrons, a separation plane existsbetween them which are either:1.Parallel to a face of the first polyhedron2.Parallel to a face of the second polyhedron3.Parallel to an edge of the first polyhedron and to anedge of the second oneBased on the principle of separation plane, we propose amethod for checking whether a separation plane is one ofthe existing three types. The first two types of plane can bechecked by simply comparing vertexes; to filter irrelevantcases early and to avoid complex computation, type 1 andtype 2 separation plane checking is carried out firstly, andthen the type 3 plane. The algorithm is described in detailas follows:1.Type 1 and type 2 separation plane checkingAs shown in Fig. 7, let C0be the World CoordinateSystem (WCS). Let C1and C2be the local WCS attached tobounding box B1and B2, respectively. And boxes B1and B2are axis-aligned relative to its local CS. Let faces set ofeach box befiji 1;2;.;6fg, fi=(ki, Li), whereki2?x;?y;?zfg is the vector of fi, Liis the distance betweenfiand the origin of local WCS. Let the vertex set bevj?j 1;2;.;8?. The transform matrix of C0to C1canbe represented as M(C0 C1). Then the detail procedure isas follows:Step1:Transform all vertex of B2into C1according toEq. 1.vjx0;y0;z0? vjx;y;z ? M C2! C0 ? M?1C1! C01C0C1C2P1P2v1v2v3v4v5v6v7v8Separation plane(p0)LiikfiFig. 7 Type 1 separation planexyoP1P2xyoP1P2xyoP1P2(a)(b)(c)Fig. 6 Three situations for two silhouettes overlap checking: a Thetwo silhouettes are not interacting if their intervals on at least one axisare not overlapping. b The two silhouettes are interacting when theirintervals on both two axes are overlapping. c The two silhouettes arenot intersecting but their intervals on both two axes are overlapping322Int J Adv Manuf Technol (2010) 46:315328Step2:To each face of B1, compare each vertex in termsof Eq. 2; if all vertexes satisfy this condition, itindicates that fiis the separation plane, and jump tostep 4. Otherwise, proceed to the next step.vj k!j Lik!j2 x;y;zfgvj k!j :3Step4:For 8vi2 V, if viare all outside of bj, it indicatesthat there has a separation plane between box Aand box B, and proceed to the next step.Otherwise, go back to step 3.Step5:End the algorithm and output the checking results.For every pair of object candidates for collision, theirOBB overlapping test is processed by using the aboveseparation plane-finding method. Once any type of separa-tion planes is found, the two OBBs will definitely notintersect. Thus, candidate pairs of objects whose OBBs donot overlap cannot intersect and are discarded.6 Narrow phase: exact polygon intersection checkingAt the broad phase, irrelevant objects are discarded, and aset of objects that possibly collide are determined. In thissection, the narrow phase of the hybrid algorithm isresponsible for determining exactly where the collisionoccurred with precise polygon intersect checking. For everypair of object candidates for collision, in order to preciselyfind whether two objects intersect, checking for collision ofevery pair of polygons of the corresponding objects isneeded. For two objects which have m and n polygons,respectively, it requires mn times polygon intersectionchecking. Intersecting two polygons is an expensivecomputational operation. In spite of most of the polygonsfiltering out at the broad phase, in order to gain fasterspeed, we make great effort to reduce the number ofchecking operations in the process for filtering polygons.Through analyzing of the modular fixture, it can befound that the fixture elements are often densely assignedby many locating holes and screw holes, which are used forpositioning and fixing when assembling. In our proposedsystem, the fixture element models are constructed in CADsoftware and then meshed. For those models, most of thepolygons belong to the nonplane surfaces. As shown inTable 1, the holes contain most of polygons for modularfixture element models.C0C1B1C2B2v1v2v4v5v6v7v8xyzbiSeparation plane(p0)(a) Spatial relationship of two boxes E562v3v4v5v6v7vB1B2xzC1pi(b) Projection of box in the plane C1(xy) Fig. 8 Type 2 separation planeInt J Adv Manuf Technol (2010) 46:315328323In the process of modular fixture assembly, besides theaxis-hole assembly, the collision often occurs betweenoutside faces of relevant objects. In our proposed system,axis-hole assembly adopts a kind of geometric constraint-based approach. That means the collision between axis andholes are not considered. So the polygons of holes are notthe intersecting candidates. Thus, the number of polygon-checking operations is sharply decreased.The intersection checking of two polygons is a commontopic and has been solved by different methods. Most VRdeveloping toolkits often provide this function, i.e., theWorldToolKit by sense 8 offers the function WTpoly_inter-sectpolygon, which can test whether the given two poly-gons intersect. In application development, we just utilizethis function directly, and the key point is to determine whatpolygons need to be checked. So the main work of thisresearch is involved in the broad phase to filter outthousands of irrelevant polygons and to find out just asmall number of pairs of candidate polygons for testing.7 Case study with the implemented softwareIn this section, we explain the implementation issues ofproposed CD algorithm and analyze its performance.7.1 Implemented softwareA useful system, named as Modular Fixture VirtualAssembly Design System (MF-VADS), has been imple-mented on a 2.4 GHz Pentium-IV PC, with 512 MB ofRAM. The system is developed with Visual C+ 6.0 andWorldToolKit and run using hardware such as: Intergraphgraphics station, 5DT dataglove, Flock of Birds. The GUIof MF-VADS is designed with the reference to the interfacelayouts of popular CAD software, which are widely usedby the industry, as shown in Fig. 9. This system has theadvantages of making the fixture design in a natural andinstructive manner, providing better match to the workingconditions, reducing lead time, and generally providing asignificant enhancement of fixture productivity and econo-my. In VE, the designer can select suitable fixture elements(a)(b)(c)Fig. 9 Snapshots of the proposed MF-VADS system: a the maininterface of proposed system, b management of modular fixtureelement database, c fixture elements assembly in virtual environmentTable 1 Comparison of the number of composited polygons of several fixture elementsElement Total Polygons Polygons of planes Polygons of holes Others 14604769269120 1116558 558 0 700 257 391 52 324Int J Adv Manuf Technol (2010) 46:315328and put them together to generate a fixture structure just as“building block” process. Without physical fixture ele-ments, he/she can try on different structure schemes andfinally design a feasible fixture configuration to meet thefixturing function requirements.7.2 Test cases and performance analysisAs shown in Fig. 10, four testing scenarios have beencreated to test our algorithm in comparison with otherrelated algorithms like SOLID 29 and RAPID 20. Thetime cost for collision detection at each iteration and theaverage time cost for collision detections among 1,000iterations are recorded.Table 2 shows the performance statistics of our algo-rithm in comparison with SOLID and RAPID. For each testscenario, we recorded the number of the checked overlapbounding box pairs and triangle pairs during the checkingprocess, respectively. We can see that when the actualcolliding seldom occurs, our algorithm achieves betterperformance (can filter most potential number of boundingboxes and triangle pairs overlap checking at the broad(a)(b) (c) (d) moving part moving partmoving partmoving partFig. 10 Several CD test experiments: a a slot fixture system withstatic environment model containing 11,316 triangles and a movingnut containing 215 triangles, b a hole fixture system with staticenvironment model containing 31,296 triangles and a moving locatorcontaining 948 triangles, c a slot fixture system with staticenvironment model containing 18,004 triangles and a moving boltcontaining 220 triangles, d a slot fixture system with staticenvironment model containing 29,452 triangles and a movingrhombus pin containing 236 trianglesActual collidesScenario (a)Scenario (b)Scenario (c)Scenario (d)3248984524NbNpNbNpNbNpNbNpSOLID5,2731,271115,27340,271107,41233,71567,41213,715RAPID4,3271,91464,32718,31445,51314,34825,5133,348Ours1,2828961,1821,0961,0136,5431131,543Table 2 Cost compare ofcollision detection algorithmsNbis the number of boundingbox overlap tests, Npis thenumber of actual collidingtriangle pairsInt J Adv Manuf Technol (2010) 46:315328325phase). Generally, in interactive virtual assembly applica-tion, often a few collides may happen due to carelessoperations. According to the recorded overlap checkingelements, we also calculated the average collision detectiontime for each experiment. The comparison chart of the CDtime is shown in Fig. 11. We can reduce that the cost ofproposed method does not increase remarkably in terms ofthe polygon count, while the other two algorithms increaseda lot. Moreover, in scenario c (hole-based modular fixturesystem), we have observed more than three times perfor-mance improvement of our method over other twoalgorithms.From the result of above two experiments, we cansummarize the performance of proposed approach.1.Low memory requirements: Actually, the hierarchicalalgorithms exploit spatial coherence by divide-and-conquer techniques to find all neighbor objects to speedup the collision detection procedure. Unlimitedly, thesemethods need very large auxiliary data structures toorganize and store the related CD information. Forinstance, in hierarchical BV method, the data structureassociated with hierarchical CD is bounding box trees.Each node in such a tree is associated with a subset ofthe primitives of the object, together with a BV thatencloses this subset. So, in order to provide “optimal”BV trees, except the type, the size of single BV shouldbe small enough to enclose their associated set ofpolygons as tightly as possible. In most universalalgorithms, the hierarchies are built on polygon level.As a result, for a VE containing large numbers ofpolygons, the tree is often very complicated withthousands of nodes. For example, an OBB-node stores(at least) 18 floats. Therefore, even though thesemethods can speed up the collision detection process,they have extremely high storage requirements.In our approach, the LPM is built upon the object level.In modular fixture assembly design process, only dozens ofelements are involved, so very little information need to bestored in LPM. Therefore, the memory is saved to a greatextent comparing to the other memory-intensive universalalgorithms.2.Low preprocessing time cost: As mentioned before,most universal CD algorithms need auxiliary datastructures to speed up checking procedure. However,construction of these data structures is time consuming.For some “static” scenarios (the environment modelsare fixed and the active objects are unchangeable), thedata structures can be constructed in a preprocess stage;thus, the precomputation can be ignored.But for virtual assembly application, once an element isassembled or disassembled, the “static” environmentmodels are updated. Accordingly, the CD checking modelneeds to be restructured. Fortunately, in our approach, theLPM is simple and built on a few OBBs which are obtaineddirectly from element models. In addition, due to thespecialties of modular fixture, at most situations, the restruc-ture of LPM is simple and fast by projecting the new addedOBB onto corresponding axes. It can be concluded that thepreprocessing of proposed approach is time-saving. Com-paring to the universal algorithm, it is more feasible forpractical virtual assembly application.3.Easily interfacing with VR applications: The algorithmis fairly simple to implement and easy to integrate withpopular VR-development tools. As we know, a scene-graph is the most common data structure used torepresent objects in a VE. Objects are represented asnodes in the scenegraph, and the relationship betweenthe objects and the environment is described by theedges. So the objects and their composite polygons arewell represented and stored for VR visualization andinteraction. Most universal algorithms need additionalcollision detection model to facilitate CD checkingprocedure. All polygons in the scenarios are assignedand recorded in such models. As a result, the polygonsare stored twice, which is memory wasted.In our proposed approach, the simple LPM is based onobject level; that is, all polygons in VE are not reassignedand restored. The pretreatment phase and the broad filteringphase are independent of polygons. At the narrow phase,very potential candidates are selected for exact polygonpolygon intersection tests, which is the fundamentalfunction provided by VR tools. So our approach can easilyinterface with any VR development tools.020406080100120Average collision detection time (ms)SOLIDRAPIDOursFig. 11 The comparison chart of the CD time for test scenarios withdifferent algorithms326Int J Adv Manuf Technol (2010) 46:3153288 ConclusionsThis paper presents a “special” collision detection strategyfor interactive modular fixture assembly design in a virtualenvironment. The strategy works by detecting collisionsbetween two parts: a dynamic assembling element movingin the virtual environment and a static object defined as acollection of all other assembled objects in the space. Basedon the characteristics of modular fixture and practicalrequirements, a new object level space partition methodol-ogy, achieved by automatically partitioning the checkingspace into cells in terms of OBBs of assembled elements,was presented. Such a preprocessing work has theadvantages of simple information representation and caneasily be constructed compared to other universal algo-rithms which often need large auxiliary data structures toorganize and store the related information. In proposed CDmethod, a strategy of using two-phase collision detection isdeveloped in order to make the approach more efficient.The broad phase is responsible for finding potentialcandidates for further exact polygons based collision tests.In this stage, those pairs of objects that cannot intersect arefiltered out by silhouette overlap checking and further OBBintersect. In the narrow phase, the collision detectionalgorithm will calculate detailed intersection betweengeometrical meshes of the objects. From the results ofseveral performance experiments, the above method wasfound to provide real-time collide detection with goodperformance at the expense of time cost and storagerequirements.This proposed method has been implemented in our VR-based modular fixture assembly design system and workswell. Although this method is just applied in modularfixture design, we believe that our potential strategy isappropriate for coping with the CD problem of interactivegraphics in the mechanical engineering applications. Be-cause mechanical products often have regular shape com-pared to other scenarios, our future effort will concentrate onextending this meth
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
|
2:不支持迅雷下载,请使用浏览器下载
3:不支持QQ浏览器下载,请用其他浏览器
4:下载后的文档和图纸-无水印
5:文档经过压缩，下载后原文更清晰
|
川公网安备: 51019002004831号