Hi guys, I have a scene where the player can move and look around using pointerlock controls. I would like to constrain its movements on X e Z dimensions (there are no constraints on Y because it is fixed).
To do that I’m going to use a simple algorithm to check if a point is inside a polygon (I don’t need any complex collision detection). The algorithm is the following:
function isInsidePoly(nvert, vertX, vertY, testX, testY) {
let res = false
let i, j;
for (i = 0, j = nvert - 1; i < nvert; j = i++) {
if ( ((vertY[i] > testY) !== (vertY[j] > testY) ) &&
(testX < (vertX[j] - vertX[i]) * (testY - vertY[i]) / (vertY[j] - vertY[i]) + vertX[i]) )
res = !res;
}
return res;
}
where:
nvert: number of polygon vertices.
vertX, vertY: arrays containing the x- and y-coordinates of the polygon’s vertices.
testX, testY: X- and Y-coordinate of the test point.
The algorithm works fine, however in order to work properly the polygon vertices must be provided in order of edges connection, not in a random order.
My problem is that I want to design the polygon topology on Blender and then import back in Threejs. Doing so, I’ve noticed that the vertices extracted from the imported BufferGeometry are not in the edge-connection order, thus the algorithm does not work.
My question: given a BufferGeometry of a polygon, how can I extract the vertices following the edge connection order (starting from any point)?
Hi!
Looks like THREE.EdgesGeometry() can do a part of the job for you
It returns an array of coordinates of vertices of external edges of a shape (in pairs):
Your part of job is to connect those pairs in correct order.
Something like that:
The answer on SO is not exactly what you need, but it’s very close and with some modification you can get a desired array of coordinates of the shape’s polygon.
Thank you very much, using EdgesGeometry was a good starting point! Unfortunately the edges connections does not follow any particular order and orientation when extracted from the geometry, so I needed to write a small function to reconstruct the correct order, but it is working fine now!
class HalfEdge {
constructor(){
this.twin = null
this.a = null
this.b = null
}
}
const edges = []
triangles.forEach(triangle=>{
triangle.forEach((vertex,vertexIndex)=>{
const edge = new HalfEdge()
edge.a = vertex
edge.b = triangle[(vertexIndex + 1) % 3 ]
edges.push(edge)
})
//now every triangle has 3 edges, we need to find which one doesnt have a twin
const edgeMap = {}
//initialize the map
vertices.forEach((v, vertexIndex) =>{
edgeMap[vertexIndex] = {}
})
//link the edges
edges.forEach( edge=>{
edgeMap[edge.a][edge.b] = edge
if(edgeMap[edge.b] && edgeMap[edge.b][edge.a] ) edge.twin = edgeMap[edge.b][edge.a]
})
//isolate the boundary edges
const boundaryEdges = edges.filter( edge=> edge.twin === null )
Now it gets a little bit tricky,since you need to connect these edges. If you write the next/prev connectivity, you can traverse these and extract the edge loops. Otherwise maybe something like this:
while(boundaryEdges.length){
const edge = boundaryEdges.pop()
const next = boundaryEdges.splice(boundaryEdges.findIndex(e=> e.a === edge.b ), 1)
edge.next = next
}
Following edge.next should give you a single loop, not connected at the end (wrapping).
