algorithm - तीन जेएस मेष में समूह की कपाली त्रिकोण समूह का तरीका?




three.js computational-geometry (2)

आपका विचार काम करता है

मैंने एक कोण थ्रेशोल्ड जोड़ा है ताकि आप थोड़ा गैर-कोपलेदार स्थलाकृति को पकड़ सकें। मुझे एक अनिवार्य पुनरावर्ती समय के लिए अनुमति देने के लिए एक एंटेंट बनाना था। इसके बजाय मेष। यूज़रडेटा में खराबी हाशिये लगाने के लिए संशोधित किया जाना चाहिए।

// संपादित करें। मैंने क्लैम्प पैरामीटर का उपयोग करने के लिए क्लास को अपडेट किया है जो आपको अधिकतम एंजेल को मूल चेहरे को दबाना देता है जब सही पर सेट होता है जब झूठ पर सेट होता है तो यह प्रत्येक चेहरे को अगले चेहरे की तुलना करेगा।

faceUtils = function(){};
faceUtils.vertexHash = function(geometry){
  geometry.vertexHash = [];
  var faces = geometry.faces;
  var vLen = geometry.vertices.length;
  for(var i=0;i<vLen;i++){
    geometry.vertexHash[i] = [];
    for(var f in faces){
         if(faces[f].a == i || faces[f].b == i || faces[f].c == i){
            geometry.vertexHash[i].push(faces[f]);
       }
     }
   }
}

faceUtils.prototype.getCoplanar = function(maxAngle, geometry, face, clamp, out, originFace){
  if(clamp == undefined){
      clamp = true;
  }
  if(this.originFace == undefined){
    this.originFace = face;
  }
  if(this.pendingRecursive == undefined){
    this.pendingRecursive = 0;
  }
    this.result = out;
  if(out == undefined){
       this.result = {count:0};
  }
  if(geometry.vertexHash == undefined){
    faceUtils.vertexHash(geometry);
  }
  this.pendingRecursive++;
  var vertexes = ["a","b","c"];
  for (var i in vertexes){
    var vertexIndex = face[vertexes[i]];
    var adjacentFaces = geometry.vertexHash[vertexIndex];
    for(var a in adjacentFaces){
        var newface = adjacentFaces[a];
        var testF = this.originFace;
        if(clamp == false){
          testF = face
        }
        if(testF.normal.angleTo(newface.normal) * (180/ Math.PI) <= maxAngle){
          if(this.result["f"+newface.a+newface.b+newface.c] == undefined){
            this.result["f"+newface.a+newface.b+newface.c] = newface;
            this.result.count++;
            this.getCoplanar(maxAngle, geometry, newface, clamp, this.result, this.originFace);
          }
        }
    }
  }
  this.pendingRecursive--;

  if(this.pendingRecursive == 0 && this.onCoplanar != undefined){
    delete this.result.count;
    this.onCoplanar(this.result);
  }
}

उपयोग सरल है:

         var faceTools = new faceUtils();
         faceTools.onCoplanar = function(rfaces){
           for(var i in rfaces){
              rfaces[i].color.setHex(0xff0000);
              intersects[0].object.geometry.colorsNeedUpdate = true;
           }
         }
         //params: maxangle, geometry, picked face
         faceTools.getCoplanar(13, geometry, face);

मैंने किसी और के बेला को कक्षा जोड़ा और यह ठीक काम करता है http://jsfiddle.net/fnuaw44r/

क्लैंप विकल्प का उपयोग करने के लिए मैंने बेला को अद्यतन किया: http://jsfiddle.net/ta0g3mLc/

जैसा कि आप सुझाव देते हैं, मैं इसकी अत्यधिक अक्षमता की कल्पना करता हूं, लेकिन यह मेष पर निर्भर करता है। मैंने एक "लंबित अनुक्रमिक" चर जोड़ा है जब तक यह शून्य के बराबर नहीं है, तब तक आप एक जीआईएफ डाल सकते हैं और इसे हटा सकते हैं जब मान शून्य हो।

यह एक शुरुआती बिंदु वैसे भी है। मुझे यकीन है कि किसी चालाक ने चेहरे के माध्यम से टकराए बिना पाश के नेस्टेड

मैं एक मॉडलिंग टूल पर काम कर रहा हूं जो आपको सीधे मेष को हेरफेर करने देता है उदाहरण के लिए, आप एक चेहरे को पकड़ सकते हैं और इसे चारों ओर खींच सकते हैं "चेहरे" के उपयोगकर्ता की धारणा एक से अधिक कपाटदार त्रिकोण की हो सकती है। उदाहरण के लिए, घन के शीर्ष "चेहरे" वास्तव में दो त्रिकोण होंगे जो एक वर्ग के रूप में एक साथ खींचते हैं।

इसे पूरा करने के लिए, मैं खींचने के दौरान उपयोग करने के लिए किसी भी विशेष त्रिकोण को सभी समस्त, इकबाल चेहरे को इकट्ठा करना चाहता हूं। मैंने सरलीफाइज़र , साथ ही इस पोस्ट को उदाहरण के रूप में देखा है, लेकिन मैं अंतर्निहित त्रिकोणों को बनाए रखना चाहता हूं, उन्हें कम नहीं / निकालना चाहता हूं

अच्छे राजभाषा दिवसों में, आप किनारे के मॉडल अला मत्तया का निर्माण करते हैं , जहां आप आसन्न चेहरों को देखने के लिए प्रत्येक किनारे पर जा सकते हैं और नॉर्मल की जांच कर सकते हैं।

मैं उम्मीद कर रहा था कि वहां कुछ कोड पहले से लिखे गए हैं जो त्रिवेणी के लिए कहीं है कि समूह एक साथ मिलकर त्रिकोण त्रिकोण अगर मैं इसे खरोंच से लिखता हूं, तो सबसे अच्छा एल्गोरिथ्म मैं सोच सकता हूँ ओ (एन ^ 2), कुछ ऐसा है:

  1. सभी चेहरे के सभी कोने चलकर किनारों के हेश (दोनों दिशाएं) बनाएं प्रत्येक प्रविष्टि 2 चेहरे पॉइंटर्स की एक सरणी है एक बार जब एक मेष बनाया या संशोधित किया जाता है, तो आपको केवल यह चरण ही करना पड़ता है।
  2. जब उपयोगकर्ता हेरफेर करने के लिए एक चेहरे को चुनता है, तो रिक्त मूल्यांकन स्टैक बनाएं और उस स्टैक में चेहरा उठाएं। इसके अलावा, खाली समीपवर्ती चेहरा सरणी बनाएं।
  3. मूल्यांकन चेहरा स्टैक बंद करें, और उस चेहरे के किनारे चलना किनारों के किनारों के आस-पास सभी चेहरे को देखिए अगर चेहरे को तख्तियार करना है, तो उस चेहरे को स्टैक्ल पर स्टैक्स पर रखें और कॉप्लानार चेहरे सरणी में स्टोर करें।
  4. मूल्यांकन स्टैक खाली होने तक चरण 3-4 दोहराएं।

जब यह एल्गोरिथम खत्म होता है, तो आपके सामने से शुरू होने वाले चेहरे के साथ आप सभी चेहरों को समतल और आसन्न होना चाहिए। लेकिन यह अपेक्षाकृत मेरे लिए अपेक्षाकृत अक्षम है

किसी भी और सभी सुझाव / संकेतक का स्वागत किया!


मैंने एक समाधान कोडित किया है जो मेरे लिए काम करता है, मैं मूल रूप से पोस्ट किए गए प्रश्न में गोलियों की तर्ज पर, और वह पुनरावर्ती का उपयोग नहीं करता है शायद यह किसी के लिए उपयोगी होगा (नोट: मैं हैश और एरेज़ आदि के साथ सुविधा के लिए अंडरस्कोर का उपयोग करता हूं)

यह एल्गोरिथम पहले जाल कोने में मैपिंग जोड़ता है, जो सभी चेहरे सूचीबद्ध करते हैं जो प्रत्येक शीर्ष के हैं। वहां से, मैं एक विशेष चेहरे से शुरू कर सकता हूं, और तब सभी समीपवर्ती चेहरों को देखता हूं जो शुरुआती चेहरे (और वहां से चले जाते हैं) के साथ कम से कम एक शीर्ष को साझा करते हैं। अगर दो कोने साझा किए जाते हैं, तो ठीक है।

var COPLANAR_ANGLE_TOLERANCE = .1; // degrees, not radians
var RAD_TO_DEG = 180 / Math.PI;
var FACELEN = 3; // meshes have triangles by default

function checkCoplanarity(f1, f2) {
  return ((f1.normal.angleTo(f2.normal) * RAD_TO_DEG) <= COPLANAR_ANGLE_TOLERANCE);
}

function assignVertexFaceHashes(geometry) {
  var vertices = geometry.vertices;
  var faces = geometry.faces, face;
  var theVertex;
  for (var faceIndex in faces) {
    face = geometry.faces[faceIndex];
    for (var vertIndex of [face.a, face.b, face.c]) {
      theVertex = vertices[vertIndex];
      if (!theVertex.hasOwnProperty('inFaces')) {
        theVertex.inFaces = {};
      }
      theVertex.inFaces[faceIndex] = true;
    }
  }
}


function findCoplanarAdjacentFaces(startFaceIndex, geometry) {
  var adjoiningFaceIndexes;
  var coplanarAdjacentFaces = {};
  var coplanarAdjacentVertices = {};
  var examQueue = [];
  var examined = {};
  var examFace, examFaceIndex;
  var adjoiningFace, adjoiningFaceIndex;
  var faces = geometry.faces;
  var vertices = geometry.vertices;
  var startFace = faces[startFaceIndex];
  examQueue.push(startFaceIndex);
  // include the start face as a coplanar face
  coplanarAdjacentVertices[startFace.a] = true;
  coplanarAdjacentVertices[startFace.b] = true;
  coplanarAdjacentVertices[startFace.c] = true;
  coplanarAdjacentFaces[startFaceIndex] = true; 
  // Map vertices back to all faces they belong to
  assignVertexFaceHashes(geometry);

  while (examQueue.length > 0) {
    examFaceIndex = examQueue.pop();
    examFace = faces[examFaceIndex];
    // console.log('examQueue:', examQueue.length);
    adjoiningFaceIndexes = [];
    for (var vertIndex of [examFace.a, examFace.b, examFace.c]) {
      adjoiningFaceIndexes = _.union(adjoiningFaceIndexes, _.map(_.keys(vertices[vertIndex].inFaces), function(c) { return parseInt(c); }));
    }
    //console.log('adjoiningFaceIndexes:', adjoiningFaceIndexes);
    for (adjoiningFaceIndex of adjoiningFaceIndexes) {
      //console.log('Examining adjoining face index:', adjoiningFaceIndex);
      if (!examined.hasOwnProperty(adjoiningFaceIndex)) {
        if ((adjoiningFaceIndex != examFaceIndex) && (!coplanarAdjacentFaces.hasOwnProperty(adjoiningFaceIndex))) {
          //console.log('adjoiningFaceIndex:', adjoiningFaceIndex);
          adjoiningFace = faces[adjoiningFaceIndex];
          if (checkCoplanarity(examFace, adjoiningFace)) {
            var overlap1 = [adjoiningFace.a, adjoiningFace.b, adjoiningFace.c];
            var overlap2 = [examFace.a, examFace.b, examFace.c];
            var vertsInCommon = _.intersection(overlap1, overlap2);
            // Check for vertices in common. If any vertices are in comment, these coplanar faces touch at least one vertex.
            if (vertsInCommon.length > 0) {
              //console.log('Pushing adjoining face due to vertices in common:', adjoiningFaceIndex);
              coplanarAdjacentFaces[adjoiningFaceIndex] = true;
              examQueue.push(adjoiningFaceIndex);
              coplanarAdjacentVertices[adjoiningFace.a] = true;
              coplanarAdjacentVertices[adjoiningFace.b] = true;
              coplanarAdjacentVertices[adjoiningFace.c] = true;
            } else {
              // it's possible the adjoining face only touches vertices to the middle of edges, so check for that.
              edgeIntersectExam:
              for (var i = 0; i < FACELEN; ++i) {
                adjoinP1 = overlap1[i];
                adjoinP2 = overlap1[(i + 1) % FACELEN];
                for (var j = 0; j < FACELEN; ++j) {
                  splitPoint = distToSegmentSquared3d(vertices[overlap2[j]], vertices[adjoinP1], vertices[adjoinP2]);
                  if (splitPoint.distance < POINT_ON_LINE_TOLERANCE) {
                    console.log('adding adjoining face due to edge intersection:', adjoiningFaceIndex);
                    console.log('j=', j, 'Source face:', examFaceIndex, examFace, 'We found split point on adjoining face index:', adjoiningFaceIndex, adjoiningFace);
                    coplanarAdjacentFaces[adjoiningFaceIndex] = true;
                    examQueue.push(adjoiningFaceIndex);
                    coplanarAdjacentVertices[adjoiningFace.a] = true;
                    coplanarAdjacentVertices[adjoiningFace.b] = true;
                    coplanarAdjacentVertices[adjoiningFace.c] = true;
                    break edgeIntersectExam;
                  }
                }
              }              
            }
          }
        }
      }
    }
    examined[examFaceIndex] = true;
  }

  return ({ faces: coplanarAdjacentFaces, vertices: coplanarAdjacentVertices });
}

function assignFacesToCoplanarGroups(csgPrimitive) {
  var geometry = csgPrimitive.geometry;
  var faceIndexList = _.mapObject(_.keys(geometry.faces), function() { return true; });
  var processedFaces = {};
  var coplanarFaces;
  var faces = geometry.faces;
  var intIndex;
  var coplanarGroupMax;
  var coplanarGroups = [];
  for (var processFaceIndex in faceIndexList) {
    intIndex = parseInt(processFaceIndex);
    if (!processedFaces.hasOwnProperty(intIndex)) {
      coplanars = findCoplanarAdjacentFaces(processFaceIndex, geometry);
      coplanarGroups.push({ faces: coplanars.faces, vertices: coplanars.vertices });
      coplanarGroupMax = coplanarGroups.length - 1;
      for (var groupedFaceIndex in coplanars.faces) {
        faces[groupedFaceIndex].coplanarGroupIndex = coplanarGroupMax;
        faces[groupedFaceIndex].color.setHex(0x0000ff); // just to help see the results
        processedFaces[groupedFaceIndex] = true;
      }
    }
  }
  geometry.coplanarGroups = coplanarGroups;
  geometry.colorsNeedUpdate = true;
}

function assignFacesToAllCoplanarGroups() {
  var now = new Date();
  var startTime = now.getTime();
  for (var csgPrimitive of csgPrimitives.children) {
    assignFacesToCoplanarGroups(csgPrimitive);
  }
  var later = new Date();
  var duration = later.getTime() - startTime;
  console.log('Done assigning faces to coplanar groups in:', duration, 'ms');
}

यहाँ मैं इसे कैसे उपयोग करता हूं I मेरे पास मेस (सरगर्मी) है, क्योंकि वे तीन सीएसजी.जेस से आते हैं । मैं प्रत्येक आदिम के लिए कपालीदार चेहरे समूहों की गणना करता हूं और उन्हें प्रत्येक आदिम की ज्यामिति पर रखता हूं।

function assignFacesToAllCoplanarGroups() {
  var now = new Date();
  var startTime = now.getTime();
  for (var csgPrimitive of csgPrimitives.children) {
    assignFacesToCoplanarGroups(csgPrimitive);
  }
  var later = new Date();
  var duration = later.getTime() - startTime;
  console.log('Done assigning faces to coplanar groups in:', duration, 'ms');
}

प्रत्येक परिणामस्वरूप कपाही समूह में कपाली चेहरों की एक सरणी होती है और उन चेहरे द्वारा उपयोग किए जाने वाले अद्वितीय कोने के एक सरणी होते हैं शीर्ष सरणियों का उपयोग करना, अब मैं वेक्टर 3.एड () फ़ंक्शन को बसाने के द्वारा एक बार में एक जाल में सभी कपाटदार चेहरे को पकड़ कर खींच कर खींच सकता हूं।

इस काम का कारण नीचे स्क्रीनशॉट द्वारा स्पष्ट किया जा सकता है दिखाया गया जाल बनाने के लिए, एक क्यूब तैयार किया गया था और उसके बाद ऊपर बताए गए सीएसजी लाइब्रेरी का उपयोग करके एक गोला बुलियन घटाया गया था।

  var box = new THREE.Mesh( new THREE.BoxGeometry( width, height, length ) );

  // CSG GEOMETRY
  cube_bsp = new ThreeBSP( box );

  var cutgeo = new THREE.SphereGeometry( 0.5,32,32 );

  // move geometry to where the cut should be
  var matrix = new THREE.Matrix4();
  matrix.setPosition( new THREE.Vector3(0.25, 0, 1.88) ); // NB: sphere does not intersect with cube
  cutgeo.applyMatrix( matrix );

  var sub =  new THREE.Mesh( cutgeo );
  var substract_bsp  = new ThreeBSP( sub );
  var subtract_bsp  = cube_bsp.subtract( substract_bsp );

  csgPrimitiveMesh = subtract_bsp.toMesh(); 

क्षेत्र काफी दूर है कि यह वास्तव में घन के साथ काटना नहीं करता है, लेकिन फिर भी, संचालन के बाद, घन में कई अतिरिक्त कपालीदार त्रिकोण होते हैं, फिर भी यह एक सुसंगत सीमा का प्रतिनिधित्व नहीं है। उदाहरण के लिए, जैसा कि आप आरेख में देख सकते हैं, कुछ त्रिकोण दूसरे त्रिभुज के किनारों के बीच स्पर्श करते हैं (कुछ उदाहरण लाल तीरों द्वारा इंगित किए जाते हैं)।

मैंने एक और एल्गोरिथ्म लिखा है जो त्रिकोण को इस तरह छूता है जब त्रिकोण को विभाजित करने का प्रयास करता है। एल्गोरिथम स्थिति को कुछ हद तक सुधार देता है:

लेकिन अभी भी अपूर्ण है क्योंकि सीएसजी लाइब्रेरी कभी-कभी त्रिकोण का उत्पादन करती है जो लगभग लाइनें हैं (दो कोने एक साथ बहुत करीब हैं), जिससे मेरे एल्गोरिदम फेंकने वाले गोल त्रुटियाँ पैदा हो रही हैं। यह भी अच्छी तरह से काम नहीं करता है अगर एक त्रिभुज किनारे का जाल में एक से अधिक त्रिकोण से छेद होता है।

यह सब देखते हुए, एक संपूर्ण दुनिया में, मैं वास्तव में एक समान चेहरे में सभी समरूप चेहरों को दोबारा जोड़ना चाहूंगा, और उसके बाद परिणामस्वरूप (बड़ा) चेहरे ठीक से त्रिभुज करें (या कुछ अन्य लाइब्रेरी जैसे कि इसे करने के लिए libtess का उपयोग करें)।

मैं ऐसा करने के लिए एक मार्ग की तलाश कर रहा हूं, अब मेरे पास समस्त समस्त त्रिकोण हैं जो एक साथ समूहबद्ध हैं। यह मुझे लगता है कि एक एल्गोरिदम होना चाहिए, जो सभी कोपोनार त्रिकोण के सभी किनारों को देखते हुए, उन सभी के परिधि को मिल सकता है इसके साथ मैं एक नए त्रिज्या चेहरे को उत्पन्न कर सकता हूं ताकि उन्हें मेरे मूल मेष में डालने के लिए त्रिकोण का एक नया सेट बनाने के लिए आकार गेटेमेट्री की तरह कुछ का उपयोग करके उन्हें बदल दिया जाए। अंतिम परिणाम यह सब लागू करने के बाद होगा, मैं सटीक ज्यामिति पर वापस लौटूंगा THREEjs BoxGemometry सीएसजी लाइब्रेरी द्वारा बसपा को रूपांतरण के बाद पहली जगह में बनाता है और उसके बाद एक जाल के लिए पुनःपरिवर्तन होता है।

यदि किसी दूसरे के पास इस दूसरे लक्ष्य को पूरा करने के सर्वोत्तम तरीकों पर कोई विचार है, तो कृपया टिप्पणी करें। अगर मुझे कुछ अच्छे तरीके से पता चला तो मैं यहां पोस्ट कर सकता हूं। अभी सबसे अच्छा विचार मेरे पास हैं:

आइडिया 1:

  1. उपरोक्त एल्गोरिथ्म से आस-पास के चेहरे के बीच सभी समस्त कक्षों के सेट में, मूल से सबसे ऊपर के शीर्ष को खोजें।
  2. उस किनारे को छोड़कर सभी किनारों को ढूंढें
  3. उस किनारे पर चलें जो कि मूल से एक वेक्टर से न्यूनतम कोण को उस शीर्ष के माध्यम से अगले शीर्ष पर पहुंचाता है।
  4. अगले शीर्ष पर, किनारे पर चलना जो अगले शीर्ष को अधिकतम कोण बनाता है। ( डॉट () और क्रॉस () का उपयोग करके सुनिश्चित करें कि आप सभी कोमलार चेहरे के सामान्य के सापेक्ष, एक कोण को सही तरीके से चुन रहे हैं)।
  5. बंद करो जब आप पहले शीर्ष पर पहुंचें। सिद्धांत रूप में आपने सभी चेहरे की परिधि (सिद्धांत में!) चलाया है

आइडिया 2 (रे कास्टिंग):

  1. ऊपर की एल्गोरिथ्म द्वारा प्राप्त समांतर चेहरे से अनोखे कॉपलैनार किनारों का एक संग्रह बनाएं
  2. ऊपर की एल्गोरिथ्म द्वारा पाया गया कपालीदार शिखर सेट में प्रत्येक शीर्ष से एक किरण को कास्ट करें, यह किसी भी समानांतर किनारे पर स्थित होता है
  3. यदि अन्य शीर्ष कोष्ठकों और / या किनारों के साथ चौराहों की संख्या अजीब होगी तो शीर्ष एक आंतरिक शिखर होगा। यदि ऐसा है, तो हम उस किनारे को त्याग कर सकते हैं जिसके साथ हम एक किरण डालते हैं, साथ ही साथ आंतरिक रूप से।
  4. अब कोई शेष शिखर चुनें। यह किसी भी किनारे पर चलना है (अब केवल दो होना चाहिए) किनारों के साथ मिलान करने वाले कोने (बेशक पिछले किनारे पर ट्रेसिंग नहीं करना) जारी रखें जब तक कि आप शुरू में शीर्ष पर वापस न जाएं। अब हमारे पास सभी समीपवर्ती चेहरे की परिधि होना चाहिए।

यह देखने के लिए कि सीएसजी लाइब्रेरी वास्तव में अत्यधिक जटिल चेहरे कैसे पैदा करता है, क्यूब मेष पर एक नज़र डालें, जब एक घटाव वाले क्षेत्र वास्तव में क्यूब को छेदते हैं:

जैसा कि आप देख सकते हैं, क्यूब पक्ष जो बूलियन ऑपरेशन से अप्रभावित होना चाहिए, उसके अंतर्गत आंतरिक त्रिकोण का एक टन होता है।

अंत में, इन गंदा कॉपलनर को खींचने का अंतिम परिणाम है लेकिन गलत सीमा-प्रतिनिधि जाल सतह नीचे एनिमेटेड जीआईफ़ में दिखाया गया है। आप देख सकते हैं कि क्यों जाल को पूरी तरह से गड़बड़ कर खींचने के लिए मैं जाल को सरल बनाना चाहता हूं।







geometry-surface